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

Last change on this file since 16445 was 16445, checked in by simon04, 4 years ago

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