与Voronoi图算法（财富的扫描线）相混淆

我正在执行Voronoi图来在视觉上查找地图中最近的位置。现在我只想在画布中使用整数坐标（x，y）来完成此操作。与Voronoi图算法（财富的扫描线）相混淆

问题是 - 我对这个算法非常困惑。我阅读了计算几何书，还没有更多关于财富算法的理论。我现在很困惑。当我正在进行编码时，对我来说似乎非常复杂。

请教我很简单的voronoi图的实现（给定坐标）。请指教我简单的Java或Python或计划代码，最好不使用散列，多线程，Delaunay Traingulation，花式颜色等。

使用Fortune算法不使用多线程或哈希映射可以实现Voronoi图吗？

2009-06-11 fireball003

Voronoi图只是一个图：不是数据结构或算法。我认为它不适合找到一组中最近的点。构建图表不会改变问题的渐近复杂性，尽管它会使问题更加复杂并且降低内存效率。你最好把你的观点放在四叉树或类似的东西上。如果你正在寻找算法，你试图解决的问题的名称是“空间索引”。 “最近点”是四叉树和其他空间索引解决的问题之一。

来源

2009-06-11 19:11:03

他试图描绘近邻视觉叠加地图上的Voronoi图，这样一方面可以一目了然其中X是最接近兴趣点见。 – erickson 2009-06-11 20:23:25

Voronoi图用于解决最近邻问题：http://en.wikipedia.org/wiki/Voronoi_diagram#Applications – 2011-11-15 17:28:54

Voronoi图_is_不只是一个图。它是一个_planar graph_（边不交叉的边），带有顶点和双向边。 – bobobobo 2013-06-17 19:23:15

看起来很复杂，因为它很复杂！您不需要散列表或线程，但您需要一个优先级队列（通常以堆的形式实现，并可在java和python标准库中使用）以及一个可让您在O（log n）中执行范围查询的树，（标准库中的不太合适，因为你不能在内部获得;我建议实现一个AA tree）。算法本身仍然非常多毛。

你可以运行一个外部程序吗？如果是这样的话，我真的建议你把重任提升到QHull，这对Voronoi图很好。可悲的是，比我们两个人都要好得多。

来源

2009-06-11 19:52:32

我明白你的意思。但我必须亲自去做评估。所以，我正在寻找一些可以研究和修改/添加到我的设计中的简单实现。 – fireball003 2009-06-11 20:03:23

去年我在看Voronoi图很多，我当然可以理解这种混乱。有一些Voronoi图生成算法的实现。一对夫妇参见this page，还有here。如上所述，Qhull当然值得研究 - MATLAB使用它来生成Voronoi图和Delaunay三角剖分以及类似的有趣事物。

来源

2009-06-12 12:53:04

这里是用Ruby和C另一种实现方式，其中包括可视化：

http://github.com/abscondment/rubyvor/

来源

2010-02-01 21:33:43

显然，财富的算法是不容易实现。特别是如果你的时间轴consider numerical robustness issues。你不会说你想用什么编程语言来实现它。如果是C++，可以找到Andriy Sydorchuk为Boost in frame of GSoC 2010项目完成的工作：Sweepline Algorithm。 Andriy的实现基于Boost.Polygon库。 Voronoi实现和Boost.Polygon都依赖整数坐标来提供数值稳健性。

关于Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane的BoostCon视频讲座给出了有关该想法，问题和陷阱的非常好的解释。

不少有关这个Voronoi项目的讨论。发生在2010/2011年的Boost邮件列表中。

来源

2011-10-27 13:34:32 mloskot

I opened a github repository与Fortune的原始纸张的港口。财富的实施非常艰难，主要是由于他如何处理数据结构。

This book出现了很多现代

Fortune's original paper需要几个读取。

Ken Wong's主要介绍与原文件比财富可以说是更清晰的算法

Ken Wong's presentation有很大的幻灯片（10，11）如何处理一个网站和一个顶点

有一个interactive JavaScript demo（ Archived version），您可以观看以帮助您查看算法。

A pdf也描述了该算法。

Steven Fortune's original implementation is on his homepage。