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    }