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