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

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

fix #13165 Validator did not warn about overlapping multipolygons

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