给定点集和 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

假设您有一个“点”类或结构，如果您为它们分配随机颜色，那么当您显示输出。

Answer 3

首先获取 Delaunay 三角剖分。 每个三角形外接圆的中心是 Voronoi 曲面细分的顶点（点）。 然后简单地连接相邻三角形的所有外接圆的中心即可导出镶嵌。 从维基百科来看，如下所示。

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

接下来，用直线将每个相邻三角形的外接圆中心连接起来获取镶嵌：

Answer 4

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

您可以通过查找每个三角形的三个垂直平分线的交点来计算该点。

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

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