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: [email protected]
> > To: [email protected]
> > 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
> > > [email protected]
> > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >
> > _______________________________________________
> > mkgmap-dev mailing list
> > [email protected]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
