Up: Directory of Computational Geometry Software

Low dimensional convex hull, Voronoi diagram and Delaunay triangulation

There are other Delaunay triangulation programs on the triangulation page. You could also use any of the arbitrary dimensional programs.

voronoi

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

There is more information on the manpage .

By Steve Fortune, Bell Labs.
This program lives in netlib.
You can get the source code by mailing send sweep2 from voronoi to the address netlib@research.att.com.

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, then at the University of Illinois at Urbana-Champaign. Get Detri either as part of the 3D alpha-shape distribution via ftp from NCSA, or as a separate package from Ernst's GeomDir directory. The latter also contains papers about Simulation of Simplicity (the used symbolic perturbation method) and 3D alpha shapes.

DeWall, InCode

 Two different three-dimensional Delauney triangulation algorithms, one divide and conquer, the other incremental. Uses a uniform grid to speed up the decomposition and insertion, respectively, so should be good on well-distributed points. Can not handle degenerate data. In ANSI C. For pointers to the code, see the Web page.

By P. Cignoni, C. Montani and R. Scopigno, of the CNR, Pisa, Italy.

tess

 Delaunay tetrahedralization of 3-D point set using a 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.

See Graphics Gems for an incremental Delaunay triangulation routine (by Lischinski).

2d convex hull

 A very short O(n lg n) two-dimensional convex hull program, in C.

By Ken Clarkson, of Bell Labs.

Get the code here.

Up: Directory of Computational Geometry Software
[HOME] The Geometry Center Home Page

Comments to: nina@geom.umn.edu
Created: May 31 1995 --- Last modified: Thu Jun 1 14:26:51 1995