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