Hi
I have a patch that outputs polygons into the map file in decreasing
size order, so that, assuming equal _drawOrder, the Garmin device
renders small details over larger areas, much like how they appear on
OpenStreetMap.org.
As well as sorting by size, polygons that straddle subDivisions
are cut up and placed into their correct subdivision, rather than being
put into an arbirary one, which, if it isn't the one in focus, renders
over the focus subdivision.
The original, full, area of polygons is tracked through a
ny cutting and clipping so that relative ordering is correct across
subdivision and map boundaries.
All this is controlled by the option --order-by-decreasing-area, with a
default of false that leaves the behavior of mkgmap unchanged. A
s such, I think this patch could be applied to the trunk development.
Regards
Ticker Berkin
mk
Index: doc/options.txt
===================================================================
--- doc/options.txt (revision 3695)
+++ doc/options.txt (working copy)
@@ -705,3 +705,8 @@
<p>
;--verbose
: Makes some operations more verbose. Mostly used with --list-styles.
+<p>
+;--order-by-decreasing-area
+: Puts area/polygons into the mapfile in decreasing size so
+that smaller features are rendered over larger ones
+(assuming _drawOrder is equal).
Index: resources/help/en/options
===================================================================
--- resources/help/en/options (revision 3695)
+++ resources/help/en/options (working copy)
@@ -699,3 +699,8 @@
--verbose
Makes some operations more verbose. Mostly used with --list-styles.
+
+--order-by-decreasing-area
+ Puts polygons/areas into the mapfile in decreasing size so that
+ smaller features are rendered over larger ones (assuming _drawOrder
+ is equal)
Index: src/uk/me/parabola/imgfmt/app/Area.java
===================================================================
--- src/uk/me/parabola/imgfmt/app/Area.java (revision 3695)
+++ src/uk/me/parabola/imgfmt/app/Area.java (working copy)
@@ -103,7 +103,20 @@
;
}
- /**
+ /**
+ * Round integer to a power of 2
+ *
+ * @param val The number of be rounded.
+ * @param shift The power of 2.
+ * @return The rounded number (rounds up).
+ */
+ private int roundPof2(int val, int shift) {
+ if (shift <= 0)
+ return val;
+ return (((val >> (shift-1)) + 1) >> 1) << shift;
+ }
+
+ /**
* Split this area up into a number of smaller areas.
*
* @param xsplit The number of pieces to split this area into in the x
@@ -110,33 +123,37 @@
* direction.
* @param ysplit The number of pieces to split this area into in the y
* direction.
+ * @param resolutionShift round to this power of 2.
* @return An area containing xsplit*ysplit areas.
*/
- public Area[] split(int xsplit, int ysplit) {
+ public Area[] split(int xsplit, int ysplit, int resolutionShift) {
Area[] areas = new Area[xsplit * ysplit];
+ int xstart;
+ int xend;
+ int ystart;
+ int yend;
- int xsize = getWidth() / xsplit;
- int ysize = getHeight() / ysplit;
-
- int xextra = getWidth() - xsize * xsplit;
- int yextra = getHeight() - ysize * ysplit;
-
+ xstart = minLong;
for (int x = 0; x < xsplit; x++) {
- int xstart = minLong + x * xsize;
- int xend = xstart + xsize;
if (x == xsplit - 1)
- xend += xextra;
-
+ xend = maxLong;
+ else
+ xend = roundPof2(xstart + (maxLong - xstart) / (xsplit - x),
+ resolutionShift);
+ ystart = minLat;
for (int y = 0; y < ysplit; y++) {
- int ystart = minLat + y * ysize;
- int yend = ystart + ysize;
if (y == ysplit - 1)
- yend += yextra;
+ yend = maxLat;
+ else
+ yend = roundPof2(ystart + (maxLat - ystart) / (ysplit - y),
+ resolutionShift);
Area a = new Area(ystart, xstart, yend, xend);
log.debug(x, y, a);
areas[x * ysplit + y] = a;
+ ystart = yend;
}
+ xstart = xend;
}
assert areas.length == xsplit * ysplit;
Index: src/uk/me/parabola/mkgmap/build/MapArea.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapArea.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/build/MapArea.java (working copy)
@@ -180,10 +180,12 @@
* @param ny The number of pieces in the y direction.
* @param resolution The resolution of the level.
* @param bounds the bounding box that is used to create the areas.
+ * @param orderByDecreasingArea aligns subareas as powerOf2 and splits polygons into the subareas.
* @return An array of the new MapArea's.
*/
- public MapArea[] split(int nx, int ny, int resolution, Area bounds) {
- Area[] areas = bounds.split(nx, ny);
+ public MapArea[] split(int nx, int ny, int resolution, Area bounds, boolean orderByDecreasingArea) {
+ int resolutionShift = orderByDecreasingArea ? (24 - resolution) : 0;
+ Area[] areas = bounds.split(nx, ny, resolutionShift);
MapArea[] mapAreas = new MapArea[nx * ny];
log.info("Splitting area " + bounds + " into " + nx + "x" + ny + " pieces at resolution " + resolution);
boolean useNormalSplit = true;
@@ -238,6 +240,10 @@
for (MapShape e : this.shapes) {
if (useNormalSplit){
+ if (orderByDecreasingArea) {
+ splitIntoAreas(mapAreas, e, used);
+ continue;
+ }
areaIndex = pickArea(mapAreas, e, xbase30, ybase30, nx, ny, dx30, dy30);
if (e.getBounds().getHeight() > maxHeight || e.getBounds().getWidth() > maxWidth){
MapArea largeObjectArea = new MapArea(e.getBounds(), resolution);
@@ -610,6 +616,32 @@
}
/**
+ * Spit the polygon into areas
+ *
+ * @param areas The available areas to choose from.
+ * @param e The map element.
+ * @param used flag vector to say area has been added to.
+ */
+ private void splitIntoAreas(MapArea[] areas, MapShape e, boolean[] used)
+ {
+ // Convert to a awt area
+ java.awt.geom.Area area = uk.me.parabola.util.Java2DConverter.createArea(e.getPoints());
+
+ for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) {
+ java.awt.geom.Area clipper = uk.me.parabola.util.Java2DConverter.createBoundsArea(areas[areaIndex].getBounds());
+ clipper.intersect(area);
+ List<List<Coord>> subShapePoints = uk.me.parabola.util.Java2DConverter.areaToShapes(clipper);
+ for (List<Coord> subShape : subShapePoints) {
+ used[areaIndex] = true;
+ MapShape s = e.copy();
+ s.setPoints(subShape);
+ areas[areaIndex].addShape(s);
+ }
+ }
+ }
+
+
+ /**
* @return true if this area contains any data
*/
public boolean hasData() {
Index: src/uk/me/parabola/mkgmap/build/MapBuilder.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapBuilder.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/build/MapBuilder.java (working copy)
@@ -147,6 +147,8 @@
private String licenseFileName;
+ private boolean orderByDecreasingArea;
+
public MapBuilder() {
regionName = null;
locationAutofill = Collections.emptySet();
@@ -188,6 +190,7 @@
driveOnLeft = true;
if ("right".equals(driveOn))
driveOnLeft = false;
+ orderByDecreasingArea = props.getProperty("order-by-decreasing-area", false);
}
/**
@@ -685,7 +688,7 @@
for (SourceSubdiv srcDivPair : srcList) {
MapSplitter splitter = new MapSplitter(srcDivPair.getSource(), zoom);
- MapArea[] areas = splitter.split();
+ MapArea[] areas = splitter.split(orderByDecreasingArea);
log.info("Map region", srcDivPair.getSource().getBounds(), "split into", areas.length, "areas at resolution", zoom.getResolution());
for (MapArea area : areas) {
@@ -1115,11 +1118,20 @@
config.setRoutable(doRoads);
if (mergeShapes){
- ShapeMergeFilter shapeMergeFilter = new ShapeMergeFilter(res);
+ ShapeMergeFilter shapeMergeFilter = new ShapeMergeFilter(res, orderByDecreasingArea);
List<MapShape> mergedShapes = shapeMergeFilter.merge(shapes);
shapes = mergedShapes;
}
+ if (orderByDecreasingArea && shapes.size() > 1) {
+ // sort so that the shape with the largest area is processed first
+ Collections.sort(shapes, new java.util.Comparator<MapShape>() {
+ public int compare(MapShape s1, MapShape s2) {
+ return Long.compare(Math.abs(s2.getFullArea()), Math.abs(s1.getFullArea()));
+ }
+ });
+ }
+
preserveHorizontalAndVerticalLines(res, shapes);
LayerFilterChain filters = new LayerFilterChain(config);
Index: src/uk/me/parabola/mkgmap/build/MapSplitter.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapSplitter.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/build/MapSplitter.java (working copy)
@@ -91,20 +91,21 @@
*
* This routine is not called recursively.
*
+ * @param orderByDecreasingArea 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() {
+ public MapArea[] split(boolean orderByDecreasingArea) {
log.debug("orig area", mapSource.getBounds());
MapArea ma = initialArea(mapSource);
- MapArea[] areas = splitMaxSize(ma);
+ MapArea[] areas = splitMaxSize(ma, orderByDecreasingArea);
// Now step through each area and see if any have too many map features
// in them. For those that do, we further split them. This is done
// recursively until everything fits.
List<MapArea> alist = new ArrayList<>();
- addAreasToList(areas, alist, 0);
+ addAreasToList(areas, alist, 0, orderByDecreasingArea);
MapArea[] results = new MapArea[alist.size()];
return alist.toArray(results);
@@ -118,8 +119,9 @@
* @param areas The areas to add to the list (and possibly split up).
* @param alist The list that will finally contain the complete list of
* map areas.
+ * @param orderByDecreasingArea aligns subareas as powerOf2 and splits polygons into the subareas.
*/
- private void addAreasToList(MapArea[] areas, List<MapArea> alist, int depth) {
+ private void addAreasToList(MapArea[] areas, List<MapArea> alist, int depth, boolean orderByDecreasingArea) {
int res = zoom.getResolution();
for (MapArea area : areas) {
Area bounds = area.getBounds();
@@ -164,10 +166,10 @@
log.debug("splitting area", area);
MapArea[] sublist;
if(bounds.getWidth() > bounds.getHeight())
- sublist = area.split(2, 1, res, bounds);
+ sublist = area.split(2, 1, res, bounds, orderByDecreasingArea);
else
- sublist = area.split(1, 2, res, bounds);
- addAreasToList(sublist, alist, depth + 1);
+ sublist = area.split(1, 2, res, bounds, orderByDecreasingArea);
+ addAreasToList(sublist, alist, depth + 1, orderByDecreasingArea);
continue;
} else {
log.error("Area too small to split at " + area.getBounds().getCenter().toOSMURL() + " (reduce the density of points, length of lines, etc.)");
@@ -192,9 +194,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 orderByDecreasingArea aligns subareas as powerOf2 and splits polygons into the subareas.
* @return An array of map areas. Each will be below the max size.
*/
- private MapArea[] splitMaxSize(MapArea mapArea) {
+ private MapArea[] splitMaxSize(MapArea mapArea, boolean orderByDecreasingArea) {
Area bounds = mapArea.getFullBounds();
int shift = zoom.getShiftValue();
@@ -214,7 +217,7 @@
if (height > MAX_DIVISION_SIZE)
ysplit = height / MAX_DIVISION_SIZE + 1;
- return mapArea.split(xsplit, ysplit, zoom.getResolution(), bounds);
+ return mapArea.split(xsplit, ysplit, zoom.getResolution(), bounds, orderByDecreasingArea);
}
/**
Index: src/uk/me/parabola/mkgmap/filters/ShapeMergeFilter.java
===================================================================
--- src/uk/me/parabola/mkgmap/filters/ShapeMergeFilter.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/filters/ShapeMergeFilter.java (working copy)
@@ -41,9 +41,11 @@
private static final Logger log = Logger.getLogger(ShapeMergeFilter.class);
private final int resolution;
private final ShapeHelper dupShape = new ShapeHelper(new ArrayList<Coord>(0));
+ private final boolean orderByDecreasingArea;
- public ShapeMergeFilter(int resolution) {
+ public ShapeMergeFilter(int resolution, boolean orderByDecreasingArea) {
this.resolution = resolution;
+ this.orderByDecreasingArea = orderByDecreasingArea;
}
public List<MapShape> merge(List<MapShape> shapes) {
@@ -84,6 +86,9 @@
for (Map<MapShape, List<ShapeHelper>> lowMap : sameTypeList){
boolean added = false;
for (MapShape ms: lowMap.keySet()){
+ if (orderByDecreasingArea && ms.getFullArea() != shape.getFullArea())
+ // must not merge areas unless derived from same thing
+ continue;
// we do not use isSimilar() here, as it compares minRes and maxRes as well
String s1 = ms.getName();
String s2 = shape.getName();
Index: src/uk/me/parabola/mkgmap/general/MapShape.java
===================================================================
--- src/uk/me/parabola/mkgmap/general/MapShape.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/general/MapShape.java (working copy)
@@ -23,6 +23,7 @@
*/
public class MapShape extends MapLine {// So top code can link objects from here
private long osmid; //TODO: remove debug aid
+ private long fullArea = Long.MAX_VALUE; // meaning unset
public MapShape() {
osmid = 0;
}
@@ -32,6 +33,7 @@
MapShape(MapShape s) {
super(s);
this.osmid = s.osmid;
+ this.fullArea = s.getFullArea();
}
public MapShape copy() {
@@ -50,4 +52,18 @@
public long getOsmid() {
return osmid;
}
+
+ public void setFullArea(long fullArea) {
+ this.fullArea = fullArea;
+ }
+
+ public long getFullArea() { // this is unadulterated size, +ve if clockwise
+ if (this.fullArea == Long.MAX_VALUE) {
+ java.util.List<uk.me.parabola.imgfmt.app.Coord> points = this.getPoints();
+ if (points.size() >= 4 && points.get(0).highPrecEquals(points.get(points.size()-1)))
+ this.fullArea = uk.me.parabola.mkgmap.filters.ShapeMergeFilter.calcAreaSizeTestVal(points);
+ }
+ return this.fullArea;
+ }
+
}
Index: src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java
===================================================================
--- src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/osmstyle/StyledConverter.java (working copy)
@@ -989,6 +989,7 @@
final MapShape shape = new MapShape(way.getId());
elementSetup(shape, gt, way);
shape.setPoints(way.getPoints());
+ shape.setFullArea(way.getFullArea());
clipper.clipShape(shape, collector);
}
Index: src/uk/me/parabola/mkgmap/osmstyle/function/AreaSizeFunction.java
===================================================================
--- src/uk/me/parabola/mkgmap/osmstyle/function/AreaSizeFunction.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/osmstyle/function/AreaSizeFunction.java (working copy)
@@ -15,6 +15,10 @@
public class AreaSizeFunction extends CachedFunction {
private final DecimalFormat nf = new DecimalFormat("0.0#####################", DecimalFormatSymbols.getInstance(Locale.US));
+ private final boolean orderByDecreasingArea = true;
+ // To be totally consistent, ie no possible difference to mkgmap behaviour when --order-by-decreasing-area is not set,
+ // this should be set from the option; however I believe that 'fullArea' is what the user might expect, rather than
+ // various different values for the same original because of clipping and cutting to expose holes.
public AreaSizeFunction() {
super(null);
@@ -27,7 +31,18 @@
if (w.hasEqualEndPoints() == false) {
return "0";
}
- return nf.format(MultiPolygonRelation.calcAreaSize(((Way) el).getPoints()));
+ double areaSize;
+ if (orderByDecreasingArea) {
+ long fullArea = w.getFullArea();
+ if (fullArea == Long.MAX_VALUE)
+ return "0";
+ // convert from high prec to value in map units
+ areaSize = (double)fullArea / (2 * (1<<uk.me.parabola.imgfmt.app.Coord.DELTA_SHIFT) *
+ (1<<uk.me.parabola.imgfmt.app.Coord.DELTA_SHIFT));
+ areaSize = Math.abs(areaSize);
+ } else
+ areaSize = MultiPolygonRelation.calcAreaSize(w.getPoints());
+ return nf.format(areaSize);
}
return null;
}
Index: src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java (working copy)
@@ -846,6 +846,7 @@
int wi = 0;
for (Way w : polygons) {
+ Long fullArea = w.getFullArea(); // trigger setting area before start cutting...
String role = getRole(w);
if ("inner".equals(role)) {
innerPolygons.set(wi);
@@ -1034,6 +1035,7 @@
outmostPolygonProcessing = false;
}
+ Long fullArea = currentPolygon.polygon.getFullArea();
for (Way mpWay : singularOuterPolygons) {
// put the cut out polygons to the
// final way map
@@ -1040,6 +1042,7 @@
if (log.isDebugEnabled())
log.debug(mpWay.getId(),mpWay.toTagString());
+ mpWay.setFullArea(fullArea);
// mark this polygons so that only polygon style rules are applied
mpWay.addTag(STYLE_FILTER_TAG, STYLE_FILTER_POLYGON);
mpWay.addTag(MP_CREATED_TAG, "true");
Index: src/uk/me/parabola/mkgmap/reader/osm/SeaGenerator.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/SeaGenerator.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/reader/osm/SeaGenerator.java (working copy)
@@ -709,6 +709,7 @@
saver.addWay(w);
}
for (Way w : seaWays) {
+ w.setFullArea(Long.MAX_VALUE-1); // sea is BIG
saver.addWay(w);
}
} else {
@@ -718,6 +719,7 @@
// first add the complete bounding box as sea
Way sea = new Way(FakeIdGenerator.makeFakeId(),bounds.toCoords());
sea.addTag("natural", "sea");
+ sea.setFullArea(Long.MAX_VALUE-1); // sea is BIG
for (Way w : landWays) {
saver.addWay(w);
@@ -991,6 +993,7 @@
ne.getLongitude() + 1));
sea.addPoint(sea.getPoints().get(0)); // close shape
sea.addTag("natural", "sea");
+ sea.setFullArea(Long.MAX_VALUE-1); // sea is BIG
log.info("sea: ", sea);
saver.addWay(sea);
Index: src/uk/me/parabola/mkgmap/reader/osm/Way.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/Way.java (revision 3695)
+++ src/uk/me/parabola/mkgmap/reader/osm/Way.java (working copy)
@@ -34,6 +34,7 @@
public class Way extends Element {
private static final Logger log = Logger.getLogger(Way.class);
private final List<Coord> points;
+ private long fullArea = Long.MAX_VALUE; // meaning unset
// This will be set if a way is read from an OSM file and the first node is the same node as the last
// one in the way. This can be set to true even if there are missing nodes and so the nodes that we
@@ -63,6 +64,7 @@
dup.closedInOSM = this.closedInOSM;
dup.complete = this.complete;
dup.isViaWay = this.isViaWay;
+ dup.fullArea = this.getFullArea();
return dup;
}
@@ -252,4 +254,16 @@
public void setViaWay(boolean isViaWay) {
this.isViaWay = isViaWay;
}
+
+ public void setFullArea(long fullArea) {
+ this.fullArea = fullArea;
+ }
+
+ public long getFullArea() { // this is unadulterated size, +ve if clockwise
+ if (this.fullArea == Long.MAX_VALUE && points.size() >= 4 && points.get(0).highPrecEquals(points.get(points.size()-1))) {
+ this.fullArea = uk.me.parabola.mkgmap.filters.ShapeMergeFilter.calcAreaSizeTestVal(points);
+ }
+ return this.fullArea;
+ }
+
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
