Computing a Voronoi diagram for planes in 3D

Question

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

In this image (samples of planes in 3d) 3D parallelograms, because 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. The borders of a Voronoi cell are parts of hyperplanes that share individual means.

Check out this site for a discussion and visualization of voronoi 3D charts:

http://www.wblut.com/2009/04/28/ooh-ooh-ooh-3d-voronoi/

To compute voronoi cells, a general way is to first build a Delaunay triangulation. In 2D, there are a number of algorithms, while in 3D it becomes much more complex. But you still have to find something. qhull may be the right way.

When you have Delaunay triangulation, calculate the center of each tetrahedron. These are the corners of the polygons to draw. For any edge of the Delaunay triangulation, draw a polygon connecting the neighboring centers. It must be a hyperplane. Now all you have to do is also draw hyperplanes for the edges that are part of the convex hull. To do this, you need to continue the hyperplanes, which you should already have from the inside, to the infinite outer.

I highly recommend starting with 2d first. When you have 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 Wikipedia graphic depicting the Delaunay and Voronoi diagrams:

Black lines are Delaunay triangulation. The brown lines are orthogonal to this and form a Voronoi diagram. Delaunay triangulation can be used for various interesting visuals: calculating a convex hull, raven diagrams and alpha forms: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

Answer 2

Boyer-Watson is usually the recommended algorithm. The problem with most works / algorithms is that they do not affect complex situations that arise when points are close to each other in space (so the tetrahedra are thin), when voronoi cells should be mostly flat and when several points are on one same sphere. Add to this the numerical complexity of working with inaccurate math and rounding, and you have a recipe for endless debugging. My recommendation is that you filter your data first, if appropriate. Otherwise, you will end up coding a huge number of special cases in your algorithm.

Some time ago, there was also a Japanese document stating that he had a different approach to resolving these situations, starting with the triangulation of delaunay and the generation of black cells from it, but it was also erroneous. It should be nice to be a researcher, coming up with wide lines of algorithms and letting researchers worry about the details ...