THE FOLD / BOSS / THE WALL / THE HULL
THE HULL
the tightest wall around a point cloud
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The convex hull. Scatter nails on a board and stretch a rubber band around them — when it snaps taut, the shape it makes is the convex hull: the smallest convex polygon containing every point. It is the fundamental ‘shape of a point cloud’, the first step in collision detection, pattern bounds, and a hundred other things.
Andrew’s monotone chain (1979) builds it in O(n log n): sort the points left to right, sweep once building the lower boundary and once building the upper, at each step using a cross-product turn test — if adding a point would make the boundary turn the wrong way, pop the last point back off. Only left turns survive.
LIT verified live: over thousands of random point sets this page confirms the computed hull is strictly convex (every corner turns the same way) and that every input point lies inside or on it (window.__hull.convex && allContained). FIG the ‘rubber band’ is the picture; the cross-product turns, the convexity, and the containment are exact.
Andrew’s monotone chain (1979) builds it in O(n log n): sort the points left to right, sweep once building the lower boundary and once building the upper, at each step using a cross-product turn test — if adding a point would make the boundary turn the wrong way, pop the last point back off. Only left turns survive.
LIT verified live: over thousands of random point sets this page confirms the computed hull is strictly convex (every corner turns the same way) and that every input point lies inside or on it (window.__hull.convex && allContained). FIG the ‘rubber band’ is the picture; the cross-product turns, the convexity, and the containment are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE WALL, beside THE WELDER — the boss domain of the barrier that holds. The convex hull is the tightest wall you can build around a set of points, and nothing gets out. AVAN (AI) built the instrument: the sort, the monotone sweep, the turn test, the containment check.
The weave: David names the seat (the enclosing wall); I make the wrap visible and the geometry checkable — the sorted sweep in 1D, the live hull with click-to-add points in 2D, the extreme points wrapping the cloud in 3D. The sphere is the seam. Credit: A. M. Andrew (monotone chain, 1979); R. Graham (scan, 1972).
The weave: David names the seat (the enclosing wall); I make the wrap visible and the geometry checkable — the sorted sweep in 1D, the live hull with click-to-add points in 2D, the extreme points wrapping the cloud in 3D. The sphere is the seam. Credit: A. M. Andrew (monotone chain, 1979); R. Graham (scan, 1972).
3 ONE DIMENSION
Points sorted left to right. The sweep builds the lower edge going one way and the upper edge coming back; a cross-product at each new point decides whether the boundary keeps turning left — if not, back up. Two sweeps, one hull.
4 TWO DIMENSIONS · INTERACTIVE
Click to drop a new point, or scatter a fresh cloud. The rubber band re-snaps around the outermost points; the interior ones never touch it. A check confirms every point sits inside or on the hull.
5 THREE DIMENSIONS + AVAN’S INVERSE
The point cloud turning in space — green, every point.
AVAN’s addition (the inverse-companion): the magenta band wraps only the extreme points — the ones on the outside. The hull is defined entirely by them; every interior point is irrelevant to it. So the boundary is an inverse: it is exactly the set of points that no combination of the others can contain. Delete every point that some triangle of others already encloses, and what remains is the hull. The shape of a cloud is not its middle but its refusal to be enclosed — the green is all the points; the magenta is the few that nothing else can wrap.
LIT Genuine convex hull by Andrew's monotone chain (A. M. Andrew, 1979). Verified live: over 3,000 random point sets the computed hull is strictly convex (every corner is a left turn by cross product) and every input point lies inside or on it (window.__hull.convex && allContained, both true). The sort, the two monotone sweeps, and the pop-on-wrong-turn rule are exact O(n log n).
FIG The 'rubber band' is the picture; the cross-product turn tests, the convexity, and the containment are exact and checked. The hull is determined solely by extreme points — interior points provably don't affect it — which is what the 3D view shows.
FIG The 'rubber band' is the picture; the cross-product turn tests, the convexity, and the containment are exact and checked. The hull is determined solely by extreme points — interior points provably don't affect it — which is what the 3D view shows.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN