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

Question

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

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

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

Answer 1

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

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

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

Answer 2

如果不考虑最佳速度，以下伪代码将以困难的方式生成 Voronoi 图：

for yloop = 0 to height-1
  for xloop = 0 to width-1

    // Generate maximal value
    closest_distance = width * height

    for point = 0 to number_of_points-1
      // calls function to calc distance
      point_distance = distance(point, xloop, yloop)

      if point_distance < closest_distance
        closest_point = point
      end if
    next

  // place result in array of point types
  points[xloop, yloop] = point

  next
next

假设您有一个“点”类或结构，如果您为它们分配随机颜色，那么在显示输出时您将看到熟悉的 voronoi 模式。

Answer 3

在尝试使用此线程作为我自己的类似问题的答案的来源后，我发现《财富》的算法（可能是因为它是最受欢迎的，因此记录最多）是最容易理解的。

维基百科关于《财富》算法的文章 保持 C、C# 和 Javascript 源代码的最新链接。他们都是一流的，并且都有漂亮的例子。

Answer 4

我很确定那个“三角形” http://www.cs.cmu.edu/~quake/triangle.html 可以生成voronoi

Answer 5

每个 Delaunay 三角形都包含 Voronoi 图的一个点。

您可以通过找到三个点的交集来计算这一点 垂直平分线 对于每个三角形。

您的 Voronoi 图将连接这组点，每个点与其最近的三个邻居。（每个邻居共享德劳内三角形的一条边）

您打算如何处理边缘情况？