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