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