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.

Draw your own

The snippet below is this plate in 29 lines of HTML and plain JavaScript with no library. It keeps the plate’s rule and its constants: one site per 21,000 px² of window, never fewer than 24 or more than 40, scattered over a box that overhangs the window by 7 % of its short side; one site in five coral; 5 % of a Lloyd step per frame against a two-frequency drift of 0.22 % of the short side; and the plate’s 45 warm-up frames before the first paint. The one change is the method. The plate clips exact polygons. This code does the cheap thing described above: it labels a grid. Every 3×3 px block gets the index of its nearest site, a block whose right or lower neighbour has a different owner is painted as wall, and a cell’s centroid is the average of its blocks’ centres. The Lloyd’s algorithm article on Wikipedia calls that pixel grid “a common simplification”. It is also why the walls here step in 3 px stairs where the plate’s are hairlines, and why the cells carry a 10 % tint: once every block has an owner, colouring it is free. The plate draws walls only. The snippet leaves out what exists for the gallery: click to re-scatter, sharp drawing on high-density screens (it draws in CSS pixels), and resizing (reload to resize).

• Grid. At 1280×720 the box is 1381×821 px, so own holds 461×274 = 126,314 blocks. There are 40 sites, and every block centre is tested against every site, so a frame makes 5.05 million distance comparisons. nearest() compares dx² + dy² and never takes a square root, because squaring does not change which distance is smaller.
• Rule. The Voronoi diagram article defines a seed’s cell as all points of the plane closer to that seed than to any other. Lloyd’s step, from the same Lloyd’s algorithm article (Stuart P. Lloyd, Bell Labs, 1957; unpublished until 1982), is: build the diagram, find each cell’s centroid, and move each site there. relax(P, c, 1) is that textbook step, and the plate calls it with 0.05. Measured on this code: 40 seeded sites on 1280×720 and five full steps take the mean site-to-centroid distance from 36.7 px to 16.8, 10.8, 7.7, 5.8 and 4.6 px.
• Speed. cells() takes about 5.3 ms a frame at 1280×720, and 1.1 ms on a 390×844 phone screen with 24 sites, in Node on the machine that built this page. The cost is sites × blocks, so halving BLOCK quadruples it. Fortune’s sweepline, which the Voronoi article gives as O(n log n), is what you would use for thousands of sites. Like the plate, the snippet counts frames, not seconds (t grows by 0.03 a frame), so a 120 Hz screen drifts twice as fast.
• Colour. The ground, the cobalt and the coral come from this site’s palette, light or dark to match your device. The walls use the plate’s opacities, 0.42 + 0.18×pulse for cobalt and 0.50 + 0.18×pulse for coral, where pulse = 0.5 + 0.5 sin(0.33 t). The seeds are 1.15 px dots at 0.85. Under reduced motion it runs the 45 warm-up steps, draws one frame and stops.

Things worth changing: PULL = 1 runs textbook Lloyd every frame, and the drift is left as the only thing keeping the cells from settling. BLOCK = 1 gives pixel-exact walls at nine times the cost. Replace dx * dx + dy * dy with Math.abs(dx) + Math.abs(dy) and you get the Manhattan diagram, whose walls run horizontal, vertical or at 45°. It still looks like a tessellation, which is why the test plants exactly that change and checks owners against a brute-force Euclidean search rather than looking at the picture. Two honest limits. A centroid averaged over 3 px blocks is an estimate, and a site sitting in a cell with no block centre keeps its place. Also, the falling distance above was measured on five steps. The article’s guarantee is about squared distance to every point of the cell, not about this mean, so treat “it falls every step” as what happened here, not as a proof.

