Graham’s scan is a method for finding the convex hull that encompasses all points on the plane. Below you’ll see an example of a convex hull.

Graham’s scan starts by finding the point with the lowest y coordinate. If there are multiple points on the y-coordinate, the point with the smallest x-value is chosen. The points are sorted by polar angles in counterclockwise rotation. Graham’s scan utilizes the stack. Points are pushed onto the stack. If the point is not part of the convex hull, the point is popped from the stack. Let’s look at an example.

We have a set of points. It’s clear which point has the lowest y-coordinate value.

From there, points are ordered in increasing angle.

Now we can follow Graham’s scan to find out which points create the convex hull. Point 0 is pushed onto the stack.

Point 1 is pushed onto the stack immediately after.

The next point to be added to the stack is 2. A line is made from point 1 to
point 2.

Whenever a left turn is made, the point is presumed to be part of the convex hull. We can clearly see a left turn being made to reach 2 from point 1. To get to point 3, another left turn is made. Currently, point 3 is part of the convex hull. A line segment is drawn from point 2 to 3 and 3 is pushed onto the stack.

We make a right turn going to point 4. We’ll draw the line to point 4 but will not push it onto the stack.

Whenever a right turn is made, Graham’s scan algorithm pops the previous value from the stack and compares the new value with the top of the stack again. In this case, we’ll pop 3 from the top of the stack and we’ll see if going from point 2 to point 4 creates a left bend. In this case it does, so we’ll draw a line segment from 2 to 4 and push 4 onto the stack.

Since going from 4 to 5 creates a left turn, we’ll push 5 onto the stack. Point 5 is currently part of the convex hull.

Moving from point 5 to 6 creates a left-hand turn, so we’ll push 6 onto the stack. Point 6 is currently part of the convex hull.

To get to point 7, we must make a right-hand turn at 6.

Point 6 is popped from the stack and the turn is examined from point 5 to point 7. Since we make a left hand turn from point 5 to point 7, we push point 7 onto the stack.

We attempt to push point 8 onto the stack. To get to point 8, we make a left at point 7, therefore point 8 is added to the stack. Point 8 is currently part of the convex hull.

Going to point 9 requires a right-hand turn at point 8.

Since there’s a right-hand turn, point 8 is popped from the stack and point 9 is compared with point 7.

To get to point 9 from point 7 requires another right-turn, so we pop point 7 from the stack too and compare point 9 to point 5. We make a left-hand turn at point 5 to get to point 9, so 9 is pushed onto the stack.

Next, we make a left turn to get to point 10. Point 10 is currently part of the convex hull.

A right turn is required to get to point 11 from point 10.

Since a right turn is taken at point 10, point 10 is popped from the stack and the path to point 10 from point 9 is examined. Since a left turn is made at point 9 to get to point 11, point 11 is pushed onto the stack.

A left turn is made at point 11 to get to point 12. Point 12 is therefore pushed onto the stack and is currently considered part of the convex hull.

A right turn is required to go to point 13 from point 12.

Point 12 is popped from the stack and the path to point 13 from point 11 is examined. Since a left turn is made at point 11, point 13 is pushed onto the stack.

A left turn is made at point 13 to get to point 14, so point 14 is pushed onto the stack.

A right turn is required to go from point 14 to point 15.

Since a right turn was made at point 14, point 14 is popped from the stack. The path to point 15 from point 13 is examined next. A left turn is made at point 13 to get to point 15, so point 15 is pushed onto the stack.

Going from point 15 to the starting point 0 requires a left turn. Since the initial point was the point that we needed to reach to complete the convex hull, the algorithm ends.

The points that are needed to create the convex hull are

0–1–2–4–5–9–11–13–15.

If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.