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