source: josm/trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java @ 14408

Last change on this file since 14408 was 14408, checked in by GerdP, 5 months ago

fix #16942 - improve performance of MultipolygonTest

  • Property svn:eol-style set to native
File size: 41.5 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.validation.tests;
3
4import static org.openstreetmap.josm.tools.I18n.marktr;
5import static org.openstreetmap.josm.tools.I18n.tr;
6import static org.openstreetmap.josm.tools.I18n.trn;
7
8import java.awt.geom.Area;
9import java.awt.geom.Point2D;
10import java.util.ArrayList;
11import java.util.Arrays;
12import java.util.Collection;
13import java.util.HashMap;
14import java.util.HashSet;
15import java.util.List;
16import java.util.Map;
17import java.util.Map.Entry;
18import java.util.Set;
19
20import org.openstreetmap.josm.command.ChangeCommand;
21import org.openstreetmap.josm.command.Command;
22import org.openstreetmap.josm.data.coor.EastNorth;
23import org.openstreetmap.josm.data.osm.DefaultNameFormatter;
24import org.openstreetmap.josm.data.osm.Node;
25import org.openstreetmap.josm.data.osm.OsmPrimitive;
26import org.openstreetmap.josm.data.osm.Relation;
27import org.openstreetmap.josm.data.osm.RelationMember;
28import org.openstreetmap.josm.data.osm.Way;
29import org.openstreetmap.josm.data.osm.WaySegment;
30import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
31import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData;
32import org.openstreetmap.josm.data.validation.OsmValidator;
33import org.openstreetmap.josm.data.validation.Severity;
34import org.openstreetmap.josm.data.validation.Test;
35import org.openstreetmap.josm.data.validation.TestError;
36import org.openstreetmap.josm.gui.mappaint.ElemStyles;
37import org.openstreetmap.josm.gui.mappaint.MapPaintStyles;
38import org.openstreetmap.josm.gui.mappaint.styleelement.AreaElement;
39import org.openstreetmap.josm.gui.progress.ProgressMonitor;
40import org.openstreetmap.josm.tools.Geometry;
41import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
42import org.openstreetmap.josm.tools.Logging;
43
44/**
45 * Checks if multipolygons are valid
46 * @since 3669
47 */
48public class MultipolygonTest extends Test {
49
50    /** Non-Way in multipolygon */
51    public static final int WRONG_MEMBER_TYPE = 1601;
52    /** No useful role for multipolygon member */
53    public static final int WRONG_MEMBER_ROLE = 1602;
54    /** Multipolygon is not closed */
55    public static final int NON_CLOSED_WAY = 1603;
56    /** No outer way for multipolygon */
57    public static final int MISSING_OUTER_WAY = 1604;
58    /** Multipolygon inner way is outside */
59    public static final int INNER_WAY_OUTSIDE = 1605;
60    /** Intersection between multipolygon ways */
61    public static final int CROSSING_WAYS = 1606;
62    /** Style for outer way mismatches / With the currently used mappaint style(s) the style for outer way mismatches the area style */
63    public static final int OUTER_STYLE_MISMATCH = 1607;
64    /** With the currently used mappaint style the style for inner way equals the multipolygon style */
65    public static final int INNER_STYLE_MISMATCH = 1608;
66    /** Area style way is not closed */
67    public static final int NOT_CLOSED = 1609;
68    /** No area style for multipolygon */
69    public static final int NO_STYLE = 1610;
70    /** Multipolygon relation should be tagged with area tags and not the outer way(s) */
71    public static final int NO_STYLE_POLYGON = 1611;
72    /** Area style on outer way */
73    public static final int OUTER_STYLE = 1613;
74    /** Multipolygon member repeated (same primitive, same role */
75    public static final int REPEATED_MEMBER_SAME_ROLE = 1614;
76    /** Multipolygon member repeated (same primitive, different role) */
77    public static final int REPEATED_MEMBER_DIFF_ROLE = 1615;
78    /** Multipolygon ring is equal to another ring */
79    public static final int EQUAL_RINGS = 1616;
80    /** Multipolygon rings share nodes */
81    public static final int RINGS_SHARE_NODES = 1617;
82
83    private static final int FOUND_INSIDE = 1;
84    private static final int FOUND_OUTSIDE = 2;
85
86    private final Set<String> keysCheckedByAnotherTest = new HashSet<>();
87
88    /**
89     * Constructs a new {@code MultipolygonTest}.
90     */
91    public MultipolygonTest() {
92        super(tr("Multipolygon"),
93                tr("This test checks if multipolygons are valid."));
94    }
95
96    @Override
97    public void startTest(ProgressMonitor progressMonitor) {
98        super.startTest(progressMonitor);
99        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.hasOnlyAreaElements(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(r.isBoundary() ? tr("No outer way for boundary") : 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 && !r.isBoundary()) {
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.ERROR, 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                    if (area.equals(ElemStyles.getAreaElemStyle(wInner, false))) {
207                        errors.add(TestError.builder(this, Severity.OTHER, INNER_STYLE_MISMATCH)
208                                .message(tr("With the currently used mappaint style the style for inner way equals the multipolygon style"))
209                                .primitives(Arrays.asList(r, wInner))
210                                .highlight(wInner)
211                                .build());
212                    }
213                }
214                for (Way wOuter : polygon.getOuterWays()) {
215                    AreaElement areaOuter = ElemStyles.getAreaElemStyle(wOuter, false);
216                    if (areaOuter != null) {
217                        if (!area.equals(areaOuter)) {
218                            String message = !areaStyle ? tr("Style for outer way mismatches")
219                                    : tr("With the currently used mappaint style(s) the style for outer way mismatches the area style");
220                            errors.add(TestError.builder(this, Severity.OTHER, OUTER_STYLE_MISMATCH)
221                                    .message(message)
222                                    .primitives(Arrays.asList(r, wOuter))
223                                    .highlight(wOuter)
224                                    .build());
225                        } else if (areaStyle) { /* style on outer way of multipolygon, but equal to polygon */
226                            errors.add(TestError.builder(this, Severity.WARNING, OUTER_STYLE)
227                                    .message(tr("Area style on outer way"))
228                                    .primitives(Arrays.asList(r, wOuter))
229                                    .highlight(wOuter)
230                                    .build());
231                        }
232                    }
233                }
234            }
235        }
236    }
237
238    /**
239     * Various geometry-related checks:<ul>
240     * <li>{@link #NON_CLOSED_WAY}: Multipolygon is not closed</li>
241     * <li>{@link #INNER_WAY_OUTSIDE}: Multipolygon inner way is outside</li>
242     * <li>{@link #CROSSING_WAYS}: Intersection between multipolygon ways</li>
243     * </ul>
244     * @param r relation
245     * @param polygon multipolygon
246     */
247    private void checkGeometryAndRoles(Relation r, Multipolygon polygon) {
248        int oldErrorsSize = errors.size();
249
250        List<Node> openNodes = polygon.getOpenEnds();
251        if (!openNodes.isEmpty()) {
252            errors.add(TestError.builder(this, Severity.ERROR, NON_CLOSED_WAY)
253                    .message(tr("Multipolygon is not closed"))
254                    .primitives(combineRelAndPrimitives(r, openNodes))
255                    .highlight(openNodes)
256                    .build());
257        }
258        Map<Long, RelationMember> wayMap = new HashMap<>();
259        for (int i = 0; i < r.getMembersCount(); i++) {
260            RelationMember mem = r.getMember(i);
261            if (!mem.isWay())
262                continue;
263            wayMap.put(mem.getWay().getUniqueId(), mem); // duplicate members were checked before
264        }
265        if (wayMap.isEmpty())
266            return;
267
268        Set<Node> sharedNodes = new HashSet<>();
269        Set<Way> intersectionWays = new HashSet<>();
270        findIntersectionNodes(r, sharedNodes, intersectionWays);
271
272        List<PolyData> innerPolygons = polygon.getInnerPolygons();
273        List<PolyData> outerPolygons = polygon.getOuterPolygons();
274        List<PolyData> allPolygons = new ArrayList<>();
275        allPolygons.addAll(outerPolygons);
276        allPolygons.addAll(innerPolygons);
277
278        Map<PolyData, List<PolyData>> crossingPolyMap = findIntersectingWays(r, innerPolygons, outerPolygons);
279
280        if (!sharedNodes.isEmpty()) {
281            for (int i = 0; i < allPolygons.size(); i++) {
282                PolyData pd1 = allPolygons.get(i);
283                checkPolygonForSelfIntersection(r, pd1);
284                // check if this ring has a way that is known to intersect with another way
285
286                if (!hasIntersectionWay(pd1, intersectionWays))
287                    continue;
288
289                for (int j = i + 1; j < allPolygons.size(); j++) {
290                    PolyData pd2 = allPolygons.get(j);
291                    if (!checkProblemMap(crossingPolyMap, pd1, pd2)) {
292                        if (hasIntersectionWay(pd2, intersectionWays))
293                            checkPolygonsForSharedNodes(r, pd1, pd2, sharedNodes);
294                    }
295                }
296            }
297        }
298        boolean checkRoles = true;
299        for (int i = oldErrorsSize; i < errors.size(); i++) {
300            if (errors.get(i).getSeverity() != Severity.OTHER) {
301                checkRoles = false;
302                break;
303            }
304        }
305        if (checkRoles) {
306            // we found no intersection or crossing between the polygons and they are closed
307            // now we can calculate the nesting level to verify the roles with some simple node checks
308            checkRoles(r, allPolygons, wayMap, sharedNodes);
309        }
310    }
311
312    /**
313     * Simple check if given ring contains way that is known to intersect.
314     * @param pd the ring
315     * @param intersectionWays the known intersection ways
316     * @return true if one or more ways are in the set of known ways
317     */
318    private boolean hasIntersectionWay(PolyData pd, Set<Way> intersectionWays) {
319        for (Way w : intersectionWays) {
320            if (pd.getWayIds().contains(w.getUniqueId())) {
321                return true;
322            }
323        }
324        return false;
325    }
326
327    /**
328     * Check if a polygon ring is self-intersecting when the ring was build from multiple ways.
329     * An self intersection in a single way is checked in {@link SelfIntersectingWay}.
330     * @param r the relation
331     * @param pd the ring
332     */
333    private void checkPolygonForSelfIntersection(Relation r, PolyData pd) {
334        if (pd.getWayIds().size() == 1)
335            return;
336        List<Node> wayNodes = pd.getNodes();
337        int num = wayNodes.size();
338        Set<Node> nodes = new HashSet<>();
339        Node firstNode = wayNodes.get(0);
340        nodes.add(firstNode);
341        List<Node> isNodes = new ArrayList<>();
342        for (int i = 1; i < num - 1; i++) {
343            Node n = wayNodes.get(i);
344            if (nodes.contains(n)) {
345                isNodes.add(n);
346            } else {
347                nodes.add(n);
348            }
349        }
350        if (!isNodes.isEmpty()) {
351            List<OsmPrimitive> prims = new ArrayList<>();
352            prims.add(r);
353            prims.addAll(isNodes);
354            errors.add(TestError.builder(this, Severity.WARNING, CROSSING_WAYS)
355                    .message(tr("Self-intersecting polygon ring"))
356                    .primitives(prims)
357                    .highlight(isNodes)
358                    .build());
359
360        }
361    }
362
363    /**
364     * Detect intersections of multipolygon ways at nodes. If any way node is used by more than two ways
365     * or two times in one way and at least once in another way we found an intersection.
366     * @param r the relation
367     * @param sharedNodes We be filled with shared nodes
368     * @param intersectionWays We be filled with ways that have a shared node
369     */
370    private static void findIntersectionNodes(Relation r, Set<Node> sharedNodes, Set<Way> intersectionWays) {
371        Map<Node, List<Way>> nodeMap = new HashMap<>();
372        for (RelationMember rm : r.getMembers()) {
373            if (!rm.isWay())
374                continue;
375            int numNodes = rm.getWay().getNodesCount();
376            for (int i = 0; i < numNodes; i++) {
377                Node n = rm.getWay().getNode(i);
378                if (n.getReferrers().size() <= 1) {
379                    continue; // cannot be a problem node
380                }
381                List<Way> ways = nodeMap.get(n);
382                if (ways == null) {
383                    ways = new ArrayList<>();
384                    nodeMap.put(n, ways);
385                }
386                ways.add(rm.getWay());
387                if (ways.size() > 2 || (ways.size() == 2 && i != 0 && i + 1 != numNodes)) {
388                    sharedNodes.add(n);
389                    intersectionWays.addAll(ways);
390                }
391            }
392        }
393    }
394
395    private enum ExtPolygonIntersection {
396        EQUAL,
397        FIRST_INSIDE_SECOND,
398        SECOND_INSIDE_FIRST,
399        OUTSIDE,
400        CROSSING
401    }
402
403    private void checkPolygonsForSharedNodes(Relation r, PolyData pd1, PolyData pd2, Set<Node> allSharedNodes) {
404        Set<Node> sharedByPolygons = new HashSet<>(allSharedNodes);
405        sharedByPolygons.retainAll(pd1.getNodes());
406        sharedByPolygons.retainAll(pd2.getNodes());
407        if (sharedByPolygons.isEmpty())
408            return;
409
410        // the two polygons share one or more nodes
411        // 1st might be equal to 2nd (same nodes, same or different direction) --> error shared way segments
412        // they overlap --> error
413        // 1st and 2nd share segments
414        // 1st fully inside 2nd --> okay
415        // 2nd fully inside 1st --> okay
416        int errorCode = RINGS_SHARE_NODES;
417        ExtPolygonIntersection res = checkOverlapAtSharedNodes(sharedByPolygons, pd1, pd2);
418        if (res == ExtPolygonIntersection.CROSSING) {
419            errorCode = CROSSING_WAYS;
420        } else if (res == ExtPolygonIntersection.EQUAL) {
421            errorCode = EQUAL_RINGS;
422        }
423        if (errorCode != 0) {
424            Set<OsmPrimitive> prims = new HashSet<>();
425            prims.add(r);
426            for (Node n : sharedByPolygons) {
427                for (OsmPrimitive p : n.getReferrers()) {
428                    if (p instanceof Way && (pd1.getWayIds().contains(p.getUniqueId()) || pd2.getWayIds().contains(p.getUniqueId()))) {
429                        prims.add(p);
430                    }
431                }
432            }
433            if (errorCode == RINGS_SHARE_NODES) {
434                errors.add(TestError.builder(this, Severity.OTHER, errorCode)
435                        .message(tr("Multipolygon rings share node(s)"))
436                        .primitives(prims)
437                        .highlight(sharedByPolygons)
438                        .build());
439            } else {
440                errors.add(TestError.builder(this, Severity.WARNING, errorCode)
441                        .message(errorCode == CROSSING_WAYS ? tr("Intersection between multipolygon ways") : tr("Multipolygon rings are equal"))
442                        .primitives(prims)
443                        .highlight(sharedByPolygons)
444                        .build());
445            }
446        }
447    }
448
449    private static ExtPolygonIntersection checkOverlapAtSharedNodes(Set<Node> shared, PolyData pd1, PolyData pd2) {
450        // Idea: if two polygons share one or more nodes they can either just touch or share segments or intersect.
451        // The insideness test is complex, so we try to reduce the number of these tests.
452        // There is no need to check all nodes, we only have to check the node following a shared node.
453
454        int[] flags = new int[2];
455        for (int loop = 0; loop < flags.length; loop++) {
456            List<Node> nodes2Test = loop == 0 ? pd1.getNodes() : pd2.getNodes();
457            int num = nodes2Test.size() - 1; // ignore closing duplicate node
458
459
460            int lenShared = 0;
461            for (int i = 0; i < num; i++) {
462                Node n = nodes2Test.get(i);
463                if (shared.contains(n)) {
464                    ++lenShared;
465                } else {
466                    if (i == 0 || lenShared > 0) {
467                        // do we have to treat lenShared > 1 special ?
468                        lenShared = 0;
469                        boolean inside = checkIfNodeIsInsidePolygon(n, loop == 0 ? pd2 : pd1);
470                        flags[loop] |= inside ? FOUND_INSIDE : FOUND_OUTSIDE;
471                        if (flags[loop] == (FOUND_INSIDE | FOUND_OUTSIDE)) {
472                            return ExtPolygonIntersection.CROSSING;
473                        }
474                    }
475                }
476            }
477        }
478
479        if ((flags[0] & FOUND_INSIDE) != 0)
480            return ExtPolygonIntersection.FIRST_INSIDE_SECOND;
481        if ((flags[1] & FOUND_INSIDE) != 0)
482            return ExtPolygonIntersection.SECOND_INSIDE_FIRST;
483        if ((flags[0] & FOUND_OUTSIDE) != (flags[1] & FOUND_OUTSIDE)) {
484            return (flags[0] & FOUND_OUTSIDE) != 0 ?
485                ExtPolygonIntersection.SECOND_INSIDE_FIRST : ExtPolygonIntersection.FIRST_INSIDE_SECOND;
486        }
487        if ((flags[0] & FOUND_OUTSIDE) != 0 && (flags[1] & FOUND_OUTSIDE) != 0) {
488            // the two polygons may only share one or more segments but they may also intersect
489            Area a1 = new Area(pd1.get());
490            Area a2 = new Area(pd2.get());
491            PolygonIntersection areaRes = Geometry.polygonIntersection(a1, a2, 1e-6);
492            if (areaRes == PolygonIntersection.OUTSIDE)
493                return ExtPolygonIntersection.OUTSIDE;
494            return ExtPolygonIntersection.CROSSING;
495        }
496        return ExtPolygonIntersection.EQUAL;
497    }
498
499    /**
500     * Helper class for calculation of nesting levels
501     */
502    private static class PolygonLevel {
503        final int level; // nesting level, even for outer, odd for inner polygons.
504        final PolyData outerWay;
505
506        PolygonLevel(PolyData pd, int level) {
507            this.outerWay = pd;
508            this.level = level;
509        }
510    }
511
512    /**
513     * Calculate the nesting levels of the polygon rings and check if calculated role matches
514     * @param r relation (for error reporting)
515     * @param allPolygons list of polygon rings
516     * @param wayMap maps way ids to relation members
517     * @param sharedNodes all nodes shared by multiple ways of this multipolygon
518     */
519    private void checkRoles(Relation r, List<PolyData> allPolygons, Map<Long, RelationMember> wayMap, Set<Node> sharedNodes) {
520        PolygonLevelFinder levelFinder = new PolygonLevelFinder(sharedNodes);
521        List<PolygonLevel> list = levelFinder.findOuterWays(allPolygons);
522        if (list == null || list.isEmpty()) {
523            return;
524        }
525
526        for (PolygonLevel pol : list) {
527            String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner";
528            for (long wayId : pol.outerWay.getWayIds()) {
529                RelationMember member = wayMap.get(wayId);
530                if (!member.getRole().equals(calculatedRole)) {
531                    errors.add(TestError.builder(this, Severity.ERROR, WRONG_MEMBER_ROLE)
532                            .message(RelationChecker.ROLE_VERIF_PROBLEM_MSG,
533                                    marktr("Role for ''{0}'' should be ''{1}''"),
534                                    member.getMember().getDisplayName(DefaultNameFormatter.getInstance()),
535                                    calculatedRole)
536                            .primitives(Arrays.asList(r, member.getMember()))
537                            .highlight(member.getMember())
538                            .build());
539                    if (pol.level == 0 && "inner".equals(member.getRole())) {
540                        // maybe only add this error if we found an outer ring with correct role(s) ?
541                        errors.add(TestError.builder(this, Severity.ERROR, INNER_WAY_OUTSIDE)
542                                .message(tr("Multipolygon inner way is outside"))
543                                .primitives(Arrays.asList(r, member.getMember()))
544                                .highlight(member.getMember())
545                                .build());
546                    }
547                }
548            }
549        }
550    }
551
552    /**
553     * Check if a node is inside the polygon according to the insideness rules of Shape.
554     * @param n the node
555     * @param p the polygon
556     * @return true if the node is inside the polygon
557     */
558    private static boolean checkIfNodeIsInsidePolygon(Node n, PolyData p) {
559        EastNorth en = n.getEastNorth();
560        return en != null && p.get().contains(en.getX(), en.getY());
561    }
562
563    /**
564     * Determine multipolygon ways which are intersecting (crossing without a common node) or sharing one or more way segments.
565     * See also {@link CrossingWays}
566     * @param r the relation (for error reporting)
567     * @param innerPolygons list of inner polygons
568     * @param outerPolygons list of outer polygons
569     * @return map with crossing polygons
570     */
571    private Map<PolyData, List<PolyData>> findIntersectingWays(Relation r, List<PolyData> innerPolygons,
572            List<PolyData> outerPolygons) {
573        HashMap<PolyData, List<PolyData>> crossingPolygonsMap = new HashMap<>();
574        HashMap<PolyData, List<PolyData>> sharedWaySegmentsPolygonsMap = new HashMap<>();
575
576        for (int loop = 0; loop < 2; loop++) {
577            /** All way segments, grouped by cells */
578            final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
579            /** The already detected ways in error */
580            final Map<List<Way>, List<WaySegment>> problemWays = new HashMap<>(50);
581
582            Map<PolyData, List<PolyData>> problemPolygonMap = (loop == 0) ? crossingPolygonsMap
583                    : sharedWaySegmentsPolygonsMap;
584
585            for (Way w : r.getMemberPrimitives(Way.class)) {
586                findIntersectingWay(w, cellSegments, problemWays, loop == 1);
587            }
588
589            if (!problemWays.isEmpty()) {
590                List<PolyData> allPolygons = new ArrayList<>(innerPolygons.size() + outerPolygons.size());
591                allPolygons.addAll(innerPolygons);
592                allPolygons.addAll(outerPolygons);
593
594                for (Entry<List<Way>, List<WaySegment>> entry : problemWays.entrySet()) {
595                    List<Way> ways = entry.getKey();
596                    if (ways.size() != 2)
597                        continue;
598                    PolyData[] crossingPolys = new PolyData[2];
599                    boolean allInner = true;
600                    for (int i = 0; i < 2; i++) {
601                        Way w = ways.get(i);
602                        for (int j = 0; j < allPolygons.size(); j++) {
603                            PolyData pd = allPolygons.get(j);
604                            if (pd.getWayIds().contains(w.getUniqueId())) {
605                                crossingPolys[i] = pd;
606                                if (j >= innerPolygons.size())
607                                    allInner = false;
608                                break;
609                            }
610                        }
611                    }
612                    boolean samePoly = false;
613                    if (crossingPolys[0] != null && crossingPolys[1] != null) {
614                        List<PolyData> crossingPolygons = problemPolygonMap.get(crossingPolys[0]);
615                        if (crossingPolygons == null) {
616                            crossingPolygons = new ArrayList<>();
617                            problemPolygonMap.put(crossingPolys[0], crossingPolygons);
618                        }
619                        crossingPolygons.add(crossingPolys[1]);
620                        if (crossingPolys[0] == crossingPolys[1]) {
621                            samePoly = true;
622                        }
623                    }
624                    if (loop == 0 || samePoly || (loop == 1 && !allInner)) {
625                        String msg = loop == 0 ? tr("Intersection between multipolygon ways")
626                                : samePoly ? tr("Multipolygon ring contains segments twice")
627                                        : tr("Multipolygon outer way shares segment(s) with other ring");
628                        errors.add(TestError.builder(this, Severity.ERROR, CROSSING_WAYS)
629                                .message(msg)
630                                .primitives(Arrays.asList(r, ways.get(0), ways.get(1)))
631                                .highlightWaySegments(entry.getValue())
632                                .build());
633                    }
634                }
635            }
636        }
637        return crossingPolygonsMap;
638    }
639
640    /**
641     * Find ways which are crossing without sharing a node.
642     * @param w way that is member of the relation
643     * @param cellSegments map with already collected way segments
644     * @param crossingWays list to collect crossing ways
645     * @param findSharedWaySegments true: find shared way segments instead of crossings
646     */
647    private static void findIntersectingWay(Way w, Map<Point2D, List<WaySegment>> cellSegments,
648            Map<List<Way>, List<WaySegment>> crossingWays, boolean findSharedWaySegments) {
649        int nodesSize = w.getNodesCount();
650        for (int i = 0; i < nodesSize - 1; i++) {
651            final WaySegment es1 = new WaySegment(w, i);
652            final EastNorth en1 = es1.getFirstNode().getEastNorth();
653            final EastNorth en2 = es1.getSecondNode().getEastNorth();
654            if (en1 == null || en2 == null) {
655                Logging.warn("Crossing ways test (MP) skipped " + es1);
656                continue;
657            }
658            for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) {
659                for (WaySegment es2 : segments) {
660
661                    List<WaySegment> highlight;
662                    if (es2.way == w)
663                        continue; // reported by CrossingWays.SelfIntersection
664                    if (findSharedWaySegments && !es1.isSimilar(es2))
665                        continue;
666                    if (!findSharedWaySegments && !es1.intersects(es2))
667                        continue;
668
669                    List<Way> prims = Arrays.asList(es1.way, es2.way);
670                    if ((highlight = crossingWays.get(prims)) == null) {
671                        highlight = new ArrayList<>();
672                        highlight.add(es1);
673                        highlight.add(es2);
674                        crossingWays.put(prims, highlight);
675                    } else {
676                        highlight.add(es1);
677                        highlight.add(es2);
678                    }
679                }
680                segments.add(es1);
681            }
682        }
683    }
684
685    /**
686     * Check if map contains combination of two given polygons.
687     * @param problemPolyMap the map
688     * @param pd1 1st polygon
689     * @param pd2 2nd polygon
690     * @return true if the combination of polygons is found in the map
691     */
692    private static boolean checkProblemMap(Map<PolyData, List<PolyData>> problemPolyMap, PolyData pd1, PolyData pd2) {
693        List<PolyData> crossingWithFirst = problemPolyMap.get(pd1);
694        if (crossingWithFirst != null && crossingWithFirst.contains(pd2)) {
695            return true;
696        }
697        List<PolyData> crossingWith2nd = problemPolyMap.get(pd2);
698        return crossingWith2nd != null && crossingWith2nd.contains(pd1);
699    }
700
701    /**
702     * Check for:<ul>
703     * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li>
704     * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li>
705     * </ul>
706     * @param r relation
707     */
708    private void checkMembersAndRoles(Relation r) {
709        for (RelationMember rm : r.getMembers()) {
710            if (rm.isWay()) {
711                if (!(rm.hasRole("inner", "outer") || !rm.hasRole())) {
712                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE)
713                            .message(tr("No useful role for multipolygon member"))
714                            .primitives(Arrays.asList(r, rm.getMember()))
715                            .build());
716                }
717            } else {
718                if (!r.isBoundary() || !rm.hasRole("admin_centre", "label", "subarea", "land_area")) {
719                    errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE)
720                            .message(r.isBoundary() ? tr("Non-Way in boundary") : tr("Non-Way in multipolygon"))
721                            .primitives(Arrays.asList(r, rm.getMember()))
722                            .build());
723                }
724            }
725        }
726    }
727
728    private static Collection<? extends OsmPrimitive> combineRelAndPrimitives(Relation r, Collection<? extends OsmPrimitive> primitives) {
729        // add multipolygon in order to let user select something and fix the error
730        if (!primitives.contains(r)) {
731            List<OsmPrimitive> newPrimitives = new ArrayList<>(primitives);
732            newPrimitives.add(0, r);
733            return newPrimitives;
734        } else {
735            return primitives;
736        }
737    }
738
739    /**
740     * Check for:<ul>
741     * <li>{@link #REPEATED_MEMBER_DIFF_ROLE}: Multipolygon member(s) repeated with different role</li>
742     * <li>{@link #REPEATED_MEMBER_SAME_ROLE}: Multipolygon member(s) repeated with same role</li>
743     * </ul>
744     * @param r relation
745     * @return true if repeated members have been detected, false otherwise
746     */
747    private boolean checkRepeatedWayMembers(Relation r) {
748        boolean hasDups = false;
749        Map<OsmPrimitive, List<RelationMember>> seenMemberPrimitives = new HashMap<>();
750        for (RelationMember rm : r.getMembers()) {
751            List<RelationMember> list = seenMemberPrimitives.get(rm.getMember());
752            if (list == null) {
753                list = new ArrayList<>(2);
754                seenMemberPrimitives.put(rm.getMember(), list);
755            } else {
756                hasDups = true;
757            }
758            list.add(rm);
759        }
760        if (hasDups) {
761            List<OsmPrimitive> repeatedSameRole = new ArrayList<>();
762            List<OsmPrimitive> repeatedDiffRole = new ArrayList<>();
763            for (Entry<OsmPrimitive, List<RelationMember>> e : seenMemberPrimitives.entrySet()) {
764                List<RelationMember> visited = e.getValue();
765                if (e.getValue().size() == 1)
766                    continue;
767                // we found a duplicate member, check if the roles differ
768                boolean rolesDiffer = false;
769                RelationMember rm = visited.get(0);
770                List<OsmPrimitive> primitives = new ArrayList<>();
771                for (int i = 1; i < visited.size(); i++) {
772                    RelationMember v = visited.get(i);
773                    primitives.add(rm.getMember());
774                    if (!v.getRole().equals(rm.getRole())) {
775                        rolesDiffer = true;
776                    }
777                }
778                if (rolesDiffer) {
779                    repeatedDiffRole.addAll(primitives);
780                } else {
781                    repeatedSameRole.addAll(primitives);
782                }
783            }
784            addRepeatedMemberError(r, repeatedDiffRole, REPEATED_MEMBER_DIFF_ROLE, tr("Multipolygon member(s) repeated with different role"));
785            addRepeatedMemberError(r, repeatedSameRole, REPEATED_MEMBER_SAME_ROLE, tr("Multipolygon member(s) repeated with same role"));
786        }
787        return hasDups;
788    }
789
790    private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) {
791        if (!repeatedMembers.isEmpty()) {
792            errors.add(TestError.builder(this, Severity.ERROR, errorCode)
793                    .message(msg)
794                    .primitives(combineRelAndPrimitives(r, repeatedMembers))
795                    .highlight(repeatedMembers)
796                    .build());
797        }
798    }
799
800    @Override
801    public Command fixError(TestError testError) {
802        if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) {
803            ArrayList<OsmPrimitive> primitives = new ArrayList<>(testError.getPrimitives());
804            if (primitives.size() >= 2 && primitives.get(0) instanceof Relation) {
805                Relation oldRel = (Relation) primitives.get(0);
806                Relation newRel = new Relation(oldRel);
807                List<OsmPrimitive> repeatedPrims = primitives.subList(1, primitives.size());
808                List<RelationMember> oldMembers = oldRel.getMembers();
809
810                List<RelationMember> newMembers = new ArrayList<>();
811                HashSet<OsmPrimitive> toRemove = new HashSet<>(repeatedPrims);
812                HashSet<OsmPrimitive> found = new HashSet<>(repeatedPrims.size());
813                for (RelationMember rm : oldMembers) {
814                    if (toRemove.contains(rm.getMember())) {
815                        if (!found.contains(rm.getMember())) {
816                            found.add(rm.getMember());
817                            newMembers.add(rm);
818                        }
819                    } else {
820                        newMembers.add(rm);
821                    }
822                }
823                newRel.setMembers(newMembers);
824                return new ChangeCommand(oldRel, newRel);
825            }
826        }
827        return null;
828    }
829
830    @Override
831    public boolean isFixable(TestError testError) {
832        return testError.getCode() == REPEATED_MEMBER_SAME_ROLE;
833    }
834
835    /**
836     * Find nesting levels of polygons. Logic taken from class MultipolygonBuilder, uses different structures.
837     */
838    private static class PolygonLevelFinder {
839        private final Set<Node> sharedNodes;
840
841        PolygonLevelFinder(Set<Node> sharedNodes) {
842            this.sharedNodes = sharedNodes;
843        }
844
845        List<PolygonLevel> findOuterWays(List<PolyData> allPolygons) {
846            return findOuterWaysRecursive(0, allPolygons);
847        }
848
849        private List<PolygonLevel> findOuterWaysRecursive(int level, List<PolyData> polygons) {
850            final List<PolygonLevel> result = new ArrayList<>();
851
852            for (PolyData pd : polygons) {
853                if (processOuterWay(level, polygons, result, pd) == null) {
854                    return null;
855                }
856            }
857
858            return result;
859        }
860
861        private Object processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) {
862            List<PolyData> inners = findInnerWaysCandidates(pd, polygons);
863
864            if (inners != null) {
865                //add new outer polygon
866                PolygonLevel pol = new PolygonLevel(pd, level);
867
868                //process inner ways
869                if (!inners.isEmpty()) {
870                    List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, inners);
871                    result.addAll(innerList);
872                }
873
874                result.add(pol);
875            }
876            return result;
877        }
878
879        /**
880         * Check if polygon is an out-most ring, if so, collect the inners
881         * @param outerCandidate polygon which is checked
882         * @param polygons all polygons
883         * @return null if outerCandidate is inside any other polygon, else a list of inner polygons (which might be empty)
884         */
885        private List<PolyData> findInnerWaysCandidates(PolyData outerCandidate, List<PolyData> polygons) {
886            List<PolyData> innerCandidates = new ArrayList<>();
887
888            for (PolyData inner : polygons) {
889                if (inner == outerCandidate) {
890                    continue;
891                }
892                if (!outerCandidate.getBounds().intersects(inner.getBounds())) {
893                    continue;
894                }
895                boolean useIntersectionTest = false;
896                Node unsharedOuterNode = null;
897                Node unsharedInnerNode = getNonIntersectingNode(outerCandidate, inner);
898                if (unsharedInnerNode != null) {
899                    if (checkIfNodeIsInsidePolygon(unsharedInnerNode, outerCandidate)) {
900                        innerCandidates.add(inner);
901                    } else {
902                        // inner is not inside outerCandidate, check if it contains outerCandidate
903                        unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
904                        if (unsharedOuterNode != null) {
905                            if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
906                                return null; // outer is inside inner
907                            }
908                        } else {
909                            useIntersectionTest = true;
910                        }
911                    }
912                } else {
913                    // all nodes of inner are also nodes of outerCandidate
914                    unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
915                    if (unsharedOuterNode == null) {
916                        return null; // all nodes shared -> same ways, maybe different direction
917                    } else {
918                        if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
919                            return null; // outer is inside inner
920                        } else {
921                            useIntersectionTest = true;
922                        }
923                    }
924                }
925                if (useIntersectionTest) {
926                    PolygonIntersection res = Geometry.polygonIntersection(inner.getNodes(), outerCandidate.getNodes());
927                    if (res == PolygonIntersection.FIRST_INSIDE_SECOND)
928                        innerCandidates.add(inner);
929                    else if (res == PolygonIntersection.SECOND_INSIDE_FIRST)
930                        return null;
931                }
932            }
933            return innerCandidates;
934        }
935
936        /**
937         * Find node of pd2 which is not an intersection node with pd1.
938         * @param pd1 1st polygon
939         * @param pd2 2nd polygon
940         * @return node of pd2 which is not an intersection node with pd1 or null if none is found
941         */
942        private Node getNonIntersectingNode(PolyData pd1, PolyData pd2) {
943            for (Node n : pd2.getNodes()) {
944                if (!sharedNodes.contains(n) || !pd1.getNodes().contains(n))
945                    return n;
946            }
947            return null;
948        }
949    }
950}
Note: See TracBrowser for help on using the repository browser.