不使用Fortune算法生成Voronoi图

我希望能在C＃中创建一个Voronoi风景。我查看了许多Unity Project文件，但它们都实现了Fortune的算法，这完全在我的头上。有没有其他生成Voronoi图的方法（这更容易理解）？性能下降对我来说是完全没问题的。非常感谢！不使用Fortune算法生成Voronoi图

旁注：由于我在团结工作，需要从生成Voronoi图的2D/3D网格，每个像素的距离检查将无法正常工作：（关于第二个想法，也许我可以用一个二维的Vector2s阵列，而不是像素，它们在x轴和z轴上有1.0个单位的间隔

来源

2017-07-27 Komm

所以，做你真正需要的几何精确Voronoi图或者是像素近似正常，因为你提到的‘风景’？ – gue

的近似绝对是好的。虽然这将是不错的顶点或边的数据，这样我就可以用它来生成一个网格。谢谢GUE！ – Komm

的可能的复制[最简单的Voronoi图的算法来实现？（https://stackoverflow.com/questions/973094/easiest-algorithm-的-维诺 - 图对实施） – Bytemain

有一种非常简单的方法可以创建一个近似的Voronoi图VD对于每个需要在VD中定义一个单元的s （二维平面），你在一个圆锥体的s处以恒定的斜率和一定的高度作为中心，然后你从上面看到圆锥体（所有尖峰都是可见的）景观。满足（投影到2D平面）是（近似的）Voronoi图。

（Image Source）

当您在意见中的要求，以获得实际的边缘数据似乎不那么容易。但是可能有一些图形例程通过相交圆锥来生成它们。

另一种方法是计算给定点集的Delaunay三角剖分。这个related post中引用了一些实现（也提到了简单的近似值）。然后你计算你的三角测量的双重图，你就得到了Voronoi图。（双图表示对于三角剖分中的每个边缘AB的每一个边缘，VD中存在一个边缘，平分两个顶点A和B之间的空间，并且对于每个三角形，在双边相遇的VD处存在顶点。） Othwerwise还有许多C# Voronoi实现：Unity-delaunay，但正如你所提到的使用Fortune方法。

如果你想自己的代码都可能在O(n^2)时间计算点用蛮力三角为n点。然后应用圈内测试和edge flips。也就是说，对于每个三角形t(abc)创建一个由t三个顶点定义的圆C。然后检查你的点的另一点d是否在C内。如果是，则翻转t中的边缘，并在d的三角形中形成边缘。该翻转完成，直到所有三角形满足空圆属性（德劳内条件）。再次以蛮力将需要O(n^2)时间。然后你可以计算上面提到的双图。

（Image Source）

来源

2017-07-27 06:38:51 gue

这是如何工作 – Bytemain

@gui：你是一个博士哇 – Bytemain

：？！？它是否也工作，当你从底部看 – Bytemain

“最简单的那蛮力方法：对于在输出的每个像素，遍历所有的点，计算距离，使用最接近慢的可以，但很简单，如果表现不重要，它就可以完成这项工作。“

[1] Easiest algorithm of Voronoi diagram to implement?

来源

2017-07-27 07:18:24 Bytemain

引用的算法是鲍耶 - 沃森这无关你的答案描述像素近似。 – gue

@gue：你在说什么？你是博士吗？哇？ – Bytemain

我不是博士学位。我看到的错误，你所使用的裁判是不是你引用一个，你引用（https://stackoverflow.com/a/10848478/4462067），但引用（https://stackoverflow.com/questions/973094/easiest-算法-的-沃罗诺伊-图对实施/ 18084287＃18084287）。那是我的困惑来自的地方。 – gue

不使用Fortune算法生成Voronoi图

回答

相关问题