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@web.de To: mkgmap-dev@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@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.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@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev