首页 / 知识

关于几何：如何给出给定点集和Delaunay三角剖分的Voronoi图？

2023-04-16 17:03:00

How do I derive a Voronoi diagram given its point set and its Delaunay triangulation?

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

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

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

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

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

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

如果不考虑最佳速度，则以下伪代码将很难生成Voronoi图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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模式。

在尝试使用该线程作为回答我自己的类似问题的答案的源之后，我发现Fortune的算法(可能是因为它最受欢迎，因此文档最多)是最容易理解的算法。

Wikipedia上有关Fortune算法的文章保留了指向C，C＃和Javascript源代码的最新链接。所有这些都是一流的，并带有精美的例子。

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

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

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

您如何应对极端情况？

点集三角剖分风险给定