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

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

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