给定点集和 Delaunay 三角剖分,如何导出 Voronoi 图?
-
01-07-2019 - |
题
我正在开发一款游戏,在其中创建一个随机的省份地图(风险或外交)。为了创建该地图,我首先生成一系列半随机点,然后计算这些点的 Delaunay 三角剖分。
完成此操作后,我现在希望创建一个点的 Voronoi 图,作为省边界的起点。此时我的数据(无双关语)由原始的一系列点和 Delaunay 三角形的集合组成。
我在网上看到了很多实现此目的的方法,但其中大多数都与 Delaunay 的派生方式有关。我很想找到一些不需要集成到 Delaunay 中,但可以单独基于数据工作的东西。如果做不到这一点,我正在寻找相对几何新手可以理解的东西,而不是最佳速度。谢谢!
解决方案
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 模式。
在尝试使用此线程作为我自己的类似问题的答案的来源后,我发现《财富》的算法(可能是因为它是最受欢迎的,因此记录最多)是最容易理解的。
维基百科关于《财富》算法的文章 保持 C、C# 和 Javascript 源代码的最新链接。他们都是一流的,并且都有漂亮的例子。
我很确定那个“三角形” http://www.cs.cmu.edu/~quake/triangle.html 可以生成voronoi
每个 Delaunay 三角形都包含 Voronoi 图的一个点。
您可以通过找到三个点的交集来计算这一点 垂直平分线 对于每个三角形。
您的 Voronoi 图将连接这组点,每个点与其最近的三个邻居。(每个邻居共享德劳内三角形的一条边)
您打算如何处理边缘情况?