📐 Voronoi Diagrams and Lloyd's Relaxation

About this simulation

A Voronoi diagram partitions a plane into regions, one per "seed" point, so that every location in a region is closer to its own seed than to any other. The cell boundaries are exactly the set of points equidistant from two neighbouring seeds. Lloyd's relaxation is a simple iterative algorithm: compute the Voronoi diagram, move each seed to the centroid (centre of mass) of its own cell, and repeat. Over successive iterations the cells become more uniform in size and shape, converging toward a centroidal Voronoi tessellation — the honeycomb-like pattern this algorithm is famous for.

How it works

• Each colored cell on the plane below is rasterized by testing, at every sample point, which seed is nearest — that seed "owns" the point.
• The small pillar at each cell's center is the seed; its height and glow track how far it still is from its own cell's centroid.
• Lloyd's relaxation repeatedly replaces each seed with its cell's centroid, which shrinks large irregular cells and grows small ones until the tessellation settles into evenly-spaced, near-hexagonal cells.
• Dragging a seed by hand instantly recomputes every affected cell boundary, showing how local moves ripple through the whole diagram.

Controls

• Seed points — how many sites tessellate the plane (4–40).
• Show centroids — reveal each cell's true centroid as a small marker.
• Show cell edges — toggle the dark Voronoi boundary lines.
• ↻ Relax 1 step — run exactly one Lloyd iteration.
• ▶ Auto-relax — run iterations continuously until stopped.
• ↺ New points — scatter a fresh random set of seeds.
• Drag any pillar to reposition its seed by hand; drag empty space to orbit the camera.

Did you know?

Lloyd's algorithm (Stuart Lloyd, 1957, originally for signal quantization) is the same idea behind k-means clustering, mesh generation for finite-element simulation, and the stippling techniques artists use to place dots evenly across an image.