2D Convex Hull Algorithms

Introduction

The 2D-convex hull of a set of points is defined as the smallest convex polygon that encloses all of the points. Smallest refers to both the area as well as the length of the perimeter. An example of a set of points and its convex hull is provided in Figure 1.

Convex hulls find use in a number of different applications including:

collision avoidance in robotics; [Zhang, RahmanianShahri 96, RahmanianShahri 96b] and
pattern recognition and digital image processing [Chaudhuri, Gall, Ye].

However, the fundamental process of finding a convex hull is often embedded inside other algorithms that themselves are important in a range of applications. Such 'next tier' algorithms include:

determining whether a point lies 'amongst' a set of other points;
determining whether two sets of points 'overlap';
finding the smallest rectangular box that will encompass a set of points; and
finding a 'rough' description of the shape defined by a series of points.

Figure 1: Example of a set of points and their convex hull.

Algorithms for Finding Convex Hulls

Over the relatively few years that the field of computational geometry has been studied, there have been a number of algorithms developed for finding 2D-convex hulls. The following table provides a summary of some of these, and lists the time complexity of the algorithm, as well as a brief comment on each algorithm.

Table 1: A comparison of algorithms for determination of convex hulls
Algorithm Name	Description/Comments	Time Complexity
Extreme/Interior Points (Naive)	Points are interior iff they are inside a triangle defined by any other three points within the set. (Must compare all points [O(n)] against all possible triangles [O(n³)])	O(n⁴)
Extreme Edges	An extreme edge occurs when all the points lie on, or to one side of, the line defined by the two points within the set. (Must compare all points [O(n)] against the line formed by all pairs of points [O(n²)])	O(n³)
Gift Wrapping	Essentially starts from an extreme point and 'wraps' a line around the set of points. See Figure 2. (Also known as the Jarvis March algorithm)	O(n²) or O(n.h) (h= hull edges)
QuickHull	Related (loosely) to the quicksort algorithm. See below for a description of the algorithm.	average O(n log n) worst O(n²)
Graham's Algorithm	See below for a description of the algorithm. Has optimal complexity.	O(n log n)

Each of the listed algorithms are discussed in detail below. Each is presented in pseudocode form and they are described with the aid of a series of illustrations. The graphical images have primarily been obtained using the convex hull applet developed as a major aspect of this thesis. This applet uses animations and interactive graphics to illustrate the functioning of each of the algorithms. Although the material presented below illustrates the behaviour of the algorithms, it is the dynamic graphics environment of the applet that enables the algorithms to be really understood.

Extreme/Interior Points (a Naive Algorithm)

Concept

Points are interior if and only if (iff) they are inside a triangle defined by any other three points within the set. The following figure shows the result of two such tests. In steps A and B two different internal points are identified.

Having discovered all of the internal points the convex hull can be constructed from the set of non-internal (extreme) points.

Time Complexity

General Case: Must compare all points [O(n)] against all possible triangles [O(n³)], therefore the algorithm is O(n⁴).
Worst Case: No special cases exist. The algorithm is always O(n⁴) as there are four nested for loops.
Best Case: No special cases exist. The algorithm is always O(n⁴).

Pseudocode

for each i do
    for each j =/= i do
        for each k =/= i =/= j do
            for each l =/= i =/= j =/= k do
                if p(l) is left or on ( p(i),p(j) ) and
                                      ( p(j),p(k) ) and
                                      ( p(k),p(l) )
                then p(i) is non-extreme
Constructed hull from extreme points

Extreme Edges

Concept

An extreme edge occurs when all the points lie on or to one side of the line defined by two points within the set. The following diagram illustrates two such tests. In the first case, Figure A, the line is identified as being extreme as all of the points are on one side of the line. As such this line segment is on the hull. Figure B illustrates the converse condition. In this case points appear on both sides of the line, hence this line segment is not on the hull.

After processing all the possible lines, all of the extreme edges will have been identified and the convex hull can be readily constructed from these.

Time Complexity

General Case: Must compare all points [O(n)] against the line formed by all pairs of points [O(n²)], therefore the algorithm is O(n³).
Worst Case: No special cases exist. The algorithm is always O(n³).
Best Case: No special cases exist. The algorithm is always O(n³).

Pseudocode

