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

Mon Jan 16 21:44:28 GMT 2012

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120116/81321150/attachment.html 