Graham Scan

The Algorithm

Graham scan (Ronald Graham, 1972) builds a convex hull in three steps: pick a pivot guaranteed to be on the hull, sort the rest by angle around it, then scan once while maintaining a stack that always turns left.

Pick the point with the lowest $y$ (breaking ties by lowest $x$) as the pivot $p_0$ — it is guaranteed to be a hull vertex, since no other point can be "above" it in every direction.
Sort all remaining points by polar angle around $p_0$, using orientation() as the comparator (never atan2, which is both slower and a source of its own precision issues) — break ties by distance from $p_0$, keeping the nearer point first, since it will be popped as redundant if collinear.
Push $p_0$ and the first two sorted points onto a stack. For every remaining point, while the top three stack entries don't make a left turn, pop the middle one; then push the new point.

from functools import cmp_to_key


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


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


def graham_scan(points):
    pivot = min(points, key=lambda p: (p[1], p[0]))

    def compare(a, b):
        o = orientation(pivot, a, b)
        if o != 0:
            return -1 if o > 0 else 1  # more counterclockwise first
        return -1 if dist_sq(pivot, a) < dist_sq(pivot, b) else 1

    rest = sorted((p for p in points if p != pivot), key=cmp_to_key(compare))

    hull = [pivot]
    for p in rest:
        while len(hull) >= 2 and orientation(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull


pts = [(0, 0), (4, 0), (4, 4), (0, 4), (2, 2), (2, -1)]
print(graham_scan(pts))

#include <algorithm>
#include <vector>

struct Point { double x, y; };

double orientation(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

double distSq(const Point& a, const Point& b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

std::vector<Point> grahamScan(std::vector<Point> points) {
    Point pivot = *std::min_element(points.begin(), points.end(),
        [](const Point& a, const Point& b) {
            return a.y != b.y ? a.y < b.y : a.x < b.x;
        });

    std::sort(points.begin(), points.end(), [&](const Point& a, const Point& b) {
        double o = orientation(pivot, a, b);
        if (o != 0) return o > 0;
        return distSq(pivot, a) < distSq(pivot, b);
    });

    std::vector<Point> hull;
    for (const auto& p : points) {
        while (hull.size() >= 2 &&
               orientation(hull[hull.size() - 2], hull.back(), p) <= 0) {
            hull.pop_back();
        }
        hull.push_back(p);
    }
    return hull;
}

Common Mistakes

Common mistake #1: sorting by atan2(y - pivot.y, x - pivot.x) instead of by the orientation() comparator. It's not just slower — atan2's own floating-point rounding can misorder two points whose true polar angles are extremely close, which is exactly the situation the comparator-based sort handles exactly (an orientation comparison of two integer or exact-rational points is exact, with no trigonometry involved at all).

Common mistake #2: forgetting the tie-breaking rule for points that are exactly collinear with the pivot. Sorting the nearer point first (as in the code above) guarantees that if a farther, collinear point also needs to be popped later, it is popped as a redundant "middle" point rather than accidentally kept while the nearer one is dropped.

Worked Example

Trace It Yourself

Run the algorithm on [(0,0), (4,0), (4,4), (0,4), (2,2), (2,-1)]. The pivot is (2,-1) (lowest $y$). Confirm that (2,2) — an interior point — never survives on the stack, and that the final hull has exactly 5 vertices, not 6.

Graham scan and Andrew's monotone chain solve the identical problem with the identical stack invariant; the only real difference is the sort key used before the scan begins.

Cookie Consent

Graham Scan

The Algorithm

Common Mistakes

Trace It Yourself

Related Reading

Convex Hulls in the Plane