<html>
<head>
<title></title>
<meta name="GENERATOR" content="MSHTML 8.00.6001.18852"></meta>
<meta name="SKYPE_FRAMEID" content="UKSDOXEVME"></meta>
<meta id="skype_v3_tb_marker_id" name="SKYPE_PARSING_HAS_FINISHED" content="metacontent"></meta>
</head>
<body>
<div>aul</div>
<div>If it is as I suspect that the number of memory allocations is the most costly part of this, wouldn't it be possible to allocate all of it once and for all. If you allocate one list of nodes for each level, the whole structure of the tree is given. You know where the children and parents is related to the start of the "level lists" the only thing missing is the min and max x any y for each level.</div>
<p align="left">/Nicklas<br />
<br />
2009-12-01 Nicklas Avén wrote:<br />
<br />
:-) ></p>
<div align="left"> </div>>
<div align="left">I think I see what you are doing</div>>
<div align="left">Had to take another look...</div>>
<div align="left"> </div>>
<div align="left">The comarasion part is the same as I used for subgeometries and as you say (I saw the blog too) the natural ordering of the edges should make the tree very effective.</div>>
<div align="left"> </div>>
<div align="left">But I think you have to cache the tree to beat my calculation :-)</div>>
<div align="left">That belive comes from some trying I did when writing the code, before I had found the qsort function. Then I build a tree as described in that C-bible I can't remember the name, just to get the measure-values ordered. I think it was the number of memory-allocations that showed to be very expensive. I might have done som elementary mistake but when I tried that tree with one node per vertex on the largest polygon of Alaska (about 70000 vertexes) it used almost 7 seconds just to build the tree and read it ordered. The whole calculation for distance between the largest polygons in Alaska and Texas now uses less than 100 ms. But it is quite likely that I had done som mistake in my treebuilding.</div>>
<div align="left">(That calculation Alaska Texas is extremly fast because Texas has that sharp edge aginst Alaska which is easy for my algoritm to catch.)</div>>
<div align="left"> </div>>
<div align="left">/Nicklas<br />
></div>>
<div align="left"> </div>>
<div align="left"> </div>>
<div align="left"><br />
> 2009-12-01 Nicklas Avén wrote:<br />
><br />
> ></div>>
<div align="left">wow, I think postgis will be hard to beat in the long run :-) </div>> >
<div align="left"> </div>> >
<div align="left">I'm not used to study those tree things, but it will be very interesting to follow this and try to understand it.</div>> >
<div align="left">Will it work on overlapping bboxes too?</div>> >
<div align="left"> </div>> >
<div align="left">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.</div>> >
<div align="left"> </div>> >
<div align="left">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 distances to with some index on the pointidentifiers list...</div>> >
<div align="left"> </div>> >
<div align="left">/Nicklas</div>> >
<div align="left"> </div>> >
<div align="left"> </div>> >
<div align="left"><br />
> ><br />
> > 2009-12-01 Paul Ramsey wrote:<br />
> ><br />
> > Niklas,<br />
> > ><br />
> > >Your cunning sorting trick got into my head and I thought and thought<br />
> > >on it and ended up borrowing the magic tree idea from Mark's prepared<br />
> > >p-i-p code, and added another dimension to that, so the trees are<br />
> > >actually in 2d space, and then starting thinking about how, given two<br />
> > >of these trees you could quickly find things like intersections or<br />
> > >even (*gasp*) distances...<br />
> > ><br />
> > >geog=# select distance(buffer('POINT(3 3)', 2),buffer('POINT(0 0)', 2));<br />
> > > distance<br />
> > >-------------------<br />
> > > 0.242640687119285<br />
> > >(1 row)<br />
> > ><br />
> > >geog=# select npoints(buffer('POINT(3 3)', 2));<br />
> > > npoints<br />
> > >---------<br />
> > > 33<br />
> > >(1 row)<br />
> > ><br />
> > >geog=# select 33*33;<br />
> > > ?column?<br />
> > >----------<br />
> > > 1089<br />
> > >(1 row)<br />
> > ><br />
> > >These two circles have 33 points each, so the brute force method<br />
> > >requires 1089 distance calculations to come up with an answer. The<br />
> > >magic trees took 29. It's also possible to *cache* the trees and<br />
> > >re-use them, both for distance calculations and intersections and<br />
> > >containments.<br />
> > ><br />
> > >Very exciting stuffs!<br />
> > ><br />
> > >However, we're almost to 1.5 and adding all the features you already<br />
> > >have in your code (maximums, points and lines of shortness, etc) would<br />
> > >take way too long. And I'm not sure my code is actually faster. Just<br />
> > >that it's much faster than the brute force ways.<br />
> > ><br />
> > >It's all in lwtree.c in liblwgeom if you want to look.<br />
> > ><br />
> > >P.<br />
> > >_______________________________________________<br />
> > >postgis-devel mailing list<br />
> > >postgis-devel@postgis.refractions.net<br />
> > >postgis.refractions.net/mailman/listinfo/postgis-devel<br />
> > ><br />
> > ></div>
</body>
</html>