# What do you call a map that shows the closest distance to a set of points?

This is one of those hard problems to Google since I don't know the right words to Google! I have a list of 6,000 retail locations in the US, and I want to know, for any given point, how far away one is from one of them.

I assumed this was a "proximity map," but that seems to mean a few different things. I THINK what I want is something like this McDonald's map from Reddit, but with an infinity decaying radius so that, even in large states where there are no locations, one gets a sense for the distance.

It seems to me there are two strategies:

1. Take the 6,000 points and run a sort of nearest neighbor algo that shows the radius expand from the nearest location, across the whole country.

2. Take a map of the country divided into the smallest possible intervals -- Census tracts or something -- and, for each tract, find the distance to the nearest location. This makes less computational sense, but I'm vague on how the first strategy would work.

In any event, I obviously didn't invent this concept, so if there's a name for it, I'm sure I can find a good QGIS tutorial!

• It's not clear if your intent is to make a map, or just make a query-able function that returns the shortest distance for a given input point. Anyway, one way to achieve this might be to do a simple distance transform. I.e. create an empty georaster, mark the pixels "1" that contain the retail locations, and then run distance_transform_edt from scipy. The resulting image pixels contain the distance to the nearest "1" (retail) pixel.
– Jon
Nov 1, 2018 at 21:32
• I do want to make a map, and that's super helpful. Thank you! Nov 1, 2018 at 21:38
• @Jon - while the scipy function is useful, my reading of the docs suggest that it assumes the raster represents points in a Cartesian plane and computes the Euclidean distance between raster cells and the specified locations. This makes the selection of the projection for the raster critical. I leave it to someone more versed in projections to make a recommendation. Nov 2, 2018 at 2:39
• @Llaves You are correct, and that's something I hadn't considered. You could make the empty raster in an equidistant projection (e.g. epsg:4087), but even then I'm not sure about distortions at a continental scale.
– Jon
Nov 2, 2018 at 3:11

The solution depends on the level of accuracy you desire. For the greatest accuracy, you would plot your points, compute the Voronoi diagram, then for each cell in your raster use the Voronoi diagram to find the closest location and then do an exact computation of the distance from the raster cell to that closest point.

At a (probably) small cost in accuracy you could skip the Voronoi step and use a breadth-first brushfire approach and work outwards from retail location, computing the distance to each raster cell.

You could probably achieve similar accuracy by dividing your data into regions corresponding to the UTM zones and using the scipy function suggested by @Jon in the comments below your question. This has its own complexities, as you need to be careful where the Voronoi cell around a retail location spans a zone. You want all the raster cells for a single retail location to be computed on the same UTM zone even if some cells fall outside the zone.

Finally, if the map is primarily a visualization tool and exact distances don't matter, the method of @Jon is probably good enough for most purposes, esp if you pick a good projection. Alternatively, just showing the Voronoi diagram on the map gives a pretty good sense of how far someone can be from the nearest location. QGIS has a built-in Voronoi function.

That McDonald's map looks like Voronoi polygons where every point along the perimeter of the enclosing polygons is closest to the point it contains. Maybe read up on Dijkstra's algorithm on distance.

• It did occur to me that -- correct me if I'm wrong -- Voronoi diagrams always divide nodes equidistantly, such that, anyone in the circumscribing polygon, the node it circumscribes is the closest one to me, right? Nov 2, 2018 at 3:28
• @ChrisWilson - yes, the Voronoi diagram divides the plane (surface) into regions such that the points within a polygon are closer to the enclosed point than to any other. But this doesn't solve the OP's problem, of finding the distance at every point of the raster, though it does tell us which point we need to compute the distance to. Nov 2, 2018 at 3:47
• Dijkstra's algorithm is used for finding shortest paths in a graph. I don't see how it helps here. Nov 2, 2018 at 3:50