for each i do
    for each j =/= i do
        for each k =/= i =/= j
            if p(k) is not left or on ( p(i), p(j) )
                then ( p(i), p(j) ) is not extreme
Constructed hull from extreme edges

Jarvis March or 'Gift Wrapping'

Concept

Figure 2 provides a diagrammatic representation of the gift wrapping algorithm. The algorithm begins by locating the lowest (right-most) point, and then finds the point that has the smallest angle (from horizontal) from this point. A hull edge must join these two points (Figure 2, Step 1). The algorithm then proceeds to find the point with the smallest angle from this established hull edge. In effect, the line extending from the established hull edge is 'bent' around, in a counter-clockwise sense, until it touches another point. If two points are found to have the same angle, then the one furthest from the 'pivot' point is used (Figure 2, Step 2). The process of 'wrapping' the line around the set of points continues (Figure 2, Step 3) until the lower rightmost point is again reached (Figure 2, Final Step), at which point the convex hull has been discovered.

Figure 2: Progress of the 'Gift Wrapping' algorithm.

Time Complexity

General Case: It is reasonably obvious that for every hull edge point discovered [O(n), or more precisely O(h) where there are h hull points] the next hull point needs to be found. This is achieved by comparing every point, hence the total time complexity is O(n²), or more precisely O(n.h).

Worst Case: When all of the points occur on the convex hull, and there are no collinear points, the time complexity of the algorithm is O(n²).

Best Case: The best case for this algorithm is to have as many points inside the convex hull as possible. This situation arises when all the points lie inside a triangle, in which case the algorithm becomes O(n).

PseudoCode

Find the lowest (right-most) point
Let i(0) be its index, and set i=i(0)
repeat
    for each j =/= i do
        Compute ccw angle from previous hull edge
    Let k = index of the point with the smallest angle
    Output (p(i),p(k)) as a hull edge
    i = k
until i = i(0)

QuickHull

Concept

The QuickHull algorithm is loosely related to the quicksort algorithm. The description provided below is based on the algorithm as outlined by O'Rourke [O'Rourke, p77].

The QuickHull begins with the generation of a quadrilateral that connects the extreme points along the compass directions (see Step A in the illustration below). Only those points that are outside of the quadrilateral can be on the hull and will be considered in further computation. Each of the four regions outside of this quadrilateral will be consider in turn and each will be recursively processed using the QuickHull function. The procedure applied to the top-right corner is depicted in the diagram below.

Step A shows the discovery of the four extreme points, their connection to form a quadrilateral, and the selection of the points in the top-right corner. Finally, Figure A highlights the point further from the line a to b, labelled c. The next step in the procedure is to identify two sets of points, those points to the right, or on, the line (a,c) and those to the right, or on, the line (c,b) (Figure B). Two calls to the QuickHull function are then made using these new sets of points.

In the figure below the first set of new points is processed in the same fashion as above. That is, the point furthest from the line (a',b') is identified, labelled c' in Figure C, and the new sets of points identified to the right, or on, (a',c') and (c',b') (Figure D) are created and processed further..

The algorithm continues with another call to the QuickHull procedure with these two new sets. Figures E and F below shows the result of this call for the first set. In this case there are only two points in the set and the recursion terminates with the two hull points being returned and the hull edge being established (Figure F, the black solid line indicates a hull edge).

The second set is then processed (Figure G), and again only two points are within this set and the recursion terminates. The other sets identified above are processed until all of the recursive calls have been complete for the top-left hand corner. At this point the convex hull is established for this region (Figure H).

After the top-left, bottom-left and bottom-right corners have been processed in an identical manner to that outlined above the complete convex hull has been found (Figure I).

Time Complexity

O'Rourke [O'Rourke, p77] provides the time complexity analysis of the QuickHull algorithm and provides the following findings:

General Case: O(n log n) - As with the quicksort, on average the points will be partitioned into two equal sets and hence to depth of the recursion is log n. At each level of recursion there are O(n) operations. Hence overall the average case is O(n log n)
Worst Case: O(n²) - as with the Quicksort algorithms there are special data sets that do not partition well during the recursive calls. This leads to O(n) recursions, therefore overall it is O(n²).
Best Case: O(n). If all of the points can be eliminated as soon as the four extreme points are identified (an O(n) operation) then no further processing is required and the overall complexity becomes O(n).

