[postgis-devel] Distance Madness

[Nicklas Avén]

wow, I think postgis will be hard to beat in the long run :-)  I'm not used to study those tree things, but it will be very interesting to follow this and try to understand it.Will it work on overlapping bboxes too? One thing I think is nice about "my" way of doing it, is that there is no indexes included. The gain is that it can be nested in subqueries and CTE's without loosing the speed. But I haven't really understood when that problem occur of not using the indexes. I have been thinking some in 3D terms too, totally without knowledge about reality. But it shouldn't be too impossible to do the same tricks in 3D and calculating point to surface instead of point to segment. But that would need a 3D type. I don't know how that use to be built, but I have imagined a list of 3D points and a related list with pointidentifiers in groups of three, defining triangels. Then it would be quite fast to do like my distance trick on the points and finding the surfaces to calculate dista!
 nces to with some index on the pointidentifiers list... /Nicklas  

2009-12-01 Paul Ramsey wrote:

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.
>_______________________________________________
>postgis-devel mailing list
>postgis-devel at postgis.refractions.net
>http://postgis.refractions.net/mailman/listinfo/postgis-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20091201/b65a00c4/attachment.html>