Voronoi Diagrams

Remarkably, the Voronoi diagram (example shown below) was first popularised in the 19th Century. They are useful for examining 2D spatial proximity problems. The idea of these diagrams is that the formed convex polygons around a generating point (seed or site) contains any point that is closer to that generating point than to any other. These polygons (regions or cells) represent a division of a cartesian plane based on a defined distance to the generating points. There are different forms of tessellation dependent upon the measurement type.

Voronoi diagrams are also called Thiessen polygons, which uses the Delaunay triangulation technique to calculate the pattern. The image below eludes to the construction and calculation and how it clearly relates to the Delaunay triangulation (shown as blue lines). The generating points, or seeds, are shown in yellow.

Construction of a Voronoi diagram Example of a Voronoi diagram

There are numerous applications of Voronoi tessellations. For example, the above shows rail stations set as ‘seeds’, the resultant pattern identifies areas where there is a high density of of activity and reveals patterns of commuting traffic relative to surrounding regions. Often, this can be re-presented as a kernel density map (the relative density of point data), also called a heat map, is shown below. The same ‘seeds’ were used to generate both images.

Example of a Kernel Density plot Example of a Voronoi diagram of world airports on Transverse Mercator projection

The above example is a based upon world airports by Trevor Manz, using D3 and shown here on the Transverse Mercator projection.

Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art. Whilst these are generated using computer algorithms, the methodology can be re-created by hand, which is great way to fully understand how these diagrams work. This online tutorial walks you through the process of hand-drawing a diagram. The construction lines help illustrate how it was achieved, though it can take a bit of practice. There’s also an excellent interactive explanation at the Cartography Playground.

Example of handrawn Voronoi diagrams

It’s a fascinating mathematical pattern that lends itself to (geo)spatial analysis. As in space syntax, the Voronoi pattern favours efficiency; the nearest neighbour, shortest path and tightest fit and is related to graph theory. What we’ve covered here is the typical type of diagram, but there are numerous other types that apply different ‘weighting’ schemes and/or distance functions, not to mention 3D applications… not achievable by hand!