[mkgmap-dev] [PATCH v1] Subdivision splitting

Sun Sep 18 15:39:22 BST 2011

> Am 14.09.2011 09:24, schrieb WanMil:
>> Attached patch should fix (all?) subdivision splitting problems.
>> Error like "Area too small to split at ..." cannot occur any more
>> because the way how subdivisions are split is changed.
>>
>
> I tested the 2028 and 2028 version with patch. Both seems to work. But
> for my test cases the patch was not needed.
>
> I'm new to the mailing list because of the too small to split error. I
> was thinking that it takes longer to fix the problem and looked into the
> code and did write code to split also the shapes when the areas are
> splitted. This works but it expect that shapes are before splitting
> within the area boundaries.

Yes, at the moment only the center of the shape is guaranteed to be 
within the area (subdivision). The area has two bounds: an official 
bounds which is guaranteed to have an non exhausting size and the "full 
bounds" which contains the real dimension of all points, lines and 
shapes. When splitting the shape it is possible that the center of the 
new splitted shapes are no longer within the subdivision official 
bounds. That's the main problem of the current subdivison split algorithm.

I think there are two main basic approaches how to fix that:
1. Drop the full bounds and split the shapes and lines on the official 
bounds. This has the advantage that you don't have an overlap of 
subdivisions and the disadvantage that you may get lots of additional 
points automatically created by the bounds splitting.

2. Drop the full bounds and create subdivisions by adding elements step 
by step until the subdivision limits are exhausted. This has the 
advantage that most of your subdivisions are maximally filled but the 
subdivisions will have a bigger overlap.

I started to implement approach 2 but after thinking again about that 
approach 1 seems to be a good solution also (and with less changes to 
existing code).

> This is not the case, and it stopped this,
> because it can't be proofed that it will work with any map. For
> debugging i did write a patch to generate overlays for Google earth to
> see the processing of mkgmap. This may of interest for you. The result
> files are to big for attaching, i put it on http://rlaib.de/mkgmap
>
> gomera-2027.kmz is processed with mkgmap 2027
> gomera-2028-type83.kmz is processed with mkgmap 2028 filtered to shape
> type 83 to make the file smaller.
> gomera-2028-wanmil.kmz is with the patch.
>

Thanks, looks interesting. Can you post your patch?

WanMil