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 }