logo separator

[mkgmap-dev] Bug in LocationHook?

From Gerd Petermann gpetermann_muenchen at hotmail.com on Wed Jan 11 08:37:10 GMT 2012

Hi WanMil,

attached is my current implementation of the BoundaryQuadTree. Maybe you (or others) can use it as it is.

I'm may have to change the code heavily to be able to store (and retrieve) the information of overlapping areas of different admin_levels.

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/ba8a5d82/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BoundaryQuadTree.java.patch
Type: application/octet-stream
Size: 5060 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120111/ba8a5d82/attachment.obj 


More information about the mkgmap-dev mailing list