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