如何根据给定的点集和其Delaunay三角剖分推导出Voronoi图？

Question

我正在开发一个游戏，其中创建了一个省份的随机地图（类似于Risk或Diplomacy）。 为了创建该地图，我首先生成一系列半随机点，然后计算这些点的德劳内三角剖分。

完成这一步骤后，我现在希望创建一个沃罗诺伊图来作为省份边界的起点。此时我的数据包括原始一系列点和德劳内三角形的集合。

我已经在网上看到了很多方法来实现这个目标，但大多数都与如何获得德劳内三角形有关。 我希望找到一些不需要将其集成到德劳内三角剖分中的方法，而是仅基于数据本身进行处理。如果无法做到这一点，我希望找到一些相对容易理解的几何新手可懂的方法，而不是追求最佳速度。谢谢！

- Macguffin

Answer 1

沃罗诺伊图只是德劳内三角剖分的对偶图。

• 因此，沃罗诺伊图的边沿着德劳内三角剖分边的垂直平分线，因此计算这些线。
• 然后，通过找到相邻边的交点来计算沃罗诺伊图的顶点。
• 最后，边缘是你计算出的那些线段的子集，这些线段位于相应顶点之间。

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

- Adam Rosenfield

---

通过计算所有三角形的外心，并连接任意共享边的两个外心，您也可以找到双重（即，沃罗诺伊图）。 - batty

根据上述评论建议，我会分两步进行：

1. 计算每个 Delaunay 三角形的外心 -> 这些是 Voronoi 图的顶点。请参阅 http://en.wikipedia.org/wiki/Circumscribed_circle#Circumscribed_circles_of_triangles
2. 对于每条 Delaunay 边，计算一个 Voronoi 边：即连接相邻两个 Delaunay 三角形外心的线段。

- balint.miklos

如何处理外部的站点/三角形？ - Tomilov Anatoliy

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 图案。

- Richard Franks

---

这很好，但我不认为生成一个Voronoi图作为图像有任何用处。也许有吗？ - Tara

不是作为图像本身，而是我用它来进行程序化的基于瓦片的世界生成（其中每个瓦片由其所属的单元格确定）。 - PixelArtDragon

着色器大多数情况下使用这种方法（仅用于图形输出）。 - Trap

Answer 3

尝试使用此线程作为类似问题答案的来源后，我发现Fortune算法-很可能是最受欢迎和因此最有文献记录的算法-是最容易理解的。

Fortune算法的维基百科文章保持对C语言、C#和Javascript源代码的新链接。所有这些都是一流的，并附有漂亮的示例。

- Wray Bowling

Answer 4

你的Delaunay三角形中包含Voronoi图的一个单一点。

你可以通过找到每个三角形的三条垂直平分线的交点来计算这个点。

你的Voronoi图将连接这组点，每个点都有它最近的三个邻居。（每个邻居共享Delaunay三角形的一边）

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

- Arc the daft

---

请注意，尽管每个Delaunay三角形都对应一个Voronoi顶点，但该顶点可能位于三角形之外。在这里可以看到一个例子：http://www.mathopenref.com/trianglecircumcenter.html - balint.miklos

Answer 5

首先要获取 Delaunay 三角剖分。每个三角形外接圆的中心是 Voronoi 图案的顶点（点）。然后，只需连接所有相邻三角形的外接圆的中心即可得到图案。维基百科上如下所示。

首先，获取所有外接圆的中心（来自所有三角形）-即红色点：

接下来，将每个相邻三角形的外接圆心连接起来，以线条形式得到镶嵌图案：

- user0123456789