Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Introduction The Convex Hull and the Graham Scan The Details The Code Creating the 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( S )
Sort all points in S based on their position on the X axis
Designate point left as the leftmost point
Designate point right as the rightmost point
Remove left and right from S
While there are still points in S
   remove Point from S
   if Point is above the line from left to right
       add Point to the end of array upper
   else
       add Point to the end of array lower
//
// Construct the lower hull
//
Add left to lower_hull
While lower is not empty
  add lower[0] to the end of lower_hull
  remove lower[0] from lower
  while size(lower_hull >= 3 and the last 3 points lower_hull are not convex
    remove the next to last element from lower_hull
//
// Construct the upper hull
//
Add left to upper_hull
While upper is not empty
  add upper[0] to the end of upper_hull
  remove upper[0] from upper
  while size(upper_hull >= 3 and the last 3 points upper_hull are not convex
    remove the next to last element from upper_hull
//
Merge upper_hull and lower_hull to form hull
return hull

Previous Page | 1 Introduction | 2 The Convex Hull and the Graham Scan | 3 The Details | 4 The Code | 5 Creating the Hull Next Page

RELATED ARTICLES Securing the Java Core Petascale Tools and Genomic Evolution Legal Compliance: Open Source and Quality Assurance SEI, Army Team Up on Software Testing Nozzle: Counteracting Memory Exploits		TOP 5 ARTICLES No Top Articles.