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

Last change on this file was 19001, checked in by GerdP, 4 months ago

fix #23517: "Tools->Create multipolygon" sorts inner before outer

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