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