在三维空间中计算平面的沃罗诺伊图

Question

有没有一种可以计算三维平面（平行四边形）的 Voronoi 图的代码/库？我检查了 Qhull，似乎它只能处理点，在其示例中，Voro++ 使用不同大小的球体，但我找不到多边形的任何东西。

在这张图片(3D 中的样本平面)中，平行四边形是 3D 的，因为它们有一个厚度，但在这种情况下，厚度将为零。

- zamazalotta

Answer 1

Voronoi单元不是平行四边形。您被您发布的图像所迷惑了。Voronoi单元的边界是分离各个平均值的超平面的一部分。请查看这个讨论和可视化3D Voronoi图的网站：

http://www.wblut.com/2009/04/28/ooh-ooh-ooh-3d-voronoi/

为了计算Voronoi图形，常见的方法是先构建Delaunay三角剖分。在2D中有许多算法可以做到这一点，而在3D中则更加复杂。但你仍然应该能够找到一些方法。qhull可能是正确的选择。

当您拥有Delaunay三角剖分时，请计算每个四面体的中心点。这些是您需要绘制的多边形的角落。对于Delaunay三角剖分中的任何边缘，请绘制连接相邻中心的多边形。这应该是一个超平面。 现在，您还需要绘制凸壳的一部分的边缘的超平面。为此，您需要将已经从内部到无限外部的超平面继续延伸。

我强烈建议先从2D开始。一旦您有了2D的工作代码，请看看如何在3D中执行相同的操作。如果您希望它快速实现，即使在2D中，这已经非常棘手了。

这是来自维基百科的图形，可视化Delaunay和Voronoi图： 黑线是Delaunay三角剖分。棕色线垂直于此，形成Voronoi图。Delaunay三角剖分可用于各种酷炫的可视化操作：计算凸包、Voronoi图和alpha形状: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

- Has QUIT--Anony-Mousse

---

我认为我的问题不够清楚。让我尝试澄清一下。当对点进行 Voronoi 图时，您得到的单元是最接近某个点的区域。我想要做的是对这些平行四边形进行 Voronoi，使得每个 Voronoi 单元定义了其对应平行四边形的最接近区域。我可以想出如何在2D中完成它（将点定义为矩形的顶点，然后将所有4个相加以获得总区域等等...），但是3D非常复杂，因此我无法信任自己。这就是为什么我正在寻找经过验证/测试的代码/论文/算法的原因。 - zamazalotta

即使在二维中，角落也不起作用。我可以轻松地画出一种情况，在这种情况下，当您只取角落时会失败。假设R1是0,0 0,1 1,1 1,0，而R2是-50,50 50,-51 50,-52 -51,49。您需要的是每对物体边缘上最接近的点集。当一组边/平面平行时，您需要最小值和最大值（在三维中，四对）。 - Has QUIT--Anony-Mousse

https://winterbloed.be/2009/04/28/ooh-ooh-ooh-3d-voronoi/是一个失效的链接，遗憾地。 - undefined

Answer 2

Bowyer-Watson通常是推荐的算法。大多数论文/算法的问题在于它们没有解决空间中点彼此靠近（因此四面体很薄）、Voronoi单元应该大多数是平坦的以及多个点位于同一球体时出现的棘手情况。加上处理不准确的数学和舍入的数字复杂性，你就会发现自己陷入了无休止的调试之中。

我的建议是，如果可以的话，首先过滤数据。否则，你将不得不在算法中编写大量特殊情况。

一段时间以前，还有一篇日本论文声称采用不同的方法来解决这些情况，即从Delaunay三角剖分开始，然后从中计算出Voronoi单元，但它也存在缺陷。

作为研究人员，提出算法的基本思路，让研究助理们去担心细节，这肯定很不错...

- JD. Bertron