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.
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.
> Date: Sat, 7 Jan 2012 21:32:40 +0100
> From: wmgcnfg@web.de
> To: mkgmap-dev@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@lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev