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

[Paul Ramsey]

Short answer: not in SQL.

Longer answer: if your objects are sufficiently small you could use
the _ST_BestSRID approach (see the geography.sql definition for
ST_Buffer for example) and flip the geographies into planar space for
the test. It's still brute force, but with far simpler calculations.

Longest: I did some thinking on using a tree approach which should be
about O(N+M) but never implemented it. You can build a tree based on
the edges in about O(N) time using their natural autocorrelation to
skip the sort step, then merge and prune the trees in the distance
calculation. I got a demo implementation working in planar space, and
I think there's ways to do it in spherical too.

P.

On Tue, Jan 3, 2012 at 11:32 PM, Evan Martin
<postgresql at realityexists.net> 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
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users