10 · Computational Geometry

What you're watching

The algorithm runs in three visible phases:

1. Pivot search — sweep through every point to find the bottom-most one (greatest screen y; ties broken by smallest x). That point is guaranteed on the hull.
2. Polar sort — gray rays fan out from the pivot to every other point. The algorithm then sorts them by polar angle (counterclockwise, math sense). This is the O(n log n) step.
3. Scan — walk the sorted list, pushing points onto a stack. Before each push, while the top two stack points and the candidate would make a non-CCW turn, the top is popped. Each candidate triggers a flashing dashed triangle: blue if it's kept (left turn), red if the top of stack is popped (right turn).

Why the cross-product test?

Every step of Graham's scan reduces to one question: given three points O, A, B, does the path O → A → B turn left or right? The textbook approach — compute angles with atan2, compare them — is wrong twice over: it's slow (transcendental) and it accumulates floating-point error. The cross product

cross(O, A, B)  =  (A_x − O_x)(B_y − O_y) − (A_y − O_y)(B_x − O_x)

decides the turn direction with two multiplies and a subtract — and if the inputs are integers, the result is exact. Sign convention (in screen coords with y pointing down):

• < 0  O→A→B is a left turn (counterclockwise visually). Keep.
• > 0  O→A→B is a right turn (clockwise visually). Pop.
• = 0  collinear. Pop (the middle point isn't extreme).

The same primitive doubles as the polar-angle comparator: if cross(pivot, A, B) < 0 then A is more CCW than B. No angles ever get computed.

Reading the panel

• Pivot: dark blue dot, labelled. Stays on the hull throughout.
• Hull-so-far: blue polyline; closes into a translucent polygon when the algorithm finishes.
• Candidate: red dot, labelled. This is the point the scan is currently trying to push.
• Test triangle: dashed lines from second-of-stack → top-of-stack → candidate. Red = right turn, top will be popped. Blue = left turn, candidate will be pushed.
• Cross value: shown live next to the test triangle and in the stats row.

Complexity

Graham's scan is O(n log n) overall — but the O(n log n) comes entirely from the polar sort. The actual hull-construction sweep is O(n) amortised: each point is pushed at most once and popped at most once. The visualisation makes this concrete: the comparison counter ticks fast during sort, then slows to a crawl during scan even though the visualisation is doing more.

What I learned writing this

• Screen coordinates flip the cross-product sign. Math convention has y pointing up, so cross > 0 means CCW. In a canvas with y pointing down, that exact same formula gives cross < 0 for visually-CCW. The algorithm doesn't need to convert — just remember to flip the inequality. I burnt half an hour on this before pinning down the sign with a paper triangle.
• Insertion sort beats merge sort for visualization. The textbook calls for O(n log n) sort, but insertion sort makes every comparison and every swap visible as a single animation step. The pedagogical clarity wins over the asymptotic difference (and at n < 50, insertion sort is faster anyway).
• The pivot guarantees correctness. Picking the bottom-most point ensures every other point has a defined polar angle (no point sits at angle "undefined" because it's the origin of the angle). Plus, that point is provably on the hull, so it's a safe anchor to start the stack from. Most algorithm textbooks gloss over this — but it's the load-bearing structural choice.
• Visualizing collinear points is awkward. The algorithm has to handle "cross = 0" (three points in a line), but visually they look identical to two points — there's no obvious "turn" to draw. I settled for treating collinear like a right turn (pop the middle), which is correct because the middle point isn't on the hull.

← Back to all algorithms