Given a set of seed points, the Voronoi diagram partitions space so that every point in a cell is closer to that cell's seed than to any other. It appears in giraffe markings, bone microstructure, city planning and epidemiology.
Voronoi cells are computed live using Fortune's sweep-line algorithm (O(n log n)). The dual graph — Delaunay triangulation — is drawn in overlay: it maximises the minimum angle of all triangles, the optimal mesh for finite-element methods and terrain rendering.
Click anywhere to add a seed point. Drag seeds to watch the tessellation update in real time. Toggle Delaunay overlay. Try the Lloyd relaxation button to iterate cells toward uniform spacing — the process that generates centroidal Voronoi diagrams.
John Snow's famous 1854 cholera map was an early Voronoi diagram: he drew boundaries around water pumps and showed that deaths clustered inside one pump's cell. Removing its handle ended the outbreak — an early triumph of spatial data analysis.
A Voronoi diagram partitions a plane around a set of seed points so that every location belongs to the region of its nearest seed. This interactive generator draws those cells in real time and supports Lloyd's relaxation, which iteratively moves each seed to its cell's centroid to even out the layout, plus a choice of Euclidean, Manhattan or Chebyshev distance metrics and an optional Delaunay triangulation overlay.
Voronoi tessellations appear throughout nature and science, from the cracking of dried mud and the cells of a giraffe's coat to the territories of animals and the structure of foams and crystals. They are foundational in computational geometry and power applications such as nearest-neighbour search, mesh generation, procedural texturing, spatial interpolation and the planning of service areas like schools or hospitals.
What is a Voronoi diagram?
Given a set of seed points, a Voronoi diagram divides the plane into regions where each region contains all locations closer to its seed than to any other. Every cell is the 'territory' of one seed, and cell boundaries are equidistant between neighbouring seeds.
What is Lloyd's relaxation?
Lloyd's algorithm repeatedly recomputes the Voronoi diagram and moves each seed to the centroid of its cell. Iterating this produces a centroidal Voronoi tessellation with more uniform, evenly spaced cells, useful for sampling and meshing.
What do the different distance metrics do?
Euclidean distance gives straight-line nearest-seed regions with smooth boundaries. Manhattan distance measures along grid axes, producing blocky, diamond-edged cells, and Chebyshev distance counts the larger axis difference, giving square-influenced regions. Each metric reshapes the cells.
The Delaunay triangulation connects seeds whose Voronoi cells share an edge, and it is the geometric dual of the Voronoi diagram. Overlaying it shows how seeds are linked and is itself widely used for generating well-shaped triangle meshes.
Each boundary lies exactly halfway, under the chosen metric, between two neighbouring seeds. With Euclidean distance these are perpendicular bisectors of the lines joining adjacent seeds, meeting at vertices equidistant from three or more seeds.
They emerge in dried mud cracks, soap foams, crystal grain boundaries, leaf cell arrangements, animal coat patterns such as giraffes, and territorial divisions, because many growth and packing processes naturally minimise distance to nearest centres.
They support nearest-neighbour queries, collision detection, mesh generation, procedural textures and game maps, spatial interpolation of data, and planning of service regions like coverage areas for towers, schools or hospitals.
More seeds create more, smaller cells and a finer partition of the plane. The average cell area shrinks roughly in proportion to one over the number of seeds, while boundaries become denser and more intricate.
Moving each seed to its cell's centroid pulls clustered seeds apart and fills sparse gaps. Repeated iterations converge toward cells of similar size and compact, hexagon-like shapes, reducing the irregularity of random seeding.
They are dual structures: each Voronoi vertex corresponds to a Delaunay triangle's circumcentre, and Voronoi edges are perpendicular to Delaunay edges. Computing one effectively gives the other, and both are central to computational geometry.