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.awt.geom.Line2D; 010import java.awt.geom.Point2D; 011import java.util.ArrayList; 012import java.util.Collection; 013import java.util.Collections; 014import java.util.HashMap; 015import java.util.HashSet; 016import java.util.List; 017import java.util.Map; 018import java.util.Set; 019 020import org.openstreetmap.josm.data.coor.EastNorth; 021import org.openstreetmap.josm.data.coor.LatLon; 022import org.openstreetmap.josm.data.osm.BBox; 023import org.openstreetmap.josm.data.osm.DataSet; 024import org.openstreetmap.josm.data.osm.Node; 025import org.openstreetmap.josm.data.osm.OsmDataManager; 026import org.openstreetmap.josm.data.osm.OsmPrimitive; 027import org.openstreetmap.josm.data.osm.QuadBuckets; 028import org.openstreetmap.josm.data.osm.Way; 029import org.openstreetmap.josm.data.preferences.sources.ValidatorPrefHelper; 030import org.openstreetmap.josm.data.projection.Ellipsoid; 031import org.openstreetmap.josm.data.validation.Severity; 032import org.openstreetmap.josm.data.validation.Test; 033import org.openstreetmap.josm.data.validation.TestError; 034import org.openstreetmap.josm.gui.progress.ProgressMonitor; 035import org.openstreetmap.josm.spi.preferences.Config; 036import org.openstreetmap.josm.tools.Logging; 037 038/** 039 * Checks if a way has an endpoint very near to another way. 040 * <br> 041 * This class is abstract since highway/railway/waterway/… ways must be handled separately. 042 * An actual implementation must override {@link #isPrimitiveUsable(OsmPrimitive)} 043 * to denote which kind of primitives can be handled. 044 * 045 * @author frsantos 046 */ 047public abstract class UnconnectedWays extends Test { 048 private final int code; 049 050 /** 051 * Unconnected highways test. 052 */ 053 public static class UnconnectedHighways extends UnconnectedWays { 054 static final int UNCONNECTED_HIGHWAYS = 1311; 055 056 /** 057 * Constructs a new {@code UnconnectedHighways} test. 058 */ 059 public UnconnectedHighways() { 060 super(tr("Unconnected highways"), UNCONNECTED_HIGHWAYS); 061 } 062 063 @Override 064 public boolean isPrimitiveUsable(OsmPrimitive p) { 065 return super.isPrimitiveUsable(p) && p.hasKey(HIGHWAY); 066 } 067 } 068 069 /** 070 * Unconnected railways test. 071 */ 072 public static class UnconnectedRailways extends UnconnectedWays { 073 static final int UNCONNECTED_RAILWAYS = 1321; 074 /** 075 * Constructs a new {@code UnconnectedRailways} test. 076 */ 077 public UnconnectedRailways() { 078 super(tr("Unconnected railways"), UNCONNECTED_RAILWAYS); 079 } 080 081 @Override 082 public boolean isPrimitiveUsable(OsmPrimitive p) { 083 return super.isPrimitiveUsable(p) && p.hasKey("railway"); 084 } 085 } 086 087 /** 088 * Unconnected waterways test. 089 */ 090 public static class UnconnectedWaterways extends UnconnectedWays { 091 static final int UNCONNECTED_WATERWAYS = 1331; 092 /** 093 * Constructs a new {@code UnconnectedWaterways} test. 094 */ 095 public UnconnectedWaterways() { 096 super(tr("Unconnected waterways"), UNCONNECTED_WATERWAYS); 097 } 098 099 @Override 100 public boolean isPrimitiveUsable(OsmPrimitive p) { 101 return super.isPrimitiveUsable(p) && p.hasKey("waterway"); 102 } 103 } 104 105 /** 106 * Unconnected natural/landuse test. 107 */ 108 public static class UnconnectedNaturalOrLanduse extends UnconnectedWays { 109 static final int UNCONNECTED_NATURAL_OR_LANDUSE = 1341; 110 /** 111 * Constructs a new {@code UnconnectedNaturalOrLanduse} test. 112 */ 113 public UnconnectedNaturalOrLanduse() { 114 super(tr("Unconnected natural lands and landuses"), UNCONNECTED_NATURAL_OR_LANDUSE); 115 } 116 117 @Override 118 public boolean isPrimitiveUsable(OsmPrimitive p) { 119 return super.isPrimitiveUsable(p) && p.hasKey("natural", "landuse"); 120 } 121 } 122 123 /** 124 * Unconnected power ways test. 125 */ 126 public static class UnconnectedPower extends UnconnectedWays { 127 static final int UNCONNECTED_POWER = 1351; 128 /** 129 * Constructs a new {@code UnconnectedPower} test. 130 */ 131 public UnconnectedPower() { 132 super(tr("Unconnected power ways"), UNCONNECTED_POWER); 133 } 134 135 @Override 136 public boolean isPrimitiveUsable(OsmPrimitive p) { 137 return super.isPrimitiveUsable(p) && p.hasTag("power", "line", "minor_line", "cable"); 138 } 139 } 140 141 protected static final int UNCONNECTED_WAYS = 1301; 142 protected static final String PREFIX = ValidatorPrefHelper.PREFIX + "." + UnconnectedWays.class.getSimpleName(); 143 144 private Set<MyWaySegment> ways; 145 private QuadBuckets<Node> endnodes; // nodes at end of way 146 private QuadBuckets<Node> endnodesHighway; // nodes at end of way 147 private QuadBuckets<Node> middlenodes; // nodes in middle of way 148 private Set<Node> othernodes; // nodes appearing at least twice 149 private Area dsArea; 150 151 private double mindist; 152 private double minmiddledist; 153 154 /** 155 * Constructs a new {@code UnconnectedWays} test. 156 * @param title The test title 157 * @since 6691 158 */ 159 public UnconnectedWays(String title) { 160 this(title, UNCONNECTED_WAYS); 161 162 } 163 164 /** 165 * Constructs a new {@code UnconnectedWays} test with the given code. 166 * @param title The test title 167 * @param code The test code 168 * @since 14468 169 */ 170 public UnconnectedWays(String title, int code) { 171 super(title, tr("This test checks if a way has an endpoint very near to another way.")); 172 this.code = code; 173 } 174 175 @Override 176 public void startTest(ProgressMonitor monitor) { 177 super.startTest(monitor); 178 ways = new HashSet<>(); 179 endnodes = new QuadBuckets<>(); 180 endnodesHighway = new QuadBuckets<>(); 181 middlenodes = new QuadBuckets<>(); 182 othernodes = new HashSet<>(); 183 mindist = Config.getPref().getDouble(PREFIX + ".node_way_distance", 10.0); 184 minmiddledist = Config.getPref().getDouble(PREFIX + ".way_way_distance", 0.0); 185 DataSet dataSet = OsmDataManager.getInstance().getEditDataSet(); 186 dsArea = dataSet == null ? null : dataSet.getDataSourceArea(); 187 } 188 189 protected Map<Node, Way> getWayEndNodesNearOtherHighway() { 190 Map<Node, Way> map = new HashMap<>(); 191 for (int iter = 0; iter < 1; iter++) { 192 for (MyWaySegment s : ways) { 193 if (isCanceled()) { 194 map.clear(); 195 return map; 196 } 197 if (s.highway) { 198 for (Node en : s.nearbyNodes(mindist)) { 199 if (en == null || !endnodesHighway.contains(en)) { 200 continue; 201 } 202 if (en.hasTag(HIGHWAY, "turning_circle", "bus_stop") 203 || en.hasTag("amenity", "parking_entrance") 204 || en.hasTag(RAILWAY, "buffer_stop") 205 || en.isKeyTrue("noexit") 206 || en.hasKey("entrance", "barrier")) { 207 continue; 208 } 209 // to handle intersections of 't' shapes and similar 210 if (en.isConnectedTo(s.w.getNodes(), 3 /* hops */, null)) { 211 continue; 212 } 213 map.put(en, s.w); 214 } 215 } 216 } 217 } 218 return map; 219 } 220 221 protected Map<Node, Way> getWayEndNodesNearOtherWay() { 222 Map<Node, Way> map = new HashMap<>(); 223 for (MyWaySegment s : ways) { 224 if (isCanceled()) { 225 map.clear(); 226 return map; 227 } 228 for (Node en : s.nearbyNodes(mindist)) { 229 if (en.isConnectedTo(s.w.getNodes(), 3 /* hops */, null)) { 230 continue; 231 } 232 if (((!s.highway && endnodesHighway.contains(en)) || endnodes.contains(en)) && !s.w.concernsArea()) { 233 map.put(en, s.w); 234 } 235 } 236 } 237 return map; 238 } 239 240 protected Map<Node, Way> getWayNodesNearOtherWay() { 241 Map<Node, Way> map = new HashMap<>(); 242 for (MyWaySegment s : ways) { 243 if (isCanceled()) { 244 map.clear(); 245 return map; 246 } 247 for (Node en : s.nearbyNodes(minmiddledist)) { 248 if (en.isConnectedTo(s.w.getNodes(), 3 /* hops */, null)) { 249 continue; 250 } 251 if (!middlenodes.contains(en)) { 252 continue; 253 } 254 map.put(en, s.w); 255 } 256 } 257 return map; 258 } 259 260 protected Map<Node, Way> getConnectedWayEndNodesNearOtherWay() { 261 Map<Node, Way> map = new HashMap<>(); 262 for (MyWaySegment s : ways) { 263 if (isCanceled()) { 264 map.clear(); 265 return map; 266 } 267 for (Node en : s.nearbyNodes(minmiddledist)) { 268 if (en.isConnectedTo(s.w.getNodes(), 3 /* hops */, null)) { 269 continue; 270 } 271 if (!othernodes.contains(en)) { 272 continue; 273 } 274 map.put(en, s.w); 275 } 276 } 277 return map; 278 } 279 280 protected final void addErrors(Severity severity, Map<Node, Way> errorMap, String message) { 281 for (Map.Entry<Node, Way> error : errorMap.entrySet()) { 282 errors.add(TestError.builder(this, severity, code) 283 .message(message) 284 .primitives(error.getKey(), error.getValue()) 285 .highlight(error.getKey()) 286 .build()); 287 } 288 } 289 290 @Override 291 public void endTest() { 292 addErrors(Severity.WARNING, getWayEndNodesNearOtherHighway(), tr("Way end node near other highway")); 293 addErrors(Severity.WARNING, getWayEndNodesNearOtherWay(), tr("Way end node near other way")); 294 /* the following two use a shorter distance */ 295 if (minmiddledist > 0.0) { 296 addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Way node near other way")); 297 addErrors(Severity.OTHER, getConnectedWayEndNodesNearOtherWay(), tr("Connected way end node near other way")); 298 } 299 ways = null; 300 endnodes = null; 301 endnodesHighway = null; 302 middlenodes = null; 303 othernodes = null; 304 dsArea = null; 305 super.endTest(); 306 } 307 308 private class MyWaySegment { 309 private final Line2D line; 310 public final Way w; 311 public final boolean isAbandoned; 312 public final boolean isBoundary; 313 public final boolean highway; 314 private final double len; 315 private Set<Node> nearbyNodeCache; 316 private double nearbyNodeCacheDist = -1.0; 317 private final Node n1; 318 private final Node n2; 319 320 MyWaySegment(Way w, Node n1, Node n2) { 321 this.w = w; 322 String railway = w.get(RAILWAY); 323 String highway = w.get(HIGHWAY); 324 this.isAbandoned = "abandoned".equals(railway) || w.isKeyTrue("disused"); 325 this.highway = (highway != null || railway != null) && !isAbandoned; 326 this.isBoundary = !this.highway && w.hasTag("boundary", "administrative"); 327 line = new Line2D.Double(n1.getEastNorth().east(), n1.getEastNorth().north(), 328 n2.getEastNorth().east(), n2.getEastNorth().north()); 329 len = line.getP1().distance(line.getP2()); 330 this.n1 = n1; 331 this.n2 = n2; 332 } 333 334 public boolean nearby(Node n, double dist) { 335 if (w == null) { 336 Logging.debug("way null"); 337 return false; 338 } 339 if (w.containsNode(n)) 340 return false; 341 if (n.isKeyTrue("noexit")) 342 return false; 343 EastNorth coord = n.getEastNorth(); 344 if (coord == null) 345 return false; 346 Point2D p = new Point2D.Double(coord.east(), coord.north()); 347 if (line.getP1().distance(p) > len+dist) 348 return false; 349 if (line.getP2().distance(p) > len+dist) 350 return false; 351 return line.ptSegDist(p) < dist; 352 } 353 354 public List<LatLon> getBounds(double fudge) { 355 double x1 = n1.getCoor().lon(); 356 double x2 = n2.getCoor().lon(); 357 if (x1 > x2) { 358 double tmpx = x1; 359 x1 = x2; 360 x2 = tmpx; 361 } 362 double y1 = n1.getCoor().lat(); 363 double y2 = n2.getCoor().lat(); 364 if (y1 > y2) { 365 double tmpy = y1; 366 y1 = y2; 367 y2 = tmpy; 368 } 369 LatLon topLeft = new LatLon(y2+fudge, x1-fudge); 370 LatLon botRight = new LatLon(y1-fudge, x2+fudge); 371 List<LatLon> ret = new ArrayList<>(2); 372 ret.add(topLeft); 373 ret.add(botRight); 374 return ret; 375 } 376 377 public Collection<Node> nearbyNodes(double dist) { 378 // If you're looking for nodes that are farther away that we looked for last time, 379 // the cached result is no good 380 if (dist > nearbyNodeCacheDist) { 381 nearbyNodeCache = null; 382 } 383 if (nearbyNodeCache != null) { 384 // If we've cached an area greater than the 385 // one now being asked for... 386 if (nearbyNodeCacheDist > dist) { 387 // Used the cached result and trim out 388 // the nodes that are not in the smaller 389 // area, but keep the old larger cache. 390 Set<Node> trimmed = new HashSet<>(nearbyNodeCache); 391 Set<Node> initial = new HashSet<>(nearbyNodeCache); 392 for (Node n : initial) { 393 if (!nearby(n, dist)) { 394 trimmed.remove(n); 395 } 396 } 397 return trimmed; 398 } 399 return nearbyNodeCache; 400 } 401 /* 402 * We know that any point near the line must be at 403 * least as close as the other end of the line, plus 404 * a little fudge for the distance away ('dist'). 405 */ 406 407 // This needs to be a hash set because the searches 408 // overlap a bit and can return duplicate nodes. 409 nearbyNodeCache = null; 410 List<LatLon> bounds = this.getBounds(dist * (360.0d / (Ellipsoid.WGS84.a * 2 * Math.PI))); 411 List<Node> foundNodes = endnodesHighway.search(new BBox(bounds.get(0), bounds.get(1))); 412 foundNodes.addAll(endnodes.search(new BBox(bounds.get(0), bounds.get(1)))); 413 414 for (Node n : foundNodes) { 415 if (!nearby(n, dist) || !n.getCoor().isIn(dsArea)) { 416 continue; 417 } 418 // It is actually very rare for us to find a node 419 // so defer as much of the work as possible, like 420 // allocating the hash set 421 if (nearbyNodeCache == null) { 422 nearbyNodeCache = new HashSet<>(); 423 } 424 nearbyNodeCache.add(n); 425 } 426 nearbyNodeCacheDist = dist; 427 if (nearbyNodeCache == null) { 428 nearbyNodeCache = Collections.emptySet(); 429 } 430 return nearbyNodeCache; 431 } 432 } 433 434 List<MyWaySegment> getWaySegments(Way w) { 435 List<MyWaySegment> ret = new ArrayList<>(); 436 if (!w.isUsable() 437 || w.hasKey("barrier") 438 || w.hasTag("natural", "cliff")) 439 return ret; 440 441 int size = w.getNodesCount(); 442 if (size < 2) 443 return ret; 444 for (int i = 1; i < size; ++i) { 445 if (i < size-1) { 446 addNode(w.getNode(i), middlenodes); 447 } 448 Node a = w.getNode(i-1); 449 Node b = w.getNode(i); 450 if (a.isDrawable() && b.isDrawable()) { 451 MyWaySegment ws = new MyWaySegment(w, a, b); 452 if (ws.isBoundary || ws.isAbandoned) { 453 continue; 454 } 455 ret.add(ws); 456 } 457 } 458 return ret; 459 } 460 461 @Override 462 public void visit(Way w) { 463 // do not consider empty ways 464 if (w.getNodesCount() > 0 465 // ignore addr:interpolation ways as they are not physical features and most of 466 // the time very near the associated highway, which is perfectly normal, see #9332 467 && !w.hasKey("addr:interpolation") 468 // similarly for public transport platforms, tree rows 469 && !w.hasTag(HIGHWAY, "platform") && !w.hasTag(RAILWAY, "platform", "platform_edge") && !w.hasTag("natural", "tree_row") 470 ) { 471 ways.addAll(getWaySegments(w)); 472 QuadBuckets<Node> set = endnodes; 473 if (w.hasKey(HIGHWAY, RAILWAY)) { 474 set = endnodesHighway; 475 } 476 addNode(w.firstNode(), set); 477 addNode(w.lastNode(), set); 478 } 479 } 480 481 private void addNode(Node n, QuadBuckets<Node> s) { 482 boolean m = middlenodes.contains(n); 483 boolean e = endnodes.contains(n); 484 boolean eh = endnodesHighway.contains(n); 485 boolean o = othernodes.contains(n); 486 if (!m && !e && !o && !eh) { 487 s.add(n); 488 } else if (!o) { 489 othernodes.add(n); 490 if (e) { 491 endnodes.remove(n); 492 } else if (eh) { 493 endnodesHighway.remove(n); 494 } else { 495 middlenodes.remove(n); 496 } 497 } 498 } 499}