30

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

完成后，我现在正在寻找创建点的 Voronoi 图，作为省边界的起点。我此时的数据（不是双关语）由原始的一系列点和 Delaunay 三角形的集合组成。

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

4

4 回答 4

20

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

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

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

于 2008-09-17T16:59:59.000 回答
9

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

于 2008-09-17T17:13:42.150 回答
2

在尝试使用该线程作为我自己类似问题的答案的来源之后，我发现 Fortune 的算法——可能是因为它是最流行的并且因此记录最多的——是最容易理解的。

关于 Fortune 算法的 Wikipedia 文章保留了指向 C、C# 和 Javascript 源代码的新链接。他们都是一流的，并带有漂亮的例子。

于 2012-10-02T14:58:15.200 回答
0

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

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

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

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

于 2008-09-17T17:14:04.707 回答