Arbitrary dimensional convex hull, Voronoi diagram, Delaunay triangulation

qhull

Arbitrary-dimensional convex hull. Computes approximate hulls. Floating-point arithmetic with many parameters for tolerancing. Very fast. Deterministic incremental algorithm with heuristics. Does Voronoi diagrams and Delaunay triangulations and, in low dimensions, Geomview output.

Check out the short abstract , or the long man page .

By Brad Barber, David Dobkin and Hannu Huhdanpaa, The Geometry Center.
To get the code, go to our ftp directory and get qhull.tar.Z.

chD

Arbitrary-dimensional convex hull. Computes exact hull of infinitessimally perturbed input. The symbolic perturbations handle all degenerate cases and break output faces up into simplices. Deterministic incremental algorithm. Does Voronoi diagrams and Delaunay triangulations and, in low dimensions, Geomview output.

The options are described in the README file for chD.

By Ioannis Emiris, U.C. Berkeley.
The code, and the relevant papers, are available by ftp from Berkeley.

Hull

Arbitrary dimensional convex hulls, Delaunay triangulations, alpha shapes, volumes of Voronoi cells; no nondegeneracy assumptions. ANSI C, about 3K lines. Exact arithmetic, with moderate speed penalty over floating point. Incremental algorithm, with performance guarantees if sites are added in random order. Output formats include postscript in 2D, geomview in 3D.

By Ken Clarkson, AT&T Bell Labs.

More information, references, and the code, is available on netlib .

Porta

Arbitrary dimensional convex hull via Fourier-Motzkin elimination, using integer arithmatic. Also does enumeration of integer points inside the convex hull and tests a new facet to see if it intersects the hull.

Check out the README for more information.

By Thomas Christof, Heidelburg University and Andreas Löbel, Konrad-Zuse-Zentrum für Informatik (ZIB).
Get this program by ftp from ZIB .

cdd

Dual convex hull - computes the vertices of a polytope defined as an intersection of halfspaces (nice because it's easier to solve convex hull given a program for the dual than visa versa). Handles unbounded intersections of halfspaces. Also can compute convex hulls of point sets, and unbounded convex hulls given an unbounded direction. A post-processing step gives the entire face structure of the polytope, and an auxillery program gives projections of the polytope to lower-dimensional subspaces. Both C and C++ source code, the latter with an exact aritmatic option as well as floating point.

There are more details in the README file.

By Komei Fukuda, ETH Zurich, Switzerland and University of Tsukuba, Japan

Get the code from ETH by ftp.

rs, qrs

Finds all the vertices of a polytope given as an intersection of halfspaces, by walking from vertex to vertex. C source code, with exact rational arithmatic and optional perturbations for degenerate polytopes.

You should look at both the README file, and the paper to understand what's going on.

By David Avis, McGill University

The code is in this ftp directory. (Try doing ftp ``by hand'' from mutt.cs.mcgill.ca, /pub/C, if you have trouble with this).

Up: Directory of Computational Geometry Software

The Geometry Center Home Page

Created: May 31 1995 ---