Voronoi and Delaunay Triangulation

From CGAFaq

For 2D Delaunay triangulation, try Shewchuk’s triangle program. It includes options for constrained triangulation and quality mesh generation. It uses exact arithmetic.

The Delaunay triangulation is equivalent to computing the convex hull of the points lifted to a paraboloid. For n-D Delaunay triangulation try Clarkson’s hull program (exact arithmetic) or Barber and Huhdanpaa’s Qhull program (floating point arithmetic). The hull program also computes Voronoi volumes and alpha shapes. The Qhull program also computes 2D Voronoi diagrams and n-D Voronoi vertices. The output of both programs may be visualized with Geomview.

There are many other codes for Delaunay triangulation and Voronoi diagrams. See Amenta’s list of computational geometry software.

The Delaunay triangulation satisfies the following property: the circumcircle of each triangle is empty. The Voronoi diagram is the closest-point map, i.e., each Voronoi cell identifies the points that are closest to an input site. The Voronoi diagram is the dual of the Delaunay triangulation. Both structures are defined for general dimension. Delaunay triangulation is an important part of mesh generation.

There is a FAQ of polyhedral computation explaining how to compute n-D Delaunay triangulation and n-D Voronoi diagram using a convex hull code, and how to use the linear programming technique to determine the Voronoi cells adjacent to a given Voronoi cell efficiently for large scale or higher dimensional cases.

Avis’ lrs code uses the same file formats as cdd. It uses exact arithmetic and is useful for problems with very large output size, since it does not require storing the output.

On a closely related topic, see

http://www.cis.ohio-state.edu/~tamaldey/medialaxis.htm

for computation of the 3D medial axis from the Voronoi diagram.

[edit]

References:

Amenta: http://www.geom.umn.edu/software/cglist

Avis: ftp://mutt.cs.mcgill.ca/pub/C/lrs.html

Barber & Huhdanpaa http://www.geom.umn.edu/locate/qhull

ftp://geom.umn.edu/pub/software/qhull.tar.Z

ftp://ftp.geom.umn.edu/pub/software/qhull.zip

Clarkson: http://cm.bell-labs.com/netlib/voronoi/hull.html

ftp://cm.bell-labs.com/netlib/voronoi/hull.shar.Z

Geomview: http://www.geom.umn.edu/locate/geomview

ftp://geom.umn.edu/pub/software/geomview/

Polyhedral Computation FAQ:

http://www.ifor.math.ethz.ch/ifor/staff/fukuda/fukuda.html

Shewchuk: http://www.cs.cmu.edu/~quake/triangle.html

ftp://cm.bell-labs.com/netlib/voronoi/triangle.shar.Z

[O’ Rourke (C)] pp. 168-204

[Preparata & Shamos] pp. 204-225

Chew, L. P. 1987. Constrained Delaunay Triangulations, Proc. Third Annual ACM Symposium on Computational Geometry.

Chew, L. P. 1989. Constrained Delaunay Triangulations, Algorithmica 4:97-108. (UPDATED VERSION OF CHEW 1987.)

Fang, T-P. and L. A. Piegl. 1994. Algorithm for Constrained Delaunay Triangulation, The Visual Computer 10:255-265. (Recommended!)

Frey, W. H. 1987. Selective Refinement: A New Strategy for Automatic Node Placement in Graded Triangular Meshes, International Journal for Numerical Methods in Engineering 24:2183-2200.

Guibas, L. and J. Stolfi. 1985. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics 4(2):74-123.

Karasick, M., D. Lieber, and L. R. Nackman. 1991. Efficient Delaunay Triangulation Using Rational Arithmetic, ACM Transactions on Graphics 10(1):71-91.

Lischinski, D. 1994. Incremental Delaunay Triangulation, Graphics Gems IV, P. S. Heckbert, Ed. Cambridge, MA: Academic Press Professional.
(Includes C++ souce code — thank you, Dani!)

[Okabe]

Schuierer, S. 1989. Delaunay Triangulation and the Radiosity Approach, Proc. Eurographics ’89, W. Hansmann, F. R. A. Hopgood, and W. Strasser, Eds. Elsevier Science Publishers, 345-353.

Subramanian, G., V. V. S. Raveendra, and M. G. Kamath. 1994. Robust Boundary Triangulation and Delaunay Triangulation of Arbitrary Triangular Domains, International Journal for Numerical Methods in Engineering 37(10):1779-1789.