geometry - 给定点集和 Delaunay 三角剖分，如何导出 Voronoi 图？

Question

我正在开发一款游戏，在其中创建一个随机的省份 map (类似于《风险》或《外交》)。为了创建该 map ，我首先生成一系列半随机点，然后计算这些点的 Delaunay 三角剖分。

完成此操作后，我现在希望创建一个点的 Voronoi 图，作为省边界的起点。此时我的数据(无双关语)由原始的一系列点和 Delaunay 三角形的集合组成。

我在网上看到了很多实现此目的的方法，但其中大多数都与 Delaunay 的派生方式有关。我很想找到一些不需要集成到 Delaunay 中，但可以单独基于数据工作的东西。如果做不到这一点，我正在寻找相对几何新手可以理解的东西，而不是最佳速度。谢谢!

Answer 1

Voronoi 图只是 Delaunay 三角剖分的对偶图。

• 因此，Voronoi 图的边缘沿着 Delaunay 三角剖分的边缘的垂直平分线，因此请计算这些线。
• 然后，通过查找相邻边的交点来计算 Voronoi 图的顶点。
• 最后，边是您计算的位于相应顶点之间的线的子集。

请注意，确切的代码取决于您为这两个图表使用的内部表示。