Changeset 15008 in josm

Timestamp:

2019-04-21T07:43:00+02:00 (6 years ago)

Author:

GerdP

Message:

fix #17614:

• don't test integer bounding box of intersection area, use doubles
• in case of multiple intersections, check each individual intersection
• introduce new constant INTERSECTION_EPS_EAST_NORTH, the value 1e-4 is just a reasonable small value, might be decreased
• improve javadoc to make clear that east/north space is assumed
• small refactorings to fix SonarLint issues

Location:

trunk

Files:

• src/org/openstreetmap/josm/data/osm/WaySegment.java (modified) (2 diffs)
• src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java (modified) (5 diffs)
• src/org/openstreetmap/josm/tools/Geometry.java (modified) (7 diffs)
• test/unit/org/openstreetmap/josm/tools/GeometryTest.java (modified) (2 diffs)

trunk/src/org/openstreetmap/josm/data/osm/WaySegment.java

@@ -13 +13 @@
      * The way.
      */
-    public Way way;
+    public final Way way;
 
     /**
@@ -19 +19 @@
      * index <code>lowerIndex + 1</code>.
      */
-    public int lowerIndex;
+    public final int lowerIndex;
 
     /**

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

@@ -272 +272 @@
                 for (int j = i + 1; j < allPolygons.size(); j++) {
                     PolyData pd2 = allPolygons.get(j);
-                    if (!checkProblemMap(crossingPolyMap, pd1, pd2)) {
-                        if (hasIntersectionWay(pd2, intersectionWays))
-                            checkPolygonsForSharedNodes(r, pd1, pd2, sharedNodes);
+                    if (!checkProblemMap(crossingPolyMap, pd1, pd2) && hasIntersectionWay(pd2, intersectionWays)) {
+                        checkPolygonsForSharedNodes(r, pd1, pd2, sharedNodes);
                     }
                 }
@@ -472 +471 @@
             Area a1 = new Area(pd1.get());
             Area a2 = new Area(pd2.get());
-            PolygonIntersection areaRes = Geometry.polygonIntersection(a1, a2, 1e-6);
+            PolygonIntersection areaRes = Geometry.polygonIntersection(a1, a2);
             if (areaRes == PolygonIntersection.OUTSIDE)
                 return ExtPolygonIntersection.OUTSIDE;
@@ -842 +841 @@
 
             for (PolyData pd : polygons) {
-                if (processOuterWay(level, polygons, result, pd) == null) {
-                    return null;
-                }
+                processOuterWay(level, polygons, result, pd);
             }
 
@@ -850 +847 @@
         }
 
-        private Object processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) {
+        private void processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) {
             List<PolyData> inners = findInnerWaysCandidates(pd, polygons);
 
@@ -865 +862 @@
                 result.add(pol);
             }
-            return result;
         }
 

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

@@ -2 +2 @@
 package org.openstreetmap.josm.tools;
 
-import java.awt.Rectangle;
 import java.awt.geom.Area;
 import java.awt.geom.Line2D;
 import java.awt.geom.Path2D;
+import java.awt.geom.PathIterator;
+import java.awt.geom.Rectangle2D;
 import java.math.BigDecimal;
 import java.math.MathContext;
@@ -72 +73 @@
     }
 
+    /** threshold value for size of intersection area given in east/north space */
+    public static final double INTERSECTION_EPS_EAST_NORTH = 1e-4;
+
     /**
      * Will find all intersection and add nodes there for list of given ways.
@@ -578 +582 @@
         Area a1 = getArea(first);
         Area a2 = getArea(second);
-        return polygonIntersection(a1, a2);
-    }
-
-    /**
-     * Tests if two polygons intersect.
+        return polygonIntersection(a1, a2, INTERSECTION_EPS_EAST_NORTH);
+    }
+
+    /**
+     * Tests if two polygons intersect. It is assumed that the area is given in East North points.
      * @param a1 Area of first polygon
      * @param a2 Area of second polygon
@@ -589 +593 @@
      */
     public static PolygonIntersection polygonIntersection(Area a1, Area a2) {
-        return polygonIntersection(a1, a2, 1.0);
+        return polygonIntersection(a1, a2, INTERSECTION_EPS_EAST_NORTH);
     }
 
@@ -604 +608 @@
         inter.intersect(a2);
 
