与Voronoi图算法混淆(Fortune的扫描线)

Question

我正在实现Voronoi图,以便在视觉上找出地图中最近的位置.现在我想只在画布中使用整数坐标(x,y)来做这个.

问题是 - 我对这个算法感到很困惑.我阅读了计算几何书,关于财富算法的更多理论.我现在真的很困惑.当我要编码时,对我来说似乎非常复杂.

请建议我非常简单地实现voronoi图(使用给定的坐标).请建议我简单的java或python或方案代码,最好没有哈希,多线程,Delaunay Traingulation,花哨的颜色等.

如果没有多线程或哈希映射,是不是可以使用Fortune算法实现Voronoi图？

Answer 1

我打开了一个带有Fortune原始论文端口的github存储库.由于他处理数据结构的方式,Fortune的实施非常难以实现.

这本书看起来更现代

"财富"杂志的原始论文需要一些阅读.

Ken Wong的论文在原始论文中描述了比Fortune更清晰的算法

Ken Wong的演讲有很多关于如何处理网站和顶点的幻灯片(10,11)

有一个互动的JavaScript演示(封存版本),你可以看以帮助您直观的算法.

一个PDF描述了算法的为好.

Steven Fortune最初的实施是在他的主页上.

这个Stony Brook站点列出了更多实现

三角形是"二维质量网格生成器和Delaunay三角形".

Voronoi图上有一本完整的书

Answer 2

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