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