A reference to code for general dimension convex hull and Delaunay
Taken from posts on comp.theory and theorynet on 20Aug93 and 02Jul94.
I am pleased to announce a new version of Qhull for general dimension
convex hull, Delaunay triangulation, and Voronoi diagrams. This is
the first program to (empirically) handle roundoff error in 3-d and
above. For example, it approximates the exact convex hull of
thousands of points near the surface of a cube. Existing programs may
produce concave edges, facets with flipped orientation, and edges with
more than two incident facets.
Qhull is based on the Quickhull algorithm. It extends the 2-d
algorithm with the n-d Beneath-beyond algorithm. It is similar to
Clarkson and Shor's randomized incremental algorithm using conflict
lists. The difference is that Quickhull selects the furthest point on
a conflict list instead of a random point. Empirically, this makes
Qhull output-sensitive. Qhull appears to be the fastest available
algorithm in 3-d and higher.
Version 2 has options to merge non-convex facets. The result is an
approximate convex hull that sandwiches all possible exact convex hulls.
Empirically, this handles arbitrary amounts of round-off error and
imprecision in 2-d, 3-d, and 4-d. In 5-d and higher, it may fail
to produce a good approximation.
The program also includes options for graphical output, partially constructed
hulls, input transformations, randomization, tracing, and execution
statistics. The program can be called from within your application.
Source code in C for general dimension convex hull and Delaunay
triangulation (qhull) is now available by anonymous ftp:
password: [your user id]
get qhull.tar.Z (Version 1 is qhull-1.0.tar.Z)
tar xf qhull.tar
You can view the results in 2-d, 3-d and 4-d with geomview
(Iris version by ftp geom.umn.edu:/pub/software/geomview/geomview-sgi.tar.Z,
Next version by ftp of /pub/software/geomview/geomview-next.tar,
Sun version by ftp of /pub/software/geomview/geomview-sun.x11-beta.tar.Z).
Version 1.0 is available for the Macintosh in pub/software/qhull.sit.hqx
It reads point coordinates from a standard file, and returns output
to a standard file. There is no graphical output.
Convex hull is an easy way to build convex polytopes (just
list the vertices). The algorithm also produces approximate convex
hulls. For example, we have produced the approximate convex hull of
12,000 points in R^6, randomly distributed in the unit cube.
The distribution includes .ps files for
Barber, C.B., Dobkin, D.P., and Huhdanpaa, H., "The Quickhull
algorithm for convex hull," Technical Report GCG53, The Geometry
Center, Univ. of Minnesota, July 1993.
The convex hull of a set of points is the smallest convex set that
contains the points. This paper presents a convex hull algorithm that
combines the 2-d Quickhull algorithm with the general dimension
Beneath-beyond algorithm. It is similar to the randomized,
incremental algorithms for convex hull and Delaunay triangulation.
Our algorithm is simpler, uses less memory, and allows good use of
virtual memory. A simple modification produces an approximate cOnvex
hull. We provide empirical evidence that the algorithm runs
faster and is output sensitive.
--Brad Barber (firstname.lastname@example.org)