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

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

完成此操作后，我现在正在寻找创建这些点的Voronoi图以用作省边界的起点。我目前的数据(无双关)包括原始的一系列点和Delaunay三角形的集合。

我已经在网上看到了许多方法，但是大多数方法都与Delaunay的派生方式有关。我很想找到不需要集成到Delaunay中但可以仅基于数据工作的东西。未能做到这一点，我正在寻找相对于新几何学而不是最佳速度可以理解的东西。谢谢!

最佳答案

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

因此，Voronoi图的边缘沿着Delaunay三角剖分的边缘的垂直平分线，因此计算这些线。

然后，通过查找相邻边的交点来计算Voronoi图的顶点。

最后，边就是位于相应顶点之间的所计算线的子集。

请注意，确切的代码取决于您在两个图中使用的内部表示形式。

关于geometry - 给定点集和Delaunay三角剖分，如何得出Voronoi图？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/85275/