Graham Scan

A polygon is convex if a line segment that joins any two points in the polygon is an edge of the polygon or lies inside of the polygon. The convex hull of a set of points is a subset of the set of points that forms the smallest convex polygon in which every point in the set of points is either on the boundary of the polygon or in the interior of the polygon.

To find the convex hull, the Graham Scan first places into the hull a point that must belong in it. Then it incrementally adds new points to the hull.

The point with the lowest y-coordinate must belong in the hull. So, the Graham Scan first places into the hull the point with the lowest y-coordinate. If there are multiple points that all have the lowest y-coordinate, then the algorithm picks the one that has the lowest x-coordinate.

The remaining points are sorted by polar angle around this leftmost lowest point, and each of the remaining points is scanned. If a point lies to the left of the line segment that joins the second-to-last point in the hull and the last point in the hull, then the point is added to the hull. If it does not, then the last point in the hull is removed until it does. Then it is added to the hull.

I implemented the Graham Scan in Java. My implementation is up at my GitHub.

Further references:

Graham, R. L. “An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set.” Information Processing Letters 1 (1972): 132-133. Amsterdam: North-Holland Publishing Company.

Skiena, Steven S., and Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. New York: Springer-Verlag, 2003.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s