[mkgmap-dev] Bug in LocationHook?

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