[mkgmap-dev] Empty rectangles in map

Mon May 10 15:14:03 BST 2021

Hi Ticker,

thanks, results look much better. I see no changes in "normal" files and only small change in the test case.

Commited with r4701.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
Gesendet: Montag, 10. Mai 2021 13:32
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] Empty rectangles in map

Hi Gerd

Here is the change that always splits polygons into subdivisions by
dividing along the internal boundaries rather than clipping. It is more
efficient and the empty rectangle problem goes away.

Ticker

On Wed, 2021-04-28 at 12:41 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> okay, so I'll wait for your results. The v1 patch always produces
> larger files with normal maps without visual effects, so it seems to
> split more often than needed (or prohibit merging too often)
>
> Gerd
>
> ________________________________________
> Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> Gesendet: Mittwoch, 28. April 2021 14:26
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Empty rectangles in map
>
> Hi Gerd
>
> Here is patch configured for Method 1, with more clarity about how to
> change.
>
> I think the best solution will be a super Method 4. For a 5 x 4
> subdivision grid it will reduces the number of polygon cuts from 80
> (5*4*4) to 19 (5-1+5*(4-1)).
>
> It shouldn't be too difficult to implement and I'll look at it next
> week.
>
> Ticker
>
> On Wed, 2021-04-28 at 09:14 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > please create two separate patches for method 1 and 2. It's not
> > obvious to me what changes are needed to get method 1.
> >
> > Gerd
> >
> > ________________________________________
> > Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> > von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> > Gesendet: Dienstag, 27. April 2021 13:11
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] Empty rectangles in map
> >
> > Hi Gerd and others
> >
> > The cause for this unrendered area is as follows:
> >
> > A large multipolygon (larger than the maximum size for a level 1
> > subdiv) exists, and is broken into some similar size pieces and
> > some
> > smaller pieces to expose inners/holes. The same problem can be
> > caused
> > by any polygons having these size properties.
> >
> > Option --order-by-decreasing-area is not in effect (with this
> > option
> > the problem goes away).
> >
> > At the outermost level, the large pieces are split into the grid of
> > subdivs necessary to be within size limits. Small pieces that fit
> > within a subdiv are allocated to the correct one. Intermediate
> > pieces
> > that extend out of the nominal subdiv bounds, but don't exceed the
> > actual addressing limits, are allocated to an existing subdiv based
> > on
> > their centre. Larger pieces that fit in a subdiv but would cause
> > size
> > problems if added to an existing subdiv are given a subdiv of their
> > own.
> >
> > At the next level down, each of the above subdivs will required
> > splitting to fit within the addressing limits. The logic that did
> > this
> > used the subdiv bounds and split this into a grid. Then every
> > element
> > in the outer MapArea is processed as above (ie split, safely
> > placed,
> > placed with overlap or own subdiv)
> >
> > The problem is that the splitting algorithm simply goes through the
> > child subdiv, clips the polygon to this size and saves the bits
> > that
> > are within the area. Polygon parts that are outside the defined
> > outer
> > level never get noticed!
> >
> > There are various possible solutions:
> >
> > Method 1: use the rigorous polygon splitting into subdivs that -
> > -order
> > -by-decreasing-area uses for levels above level 0. This is simple
> > to
> > implement, safe, mergeShapes might recombine more cut fragments as
> > they
> > are all together. Disadvantages are that, for a normal map, more
> > polygons might be split, leading to larger RGN size (but not for
> > bad
> > -map-split.osm.pbf). The overall size is still less that with -
> > -order
> > -by...
> >
> > Method 2: When the child subdiv grid is created, use any expanded
> > size
> > of the parent subdiv. This stops overhanging bits of polygons being
> > lost. Again, simple to implement. It results in overlapping subdivs
> > at
> > lower levels and I don't know this causes other problems, but
> > probably
> > not; this used to be done and still does for some sizes of polygons
> > and
> > lines. Some shape-merging won't happen because the joining bits are
> > in
> > a different subdiv.
> >
> > Method 3: Allocated oversize polygons to their own subdiv. Again,
> > simple to implement, but I see no advantage over Method 2. Even
> > more
> > shape-merging might not happen.
> >
> > Method 4: Detect when an object will have bits missed and semi-cut
> > rather than clip them to continue having an oversize part in the
> > child
> > subdiv. This is more complicated to implement but, if done, could
> > replace the clipping code and be more efficient. If a parent subDiv
> > is
> > divided into 2 children, it already happens like this.
> >
> > Although I prefer Method 1, I suspect Method 2 is what should be
> > done
> > in the short-term and so I've attached a patch that is configured
> > for
> > Method 2, but, with a couple of edits to change some flag handling,
> > does Method 1.
> >
> > Ticker
> >
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev