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