Scatter some points, then colour every position in the plane by whichever point is nearest. The boundaries that appear were never drawn: they are just where the answer changes.
Move the cursor over the canvas — it is part of the simulation.
Drag your finger across the canvas — it is part of the simulation.
Your cursor is a site. Move it slowly near a boundary and watch cells that are nowhere near you change shape, because adding a site steals area from everyone whose territory it touches. Then switch the distance to Manhattan and the whole world turns into city blocks without a single site moving.
The definition, and it is the whole thing. Each cell is the set of points closer to one site than to any other. Everything else, including the fact that the cells are convex polygons, is a consequence.
Euclidean, Manhattan, Chebyshev. Change which one you mean by nearest and the cell walls stop being straight-line bisectors: Manhattan gives staircase boundaries, Chebyshev gives boxes. The sites never moved.
Connect every pair of sites whose cells touch and you get the Delaunay triangulation, the triangulation that maximises the smallest angle. Two of the most used structures in computational geometry are the same object seen from two sides.
Brute force on purpose: a coarse grid where every cell asks every site who is closest, then the result is scaled up with smoothing. Fortune's sweep-line algorithm would build the exact diagram in O(n log n), but it needs a priority queue and careful degenerate-case handling, and here the sites move every frame so the diagram would be rebuilt anyway. Borders are found by checking whether a pixel's owner differs from its right or lower neighbour, which is one comparison instead of any geometry.
Cut straight from lab.js. These are the real lines that run above, not a simplified version.
const dist = (dx, dy) =>
met === 0 ? dx * dx + dy * dy
: met === 1 ? Math.abs(dx) + Math.abs(dy)
: Math.max(Math.abs(dx), Math.abs(dy));The diagram is defined by a distance, and swapping the distance swaps the geometry. Euclidean skips the square root because only the ordering matters and squaring is monotonic. Manhattan is city blocks, Chebyshev is how a king moves. Same sites, entirely different world.
const RES = 150, RH = Math.max(1, Math.round((RES * h) / w));
const own = new Int16Array(RES * RH);
for (let j = 0; j < RH; j++) {
const y = ((j + 0.5) / RH) * h;
for (let i = 0; i < RES; i++) {
const x = ((i + 0.5) / RES) * w;
let best = 1e18, bi = 0;
for (let s = 0; s < pts.length; s++) {
const d = dist(x - pts[s].x, y - pts[s].y);
if (d < best) { best = d; bi = s; }
}
own[j * RES + i] = bi;Every grid cell asks every site who is closest. Fortune's sweep-line would do it exactly in O(n log n), but it needs a priority queue and careful handling of degenerate cases, and here the sites move every frame so the diagram would be rebuilt regardless. At this resolution the naive loop costs under a millisecond.
const edge = (i + 1 < RES && own[q + 1] !== id) || (j + 1 < RH && own[q + RES] !== id);
const a = edge ? 0.9 : 0.05 + ((id * 37) % 100) / 100 * 0.22;
d[o] = rgb[0] * a; d[o+1] = rgb[1] * a; d[o+2] = rgb[2] * a; d[o+3] = 255;No geometry is computed to find the cell walls. A pixel is on a border if its owner differs from the neighbour to its right or below — one comparison. The bisector lines you see were never constructed; they are just where the answer changes, which is also exactly what a Voronoi edge is.
John Snow drew one by hand in 1854 around the water pumps of London and used it to argue that cholera came from a single pump on Broad Street. The same diagram is used for cell shapes in tissue, coverage areas for antennas, mesh generation for simulation, and crystal grain boundaries, which grow into exactly this because each seed claims what is nearest.
Everything above, in one piece. This is the entire experiment as it lives in lab.js.
{ id: 'voronoi',
name: L('Voronoi', 'Voronoi'),
note: L('Every point belongs to whoever is nearest. Change what "near" means and the world changes shape.',
'Cada punto pertenece a quien tenga más cerca. Cambia qué significa "cerca" y el mundo cambia de forma.'),
params: [
{ key: 'sites', label: L('Sites', 'Sitios'), min: 3, max: 40, step: 1, def: 14 },
{ key: 'speed', label: L('Drift', 'Deriva'), min: 0, max: 3, step: 0.1, def: 0.8 },
{ key: 'metric', label: L('Distance', 'Distancia'), min: 0, max: 2, step: 1, def: 0 }
],
make(w, h) {
let S = [], K = 0;
const seed = (n, w, h) => {
S = []; K = n;
for (let i = 0; i < n; i++)
S.push({ x: Math.random() * w, y: Math.random() * h,
vx: (Math.random() - 0.5) * 40, vy: (Math.random() - 0.5) * 40 });
};
seed(14, w, h);
return {
resize(w, h) { seed(K, w, h); },
reset() { seed(K, w, h); },
step(ctx, w, h, t, acc, P, M) {
if ((P.sites | 0) !== K) seed(P.sites | 0, w, h);
const met = P.metric | 0, dt = 1 / 60;
S.forEach(s => {
s.x += s.vx * P.speed * dt; s.y += s.vy * P.speed * dt;
if (s.x < 0 || s.x > w) s.vx *= -1;
if (s.y < 0 || s.y > h) s.vy *= -1;
s.x = Math.max(0, Math.min(w, s.x)); s.y = Math.max(0, Math.min(h, s.y));
});
// El cursor es un sitio más: la teselación reacciona en vivo
const pts = M.in ? S.concat([{ x: M.x, y: M.y, cur: 1 }]) : S;
const dist = (dx, dy) =>
met === 0 ? dx * dx + dy * dy
: met === 1 ? Math.abs(dx) + Math.abs(dy)
: Math.max(Math.abs(dx), Math.abs(dy));
const RES = 150, RH = Math.max(1, Math.round((RES * h) / w));
const own = new Int16Array(RES * RH);
for (let j = 0; j < RH; j++) {
const y = ((j + 0.5) / RH) * h;
for (let i = 0; i < RES; i++) {
const x = ((i + 0.5) / RES) * w;
let best = 1e18, bi = 0;
for (let s = 0; s < pts.length; s++) {
const d = dist(x - pts[s].x, y - pts[s].y);
if (d < best) { best = d; bi = s; }
}
own[j * RES + i] = bi;
}
}
const img = ctx.createImageData(RES, RH), d = img.data;
const rgb = acc.split(',').map(Number);
for (let j = 0; j < RH; j++) for (let i = 0; i < RES; i++) {
const q = j * RES + i, o = q * 4, id = own[q];
// Borde = donde cambia el dueño respecto al vecino
const edge = (i + 1 < RES && own[q + 1] !== id) || (j + 1 < RH && own[q + RES] !== id);
const a = edge ? 0.9 : 0.05 + ((id * 37) % 100) / 100 * 0.22;
d[o] = rgb[0] * a; d[o+1] = rgb[1] * a; d[o+2] = rgb[2] * a; d[o+3] = 255;
}
const off = document.createElement('canvas');
off.width = RES; off.height = RH;
off.getContext('2d').putImageData(img, 0, 0);
ctx.imageSmoothingEnabled = true;
ctx.drawImage(off, 0, 0, w, h);
pts.forEach(s => {
ctx.fillStyle = s.cur ? 'rgba(235,238,245,1)' : `rgba(${acc},0.95)`;
ctx.beginPath(); ctx.arc(s.x, s.y, s.cur ? 4 : 2.4, 0, TAU); ctx.fill();
});
ctx.font = '11px monospace';
ctx.fillStyle = `rgba(${acc},0.55)`;
ctx.fillText(['Euclidean — straight line, the usual one',
'Manhattan — |dx| + |dy|, city blocks',
'Chebyshev — max(|dx|,|dy|), king moves'][met], 12, h - 28);
ctx.fillStyle = `rgba(${acc},0.95)`;
ctx.fillText(pts.length + ' sites' + (M.in ? ' · one of them is your cursor' : ''), 12, h - 12);
}
};
}
},