001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.validation.tests;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005
006import java.awt.geom.Point2D;
007import java.util.ArrayList;
008import java.util.Arrays;
009import java.util.HashMap;
010import java.util.HashSet;
011import java.util.List;
012import java.util.Map;
013import java.util.Objects;
014import java.util.Set;
015import java.util.stream.Collectors;
016
017import org.openstreetmap.josm.data.coor.EastNorth;
018import org.openstreetmap.josm.data.osm.OsmPrimitive;
019import org.openstreetmap.josm.data.osm.OsmUtils;
020import org.openstreetmap.josm.data.osm.Relation;
021import org.openstreetmap.josm.data.osm.Way;
022import org.openstreetmap.josm.data.osm.WaySegment;
023import org.openstreetmap.josm.data.validation.OsmValidator;
024import org.openstreetmap.josm.data.validation.Severity;
025import org.openstreetmap.josm.data.validation.Test;
026import org.openstreetmap.josm.data.validation.TestError;
027import org.openstreetmap.josm.data.validation.util.ValUtil;
028import org.openstreetmap.josm.gui.progress.ProgressMonitor;
029import org.openstreetmap.josm.tools.CheckParameterUtil;
030import org.openstreetmap.josm.tools.Logging;
031
032/**
033 * Tests if there are segments that crosses in the same layer/level
034 *
035 * @author frsantos
036 */
037public abstract class CrossingWays extends Test {
038
039    static final String BARRIER = "barrier";
040    static final String HIGHWAY = "highway";
041    static final String RAILWAY = "railway";
042    static final String WATERWAY = "waterway";
043    static final String LANDUSE = "landuse";
044
045    static final class MessageHelper {
046        final String message;
047        final int code;
048
049        MessageHelper(String message, int code) {
050            this.message = message;
051            this.code = code;
052        }
053    }
054
055    /**
056     * Type of way. Entries have to be declared in alphabetical order, see sort below.
057     */
058    private enum WayType {
059        BARRIER, BUILDING, HIGHWAY, RAILWAY, RESIDENTIAL_AREA, WATERWAY, WAY;
060
061        static WayType of(Way w) {
062            if (w.hasKey(CrossingWays.BARRIER))
063                return BARRIER;
064            if (isBuilding(w))
065                return BUILDING;
066            else if (w.hasKey(CrossingWays.HIGHWAY))
067                return HIGHWAY;
068            else if (isRailway(w))
069                return RAILWAY;
070            else if (isResidentialArea(w))
071                return RESIDENTIAL_AREA;
072            else if (w.hasKey(CrossingWays.WATERWAY))
073                return WATERWAY;
074            else
075                return WAY;
076        }
077    }
078
079    /** All way segments, grouped by cells */
080    private final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
081    /** The already detected ways in error */
082    private final Map<List<Way>, List<WaySegment>> seenWays = new HashMap<>(50);
083
084    protected final int code;
085
086    /**
087     * General crossing ways test.
088     */
089    public static class Ways extends CrossingWays {
090
091        protected static final int CROSSING_WAYS = 601;
092
093        /**
094         * Constructs a new crossing {@code Ways} test.
095         */
096        public Ways() {
097            super(tr("Crossing ways"), CROSSING_WAYS);
098        }
099
100        @Override
101        public boolean isPrimitiveUsable(OsmPrimitive w) {
102            return super.isPrimitiveUsable(w)
103                    && !isProposedOrAbandoned(w)
104                    && (isHighway(w)
105                    || w.hasKey(WATERWAY)
106                    || isRailway(w)
107                    || isCoastline(w)
108                    || isBuilding(w)
109                    || w.hasKey(BARRIER)
110                    || isResidentialArea(w));
111        }
112
113        @Override
114        boolean ignoreWaySegmentCombination(Way w1, Way w2) {
115            if (w1 == w2)
116                return true;
117            if (areLayerOrLevelDifferent(w1, w2))
118                return true;
119            if (isBuilding(w1) && isBuilding(w2))
120                return true; // handled by mapcss tests
121            if (((isResidentialArea(w1) || w1.hasKey(BARRIER, HIGHWAY, RAILWAY, WATERWAY) || isWaterArea(w1))
122                    && isResidentialArea(w2))
123                    || ((isResidentialArea(w2) || w2.hasKey(BARRIER, HIGHWAY, RAILWAY, WATERWAY) || isWaterArea(w2))
124                            && isResidentialArea(w1)))
125                return true;
126            if (isWaterArea(w1) && isWaterArea(w2))
127                return true; // handled by mapcss tests
128            if (w1.hasKey(RAILWAY) && w2.hasKey(RAILWAY) && (w1.hasTag(RAILWAY, "yard") != w2.hasTag(RAILWAY, "yard")
129                    || w1.hasTag(RAILWAY, "halt") != w2.hasTag(RAILWAY, "halt")))
130                return true;  // see #20089, #21541
131            return (w1.hasTag(WATERWAY, "river", "stream", "canal", "drain", "ditch") && isWaterArea(w2))
132                    || (w2.hasTag(WATERWAY, "river", "stream", "canal", "drain", "ditch") && isWaterArea(w1));
133        }
134
135        @Override
136        MessageHelper createMessage(Way w1, Way w2) {
137            WayType[] types = {WayType.of(w1), WayType.of(w2)};
138            Arrays.sort(types);
139
140            if (types[0] == types[1]) {
141                switch (types[0]) {
142                // 610 and 640 where removed for #16707
143                case BARRIER:
144                    return new MessageHelper(tr("Crossing barriers"), 603);
145                case HIGHWAY:
146                    return new MessageHelper(tr("Crossing highways"), 620);
147                case RAILWAY:
148                    return new MessageHelper(tr("Crossing railways"), 630);
149                case WATERWAY:
150                    return new MessageHelper(tr("Crossing waterways"), 650);
151                case WAY:
152                default:
153                    return new MessageHelper(tr("Crossing ways"), CROSSING_WAYS);
154                }
155            } else {
156                switch (types[0]) {
157                case BARRIER:
158                    switch (types[1]) {
159                    case BUILDING:
160                        return new MessageHelper(tr("Crossing barrier/building"), 661);
161                    case HIGHWAY:
162                        return new MessageHelper(tr("Crossing barrier/highway"), 662);
163                    case RAILWAY:
164                        return new MessageHelper(tr("Crossing barrier/railway"), 663);
165                    case WATERWAY:
166                        return new MessageHelper(tr("Crossing barrier/waterway"), 664);
167                    case WAY:
168                    default:
169                        return new MessageHelper(tr("Crossing barrier/way"), 665);
170                    }
171                case BUILDING:
172                    switch (types[1]) {
173                    case HIGHWAY:
174                        return new MessageHelper(tr("Crossing building/highway"), 612);
175                    case RAILWAY:
176                        return new MessageHelper(tr("Crossing building/railway"), 613);
177                    case RESIDENTIAL_AREA:
178                        return new MessageHelper(tr("Crossing building/residential area"), 614);
179                    case WATERWAY:
180                        return new MessageHelper(tr("Crossing building/waterway"), 615);
181                    case WAY:
182                    default:
183                        return new MessageHelper(tr("Crossing building/way"), 611);
184                    }
185                case HIGHWAY:
186                    switch (types[1]) {
187                    case RAILWAY:
188                        return new MessageHelper(tr("Crossing highway/railway"), 622);
189                    case WATERWAY:
190                        return new MessageHelper(tr("Crossing highway/waterway"), 623);
191                    case WAY:
192                    default:
193                        return new MessageHelper(tr("Crossing highway/way"), 621);
194                    }
195                case RAILWAY:
196                    switch (types[1]) {
197                    case WATERWAY:
198                        return new MessageHelper(tr("Crossing railway/waterway"), 632);
199                    case WAY:
200                    default:
201                        return new MessageHelper(tr("Crossing railway/way"), 631);
202                    }
203                case RESIDENTIAL_AREA:
204                    return new MessageHelper(tr("Crossing residential area/way"), 641);
205                case WATERWAY:
206                default:
207                    return new MessageHelper(tr("Crossing waterway/way"), 651);
208                }
209            }
210        }
211    }
212
213    /**
214     * Crossing boundaries ways test.
215     */
216    public static class Boundaries extends CrossingWays {
217
218        protected static final int CROSSING_BOUNDARIES = 602;
219
220        /**
221         * Constructs a new crossing {@code Boundaries} test.
222         */
223        public Boundaries() {
224            super(tr("Crossing boundaries"), CROSSING_BOUNDARIES);
225        }
226
227        @Override
228        public boolean isPrimitiveUsable(OsmPrimitive p) {
229            return super.isPrimitiveUsable(p) && p.hasKey("boundary") && !p.hasTag("boundary", "protected_area")
230                    && (!(p instanceof Relation) || p.isMultipolygon());
231        }
232
233        @Override
234        boolean ignoreWaySegmentCombination(Way w1, Way w2) {
235            // ignore ways which have no common boundary tag value
236            Set<String> s1 = getBoundaryTags(w1);
237            Set<String> s2 = getBoundaryTags(w2);
238            return s1.stream().noneMatch(s2::contains);
239        }
240
241        /**
242         * Collect all boundary tag values of the way and its parent relations
243         * @param w the way to check
244         * @return set with the found boundary tag values
245         */
246        private static Set<String> getBoundaryTags(Way w) {
247            final Set<String> types = new HashSet<>();
248            String type = w.get("boundary");
249            if (type != null)
250                types.add(type);
251            w.referrers(Relation.class).filter(Relation::isMultipolygon).map(r -> r.get("boundary"))
252                    .filter(Objects::nonNull).forEach(types::add);
253            types.remove("protected_area");
254            return types;
255        }
256
257        @Override
258        public void visit(Relation r) {
259            for (Way w : r.getMemberPrimitives(Way.class)) {
260                if (!w.isIncomplete())
261                    visit(w);
262            }
263        }
264    }
265
266    /**
267     * Self crossing ways test (for all ways)
268     */
269    public static class SelfCrossing extends CrossingWays {
270
271        protected static final int CROSSING_SELF = 604;
272
273        /**
274         * Constructs a new SelfIntersection test.
275         */
276        public SelfCrossing() {
277            super(tr("Self crossing ways"), CROSSING_SELF);
278        }
279
280        @Override
281        boolean ignoreWaySegmentCombination(Way w1, Way w2) {
282            return false; // we should not get here
283        }
284    }
285
286    /**
287     * Constructs a new {@code CrossingWays} test.
288     * @param title The test title
289     * @param code The test code
290     * @since 12958
291     */
292    protected CrossingWays(String title, int code) {
293        super(title, tr("This test checks if two roads, railways, waterways or buildings crosses in the same layer, " +
294                "but are not connected by a node."));
295        this.code = code;
296    }
297
298    @Override
299    public void startTest(ProgressMonitor monitor) {
300        super.startTest(monitor);
301        cellSegments.clear();
302        seenWays.clear();
303    }
304
305    @Override
306    public void endTest() {
307        super.endTest();
308        cellSegments.clear();
309        seenWays.clear();
310    }
311
312    static boolean isCoastline(OsmPrimitive w) {
313        return w.hasTag("natural", "water", "coastline") || w.hasTag(LANDUSE, "reservoir");
314    }
315
316    static boolean isWaterArea(OsmPrimitive w) {
317        return w.hasTag("natural", "water") || w.hasTag("waterway", "riverbank") || w.hasTag(LANDUSE, "reservoir");
318    }
319
320    static boolean isHighway(OsmPrimitive w) {
321        return w.hasTagDifferent(HIGHWAY, "rest_area", "services", "bus_stop", "platform");
322    }
323
324    static boolean isRailway(OsmPrimitive w) {
325        return w.hasKey(RAILWAY) && !isSubwayOrTramOrRazed(w);
326    }
327
328    static boolean isSubwayOrTramOrRazed(OsmPrimitive w) {
329        return w.hasTag(RAILWAY, "subway", "tram", "razed") ||
330              (w.hasTag(RAILWAY, "construction") && w.hasTag("construction", "tram")) ||
331              (w.hasTag(RAILWAY, "disused") && w.hasTag("disused", "tram"));
332    }
333
334    static boolean isProposedOrAbandoned(OsmPrimitive w) {
335        return w.hasTag(HIGHWAY, "proposed") || w.hasTag(RAILWAY, "proposed", "abandoned");
336    }
337
338    abstract boolean ignoreWaySegmentCombination(Way w1, Way w2);
339
340    MessageHelper createMessage(Way w1, Way w2) {
341        return new MessageHelper(this.name, this.code);
342    }
343
344    @Override
345    public void visit(Way w) {
346        boolean findSelfCrossingOnly = this instanceof SelfCrossing;
347        if (findSelfCrossingOnly) {
348            // free memory, we are not interested in previous ways
349            cellSegments.clear();
350            seenWays.clear();
351        }
352
353        int nodesSize = w.getNodesCount();
354        for (int i = 0; i < nodesSize - 1; i++) {
355            final WaySegment es1 = new WaySegment(w, i);
356            final EastNorth en1 = es1.getFirstNode().getEastNorth();
357            final EastNorth en2 = es1.getSecondNode().getEastNorth();
358            if (en1 == null || en2 == null) {
359                Logging.warn("Crossing ways test skipped " + es1);
360                continue;
361            }
362            for (List<WaySegment> segments : getSegments(cellSegments, en1, en2)) {
363                for (WaySegment es2 : segments) {
364                    List<Way> prims;
365                    List<WaySegment> highlight;
366
367                    if (!es1.intersects(es2)
368                            || (!findSelfCrossingOnly && ignoreWaySegmentCombination(es1.getWay(), es2.getWay()))) {
369                        continue;
370                    }
371
372                    prims = new ArrayList<>();
373                    prims.add(es1.getWay());
374                    if (es1.getWay() != es2.getWay())
375                        prims.add(es2.getWay());
376                    if ((highlight = seenWays.get(prims)) == null) {
377                        highlight = new ArrayList<>();
378                        highlight.add(es1);
379                        highlight.add(es2);
380
381                        final MessageHelper message = createMessage(es1.getWay(), es2.getWay());
382                        errors.add(TestError.builder(this, Severity.WARNING, message.code)
383                                .message(message.message)
384                                .primitives(prims)
385                                .highlightWaySegments(highlight)
386                                .build());
387                        seenWays.put(prims, highlight);
388                    } else {
389                        highlight.add(es1);
390                        highlight.add(es2);
391                    }
392                }
393                segments.add(es1);
394            }
395        }
396    }
397
398    private static boolean areLayerOrLevelDifferent(Way w1, Way w2) {
399        return !Objects.equals(OsmUtils.getLayer(w1), OsmUtils.getLayer(w2))
400            || !Objects.equals(w1.get("level"), w2.get("level"));
401    }
402
403    /**
404     * Returns all the cells this segment crosses.  Each cell contains the list
405     * of segments already processed
406     * @param cellSegments map with already collected way segments
407     * @param n1 The first EastNorth
408     * @param n2 The second EastNorth
409     * @return A list with all the cells the segment crosses
410     */
411    public static List<List<WaySegment>> getSegments(Map<Point2D, List<WaySegment>> cellSegments, EastNorth n1, EastNorth n2) {
412        return ValUtil.getSegmentCells(n1, n2, OsmValidator.getGridDetail()).stream()
413                .map(cell -> cellSegments.computeIfAbsent(cell, k -> new ArrayList<>()))
414                .collect(Collectors.toList());
415    }
416
417    /**
418     * Find ways which are crossing without sharing a node.
419     * @param w way that is to be checked
420     * @param cellSegments map with already collected way segments
421     * @param crossingWays map to collect crossing ways and related segments
422     * @param findSharedWaySegments true: find shared way segments instead of crossings
423     */
424    public static void findIntersectingWay(Way w, Map<Point2D, List<WaySegment>> cellSegments,
425            Map<List<Way>, List<WaySegment>> crossingWays, boolean findSharedWaySegments) {
426        int nodesSize = w.getNodesCount();
427        for (int i = 0; i < nodesSize - 1; i++) {
428            final WaySegment es1 = new WaySegment(w, i);
429            final EastNorth en1 = es1.getFirstNode().getEastNorth();
430            final EastNorth en2 = es1.getSecondNode().getEastNorth();
431            if (en1 == null || en2 == null) {
432                Logging.warn("Crossing ways test skipped " + es1);
433                continue;
434            }
435            for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) {
436                for (WaySegment es2 : segments) {
437
438                    List<WaySegment> highlight;
439                    if (es2.getWay() == w // reported by CrossingWays.SelfIntersection
440                            || (findSharedWaySegments && !es1.isSimilar(es2))
441                            || (!findSharedWaySegments && !es1.intersects(es2)))
442                        continue;
443
444                    List<Way> prims = Arrays.asList(es1.getWay(), es2.getWay());
445                    if ((highlight = crossingWays.get(prims)) == null) {
446                        highlight = new ArrayList<>();
447                        highlight.add(es1);
448                        highlight.add(es2);
449                        crossingWays.put(prims, highlight);
450                    } else {
451                        highlight.add(es1);
452                        highlight.add(es2);
453                    }
454                }
455                segments.add(es1);
456            }
457        }
458    }
459
460    /**
461     * Check if the given way is self crossing
462     * @param way the way to check
463     * @return {@code true} if one or more segments of the way are crossing
464     * @see SelfIntersectingWay
465     * @since 17393
466     */
467    public static boolean isSelfCrossing(Way way) {
468        CheckParameterUtil.ensureParameterNotNull(way, "way");
469        SelfCrossing test = new SelfCrossing();
470        test.visit(way);
471        return !test.getErrors().isEmpty();
472    }
473}