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

Last change on this file since 12700 was 12700, checked in by bastiK, 8 years ago

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