Changeset 15069 in josm for trunk/src/org/openstreetmap

Timestamp:

2019-05-11T11:15:49+02:00 (6 years ago)

Author:

GerdP

Message:

fix #17695

• add support to find multipolygon inside polygon or multipolygon with ContainsFinder
• add some unit tests
• performance_1: improve isPolygonInsideMultiPolygon() by using the areas calculated

in MultipolygonBuilder.joinWays() instead of calling getArea() again.

• performance_2: improve isPolygonInsideMultiPolygon() by first checking bounding boxes (helps with complex MP containing many inners as it avoids the Area.intersect() method)
• performance_3: implement new methods to reuse result of complex method MultipolygonBuilder.joinWays() in ContainsFinder

Location:

trunk/src/org/openstreetmap/josm

Files:

• gui/mappaint/mapcss/Selector.java (modified) (4 diffs)
• tools/Geometry.java (modified) (6 diffs)

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

@@ -5 +5 @@
 
 import java.text.MessageFormat;
+import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
@@ -313 +314 @@
 
         private class ContainsFinder extends AbstractFinder {
+            protected List<IPrimitive> toCheck;
+
             protected ContainsFinder(Environment e) {
                 super(e);
@@ -319 +322 @@
 
             @Override
-            public void visit(INode n) {
-                if (left.matches(new Environment(n).withParent(e.osm))
-                    && ((e.osm instanceof IWay && Geometry.nodeInsidePolygon(n, ((IWay<?>) e.osm).getNodes()))
-                            || (e.osm instanceof Relation && (
-                                    (Relation) e.osm).isMultipolygon() && Geometry.isNodeInsideMultiPolygon(n, (Relation) e.osm, null)))) {
-                    addToChildren(e, n);
-                }
-            }
-
-            @Override
-            public void visit(IWay<?> w) {
-                if (left.matches(new Environment(w).withParent(e.osm))
-                    && ((e.osm instanceof IWay && Geometry.PolygonIntersection.FIRST_INSIDE_SECOND.equals(
-                            Geometry.polygonIntersection(w.getNodes(), ((IWay<?>) e.osm).getNodes())))
-                            || (e.osm instanceof Relation && (
-                                    (Relation) e.osm).isMultipolygon()
-                                    && Geometry.isPolygonInsideMultiPolygon(w.getNodes(), (Relation) e.osm, null)))) {
-                    addToChildren(e, w);
+            public void visit(Collection<? extends IPrimitive> primitives) {
+                for (IPrimitive p : primitives) {
+                    if (p != e.osm && isPrimitiveUsable(p) && left.matches(new Environment(p).withParent(e.osm))) {
+                        if (toCheck == null) {
+                            toCheck = new ArrayList<>();
+                        }
+                        toCheck.add(p);
+                    }
+                }
+            }
+
+            void execGeometryTests() {
+                if (toCheck == null || toCheck.isEmpty())
+                    return;
+
+                if (e.osm instanceof IWay) {
+                    for (IPrimitive p : Geometry.filterInsidePolygon(toCheck, (IWay<?>) e.osm)) {
+                        addToChildren(e, p);
+                    }
+                } else if (e.osm instanceof Relation) {
+                    for (IPrimitive p : Geometry.filterInsideMultipolygon(toCheck, (Relation) e.osm)) {
+                        addToChildren(e, p);
+                    }
                 }
             }
@@ -364 +372 @@
                         containsFinder.visit(e.osm.getDataSet().searchWays(e.osm.getBBox()));
                     }
+                    if (((OptimizedGeneralSelector) left).matchesBase(OsmPrimitiveType.RELATION)) {
+                        containsFinder.visit(e.osm.getDataSet().searchRelations(e.osm.getBBox()));
+                    }
                 } else {
                     // use slow test
                     containsFinder.visit(e.osm.getDataSet().allPrimitives());
                 }
-
+                containsFinder.execGeometryTests();
                 return e.children != null;
 

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

@@ -30 +30 @@
 import org.openstreetmap.josm.data.osm.INode;
 import org.openstreetmap.josm.data.osm.IPrimitive;
+import org.openstreetmap.josm.data.osm.IWay;
 import org.openstreetmap.josm.data.osm.MultipolygonBuilder;
 import org.openstreetmap.josm.data.osm.MultipolygonBuilder.JoinedPolygon;
@@ -39 +40 @@
 import org.openstreetmap.josm.data.osm.WaySegment;
 import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
+import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData;
 import org.openstreetmap.josm.data.osm.visitor.paint.relations.MultipolygonCache;
 import org.openstreetmap.josm.data.projection.Projection;
@@ -965 +967 @@
      * 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.
+     * For repeated tests against {@code multiPolygon} better use {@link Geometry#filterInsideMultipolygon}.
      * @param node node
      * @param multiPolygon multipolygon
@@ -977 +980 @@
      * 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.
+     * For repeated tests against {@code multiPolygon} better use {@link Geometry#filterInsideMultipolygon}.
      * <p>
      * If {@code nodes} contains exactly one element, then it is checked whether that one node is inside the multipolygon.
@@ -982 +986 @@
      * @param multiPolygon multipolygon
      * @param isOuterWayAMatch allows to decide if the immediate {@code outer} way of the multipolygon is a match
-     * @return {@code true} if the polygon formed by nodes is inside the multipolygon
+     * @return {@code true} if the multipolygon is valid and the polygon formed by nodes is inside the multipolygon
      */
     public static boolean isPolygonInsideMultiPolygon(List<? extends INode> nodes, Relation multiPolygon, Predicate<Way> isOuterWayAMatch) {
-        // Extract outer/inner members from multipolygon
+        try {
+            return isPolygonInsideMultiPolygon(nodes, MultipolygonBuilder.joinWays(multiPolygon), isOuterWayAMatch);
+        } catch (MultipolygonBuilder.JoinedPolygonCreationException ex) {
+            Logging.trace(ex);
+            Logging.debug("Invalid multipolygon " + multiPolygon);
+            return false;
+        }
+    }
+
+    /**
+     * 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.
+     * For repeated tests against {@code multiPolygon} better use {@link Geometry#filterInsideMultipolygon}.
+     * <p>
+     * If {@code nodes} contains exactly one element, then it is checked whether that one node is inside the multipolygon.
+     * @param nodes nodes forming the polygon
+     * @param outerInner result of {@link MultipolygonBuilder#joinWays(Relation)}
+     * @param isOuterWayAMatch allows to decide if the immediate {@code outer} way of the multipolygon is a match
+     * @return {@code true} if the multipolygon is valid and the polygon formed by nodes is inside the multipolygon
+     * @since 15069
+     */
+    public static boolean isPolygonInsideMultiPolygon(List<? extends INode> nodes, Pair<List<JoinedPolygon>,
+            List<JoinedPolygon>> outerInner, Predicate<Way> isOuterWayAMatch) {
+        Area a1 = nodes.size() == 1 ? null : getArea(nodes);
+        // Test if object is inside an outer member
+        for (JoinedPolygon out : outerInner.a) {
+            if (a1 == null
+                    ? nodeInsidePolygon(nodes.get(0), out.getNodes())
+                    : PolygonIntersection.FIRST_INSIDE_SECOND == polygonIntersection(a1, out.area)) {
+                boolean insideInner = false;
+                // If inside an outer, check it is not inside an inner
+                for (JoinedPolygon in : outerInner.b) {
+                    if (a1 == null ? nodeInsidePolygon(nodes.get(0), in.getNodes())
+                            : in.area.getBounds2D().contains(a1.getBounds2D())
+                                    && polygonIntersection(a1, in.area) == PolygonIntersection.FIRST_INSIDE_SECOND
+                                    && polygonIntersection(in.area, out.area) == PolygonIntersection.FIRST_INSIDE_SECOND) {
+                        insideInner = true;
+                        break;
+                    }
+                }
+                if (!insideInner) {
+                    // Final check using predicate
+                    if (isOuterWayAMatch == null || isOuterWayAMatch.test(out.ways.get(0)
+                            /* TODO give a better representation of the outer ring to the predicate */)) {
+                        return true;
+                    }
+                }
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Find all primitives in the given collection which are inside the given polygon.
+     * @param primitives the primitives
+     * @param polygon the polygon
+     * @return a new list containing the found primitives, empty if polygon is invalid or nothing was found.
+     * @since 15069
+     */
+
+    public static List<IPrimitive> filterInsidePolygon(List<IPrimitive> primitives, IWay<?> polygon) {
+        List<IPrimitive> res = new ArrayList<>();
+        if (!polygon.isClosed() || polygon.getNodesCount() <= 3)
+            return res;
+        /** polygon area in east north space, calculated only when really needed */
+        Area polygonArea = null;
+        for (IPrimitive p : primitives) {
+            if (p instanceof INode) {
+                if (nodeInsidePolygon((INode) p, polygon.getNodes())) {
+                    res.add(p);
+                }
+            } else if (p instanceof IWay) {
+                if (polygonArea == null) {
+                    polygonArea = getArea(polygon.getNodes());
+                }
+                if (PolygonIntersection.FIRST_INSIDE_SECOND == polygonIntersection(getArea(((IWay<?>) p).getNodes()),
+                        polygonArea)) {
+                    res.add(p);
+                }
+            } else if (p.isMultipolygon()) {
+                if (polygonArea == null) {
+                    polygonArea = getArea(polygon.getNodes());
+                }
+                Multipolygon mp = new Multipolygon((Relation) p);
+                boolean inside = true;
+                // a (valid) multipolygon is inside the polygon if all outer rings are inside
+                for (PolyData outer : mp.getOuterPolygons()) {
+                    if (PolygonIntersection.FIRST_INSIDE_SECOND != polygonIntersection(getArea(outer.getNodes()),
+                            polygonArea)) {
+                        inside = false;
+                        break;
+                    }
+                }
+                if (inside) {
+                    res.add(p);
+                }
+            }
+        }
+        return res;
+    }
+
+    /**
+     * Find all primitives in the given collection which are inside the given multipolygon. Members of the multipolygon are
+     * ignored.
+     * @param primitives the primitives
+     * @param multiPolygon the multipolygon relation
+     * @return a new list containing the found primitives, empty if multipolygon is invalid or nothing was found.
+     * @since 15069
+     */
+    public static List<IPrimitive> filterInsideMultipolygon(Collection<IPrimitive> primitives, Relation multiPolygon) {
+        List<IPrimitive> res = new ArrayList<>();
+        if (primitives.isEmpty())
+            return res;
+
         final Pair<List<JoinedPolygon>, List<JoinedPolygon>> outerInner;
         try {
@@ -992 +1109 @@
             Logging.trace(ex);
             Logging.debug("Invalid multipolygon " + multiPolygon);
-            return false;
-        }
-        // Test if object is inside an outer member
-        for (JoinedPolygon out : outerInner.a) {
-            if (nodes.size() == 1
-                    ? nodeInsidePolygon(nodes.get(0), out.getNodes())
-                    : PolygonIntersection.FIRST_INSIDE_SECOND == polygonIntersection(nodes, out.getNodes())) {
-                boolean insideInner = false;
-                // If inside an outer, check it is not inside an inner
-                for (JoinedPolygon in : outerInner.b) {
-                    if (nodes.size() == 1 ? nodeInsidePolygon(nodes.get(0), in.getNodes())
-                            : polygonIntersection(nodes, in.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND
-                                    && polygonIntersection(in.getNodes(),
-                                            out.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND) {
-                        insideInner = true;
+            return res;
+        }
+
+        Set<OsmPrimitive> members = multiPolygon.getMemberPrimitives();
+        for (IPrimitive p : primitives) {
+            if (members.contains(p))
+                continue;
+            if (p instanceof Node) {
+                if (isPolygonInsideMultiPolygon(Collections.singletonList((Node) p), outerInner, null)) {
+                    res.add(p);
+                }
+            } else if (p instanceof Way) {
+                if (isPolygonInsideMultiPolygon(((Way) p).getNodes(), outerInner, null)) {
+                    res.add(p);
+                }
+            } else if (p.isMultipolygon()) {
+                Multipolygon mp = new Multipolygon((Relation) p);
+                boolean inside = true;
+                // a (valid) multipolygon is inside multiPolygon if all outer rings are inside
+                for (PolyData outer : mp.getOuterPolygons()) {
+                    if (!isPolygonInsideMultiPolygon(outer.getNodes(), outerInner, null)) {
+                        inside = false;
                         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.test(out.ways.get(0)
-                            /* TODO give a better representation of the outer ring to the predicate */)) {
-                        return true;
-                    }
-                }
-            }
-        }
-        return false;
-    }
+                if (inside) {
+                    res.add(p);
+                }
+            }
+        }
+        return res;
+    }
+
 
     /**