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

Last change on this file since 15244 was 15244, checked in by Don-vip, 5 years ago

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