[postgis-users] A faster way to find "adjacent" polygons

[Evan Martin]

I have a table of polygons covering most of the world and for a given 
polygon I need to find all polygons adjacent to it. In theory, two 
adjacent polygons should have a part of their border in common, but in 
practice the data is not that precise - sometimes there's a slight 
overlap and sometimes a slight gap between adjacent polygons. Since 
these polygons can cross the dateline I have them stored as geography. 
It looks like ST_DWithin(geog, geog, distance) does exactly what I want, eg.

SELECT *
FROM polygons p1
JOIN polygons p2 ON p1.id < p2.id AND ST_DWithin(p1.geog, p2.geog, 100, 
false)

The only problem is that this is slow! There are about 300 polygons in 
total and this query takes about 75 minutes. I have a GIST index defined 
on the geography column. Just doing && is fast - it seems to be 
_ST_DWithin that's slow. There's one pair of polygons I found (with 300 
points and 1300 points) that share a part of the border (ST_Intersects = 
true) and _ST_DWithin takes 1.2 or 3.9 seconds just for that one pair, 
depending on the order of the arguments.

Is there some other way I can do this? I couldn't figure out any way to 
get the correct result with geometry around the dateline and ST_DWithin 
looks like the appropriate geography function.

Can ST_DWithin itself be made faster? I had a look at the source and it 
seems to be calculating the distance between each combination of edges - 
so O(n^2). Isn't there a more efficient algorithm for this out there? I 
know there's Rotating Calipers for a plane - is there something like 
that which works on a sphere? Or is it possible to consider only the 
edges of each polygon that are within the intersection of their bounding 
boxes? I'm a newbie to this, so it might be a silly idea, but surely 
there has to be something faster than the brute force approach?

Any help would be appreciated!

Evan