如何根据其点集和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模式.