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

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

完成后,我现在正在寻找创建点的Voronoi图表作为省边界的起点.此时我的数据(没有双关语)由原始的点系列和Delaunay三角形的集合组成.

我已经在网上看到过很多方法可以做到这一点,但是大多数方法都与Delaunay的衍生方式有关.我很想找到一些不需要集成到Delaunay的东西,但可以单独根据数据工作.如果做不到这一点,我正在寻找相对几何新手可以理解的东西,而不是最佳速度.谢谢!

1> Adam Rosenfi..：

---

Voronoi图只是Delaunay三角剖分的双重图.

因此,Voronoi图的边缘沿着Delaunay三角剖分边缘的垂直平分线,因此计算这些线.

然后,通过找到相邻边的交点来计算Voronoi图的顶点.

最后,边缘是您计算的线的子集,它们位于相应的顶点之间.

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

---

您还可以通过计算所有三角形的圆周,并连接任意两个三角形共享边缘的圆周来找到双重(即Voronoi图).

---

正如上面的评论中所建议的,我将分两步完成:1.计算每个Delaunay三角形的外心 - >这些是Voronoi顶点.见http://en.wikipedia.org/wiki/Circumscribed_circle#Circumscribed_circles_of_triangles 2.对于每德洛奈边缘,计算维诺边缘:段连接两个相邻的德洛奈三角形的外心.

---

@ balint.miklos如何处理外部网站/三角形？

2> Alexandra Fr..：

---

如果不考虑最佳速度,则以下伪代码将以困难的方式生成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模式.