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