Introduction

Drop a handful of pebbles onto still water and watch the ripples race outward. Each ripple claims every point it reaches before any other. When the fronts collide, they leave a network of boundaries — and that network is a Voronoi diagram.

A Voronoi diagram of a set of seed points partitions the plane into regions, one per seed, where every point in a region is closer to its seed than to any other seed. The boundary between two regions is the perpendicular bisector of the segment joining their seeds — the set of all points equidistant from both.

The geometry appears everywhere in nature: the hexagonal cells of a beehive, the cracks in dried mud, the spots on a giraffe, the territories of competing plant roots, even the large-scale structure of galaxies. When physical forces push outward from centers and compete for space, Voronoi geometry is the result.

Voronoi diagrams were first studied systematically by the Ukrainian mathematician Georgy Voronoi in 1908, and the efficient algorithm for computing them — sweeping a line across the plane — was discovered by Steven Fortune in 1987. Fortune's algorithm runs in O(nlog⁡n)O(n \log n) time for nn seeds, which is optimal since sorting alone requires that much.

Shatter the Plate

Click anywhere on the plate to add impact points (seeds). Each click shatters the surface along the Voronoi boundaries — the cracks run exactly where two seeds are equidistant. You can add up to 30 seeds; use Reset to start fresh with a blank plate.

<!-- Voronoi shattering demo — click to seed, plate fractures along Voronoi edges -->
<div class="toolbar">
  <span class="hint-text">Click on the plate to drop impact points — the surface shatters along Voronoi boundaries.</span>
  <button id="btn-reset" type="button">Reset</button>
</div>
<canvas id="canvas" width="480" height="360" title="Click to add seed points and shatter the plate"></canvas>
<p class="seed-count" id="seed-count">Seeds: 0</p>

/* Layout and visual style for the Voronoi shattering demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.toolbar {
  display: flex;
  align-items: center;
  justify-content: space-between;
  margin-bottom: .5rem;
  gap: .5rem;
  flex-wrap: wrap;
}
.hint-text { font-size: .85rem; color: #555; flex: 1; }
button {
  font: 600 13px system-ui, sans-serif;
  padding: .35rem .8rem;
  border: 1px solid #1d3557;
  background: #1d3557;
  color: #fff;
  border-radius: 7px;
  cursor: pointer;
  white-space: nowrap;
}
button:hover { background: #16304e; }
/* Canvas fills container, crosshair cursor for precision clicking */
#canvas {
  display: block;
  width: 100%;
  max-width: 480px;
  border: 2px solid #c8d4de;
  border-radius: 10px;
  cursor: crosshair;
  touch-action: none;
}
.seed-count { font-size: .8rem; color: #777; margin: .4rem 0 0; }

// Voronoi shattering: nearest-seed partition of the canvas into colored cells
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width;
const H = canvas.height;
const MAX_SEEDS = 30;

// Pastel color palette — one color per Voronoi cell (seed)
const PALETTE = [
  '#c9e4f5','#f5e6c9','#d4f5c9','#f5c9d4','#e8c9f5',
  '#c9f5ef','#f5f0c9','#c9cbf5','#f5d9c9','#d1f5c9',
  '#f5c9ec','#c9dff5','#f0f5c9','#f5c9c9','#c9f5db',
  '#f5e8c9','#d9c9f5','#c9f5f1','#f5cac9','#c9f5e5',
  '#e5c9f5','#c9f3f5','#f5d4c9','#c9f5cd','#f5c9e0',
  '#cef5c9','#f5c9f0','#c9ecf5','#f5f5c9','#f5c9de'
];

// Application state: array of seed points {x, y}
let seeds = [];

// Build the Voronoi diagram by painting each pixel the color of its nearest seed.
// This brute-force raster approach is O(W*H*n) but clear and correct for small n.
function buildVoronoiImage() {
  // Write directly to pixel buffer for speed
  const imgData = ctx.createImageData(W, H);
  const data = imgData.data;

  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      // Find the nearest seed by squared Euclidean distance
      let minDist = Infinity;
      let nearest = 0;
      for (let i = 0; i < seeds.length; i++) {
        const dx = x - seeds[i].x;
        const dy = y - seeds[i].y;
        const d = dx * dx + dy * dy;
        if (d < minDist) { minDist = d; nearest = i; }
      }
      // Decode the hex color for this cell and write RGBA into the pixel buffer
      const hex = PALETTE[nearest % PALETTE.length];
      const r = parseInt(hex.slice(1, 3), 16);
      const g = parseInt(hex.slice(3, 5), 16);
      const b = parseInt(hex.slice(5, 7), 16);
      const idx = (y * W + x) * 4;
      data[idx] = r; data[idx + 1] = g; data[idx + 2] = b; data[idx + 3] = 255;
    }
  }
  ctx.putImageData(imgData, 0, 0);
}

// Overlay crack lines (Voronoi edges) and seed dots on top of the colored cells
function drawEdgesAndSeeds() {
  // Read the painted image and detect color boundaries (Voronoi edges)
  const imgData = ctx.getImageData(0, 0, W, H);
  const d = imgData.data;

  // Draw dark lines wherever adjacent pixels belong to different seeds
  ctx.save();
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 1;

  // Scan every pixel; compare with right neighbor and bottom neighbor
  for (let y = 0; y < H - 1; y++) {
    for (let x = 0; x < W - 1; x++) {
      const idxA = (y * W + x) * 4;
      const idxB = (y * W + (x + 1)) * 4;
      const idxC = ((y + 1) * W + x) * 4;
      const diffH = Math.abs(d[idxA] - d[idxB]) + Math.abs(d[idxA + 1] - d[idxB + 1]) + Math.abs(d[idxA + 2] - d[idxB + 2]);
      const diffV = Math.abs(d[idxA] - d[idxC]) + Math.abs(d[idxA + 1] - d[idxC + 1]) + Math.abs(d[idxA + 2] - d[idxC + 2]);
      // Large color difference means we crossed a Voronoi boundary — draw a crack
      if (diffH > 20) {
        ctx.globalAlpha = 0.55;
        ctx.fillStyle = '#1d3557';
        ctx.fillRect(x, y, 2, 1);
      }
      if (diffV > 20) {
        ctx.globalAlpha = 0.55;
        ctx.fillStyle = '#1d3557';
        ctx.fillRect(x, y, 1, 2);
      }
    }
  }
  ctx.globalAlpha = 1;
  ctx.restore();

  // Draw a small dot at each seed position (impact point)
  seeds.forEach((s, i) => {
    ctx.beginPath();
    ctx.arc(s.x, s.y, 5, 0, Math.PI * 2);
    ctx.fillStyle = '#1d3557';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  });
}

