Visualising Supermarkets with a Voronoi Diagram

This post is an introduction to Voronoi diagrams and showcases some images from them.

Voronoi diagrams

If you have a set of points, a Voronoi diagram creates a cell around each point containing places that are closer to that point than any other.

Points at random locations generating a colourful Voronoi diagram — An example Voronoi diagram made with Alex Beutel's WebGL Voronoi diagram generator. The lines where the coloured cells intersect is equidistant between two of the points.

When Voronoi diagrams are displayed on top of a geographical map they are able to show at a glance what the closest point of interest is for any location on the map.

A map centred on Australia and New Zealand with points at airports generating a Voronoi diagram — Jason Davies's World Airports Voronoi, centred here on Australia and New Zealand, give an indication of the shape of the landmasses, highlighting areas with a high and low density of airports.

As well as a tool for visualising geographic data, Voronoi diagrams are useful for calculating shatter patterns in 3D graphics and generating realistic terrain.

Supermarkets

My work on SuperLocate had left me with the location data for 12,598 supermarkets in the United Kingdom. After seeing the World Airports Voronoi I thought it would be interesting to try and visualise the data in the same way.

To make it easier to draw the map I’ve made two simplifications:

The map uses the euclidian (or ‘as the crow flies’) distance to draw the Veronoi diagram. While it shows the closest by distance, in many cases it is not accurate at showing the closest in time because it does not consider transport links.
I’ve also assumed that every point has an equal influence. This isn’t true as supermarkets are of difference sizes and have different facilities. It would be possible to use a weighted Voronoi diagram but this would be more complex to construct.

You can explore the whole map that I made. Here are some parts of it that I like:

A map centred on the Peak District where very few supermarkets marked. Many are marked Manchester, Huddersfield and Sheffield which surround. — The low density of supermarkets in the Peak District, in contrast to the surrounding towns and cities of Manchester, Huddersfield and Sheffield.

Supermarkets dotted along Mile End Road in East London.

If you end up in Richmond park, the Voronoi diagram makes it easy to see which direction you should head to get to a shop in the quickest way.

If you’re so inclined, you can also read my technical explanation of how I built the visualisation with D3 and Leaflet.

The map layer of the supermarket visualisations on this page is copyright Mapbox and OpenStreetMap.