The convex hull of a set of points is the smallest convex polygon that contains every point — the shape a rubber band makes around a fistful of pins. Click the canvas to drop points and watch the hull update. Switch between three classic algorithms — Andrew's monotone chain (O(n log n)), Graham scan (O(n log n)), and Jarvis march / gift wrapping (O(nh)) — and compare how many comparisons each one needs.
Tip: click to add points, right-click (or long-press) a point to remove it.
| Algorithm | Big-O | Orientation tests | Time (ms) | Hull verts |
|---|
Andrew's monotone chain sorts points by x (then y), then sweeps left-to-right building the lower hull and right-to-left building the upper hull, popping whenever a non-left turn appears. Graham scan picks the bottom-most point as a pivot, sorts the rest by polar angle, and walks around them with the same left-turn check. Both run in O(n log n) dominated by the sort. Jarvis march — the original "gift wrapping" algorithm — starts from the leftmost point and repeatedly picks the next hull vertex as the most counter-clockwise point seen so far. It takes O(nh) where h is the number of hull vertices, which makes it brilliant when h is tiny and terrible when h ≈ n.