[mkgmap-dev] Bug in LocationHook?From WanMil wmgcnfg at web.de on Sun Jan 8 07:04:12 GMT 2012
Hi Gerd, I remember that I tried the other strategy. I don't remember how I did organize the boundaries. But it was *magnitudes* slower (not just slower but magnitudes slower) so that I didn't started to improve my poor implementation. I also tried to use other data structures with the help of other libraries (like JSI or JTS). Some of the data structures were little faster than the ElementQuadTree (remember: the old one before our optimizations). But the improvements were too small to use an additional library in mkgmap. WanMil > 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 > > > _______________________________________________ > 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