The tightest enclosing shape
The convex hull of a set of points is the smallest convex polygon that contains them all. Picture stretching a rubber band around the outermost points and letting it snap tight: the resulting outline is the hull. It is a foundational structure for collision bounds, shape analysis, and other geometry.
The turn test
The engine behind hull algorithms is the orientation or turn test. Given three points in order you ask whether the path turns left, turns right, or goes straight. This is decided by the sign of a cross product, computed with only multiplications and subtractions, no square roots or angles. A convex boundary only ever turns one consistent direction.
A common construction
The Graham scan builds the hull by sorting and a single stack pass.
- Sort the points, often by angle around the lowest point or simply by coordinate.
- Walk through them maintaining a stack of hull candidates.
- Before pushing a new point, pop any top that would create a wrong turn, since such a point lies inside.
The sort dominates the cost, and the scan itself is a single linear pass over the sorted points.
Key idea
Use the orientation turn test to keep only points that bend the boundary the right way, building the smallest convex polygon with a sort followed by a single stack scan.