001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.validation.tests;
003
004import static org.openstreetmap.josm.data.validation.tests.CrossingWays.HIGHWAY;
005import static org.openstreetmap.josm.data.validation.tests.CrossingWays.RAILWAY;
006import static org.openstreetmap.josm.tools.I18n.tr;
007
008import java.awt.geom.Area;
009import java.awt.geom.Line2D;
010import java.awt.geom.Point2D;
011import java.util.ArrayList;
012import java.util.Collection;
013import java.util.Collections;
014import java.util.HashMap;
015import java.util.HashSet;
016import java.util.List;
017import java.util.Map;
018import java.util.Set;
019
020import org.openstreetmap.josm.Main;
021import org.openstreetmap.josm.data.coor.EastNorth;
022import org.openstreetmap.josm.data.coor.LatLon;
023import org.openstreetmap.josm.data.osm.BBox;
024import org.openstreetmap.josm.data.osm.DataSet;
025import org.openstreetmap.josm.data.osm.Node;
026import org.openstreetmap.josm.data.osm.OsmPrimitive;
027import org.openstreetmap.josm.data.osm.QuadBuckets;
028import org.openstreetmap.josm.data.osm.Way;
029import org.openstreetmap.josm.data.preferences.sources.ValidatorPrefHelper;
030import org.openstreetmap.josm.data.projection.Ellipsoid;
031import org.openstreetmap.josm.data.validation.Severity;
032import org.openstreetmap.josm.data.validation.Test;
033import org.openstreetmap.josm.data.validation.TestError;
034import org.openstreetmap.josm.gui.progress.ProgressMonitor;
035import org.openstreetmap.josm.spi.preferences.Config;
036import org.openstreetmap.josm.tools.Logging;
037
038/**
039 * Checks if a way has an endpoint very near to another way.
040 * <br>
041 * This class is abstract since highway/railway/waterway/… ways must be handled separately.
042 * An actual implementation must override {@link #isPrimitiveUsable(OsmPrimitive)}
043 * to denote which kind of primitives can be handled.
044 *
045 * @author frsantos
046 */
047public abstract class UnconnectedWays extends Test {
048
049    /**
050     * Unconnected highways test.
051     */
052    public static class UnconnectedHighways extends UnconnectedWays {
053
054        /**
055         * Constructs a new {@code UnconnectedHighways} test.
056         */
057        public UnconnectedHighways() {
058            super(tr("Unconnected highways"));
059        }
060
061        @Override
062        public boolean isPrimitiveUsable(OsmPrimitive p) {
063            return super.isPrimitiveUsable(p) && p.hasKey(HIGHWAY);
064        }
065    }
066
067    /**
068     * Unconnected railways test.
069     */
070    public static class UnconnectedRailways extends UnconnectedWays {
071
072        /**
073         * Constructs a new {@code UnconnectedRailways} test.
074         */
075        public UnconnectedRailways() {
076            super(tr("Unconnected railways"));
077        }
078
079        @Override
080        public boolean isPrimitiveUsable(OsmPrimitive p) {
081            return super.isPrimitiveUsable(p) && p.hasKey("railway");
082        }
083    }
084
085    /**
086     * Unconnected waterways test.
087     */
088    public static class UnconnectedWaterways extends UnconnectedWays {
089
090        /**
091         * Constructs a new {@code UnconnectedWaterways} test.
092         */
093        public UnconnectedWaterways() {
094            super(tr("Unconnected waterways"));
095        }
096
097        @Override
098        public boolean isPrimitiveUsable(OsmPrimitive p) {
099            return super.isPrimitiveUsable(p) && p.hasKey("waterway");
100        }
101    }
102
103    /**
104     * Unconnected natural/landuse test.
105     */
106    public static class UnconnectedNaturalOrLanduse extends UnconnectedWays {
107
108        /**
109         * Constructs a new {@code UnconnectedNaturalOrLanduse} test.
110         */
111        public UnconnectedNaturalOrLanduse() {
112            super(tr("Unconnected natural lands and landuses"));
113        }
114
115        @Override
116        public boolean isPrimitiveUsable(OsmPrimitive p) {
117            return super.isPrimitiveUsable(p) && p.hasKey("natural", "landuse");
118        }
119    }
120
121    /**
122     * Unconnected power ways test.
123     */
124    public static class UnconnectedPower extends UnconnectedWays {
125
126        /**
127         * Constructs a new {@code UnconnectedPower} test.
128         */
129        public UnconnectedPower() {
130            super(tr("Unconnected power ways"));
131        }
132
133        @Override
134        public boolean isPrimitiveUsable(OsmPrimitive p) {
135            return super.isPrimitiveUsable(p) && p.hasTag("power", "line", "minor_line", "cable");
136        }
137    }
138
139    protected static final int UNCONNECTED_WAYS = 1301;
140    protected static final String PREFIX = ValidatorPrefHelper.PREFIX + "." + UnconnectedWays.class.getSimpleName();
141
142    private Set<MyWaySegment> ways;
143    private QuadBuckets<Node> endnodes; // nodes at end of way
144    private QuadBuckets<Node> endnodesHighway; // nodes at end of way
145    private QuadBuckets<Node> middlenodes; // nodes in middle of way
146    private Set<Node> othernodes; // nodes appearing at least twice
147    private Area dsArea;
148
149    private double mindist;
150    private double minmiddledist;
151
152    /**
153     * Constructs a new {@code UnconnectedWays} test.
154     * @param title The test title
155     * @since 6691
156     */
157    public UnconnectedWays(String title) {
158        super(title, tr("This test checks if a way has an endpoint very near to another way."));
159    }
160
161    @Override
162    public void startTest(ProgressMonitor monitor) {
163        super.startTest(monitor);
164        ways = new HashSet<>();
165        endnodes = new QuadBuckets<>();
166        endnodesHighway = new QuadBuckets<>();
167        middlenodes = new QuadBuckets<>();
168        othernodes = new HashSet<>();
169        mindist = Config.getPref().getDouble(PREFIX + ".node_way_distance", 10.0);
170        minmiddledist = Config.getPref().getDouble(PREFIX + ".way_way_distance", 0.0);
171        DataSet dataSet = Main.main != null ? Main.main.getEditDataSet() : null;
172        dsArea = dataSet == null ? null : dataSet.getDataSourceArea();
173    }
174
175    protected Map<Node, Way> getWayEndNodesNearOtherHighway() {
176        Map<Node, Way> map = new HashMap<>();
177        for (int iter = 0; iter < 1; iter++) {
178            for (MyWaySegment s : ways) {
179                if (isCanceled()) {
180                    map.clear();
181                    return map;
182                }
183                for (Node en : s.nearbyNodes(mindist)) {
184                    if (en == null || !s.highway || !endnodesHighway.contains(en)) {
185                        continue;
186                    }
187                    if (en.hasTag(HIGHWAY, "turning_circle", "bus_stop")
188                            || en.hasTag("amenity", "parking_entrance")
189                            || en.hasTag(RAILWAY, "buffer_stop")
190                            || en.isKeyTrue("noexit")
191                            || en.hasKey("entrance", "barrier")) {
192                        continue;
193                    }
194                    // to handle intersections of 't' shapes and similar
195                    if (en.isConnectedTo(s.w.getNodes(), 3 /* hops */, null)) {
196                        continue;
197                    }
198                    map.put(en, s.w);
199                }
200            }
201        }
202        return map;
203    }
204
205    protected Map<Node, Way> getWayEndNodesNearOtherWay() {
206        Map<Node, Way> map = new HashMap<>();
207        for (MyWaySegment s : ways) {
208            if (isCanceled()) {
209                map.clear();
210                return map;
211            }
212            for (Node en : s.nearbyNodes(mindist)) {
213                if (en.isConnectedTo(s.w.getNodes(), 3 /* hops */, null)) {
214                    continue;
215                }
216                if (!s.highway && endnodesHighway.contains(en) && !s.w.concernsArea()) {
217                    map.put(en, s.w);
218                } else if (endnodes.contains(en) && !s.w.concernsArea()) {
219                    map.put(en, s.w);
220                }
221            }
222        }
223        return map;
224    }
225
226    protected Map<Node, Way> getWayNodesNearOtherWay() {
227        Map<Node, Way> map = new HashMap<>();
228        for (MyWaySegment s : ways) {
229            if (isCanceled()) {
230                map.clear();
231                return map;
232            }
233            for (Node en : s.nearbyNodes(minmiddledist)) {
234                if (en.isConnectedTo(s.w.getNodes(), 3 /* hops */, null)) {
235                    continue;
236                }
237                if (!middlenodes.contains(en)) {
238                    continue;
239                }
240                map.put(en, s.w);
241            }
242        }
243        return map;
244    }
245
246    protected Map<Node, Way> getConnectedWayEndNodesNearOtherWay() {
247        Map<Node, Way> map = new HashMap<>();
248        for (MyWaySegment s : ways) {
249            if (isCanceled()) {
250                map.clear();
251                return map;
252            }
253            for (Node en : s.nearbyNodes(minmiddledist)) {
254                if (en.isConnectedTo(s.w.getNodes(), 3 /* hops */, null)) {
255                    continue;
256                }
257                if (!othernodes.contains(en)) {
258                    continue;
259                }
260                map.put(en, s.w);
261            }
262        }
263        return map;
264    }
265
266    protected final void addErrors(Severity severity, Map<Node, Way> errorMap, String message) {
267        for (Map.Entry<Node, Way> error : errorMap.entrySet()) {
268            errors.add(TestError.builder(this, severity, UNCONNECTED_WAYS)
269                    .message(message)
270                    .primitives(error.getKey(), error.getValue())
271                    .highlight(error.getKey())
272                    .build());
273        }
274    }
275
276    @Override
277    public void endTest() {
278        addErrors(Severity.WARNING, getWayEndNodesNearOtherHighway(), tr("Way end node near other highway"));
279        addErrors(Severity.WARNING, getWayEndNodesNearOtherWay(), tr("Way end node near other way"));
280        /* the following two use a shorter distance */
281        if (minmiddledist > 0.0) {
282            addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Way node near other way"));
283            addErrors(Severity.OTHER, getConnectedWayEndNodesNearOtherWay(), tr("Connected way end node near other way"));
284        }
285        ways = null;
286        endnodes = null;
287        endnodesHighway = null;
288        middlenodes = null;
289        othernodes = null;
290        dsArea = null;
291        super.endTest();
292    }
293
294    private class MyWaySegment {
295        private final Line2D line;
296        public final Way w;
297        public final boolean isAbandoned;
298        public final boolean isBoundary;
299        public final boolean highway;
300        private final double len;
301        private Set<Node> nearbyNodeCache;
302        private double nearbyNodeCacheDist = -1.0;
303        private final Node n1;
304        private final Node n2;
305
306        MyWaySegment(Way w, Node n1, Node n2) {
307            this.w = w;
308            String railway = w.get(RAILWAY);
309            String highway = w.get(HIGHWAY);
310            this.isAbandoned = "abandoned".equals(railway) || w.isKeyTrue("disused");
311            this.highway = (highway != null || railway != null) && !isAbandoned;
312            this.isBoundary = !this.highway && w.hasTag("boundary", "administrative");
313            line = new Line2D.Double(n1.getEastNorth().east(), n1.getEastNorth().north(),
314                    n2.getEastNorth().east(), n2.getEastNorth().north());
315            len = line.getP1().distance(line.getP2());
316            this.n1 = n1;
317            this.n2 = n2;
318        }
319
320        public boolean nearby(Node n, double dist) {
321            if (w == null) {
322                Logging.debug("way null");
323                return false;
324            }
325            if (w.containsNode(n))
326                return false;
327            if (n.isKeyTrue("noexit"))
328                return false;
329            EastNorth coord = n.getEastNorth();
330            if (coord == null)
331                return false;
332            Point2D p = new Point2D.Double(coord.east(), coord.north());
333            if (line.getP1().distance(p) > len+dist)
334                return false;
335            if (line.getP2().distance(p) > len+dist)
336                return false;
337            return line.ptSegDist(p) < dist;
338        }
339
340        public List<LatLon> getBounds(double fudge) {
341            double x1 = n1.getCoor().lon();
342            double x2 = n2.getCoor().lon();
343            if (x1 > x2) {
344                double tmpx = x1;
345                x1 = x2;
346                x2 = tmpx;
347            }
348            double y1 = n1.getCoor().lat();
349            double y2 = n2.getCoor().lat();
350            if (y1 > y2) {
351                double tmpy = y1;
352                y1 = y2;
353                y2 = tmpy;
354            }
355            LatLon topLeft = new LatLon(y2+fudge, x1-fudge);
356            LatLon botRight = new LatLon(y1-fudge, x2+fudge);
357            List<LatLon> ret = new ArrayList<>(2);
358            ret.add(topLeft);
359            ret.add(botRight);
360            return ret;
361        }
362
363        public Collection<Node> nearbyNodes(double dist) {
364            // If you're looking for nodes that are farther away that we looked for last time,
365            // the cached result is no good
366            if (dist > nearbyNodeCacheDist) {
367                nearbyNodeCache = null;
368            }
369            if (nearbyNodeCache != null) {
370                // If we've cached an area greater than the
371                // one now being asked for...
372                if (nearbyNodeCacheDist > dist) {
373                    // Used the cached result and trim out
374                    // the nodes that are not in the smaller
375                    // area, but keep the old larger cache.
376                    Set<Node> trimmed = new HashSet<>(nearbyNodeCache);
377                    Set<Node> initial = new HashSet<>(nearbyNodeCache);
378                    for (Node n : initial) {
379                        if (!nearby(n, dist)) {
380                            trimmed.remove(n);
381                        }
382                    }
383                    return trimmed;
384                }
385                return nearbyNodeCache;
386            }
387            /*
388             * We know that any point near the line must be at
389             * least as close as the other end of the line, plus
390             * a little fudge for the distance away ('dist').
391             */
392
393            // This needs to be a hash set because the searches
394            // overlap a bit and can return duplicate nodes.
395            nearbyNodeCache = null;
396            List<LatLon> bounds = this.getBounds(dist * (360.0d / (Ellipsoid.WGS84.a * 2 * Math.PI)));
397            List<Node> foundNodes = endnodesHighway.search(new BBox(bounds.get(0), bounds.get(1)));
398            foundNodes.addAll(endnodes.search(new BBox(bounds.get(0), bounds.get(1))));
399
400            for (Node n : foundNodes) {
401                if (!nearby(n, dist) || !n.getCoor().isIn(dsArea)) {
402                    continue;
403                }
404                // It is actually very rare for us to find a node
405                // so defer as much of the work as possible, like
406                // allocating the hash set
407                if (nearbyNodeCache == null) {
408                    nearbyNodeCache = new HashSet<>();
409                }
410                nearbyNodeCache.add(n);
411            }
412            nearbyNodeCacheDist = dist;
413            if (nearbyNodeCache == null) {
414                nearbyNodeCache = Collections.emptySet();
415            }
416            return nearbyNodeCache;
417        }
418    }
419
420    List<MyWaySegment> getWaySegments(Way w) {
421        List<MyWaySegment> ret = new ArrayList<>();
422        if (!w.isUsable()
423                || w.hasKey("barrier")
424                || w.hasTag("natural", "cliff"))
425            return ret;
426
427        int size = w.getNodesCount();
428        if (size < 2)
429            return ret;
430        for (int i = 1; i < size; ++i) {
431            if (i < size-1) {
432                addNode(w.getNode(i), middlenodes);
433            }
434            Node a = w.getNode(i-1);
435            Node b = w.getNode(i);
436            if (a.isDrawable() && b.isDrawable()) {
437                MyWaySegment ws = new MyWaySegment(w, a, b);
438                if (ws.isBoundary || ws.isAbandoned) {
439                    continue;
440                }
441                ret.add(ws);
442            }
443        }
444        return ret;
445    }
446
447    @Override
448    public void visit(Way w) {
449        // do not consider empty ways
450        if (w.getNodesCount() > 0
451                // ignore addr:interpolation ways as they are not physical features and most of
452                // the time very near the associated highway, which is perfectly normal, see #9332
453                && !w.hasKey("addr:interpolation")
454                // similarly for public transport platforms
455                && !w.hasTag(HIGHWAY, "platform") && !w.hasTag(RAILWAY, "platform")
456                ) {
457            ways.addAll(getWaySegments(w));
458            QuadBuckets<Node> set = endnodes;
459            if (w.hasKey(HIGHWAY, RAILWAY)) {
460                set = endnodesHighway;
461            }
462            addNode(w.firstNode(), set);
463            addNode(w.lastNode(), set);
464        }
465    }
466
467    private void addNode(Node n, QuadBuckets<Node> s) {
468        boolean m = middlenodes.contains(n);
469        boolean e = endnodes.contains(n);
470        boolean eh = endnodesHighway.contains(n);
471        boolean o = othernodes.contains(n);
472        if (!m && !e && !o && !eh) {
473            s.add(n);
474        } else if (!o) {
475            othernodes.add(n);
476            if (e) {
477                endnodes.remove(n);
478            } else if (eh) {
479                endnodesHighway.remove(n);
480            } else {
481                middlenodes.remove(n);
482            }
483        }
484    }
485}