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

Sun Apr 22 22:19:20 BST 2012

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 at iki.fi
>  > To: mkgmap-dev at lists.mkgmap.org.uk
>  > 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 lists.mkgmap.org.uk
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev