6
$\begingroup$

Is there a known algorithm to compute the (generalized) Voronoi diagram of a set of points, line segments and triangles in $\mathbb{R}^3$? If yes, are there any available implementations?

I know that there are two methods with available code for line segments and points on the plane, described in the following papers:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.8990 (CGAL) https://www.sciencedirect.com/science/article/pii/S0925772101000037 (VRONI)

I am also aware of a method that computes voxelizations for a closely related 3D problem, where the sites/objects are surfaces: http://sci.utah.edu/~jedwards/research/gvd/

But I'm not being able to find an algoithm for the case when the sites are vertices, line segments and triangles in space. The output should be the Voronoi diagram vertex coordinates and the (possibly curved) bisector descriptions.

$\endgroup$
3
  • 1
    $\begingroup$ As background personal history: I spent one week writing software for this in Mathematica in 1999 for a single figure in my book Pattern classification (2nd ed.), which, as far as I know, is the first book to contain such an exact three-dimensional Voronoi tessellation. (Alas, I cannot find that code right now.) $\endgroup$ – David G. Stork Sep 27 '18 at 23:31
  • $\begingroup$ Thanks for your answer, David. What algorithm did you use to generate the exact three-dimensional tesselation for your book? $\endgroup$ – Leonardo Sacht Sep 28 '18 at 1:15
  • $\begingroup$ I defined a separating plane for each pair of point, then computed the intersection points, then formed the cells based on those points. $\endgroup$ – David G. Stork Sep 28 '18 at 2:45
5
$\begingroup$

Voronoi diagrams of points in $R^3$ are now implemented in several software libraries and can be computed, for example, in a few lines of Python code. This has not always been the case, so it still isn't trivial.

However, moving from Voronoi diagrams of points to diagrams of more complicated objects shifts the difficulty from asymptotical complexity issues (i.e., devising asymptotically efficient algorithms for point sets) to the difficulty of representing and computing with curved bisectors.

Furthermore, implementing algorithms that work on curved bisectors encounters inherent robustness difficulties. As an example, the vertex of a 3D Voronoi diagram is, by definition, a single intersection point of four edge curves in $R^3$, or equivalently of six face surfaces.

Robustness issues in geometric computing are a known research problem (see, for example, here, here or here), with many papers presenting problems even for simpler objects such as points and lines (for example, this one). Handling these degenerate cases in general and for curved objects, in particular, requires both theoretical and practical sophisticated methods. The book "Effective Computational Geometry for Curves and Surfaces" presents some of these methods for many known problems and in the context of your question, chapter 2 is especially relevant and can refer you to additional papers.

Even for the limited case of line segments in $R^2$, the two excellent implementations you cited apply advanced methods to handle these problems. The CGAL implementation adopts the Exact Geometric Computation (EGC) paradigm (including exact computations with square roots) and applies advanced geometric and arithmetic filtering for acceleration. The VRONI implementation, on the other hand, uses a more engineering approach for floating point computations, which combines the relaxation of epsilon thresholds with a multi-level recovery process. Both implementations are very impressive in their achievement. However, the problem in $R^2$ is relatively easy compared to the 3D problem in your question. In $R^2$, the bisectors are just parabola segments and there is no need to handle surfaces in $R^3$ and their intersection curves. In the Voronoi diagram of triangles, segments, and points in $R^3$, the bisector surfaces are quadric surfaces and the curves of the Voronoi edges can be polynomials of degree 4.

The only implementation I am aware of, which addresses these difficulties, is the one presented in this paper. They use a tracing algorithm (similar to the one in this previous paper) and apply exact arithmetic to handle the inherent robustness issues. In fact, they developed a special exact algebraic library (MAPC - library for manipulating algebraic points and curves) in order to be able to handle these curves and surfaces. The papers describing the implementation (short and long version) are a good reference to the algorithmic and practical difficulties of computing the Voronoi diagram of polyhedrons in $R^3$.

While their method was implemented in the past, I'd be surprised if the Voronoi code is still maintained. At the time, I managed to compile and run the MAPC library, but even compiling just the library on its own wasn't an easy task (and required dependencies on several outside libraries).

All this leads me to the conclusion that, unfortunately, it is unlikely that there are any available exact implementations to your problem. However, depending on your application, you may be able to use one of the non-exact solutions that exist. One direction, as you mentioned, is approximate solutions (such as this one) or voxelization methods, which can be accelerated using GPUs. Another practical approach, which may apply to you, is based on the Voronoi diagrams of points in $R^3$, for which there are software implementations as mentioned above. In these methods (mentioned in the book above), you sample the input objects, perform 3D Voronoi diagram computations on the sample points and then prune the output from unwanted faces.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for your answer! I read the paper by Culver you suggested and indeed they describe a complete solution for the problem. They also present the details and how to face the algorithmic difficulties of the problem. Unfortunately I couldn't find their code anywhere but at least now I have a description of a solution and can implement it myself. I will also consider the non-exact solutions you suggested for a relaxed version of my problem. $\endgroup$ – Leonardo Sacht Feb 6 '19 at 22:33
2
$\begingroup$

This is close, and may lead (through its references and using Google scholar to trace its future citations) to what you seek. This is an algorithm to compute the Voronoi diagram within a triangulated polyhedron. The medial axis in the title (and figure) is a subset of the Voronoi diagram.

Culver, Tim, John Keyser, and Dinesh Manocha. "Exact computation of the medial axis of a polyhedron." Computer Aided Geometric Design 21, no. 1 (2004): 65-98.

"Our algorithm computes the portion of the generalized Voronoi diagram that lies within the polyhedron. As a post-process, it then removes certain sheets, leaving the medial axis."


          VenusDeMilo


$\endgroup$
2
  • $\begingroup$ I see after posting this that @IddoHanniel's "this paper" links to the same paper. – $\endgroup$ – Joseph O'Rourke Feb 6 '19 at 0:59
  • $\begingroup$ Thanks for your suggestion. This solves the problem, though I couldn't find any implementation available. $\endgroup$ – Leonardo Sacht Feb 6 '19 at 22:35
0
$\begingroup$

for line segments, de berg et al. wrote a chapter about voronoi diagrams(chapter 7) in their book computational geometry. They also explain how to adapt fortunes algorithm to work with disjoint line segments, but they don't list a new algorithm in pseudocode.

DOI: 10.1007/978-3-540-77974-2 http://link.springer.com/10.1007/978-3-540-77974-2

http://ir.mksu.ac.ke/bitstream/handle/123456780/6196/2008_Book_ComputationalGeometry.pdf?sequence=1&isAllowed=y

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.