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}