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
Index: src/uk/me/parabola/mkgmap/build/MapArea.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapArea.java (revision 4685)
+++ 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 4685)
+++ src/uk/me/parabola/mkgmap/build/MapBuilder.java (working copy)
@@ -803,11 +803,15 @@
List<SourceSubdiv> nextList = new ArrayList<>();
Zoom zoom = map.createZoom(linfo.getLevel(), linfo.getBits());
+ //%%%mbs see also MapSpltter.split()
+ // method 1: true at levels > 0, depends on --order-by for level 9
+ // method 2: depends on --order-by for all levels
+ boolean splitPolygonsIntoArea = /* linfo.getLevel() != 0 ? true : */ 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 4685)
+++ src/uk/me/parabola/mkgmap/build/MapSplitter.java (working copy)
@@ -91,16 +91,19 @@
*
* 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: maybe always be true so that even at level 0, 0x4b polygons don't overlap?
+ // method 2: depends on incoming param
+ MapArea[] areas = splitMaxSize(ma, /* true */ splitPolygonsIntoArea);
if (areas == null) {
log.warn("initial split returned null for", ma);
return origArea;
@@ -209,9 +212,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) { //%%%mbs new param
/**
* mapArea.getBounds() comes from the original map source or parent/split MapArea.
* mapArea.getFullBounds() is calculated from elements added to the MapArea.
@@ -223,9 +227,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
