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

完成此操作后，我现在正在寻找创建这些点的Voronoi图，以作为省边界的起点。我目前的数据(无双关)包括原始的一系列点和Delaunay三角形的集合。

我已经在网上看到了许多方法，但是大多数方法都与Delaunay的派生方式有关。我很想找到一些不需要集成到Delaunay中但可以仅基于数据工作的东西。未能做到这一点，我正在寻找相对于新几何学而不是最佳速度可以理解的东西。谢谢！

解决方案

回答

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

回答

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

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

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

回答

如果不考虑最佳速度，则以下伪代码将很难生成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模式。

回答

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

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

Voronoi图将连接这组点，每个点与它的最近三个邻居相邻。 (每个邻居共享Delaunay三角形的一侧)

我们如何计划应对极端情况？