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.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.Map.Entry;
018import java.util.Objects;
019import java.util.Set;
020
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.OsmDataManager;
027import org.openstreetmap.josm.data.osm.OsmPrimitive;
028import org.openstreetmap.josm.data.osm.OsmUtils;
029import org.openstreetmap.josm.data.osm.QuadBuckets;
030import org.openstreetmap.josm.data.osm.Way;
031import org.openstreetmap.josm.data.preferences.sources.ValidatorPrefHelper;
032import org.openstreetmap.josm.data.projection.Ellipsoid;
033import org.openstreetmap.josm.data.validation.Severity;
034import org.openstreetmap.josm.data.validation.Test;
035import org.openstreetmap.josm.data.validation.TestError;
036import org.openstreetmap.josm.gui.progress.ProgressMonitor;
037import org.openstreetmap.josm.spi.preferences.Config;
038import org.openstreetmap.josm.tools.Geometry;
039import org.openstreetmap.josm.tools.Logging;
040
041/**
042 * Checks if a way has an endpoint very near to another way.
043 * <br>
044 * This class is abstract since highway/railway/waterway/… ways must be handled separately.
045 * An actual implementation must override {@link #isPrimitiveUsable(OsmPrimitive)}
046 * to denote which kind of primitives can be handled.
047 *
048 * @author frsantos
049 */
050public abstract class UnconnectedWays extends Test {
051    private final int code;
052    private final boolean isHighwayTest;
053
054    protected abstract boolean isCandidate(OsmPrimitive p);
055
056    protected boolean isWantedWay(Way w) {
057        return w.isUsable() && isCandidate(w);
058    }
059
060    /**
061     * Check if unconnected end node should be ignored.
062     * @param n the node
063     * @return true if node should be ignored
064     */
065    protected boolean ignoreUnconnectedEndNode(Node n) {
066        return false;
067    }
068
069    @Override
070    public boolean isPrimitiveUsable(OsmPrimitive p) {
071        return super.isPrimitiveUsable(p) && ((partialSelection && p instanceof Node) || isCandidate(p));
072    }
073
074    /**
075     * Unconnected highways test.
076     */
077    public static class UnconnectedHighways extends UnconnectedWays {
078        static final int UNCONNECTED_HIGHWAYS = 1311;
079
080        /**
081         * Constructs a new {@code UnconnectedHighways} test.
082         */
083        public UnconnectedHighways() {
084            super(tr("Unconnected highways"), UNCONNECTED_HIGHWAYS, true);
085        }
086
087        @Override
088        protected boolean isCandidate(OsmPrimitive p) {
089            return p.hasKey(HIGHWAY);
090        }
091
092        @Override
093        protected boolean ignoreUnconnectedEndNode(Node n) {
094            return n.hasTag(HIGHWAY, "turning_circle", "bus_stop")
095                    || n.hasTag("amenity", "parking_entrance")
096                    || n.isKeyTrue("noexit")
097                    || n.hasKey("entrance", "barrier")
098                    || n.getParentWays().stream().anyMatch(Test::isBuilding);
099        }
100    }
101
102    /**
103     * Unconnected railways test.
104     */
105    public static class UnconnectedRailways extends UnconnectedWays {
106        static final int UNCONNECTED_RAILWAYS = 1321;
107        /**
108         * Constructs a new {@code UnconnectedRailways} test.
109         */
110        public UnconnectedRailways() {
111            super(tr("Unconnected railways"), UNCONNECTED_RAILWAYS, false);
112        }
113
114        @Override
115        protected boolean isCandidate(OsmPrimitive p) {
116            return p.hasTagDifferent(RAILWAY, "abandoned");
117        }
118
119        @Override
120        protected boolean ignoreUnconnectedEndNode(Node n) {
121            return n.hasTag(RAILWAY, "buffer_stop");
122        }
123    }
124
125    /**
126     * Unconnected waterways test.
127     */
128    public static class UnconnectedWaterways extends UnconnectedWays {
129        static final int UNCONNECTED_WATERWAYS = 1331;
130        /**
131         * Constructs a new {@code UnconnectedWaterways} test.
132         */
133        public UnconnectedWaterways() {
134            super(tr("Unconnected waterways"), UNCONNECTED_WATERWAYS, false);
135        }
136
137        @Override
138        protected boolean isCandidate(OsmPrimitive p) {
139            return p.hasKey("waterway");
140        }
141    }
142
143    /**
144     * Unconnected natural/landuse test.
145     */
146    public static class UnconnectedNaturalOrLanduse extends UnconnectedWays {
147        static final int UNCONNECTED_NATURAL_OR_LANDUSE = 1341;
148        /**
149         * Constructs a new {@code UnconnectedNaturalOrLanduse} test.
150         */
151        public UnconnectedNaturalOrLanduse() {
152            super(tr("Unconnected natural lands and landuses"), UNCONNECTED_NATURAL_OR_LANDUSE, false);
153        }
154
155        @Override
156        protected boolean isCandidate(OsmPrimitive p) {
157            return p.hasKey("landuse") || p.hasTagDifferent("natural", "tree_row", "cliff");
158        }
159    }
160
161    /**
162     * Unconnected power ways test.
163     */
164    public static class UnconnectedPower extends UnconnectedWays {
165        static final int UNCONNECTED_POWER = 1351;
166        /**
167         * Constructs a new {@code UnconnectedPower} test.
168         */
169        public UnconnectedPower() {
170            super(tr("Unconnected power ways"), UNCONNECTED_POWER, false);
171        }
172
173        @Override
174        protected boolean isCandidate(OsmPrimitive p) {
175            return p.hasTag("power", "line", "minor_line", "cable");
176        }
177
178        @Override
179        protected boolean ignoreUnconnectedEndNode(Node n) {
180            return n.hasTag("power", "terminal");
181        }
182    }
183
184    protected static final int UNCONNECTED_WAYS = 1301;
185    protected static final String PREFIX = ValidatorPrefHelper.PREFIX + "." + UnconnectedWays.class.getSimpleName();
186
187    private List<MyWaySegment> waySegments;
188    private Set<Node> endnodes; // nodes at end of way
189    private Set<Node> middlenodes; // nodes in middle of way
190    private Set<Node> othernodes; // nodes appearing at least twice
191    private QuadBuckets<Node> searchNodes;
192    private Set<Way> waysToTest;
193    private Set<Node> nodesToTest;
194    private Area dsArea;
195
196    private double mindist;
197    private double minmiddledist;
198    private double maxLen; // maximum length of allowed detour to reach the unconnected node
199    private DataSet ds;
200
201    /**
202     * Constructs a new {@code UnconnectedWays} test.
203     * @param title The test title
204     * @since 6691
205     */
206    public UnconnectedWays(String title) {
207        this(title, UNCONNECTED_WAYS, false);
208
209    }
210
211    /**
212     * Constructs a new {@code UnconnectedWays} test with the given code.
213     * @param title The test title
214     * @param code The test code
215     * @param isHighwayTest use {@code true} if test concerns highways or railways
216     * @since 14468
217     */
218    public UnconnectedWays(String title, int code, boolean isHighwayTest) {
219        super(title, tr("This test checks if a way has an endpoint very near to another way."));
220        this.code = code;
221        this.isHighwayTest = isHighwayTest;
222    }
223
224    @Override
225    public void startTest(ProgressMonitor monitor) {
226        super.startTest(monitor);
227        waySegments = new ArrayList<>();
228        searchNodes = new QuadBuckets<>();
229        waysToTest = new HashSet<>();
230        nodesToTest = new HashSet<>();
231        endnodes = new HashSet<>();
232        middlenodes = new HashSet<>();
233        othernodes = new HashSet<>();
234        mindist = Config.getPref().getDouble(PREFIX + ".node_way_distance", 10.0);
235        minmiddledist = Config.getPref().getDouble(PREFIX + ".way_way_distance", 0.0);
236        ds = OsmDataManager.getInstance().getEditDataSet();
237        dsArea = ds == null ? null : ds.getDataSourceArea();
238    }
239
240    protected Map<Node, MyWaySegment> getHighwayEndNodesNearOtherHighway() {
241        Map<Node, MyWaySegment> map = new HashMap<>();
242        for (MyWaySegment s : waySegments) {
243            if (isCanceled()) {
244                map.clear();
245                return map;
246            }
247            for (Node endnode : s.nearbyNodes(mindist)) {
248                Way parentWay = getWantedParentWay(endnode);
249                if (parentWay != null) {
250                    if (!Objects.equals(OsmUtils.getLayer(s.w), OsmUtils.getLayer(parentWay))) {
251                        continue; // ignore ways with different layer tag
252                    }
253
254                    // to handle intersections of 't' shapes and similar
255                    if (!s.isConnectedTo(endnode)) {
256                        if (parentWay.hasTag(HIGHWAY, "platform") || s.w.hasTag(HIGHWAY, "platform")
257                                || s.barrierBetween(endnode)) {
258                            continue;
259                        }
260                        addIfNewOrCloser(map, endnode, s);
261                    }
262                }
263            }
264        }
265        return map;
266    }
267
268    protected Map<Node, MyWaySegment> getWayEndNodesNearOtherWay() {
269        Map<Node, MyWaySegment> map = new HashMap<>();
270
271        for (MyWaySegment s : waySegments) {
272            if (isCanceled()) {
273                map.clear();
274                return map;
275            }
276            if (!s.concernsArea) {
277                for (Node endnode : s.nearbyNodes(mindist)) {
278                    if (!s.isConnectedTo(endnode)) {
279                        if (s.w.hasTag("power")) {
280                            boolean badConnection = false;
281                            Way otherWay = getWantedParentWay(endnode);
282                            if (otherWay != null) {
283                                for (String key : Arrays.asList("voltage", "frequency")) {
284                                    String v1 = s.w.get(key);
285                                    String v2 = otherWay.get(key);
286                                    if (v1 != null && v2 != null && !v1.equals(v2)) {
287                                        badConnection = true;
288                                    }
289                                }
290                            }
291                            if (badConnection)
292                                continue;
293                        }
294                        addIfNewOrCloser(map, endnode, s);
295                    }
296                }
297            }
298        }
299        return map;
300    }
301
302    protected Map<Node, MyWaySegment> getWayNodesNearOtherWay() {
303        Map<Node, MyWaySegment> map = new HashMap<>();
304        for (MyWaySegment s : waySegments) {
305            if (isCanceled()) {
306                map.clear();
307                return map;
308            }
309            for (Node en : s.nearbyNodes(minmiddledist)) {
310                if (!s.isConnectedTo(en)) {
311                    addIfNewOrCloser(map, en, s);
312                }
313            }
314        }
315        return map;
316    }
317
318    /**
319     * An unconnected node might have multiple parent ways, e.g. a highway and a landuse way.
320     * Make sure we get the one that was analysed before.
321     * @param endnode the node which is known to be an end node of the wanted way
322     * @return the wanted way
323     */
324    private Way getWantedParentWay(Node endnode) {
325        for (Way w : endnode.getParentWays()) {
326            if (isWantedWay(w))
327                return w;
328        }
329        Logging.error("end node without matching parent way");
330        return null;
331    }
332
333    private void addIfNewOrCloser(Map<Node, MyWaySegment> map, Node node, MyWaySegment ws) {
334        if (partialSelection && !nodesToTest.contains(node) && !waysToTest.contains(ws.w))
335            return;
336        MyWaySegment old = map.get(node);
337        if (old != null) {
338            double d1 = ws.getDist(node);
339            double d2 = old.getDist(node);
340            if (d1 > d2) {
341                // keep old value
342                return;
343            }
344        }
345        map.put(node, ws);
346    }
347
348    protected final void addErrors(Severity severity, Map<Node, MyWaySegment> errorMap, String message) {
349        for (Entry<Node, MyWaySegment> error : errorMap.entrySet()) {
350            Node node = error.getKey();
351            MyWaySegment ws = error.getValue();
352            errors.add(TestError.builder(this, severity, code)
353                    .message(message)
354                    .primitives(node, ws.w)
355                    .highlight(node)
356                    .build());
357        }
358    }
359
360    @Override
361    public void endTest() {
362        if (ds == null)
363            return;
364
365        for (Way w : ds.getWays()) {
366            if (isWantedWay(w) && w.getRealNodesCount() > 1) {
367                waySegments.addAll(getWaySegments(w));
368                addNode(w.firstNode(), endnodes);
369                addNode(w.lastNode(), endnodes);
370            }
371        }
372        fillSearchNodes(endnodes);
373        if (!searchNodes.isEmpty()) {
374            maxLen = 4 * mindist;
375            if (isHighwayTest) {
376                addErrors(Severity.WARNING, getHighwayEndNodesNearOtherHighway(), tr("Way end node near other highway"));
377            } else {
378                addErrors(Severity.WARNING, getWayEndNodesNearOtherWay(), tr("Way end node near other way"));
379            }
380        }
381
382        /* the following two should use a shorter distance */
383        boolean includeOther = isBeforeUpload ? ValidatorPrefHelper.PREF_OTHER_UPLOAD.get() : ValidatorPrefHelper.PREF_OTHER.get();
384        if (minmiddledist > 0.0 && includeOther) {
385            maxLen = 4 * minmiddledist;
386            fillSearchNodes(middlenodes);
387            addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Way node near other way"));
388            fillSearchNodes(othernodes);
389            addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Connected way end node near other way"));
390        }
391
392        waySegments = null;
393        endnodes = null;
394        middlenodes = null;
395        othernodes = null;
396        searchNodes = null;
397        dsArea = null;
398        ds = null;
399        super.endTest();
400    }
401
402    private void fillSearchNodes(Collection<Node> nodes) {
403        searchNodes.clear();
404        for (Node n : nodes) {
405            if (!ignoreUnconnectedEndNode(n) && n.getCoor().isIn(dsArea)) {
406                searchNodes.add(n);
407            }
408        }
409    }
410
411    private class MyWaySegment {
412        public final Way w;
413        private final Node n1;
414        private final Node n2;
415        private final boolean concernsArea;
416
417        MyWaySegment(Way w, Node n1, Node n2, boolean concersArea) {
418            this.w = w;
419            this.n1 = n1;
420            this.n2 = n2;
421            this.concernsArea = concersArea;
422        }
423
424        /**
425         * Check if the given node is connected to this segment using a reasonable short way.
426         * @param startNode the node
427         * @return true if a reasonable connection was found
428         */
429        boolean isConnectedTo(Node startNode) {
430            return isConnectedTo(startNode, null, new HashSet<>(), 0);
431        }
432
433        /**
434         * Check if the given node is connected to this segment using a reasonable short way.
435         * @param node the given node
436         * @param startWay previously visited way or null if first
437         * @param visited set of visited nodes
438         * @param len length of the travelled route
439         * @return true if a reasonable connection was found
440         */
441        boolean isConnectedTo(Node node, Way startWay, Set<Node> visited, double len) {
442            if (n1 == node || n2 == node) {
443                return true;
444            }
445            if (len > maxLen) {
446                return false;
447            }
448            if (visited != null) {
449                visited.add(node);
450                for (final Way way : node.getParentWays()) {
451                    if (isWantedWay(way)) {
452                        List<Node> nextNodes = new ArrayList<>();
453                        int pos = way.getNodes().indexOf(node);
454                        if (pos > 0) {
455                            nextNodes.add(way.getNode(pos - 1));
456                        }
457                        if (pos + 1 < way.getNodesCount()) {
458                            nextNodes.add(way.getNode(pos + 1));
459                        }
460                        for (Node next : nextNodes) {
461                            final boolean containsN = visited.contains(next);
462                            visited.add(next);
463                            if (!containsN && isConnectedTo(next, way, visited,
464                                    len + node.getCoor().greatCircleDistance(next.getCoor()))) {
465                                return true;
466                            }
467                        }
468                    }
469                }
470            }
471            return false;
472        }
473
474        double getDist(Node n) {
475            EastNorth coord = n.getEastNorth();
476            if (coord == null)
477                return Double.NaN;
478            EastNorth closest = Geometry.closestPointToSegment(n1.getEastNorth(), n2.getEastNorth(), coord);
479            Node x = new Node();
480            x.setEastNorth(closest);
481            return x.getCoor().greatCircleDistance(n.getCoor());
482
483        }
484
485        boolean nearby(Node n, double dist) {
486            if (w.containsNode(n))
487                return false;
488            double d = getDist(n);
489            return !Double.isNaN(d) && d < dist;
490        }
491
492        BBox getBounds(double fudge) {
493            double x1 = n1.getCoor().lon();
494            double x2 = n2.getCoor().lon();
495            if (x1 > x2) {
496                double tmpx = x1;
497                x1 = x2;
498                x2 = tmpx;
499            }
500            double y1 = n1.getCoor().lat();
501            double y2 = n2.getCoor().lat();
502            if (y1 > y2) {
503                double tmpy = y1;
504                y1 = y2;
505                y2 = tmpy;
506            }
507            LatLon topLeft = new LatLon(y2+fudge, x1-fudge);
508            LatLon botRight = new LatLon(y1-fudge, x2+fudge);
509            return new BBox(topLeft, botRight);
510        }
511
512        Collection<Node> nearbyNodes(double dist) {
513            /*
514             * We know that any point near the line segment must be at
515             * least as close as the other end of the line, plus
516             * a little fudge for the distance away ('dist').
517             */
518
519            BBox bounds = this.getBounds(dist * (360.0d / (Ellipsoid.WGS84.a * 2 * Math.PI)));
520            List<Node> result = null;
521            List<Node> foundNodes = searchNodes.search(bounds);
522            for (Node n : foundNodes) {
523                if (!nearby(n, dist)) {
524                    continue;
525                }
526                // It is actually very rare for us to find a node
527                // so defer as much of the work as possible, like
528                // allocating the hash set
529                if (result == null) {
530                    result = new ArrayList<>();
531                }
532                result.add(n);
533            }
534            return result == null ? Collections.emptyList() : result;
535        }
536
537        private boolean barrierBetween(Node endnode) {
538            EastNorth closest = Geometry.closestPointToSegment(n1.getEastNorth(), n2.getEastNorth(), endnode.getEastNorth());
539            Node x = new Node();
540            x.setEastNorth(closest);
541            BBox bbox = new BBox(endnode.getCoor(), x.getCoor());
542            for (Way nearbyWay: ds.searchWays(bbox)) {
543                if (nearbyWay != w && nearbyWay.hasTag("barrier") && !endnode.getParentWays().contains(nearbyWay)) {
544                    //make sure that the barrier is really between the two nodes, not just close to them
545                    Way directWay = new Way();
546                    directWay.addNode(endnode);
547                    directWay.addNode(x);
548                    if (!Geometry.addIntersections(Arrays.asList(nearbyWay, directWay), true, new ArrayList<>()).isEmpty())
549                        return true;
550                }
551            }
552            return false;
553        }
554
555    }
556
557    List<MyWaySegment> getWaySegments(Way w) {
558        List<MyWaySegment> ret = new ArrayList<>();
559        if (!w.isUsable() || w.isKeyTrue("disused"))
560            return ret;
561
562        int size = w.getNodesCount();
563        boolean concersArea = w.concernsArea();
564        for (int i = 1; i < size; ++i) {
565            if (i < size-1) {
566                addNode(w.getNode(i), middlenodes);
567            }
568            Node a = w.getNode(i-1);
569            Node b = w.getNode(i);
570            if (a.isDrawable() && b.isDrawable()) {
571                MyWaySegment ws = new MyWaySegment(w, a, b, concersArea);
572                ret.add(ws);
573            }
574        }
575        return ret;
576    }
577
578    @Override
579    public void visit(Way w) {
580        if (partialSelection) {
581            waysToTest.add(w);
582        }
583    }
584
585    @Override
586    public void visit(Node n) {
587        if (partialSelection) {
588            nodesToTest.add(n);
589        }
590    }
591
592    private void addNode(Node n, Set<Node> s) {
593        boolean m = middlenodes.contains(n);
594        boolean e = endnodes.contains(n);
595        boolean o = othernodes.contains(n);
596        if (!m && !e && !o) {
597            s.add(n);
598        } else if (!o) {
599            othernodes.add(n);
600            if (e) {
601                endnodes.remove(n);
602            } else {
603                middlenodes.remove(n);
604            }
605        }
606    }
607}