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

Mon Apr 23 19:29:50 BST 2012

Hi WanMil,

okay, I'll try to find a better solution. Up to now I was working on improvements in splitter and a faster method
for the rastering of boundaries. The latter is almost done, and I assume that I'll have a patch ready tomorrow.

Gerd

> Date: Sun, 22 Apr 2012 23:19:20 +0200
> From: wmgcnfg at web.de
> To: mkgmap-dev at 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 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
> 
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120423/96c1f5f0/attachment.html 