function redraw() {
  ctx.clearRect(0, 0, W, H);
  if (seeds.length === 0) {
    // No seeds yet — show a blank plate with instructions
    ctx.fillStyle = '#eef3f7';
    ctx.fillRect(0, 0, W, H);
    ctx.fillStyle = '#8aa0b0';
    ctx.font = '15px system-ui, sans-serif';
    ctx.textAlign = 'center';
    ctx.fillText('Click to add impact points', W / 2, H / 2);
    ctx.textAlign = 'start';
    return;
  }
  buildVoronoiImage();
  drawEdgesAndSeeds();
}

function updateCount() {
  document.getElementById('seed-count').textContent =
    'Seeds: ' + seeds.length + ' / ' + MAX_SEEDS;
}

function addSeed(x, y) {
  if (seeds.length >= MAX_SEEDS) return;
  seeds.push({ x, y });
  redraw();
  updateCount();
}

// Mouse click handler — maps CSS pixels to canvas pixels via scale factors
canvas.addEventListener('click', function(e) {
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width;
  const scaleY = H / rect.height;
  const cx = (e.clientX - rect.left) * scaleX;
  const cy = (e.clientY - rect.top) * scaleY;
  addSeed(Math.round(cx), Math.round(cy));
});

document.getElementById('btn-reset').addEventListener('click', function() {
  seeds = [];
  redraw();
  updateCount();
});

// Initial render
redraw();
updateCount();
Result
Console

Notice how every crack is a straight line segment — a piece of the perpendicular bisector between two seeds. Three cracks always meet at a single point (a Voronoi vertex), which is equidistant from exactly three seeds. The more seeds you add, the finer the fracture — just like real glass shatters into smaller fragments near an impact point.

The Real Complexity

Computing a Voronoi diagram from scratch looks deceptively expensive — after all, each of the nn seeds could in principle influence every other. But the structure is far more local than it appears.

  • Naive approach: for each of infinitely many candidate boundary points, check which seed is closest — obviously impractical.
  • Brute force for vertices: a Voronoi vertex is the circumcenter of three seeds. Try all (n3)\binom{n}{3} triples, check that no other seed lies inside the circumcircle — O(n4)O(n^4) total.
  • Fortune's sweepline (1987): a vertical line sweeps left to right. A beach line of parabolas (one per seed seen so far) tracks the advancing wavefront. Events — parabola intersections and circle events — are processed in a priority queue. Total time: O(nlog⁡n)O(n \log n), space O(n)O(n).
  • Lower bound: Ω(nlog⁡n)\Omega(n \log n) is provably optimal. Any algorithm that computes the Voronoi diagram can sort nn numbers (by placing seeds on a line), and sorting requires Ω(nlog⁡n)\Omega(n \log n) comparisons.

The dual graph of a Voronoi diagram is the Delaunay triangulation: connect seeds whose Voronoi cells share an edge. Every triangle's circumcircle contains no other seed — this empty circumcircle property makes Delaunay triangulations maximize the minimum angle, avoiding slivers. The same structure solves the closest pair problem and underpins nearest-neighbor search trees.

Where It Matters

Voronoi diagrams are one of the most versatile structures in computational geometry. Their applications span fields from telecommunications to biology:

  • Wireless networks: each cell-tower's coverage zone is exactly its Voronoi cell — the region closer to it than to any rival tower. Planning tower placement to cover a city is a Voronoi optimization problem.
  • Epidemiology: John Snow's 1854 cholera map implicitly used Voronoi regions to link deaths to water pumps — one of history's most famous data visualizations.
  • Game AI and pathfinding: Voronoi roadmaps give moving agents natural corridors that stay as far as possible from all obstacles.
  • Mesh generation for simulation: finite-element solvers need meshes that avoid sliver triangles; the dual Delaunay triangulation is the standard tool.
  • Fracture simulation in film and games: shatter effects in movies and games (glass breaking, rock splitting) are rendered by computing Voronoi cells around random impact points, exactly as in our demo.
  • Biology and ecology: animal territories, plant root competition, and the cells of living tissue all self-organize into approximate Voronoi patterns driven by proximity and resource competition.

Understanding the convex hull and Voronoi diagram together gives you the two most important proximity structures in computational geometry.

Conclusion

A Voronoi diagram emerges from the simplest possible rule: every point belongs to whichever seed is closest. From that one sentence flows the geometry of cracked mud, giraffe spots, cell towers, and shattered glass — and an O(nlog⁡n)O(n \log n) algorithm that is provably as fast as it can be.

The next time you see a pane of glass crack into irregular shards, or dried earth split along ancient lines, you are watching Fortune's algorithm run in nature — each fragment the territory of the impact point that claimed it first. The math of breaking things apart turns out to be the math of belonging to the nearest neighbor.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/voronoi-shattering/Content licensed under CC BY-NC 4.0.