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