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.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.DataSet; 024import org.openstreetmap.josm.data.osm.Node; 025import org.openstreetmap.josm.data.osm.OsmPrimitive; 026import org.openstreetmap.josm.data.osm.QuadBuckets; 027import org.openstreetmap.josm.data.osm.Way; 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(new TestError(this, severity, message, UNCONNECTED_WAYS, 266 Arrays.asList(error.getKey(), error.getValue()), 267 Arrays.asList(error.getKey()))); 268 } 269 } 270 271 @Override 272 public void endTest() { 273 addErrors(Severity.WARNING, getWayEndNodesNearOtherHighway(), tr("Way end node near other highway")); 274 addErrors(Severity.WARNING, getWayEndNodesNearOtherWay(), tr("Way end node near other way")); 275 /* the following two use a shorter distance */ 276 if (minmiddledist > 0.0) { 277 addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Way node near other way")); 278 addErrors(Severity.OTHER, getConnectedWayEndNodesNearOtherWay(), tr("Connected way end node near other way")); 279 } 280 ways = null; 281 endnodes = null; 282 endnodesHighway = null; 283 middlenodes = null; 284 othernodes = null; 285 dsArea = null; 286 super.endTest(); 287 } 288 289 private class MyWaySegment { 290 private final Line2D line; 291 public final Way w; 292 public final boolean isAbandoned; 293 public final boolean isBoundary; 294 public final boolean highway; 295 private final double len; 296 private Set<Node> nearbyNodeCache; 297 private double nearbyNodeCacheDist = -1.0; 298 private final Node n1; 299 private final Node n2; 300 301 MyWaySegment(Way w, Node n1, Node n2) { 302 this.w = w; 303 String railway = w.get("railway"); 304 String highway = w.get("highway"); 305 this.isAbandoned = "abandoned".equals(railway) || w.isKeyTrue("disused"); 306 this.highway = (highway != null || railway != null) && !isAbandoned; 307 this.isBoundary = !this.highway && "administrative".equals(w.get("boundary")); 308 line = new Line2D.Double(n1.getEastNorth().east(), n1.getEastNorth().north(), 309 n2.getEastNorth().east(), n2.getEastNorth().north()); 310 len = line.getP1().distance(line.getP2()); 311 this.n1 = n1; 312 this.n2 = n2; 313 } 314 315 public boolean nearby(Node n, double dist) { 316 if (w == null) { 317 Main.debug("way null"); 318 return false; 319 } 320 if (w.containsNode(n)) 321 return false; 322 if (n.isKeyTrue("noexit")) 323 return false; 324 EastNorth coord = n.getEastNorth(); 325 if (coord == null) 326 return false; 327 Point2D p = new Point2D.Double(coord.east(), coord.north()); 328 if (line.getP1().distance(p) > len+dist) 329 return false; 330 if (line.getP2().distance(p) > len+dist) 331 return false; 332 return line.ptSegDist(p) < dist; 333 } 334 335 public List<LatLon> getBounds(double fudge) { 336 double x1 = n1.getCoor().lon(); 337 double x2 = n2.getCoor().lon(); 338 if (x1 > x2) { 339 double tmpx = x1; 340 x1 = x2; 341 x2 = tmpx; 342 } 343 double y1 = n1.getCoor().lat(); 344 double y2 = n2.getCoor().lat(); 345 if (y1 > y2) { 346 double tmpy = y1; 347 y1 = y2; 348 y2 = tmpy; 349 } 350 LatLon topLeft = new LatLon(y2+fudge, x1-fudge); 351 LatLon botRight = new LatLon(y1-fudge, x2+fudge); 352 List<LatLon> ret = new ArrayList<>(2); 353 ret.add(topLeft); 354 ret.add(botRight); 355 return ret; 356 } 357 358 public Collection<Node> nearbyNodes(double dist) { 359 // If you're looking for nodes that are farther away that we looked for last time, 360 // the cached result is no good 361 if (dist > nearbyNodeCacheDist) { 362 nearbyNodeCache = null; 363 } 364 if (nearbyNodeCache != null) { 365 // If we've cached an area greater than the 366 // one now being asked for... 367 if (nearbyNodeCacheDist > dist) { 368 // Used the cached result and trim out 369 // the nodes that are not in the smaller 370 // area, but keep the old larger cache. 371 Set<Node> trimmed = new HashSet<>(nearbyNodeCache); 372 Set<Node> initial = new HashSet<>(nearbyNodeCache); 373 for (Node n : initial) { 374 if (!nearby(n, dist)) { 375 trimmed.remove(n); 376 } 377 } 378 return trimmed; 379 } 380 return nearbyNodeCache; 381 } 382 /* 383 * We know that any point near the line must be at 384 * least as close as the other end of the line, plus 385 * a little fudge for the distance away ('dist'). 386 */ 387 388 // This needs to be a hash set because the searches 389 // overlap a bit and can return duplicate nodes. 390 nearbyNodeCache = null; 391 List<LatLon> bounds = this.getBounds(dist); 392 List<Node> foundNodes = endnodesHighway.search(new BBox(bounds.get(0), bounds.get(1))); 393 foundNodes.addAll(endnodes.search(new BBox(bounds.get(0), bounds.get(1)))); 394 395 for (Node n : foundNodes) { 396 if (!nearby(n, dist) || !n.getCoor().isIn(dsArea)) { 397 continue; 398 } 399 // It is actually very rare for us to find a node 400 // so defer as much of the work as possible, like 401 // allocating the hash set 402 if (nearbyNodeCache == null) { 403 nearbyNodeCache = new HashSet<>(); 404 } 405 nearbyNodeCache.add(n); 406 } 407 nearbyNodeCacheDist = dist; 408 if (nearbyNodeCache == null) { 409 nearbyNodeCache = Collections.emptySet(); 410 } 411 return nearbyNodeCache; 412 } 413 } 414 415 List<MyWaySegment> getWaySegments(Way w) { 416 List<MyWaySegment> ret = new ArrayList<>(); 417 if (!w.isUsable() 418 || w.hasKey("barrier") 419 || w.hasTag("natural", "cliff")) 420 return ret; 421 422 int size = w.getNodesCount(); 423 if (size < 2) 424 return ret; 425 for (int i = 1; i < size; ++i) { 426 if (i < size-1) { 427 addNode(w.getNode(i), middlenodes); 428 } 429 Node a = w.getNode(i-1); 430 Node b = w.getNode(i); 431 if (a.isDrawable() && b.isDrawable()) { 432 MyWaySegment ws = new MyWaySegment(w, a, b); 433 if (ws.isBoundary || ws.isAbandoned) { 434 continue; 435 } 436 ret.add(ws); 437 } 438 } 439 return ret; 440 } 441 442 @Override 443 public void visit(Way w) { 444 if (w.getNodesCount() > 0 // do not consider empty ways 445 && !w.hasKey("addr:interpolation") // ignore addr:interpolation ways as they are not physical features and most of 446 // the time very near the associated highway, which is perfectly normal, see #9332 447 && !w.hasTag("highway", "platform") && !w.hasTag("railway", "platform") // similarly for public transport platforms 448 ) { 449 ways.addAll(getWaySegments(w)); 450 QuadBuckets<Node> set = endnodes; 451 if (w.hasKey("highway") || w.hasKey("railway")) { 452 set = endnodesHighway; 453 } 454 addNode(w.firstNode(), set); 455 addNode(w.lastNode(), set); 456 } 457 } 458 459 private void addNode(Node n, QuadBuckets<Node> s) { 460 boolean m = middlenodes.contains(n); 461 boolean e = endnodes.contains(n); 462 boolean eh = endnodesHighway.contains(n); 463 boolean o = othernodes.contains(n); 464 if (!m && !e && !o && !eh) { 465 s.add(n); 466 } else if (!o) { 467 othernodes.add(n); 468 if (e) { 469 endnodes.remove(n); 470 } else if (eh) { 471 endnodesHighway.remove(n); 472 } else { 473 middlenodes.remove(n); 474 } 475 } 476 } 477}