<canvas id="cells" style="position:fixed; inset:0"></canvas>
<script>
const dark = matchMedia('(prefers-color-scheme: dark)').matches, still = matchMedia('(prefers-reduced-motion: reduce)').matches;
const [ground, cool, warm] = dark ? [[11, 13, 18], [150, 180, 255], [255, 120, 84]] : [[231, 226, 213], [40, 72, 205], [190, 68, 28]];
const MARGIN = 0.07, FEW = 24, MANY = 40, AREA = 21000, PULL = 0.05, AMP = 0.0022, HOT = 0.2, DT = 0.03, WARMUP = 45, PULSE = 0.33;  // the plate's constants
const BLOCK = 3, TINT = 0.1;  // this snippet only: one owner per 3x3 px block, and cells tinted at 10 % (the plate draws walls alone)
// the owner of (x, y) is the nearest site, by squared Euclidean distance (no square root needed to compare)
function nearest(P, x, y) { let best = 0, bd = Infinity; for (let i = 0; i < P.length; i++) { const dx = x - P[i].x, dy = y - P[i].y, d = dx * dx + dy * dy; if (d < bd) { bd = d; best = i; } } return best; }
// label every block centre in the box with its owner, and average each cell's blocks into its centroid
function cells(P, box, s) { const nx = Math.ceil((box[2] - box[0]) / s), ny = Math.ceil((box[3] - box[1]) / s), own = new Int32Array(nx * ny), sx = new Float64Array(P.length), sy = new Float64Array(P.length), n = new Float64Array(P.length);
  for (let j = 0; j < ny; j++) for (let i = 0; i < nx; i++) { const x = box[0] + (i + 0.5) * s, y = box[1] + (j + 0.5) * s, o = nearest(P, x, y); own[j * nx + i] = o; sx[o] += x; sy[o] += y; n[o]++; }
  return { nx, ny, own, cx: P.map((p, i) => n[i] ? sx[i] / n[i] : p.x), cy: P.map((p, i) => n[i] ? sy[i] / n[i] : p.y) }; }
// one Lloyd step, taken k of the way: each site moves toward its cell's centroid (k = 1 is the textbook step)
function relax(P, c, k) { P.forEach((p, i) => { p.x += (c.cx[i] - p.x) * k; p.y += (c.cy[i] - p.y) * k; }); }
const cv = document.getElementById('cells'), ctx = cv.getContext('2d'), img = document.createElement('canvas'), ic = img.getContext('2d'), R = Math.random, TAU = 2 * Math.PI;
const W = cv.width = innerWidth, H = cv.height = innerHeight, m = Math.min(W, H) * MARGIN, box = [-m, -m, W + m, H + m];  // the box overhangs the window, so its edge is never seen
const P = Array.from({ length: Math.max(FEW, Math.min(MANY, Math.round(W * H / AREA))) }, () => ({ x: box[0] + R() * (box[2] - box[0]), y: box[1] + R() * (box[3] - box[1]), w1: 0.09 + R() * 0.13, p1: R() * TAU, w2: 0.07 + R() * 0.15, p2: R() * TAU, hot: R() < HOT }));
let t = 0, c;
function step() { c = cells(P, box, BLOCK); relax(P, c, PULL); const a = Math.min(W, H) * AMP;  // Lloyd pulls, a slow two-frequency drift pushes back
  for (const p of P) { p.x = Math.min(box[2], Math.max(box[0], p.x + Math.cos(t * p.w1 + p.p1) * a)); p.y = Math.min(box[3], Math.max(box[1], p.y + Math.sin(t * p.w2 + p.p2) * a)); } t += DT; }
const mix = (ink, a) => ground.map((g, k) => g + (ink[k] - g) * a);
function draw() { const { nx, ny, own } = c, im = ic.createImageData(nx, ny), d = im.data, pulse = 0.5 + 0.5 * Math.sin(t * PULSE);
  const fill = P.map((p) => mix(p.hot ? warm : cool, TINT)), wall = P.map((p) => p.hot ? mix(warm, 0.5 + 0.18 * pulse) : mix(cool, 0.42 + 0.18 * pulse));
  for (let q = 0; q < nx * ny; q++) { const o = own[q], edge = (q % nx < nx - 1 && own[q + 1] !== o) || (q + nx < nx * ny && own[q + nx] !== o); d.set(edge ? wall[o] : fill[o], q * 4); d[q * 4 + 3] = 255; }
  img.width = nx; img.height = ny; ic.putImageData(im, 0, 0); ctx.imageSmoothingEnabled = false; ctx.drawImage(img, box[0], box[1], nx * BLOCK, ny * BLOCK);
  for (const p of P) { ctx.fillStyle = 'rgba(' + (p.hot ? warm : cool) + ',0.85)'; ctx.beginPath(); ctx.arc(p.x, p.y, 1.15, 0, TAU); ctx.fill(); } }
for (let i = 0; i < WARMUP; i++) step();  // the plate's warm-up: 45 frames of relaxation before the first paint
const frame = () => { step(); draw(); requestAnimationFrame(frame); }; draw(); if (!still) requestAnimationFrame(frame);  // reduced motion: one still frame
</script>

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