Ok, I think I didn't understand your concept: The basis principle of the tree is that there are non intersecting areas only so that only one area can be found for one point. And each area contains all tags of all intersecting boundaries. I thought merging would be a performance thing only. The advantage of this is that you only need one match to get all. If we implement cutting ways by boundaries there is the disadvantage that we don't know in the LocationHook which tags are relevant and therefore ways might be splitted too much. WanMil
Hi WanMil,
of course it is faster, but how do you solve the problem that the information is incomplete? Maybe I did not make that clear: Without the merge step, you have to travel through the nodeElems until information from all areas in combined. If you don't do this, you have the same result as in trunk when you remove an element from the list after it was first processed.
Ciao, Gerd
WanMil wrote
Mmmh, I tested with an without merge using 66 tiles.
LocationHook time with merge: 72,7s LocationHook time without merge: 55,6s
The times are very different. So I assumed that the GC slowed down the merge variant so I compared the timings of each tile. One tile was 8s slower with the merge variant. So maybe the GC slowed it down.
But most of the tiles were quicker with the non merge variant. Some are quicker with merging and some are rather equal.
Maybe timings can be improved by changing the depth and the nodeNum constraint in the split method but merging does not seem to be an overall improvement.
WanMil
Hi WanMil,
yes, it improves performance because the merge is done only once, and without the merge it would be needed to do more or less the same action for each single search. I see no better way to handle the problem with those level=7 areas.
Ciao, Gerd
WanMil wrote
> > > > * I don't understand why you need a merge() method. Could you explain > > what you are doing in this method and why it's required? > The get method() of the tree returns the data for the first area that > contains the coord. > This area should contain all tags of the area itself plus those from > areas intersecting it. > Maybe this is not correct?
Sounds wrong. If Area a1 is intersected by a2 only in 10% of its area then an element located in the 90% that does not intersect would be tagged with a1 and a2?
The merge() first creates a new nodeElem with the intersection, it merges the tags into this and subtracts the intersection from the others, so only the 10% part gets more tags. Thinking again about this I might not need both subtract() calls since I move the intersection part before the others .
I doubt that merge improves the performance. It breaks two areas into three probably with intersecting bounding boxes. So I would expect that you don't save much contains checks. But don't mind about my doubts: Did you measure a noticeable performance difference?
WanMil _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.638310.n2.nabble.com/Patch-v3-LocationHook-with-new-Quadtree-tp71... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.638310.n2.nabble.com/Patch-v3-LocationHook-with-new-Quadtree-tp71... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev