source: josm/trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java @ 12941

Last change on this file since 12941 was 12941, checked in by GerdP, 18 months ago

fix #14766 - Self-intersection check not working for multipolygons

The test failed to detect self-intersecting rings formed by multiple ways.
This is now handled. Single self-intersecting ways are still only handled by SelfIntersectingWay to avoind duplicate warnings for the same issue.

  • Property svn:eol-style set to native
File size: 40.6 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.validation.tests;
3
4import static org.openstreetmap.josm.tools.I18n.marktr;
5import static org.openstreetmap.josm.tools.I18n.tr;
6import static org.openstreetmap.josm.tools.I18n.trn;
7
8import java.awt.geom.Area;
9import java.awt.geom.Point2D;
10import java.util.ArrayList;
11import java.util.Arrays;
12import java.util.Collection;
13import java.util.HashMap;
14import java.util.HashSet;
15import java.util.List;
16import java.util.Map;
17import java.util.Map.Entry;
18import java.util.Set;
19
20import org.openstreetmap.josm.command.ChangeCommand;
21import org.openstreetmap.josm.command.Command;
22import org.openstreetmap.josm.data.coor.EastNorth;
23import org.openstreetmap.josm.data.osm.DefaultNameFormatter;
24import org.openstreetmap.josm.data.osm.Node;
25import org.openstreetmap.josm.data.osm.OsmPrimitive;
26import org.openstreetmap.josm.data.osm.Relation;
27import org.openstreetmap.josm.data.osm.RelationMember;
28import org.openstreetmap.josm.data.osm.Way;
29import org.openstreetmap.josm.data.osm.WaySegment;
30import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
31import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData;
32import org.openstreetmap.josm.data.validation.OsmValidator;
33import org.openstreetmap.josm.data.validation.Severity;
34import org.openstreetmap.josm.data.validation.Test;
35import org.openstreetmap.josm.data.validation.TestError;
36import org.openstreetmap.josm.gui.mappaint.ElemStyles;
37import org.openstreetmap.josm.gui.mappaint.MapPaintStyles;
38import org.openstreetmap.josm.gui.mappaint.styleelement.AreaElement;
39import org.openstreetmap.josm.gui.progress.ProgressMonitor;
40import org.openstreetmap.josm.tools.Geometry;
41import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
42import org.openstreetmap.josm.tools.Logging;
43
44/**
45 * Checks if multipolygons are valid
46 * @since 3669
47 */
48public class MultipolygonTest extends Test {
49
50    /** Non-Way in multipolygon */
51    public static final int WRONG_MEMBER_TYPE = 1601;
52    /** No useful role for multipolygon member */
53    public static final int WRONG_MEMBER_ROLE = 1602;
54    /** Multipolygon is not closed */
55    public static final int NON_CLOSED_WAY = 1603;
56    /** No outer way for multipolygon */
57    public static final int MISSING_OUTER_WAY = 1604;
58    /** Multipolygon inner way is outside */
59    public static final int INNER_WAY_OUTSIDE = 1605;
60    /** Intersection between multipolygon ways */
61    public static final int CROSSING_WAYS = 1606;
62    /** Style for outer way mismatches / With the currently used mappaint style(s) the style for outer way mismatches the area style */
63    public static final int OUTER_STYLE_MISMATCH = 1607;
64    /** With the currently used mappaint style the style for inner way equals the multipolygon style */
65    public static final int INNER_STYLE_MISMATCH = 1608;
66    /** Area style way is not closed */
67    public static final int NOT_CLOSED = 1609;
68    /** No area style for multipolygon */
69    public static final int NO_STYLE = 1610;
70    /** Multipolygon relation should be tagged with area tags and not the outer way(s) */
71    public static final int NO_STYLE_POLYGON = 1611;
72    /** Area style on outer way */
73    public static final int OUTER_STYLE = 1613;
74    /** Multipolygon member repeated (same primitive, same role */
75    public static final int REPEATED_MEMBER_SAME_ROLE = 1614;
76    /** Multipolygon member repeated (same primitive, different role) */
77    public static final int REPEATED_MEMBER_DIFF_ROLE = 1615;
78    /** Multipolygon ring is equal to another ring */
79    public static final int EQUAL_RINGS = 1616;
80    /** Multipolygon rings share nodes */
81    public static final int RINGS_SHARE_NODES = 1617;
82
83    private static final int FOUND_INSIDE = 1;
84    private static final int FOUND_OUTSIDE = 2;
85
86    private final Set<String> keysCheckedByAnotherTest = new HashSet<>();
87
88    /**
89     * Constructs a new {@code MultipolygonTest}.
90     */
91    public MultipolygonTest() {
92        super(tr("Multipolygon"),
93                tr("This test checks if multipolygons are valid."));
94    }
95
96    @Override
97    public void startTest(ProgressMonitor progressMonitor) {
98        super.startTest(progressMonitor);
99        keysCheckedByAnotherTest.clear();
100        for (Test t : OsmValidator.getEnabledTests(false)) {
101            if (t instanceof UnclosedWays) {
102                keysCheckedByAnotherTest.addAll(((UnclosedWays) t).getCheckedKeys());
103                break;
104            }
105        }
106    }
107
108    @Override
109    public void endTest() {
110        keysCheckedByAnotherTest.clear();
111        super.endTest();
112    }
113
114    @Override
115    public void visit(Way w) {
116        if (!w.isArea() && ElemStyles.hasOnlyAreaElements(w)) {
117            List<Node> nodes = w.getNodes();
118            if (nodes.isEmpty()) return; // fix zero nodes bug
119            for (String key : keysCheckedByAnotherTest) {
120                if (w.hasKey(key)) {
121                    return;
122                }
123            }
124            errors.add(TestError.builder(this, Severity.WARNING, NOT_CLOSED)
125                    .message(tr("Area style way is not closed"))
126                    .primitives(w)
127                    .highlight(Arrays.asList(nodes.get(0), nodes.get(nodes.size() - 1)))
128                    .build());
129        }
130    }
131
132    @Override
133    public void visit(Relation r) {
134        if (r.isMultipolygon() && r.getMembersCount() > 0) {
135            checkMembersAndRoles(r);
136            checkOuterWay(r);
137            boolean hasRepeatedMembers = checkRepeatedWayMembers(r);
138            // Rest of checks is only for complete multipolygon
139            if (!hasRepeatedMembers && !r.hasIncompleteMembers()) {
140                Multipolygon polygon = new Multipolygon(r);
141                checkStyleConsistency(r, polygon);
142                checkGeometryAndRoles(r, polygon);
143            }
144        }
145    }
146
147    /**
148     * Checks that multipolygon has at least an outer way:<ul>
149     * <li>{@link #MISSING_OUTER_WAY}: No outer way for multipolygon</li>
150     * </ul>
151     * @param r relation
152     */
153    private void checkOuterWay(Relation r) {
154        for (RelationMember m : r.getMembers()) {
155            if (m.isWay() && "outer".equals(m.getRole())) {
156                return;
157            }
158        }
159        errors.add(TestError.builder(this, Severity.WARNING, MISSING_OUTER_WAY)
160                .message(r.isBoundary() ? tr("No outer way for boundary") : tr("No outer way for multipolygon"))
161                .primitives(r)
162                .build());
163    }
164
165    /**
166     * Various style-related checks:<ul>
167     * <li>{@link #NO_STYLE_POLYGON}: Multipolygon relation should be tagged with area tags and not the outer way</li>
168     * <li>{@link #INNER_STYLE_MISMATCH}: With the currently used mappaint style the style for inner way equals the multipolygon style</li>
169     * <li>{@link #OUTER_STYLE_MISMATCH}: Style for outer way mismatches</li>
170     * <li>{@link #OUTER_STYLE}: Area style on outer way</li>
171     * </ul>
172     * @param r relation
173     * @param polygon multipolygon
174     */
175    private void checkStyleConsistency(Relation r, Multipolygon polygon) {
176        ElemStyles styles = MapPaintStyles.getStyles();
177        if (styles != null && !r.isBoundary()) {
178            AreaElement area = ElemStyles.getAreaElemStyle(r, false);
179            boolean areaStyle = area != null;
180            // If area style was not found for relation then use style of ways
181            if (area == null) {
182                for (Way w : polygon.getOuterWays()) {
183                    area = ElemStyles.getAreaElemStyle(w, true);
184                    if (area != null) {
185                        break;
186                    }
187                }
188                if (area == null) {
189                    errors.add(TestError.builder(this, Severity.OTHER, NO_STYLE)
190                            .message(tr("No area style for multipolygon"))
191                            .primitives(r)
192                            .build());
193                } else {
194                    /* old style multipolygon - solve: copy tags from outer way to multipolygon */
195                    errors.add(TestError.builder(this, Severity.ERROR, NO_STYLE_POLYGON)
196                            .message(trn("Multipolygon relation should be tagged with area tags and not the outer way",
197                                    "Multipolygon relation should be tagged with area tags and not the outer ways",
198                                    polygon.getOuterWays().size()))
199                            .primitives(r)
200                            .build());
201                }
202            }
203
204            if (area != null) {
205                for (Way wInner : polygon.getInnerWays()) {
206                    if (area.equals(ElemStyles.getAreaElemStyle(wInner, false))) {
207                        errors.add(TestError.builder(this, Severity.OTHER, INNER_STYLE_MISMATCH)
208                                .message(tr("With the currently used mappaint style the style for inner way equals the multipolygon style"))
209                                .primitives(Arrays.asList(r, wInner))
210                                .highlight(wInner)
211                                .build());
212                    }
213                }
214                for (Way wOuter : polygon.getOuterWays()) {
215                    AreaElement areaOuter = ElemStyles.getAreaElemStyle(wOuter, false);
216                    if (areaOuter != null) {
217                        if (!area.equals(areaOuter)) {
218                            String message = !areaStyle ? tr("Style for outer way mismatches")
219                                    : tr("With the currently used mappaint style(s) the style for outer way mismatches the area style");
220                            errors.add(TestError.builder(this, Severity.OTHER, OUTER_STYLE_MISMATCH)
221                                    .message(message)
222                                    .primitives(Arrays.asList(r, wOuter))
223                                    .highlight(wOuter)
224                                    .build());
225                        } else if (areaStyle) { /* style on outer way of multipolygon, but equal to polygon */
226                            errors.add(TestError.builder(this, Severity.WARNING, OUTER_STYLE)
227                                    .message(tr("Area style on outer way"))
228                                    .primitives(Arrays.asList(r, wOuter))
229                                    .highlight(wOuter)
230                                    .build());
231                        }
232                    }
233                }
234            }
235        }
236    }
237
238    /**
239     * Various geometry-related checks:<ul>
240     * <li>{@link #NON_CLOSED_WAY}: Multipolygon is not closed</li>
241     * <li>{@link #INNER_WAY_OUTSIDE}: Multipolygon inner way is outside</li>
242     * <li>{@link #CROSSING_WAYS}: Intersection between multipolygon ways</li>
243     * </ul>
244     * @param r relation
245     * @param polygon multipolygon
246     */
247    private void checkGeometryAndRoles(Relation r, Multipolygon polygon) {
248        int oldErrorsSize = errors.size();
249
250        List<Node> openNodes = polygon.getOpenEnds();
251        if (!openNodes.isEmpty()) {
252            errors.add(TestError.builder(this, Severity.ERROR, NON_CLOSED_WAY)
253                    .message(tr("Multipolygon is not closed"))
254                    .primitives(combineRelAndPrimitives(r, openNodes))
255                    .highlight(openNodes)
256                    .build());
257        }
258        Map<Long, RelationMember> wayMap = new HashMap<>();
259        for (int i = 0; i < r.getMembersCount(); i++) {
260            RelationMember mem = r.getMember(i);
261            if (!mem.isWay())
262                continue;
263            wayMap.put(mem.getWay().getUniqueId(), mem); // duplicate members were checked before
264        }
265        if (wayMap.isEmpty())
266            return;
267
268        Set<Node> sharedNodes = findIntersectionNodes(r);
269        List<PolyData> innerPolygons = polygon.getInnerPolygons();
270        List<PolyData> outerPolygons = polygon.getOuterPolygons();
271        List<PolyData> allPolygons = new ArrayList<>();
272        allPolygons.addAll(outerPolygons);
273        allPolygons.addAll(innerPolygons);
274        Map<PolyData, List<PolyData>> crossingPolyMap = findIntersectingWays(r, innerPolygons, outerPolygons);
275
276        if (!sharedNodes.isEmpty()) {
277            for (int i = 0; i < allPolygons.size(); i++) {
278                PolyData pd1 = allPolygons.get(i);
279                checkPolygonForSelfIntersection(r, pd1);
280                for (int j = i + 1; j < allPolygons.size(); j++) {
281                    PolyData pd2 = allPolygons.get(j);
282                    if (!checkProblemMap(crossingPolyMap, pd1, pd2)) {
283                        checkPolygonsForSharedNodes(r, pd1, pd2, sharedNodes);
284                    }
285                }
286            }
287        }
288        boolean checkRoles = true;
289        for (int i = oldErrorsSize; i < errors.size(); i++) {
290            if (errors.get(i).getSeverity() != Severity.OTHER) {
291                checkRoles = false;
292                break;
293            }
294        }
295        if (checkRoles) {
296            // we found no intersection or crossing between the polygons and they are closed
297            // now we can calculate the nesting level to verify the roles with some simple node checks
298            checkRoles(r, allPolygons, wayMap, sharedNodes);
299        }
300    }
301
302    /**
303     * Check if a polygon ring is self-intersecting when the ring was build from multiple ways.
304     * An self intersection in a single way is checked in {@link SelfIntersectingWay}.
305     * @param r the relation
306     * @param pd the ring
307     */
308    private void checkPolygonForSelfIntersection(Relation r, PolyData pd) {
309        if (pd.getWayIds().size() == 1)
310            return;
311        List<Node> wayNodes = pd.getNodes();
312        int num = wayNodes.size();
313        Set<Node> nodes = new HashSet<>();
314        Node firstNode = wayNodes.get(0);
315        nodes.add(firstNode);
316        List<Node> isNodes = new ArrayList<>();
317        for (int i = 1; i < num - 1; i++) {
318            Node n = wayNodes.get(i);
319            if (nodes.contains(n)) {
320                isNodes.add(n);
321            } else {
322                nodes.add(n);
323            }
324        }
325        if (!isNodes.isEmpty()) {
326            List<OsmPrimitive> prims = new ArrayList<>();
327            prims.add(r);
328            prims.addAll(isNodes);
329            errors.add(TestError.builder(this, Severity.WARNING, CROSSING_WAYS)
330                    .message(tr("Self-intersecting polygon ring"))
331                    .primitives(prims)
332                    .highlight(isNodes)
333                    .build());
334
335        }
336    }
337
338    /**
339     * Detect intersections of multipolygon ways at nodes. If any way node is used by more than two ways
340     * or two times in one way and at least once in another way we found an intersection.
341     * @param r the relation
342     * @return List of nodes were ways intersect
343     */
344    private static Set<Node> findIntersectionNodes(Relation r) {
345        Set<Node> intersectionNodes = new HashSet<>();
346        Map<Node, List<Way>> nodeMap = new HashMap<>();
347        for (RelationMember rm : r.getMembers()) {
348            if (!rm.isWay())
349                continue;
350            int numNodes = rm.getWay().getNodesCount();
351            for (int i = 0; i < numNodes; i++) {
352                Node n = rm.getWay().getNode(i);
353                if (n.getReferrers().size() <= 1) {
354                    continue; // cannot be a problem node
355                }
356                List<Way> ways = nodeMap.get(n);
357                if (ways == null) {
358                    ways = new ArrayList<>();
359                    nodeMap.put(n, ways);
360                }
361                ways.add(rm.getWay());
362                if (ways.size() > 2 || (ways.size() == 2 && i != 0 && i + 1 != numNodes)) {
363                    intersectionNodes.add(n);
364                }
365            }
366        }
367        return intersectionNodes;
368    }
369
370    private enum ExtPolygonIntersection {
371        EQUAL,
372        FIRST_INSIDE_SECOND,
373        SECOND_INSIDE_FIRST,
374        OUTSIDE,
375        CROSSING
376    }
377
378    private void checkPolygonsForSharedNodes(Relation r, PolyData pd1, PolyData pd2, Set<Node> allSharedNodes) {
379        Set<Node> sharedByPolygons = new HashSet<>(allSharedNodes);
380        sharedByPolygons.retainAll(pd1.getNodes());
381        sharedByPolygons.retainAll(pd2.getNodes());
382        if (sharedByPolygons.isEmpty())
383            return;
384
385        // the two polygons share one or more nodes
386        // 1st might be equal to 2nd (same nodes, same or different direction) --> error shared way segments
387        // they overlap --> error
388        // 1st and 2nd share segments
389        // 1st fully inside 2nd --> okay
390        // 2nd fully inside 1st --> okay
391        int errorCode = RINGS_SHARE_NODES;
392        ExtPolygonIntersection res = checkOverlapAtSharedNodes(sharedByPolygons, pd1, pd2);
393        if (res == ExtPolygonIntersection.CROSSING) {
394            errorCode = CROSSING_WAYS;
395        } else if (res == ExtPolygonIntersection.EQUAL) {
396            errorCode = EQUAL_RINGS;
397        }
398        if (errorCode != 0) {
399            Set<OsmPrimitive> prims = new HashSet<>();
400            prims.add(r);
401            for (Node n : sharedByPolygons) {
402                for (OsmPrimitive p : n.getReferrers()) {
403                    if (p instanceof Way && (pd1.getWayIds().contains(p.getUniqueId()) || pd2.getWayIds().contains(p.getUniqueId()))) {
404                        prims.add(p);
405                    }
406                }
407            }
408            if (errorCode == RINGS_SHARE_NODES) {
409                errors.add(TestError.builder(this, Severity.OTHER, errorCode)
410                        .message(tr("Multipolygon rings share node(s)"))
411                        .primitives(prims)
412                        .highlight(sharedByPolygons)
413                        .build());
414            } else {
415                errors.add(TestError.builder(this, Severity.WARNING, errorCode)
416                        .message(errorCode == CROSSING_WAYS ? tr("Intersection between multipolygon ways") : tr("Multipolygon rings are equal"))
417                        .primitives(prims)
418                        .highlight(sharedByPolygons)
419                        .build());
420            }
421        }
422    }
423
424    private static ExtPolygonIntersection checkOverlapAtSharedNodes(Set<Node> shared, PolyData pd1, PolyData pd2) {
425        // Idea: if two polygons share one or more nodes they can either just touch or share segments or intersect.
426        // The insideness test is complex, so we try to reduce the number of these tests.
427        // There is no need to check all nodes, we only have to check the node following a shared node.
428
429        int[] flags = new int[2];
430        for (int loop = 0; loop < flags.length; loop++) {
431            List<Node> nodes2Test = loop == 0 ? pd1.getNodes() : pd2.getNodes();
432            int num = nodes2Test.size() - 1; // ignore closing duplicate node
433
434
435            int lenShared = 0;
436            for (int i = 0; i < num; i++) {
437                Node n = nodes2Test.get(i);
438                if (shared.contains(n)) {
439                    ++lenShared;
440                } else {
441                    if (i == 0 || lenShared > 0) {
442                        // do we have to treat lenShared > 1 special ?
443                        lenShared = 0;
444                        boolean inside = checkIfNodeIsInsidePolygon(n, loop == 0 ? pd2 : pd1);
445                        flags[loop] |= inside ? FOUND_INSIDE : FOUND_OUTSIDE;
446                        if (flags[loop] == (FOUND_INSIDE | FOUND_OUTSIDE)) {
447                            return ExtPolygonIntersection.CROSSING;
448                        }
449                    }
450                }
451            }
452        }
453
454        if ((flags[0] & FOUND_INSIDE) != 0)
455            return ExtPolygonIntersection.FIRST_INSIDE_SECOND;
456        if ((flags[1] & FOUND_INSIDE) != 0)
457            return ExtPolygonIntersection.SECOND_INSIDE_FIRST;
458        if ((flags[0] & FOUND_OUTSIDE) != (flags[1] & FOUND_OUTSIDE)) {
459            return (flags[0] & FOUND_OUTSIDE) != 0 ?
460                ExtPolygonIntersection.SECOND_INSIDE_FIRST : ExtPolygonIntersection.FIRST_INSIDE_SECOND;
461        }
462        if ((flags[0] & FOUND_OUTSIDE) != 0 && (flags[1] & FOUND_OUTSIDE) != 0) {
463            // the two polygons may only share one or more segments but they may also intersect
464            Area a1 = new Area(pd1.get());
465            Area a2 = new Area(pd2.get());
466            PolygonIntersection areaRes = Geometry.polygonIntersection(a1, a2, 1e-6);
467            if (areaRes == PolygonIntersection.OUTSIDE)
468                return ExtPolygonIntersection.OUTSIDE;
469            return ExtPolygonIntersection.CROSSING;
470        }
471        return ExtPolygonIntersection.EQUAL;
472    }
473
474    /**
475     * Helper class for calculation of nesting levels
476     */
477    private static class PolygonLevel {
478        final int level; // nesting level, even for outer, odd for inner polygons.
479        final PolyData outerWay;
480
481        PolygonLevel(PolyData pd, int level) {
482            this.outerWay = pd;
483            this.level = level;
484        }
485    }
486
487    /**
488     * Calculate the nesting levels of the polygon rings and check if calculated role matches
489     * @param r relation (for error reporting)
490     * @param allPolygons list of polygon rings
491     * @param wayMap maps way ids to relation members
492     * @param sharedNodes all nodes shared by multiple ways of this multipolygon
493     */
494    private void checkRoles(Relation r, List<PolyData> allPolygons, Map<Long, RelationMember> wayMap, Set<Node> sharedNodes) {
495        PolygonLevelFinder levelFinder = new PolygonLevelFinder(sharedNodes);
496        List<PolygonLevel> list = levelFinder.findOuterWays(allPolygons);
497        if (list == null || list.isEmpty()) {
498            return;
499        }
500
501        for (PolygonLevel pol : list) {
502            String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner";
503            for (long wayId : pol.outerWay.getWayIds()) {
504                RelationMember member = wayMap.get(wayId);
505                if (!member.getRole().equals(calculatedRole)) {
506                    errors.add(TestError.builder(this, Severity.ERROR, WRONG_MEMBER_ROLE)
507                            .message(RelationChecker.ROLE_VERIF_PROBLEM_MSG,
508                                    marktr("Role for ''{0}'' should be ''{1}''"),
509                                    member.getMember().getDisplayName(DefaultNameFormatter.getInstance()),
510                                    calculatedRole)
511                            .primitives(Arrays.asList(r, member.getMember()))
512                            .highlight(member.getMember())
513                            .build());
514                    if (pol.level == 0 && "inner".equals(member.getRole())) {
515                        // maybe only add this error if we found an outer ring with correct role(s) ?
516                        errors.add(TestError.builder(this, Severity.ERROR, INNER_WAY_OUTSIDE)
517                                .message(tr("Multipolygon inner way is outside"))
518                                .primitives(Arrays.asList(r, member.getMember()))
519                                .highlight(member.getMember())
520                                .build());
521                    }
522                }
523            }
524        }
525    }
526
527    /**
528     * Check if a node is inside the polygon according to the insideness rules of Shape.
529     * @param n the node
530     * @param p the polygon
531     * @return true if the node is inside the polygon
532     */
533    private static boolean checkIfNodeIsInsidePolygon(Node n, PolyData p) {
534        EastNorth en = n.getEastNorth();
535        return en != null && p.get().contains(en.getX(), en.getY());
536    }
537
538    /**
539     * Determine multipolygon ways which are intersecting (crossing without a common node) or sharing one or more way segments.
540     * See also {@link CrossingWays}
541     * @param r the relation (for error reporting)
542     * @param innerPolygons list of inner polygons
543     * @param outerPolygons list of outer polygons
544     * @return map with crossing polygons
545     */
546    private Map<PolyData, List<PolyData>> findIntersectingWays(Relation r, List<PolyData> innerPolygons,
547            List<PolyData> outerPolygons) {
548        HashMap<PolyData, List<PolyData>> crossingPolygonsMap = new HashMap<>();
549        HashMap<PolyData, List<PolyData>> sharedWaySegmentsPolygonsMap = new HashMap<>();
550
551        for (int loop = 0; loop < 2; loop++) {
552            /** All way segments, grouped by cells */
553            final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
554            /** The already detected ways in error */
555            final Map<List<Way>, List<WaySegment>> problemWays = new HashMap<>(50);
556
557            Map<PolyData, List<PolyData>> problemPolygonMap = (loop == 0) ? crossingPolygonsMap
558                    : sharedWaySegmentsPolygonsMap;
559
560            for (Way w : r.getMemberPrimitives(Way.class)) {
561                findIntersectingWay(w, cellSegments, problemWays, loop == 1);
562            }
563
564            if (!problemWays.isEmpty()) {
565                List<PolyData> allPolygons = new ArrayList<>(innerPolygons.size() + outerPolygons.size());
566                allPolygons.addAll(innerPolygons);
567                allPolygons.addAll(outerPolygons);
568
569                for (Entry<List<Way>, List<WaySegment>> entry : problemWays.entrySet()) {
570                    List<Way> ways = entry.getKey();
571                    if (ways.size() != 2)
572                        continue;
573                    PolyData[] crossingPolys = new PolyData[2];
574                    boolean allInner = true;
575                    for (int i = 0; i < 2; i++) {
576                        Way w = ways.get(i);
577                        for (int j = 0; j < allPolygons.size(); j++) {
578                            PolyData pd = allPolygons.get(j);
579                            if (pd.getWayIds().contains(w.getUniqueId())) {
580                                crossingPolys[i] = pd;
581                                if (j >= innerPolygons.size())
582                                    allInner = false;
583                                break;
584                            }
585                        }
586                    }
587                    boolean samePoly = false;
588                    if (crossingPolys[0] != null && crossingPolys[1] != null) {
589                        List<PolyData> crossingPolygons = problemPolygonMap.get(crossingPolys[0]);
590                        if (crossingPolygons == null) {
591                            crossingPolygons = new ArrayList<>();
592                            problemPolygonMap.put(crossingPolys[0], crossingPolygons);
593                        }
594                        crossingPolygons.add(crossingPolys[1]);
595                        if (crossingPolys[0] == crossingPolys[1]) {
596                            samePoly = true;
597                        }
598                    }
599                    if (loop == 0 || samePoly || (loop == 1 && !allInner)) {
600                        String msg = loop == 0 ? tr("Intersection between multipolygon ways")
601                                : samePoly ? tr("Multipolygon ring contains segments twice")
602                                        : tr("Multipolygon outer way shares segment(s) with other ring");
603                        errors.add(TestError.builder(this, Severity.ERROR, CROSSING_WAYS)
604                                .message(msg)
605                                .primitives(Arrays.asList(r, ways.get(0), ways.get(1)))
606                                .highlightWaySegments(entry.getValue())
607                                .build());
608                    }
609                }
610            }
611        }
612        return crossingPolygonsMap;
613    }
614
615    /**
616     * Find ways which are crossing without sharing a node.
617     * @param w way that is member of the relation
618     * @param cellSegments map with already collected way segments
619     * @param crossingWays list to collect crossing ways
620     * @param findSharedWaySegments true: find shared way segments instead of crossings
621     */
622    private static void findIntersectingWay(Way w, Map<Point2D, List<WaySegment>> cellSegments,
623            Map<List<Way>, List<WaySegment>> crossingWays, boolean findSharedWaySegments) {
624        int nodesSize = w.getNodesCount();
625        for (int i = 0; i < nodesSize - 1; i++) {
626            final WaySegment es1 = new WaySegment(w, i);
627            final EastNorth en1 = es1.getFirstNode().getEastNorth();
628            final EastNorth en2 = es1.getSecondNode().getEastNorth();
629            if (en1 == null || en2 == null) {
630                Logging.warn("Crossing ways test (MP) skipped " + es1);
631                continue;
632            }
633            for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) {
634                for (WaySegment es2 : segments) {
635
636                    List<WaySegment> highlight;
637                    if (es2.way == w)
638                        continue; // reported by CrossingWays.SelfIntersection
639                    if (findSharedWaySegments && !es1.isSimilar(es2))
640                        continue;
641                    if (!findSharedWaySegments && !es1.intersects(es2))
642                        continue;
643
644                    List<Way> prims = Arrays.asList(es1.way, es2.way);
645                    if ((highlight = crossingWays.get(prims)) == null) {
646                        highlight = new ArrayList<>();
647                        highlight.add(es1);
648                        highlight.add(es2);
649                        crossingWays.put(prims, highlight);
650                    } else {
651                        highlight.add(es1);
652                        highlight.add(es2);
653                    }
654                }
655                segments.add(es1);
656            }
657        }
658    }
659
660    /**
661     * Check if map contains combination of two given polygons.
662     * @param problemPolyMap the map
663     * @param pd1 1st polygon
664     * @param pd2 2nd polygon
665     * @return true if the combination of polygons is found in the map
666     */
667    private static boolean checkProblemMap(Map<PolyData, List<PolyData>> problemPolyMap, PolyData pd1, PolyData pd2) {
668        List<PolyData> crossingWithFirst = problemPolyMap.get(pd1);
669        if (crossingWithFirst != null && crossingWithFirst.contains(pd2)) {
670            return true;
671        }
672        List<PolyData> crossingWith2nd = problemPolyMap.get(pd2);
673        return crossingWith2nd != null && crossingWith2nd.contains(pd1);
674    }
675
676    /**
677     * Check for:<ul>
678     * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li>
679     * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li>
680     * </ul>
681     * @param r relation
682     */
683    private void checkMembersAndRoles(Relation r) {
684        for (RelationMember rm : r.getMembers()) {
685            if (rm.isWay()) {
686                if (!(rm.hasRole("inner", "outer") || !rm.hasRole())) {
687                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE)
688                            .message(tr("No useful role for multipolygon member"))
689                            .primitives(Arrays.asList(r, rm.getMember()))
690                            .build());
691                }
692            } else {
693                if (!r.isBoundary() || !rm.hasRole("admin_centre", "label", "subarea", "land_area")) {
694                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE)
695                            .message(r.isBoundary() ? tr("Non-Way in boundary") : tr("Non-Way in multipolygon"))
696                            .primitives(Arrays.asList(r, rm.getMember()))
697                            .build());
698                }
699            }
700        }
701    }
702
703    private static Collection<? extends OsmPrimitive> combineRelAndPrimitives(Relation r, Collection<? extends OsmPrimitive> primitives) {
704        // add multipolygon in order to let user select something and fix the error
705        if (!primitives.contains(r)) {
706            List<OsmPrimitive> newPrimitives = new ArrayList<>(primitives);
707            newPrimitives.add(0, r);
708            return newPrimitives;
709        } else {
710            return primitives;
711        }
712    }
713
714    /**
715     * Check for:<ul>
716     * <li>{@link #REPEATED_MEMBER_DIFF_ROLE}: Multipolygon member(s) repeated with different role</li>
717     * <li>{@link #REPEATED_MEMBER_SAME_ROLE}: Multipolygon member(s) repeated with same role</li>
718     * </ul>
719     * @param r relation
720     * @return true if repeated members have been detected, false otherwise
721     */
722    private boolean checkRepeatedWayMembers(Relation r) {
723        boolean hasDups = false;
724        Map<OsmPrimitive, List<RelationMember>> seenMemberPrimitives = new HashMap<>();
725        for (RelationMember rm : r.getMembers()) {
726            List<RelationMember> list = seenMemberPrimitives.get(rm.getMember());
727            if (list == null) {
728                list = new ArrayList<>(2);
729                seenMemberPrimitives.put(rm.getMember(), list);
730            } else {
731                hasDups = true;
732            }
733            list.add(rm);
734        }
735        if (hasDups) {
736            List<OsmPrimitive> repeatedSameRole = new ArrayList<>();
737            List<OsmPrimitive> repeatedDiffRole = new ArrayList<>();
738            for (Entry<OsmPrimitive, List<RelationMember>> e : seenMemberPrimitives.entrySet()) {
739                List<RelationMember> visited = e.getValue();
740                if (e.getValue().size() == 1)
741                    continue;
742                // we found a duplicate member, check if the roles differ
743                boolean rolesDiffer = false;
744                RelationMember rm = visited.get(0);
745                List<OsmPrimitive> primitives = new ArrayList<>();
746                for (int i = 1; i < visited.size(); i++) {
747                    RelationMember v = visited.get(i);
748                    primitives.add(rm.getMember());
749                    if (!v.getRole().equals(rm.getRole())) {
750                        rolesDiffer = true;
751                    }
752                }
753                if (rolesDiffer) {
754                    repeatedDiffRole.addAll(primitives);
755                } else {
756                    repeatedSameRole.addAll(primitives);
757                }
758            }
759            addRepeatedMemberError(r, repeatedDiffRole, REPEATED_MEMBER_DIFF_ROLE, tr("Multipolygon member(s) repeated with different role"));
760            addRepeatedMemberError(r, repeatedSameRole, REPEATED_MEMBER_SAME_ROLE, tr("Multipolygon member(s) repeated with same role"));
761        }
762        return hasDups;
763    }
764
765    private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) {
766        if (!repeatedMembers.isEmpty()) {
767            errors.add(TestError.builder(this, Severity.ERROR, errorCode)
768                    .message(msg)
769                    .primitives(combineRelAndPrimitives(r, repeatedMembers))
770                    .highlight(repeatedMembers)
771                    .build());
772        }
773    }
774
775    @Override
776    public Command fixError(TestError testError) {
777        if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) {
778            ArrayList<OsmPrimitive> primitives = new ArrayList<>(testError.getPrimitives());
779            if (primitives.size() >= 2 && primitives.get(0) instanceof Relation) {
780                Relation oldRel = (Relation) primitives.get(0);
781                Relation newRel = new Relation(oldRel);
782                List<OsmPrimitive> repeatedPrims = primitives.subList(1, primitives.size());
783                List<RelationMember> oldMembers = oldRel.getMembers();
784
785                List<RelationMember> newMembers = new ArrayList<>();
786                HashSet<OsmPrimitive> toRemove = new HashSet<>(repeatedPrims);
787                HashSet<OsmPrimitive> found = new HashSet<>(repeatedPrims.size());
788                for (RelationMember rm : oldMembers) {
789                    if (toRemove.contains(rm.getMember())) {
790                        if (!found.contains(rm.getMember())) {
791                            found.add(rm.getMember());
792                            newMembers.add(rm);
793                        }
794                    } else {
795                        newMembers.add(rm);
796                    }
797                }
798                newRel.setMembers(newMembers);
799                return new ChangeCommand(oldRel, newRel);
800            }
801        }
802        return null;
803    }
804
805    @Override
806    public boolean isFixable(TestError testError) {
807        return testError.getCode() == REPEATED_MEMBER_SAME_ROLE;
808    }
809
810    /**
811     * Find nesting levels of polygons. Logic taken from class MultipolygonBuilder, uses different structures.
812     */
813    private static class PolygonLevelFinder {
814        private final Set<Node> sharedNodes;
815
816        PolygonLevelFinder(Set<Node> sharedNodes) {
817            this.sharedNodes = sharedNodes;
818        }
819
820        List<PolygonLevel> findOuterWays(List<PolyData> allPolygons) {
821            return findOuterWaysRecursive(0, allPolygons);
822        }
823
824        private List<PolygonLevel> findOuterWaysRecursive(int level, List<PolyData> polygons) {
825            final List<PolygonLevel> result = new ArrayList<>();
826
827            for (PolyData pd : polygons) {
828                if (processOuterWay(level, polygons, result, pd) == null) {
829                    return null;
830                }
831            }
832
833            return result;
834        }
835
836        private Object processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) {
837            List<PolyData> inners = findInnerWaysCandidates(pd, polygons);
838
839            if (inners != null) {
840                //add new outer polygon
841                PolygonLevel pol = new PolygonLevel(pd, level);
842
843                //process inner ways
844                if (!inners.isEmpty()) {
845                    List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, inners);
846                    result.addAll(innerList);
847                }
848
849                result.add(pol);
850            }
851            return result;
852        }
853
854        /**
855         * Check if polygon is an out-most ring, if so, collect the inners
856         * @param outerCandidate polygon which is checked
857         * @param polygons all polygons
858         * @return null if outerCandidate is inside any other polygon, else a list of inner polygons (which might be empty)
859         */
860        private List<PolyData> findInnerWaysCandidates(PolyData outerCandidate, List<PolyData> polygons) {
861            List<PolyData> innerCandidates = new ArrayList<>();
862
863            for (PolyData inner : polygons) {
864                if (inner == outerCandidate) {
865                    continue;
866                }
867                if (!outerCandidate.getBounds().intersects(inner.getBounds())) {
868                    continue;
869                }
870                boolean useIntersectionTest = false;
871                Node unsharedOuterNode = null;
872                Node unsharedInnerNode = getNonIntersectingNode(outerCandidate, inner);
873                if (unsharedInnerNode != null) {
874                    if (checkIfNodeIsInsidePolygon(unsharedInnerNode, outerCandidate)) {
875                        innerCandidates.add(inner);
876                    } else {
877                        // inner is not inside outerCandidate, check if it contains outerCandidate
878                        unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
879                        if (unsharedOuterNode != null) {
880                            if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
881                                return null; // outer is inside inner
882                            }
883                        } else {
884                            useIntersectionTest = true;
885                        }
886                    }
887                } else {
888                    // all nodes of inner are also nodes of outerCandidate
889                    unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
890                    if (unsharedOuterNode == null) {
891                        return null; // all nodes shared -> same ways, maybe different direction
892                    } else {
893                        if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
894                            return null; // outer is inside inner
895                        } else {
896                            useIntersectionTest = true;
897                        }
898                    }
899                }
900                if (useIntersectionTest) {
901                    PolygonIntersection res = Geometry.polygonIntersection(inner.getNodes(), outerCandidate.getNodes());
902                    if (res == PolygonIntersection.FIRST_INSIDE_SECOND)
903                        innerCandidates.add(inner);
904                    else if (res == PolygonIntersection.SECOND_INSIDE_FIRST)
905                        return null;
906                }
907            }
908            return innerCandidates;
909        }
910
911        /**
912         * Find node of pd2 which is not an intersection node with pd1.
913         * @param pd1 1st polygon
914         * @param pd2 2nd polygon
915         * @return node of pd2 which is not an intersection node with pd1 or null if none is found
916         */
917        private Node getNonIntersectingNode(PolyData pd1, PolyData pd2) {
918            for (Node n : pd2.getNodes()) {
919                if (!sharedNodes.contains(n) || !pd1.getNodes().contains(n))
920                    return n;
921            }
922            return null;
923        }
924    }
925}
Note: See TracBrowser for help on using the repository browser.