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