[mkgmap-dev] Bug in LocationHook?

Wed Jan 11 08:16:22 GMT 2012

Hi WanMil,

I tried omitting the merge step, it did not show more than 1% improvement, and I wasn't sure about the side effects regarding the lies_in processing.
I will continue analyzing that later.

Gerd

> Date: Sun, 8 Jan 2012 22:17:25 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] Bug in LocationHook?
> 
> > Hi WanMil
> >
> >  > 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 tried it anyway and found some interesting results:
> > Sometimes it is ~ 20% faster, sometimes it is much slower (maybe 100% ).
> > So, I think it might be a good alternative if we can avoid the bad cases.
> >
> > I created a simple grid that stores all boundaries that intersect with
> > each element (similar to the grid in splitter). This is done quicker
> > than the creation of the quadtree.
> > Using the grid, for each Coord I get a list of boundaries to test:
> > ...
> > Boundary b = currentBoundaries.get(blist.get(i));
> > if (b.getBbox().contains(co)){
> > if (b.getArea().contains(co.getLongitude(),co.getLatitude())){
> > return b; // return the area that contains the point }
> > }
> > ...
> >
> > the performance problem is in the b.getArea().contains(...)
> > For some boundaries, this test performs very slowly (> 1ms for one
> > test), and it seems to be related to the number of points that form the
> > shape of the boundary.
> > Some areas are built with < 20 points, others with > 8000.
> >
> > So, what I need is a quicker contains() or some kind of tree that allows
> > to avoid it.
> > Any idea?
> 
> I think the problem does not exist in the current quad tree because the 
> areas are splitted into subareas. This also reduces the number of points 
> and makes it quicker and easier to test. You could get the number of 
> points from the boundary and decide if an area should be splitted into 
> subareas. It would also be possible to save the splitted subareas as 
> precompiled bounds. If your grid always have the same dimension this 
> might improve the handling.
> 
> You might also remove the merge step. For most tiles more than one 
> precompiled file is loaded. The bounds are merged afterwards. This step 
> sounds superfluous as the LocationHook only checks if one point of a way 
> is in the boundary and not for all points. Therefore it is not necessary 
> to have the boundary area as one complete area object.
> 
> WanMil
> 
> >
> > Ciao,
> > Gerd
> >
> >
> >
> > _______________________________________________
> > 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/20120111/52f25c00/attachment.html 