Graham Scan Convex Hull Tutorial | Easy Explanation with Python

Graham Scan is a fast and elegant algorithm for finding the convex hull of a set of points. In this tutorial, we explain the method in simple terms, show how left and right turns work, give pseudocode, and provide a Python implementation.

1. Main idea

Imagine many points placed on a sheet.

You want to tie a rubber band around the outermost points only.
That outer boundary is called the convex hull.

Graham Scan finds this boundary in a smart way.

Simple idea:

first choose a starting point
sort the other points by angle
walk through them one by one
whenever you make a “wrong turn,” remove the middle point

So Graham Scan is like:
keep only the points that help form the outer boundary.

2. Basic intuition

Suppose you are walking around the points in order.

Every time you add a new point, check the last two points already in your hull.

Ask:

“Did I turn left or right?”

Left turn → good, keep going
Right turn → bad, the middle point is inside, remove it

This is the heart of Graham Scan.

3. Important step: choose the starting point

First, pick the point with:

smallest y-coordinate
if tie, then smallest x-coordinate

This is the bottom-most point.

Why?

Because it is guaranteed to lie on the hull, so it is a good starting point.

4. Sort by angle

Now sort all remaining points by the angle they make with the starting point.

This lets us sweep around the points in circular order.

5. Orientation test

For three points A, B, C, compute:

[(B_x-A_x)(C_y-A_y) – (B_y-A_y)(C_x-A_x)]

This tells the turn direction:

positive → left turn
negative → right turn
zero → collinear

In Graham Scan:

left turn = keep
right turn = pop/remove the middle point

6. Algorithm steps

Find the bottom-most point
Sort all other points by polar angle from that point
Put first three points into a stack
For each remaining point:
* look at top two points in stack
* if they and new point make a right turn, pop stack
* repeat until left turn appears
* then push new point
Stack finally contains hull points

7. Pseudocode

			
GRAHAM_SCAN(points):
    start = point with smallest y
            (if tie, smallest x)
    sort remaining points by polar angle with respect to start
    stack = [start, first point, second point]
    for each point p in remaining sorted points:
        while stack has at least 2 points
              and turn(second_top, top, p) is not left:
            pop top from stack
        push p into stack
    return stack

		

8. Why it works

If three consecutive points make a right turn, then the middle point cannot be on the outer boundary.

So we safely remove it.

By repeating this, only the true outer points remain.

9. Time complexity

finding start point: O(n)
sorting by angle: O(n log n)
scanning points: O(n)

So total time is:

[O(n log n)]

That is much faster than brute force.

10. Python implementation

import math
import matplotlib.pyplot as plt

def orientation(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def distance_sq(a, b):
    return (a[0] - b[0])**2 + (a[1] - b[1])**2

def graham_scan(points):
    if len(points) <= 1:
        return points[:]

    # Step 1: Find bottom-most point
    start = min(points, key=lambda p: (p[1], p[0]))

    # Step 2: Sort by polar angle, then distance
    def polar_angle(p):
        return math.atan2(p[1] - start[1], p[0] - start[0])

    sorted_points = sorted(points, key=lambda p: (polar_angle(p), distance_sq(start, p)))

    # Remove closer collinear points with same angle, keep farthest
    filtered = []
    for p in sorted_points:
        while len(filtered) > 0 and polar_angle(filtered[-1]) == polar_angle(p):
            if distance_sq(start, p) >= distance_sq(start, filtered[-1]):
                filtered.pop()
            else:
                break
        else:
            filtered.append(p)

    if len(filtered) < 3:
        return filtered

    # Step 3: Build hull using stack
    stack = filtered[:2]

    for p in filtered[2:]:
        while len(stack) >= 2 and orientation(stack[-2], stack[-1], p) <= 0:
            stack.pop()
        stack.append(p)

    return stack


# Example points
points = [(1, 1), (2, 5), (4, 6), (6, 4), (5, 1), (3, 2), (4, 3), (2, 3)]

hull = graham_scan(points)

print("Hull points in order:")
for p in hull:
    print(p)

# Plot
x = [p[0] for p in points]
y = [p[1] for p in points]

plt.figure(figsize=(6, 6))
plt.scatter(x, y)

hx = [p[0] for p in hull] + [hull[0][0]]
hy = [p[1] for p in hull] + [hull[0][1]]
plt.plot(hx, hy)

for i, p in enumerate(points):
    plt.text(p[0] + 0.05, p[1] + 0.05, f"P{i}")

plt.title("Convex Hull using Graham Scan")
plt.xlabel("X")
plt.ylabel("Y")
plt.grid(True)
plt.axis("equal")
plt.show()

import math

import matplotlib.pyplot as plt

def orientation(a, b, c):

return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def distance_sq(a, b):

return (a[0] - b[0])**2 + (a[1] - b[1])**2

def graham_scan(points):

if len(points) <= 1:

return points[:]

# Step 1: Find bottom-most point

start = min(points, key=lambda p: (p[1], p[0]))

# Step 2: Sort by polar angle, then distance

def polar_angle(p):

return math.atan2(p[1] - start[1], p[0] - start[0])

sorted_points = sorted(points, key=lambda p: (polar_angle(p), distance_sq(start, p)))

# Remove closer collinear points with same angle, keep farthest

filtered = []

for p in sorted_points:

while len(filtered) > 0 and polar_angle(filtered[-1]) == polar_angle(p):

if distance_sq(start, p) >= distance_sq(start, filtered[-1]):

filtered.pop()

else:

break

else:

filtered.append(p)

if len(filtered) < 3:

return filtered

# Step 3: Build hull using stack

stack = filtered[:2]

for p in filtered[2:]:

while len(stack) >= 2 and orientation(stack[-2], stack[-1], p) <= 0:

stack.pop()

stack.append(p)

return stack

# Example points

points = [(1, 1), (2, 5), (4, 6), (6, 4), (5, 1), (3, 2), (4, 3), (2, 3)]

hull = graham_scan(points)

print("Hull points in order:")

for p in hull:

print(p)

# Plot

x = [p[0] for p in points]

y = [p[1] for p in points]

plt.figure(figsize=(6, 6))

plt.scatter(x, y)

hx = [p[0] for p in hull] + [hull[0][0]]

hy = [p[1] for p in hull] + [hull[0][1]]

plt.plot(hx, hy)

for i, p in enumerate(points):

plt.text(p[0] + 0.05, p[1] + 0.05, f"P{i}")

plt.title("Convex Hull using Graham Scan")

plt.xlabel("X")

plt.ylabel("Y")

plt.grid(True)

plt.axis("equal")

plt.show()

11. Very short narration script

“Graham Scan finds the convex hull by first choosing the bottom-most point, then sorting all other points by angle around it. After that, it scans through the sorted points and removes any point that creates a right turn. In the end, the remaining points form the outer boundary.”

12. One-line summary

Graham Scan sorts points around a starting point and keeps removing inward turns until only the outer hull remains.

I hope this tutorial will create a good foundation for you. If you want tutorials on another topic or you have any queries, please send an mail at contact@spatial-dev.guru.