[mkgmap-dev] Small holes in boundary coverage

Tue Mar 27 21:46:41 BST 2012

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 lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev