Fast minimum distance between two sets of polygons

Question

I'm trying to calculate the minimum distance between a set a polygons, and a subset thereof. I've used a quick-and-dirty GeoPandas apply:

df['subset_distance'] = df.geometry.apply(lambda g: df_subset.distance(g).min())

which works, but it's pretty slow, even on my test dataset of around 700 polygons. I need to find the minimum distances for around 2 million polygons and a subset of 4k polygons, so I suspect I'm going to need a different strategy. Could anyone suggest a better approach? I'm comfortable with PostGIS, and any combination of Python spatial libraries.

Answer 1

You can do this in Python with the help of Rtree and Shapely. The procedure would look similar to this answer.

The R-tree index would identify a list of possible nearest polygons, all based on bounding boxes. Then from this shortlist list, you'd go through them and use Shapely to determine which polygon is closest, based on the minimum distance between the geometries. Consider that you might have more than one geometry that is closest (e.g., if there are multiple polygons that intersect, they will all be 0 distance, thus there is no metric for "closest". You could additionally evaluate the minimum distance of centroids from polygons with 0 distance.)

This is a pretty good blog post showing how to use GeoPanda's sindex (spatial index), which is based on Rtree (which is an optional dependency for GeoPandas).

Answer 2

In PostGIS, use ST_Distance.

--If the units of the spatial reference is meters then units would be meters
SELECT DISTINCT ON (df.gid) df.gid, df.name, df_subset.name
FROM df
    LEFT JOIN df_subset ON ST_Distance(df.geometry, df_subset.geometry)
ORDER BY df.name, ST_Distance(df.geometry, df_subset.geometry);

ST_DWithin would be faster because it uses indexes but you must supply a distance parameter also.