计算 3D 平面的 Voronoi 图 [英] Calculating a Voronoi diagram for planes in 3D
问题描述
是否有代码/库可以计算 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.
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 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.
Check out this website discussing and visualizing 3D voronoi diagrams:
http://www.wblut.com/2009/04/28/ooh-ooh-ooh-3d-voronoi/
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.
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.
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.
This is a graphic from Wikipedia visualizing both Delaunay and Voronoi diagrams:
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
这篇关于计算 3D 平面的 Voronoi 图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
