[mkgmap-dev] Small holes in boundary coverage

Thu Mar 29 17:41:05 BST 2012

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.