[mkgmap-dev] Bug in LocationHook?

Wed Jan 11 00:24:40 GMT 2012

Hi WanMil,

hmm, sounds interesting, but I don't yet understand why we need a different structure for this.
If I got this right, you want to avoid assigning tags that are not needed by the style. 
I think this can also be done with the existing structure, we just have to filter the 
map boundarySetTags .
Or, if we know that only level=4 and level=2 are referenced, maybe we can omit searching some of the boundaries in the ElementquadTree.

Besides that, my quadtree works, but it doesn't save as much time as expected, and I found a small bug in the Area.contains() method:
If I search for a point that lies exactly on the right most corner or line of the area, contains() doesn't always find it.
I thought this is because of rounding errors, but if I got it right, it is simply a wrong test (x + w < y instead of x + w <= y).
If you like, I can prepare a small sample to show that.
I thought that the result of my implementation of LocationHook should be exactly the same as that from trunk when I make sure that both do only use the same point of a way for searching. In many cases, it was like that, but because of the above error, it sometimes was not.
Took me quite a while to track that down ;-)

My solution is still not much faster than r2165 (maybe 5%-10%) because I create a new quadtree for each level and then iterate through the elements. This requires more or less the same number of calculations as r2165, when only one point of a way is put into the quadtree.

I want to have a solution that creates the quadtree so that it stops if the (sub) tree is fully covered by one or more areas. It should be possible to do this in a short time. If I can manage to identify the intersections of different boundaries, I could merge the tags of them and that would mean that each elem has to be searched only once. That's what I am working on now.

Ciao,
Gerd

> Date: Tue, 10 Jan 2012 22:42:21 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] Bug in LocationHook?
> 
> Hi Gerd,
> 
> if you manage to provide a high performance data structure to check in 
> which areas an element lies in then it might also be possible to move 
> the LocationHook into the style system. So there might be a rule like:
> 
> mkgmap:admin_level2 lies_in 'DEU' { set 
> mkgmap:country='mkgmap:admin_level2' }
> 
> Maybe this reduces the costs for assigning the boundary information a 
> lot because only the boundaries really referenced by the style must be 
> checked.
> 
> WanMil
> 
> > Hi WanMil,
> >
> > I've coded a quadtree that allows to store the boundary areas. Now I always
> > see better throughput,  but memory requirement is a bit higher.
> > I think the way is correct, but I'll need some time for testing and fine
> > tuning.
> >
> > Ciao,
> > Gerd
> >
> >
> >
> > WanMil wrote
> >>
> >>> 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 .org
> >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>
> >> _______________________________________________
> >> mkgmap-dev mailing list
> >> mkgmap-dev at .org
> >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>
> >
> >
> > --
> > View this message in context: http://gis.638310.n2.nabble.com/Bug-in-LocationHook-tp7157897p7167271.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/20120111/f8f3850a/attachment.html 