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