Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] adfs_v1_0.gz(22 Kbytes)
Manuscript Title: Computing the 3-dimensional convex hull.
Authors: D.C.S. Allison, M.T. Noga
Program title: tetra
Catalogue identifier: ADFS_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 103(1997)74
Programming language: C.
Computer: Sun SPARCstation 10.
Operating system: Solaris 2.5.
Word size: 32
Keywords: General purpose, Utility, Convex hull, Facet, Polytope, Binary trees.
Classification: 4.14.

Nature of problem:
The program determines the convex hull of a set of points in (x,y,z) space. The convex hull is the minimum volume convex polytope which encloses the set of points. This polytope can be considered to be composed of a set of triangular faces called facets. The program returns the points on the hull and, if requested, information from a balanced binary tree containing all the facets on the hull.

Solution method:
The method is an extension of the technique first proposed by Eddy [1] for the computation of the two-dimensional convex hull. In two dimensions, when a point is found that is highest above an existing line, remaining points are checked to see if they are interior to a triangle. In three dimensions, when a point is found that is highest above an existing facet, remaining points are checked to see if they are interior to a tetrahedron consisting of four triangular facets. The first step is to use a preprocessing technique due to Golin and Sedgewick [2] to eliminate points which are known to be interior to the hull. The second step is to determine two extreme hull points in the x direction (xmin and xmax), and one in the y direction. These three extreme points are then taken as an initial facet and the highest point above this facet is found. This defines a tetrahedron with four facets and another elimination technique can be used to delete points that are interior to the tetrahedron. Then, for each of the four facets, iteratively find new highest points and new tetrahedra eliminating interior points at each stage. If a facet is found to have a point above it, then this facet cannot be on the hull and it can be deleted from further consideration. The program finishes whenever there are no points left above the set of candidate facets. During the iterative process, the facets added can cause the growing polytope to become nonconvex. This condition is handled by recursively adding and removing facets until the polytope returns to a convex state. The final convex polytope, the convex hull, is defined by a set of interlocking facets. The points on the hull can then be found by scanning the set of facets.

Restrictions:
None. Storage is dynamically allocated so that a larger number of points can be processed without increasing the size of the data structures. (Uses 33 words per input point.)

Unusual features:
None

Running time:
On a Sun 10 (50 MHz CPU, 64 MB RAM) the running time to find the convex hull of a set of 1000 points uniformly distributed within a cube is approximately 0.2 seconds. Performance tests for larger set sizes with uniform distributions in a cube indicate that the expected running time for sets of size n is O(n). This behaviour is in agreement with the theoretical result of Golin and Sedgewick [2].

References:
[1] W.F. Eddy, ACM Trans. Math. Soft. 3(1977)398.
[2] M. Golin and R. Sedgewick, Tech. Rep. CS-TR-130-87, Princeton Univ. (1987).