
Hello WanMil, Currently we are placing the elements into the quadtree and iterate over the boundaries, actually we place each point of a way into the quadtree. Did you ever consider to do the search the other way around? I mean, put the boundaries into something like a simple grid or quadtree or r-tree and iterate over the elements to search a boundary? I did not do a deep analysis of the complexity of both strategies, but I have the feeling that the latter could be much faster. ciao, Gerd
Date: Sat, 7 Jan 2012 21:32:40 +0100 From: wmgcnfg@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Bug in LocationHook?
Hi,
WanMil wrote
that sounds strange. I think recreating the quadtree would only be benficial if recreating takes less time than removing elements. I wonder if that's the case?
I think the current quadtree implementation has one problem: As long as it still contains a few elements, a get(...) takes more or less the same time. I guess that's because it still calls a lot of intersect() calculations to return a result. I am still searching for an error which seems to slow down the program too much, but my patch does this: - It keeps the list elemList - If currLevel is changed, it checks if the previous level caused any changes to the elements in the quadTree. If not, the whole elemList is tested, all elements that are fully worked out are removed. If the remaining list is much smaller, the quadtree is replaced.
Sounds reasonable. There might be another solution within the quadtree: At the moments subtrees are not reduced. At an early stage of implementation I did have implemented this but it did not have an advantage. Now the quadtree uses other datastructures which might be easier to reduce. So a node which is not a leaf can be reduced after a successful remove operation if all childs are leafs and the sum of points in the leafs are lower than the maxsize. That should be not too complicted to implement and does not require any special handling in the LocationHook.
I will give it a try within the next days.
WanMil
Ciao, Gerd
-- View this message in context: http://gis.638310.n2.nabble.com/Bug-in-LocationHook-tp7157897p7161772.html 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
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev