> Date: Sun, 22 Apr 2012 23:19:20 +0200
> From: wmgcnfg@web.de
> To: mkgmap-dev@lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] Subdivision width is 36627 at 3230916/1236133
>
> 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@iki.fi
> > > To: mkgmap-dev@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@lists.mkgmap.org.uk
> > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >
> >
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev@lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev