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

Timestamp:

2012-09-30T22:47:57+02:00 (12 years ago)

Author:

Don-vip

Message:

fix #7034, fix #8067 - Rework "Building inside Building" test from scratch

Location:

trunk/src/org/openstreetmap/josm

Files:

• data/validation/tests/BuildingInBuilding.java (modified) (5 diffs)
• tools/Geometry.java (modified) (3 diffs)

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

@@ -5 +5 @@
 
 import java.util.Collection;
+import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Set;
 
-import org.openstreetmap.josm.data.coor.LatLon;
 import org.openstreetmap.josm.data.osm.Node;
 import org.openstreetmap.josm.data.osm.OsmPrimitive;
@@ -21 +22 @@
 import org.openstreetmap.josm.tools.FilteredCollection;
 import org.openstreetmap.josm.tools.Geometry;
+import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
 import org.openstreetmap.josm.tools.Predicate;
 
@@ -48 +50 @@
     }
 
+    @Override
+    public void visit(Relation r) {
+        if (r.isUsable() && r.isMultipolygon() && isBuilding(r)) {
+            primitivesToCheck.add(r);
+            for (RelationMember m : r.getMembers()) {
+                if (m.getRole().equals("outer") && m.getType().equals(OsmPrimitiveType.WAY)) {
+                    index.add(m.getWay());
+                }
+            }
+        }
+    }
+
     private static boolean isInPolygon(Node n, List<Node> polygon) {
         return Geometry.nodeInsidePolygon(n, polygon);
     }
 
-    /**
-     * Return true if w is in polygon.
-     */
-    private static boolean isInPolygon(Way w, List<Node> polygon) {
-        // Check that all nodes of w are in polygon
-        for (Node n : w.getNodes()) {
-            if (!isInPolygon(n, polygon))
-                return false;
+    protected class MultiPolygonMembers {
+        public final Set<Way> outers = new HashSet<Way>();
+        public final Set<Way> inners = new HashSet<Way>();
+        public MultiPolygonMembers(Relation multiPolygon) {
+            for (RelationMember m : multiPolygon.getMembers()) {
+                if (m.getType().equals(OsmPrimitiveType.WAY)) {
+                    if (m.getRole().equals("outer")) {
+                        outers.add(m.getWay());
+                    } else if (m.getRole().equals("inner")) {
+                        inners.add(m.getWay());
+                    }
+                }
+            }
         }
-        // All nodes can be inside polygon and still, w outside:
-        //            +-------------+
-        //           /|             |
-        //          / |             |
-        //         /  |             |
-        //        / w |             |
-        //  +----+----+             |
-        //  |       polygon         |
-        //  |_______________________|
-        //
-        for (int i=1; i<w.getNodesCount(); i++) {
-            LatLon center = w.getNode(i).getCoor().getCenter(w.getNode(i-1).getCoor());
-            if (center != null && !isInPolygon(new Node(center), polygon))
-                return false;
+    }
+    
+    protected boolean sameLayers(Way w1, Way w2) {
+        String l1 = w1.get("layer") != null ? w1.get("layer") : "0";
+        String l2 = w2.get("layer") != null ? w2.get("layer") : "0";
+        return l1.equals(l2);
+    }
+    
+    protected boolean isWayInsideMultiPolygon(Way object, Relation multiPolygon) {
+        // Extract outer/inner members from multipolygon
+        MultiPolygonMembers mpm = new MultiPolygonMembers(multiPolygon);
+        // Test if object is inside an outer member
+        for (Way out : mpm.outers) {
+            PolygonIntersection inter = Geometry.polygonIntersection(object.getNodes(), out.getNodes());
+            if (inter == PolygonIntersection.FIRST_INSIDE_SECOND || inter == PolygonIntersection.CROSSING) {
+                boolean insideInner = false;
+                // If inside an outer, check it is not inside an inner
+                for (Way in : mpm.inners) {
+                    if (Geometry.polygonIntersection(in.getNodes(), out.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND &&
+                        Geometry.polygonIntersection(object.getNodes(), in.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND) {
+                        insideInner = true;
+                        break;
+                    }
+                }
+                // Inside outer but not inside inner -> the building appears to be inside a buiding
+                if (!insideInner) {
+                    // Final check on "layer" tag. Buildings of different layers may be superposed
+                    if (sameLayers(object, out)) {
+                        return true;
+                    }
+                }
+            }
         }
-        return true;
+        return false;
     }
-
+    
     @Override
     public void endTest() {
         for (final OsmPrimitive p : primitivesToCheck) {
             Collection<Way> outers = new FilteredCollection<Way>(index.search(p.getBBox()), new Predicate<Way>() {
+                
+                protected boolean evaluateNode(Node n, Way object) {
+                    return isInPolygon(n, object.getNodes()) || object.getNodes().contains(n);
+                }
+                
+                protected boolean evaluateWay(Way w, Way object) {
+                    if (w.equals(object)) return false;
+                    
+                    // Get all multipolygons referencing object
+                    Collection<OsmPrimitive> buildingMultiPolygons = new FilteredCollection<OsmPrimitive>(object.getReferrers(), new Predicate<OsmPrimitive>() {
+                        @Override
+                        public boolean evaluate(OsmPrimitive object) {
+                            return primitivesToCheck.contains(object);
+                        }
+                    }) ;
+                    
+                    // if there's none, test if w is inside object
+                    if (buildingMultiPolygons.isEmpty()) {
+                        PolygonIntersection inter = Geometry.polygonIntersection(w.getNodes(), object.getNodes());
+                        // Final check on "layer" tag. Buildings of different layers may be superposed
+                        return (inter == PolygonIntersection.FIRST_INSIDE_SECOND || inter == PolygonIntersection.CROSSING) && sameLayers(w, object);
+                    } else {
+                        // Else, test if w is inside one of the multipolygons
+                        for (OsmPrimitive bmp : buildingMultiPolygons) {
+                            if (bmp instanceof Relation) {
+                                if (isWayInsideMultiPolygon(w, (Relation) bmp)) {
+                                    return true;
+                                }
+                            }
+                        }
+                        return false;
+                    }
+                }
+                
+                protected boolean evaluateRelation(Relation r, Way object) {
+                    MultiPolygonMembers mpm = new MultiPolygonMembers((Relation) p);
+                    for (Way out : mpm.outers) {
+                        if (evaluateWay(out, object)) {
+                            return true;
+                        }
+                    }
+                    return false;
+                }
+                
                 @Override
                 public boolean evaluate(Way object) {
@@ -88 +169 @@
                         return false;
                     else if (p instanceof Node)
-                        return isInPolygon((Node) p, object.getNodes()) || object.getNodes().contains(p);
+                        return evaluateNode((Node) p, object);
                     else if (p instanceof Way)
-                        return isInPolygon((Way) p, object.getNodes()) && !isInInnerWay((Way)p, object);
-                    else
-                        return false;
+                        return evaluateWay((Way) p, object);
+                    else if (p instanceof Relation)
+                        return evaluateRelation((Relation) p, object);
+                    return false;
                 }
             });
+            
             if (!outers.isEmpty()) {
                 errors.add(new TestError(this, Severity.WARNING,
@@ -103 +186 @@
         super.endTest();
     }
-
-    private boolean isInInnerWay(Way w, Way outer) {
-        for (OsmPrimitive r : outer.getReferrers()) {
-            if (r instanceof Relation && ((Relation)r).isMultipolygon()) {
-                for (RelationMember m : ((Relation)r).getMembers()) {
-                    if (m.hasRole() && m.getRole().equals("inner") && m.getType().equals(OsmPrimitiveType.WAY)) {
-                        // Only check inner ways actually inside the current outer
-                        Way inner = m.getWay();
-                        if (isInPolygon(inner, outer.getNodes())) {
-                            // If the tested way is inside this inner, outer is a false positive
-                            if (isInPolygon(w, inner.getNodes()))
-                                return true;
-                        }
-                    }
-                }
-            }
-        }
-        return false;
-    }
 }

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.math.BigDecimal;
 import java.math.MathContext;
 import java.util.ArrayList;
 import java.util.Comparator;
-import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -369 +371 @@
     }
 
+    private static Area getArea(List<Node> polygon) {
+        Path2D path = new Path2D.Double();
+
+        boolean begin = true;
+        for (Node n : polygon) {
+            if (begin) {
+                path.moveTo(n.getEastNorth().getX(), n.getEastNorth().getY());
+                begin = false;
+            } else {
+                path.lineTo(n.getEastNorth().getX(), n.getEastNorth().getY());
+            }
+        }
+        path.closePath();
+        
+        return new Area(path);
+    }
+    
     /**
      * Tests if two polygons intersect.
@@ -374 +393 @@
      * @param second
      * @return intersection kind
-     * TODO: test segments, not only points
-     * TODO: is O(N*M), should use sweep for better performance.
      */
     public static PolygonIntersection polygonIntersection(List<Node> first, List<Node> second) {
-        Set<Node> firstSet = new HashSet<Node>(first);
-        Set<Node> secondSet = new HashSet<Node>(second);
-
-        int nodesInsideSecond = 0;
-        int nodesOutsideSecond = 0;
-        int nodesInsideFirst = 0;
-        int nodesOutsideFirst = 0;
-
-        for (Node insideNode : first) {
-            if (secondSet.contains(insideNode)) {
-                continue;
-                //ignore touching nodes.
-            }
-
-            if (nodeInsidePolygon(insideNode, second)) {
-                nodesInsideSecond ++;
-            }
-            else {
-                nodesOutsideSecond ++;
-            }
-        }
-
-        for (Node insideNode : second) {
-            if (firstSet.contains(insideNode)) {
-                continue;
-                //ignore touching nodes.
-            }
-
-            if (nodeInsidePolygon(insideNode, first)) {
-                nodesInsideFirst ++;
-            }
-            else {
-                nodesOutsideFirst ++;
-            }
-        }
-
-        if (nodesInsideFirst == 0) {
-            if (nodesInsideSecond == 0){
-                if (nodesOutsideFirst + nodesInsideSecond > 0)
-                    return PolygonIntersection.OUTSIDE;
-                else
-                    //all nodes common
-                    return PolygonIntersection.CROSSING;
-            } else
-                return PolygonIntersection.FIRST_INSIDE_SECOND;
-        }
-        else
-        {
-            if (nodesInsideSecond == 0)
-                return PolygonIntersection.SECOND_INSIDE_FIRST;
-            else
-                return PolygonIntersection.CROSSING;
+        
+        Area a1 = getArea(first);
+        Area a2 = getArea(second);
+        
+        Area inter = new Area(a1);
+        inter.intersect(a2);
+        
+        Rectangle bounds = inter.getBounds();
+        
+        if (inter.isEmpty() || bounds.getHeight()*bounds.getWidth() <= 1.0) {
+            return PolygonIntersection.OUTSIDE;
+        } else if (inter.equals(a1)) {
+            return PolygonIntersection.FIRST_INSIDE_SECOND;
+        } else if (inter.equals(a2)) {
+            return PolygonIntersection.SECOND_INSIDE_FIRST;
+        } else {
+            return PolygonIntersection.CROSSING;
         }
     }