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.OsmUtils; 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.ValidatorPreference; 031import org.openstreetmap.josm.gui.progress.ProgressMonitor; 032 033/** 034 * Tests if there are segments that crosses in the same layer 035 * 036 * @author frsantos 037 */ 038public class UnconnectedWays extends Test { 039 040 protected static final int UNCONNECTED_WAYS = 1301; 041 protected static final String PREFIX = ValidatorPreference.PREFIX + "." + UnconnectedWays.class.getSimpleName(); 042 043 private Set<MyWaySegment> ways; 044 private QuadBuckets<Node> endnodes; // nodes at end of way 045 private QuadBuckets<Node> endnodes_highway; // nodes at end of way 046 private QuadBuckets<Node> middlenodes; // nodes in middle of way 047 private Set<Node> othernodes; // nodes appearing at least twice 048 private Area dsArea; 049 050 private double mindist; 051 private double minmiddledist; 052 053 /** 054 * Constructor 055 */ 056 public UnconnectedWays() { 057 super(tr("Unconnected ways"), 058 tr("This test checks if a way has an endpoint very near to another way.")); 059 } 060 061 @Override 062 public void startTest(ProgressMonitor monitor) { 063 super.startTest(monitor); 064 ways = new HashSet<MyWaySegment>(); 065 endnodes = new QuadBuckets<Node>(); 066 endnodes_highway = new QuadBuckets<Node>(); 067 middlenodes = new QuadBuckets<Node>(); 068 othernodes = new HashSet<Node>(); 069 mindist = Main.pref.getDouble(PREFIX + ".node_way_distance", 10.0); 070 minmiddledist = Main.pref.getDouble(PREFIX + ".way_way_distance", 0.0); 071 dsArea = Main.main.getCurrentDataSet().getDataSourceArea(); 072 } 073 074 @Override 075 public void endTest() { 076 Map<Node, Way> map = new HashMap<Node, Way>(); 077 for (int iter = 0; iter < 1; iter++) { 078 for (MyWaySegment s : ways) { 079 Collection<Node> nearbyNodes = s.nearbyNodes(mindist); 080 for (Node en : nearbyNodes) { 081 if (en == null || !s.highway || !endnodes_highway.contains(en)) { 082 continue; 083 } 084 if ("turning_circle".equals(en.get("highway")) 085 || "bus_stop".equals(en.get("highway")) 086 || "buffer_stop".equals(en.get("railway")) 087 || OsmUtils.isTrue(en.get("noexit")) 088 || en.hasKey("barrier")) { 089 continue; 090 } 091 // There's a small false-positive here. Imagine an intersection 092 // like a 't'. If the top part of the 't' is short enough, it 093 // will trigger the node at the very top of the 't' to be unconnected 094 // to the way that "crosses" the 't'. We should probably check that 095 // the ways to which 'en' belongs are not connected to 's.w'. 096 map.put(en, s.w); 097 } 098 if(isCanceled()) 099 return; 100 } 101 } 102 for (Map.Entry<Node, Way> error : map.entrySet()) { 103 errors.add(new TestError(this, Severity.WARNING, 104 tr("Way end node near other highway"), 105 UNCONNECTED_WAYS, 106 Arrays.asList(error.getKey(), error.getValue()), 107 Arrays.asList(error.getKey()))); 108 } 109 map.clear(); 110 for (MyWaySegment s : ways) { 111 if(isCanceled()) 112 return; 113 for (Node en : s.nearbyNodes(mindist)) { 114 if (endnodes_highway.contains(en) && !s.highway && !s.w.concernsArea()) { 115 map.put(en, s.w); 116 } else if (endnodes.contains(en) && !s.w.concernsArea()) { 117 map.put(en, s.w); 118 } 119 } 120 } 121 for (Map.Entry<Node, Way> error : map.entrySet()) { 122 errors.add(new TestError(this, Severity.WARNING, 123 tr("Way end node near other way"), 124 UNCONNECTED_WAYS, 125 Arrays.asList(error.getKey(), error.getValue()), 126 Arrays.asList(error.getKey()))); 127 } 128 /* the following two use a shorter distance */ 129 if (minmiddledist > 0.0) { 130 map.clear(); 131 for (MyWaySegment s : ways) { 132 if(isCanceled()) 133 return; 134 for (Node en : s.nearbyNodes(minmiddledist)) { 135 if (!middlenodes.contains(en)) { 136 continue; 137 } 138 map.put(en, s.w); 139 } 140 } 141 for (Map.Entry<Node, Way> error : map.entrySet()) { 142 errors.add(new TestError(this, Severity.OTHER, 143 tr("Way node near other way"), 144 UNCONNECTED_WAYS, 145 Arrays.asList(error.getKey(), error.getValue()), 146 Arrays.asList(error.getKey()))); 147 } 148 map.clear(); 149 for (MyWaySegment s : ways) { 150 for (Node en : s.nearbyNodes(minmiddledist)) { 151 if(isCanceled()) 152 return; 153 if (!othernodes.contains(en)) { 154 continue; 155 } 156 map.put(en, s.w); 157 } 158 } 159 for (Map.Entry<Node, Way> error : map.entrySet()) { 160 errors.add(new TestError(this, Severity.OTHER, 161 tr("Connected way end node near other way"), 162 UNCONNECTED_WAYS, 163 Arrays.asList(error.getKey(), error.getValue()), 164 Arrays.asList(error.getKey()))); 165 } 166 } 167 ways = null; 168 endnodes = null; 169 endnodes_highway = null; 170 middlenodes = null; 171 othernodes = null; 172 dsArea = null; 173 super.endTest(); 174 } 175 176 private class MyWaySegment { 177 private final Line2D line; 178 public final Way w; 179 public final boolean isAbandoned; 180 public final boolean isBoundary; 181 public final boolean highway; 182 private final double len; 183 private Set<Node> nearbyNodeCache; 184 double nearbyNodeCacheDist = -1.0; 185 final Node n1; 186 final Node n2; 187 188 public MyWaySegment(Way w, Node n1, Node n2) { 189 this.w = w; 190 String railway = w.get("railway"); 191 String highway = w.get("highway"); 192 this.isAbandoned = "abandoned".equals(railway) || OsmUtils.isTrue(w.get("disused")); 193 this.highway = (highway != null || railway != null) && !isAbandoned; 194 this.isBoundary = !this.highway && "administrative".equals(w.get("boundary")); 195 line = new Line2D.Double(n1.getEastNorth().east(), n1.getEastNorth().north(), 196 n2.getEastNorth().east(), n2.getEastNorth().north()); 197 len = line.getP1().distance(line.getP2()); 198 this.n1 = n1; 199 this.n2 = n2; 200 } 201 202 public boolean nearby(Node n, double dist) { 203 if (w == null) { 204 Main.debug("way null"); 205 return false; 206 } 207 if (w.containsNode(n)) 208 return false; 209 if (OsmUtils.isTrue(n.get("noexit"))) 210 return false; 211 EastNorth coord = n.getEastNorth(); 212 if (coord == null) 213 return false; 214 Point2D p = new Point2D.Double(coord.east(), coord.north()); 215 if (line.getP1().distance(p) > len+dist) 216 return false; 217 if (line.getP2().distance(p) > len+dist) 218 return false; 219 return line.ptSegDist(p) < dist; 220 } 221 222 public List<LatLon> getBounds(double fudge) { 223 double x1 = n1.getCoor().lon(); 224 double x2 = n2.getCoor().lon(); 225 if (x1 > x2) { 226 double tmpx = x1; 227 x1 = x2; 228 x2 = tmpx; 229 } 230 double y1 = n1.getCoor().lat(); 231 double y2 = n2.getCoor().lat(); 232 if (y1 > y2) { 233 double tmpy = y1; 234 y1 = y2; 235 y2 = tmpy; 236 } 237 LatLon topLeft = new LatLon(y2+fudge, x1-fudge); 238 LatLon botRight = new LatLon(y1-fudge, x2+fudge); 239 List<LatLon> ret = new ArrayList<LatLon>(2); 240 ret.add(topLeft); 241 ret.add(botRight); 242 return ret; 243 } 244 245 public Collection<Node> nearbyNodes(double dist) { 246 // If you're looking for nodes that are farther 247 // away that we looked for last time, the cached 248 // result is no good 249 if (dist > nearbyNodeCacheDist) { 250 nearbyNodeCache = null; 251 } 252 if (nearbyNodeCache != null) { 253 // If we've cached an aread greater than the 254 // one now being asked for... 255 if (nearbyNodeCacheDist > dist) { 256 // Used the cached result and trim out 257 // the nodes that are not in the smaller 258 // area, but keep the old larger cache. 259 Set<Node> trimmed = new HashSet<Node>(nearbyNodeCache); 260 Set<Node> initial = new HashSet<Node>(nearbyNodeCache); 261 for (Node n : initial) { 262 if (!nearby(n, dist)) { 263 trimmed.remove(n); 264 } 265 } 266 return trimmed; 267 } 268 return nearbyNodeCache; 269 } 270 /* 271 * We know that any point near the line must be at 272 * least as close as the other end of the line, plus 273 * a little fudge for the distance away ('dist'). 274 */ 275 276 // This needs to be a hash set because the searches 277 // overlap a bit and can return duplicate nodes. 278 nearbyNodeCache = null; 279 List<LatLon> bounds = this.getBounds(dist); 280 List<Node> found_nodes = endnodes_highway.search(new BBox(bounds.get(0), bounds.get(1))); 281 found_nodes.addAll(endnodes.search(new BBox(bounds.get(0), bounds.get(1)))); 282 283 for (Node n : found_nodes) { 284 if (!nearby(n, dist) || !n.getCoor().isIn(dsArea)) { 285 continue; 286 } 287 // It is actually very rare for us to find a node 288 // so defer as much of the work as possible, like 289 // allocating the hash set 290 if (nearbyNodeCache == null) { 291 nearbyNodeCache = new HashSet<Node>(); 292 } 293 nearbyNodeCache.add(n); 294 } 295 nearbyNodeCacheDist = dist; 296 if (nearbyNodeCache == null) { 297 nearbyNodeCache = Collections.emptySet(); 298 } 299 return nearbyNodeCache; 300 } 301 } 302 303 List<MyWaySegment> getWaySegments(Way w) { 304 List<MyWaySegment> ret = new ArrayList<MyWaySegment>(); 305 if (!w.isUsable() 306 || w.hasKey("barrier") 307 || "cliff".equals(w.get("natural"))) 308 return ret; 309 310 int size = w.getNodesCount(); 311 if (size < 2) 312 return ret; 313 for (int i = 1; i < size; ++i) { 314 if(i < size-1) { 315 addNode(w.getNode(i), middlenodes); 316 } 317 Node a = w.getNode(i-1); 318 Node b = w.getNode(i); 319 if (a.isDrawable() && b.isDrawable()) { 320 MyWaySegment ws = new MyWaySegment(w, a, b); 321 if (ws.isBoundary || ws.isAbandoned) { 322 continue; 323 } 324 ret.add(ws); 325 } 326 } 327 return ret; 328 } 329 330 @Override 331 public void visit(Way w) { 332 // Do not consider empty ways and addr:interpolation ways as they are not physical features and most of the time 333 // very near the associated highway, which is perfectly normal, see #9332 334 if (w.getNodesCount() > 0 && !w.hasKey("addr:interpolation")) { 335 ways.addAll(getWaySegments(w)); 336 QuadBuckets<Node> set = endnodes; 337 if (w.hasKey("highway") || w.hasKey("railway")) { 338 set = endnodes_highway; 339 } 340 addNode(w.firstNode(), set); 341 addNode(w.lastNode(), set); 342 } 343 } 344 345 @Override 346 public void visit(Node n) { 347 } 348 349 private void addNode(Node n, QuadBuckets<Node> s) { 350 boolean m = middlenodes.contains(n); 351 boolean e = endnodes.contains(n); 352 boolean eh = endnodes_highway.contains(n); 353 boolean o = othernodes.contains(n); 354 if (!m && !e && !o && !eh) { 355 s.add(n); 356 } else if (!o) { 357 othernodes.add(n); 358 if (e) { 359 endnodes.remove(n); 360 } else if (eh) { 361 endnodes_highway.remove(n); 362 } else { 363 middlenodes.remove(n); 364 } 365 } 366 } 367}