001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.validation.tests; 003 004import static org.openstreetmap.josm.data.validation.tests.CrossingWays.HIGHWAY; 005import static org.openstreetmap.josm.data.validation.tests.CrossingWays.RAILWAY; 006import static org.openstreetmap.josm.tools.I18n.tr; 007 008import java.awt.geom.Area; 009import java.util.ArrayList; 010import java.util.Arrays; 011import java.util.Collection; 012import java.util.Collections; 013import java.util.HashMap; 014import java.util.HashSet; 015import java.util.Iterator; 016import java.util.LinkedHashSet; 017import java.util.List; 018import java.util.Map; 019import java.util.Map.Entry; 020import java.util.Objects; 021import java.util.Set; 022import java.util.stream.Collectors; 023 024import org.openstreetmap.josm.data.coor.EastNorth; 025import org.openstreetmap.josm.data.coor.LatLon; 026import org.openstreetmap.josm.data.osm.BBox; 027import org.openstreetmap.josm.data.osm.DataSet; 028import org.openstreetmap.josm.data.osm.Node; 029import org.openstreetmap.josm.data.osm.OsmDataManager; 030import org.openstreetmap.josm.data.osm.OsmPrimitive; 031import org.openstreetmap.josm.data.osm.OsmUtils; 032import org.openstreetmap.josm.data.osm.QuadBuckets; 033import org.openstreetmap.josm.data.osm.Way; 034import org.openstreetmap.josm.data.preferences.sources.ValidatorPrefHelper; 035import org.openstreetmap.josm.data.projection.Ellipsoid; 036import org.openstreetmap.josm.data.projection.ProjectionRegistry; 037import org.openstreetmap.josm.data.validation.Severity; 038import org.openstreetmap.josm.data.validation.Test; 039import org.openstreetmap.josm.data.validation.TestError; 040import org.openstreetmap.josm.gui.progress.ProgressMonitor; 041import org.openstreetmap.josm.spi.preferences.Config; 042import org.openstreetmap.josm.tools.Geometry; 043import org.openstreetmap.josm.tools.Logging; 044 045/** 046 * Checks if a way has an endpoint very near to another way. 047 * <br> 048 * This class is abstract since highway/railway/waterway/… ways must be handled separately. 049 * An actual implementation must override {@link #isPrimitiveUsable(OsmPrimitive)} 050 * to denote which kind of primitives can be handled. 051 * 052 * @author frsantos 053 */ 054public abstract class UnconnectedWays extends Test { 055 private static final String POWER = "power"; 056 private static final String PLATFORM = "platform"; 057 private static final String PLATFORM_EDGE = "platform_edge"; 058 private static final String CONSTRUCTION = "construction"; 059 private final int code; 060 private final boolean isHighwayTest; 061 062 static final double DETOUR_FACTOR = 4; 063 064 protected abstract boolean isCandidate(OsmPrimitive p); 065 066 protected boolean isWantedWay(Way w) { 067 return w.isUsable() && isCandidate(w); 068 } 069 070 /** 071 * Check if unconnected end node should be ignored. 072 * @param n the node 073 * @return true if node should be ignored 074 */ 075 protected boolean ignoreUnconnectedEndNode(Node n) { 076 return false; 077 } 078 079 @Override 080 public boolean isPrimitiveUsable(OsmPrimitive p) { 081 return super.isPrimitiveUsable(p) && ((partialSelection && p instanceof Node) || isCandidate(p)); 082 } 083 084 /** 085 * Unconnected highways test. 086 */ 087 public static class UnconnectedHighways extends UnconnectedWays { 088 static final int UNCONNECTED_HIGHWAYS = 1311; 089 090 /** 091 * Constructs a new {@code UnconnectedHighways} test. 092 */ 093 public UnconnectedHighways() { 094 super(tr("Unconnected highways"), UNCONNECTED_HIGHWAYS, true); 095 } 096 097 @Override 098 protected boolean isCandidate(OsmPrimitive p) { 099 return p.hasKey(HIGHWAY); 100 } 101 102 @Override 103 protected boolean ignoreUnconnectedEndNode(Node n) { 104 return n.hasTag(HIGHWAY, "turning_circle", "bus_stop", "elevator") 105 || n.hasTag("amenity", "parking_entrance", "ferry_terminal") 106 || n.isKeyTrue("noexit") 107 || n.hasKey("entrance", "barrier") 108 || n.getParentWays().stream().anyMatch(p -> isBuilding(p) || p.hasTag(RAILWAY, PLATFORM, PLATFORM_EDGE)); 109 } 110 } 111 112 /** 113 * Unconnected railways test. 114 */ 115 public static class UnconnectedRailways extends UnconnectedWays { 116 static final int UNCONNECTED_RAILWAYS = 1321; 117 /** 118 * Constructs a new {@code UnconnectedRailways} test. 119 */ 120 public UnconnectedRailways() { 121 super(tr("Unconnected railways"), UNCONNECTED_RAILWAYS, false); 122 } 123 124 @Override 125 protected boolean isCandidate(OsmPrimitive p) { 126 if (p.hasTag(RAILWAY, CONSTRUCTION) && p.hasKey(CONSTRUCTION)) 127 return p.hasTagDifferent(CONSTRUCTION, PLATFORM, PLATFORM_EDGE, "service_station", "station"); 128 return p.hasTagDifferent(RAILWAY, "proposed", "planned", "abandoned", "razed", "disused", "no", 129 PLATFORM, PLATFORM_EDGE, "service_station", "station"); 130 } 131 132 @Override 133 protected boolean ignoreUnconnectedEndNode(Node n) { 134 if (n.hasTag(RAILWAY, "buffer_stop") || n.isKeyTrue("noexit")) 135 return true; 136 // See #21038. Check also if next node to end node is a buffer stop. 137 Way parent = getWantedParentWay(n); 138 if (parent != null && parent.getNodesCount() > 1) { 139 Node next = null; 140 if (n == parent.firstNode()) 141 next = parent.getNode(1); 142 else if (n == parent.lastNode()) { 143 next = parent.getNode(parent.getNodesCount() - 2); 144 } 145 if (next != null) 146 return next.hasTag(RAILWAY, "buffer_stop"); 147 } 148 return false; 149 150 } 151 } 152 153 /** 154 * Unconnected waterways test. 155 */ 156 public static class UnconnectedWaterways extends UnconnectedWays { 157 static final int UNCONNECTED_WATERWAYS = 1331; 158 /** 159 * Constructs a new {@code UnconnectedWaterways} test. 160 */ 161 public UnconnectedWaterways() { 162 super(tr("Unconnected waterways"), UNCONNECTED_WATERWAYS, false); 163 } 164 165 @Override 166 protected boolean isCandidate(OsmPrimitive p) { 167 return p.hasTagDifferent("waterway", "dam", "lock_gate", "weir"); 168 } 169 } 170 171 /** 172 * Unconnected natural/landuse test. 173 */ 174 public static class UnconnectedNaturalOrLanduse extends UnconnectedWays { 175 static final int UNCONNECTED_NATURAL_OR_LANDUSE = 1341; 176 /** 177 * Constructs a new {@code UnconnectedNaturalOrLanduse} test. 178 */ 179 public UnconnectedNaturalOrLanduse() { 180 super(tr("Unconnected natural lands and landuses"), UNCONNECTED_NATURAL_OR_LANDUSE, false); 181 } 182 183 @Override 184 protected boolean isCandidate(OsmPrimitive p) { 185 return p.hasKey("landuse") || p.hasTagDifferent("natural", "arete", "cliff", "ridge", "tree_row"); 186 } 187 } 188 189 /** 190 * Unconnected power ways test. 191 */ 192 public static class UnconnectedPower extends UnconnectedWays { 193 static final int UNCONNECTED_POWER = 1351; 194 /** 195 * Constructs a new {@code UnconnectedPower} test. 196 */ 197 public UnconnectedPower() { 198 super(tr("Unconnected power ways"), UNCONNECTED_POWER, false); 199 } 200 201 @Override 202 protected boolean isCandidate(OsmPrimitive p) { 203 return p.hasTag(POWER, "line", "minor_line", "cable"); 204 } 205 206 @Override 207 protected boolean ignoreUnconnectedEndNode(Node n) { 208 return n.hasTag(POWER, "terminal") || n.hasTag("location:transition", "yes") 209 || n.hasTag("line_management", "transition", "termination"); 210 } 211 } 212 213 protected static final int UNCONNECTED_WAYS = 1301; 214 protected static final String PREFIX = ValidatorPrefHelper.PREFIX + "." + UnconnectedWays.class.getSimpleName(); 215 216 private List<MyWaySegment> waySegments; 217 private Set<Node> endnodes; // nodes at end of way 218 private Set<Node> middlenodes; // nodes in middle of way 219 private Set<Node> othernodes; // nodes appearing at least twice 220 private QuadBuckets<Node> searchNodes; 221 private Set<Way> waysToTest; 222 private Set<Node> nodesToTest; 223 private Area dsArea; 224 225 private double mindist; 226 private double minmiddledist; 227 private double maxLen; // maximum length of allowed detour to reach the unconnected node 228 private DataSet ds; 229 230 /** 231 * Constructs a new {@code UnconnectedWays} test. 232 * @param title The test title 233 * @since 6691 234 */ 235 protected UnconnectedWays(String title) { 236 this(title, UNCONNECTED_WAYS, false); 237 } 238 239 /** 240 * Constructs a new {@code UnconnectedWays} test with the given code. 241 * @param title The test title 242 * @param code The test code 243 * @param isHighwayTest use {@code true} if test concerns highways or railways 244 * @since 14468 245 */ 246 protected UnconnectedWays(String title, int code, boolean isHighwayTest) { 247 super(title, tr("This test checks if a way has an endpoint very near to another way.")); 248 this.code = code; 249 this.isHighwayTest = isHighwayTest; 250 } 251 252 @Override 253 public void startTest(ProgressMonitor monitor) { 254 super.startTest(monitor); 255 waySegments = new ArrayList<>(); 256 searchNodes = new QuadBuckets<>(); 257 waysToTest = new HashSet<>(); 258 nodesToTest = new HashSet<>(); 259 endnodes = new HashSet<>(); 260 middlenodes = new HashSet<>(); 261 othernodes = new HashSet<>(); 262 mindist = Config.getPref().getDouble(PREFIX + ".node_way_distance", 10.0); 263 if (this instanceof UnconnectedRailways) 264 mindist = Config.getPref().getDouble(PREFIX + ".node_way_distance_railway", 1.0); 265 minmiddledist = Config.getPref().getDouble(PREFIX + ".way_way_distance", 0.0); 266 ds = OsmDataManager.getInstance().getActiveDataSet(); 267 dsArea = ds == null ? null : ds.getDataSourceArea(); 268 } 269 270 protected Map<Node, MyWaySegment> getHighwayEndNodesNearOtherHighway() { 271 Map<Node, MyWaySegment> map = new HashMap<>(); 272 for (MyWaySegment s : waySegments) { 273 if (isCanceled()) { 274 map.clear(); 275 return map; 276 } 277 if (s.w.hasTag(HIGHWAY, PLATFORM)) 278 continue; 279 for (Node endnode : s.nearbyNodes(mindist)) { 280 Way parentWay = getWantedParentWay(endnode); 281 if (parentWay != null && !parentWay.hasTag(HIGHWAY, PLATFORM) 282 && Objects.equals(OsmUtils.getLayer(s.w), OsmUtils.getLayer(parentWay)) 283 // to handle intersections of 't' shapes and similar 284 && !s.isConnectedTo(endnode) && !s.obstacleBetween(endnode)) { 285 addIfNewOrCloser(map, endnode, s); 286 } 287 } 288 } 289 return map; 290 } 291 292 protected Map<Node, MyWaySegment> getWayEndNodesNearOtherWay() { 293 Map<Node, MyWaySegment> map = new HashMap<>(); 294 295 for (MyWaySegment s : waySegments) { 296 if (isCanceled()) { 297 map.clear(); 298 return map; 299 } 300 if (!s.concernsArea) { 301 for (Node endnode : s.nearbyNodes(mindist)) { 302 if (!s.isConnectedTo(endnode)) { 303 if (s.w.hasTag(POWER)) { 304 boolean badConnection = false; 305 Way otherWay = getWantedParentWay(endnode); 306 if (otherWay != null) { 307 for (String key : Arrays.asList("voltage", "frequency")) { 308 String v1 = s.w.get(key); 309 String v2 = otherWay.get(key); 310 if (v1 != null && v2 != null && !v1.equals(v2)) { 311 badConnection = true; 312 } 313 } 314 } 315 if (badConnection) 316 continue; 317 } 318 addIfNewOrCloser(map, endnode, s); 319 } 320 } 321 } 322 } 323 return map; 324 } 325 326 protected Map<Node, MyWaySegment> getWayNodesNearOtherWay() { 327 Map<Node, MyWaySegment> map = new HashMap<>(); 328 for (MyWaySegment s : waySegments) { 329 if (isCanceled()) { 330 map.clear(); 331 return map; 332 } 333 for (Node en : s.nearbyNodes(minmiddledist)) { 334 if (!s.isConnectedTo(en)) { 335 addIfNewOrCloser(map, en, s); 336 } 337 } 338 } 339 return map; 340 } 341 342 /** 343 * An unconnected node might have multiple parent ways, e.g. a highway and a landuse way. 344 * Make sure we get the one that was analysed before. 345 * @param endnode the node which is known to be an end node of the wanted way 346 * @return the wanted way 347 */ 348 protected Way getWantedParentWay(Node endnode) { 349 for (Way w : endnode.getParentWays()) { 350 if (isWantedWay(w)) 351 return w; 352 } 353 Logging.error("end node without matching parent way"); 354 return null; 355 } 356 357 private void addIfNewOrCloser(Map<Node, MyWaySegment> map, Node node, MyWaySegment ws) { 358 if (partialSelection && !nodesToTest.contains(node) && !waysToTest.contains(ws.w)) 359 return; 360 MyWaySegment old = map.get(node); 361 if (old != null) { 362 double d1 = ws.getDist(node); 363 double d2 = old.getDist(node); 364 if (d1 > d2) { 365 // keep old value 366 return; 367 } 368 } 369 map.put(node, ws); 370 } 371 372 protected final void addErrors(Severity severity, Map<Node, MyWaySegment> errorMap, String message) { 373 for (Entry<Node, MyWaySegment> error : errorMap.entrySet()) { 374 Node node = error.getKey(); 375 MyWaySegment ws = error.getValue(); 376 errors.add(TestError.builder(this, severity, code) 377 .message(message) 378 .primitives(node, ws.w) 379 .highlight(node) 380 .build()); 381 } 382 } 383 384 @Override 385 public void endTest() { 386 if (ds == null) 387 return; 388 389 for (Way w : ds.getWays()) { 390 if (isWantedWay(w) && w.getRealNodesCount() > 1) { 391 waySegments.addAll(getWaySegments(w)); 392 addNode(w.firstNode(), endnodes); 393 addNode(w.lastNode(), endnodes); 394 } 395 } 396 fillSearchNodes(endnodes); 397 if (!searchNodes.isEmpty()) { 398 maxLen = DETOUR_FACTOR * mindist; 399 if (isHighwayTest) { 400 addErrors(Severity.WARNING, getHighwayEndNodesNearOtherHighway(), tr("Way end node near other highway")); 401 } else { 402 addErrors(Severity.WARNING, getWayEndNodesNearOtherWay(), tr("Way end node near other way")); 403 } 404 } 405 406 /* the following two should use a shorter distance */ 407 boolean includeOther = isBeforeUpload ? ValidatorPrefHelper.PREF_OTHER_UPLOAD.get() : ValidatorPrefHelper.PREF_OTHER.get(); 408 if (minmiddledist > 0.0 && includeOther) { 409 maxLen = DETOUR_FACTOR * minmiddledist; 410 fillSearchNodes(middlenodes); 411 addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Way node near other way")); 412 fillSearchNodes(othernodes); 413 addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Connected way end node near other way")); 414 } 415 416 waySegments = null; 417 endnodes = null; 418 middlenodes = null; 419 othernodes = null; 420 searchNodes = null; 421 waysToTest = null; 422 nodesToTest = null; 423 dsArea = null; 424 ds = null; 425 super.endTest(); 426 } 427 428 private void fillSearchNodes(Collection<Node> nodes) { 429 searchNodes.clear(); 430 for (Node n : nodes) { 431 if (!ignoreUnconnectedEndNode(n) && n.getCoor().isIn(dsArea)) { 432 searchNodes.add(n); 433 } 434 } 435 } 436 437 private class MyWaySegment { 438 /** the way */ 439 public final Way w; 440 private final Node n1; 441 private final Node n2; 442 private final boolean concernsArea; 443 444 MyWaySegment(Way w, Node n1, Node n2, boolean concersArea) { 445 this.w = w; 446 this.n1 = n1; 447 this.n2 = n2; 448 this.concernsArea = concersArea; 449 } 450 451 /** 452 * Check if the given node is connected to this segment using a reasonable short way. 453 * @param startNode the node 454 * @return true if a reasonable connection was found 455 */ 456 boolean isConnectedTo(Node startNode) { 457 return isConnectedTo(startNode, new LinkedHashSet<>(), 0, w); 458 } 459 460 /** 461 * Check if the given node is connected to this segment using a reasonable short way. 462 * @param node the given node 463 * @param visited set of visited nodes 464 * @param len length of the travelled route 465 * @param parent the previous parent way 466 * @return true if a reasonable connection was found 467 */ 468 private boolean isConnectedTo(Node node, Set<Node> visited, double len, Way parent) { 469 if (len > maxLen) { 470 return false; 471 } 472 if (n1 == node || n2 == node) { 473 Node uncon = visited.iterator().next(); 474 LatLon cl = ProjectionRegistry.getProjection().eastNorth2latlon(calcClosest(uncon)); 475 // calculate real detour length, closest point might be somewhere between n1 and n2 476 double detourLen = len + node.greatCircleDistance(cl); 477 if (detourLen > maxLen) 478 return false; 479 // see #17914: flag also nodes which are very close 480 double directDist = getDist(uncon); 481 if (directDist <= 0.1) 482 return false; 483 return directDist > 0.5 || (visited.size() == 2 && directDist * 1.5 > detourLen); 484 } 485 if (visited != null) { 486 visited.add(node); 487 List<Way> wantedParents = node.getParentWays().stream().filter(UnconnectedWays.this::isWantedWay) 488 .collect(Collectors.toList()); 489 if (wantedParents.size() > 1 && wantedParents.indexOf(parent) != wantedParents.size() - 1) { 490 // we want to find a different way. so move known way to the end of the list 491 wantedParents.remove(parent); 492 wantedParents.add(parent); 493 } 494 495 for (final Way way : wantedParents) { 496 List<Node> nextNodes = new ArrayList<>(); 497 int pos = way.getNodes().indexOf(node); 498 if (pos > 0) { 499 nextNodes.add(way.getNode(pos - 1)); 500 } 501 if (pos + 1 < way.getNodesCount()) { 502 nextNodes.add(way.getNode(pos + 1)); 503 } 504 for (Node next : nextNodes) { 505 final boolean containsN = visited.contains(next); 506 visited.add(next); 507 if (!containsN && isConnectedTo(next, visited, 508 len + node.greatCircleDistance(next), way)) { 509 return true; 510 } 511 } 512 } 513 } 514 return false; 515 } 516 517 private EastNorth calcClosest(Node n) { 518 return Geometry.closestPointToSegment(n1.getEastNorth(), n2.getEastNorth(), n.getEastNorth()); 519 } 520 521 double getDist(Node n) { 522 EastNorth closest = calcClosest(n); 523 return n.greatCircleDistance(ProjectionRegistry.getProjection().eastNorth2latlon(closest)); 524 } 525 526 private boolean nearby(Node n, double dist) { 527 if (w.containsNode(n)) 528 return false; 529 double d = getDist(n); 530 return !Double.isNaN(d) && d < dist; 531 } 532 533 private BBox getBounds(double fudge) { 534 double x1 = n1.lon(); 535 double x2 = n2.lon(); 536 if (x1 > x2) { 537 double tmpx = x1; 538 x1 = x2; 539 x2 = tmpx; 540 } 541 double y1 = n1.lat(); 542 double y2 = n2.lat(); 543 if (y1 > y2) { 544 double tmpy = y1; 545 y1 = y2; 546 y2 = tmpy; 547 } 548 LatLon topLeft = new LatLon(y2+fudge, x1-fudge); 549 LatLon botRight = new LatLon(y1-fudge, x2+fudge); 550 return new BBox(topLeft, botRight); 551 } 552 553 /** 554 * We know that any point near the line segment must be at 555 * least as close as the other end of the line, plus 556 * a little fudge for the distance away (dist) 557 * @param dist fudge to add 558 * @return collection of nearby nodes 559 */ 560 Collection<Node> nearbyNodes(double dist) { 561 BBox bounds = this.getBounds(dist * (360.0d / (Ellipsoid.WGS84.a * 2 * Math.PI))); 562 List<Node> result = null; 563 List<Node> foundNodes = searchNodes.search(bounds); 564 for (Node n : foundNodes) { 565 if (!nearby(n, dist)) { 566 continue; 567 } 568 // It is actually very rare for us to find a node 569 // so defer as much of the work as possible, like 570 // allocating the hash set 571 if (result == null) { 572 result = new ArrayList<>(); 573 } 574 result.add(n); 575 } 576 return result == null ? Collections.emptyList() : result; 577 } 578 579 private boolean obstacleBetween(Node endnode) { 580 EastNorth en = endnode.getEastNorth(); 581 EastNorth closest = calcClosest(endnode); 582 LatLon llClosest = ProjectionRegistry.getProjection().eastNorth2latlon(closest); 583 // find obstacles between end node and way segment 584 BBox bbox = new BBox(endnode.getCoor(), llClosest); 585 for (Way nearbyWay : ds.searchWays(bbox)) { 586 if (nearbyWay != w && nearbyWay.isUsable() && isObstacle(nearbyWay) 587 && !endnode.getParentWays().contains(nearbyWay)) { 588 //make sure that the obstacle is really between endnode and the highway segment, not just close to or around them 589 Iterator<Node> iter = nearbyWay.getNodes().iterator(); 590 EastNorth prev = iter.next().getEastNorth(); 591 while (iter.hasNext()) { 592 EastNorth curr = iter.next().getEastNorth(); 593 if (Geometry.getSegmentSegmentIntersection(closest, en, prev, curr) != null) { 594 return true; 595 } 596 prev = curr; 597 } 598 } 599 } 600 return false; 601 } 602 603 private boolean isObstacle(Way w) { 604 return w.hasKey("barrier", "waterway") || isBuilding(w) || w.hasTag("man_made", "embankment", "dyke"); 605 } 606 } 607 608 List<MyWaySegment> getWaySegments(Way w) { 609 List<MyWaySegment> ret = new ArrayList<>(); 610 if (!w.isUsable() || w.isKeyTrue("disused")) 611 return ret; 612 613 int size = w.getNodesCount(); 614 boolean concersArea = w.concernsArea(); 615 for (int i = 1; i < size; ++i) { 616 if (i < size-1) { 617 addNode(w.getNode(i), middlenodes); 618 } 619 Node a = w.getNode(i-1); 620 Node b = w.getNode(i); 621 if (a.isLatLonKnown() && b.isLatLonKnown()) { 622 MyWaySegment ws = new MyWaySegment(w, a, b, concersArea); 623 ret.add(ws); 624 } 625 } 626 return ret; 627 } 628 629 @Override 630 public void visit(Way w) { 631 if (partialSelection) { 632 waysToTest.add(w); 633 } 634 } 635 636 @Override 637 public void visit(Node n) { 638 if (partialSelection) { 639 nodesToTest.add(n); 640 } 641 } 642 643 private void addNode(Node n, Set<Node> s) { 644 boolean m = middlenodes.contains(n); 645 boolean e = endnodes.contains(n); 646 boolean o = othernodes.contains(n); 647 if (!m && !e && !o) { 648 s.add(n); 649 } else if (!o) { 650 othernodes.add(n); 651 if (e) { 652 endnodes.remove(n); 653 } else { 654 middlenodes.remove(n); 655 } 656 } 657 } 658}