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

[Andy Colson]

On 1/4/2012 1:32 AM, Evan Martin wrote:
> 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

I have no idea if the && operator is actually just a call to ST_DWithin, 
but I don't think so.  In that case you might be able to use && to cut 
the list down first.  Something like:

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


This will make a bounding box around p1 and p2 and see if the intersect, 
not sure if you need both that way, you could just ST_Buffer one of 
them.  The bounding box calc is not exact, but should be fast and 
indexable, so you still need the ST_DWithin.

Again, no idea if this is actually faster.

-Andy