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