[mkgmap-dev] Bug in LocationHook?

Sun Jan 8 09:34:41 GMT 2012

> Hi WanMil,
>
> here is an example that shows the problem : Way 104052830 lies in two
> different boundaries with the same admin_level=8: r114493 (Creutzwald) and
> r1184868 (Völklingen) . I think this is correct, a way can cross boundaries.
>
> The way is not found in a postcode-only boundary.
>
> For r114493, mkgmap does not find the postcode tag, but for r1184868 it
> does.
>
> mgkmap finds the way first in r114493 when currLevel is admin_level=8 and
> finds all remaining tags in r114493, so it removes the way from the
> quadtree.
>
> If the way is not removed, we find it again in r1184868 which would set
> postcode as well.
> Of course, it makes no sense to set the postcode of r1184868 and the name of
> r114493, so mkgmap probably works all right.
>
> The problem is that it would also be correct to find r1184868 and tag the
> way with different data, and that makes it hard to compare results of mkgmap
> if I change the logic so that this happens :-(

Ok, that's a very basic problem of the current LocationHook 
implementation. Elements that belong to more than one boundary are 
located to one of it. Also if the element only touches on boundary it is 
possible that it is located to it.
It would be possible to change that (which also means ways/polygons 
needs to be splitted) but the performance would be terrible.

>
> Anyway: I saw that r114493 contains a tag "addr:postcode=57150" which is
> ignored by LocationHook. What would be the right way to recognize that as a
> zip code?

This must be addressed by the style. LocationHook only adds the 
mkgmap:XXX tags which can be used by the style. The real assingment is 
done in the style. (in the default style) There are different rules for 
each possible tag. The first rule is the most prioritized rule. So if 
you move the addr:postcode rule before the mkgmap:postcode rule then the 
addr:postcode tag is preferred.

>
> Gerd
>
>
>
>
>
>
> WanMil wrote
>>
>> No.
>> An element can lie only in one admin_level with each number bound (one
>> for admin_level=11,10,9,8,7,etc.).
>> There can be only one bound tagged with postcode.
>> If an admin_level is tagged with a postcode there must be no other bound
>> at the same position tagged with postcode.
>> That means it is sufficient to check for the admin_level.
>>
>> That's tricky but it works if the input data is correct.
>>
>> WanMil
>>
>>> WanMil,
>>>
>>> the problem is this:
>>> We 1st process all boundaries with postcode-only tag. That's ok.
>>> We start processing boundaries that have an admin-level tag.
>>> The first boundary that has an admin-level tag but no postcode-tag
>>> switches
>>> the currLevel from postcode to something starting with
>>> mkgmap:admin-level,
>>> but we still may have other boundaries that have the postcode tag coming
>>> later.
>>> So, I think we must first process all boundaries that have a postcode
>>> tag.
>>>
>>> Gerd
>>>
>>>
>>> WanMil wrote
>>>>
>>>> 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 .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-tp7157897p7164147.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-tp7157897p7164242.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