Convex Hull Construction Screensaver
The Convex Hull Construction screensaver runs a real live Graham scan, building the tightest polygon that wraps a random point cloud, step by step. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Convex Hull Construction screensaver works
The saver scatters a real random cloud of points, then sorts them by angle around the lowest point, exactly as a real Graham scan requires.
It then walks the sorted points, pushing each onto a stack and popping back whenever three consecutive points would turn the wrong way.
Each push and pop is drawn live, so you watch the real hull boundary tighten into shape point by point.
Once the full convex hull is closed, it holds briefly, then a fresh random point cloud and hull build begins.
The rubber band around a point cloud
The convex hull of a set of points is the smallest convex shape that contains them all. A common picture is a rubber band stretched around nails in a board: when released it snaps to the hull. A shape is convex if the line between any two of its points stays inside it, so the hull has no dents.
Ronald Graham published his scan in 1972. Its cost is dominated by the sorting step, which takes on the order of n log n time; the stack walk afterwards is linear. The decisive test is the cross product of two vectors, whose sign says whether three points make a left (counter-clockwise) turn or a right (clockwise) turn, and zero means they are collinear. A right turn means the middle point cannot be on the hull, so it is popped. Other algorithms exist, such as Andrew’s monotone chain and the gift-wrapping method, called the Jarvis march after R. A. Jarvis (1973), which runs in time proportional to the number of points times the number of hull vertices and so suits hulls with few corners.
Hulls are used in collision detection for games and robotics, in geographic analysis to bound a set of locations, in pattern recognition, and as a building block for other geometric constructions. Implementations need a rule for collinear points and duplicates, since floating-point arithmetic can misjudge a turn that is almost straight.
A worked example
A point that sits just inside the current boundary gets popped back off the hull the moment a later point makes the turn direction invalid, exactly matching the real Graham scan rule.
Settings & tips
- Accent recolours the hull boundary.
- The point cloud is real and randomized every run.
- A fresh point cloud generates automatically once the hull closes.
Frequently asked questions
- Is this a real computational geometry algorithm?
- Yes — a real, correct Graham scan implementation, run live on a randomized point cloud.
- What is a convex hull?
- The smallest convex polygon that contains every point in the set — a real, well-defined geometric shape.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- What is the cross product test in Graham scan?
- For three consecutive points it computes a signed area. A positive sign means a counter-clockwise turn, a negative sign a clockwise turn, and zero means the points are collinear.
- How fast can a convex hull be computed?
- Graham scan takes O(n log n) time, dominated by sorting. Output-sensitive methods such as the Jarvis march take O(nh) for h hull vertices, which can be faster when the hull is small.
- Does the idea work in three dimensions?
- Yes, the hull of a 3D point set is a polyhedron, and algorithms such as quickhull compute it. The ideas get more elaborate, but the picture of shrink-wrapping the points remains.