鉴于其点集及其 Delaunay 三角剖分，我如何推导出 Voronoi 图? [英] How do I derive a Voronoi diagram given its point set and its Delaunay triangulation?

问题描述

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

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.

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

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.

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

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!

推荐答案

Voronoi 图就是 Delaunay 三角剖分的对偶图.

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

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

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

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

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