Voronoi Drift

About this piece

Scatter a few dozen seeds. Every other point on the plate belongs to whichever seed is nearest to it, and the region a single seed owns is its Voronoi cell. The lines you can see are the ties — the points that cannot decide between two seeds — and each one is exactly the perpendicular bisector of a pair of neighbouring seeds. Georgy Voronoy formalised the construction in 1908, but John Snow had already drawn one by hand in 1854, mapping which London houses were nearer the Broad Street pump than any other, to argue that cholera came from water.

It is also everywhere in nature for a dull and honest reason: whenever things grow outward from scattered centres at the same rate and stop where they meet, the boundaries you get are a Voronoi diagram. Dried mud, giraffe markings, grain boundaries in cooled metal, the cracks in glaze.

Built by clipping, not by sampling

Each cell here starts as the whole frame rectangle and is then clipped, one seed at a time, against the half-plane “closer to me than to that one” — the standard Sutherland–Hodgman polygon clip, run once per other seed. That is O(n²) and would be the wrong algorithm at ten thousand seeds; Fortune’s sweepline gets you O(n log n) and exists for exactly that case. At the 24–40 seeds used here it is a few hundred half-plane clips per frame, roughly a third of a millisecond, and it buys real polygon geometry.

The cheap alternative is to decide an owner per pixel on a coarse grid and mark the disagreements. It is faster, and it is what this piece deliberately does not do: sampled walls come out staircased, and on the light theme a staircased hairline reads as a compression artefact rather than as a drawn line. Clipped polygons stay a clean hairline at any window size.

What makes it move

Two forces that never agree. The first is Lloyd relaxation: move each seed to the centroid of its own cell, then rebuild the diagram, and repeat. Its fixed points are centroidal Voronoi tessellations, and they are strikingly even — run it to convergence on random seeds and the cells go nearly hexagonal, which is why the same loop is used for stippling, for mesh generation and for k-means clustering. This piece takes only 5% of that step per frame, so the tessellation is permanently mid-relaxation rather than settled.

The second is a slow two-frequency drift on every seed, which keeps moving the target Lloyd is chasing. Neither wins. That is the whole composition: walls that are always tidying themselves and never finish. Click the canvas to throw the seeds away and start from a fresh scatter — the first second or two after a click is the relaxation doing its most visible work.

What to look for

The clip rectangle is deliberately larger than the window, so the outer boundary of the diagram falls off-screen and every line you can see is a genuine wall between two cells rather than the edge of a box. Watch a wall that separates two cells drifting apart: it does not slide, it pivots, because a bisector is pinned to the midpoint of the two seeds and turns with them. And watch cells with few neighbours grow — a cell with three walls is nearly always one that is about to be squeezed out.

Honest limits: this is the ordinary Euclidean diagram with all seeds weighted equally. Weighted (power) diagrams size each cell to its seed and are far more useful for real work, but under drift they let cells vanish outright, which reads as a glitch rather than as motion. Walls only, no fills — thirty distinct cell colours is not a palette this site has, and flooding a near-black plate with light blocks is how a palette stops being legible. Reduced-motion visitors get the relaxation run 90 steps and then held as a single still frame.

Curious how the loop and canvas fit together? Read how it works →