[mkgmap-dev] Small holes in boundary coverage

Thu Mar 29 21:38:46 BST 2012

Hi Gerd,

thanks a lot.
Unfortunately the new patched code creates more holes than the current 
SVN code. The BoundaryCoverageUtil creates 1000 separate polygons for 
admin_level=2 instead of 640.

I have uploaded the results of the BoundaryCoverageUtil to
http://www.navmaps.eu/wanmil/coverage_2.zip.

It seems that there are many holes around the Greenwich meridian. Can 
you have a look on it and check if old or new code is better?

Anyhow I aggree that the holes are more a cosmetic problem. But maybe 
it's worthy to invest the time to know exactly what happens there to be 
sure that there are no other problems.

Thanks!
WanMil

> Hi WanMil,
>
> attached is a patch that changes all boundary routines to use double
> precision.
> The file format has changed again, so one has to create new boundaries.
>
> http://gis.19327.n5.nabble.com/file/n5604371/boundary_double_v1.patch
> boundary_double_v1.patch
>
> Although it uses double precision, the new format produces smaller files
> because
> it uses delta coding for the boundary coordinates.
>
> I found a strange error in Area.subtract(). For two given areas a1 and a2
> lying within
> a bbox, a1.subtract(a2) may result in an area lying outside of the bbox.
> I've added a test for that.
> The performance is almost equal, the newer version  may be a bit faster.
>
> Gerd
>
>
>
> GerdP wrote
>>
>> Hi WanMil,
>>
>> I can try writing the RAW format with double precision. Do you have a
>> sample input that
>> creates a hole? I tried africa and asia and found none, the europe file is
>> too large for my
>> machine.
>> We may also try to save the quadtree data with doubles without getting
>> much larger files if we use a compressed format (e.g. the delta coding
>> used in pbf or o5m).
>>
>> Gerd
>>
>>
>> WanMil wrote
>>>
>>> Hi Gerd,
>>>
>>> your conclusion sound very reasonable. The number of holes has been
>>> reduced quite a lot after your last patch and if your example a) b) and
>>> c) are not equal all the time there is no chance to avoid such holes
>>> completely.
>>>
>>> Just a quick idea: Would it improve (and reduce the number of holes) if
>>> the intermediate bounds format which is written first uses double
>>> instead of float precision? I think it doesn't really matter if the
>>> intermediate format uses more space on disk?!
>>>
>>> I will try to create updated bounds files during the weekend and then we
>>> can start a one week test phase with more users before merging back to
>>> trunk.
>>>
>>> WanMil
>>>
>>>> Hi WanMil,
>>>>
>>>> I found three reasons for these holes: errors in BoundaryQuadTree,
>>>> "errors"
>>>> in java.awt.geom.Area and rounding erros.
>>>>
>>>> My last patches fixed the errors that I found in BoundaryQuadTree, I
>>>> also
>>>> tried to avoid the problem
>>>> with the rounding errors (we are doing the calculations with double
>>>> precision, but we save with float
>>>> precision).
>>>>
>>>> I stopped  searching when I saw fewer holes in the result of the
>>>> performance
>>>> branch
>>>> than in the result of trunk.
>>>>
>>>> The errors in java.awt.geom.Area are complex. I think one has different
>>>> options to calculate the intersection of two areas a1 and a2:
>>>> a) Area x = new Area(a1); x.intersect(a2)
>>>> b) Area x = new Area(a2); x.intersect(a1)
>>>> c) Area x = new Area(a1); x.add(a2);x.subtract(a1);x.subtract(a2);
>>>>
>>>> In an ideal world I would expect to get exactly the same result for
>>>> these
>>>> three calculations, but sometimes the real results are not equal. The
>>>> same
>>>> problem occurs when we add the areas again in the BoundaryCoverageUtil.
>>>>
>>>> Maybe we can get rid of a few more of the holes if we manage to do all
>>>> calculations with doubles, but probably even doubles will not solve all
>>>> problems.
>>>>
>>>> The question is if we should invest time for that. I think the holes are
>>>> purely cosmetic, if you really manage to query BoundaryQuadTree for a
>>>> point
>>>> that lies within such a hole, it will return the result for a point that
>>>> is
>>>> next to it, I think this is good enough.
>>>>
>>>> What do you mean?
>>>>
>>>> Gerd
>>>>
>>>>
>>>>
>>>> WanMil wrote
>>>>>
>>>>> Hi Gerd,
>>>>>
>>>>> thanks for the patch. I have commited it although I still see the
>>>>> problem. I am not sure if the holes are at the same place but there are
>>>>> some of them which I cannot explain with wrong boundary data.
>>>>>
>>>>> Can you please recheck that?
>>>>>
>>>>> Thanks!
>>>>> WanMil
>>>>>
>>>>>> Hi WanMil,
>>>>>>
>>>>>> attached is a fix for this problem.
>>>>>>
>>>>>> Please, can you review if the UnusedElementsRemoverHook is still
>>>>>> useful?
>>>>>> With my test data, it is slowing down mkgmap a little bit and I also
>>>>>> see
>>>>>> a different result for one tile in the UK when I disable it.
>>>>>>
>>>>>> Gerd
>>>>>>
>>>>>>    >   Date: Thu, 15 Mar 2012 21:11:02 +0100
>>>>>>    >   From: wmgcnfg@
>>>>>>    >   To: mkgmap-dev at .org
>>>>>>    >   Subject: [mkgmap-dev] Small holes in boundary coverage
>>>>>>    >
>>>>>>    >   Hi,
>>>>>>    >
>>>>>>    >   I have compiled world bounds using the performance branch. They
>>>>>> can be
>>>>>>    >   downloaded from
>>>>>> http://www.navmaps.eu/wanmil/bounds_perf_20120313.zip.
>>>>>>    >
>>>>>>    >   I have checked the coverage of different admin_levels with the
>>>>>>    >   BoundaryCoverageUtil. The result for admin_level=2 can be
>>>>>> downloaded
>>>>>>    >   from http://files.mkgmap.org.uk/detail/61.
>>>>>>    >
>>>>>>    >   Some countries are missing (USA, Canada, some african countries).
>>>>>> I
>>>>>>    >   assume that their boundaries were/are corrupt.
>>>>>>    >
>>>>>>    >   The more interesting thing is that there are small holes
>>>>>> throughout
>>>>>> the
>>>>>>    >   world in admin_level=2. They seem to be created by the bounds
>>>>>>    >   preparation and should not be there. Gerd, can you please have a
>>>>>> look
>>>>>> on it?
>>>>>>    >
>>>>>>    >   Thanks!
>>>>>>    >   WanMil
>>>>>>    >   _______________________________________________
>>>>>>    >   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
>>>>>
>>>>> _______________________________________________
>>>>> mkgmap-dev mailing list
>>>>> mkgmap-dev at .org
>>>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>>>>>
>>>>
>>>>
>>>> --
>>>> View this message in context:
>>>> http://gis.19327.n5.nabble.com/Small-holes-in-boundary-coverage-tp5569161p5597147.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.19327.n5.nabble.com/Small-holes-in-boundary-coverage-tp5569161p5604371.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