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