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

Last change on this file since 14468 was 14437, checked in by GerdP, 5 years ago

fix #17010 - Validator creates multiple errors/warnings for same problem

The fix reduces the noise.

  • Don't check roles again in RelationChecker when MultipolygonTest is enabled
  • remove special code that just searches for an outer way
  • correct checkMembersAndRoles, it did not find wrong roles for way members
  • 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 /** Multipolygon inner way is outside */
57 public static final int INNER_WAY_OUTSIDE = 1605;
58 /** Intersection between multipolygon ways */
59 public static final int CROSSING_WAYS = 1606;
60 /** Style for outer way mismatches / With the currently used mappaint style(s) the style for outer way mismatches the area style */
61 public static final int OUTER_STYLE_MISMATCH = 1607;
62 /** With the currently used mappaint style the style for inner way equals the multipolygon style */
63 public static final int INNER_STYLE_MISMATCH = 1608;
64 /** Area style way is not closed */
65 public static final int NOT_CLOSED = 1609;
66 /** No area style for multipolygon */
67 public static final int NO_STYLE = 1610;
68 /** Multipolygon relation should be tagged with area tags and not the outer way(s) */
69 public static final int NO_STYLE_POLYGON = 1611;
70 /** Area style on outer way */
71 public static final int OUTER_STYLE = 1613;
72 /** Multipolygon member repeated (same primitive, same role */
73 public static final int REPEATED_MEMBER_SAME_ROLE = 1614;
74 /** Multipolygon member repeated (same primitive, different role) */
75 public static final int REPEATED_MEMBER_DIFF_ROLE = 1615;
76 /** Multipolygon ring is equal to another ring */
77 public static final int EQUAL_RINGS = 1616;
78 /** Multipolygon rings share nodes */
79 public static final int RINGS_SHARE_NODES = 1617;
80
81 private static final int FOUND_INSIDE = 1;
82 private static final int FOUND_OUTSIDE = 2;
83
84 private final Set<String> keysCheckedByAnotherTest = new HashSet<>();
85
86 /**
87 * Constructs a new {@code MultipolygonTest}.
88 */
89 public MultipolygonTest() {
90 super(tr("Multipolygon"),
91 tr("This test checks if multipolygons are valid."));
92 }
93
94 @Override
95 public void startTest(ProgressMonitor progressMonitor) {
96 super.startTest(progressMonitor);
97 keysCheckedByAnotherTest.clear();
98 for (Test t : OsmValidator.getEnabledTests(false)) {
99 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}
Note: See TracBrowser for help on using the repository browser.