Changeset 6607 in josm for trunk

Timestamp:

2014-01-03T11:12:16+01:00 (11 years ago)

Author:

simon04

Message:

see #9516 - MapCSS: add basic support for a "contains" expression

The current syntax is outer ∋ inner, e.g., way[building?] ∋ node[building?].

This implementation is known to be inefficient since, for every match on the right side, it checks all primitives of the dataset for a match.

Nevertheless, this implementation allows mappers to write specific MapCSS-based tests involving this spatial operator.

Location:

trunk/src/org/openstreetmap/josm

Files:

• data/validation/tests/BuildingInBuilding.java (modified) (4 diffs)
• gui/mappaint/mapcss/MapCSSParser.jj (modified) (3 diffs)
• gui/mappaint/mapcss/Selector.java (modified) (7 diffs)
• tools/Geometry.java (modified) (3 diffs)

trunk/src/org/openstreetmap/josm/data/validation/tests/BuildingInBuilding.java

@@ -73 +73 @@
     }
 
-    protected class MultiPolygonMembers {
-        private final Set<Way> outers = new HashSet<Way>();
-        private final Set<Way> inners = new HashSet<Way>();
-        public MultiPolygonMembers(Relation multiPolygon) {
-            for (RelationMember m : multiPolygon.getMembers()) {
-                if (m.getType().equals(OsmPrimitiveType.WAY)) {
-                    if (m.getRole().equals("outer")) {
-                        outers.add(m.getWay());
-                    } else if (m.getRole().equals("inner")) {
-                        inners.add(m.getWay());
-                    }
-                }
-            }
-        }
-    }
-
     protected boolean sameLayers(Way w1, Way w2) {
         String l1 = w1.get("layer") != null ? w1.get("layer") : "0";
         String l2 = w2.get("layer") != null ? w2.get("layer") : "0";
         return l1.equals(l2);
-    }
-
-    protected boolean isWayInsideMultiPolygon(Way object, Relation multiPolygon) {
-        // Extract outer/inner members from multipolygon
-        MultiPolygonMembers mpm = new MultiPolygonMembers(multiPolygon);
-        // Test if object is inside an outer member
-        for (Way out : mpm.outers) {
-            PolygonIntersection inter = Geometry.polygonIntersection(object.getNodes(), out.getNodes());
-            if (inter == PolygonIntersection.FIRST_INSIDE_SECOND || inter == PolygonIntersection.CROSSING) {
-                boolean insideInner = false;
-                // If inside an outer, check it is not inside an inner
-                for (Way in : mpm.inners) {
-                    if (Geometry.polygonIntersection(in.getNodes(), out.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND &&
-                        Geometry.polygonIntersection(object.getNodes(), in.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND) {
-                        insideInner = true;
-                        break;
-                    }
-                }
-                // Inside outer but not inside inner -> the building appears to be inside a buiding
-                if (!insideInner) {
-                    // Final check on "layer" tag. Buildings of different layers may be superposed
-                    if (sameLayers(object, out)) {
-                        return true;
-                    }
-                }
-            }
-        }
-        return false;
     }
 
@@ -132 +88 @@
                 }
 
-                protected boolean evaluateWay(Way w, Way object) {
+                protected boolean evaluateWay(final Way w, Way object) {
                     if (w.equals(object)) return false;
 
@@ -151 +107 @@
                         // Else, test if w is inside one of the multipolygons
                         for (OsmPrimitive bmp : buildingMultiPolygons) {
-                            if (bmp instanceof Relation && isWayInsideMultiPolygon(w, (Relation) bmp)) {
+                            if (bmp instanceof Relation && Geometry.isPolygonInsideMultiPolygon(w.getNodes(), (Relation) bmp, new Predicate<Way>() {
+                                @Override
+                                public boolean evaluate(Way outer) {
+                                    return sameLayers(w, outer);
+                                }
+                            })) {
                                 return true;
                             }
@@ -160 +121 @@
 
                 protected boolean evaluateRelation(Relation r, Way object) {
-                    MultiPolygonMembers mpm = new MultiPolygonMembers((Relation) p);
+                    Geometry.MultiPolygonMembers mpm = new Geometry.MultiPolygonMembers((Relation) p);
                     for (Way out : mpm.outers) {
                         if (evaluateWay(out, object)) {

trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/MapCSSParser.jj

@@ -80 +80 @@
 |   < CARET: "^" >
 |   < FULLSTOP: "." >
+|   < CONTAINS: "∋" >
 |   < COMMENT_START: "/*" > : COMMENT
 |   < UNEXPECTED_CHAR : ~[] > // avoid TokenMgrErrors because they are hard to recover from
@@ -262 +263 @@
 Selector child_selector() :
 {
-    boolean parentSelector = false;
+    Selector.ChildOrParentSelectorType type = null;
     Condition c;
     List<Condition> conditions = new ArrayList<Condition>();
@@ -272 +273 @@
     selLeft=selector() w()
     (
-        ( <GREATER> { parentSelector = false; } | <LESS> { parentSelector = true; } ) 
-        ( ( c=condition(Context.LINK) | c=class_or_pseudoclass(Context.LINK) ) { conditions.add(c); } )*
+        (
+            ( <GREATER> { type = Selector.ChildOrParentSelectorType.CHILD; } | <LESS> { type = Selector.ChildOrParentSelectorType.PARENT; } )
+            ( ( c=condition(Context.LINK) | c=class_or_pseudoclass(Context.LINK) ) { conditions.add(c); } )*
+        |
+            <CONTAINS> { type = Selector.ChildOrParentSelectorType.CONTAINS; }
+        )
         { selLink = new LinkSelector(conditions); }
         w()
         selRight=selector() w()
     )?
-    { return selRight != null ? new ChildOrParentSelector(selLeft, selLink, selRight, parentSelector) : selLeft; }
+    { return selRight != null ? new ChildOrParentSelector(selLeft, selLink, selRight, type) : selLeft; }
 }
 

trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Selector.java

@@ -15 +15 @@
 import org.openstreetmap.josm.gui.mappaint.Environment;
 import org.openstreetmap.josm.gui.mappaint.Range;
+import org.openstreetmap.josm.tools.Geometry;
 import org.openstreetmap.josm.tools.Pair;
 import org.openstreetmap.josm.tools.Utils;
@@ -33 +34 @@
 
     public Range getRange();
+
+    public static enum ChildOrParentSelectorType {
+        CHILD, PARENT, CONTAINS
+    }
 
     /**
@@ -54 +59 @@
         /** true, if this represents a parent selector (otherwise it is a child selector)
          */
-        private final boolean parentSelector;
+        private final ChildOrParentSelectorType type;
 
         /**
@@ -60 +65 @@
          * @param a the first selector
          * @param b the second selector
-         * @param parentSelector if true, this is a parent selector; otherwise a child selector
+         * @param type the selector type
          */
-        public ChildOrParentSelector(Selector a, LinkSelector link, Selector b, boolean parentSelector) {
+        public ChildOrParentSelector(Selector a, LinkSelector link, Selector b, ChildOrParentSelectorType type) {
             this.left = a;
             this.link = link;
             this.right = b;
-            this.parentSelector = parentSelector;
+            this.type = type;
         }
 
@@ -142 +147 @@
         }
 
+        private class ContainsFinder extends AbstractVisitor {
+            private final Environment e;
+            private final List<Node> nodes;
+
+            private ContainsFinder(Environment e) {
+                this.e = e;
+                if (e.osm instanceof Node) {
+                    nodes = Collections.singletonList((Node) e.osm);
+                } else if (e.osm instanceof Way) {
+                    nodes = ((Way) e.osm).getNodes();
+                } else {
+                    throw new IllegalArgumentException("Relations not supported");
+                }
+            }
+
+            @Override
+            public void visit(Node n) {
+            }
+
+            @Override
+            public void visit(Way w) {
+                if (e.parent == null && left.matches(e.withPrimitive(w))) {
+                    if (nodes.size() == 1
+                            ? Geometry.nodeInsidePolygon(nodes.get(0), w.getNodes())
+                            : Geometry.PolygonIntersection.FIRST_INSIDE_SECOND.equals(Geometry.polygonIntersection(nodes, w.getNodes()))) {
+                        e.parent = w;
+                        e.index = 0;
+                    }
+                }
+            }
+
+            @Override
+            public void visit(Relation r) {
+                if (e.parent == null && left.matches(e.withPrimitive(r))) {
+                    if (r.isMultipolygon() && Geometry.isPolygonInsideMultiPolygon(nodes, r, null)) {
+                        e.parent = r;
+                        e.index = 0;
+                    }
+                }
+            }
+        }
+
         @Override
         public boolean matches(Environment e) {
@@ -147 +194 @@
                 return false;
 
-            if (!parentSelector) {
+            if (ChildOrParentSelectorType.CONTAINS.equals(type)) {
+                final OsmPrimitive rightPrimitive = e.osm;
+                final ContainsFinder containsFinder = new ContainsFinder(e);
+                for (final OsmPrimitive p : rightPrimitive.getDataSet().allPrimitives()) {
+                    if (rightPrimitive.equals(p)) {
+                        continue;
+                    }
+                    p.accept(containsFinder);
+                    if (e.parent != null) {
+                        e.osm = rightPrimitive;
+                        return true;
+                    }
+                }
+            } else if (ChildOrParentSelectorType.CHILD.equals(type)) {
                 MatchingReferrerFinder collector = new MatchingReferrerFinder(e);
                 e.osm.visitReferrers(collector);
@@ -195 +255 @@
         @Override
         public String toString() {
-            return left +" "+ (parentSelector? "<" : ">")+link+" " +right;
+            return left + " " + (ChildOrParentSelectorType.PARENT.equals(type) ? "<" : ">") + link + " " + right;
         }
     }

trunk/src/org/openstreetmap/josm/tools/Geometry.java

@@ -9 +9 @@
 import java.math.MathContext;
 import java.util.ArrayList;
+import java.util.Collections;
 import java.util.Comparator;
+import java.util.EnumSet;
+import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -23 +26 @@
 import org.openstreetmap.josm.data.osm.Node;
 import org.openstreetmap.josm.data.osm.NodePositionComparator;
+import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
+import org.openstreetmap.josm.data.osm.Relation;
+import org.openstreetmap.josm.data.osm.RelationMember;
 import org.openstreetmap.josm.data.osm.Way;
 
@@ -736 +742 @@
         }
     }
+
+    public static class MultiPolygonMembers {
+        public final Set<Way> outers = new HashSet<Way>();
+        public final Set<Way> inners = new HashSet<Way>();
+
+        public MultiPolygonMembers(Relation multiPolygon) {
+            for (RelationMember m : multiPolygon.getMembers()) {
+                if (m.getType().equals(OsmPrimitiveType.WAY)) {
+                    if (m.getRole().equals("outer")) {
+                        outers.add(m.getWay());
+                    } else if (m.getRole().equals("inner")) {
+                        inners.add(m.getWay());
+                    }
+                }
+            }
+        }
+    }
+
+    /**
+     * Tests if the {@code node} is inside the multipolygon {@code multiPolygon}. The nullable argument
+     * {@code isOuterWayAMatch} allows to decide if the immediate {@code outer} way of the multipolygon is a match.
+     */
+    public static boolean isNodeInsideMultiPolygon(Node node, Relation multiPolygon, Predicate<Way> isOuterWayAMatch) {
+        return isPolygonInsideMultiPolygon(Collections.singletonList(node), multiPolygon, isOuterWayAMatch);
+    }
+
+    /**
+     * Tests if the polygon formed by {@code nodes} is inside the multipolygon {@code multiPolygon}. The nullable argument
+     * {@code isOuterWayAMatch} allows to decide if the immediate {@code outer} way of the multipolygon is a match.
+     * <p/>
+     * If {@code nodes} contains exactly one element, then it is checked whether that one node is inside the multipolygon.
+     */
+    public static boolean isPolygonInsideMultiPolygon(List<Node> nodes, Relation multiPolygon, Predicate<Way> isOuterWayAMatch) {
+        // Extract outer/inner members from multipolygon
+        MultiPolygonMembers mpm = new MultiPolygonMembers(multiPolygon);
+        // Test if object is inside an outer member
+        for (Way out : mpm.outers) {
+            if (nodes.size() == 1
+                    ? nodeInsidePolygon(nodes.get(0), out.getNodes())
+                    : EnumSet.of(PolygonIntersection.FIRST_INSIDE_SECOND, PolygonIntersection.CROSSING).contains(polygonIntersection(nodes, out.getNodes()))) {
+                boolean insideInner = false;
+                // If inside an outer, check it is not inside an inner
+                for (Way in : mpm.inners) {
+                    if (polygonIntersection(in.getNodes(), out.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND
+                            && (nodes.size() == 1
+                            ? nodeInsidePolygon(nodes.get(0), in.getNodes())
+                            : polygonIntersection(nodes, in.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND)) {
+                        insideInner = true;
+                        break;
+                    }
+                }
+                // Inside outer but not inside inner -> the polygon appears to be inside a the multipolygon
+                if (!insideInner) {
+                    // Final check using predicate
+                    if (isOuterWayAMatch == null || isOuterWayAMatch.evaluate(out)) {
+                        return true;
+                    }
+                }
+            }
+        }
+        return false;
+    }
 }