001// License: GPL. See LICENSE file for details.
002package org.openstreetmap.josm.data.validation.tests;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005
006import java.util.Collection;
007import java.util.HashSet;
008import java.util.LinkedList;
009import java.util.List;
010import java.util.Set;
011
012import org.openstreetmap.josm.data.osm.Node;
013import org.openstreetmap.josm.data.osm.OsmPrimitive;
014import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
015import org.openstreetmap.josm.data.osm.QuadBuckets;
016import org.openstreetmap.josm.data.osm.Relation;
017import org.openstreetmap.josm.data.osm.RelationMember;
018import org.openstreetmap.josm.data.osm.Way;
019import org.openstreetmap.josm.data.validation.Severity;
020import org.openstreetmap.josm.data.validation.Test;
021import org.openstreetmap.josm.data.validation.TestError;
022import org.openstreetmap.josm.tools.FilteredCollection;
023import org.openstreetmap.josm.tools.Geometry;
024import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
025import org.openstreetmap.josm.tools.Predicate;
026
027/**
028 * Checks for building areas inside of buildings
029 * @since 4409
030 */
031public class BuildingInBuilding extends Test {
032
033    protected static final int BUILDING_INSIDE_BUILDING = 2001;
034    private final List<OsmPrimitive> primitivesToCheck = new LinkedList<OsmPrimitive>();
035    private final QuadBuckets<Way> index = new QuadBuckets<Way>();
036
037    /**
038     * Constructs a new {@code BuildingInBuilding} test.
039     */
040    public BuildingInBuilding() {
041        super(tr("Building inside building"), tr("Checks for building areas inside of buildings."));
042    }
043
044    @Override
045    public void visit(Node n) {
046        if (n.isUsable() && isBuilding(n)) {
047            primitivesToCheck.add(n);
048        }
049    }
050
051    @Override
052    public void visit(Way w) {
053        if (w.isUsable() && w.isClosed() && isBuilding(w)) {
054            primitivesToCheck.add(w);
055            index.add(w);
056        }
057    }
058
059    @Override
060    public void visit(Relation r) {
061        if (r.isUsable() && r.isMultipolygon() && isBuilding(r)) {
062            primitivesToCheck.add(r);
063            for (RelationMember m : r.getMembers()) {
064                if (m.getRole().equals("outer") && m.getType().equals(OsmPrimitiveType.WAY)) {
065                    index.add(m.getWay());
066                }
067            }
068        }
069    }
070
071    private static boolean isInPolygon(Node n, List<Node> polygon) {
072        return Geometry.nodeInsidePolygon(n, polygon);
073    }
074
075    protected class MultiPolygonMembers {
076        private final Set<Way> outers = new HashSet<Way>();
077        private final Set<Way> inners = new HashSet<Way>();
078        public MultiPolygonMembers(Relation multiPolygon) {
079            for (RelationMember m : multiPolygon.getMembers()) {
080                if (m.getType().equals(OsmPrimitiveType.WAY)) {
081                    if (m.getRole().equals("outer")) {
082                        outers.add(m.getWay());
083                    } else if (m.getRole().equals("inner")) {
084                        inners.add(m.getWay());
085                    }
086                }
087            }
088        }
089    }
090
091    protected boolean sameLayers(Way w1, Way w2) {
092        String l1 = w1.get("layer") != null ? w1.get("layer") : "0";
093        String l2 = w2.get("layer") != null ? w2.get("layer") : "0";
094        return l1.equals(l2);
095    }
096
097    protected boolean isWayInsideMultiPolygon(Way object, Relation multiPolygon) {
098        // Extract outer/inner members from multipolygon
099        MultiPolygonMembers mpm = new MultiPolygonMembers(multiPolygon);
100        // Test if object is inside an outer member
101        for (Way out : mpm.outers) {
102            PolygonIntersection inter = Geometry.polygonIntersection(object.getNodes(), out.getNodes());
103            if (inter == PolygonIntersection.FIRST_INSIDE_SECOND || inter == PolygonIntersection.CROSSING) {
104                boolean insideInner = false;
105                // If inside an outer, check it is not inside an inner
106                for (Way in : mpm.inners) {
107                    if (Geometry.polygonIntersection(in.getNodes(), out.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND &&
108                        Geometry.polygonIntersection(object.getNodes(), in.getNodes()) == PolygonIntersection.FIRST_INSIDE_SECOND) {
109                        insideInner = true;
110                        break;
111                    }
112                }
113                // Inside outer but not inside inner -> the building appears to be inside a buiding
114                if (!insideInner) {
115                    // Final check on "layer" tag. Buildings of different layers may be superposed
116                    if (sameLayers(object, out)) {
117                        return true;
118                    }
119                }
120            }
121        }
122        return false;
123    }
124
125    @Override
126    public void endTest() {
127        for (final OsmPrimitive p : primitivesToCheck) {
128            Collection<Way> outers = new FilteredCollection<Way>(index.search(p.getBBox()), new Predicate<Way>() {
129
130                protected boolean evaluateNode(Node n, Way object) {
131                    return isInPolygon(n, object.getNodes()) || object.getNodes().contains(n);
132                }
133
134                protected boolean evaluateWay(Way w, Way object) {
135                    if (w.equals(object)) return false;
136
137                    // Get all multipolygons referencing object
138                    Collection<OsmPrimitive> buildingMultiPolygons = new FilteredCollection<OsmPrimitive>(object.getReferrers(), new Predicate<OsmPrimitive>() {
139                        @Override
140                        public boolean evaluate(OsmPrimitive object) {
141                            return primitivesToCheck.contains(object);
142                        }
143                    }) ;
144
145                    // if there's none, test if w is inside object
146                    if (buildingMultiPolygons.isEmpty()) {
147                        PolygonIntersection inter = Geometry.polygonIntersection(w.getNodes(), object.getNodes());
148                        // Final check on "layer" tag. Buildings of different layers may be superposed
149                        return (inter == PolygonIntersection.FIRST_INSIDE_SECOND || inter == PolygonIntersection.CROSSING) && sameLayers(w, object);
150                    } else {
151                        // Else, test if w is inside one of the multipolygons
152                        for (OsmPrimitive bmp : buildingMultiPolygons) {
153                            if (bmp instanceof Relation && isWayInsideMultiPolygon(w, (Relation) bmp)) {
154                                return true;
155                            }
156                        }
157                        return false;
158                    }
159                }
160
161                protected boolean evaluateRelation(Relation r, Way object) {
162                    MultiPolygonMembers mpm = new MultiPolygonMembers((Relation) p);
163                    for (Way out : mpm.outers) {
164                        if (evaluateWay(out, object)) {
165                            return true;
166                        }
167                    }
168                    return false;
169                }
170
171                @Override
172                public boolean evaluate(Way object) {
173                    if (p.equals(object))
174                        return false;
175                    else if (p instanceof Node)
176                        return evaluateNode((Node) p, object);
177                    else if (p instanceof Way)
178                        return evaluateWay((Way) p, object);
179                    else if (p instanceof Relation)
180                        return evaluateRelation((Relation) p, object);
181                    return false;
182                }
183            });
184
185            if (!outers.isEmpty()) {
186                errors.add(new TestError(this, Severity.WARNING,
187                        tr("Building inside building"), BUILDING_INSIDE_BUILDING, p));
188            }
189        }
190        
191        primitivesToCheck.clear();
192        index.clear();
193
194        super.endTest();
195    }
196}