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