Graham's Scan
Given a set of points on the plane, Graham's scan computes their
convex hull.
The algorithm works in three phases:
- Find an extreme point. This point will be the pivot,
is guaranteed to be on the hull, and is chosen to be the
point with largest y coordinate.
- Sort the points in order of increasing angle about the pivot.
We end up with a star-shaped polygon (one in which one special
point, in this case the pivot, can "see" the whole polygon).
- Build the hull, by marching around the star-shaped poly, adding
edges when we make a left turn, and back-tracking when we make
a right turn.
Here's a demonstration of Graham's scan. It finds the convex hull of
30 points randomly positioned on the plane. Click on "Run" to start the demo.
Here we see an example where the points are in convex position, ie,
they are the vertices of a convex polygon. In this case, the algorithm
makes no right turns, and hence never has to back-track.
Alejo Hausner, CS Department, Princeton University
Last modified: Tue Jul 16 15:22:42 1996