source: josm/trunk/src/org/openstreetmap/josm/data/validation/tests/MultipolygonTest.java@ 12941

Last change on this file since 12941 was 12941, checked in by GerdP, 7 years ago

fix #14766 - Self-intersection check not working for multipolygons

The test failed to detect self-intersecting rings formed by multiple ways.
This is now handled. Single self-intersecting ways are still only handled by SelfIntersectingWay to avoind duplicate warnings for the same issue.
  • Property svn:eol-style set to native
File size: 40.6 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.validation.tests;
3
4import static org.openstreetmap.josm.tools.I18n.marktr;
5import static org.openstreetmap.josm.tools.I18n.tr;
6import static org.openstreetmap.josm.tools.I18n.trn;
7
8import java.awt.geom.Area;
9import java.awt.geom.Point2D;
10import java.util.ArrayList;
11import java.util.Arrays;
12import java.util.Collection;
13import java.util.HashMap;
14import java.util.HashSet;
15import java.util.List;
16import java.util.Map;
17import java.util.Map.Entry;
18import java.util.Set;
19
20import org.openstreetmap.josm.command.ChangeCommand;
21import org.openstreetmap.josm.command.Command;
22import org.openstreetmap.josm.data.coor.EastNorth;
23import org.openstreetmap.josm.data.osm.DefaultNameFormatter;
24import org.openstreetmap.josm.data.osm.Node;
25import org.openstreetmap.josm.data.osm.OsmPrimitive;
26import org.openstreetmap.josm.data.osm.Relation;
27import org.openstreetmap.josm.data.osm.RelationMember;
28import org.openstreetmap.josm.data.osm.Way;
29import org.openstreetmap.josm.data.osm.WaySegment;
30import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
31import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData;
32import org.openstreetmap.josm.data.validation.OsmValidator;
33import org.openstreetmap.josm.data.validation.Severity;
34import org.openstreetmap.josm.data.validation.Test;
35import org.openstreetmap.josm.data.validation.TestError;
36import org.openstreetmap.josm.gui.mappaint.ElemStyles;
37import org.openstreetmap.josm.gui.mappaint.MapPaintStyles;
38import org.openstreetmap.josm.gui.mappaint.styleelement.AreaElement;
39import org.openstreetmap.josm.gui.progress.ProgressMonitor;
40import org.openstreetmap.josm.tools.Geometry;
41import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
42import org.openstreetmap.josm.tools.Logging;
43
44/**
45 * Checks if multipolygons are valid
46 * @since 3669
47 */
48public class MultipolygonTest extends Test {
49
50 /** Non-Way in multipolygon */
51 public static final int WRONG_MEMBER_TYPE = 1601;
52 /** No useful role for multipolygon member */
53 public static final int WRONG_MEMBER_ROLE = 1602;
54 /** Multipolygon is not closed */
55 public static final int NON_CLOSED_WAY = 1603;
56 /** No outer way for multipolygon */
57 public static final int MISSING_OUTER_WAY = 1604;
58 /** Multipolygon inner way is outside */
59 public static final int INNER_WAY_OUTSIDE = 1605;
60 /** Intersection between multipolygon ways */
61 public static final int CROSSING_WAYS = 1606;
62 /** Style for outer way mismatches / With the currently used mappaint style(s) the style for outer way mismatches the area style */
63 public static final int OUTER_STYLE_MISMATCH = 1607;
64 /** With the currently used mappaint style the style for inner way equals the multipolygon style */
65 public static final int INNER_STYLE_MISMATCH = 1608;
66 /** Area style way is not closed */
67 public static final int NOT_CLOSED = 1609;
68 /** No area style for multipolygon */
69 public static final int NO_STYLE = 1610;
70 /** Multipolygon relation should be tagged with area tags and not the outer way(s) */
71 public static final int NO_STYLE_POLYGON = 1611;
72 /** Area style on outer way */
73 public static final int OUTER_STYLE = 1613;
74 /** Multipolygon member repeated (same primitive, same role */
75 public static final int REPEATED_MEMBER_SAME_ROLE = 1614;
76 /** Multipolygon member repeated (same primitive, different role) */
77 public static final int REPEATED_MEMBER_DIFF_ROLE = 1615;
78 /** Multipolygon ring is equal to another ring */
79 public static final int EQUAL_RINGS = 1616;
80 /** Multipolygon rings share nodes */
81 public static final int RINGS_SHARE_NODES = 1617;
82
83 private static final int FOUND_INSIDE = 1;
84 private static final int FOUND_OUTSIDE = 2;
85
86 private final Set<String> keysCheckedByAnotherTest = new HashSet<>();
87
88 /**
89 * Constructs a new {@code MultipolygonTest}.
90 */
91 public MultipolygonTest() {
92 super(tr("Multipolygon"),
93 tr("This test checks if multipolygons are valid."));
94 }
95
96 @Override
97 public void startTest(ProgressMonitor progressMonitor) {
98 super.startTest(progressMonitor);
99 keysCheckedByAnotherTest.clear();
100 for (Test t : OsmValidator.getEnabledTests(false)) {
101 if (t instanceof UnclosedWays) {
102 keysCheckedByAnotherTest.addAll(((UnclosedWays) t).getCheckedKeys());
103 break;
104 }
105 }
106 }
107
108 @Override
109 public void endTest() {
110 keysCheckedByAnotherTest.clear();
111 super.endTest();
112 }
113
114 @Override
115 public void visit(Way w) {
116 if (!w.isArea() && ElemStyles.hasOnlyAreaElements(w)) {
117 List<Node> nodes = w.getNodes();
118 if (nodes.isEmpty()) return; // fix zero nodes bug
119 for (String key : keysCheckedByAnotherTest) {
120 if (w.hasKey(key)) {
121 return;
122 }
123 }
124 errors.add(TestError.builder(this, Severity.WARNING, NOT_CLOSED)
125 .message(tr("Area style way is not closed"))
126 .primitives(w)
127 .highlight(Arrays.asList(nodes.get(0), nodes.get(nodes.size() - 1)))
128 .build());
129 }
130 }
131
132 @Override
133 public void visit(Relation r) {
134 if (r.isMultipolygon() && r.getMembersCount() > 0) {
135 checkMembersAndRoles(r);
136 checkOuterWay(r);
137 boolean hasRepeatedMembers = checkRepeatedWayMembers(r);
138 // Rest of checks is only for complete multipolygon
139 if (!hasRepeatedMembers && !r.hasIncompleteMembers()) {
140 Multipolygon polygon = new Multipolygon(r);
141 checkStyleConsistency(r, polygon);
142 checkGeometryAndRoles(r, polygon);
143 }
144 }
145 }
146
147 /**
148 * Checks that multipolygon has at least an outer way:<ul>
149 * <li>{@link #MISSING_OUTER_WAY}: No outer way for multipolygon</li>
150 * </ul>
151 * @param r relation
152 */
153 private void checkOuterWay(Relation r) {
154 for (RelationMember m : r.getMembers()) {
155 if (m.isWay() && "outer".equals(m.getRole())) {
156 return;
157 }
158 }
159 errors.add(TestError.builder(this, Severity.WARNING, MISSING_OUTER_WAY)
160 .message(r.isBoundary() ? tr("No outer way for boundary") : tr("No outer way for multipolygon"))
161 .primitives(r)
162 .build());
163 }
164
165 /**
166 * Various style-related checks:<ul>
167 * <li>{@link #NO_STYLE_POLYGON}: Multipolygon relation should be tagged with area tags and not the outer way</li>
168 * <li>{@link #INNER_STYLE_MISMATCH}: With the currently used mappaint style the style for inner way equals the multipolygon style</li>
169 * <li>{@link #OUTER_STYLE_MISMATCH}: Style for outer way mismatches</li>
170 * <li>{@link #OUTER_STYLE}: Area style on outer way</li>
171 * </ul>
172 * @param r relation
173 * @param polygon multipolygon
174 */
175 private void checkStyleConsistency(Relation r, Multipolygon polygon) {
176 ElemStyles styles = MapPaintStyles.getStyles();
177 if (styles != null && !r.isBoundary()) {
178 AreaElement area = ElemStyles.getAreaElemStyle(r, false);
179 boolean areaStyle = area != null;
180 // If area style was not found for relation then use style of ways
181 if (area == null) {
182 for (Way w : polygon.getOuterWays()) {
183 area = ElemStyles.getAreaElemStyle(w, true);
184 if (area != null) {
185 break;
186 }
187 }
188 if (area == null) {
189 errors.add(TestError.builder(this, Severity.OTHER, NO_STYLE)
190 .message(tr("No area style for multipolygon"))
191 .primitives(r)
192 .build());
193 } else {
194 /* old style multipolygon - solve: copy tags from outer way to multipolygon */
195 errors.add(TestError.builder(this, Severity.ERROR, NO_STYLE_POLYGON)
196 .message(trn("Multipolygon relation should be tagged with area tags and not the outer way",
197 "Multipolygon relation should be tagged with area tags and not the outer ways",
198 polygon.getOuterWays().size()))
199 .primitives(r)
200 .build());
201 }
202 }
203
204 if (area != null) {
205 for (Way wInner : polygon.getInnerWays()) {
206 if (area.equals(ElemStyles.getAreaElemStyle(wInner, false))) {
207 errors.add(TestError.builder(this, Severity.OTHER, INNER_STYLE_MISMATCH)
208 .message(tr("With the currently used mappaint style the style for inner way equals the multipolygon style"))
209 .primitives(Arrays.asList(r, wInner))
210 .highlight(wInner)
211 .build());
212 }
213 }
214 for (Way wOuter : polygon.getOuterWays()) {
215 AreaElement areaOuter = ElemStyles.getAreaElemStyle(wOuter, false);
216 if (areaOuter != null) {
217 if (!area.equals(areaOuter)) {
218 String message = !areaStyle ? tr("Style for outer way mismatches")
219 : tr("With the currently used mappaint style(s) the style for outer way mismatches the area style");
220 errors.add(TestError.builder(this, Severity.OTHER, OUTER_STYLE_MISMATCH)
221 .message(message)
222 .primitives(Arrays.asList(r, wOuter))
223 .highlight(wOuter)
224 .build());
225 } else if (areaStyle) { /* style on outer way of multipolygon, but equal to polygon */
226 errors.add(TestError.builder(this, Severity.WARNING, OUTER_STYLE)
227 .message(tr("Area style on outer way"))
228 .primitives(Arrays.asList(r, wOuter))
229 .highlight(wOuter)
230 .build());
231 }
232 }
233 }
234 }
235 }
236 }
237
238 /**
239 * Various geometry-related checks:<ul>
240 * <li>{@link #NON_CLOSED_WAY}: Multipolygon is not closed</li>
241 * <li>{@link #INNER_WAY_OUTSIDE}: Multipolygon inner way is outside</li>
242 * <li>{@link #CROSSING_WAYS}: Intersection between multipolygon ways</li>
243 * </ul>
244 * @param r relation
245 * @param polygon multipolygon
246 */
247 private void checkGeometryAndRoles(Relation r, Multipolygon polygon) {
248 int oldErrorsSize = errors.size();
249
250 List<Node> openNodes = polygon.getOpenEnds();
251 if (!openNodes.isEmpty()) {
252 errors.add(TestError.builder(this, Severity.ERROR, NON_CLOSED_WAY)
253 .message(tr("Multipolygon is not closed"))
254 .primitives(combineRelAndPrimitives(r, openNodes))
255 .highlight(openNodes)
256 .build());
257 }
258 Map<Long, RelationMember> wayMap = new HashMap<>();
259 for (int i = 0; i < r.getMembersCount(); i++) {
260 RelationMember mem = r.getMember(i);
261 if (!mem.isWay())
262 continue;
263 wayMap.put(mem.getWay().getUniqueId(), mem); // duplicate members were checked before
264 }
265 if (wayMap.isEmpty())
266 return;
267
268 Set<Node> sharedNodes = findIntersectionNodes(r);
269 List<PolyData> innerPolygons = polygon.getInnerPolygons();
270 List<PolyData> outerPolygons = polygon.getOuterPolygons();
271 List<PolyData> allPolygons = new ArrayList<>();
272 allPolygons.addAll(outerPolygons);
273 allPolygons.addAll(innerPolygons);
274 Map<PolyData, List<PolyData>> crossingPolyMap = findIntersectingWays(r, innerPolygons, outerPolygons);
275
276 if (!sharedNodes.isEmpty()) {
277 for (int i = 0; i < allPolygons.size(); i++) {
278 PolyData pd1 = allPolygons.get(i);
279 checkPolygonForSelfIntersection(r, pd1);
280 for (int j = i + 1; j < allPolygons.size(); j++) {
281 PolyData pd2 = allPolygons.get(j);
282 if (!checkProblemMap(crossingPolyMap, pd1, pd2)) {
283 checkPolygonsForSharedNodes(r, pd1, pd2, sharedNodes);
284 }
285 }
286 }
287 }
288 boolean checkRoles = true;
289 for (int i = oldErrorsSize; i < errors.size(); i++) {
290 if (errors.get(i).getSeverity() != Severity.OTHER) {
291 checkRoles = false;
292 break;
293 }
294 }
295 if (checkRoles) {
296 // we found no intersection or crossing between the polygons and they are closed
297 // now we can calculate the nesting level to verify the roles with some simple node checks
298 checkRoles(r, allPolygons, wayMap, sharedNodes);
299 }
300 }
301
302 /**
303 * Check if a polygon ring is self-intersecting when the ring was build from multiple ways.
304 * An self intersection in a single way is checked in {@link SelfIntersectingWay}.
305 * @param r the relation
306 * @param pd the ring
307 */
308 private void checkPolygonForSelfIntersection(Relation r, PolyData pd) {
309 if (pd.getWayIds().size() == 1)
310 return;
311 List<Node> wayNodes = pd.getNodes();
312 int num = wayNodes.size();
313 Set<Node> nodes = new HashSet<>();
314 Node firstNode = wayNodes.get(0);
315 nodes.add(firstNode);
316 List<Node> isNodes = new ArrayList<>();
317 for (int i = 1; i < num - 1; i++) {
318 Node n = wayNodes.get(i);
319 if (nodes.contains(n)) {
320 isNodes.add(n);
321 } else {
322 nodes.add(n);
323 }
324 }
325 if (!isNodes.isEmpty()) {
326 List<OsmPrimitive> prims = new ArrayList<>();
327 prims.add(r);
328 prims.addAll(isNodes);
329 errors.add(TestError.builder(this, Severity.WARNING, CROSSING_WAYS)
330 .message(tr("Self-intersecting polygon ring"))
331 .primitives(prims)
332 .highlight(isNodes)
333 .build());
334
335 }
336 }
337
338 /**
339 * Detect intersections of multipolygon ways at nodes. If any way node is used by more than two ways
340 * or two times in one way and at least once in another way we found an intersection.
341 * @param r the relation
342 * @return List of nodes were ways intersect
343 */
344 private static Set<Node> findIntersectionNodes(Relation r) {
345 Set<Node> intersectionNodes = new HashSet<>();
346 Map<Node, List<Way>> nodeMap = new HashMap<>();
347 for (RelationMember rm : r.getMembers()) {
348 if (!rm.isWay())
349 continue;
350 int numNodes = rm.getWay().getNodesCount();
351 for (int i = 0; i < numNodes; i++) {
352 Node n = rm.getWay().getNode(i);
353 if (n.getReferrers().size() <= 1) {
354 continue; // cannot be a problem node
355 }
356 List<Way> ways = nodeMap.get(n);
357 if (ways == null) {
358 ways = new ArrayList<>();
359 nodeMap.put(n, ways);
360 }
361 ways.add(rm.getWay());
362 if (ways.size() > 2 || (ways.size() == 2 && i != 0 && i + 1 != numNodes)) {
363 intersectionNodes.add(n);
364 }
365 }
366 }
367 return intersectionNodes;
368 }
369
370 private enum ExtPolygonIntersection {
371 EQUAL,
372 FIRST_INSIDE_SECOND,
373 SECOND_INSIDE_FIRST,
374 OUTSIDE,
375 CROSSING
376 }
377
378 private void checkPolygonsForSharedNodes(Relation r, PolyData pd1, PolyData pd2, Set<Node> allSharedNodes) {
379 Set<Node> sharedByPolygons = new HashSet<>(allSharedNodes);
380 sharedByPolygons.retainAll(pd1.getNodes());
381 sharedByPolygons.retainAll(pd2.getNodes());
382 if (sharedByPolygons.isEmpty())
383 return;
384
385 // the two polygons share one or more nodes
386 // 1st might be equal to 2nd (same nodes, same or different direction) --> error shared way segments
387 // they overlap --> error
388 // 1st and 2nd share segments
389 // 1st fully inside 2nd --> okay
390 // 2nd fully inside 1st --> okay
391 int errorCode = RINGS_SHARE_NODES;
392 ExtPolygonIntersection res = checkOverlapAtSharedNodes(sharedByPolygons, pd1, pd2);
393 if (res == ExtPolygonIntersection.CROSSING) {
394 errorCode = CROSSING_WAYS;
395 } else if (res == ExtPolygonIntersection.EQUAL) {
396 errorCode = EQUAL_RINGS;
397 }
398 if (errorCode != 0) {
399 Set<OsmPrimitive> prims = new HashSet<>();
400 prims.add(r);
401 for (Node n : sharedByPolygons) {
402 for (OsmPrimitive p : n.getReferrers()) {
403 if (p instanceof Way && (pd1.getWayIds().contains(p.getUniqueId()) || pd2.getWayIds().contains(p.getUniqueId()))) {
404 prims.add(p);
405 }
406 }
407 }
408 if (errorCode == RINGS_SHARE_NODES) {
409 errors.add(TestError.builder(this, Severity.OTHER, errorCode)
410 .message(tr("Multipolygon rings share node(s)"))
411 .primitives(prims)
412 .highlight(sharedByPolygons)
413 .build());
414 } else {
415 errors.add(TestError.builder(this, Severity.WARNING, errorCode)
416 .message(errorCode == CROSSING_WAYS ? tr("Intersection between multipolygon ways") : tr("Multipolygon rings are equal"))
417 .primitives(prims)
418 .highlight(sharedByPolygons)
419 .build());
420 }
421 }
422 }
423
424 private static ExtPolygonIntersection checkOverlapAtSharedNodes(Set<Node> shared, PolyData pd1, PolyData pd2) {
425 // Idea: if two polygons share one or more nodes they can either just touch or share segments or intersect.
426 // The insideness test is complex, so we try to reduce the number of these tests.
427 // There is no need to check all nodes, we only have to check the node following a shared node.
428
429 int[] flags = new int[2];
430 for (int loop = 0; loop < flags.length; loop++) {
431 List<Node> nodes2Test = loop == 0 ? pd1.getNodes() : pd2.getNodes();
432 int num = nodes2Test.size() - 1; // ignore closing duplicate node
433
434
435 int lenShared = 0;
436 for (int i = 0; i < num; i++) {
437 Node n = nodes2Test.get(i);
438 if (shared.contains(n)) {
439 ++lenShared;
440 } else {
441 if (i == 0 || lenShared > 0) {
442 // do we have to treat lenShared > 1 special ?
443 lenShared = 0;
444 boolean inside = checkIfNodeIsInsidePolygon(n, loop == 0 ? pd2 : pd1);
445 flags[loop] |= inside ? FOUND_INSIDE : FOUND_OUTSIDE;
446 if (flags[loop] == (FOUND_INSIDE | FOUND_OUTSIDE)) {
447 return ExtPolygonIntersection.CROSSING;
448 }
449 }
450 }
451 }
452 }
453
454 if ((flags[0] & FOUND_INSIDE) != 0)
455 return ExtPolygonIntersection.FIRST_INSIDE_SECOND;
456 if ((flags[1] & FOUND_INSIDE) != 0)
457 return ExtPolygonIntersection.SECOND_INSIDE_FIRST;
458 if ((flags[0] & FOUND_OUTSIDE) != (flags[1] & FOUND_OUTSIDE)) {
459 return (flags[0] & FOUND_OUTSIDE) != 0 ?
460 ExtPolygonIntersection.SECOND_INSIDE_FIRST : ExtPolygonIntersection.FIRST_INSIDE_SECOND;
461 }
462 if ((flags[0] & FOUND_OUTSIDE) != 0 && (flags[1] & FOUND_OUTSIDE) != 0) {
463 // the two polygons may only share one or more segments but they may also intersect
464 Area a1 = new Area(pd1.get());
465 Area a2 = new Area(pd2.get());
466 PolygonIntersection areaRes = Geometry.polygonIntersection(a1, a2, 1e-6);
467 if (areaRes == PolygonIntersection.OUTSIDE)
468 return ExtPolygonIntersection.OUTSIDE;
469 return ExtPolygonIntersection.CROSSING;
470 }
471 return ExtPolygonIntersection.EQUAL;
472 }
473
474 /**
475 * Helper class for calculation of nesting levels
476 */
477 private static class PolygonLevel {
478 final int level; // nesting level, even for outer, odd for inner polygons.
479 final PolyData outerWay;
480
481 PolygonLevel(PolyData pd, int level) {
482 this.outerWay = pd;
483 this.level = level;
484 }
485 }
486
487 /**
488 * Calculate the nesting levels of the polygon rings and check if calculated role matches
489 * @param r relation (for error reporting)
490 * @param allPolygons list of polygon rings
491 * @param wayMap maps way ids to relation members
492 * @param sharedNodes all nodes shared by multiple ways of this multipolygon
493 */
494 private void checkRoles(Relation r, List<PolyData> allPolygons, Map<Long, RelationMember> wayMap, Set<Node> sharedNodes) {
495 PolygonLevelFinder levelFinder = new PolygonLevelFinder(sharedNodes);
496 List<PolygonLevel> list = levelFinder.findOuterWays(allPolygons);
497 if (list == null || list.isEmpty()) {
498 return;
499 }
500
501 for (PolygonLevel pol : list) {
502 String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner";
503 for (long wayId : pol.outerWay.getWayIds()) {
504 RelationMember member = wayMap.get(wayId);
505 if (!member.getRole().equals(calculatedRole)) {
506 errors.add(TestError.builder(this, Severity.ERROR, WRONG_MEMBER_ROLE)
507 .message(RelationChecker.ROLE_VERIF_PROBLEM_MSG,
508 marktr("Role for ''{0}'' should be ''{1}''"),
509 member.getMember().getDisplayName(DefaultNameFormatter.getInstance()),
510 calculatedRole)
511 .primitives(Arrays.asList(r, member.getMember()))
512 .highlight(member.getMember())
513 .build());
514 if (pol.level == 0 && "inner".equals(member.getRole())) {
515 // maybe only add this error if we found an outer ring with correct role(s) ?
516 errors.add(TestError.builder(this, Severity.ERROR, INNER_WAY_OUTSIDE)
517 .message(tr("Multipolygon inner way is outside"))
518 .primitives(Arrays.asList(r, member.getMember()))
519 .highlight(member.getMember())
520 .build());
521 }
522 }
523 }
524 }
525 }
526
527 /**
528 * Check if a node is inside the polygon according to the insideness rules of Shape.
529 * @param n the node
530 * @param p the polygon
531 * @return true if the node is inside the polygon
532 */
533 private static boolean checkIfNodeIsInsidePolygon(Node n, PolyData p) {
534 EastNorth en = n.getEastNorth();
535 return en != null && p.get().contains(en.getX(), en.getY());
536 }
537
538 /**
539 * Determine multipolygon ways which are intersecting (crossing without a common node) or sharing one or more way segments.
540 * See also {@link CrossingWays}
541 * @param r the relation (for error reporting)
542 * @param innerPolygons list of inner polygons
543 * @param outerPolygons list of outer polygons
544 * @return map with crossing polygons
545 */
546 private Map<PolyData, List<PolyData>> findIntersectingWays(Relation r, List<PolyData> innerPolygons,
547 List<PolyData> outerPolygons) {
548 HashMap<PolyData, List<PolyData>> crossingPolygonsMap = new HashMap<>();
549 HashMap<PolyData, List<PolyData>> sharedWaySegmentsPolygonsMap = new HashMap<>();
550
551 for (int loop = 0; loop < 2; loop++) {
552 /** All way segments, grouped by cells */
553 final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
554 /** The already detected ways in error */
555 final Map<List<Way>, List<WaySegment>> problemWays = new HashMap<>(50);
556
557 Map<PolyData, List<PolyData>> problemPolygonMap = (loop == 0) ? crossingPolygonsMap
558 : sharedWaySegmentsPolygonsMap;
559
560 for (Way w : r.getMemberPrimitives(Way.class)) {
561 findIntersectingWay(w, cellSegments, problemWays, loop == 1);
562 }
563
564 if (!problemWays.isEmpty()) {
565 List<PolyData> allPolygons = new ArrayList<>(innerPolygons.size() + outerPolygons.size());
566 allPolygons.addAll(innerPolygons);
567 allPolygons.addAll(outerPolygons);
568
569 for (Entry<List<Way>, List<WaySegment>> entry : problemWays.entrySet()) {
570 List<Way> ways = entry.getKey();
571 if (ways.size() != 2)
572 continue;
573 PolyData[] crossingPolys = new PolyData[2];
574 boolean allInner = true;
575 for (int i = 0; i < 2; i++) {
576 Way w = ways.get(i);
577 for (int j = 0; j < allPolygons.size(); j++) {
578 PolyData pd = allPolygons.get(j);
579 if (pd.getWayIds().contains(w.getUniqueId())) {
580 crossingPolys[i] = pd;
581 if (j >= innerPolygons.size())
582 allInner = false;
583 break;
584 }
585 }
586 }
587 boolean samePoly = false;
588 if (crossingPolys[0] != null && crossingPolys[1] != null) {
589 List<PolyData> crossingPolygons = problemPolygonMap.get(crossingPolys[0]);
590 if (crossingPolygons == null) {
591 crossingPolygons = new ArrayList<>();
592 problemPolygonMap.put(crossingPolys[0], crossingPolygons);
593 }
594 crossingPolygons.add(crossingPolys[1]);
595 if (crossingPolys[0] == crossingPolys[1]) {
596 samePoly = true;
597 }
598 }
599 if (loop == 0 || samePoly || (loop == 1 && !allInner)) {
600 String msg = loop == 0 ? tr("Intersection between multipolygon ways")
601 : samePoly ? tr("Multipolygon ring contains segments twice")
602 : tr("Multipolygon outer way shares segment(s) with other ring");
603 errors.add(TestError.builder(this, Severity.ERROR, CROSSING_WAYS)
604 .message(msg)
605 .primitives(Arrays.asList(r, ways.get(0), ways.get(1)))
606 .highlightWaySegments(entry.getValue())
607 .build());
608 }
609 }
610 }
611 }
612 return crossingPolygonsMap;
613 }
614
615 /**
616 * Find ways which are crossing without sharing a node.
617 * @param w way that is member of the relation
618 * @param cellSegments map with already collected way segments
619 * @param crossingWays list to collect crossing ways
620 * @param findSharedWaySegments true: find shared way segments instead of crossings
621 */
622 private static void findIntersectingWay(Way w, Map<Point2D, List<WaySegment>> cellSegments,
623 Map<List<Way>, List<WaySegment>> crossingWays, boolean findSharedWaySegments) {
624 int nodesSize = w.getNodesCount();
625 for (int i = 0; i < nodesSize - 1; i++) {
626 final WaySegment es1 = new WaySegment(w, i);
627 final EastNorth en1 = es1.getFirstNode().getEastNorth();
628 final EastNorth en2 = es1.getSecondNode().getEastNorth();
629 if (en1 == null || en2 == null) {
630 Logging.warn("Crossing ways test (MP) skipped " + es1);
631 continue;
632 }
633 for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) {
634 for (WaySegment es2 : segments) {
635
636 List<WaySegment> highlight;
637 if (es2.way == w)
638 continue; // reported by CrossingWays.SelfIntersection
639 if (findSharedWaySegments && !es1.isSimilar(es2))
640 continue;
641 if (!findSharedWaySegments && !es1.intersects(es2))
642 continue;
643
644 List<Way> prims = Arrays.asList(es1.way, es2.way);
645 if ((highlight = crossingWays.get(prims)) == null) {
646 highlight = new ArrayList<>();
647 highlight.add(es1);
648 highlight.add(es2);
649 crossingWays.put(prims, highlight);
650 } else {
651 highlight.add(es1);
652 highlight.add(es2);
653 }
654 }
655 segments.add(es1);
656 }
657 }
658 }
659
660 /**
661 * Check if map contains combination of two given polygons.
662 * @param problemPolyMap the map
663 * @param pd1 1st polygon
664 * @param pd2 2nd polygon
665 * @return true if the combination of polygons is found in the map
666 */
667 private static boolean checkProblemMap(Map<PolyData, List<PolyData>> problemPolyMap, PolyData pd1, PolyData pd2) {
668 List<PolyData> crossingWithFirst = problemPolyMap.get(pd1);
669 if (crossingWithFirst != null && crossingWithFirst.contains(pd2)) {
670 return true;
671 }
672 List<PolyData> crossingWith2nd = problemPolyMap.get(pd2);
673 return crossingWith2nd != null && crossingWith2nd.contains(pd1);
674 }
675
676 /**
677 * Check for:<ul>
678 * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li>
679 * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li>
680 * </ul>
681 * @param r relation
682 */
683 private void checkMembersAndRoles(Relation r) {
684 for (RelationMember rm : r.getMembers()) {
685 if (rm.isWay()) {
686 if (!(rm.hasRole("inner", "outer") || !rm.hasRole())) {
687 errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE)
688 .message(tr("No useful role for multipolygon member"))
689 .primitives(Arrays.asList(r, rm.getMember()))
690 .build());
691 }
692 } else {
693 if (!r.isBoundary() || !rm.hasRole("admin_centre", "label", "subarea", "land_area")) {
694 errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE)
695 .message(r.isBoundary() ? tr("Non-Way in boundary") : tr("Non-Way in multipolygon"))
696 .primitives(Arrays.asList(r, rm.getMember()))
697 .build());
698 }
699 }
700 }
701 }
702
703 private static Collection<? extends OsmPrimitive> combineRelAndPrimitives(Relation r, Collection<? extends OsmPrimitive> primitives) {
704 // add multipolygon in order to let user select something and fix the error
705 if (!primitives.contains(r)) {
706 List<OsmPrimitive> newPrimitives = new ArrayList<>(primitives);
707 newPrimitives.add(0, r);
708 return newPrimitives;
709 } else {
710 return primitives;
711 }
712 }
713
714 /**
715 * Check for:<ul>
716 * <li>{@link #REPEATED_MEMBER_DIFF_ROLE}: Multipolygon member(s) repeated with different role</li>
717 * <li>{@link #REPEATED_MEMBER_SAME_ROLE}: Multipolygon member(s) repeated with same role</li>
718 * </ul>
719 * @param r relation
720 * @return true if repeated members have been detected, false otherwise
721 */
722 private boolean checkRepeatedWayMembers(Relation r) {
723 boolean hasDups = false;
724 Map<OsmPrimitive, List<RelationMember>> seenMemberPrimitives = new HashMap<>();
725 for (RelationMember rm : r.getMembers()) {
726 List<RelationMember> list = seenMemberPrimitives.get(rm.getMember());
727 if (list == null) {
728 list = new ArrayList<>(2);
729 seenMemberPrimitives.put(rm.getMember(), list);
730 } else {
731 hasDups = true;
732 }
733 list.add(rm);
734 }
735 if (hasDups) {
736 List<OsmPrimitive> repeatedSameRole = new ArrayList<>();
737 List<OsmPrimitive> repeatedDiffRole = new ArrayList<>();
738 for (Entry<OsmPrimitive, List<RelationMember>> e : seenMemberPrimitives.entrySet()) {
739 List<RelationMember> visited = e.getValue();
740 if (e.getValue().size() == 1)
741 continue;
742 // we found a duplicate member, check if the roles differ
743 boolean rolesDiffer = false;
744 RelationMember rm = visited.get(0);
745 List<OsmPrimitive> primitives = new ArrayList<>();
746 for (int i = 1; i < visited.size(); i++) {
747 RelationMember v = visited.get(i);
748 primitives.add(rm.getMember());
749 if (!v.getRole().equals(rm.getRole())) {
750 rolesDiffer = true;
751 }
752 }
753 if (rolesDiffer) {
754 repeatedDiffRole.addAll(primitives);
755 } else {
756 repeatedSameRole.addAll(primitives);
757 }
758 }
759 addRepeatedMemberError(r, repeatedDiffRole, REPEATED_MEMBER_DIFF_ROLE, tr("Multipolygon member(s) repeated with different role"));
760 addRepeatedMemberError(r, repeatedSameRole, REPEATED_MEMBER_SAME_ROLE, tr("Multipolygon member(s) repeated with same role"));
761 }
762 return hasDups;
763 }
764
765 private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) {
766 if (!repeatedMembers.isEmpty()) {
767 errors.add(TestError.builder(this, Severity.ERROR, errorCode)
768 .message(msg)
769 .primitives(combineRelAndPrimitives(r, repeatedMembers))
770 .highlight(repeatedMembers)
771 .build());
772 }
773 }
774
775 @Override
776 public Command fixError(TestError testError) {
777 if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) {
778 ArrayList<OsmPrimitive> primitives = new ArrayList<>(testError.getPrimitives());
779 if (primitives.size() >= 2 && primitives.get(0) instanceof Relation) {
780 Relation oldRel = (Relation) primitives.get(0);
781 Relation newRel = new Relation(oldRel);
782 List<OsmPrimitive> repeatedPrims = primitives.subList(1, primitives.size());
783 List<RelationMember> oldMembers = oldRel.getMembers();
784
785 List<RelationMember> newMembers = new ArrayList<>();
786 HashSet<OsmPrimitive> toRemove = new HashSet<>(repeatedPrims);
787 HashSet<OsmPrimitive> found = new HashSet<>(repeatedPrims.size());
788 for (RelationMember rm : oldMembers) {
789 if (toRemove.contains(rm.getMember())) {
790 if (!found.contains(rm.getMember())) {
791 found.add(rm.getMember());
792 newMembers.add(rm);
793 }
794 } else {
795 newMembers.add(rm);
796 }
797 }
798 newRel.setMembers(newMembers);
799 return new ChangeCommand(oldRel, newRel);
800 }
801 }
802 return null;
803 }
804
805 @Override
806 public boolean isFixable(TestError testError) {
807 return testError.getCode() == REPEATED_MEMBER_SAME_ROLE;
808 }
809
810 /**
811 * Find nesting levels of polygons. Logic taken from class MultipolygonBuilder, uses different structures.
812 */
813 private static class PolygonLevelFinder {
814 private final Set<Node> sharedNodes;
815
816 PolygonLevelFinder(Set<Node> sharedNodes) {
817 this.sharedNodes = sharedNodes;
818 }
819
820 List<PolygonLevel> findOuterWays(List<PolyData> allPolygons) {
821 return findOuterWaysRecursive(0, allPolygons);
822 }
823
824 private List<PolygonLevel> findOuterWaysRecursive(int level, List<PolyData> polygons) {
825 final List<PolygonLevel> result = new ArrayList<>();
826
827 for (PolyData pd : polygons) {
828 if (processOuterWay(level, polygons, result, pd) == null) {
829 return null;
830 }
831 }
832
833 return result;
834 }
835
836 private Object processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) {
837 List<PolyData> inners = findInnerWaysCandidates(pd, polygons);
838
839 if (inners != null) {
840 //add new outer polygon
841 PolygonLevel pol = new PolygonLevel(pd, level);
842
843 //process inner ways
844 if (!inners.isEmpty()) {
845 List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, inners);
846 result.addAll(innerList);
847 }
848
849 result.add(pol);
850 }
851 return result;
852 }
853
854 /**
855 * Check if polygon is an out-most ring, if so, collect the inners
856 * @param outerCandidate polygon which is checked
857 * @param polygons all polygons
858 * @return null if outerCandidate is inside any other polygon, else a list of inner polygons (which might be empty)
859 */
860 private List<PolyData> findInnerWaysCandidates(PolyData outerCandidate, List<PolyData> polygons) {
861 List<PolyData> innerCandidates = new ArrayList<>();
862
863 for (PolyData inner : polygons) {
864 if (inner == outerCandidate) {
865 continue;
866 }
867 if (!outerCandidate.getBounds().intersects(inner.getBounds())) {
868 continue;
869 }
870 boolean useIntersectionTest = false;
871 Node unsharedOuterNode = null;
872 Node unsharedInnerNode = getNonIntersectingNode(outerCandidate, inner);
873 if (unsharedInnerNode != null) {
874 if (checkIfNodeIsInsidePolygon(unsharedInnerNode, outerCandidate)) {
875 innerCandidates.add(inner);
876 } else {
877 // inner is not inside outerCandidate, check if it contains outerCandidate
878 unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
879 if (unsharedOuterNode != null) {
880 if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
881 return null; // outer is inside inner
882 }
883 } else {
884 useIntersectionTest = true;
885 }
886 }
887 } else {
888 // all nodes of inner are also nodes of outerCandidate
889 unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
890 if (unsharedOuterNode == null) {
891 return null; // all nodes shared -> same ways, maybe different direction
892 } else {
893 if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
894 return null; // outer is inside inner
895 } else {
896 useIntersectionTest = true;
897 }
898 }
899 }
900 if (useIntersectionTest) {
901 PolygonIntersection res = Geometry.polygonIntersection(inner.getNodes(), outerCandidate.getNodes());
902 if (res == PolygonIntersection.FIRST_INSIDE_SECOND)
903 innerCandidates.add(inner);
904 else if (res == PolygonIntersection.SECOND_INSIDE_FIRST)
905 return null;
906 }
907 }
908 return innerCandidates;
909 }
910
911 /**
912 * Find node of pd2 which is not an intersection node with pd1.
913 * @param pd1 1st polygon
914 * @param pd2 2nd polygon
915 * @return node of pd2 which is not an intersection node with pd1 or null if none is found
916 */
917 private Node getNonIntersectingNode(PolyData pd1, PolyData pd2) {
918 for (Node n : pd2.getNodes()) {
919 if (!sharedNodes.contains(n) || !pd1.getNodes().contains(n))
920 return n;
921 }
922 return null;
923 }
924 }
925}
Note: See TracBrowser for help on using the repository browser.