有没有code /库，可以计算出在3D平面（平行四边形）Voronoi图？我检查Qhull，似乎只能用点工作，在其示例Voro ++可以与球的大小不同，但我无法找到任何的多边形。

Is there a code/library that can calculate a Voronoi diagram for planes (parallelograms) in 3D? I checked Qhull and it seems it can only work with points, in its examples Voro++ works with different size of spheres but I couldn't find anything for polygons.

在此图像（在3D样品架）的平行四边形是3D，因为他们有的厚度，但在这种情况下，厚度将为零。！

In this image (sample planes in 3d) the parallelograms are 3D since they have a thickness, but in this case the thickness will be zero.!

推荐答案

Voronoi单元不是平行四边形。你是通过你发布的形象在这里混淆。 Voronoi单元的边界是被分离的各个装置中的超平面的部分。

Voronoi cells are not parallelograms. You are confused here by the image you posted. Voronoi cell borders are parts of the hyperplanes that are separating the individual means.

看看这个网站讨论和可视化3D的Voronoi图：

Check out this website discussing and visualizing 3D voronoi diagrams:

http://www.wblut.com / 2009/04/28 /哦 - 哦 - 哦 - 3D-Voronoi图/

为了计算Voronoi单元中，常用的方法是先构建Delaunay三角。有许多算法，为此在2D，而在三维它得到显著更加复杂。但是，你应该还是能够找到的东西。 qhull 也许是正确的路要走。

In order to compute the voronoi cells, the common way is to first build the Delaunay Triangulation. There are a number of algorithms to do this in 2D, while in 3D it gets significantly more complex. But you should still be able to find something. qhull might be the proper way to go.

当你有德劳内三角测量，计算各tetraeder的中心。这些都是你需要绘制多边形的角落。对于Delaunay三角任何边缘，绘制多边形连接相邻的中心。这应该是一个超平面。 现在，所有你需要做的还绘制超平面的边缘是凸包的一部分。为此，您需要继续，你应该已经从内到外的无限的超平面。

When you have the Delaunay triangulation, compute the center of each tetraeder. These are the corners of the polygons that you need to draw. For any edge in the Delaunay triangulation, draw a polygon connecting the adjacent centers. This should be a hyperplane. Now all you need to do is also draw the Hyperplanes for edges that are part of the convex hull. For this you need to continue the hyperplanes that you should already have from the inside to the infinite outside.

我强烈建议以启动二维第一。一旦你有一个工作code为2D，请参阅如何在3D这样做。这已经是美元的2D p $ ptty的技巧，如果你希望它是快速的。

I strongly recommend to start with 2d first. Once you have a working code for 2D, see how to do the same in 3D. This is already pretty tricky in 2D if you want it to be fast.

这是维基百科的图形可视化既德劳和Voronoi图：

This is a graphic from Wikipedia visualizing both Delaunay and Voronoi diagrams:

中的黑线是Delaunay三角。的棕色系是正交于此，并且形成所述Voronoi图。 Delaunay三角可用于各种凉爽可视化的东西：计算所述凸包的Voronoi图和阿尔法形状：http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

The black lines are the Delaunay Triangulation. The brown lines are orthogonal to this, and form the Voronoi diagram. Delaunay triangulation can be used for various cool visualization things: computing the convex hull, the voronoi diagrams and alpha shapes: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html