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

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

fix #19136: Validator no longer raises issues for old-style multipolygons

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