[mkgmap-dev] Empty rectangles in map

Wed Apr 28 13:26:18 BST 2021

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: overSizePolyHole_v2.patch
Type: text/x-patch
Size: 5071 bytes
Desc: not available
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20210428/d9f4f59f/attachment.bin>