我正在实施 Voronoi 图以直观地找出地图中最近的位置。现在我只想在画布中使用整数坐标 (x,y) 来做到这一点。
问题是 - 我对这个算法真的很困惑。我读了计算几何书，关于财富算法的更多理论。我现在真的很困惑。当我要进行编码时，这对我来说似乎很复杂。
请建议我非常简单地实现 voronoi 图（具有给定坐标）。请建议我使用简单的 java 或 python 或方案代码，最好不要使用哈希、多线程、Delaunay Traingulation、花哨的颜色等。
在没有多线程或哈希映射的情况下，是否可以使用 Fortune 算法实现 Voronoi 图？
我打开了一个 github 存储库，其中包含 Fortune 的原始论文。Fortune 的实现非常难以遵循，主要是因为他处理数据结构的方式。
这本书看起来更现代
《财富》的原始论文需要读几遍。
Ken Wong 的论文对算法的描述可以说比原始论文中的财富更清晰
Ken Wong 的演示文稿有很棒的幻灯片 (10, 11) 关于如何处理站点和顶点
您可以观看一个交互式 JavaScript 演示（存档版本），以帮助您可视化算法。
这个石溪网站列出了更多的实现
Triangle是“二维质量网格生成器和 Delaunay 三角剖分器”。
Atsuyuki Okabe、Barry Boots 等人在 Voronoi 图上有一整本书，名为“Voronoi 图的空间镶嵌概念和应用”
Voronoi 图只是一个图：不是数据结构或算法。我认为它不适合在集合中找到最近的点。构建图表不会改变您的问题的渐近复杂性，尽管它会使您的问题更复杂且内存效率更低。你最好把你的点放在四叉树或类似的东西上。如果您正在寻找算法，那么您要解决的问题的名称是“空间索引”。“最近点”是四叉树和其他空间索引解决的问题之一。
这是 Ruby 和 C 中的另一个实现，包括可视化：
显然，Fortune 的算法实现起来并非易事。特别是如果您考虑数值稳健性问题时间线。你没有说你想用什么编程语言来实现它。如果是 C++，您可以在 GSoC 2010项目的框架中找到 Andriy Sydorchuk 为 Boost 所做的工作：Sweepline Algorithm。Andriy 的实现基于Boost.Polygon库。Voronoi 实现和 Boost.Polygon 都依赖整数坐标来提供数值鲁棒性。
关于平面中点、线段和多边形中轴的 Voronoi 图的扫描线算法的 BoostCon 视频讲座很好地解释了这个想法、问题和陷阱。
与此 Voronoi 项目相关的讨论很多。2010/2011 年发生在 Boost 邮件列表中。