Calculating a Voronoi diagram for planes in 3D

Question

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

Answer 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