Up: Directory of Computational Geometry Software

Low dimensional convex hull, Voronoi diagram and Delaunay triangulation

There are other excellent Delaunay triangulation programs on the triangulation page. In three or higher dimensions, you should consider the arbitrary dimensional programs, some of which are very good. Finally, you might be interested in constrained Delaunay triangulation, trapezoidation or some other operation on polygons.

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 available. There's a short paper about this program.
You can download Detri from Ernst's GeomDir directory. It also contains papers about Simulation of Simplicity (the symbolic perturbation method employed) and 3D alpha shapes.

By Ernst Mücke, then at the University of Illinois at Urbana-Champaign.

DeWall, InCode

 Two 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.
Get tess from our ftp directory.

By Carol Hazelwood, Southwest Texas State University.

Delaunay tree

 Computes a randomized dynamic data structure for Delaunay triangulations in either two or three dimensions. Randomized dynamic in this case means that you can insert a new point in expected O(lg n) time and delete a random point in expected O(lg n lg lg n) time.

In C++ using LEDA. Some documentation (French and English) in the tar files, which you can download from INRIA.

By Olivier Devillers, INRIA.

2D Delaunay triangulation and Voronoi diagram and 3D convex hull

The classic here is Steve Fortune's voronoi program. Implements Fortune's planesweep algorithm. in C using floating-point arithmetic.

There is more information on the manpage .

Steve Fortune is at Bell Labs.
You can get the source code by mailing send sweep2 from voronoi to the address netlib@research.att.com.

See Graphics Gems IV for an incremental 2D Delaunay triangulation program by Dani Lischinski, at the University of Washington.
Computational Geometry in C has a a very simple $O(n^3)$ two dimensional Delaunay triangulation program by Joe O'Rourke at Smith College.
At the bottom of this page, there is a pointer to (yet another) short floating-point implemenation of the Guibas-Stolfi Delaunay triangulation algorithm. By Geoff Leach, at RMIT, Austria.

3d convex hull

 A nice incremental three-dimensional convex hull program, from Computational Geometry in C, by Joe O'Rourke.

2D convex hulls
Here is a short, robust O(n lg n) two-dimensional convex hull program, in C. You could print it on the back of a business card. By Ken Clarkson, at Bell Labs.
There is a two-dimensional convex hull program in Computational Geometry in C, by Joe O'Rourke. Uses Graham's scan algorithm, also $O(n lg n)$.

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