Clarkson's higher dimensional convex hull code
Hull is an ANSI C program by Ken Clarkson of Bell Laboratories
that computes the convex hull of a point set in general (but small!)
The input is a list of points, and the output is a list of facets of the convex hull of the
points, each facet presented as a list of its vertices.
(The facets are assumed to be simplices, such
as triangles in 3d; this is enforced by tiebreaking, giving a triangulation
of a facet by "placing".)
The program can also compute Delaunay triangulations and alpha shapes, and
volumes of Voronoi
The program uses exact arithmetic when possible, with a moderate speed penalty.
(Typically a factor of 2 or 3 for Delaunay triangulation,
less for convex hulls). Output in postscript
and OFF format for geomview is supported.
Download Files (local site)Ken Clarkson's WebpageOfficial site
This page last modified on 2008-07-10