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