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.data.validation.tests.CrossingWays.WATERWAY; 007import static org.openstreetmap.josm.tools.I18n.tr; 008 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.LinkedHashSet; 016import java.util.List; 017import java.util.Map; 018import java.util.Set; 019import java.util.TreeSet; 020import java.util.function.Predicate; 021import java.util.stream.Collectors; 022 023import org.openstreetmap.josm.data.osm.Node; 024import org.openstreetmap.josm.data.osm.OsmPrimitive; 025import org.openstreetmap.josm.data.osm.OsmUtils; 026import org.openstreetmap.josm.data.osm.Relation; 027import org.openstreetmap.josm.data.osm.Way; 028import org.openstreetmap.josm.data.osm.WaySegment; 029import org.openstreetmap.josm.data.preferences.ListProperty; 030import org.openstreetmap.josm.data.preferences.sources.ValidatorPrefHelper; 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.MultiMap; 037import org.openstreetmap.josm.tools.Pair; 038 039/** 040 * Tests if there are overlapping ways. 041 * 042 * @author frsantos 043 * @since 3669 044 */ 045public class OverlappingWays extends Test { 046 047 /** Bag of all way segments */ 048 private MultiMap<Pair<Node, Node>, WaySegment> nodePairs; 049 050 private boolean onlyKnownLinear; 051 private boolean includeOther; 052 private boolean ignoreLayer; 053 054 protected static final int OVERLAPPING_HIGHWAY = 101; 055 protected static final int OVERLAPPING_RAILWAY = 102; 056 protected static final int OVERLAPPING_WAY = 103; 057 protected static final int OVERLAPPING_WATERWAY = 104; 058 protected static final int OVERLAPPING_HIGHWAY_AREA = 111; 059 protected static final int OVERLAPPING_RAILWAY_AREA = 112; 060 protected static final int OVERLAPPING_WAY_AREA = 113; 061 protected static final int OVERLAPPING_WATERWAY_AREA = 114; 062 protected static final int DUPLICATE_WAY_SEGMENT = 121; 063 protected static final int OVERLAPPING_HIGHWAY_LINEAR_WAY = 131; 064 protected static final int OVERLAPPING_RAILWAY_LINEAR_WAY = 132; 065 protected static final int OVERLAPPING_WATERWAY_LINEAR_WAY = 133; 066 067 protected static final ListProperty IGNORED_KEYS = new ListProperty( 068 "overlapping-ways.ignored-keys", Arrays.asList( 069 "barrier", "indoor", "building", "building:part", "historic:building", "demolished:building", 070 "removed:building", "disused:building", "abandoned:building", "proposed:building", "man_made")); 071 protected static final Predicate<OsmPrimitive> IGNORED = primitive -> 072 IGNORED_KEYS.get().stream().anyMatch(primitive::hasKey) || primitive.hasTag("tourism", "camp_site"); 073 074 /** Constructor */ 075 public OverlappingWays() { 076 super(tr("Overlapping ways"), 077 tr("This test checks that a connection between two nodes " 078 + "is not used by more than one way.")); 079 } 080 081 @Override 082 public void startTest(ProgressMonitor monitor) { 083 super.startTest(monitor); 084 nodePairs = new MultiMap<>(1000); 085 includeOther = isBeforeUpload ? ValidatorPrefHelper.PREF_OTHER_UPLOAD.get() : ValidatorPrefHelper.PREF_OTHER.get(); 086 onlyKnownLinear = Config.getPref().getBoolean("overlapping-ways.only-known-linear", true); 087 ignoreLayer = Config.getPref().getBoolean("overlapping-ways.ignore-layer", false); 088 } 089 090 private static boolean parentMultipolygonConcernsArea(OsmPrimitive p) { 091 return p.referrers(Relation.class) 092 .anyMatch(Relation::isMultipolygon); 093 } 094 095 @Override 096 public void endTest() { 097 Map<List<Way>, Set<WaySegment>> seenWays = new HashMap<>(500); 098 099 for (Set<WaySegment> duplicated : nodePairs.values()) { 100 if (duplicated.size() <= 1) 101 continue; 102 if (ignoreLayer) { 103 analyseOverlaps(duplicated, seenWays); 104 } else { 105 // group by layer tag value (which is very likely null) 106 Map<String, Set<WaySegment>> grouped = new HashMap<>(); 107 for (WaySegment ws : duplicated) { 108 // order in set is important 109 grouped.computeIfAbsent(OsmUtils.getLayer(ws.getWay()), k -> new LinkedHashSet<>()).add(ws); 110 } 111 grouped.values().forEach(group -> analyseOverlaps(group, seenWays)); 112 } 113 } 114 nodePairs = null; 115 116 super.endTest(); 117 } 118 119 private void analyseOverlaps(Set<WaySegment> duplicated, Map<List<Way>, Set<WaySegment>> seenWays) { 120 int ways = duplicated.size(); 121 if (ways <= 1) 122 return; 123 124 List<Way> currentWays = duplicated.stream().map(ws -> ws.getWay()).collect(Collectors.toList()); 125 Collection<WaySegment> highlight; 126 if ((highlight = seenWays.get(currentWays)) != null) { 127 /* this combination of ways was seen before, just add highlighted segment */ 128 highlight.addAll(duplicated); 129 } else { 130 int countHighway = 0; 131 int countRailway = 0; 132 int countWaterway = 0; 133 int countOther = 0; 134 int numAreas = 0; 135 for (WaySegment ws : duplicated) { 136 boolean isArea = ws.getWay().concernsArea(); 137 if (ws.getWay().hasKey(HIGHWAY)) { 138 if (!isArea) { 139 countHighway++; 140 } 141 } else if (ws.getWay().hasKey(RAILWAY)) { 142 if (!isArea) { 143 countRailway++; 144 } 145 } else if (ws.getWay().hasKey(WATERWAY)) { 146 if (!isArea) { 147 countWaterway++; 148 } 149 } else { 150 if (ws.getWay().getInterestingTags().isEmpty() && parentMultipolygonConcernsArea(ws.getWay())) 151 isArea = true; 152 if (!isArea && isOtherLinear(ws.getWay())) { 153 countOther++; 154 } 155 } 156 if (isArea) { 157 numAreas++; 158 } 159 } 160 if (numAreas == ways) { 161 // no linear object, we don't care when areas share segments 162 return; 163 } 164 165 166 // If two or more of the overlapping ways are highways or railways mark a separate error 167 String errortype; 168 int type; 169 int allKnownLinear = countHighway + countRailway + countWaterway + countOther; 170 final Severity severity; 171 if (countHighway > 1) { 172 errortype = tr("Overlapping highways"); 173 type = OVERLAPPING_HIGHWAY; 174 severity = Severity.ERROR; 175 } else if (countRailway > 1) { 176 errortype = tr("Overlapping railways"); 177 type = OVERLAPPING_RAILWAY; 178 severity = Severity.ERROR; 179 } else if (countWaterway > 1) { 180 errortype = tr("Overlapping waterways"); 181 type = OVERLAPPING_WATERWAY; 182 severity = Severity.ERROR; 183 } else if (countHighway > 0 && countHighway < allKnownLinear) { 184 errortype = tr("Highway shares segment with linear way"); 185 type = OVERLAPPING_HIGHWAY_LINEAR_WAY; 186 severity = Severity.WARNING; 187 } else if (countRailway > 0 && countRailway < allKnownLinear) { 188 errortype = tr("Railway shares segment with linear way"); 189 type = OVERLAPPING_HIGHWAY_LINEAR_WAY; 190 severity = Severity.WARNING; 191 } else if (countWaterway > 0 && countWaterway < allKnownLinear) { 192 errortype = tr("Waterway shares segment with linear way"); 193 type = OVERLAPPING_WATERWAY_LINEAR_WAY; 194 severity = Severity.WARNING; 195 } else if (!includeOther || onlyKnownLinear) { 196 return; 197 } else if (countHighway > 0) { 198 errortype = tr("Highway shares segment with other way"); 199 type = OVERLAPPING_HIGHWAY_AREA; 200 severity = Severity.OTHER; 201 } else if (countRailway > 0) { 202 errortype = tr("Railway shares segment with other way"); 203 type = OVERLAPPING_RAILWAY_AREA; 204 severity = Severity.OTHER; 205 } else if (countWaterway > 0) { 206 errortype = tr("Waterway shares segment with other way"); 207 type = OVERLAPPING_WATERWAY_AREA; 208 severity = Severity.OTHER; 209 } else { 210 errortype = tr("Ways share segment"); 211 type = OVERLAPPING_WAY; 212 severity = Severity.OTHER; 213 } 214 215 List<OsmPrimitive> prims = new ArrayList<>(currentWays); 216 errors.add(TestError.builder(this, severity, type) 217 .message(errortype) 218 .primitives(prims) 219 .highlightWaySegments(duplicated) 220 .build()); 221 seenWays.put(currentWays, duplicated); 222 } 223 } 224 225 private static boolean isOtherLinear(Way way) { 226 // it is assumed that area=* was evaluated before and is false 227 return (way.hasKey("barrier", "addr:interpolation", "route", "ford") 228 || way.hasTag("natural", "tree_row", "cliff", "ridge") 229 || way.hasTag("power", "line", "minor_line", "cable", "portal") 230 || way.hasTag("man_made", "pipeline")); 231 } 232 233 protected static Set<WaySegment> checkDuplicateWaySegment(Way w) { 234 // test for ticket #4959 235 Set<WaySegment> segments = new TreeSet<>((o1, o2) -> { 236 final List<Node> n1 = Arrays.asList(o1.getFirstNode(), o1.getSecondNode()); 237 final List<Node> n2 = Arrays.asList(o2.getFirstNode(), o2.getSecondNode()); 238 Collections.sort(n1); 239 Collections.sort(n2); 240 final int first = n1.get(0).compareTo(n2.get(0)); 241 final int second = n1.get(1).compareTo(n2.get(1)); 242 return first != 0 ? first : second; 243 }); 244 final Set<WaySegment> duplicateWaySegments = new HashSet<>(); 245 246 for (int i = 0; i < w.getNodesCount() - 1; i++) { 247 final WaySegment segment = new WaySegment(w, i); 248 final boolean wasInSet = !segments.add(segment); 249 if (wasInSet) { 250 duplicateWaySegments.add(segment); 251 } 252 } 253 return duplicateWaySegments; 254 } 255 256 @Override 257 public void visit(Way w) { 258 259 final Set<WaySegment> duplicateWaySegment = checkDuplicateWaySegment(w); 260 if (!duplicateWaySegment.isEmpty()) { 261 errors.add(TestError.builder(this, Severity.ERROR, DUPLICATE_WAY_SEGMENT) 262 .message(tr("Way contains segment twice")) 263 .primitives(w) 264 .highlightWaySegments(duplicateWaySegment) 265 .build()); 266 return; 267 } 268 269 if (IGNORED.test(w)) 270 return; 271 272 if (onlyKnownLinear && (w.concernsArea() || w.getInterestingTags().isEmpty())) 273 return; 274 275 Node lastN = null; 276 int i = -2; 277 for (Node n : w.getNodes()) { 278 i++; 279 if (lastN == null) { 280 lastN = n; 281 continue; 282 } 283 nodePairs.put(Pair.sort(new Pair<>(lastN, n)), 284 new WaySegment(w, i)); 285 lastN = n; 286 } 287 } 288}