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