PseudoCode

Locate leftmost, rightmost, lowest, and highest points
Connect these points with a quadrilateral
Run QuickHull on the four triangular regions exterior to the quadrilateral

function QuickHull(a,b,s)
    if S={a,b} then return(a,b)
    else
        c = index of right of (a,c)
        A = points right of (a,c)
        B = points right of (a,b)
        return QuickHull(a,c,A) concatenated with QuickHull(c,b,B)

Variations on the QuickHull Theme

Wenger has recently published a 'randomized QuickHull' algorithm with expected running time O(n log h) where h is the number of points on the convex hull. [Wenger]

Graham's Algorithm

Concept

Graham published a paper in 1972 [Graham] in which he presented a relatively simple algorithm that computed the convex hull of a finite planar set of points with a worst case time complexity of O(n log n).

The description provided below is based on the algorithm as outlined by O'Rourke. [O'Rourke, p80] Note that this has been slightly updated from the original version of the 'Graham Scan' algorithm.

The first step is to identify the lowest (right-most) point, called this point 0, this point is guaranteed to be on the hull (Step A). The next stage is to sort all of the points angularly about this point measured in a anti-clockwise direction relative to the positive horizontal direction (Step B). The point found to have the greatest angle is pushed onto a stack followed by point 0 (Step B). The points are then processed in turn, starting from the point with the lowest angle (point 1) until the final point (point 9) is reached. The process involves a test for a strict left turn from the point at top-1 in the stack, to the point at the top of the stack to the point being tested. If a left turn is found than that point is pushed onto the stack and the next point is then processed. If a left turn is not found than the top entry on the stack is removed and the same point is rechecked. This process is illustrated in steps C-L.

In step C point 1 is tested as to whether it is left of the line defined by points 9 and 0. In this case it is and therefore pushed onto the stack. Similarly points 2 and 3 are pushed onto the stack (Step D and E). When point 4 is tested a right turn from the line defined by points 2 and 3 is discovered, hence the top of the stack is popped and point 3 removed (Step F). In the following step point 4 is found to be left of points 1,2 and is pushed on the stack (Step G). However, when point 5 is checked against 2 and 4 a right turn is discovered and hence point 4 is popped from the stack. Checking point 5 again reveals a left turn from points 1 and 2 and hence it is pushed onto the stack. The process is continued, first by pushing point 6, and then point 7, onto the stack (Step J). Subsequent tests reveal that point 8 is to the right of both of these and hence 7 and the 6 are popped from the stack (Step K). Further processing reveals that point 8 should be pushed onto the stack and finally point 9 is reached and the process terminates (Step L). At this stage the complete convex hull has been discovered.

PseudoCode

Find the lowest (right-most) point
label this point p(0)
Sort all other points angularly about p(0)
    break ties in favour of closeness to p(0)
    label p(1),...,p(n-1)
    Stack S=(p(n-1),p(0))=(p(t-1),p(i)); t indexes top
    i = 1
    while i < n do
        if p(i) is strictly left of ( p(t-1),p(t) )
        then Push(S,i) and set i = i + 1
        else Pop(S)

Time Complexity

There can be at most n pushes and n pops from the stack and hence the latter part of the algorithm is O(n). Therefore the complexity is dominated by the sort and this is known to have a lower bound of O(n log n).

General Case: O(n log n).
Worst Case: O(n log n).
Best Case: O(n log n).

'State-of-the-Art' of 2D-Convex Hull Computation

The question remains as to whether an algorithm with lower complexity than the Graham's scan can be found. This can be answered indirectly by showing that an algorithm that finds a convex hull can be used to sort a sequence of numbers. The procedure was developed by Shamos in 1978 [Shamos] and is outlined in O'Rourke's book [O'Rourke, p96]. The conclusion of this analysis is that the lower bound for the 2D convex hull problem is O(n log n), or more specifically O(n log h), where h represents the number of points on the hull. This does not stop further research into this field and work continues in earnest to develop faster optimal algorithms. An example is the algorithm published by Wang and Xiao who used the fact that a convex hull is a special type of star polygon in order to develop a real time algorithm. [Wang] Other fast algorithms includes Bhattacharya's algorithm which has been proven experimentally to be faster than Graham's algorithm for small output sizes. [Bhattacharya] Even self-organizing neural net model have been employed in the computation of convex hulls. [Datta]

