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