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 * Determine multipolygon ways which are intersecting (crossing without a common node) or sharing one or more way segments. 523 * See also {@link CrossingWays} 524 * @param r the relation (for error reporting) 525 * @param innerPolygons list of inner polygons 526 * @param outerPolygons list of outer polygons 527 * @return map with crossing polygons 528 */ 529 private Map<PolyData, List<PolyData>> findIntersectingWays(Relation r, List<PolyData> innerPolygons, 530 List<PolyData> outerPolygons) { 531 HashMap<PolyData, List<PolyData>> crossingPolygonsMap = new HashMap<>(); 532 HashMap<PolyData, List<PolyData>> sharedWaySegmentsPolygonsMap = new HashMap<>(); 533 534 for (int loop = 0; loop < 2; loop++) { 535 536 Map<List<Way>, List<WaySegment>> crossingWays = findIntersectingWays(r, loop == 1); 537 538 if (!crossingWays.isEmpty()) { 539 Map<PolyData, List<PolyData>> problemPolygonMap = (loop == 0) ? crossingPolygonsMap 540 : sharedWaySegmentsPolygonsMap; 541 542 List<PolyData> allPolygons = new ArrayList<>(innerPolygons.size() + outerPolygons.size()); 543 allPolygons.addAll(innerPolygons); 544 allPolygons.addAll(outerPolygons); 545 546 for (Entry<List<Way>, List<WaySegment>> entry : crossingWays.entrySet()) { 547 List<Way> ways = entry.getKey(); 548 if (ways.size() != 2) 549 continue; 550 PolyData[] crossingPolys = new PolyData[2]; 551 boolean allInner = true; 552 for (int i = 0; i < 2; i++) { 553 Way w = ways.get(i); 554 for (int j = 0; j < allPolygons.size(); j++) { 555 PolyData pd = allPolygons.get(j); 556 if (pd.getWayIds().contains(w.getUniqueId())) { 557 crossingPolys[i] = pd; 558 if (j >= innerPolygons.size()) 559 allInner = false; 560 break; 561 } 562 } 563 } 564 boolean samePoly = false; 565 if (crossingPolys[0] != null && crossingPolys[1] != null) { 566 List<PolyData> crossingPolygons = problemPolygonMap.get(crossingPolys[0]); 567 if (crossingPolygons == null) { 568 crossingPolygons = new ArrayList<>(); 569 problemPolygonMap.put(crossingPolys[0], crossingPolygons); 570 } 571 crossingPolygons.add(crossingPolys[1]); 572 if (crossingPolys[0] == crossingPolys[1]) { 573 samePoly = true; 574 } 575 } 576 if (r == createdRelation && loop == 1 && !allInner) { 577 repeatCheck = true; 578 } else if (loop == 0 || samePoly || (loop == 1 && !allInner)) { 579 String msg = loop == 0 ? tr("Intersection between multipolygon ways") 580 : samePoly ? tr("Multipolygon ring contains segments twice") 581 : tr("Multipolygon outer way shares segment(s) with other ring"); 582 errors.add(TestError.builder(this, Severity.ERROR, CROSSING_WAYS) 583 .message(msg) 584 .primitives(Arrays.asList(r, ways.get(0), ways.get(1))) 585 .highlightWaySegments(entry.getValue()) 586 .build()); 587 } 588 } 589 } 590 } 591 return crossingPolygonsMap; 592 } 593 594 /** 595 * Determine multipolygon ways which are intersecting (crossing without a common node). 596 * This should only be used for relations with incomplete members. 597 * See also {@link CrossingWays} 598 * @param r the relation (for error reporting) 599 */ 600 private void findIntersectingWaysIncomplete(Relation r) { 601 for (Entry<List<Way>, List<WaySegment>> entry : findIntersectingWays(r, false).entrySet()) { 602 List<Way> ways = entry.getKey(); 603 if (ways.size() != 2) 604 continue; 605 606 errors.add(TestError.builder(this, Severity.ERROR, CROSSING_WAYS) 607 .message(tr("Intersection between multipolygon ways")) 608 .primitives(Arrays.asList(r, ways.get(0), ways.get(1))) 609 .highlightWaySegments(entry.getValue()) 610 .build()); 611 } 612 } 613 614 /** 615 * See {@link CrossingWays} 616 * @param r the relation 617 * @param findSharedWaySegments true: find shared way segments instead of crossings 618 * @return map with crossing ways and the related segments 619 */ 620 private static Map<List<Way>, List<WaySegment>> findIntersectingWays(Relation r, boolean findSharedWaySegments) { 621 /** All way segments, grouped by cells */ 622 final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000); 623 /** The detected crossing ways */ 624 final Map<List<Way>, List<WaySegment>> crossingWays = new HashMap<>(50); 625 626 for (Way w: r.getMemberPrimitives(Way.class)) { 627 if (!w.hasIncompleteNodes()) { 628 findIntersectingWay(w, cellSegments, crossingWays, findSharedWaySegments); 629 } 630 } 631 return crossingWays; 632 } 633 634 /** 635 * Find ways which are crossing without sharing a node. 636 * @param w way that is member of the relation 637 * @param cellSegments map with already collected way segments 638 * @param crossingWays map to collect crossing ways and related segments 639 * @param findSharedWaySegments true: find shared way segments instead of crossings 640 */ 641 private static void findIntersectingWay(Way w, Map<Point2D, List<WaySegment>> cellSegments, 642 Map<List<Way>, List<WaySegment>> crossingWays, boolean findSharedWaySegments) { 643 int nodesSize = w.getNodesCount(); 644 for (int i = 0; i < nodesSize - 1; i++) { 645 final WaySegment es1 = new WaySegment(w, i); 646 final EastNorth en1 = es1.getFirstNode().getEastNorth(); 647 final EastNorth en2 = es1.getSecondNode().getEastNorth(); 648 if (en1 == null || en2 == null) { 649 Logging.warn("Crossing ways test (MP) skipped " + es1); 650 continue; 651 } 652 for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) { 653 for (WaySegment es2 : segments) { 654 655 List<WaySegment> highlight; 656 if (es2.way == w // reported by CrossingWays.SelfIntersection 657 || (findSharedWaySegments && !es1.isSimilar(es2)) 658 || (!findSharedWaySegments && !es1.intersects(es2))) 659 continue; 660 661 List<Way> prims = Arrays.asList(es1.way, es2.way); 662 if ((highlight = crossingWays.get(prims)) == null) { 663 highlight = new ArrayList<>(); 664 highlight.add(es1); 665 highlight.add(es2); 666 crossingWays.put(prims, highlight); 667 } else { 668 highlight.add(es1); 669 highlight.add(es2); 670 } 671 } 672 segments.add(es1); 673 } 674 } 675 } 676 677 /** 678 * Check if map contains combination of two given polygons. 679 * @param problemPolyMap the map 680 * @param pd1 1st polygon 681 * @param pd2 2nd polygon 682 * @return true if the combination of polygons is found in the map 683 */ 684 private static boolean checkProblemMap(Map<PolyData, List<PolyData>> problemPolyMap, PolyData pd1, PolyData pd2) { 685 List<PolyData> crossingWithFirst = problemPolyMap.get(pd1); 686 if (crossingWithFirst != null && crossingWithFirst.contains(pd2)) { 687 return true; 688 } 689 List<PolyData> crossingWith2nd = problemPolyMap.get(pd2); 690 return crossingWith2nd != null && crossingWith2nd.contains(pd1); 691 } 692 693 /** 694 * Check for:<ul> 695 * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li> 696 * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li> 697 * </ul> 698 * @param r relation 699 * @param tmpErrors list that will contain found errors 700 * @return true if ways with roles other than inner, outer or empty where found 701 */ 702 private boolean checkMembersAndRoles(Relation r, List<TestError> tmpErrors) { 703 boolean hasUnexpectedWayRole = false; 704 for (RelationMember rm : r.getMembers()) { 705 if (rm.isWay()) { 706 if (rm.hasRole() && !(rm.hasRole("inner", "outer"))) 707 hasUnexpectedWayRole = true; 708 if (!(rm.hasRole("inner", "outer")) || !rm.hasRole()) { 709 tmpErrors.add(TestError.builder(this, Severity.ERROR, WRONG_MEMBER_ROLE) 710 .message(tr("Role for multipolygon way member should be inner or outer")) 711 .primitives(Arrays.asList(r, rm.getMember())) 712 .build()); 713 } 714 } else { 715 if (!r.isBoundary() || !rm.hasRole("admin_centre", "label", "subarea", "land_area")) { 716 tmpErrors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE) 717 .message(r.isBoundary() ? tr("Non-Way in boundary") : tr("Non-Way in multipolygon")) 718 .primitives(Arrays.asList(r, rm.getMember())) 719 .build()); 720 } 721 } 722 } 723 return hasUnexpectedWayRole; 724 } 725 726 private static Collection<? extends OsmPrimitive> combineRelAndPrimitives(Relation r, Collection<? extends OsmPrimitive> primitives) { 727 // add multipolygon in order to let user select something and fix the error 728 if (!primitives.contains(r)) { 729 List<OsmPrimitive> newPrimitives = new ArrayList<>(primitives); 730 newPrimitives.add(0, r); 731 return newPrimitives; 732 } else { 733 return primitives; 734 } 735 } 736 737 /** 738 * Check for:<ul> 739 * <li>{@link #REPEATED_MEMBER_DIFF_ROLE}: Multipolygon member(s) repeated with different role</li> 740 * <li>{@link #REPEATED_MEMBER_SAME_ROLE}: Multipolygon member(s) repeated with same role</li> 741 * </ul> 742 * @param r relation 743 * @return true if repeated members have been detected, false otherwise 744 */ 745 private boolean checkRepeatedWayMembers(Relation r) { 746 boolean hasDups = false; 747 Map<OsmPrimitive, List<RelationMember>> seenMemberPrimitives = new HashMap<>(); 748 for (RelationMember rm : r.getMembers()) { 749 if (!rm.isWay()) 750 continue; 751 List<RelationMember> list = seenMemberPrimitives.get(rm.getMember()); 752 if (list == null) { 753 list = new ArrayList<>(2); 754 seenMemberPrimitives.put(rm.getMember(), list); 755 } else { 756 hasDups = true; 757 } 758 list.add(rm); 759 } 760 if (hasDups) { 761 List<OsmPrimitive> repeatedSameRole = new ArrayList<>(); 762 List<OsmPrimitive> repeatedDiffRole = new ArrayList<>(); 763 for (Entry<OsmPrimitive, List<RelationMember>> e : seenMemberPrimitives.entrySet()) { 764 List<RelationMember> visited = e.getValue(); 765 if (e.getValue().size() == 1) 766 continue; 767 // we found a duplicate member, check if the roles differ 768 boolean rolesDiffer = false; 769 RelationMember rm = visited.get(0); 770 List<OsmPrimitive> primitives = new ArrayList<>(); 771 for (int i = 1; i < visited.size(); i++) { 772 RelationMember v = visited.get(i); 773 primitives.add(rm.getMember()); 774 if (!v.getRole().equals(rm.getRole())) { 775 rolesDiffer = true; 776 } 777 } 778 if (rolesDiffer) { 779 repeatedDiffRole.addAll(primitives); 780 } else { 781 repeatedSameRole.addAll(primitives); 782 } 783 } 784 addRepeatedMemberError(r, repeatedDiffRole, REPEATED_MEMBER_DIFF_ROLE, tr("Multipolygon member(s) repeated with different role")); 785 addRepeatedMemberError(r, repeatedSameRole, REPEATED_MEMBER_SAME_ROLE, tr("Multipolygon member(s) repeated with same role")); 786 } 787 return hasDups; 788 } 789 790 private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) { 791 if (!repeatedMembers.isEmpty()) { 792 errors.add(TestError.builder(this, Severity.ERROR, errorCode) 793 .message(msg) 794 .primitives(combineRelAndPrimitives(r, repeatedMembers)) 795 .highlight(repeatedMembers) 796 .build()); 797 } 798 } 799 800 @Override 801 public Command fixError(TestError testError) { 802 if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) { 803 ArrayList<OsmPrimitive> primitives = new ArrayList<>(testError.getPrimitives()); 804 if (primitives.size() >= 2 && primitives.get(0) instanceof Relation) { 805 Relation oldRel = (Relation) primitives.get(0); 806 Relation newRel = new Relation(oldRel); 807 List<OsmPrimitive> repeatedPrims = primitives.subList(1, primitives.size()); 808 List<RelationMember> oldMembers = oldRel.getMembers(); 809 810 List<RelationMember> newMembers = new ArrayList<>(); 811 HashSet<OsmPrimitive> toRemove = new HashSet<>(repeatedPrims); 812 HashSet<OsmPrimitive> found = new HashSet<>(repeatedPrims.size()); 813 for (RelationMember rm : oldMembers) { 814 if (toRemove.contains(rm.getMember())) { 815 if (!found.contains(rm.getMember())) { 816 found.add(rm.getMember()); 817 newMembers.add(rm); 818 } 819 } else { 820 newMembers.add(rm); 821 } 822 } 823 newRel.setMembers(newMembers); 824 return new ChangeCommand(oldRel, newRel); 825 } 826 } 827 return null; 828 } 829 830 @Override 831 public boolean isFixable(TestError testError) { 832 return testError.getCode() == REPEATED_MEMBER_SAME_ROLE; 833 } 834 835 /** 836 * Find nesting levels of polygons. Logic taken from class MultipolygonBuilder, uses different structures. 837 */ 838 private static class PolygonLevelFinder { 839 private final Set<Node> sharedNodes; 840 841 PolygonLevelFinder(Set<Node> sharedNodes) { 842 this.sharedNodes = sharedNodes; 843 } 844 845 List<PolygonLevel> findOuterWays(List<PolyData> allPolygons) { 846 return findOuterWaysRecursive(0, allPolygons); 847 } 848 849 private List<PolygonLevel> findOuterWaysRecursive(int level, List<PolyData> polygons) { 850 final List<PolygonLevel> result = new ArrayList<>(); 851 852 for (PolyData pd : polygons) { 853 processOuterWay(level, polygons, result, pd); 854 } 855 856 return result; 857 } 858 859 private void processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) { 860 List<PolyData> inners = findInnerWaysCandidates(pd, polygons); 861 862 if (inners != null) { 863 //add new outer polygon 864 PolygonLevel pol = new PolygonLevel(pd, level); 865 866 //process inner ways 867 if (!inners.isEmpty()) { 868 List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, inners); 869 result.addAll(innerList); 870 } 871 872 result.add(pol); 873 } 874 } 875 876 /** 877 * Check if polygon is an out-most ring, if so, collect the inners 878 * @param outerCandidate polygon which is checked 879 * @param polygons all polygons 880 * @return null if outerCandidate is inside any other polygon, else a list of inner polygons (which might be empty) 881 */ 882 private List<PolyData> findInnerWaysCandidates(PolyData outerCandidate, List<PolyData> polygons) { 883 List<PolyData> innerCandidates = new ArrayList<>(); 884 885 for (PolyData inner : polygons) { 886 if (inner == outerCandidate) { 887 continue; 888 } 889 if (!outerCandidate.getBounds().intersects(inner.getBounds())) { 890 continue; 891 } 892 boolean useIntersectionTest = false; 893 Node unsharedOuterNode = null; 894 Node unsharedInnerNode = getNonIntersectingNode(outerCandidate, inner); 895 if (unsharedInnerNode != null) { 896 if (checkIfNodeIsInsidePolygon(unsharedInnerNode, outerCandidate)) { 897 innerCandidates.add(inner); 898 } else { 899 // inner is not inside outerCandidate, check if it contains outerCandidate 900 unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate); 901 if (unsharedOuterNode != null) { 902 if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) { 903 return null; // outer is inside inner 904 } 905 } else { 906 useIntersectionTest = true; 907 } 908 } 909 } else { 910 // all nodes of inner are also nodes of outerCandidate 911 unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate); 912 if (unsharedOuterNode == null) { 913 return null; // all nodes shared -> same ways, maybe different direction 914 } else { 915 if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) { 916 return null; // outer is inside inner 917 } else { 918 useIntersectionTest = true; 919 } 920 } 921 } 922 if (useIntersectionTest) { 923 PolygonIntersection res = Geometry.polygonIntersection(inner.getNodes(), outerCandidate.getNodes()); 924 if (res == PolygonIntersection.FIRST_INSIDE_SECOND) 925 innerCandidates.add(inner); 926 else if (res == PolygonIntersection.SECOND_INSIDE_FIRST) 927 return null; 928 } 929 } 930 return innerCandidates; 931 } 932 933 /** 934 * Find node of pd2 which is not an intersection node with pd1. 935 * @param pd1 1st polygon 936 * @param pd2 2nd polygon 937 * @return node of pd2 which is not an intersection node with pd1 or null if none is found 938 */ 939 private Node getNonIntersectingNode(PolyData pd1, PolyData pd2) { 940 for (Node n : pd2.getNodes()) { 941 if (!sharedNodes.contains(n) || !pd1.getNodes().contains(n)) 942 return n; 943 } 944 return null; 945 } 946 } 947 948 /** 949 * Create a multipolygon relation from the given ways and test it. 950 * @param ways the collection of ways 951 * @return a pair of a {@link Multipolygon} instance and the relation. 952 * @since 15160 953 */ 954 public Relation makeFromWays(Collection<Way> ways) { 955 Relation r = new Relation(); 956 createdRelation = r; 957 r.put("type", "multipolygon"); 958 for (Way w : ways) { 959 r.addMember(new RelationMember("", w)); 960 } 961 do { 962 repeatCheck = false; 963 errors.clear(); 964 Multipolygon polygon = null; 965 boolean hasRepeatedMembers = checkRepeatedWayMembers(r); 966 if (!hasRepeatedMembers) { 967 polygon = new Multipolygon(r); 968 // don't check style consistency here 969 checkGeometryAndRoles(r, polygon); 970 } 971 createdRelation = null; // makes sure that repeatCheck is only set once 972 } while (repeatCheck); 973 errors.removeIf(e->e.getSeverity() == Severity.OTHER); 974 return r; 975 } 976 977}