A simpler hull recipe
Andrew monotone chain computes the same convex hull as Graham scan but avoids angle computation. It sorts points by x coordinate, breaking ties by y, then builds the hull in two passes.
Building two chains
First sweep left to right to build the lower hull. For each point, while the last two hull points and the new point make a non left turn, pop the last point, then push.
- Sweep again right to left for the upper hull using the same rule.
- Concatenate the two chains, dropping the duplicated endpoints.
The result is the full boundary in counterclockwise order.
Why it is appealing
Because it sorts by coordinate rather than angle, the comparison is trivial and totally ordered, which sidesteps the fragile angular ties that plague Graham scan. The orientation pop rule is identical for both chains, so the code is short and symmetric.
Cost
The sort dominates the work, and each chain pass is linear since every point is pushed and popped at most once across a chain.
Key idea
The monotone chain sorts points by coordinate, then sweeps once each way popping non left turns to form lower and upper chains, joining them into a clean convex hull without any angle math.