不使用Fortune算法生成Voronoi图

Question

我希望创造一个沃罗诺伊景观在统一在C#。我看了很多Unity文件，但它们都实现了“财富”的算法，这完全超出了我的想象。是否还有其他方法来生成Voronoi图(更容易理解)？缓慢的表演对我来说是完全没有问题的。非常感谢！

Sidenote:由于我在统一中工作，需要从Voronoi图生成2D/3D网格，所以每像素距离检查不起作用:，(再考虑一下，也许我可以使用一个2D的Vector2s数组，而不是像素，在x和z轴上间隔为1.0单位)。

Answer 1

有一个非常简单的方法来创建一个近似Voronoi图VD。对于每一个应该在VD (2D平面)中定义一个单元的s，您可以在s上以一个恒定的斜率和一定的高度为中心。然后你从上面看那一片圆锥体(在那里所有的尖峰都是可见的)。不同的锥相交的边界(投影到二维平面)是(近似的) Voronoi图。

​

​

(像源)

正如您在注释中所要求的那样，获取实际的边缘数据似乎并不容易。但是可以有一些图形例程，通过相交锥来生成它们。

另一种方法是计算给定点集的Delaunay三角剖分。在这个相关员额中引用了一些实现(也提到了简单的近似)。然后计算出三角剖分的对偶图，然后得到Voronoi图。(对偶图意味着，对于三角剖分中的每一个边AB，在VD中存在一个边，将两个顶点A和B之间的空间平分，对于每个三角形，在VD中存在一个顶点，其中对偶边相交。)当然，也有许多C# Voronoi实现：统一-德拉奈，但正如您所提到的，使用了“财富”方法。

如果你想自己编码所有的东西，你可以用蛮力计算n点在O(n^2)时间的三角剖分。然后应用圆周测试和边翻转.也就是说，对于每个三角形，t(abc)创建一个由t的三个顶点定义的圆C。然后检查是否有另一个点d设置在C内。如果是这样的话，然后翻转在t中的边，并与d一起在三角形中形成一个边。这种翻转直到所有三角形满足空圆属性(Delaunay条件)为止。再一次用野蛮的力量将花费O(n^2)的时间。然后，您可以像上面提到的那样计算对偶图。

​

​

(像源)

Answer 2

“最简单?这是蛮力法:对于输出中的每一个像素，迭代所有点，计算距离，使用最接近的距离。尽管速度慢，但非常简单。如果性能不重要，它就能完成任务。”

1