Index: trunk/src/org/openstreetmap/josm/data/osm/WaySegment.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/WaySegment.java (revision 15007)
+++ trunk/src/org/openstreetmap/josm/data/osm/WaySegment.java (revision 15008)
@@ -13,5 +13,5 @@
* The way.
*/
- public Way way;
+ public final Way way;
/**
@@ -19,5 +19,5 @@
* index lowerIndex + 1.
*/
- public int lowerIndex;
+ public final int lowerIndex;
/**
Index: trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java (revision 15007)
+++ trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java (revision 15008)
@@ -272,7 +272,6 @@
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,5 +471,5 @@
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,7 +841,5 @@
for (PolyData pd : polygons) {
- if (processOuterWay(level, polygons, result, pd) == null) {
- return null;
- }
+ processOuterWay(level, polygons, result, pd);
}
@@ -850,5 +847,5 @@
}
- private Object processOuterWay(int level, List polygons, List result, PolyData pd) {
+ private void processOuterWay(int level, List polygons, List result, PolyData pd) {
List inners = findInnerWaysCandidates(pd, polygons);
@@ -865,5 +862,4 @@
result.add(pol);
}
- return result;
}
Index: trunk/src/org/openstreetmap/josm/tools/Geometry.java
===================================================================
--- trunk/src/org/openstreetmap/josm/tools/Geometry.java (revision 15007)
+++ trunk/src/org/openstreetmap/josm/tools/Geometry.java (revision 15008)
@@ -2,8 +2,9 @@
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,4 +73,7 @@
}
+ /** 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,9 +582,9 @@
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,5 +593,5 @@
*/
public static PolygonIntersection polygonIntersection(Area a1, Area a2) {
- return polygonIntersection(a1, a2, 1.0);
+ return polygonIntersection(a1, a2, INTERSECTION_EPS_EAST_NORTH);
}
@@ -604,7 +608,5 @@
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,4 +620,36 @@
/**
+ * 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,15 +812,15 @@
*
* @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;
Index: trunk/test/unit/org/openstreetmap/josm/tools/GeometryTest.java
===================================================================
--- trunk/test/unit/org/openstreetmap/josm/tools/GeometryTest.java (revision 15007)
+++ trunk/test/unit/org/openstreetmap/josm/tools/GeometryTest.java (revision 15008)
@@ -3,4 +3,5 @@
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
import java.io.FileInputStream;
@@ -159,3 +160,64 @@
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 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 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 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 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));
+ }
}