与 Voronoi 图算法混淆（财富的扫描线）
我正在实施 Voronoi 图来直观地找出地图中最近的位置。 现在我想仅在画布中使用整数坐标 (x,y) 来执行此操作。
问题是 - 我对这个算法真的很困惑。 我读了《计算几何》这本书，对《财富》算法的理论了解不多。 我现在真的很困惑。 当我要编码时，这对我来说似乎非常复杂。
请告诉我 voronoi 图的非常简单的实现（带有给定的坐标）。 请给我建议简单的java或python或方案代码，最好没有哈希，多线程，Delaunay Traingulation，花哨的颜色等。
是否可以使用Fortune的算法实现Voronoi图而无需多线程或哈希图？
I am implementing Voronoi diagram to find out the nearest location in a map visually. Right now I want to do this using integer coordinates (x,y) only in a canvas.
Problem is- I am really confused about this algorithm. I read the Computational Geometry book, few more theory on Fortune's algorithm. And I am really confused now. It seems very complex to me when I am going for coding.
Please advice me very simple implementation of voronoi diagram (with given coordinates). Please advice me simple java or python or scheme code preferably without- hash, multi-threading, Delaunay Traingulation, fancy colors etc.
Isn't it possible to implement Voronoi diagram using Fortune's algorithm without multithreading or hash map?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我使用《财富》原始论文的端口打开了一个 github 存储库。 《财富》的实施非常难以遵循，主要是由于他处理数据结构的方式。
这本书显得更加现代
《财富》杂志的原始论文需要阅读几遍。
肯·黄的 论文对算法的描述可以说比《财富》杂志原始论文中的算法更加清晰
Ken Wong 的演示 有很棒的幻灯片 (10, 11)，介绍如何处理站点和顶点
有一个 交互式 JavaScript 演示 (存档版本）您可以观看以帮助您可视化算法。
pdf (存档版本）也描述了该算法。
Steven Fortune 的原始实现位于他的主页上。
此 Stony Brook 站点列出了更多实现
Triangle 是“二维质量网格生成器和 Delaunay 三角测量器”。
有一个整个Atsuyuki Okabe、Barry Boots 等人编写的关于 Voronoi 图的“空间镶嵌概念和 Voronoi 图的应用”一书
I opened a github repository with a port of Fortune's original paper. Fortune's implementation was very tough to follow mostly due to how he handled data structures.
This book appears a lot more modern
Fortune's original paper requires a few reads.
Ken Wong's paper describes the algorithm with arguably more clarity than Fortune in the original paper
Ken Wong's presentation has great slides (10, 11) on how to process a site and a vertex
There is an interactive JavaScript demo (Archived version) you can watch to help you visualize the algorithm.
A pdf (Archived version) describes the algorithm as well.
Steven Fortune's original implementation is on his homepage.
This Stony Brook site lists more implementations
Triangle is "A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator."
There is an entire book called "Spatial Tesselations Concepts and Applications of Voronoi Diagrams" by Atsuyuki Okabe, Barry Boots et al on Voronoi diagrams
Voronoi 图只是一个图：不是数据结构或算法。 我认为它不适合寻找集合中最近的点。 构建图表不会改变问题的渐近复杂性，尽管它会使问题变得更复杂并且内存效率更低。 你最好将你的点放在四叉树或类似的东西中。 如果您正在寻找算法，那么您要解决的问题的名称是“空间索引”。 “最近点”是四叉树和其他空间索引解决的问题之一。
The Voronoi diagram is just a diagram: not a data structure or algorithm. I don't think it's suited to finding the nearest point in a set. Constructing the diagram would not change the asymptotic complexity of your problem, although it would make your problem more complicated and less memory efficient. You would be better off putting your points in a quadtree or something similar. If you're looking for algorithms, the name of the problem you're trying to solve is "spatial indexing". "Nearest point" is one of the problems solved by quadtrees and other spatial indexes.
看起来很复杂，因为它很复杂！ 你不需要哈希表或线程，但你需要一个优先级队列（通常作为堆实现，并且在 java 和 python 标准库中都可用）和一棵树，它可以让你在 O(log n) 中进行范围查询（标准库中的那些并不真正合适，因为你无法了解它们的内部结构；我建议实现 AA 树）。 而且算法本身仍然很复杂。
可以运行外部程序吗？ 如果是这样，我真的建议你把繁重的工作留给 QHull，它非常擅长 Voronoi 图。 可悲的是，比我们任何一个人都好得多。
It seems complicated because it is complicated! You don't need a hashtable or threads, but you will need a priority queue (usually implemented as a heap, and available in both the java and python standard libraries) and a tree which lets you do range queries in O(log n) (the ones in the standard libraries aren't really suitable because you can't get at their internals; i'd suggest implementing an AA tree). And the algorithm itself is still pretty hairy.
Can you run an external program? If so, i really suggest you leave the heavy lifting to QHull, which is very good at Voronoi diagrams. Much better than either of us will ever be, sadly.
去年我经常查看 Voronoi 图，我当然可以理解其中的混乱。 有一些 Voronoi 图生成算法的实现。 请参阅此页面，还有此处。 正如 twic 提到的，Qhull 确实值得一看 - MATLAB 使用它来生成 Voronoi 图和 Delaunay 三角剖分以及类似的有趣的东西。
I was looking at Voronoi diagrams quite a bit last year and I can certainly appreciate the confusion. There are a few implementations of Voronoi diagram generating algorithms around. See this page for a couple, and also here. As twic mentioned, Qhull is certainly worth looking at - MATLAB uses it to generate Voronoi diagrams and Delaunay triangulations and fun things like that.
这是 Ruby 和 C 语言的另一个实现，包括可视化：
http://github.com/abscondment/rubyvor/< /a>
Here is another implementation in Ruby and C, including visualization:
http://github.com/abscondment/rubyvor/
显然，《财富》的算法实施起来并不简单。 特别是如果您考虑数值稳健性问题时间表。 你没有说你想用什么编程语言来实现它。 如果是 C++，您可以在 Boost 中找到 Andriy Sydorchuk 所做的工作GSoC 2010项目框架：扫描线算法。 Andriy 的实现基于 Boost.Polygon 库。 Voronoi 实现和 Boost.Polygon 都依赖于整数坐标来提供数值鲁棒性。
BoostCon 视频讲座 平面上点、线段和多边形中轴的 Voronoi 图的扫描线算法 很好地解释了这个想法、问题和陷阱。
与此 Voronoi 项目相关的讨论相当多。 发生在 2010/2011 年的 Boost 邮件列表中。
Obviously, the Fortune's algorithm is not trivial to implement. Especially if you consider numerical robustness issues timeline. You don't say what programming language you want to use to implement it. In case it is C++, you can find the Andriy Sydorchuk's work done for Boost in frame of GSoC 2010 project: Sweepline Algorithm. Andriy's implementation is based on Boost.Polygon library. Both, the Voronoi implementation and the Boost.Polygon rely on integer coordinates in order to provide numerical robustness.
The BoostCon video lecture on Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane gives a very good explanation of the idea, problems and pitfalls.
Quite a lot of discussion related to this Voronoi project. happened in Boost mailing list in 2010/2011.