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

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

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