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