Of course many of the convex hull algorithms developed over the years can only be employed when the points are held as integers, or, where the points are stored in floating point representations, the convex hull computation is performed using only integer arithmetic and hence only an approximate hull is located. To overcome this restriction special algorithms have been developed. One example of such an algorithm is by Jaromczyk, which is numerically stable and optimal in time and space complexity and employs floating point arithmetic. [Jaromczyk]

It is interesting to note that the lower bound of O(n log n) for a set of points is not the lower bound if the points construct a simple polygon. In this case it has been shown that the lower bound is O(n). [McCallum, Melkman] A WWW page that discusses one such algorithm and implements a Java demonstration of the algorithm is available elsewhere on the internet [Lang].

There are many more examples of algorithms developed over the years to solve the convex hull problem however it is not a trivial endeavour. This is exemplified by Toussaint publication, of a counter-example for a previously published algorithm developed by Chen. [Toussaint, Chen]

Finally, for a reasonably recent review of convex hull hull algorithms see Yamamoto. [Yamamoto]

High Dimensional Convex Hull Computation

All of the above discussion has focused on the computation of convex hulls for points in a 2D plane. However, convex hulls also exist in higher dimensional space. For example, in 3D the convex hull becomes a bounding cage. Much literature exists on this topic and it is beyond the scope of this thesis to report on these. However, it is worthwhile to note a few recent investigations in this field. Erickson has recently reported a new lower bound for the convex hull problems in odd dimensions [Erickson]. Other example of recent work include:

Emiris' Beneath-Beyond algorithm for computing convex hulls in arbitrary dimension; [Emiris]
Borgwardt's Gift Wrapping with the so-called Throw-Away Principle; [Borgwardt]
A QuickHull algorithm with the general-dimension Beneath-Beyond Algorithm in two, three, or four dimensions; [Barber]
Chan's simple output-sensitive algorithm in two or three dimensions with in worst-case optimal O(n log h) time and O (n) space, where h denotes the number of vertices of the convex hull; [Chan] and
Chazelle's optimal convex hull algorithm in any fixed dimension. [Chazelle]

Further, neural networks have even been employed in convex hull determination in N-dimensional space. [Leung]

Parallel Convex Hull Computation

Another active area of research is in the development of efficient parallel algorithms for convex hull computation. Again, it is beyond the scope of this thesis to extensively cover the literature. However, a few recent publications in this field are noteworthy.

Diallo et. al. have recently published a paper in which they report scalable parallel algorithms for building the convex hull of coplanar points. Their algorithms are designed for the coarse grained multicomputer model: p processors with O(n/p) >> O(1) local memory each. They report that their algorithms scale over a large range of values of n and p, involve only a constant number of global communication calls, and also operate in optimal time, i.e. (n log n)/p). [Diallo] Other reports include Day and Tracey's report of a divide and conquer parallel algorithm for determining the convex hull of a set of 2D points. [Day] Other recent related reports include:

Chen's report of parallel method for finding the convex hull of planar discs in the EREW PRAM model; [Chen]
Gupta's very fast parallel algorithms for the planar convex hull algorithms are designed for the arbitrary CRCW PRAM model; [Gupta]
Ghouse's efficient parallel algorithms for constructing 2-dimensional convex hulls on a randomized CRCW PRAM; [Ghouse]
Olariu's fast adaptive convex hull algorithm on a 2-dimensional processor array with a reconfigurable bus system; [Olariu]
Amato's paper that discusses the first parallel algorithm for the 3-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm for the time-optimal computation of 3-D convex hulls on a CREW PRAM; [Amato] and
Berkman's parallel algorithm for finding the convex hull of a sorted point set processors on a Common CRCW PRAM. [Berkman]

Convex Hull Applet

As noted above an applet has been developed during the course of this project that enables the steps involved in the convex hull algorithms to be visualized This applet enables the use to create their own set of points and have the algorithms construct a convex hull from this set. The applet provides an indication of the time taken and the number of important operations required to achieve the result. Further, the applet provides a demonstration mode in with each step through the pseudocode is diagrammatically depicted. Finally, the user is able to 'single-step' through the pseudocode to see the precise effect of each step.