[mkgmap-dev] Bug in LocationHook?

Sun Jan 8 07:16:58 GMT 2012

Hi Gerd,

I don't see a problem just right now.

The algorithm is as follows:
1. Load the precompiled bounds
2. Sort the bounds in the order
    1. all bounds tagged with a postcode tag only
    2. all bounds tagged with admin_level=11
    3. all bounds tagged with admin_level=10
    4. ..
    5. all bounds tagged with admin_level=2
3. Go through the bounds and assign all tags and assign the referenced 
bounds tags also.
4. If an element is tagged with all remaining bounds tags it can be 
removed from the quadtree.

Now comes the tricky thing:
If a boundary with admin_level=4 also has a postcode tag it is ensured 
that no element without postcode tag is removed from the quadtree.
Why?
I assume that there must not be two overlapping postcode areas. So 
tagging admin_level=10 with postcode 12345 and admin_level=9 with 
postcode 12345 too would be an OSM error. There should be only one 
postcode area defining the whole area.
With this assumption there can be only one bounds tagged with postcode 
only or one bounds tagged with an admin_level and the postcode.
Postcode only bounds are handled first so after that it is only possible 
that an element lies in an area tagged with admin_level and postcode. So 
it's sufficient to check that the admin_level is set before removing it 
from the quadtree.

WanMil

> Hi WanMil,
>
> I think the problem is that we sort the boundaries before analysing the
> lies_in tag. If we first fill the missing zip code tag (and maybe the
> admin_level tag as well) from the boundaries found in lies_in, we should not
> see the problem that elements are removed too early.
> I'm just trying that.
>
> Ciao,
> Gerd
>
>
> WanMil wrote
>>
>>> Hi,
>>>
>>>
>>> WanMil wrote
>>>>
>>>> that sounds strange. I think recreating the quadtree would only be
>>>> benficial if recreating takes less time than removing elements. I wonder
>>>> if that's the case?
>>>>
>>>
>>> I think the current quadtree implementation has one problem: As long as
>>> it
>>> still contains a few elements, a get(...) takes more or less the same
>>> time.
>>> I guess that's because it still calls a lot of intersect() calculations
>>> to
>>> return a result.
>>> I am still searching for an error which seems to slow down the program
>>> too
>>> much, but my patch does this:
>>> - It keeps the list elemList
>>> - If currLevel is changed, it checks if the previous level caused any
>>> changes to the elements in the quadTree. If not, the whole elemList is
>>> tested, all elements that are fully worked out are removed.
>>> If the remaining list is much smaller, the quadtree is replaced.
>>
>> Sounds reasonable. There might be another solution within the quadtree:
>> At the moments subtrees are not reduced. At an early stage of
>> implementation I did have implemented this but it did not have an
>> advantage.
>> Now the quadtree uses other datastructures which might be easier to
>> reduce. So a node which is not a leaf can be reduced after a successful
>> remove operation if all childs are leafs and the sum of points in the
>> leafs are lower than the maxsize. That should be not too complicted to
>> implement and does not require any special handling in the LocationHook.
>>
>> I will give it a try within the next days.
>>
>> WanMil
>>
>>
>>>
>>> Ciao,
>>> Gerd
>>>
>>>
>>> --
>>> View this message in context:
>>> http://gis.638310.n2.nabble.com/Bug-in-LocationHook-tp7157897p7161772.html
>>> Sent from the Mkgmap Development mailing list archive at Nabble.com.
>>> _______________________________________________
>>> 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-tp7157897p7162654.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