The following "divide and conquer" algorithm - though worst case O(N2) is far more likely to be O(N log(N)) and outperforms Graham in most cases. It has the considerable advantages of computational simplicity and robustness.
It is possible to implement this algorithm by means of a single call to a general recursive primitive but as a special case serves for all but the uppermost level of the recursion we implement the simpler case recursively and code the first level explicitly.
Note that in the following a set refers to an unordered collection of objects while a list is an ordered collection of obects. fset denotes the empty set while flist denotes the empty list
The basic primitive LeftHull accepts two points a and b and a set S of points
known to lie to the "left" of the line ab and to project to points between a and b.
It returns a list of points defining the remainder of the boundary of
the covex hull containing a,b and S (from b to a exclusive).
We can define LeftHull as follows:
LeftHull(a,b,Sab)
if S=fset then return flist
Set nab | = | æ | ay-by | ö |
è | bx-ax | ø |
Set ncb | = | æ | cy-by | ö |
è | bx-cx | ø |
Set nac | = | æ | ay-cy | ö |
è | cx-ax | ø |
The top level of the recursion is given simply a set of points S and proceeds as follows:
Find two distinct points a and b Î S known to lie on the minimal convex hull containing S.
The obvious choice for a,b are the points having minimal and maximal y coordinates.
Set nab | = | æ | ay-by | ö |
è | bx-ax | ø |
Note that if a and b are chosen by minimal and maximal y then the two "halves" of solution correspond to the left and right hand boundaries of the hull.
This method generalises for three or higher dimensional convex hulls in the obvious manner.
In 3D, the recursive primitive accepts three points and a set of points known to lie to one side
of the plane defined by them and to project into that plane to points within the triangle.
It finds that point furthest from the plane and calls itself
for three distinct subsets of the inherited set while discarding all those points within the constructed tetrahedron.