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