给定点集和Delaunay三角剖分，如何导出Voronoi图？ [英] How do I derive a Voronoi diagram given its point set and its Delaunay triangulation?

问题描述

我正在制作一个游戏，在那里我创建了一个随机的省份地图（一个风险或外交）。为了创建该地图，我首先生成一系列半随机点，然后计算这些点的Delaunay三角剖分。

完成这些工作后，我现在正在创建一个Voronoi图表作为省边界的出发点。我在这一点上的数据（没有双关意图）由原始系列的点和Delaunay三角形集合组成。

我见过很多方法可以做这在网络上，但其中大部分都与德劳内派生方式有关。我很想找到一些不需要整合到德劳内的东西，但可以单独依据数据进行工作。如果不这样做，我正在寻找相对几何新手可以理解的东西，而不是最佳速度。谢谢！

解决方案

Voronoi图只是Delaunay三角剖分的双重图。因此，Voronoi图的边沿沿着Delaunay三角剖分边缘的垂直平分线，因此计算这些线。然后，通过查找相邻边的交点来计算Voronoi图的顶点。

最后，边是那些位于相应顶点之间的线的子集。

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

I'm working on a game where I create a random map of provinces (a la Risk or Diplomacy). To create that map, I'm first generating a series of semi-random points, then figuring the Delaunay triangulations of those points.

With that done, I am now looking to create a Voronoi diagram of the points to serve as a starting point for the province borders. My data at this point (no pun intended) consists of the original series of points and a collection of the Delaunay triangles.

I've seen a number of ways to do this on the web, but most of them are tied up with how the Delaunay was derived. I'd love to find something that doesn't need to be integrated to the Delaunay, but can work based off the data alone. Failing that, I'm looking for something comprehensible to a relative geometry newbie, as opposed to optimal speed. Thanks!

解决方案

The Voronoi diagram is just the dual graph of the Delaunay triangulation.

• So, the edges of the Voronoi diagram are along the perpendicular bisectors of the edges of the Delaunay triangulation, so compute those lines.
• Then, compute the vertices of the Voronoi diagram by finding the intersections of adjacent edges.
• Finally, the edges are then the subsets of the lines you computed which lie between the corresponding vertices.

Note that the exact code depends on the internal representation you're using for the two diagrams.

这篇关于给定点集和Delaunay三角剖分，如何导出Voronoi图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！