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: [email protected] > To: [email protected] > 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 > > [email protected] > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > > _______________________________________________ > mkgmap-dev mailing list > [email protected] > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list [email protected] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
