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