Voronoi Diagrams
Plant seeds and watch territories form. Each region belongs to its nearest seed. Seeds on the boundary get contrasting colors; interior seeds blend from their neighbors.
Place a few seeds. Every point on the canvas belongs to whichever seed is nearest — and colors itself with that seed’s hue. Seeds on the boundary get a color chosen to contrast their neighbors; seeds placed in the interior blend from the hues around them.
What is a Voronoi diagram?
Imagine your school has three water fountains. You always walk to whichever one is nearest. Every spot in the hallway “belongs” to exactly one fountain. Draw a map of those territories and you have a Voronoi diagram.
Each territory is called a cell. The colored region around a seed is its cell — every point inside that cell is closer to that seed than to any other.
The boundaries between cells are exactly where two seeds are the same distance away. Because of that, boundaries are always perfectly straight lines. Three cells always meet at a single vertex, a point that is exactly equidistant from three seeds at once.
One seed always makes one cell. Add a seed, add a cell. Always.
How is it computed?
Start with any two seeds. The boundary between their cells is a line that sits exactly halfway between them — and it crosses at a right angle. This is called the perpendicular bisector.
For many seeds, draw the perpendicular bisector for every pair. Each bisector is an infinitely long line. Trim each one to only the part that is actually closer to its two seeds than to any other seed. The trimmed pieces form the Voronoi boundaries.
In practice, computers use algorithms like Fortune’s sweep line to compute this in a single pass, but the rule is always the same: every boundary point is a tie between exactly two seeds.
The Delaunay Triangulation
The Voronoi diagram has a secret twin called the Delaunay triangulation. Connect every pair of seeds whose cells share a boundary. The result is a mesh of triangles that fills the space between seeds.
They are “duals” — each Voronoi boundary has exactly one Delaunay edge crossing it at a right angle, and each Voronoi vertex corresponds to one Delaunay triangle.
The Delaunay triangulation has a beautiful property: draw a circle through any triangle’s three corners — no other seed falls inside that circle. This “empty circumcircle” rule keeps triangles fat and well-shaped; slivery needles never form.
Toggle Delaunay in the viewer to switch from cell fills to the triangle mesh. When drawing images the averaged colors of three nearby seeds give each triangle a blended hue — a low-poly mosaic effect.
What are they good for?
Voronoi diagrams and Delaunay triangulations appear everywhere:
| Where | Why |
|---|---|
| Cell towers | Your phone connects to its nearest tower. The coverage map is a Voronoi diagram. |
| City planning | Fire stations, schools, and hospitals are sited so that every neighborhood falls in exactly one cell — no one is unfairly far from help. |
| Nature | Giraffe spots, dragonfly wings, foam bubbles, and the spongy bone inside your skeleton all grow in Voronoi-like patterns that minimize material while maximizing strength. |
| Video games & movies | Delaunay triangulation is the standard way to build terrain meshes and character models from a cloud of points. |
| Science | Protein folding, galaxy clustering, and weather forecasting all use Voronoi cells to partition space around data points. |
How to use the viewer
Manual mode — click anywhere to plant a seed. Drag seeds to move them; regions reshape in real time. Try these:
- Two seeds — one perfectly straight line bisects the canvas. Move the seeds toward each other and watch the boundary stay exactly halfway between them.
- Many seeds — add 15 or 20. Notice that adding a new seed only reshapes the nearby cells; distant ones are untouched.
- Toggle Delaunay — switch from cell fills to the triangle mesh. Toggle Edges to show or hide the wireframe. Toggle Seeds to show or hide the dots.
Auto — Image mode — select an image and press ▶ Play. Seeds are placed one at a time, from most important to least, and the picture emerges coarse-to-fine. The Speed slider controls how fast seeds are added (up to 500 per second). Choose ↻ Slideshow to cycle through all images automatically.
Auto — Random mode — seeds appear at random positions with a golden-angle color palette. Watch up to 80 regions form, then the cycle resets.
Drawing pictures with seeds
Not all seed placements are equal. Spreading seeds uniformly gives every region the same area — a classic Voronoi mosaic. Concentrating seeds in high-detail areas gives those areas smaller, more precise cells, while flat areas get large coarse ones — a form of visual compression.
The images in this viewer use a technique called stippling: placing dots so that the resulting Voronoi cells reconstruct the image as faithfully as possible. Seeds are ordered by a weighted farthest-point algorithm:
- Place the first seed at the most visually interesting spot.
- Each new seed goes as far as possible from all existing seeds — weighted by how much detail that area has.
- Seeds arrive in importance order, so the image builds coarse-to-fine: faces and edges appear first, then midtones, then flat background.
The photo images in the viewer also use a center bias — a Gaussian weight that gradually de-emphasizes the corners of the frame, matching how subjects tend to be composed in photographs.