Hi Gerd
Here it is - changes are:
- Some restructuring with early stopping where possible.
- Merging polygons for POINT IN/ON test so a point on shared boundary
becomes IN rather than ON.
- Not merging polygons when no need.
- Make the function cacheable, so that there is negligible cost to the
second call:
highway=path & is_in(landuse, residential, all)=true [0xAA]
highway=path & is_in(landuse, residential, all)=false [0xBB]
- Improved the layout of documentation in the Style Manual.
- Fixed quite a few problems.
I've left quite a lot of debug in for the moment, I think there will
still be work to do.
It gives correct answers to 'point-on.osm'. I haven't worked through is
-in-hook-sample-v3.osm yet because I wanted to get this revision out to
replace faults in the previous versions.
Ticker
On Tue, 2020-02-11 at 15:49 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> whatever you plan to do. I moved the code to the lib because it is easier to
> write a unit test.
> I would not invest much time to avoid a few tests which only happen in very
> rare cases. Makes testing more complicated and code less readable.
>
> Gerd
Index: doc/styles/rules.txt
===================================================================
--- doc/styles/rules.txt (revision 4445)
+++ doc/styles/rules.txt (working copy)
@@ -285,19 +285,22 @@
|is_in(tag,value,method) | x | x | |
+true+ if the element is in polygon(s) having the specified +tag+=+value+ according to the +method+, +false+ otherwise.
The methods available depend on the Style section:
-"points":
+
+* points:
+in+ - the Node is within a polygon.
+in_or_on+ - it is within or on the edge.
+on+ - it is on the edge.
-"lines":
- +all+ - part of the Way is within the polygon(s), none is outside; it might touch an edge.
+
+* lines:
+ +all+ - part of the Way is within the polygon(s), none is outside; it might touch an edge.
+all_in_or_on+ - none is outside. This is useful for the negative - is_in(...,all_in_or_on)=false - for processing a line that is outside the polgon(s).
+on+ - it runs along the edge.
+any+ - part is within.
+any_in_or_on+ - part is within or in the edge.
-"polygons":
+
+* polygons:
+all+ - all of the closed Way is within the polygon(s).
- +any" - some is within.
+ +any+ - some is within.
|====
Index: src/uk/me/parabola/mkgmap/osmstyle/function/IsInFunction.java
===================================================================
--- src/uk/me/parabola/mkgmap/osmstyle/function/IsInFunction.java (revision 4445)
+++ src/uk/me/parabola/mkgmap/osmstyle/function/IsInFunction.java (working copy)
@@ -22,6 +22,7 @@
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
+import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.reader.osm.Element;
import uk.me.parabola.mkgmap.reader.osm.ElementSaver;
import uk.me.parabola.mkgmap.reader.osm.FeatureKind;
@@ -37,7 +38,8 @@
* @author Ticker Berkin
*
*/
-public class IsInFunction extends StyleFunction {
+public class IsInFunction extends CachedFunction { // StyleFunction
+ private static final Logger log = Logger.getLogger(IsInFunction.class);
private enum MethodArg {
@@ -91,10 +93,10 @@
private class CanStopProcessing extends RuntimeException {};
private MethodArg method;
- private boolean hasIn = false;
- private boolean hasOn = false;
- private boolean hasOut = false;
- private ElementQuadTree qt;
+ private boolean hasIn;
+ private boolean hasOn;
+ private boolean hasOut;
+ private ElementQuadTree qt = null;
public IsInFunction() {
super(null);
@@ -102,10 +104,22 @@
// 1: polygon tagName
// 2: value for above tag
// 3: method keyword, see above
+ log.info("isInFunction", System.identityHashCode(this));
}
+ private void resetHasFlags() {
+ // the instance is per unique call in rules, then applied repeatedly to each point/line/polygon
+ hasIn = false;
+ hasOn = false;
+ hasOut = false;
+ }
+
protected String calcImpl(Element el) {
- if (qt == null || qt.isEmpty())
+ log.info("calcImpl", System.identityHashCode(this), kind, params, el);
+ assert qt != null : "invoked the non-augmented instance";
+ resetHasFlags();
+
+ if (qt.isEmpty())
return String.valueOf(false);
try {
switch (kind) {
@@ -120,17 +134,21 @@
break;
}
} catch (CanStopProcessing e) {}
+ log.info("done", hasIn, hasOn, hasOut);
return String.valueOf(mapHasFlagsAnswer());
}
+/* don't have this for CachedFunction
@Override
public String value(Element el) {
return calcImpl(el);
}
-
+*/
+
@Override
public void setParams(List<String> params, FeatureKind kind) {
super.setParams(params, kind);
+ log.info("setParams", System.identityHashCode(this), kind, params);
String methodStr = params.get(2);
boolean knownMethod = false;
List<String> methodsForKind = new ArrayList<>();
@@ -150,22 +168,34 @@
}
private void setIn() {
+ log.info("setIn", hasIn, hasOn, hasOut);
hasIn = true;
- if (method.canStopIn())
+ if (method.canStopIn() || (hasOn && hasOut))
throw new CanStopProcessing();
}
private void setOn() {
+ log.info("setOn", hasIn, hasOn, hasOut);
hasOn = true;
- if (method.canStopOn())
+ if (method.canStopOn() || (hasIn && hasOut))
throw new CanStopProcessing();
}
private void setOut() {
+ log.info("setOut", hasIn, hasOn, hasOut);
hasOut = true;
- if (method.canStopOut())
+ if (method.canStopOut() || (hasIn && hasOn))
throw new CanStopProcessing();
}
+ private void setHasFromFlags(int flags) {
+ if ((flags & IsInUtil.IN) != 0)
+ setIn();
+ if ((flags & IsInUtil.ON) != 0)
+ setOn();
+ if ((flags & IsInUtil.OUT) != 0)
+ setOut();
+ }
+
private boolean mapHasFlagsAnswer() {
switch (method) {
case POINT_IN:
@@ -192,39 +222,67 @@
return false;
}
- private void doPointTest(Node el) {
- //doCommonTest(el);
- Coord c = el.getLocation();
- Area elementBbox = Area.getBBox(Collections.singletonList(c));
- Set<Way> polygons = qt.get(elementBbox).stream().map(e -> (Way) e)
- .collect(Collectors.toCollection(LinkedHashSet::new));
+ private static boolean notInHole(Coord c, List<List<Coord>> holes) {
+ if (holes == null)
+ return true;
+ for (List<Coord> hole : holes)
+ if (IsInUtil.insidePolygon(c, true, hole))
+ return false;
+ return true;
+ }
+
+ private void checkPointInShape(Coord c, List<Coord> shape, List<List<Coord>> holes) {
/*
- We can use the method to control the onBoundary condition of insidePolygon.
-
Because we are processing polygons one-by-one, OUT is only meaningful once we have
checked all the polygons and haven't satisfied IN/ON, so no point is calling setOut()
and it wouldn't stop the processing or effect the answer anyway
*/
- for (Way polygon : polygons) {
- List<Coord> shape = polygon.getPoints();
- switch (method) {
- case POINT_IN:
- if (IsInUtil.insidePolygon(c, false, shape))
+ switch (method) { // Use the method to control the onBoundary condition of insidePolygon.
+ case POINT_IN:
+ if (IsInUtil.insidePolygon(c, false, shape))
+ if (notInHole(c, holes))
setIn();
- break;
- case POINT_IN_OR_ON:
- if (IsInUtil.insidePolygon(c, true, shape))
- setIn(); // don't care about setOn()
- break;
- case POINT_ON:
- if (IsInUtil.insidePolygon(c, true, shape) &&
- !IsInUtil.insidePolygon(c, false, shape))
- setOn(); // don't care about setIn()
- break;
- }
+ else // in hole in this shape, no point in looking at more shapes
+ throw new CanStopProcessing();
+ break;
+ case POINT_IN_OR_ON:
+ if (IsInUtil.insidePolygon(c, true, shape))
+ // no need to check holes for this as didn't need to merge polygons
+ setIn(); // don't care about setOn()
+ break;
+ case POINT_ON:
+ if (IsInUtil.insidePolygon(c, true, shape) &&
+ !IsInUtil.insidePolygon(c, false, shape))
+ // hole checking is a separate pass
+ setOn(); // don't care about setIn()
+ break;
}
}
+ private void doPointTest(Node el) {
+ Coord c = el.getLocation();
+ Area elementBbox = Area.getBBox(Collections.singletonList(c));
+ Set<Way> polygons = qt.get(elementBbox).stream().map(e -> (Way) e)
+ .collect(Collectors.toCollection(LinkedHashSet::new));
+ if ((method == MethodArg.POINT_IN || method == MethodArg.POINT_ON) && polygons.size() > 1) {
+ // need to merge shapes so that POI on shared boundary becomes IN rather than ON
+ List<List<Coord>> outers = new ArrayList<>();
+ List<List<Coord>> holes = new ArrayList<>();
+ IsInUtil.mergePolygons(polygons, outers, holes);
+ log.info("pointMerge", polygons.size(), outers.size(), holes.size());
+ for (List<Coord> shape : outers)
+ checkPointInShape(c, shape, holes);
+ if (method == MethodArg.POINT_ON && !holes.isEmpty())
+ // need to check if on edge of hole
+ for (List<Coord> hole : holes)
+ checkPointInShape(c, hole, null);
+ } else { // just one polygon or IN_OR_ON, which can do one-by-one
+ log.info("point1by1", polygons.size());
+ for (Way polygon : polygons)
+ checkPointInShape(c, polygon.getPoints(), null);
+ }
+ }
+
private void doLineTest(Way el) {
doCommonTest(el);
}
@@ -233,25 +291,51 @@
doCommonTest(el);
}
+ private void checkHoles(List<Coord> polyLine, List<List<Coord>> holes, Area elementBbox) {
+ for (List<Coord> hole : holes) {
+ int flags = IsInUtil.isLineInShape(kind, polyLine, hole, elementBbox);
+ if ((flags & IsInUtil.IN) != 0) {
+ setOut();
+ if ((flags & IsInUtil.ON) != 0)
+ setOn();
+ if ((flags & IsInUtil.OUT) != 0)
+ setIn();
+ return;
+ }
+ }
+ }
+
private void doCommonTest(Element el) {
- Area elementBbox;
- if (kind == FeatureKind.POINT) {
- elementBbox = Area.getBBox(Collections.singletonList(((Node) el).getLocation()));
- } else {
- elementBbox = Area.getBBox(((Way)el).getPoints());
- }
- // cast Element type to Way
+ List<Coord> polyLine = ((Way)el).getPoints();
+ Area elementBbox = Area.getBBox(polyLine);
Set<Way> polygons = qt.get(elementBbox).stream().map(e -> (Way) e)
.collect(Collectors.toCollection(LinkedHashSet::new));
- int flags = IsInUtil.calcInsideness(kind, el, polygons);
- if ((flags & IsInUtil.IN) != 0)
- setIn();
- if ((flags & IsInUtil.ON) != 0)
- setOn();
- if ((flags & IsInUtil.OUT) != 0)
- setOut();
+ if ((method == MethodArg.LINE_SOME_IN_NONE_OUT ||
+ method == MethodArg.LINE_ALL_IN_OR_ON ||
+ method == MethodArg.LINE_ALL_ON ||
+ method == MethodArg.POLYGON_ALL) && polygons.size() > 1) {
+ // ALL-like methods need to merge shapes
+ List<List<Coord>> outers = new ArrayList<>();
+ List<List<Coord>> holes = new ArrayList<>();
+ IsInUtil.mergePolygons(polygons, outers, holes);
+ log.info("polyMerge", polygons.size(), outers.size(), holes.size());
+ for (List<Coord> shape : outers) {
+ int flags = IsInUtil.isLineInShape(kind, polyLine, shape, elementBbox);
+ if ((flags & (IsInUtil.IN | IsInUtil.ON)) != 0) {
+ // this shape is the one to consider
+ setHasFromFlags(flags); // might set OUT and stop
+ if ((flags & IsInUtil.IN) != 0)
+ checkHoles(polyLine, holes, elementBbox);
+ break;
+ }
+ }
+ } else { // an ANY-like method
+ log.info("poly1by1", polygons.size());
+ for (Way polygon : polygons)
+ setHasFromFlags(IsInUtil.isLineInShape(kind, polyLine, polygon.getPoints(), elementBbox));
+ }
}
-
+
@Override
public String getName() {
return "is_in";
@@ -279,17 +363,24 @@
}
@Override
+ protected String getCacheTag() {
+ return "mkgmap:cache_is_in_" + kind + "_" + String.join("_", params);
+ }
+
+ @Override
public void augmentWith(ElementSaver elementSaver) {
+ log.info("augmentWith", System.identityHashCode(this), kind, params);
+ // the cached function mechanism creates an instance for each occurance in the rule file
+ // but then just uses one of them for augmentWith() and calcImpl().
if (qt != null)
return;
qt = buildTree(elementSaver, params.get(0), params.get(1));
}
-
public static ElementQuadTree buildTree(ElementSaver elementSaver, String tagKey, String tagVal) {
List<Element> matchingPolygons = new ArrayList<>();
for (Way w : elementSaver.getWays().values()) {
- if (w.isComplete() && w.hasIdenticalEndPoints()
+ if (w.hasIdenticalEndPoints()
&& !"polyline".equals(w.getTag(MultiPolygonRelation.STYLE_FILTER_TAG))) {
String val = w.getTag(tagKey);
if (val != null && val.equals(tagVal)) {
Index: src/uk/me/parabola/util/IsInUtil.java
===================================================================
--- src/uk/me/parabola/util/IsInUtil.java (revision 4445)
+++ src/uk/me/parabola/util/IsInUtil.java (working copy)
@@ -60,93 +60,27 @@
// hide public constructor
}
- /**
- * Calculate status of element regarding a list of polygons.
- * @param kind type of rule (POINT, POLYLINE, POLYGON)
- * @param el the element
- * @param polygons the polygons which should be tested
- * @return integer containing flags IN, ON, and OUT
- */
- public static int calcInsideness(FeatureKind kind, Element el, Set<Way> polygons) {
- int result = 0;
- if (polygons == null || polygons.isEmpty()) {
- return OUT;
+ public static void mergePolygons(Set<Way> polygons, List<List<Coord>> outers, List<List<Coord>> holes) {
+ // combine all polygons which intersect the bbox of the element if possible
+ Path2D.Double path = new Path2D.Double();
+ for (Way polygon : polygons) {
+ path.append(Java2DConverter.createPath2D(polygon.getPoints()), false);
}
-
- Area elementBbox;
- if (el instanceof Node) {
- Coord c = ((Node) el).getLocation();
- for (Way polygon : polygons) {
- switch (isPointInShape(c, polygon.getPoints())) {
- case IN:
- return IN;
- case ON:
- result |= ON;
- default:
- }
- }
- return result == 0 ? OUT : ON;
- } else if (el instanceof Way) {
- Way w = (Way) el;
- if (w.isComplete()) {
- elementBbox = Area.getBBox(w.getPoints());
- if (polygons.size() > 1) {
- // combine all polygons which intersect the bbox of the element if possible
- Path2D.Double path = new Path2D.Double();
- for (Way polygon : polygons) {
- path.append(Java2DConverter.createPath2D(polygon.getPoints()), false);
- }
- java.awt.geom.Area polygonsArea = new java.awt.geom.Area(path);
- List<List<Coord>> mergedShapes = Java2DConverter.areaToShapes(polygonsArea);
+ java.awt.geom.Area polygonsArea = new java.awt.geom.Area(path);
+ List<List<Coord>> mergedShapes = Java2DConverter.areaToShapes(polygonsArea);
- // combination of polygons may contain holes. They are counter clockwise.
- List<List<Coord>> holes = new ArrayList<>();
- List<List<Coord>> outers = new ArrayList<>();
- for (List<Coord> shape : mergedShapes) {
- (Way.clockwise(shape) ? outers : holes).add(shape);
- }
-
- // check if any outer intersects with the way
- for (List<Coord> shape : outers) {
- int tmpRes = isLineInShape(kind, w.getPoints(), shape, elementBbox);
- if (tmpRes != OUT) {
- result |= tmpRes;
- if ((tmpRes & IN) != 0) {
- result = tmpRes;
- break;
- }
- }
- }
- if ((result & IN) != 0 && !holes.isEmpty()) {
- // an outer ring matched
- // check if any hole intersects with the way
- for (List<Coord> hole : holes) {
- int tmpRes = isLineInShape(kind, w.getPoints(), hole, elementBbox);
- if (tmpRes == IN_ON_OUT)
- return tmpRes;
- if ((tmpRes & IN) != 0)
- result = OUT;
- result |= tmpRes & ON;
-
- }
- }
-
- } else if (polygons.size() == 1) {
- result = isLineInShape(kind, w.getPoints(), (polygons.iterator().next()).getPoints(), elementBbox);
- }
- }
+ // combination of polygons may contain holes. They are counter clockwise.
+ for (List<Coord> shape : mergedShapes) {
+ (Way.clockwise(shape) ? outers : holes).add(shape);
}
- if (result == 0)
- result = OUT;
- return result;
}
-
+
private enum IntersectionStatus {
TOUCHING, CROSSING, SPLITTING, JOINING,SIMILAR, DOUBLE_SPIKE
}
- private static int isLineInShape(FeatureKind kind, List<Coord> lineToTest, List<Coord> shape, Area elementBbox) {
+ public static int isLineInShape(FeatureKind kind, List<Coord> lineToTest, List<Coord> shape, Area elementBbox) {
final int n = lineToTest.size();
int status = isPointInShape(lineToTest.get(0), shape);
BitSet onBoundary = new BitSet();
@@ -428,7 +362,7 @@
if (inOrOn) {
// point is in or on
boolean in = insidePolygon(p, false, shape);
- return inOrOn != in ? ON : IN;
+ return in ? IN : ON;
}
return OUT;
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
