Changeset 15069 in josm


Ignore:
Timestamp:
2019-05-11T11:15:49+02:00 (6 months 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
Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/gui/mappaint/mapcss/Selector.java

    r15068 r15069  
    55
    66import java.text.MessageFormat;
     7import java.util.ArrayList;
    78import java.util.Collection;
    89import java.util.Collections;
     
    313314
    314315        private class ContainsFinder extends AbstractFinder {
     316            protected List<IPrimitive> toCheck;
     317
    315318            protected ContainsFinder(Environment e) {
    316319                super(e);
     
    319322
    320323            @Override
    321             public void visit(INode n) {
    322                 if (left.matches(new Environment(n).withParent(e.osm))
    323                     && ((e.osm instanceof IWay && Geometry.nodeInsidePolygon(n, ((IWay<?>) e.osm).getNodes()))
    324                             || (e.osm instanceof Relation && (
    325                                     (Relation) e.osm).isMultipolygon() && Geometry.isNodeInsideMultiPolygon(n, (Relation) e.osm, null)))) {
    326                     addToChildren(e, n);
    327                 }
    328             }
    329 
    330             @Override
    331             public void visit(IWay<?> w) {
    332                 if (left.matches(new Environment(w).withParent(e.osm))
    333                     && ((e.osm instanceof IWay && Geometry.PolygonIntersection.FIRST_INSIDE_SECOND.equals(
    334                             Geometry.polygonIntersection(w.getNodes(), ((IWay<?>) e.osm).getNodes())))
    335                             || (e.osm instanceof Relation && (
    336                                     (Relation) e.osm).isMultipolygon()
    337                                     && Geometry.isPolygonInsideMultiPolygon(w.getNodes(), (Relation) e.osm, null)))) {
    338                     addToChildren(e, w);
     324            public void visit(Collection<? extends IPrimitive> primitives) {
     325                for (IPrimitive p : primitives) {
     326                    if (p != e.osm && isPrimitiveUsable(p) && left.matches(new Environment(p).withParent(e.osm))) {
     327                        if (toCheck == null) {
     328                            toCheck = new ArrayList<>();
     329                        }
     330                        toCheck.add(p);
     331                    }
     332                }
     333            }
     334
     335            void execGeometryTests() {
     336                if (toCheck == null || toCheck.isEmpty())
     337                    return;
     338
     339                if (e.osm instanceof IWay) {
     340                    for (IPrimitive p : Geometry.filterInsidePolygon(toCheck, (IWay<?>) e.osm)) {
     341                        addToChildren(e, p);
     342                    }
     343                } else if (e.osm instanceof Relation) {
     344                    for (IPrimitive p : Geometry.filterInsideMultipolygon(toCheck, (Relation) e.osm)) {
     345                        addToChildren(e, p);
     346                    }
    339347                }
    340348            }
     
    364372                        containsFinder.visit(e.osm.getDataSet().searchWays(e.osm.getBBox()));
    365373                    }
     374                    if (((OptimizedGeneralSelector) left).matchesBase(OsmPrimitiveType.RELATION)) {
     375                        containsFinder.visit(e.osm.getDataSet().searchRelations(e.osm.getBBox()));
     376                    }
    366377                } else {
    367378                    // use slow test
    368379                    containsFinder.visit(e.osm.getDataSet().allPrimitives());
    369380                }
    370 
     381                containsFinder.execGeometryTests();
    371382                return e.children != null;
    372383
  • trunk/src/org/openstreetmap/josm/tools/Geometry.java

    r15056 r15069  
    3030import org.openstreetmap.josm.data.osm.INode;
    3131import org.openstreetmap.josm.data.osm.IPrimitive;
     32import org.openstreetmap.josm.data.osm.IWay;
    3233import org.openstreetmap.josm.data.osm.MultipolygonBuilder;
    3334import org.openstreetmap.josm.data.osm.MultipolygonBuilder.JoinedPolygon;
     
    3940import org.openstreetmap.josm.data.osm.WaySegment;
    4041import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
     42import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData;
    4143import org.openstreetmap.josm.data.osm.visitor.paint.relations.MultipolygonCache;
    4244import org.openstreetmap.josm.data.projection.Projection;
     
    965967     * Tests if the {@code node} is inside the multipolygon {@code multiPolygon}. The nullable argument
    966968     * {@code isOuterWayAMatch} allows to decide if the immediate {@code outer} way of the multipolygon is a match.
     969     * For repeated tests against {@code multiPolygon} better use {@link Geometry#filterInsideMultipolygon}.
    967970     * @param node node
    968971     * @param multiPolygon multipolygon
     
    977980     * Tests if the polygon formed by {@code nodes} is inside the multipolygon {@code multiPolygon}. The nullable argument
    978981     * {@code isOuterWayAMatch} allows to decide if the immediate {@code outer} way of the multipolygon is a match.
     982     * For repeated tests against {@code multiPolygon} better use {@link Geometry#filterInsideMultipolygon}.
    979983     * <p>
    980984     * If {@code nodes} contains exactly one element, then it is checked whether that one node is inside the multipolygon.
     
    982986     * @param multiPolygon multipolygon
    983987     * @param isOuterWayAMatch allows to decide if the immediate {@code outer} way of the multipolygon is a match
    984      * @return {@code true} if the polygon formed by nodes is inside the multipolygon
     988     * @return {@code true} if the multipolygon is valid and the polygon formed by nodes is inside the multipolygon
    985989     */
    986990    public static boolean isPolygonInsideMultiPolygon(List<? extends INode> nodes, Relation multiPolygon, Predicate<Way> isOuterWayAMatch) {
    987         // Extract outer/inner members from multipolygon
     991        try {
     992            return isPolygonInsideMultiPolygon(nodes, MultipolygonBuilder.joinWays(multiPolygon), isOuterWayAMatch);
     993        } catch (MultipolygonBuilder.JoinedPolygonCreationException ex) {
     994            Logging.trace(ex);
     995            Logging.debug("Invalid multipolygon " + multiPolygon);
     996            return false;
     997        }
     998    }
     999
     1000    /**
     1001     * Tests if the polygon formed by {@code nodes} is inside the multipolygon {@code multiPolygon}. The nullable argument
     1002     * {@code isOuterWayAMatch} allows to decide if the immediate {@code outer} way of the multipolygon is a match.
     1003     * For repeated tests against {@code multiPolygon} better use {@link Geometry#filterInsideMultipolygon}.
     1004     * <p>
     1005     * If {@code nodes} contains exactly one element, then it is checked whether that one node is inside the multipolygon.
     1006     * @param nodes nodes forming the polygon
     1007     * @param outerInner result of {@link MultipolygonBuilder#joinWays(Relation)}
     1008     * @param isOuterWayAMatch allows to decide if the immediate {@code outer} way of the multipolygon is a match
     1009     * @return {@code true} if the multipolygon is valid and the polygon formed by nodes is inside the multipolygon
     1010     * @since 15069
     1011     */
     1012    public static boolean isPolygonInsideMultiPolygon(List<? extends INode> nodes, Pair<List<JoinedPolygon>,
     1013            List<JoinedPolygon>> outerInner, Predicate<Way> isOuterWayAMatch) {
     1014        Area a1 = nodes.size() == 1 ? null : getArea(nodes);
     1015        // Test if object is inside an outer member
     1016        for (JoinedPolygon out : outerInner.a) {
     1017            if (a1 == null
     1018                    ? nodeInsidePolygon(nodes.get(0), out.getNodes())
     1019                    : PolygonIntersection.FIRST_INSIDE_SECOND == polygonIntersection(a1, out.area)) {
     1020                boolean insideInner = false;
     1021                // If inside an outer, check it is not inside an inner
     1022                for (JoinedPolygon in : outerInner.b) {
     1023                    if (a1 == null ? nodeInsidePolygon(nodes.get(0), in.getNodes())
     1024                            : in.area.getBounds2D().contains(a1.getBounds2D())
     1025                                    && polygonIntersection(a1, in.area) == PolygonIntersection.FIRST_INSIDE_SECOND
     1026                                    && polygonIntersection(in.area, out.area) == PolygonIntersection.FIRST_INSIDE_SECOND) {
     1027                        insideInner = true;
     1028                        break;
     1029                    }
     1030                }
     1031                if (!insideInner) {
     1032                    // Final check using predicate
     1033                    if (isOuterWayAMatch == null || isOuterWayAMatch.test(out.ways.get(0)
     1034                            /* TODO give a better representation of the outer ring to the predicate */)) {
     1035                        return true;
     1036                    }
     1037                }
     1038            }
     1039        }
     1040        return false;
     1041    }
     1042
     1043    /**
     1044     * Find all primitives in the given collection which are inside the given polygon.
     1045     * @param primitives the primitives
     1046     * @param polygon the polygon
     1047     * @return a new list containing the found primitives, empty if polygon is invalid or nothing was found.
     1048     * @since 15069
     1049     */
     1050
     1051    public static List<IPrimitive> filterInsidePolygon(List<IPrimitive> primitives, IWay<?> polygon) {
     1052        List<IPrimitive> res = new ArrayList<>();
     1053        if (!polygon.isClosed() || polygon.getNodesCount() <= 3)
     1054            return res;
     1055        /** polygon area in east north space, calculated only when really needed */
     1056        Area polygonArea = null;
     1057        for (IPrimitive p : primitives) {
     1058            if (p instanceof INode) {
     1059                if (nodeInsidePolygon((INode) p, polygon.getNodes())) {
     1060                    res.add(p);
     1061                }
     1062            } else if (p instanceof IWay) {
     1063                if (polygonArea == null) {
     1064                    polygonArea = getArea(polygon.getNodes());
     1065                }
     1066                if (PolygonIntersection.FIRST_INSIDE_SECOND == polygonIntersection(getArea(((IWay<?>) p).getNodes()),
     1067                        polygonArea)) {
     1068                    res.add(p);
     1069                }
     1070            } else if (p.isMultipolygon()) {
     1071                if (polygonArea == null) {
     1072                    polygonArea = getArea(polygon.getNodes());
     1073                }
     1074                Multipolygon mp = new Multipolygon((Relation) p);
     1075                boolean inside = true;
     1076                // a (valid) multipolygon is inside the polygon if all outer rings are inside
     1077                for (PolyData outer : mp.getOuterPolygons()) {
     1078                    if (PolygonIntersection.FIRST_INSIDE_SECOND != polygonIntersection(getArea(outer.getNodes()),
     1079                            polygonArea)) {
     1080                        inside = false;
     1081                        break;
     1082                    }
     1083                }
     1084                if (inside) {
     1085                    res.add(p);
     1086                }
     1087            }
     1088        }
     1089        return res;
     1090    }
     1091
     1092    /**
     1093     * Find all primitives in the given collection which are inside the given multipolygon. Members of the multipolygon are
     1094     * ignored.
     1095     * @param primitives the primitives
     1096     * @param multiPolygon the multipolygon relation
     1097     * @return a new list containing the found primitives, empty if multipolygon is invalid or nothing was found.
     1098     * @since 15069
     1099     */
     1100    public static List<IPrimitive> filterInsideMultipolygon(Collection<IPrimitive> primitives, Relation multiPolygon) {
     1101        List<IPrimitive> res = new ArrayList<>();
     1102        if (primitives.isEmpty())
     1103            return res;
     1104
    9881105        final Pair<List<JoinedPolygon>, List<JoinedPolygon>> outerInner;
    9891106        try {
     
    9921109            Logging.trace(ex);
    9931110            Logging.debug("Invalid multipolygon " + multiPolygon);
    994             return false;
    995         }
    996         // Test if object is inside an outer member
    997         for (JoinedPolygon out : outerInner.a) {
    998             if (nodes.size() == 1
    999                     ? nodeInsidePolygon(nodes.get(0), out.getNodes())
    1000                     : PolygonIntersection.FIRST_INSIDE_SECOND == polygonIntersection(nodes, out.getNodes())) {
    1001                 boolean insideInner = false;
    1002                 // If inside an outer, check it is not inside an inner
    1003                 for (JoinedPolygon in : outerInner.b) {
    1004                     if (nodes.size() == 1 ? nodeInsidePolygon(nodes.get(0), in.getNodes())
    1005                             : polygonIntersection(nodes, in.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND
    1006                                     && polygonIntersection(in.getNodes(),
    1007                                             out.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND) {
    1008                         insideInner = true;
     1111            return res;
     1112        }
     1113
     1114        Set<OsmPrimitive> members = multiPolygon.getMemberPrimitives();
     1115        for (IPrimitive p : primitives) {
     1116            if (members.contains(p))
     1117                continue;
     1118            if (p instanceof Node) {
     1119                if (isPolygonInsideMultiPolygon(Collections.singletonList((Node) p), outerInner, null)) {
     1120                    res.add(p);
     1121                }
     1122            } else if (p instanceof Way) {
     1123                if (isPolygonInsideMultiPolygon(((Way) p).getNodes(), outerInner, null)) {
     1124                    res.add(p);
     1125                }
     1126            } else if (p.isMultipolygon()) {
     1127                Multipolygon mp = new Multipolygon((Relation) p);
     1128                boolean inside = true;
     1129                // a (valid) multipolygon is inside multiPolygon if all outer rings are inside
     1130                for (PolyData outer : mp.getOuterPolygons()) {
     1131                    if (!isPolygonInsideMultiPolygon(outer.getNodes(), outerInner, null)) {
     1132                        inside = false;
    10091133                        break;
    10101134                    }
    10111135                }
    1012                 // Inside outer but not inside inner -> the polygon appears to be inside a the multipolygon
    1013                 if (!insideInner) {
    1014                     // Final check using predicate
    1015                     if (isOuterWayAMatch == null || isOuterWayAMatch.test(out.ways.get(0)
    1016                             /* TODO give a better representation of the outer ring to the predicate */)) {
    1017                         return true;
    1018                     }
    1019                 }
    1020             }
    1021         }
    1022         return false;
    1023     }
     1136                if (inside) {
     1137                    res.add(p);
     1138                }
     1139            }
     1140        }
     1141        return res;
     1142    }
     1143
    10241144
    10251145    /**
  • trunk/test/unit/org/openstreetmap/josm/data/validation/tests/MapCSSTagCheckerTest.java

    r15064 r15069  
    339339        assertEquals(1, errors.size());
    340340    }
     341
     342    /**
     343     * Non-regression test for <a href="https://josm.openstreetmap.de/ticket/17695">Bug #17695</a>.
     344     * @throws Exception if an error occurs
     345     */
     346    @Test
     347    public void testTicket17695() throws Exception {
     348        final MapCSSTagChecker test = buildTagChecker(
     349                "*[building] ∈  *[building] {" +
     350                "throwWarning: tr(\"Building inside building\");" +
     351                "}");
     352        try (InputStream is = TestUtils.getRegressionDataStream(17695, "bib2.osm")) {
     353            test.visit(OsmReader.parseDataSet(is, null).allPrimitives());
     354            List<TestError> errors = test.getErrors();
     355            assertEquals(6, errors.size());
     356        }
     357    }
     358
    341359}
  • trunk/test/unit/org/openstreetmap/josm/tools/GeometryTest.java

    r15035 r15069  
    265265
    266266    /**
     267     * Test of {@link Geometry#filterInsideMultipolygon}
     268     */
     269    @Test
     270    public void testFilterInsideMultiPolygon() {
     271        Node node1 = new Node(new LatLon(1.01, 1.0));
     272        Node node2 = new Node(new LatLon(1.01, 1.1));
     273        Node node3 = new Node(new LatLon(1.02, 1.05));
     274        Way w1 = new Way();
     275        w1.setNodes(Arrays.asList(node1, node2, node3, node1));
     276        w1.put("building", "yes");
     277        Relation mp1 = new Relation();
     278        mp1.addMember(new RelationMember("outer", w1));
     279        mp1.put("type", "multipolygon");
     280
     281        Node node4 = new Node(new LatLon(1.0, 1.09));
     282        Node node5 = new Node(new LatLon(1.0, 1.12));
     283        Node node6 = new Node(new LatLon(1.1, 1.12));
     284        Node node7 = new Node(new LatLon(1.1, 1.09));
     285        Way outer = new Way();
     286        outer.setNodes(Arrays.asList(node4, node5, node6, node7, node4));
     287        Node node8 = new Node(new LatLon(1.04, 1.1));
     288        Node node9 = new Node(new LatLon(1.04, 1.11));
     289        Node node10 = new Node(new LatLon(1.06, 1.105));
     290        Way inner = new Way();
     291        inner.setNodes(Arrays.asList(node8, node9, node10, node8));
     292        Relation mp2 = new Relation();
     293        mp2.addMember(new RelationMember("outer", outer));
     294        mp2.addMember(new RelationMember("inner", inner));
     295        mp2.put("type", "multipolygon");
     296        assertFalse(Geometry.isPolygonInsideMultiPolygon(w1.getNodes(), mp2, null));
     297        assertFalse(Geometry.filterInsideMultipolygon(Arrays.asList(w1), mp2).contains(w1));
     298
     299        node4.setCoor(new LatLon(1.006, 0.99));
     300        // now w1 is inside
     301        assertTrue(Geometry.isPolygonInsideMultiPolygon(w1.getNodes(), mp2, null));
     302        assertTrue(Geometry.filterInsideMultipolygon(Arrays.asList(w1), mp2).contains(w1));
     303        assertTrue(Geometry.filterInsideMultipolygon(Arrays.asList(mp1), mp2).contains(mp1));
     304        assertTrue(Geometry.filterInsideMultipolygon(Arrays.asList(w1, mp1), mp2).contains(w1));
     305        assertTrue(Geometry.filterInsideMultipolygon(Arrays.asList(w1, mp1), mp2).contains(mp1));
     306    }
     307
     308    /**
    267309     * Test of {@link Geometry#getDistance} method.
    268310     */
Note: See TracChangeset for help on using the changeset viewer.