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