不使用 Fortune 算法生成 Voronoi 图
Generate Voronoi diagram without using Fortune's algorithm
我希望用 C# 在 Unity 中创建一个 Voronoi 景观。看了很多Unity Project的文件，都实现了Fortune的算法，完全看不懂。有没有其他生成Voronoi图的方法（更容易理解）？
性能缓慢对我来说完全没问题。
非常感谢！
旁注：由于我在 Unity 中工作并且需要从 Voronoi 图生成 2D/3D 网格，因此每像素距离检查将不起作用:,(
再想一想，也许我可以使用 Vector2 的二维数组而不是像素，它们在 x 轴和 z 轴上间隔 1.0 个单位。
有一种非常简单的方法可以创建近似的 Voronoi 图 VD。对于应在 VD（2D 平面）中定义单元格的每个站点 s，您将圆锥体置于 s 的中心，具有恒定的斜率和一定的高度。然后你从上面看锥体景观（所有尖峰都可见）。不同锥体相遇的边界（投影到 2D 平面）是（近似的）Voronoi 图。
正如您在评论中所要求的那样，要获得实际的边缘数据似乎并不容易。但是可以有一些图形例程通过使锥体相交来生成它们。
另一种方法是计算给定点集的 Delaunay 三角剖分。 related post (also simple approximations are mentioned). Then you compute the dual graph of your triangulation and you have the Voronoi diagram. (Dual graph means that for every for every edge AB in the triangulation there exists an edge in the VD bisecting the space between the two vertices A and B, and for every triangle there exists a vertex in the VD where the dual edges meet.) Othwerwise there are also many C# Voronoi implementations around: Unity-delaunay 中引用了一些实现，但正如您提到的使用 Fortune 方法。
如果您想自己编写所有代码，您可以在 O(n^2) 时间内用蛮力计算点的三角剖分 n 个点。然后应用圆内测试和 edge flips。也就是说，对于每个三角形 t(abc) 创建一个由 t 的三个顶点定义的圆 C。然后检查 C 内是否有你的点集的另一个点 d。如果是这样，则翻转 t 中的边，并在 d 中形成三角形中的边。完成此翻转，直到所有三角形都满足空圆 属性（Delaunay 条件）。再次使用蛮力将花费 O(n^2) 时间。然后你可以计算上面提到的对偶图。
"Easiest? That's the brute-force approach: For each pixel in your output, iterate through all points, compute distance, use the closest. Slow as can be, but very simple. If performance isn't important, it does the job."
[1] Easiest algorithm of Voronoi diagram to implement?
我希望用 C# 在 Unity 中创建一个 Voronoi 景观。看了很多Unity Project的文件，都实现了Fortune的算法，完全看不懂。有没有其他生成Voronoi图的方法（更容易理解）？ 性能缓慢对我来说完全没问题。 非常感谢！
旁注：由于我在 Unity 中工作并且需要从 Voronoi 图生成 2D/3D 网格，因此每像素距离检查将不起作用:,( 再想一想，也许我可以使用 Vector2 的二维数组而不是像素，它们在 x 轴和 z 轴上间隔 1.0 个单位。
有一种非常简单的方法可以创建近似的 Voronoi 图 VD。对于应在 VD（2D 平面）中定义单元格的每个站点 s，您将圆锥体置于 s 的中心，具有恒定的斜率和一定的高度。然后你从上面看锥体景观（所有尖峰都可见）。不同锥体相遇的边界（投影到 2D 平面）是（近似的）Voronoi 图。
正如您在评论中所要求的那样，要获得实际的边缘数据似乎并不容易。但是可以有一些图形例程通过使锥体相交来生成它们。
另一种方法是计算给定点集的 Delaunay 三角剖分。 related post (also simple approximations are mentioned). Then you compute the dual graph of your triangulation and you have the Voronoi diagram. (Dual graph means that for every for every edge AB in the triangulation there exists an edge in the VD bisecting the space between the two vertices A and B, and for every triangle there exists a vertex in the VD where the dual edges meet.) Othwerwise there are also many C# Voronoi implementations around: Unity-delaunay 中引用了一些实现，但正如您提到的使用 Fortune 方法。
如果您想自己编写所有代码，您可以在 O(n^2) 时间内用蛮力计算点的三角剖分 n 个点。然后应用圆内测试和 edge flips。也就是说，对于每个三角形 t(abc) 创建一个由 t 的三个顶点定义的圆 C。然后检查 C 内是否有你的点集的另一个点 d。如果是这样，则翻转 t 中的边，并在 d 中形成三角形中的边。完成此翻转，直到所有三角形都满足空圆 属性（Delaunay 条件）。再次使用蛮力将花费 O(n^2) 时间。然后你可以计算上面提到的对偶图。
"Easiest? That's the brute-force approach: For each pixel in your output, iterate through all points, compute distance, use the closest. Slow as can be, but very simple. If performance isn't important, it does the job."
[1] Easiest algorithm of Voronoi diagram to implement?