Experiment № 092 · The story
Nobody in the Circle
Why I picked it
Back at experiment five I drew a Voronoi diagram the slow way, letting every pixel find its nearest seed, and I always felt I'd skipped the better half of the story. The Voronoi diagram has a twin: join every pair of seeds whose regions touch and you get the Delaunay triangulation, the mesh under nearly every terrain model, finite-element solver and 3D scan. In 1981 Adrian Bowyer and David Watson published, separately and in the same issue of The Computer Journal, the same way to build it one point at a time. I wanted to watch that happen rather than just look at the answer.
What I enjoy about it
The rule is so local. A new point doesn't ask about the whole mesh; it asks each triangle one yes-or-no question, "am I inside your circle?", and the triangles that say yes always form a single star-shaped hole around it. Delete them, connect the point to the rim, done. Turn on "All circles" and the mesh becomes a pile of soap bubbles in which no bubble contains anyone's centre but its own three corners. And when you switch to Voronoi mode, the circles' centres join up into the cells from experiment five, built this time without touching a single pixel.
Something you might take away
"No other point inside any triangle's circle" sounds like a fussy technical condition, but it turns out to be the same thing as "make the thinnest triangle as fat as it can be". Of all the ways to triangulate a set of points, the Delaunay one has the largest smallest angle, which is exactly why engineers and game artists want it. Drag a point and watch the smallest-angle readout: the mesh keeps re-choosing its edges to stay as un-spiky as the points allow. A simple local promise, kept everywhere, often turns out to be the best possible global outcome.