Low dimensional Voronoi diagram and Delaunay triangulation

voronoi

Voronoi diagram of points in the plane. Fortune's planesweep algorithm. Floating-point arithmatic in C.

There is more information on the manpage .

By Steve Fortune, Bell Labs.
This program lives in netlib .

geompack

Delaunay triangulation of point sets in 2-D, 3-D and k-D, where k is small. Also contains convex decomposition and triangulation programs for 2D polygons and 3D polyhedra. Fortran 77 source code.

By Barry Joe, University of Alberta.
For more info (including references) go to the ftp site at Alberta.

Detri

Robust Delaunay tetrahedralization of 3-D point sets. Randomized incremental flipping algorithm. Achieves robustness using symbolic perturbation (so good on degenerate input). Executables for SGI and Sun, and C sources freely available.

There's a short paper about this program.

By Ernst Mücke, University of Illinois at Urbana-Champaign. Get Detri either as part of the 3D alpha-shape distribution via ftp from NCSA, or as a seperate package from Illinois. (Try doing ftp ``by hand'' from cs.uiuc.edu, /pub/edels/geometry, if you have trouble with this). The latter site also contains papers about simulation of simplicity (the degeneracy technique) and 3D alpha shapes.

tess

Delaunay tetrahedralization of 3-D point set using a sort of gift-wrapping algorithm. In C. Floating point with careful attention to numerical stability, but not guaranteed to handle degenerate input.

There's more information in the README file.

By Carol Hazelwood, Southwest Texas State University.
Get tess from our ftp directory.

Up: Directory of Computational Geometry Software

The Geometry Center Home Page

Created: May 31 1995 ---