Voronoi diagram generator and tools

What is a Voronoi diagram?

Scatter a few points on a page and color every spot by the point it is closest to. The colored regions are the cells of a Voronoi diagram, and the lines between them are the places that are equally far from two points. Every cell holds exactly one point — its site — and together the cells cover the page with no gaps or overlaps.

The idea goes by many names. Mathematicians say Voronoi diagram, Voronoi tessellation or Dirichlet tessellation. Geographers and GIS users say Thiessen polygons. Physicists call the cells around atoms Wigner–Seitz cells. They all describe the same construction: divide space by nearest site.

Three facts explain most of what you see in any Voronoi diagram. Each border lies on the perpendicular bisector between two sites. Each corner, where three cells meet, is the center of a circle through three sites that contains no other site. And with ordinary straight-line distance every cell is a convex polygon. The illustrated guide walks through each of these with interactive figures.

Which Voronoi tool should I use?

Start from what you want to do:

• Voronoi diagram generatorQuickly draw cells from your own points, relax them and recolor them.
• Voronoi map generatorFind the service area of each store, school or station on a real map.
• Spherical VoronoiWork at country, continent or world scale, where flat maps distort distance.
• Voronoi pattern generatorDesign a cell pattern for laser cutting, 3D printing or a background.
• Image to Voronoi mosaicTurn a photo into a stained-glass, low-poly picture.
• Voronoi stipplingTurn a photo into evenly spaced dots for print or a pen plotter.
• Voronoi fantasy map generatorMake an island or continent with biomes and kingdoms for a game or story.
• Delaunay triangulation generatorSee the triangulation that is the Voronoi diagram's dual, with circumcircles.
• Lloyd relaxationEven out points step by step into a centroidal Voronoi tessellation.
• Weighted VoronoiLet some sites reach further than others: power and multiplicative diagrams.
• Voronoi distance metricsMeasure distance along a street grid or like a chess king instead of a straight line.
• Voronoi simulationWatch cells grow and see Fortune's sweep-line algorithm at work.

How to make a Voronoi diagram online

1. Open the Voronoi generator. A random diagram is ready to edit.
2. Click to add sites, drag them to move them, and right-click to remove them. The cells follow instantly.
3. Press Relax to make the cells more even, or Random to start over with a set number of points.
4. Pick a palette and border style, and switch on the Delaunay triangulation if you want to see the structure underneath.

If your points are real places, use the map version instead: paste latitude and longitude pairs or upload a CSV or GeoJSON file, clip the cells to a city or district boundary, and read off the area of every cell in square kilometers. All tools compute in your browser; your data is not uploaded.

Voronoi diagrams in planning and GIS

In geography the cells are called Thiessen polygons, after the meteorologist who used them in 1911 to estimate rainfall over an area from a handful of rain gauges. Each gauge stands for the area closer to it than to any other gauge. The same logic gives a first estimate of many catchments:

• the neighborhood each school, clinic or library serves if people go to the nearest one;
• the trade area of each store in a chain, and where a new store would take customers from;
• the response zone of each fire station or ambulance base;
• the area a weather station or air-quality sensor represents.

Where straight-line cells fall short

A Voronoi cell measures distance as the crow flies. Rivers, rail lines and road networks bend real travel, so for walking or driving catchments a network-based isochrone is more accurate. Size matters too: bigger or better facilities attract people from further away, which a weighted Voronoi diagram can approximate. And at country or world scale, flat-map distance is distorted, so use the spherical Voronoi tool.

Voronoi diagrams in design and art

Cells grown from scattered points look natural because nature builds them the same way: giraffe skin, dried mud, dragonfly wings, foam and plant tissue all approach Voronoi patterns. Designers use that look in facade screens, lamps and furniture, jewelry, 3D-printed lattices and textile prints.

Two settings decide the character of a pattern. Regularity — how many relaxation steps the points get — moves it from wild to calm and honeycomb-like. The gap between cells, with rounded corners, turns a diagram into something that can be cut from a sheet. Try both in the pattern generator. For pictures, the mosaic and stippling tools follow the colors and tones of a photo, and the fantasy map generator uses a relaxed Voronoi grid as the backbone of a whole world.

The geometry behind it

Delaunay triangulation

Connect every two sites whose cells share a border and you get the Delaunay triangulation: triangles whose circumcircles contain no other site. It carries the same information as the Voronoi diagram, and most software, including every tool here, builds it first. Explore it in the Delaunay generator.

Relaxation and centroidal Voronoi tessellations

Moving every site to the center of its cell and repeating — Lloyd's algorithm — spreads points evenly. When every site sits at its cell's centroid the result is a centroidal Voronoi tessellation, the basis of good meshes, even sampling and stippling. Watch it converge in the relaxation tool.

Weights, metrics and the sphere

Change how distance is measured and the cells change shape: weights give power and multiplicatively weighted diagrams with curved borders; Manhattan or Chebyshev distance gives borders at 45 and 90 degrees; great-circle distance on the globe gives cells that wrap around the Earth. Each has its own tool: weighted Voronoi, distance metrics and spherical Voronoi.

How the diagram is computed

Fast algorithms build a Voronoi diagram of n sites in O(n log n) time, either with Fortune's sweep line or through the Delaunay triangulation. The simulation shows both the growing-cells picture and the sweep line with its beach line of parabolas.

Glossary

Site (seed, generator)

One of the input points. Each site owns exactly one cell.

Voronoi cell

All locations closer to one site than to any other.

Voronoi edge

A border between two cells, lying on the perpendicular bisector of their sites.

Voronoi vertex

A corner where three or more cells meet; the center of an empty circle through their sites.

Thiessen polygons

The GIS name for Voronoi cells, used for catchments and for weighting point measurements by area.

Delaunay triangulation

The dual of the Voronoi diagram: sites joined whenever their cells touch.

Lloyd relaxation

Repeatedly moving each site to its cell's centroid to even out the cells.

Power diagram

A weighted Voronoi diagram using squared distance minus squared radius; its borders stay straight.

Questions