[postgis-devel] Distance Madness

[Paul Ramsey]

Niklas,

Your cunning sorting trick got into my head and I thought and thought
on it and ended up borrowing the magic tree idea from Mark's prepared
p-i-p code, and added another dimension to that, so the trees are
actually in 2d space, and then starting thinking about how, given two
of these trees you could quickly find things like intersections or
even (*gasp*) distances...

geog=# select distance(buffer('POINT(3 3)', 2),buffer('POINT(0 0)', 2));
     distance
-------------------
 0.242640687119285
(1 row)

geog=# select npoints(buffer('POINT(3 3)', 2));
 npoints
---------
      33
(1 row)

geog=# select 33*33;
 ?column?
----------
     1089
(1 row)

These two circles have 33 points each, so the brute force method
requires 1089 distance calculations to come up with an answer. The
magic trees took 29. It's also possible to *cache* the trees and
re-use them, both for distance calculations and intersections and
containments.

Very exciting stuffs!

However, we're almost to 1.5 and adding all the features you already
have in your code (maximums, points and lines of shortness, etc) would
take way too long. And I'm not sure my code is actually faster. Just
that it's much faster than the brute force ways.

It's all in lwtree.c in liblwgeom if you want to look.

P.