Calculating a Voronoi diagram for planes in 3D

问题:

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.!

回答1:

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

回答2:

Bowyer-Watson is usually the recommended algorithm. The problem with most papers/algorithms is that they don't address the tricky situations that arise when points are close to each other in space (so the tetrahedrons are thin), when voronoi cells should end up mostly flat and when multiple points are on the same sphere. Add to that the numerical complexity of dealing with inaccurate math and rounding and you have yourself a recipe for endless debugging. My recommendation is that you filter your data first if that's acceptable. Otherwise, you will end up coding an enormous amount of special cases in your algorithm.

A while ago, there was also a Japanese paper that claimed to have a different approach for resolving these situations by starting from the delaunay triangulation and working out the voronoi cells from that, but it too was flawed. It must be nice to be a researcher, coming up with the broad lines of algorithms and letting the research assistants worry about the details...