Convex Hull

From CGAFaq

For n-D convex hulls, try Clarkson’s hull program (exact arithmetic) or Barber and Huhdanpaa’s Qhull program (floating point arithmetic). Qhull 3.1 includes triangulated output and improved handling of difficult inputs. Qhull computes convex hulls, Delaunay triangulations, Voronoi diagrams, and halfspace intersections about a point.

Qhull handles numeric precision problems by merging facets. The output of both programs may be visualized with Geomview.

In higher dimensions, the number of facets may be much smaller than the number of lower-dimensional features. When this is the case, Fukuda’s cdd program is much faster than Qhull or hull.

There are many other codes for convex hulls. See Amenta’s list of computational geometry software.

References:

• Amenta: http://www.geom.umn.edu/software/cglist/

• Barber & Huhdanpaa http://www.geom.umn.edu/locate/qhull

• Clarkson: http://cm.bell-labs.com/netlib/voronoi/hull.html
  

ftp://cm.bell-labs.com/netlib/voronoi/hull.shar.Z

• Geomview: http://www.geom.umn.edu/locate/geomview
  

ftp://geom.umn.edu/pub/software/geomview/

• Fukuda: http://www.ifor.math.ethz.ch/staff/fukuda/cdd_home/cdd.html
  

ftp://ftp.ifor.math.ethz.ch/pub/fukuda/cdd/

• [O’ Rourke (C)] pp. 70-167
  

C code for Graham’s algorithm on p.80-96.

Three-dimensional convex hull discussed in Chapter 4 (p.113-67).

C code for the incremental algorithm on p.130-60.

• [Preparata & Shamos] pp. 95-184