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