[mkgmap-dev] Bug in LocationHook?From Gerd Petermann gpetermann_muenchen at hotmail.com on Sun Jan 8 06:31:58 GMT 2012
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 at web.de > To: mkgmap-dev at 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 at lists.mkgmap.org.uk > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > > _______________________________________________ > mkgmap-dev mailing list > mkgmap-dev at lists.mkgmap.org.uk > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev -------------- next part -------------- An HTML attachment was scrubbed... URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120108/d2c76b09/attachment.html
- 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