Up: Directory of Computational Geometry Software

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 qhull home page (http://www.qhull.org/) for more information.

By Brad Barber, David Dobkin and Hannu Huhdanpaa, The Geometry Center.


chD

Arbitrary-dimensional convex hull. Computes exact hull of infinitesimally 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 non-degeneracy 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, Bell Labs.

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


Porta

Arbitrary dimensional convex hull or dual convex hull via Fourier-Motzkin elimination. Uses integer arithmetic but does not handle degeneracies. Also does enumeration of integer points inside the convex hull, projection of halfspace intersection, 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 Loebel, Konrad-Zuse-Zentrum fur 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 auxiliary program gives projections of the polytope to lower-dimensional subspaces. Both C and C++ source code, the latter with an exact arithmetic option as well as floating point.

Just had a new release! Look here for more details.

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

Get the code from ETH by ftp.


lrs (rs, qrs)

lrs, like earlier versions rs and qrs, finds all the vertices of a an intersection of halfspaces, by walking from vertex to vertex. C source code, with exact rational arithmetic and optional lexicographic symbolic perturbation to handle 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

[HOME] The Geometry Center Home Page

Comments to: nina@geom.umn.edu