[mkgmap-dev] Bug in LocationHook?From WanMil wmgcnfg at web.de on Sat Jan 7 20:32:40 GMT 2012
> 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 at lists.mkgmap.org.uk > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
- Previous message: [mkgmap-dev] Bug in LocationHook?
- Next message: [mkgmap-dev] Bug in LocationHook?
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list