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