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-boun...@lists.mkgmap.org.uk> im Auftrag
> von Ticker Berkin <rwb-mkg...@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@lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Index: src/uk/me/parabola/mkgmap/build/MapArea.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapArea.java (revision 4687)
+++ src/uk/me/parabola/mkgmap/build/MapArea.java (working copy)
@@ -257,14 +257,16 @@
continue;
}
int areaIndex = pickArea(mapAreas, e, xbaseHp, ybaseHp, nx, ny, dxHp, dyHp);
- if ((shapeBounds.getHeight() > maxHeight || shapeBounds.getWidth() > maxWidth) &&
- !areas[areaIndex].contains(shapeBounds)) {
+ if (areas[areaIndex].contains(shapeBounds)) {
+ mapAreas[areaIndex].addShape(e);
+ } else if (shapeBounds.getHeight() <= maxHeight && shapeBounds.getWidth() <= maxWidth) {
+ // this polygon is partially outside the subdivision, but won't exceed the allowable offsets
+ mapAreas[areaIndex].addShape(e);
+ } else {
MapArea largeObjectArea = new MapArea(shapeBounds, areaResolution, true); // use splitIntoAreas to deal with overflow
largeObjectArea.addShape(e);
addedAreas.add(largeObjectArea);
- continue;
}
- mapAreas[areaIndex].addShape(e);
}
}
Index: src/uk/me/parabola/mkgmap/build/MapBuilder.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapBuilder.java (revision 4687)
+++ src/uk/me/parabola/mkgmap/build/MapBuilder.java (working copy)
@@ -803,11 +803,16 @@
List<SourceSubdiv> nextList = new ArrayList<>();
Zoom zoom = map.createZoom(linfo.getLevel(), linfo.getBits());
+ //%%%mbs see also MapSplitter.split()
+ // method 1: true at levels > 0, depends on --order-by for level 0
+ boolean splitPolygonsIntoArea = linfo.getLevel() != 0 ? true : orderByDecreasingArea;
+ // method 2: depends on --order-by for all levels
+ //boolean splitPolygonsIntoArea = orderByDecreasingArea;
for (SourceSubdiv srcDivPair : srcList) {
MapSplitter splitter = new MapSplitter(srcDivPair.getSource(), zoom);
- MapArea[] areas = splitter.split(orderByDecreasingArea);
+ MapArea[] areas = splitter.split(splitPolygonsIntoArea);
log.info("Map region", srcDivPair.getSource().getBounds(), "split into", areas.length, "areas at resolution", zoom.getResolution());
for (MapArea area : areas) {
Index: src/uk/me/parabola/mkgmap/build/MapSplitter.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapSplitter.java (revision 4687)
+++ src/uk/me/parabola/mkgmap/build/MapSplitter.java (working copy)
@@ -91,16 +91,20 @@
*
* This routine is not called recursively.
*
- * @param orderByDecreasingArea aligns subareas as powerOf2 and splits polygons into the subareas.
+ * @param splitPolygonsIntoArea aligns subareas as powerOf2 and splits polygons into the subareas.
* @return An array of map areas, each of which is within the size limit
* and the limit on the number of features.
*/
- public MapArea[] split(boolean orderByDecreasingArea) {
+ public MapArea[] split(boolean splitPolygonsIntoArea) {
log.debug("orig area", mapSource.getBounds());
- MapArea ma = initialArea(mapSource, orderByDecreasingArea);
+ MapArea ma = initialArea(mapSource, splitPolygonsIntoArea);
MapArea[] origArea = {ma};
- MapArea[] areas = splitMaxSize(ma);
+ //%%%mbs see also MapBuilder.makeMapAreas()
+ // method 1: true so subdivisions exactly abut
+ MapArea[] areas = splitMaxSize(ma, true);
+ // method 2: depends on incoming param
+ //MapArea[] areas = splitMaxSize(ma, splitPolygonsIntoArea);
if (areas == null) {
log.warn("initial split returned null for", ma);
return origArea;
@@ -209,9 +213,10 @@
* If the area is already small enough then it will be returned unchanged.
*
* @param mapArea The area that needs to be split down.
+ * @param splitPolygonsIntoArea If true, don't expand subDiv due to oversize elements
* @return An array of map areas. Each will be below the max size.
*/
- private MapArea[] splitMaxSize(MapArea mapArea) {
+ private MapArea[] splitMaxSize(MapArea mapArea, boolean splitPolygonsIntoArea) {
/**
* mapArea.getBounds() comes from the original map source or parent/split MapArea.
* mapArea.getFullBounds() is calculated from elements added to the MapArea.
@@ -223,9 +228,16 @@
* Some map sources might not set getBounds().
* If there are no elements, getFullBounds isEmpty.
*/
- Area bounds = mapArea.getBounds();
- if (bounds.isEmpty()) // ??? think this func is wrong for single point/horiz/vert/line
- bounds = mapArea.getFullBounds();
+ Area bounds;
+ if (splitPolygonsIntoArea) { // splitting based on parent/map size
+ bounds = mapArea.getBounds();
+ if (bounds.isEmpty()) // ??? think this func is wrong for single point/horiz/vert/line
+ bounds = mapArea.getFullBounds();
+ } else { // use bounds with any expansion due to oversize elements allowed into subdivisions
+ bounds = mapArea.getFullBounds();
+ if (bounds.isEmpty())
+ bounds = mapArea.getBounds();
+ }
if (bounds.isEmpty())
return null;
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
