Changeset 19272 in josm

Timestamp:

2024-12-19T22:13:29+01:00 (13 hours ago)

Author:

taylor.smock

Message:

See #24046: Reduce cost of Geometry#filterInsidePolygon when a primitive is a relation

This was done by checking that the bounds of the polygon contain the bounds of
the multipolygon ring before creating an area from the multipolygon ring.

If the polygon does not contain the bounds of the ring, then at least part
of the ring is outside the polygon, and thus is not inside the polygon.

Measurements using validators at (57.5183581,-75.0512982),(57.2181217,-73.9434821):

• CPU: -87%
• Memory: -62%

Please note that the test area is still very expensive in
Geometry#filterInsideMultipolygon (note the Multipolygon).

Location:

trunk

Files:

• src/org/openstreetmap/josm/tools/Geometry.java (modified) (2 diffs)
• test/unit/org/openstreetmap/josm/tools/GeometryTest.java (modified) (4 diffs)

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

@@ -705 +705 @@
         inter.intersect(a2);
 
+        // Note: Area has an equals method that takes Area; it does _not_ override the Object.equals method.
         if (inter.isEmpty() || !checkIntersection(inter, eps)) {
             return new Pair<>(PolygonIntersection.OUTSIDE, inter);
@@ -1196 +1197 @@
                 for (PolyData outer : mp.getOuterPolygons()) {
                     if (!outer.isClosed()
+                            || !polygonArea.getBounds2D().contains(outer.getBounds())
                             || PolygonIntersection.FIRST_INSIDE_SECOND != polygonIntersection(getArea(outer.getNodes()),
                                     polygonArea)) {

trunk/test/unit/org/openstreetmap/josm/tools/GeometryTest.java

@@ -2 +2 @@
 package org.openstreetmap.josm.tools;
 
+import static org.junit.jupiter.api.Assertions.assertAll;
 import static org.junit.jupiter.api.Assertions.assertDoesNotThrow;
 import static org.junit.jupiter.api.Assertions.assertEquals;
@@ -15 +16 @@
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
@@ -29 +31 @@
 import org.openstreetmap.josm.data.coor.LatLon;
 import org.openstreetmap.josm.data.osm.DataSet;
+import org.openstreetmap.josm.data.osm.IPrimitive;
 import org.openstreetmap.josm.data.osm.Node;
 import org.openstreetmap.josm.data.osm.OsmPrimitive;
@@ -574 +577 @@
     }
 
+    @Test
+    void testFilterInsidePolygon() {
+        final Way polygon = TestUtils.newWay("", new Node(new LatLon(39.0673254, -108.5610777)),
+                new Node(new LatLon(39.0672673, -108.561012)),
+                new Node(new LatLon(39.0673414, -108.5609747)));
+        polygon.addNode(polygon.firstNode());
+        final Node out1 = new Node(new LatLon(39.0673259, -108.5610835));
+        final Node out2 = new Node(new LatLon(39.067263, -108.5610113));
+        final Node out3 = new Node(new LatLon(39.0673434, -108.5609708));
+        final Node out4 = new Node(new LatLon(39.067336, -108.5610312));
+        final Node out5 = new Node(new LatLon(39.0672963, -108.5610448));
+        final Node in1 = new Node(new LatLon(39.0672965, -108.5610446));
+        final Node in2 = new Node(new LatLon(39.0673009, -108.5609964));
+        final Node in3 = new Node(new LatLon(39.0673315, -108.5610294));
+        int i = 1;
+        for (final Node node : Arrays.asList(out1, out2, out3, out4, out5)) {
+            node.put("name", "out" + i++);
+        }
+        i = 1;
+        for (final Node node : Arrays.asList(in1, in2, in3)) {
+            node.put("name", "in" + i++);
+        }
+        // Not closed, ignored
+        final Way win1 = TestUtils.newWay("name=win1", in1, in2, in3);
+        final Way win2 = TestUtils.newWay("name=win2", in1, in2, in3, in1);
+        final Way wout1 = TestUtils.newWay("name=wout1", out1, out2, out3, out1);
+        final Relation rin1 = TestUtils.newRelation("type=multipolygon name=rin1", new RelationMember("outer", win2));
+        // Ignored, not multipolygon
+        final Relation rin2 = TestUtils.newRelation("name=rin2", new RelationMember("outer", win2));
+        // Ignored, sole outer is not closed
+        final Relation rin3 = TestUtils.newRelation("type=multipolygon name=rin3", new RelationMember("outer", win1));
+        final Relation rout1 = TestUtils.newRelation("type=multipolygon name=rout1", new RelationMember("outer", wout1));
+        final Collection<IPrimitive> result = Geometry.filterInsidePolygon(Arrays.asList(out1, out2, out3, out4, out5, in1, in2, in3,
+                win1, win2, wout1, rin1, rin2, rin3, rout1), polygon);
+        assertAll(() -> assertTrue(result.contains(in1)),
+                () -> assertTrue(result.contains(in2)),
+                () -> assertTrue(result.contains(in3)),
+                () -> assertTrue(result.contains(win2)),
+                () -> assertTrue(result.contains(rin1)));
+        assertEquals(5, result.size(), () -> {
+            final List<IPrimitive> notExpected = new ArrayList<>(result);
+            notExpected.removeAll(Arrays.asList(in1, in2, in3, win2, rin1));
+            return notExpected.stream().map(p -> p.get("name")).collect(Collectors.joining("\n"));
+        });
+    }
+
     /**
      * A non-regression test for an issue found during the investigation of #22684 (see comment:3 by GerdP)