source: josm/trunk/src/org/openstreetmap/josm/data/validation/tests/UnconnectedWays.java@ 16404

Last change on this file since 16404 was 16404, checked in by GerdP, 4 years ago

see #17914: End node near other way test does not work if highways are connected with another node

  • add man_made=embankment and man_made=dyke as barrier like obstacles
  • Property svn:eol-style set to native
File size: 22.8 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.validation.tests;
3
4import static org.openstreetmap.josm.data.validation.tests.CrossingWays.HIGHWAY;
5import static org.openstreetmap.josm.data.validation.tests.CrossingWays.RAILWAY;
6import static org.openstreetmap.josm.tools.I18n.tr;
7
8import java.awt.geom.Area;
9import java.util.ArrayList;
10import java.util.Arrays;
11import java.util.Collection;
12import java.util.Collections;
13import java.util.HashMap;
14import java.util.HashSet;
15import java.util.Iterator;
16import java.util.LinkedHashSet;
17import java.util.List;
18import java.util.Map;
19import java.util.Map.Entry;
20import java.util.Objects;
21import java.util.Set;
22import java.util.stream.Collectors;
23
24import org.openstreetmap.josm.data.coor.EastNorth;
25import org.openstreetmap.josm.data.coor.LatLon;
26import org.openstreetmap.josm.data.osm.BBox;
27import org.openstreetmap.josm.data.osm.DataSet;
28import org.openstreetmap.josm.data.osm.Node;
29import org.openstreetmap.josm.data.osm.OsmDataManager;
30import org.openstreetmap.josm.data.osm.OsmPrimitive;
31import org.openstreetmap.josm.data.osm.OsmUtils;
32import org.openstreetmap.josm.data.osm.QuadBuckets;
33import org.openstreetmap.josm.data.osm.Way;
34import org.openstreetmap.josm.data.preferences.sources.ValidatorPrefHelper;
35import org.openstreetmap.josm.data.projection.Ellipsoid;
36import org.openstreetmap.josm.data.projection.ProjectionRegistry;
37import org.openstreetmap.josm.data.validation.Severity;
38import org.openstreetmap.josm.data.validation.Test;
39import org.openstreetmap.josm.data.validation.TestError;
40import org.openstreetmap.josm.gui.progress.ProgressMonitor;
41import org.openstreetmap.josm.spi.preferences.Config;
42import org.openstreetmap.josm.tools.Geometry;
43import org.openstreetmap.josm.tools.Logging;
44
45/**
46 * Checks if a way has an endpoint very near to another way.
47 * <br>
48 * This class is abstract since highway/railway/waterway/… ways must be handled separately.
49 * An actual implementation must override {@link #isPrimitiveUsable(OsmPrimitive)}
50 * to denote which kind of primitives can be handled.
51 *
52 * @author frsantos
53 */
54public abstract class UnconnectedWays extends Test {
55 private final int code;
56 private final boolean isHighwayTest;
57
58 static final double DETOUR_FACTOR = 4;
59
60 protected abstract boolean isCandidate(OsmPrimitive p);
61
62 protected boolean isWantedWay(Way w) {
63 return w.isUsable() && isCandidate(w);
64 }
65
66 /**
67 * Check if unconnected end node should be ignored.
68 * @param n the node
69 * @return true if node should be ignored
70 */
71 protected boolean ignoreUnconnectedEndNode(Node n) {
72 return false;
73 }
74
75 @Override
76 public boolean isPrimitiveUsable(OsmPrimitive p) {
77 return super.isPrimitiveUsable(p) && ((partialSelection && p instanceof Node) || isCandidate(p));
78 }
79
80 /**
81 * Unconnected highways test.
82 */
83 public static class UnconnectedHighways extends UnconnectedWays {
84 static final int UNCONNECTED_HIGHWAYS = 1311;
85
86 /**
87 * Constructs a new {@code UnconnectedHighways} test.
88 */
89 public UnconnectedHighways() {
90 super(tr("Unconnected highways"), UNCONNECTED_HIGHWAYS, true);
91 }
92
93 @Override
94 protected boolean isCandidate(OsmPrimitive p) {
95 return p.hasKey(HIGHWAY);
96 }
97
98 @Override
99 protected boolean ignoreUnconnectedEndNode(Node n) {
100 return n.hasTag(HIGHWAY, "turning_circle", "bus_stop", "elevator")
101 || n.hasTag("amenity", "parking_entrance")
102 || n.isKeyTrue("noexit")
103 || n.hasKey("entrance", "barrier")
104 || n.getParentWays().stream().anyMatch(Test::isBuilding);
105 }
106 }
107
108 /**
109 * Unconnected railways test.
110 */
111 public static class UnconnectedRailways extends UnconnectedWays {
112 static final int UNCONNECTED_RAILWAYS = 1321;
113 /**
114 * Constructs a new {@code UnconnectedRailways} test.
115 */
116 public UnconnectedRailways() {
117 super(tr("Unconnected railways"), UNCONNECTED_RAILWAYS, false);
118 }
119
120 @Override
121 protected boolean isCandidate(OsmPrimitive p) {
122 return p.hasTagDifferent(RAILWAY, "abandoned", "platform", "razed");
123 }
124
125 @Override
126 protected boolean ignoreUnconnectedEndNode(Node n) {
127 return n.hasTag(RAILWAY, "buffer_stop")
128 || n.isKeyTrue("noexit");
129 }
130 }
131
132 /**
133 * Unconnected waterways test.
134 */
135 public static class UnconnectedWaterways extends UnconnectedWays {
136 static final int UNCONNECTED_WATERWAYS = 1331;
137 /**
138 * Constructs a new {@code UnconnectedWaterways} test.
139 */
140 public UnconnectedWaterways() {
141 super(tr("Unconnected waterways"), UNCONNECTED_WATERWAYS, false);
142 }
143
144 @Override
145 protected boolean isCandidate(OsmPrimitive p) {
146 return p.hasKey("waterway");
147 }
148 }
149
150 /**
151 * Unconnected natural/landuse test.
152 */
153 public static class UnconnectedNaturalOrLanduse extends UnconnectedWays {
154 static final int UNCONNECTED_NATURAL_OR_LANDUSE = 1341;
155 /**
156 * Constructs a new {@code UnconnectedNaturalOrLanduse} test.
157 */
158 public UnconnectedNaturalOrLanduse() {
159 super(tr("Unconnected natural lands and landuses"), UNCONNECTED_NATURAL_OR_LANDUSE, false);
160 }
161
162 @Override
163 protected boolean isCandidate(OsmPrimitive p) {
164 return p.hasKey("landuse") || p.hasTagDifferent("natural", "tree_row", "cliff");
165 }
166 }
167
168 /**
169 * Unconnected power ways test.
170 */
171 public static class UnconnectedPower extends UnconnectedWays {
172 static final int UNCONNECTED_POWER = 1351;
173 /**
174 * Constructs a new {@code UnconnectedPower} test.
175 */
176 public UnconnectedPower() {
177 super(tr("Unconnected power ways"), UNCONNECTED_POWER, false);
178 }
179
180 @Override
181 protected boolean isCandidate(OsmPrimitive p) {
182 return p.hasTag("power", "line", "minor_line", "cable");
183 }
184
185 @Override
186 protected boolean ignoreUnconnectedEndNode(Node n) {
187 return n.hasTag("power", "terminal");
188 }
189 }
190
191 protected static final int UNCONNECTED_WAYS = 1301;
192 protected static final String PREFIX = ValidatorPrefHelper.PREFIX + "." + UnconnectedWays.class.getSimpleName();
193
194 private List<MyWaySegment> waySegments;
195 private Set<Node> endnodes; // nodes at end of way
196 private Set<Node> middlenodes; // nodes in middle of way
197 private Set<Node> othernodes; // nodes appearing at least twice
198 private QuadBuckets<Node> searchNodes;
199 private Set<Way> waysToTest;
200 private Set<Node> nodesToTest;
201 private Area dsArea;
202
203 private double mindist;
204 private double minmiddledist;
205 private double maxLen; // maximum length of allowed detour to reach the unconnected node
206 private DataSet ds;
207
208 /**
209 * Constructs a new {@code UnconnectedWays} test.
210 * @param title The test title
211 * @since 6691
212 */
213 public UnconnectedWays(String title) {
214 this(title, UNCONNECTED_WAYS, false);
215
216 }
217
218 /**
219 * Constructs a new {@code UnconnectedWays} test with the given code.
220 * @param title The test title
221 * @param code The test code
222 * @param isHighwayTest use {@code true} if test concerns highways or railways
223 * @since 14468
224 */
225 public UnconnectedWays(String title, int code, boolean isHighwayTest) {
226 super(title, tr("This test checks if a way has an endpoint very near to another way."));
227 this.code = code;
228 this.isHighwayTest = isHighwayTest;
229 }
230
231 @Override
232 public void startTest(ProgressMonitor monitor) {
233 super.startTest(monitor);
234 waySegments = new ArrayList<>();
235 searchNodes = new QuadBuckets<>();
236 waysToTest = new HashSet<>();
237 nodesToTest = new HashSet<>();
238 endnodes = new HashSet<>();
239 middlenodes = new HashSet<>();
240 othernodes = new HashSet<>();
241 mindist = Config.getPref().getDouble(PREFIX + ".node_way_distance", 10.0);
242 minmiddledist = Config.getPref().getDouble(PREFIX + ".way_way_distance", 0.0);
243 ds = OsmDataManager.getInstance().getActiveDataSet();
244 dsArea = ds == null ? null : ds.getDataSourceArea();
245 }
246
247 protected Map<Node, MyWaySegment> getHighwayEndNodesNearOtherHighway() {
248 Map<Node, MyWaySegment> map = new HashMap<>();
249 for (MyWaySegment s : waySegments) {
250 if (isCanceled()) {
251 map.clear();
252 return map;
253 }
254 if (s.w.hasTag(HIGHWAY, "platform"))
255 continue;
256 for (Node endnode : s.nearbyNodes(mindist)) {
257 Way parentWay = getWantedParentWay(endnode);
258 if (parentWay != null && !parentWay.hasTag(HIGHWAY, "platform")
259 && Objects.equals(OsmUtils.getLayer(s.w), OsmUtils.getLayer(parentWay))
260 // to handle intersections of 't' shapes and similar
261 && !s.isConnectedTo(endnode) && !s.obstacleBetween(endnode)) {
262 addIfNewOrCloser(map, endnode, s);
263 }
264 }
265 }
266 return map;
267 }
268
269 protected Map<Node, MyWaySegment> getWayEndNodesNearOtherWay() {
270 Map<Node, MyWaySegment> map = new HashMap<>();
271
272 for (MyWaySegment s : waySegments) {
273 if (isCanceled()) {
274 map.clear();
275 return map;
276 }
277 if (!s.concernsArea) {
278 for (Node endnode : s.nearbyNodes(mindist)) {
279 if (!s.isConnectedTo(endnode)) {
280 if (s.w.hasTag("power")) {
281 boolean badConnection = false;
282 Way otherWay = getWantedParentWay(endnode);
283 if (otherWay != null) {
284 for (String key : Arrays.asList("voltage", "frequency")) {
285 String v1 = s.w.get(key);
286 String v2 = otherWay.get(key);
287 if (v1 != null && v2 != null && !v1.equals(v2)) {
288 badConnection = true;
289 }
290 }
291 }
292 if (badConnection)
293 continue;
294 }
295 addIfNewOrCloser(map, endnode, s);
296 }
297 }
298 }
299 }
300 return map;
301 }
302
303 protected Map<Node, MyWaySegment> getWayNodesNearOtherWay() {
304 Map<Node, MyWaySegment> map = new HashMap<>();
305 for (MyWaySegment s : waySegments) {
306 if (isCanceled()) {
307 map.clear();
308 return map;
309 }
310 for (Node en : s.nearbyNodes(minmiddledist)) {
311 if (!s.isConnectedTo(en)) {
312 addIfNewOrCloser(map, en, s);
313 }
314 }
315 }
316 return map;
317 }
318
319 /**
320 * An unconnected node might have multiple parent ways, e.g. a highway and a landuse way.
321 * Make sure we get the one that was analysed before.
322 * @param endnode the node which is known to be an end node of the wanted way
323 * @return the wanted way
324 */
325 private Way getWantedParentWay(Node endnode) {
326 for (Way w : endnode.getParentWays()) {
327 if (isWantedWay(w))
328 return w;
329 }
330 Logging.error("end node without matching parent way");
331 return null;
332 }
333
334 private void addIfNewOrCloser(Map<Node, MyWaySegment> map, Node node, MyWaySegment ws) {
335 if (partialSelection && !nodesToTest.contains(node) && !waysToTest.contains(ws.w))
336 return;
337 MyWaySegment old = map.get(node);
338 if (old != null) {
339 double d1 = ws.getDist(node);
340 double d2 = old.getDist(node);
341 if (d1 > d2) {
342 // keep old value
343 return;
344 }
345 }
346 map.put(node, ws);
347 }
348
349 protected final void addErrors(Severity severity, Map<Node, MyWaySegment> errorMap, String message) {
350 for (Entry<Node, MyWaySegment> error : errorMap.entrySet()) {
351 Node node = error.getKey();
352 MyWaySegment ws = error.getValue();
353 errors.add(TestError.builder(this, severity, code)
354 .message(message)
355 .primitives(node, ws.w)
356 .highlight(node)
357 .build());
358 }
359 }
360
361 @Override
362 public void endTest() {
363 if (ds == null)
364 return;
365
366 for (Way w : ds.getWays()) {
367 if (isWantedWay(w) && w.getRealNodesCount() > 1) {
368 waySegments.addAll(getWaySegments(w));
369 addNode(w.firstNode(), endnodes);
370 addNode(w.lastNode(), endnodes);
371 }
372 }
373 fillSearchNodes(endnodes);
374 if (!searchNodes.isEmpty()) {
375 maxLen = DETOUR_FACTOR * mindist;
376 if (isHighwayTest) {
377 addErrors(Severity.WARNING, getHighwayEndNodesNearOtherHighway(), tr("Way end node near other highway"));
378 } else {
379 addErrors(Severity.WARNING, getWayEndNodesNearOtherWay(), tr("Way end node near other way"));
380 }
381 }
382
383 /* the following two should use a shorter distance */
384 boolean includeOther = isBeforeUpload ? ValidatorPrefHelper.PREF_OTHER_UPLOAD.get() : ValidatorPrefHelper.PREF_OTHER.get();
385 if (minmiddledist > 0.0 && includeOther) {
386 maxLen = DETOUR_FACTOR * minmiddledist;
387 fillSearchNodes(middlenodes);
388 addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Way node near other way"));
389 fillSearchNodes(othernodes);
390 addErrors(Severity.OTHER, getWayNodesNearOtherWay(), tr("Connected way end node near other way"));
391 }
392
393 waySegments = null;
394 endnodes = null;
395 middlenodes = null;
396 othernodes = null;
397 searchNodes = null;
398 dsArea = null;
399 ds = null;
400 super.endTest();
401 }
402
403 private void fillSearchNodes(Collection<Node> nodes) {
404 searchNodes.clear();
405 for (Node n : nodes) {
406 if (!ignoreUnconnectedEndNode(n) && n.getCoor().isIn(dsArea)) {
407 searchNodes.add(n);
408 }
409 }
410 }
411
412 private class MyWaySegment {
413 /** the way */
414 public final Way w;
415 private final Node n1;
416 private final Node n2;
417 private final boolean concernsArea;
418
419 MyWaySegment(Way w, Node n1, Node n2, boolean concersArea) {
420 this.w = w;
421 this.n1 = n1;
422 this.n2 = n2;
423 this.concernsArea = concersArea;
424 }
425
426 /**
427 * Check if the given node is connected to this segment using a reasonable short way.
428 * @param startNode the node
429 * @return true if a reasonable connection was found
430 */
431 boolean isConnectedTo(Node startNode) {
432 return isConnectedTo(startNode, new LinkedHashSet<>(), 0, w);
433 }
434
435 /**
436 * Check if the given node is connected to this segment using a reasonable short way.
437 * @param node the given node
438 * @param visited set of visited nodes
439 * @param len length of the travelled route
440 * @param parent the previous parent way
441 * @return true if a reasonable connection was found
442 */
443 private boolean isConnectedTo(Node node, LinkedHashSet<Node> visited, double len, Way parent) {
444 if (len > maxLen) {
445 return false;
446 }
447 if (n1 == node || n2 == node) {
448 Node uncon = visited.iterator().next();
449 LatLon cl = ProjectionRegistry.getProjection().eastNorth2latlon(calcClosest(uncon));
450 // calculate real detour length, closest point might be somewhere between n1 and n2
451 double detourLen = len + node.getCoor().greatCircleDistance(cl);
452 if (detourLen > maxLen)
453 return false;
454 // see #17914: flag also nodes which are very close
455 double directDist = getDist(uncon);
456 if (directDist <= 0.1)
457 return false;
458 return directDist > 0.5 || (visited.size() == 2 && directDist * 1.5 > detourLen);
459 }
460 if (visited != null) {
461 visited.add(node);
462 List<Way> wantedParents = node.getParentWays().stream().filter(pw -> isWantedWay(pw))
463 .collect(Collectors.toList());
464 if (wantedParents.size() > 1 && wantedParents.indexOf(parent) != wantedParents.size() - 1) {
465 // we want to find a different way. so move known way to the end of the list
466 wantedParents.remove(parent);
467 wantedParents.add(parent);
468 }
469
470 for (final Way way : wantedParents) {
471 List<Node> nextNodes = new ArrayList<>();
472 int pos = way.getNodes().indexOf(node);
473 if (pos > 0) {
474 nextNodes.add(way.getNode(pos - 1));
475 }
476 if (pos + 1 < way.getNodesCount()) {
477 nextNodes.add(way.getNode(pos + 1));
478 }
479 for (Node next : nextNodes) {
480 final boolean containsN = visited.contains(next);
481 visited.add(next);
482 if (!containsN && isConnectedTo(next, visited,
483 len + node.getCoor().greatCircleDistance(next.getCoor()), way)) {
484 return true;
485 }
486 }
487 }
488 }
489 return false;
490 }
491
492 private EastNorth calcClosest(Node n) {
493 return Geometry.closestPointToSegment(n1.getEastNorth(), n2.getEastNorth(), n.getEastNorth());
494 }
495
496 double getDist(Node n) {
497 EastNorth closest = calcClosest(n);
498 return n.getCoor().greatCircleDistance(ProjectionRegistry.getProjection().eastNorth2latlon(closest));
499 }
500
501 private boolean nearby(Node n, double dist) {
502 if (w.containsNode(n))
503 return false;
504 double d = getDist(n);
505 return !Double.isNaN(d) && d < dist;
506 }
507
508 private BBox getBounds(double fudge) {
509 double x1 = n1.getCoor().lon();
510 double x2 = n2.getCoor().lon();
511 if (x1 > x2) {
512 double tmpx = x1;
513 x1 = x2;
514 x2 = tmpx;
515 }
516 double y1 = n1.getCoor().lat();
517 double y2 = n2.getCoor().lat();
518 if (y1 > y2) {
519 double tmpy = y1;
520 y1 = y2;
521 y2 = tmpy;
522 }
523 LatLon topLeft = new LatLon(y2+fudge, x1-fudge);
524 LatLon botRight = new LatLon(y1-fudge, x2+fudge);
525 return new BBox(topLeft, botRight);
526 }
527
528 /**
529 * We know that any point near the line segment must be at
530 * least as close as the other end of the line, plus
531 * a little fudge for the distance away (dist)
532 * @param dist fudge to add
533 * @return collection of nearby nodes
534 */
535 Collection<Node> nearbyNodes(double dist) {
536 BBox bounds = this.getBounds(dist * (360.0d / (Ellipsoid.WGS84.a * 2 * Math.PI)));
537 List<Node> result = null;
538 List<Node> foundNodes = searchNodes.search(bounds);
539 for (Node n : foundNodes) {
540 if (!nearby(n, dist)) {
541 continue;
542 }
543 // It is actually very rare for us to find a node
544 // so defer as much of the work as possible, like
545 // allocating the hash set
546 if (result == null) {
547 result = new ArrayList<>();
548 }
549 result.add(n);
550 }
551 return result == null ? Collections.emptyList() : result;
552 }
553
554 private boolean obstacleBetween(Node endnode) {
555 EastNorth en = endnode.getEastNorth();
556 EastNorth closest = calcClosest(endnode);
557 LatLon llClosest = ProjectionRegistry.getProjection().eastNorth2latlon(closest);
558 // find obstacles between end node and way segment
559 BBox bbox = new BBox(endnode.getCoor(), llClosest);
560 for (Way nearbyWay : ds.searchWays(bbox)) {
561 if (nearbyWay != w && nearbyWay.isUsable() && isObstacle(nearbyWay)
562 && !endnode.getParentWays().contains(nearbyWay)) {
563 //make sure that the obstacle is really between endnode and the highway segment, not just close to or around them
564 Iterator<Node> iter = nearbyWay.getNodes().iterator();
565 EastNorth prev = iter.next().getEastNorth();
566 while (iter.hasNext()) {
567 EastNorth curr = iter.next().getEastNorth();
568 if (Geometry.getSegmentSegmentIntersection(closest, en, prev, curr) != null) {
569 return true;
570 }
571 prev = curr;
572 }
573 }
574 }
575 return false;
576 }
577
578 private boolean isObstacle(Way w) {
579 return w.hasKey("barrier", "waterway") || isBuilding(w) || w.hasTag("man_made", "embankment", "dyke");
580 }
581 }
582
583 List<MyWaySegment> getWaySegments(Way w) {
584 List<MyWaySegment> ret = new ArrayList<>();
585 if (!w.isUsable() || w.isKeyTrue("disused"))
586 return ret;
587
588 int size = w.getNodesCount();
589 boolean concersArea = w.concernsArea();
590 for (int i = 1; i < size; ++i) {
591 if (i < size-1) {
592 addNode(w.getNode(i), middlenodes);
593 }
594 Node a = w.getNode(i-1);
595 Node b = w.getNode(i);
596 if (a.isDrawable() && b.isDrawable()) {
597 MyWaySegment ws = new MyWaySegment(w, a, b, concersArea);
598 ret.add(ws);
599 }
600 }
601 return ret;
602 }
603
604 @Override
605 public void visit(Way w) {
606 if (partialSelection) {
607 waysToTest.add(w);
608 }
609 }
610
611 @Override
612 public void visit(Node n) {
613 if (partialSelection) {
614 nodesToTest.add(n);
615 }
616 }
617
618 private void addNode(Node n, Set<Node> s) {
619 boolean m = middlenodes.contains(n);
620 boolean e = endnodes.contains(n);
621 boolean o = othernodes.contains(n);
622 if (!m && !e && !o) {
623 s.add(n);
624 } else if (!o) {
625 othernodes.add(n);
626 if (e) {
627 endnodes.remove(n);
628 } else {
629 middlenodes.remove(n);
630 }
631 }
632 }
633}
Note: See TracBrowser for help on using the repository browser.