Building the Convex Hull

Computing the Convex Hull

So given a set of points, how do you compute the convex hull without benefit of hammer, nails, and rubber bands?

For some problems, a brute force solution is adequate. In the case of a convex hull, a reasonable brute force algorithm might look like this:

for all points p in S
  for all points q in S
    if p != q
      draw a line from p to q
      if all points in S except p and q lie to the left of the line
        add the directed vector pq to the solution set

After running this algorithm, you've got a list of point pairs that compose the solution set, and you simply have to put them together in the correct order.

This solution works, but with just a quick look at the code you can see a big problem -- a triply nested loop that runs over the magnitude of N, making this an O(n³) algorithm. That's not going to scale up as well as we might like.

Fortunately, a little searching shows you that there are algorithms that calculate a convex hull in a 2D space considerably faster -- in O(n·lgn) time, as a matter of fact.

The Graham Scan

The algorithm I demonstrate here is referred to as the Andrew's variant of the Graham scan. Ronald Graham's 1972 paper An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set proposed a convex hull construction algorithm that ran in O(n·lgn) time. Andrew's variation is a simplification that requires a bit less computation. First I give the terse definition of the algorithm, then explain each step in more detail.

Algorithm ConvexHull( <i>S</i> )
Sort all points in <i>S</i> based on their position on the X axis
Designate point <i>left</i> as the leftmost point
Designate point <i>right</i> as the rightmost point
Remove <i>left</i> and <i>right</i> from <i>S</i>
While there are still points in <i>S</i>
   remove <i>Point</i> from <i>S</i>
   if <i>Point</i> is above the line from <i>left</i> to <i>right</i>
       add <i>Point</i> to the end of array <i>upper</i>
   else
       add <i>Point</i> to the end of array <i>lower</i>
//
// Construct the lower hull
//
Add <i>left</i> to <i>lower_hull</i>
While <i>lower</i> is not empty
  add <i>lower[0]</i> to the end of <i>lower_hull</i>
  remove <i>lower[0]</i> from <i>lower</i>
  while size(<i>lower_hull</i> >= 3 and the last 3 points <i>lower_hull</i> are not convex
    remove the next to last element from <em>lower_hull</em>
//
// Construct the upper hull
//
Add <i>left</i> to <i>upper_hull</i>
While <i>upper</i> is not empty
  add <i>upper[0]</i> to the end of <i>upper_hull</i>
  remove <i>upper[0]</i> from <i>upper</i>
  while size(<i>upper_hull</i> >= 3 and the last 3 points <i>upper_hull</i> are not convex
    remove the next to last element from <em>upper_hull</em>
//
Merge <i>upper_hull</i> and <i>lower_hull</i> to form <i>hull</i>
return <i>hull</i>