[mkgmap-dev] [Patch v4] LocationHook with new Quadtree

Tue Jan 17 21:57:20 GMT 2012

Hi Gerd,

fine. (I cannot commit that for now because the snippet has a compile 
problem with bbox.contains and I don't have time to fix that now).

Please think about the change to start searching with the mid point. 
Probably it won't reduce the number of get operations but I expect that 
it improves the quality of the search results in case the element 
crosses a boundary.

WanMil

> Hi WanMil,
>
> funny, I also thought a new branch would be a good idea, and my latest
> version also uses the mid
> point for the first test. Since I've added this snippt to
> BoundaryQuadTree, the algorithm always
> seems to find a good result for the first point that is searched. This
> saves quite a lot of searches.
>
> public Tags get(Coord co){
> Tags res;
> res = root.get(co);
> if (res == null && bbox.contains(co)){
> // we did not find the point, probably it lies on a boundary and
> // the clauses regarding insideness of areas make it "invisible"
> // try again a few other nearby points
> Coord neighbour1 = new Coord(co.getLatitude()-1, co.getLongitude());
> Coord neighbour2 = new Coord(co.getLatitude() , co.getLongitude()-1);
> Coord neighbour3 = new Coord(co.getLatitude()+1, co.getLongitude());
> Coord neighbour4 = new Coord(co.getLatitude() , co.getLongitude()+1);
> res = root.get(neighbour1);
> if (res == null)
> res = root.get(neighbour2);
> if (res == null)
> res = root.get(neighbour3);
> if (res == null)
> res = root.get(neighbour4);
> }
> return res;
>
>
> Ciao,
> Gerd
>
>  > Date: Mon, 16 Jan 2012 22:34:22 +0100
>  > From: wmgcnfg at web.de
>  > To: mkgmap-dev at lists.mkgmap.org.uk
>  > Subject: Re: [mkgmap-dev] [Patch v4] LocationHook with new Quadtree
>  >
>  > Hi Gerd,
>  >
>  > I think there are some steps left for the optimization. Therefore I have
>  > created a new branch (performance) for all kind of performance
>  > improvements (starting with your LocationHook optimizations). It's
>  > easier for other people to test.
>  > The branch can be merge back to the trunk if it reaches stability.
>  >
>  > One new idea:
>  > I think your idea to use the first point of a way to get it's location
>  > information is better than the old behaviour of the LocationHook because
>  > that was not forseeable. Now we have an easy rule: First point (or if
>  > that has no location information the next point which has such
> information).
>  > What do you think about using the mid point instead of the first point.
>  > The mid point (points.size()/2) would avoid problems with streets that
>  > have one point just before the city border. Using the mid point would
>  > give a higher probability that most (or all) of the street lies in the
>  > same boundaries like the mid point.
>  >
>  > WanMil
>  >
>  >
>  > > Hi,
>  > >
>  > > this contains the corrections and optimizations suggested by WanMil
> and is
>  > > now based on r2168.
>  > > I decided to return a reference to the internal Tags instance
> instead of
>  > > using a costly Tags.copy() for each result of quadtree.get()
>  > > If that is not liked, I suppose to change the get() to something like
>  > > addLocationTags (Coord co, Tags tags){..}
>  > > to let quadtree add the missing tags to the callers tags strucure.
>  > >
>  > > ciao,
>  > > Gerd
>  > >
>  > >
> http://gis.638310.n2.nabble.com/file/n7182307/locationHook_speedup_v4.patch
>  > > locationHook_speedup_v4.patch
>  > >
>  > >
>  > >
>  > > --
>  > > View this message in context:
> http://gis.638310.n2.nabble.com/Patch-v4-LocationHook-with-new-Quadtree-tp7182307p7182307.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