A program for convex hulls
Hull is an ANSI C program that computes the convex hull of a point set
in general (but small!) dimension. 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
The program can also compute Delaunay triangulations and alpha shapes,
and volumes of Voronoi regions. 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.
This document is an html version of the manpage, with links to
papers describing the algorithm.
At long last, I've made the code a bit more portable: it compiles under gcc
with the provided makefile, and I've included Visual Studio 7 solution and
project files to build it on Windows (as a console application).
I'm told it also compiles and runs fine under Solaris.
Examples of use
The input_file (default stdin) is a sequence
of points (also called sites), separated by \n; a d-dimensional
point is specified
as a group of d floats separated by whitespace (other than \n).
The output_file (default stdout)
gives d-tuples of the input points, where
a point is given as an integer i if it was the i'th
point in the input_file.
If the convex hull lies in a flat (affine subspace)
of dimension d', the output will comprise a list of d'-tuples,
the vertices of the convex hull relative to that flat.
The output tuples represent the facets of the convex hull
of the input set. A facet which is not a simplex is output
implicitly as the collection of simplices of its triangulation.
The output for Delaunay triangulation includes a "point at infinity",
numbered -1; facets including it correspond to facets of the convex hull
of the sites.
Some chatter will appear on debug_file (default stderr).
The coordinates of the input points are rounded to integers.
With -m<multiplier>, the coordinates are multiplied by
The program attempts to use a method that gives exact answers
to numerical tests; in some circumstances, this may fail,
and with some warnings, the program continues, using approximate
More detail on the options:
- compute the Delaunay triangulation of the input set.
- give the main output (convex hull or Delaunay triangulation)
in output <format>, which is by default the list of vertex numbers
described above, or
ps, for postscript output of planar points, or
off, for OFF output of 3d points.
- compute the alpha shape using parameter < alpha >: the output is
the set of all
d-tuples of sites such that there is a ball of radius < alpha >
containing those sites on its bounding sphere, and containing no other sites.
A Delaunay triangulation computation is implied by this option and by -A.
- output the alpha shape in format <format>, as in option -f.
- compute the alpha shape of the input, finding the smallest alpha
so that the sites are all contained in the alpha-shape.
- randomly shuffle the input points; this may speed up the program.
- randomly shuffle using < seed > for the random number generator.
- do not produce main output (convex hull or Delaunay triangulation).
If you want an alpha shape only, you need this to turn off the Delaunay output.
- Give volumes of Voronoi regions of input sites, and in general
d'-volumes of d'-dimensional Voronoi cells. Implies -d.
If the convex hull is a single point, the algorithm will fail to report it.
All other degeneracies should be handled.
Tie-breaking is done so that all reported facets are
If the input points are degenerate, some hull facets may be;
for example, some Delaunay simplices may have zero volume.
Determining non-simplicial facets or deleting zero-volume
Delaunauy simplices could be done in post-processing
The file rand.c includes calls to pseudo-random number generators;
No simplices are deleted; the only way to free storage
is to free it all using free_hull_storage.
using an earlier version written by Susan Dorward, who is not to blame.
The program implements an incremental algorithm, which can be randomized
if desired; the algorithm is roughly as described in Section 3
(page 7) of
K. L.Clarkson, K.Mehlhorn, and R.Seidel.
Four results on randomized
Comp. Geom.: Theory and Applications, pages 185--121, 1993.
Preliminary version in Proc. Symp. Theor. Aspects of Comp. Sci.,
The code is an implementation of the "all-visibilities"
The "anti-origin" point of that discussion is represented as a NULL point
in the code, so that simplex s represents a facet iff s->peak.vert is NULL.
The numerical code, for computing normals to facets and so on, is an
Safe and effective
In Proc. 31st IEEE Symposium on Foundations of Computer Science,
pages 387--395, Pittsburgh, PA, October 1992.
The conditioning procedure of that paper is used, and applied to
finding a normal vector to a facet of the convex hull.
The visibility test is then a dot product. Vectors a_1, a_2...
are obtained from points p_0, p_1,...by translating
p_0 to the origin: a_i = p_i-p_0, for i=1..cdim.
The main function to call is
simplex *build_convex_hull(gsitef *get_s, site_n *site_numm, short dim, short vdd)
returns pointer to root simplex of triangulation of convex hull (or Delaunay
triangulation if vdd==1).
see hull.h for gsitef typedef etc.
- returns next site each call;
hull construction stops when NULL returned;
- returns number of site when given site;
- dimension of point set;
- if (vdd) then return Delaunay triangulation, otherwise convex hull;