[mkgmap-dev] Bug in LocationHook?

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 