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)) {
275                        if (hasIntersectionWay(pd2, intersectionWays))
276                            checkPolygonsForSharedNodes(r, pd1, pd2, sharedNodes);
277                    }
278                }
279            }
280        }
281        boolean checkRoles = true;
282        for (int i = oldErrorsSize; i < errors.size(); i++) {
283            if (errors.get(i).getSeverity() != Severity.OTHER) {
284                checkRoles = false;
285                break;
286            }
287        }
288        if (checkRoles) {
289            // we found no intersection or crossing between the polygons and they are closed
290            // now we can calculate the nesting level to verify the roles with some simple node checks
291            checkRoles(r, allPolygons, wayMap, sharedNodes);
292        }
293    }
294
295    /**
296     * Simple check if given ring contains way that is known to intersect.
297     * @param pd the ring
298     * @param intersectionWays the known intersection ways
299     * @return true if one or more ways are in the set of known ways
300     */
301    private static boolean hasIntersectionWay(PolyData pd, Set<Way> intersectionWays) {
302        for (Way w : intersectionWays) {
303            if (pd.getWayIds().contains(w.getUniqueId())) {
304                return true;
305            }
306        }
307        return false;
308    }
309
310    /**
311     * Check if a polygon ring is self-intersecting when the ring was build from multiple ways.
312     * An self intersection in a single way is checked in {@link SelfIntersectingWay}.
313     * @param r the relation
314     * @param pd the ring
315     */
316    private void checkPolygonForSelfIntersection(Relation r, PolyData pd) {
317        if (pd.getWayIds().size() == 1)
318            return;
319        List<Node> wayNodes = pd.getNodes();
320        int num = wayNodes.size();
321        Set<Node> nodes = new HashSet<>();
322        Node firstNode = wayNodes.get(0);
323        nodes.add(firstNode);
324        List<Node> isNodes = new ArrayList<>();
325        for (int i = 1; i < num - 1; i++) {
326            Node n = wayNodes.get(i);
327            if (nodes.contains(n)) {
328                isNodes.add(n);
329            } else {
330                nodes.add(n);
331            }
332        }
333        if (!isNodes.isEmpty()) {
334            List<OsmPrimitive> prims = new ArrayList<>();
335            prims.add(r);
336            prims.addAll(isNodes);
337            errors.add(TestError.builder(this, Severity.WARNING, CROSSING_WAYS)
338                    .message(tr("Self-intersecting polygon ring"))
339                    .primitives(prims)
340                    .highlight(isNodes)
341                    .build());
342
343        }
344    }
345
346    /**
347     * Detect intersections of multipolygon ways at nodes. If any way node is used by more than two ways
348     * or two times in one way and at least once in another way we found an intersection.
349     * @param r the relation
350     * @param sharedNodes We be filled with shared nodes
351     * @param intersectionWays We be filled with ways that have a shared node
352     */
353    private static void findIntersectionNodes(Relation r, Set<Node> sharedNodes, Set<Way> intersectionWays) {
354        Map<Node, List<Way>> nodeMap = new HashMap<>();
355        for (RelationMember rm : r.getMembers()) {
356            if (!rm.isWay())
357                continue;
358            int numNodes = rm.getWay().getNodesCount();
359            for (int i = 0; i < numNodes; i++) {
360                Node n = rm.getWay().getNode(i);
361                if (n.getReferrers().size() <= 1) {
362                    continue; // cannot be a problem node
363                }
364                List<Way> ways = nodeMap.get(n);
365                if (ways == null) {
366                    ways = new ArrayList<>();
367                    nodeMap.put(n, ways);
368                }
369                ways.add(rm.getWay());
370                if (ways.size() > 2 || (ways.size() == 2 && i != 0 && i + 1 != numNodes)) {
371                    sharedNodes.add(n);
372                    intersectionWays.addAll(ways);
373                }
374            }
375        }
376    }
377
378    private enum ExtPolygonIntersection {
379        EQUAL,
380        FIRST_INSIDE_SECOND,
381        SECOND_INSIDE_FIRST,
382        OUTSIDE,
383        CROSSING
384    }
385
386    private void checkPolygonsForSharedNodes(Relation r, PolyData pd1, PolyData pd2, Set<Node> allSharedNodes) {
387        Set<Node> sharedByPolygons = new HashSet<>(allSharedNodes);
388        sharedByPolygons.retainAll(pd1.getNodes());
389        sharedByPolygons.retainAll(pd2.getNodes());
390        if (sharedByPolygons.isEmpty())
391            return;
392
393        // the two polygons share one or more nodes
394        // 1st might be equal to 2nd (same nodes, same or different direction) --> error shared way segments
395        // they overlap --> error
396        // 1st and 2nd share segments
397        // 1st fully inside 2nd --> okay
398        // 2nd fully inside 1st --> okay
399        int errorCode = RINGS_SHARE_NODES;
400        ExtPolygonIntersection res = checkOverlapAtSharedNodes(sharedByPolygons, pd1, pd2);
401        if (res == ExtPolygonIntersection.CROSSING) {
402            errorCode = CROSSING_WAYS;
403        } else if (res == ExtPolygonIntersection.EQUAL) {
404            errorCode = EQUAL_RINGS;
405        }
406        if (errorCode != 0) {
407            Set<OsmPrimitive> prims = new HashSet<>();
408            prims.add(r);
409            for (Node n : sharedByPolygons) {
410                for (OsmPrimitive p : n.getReferrers()) {
411                    if (p instanceof Way && (pd1.getWayIds().contains(p.getUniqueId()) || pd2.getWayIds().contains(p.getUniqueId()))) {
412                        prims.add(p);
413                    }
414                }
415            }
416            if (errorCode == RINGS_SHARE_NODES) {
417                errors.add(TestError.builder(this, Severity.OTHER, errorCode)
418                        .message(tr("Multipolygon rings share node(s)"))
419                        .primitives(prims)
420                        .highlight(sharedByPolygons)
421                        .build());
422            } else {
423                errors.add(TestError.builder(this, Severity.WARNING, errorCode)
424                        .message(errorCode == CROSSING_WAYS ? tr("Intersection between multipolygon ways") : tr("Multipolygon rings are equal"))
425                        .primitives(prims)
426                        .highlight(sharedByPolygons)
427                        .build());
428            }
429        }
430    }
431
432    private static ExtPolygonIntersection checkOverlapAtSharedNodes(Set<Node> shared, PolyData pd1, PolyData pd2) {
433        // Idea: if two polygons share one or more nodes they can either just touch or share segments or intersect.
434        // The insideness test is complex, so we try to reduce the number of these tests.
435        // There is no need to check all nodes, we only have to check the node following a shared node.
436
437        int[] flags = new int[2];
438        for (int loop = 0; loop < flags.length; loop++) {
439            List<Node> nodes2Test = loop == 0 ? pd1.getNodes() : pd2.getNodes();
440            int num = nodes2Test.size() - 1; // ignore closing duplicate node
441
442
443            int lenShared = 0;
444            for (int i = 0; i < num; i++) {
445                Node n = nodes2Test.get(i);
446                if (shared.contains(n)) {
447                    ++lenShared;
448                } else {
449                    if (i == 0 || lenShared > 0) {
450                        // do we have to treat lenShared > 1 special ?
451                        lenShared = 0;
452                        boolean inside = checkIfNodeIsInsidePolygon(n, loop == 0 ? pd2 : pd1);
453                        flags[loop] |= inside ? FOUND_INSIDE : FOUND_OUTSIDE;
454                        if (flags[loop] == (FOUND_INSIDE | FOUND_OUTSIDE)) {
455                            return ExtPolygonIntersection.CROSSING;
456                        }
457                    }
458                }
459            }
460        }
461
462        if ((flags[0] & FOUND_INSIDE) != 0)
463            return ExtPolygonIntersection.FIRST_INSIDE_SECOND;
464        if ((flags[1] & FOUND_INSIDE) != 0)
465            return ExtPolygonIntersection.SECOND_INSIDE_FIRST;
466        if ((flags[0] & FOUND_OUTSIDE) != (flags[1] & FOUND_OUTSIDE)) {
467            return (flags[0] & FOUND_OUTSIDE) != 0 ?
468                ExtPolygonIntersection.SECOND_INSIDE_FIRST : ExtPolygonIntersection.FIRST_INSIDE_SECOND;
469        }
470        if ((flags[0] & FOUND_OUTSIDE) != 0 && (flags[1] & FOUND_OUTSIDE) != 0) {
471            // the two polygons may only share one or more segments but they may also intersect
472            Area a1 = new Area(pd1.get());
473            Area a2 = new Area(pd2.get());
474            PolygonIntersection areaRes = Geometry.polygonIntersection(a1, a2, 1e-6);
475            if (areaRes == PolygonIntersection.OUTSIDE)
476                return ExtPolygonIntersection.OUTSIDE;
477            return ExtPolygonIntersection.CROSSING;
478        }
479        return ExtPolygonIntersection.EQUAL;
480    }
481
482    /**
483     * Helper class for calculation of nesting levels
484     */
485    private static class PolygonLevel {
486        final int level; // nesting level, even for outer, odd for inner polygons.
487        final PolyData outerWay;
488
489        PolygonLevel(PolyData pd, int level) {
490            this.outerWay = pd;
491            this.level = level;
492        }
493    }
494
495    /**
496     * Calculate the nesting levels of the polygon rings and check if calculated role matches
497     * @param r relation (for error reporting)
498     * @param allPolygons list of polygon rings
499     * @param wayMap maps way ids to relation members
500     * @param sharedNodes all nodes shared by multiple ways of this multipolygon
501     */
502    private void checkRoles(Relation r, List<PolyData> allPolygons, Map<Long, RelationMember> wayMap, Set<Node> sharedNodes) {
503        PolygonLevelFinder levelFinder = new PolygonLevelFinder(sharedNodes);
504        List<PolygonLevel> list = levelFinder.findOuterWays(allPolygons);
505        if (list == null || list.isEmpty()) {
506            return;
507        }
508
509        for (PolygonLevel pol : list) {
510            String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner";
511            for (long wayId : pol.outerWay.getWayIds()) {
512                RelationMember member = wayMap.get(wayId);
513                if (!calculatedRole.equals(member.getRole())) {
514                    errors.add(TestError.builder(this, Severity.ERROR, WRONG_MEMBER_ROLE)
515                            .message(RelationChecker.ROLE_VERIF_PROBLEM_MSG,
516                                    marktr("Role for ''{0}'' should be ''{1}''"),
517                                    member.getMember().getDisplayName(DefaultNameFormatter.getInstance()),
518                                    calculatedRole)
519                            .primitives(Arrays.asList(r, member.getMember()))
520                            .highlight(member.getMember())
521                            .build());
522                    if (pol.level == 0 && "inner".equals(member.getRole())) {
523                        // maybe only add this error if we found an outer ring with correct role(s) ?
524                        errors.add(TestError.builder(this, Severity.ERROR, INNER_WAY_OUTSIDE)
525                                .message(tr("Multipolygon inner way is outside"))
526                                .primitives(Arrays.asList(r, member.getMember()))
527                                .highlight(member.getMember())
528                                .build());
529                    }
530                }
531            }
532        }
533    }
534
535    /**
536     * Check if a node is inside the polygon according to the insideness rules of Shape.
537     * @param n the node
538     * @param p the polygon
539     * @return true if the node is inside the polygon
540     */
541    private static boolean checkIfNodeIsInsidePolygon(Node n, PolyData p) {
542        EastNorth en = n.getEastNorth();
543        return en != null && p.get().contains(en.getX(), en.getY());
544    }
545
546    /**
547     * Determine multipolygon ways which are intersecting (crossing without a common node) or sharing one or more way segments.
548     * See also {@link CrossingWays}
549     * @param r the relation (for error reporting)
550     * @param innerPolygons list of inner polygons
551     * @param outerPolygons list of outer polygons
552     * @return map with crossing polygons
553     */
554    private Map<PolyData, List<PolyData>> findIntersectingWays(Relation r, List<PolyData> innerPolygons,
555            List<PolyData> outerPolygons) {
556        HashMap<PolyData, List<PolyData>> crossingPolygonsMap = new HashMap<>();
557        HashMap<PolyData, List<PolyData>> sharedWaySegmentsPolygonsMap = new HashMap<>();
558
559        for (int loop = 0; loop < 2; loop++) {
560            /** All way segments, grouped by cells */
561            final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
562            /** The already detected ways in error */
563            final Map<List<Way>, List<WaySegment>> problemWays = new HashMap<>(50);
564
565            Map<PolyData, List<PolyData>> problemPolygonMap = (loop == 0) ? crossingPolygonsMap
566                    : sharedWaySegmentsPolygonsMap;
567
568            for (Way w : r.getMemberPrimitives(Way.class)) {
569                findIntersectingWay(w, cellSegments, problemWays, loop == 1);
570            }
571
572            if (!problemWays.isEmpty()) {
573                List<PolyData> allPolygons = new ArrayList<>(innerPolygons.size() + outerPolygons.size());
574                allPolygons.addAll(innerPolygons);
575                allPolygons.addAll(outerPolygons);
576
577                for (Entry<List<Way>, List<WaySegment>> entry : problemWays.entrySet()) {
578                    List<Way> ways = entry.getKey();
579                    if (ways.size() != 2)
580                        continue;
581                    PolyData[] crossingPolys = new PolyData[2];
582                    boolean allInner = true;
583                    for (int i = 0; i < 2; i++) {
584                        Way w = ways.get(i);
585                        for (int j = 0; j < allPolygons.size(); j++) {
586                            PolyData pd = allPolygons.get(j);
587                            if (pd.getWayIds().contains(w.getUniqueId())) {
588                                crossingPolys[i] = pd;
589                                if (j >= innerPolygons.size())
590                                    allInner = false;
591                                break;
592                            }
593                        }
594                    }
595                    boolean samePoly = false;
596                    if (crossingPolys[0] != null && crossingPolys[1] != null) {
597                        List<PolyData> crossingPolygons = problemPolygonMap.get(crossingPolys[0]);
598                        if (crossingPolygons == null) {
599                            crossingPolygons = new ArrayList<>();
600                            problemPolygonMap.put(crossingPolys[0], crossingPolygons);
601                        }
602                        crossingPolygons.add(crossingPolys[1]);
603                        if (crossingPolys[0] == crossingPolys[1]) {
604                            samePoly = true;
605                        }
606                    }
607                    if (loop == 0 || samePoly || (loop == 1 && !allInner)) {
608                        String msg = loop == 0 ? tr("Intersection between multipolygon ways")
609                                : samePoly ? tr("Multipolygon ring contains segments twice")
610                                        : tr("Multipolygon outer way shares segment(s) with other ring");
611                        errors.add(TestError.builder(this, Severity.ERROR, CROSSING_WAYS)
612                                .message(msg)
613                                .primitives(Arrays.asList(r, ways.get(0), ways.get(1)))
614                                .highlightWaySegments(entry.getValue())
615                                .build());
616                    }
617                }
618            }
619        }
620        return crossingPolygonsMap;
621    }
622
623    /**
624     * Find ways which are crossing without sharing a node.
625     * @param w way that is member of the relation
626     * @param cellSegments map with already collected way segments
627     * @param crossingWays list to collect crossing ways
628     * @param findSharedWaySegments true: find shared way segments instead of crossings
629     */
630    private static void findIntersectingWay(Way w, Map<Point2D, List<WaySegment>> cellSegments,
631            Map<List<Way>, List<WaySegment>> crossingWays, boolean findSharedWaySegments) {
632        int nodesSize = w.getNodesCount();
633        for (int i = 0; i < nodesSize - 1; i++) {
634            final WaySegment es1 = new WaySegment(w, i);
635            final EastNorth en1 = es1.getFirstNode().getEastNorth();
636            final EastNorth en2 = es1.getSecondNode().getEastNorth();
637            if (en1 == null || en2 == null) {
638                Logging.warn("Crossing ways test (MP) skipped " + es1);
639                continue;
640            }
641            for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) {
642                for (WaySegment es2 : segments) {
643
644                    List<WaySegment> highlight;
645                    if (es2.way == w)
646                        continue; // reported by CrossingWays.SelfIntersection
647                    if (findSharedWaySegments && !es1.isSimilar(es2))
648                        continue;
649                    if (!findSharedWaySegments && !es1.intersects(es2))
650                        continue;
651
652                    List<Way> prims = Arrays.asList(es1.way, es2.way);
653                    if ((highlight = crossingWays.get(prims)) == null) {
654                        highlight = new ArrayList<>();
655                        highlight.add(es1);
656                        highlight.add(es2);
657                        crossingWays.put(prims, highlight);
658                    } else {
659                        highlight.add(es1);
660                        highlight.add(es2);
661                    }
662                }
663                segments.add(es1);
664            }
665        }
666    }
667
668    /**
669     * Check if map contains combination of two given polygons.
670     * @param problemPolyMap the map
671     * @param pd1 1st polygon
672     * @param pd2 2nd polygon
673     * @return true if the combination of polygons is found in the map
674     */
675    private static boolean checkProblemMap(Map<PolyData, List<PolyData>> problemPolyMap, PolyData pd1, PolyData pd2) {
676        List<PolyData> crossingWithFirst = problemPolyMap.get(pd1);
677        if (crossingWithFirst != null && crossingWithFirst.contains(pd2)) {
678            return true;
679        }
680        List<PolyData> crossingWith2nd = problemPolyMap.get(pd2);
681        return crossingWith2nd != null && crossingWith2nd.contains(pd1);
682    }
683
684    /**
685     * Check for:<ul>
686     * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li>
687     * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li>
688     * </ul>
689     * @param r relation
690     * @param tmpErrors list that will contain found errors
691     * @return true if ways with roles other than inner, outer or empty where found
692     */
693    private boolean checkMembersAndRoles(Relation r, List<TestError> tmpErrors) {
694        boolean hasUnexpectedWayRole = false;
695        for (RelationMember rm : r.getMembers()) {
696            if (rm.isWay()) {
697                if (rm.hasRole() && !(rm.hasRole("inner", "outer")))
698                    hasUnexpectedWayRole = true;
699                if (!(rm.hasRole("inner", "outer")) || !rm.hasRole()) {
700                    tmpErrors.add(TestError.builder(this, Severity.ERROR, WRONG_MEMBER_ROLE)
701                            .message(tr("Role for multipolygon way member should be inner or outer"))
702                            .primitives(Arrays.asList(r, rm.getMember()))
703                            .build());
704                }
705            } else {
706                if (!r.isBoundary() || !rm.hasRole("admin_centre", "label", "subarea", "land_area")) {
707                    tmpErrors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE)
708                            .message(r.isBoundary() ? tr("Non-Way in boundary") : tr("Non-Way in multipolygon"))
709                            .primitives(Arrays.asList(r, rm.getMember()))
710                            .build());
711                }
712            }
713        }
714        return hasUnexpectedWayRole;
715    }
716
717    private static Collection<? extends OsmPrimitive> combineRelAndPrimitives(Relation r, Collection<? extends OsmPrimitive> primitives) {
718        // add multipolygon in order to let user select something and fix the error
719        if (!primitives.contains(r)) {
720            List<OsmPrimitive> newPrimitives = new ArrayList<>(primitives);
721            newPrimitives.add(0, r);
722            return newPrimitives;
723        } else {
724            return primitives;
725        }
726    }
727
728    /**
729     * Check for:<ul>
730     * <li>{@link #REPEATED_MEMBER_DIFF_ROLE}: Multipolygon member(s) repeated with different role</li>
731     * <li>{@link #REPEATED_MEMBER_SAME_ROLE}: Multipolygon member(s) repeated with same role</li>
732     * </ul>
733     * @param r relation
734     * @return true if repeated members have been detected, false otherwise
735     */
736    private boolean checkRepeatedWayMembers(Relation r) {
737        boolean hasDups = false;
738        Map<OsmPrimitive, List<RelationMember>> seenMemberPrimitives = new HashMap<>();
739        for (RelationMember rm : r.getMembers()) {
740            if (!rm.isWay())
741                continue;
742            List<RelationMember> list = seenMemberPrimitives.get(rm.getMember());
743            if (list == null) {
744                list = new ArrayList<>(2);
745                seenMemberPrimitives.put(rm.getMember(), list);
746            } else {
747                hasDups = true;
748            }
749            list.add(rm);
750        }
751        if (hasDups) {
752            List<OsmPrimitive> repeatedSameRole = new ArrayList<>();
753            List<OsmPrimitive> repeatedDiffRole = new ArrayList<>();
754            for (Entry<OsmPrimitive, List<RelationMember>> e : seenMemberPrimitives.entrySet()) {
755                List<RelationMember> visited = e.getValue();
756                if (e.getValue().size() == 1)
757                    continue;
758                // we found a duplicate member, check if the roles differ
759                boolean rolesDiffer = false;
760                RelationMember rm = visited.get(0);
761                List<OsmPrimitive> primitives = new ArrayList<>();
762                for (int i = 1; i < visited.size(); i++) {
763                    RelationMember v = visited.get(i);
764                    primitives.add(rm.getMember());
765                    if (!v.getRole().equals(rm.getRole())) {
766                        rolesDiffer = true;
767                    }
768                }
769                if (rolesDiffer) {
770                    repeatedDiffRole.addAll(primitives);
771                } else {
772                    repeatedSameRole.addAll(primitives);
773                }
774            }
775            addRepeatedMemberError(r, repeatedDiffRole, REPEATED_MEMBER_DIFF_ROLE, tr("Multipolygon member(s) repeated with different role"));
776            addRepeatedMemberError(r, repeatedSameRole, REPEATED_MEMBER_SAME_ROLE, tr("Multipolygon member(s) repeated with same role"));
777        }
778        return hasDups;
779    }
780
781    private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) {
782        if (!repeatedMembers.isEmpty()) {
783            errors.add(TestError.builder(this, Severity.ERROR, errorCode)
784                    .message(msg)
785                    .primitives(combineRelAndPrimitives(r, repeatedMembers))
786                    .highlight(repeatedMembers)
787                    .build());
788        }
789    }
790
791    @Override
792    public Command fixError(TestError testError) {
793        if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) {
794            ArrayList<OsmPrimitive> primitives = new ArrayList<>(testError.getPrimitives());
795            if (primitives.size() >= 2 && primitives.get(0) instanceof Relation) {
796                Relation oldRel = (Relation) primitives.get(0);
797                Relation newRel = new Relation(oldRel);
798                List<OsmPrimitive> repeatedPrims = primitives.subList(1, primitives.size());
799                List<RelationMember> oldMembers = oldRel.getMembers();
800
801                List<RelationMember> newMembers = new ArrayList<>();
802                HashSet<OsmPrimitive> toRemove = new HashSet<>(repeatedPrims);
803                HashSet<OsmPrimitive> found = new HashSet<>(repeatedPrims.size());
804                for (RelationMember rm : oldMembers) {
805                    if (toRemove.contains(rm.getMember())) {
806                        if (!found.contains(rm.getMember())) {
807                            found.add(rm.getMember());
808                            newMembers.add(rm);
809                        }
810                    } else {
811                        newMembers.add(rm);
812                    }
813                }
814                newRel.setMembers(newMembers);
815                return new ChangeCommand(oldRel, newRel);
816            }
817        }
818        return null;
819    }
820
821    @Override
822    public boolean isFixable(TestError testError) {
823        return testError.getCode() == REPEATED_MEMBER_SAME_ROLE;
824    }
825
826    /**
827     * Find nesting levels of polygons. Logic taken from class MultipolygonBuilder, uses different structures.
828     */
829    private static class PolygonLevelFinder {
830        private final Set<Node> sharedNodes;
831
832        PolygonLevelFinder(Set<Node> sharedNodes) {
833            this.sharedNodes = sharedNodes;
834        }
835
836        List<PolygonLevel> findOuterWays(List<PolyData> allPolygons) {
837            return findOuterWaysRecursive(0, allPolygons);
838        }
839
840        private List<PolygonLevel> findOuterWaysRecursive(int level, List<PolyData> polygons) {
841            final List<PolygonLevel> result = new ArrayList<>();
842
843            for (PolyData pd : polygons) {
844                if (processOuterWay(level, polygons, result, pd) == null) {
845                    return null;
846                }
847            }
848
849            return result;
850        }
851
852        private Object processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) {
853            List<PolyData> inners = findInnerWaysCandidates(pd, polygons);
854
855            if (inners != null) {
856                //add new outer polygon
857                PolygonLevel pol = new PolygonLevel(pd, level);
858
859                //process inner ways
860                if (!inners.isEmpty()) {
861                    List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, inners);
862                    result.addAll(innerList);
863                }
864
865                result.add(pol);
866            }
867            return result;
868        }
869
870        /**
871         * Check if polygon is an out-most ring, if so, collect the inners
872         * @param outerCandidate polygon which is checked
873         * @param polygons all polygons
874         * @return null if outerCandidate is inside any other polygon, else a list of inner polygons (which might be empty)
875         */
876        private List<PolyData> findInnerWaysCandidates(PolyData outerCandidate, List<PolyData> polygons) {
877            List<PolyData> innerCandidates = new ArrayList<>();
878
879            for (PolyData inner : polygons) {
880                if (inner == outerCandidate) {
881                    continue;
882                }
883                if (!outerCandidate.getBounds().intersects(inner.getBounds())) {
884                    continue;
885                }
886                boolean useIntersectionTest = false;
887                Node unsharedOuterNode = null;
888                Node unsharedInnerNode = getNonIntersectingNode(outerCandidate, inner);
889                if (unsharedInnerNode != null) {
890                    if (checkIfNodeIsInsidePolygon(unsharedInnerNode, outerCandidate)) {
891                        innerCandidates.add(inner);
892                    } else {
893                        // inner is not inside outerCandidate, check if it contains outerCandidate
894                        unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
895                        if (unsharedOuterNode != null) {
896                            if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
897                                return null; // outer is inside inner
898                            }
899                        } else {
900                            useIntersectionTest = true;
901                        }
902                    }
903                } else {
904                    // all nodes of inner are also nodes of outerCandidate
905                    unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
906                    if (unsharedOuterNode == null) {
907                        return null; // all nodes shared -> same ways, maybe different direction
908                    } else {
909                        if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
910                            return null; // outer is inside inner
911                        } else {
912                            useIntersectionTest = true;
913                        }
914                    }
915                }
916                if (useIntersectionTest) {
917                    PolygonIntersection res = Geometry.polygonIntersection(inner.getNodes(), outerCandidate.getNodes());
918                    if (res == PolygonIntersection.FIRST_INSIDE_SECOND)
919                        innerCandidates.add(inner);
920                    else if (res == PolygonIntersection.SECOND_INSIDE_FIRST)
921                        return null;
922                }
923            }
924            return innerCandidates;
925        }
926
927        /**
928         * Find node of pd2 which is not an intersection node with pd1.
929         * @param pd1 1st polygon
930         * @param pd2 2nd polygon
931         * @return node of pd2 which is not an intersection node with pd1 or null if none is found
932         */
933        private Node getNonIntersectingNode(PolyData pd1, PolyData pd2) {
934            for (Node n : pd2.getNodes()) {
935                if (!sharedNodes.contains(n) || !pd1.getNodes().contains(n))
936                    return n;
937            }
938            return null;
939        }
940    }
941}