-        Rectangle bounds = inter.getBounds();
-
-        if (inter.isEmpty() || bounds.getHeight()*bounds.getWidth() <= eps) {
+        if (inter.isEmpty() || !checkIntersection(inter, eps)) {
             return PolygonIntersection.OUTSIDE;
         } else if (a2.getBounds2D().contains(a1.getBounds2D()) && inter.equals(a1)) {
@@ -618 +620 @@
 
     /**
+     * Check an intersection area which might describe multiple small polygons.
+     * Return true if any of the polygons is bigger than the given threshold.
+     * @param inter the intersection area
+     * @param eps an area threshold, everything below is considered an empty intersection
+     * @return true if any of the polygons is bigger than the given threshold
+     */
+    private static boolean checkIntersection(Area inter, double eps) {
+        PathIterator pit = inter.getPathIterator(null);
+        double[] res = new double[6];
+        Rectangle2D r = new Rectangle2D.Double();
+        while (!pit.isDone()) {
+            int type = pit.currentSegment(res);
+            switch (type) {
+            case PathIterator.SEG_MOVETO:
+                r = new Rectangle2D.Double(res[0], res[1], 0, 0);
+                break;
+            case PathIterator.SEG_LINETO:
+                r.add(res[0], res[1]);
+                break;
+            case PathIterator.SEG_CLOSE:
+                if (r.getWidth() > eps || r.getHeight() > eps)
+                    return true;
+                break;
+            default:
+                break;
+            }
+            pit.next();
+        }
+        return false;
+    }
+
+    /**
      * Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner.
      * @param polygonNodes list of nodes from polygon path.
@@ -778 +812 @@
      *
      * @param p1 first point
-     * @param p2 Common endpoint
+     * @param common Common end point
      * @param p3 third point
      * @return Angle in radians (-pi, pi]
      */
-    public static double getCornerAngle(EastNorth p1, EastNorth p2, EastNorth p3) {
+    public static double getCornerAngle(EastNorth p1, EastNorth common, EastNorth p3) {
 
         CheckParameterUtil.ensure(p1, "p1", EastNorth::isValid);
-        CheckParameterUtil.ensure(p2, "p2", EastNorth::isValid);
+        CheckParameterUtil.ensure(common, "p2", EastNorth::isValid);
         CheckParameterUtil.ensure(p3, "p3", EastNorth::isValid);
 
-        Double result = getSegmentAngle(p2, p1) - getSegmentAngle(p2, p3);
+        double result = getSegmentAngle(common, p1) - getSegmentAngle(common, p3);
         if (result <= -Math.PI) {
             result += 2 * Math.PI;

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

@@ -3 +3 @@
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
 
 import java.io.FileInputStream;
@@ -159 +160 @@
         assertEquals(new EastNorth(150, 266d + 2d/3d), Geometry.getCentroidEN(Arrays.asList(en1, en2, en3)));
     }
+
+
+    /**
+     * Test of {@link Geometry#polygonIntersection} method with two triangles.
+     */
+    @Test
+    public void testPolygonIntersectionTriangles() {
+        Node node1 = new Node(new LatLon(0.0, 1.0));
+        Node node2 = new Node(new LatLon(0.0, 2.0));
+        Node node3 = new Node(new LatLon(5.0, 1.5));
+        List<Node> poly1 = Arrays.asList(node1, node2, node3, node1);
+        Node node4 = new Node(new LatLon(10.0, 1.0));
+        Node node5 = new Node(new LatLon(10.0, 2.0));
+        Node node6 = new Node(new LatLon(5.000001, 1.5));
+        List<Node> poly2 = Arrays.asList(node4, node5, node6, node4);
+        // no intersection, not even touching
+        assertEquals(Geometry.PolygonIntersection.OUTSIDE, Geometry.polygonIntersection(poly1, poly2));
+
+        node5.setCoor(new LatLon(5.0, 1.5));
+        // touching in a single point with two different nodes
+        assertEquals(Geometry.PolygonIntersection.OUTSIDE, Geometry.polygonIntersection(poly1, poly2));
+
+        node5.setCoor(new LatLon(4.99999999, 1.5));
+        // now node5 lies inside way1, intersection is a very small area, in OSM precision nodes are equal
+        assertEquals(node5.getCoor().getRoundedToOsmPrecision(), node3.getCoor().getRoundedToOsmPrecision());
+        assertEquals(Geometry.PolygonIntersection.CROSSING, Geometry.polygonIntersection(poly1, poly2));
+
+        node5.setCoor(new LatLon(4.9999999, 1.5));
+        // intersection area is too big to ignore
+        assertNotEquals(node5.getCoor().getRoundedToOsmPrecision(), node3.getCoor().getRoundedToOsmPrecision());
+        assertEquals(Geometry.PolygonIntersection.CROSSING, Geometry.polygonIntersection(poly1, poly2));
+    }
+
+    /**
+     * Test of {@link Geometry#polygonIntersection} method with two V-shapes
+     */
+    @Test
+    public void testPolygonIntersectionVShapes() {
+        Node node1 = new Node(new LatLon(1.0, 1.0));
+        Node node2 = new Node(new LatLon(2.0, 2.0));
+        Node node3 = new Node(new LatLon(0.9, 1.0));
+        Node node4 = new Node(new LatLon(2.0, 0.0));
+        List<Node> poly1 = Arrays.asList(node1, node2, node3, node4, node1);
+        Node node5 = new Node(new LatLon(3.0, 1.0));
+        Node node6 = new Node(new LatLon(2.0, 2.0)); // like node2
+        Node node7 = new Node(new LatLon(3.1, 1.0));
+        Node node8 = new Node(new LatLon(2.0, 0.0)); // like node4
+        List<Node> poly2 = Arrays.asList(node5, node6, node7, node8, node5);
+
+        // touching in two points but not overlapping
+        assertEquals(Geometry.PolygonIntersection.OUTSIDE, Geometry.polygonIntersection(poly1, poly2));
+
+        // touching in one point, small overlap at the other
+        node6.setCoor(new LatLon(1.9999999, 2.0));
+        assertEquals(Geometry.PolygonIntersection.CROSSING, Geometry.polygonIntersection(poly1, poly2));
+
+        // two small overlaps, but clearly visible because lines are crossing
+        node6.setCoor(new LatLon(1.99999999, 2.0));
+        node8.setCoor(new LatLon(1.99999999, 0.0));
+        assertEquals(Geometry.PolygonIntersection.OUTSIDE, Geometry.polygonIntersection(poly1, poly2));
+    }
 }