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

Last change on this file since 14408 was 14408, checked in by GerdP, 5 years ago

fix #16942 - improve performance of MultipolygonTest
  • Property svn:eol-style set to native
File size: 41.5 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 = new HashSet<>();
269 Set<Way> intersectionWays = new HashSet<>();
270 findIntersectionNodes(r, sharedNodes, intersectionWays);
271
272 List<PolyData> innerPolygons = polygon.getInnerPolygons();
273 List<PolyData> outerPolygons = polygon.getOuterPolygons();
274 List<PolyData> allPolygons = new ArrayList<>();
275 allPolygons.addAll(outerPolygons);
276 allPolygons.addAll(innerPolygons);
277
278 Map<PolyData, List<PolyData>> crossingPolyMap = findIntersectingWays(r, innerPolygons, outerPolygons);
279
280 if (!sharedNodes.isEmpty()) {
281 for (int i = 0; i < allPolygons.size(); i++) {
282 PolyData pd1 = allPolygons.get(i);
283 checkPolygonForSelfIntersection(r, pd1);
284 // check if this ring has a way that is known to intersect with another way
285
286 if (!hasIntersectionWay(pd1, intersectionWays))
287 continue;
288
289 for (int j = i + 1; j < allPolygons.size(); j++) {
290 PolyData pd2 = allPolygons.get(j);
291 if (!checkProblemMap(crossingPolyMap, pd1, pd2)) {
292 if (hasIntersectionWay(pd2, intersectionWays))
293 checkPolygonsForSharedNodes(r, pd1, pd2, sharedNodes);
294 }
295 }
296 }
297 }
298 boolean checkRoles = true;
299 for (int i = oldErrorsSize; i < errors.size(); i++) {
300 if (errors.get(i).getSeverity() != Severity.OTHER) {
301 checkRoles = false;
302 break;
303 }
304 }
305 if (checkRoles) {
306 // we found no intersection or crossing between the polygons and they are closed
307 // now we can calculate the nesting level to verify the roles with some simple node checks
308 checkRoles(r, allPolygons, wayMap, sharedNodes);
309 }
310 }
311
312 /**
313 * Simple check if given ring contains way that is known to intersect.
314 * @param pd the ring
315 * @param intersectionWays the known intersection ways
316 * @return true if one or more ways are in the set of known ways
317 */
318 private boolean hasIntersectionWay(PolyData pd, Set<Way> intersectionWays) {
319 for (Way w : intersectionWays) {
320 if (pd.getWayIds().contains(w.getUniqueId())) {
321 return true;
322 }
323 }
324 return false;
325 }
326
327 /**
328 * Check if a polygon ring is self-intersecting when the ring was build from multiple ways.
329 * An self intersection in a single way is checked in {@link SelfIntersectingWay}.
330 * @param r the relation
331 * @param pd the ring
332 */
333 private void checkPolygonForSelfIntersection(Relation r, PolyData pd) {
334 if (pd.getWayIds().size() == 1)
335 return;
336 List<Node> wayNodes = pd.getNodes();
337 int num = wayNodes.size();
338 Set<Node> nodes = new HashSet<>();
339 Node firstNode = wayNodes.get(0);
340 nodes.add(firstNode);
341 List<Node> isNodes = new ArrayList<>();
342 for (int i = 1; i < num - 1; i++) {
343 Node n = wayNodes.get(i);
344 if (nodes.contains(n)) {
345 isNodes.add(n);
346 } else {
347 nodes.add(n);
348 }
349 }
350 if (!isNodes.isEmpty()) {
351 List<OsmPrimitive> prims = new ArrayList<>();
352 prims.add(r);
353 prims.addAll(isNodes);
354 errors.add(TestError.builder(this, Severity.WARNING, CROSSING_WAYS)
355 .message(tr("Self-intersecting polygon ring"))
356 .primitives(prims)
357 .highlight(isNodes)
358 .build());
359
360 }
361 }
362
363 /**
364 * Detect intersections of multipolygon ways at nodes. If any way node is used by more than two ways
365 * or two times in one way and at least once in another way we found an intersection.
366 * @param r the relation
367 * @param sharedNodes We be filled with shared nodes
368 * @param intersectionWays We be filled with ways that have a shared node
369 */
370 private static void findIntersectionNodes(Relation r, Set<Node> sharedNodes, Set<Way> intersectionWays) {
371 Map<Node, List<Way>> nodeMap = new HashMap<>();
372 for (RelationMember rm : r.getMembers()) {
373 if (!rm.isWay())
374 continue;
375 int numNodes = rm.getWay().getNodesCount();
376 for (int i = 0; i < numNodes; i++) {
377 Node n = rm.getWay().getNode(i);
378 if (n.getReferrers().size() <= 1) {
379 continue; // cannot be a problem node
380 }
381 List<Way> ways = nodeMap.get(n);
382 if (ways == null) {
383 ways = new ArrayList<>();
384 nodeMap.put(n, ways);
385 }
386 ways.add(rm.getWay());
387 if (ways.size() > 2 || (ways.size() == 2 && i != 0 && i + 1 != numNodes)) {
388 sharedNodes.add(n);
389 intersectionWays.addAll(ways);
390 }
391 }
392 }
393 }
394
395 private enum ExtPolygonIntersection {
396 EQUAL,
397 FIRST_INSIDE_SECOND,
398 SECOND_INSIDE_FIRST,
399 OUTSIDE,
400 CROSSING
401 }
402
403 private void checkPolygonsForSharedNodes(Relation r, PolyData pd1, PolyData pd2, Set<Node> allSharedNodes) {
404 Set<Node> sharedByPolygons = new HashSet<>(allSharedNodes);
405 sharedByPolygons.retainAll(pd1.getNodes());
406 sharedByPolygons.retainAll(pd2.getNodes());
407 if (sharedByPolygons.isEmpty())
408 return;
409
410 // the two polygons share one or more nodes
411 // 1st might be equal to 2nd (same nodes, same or different direction) --> error shared way segments
412 // they overlap --> error
413 // 1st and 2nd share segments
414 // 1st fully inside 2nd --> okay
415 // 2nd fully inside 1st --> okay
416 int errorCode = RINGS_SHARE_NODES;
417 ExtPolygonIntersection res = checkOverlapAtSharedNodes(sharedByPolygons, pd1, pd2);
418 if (res == ExtPolygonIntersection.CROSSING) {
419 errorCode = CROSSING_WAYS;
420 } else if (res == ExtPolygonIntersection.EQUAL) {
421 errorCode = EQUAL_RINGS;
422 }
423 if (errorCode != 0) {
424 Set<OsmPrimitive> prims = new HashSet<>();
425 prims.add(r);
426 for (Node n : sharedByPolygons) {
427 for (OsmPrimitive p : n.getReferrers()) {
428 if (p instanceof Way && (pd1.getWayIds().contains(p.getUniqueId()) || pd2.getWayIds().contains(p.getUniqueId()))) {
429 prims.add(p);
430 }
431 }
432 }
433 if (errorCode == RINGS_SHARE_NODES) {
434 errors.add(TestError.builder(this, Severity.OTHER, errorCode)
435 .message(tr("Multipolygon rings share node(s)"))
436 .primitives(prims)
437 .highlight(sharedByPolygons)
438 .build());
439 } else {
440 errors.add(TestError.builder(this, Severity.WARNING, errorCode)
441 .message(errorCode == CROSSING_WAYS ? tr("Intersection between multipolygon ways") : tr("Multipolygon rings are equal"))
442 .primitives(prims)
443 .highlight(sharedByPolygons)
444 .build());
445 }
446 }
447 }
448
449 private static ExtPolygonIntersection checkOverlapAtSharedNodes(Set<Node> shared, PolyData pd1, PolyData pd2) {
450 // Idea: if two polygons share one or more nodes they can either just touch or share segments or intersect.
451 // The insideness test is complex, so we try to reduce the number of these tests.
452 // There is no need to check all nodes, we only have to check the node following a shared node.
453
454 int[] flags = new int[2];
455 for (int loop = 0; loop < flags.length; loop++) {
456 List<Node> nodes2Test = loop == 0 ? pd1.getNodes() : pd2.getNodes();
457 int num = nodes2Test.size() - 1; // ignore closing duplicate node
458
459
460 int lenShared = 0;
461 for (int i = 0; i < num; i++) {
462 Node n = nodes2Test.get(i);
463 if (shared.contains(n)) {
464 ++lenShared;
465 } else {
466 if (i == 0 || lenShared > 0) {
467 // do we have to treat lenShared > 1 special ?
468 lenShared = 0;
469 boolean inside = checkIfNodeIsInsidePolygon(n, loop == 0 ? pd2 : pd1);
470 flags[loop] |= inside ? FOUND_INSIDE : FOUND_OUTSIDE;
471 if (flags[loop] == (FOUND_INSIDE | FOUND_OUTSIDE)) {
472 return ExtPolygonIntersection.CROSSING;
473 }
474 }
475 }
476 }
477 }
478
479 if ((flags[0] & FOUND_INSIDE) != 0)
480 return ExtPolygonIntersection.FIRST_INSIDE_SECOND;
481 if ((flags[1] & FOUND_INSIDE) != 0)
482 return ExtPolygonIntersection.SECOND_INSIDE_FIRST;
483 if ((flags[0] & FOUND_OUTSIDE) != (flags[1] & FOUND_OUTSIDE)) {
484 return (flags[0] & FOUND_OUTSIDE) != 0 ?
485 ExtPolygonIntersection.SECOND_INSIDE_FIRST : ExtPolygonIntersection.FIRST_INSIDE_SECOND;
486 }
487 if ((flags[0] & FOUND_OUTSIDE) != 0 && (flags[1] & FOUND_OUTSIDE) != 0) {
488 // the two polygons may only share one or more segments but they may also intersect
489 Area a1 = new Area(pd1.get());
490 Area a2 = new Area(pd2.get());
491 PolygonIntersection areaRes = Geometry.polygonIntersection(a1, a2, 1e-6);
492 if (areaRes == PolygonIntersection.OUTSIDE)
493 return ExtPolygonIntersection.OUTSIDE;
494 return ExtPolygonIntersection.CROSSING;
495 }
496 return ExtPolygonIntersection.EQUAL;
497 }
498
499 /**
500 * Helper class for calculation of nesting levels
501 */
502 private static class PolygonLevel {
503 final int level; // nesting level, even for outer, odd for inner polygons.
504 final PolyData outerWay;
505
506 PolygonLevel(PolyData pd, int level) {
507 this.outerWay = pd;
508 this.level = level;
509 }
510 }
511
512 /**
513 * Calculate the nesting levels of the polygon rings and check if calculated role matches
514 * @param r relation (for error reporting)
515 * @param allPolygons list of polygon rings
516 * @param wayMap maps way ids to relation members
517 * @param sharedNodes all nodes shared by multiple ways of this multipolygon
518 */
519 private void checkRoles(Relation r, List<PolyData> allPolygons, Map<Long, RelationMember> wayMap, Set<Node> sharedNodes) {
520 PolygonLevelFinder levelFinder = new PolygonLevelFinder(sharedNodes);
521 List<PolygonLevel> list = levelFinder.findOuterWays(allPolygons);
522 if (list == null || list.isEmpty()) {
523 return;
524 }
525
526 for (PolygonLevel pol : list) {
527 String calculatedRole = (pol.level % 2 == 0) ? "outer" : "inner";
528 for (long wayId : pol.outerWay.getWayIds()) {
529 RelationMember member = wayMap.get(wayId);
530 if (!member.getRole().equals(calculatedRole)) {
531 errors.add(TestError.builder(this, Severity.ERROR, WRONG_MEMBER_ROLE)
532 .message(RelationChecker.ROLE_VERIF_PROBLEM_MSG,
533 marktr("Role for ''{0}'' should be ''{1}''"),
534 member.getMember().getDisplayName(DefaultNameFormatter.getInstance()),
535 calculatedRole)
536 .primitives(Arrays.asList(r, member.getMember()))
537 .highlight(member.getMember())
538 .build());
539 if (pol.level == 0 && "inner".equals(member.getRole())) {
540 // maybe only add this error if we found an outer ring with correct role(s) ?
541 errors.add(TestError.builder(this, Severity.ERROR, INNER_WAY_OUTSIDE)
542 .message(tr("Multipolygon inner way is outside"))
543 .primitives(Arrays.asList(r, member.getMember()))
544 .highlight(member.getMember())
545 .build());
546 }
547 }
548 }
549 }
550 }
551
552 /**
553 * Check if a node is inside the polygon according to the insideness rules of Shape.
554 * @param n the node
555 * @param p the polygon
556 * @return true if the node is inside the polygon
557 */
558 private static boolean checkIfNodeIsInsidePolygon(Node n, PolyData p) {
559 EastNorth en = n.getEastNorth();
560 return en != null && p.get().contains(en.getX(), en.getY());
561 }
562
563 /**
564 * Determine multipolygon ways which are intersecting (crossing without a common node) or sharing one or more way segments.
565 * See also {@link CrossingWays}
566 * @param r the relation (for error reporting)
567 * @param innerPolygons list of inner polygons
568 * @param outerPolygons list of outer polygons
569 * @return map with crossing polygons
570 */
571 private Map<PolyData, List<PolyData>> findIntersectingWays(Relation r, List<PolyData> innerPolygons,
572 List<PolyData> outerPolygons) {
573 HashMap<PolyData, List<PolyData>> crossingPolygonsMap = new HashMap<>();
574 HashMap<PolyData, List<PolyData>> sharedWaySegmentsPolygonsMap = new HashMap<>();
575
576 for (int loop = 0; loop < 2; loop++) {
577 /** All way segments, grouped by cells */
578 final Map<Point2D, List<WaySegment>> cellSegments = new HashMap<>(1000);
579 /** The already detected ways in error */
580 final Map<List<Way>, List<WaySegment>> problemWays = new HashMap<>(50);
581
582 Map<PolyData, List<PolyData>> problemPolygonMap = (loop == 0) ? crossingPolygonsMap
583 : sharedWaySegmentsPolygonsMap;
584
585 for (Way w : r.getMemberPrimitives(Way.class)) {
586 findIntersectingWay(w, cellSegments, problemWays, loop == 1);
587 }
588
589 if (!problemWays.isEmpty()) {
590 List<PolyData> allPolygons = new ArrayList<>(innerPolygons.size() + outerPolygons.size());
591 allPolygons.addAll(innerPolygons);
592 allPolygons.addAll(outerPolygons);
593
594 for (Entry<List<Way>, List<WaySegment>> entry : problemWays.entrySet()) {
595 List<Way> ways = entry.getKey();
596 if (ways.size() != 2)
597 continue;
598 PolyData[] crossingPolys = new PolyData[2];
599 boolean allInner = true;
600 for (int i = 0; i < 2; i++) {
601 Way w = ways.get(i);
602 for (int j = 0; j < allPolygons.size(); j++) {
603 PolyData pd = allPolygons.get(j);
604 if (pd.getWayIds().contains(w.getUniqueId())) {
605 crossingPolys[i] = pd;
606 if (j >= innerPolygons.size())
607 allInner = false;
608 break;
609 }
610 }
611 }
612 boolean samePoly = false;
613 if (crossingPolys[0] != null && crossingPolys[1] != null) {
614 List<PolyData> crossingPolygons = problemPolygonMap.get(crossingPolys[0]);
615 if (crossingPolygons == null) {
616 crossingPolygons = new ArrayList<>();
617 problemPolygonMap.put(crossingPolys[0], crossingPolygons);
618 }
619 crossingPolygons.add(crossingPolys[1]);
620 if (crossingPolys[0] == crossingPolys[1]) {
621 samePoly = true;
622 }
623 }
624 if (loop == 0 || samePoly || (loop == 1 && !allInner)) {
625 String msg = loop == 0 ? tr("Intersection between multipolygon ways")
626 : samePoly ? tr("Multipolygon ring contains segments twice")
627 : tr("Multipolygon outer way shares segment(s) with other ring");
628 errors.add(TestError.builder(this, Severity.ERROR, CROSSING_WAYS)
629 .message(msg)
630 .primitives(Arrays.asList(r, ways.get(0), ways.get(1)))
631 .highlightWaySegments(entry.getValue())
632 .build());
633 }
634 }
635 }
636 }
637 return crossingPolygonsMap;
638 }
639
640 /**
641 * Find ways which are crossing without sharing a node.
642 * @param w way that is member of the relation
643 * @param cellSegments map with already collected way segments
644 * @param crossingWays list to collect crossing ways
645 * @param findSharedWaySegments true: find shared way segments instead of crossings
646 */
647 private static void findIntersectingWay(Way w, Map<Point2D, List<WaySegment>> cellSegments,
648 Map<List<Way>, List<WaySegment>> crossingWays, boolean findSharedWaySegments) {
649 int nodesSize = w.getNodesCount();
650 for (int i = 0; i < nodesSize - 1; i++) {
651 final WaySegment es1 = new WaySegment(w, i);
652 final EastNorth en1 = es1.getFirstNode().getEastNorth();
653 final EastNorth en2 = es1.getSecondNode().getEastNorth();
654 if (en1 == null || en2 == null) {
655 Logging.warn("Crossing ways test (MP) skipped " + es1);
656 continue;
657 }
658 for (List<WaySegment> segments : CrossingWays.getSegments(cellSegments, en1, en2)) {
659 for (WaySegment es2 : segments) {
660
661 List<WaySegment> highlight;
662 if (es2.way == w)
663 continue; // reported by CrossingWays.SelfIntersection
664 if (findSharedWaySegments && !es1.isSimilar(es2))
665 continue;
666 if (!findSharedWaySegments && !es1.intersects(es2))
667 continue;
668
669 List<Way> prims = Arrays.asList(es1.way, es2.way);
670 if ((highlight = crossingWays.get(prims)) == null) {
671 highlight = new ArrayList<>();
672 highlight.add(es1);
673 highlight.add(es2);
674 crossingWays.put(prims, highlight);
675 } else {
676 highlight.add(es1);
677 highlight.add(es2);
678 }
679 }
680 segments.add(es1);
681 }
682 }
683 }
684
685 /**
686 * Check if map contains combination of two given polygons.
687 * @param problemPolyMap the map
688 * @param pd1 1st polygon
689 * @param pd2 2nd polygon
690 * @return true if the combination of polygons is found in the map
691 */
692 private static boolean checkProblemMap(Map<PolyData, List<PolyData>> problemPolyMap, PolyData pd1, PolyData pd2) {
693 List<PolyData> crossingWithFirst = problemPolyMap.get(pd1);
694 if (crossingWithFirst != null && crossingWithFirst.contains(pd2)) {
695 return true;
696 }
697 List<PolyData> crossingWith2nd = problemPolyMap.get(pd2);
698 return crossingWith2nd != null && crossingWith2nd.contains(pd1);
699 }
700
701 /**
702 * Check for:<ul>
703 * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li>
704 * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li>
705 * </ul>
706 * @param r relation
707 */
708 private void checkMembersAndRoles(Relation r) {
709 for (RelationMember rm : r.getMembers()) {
710 if (rm.isWay()) {
711 if (!(rm.hasRole("inner", "outer") || !rm.hasRole())) {
712 errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE)
713 .message(tr("No useful role for multipolygon member"))
714 .primitives(Arrays.asList(r, rm.getMember()))
715 .build());
716 }
717 } else {
718 if (!r.isBoundary() || !rm.hasRole("admin_centre", "label", "subarea", "land_area")) {
719 errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE)
720 .message(r.isBoundary() ? tr("Non-Way in boundary") : tr("Non-Way in multipolygon"))
721 .primitives(Arrays.asList(r, rm.getMember()))
722 .build());
723 }
724 }
725 }
726 }
727
728 private static Collection<? extends OsmPrimitive> combineRelAndPrimitives(Relation r, Collection<? extends OsmPrimitive> primitives) {
729 // add multipolygon in order to let user select something and fix the error
730 if (!primitives.contains(r)) {
731 List<OsmPrimitive> newPrimitives = new ArrayList<>(primitives);
732 newPrimitives.add(0, r);
733 return newPrimitives;
734 } else {
735 return primitives;
736 }
737 }
738
739 /**
740 * Check for:<ul>
741 * <li>{@link #REPEATED_MEMBER_DIFF_ROLE}: Multipolygon member(s) repeated with different role</li>
742 * <li>{@link #REPEATED_MEMBER_SAME_ROLE}: Multipolygon member(s) repeated with same role</li>
743 * </ul>
744 * @param r relation
745 * @return true if repeated members have been detected, false otherwise
746 */
747 private boolean checkRepeatedWayMembers(Relation r) {
748 boolean hasDups = false;
749 Map<OsmPrimitive, List<RelationMember>> seenMemberPrimitives = new HashMap<>();
750 for (RelationMember rm : r.getMembers()) {
751 List<RelationMember> list = seenMemberPrimitives.get(rm.getMember());
752 if (list == null) {
753 list = new ArrayList<>(2);
754 seenMemberPrimitives.put(rm.getMember(), list);
755 } else {
756 hasDups = true;
757 }
758 list.add(rm);
759 }
760 if (hasDups) {
761 List<OsmPrimitive> repeatedSameRole = new ArrayList<>();
762 List<OsmPrimitive> repeatedDiffRole = new ArrayList<>();
763 for (Entry<OsmPrimitive, List<RelationMember>> e : seenMemberPrimitives.entrySet()) {
764 List<RelationMember> visited = e.getValue();
765 if (e.getValue().size() == 1)
766 continue;
767 // we found a duplicate member, check if the roles differ
768 boolean rolesDiffer = false;
769 RelationMember rm = visited.get(0);
770 List<OsmPrimitive> primitives = new ArrayList<>();
771 for (int i = 1; i < visited.size(); i++) {
772 RelationMember v = visited.get(i);
773 primitives.add(rm.getMember());
774 if (!v.getRole().equals(rm.getRole())) {
775 rolesDiffer = true;
776 }
777 }
778 if (rolesDiffer) {
779 repeatedDiffRole.addAll(primitives);
780 } else {
781 repeatedSameRole.addAll(primitives);
782 }
783 }
784 addRepeatedMemberError(r, repeatedDiffRole, REPEATED_MEMBER_DIFF_ROLE, tr("Multipolygon member(s) repeated with different role"));
785 addRepeatedMemberError(r, repeatedSameRole, REPEATED_MEMBER_SAME_ROLE, tr("Multipolygon member(s) repeated with same role"));
786 }
787 return hasDups;
788 }
789
790 private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) {
791 if (!repeatedMembers.isEmpty()) {
792 errors.add(TestError.builder(this, Severity.ERROR, errorCode)
793 .message(msg)
794 .primitives(combineRelAndPrimitives(r, repeatedMembers))
795 .highlight(repeatedMembers)
796 .build());
797 }
798 }
799
800 @Override
801 public Command fixError(TestError testError) {
802 if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) {
803 ArrayList<OsmPrimitive> primitives = new ArrayList<>(testError.getPrimitives());
804 if (primitives.size() >= 2 && primitives.get(0) instanceof Relation) {
805 Relation oldRel = (Relation) primitives.get(0);
806 Relation newRel = new Relation(oldRel);
807 List<OsmPrimitive> repeatedPrims = primitives.subList(1, primitives.size());
808 List<RelationMember> oldMembers = oldRel.getMembers();
809
810 List<RelationMember> newMembers = new ArrayList<>();
811 HashSet<OsmPrimitive> toRemove = new HashSet<>(repeatedPrims);
812 HashSet<OsmPrimitive> found = new HashSet<>(repeatedPrims.size());
813 for (RelationMember rm : oldMembers) {
814 if (toRemove.contains(rm.getMember())) {
815 if (!found.contains(rm.getMember())) {
816 found.add(rm.getMember());
817 newMembers.add(rm);
818 }
819 } else {
820 newMembers.add(rm);
821 }
822 }
823 newRel.setMembers(newMembers);
824 return new ChangeCommand(oldRel, newRel);
825 }
826 }
827 return null;
828 }
829
830 @Override
831 public boolean isFixable(TestError testError) {
832 return testError.getCode() == REPEATED_MEMBER_SAME_ROLE;
833 }
834
835 /**
836 * Find nesting levels of polygons. Logic taken from class MultipolygonBuilder, uses different structures.
837 */
838 private static class PolygonLevelFinder {
839 private final Set<Node> sharedNodes;
840
841 PolygonLevelFinder(Set<Node> sharedNodes) {
842 this.sharedNodes = sharedNodes;
843 }
844
845 List<PolygonLevel> findOuterWays(List<PolyData> allPolygons) {
846 return findOuterWaysRecursive(0, allPolygons);
847 }
848
849 private List<PolygonLevel> findOuterWaysRecursive(int level, List<PolyData> polygons) {
850 final List<PolygonLevel> result = new ArrayList<>();
851
852 for (PolyData pd : polygons) {
853 if (processOuterWay(level, polygons, result, pd) == null) {
854 return null;
855 }
856 }
857
858 return result;
859 }
860
861 private Object processOuterWay(int level, List<PolyData> polygons, List<PolygonLevel> result, PolyData pd) {
862 List<PolyData> inners = findInnerWaysCandidates(pd, polygons);
863
864 if (inners != null) {
865 //add new outer polygon
866 PolygonLevel pol = new PolygonLevel(pd, level);
867
868 //process inner ways
869 if (!inners.isEmpty()) {
870 List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, inners);
871 result.addAll(innerList);
872 }
873
874 result.add(pol);
875 }
876 return result;
877 }
878
879 /**
880 * Check if polygon is an out-most ring, if so, collect the inners
881 * @param outerCandidate polygon which is checked
882 * @param polygons all polygons
883 * @return null if outerCandidate is inside any other polygon, else a list of inner polygons (which might be empty)
884 */
885 private List<PolyData> findInnerWaysCandidates(PolyData outerCandidate, List<PolyData> polygons) {
886 List<PolyData> innerCandidates = new ArrayList<>();
887
888 for (PolyData inner : polygons) {
889 if (inner == outerCandidate) {
890 continue;
891 }
892 if (!outerCandidate.getBounds().intersects(inner.getBounds())) {
893 continue;
894 }
895 boolean useIntersectionTest = false;
896 Node unsharedOuterNode = null;
897 Node unsharedInnerNode = getNonIntersectingNode(outerCandidate, inner);
898 if (unsharedInnerNode != null) {
899 if (checkIfNodeIsInsidePolygon(unsharedInnerNode, outerCandidate)) {
900 innerCandidates.add(inner);
901 } else {
902 // inner is not inside outerCandidate, check if it contains outerCandidate
903 unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
904 if (unsharedOuterNode != null) {
905 if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
906 return null; // outer is inside inner
907 }
908 } else {
909 useIntersectionTest = true;
910 }
911 }
912 } else {
913 // all nodes of inner are also nodes of outerCandidate
914 unsharedOuterNode = getNonIntersectingNode(inner, outerCandidate);
915 if (unsharedOuterNode == null) {
916 return null; // all nodes shared -> same ways, maybe different direction
917 } else {
918 if (checkIfNodeIsInsidePolygon(unsharedOuterNode, inner)) {
919 return null; // outer is inside inner
920 } else {
921 useIntersectionTest = true;
922 }
923 }
924 }
925 if (useIntersectionTest) {
926 PolygonIntersection res = Geometry.polygonIntersection(inner.getNodes(), outerCandidate.getNodes());
927 if (res == PolygonIntersection.FIRST_INSIDE_SECOND)
928 innerCandidates.add(inner);
929 else if (res == PolygonIntersection.SECOND_INSIDE_FIRST)
930 return null;
931 }
932 }
933 return innerCandidates;
934 }
935
936 /**
937 * Find node of pd2 which is not an intersection node with pd1.
938 * @param pd1 1st polygon
939 * @param pd2 2nd polygon
940 * @return node of pd2 which is not an intersection node with pd1 or null if none is found
941 */
942 private Node getNonIntersectingNode(PolyData pd1, PolyData pd2) {
943 for (Node n : pd2.getNodes()) {
944 if (!sharedNodes.contains(n) || !pd1.getNodes().contains(n))
945 return n;
946 }
947 return null;
948 }
949 }
950}
Note: See TracBrowser for help on using the repository browser.