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