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