[mkgmap-dev] Subdivision width is 36627 at 3230916/1236133

Fri Apr 27 18:24:57 BST 2012

Hi Gerd,

> Hi WanMil,
>
> before I start thinking about a different algorithm, I just want to make
> sure that
> I understood the cause of the problem in the existing one:

I am also not 100% sure if I understand the algorithm completely so 
please don't understand my answers as 100% correct :-)

>
> 1) mkgmap complains when a subdivision has an area with a width>  0x7fff (if
> resolution is 24)
Yes. Each subdivision has a specific maximum area width.

> 2) we add elements to the area and update the with and height of the area
> whenever an added
> element has a point that lies outside of the previous bounds.
Correct. Maybe that could be a good point to improve the algorithm 
essentially. Instead of adding elements to the subdivision and detecting 
that the width/height has been exceeded it would be better to start with 
an empty subdivision. Then add elements if they don't exceed the 
subdivion limits. If no more elements can be added create a new 
subdivision. I am not sure which limitations must be met to be compliant 
with garmin subdivision format, e.g. is it necessary that subdivisions 
are hierachical in the different resolutions and is it necessary that an 
element is not contained in two different hierarchies. That would 
require to start at the upper most resolution and split them as needed. 
This is the current algorithm.

> 3) the methods in PolygonSubdivSizeSplitterFilter and LineSizeSplitterFilter
> should make sure that
> a single element is not larger than the maximum size of 0x7fff (I think
> LineSizeSplitterFilter doesn't
> even do this correctly, but a corrected version did not solve the problem)
Correct. The filters should ensure that a single element is not larger 
than the maximum width/height of a resoultion.
I think one problem can be if there are two large elements within one 
subdivions whith its center points close together. If the center points 
are located always in the same subdivision no matter how often the 
subdivision is split the algorithm will fail.
Example (see attached drawing): two parallel lines (green) with max 
width, close together and slightly shifted. Their center points (black 
crosses) are so close together so that they always belong to the same 
subdivision. The subdivision (red) size must grow to the blue bounds but 
the blue bounds exceed the subdiv width.

>
> The error message "Subdivision width is 36627..." is produced because of a
> long MapLine with a width of ~72000 that has just 7 points. The line between
> the first 6 points has a  width<  30000, the last point is far away and adds
> the ~ 42000. That also means, the middle of the line is far away from any
> point that belongs to the line. Since LineSizeSplitterFilter just splits the
> line into parts that have a width<  0x7fff, we still add a part of the line
> that is far away from the middle of the MapArea and therefore outside of the
> maximum area size.
> Is that correct?

Sounds reasonable.

>
> To solve the problem, I think we have to find the first and last point which
> is not too far away from the center, and then split the element into 2 or 3
> parts.
> Would that work?

Sounds reasonable too. But one must ensure that the center points of 
each splitted part are also located within the subdivions basic bounds. 
Otherwise the splitted part will not be put into the subdivision (I 
think...).

WanMil

>
> Gerd
>
>
>
> Gerd
>
>
> WanMil wrote
>>
>> I think (for quite a while) that the subdivision split code requires a
>> complete rework to get rid of problems with it.
>>
>> A broad algorithm how subdivisons are created is:
>> 1. Create subdivisions with maximum allowed size
>> 2. Add all elements to their subdivision. An element is added to a
>> subdivision if its center point lied within the subdivision.
>> 3. For all subdivisions that are too big: Divide them into two halves
>> and assign the elements again.
>>
>> The fact that lines and shapes do not have one point only is completely
>> ignored. So it might be possible that the center point lies within a
>> subdivison but the bounding box of the element exhausts the max size of
>> a subdivision.
>>
>> I think the algorithm should be the other way round:
>> Create a subdivision with minimum size and add (in an intelligent way)
>> elements until the subdivision is full.
>>
>> The problem is "in an intelligent way" because there are multiple
>> restrictions for a subdivison so that it is not so easy to optimize the
>> algorithm. I started with an improvement some time ago but did not
>> finish it. Maybe I can dig out the old source code and post it so that
>> you can have a look on it and use it as one idea how to improve the
>> situation.
>>
>> So long if you are interested in understanding what's happening there
>> start with the classes
>> MapSplitter
>> MapArea
>> all filter classes in uk.me.parabola.mkgmap.filters
>> and of course Subdivision
>>
>> WanMil
>>
>>> Hi,
>>>
>>> I think the problem is not a polygon or something like this.
>>> MapSplitter contains a lot of tests to make sure that an area doesn't
>>> contain too many objects, but the test doesn't check for the case that
>>> the area is too large, so it skips the split process for a large almost
>>> empty area:
>>> if (area.getNumLines()>  MAX_NUM_LINES ||
>>> area.getNumPoints()>  MAX_NUM_POINTS ||
>>> (sizes[MapArea.POINT_KIND] +
>>> sizes[MapArea.LINE_KIND] +
>>> sizes[MapArea.SHAPE_KIND])>  MAX_RGN_SIZE ||
>>> sizes[MapArea.XT_POINT_KIND]>  MAX_XT_POINTS_SIZE ||
>>> sizes[MapArea.XT_LINE_KIND]>  MAX_XT_LINES_SIZE ||
>>> sizes[MapArea.XT_SHAPE_KIND]>  MAX_XT_SHAPES_SIZE){
>>> ...
>>> }
>>>
>>> log.debug("adding area unsplit", ",has points" + area.hasPoints());
>>>
>>> later, in MapBuilder, this part causes the warning message:
>>> int w = ((area.getWidth() + 1)/2 + mask)>>  shift;
>>> if (w>  0x7fff) {
>>> log.warn("Subdivision width is " + w + " at " + new Coord(latitude,
>>> longitude));
>>> w = 0x7fff;
>>> }
>>>
>>> I am not sure what kind of test we have to add in MapSplitter.
>>>
>>> Gerd
>>>
>>>
>>>   >  Date: Sun, 22 Apr 2012 23:39:28 +0300
>>>   >  From: marko.makela@
>>>   >  To: mkgmap-dev at .org
>>>   >  Subject: Re: [mkgmap-dev] Subdivision width is 36627 at
>>> 3230916/1236133
>>>   >
>>>   >  Hi WanMil,
>>>   >
>>>   >  >AFAIK 3230916/1236133 is only the center point of the problematic
>>>   >  >polygon. I thought that my commit r2028 has fixed problems where a
>>>   >  >single polygon is too big to fit into a subdivision. This is done by
>>>   >  >the class PolygonSubdivSizeSplitterFilter.
>>>   >
>>>   >  Could the diagnostics be extended to show more details of the polygon,
>>>   >  such as the WGS84 coordinates of some nodes (or the OSM id or tags, if
>>>   >  they are available)? I am happy to apply such a patch and rerun, and
>>>   >  narrow down the input if it is of any help. Currently, I am using
>>> mkgmap
>>>   >  r2272.
>>>   >
>>>   >  >The MapSplitter/MapArea class should be a good starting point to
>>> track
>>>   >  >down the problem.
>>>   >
>>>   >  I hope you or Gerd can figure this out. Sorry, my day job keeps me so
>>>   >  busy that I do not have any spare brain power for coding or debugging
>>> at
>>>   >  the moment.
>>>   >
>>>   >  Best regards,
>>>   >
>>>   >  Marko
>>>   >  _______________________________________________
>>>   >  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/Subdivision-width-is-36627-at-3230916-1236133-tp5657229p5670699.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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: subdivision_width.svg
Type: image/svg+xml
Size: 9265 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120427/f9223c53/attachment.bin 