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

Fri Apr 27 17:02:15 BST 2012

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:

1) mkgmap complains when a subdivision has an area with a width > 0x7fff (if
resolution is 24)
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.
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)

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?

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?

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.