Last week I sent you off with a promise tucked in your back pocket. We'd spent the whole episode ruling off tidy little cells with a compass and straightedge - grids, hexagons, the seventeen wallpaper groups - and right at the end I said: what if we stopped being so tidy? What if, instead of drawing the boundaries ourselves, we scattered a handful of points on the plane and let them fight it out for territory? Let each point claim everywhere that's closer to it than to any other point, and let the borders fall wherever they fall. Allez, today we cash that promise, and it leads us to one of the most useful and beautiful structures in all of generative art: the Voronoi diagram.
Here's the whole idea in one sentence, and honestly it's so simple it feels like it shouldn't be this powerful. Drop some points on a canvas. Call them seeds. Now for every other spot on the canvas, ask one question: which seed am I closest to? Colour that spot to match its nearest seed. Do that everywhere, and the plane carves itself into regions - one region per seed - with borders exactly halfway between neighbours. No compass. No angles adding to 360. Just distance, and the plane sorts itself out. Let me show you what I figured out about building these, because once you can make a Voronoi diagram you've unlocked cracked mud, giraffe skin, stained glass, cell tissue, shattering glass, and stippled pen-plotter portraits - all from the same tiny idea.
Before anything fancy, let's nail the core. Everything in a Voronoi diagram comes down to measuring distance from a point to a seed. That's our old friend Pythagoras from the trig episode - the straight-line distance between two points.
// straight-line (Euclidean) distance between two points.
// this is just Pythagoras: the hypotenuse of the dx, dy right triangle.
function distance(ax, ay, bx, by) {
const dx = ax - bx;
const dy = ay - by;
return Math.sqrt(dx * dx + dy * dy);
}
Now here's a tiny trick that matters a lot when you're doing this millions of times: if all you want is which seed is nearest, you never need the actual distance. The square root is monotonic - bigger distance means bigger squared-distance - so comparing dx*dx + dy*dy gives the exact same winner without ever calling Math.sqrt. On a full-canvas Voronoi that's thousands of square roots you just deleted. Little wins like that are the difference between a laggy sketch and a smooth one.
// find the index of the seed nearest to pixel (px, py).
// we compare SQUARED distance - no sqrt needed to pick a winner, and it's much faster.
function nearestSeed(px, py, seeds) {
let best = 0;
let bestDist = Infinity;
for (let i = 0; i < seeds.length; i++) {
const dx = px - seeds[i].x;
const dy = py - seeds[i].y;
const d = dx * dx + dy * dy; // squared distance
if (d < bestDist) {
bestDist = d;
best = i;
}
}
return best;
}
That little function is the Voronoi diagram, really. Everything else is just calling it a lot and colouring the result.
There are clever, fast algorithms for Voronoi diagrams - Fortune's sweepline being the famous one, running in O(n log n) - and we'll nod at it later. But I'm a big believer in building the dumb version first, because the dumb version is where the understanding lives. The dumb version is: walk every single pixel, find its nearest seed, colour it. That's it. Let me set up some seeds with random positions and colours.
// scatter n seeds, each with a random position and a random colour.
function makeSeeds(n, w, h) {
const seeds = [];
for (let i = 0; i < n; i++) {
seeds.push({
x: Math.random() * w,
y: Math.random() * h,
color: [
(Math.random() * 200 + 30) | 0, // keep it out of pure black/white
(Math.random() * 200 + 30) | 0,
(Math.random() * 200 + 30) | 0,
],
});
}
return seeds;
}
Now the painting. We can't use fillRect per pixel - way too slow - so we grab the raw pixel buffer with createImageData, write four bytes (R, G, B, A) per pixel directly, and blit the whole thing back in one putImageData. We touched pixel buffers back in the pixel-manipulation episode, so this'll feel familiar.
// brute-force Voronoi: for every pixel, find its nearest seed and colour it.
function drawVoronoi(ctx, seeds) {
const w = ctx.canvas.width;
const h = ctx.canvas.height;
const img = ctx.createImageData(w, h);
for (let y = 0; y < h; y++) {
for (let x = 0; x < w; x++) {
const s = nearestSeed(x, y, seeds);
const idx = (y * w + x) * 4; // 4 bytes per pixel: R G B A
const c = seeds[s].color;
img.data[idx] = c[0];
img.data[idx + 1] = c[1];
img.data[idx + 2] = c[2];
img.data[idx + 3] = 255; // fully opaque
}
}
ctx.putImageData(img, 0, 0);
}
Run drawVoronoi(ctx, makeSeeds(20, w, h)) and boom - twenty coloured cells, each a little irregular polygon, borders running exactly halfway between neighbouring seeds. That's a Voronoi diagram. I still get a small kick every time one appears, because there's something so organic about it - it looks grown, not drawn. Makes sense, right? It's the same rule cells in your body follow when they pack together, the same rule that cracks drying mud. Nature reaches for Voronoi constantly because "everywhere closest to me" is the most natural definition of territory there is.
Want to actually see the seeds? Drop a dot at each one so you can watch the borders sit halfway between them.
// draw the seed points on top, so you can see the border sits halfway between them.
function drawSeeds(ctx, seeds) {
ctx.fillStyle = "#101014";
for (const s of seeds) {
ctx.beginPath();
ctx.arc(s.x, s.y, 3, 0, Math.PI * 2);
ctx.fill();
}
}
Here's where it gets fun, and it's a one-line change. We measured distance with Pythagoras - straight-line, "as the crow flies". But that's a choice. What if distance meant "how far a taxi drives on a grid of streets", where you can only move horizontally and vertically? That's Manhattan distance, and swapping it in warps every cell border into stark diagonal-and-straight edges. Same seeds, completely different mood.
// Manhattan (taxicab) distance: no diagonals, you walk the grid.
// swap this into nearestSeed and the round-ish cells snap into blocky crystal shapes.
function nearestManhattan(px, py, seeds) {
let best = 0;
let bestDist = Infinity;
for (let i = 0; i < seeds.length; i++) {
const d = Math.abs(px - seeds[i].x) + Math.abs(py - seeds[i].y);
if (d < bestDist) {
bestDist = d;
best = i;
}
}
return best;
}
Try it. The cells go all angular and faceted, like cut gemstones. Now imagine going further - Chebyshev distance (the max of dx and dy, giving square-ish cells), or even weird fractional power distances. Each metric is a different ruler, and the ruler you pick is a huge creative lever. This is the kind of thing I love pointing out: the algorithm didn't change one bit, only our definition of "near" did, and the whole aesthetic flipped. That's generative art in a nutshell - tiny rule change, massive visual payoff.
Now for the part that genuinly blew my mind the first time I understood it. Every Voronoi diagram has a secret twin hiding inside it, and they are two views of the exact same information. Take your seeds. Connect two seeds with a line if and only if their Voronoi cells share a border. Do that for every pair, and you get a mesh of triangles covering all your seeds. That mesh is the Delaunay triangulation, and it is the dual of the Voronoi diagram - flip one and you get the other, for free.
Why do we care? Because triangles are the currency of computer graphics. A Delaunay triangulation gives you the "nicest" possible triangles from a scatter of points - it avoids thin slivery triangles and prefers fat, well-proportioned ones. That makes it the go-to for terrain meshes, for turning scattered elevation samples into a smooth 3D surface, for finish-line stuff like that low-poly art style where a photo becomes a mosaic of flat triangles. Same points, two structures, endless uses.
The magic property that defines it: a triangle belongs to the Delaunay triangulation if its circumcircle - the unique circle passing through all three of its corners - contains no other seed inside it. Empty circumcircle, valid triangle. That one rule is the whole thing. So first, let me compute a circumcircle from three points.
// the circumcircle of a triangle: the unique circle through all three corners.
// returns its centre (x, y) and radius r, or null if the points are collinear.
function circumcircle(a, b, c) {
const ax = a.x, ay = a.y, bx = b.x, by = b.y, cx = c.x, cy = c.y;
const d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));
if (Math.abs(d) < 1e-9) return null; // three points on a line - no circle
const a2 = ax * ax + ay * ay;
const b2 = bx * bx + by * by;
const c2 = cx * cx + cy * cy;
const ux = (a2 * (by - cy) + b2 * (cy - ay) + c2 * (ay - by)) / d;
const uy = (a2 * (cx - bx) + b2 * (ax - cx) + c2 * (bx - ax)) / d;
return { x: ux, y: uy, r: Math.hypot(ax - ux, ay - uy) };
}
That formula looks scary but it's just solving "find the point equidistant from all three corners" - which is precisely what a circumcenter is. Don't memorise it; understand what it gives you and keep it in your toolkit. Now the naive triangulation: check every possible triple of seeds, and keep the ones whose circumcircle is empty.
// naive Delaunay: test every triple of points, keep triangles with an EMPTY circumcircle.
// this is O(n^4) - slow, but crystal clear. it's how you LEARN the property.
function delaunay(points) {
const triangles = [];
const n = points.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
const cc = circumcircle(points[i], points[j], points[k]);
if (!cc) continue;
let empty = true;
for (let m = 0; m < n; m++) {
if (m === i || m === j || m === k) continue;
const dx = points[m].x - cc.x;
const dy = points[m].y - cc.y;
// is seed m strictly inside this circumcircle? then the triangle is illegal.
if (dx * dx + dy * dy < cc.r * cc.r - 1e-6) { empty = false; break; }
}
if (empty) triangles.push([i, j, k]);
}
}
}
return triangles;
}
I want to be honest with you: this is the slow, brute version. It's O(n to the fourth), so it's fine for a few dozen points and it'll crawl for hundreds. The real-world tools use Bowyer-Watson incremental insertion or a divide-and-conquer approach to hit O(n log n), and libraries like d3-delaunay do it blazingly fast. But you don't reach for a library until you've felt the empty-circumcircle rule in your own hands. So play with this one at small n first. Drawing the mesh is easy - each triangle is three line segments.
// draw the triangle mesh: each triangle is just three corners connected.
function drawTriangles(ctx, points, triangles) {
ctx.strokeStyle = "#e8e8ee";
ctx.lineWidth = 1;
for (const [i, j, k] of triangles) {
ctx.beginPath();
ctx.moveTo(points[i].x, points[i].y);
ctx.lineTo(points[j].x, points[j].y);
ctx.lineTo(points[k].x, points[k].y);
ctx.closePath();
ctx.stroke();
}
}
Draw the Voronoi cells and the Delaunay mesh on the same seeds and stare at them together - you'll see it. Every Delaunay edge crosses exactly one Voronoi border, at a right angle, right in the middle. Two structures, one truth. It's one of those maths facts that feels almost too neat to be real.
Pure random seeds give you cells of wildly different sizes - some tiny, some huge, all lopsided. Sometimes that's exactly the messy-organic look you want. But often you want something calmer: cells that are roughly equal, evenly spread, that pleasing "blue noise" texture where nothing clumps and nothing gaps. There's a gorgeous iterative trick for that, and it's called Lloyd relaxation.
The move is dead simple. For each cell, find its centroid - its centre of mass, the average position of all the pixels inside it. Then teleport the seed to that centroid. Repeat. Each pass, seeds drift toward the middle of their own territory, cells even out, and after a handful of iterations the whole thing settles into a beautifully regular honeycomb-ish spread. This is a centroidal Voronoi diagram, and it's one of my favourite algorithms in the world because it's basically the cells politely negotiating fair borders with each other.
// one Lloyd step: move every seed to the centre of mass of its own cell.
// we sample pixels (every 2px for speed) to estimate each cell's centroid.
function lloydStep(seeds, w, h) {
const sumX = new Array(seeds.length).fill(0);
const sumY = new Array(seeds.length).fill(0);
const count = new Array(seeds.length).fill(0);
for (let y = 0; y < h; y += 2) {
for (let x = 0; x < w; x += 2) {
const s = nearestSeed(x, y, seeds);
sumX[s] += x;
sumY[s] += y;
count[s]++;
}
}
for (let i = 0; i < seeds.length; i++) {
if (count[i] > 0) {
seeds[i].x = sumX[i] / count[i]; // centroid = average of the cell's pixels
seeds[i].y = sumY[i] / count[i];
}
}
}
Wrap that in a loop and watch the magic happen over a few iterations. Honestly, animate it - redraw after each step - because watching the seeds shuffle themselves into an even lattice is mesmerising, like watching soap bubbles settle.
// run several relaxation passes. 3 to 8 iterations is usually plenty.
function relax(seeds, w, h, iterations) {
for (let i = 0; i < iterations; i++) {
lloydStep(seeds, w, h);
// (redraw here each pass if you want to animate the settling)
}
}
The first pass does most of the work; by pass five or six it's barely moving. That convergence is the diagram telling you it's found a comfortable equilibrium - the centroidal state where every seed already sits at its own centre. Tidy from chaos, and you never told any single seed where to go. They sorted it out amongst themselves.
Let me pull this out of the abstract, because Voronoi shows up in more real creative work than almost anything else we've covered. A few of my favourites:
Stippling. This is the big one for pen-plotter people (remember the plotter episode?). You want to render a photo as thousands of ink dots, denser where the image is dark. The trick: run a weighted Lloyd relaxation, where each pixel pulls on its seed with a strength based on how dark the source image is there. Dots migrate toward the shadows and spread out in the highlights, and you get those stunning stipple portraits that look hand-drawn. Same relaxation loop, just weighted.
// weighted Lloyd for stippling: pull each seed toward the DARK mass of its cell.
// darkness(x, y) returns 0..1 - how dark the source image is at that pixel.
function weightedLloydStep(seeds, w, h, darkness) {
const sx = new Array(seeds.length).fill(0);
const sy = new Array(seeds.length).fill(0);
const sw = new Array(seeds.length).fill(0);
for (let y = 0; y < h; y += 2) {
for (let x = 0; x < w; x += 2) {
const weight = darkness(x, y); // darker pixels pull harder
const s = nearestSeed(x, y, seeds);
sx[s] += x * weight;
sy[s] += y * weight;
sw[s] += weight;
}
}
for (let i = 0; i < seeds.length; i++) {
if (sw[i] > 0) {
seeds[i].x = sx[i] / sw[i]; // weighted centroid, not plain average
seeds[i].y = sy[i] / sw[i];
}
}
}
Shattering and cracks. Want to break a shape like glass, or draw the cracks in dried mud or old paint? Scatter seeds, build the Voronoi cells, and treat each cell as a shard. Push the shards apart from a centre and you've got an explosion. The cell borders are the crack lines. It's the cheapest convincing shatter effect there is, and it's the same diagram we've been building all along - you're just reading the borders as fractures instead of colouring the interiors.
Organic texture. Giraffe coats, cracked lava, cell tissue, cobblestones, stained glass, the crackle in old ceramics - all Voronoi. Colour the cells, outline them dark, add a little noise (from the noise episode) to jitter the borders so they aren't perfectly straight, and you've got instant natural-looking texture. Here's the jitter idea - perturb each border pixel's lookup with a touch of noise so the edges wobble like real cracks.
// nudge the sampling point with a little noise before finding its cell,
// so the borders wobble organically instead of being laser-straight.
function organicNearest(px, py, seeds, noise) {
const jx = px + noise(px * 0.02, py * 0.02) * 12; // noise-warped lookup
const jy = py + noise(px * 0.02 + 100, py * 0.02) * 12;
return nearestSeed(jx, jy, seeds);
}
Swap organicNearest in for nearestSeed inside your paint loop and the sharp cell borders turn into hand-cracked, natural-looking seams. That combo - a clean structural algorithm plus a dusting of noise to rough it up - is one of the most reliable recipes in the whole generative toolbox. I use some version of it constantly.
Look back at the ladder we climbed today. We started with a single question - who's my nearest seed? - and painted a whole plane of organic cells from it. We swapped the ruler from Pythagoras to Manhattan and watched round cells snap into crystals. We uncovered the Delaunay triangulation, the secret twin of every Voronoi diagram, defined by the empty-circumcircle rule, and saw that flipping one gives you the other for free. We relaxed the chaos into an even, calm honeycomb with Lloyd's centroid trick. And we saw where it all cashes out - stippled portraits, shattering glass, giraffe skin, terrain meshes. All from distance, the humblest idea in geometry.
So this week's homework, and it's a proper playground: get drawVoronoi and relax running together. Scatter fifty seeds, colour them, then hit them with three or four Lloyd passes and watch the mess turn into order in front of you. Then push on the levers - swap in Manhattan distance, crank the seed count, feed the weighted version a dark blob so dots swarm toward it. Feel how a single distance rule generates this much variety. That intuition is worth more than any formula.
And here's the thread I want you carrying into next time. All episode we've been dividing space - carving the plane into separate regions, each seed keeping to its own patch. But there's a completely opposite way to relate to space that's just as magical. Instead of cutting the plane into pieces, what if we tried to thread it - to draw a single, unbroken line that visits every corner of a region without ever crossing itself, folding through the plane so tightly that it eventually touches everywhere? A curve that fills space. It sounds impossible, almost paradoxical, and it's one of the strangest and most beautiful ideas in mathematics - and it's exactly where we go next. 't Was plezant to grow some cells with you - now go scatter some seeds and watch them find their borders :-).
dx*dx + dy*dy is all you compare. Thousands of square roots deleted, sketch stays smoothSo that's spatial division, from a single "who's nearest?" question all the way to stipple portraits and shattering glass, and every step of it was just distance quietly doing its job. The big takeaway, one more time: scatter points, let each claim what's closest, and the plane organises itself into something that looks grown rather than drawn. Go get the seeds relaxing and swap that ruler around until a texture surprises you - that surprise is the whole point. And hold onto the flipside I left you with, because next time we stop dividing space and start threading it with a single line that somehow fills the entire plane. Merci voor het lezen, en tot de volgende keer :-).
Sallukes! Thanks for reading.
X
@femdev