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.util.ArrayList;
007import java.util.Arrays;
008import java.util.Collection;
009import java.util.Collections;
010import java.util.HashMap;
011import java.util.HashSet;
012import java.util.List;
013import java.util.Map;
014import java.util.Set;
015import java.util.TreeSet;
016
017import org.openstreetmap.josm.data.osm.Node;
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.preferences.CollectionProperty;
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.gui.progress.ProgressMonitor;
028import org.openstreetmap.josm.tools.MultiMap;
029import org.openstreetmap.josm.tools.Pair;
030
031/**
032 * Tests if there are overlapping ways.
033 *
034 * @author frsantos
035 */
036public class OverlappingWays extends Test {
037
038    /** Bag of all way segments */
039    private MultiMap<Pair<Node, Node>, WaySegment> nodePairs;
040
041    protected static final int OVERLAPPING_HIGHWAY = 101;
042    protected static final int OVERLAPPING_RAILWAY = 102;
043    protected static final int OVERLAPPING_WAY = 103;
044    protected static final int OVERLAPPING_HIGHWAY_AREA = 111;
045    protected static final int OVERLAPPING_RAILWAY_AREA = 112;
046    protected static final int OVERLAPPING_WAY_AREA = 113;
047    protected static final int OVERLAPPING_AREA = 120;
048    protected static final int DUPLICATE_WAY_SEGMENT = 121;
049
050    protected static final CollectionProperty IGNORED_KEYS = new CollectionProperty(
051            "overlapping-ways.ignored-keys", Arrays.asList("barrier", "building", "historic:building", "man_made"));
052
053    /** Constructor */
054    public OverlappingWays() {
055        super(tr("Overlapping ways"),
056                tr("This test checks that a connection between two nodes "
057                        + "is not used by more than one way."));
058    }
059
060    @Override
061    public void startTest(ProgressMonitor monitor) {
062        super.startTest(monitor);
063        nodePairs = new MultiMap<>(1000);
064    }
065
066    private static boolean parentMultipolygonConcernsArea(OsmPrimitive p) {
067        for (Relation r : OsmPrimitive.getFilteredList(p.getReferrers(), Relation.class)) {
068            if (r.concernsArea()) {
069                return true;
070            }
071        }
072        return false;
073    }
074
075    @Override
076    public void endTest() {
077        Map<List<Way>, Set<WaySegment>> seenWays = new HashMap<>(500);
078
079        Collection<TestError> preliminaryErrors = new ArrayList<>();
080        for (Set<WaySegment> duplicated : nodePairs.values()) {
081            int ways = duplicated.size();
082
083            if (ways > 1) {
084                List<OsmPrimitive> prims = new ArrayList<>();
085                List<Way> currentWays = new ArrayList<>();
086                Collection<WaySegment> highlight;
087                int highway = 0;
088                int railway = 0;
089                int area = 0;
090
091                for (WaySegment ws : duplicated) {
092                    if (ws.way.get("highway") != null) {
093                        highway++;
094                    } else if (ws.way.get("railway") != null) {
095                        railway++;
096                    }
097                    Boolean ar = OsmUtils.getOsmBoolean(ws.way.get("area"));
098                    if (ar != null && ar) {
099                        area++;
100                    }
101                    if (ws.way.concernsArea() || parentMultipolygonConcernsArea(ws.way)) {
102                        area++;
103                        ways--;
104                    }
105
106                    prims.add(ws.way);
107                    currentWays.add(ws.way);
108                }
109                /* These ways not seen before
110                 * If two or more of the overlapping ways are
111                 * highways or railways mark a separate error
112                 */
113                if ((highlight = seenWays.get(currentWays)) == null) {
114                    String errortype;
115                    int type;
116
117                    if (area > 0) {
118                        if (ways == 0 || duplicated.size() == area) {
119                            errortype = tr("Areas share segment");
120                            type = OVERLAPPING_AREA;
121                        } else if (highway == ways) {
122                            errortype = tr("Highways share segment with area");
123                            type = OVERLAPPING_HIGHWAY_AREA;
124                        } else if (railway == ways) {
125                            errortype = tr("Railways share segment with area");
126                            type = OVERLAPPING_RAILWAY_AREA;
127                        } else {
128                            errortype = tr("Ways share segment with area");
129                            type = OVERLAPPING_WAY_AREA;
130                        }
131                    } else if (highway == ways) {
132                        errortype = tr("Overlapping highways");
133                        type = OVERLAPPING_HIGHWAY;
134                    } else if (railway == ways) {
135                        errortype = tr("Overlapping railways");
136                        type = OVERLAPPING_RAILWAY;
137                    } else {
138                        errortype = tr("Overlapping ways");
139                        type = OVERLAPPING_WAY;
140                    }
141
142                    Severity severity = type < OVERLAPPING_HIGHWAY_AREA ? Severity.WARNING : Severity.OTHER;
143                    preliminaryErrors.add(TestError.builder(this, severity, type)
144                            .message(errortype)
145                            .primitives(prims)
146                            .highlightWaySegments(duplicated)
147                            .build());
148                    seenWays.put(currentWays, duplicated);
149                } else { /* way seen, mark highlight layer only */
150                    highlight.addAll(duplicated);
151                }
152            }
153        }
154
155        // see ticket #9598 - only report if at least 3 segments are shared, except for overlapping ways, i.e warnings (see #9820)
156        for (TestError error : preliminaryErrors) {
157            if (error.getSeverity().equals(Severity.WARNING) || error.getHighlighted().size() / error.getPrimitives().size() >= 3) {
158                boolean ignore = false;
159                for (String ignoredKey : IGNORED_KEYS.get()) {
160                    if (error.getPrimitives().stream().anyMatch(p -> p.hasKey(ignoredKey))) {
161                        ignore = true;
162                        break;
163                    }
164                }
165                if (!ignore) {
166                    errors.add(error);
167                }
168            }
169        }
170
171        super.endTest();
172        nodePairs = null;
173    }
174
175    protected static Set<WaySegment> checkDuplicateWaySegment(Way w) {
176        // test for ticket #4959
177        Set<WaySegment> segments = new TreeSet<>((o1, o2) -> {
178            final List<Node> n1 = Arrays.asList(o1.getFirstNode(), o1.getSecondNode());
179            final List<Node> n2 = Arrays.asList(o2.getFirstNode(), o2.getSecondNode());
180            Collections.sort(n1);
181            Collections.sort(n2);
182            final int first = n1.get(0).compareTo(n2.get(0));
183            final int second = n1.get(1).compareTo(n2.get(1));
184            return first != 0 ? first : second;
185        });
186        final Set<WaySegment> duplicateWaySegments = new HashSet<>();
187
188        for (int i = 0; i < w.getNodesCount() - 1; i++) {
189            final WaySegment segment = new WaySegment(w, i);
190            final boolean wasInSet = !segments.add(segment);
191            if (wasInSet) {
192                duplicateWaySegments.add(segment);
193            }
194        }
195        if (duplicateWaySegments.size() > 1) {
196            return duplicateWaySegments;
197        } else {
198            return null;
199        }
200    }
201
202    @Override
203    public void visit(Way w) {
204
205        final Set<WaySegment> duplicateWaySegment = checkDuplicateWaySegment(w);
206        if (duplicateWaySegment != null) {
207            errors.add(TestError.builder(this, Severity.ERROR, DUPLICATE_WAY_SEGMENT)
208                    .message(tr("Way contains segment twice"))
209                    .primitives(w)
210                    .highlightWaySegments(duplicateWaySegment)
211                    .build());
212            return;
213        }
214
215        Node lastN = null;
216        int i = -2;
217        for (Node n : w.getNodes()) {
218            i++;
219            if (lastN == null) {
220                lastN = n;
221                continue;
222            }
223            nodePairs.put(Pair.sort(new Pair<>(lastN, n)),
224                    new WaySegment(w, i));
225            lastN = n;
226        }
227    }
228}