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