Voronoi and Delaunay

When points are scattered across the plane and each one is given everything closer to it than to any other point, the result is a set of convex polygons: Voronoi cells. Nature draws them all the time; a giraffe's patches, the veins of a dragonfly's wing, cracks in dried mud and soap foam all resemble them. People draw them too, as coverage maps of mobile masts.

How it works

The border between two neighbours is the perpendicular bisector of the segment joining them. Joining every pair of points whose cells touch gives the Delaunay triangulation, the dual picture: the corners of the Voronoi cells are the centres of circles drawn round its triangles, and no point lies inside any such circle. The generator builds the triangulation and assembles the cells from those centres.

“Points” decide the look. Random points give a jumble of tiny and huge cells. A Poisson disk keeps points at least r apart but otherwise random, by Bridson's algorithm: a new point is tried in a ring round one already placed, up to thirty times. Cones at the edge of the retina are arranged in much the same way. “Relaxation” is Lloyd's algorithm: each point moves to the centroid of its cell, the diagram is rebuilt, and after a few steps the cells even out towards the hexagons of a honeycomb. In tile mode the points live on a torus and the mosaic has no seam.

A bit of history

Descartes sketched such partitions in 1644 and Dirichlet used them for quadratic forms in 1850. In 1854 the London physician John Snow outlined the area closer to the Broad Street pump than to any other and showed that most cholera victims lived inside it. Georgy Voronoy built the general theory in 1908, and Boris Delaunay stated the empty-circle criterion in 1934. Stuart Lloyd devised his algorithm at Bell Labs in 1957 for quantising signals but published it only in 1982; it is now the standard way to solve k-means. Robert Bridson described fast Poisson disk sampling in 2007.

What to tweak

• Compare “Points” set to “random” and “Poisson disk” with “Relaxation” at 0, then raise it to 10: the cells turn almost into a honeycomb.
• “Style” set to “triangulation” shows the Delaunay mesh with its points; “low-poly” fills its triangles, and with “Colouring” at “by noise” gives a polygonal illustration.
• “Style” set to “stipple” puts a dot in every cell, its area proportional to the cell's.
• “Gap” and “Roundness” turn the cells into pebbles or cells under a microscope.
• Over the “stained glass” style, add the “Glow” effect and the panes light up as if the sun were behind them.