[mkgmap-dev] Bug in LocationHook?

Mon Jan 9 09:31:08 GMT 2012

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.