3d - 计算 3D 平面的 Voronoi 图

Question

是否有代码/库可以计算 3D 平面(平行四边形)的 Voronoi 图？我检查了 Qhull，它似乎只能处理点，在其示例中，Voro++ 适用于不同大小的球体，但我找不到任何多边形。

在这张图片中 (sample planes in 3d)平行四边形是 3D 的，因为它们有厚度，但在这种情况下，厚度将为零。!

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 图:

黑线是德劳内三角剖分。棕色线与此正交，形成 Voronoi 图。 Delaunay 三角剖分可用于各种很酷的可视化事物:计算凸包、voronoi 图和 alpha 形状:http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html