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] aati_v1_0.gz(7 Kbytes)
Manuscript Title: Computing the convex hull of a set of points.
Authors: D.C.S. Allison, M.T. Noga
Program title: CXHULL
Catalogue identifier: AATI_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 43(1987)381
Programming language: Fortran.
Computer: VAX 8600.
Operating system: VMS VERSION 4.2.
RAM: 8K words
Word size: 32
Keywords: Convex hull, Polygon, Sorting, General purpose, Utility.
Classification: 4.14.

Nature of problem:
The program determines the vertices of the convex hull of a set of points in the (x,y) plane. The convex hull is the minimum area convex polygon which will entirely contain the set. The vertices are output in countrclockwise order beginning with the vertex which has least y- coordinate.

Solution method:
The method is a variation of the technique first proposed by Graham. First, find the bottommost point of the set the point with minimum y- coordinate. Next, order the remaining points in terms of increasing angular value taking the bottommost point as origin. If connected, these ordered points may be considered as the vertices of a simple polygon. Finally, take this polygon and eliminate any vertex whose common edges form a reflex angle (greater than 180 degrees) with respect to the interior of the polygon. The vertices which remain after the elimination define the convex hull.

Restrictions:
The number of points which can be processed by CXHULL has been set at 1000. Larger point sets can be considered by increasing the dimension of the arrays in the calling routine.

Running time:
On a VAX 8600 the running time to find the convex hull set of 1000 points uniformly distributed in the plane is approximately 0.08 s. The algorithm exhibits O(nlogn) average case time complexity for sets of size n. The worst case is O(n**2). However, it is improbable that this performance will ever be encountered in practice.