Graham Scan
Sort points by angle around the lowest point; keep a stack, popping on right turns.
Decision · step 2 of 12Plane Geometry: Graham scan: sort by angle, keep left turns
The pivot is B (7, 1), the lowest point. It is certainly on the hull, and every other point is now ordered by the angle it makes from here: C, D, H, G, E, F, A.
What you will see
Points are visited in angular order; a right turn pops the previous hull point.
Cost
| Best | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Points announce coordinates and role; each step announces the geometric test and its result in words (left turn, intersects).
Reduced motion: Shapes appear in place; the sweep line jumps between events.
Before this
Related
Taught by the same lesson
Plane Geometry covers these too, in the same run.