Hi Gerd
I've written some new code for splitting polygons in an efficient
manner. The main interface takes a shape and line of latitude or
longitude and returns 2 lists of shapes on either side of the line.
There is also a function to clip to rectangle.
I've put the code in util/ShapeSplitter but it could go elsewhere if
you prefer.
So far I've only converted build/MapArea to use it, but I think it can
be used throughout eventually. For the moment I've commented out the
old code in MapArea, but this can be deleted in a while.
Regards
Ticker
Index: src/uk/me/parabola/mkgmap/build/MapArea.java
===================================================================
--- src/uk/me/parabola/mkgmap/build/MapArea.java (revision 3742)
+++ src/uk/me/parabola/mkgmap/build/MapArea.java (working copy)
@@ -23,7 +23,8 @@
import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import uk.me.parabola.imgfmt.Utils;
-import uk.me.parabola.util.Java2DConverter;
+// import uk.me.parabola.util.Java2DConverter;
+import uk.me.parabola.util.ShapeSplitter;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.trergn.Overview;
@@ -658,10 +659,6 @@
/**
* Spit the polygon into areas
*
- * Using .intersect() here is expensive. The code should be changed to
- * use a simple rectangle clipping algorithm as in, say,
- * util/ShapeSplitter.java
- *
* @param areas The available areas to choose from.
* @param e The map element.
* @param used flag vector to say area has been added to.
@@ -668,6 +665,11 @@
*/
private void splitIntoAreas(MapArea[] areas, MapShape e, boolean[] used)
{
+ if (areas.length == 1) { // this happens quite a lot
+ used[0] = true;
+ areas[0].addShape(e);
+ return;
+ }
// quick check if bbox of shape lies fully inside one of the areas
Area shapeBounds = e.getBounds();
@@ -675,10 +677,19 @@
// tricky problems as it might not really be fully within the area.
// so: pretend the shape is a touch bigger. Will get the optimisation most of the time
// and in the boundary cases will fall into the precise code.
- shapeBounds = new Area(shapeBounds.getMinLat()-2,
- shapeBounds.getMinLong()-2,
- shapeBounds.getMaxLat()+2,
- shapeBounds.getMaxLong()+2);
+ int xtra = 2;
+ // However, if the shape is significantly larger than the error margin (ie most of it
+ // should be in this area) I don't see any problem in letting it expand a little bit out
+ // of the area.
+ // This avoids very small polygons being left in the adjacent areas, which ShapeMergeFilter
+ // notices with an debug message and then output filters probably chuck away.
+ if (Math.min(shapeBounds.getWidth(), shapeBounds.getHeight()) > 8)
+ xtra = -2; // pretend shape is smaller
+
+ shapeBounds = new Area(shapeBounds.getMinLat()-xtra,
+ shapeBounds.getMinLong()-xtra,
+ shapeBounds.getMaxLat()+xtra,
+ shapeBounds.getMaxLong()+xtra);
for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) {
if (areas[areaIndex].getBounds().contains(shapeBounds)) {
used[areaIndex] = true;
@@ -688,6 +699,7 @@
}
// Shape crosses area(s), we have to split it
+/* old, redundant code
// Convert to a awt area
List<Coord> coords = e.getPoints();
java.awt.geom.Area area = Java2DConverter.createArea(coords);
@@ -698,14 +710,54 @@
Coord co = coords.get(i);
shapeHashMap.put(Utils.coord2Long(co), co);
}
+*/
if (areasHashMap == null)
areasHashMap = new Long2ObjectOpenHashMap<>();
+ if (areas.length == 2) { // just divide along the line between the two areas
+ int dividingLine = 0;
+ boolean isLongitude = false;
+ boolean commonLine = true;
+ if (areas[0].getBounds().getMaxLat() == areas[1].getBounds().getMinLat()) {
+ dividingLine = areas[0].getBounds().getMaxLat();
+ isLongitude = false;
+ } else if (areas[0].getBounds().getMaxLong() == areas[1].getBounds().getMinLong()) {
+ dividingLine = areas[0].getBounds().getMaxLong();
+ isLongitude = true;
+ } else {
+ commonLine = false;
+ log.warn("Split into 2 expects shared edge between the areas");
+ }
+ if (commonLine) {
+ List<List<Coord>> lessList = new ArrayList<>(), moreList = new ArrayList<>();
+ ShapeSplitter.splitShape(e.getPoints(), dividingLine << Coord.DELTA_SHIFT, isLongitude, lessList, moreList, areasHashMap);
+ for (List<Coord> subShape : lessList) {
+ MapShape s = e.copy();
+ s.setPoints(subShape);
+ s.setClipped(true);
+ areas[0].addShape(s);
+ used[0] = true;
+ }
+ for (List<Coord> subShape : moreList) {
+ MapShape s = e.copy();
+ s.setPoints(subShape);
+ s.setClipped(true);
+ areas[1].addShape(s);
+ used[1] = true;
+ }
+ return;
+ }
+ }
+
for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) {
+/* old, redundant code
java.awt.geom.Area clipper = Java2DConverter.createBoundsArea(areas[areaIndex].getBounds());
clipper.intersect(area);
List<List<Coord>> subShapePoints = Java2DConverter.areaToShapes(clipper);
+*/
+ List<List<Coord>> subShapePoints = ShapeSplitter.clipToBounds(e.getPoints(), areas[areaIndex].getBounds(), areasHashMap);
for (List<Coord> subShape : subShapePoints) {
+/* old, redundant code
// Use original or share newly created coords on clipped edge.
// NB: .intersect()/areaToShapes can output flattened shapes,
// normally triangles, in any orientation; check we haven't got one by calc area.
@@ -734,6 +786,12 @@
areasHashMap.put(hashVal, co);
}
}
+ if (signedAreaSize == 0) {
+ log.warn("splitIntoAreas creates zero area shape. id", e.getOsmid(),
+ "type", uk.me.parabola.mkgmap.reader.osm.GType.formatType(e.getType()), subSize,
+ "points, at", subShape.get(0).toOSMURL());
+ continue;
+ }
if (Math.abs(signedAreaSize) < ShapeMergeFilter.SINGLE_POINT_AREA
&& areas[areaIndex].areaResolution != 24) {
if (log.isInfoEnabled()) {
@@ -743,13 +801,7 @@
}
continue;
}
-
- if (signedAreaSize == 0) {
- log.warn("splitIntoAreas creates single point shape. id", e.getOsmid(),
- "type", uk.me.parabola.mkgmap.reader.osm.GType.formatType(e.getType()), subSize,
- "points, at", subShape.get(0).toOSMURL());
- continue;
- }
+*/
MapShape s = e.copy();
s.setPoints(subShape);
s.setClipped(true);
@@ -759,7 +811,6 @@
}
}
-
/**
* @return true if this area contains any data
*/
Index: src/uk/me/parabola/mkgmap/filters/ShapeMergeFilter.java
===================================================================
--- src/uk/me/parabola/mkgmap/filters/ShapeMergeFilter.java (revision 3742)
+++ src/uk/me/parabola/mkgmap/filters/ShapeMergeFilter.java (working copy)
@@ -61,7 +61,8 @@
count++;
if (shape.getPoints().get(0) != shape.getPoints().get(shape.getPoints().size()-1)){
// should not happen here
- log.error("shape is not closed with identical points", shape.getOsmid());
+ log.error("shape is not closed with identical points", shape.getOsmid(),
+ shape.getPoints().get(0).toOSMURL());
mergedShapes.add(shape);
continue;
}
@@ -73,7 +74,8 @@
log.error("ignoring shape with id", sh.id, "and type",
GType.formatType(shape.getType()), "at resolution", resolution + ", it",
(shape.wasClipped() ? "was clipped to" : "has"),
- shape.getPoints().size(), "points and has an empty area ");
+ shape.getPoints().size(), "points and has an empty area",
+ shape.getPoints().get(0).toOSMURL());
continue;
}
if (sameTypeList.isEmpty()){
Index: src/uk/me/parabola/util/ShapeSplitter.java
===================================================================
--- src/uk/me/parabola/util/ShapeSplitter.java (revision 3742)
+++ src/uk/me/parabola/util/ShapeSplitter.java (working copy)
@@ -18,6 +18,14 @@
import java.awt.geom.Rectangle2D;
import java.util.Arrays;
+// RWB new bits
+import java.util.ArrayList;
+import java.util.List;
+import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
+import uk.me.parabola.imgfmt.Utils;
+import uk.me.parabola.imgfmt.app.Area;
+import uk.me.parabola.imgfmt.app.Coord;
+
import uk.me.parabola.log.Logger;
public class ShapeSplitter {
@@ -269,4 +277,347 @@
return pointsToPath2D(outputList, countVals);
}
-}
+/* Dec16/Jan17. Ticker Berkin. New implementation for splitting shapes.
+
+Eventually can be used instead of some of the above and maybe in following code:
+
+done mkgmap/build/MapArea.java
+ mkgmap/filters/PolygonSplitterBase.java
+ mkgmap/filters/ShapeMergeFilter.java
+ mkgmap/general/AreaClipper.java
+ mkgmap/general/PolygonClipper.java
+ mkgmap/reader/osm/MultiPolygonRelation.java
+ mkgmap/reader/osm/SeaGenerator.java
+ mkgmap/reader/osm/boundary/BoundaryConverter.java
+ mkgmap/reader/osm/boundary/BoundaryCoverageUtil.java
+ mkgmap/reader/osm/boundary/BoundaryDiff.java
+ mkgmap/reader/osm/boundary/BoundaryElement.java
+ mkgmap/reader/osm/boundary/BoundaryFile2Gpx.java
+ mkgmap/reader/osm/boundary/BoundaryQuadTree.java
+ mkgmap/reader/osm/boundary/BoundaryRelation.java
+ mkgmap/reader/osm/boundary/BoundarySaver.java
+ mkgmap/reader/osm/boundary/BoundaryUtil.java
+ mkgmap/sea/optional/PrecompSeaGenerator.java
+ mkgmap/sea/optional/PrecompSeaMerger.java
+ util/ElementQuadTreeNode.java
+ util/Java2DConverter.java
+ util/QuadTreeNode.java
+*/
+
+ /**
+ * closes a shape and appends to list.
+ *
+ * If the shape starts and ends at the same point on the dividing line then
+ * there is no need to close it. Also check for and chuck a spike, which happens
+ * if there is a single point just across the dividing line and the two intersecting
+ * points ended up being the same.
+ *
+ * @param points the shape to process.
+ * @param origList list of shapes to which we append new shapes.
+ */
+ private static void closeAppend(List<Coord> points, List<List<Coord>> origList, boolean onDividingLine) {
+ Coord firstCoord = points.get(0);
+ int lastPointInx = points.size()-1;
+ if (firstCoord.highPrecEquals(points.get(lastPointInx))) { // start and end at same point on line
+ if (lastPointInx == 2) // just a single point across the line
+ return;
+ // There should be no need to close the line, but am finding, for shapes that never crossed the
+ // dividing line, quite a few that, after splitShapes has rotating the shape by 1, have first and last
+ // points highPrecEquals but they are different objects.
+ // This means that the original first and last were the same object, but the second and last were highPrecEquals!
+ // If left like this, it might be flagged by ShapeMergeFilter.
+ // NB: if no coordPool, likely to be different closing object anyway
+ if (firstCoord != points.get(lastPointInx)) {
+ if (onDividingLine)
+ log.error("high prec/diff obj", firstCoord, lastPointInx, onDividingLine, firstCoord.toOSMURL());
+ else
+ points.set(lastPointInx, firstCoord); // quietly replace with first point
+ }
+ } else
+ points.add(firstCoord); // close it
+ origList.add(points);
+ } // closeAppend
+
+ /**
+ * Service routine for processLineList. Processes a nested list of holes within a shape or
+ * list of shapes within a hole.
+ *
+ * Recurses to check for and handle the opposite of what has been called to process.
+ *
+ * @param startInx starting point in list.
+ * @param endEnclosed point where starting line ends on dividing line.
+ * @param addHolesToThis if not null, then called from a shape and subtract holes from it
+ * otherwise new shapes within a hole.
+ * @param lineInfo array of lines.
+ * @param origList list of shapes to which we append new shapes.
+ */
+ private static int doLines(int startInx, int endEnclosed, MergeCloseHelper addHolesToThis,
+ MergeCloseHelper[] lineInfo, List<List<Coord>> origList) {
+ int inx = startInx;
+ while (inx < lineInfo.length) {
+ MergeCloseHelper thisLine = lineInfo[inx];
+ if (thisLine.highPoint > endEnclosed) // only do enclosed items
+ break;
+ // process any enclosed lines
+ inx = doLines(inx+1, thisLine.highPoint, addHolesToThis == null ? thisLine : null, lineInfo, origList);
+ if (addHolesToThis == null) // handling list of shapes
+ closeAppend(thisLine.points, origList, true);
+ else // handling list of holes
+ addHolesToThis.addHole(thisLine);
+ }
+ return inx;
+ } // doLines
+
+ /**
+ * Service routine for splitShape. Takes list of lines and appends distinct shapes
+ * @param newList list of lines that start and end on the dividing line (or orig startPoint)
+ * @param origList list of shapes to which we append new shapes formed from above
+ * @param isLongitude true if dividing on a line of longitude, false if latitude
+ */
+ private static void processLineList(List<List<Coord>> newList, List<List<Coord>> origList, boolean isLongitude) {
+ if (origList == null) // never wanted this side
+ return;
+ List<Coord> firstPoly = newList.get(0);
+ if (newList.size() == 1) { // single shape that never crossed line
+ if (!firstPoly.isEmpty()) // all on this side
+ closeAppend(firstPoly, origList, false);
+ return;
+ }
+ // look at last elem in list of lists
+ List<Coord> lastPoly = newList.get(newList.size()-1);
+ if (lastPoly.isEmpty()) // will be empty if did not return to this side
+ newList.remove(newList.size()-1);
+ else { // ended up on this side and must have crossed the line
+ // so first points are a continuation of last
+ lastPoly.addAll(firstPoly);
+ newList.remove(0);
+ firstPoly = newList.get(0);
+ }
+ if (newList.size() == 1) { // simple poly that crossed once and back
+ closeAppend(firstPoly, origList, true);
+ return;
+ }
+ // Above were the simple cases - probably 99% of calls.
+
+ // Now imagine something like a snake, with a coiled bit, zig-zag bit and
+ // a flat area that has been flash shape hacked out of it. Then cut a line
+ // through these complex shapes and now need to describe the shapes remaining
+ // on one side of the cut. I think the following does this!
+ // splitShape has generated a list of lines that start and end on the dividing line.
+ // These lines don't cross. Order them by their lowest point on the divider, but note which
+ // direction they go. The first (and last) line must define a shape. Starting with this
+ // shape; the next line up, if it is within this shape, must define a hole and
+ // so is added to the list of points for the shape. For the hole, recurse to
+ // handle any shapes enclosed. Repeat until we reach the end of the enclosing
+ // space.
+
+ final int numLines = newList.size();
+ // make ordered list of more info about the lines that start/end on the dividing line
+ MergeCloseHelper[] lineInfo = new MergeCloseHelper[numLines];
+ for (int inx = 0; inx < numLines; ++inx)
+ lineInfo[inx] = new MergeCloseHelper(newList.get(inx), isLongitude);
+ Arrays.sort(lineInfo);
+
+ log.debug("complex ShapeSplit", numLines, "at", firstPoly.get(0).toOSMURL());
+ for (MergeCloseHelper el : lineInfo)
+ log.debug(el.lowPoint, el.highPoint, el.direction);
+
+ int dummy = doLines(0, Integer.MAX_VALUE, null, lineInfo, origList);
+ assert dummy == lineInfo.length;
+ } // processLineList
+
+
+ /**
+ * Helper class for splitShape. Holds information about line.
+ * Sorts array of itself according to lowest point on dividing line.
+ */
+ private static class MergeCloseHelper implements Comparable<MergeCloseHelper> {
+
+ List<Coord> points;
+ int direction;
+ int lowPoint, highPoint;
+
+ MergeCloseHelper(List<Coord> points, boolean isLongitude) {
+ this.points = points;
+ Coord aCoord = points.get(0);
+ int firstPoint = isLongitude ? aCoord.getHighPrecLat() : aCoord.getHighPrecLon();
+ aCoord = points.get(points.size()-1);
+ int lastPoint = isLongitude ? aCoord.getHighPrecLat() : aCoord.getHighPrecLon();
+ this.direction = Integer.signum(lastPoint - firstPoint);
+ if (this.direction > 0) {
+ this.lowPoint = firstPoint;
+ this.highPoint = lastPoint;
+ } else {
+ this.lowPoint = lastPoint;
+ this.highPoint = firstPoint;
+ }
+ } // MergeCloseHelper
+
+ public int compareTo(MergeCloseHelper other) {
+ int cmp = this.lowPoint - other.lowPoint;
+ if (cmp != 0)
+ return cmp;
+ // for same lowPoint, sort highPoint other way around to enclose as much as possible
+ cmp = other.highPoint - this.highPoint;
+ if (cmp != 0)
+ return cmp;
+ // pathalogical case where when have same start & end
+ log.error("Lines hit divider at same points", this.lowPoint, this.highPoint, this.points.get(0).toOSMURL());
+ // %%% should return one with larger area as being less,
+ // but I don't think anyone will define an area like this and expect it to work
+ // so, for moment:
+ return this.direction - other.direction;
+ } // compareTo
+
+ void addHole(MergeCloseHelper other) {
+ if (other.direction == 0 && other.points.size() == 3)
+ return; // spike into this area. cf. closeAppend()
+ // shapes must have opposite directions.
+ if (this.direction == 0 && other.direction == 0)
+ log.error("Direction of shape and hole indeterminate", this.points.get(0).toOSMURL());
+ else if (this.direction != 0 && other.direction != 0 && this.direction == other.direction)
+ log.error("Direction of shape and hole conflict", this.points.get(0).toOSMURL());
+ else if (this.direction < 0 || other.direction > 0) {
+ this.points.addAll(other.points);
+ if (this.direction == 0)
+ this.direction = -1;
+ } else { // add at start
+ other.points.addAll(this.points);
+ this.points = other.points;
+ if (this.direction == 0)
+ this.direction = +1;
+ }
+ } // addHole
+
+ } // MergeCloseHelper
+
+ /**
+ * split a shape with a line
+ * @param coords the shape. Must be closed.
+ * @param dividingLine the line in high precision.
+ * @param isLongitude true if above is line of longitude, false if latitude.
+ * @param lessList list of shapes to which we append new shapes on lower/left side of line.
+ * @param moreList list of shapes to which we append new shapes on upper/right side of line.
+ * @param coordPool if not null, hashmap for created coordinates. Will all be on the line.
+ */
+ public static void splitShape(List<Coord> coords, int dividingLine, boolean isLongitude,
+ List<List<Coord>> lessList, List<List<Coord>> moreList,
+ Long2ObjectOpenHashMap<Coord> coordPool) {
+
+ List<List<Coord>> newLess = null, newMore = null;
+ List<Coord> lessPoly = null, morePoly = null;
+ if (lessList != null) {
+ newLess = new ArrayList<>();
+ lessPoly = new ArrayList<>();
+ newLess.add(lessPoly);
+ }
+ if (moreList != null) {
+ newMore = new ArrayList<>();
+ morePoly = new ArrayList<>();
+ newMore.add(morePoly);
+ }
+ Coord trailCoord = null;
+ int trailPosn = 0, trailRel = 0;
+
+ for (Coord leadCoord : coords) {
+ int leadPosn = isLongitude ? leadCoord.getHighPrecLon() : leadCoord.getHighPrecLat();
+ int leadRel = Integer.signum(leadPosn - dividingLine);
+ if (trailCoord != null) { // use first point as trailing (poly is closed)
+
+ Coord lineCoord = null;
+ if (trailRel == 0) // trailing point on line
+ lineCoord = trailCoord;
+ else if (leadRel == 0) // leading point on line
+ lineCoord = leadCoord;
+ else if (trailRel != leadRel) { // crosses line; make intersecting coord
+ int newOther = isLongitude ? trailCoord.getHighPrecLat() : trailCoord.getHighPrecLon();
+ int leadOther = isLongitude ? leadCoord.getHighPrecLat() : leadCoord.getHighPrecLon();
+ if (newOther != leadOther)
+ newOther += (dividingLine - trailPosn) * (leadOther - newOther) / (leadPosn - trailPosn);
+ lineCoord = Coord.makeHighPrecCoord(isLongitude ? newOther : dividingLine, isLongitude ? dividingLine : newOther);
+ }
+ if (lineCoord != null && coordPool != null) {
+ // Add new coords to pool. Also add existing ones if on the dividing line because there is slight
+ // chance that the intersection will coincide with an existing point and ShapeMergeFilter expects
+ // the opening/closing point to be the same object. If we see the original point first,
+ // all is good, but if other way around, it will replace an original point with the created one.
+ long hashVal = Utils.coord2Long(lineCoord);
+ Coord replCoord = coordPool.get(hashVal);
+ if (replCoord == null)
+ coordPool.put(hashVal, lineCoord);
+ else
+ lineCoord = replCoord;
+ }
+
+ if (lessList != null) {
+ if (leadRel < 0) { // this point required
+ if (trailRel >= 0) // previous not on this side, add line point
+ lessPoly.add(lineCoord);
+ lessPoly.add(leadCoord);
+ } else if (trailRel < 0) { // if this not reqd and prev was, add line point and start new shape
+ lessPoly.add(lineCoord);
+ lessPoly = new ArrayList<>();
+ newLess.add(lessPoly);
+ }
+ }
+
+ // identical to above except other way around
+ if (moreList != null) {
+ if (leadRel > 0) { // this point required
+ if (trailRel <= 0) // previous not on this side, add line point
+ morePoly.add(lineCoord);
+ morePoly.add(leadCoord);
+ } else if (trailRel > 0) { // if this not reqd and prev was, add line point and start new shape
+ morePoly.add(lineCoord);
+ morePoly = new ArrayList<>();
+ newMore.add(morePoly);
+ }
+ }
+
+ } // if not first Coord
+ trailCoord = leadCoord;
+ trailPosn = leadPosn;
+ trailRel = leadRel;
+ } // for leadCoord
+ processLineList(newLess, lessList, isLongitude);
+ processLineList(newMore, moreList, isLongitude);
+ } // splitShape
+
+
+ /**
+ * clip a shape with a rectangle
+ *
+ * Use above splitShape for each side; just keeping the 1/2 we want each time.
+ *
+ * @param coords the shape.
+ * @param bounds the clipping area.
+ * @param coordPool if not null, hashmap for created coordinates. Will all be on the edge.
+ * @return list of shapes.
+ */
+ public static List<List<Coord>> clipToBounds(List<Coord> coords, Area bounds, Long2ObjectOpenHashMap<Coord> coordPool) {
+ List<List<Coord>> newListA = new ArrayList<>();
+ int dividingLine = bounds.getMinLat() << Coord.DELTA_SHIFT;
+ splitShape(coords, dividingLine, false, null, newListA, coordPool);
+ if (newListA.isEmpty())
+ return newListA;
+ List<List<Coord>> newListB = new ArrayList<>();
+ dividingLine = bounds.getMinLong() << Coord.DELTA_SHIFT;
+ for (List<Coord> aShape : newListA)
+ splitShape(aShape, dividingLine, true, null, newListB, coordPool);
+ if (newListB.isEmpty())
+ return newListB;
+ newListA.clear();
+ dividingLine = bounds.getMaxLat() << Coord.DELTA_SHIFT;
+ for (List<Coord> aShape : newListB)
+ splitShape(aShape, dividingLine, false, newListA, null, coordPool);
+ if (newListA.isEmpty())
+ return newListA;
+ newListB.clear();
+ dividingLine = bounds.getMaxLong() << Coord.DELTA_SHIFT;
+ for (List<Coord> aShape : newListA)
+ splitShape(aShape, dividingLine, true, newListB, null, coordPool);
+ return newListB;
+ } // clipToBounds
+
+
+} // ShapeSplitter
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
