001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.validation.tests; 003 004import static org.openstreetmap.josm.tools.I18n.marktr; 005import static org.openstreetmap.josm.tools.I18n.tr; 006import static org.openstreetmap.josm.tools.I18n.trn; 007 008import java.awt.geom.GeneralPath; 009import java.util.ArrayList; 010import java.util.Arrays; 011import java.util.Collection; 012import java.util.Collections; 013import java.util.HashMap; 014import java.util.HashSet; 015import java.util.List; 016import java.util.Map; 017import java.util.Map.Entry; 018import java.util.Set; 019 020import org.openstreetmap.josm.actions.CreateMultipolygonAction; 021import org.openstreetmap.josm.command.ChangeCommand; 022import org.openstreetmap.josm.command.Command; 023import org.openstreetmap.josm.data.osm.Node; 024import org.openstreetmap.josm.data.osm.OsmPrimitive; 025import org.openstreetmap.josm.data.osm.Relation; 026import org.openstreetmap.josm.data.osm.RelationMember; 027import org.openstreetmap.josm.data.osm.Way; 028import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon; 029import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData; 030import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection; 031import org.openstreetmap.josm.data.validation.OsmValidator; 032import org.openstreetmap.josm.data.validation.Severity; 033import org.openstreetmap.josm.data.validation.Test; 034import org.openstreetmap.josm.data.validation.TestError; 035import org.openstreetmap.josm.gui.DefaultNameFormatter; 036import org.openstreetmap.josm.gui.mappaint.ElemStyles; 037import org.openstreetmap.josm.gui.mappaint.MapPaintStyles; 038import org.openstreetmap.josm.gui.mappaint.styleelement.AreaElement; 039import org.openstreetmap.josm.gui.progress.ProgressMonitor; 040import org.openstreetmap.josm.tools.Pair; 041 042/** 043 * Checks if multipolygons are valid 044 * @since 3669 045 */ 046public class MultipolygonTest extends Test { 047 048 /** Non-Way in multipolygon */ 049 public static final int WRONG_MEMBER_TYPE = 1601; 050 /** No useful role for multipolygon member */ 051 public static final int WRONG_MEMBER_ROLE = 1602; 052 /** Multipolygon is not closed */ 053 public static final int NON_CLOSED_WAY = 1603; 054 /** No outer way for multipolygon */ 055 public static final int MISSING_OUTER_WAY = 1604; 056 /** Multipolygon inner way is outside */ 057 public static final int INNER_WAY_OUTSIDE = 1605; 058 /** Intersection between multipolygon ways */ 059 public static final int CROSSING_WAYS = 1606; 060 /** Style for outer way mismatches / With the currently used mappaint style(s) the style for outer way mismatches the area style */ 061 public static final int OUTER_STYLE_MISMATCH = 1607; 062 /** With the currently used mappaint style the style for inner way equals the multipolygon style */ 063 public static final int INNER_STYLE_MISMATCH = 1608; 064 /** Area style way is not closed */ 065 public static final int NOT_CLOSED = 1609; 066 /** No area style for multipolygon */ 067 public static final int NO_STYLE = 1610; 068 /** Multipolygon relation should be tagged with area tags and not the outer way(s) */ 069 public static final int NO_STYLE_POLYGON = 1611; 070 /** Area style on outer way */ 071 public static final int OUTER_STYLE = 1613; 072 /** Multipolygon member repeated (same primitive, same role */ 073 public static final int REPEATED_MEMBER_SAME_ROLE = 1614; 074 /** Multipolygon member repeated (same primitive, different role) */ 075 public static final int REPEATED_MEMBER_DIFF_ROLE = 1615; 076 077 private static volatile ElemStyles styles; 078 079 private final Set<String> keysCheckedByAnotherTest = new HashSet<>(); 080 081 /** 082 * Constructs a new {@code MultipolygonTest}. 083 */ 084 public MultipolygonTest() { 085 super(tr("Multipolygon"), 086 tr("This test checks if multipolygons are valid.")); 087 } 088 089 @Override 090 public void initialize() { 091 styles = MapPaintStyles.getStyles(); 092 } 093 094 @Override 095 public void startTest(ProgressMonitor progressMonitor) { 096 super.startTest(progressMonitor); 097 keysCheckedByAnotherTest.clear(); 098 for (Test t : OsmValidator.getEnabledTests(false)) { 099 if (t instanceof UnclosedWays) { 100 keysCheckedByAnotherTest.addAll(((UnclosedWays) t).getCheckedKeys()); 101 break; 102 } 103 } 104 } 105 106 @Override 107 public void endTest() { 108 keysCheckedByAnotherTest.clear(); 109 super.endTest(); 110 } 111 112 private static GeneralPath createPath(List<Node> nodes) { 113 GeneralPath result = new GeneralPath(); 114 result.moveTo((float) nodes.get(0).getCoor().lat(), (float) nodes.get(0).getCoor().lon()); 115 for (int i = 1; i < nodes.size(); i++) { 116 Node n = nodes.get(i); 117 result.lineTo((float) n.getCoor().lat(), (float) n.getCoor().lon()); 118 } 119 return result; 120 } 121 122 private static List<GeneralPath> createPolygons(List<Multipolygon.PolyData> joinedWays) { 123 List<GeneralPath> result = new ArrayList<>(); 124 for (Multipolygon.PolyData way : joinedWays) { 125 result.add(createPath(way.getNodes())); 126 } 127 return result; 128 } 129 130 private static Intersection getPolygonIntersection(GeneralPath outer, List<Node> inner) { 131 boolean inside = false; 132 boolean outside = false; 133 134 for (Node n : inner) { 135 boolean contains = outer.contains(n.getCoor().lat(), n.getCoor().lon()); 136 inside = inside | contains; 137 outside = outside | !contains; 138 if (inside & outside) { 139 return Intersection.CROSSING; 140 } 141 } 142 143 return inside ? Intersection.INSIDE : Intersection.OUTSIDE; 144 } 145 146 @Override 147 public void visit(Way w) { 148 if (!w.isArea() && ElemStyles.hasOnlyAreaElemStyle(w)) { 149 List<Node> nodes = w.getNodes(); 150 if (nodes.isEmpty()) return; // fix zero nodes bug 151 for (String key : keysCheckedByAnotherTest) { 152 if (w.hasKey(key)) { 153 return; 154 } 155 } 156 errors.add(TestError.builder(this, Severity.WARNING, NOT_CLOSED) 157 .message(tr("Area style way is not closed")) 158 .primitives(w) 159 .highlight(Arrays.asList(nodes.get(0), nodes.get(nodes.size() - 1))) 160 .build()); 161 } 162 } 163 164 @Override 165 public void visit(Relation r) { 166 if (r.isMultipolygon()) { 167 checkMembersAndRoles(r); 168 checkOuterWay(r); 169 checkRepeatedWayMembers(r); 170 171 // Rest of checks is only for complete multipolygons 172 if (!r.hasIncompleteMembers()) { 173 Multipolygon polygon = new Multipolygon(r); 174 175 // Create new multipolygon using the logics from CreateMultipolygonAction and see if roles match. 176 checkMemberRoleCorrectness(r); 177 checkStyleConsistency(r, polygon); 178 checkGeometry(r, polygon); 179 } 180 } 181 } 182 183 /** 184 * Checks that multipolygon has at least an outer way:<ul> 185 * <li>{@link #MISSING_OUTER_WAY}: No outer way for multipolygon</li> 186 * </ul> 187 * @param r relation 188 */ 189 private void checkOuterWay(Relation r) { 190 boolean hasOuterWay = false; 191 for (RelationMember m : r.getMembers()) { 192 if ("outer".equals(m.getRole())) { 193 hasOuterWay = true; 194 break; 195 } 196 } 197 if (!hasOuterWay) { 198 errors.add(TestError.builder(this, Severity.WARNING, MISSING_OUTER_WAY) 199 .message(tr("No outer way for multipolygon")) 200 .primitives(r) 201 .build()); 202 } 203 } 204 205 /** 206 * Create new multipolygon using the logics from CreateMultipolygonAction and see if roles match:<ul> 207 * <li>{@link #WRONG_MEMBER_ROLE}: Role for ''{0}'' should be ''{1}''</li> 208 * </ul> 209 * @param r relation 210 */ 211 private void checkMemberRoleCorrectness(Relation r) { 212 final Pair<Relation, Relation> newMP = CreateMultipolygonAction.createMultipolygonRelation(r.getMemberPrimitives(Way.class), false); 213 if (newMP != null) { 214 for (RelationMember member : r.getMembers()) { 215 final Collection<RelationMember> memberInNewMP = newMP.b.getMembersFor(Collections.singleton(member.getMember())); 216 if (memberInNewMP != null && !memberInNewMP.isEmpty()) { 217 final String roleInNewMP = memberInNewMP.iterator().next().getRole(); 218 if (!member.getRole().equals(roleInNewMP)) { 219 errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE) 220 .message(RelationChecker.ROLE_VERIF_PROBLEM_MSG, 221 marktr("Role for ''{0}'' should be ''{1}''"), 222 member.getMember().getDisplayName(DefaultNameFormatter.getInstance()), roleInNewMP) 223 .primitives(addRelationIfNeeded(r, member.getMember())) 224 .highlight(member.getMember()) 225 .build()); 226 } 227 } 228 } 229 } 230 } 231 232 /** 233 * Various style-related checks:<ul> 234 * <li>{@link #NO_STYLE_POLYGON}: Multipolygon relation should be tagged with area tags and not the outer way</li> 235 * <li>{@link #INNER_STYLE_MISMATCH}: With the currently used mappaint style the style for inner way equals the multipolygon style</li> 236 * <li>{@link #OUTER_STYLE_MISMATCH}: Style for outer way mismatches</li> 237 * <li>{@link #OUTER_STYLE}: Area style on outer way</li> 238 * </ul> 239 * @param r relation 240 * @param polygon multipolygon 241 */ 242 private void checkStyleConsistency(Relation r, Multipolygon polygon) { 243 if (styles != null && !"boundary".equals(r.get("type"))) { 244 AreaElement area = ElemStyles.getAreaElemStyle(r, false); 245 boolean areaStyle = area != null; 246 // If area style was not found for relation then use style of ways 247 if (area == null) { 248 for (Way w : polygon.getOuterWays()) { 249 area = ElemStyles.getAreaElemStyle(w, true); 250 if (area != null) { 251 break; 252 } 253 } 254 if (area == null) { 255 errors.add(TestError.builder(this, Severity.OTHER, NO_STYLE) 256 .message(tr("No area style for multipolygon")) 257 .primitives(r) 258 .build()); 259 } else { 260 /* old style multipolygon - solve: copy tags from outer way to multipolygon */ 261 errors.add(TestError.builder(this, Severity.WARNING, NO_STYLE_POLYGON) 262 .message(trn("Multipolygon relation should be tagged with area tags and not the outer way", 263 "Multipolygon relation should be tagged with area tags and not the outer ways", 264 polygon.getOuterWays().size())) 265 .primitives(r) 266 .build()); 267 } 268 } 269 270 if (area != null) { 271 for (Way wInner : polygon.getInnerWays()) { 272 AreaElement areaInner = ElemStyles.getAreaElemStyle(wInner, false); 273 274 if (areaInner != null && area.equals(areaInner)) { 275 errors.add(TestError.builder(this, Severity.OTHER, INNER_STYLE_MISMATCH) 276 .message(tr("With the currently used mappaint style the style for inner way equals the multipolygon style")) 277 .primitives(addRelationIfNeeded(r, wInner)) 278 .highlight(wInner) 279 .build()); 280 } 281 } 282 for (Way wOuter : polygon.getOuterWays()) { 283 AreaElement areaOuter = ElemStyles.getAreaElemStyle(wOuter, false); 284 if (areaOuter != null) { 285 if (!area.equals(areaOuter)) { 286 String message = !areaStyle ? tr("Style for outer way mismatches") 287 : tr("With the currently used mappaint style(s) the style for outer way mismatches the area style"); 288 errors.add(TestError.builder(this, Severity.OTHER, OUTER_STYLE_MISMATCH) 289 .message(message) 290 .primitives(addRelationIfNeeded(r, wOuter)) 291 .highlight(wOuter) 292 .build()); 293 } else if (areaStyle) { /* style on outer way of multipolygon, but equal to polygon */ 294 errors.add(TestError.builder(this, Severity.WARNING, OUTER_STYLE) 295 .message(tr("Area style on outer way")) 296 .primitives(addRelationIfNeeded(r, wOuter)) 297 .highlight(wOuter) 298 .build()); 299 } 300 } 301 } 302 } 303 } 304 } 305 306 /** 307 * Various geometry-related checks:<ul> 308 * <li>{@link #NON_CLOSED_WAY}: Multipolygon is not closed</li> 309 * <li>{@link #INNER_WAY_OUTSIDE}: Multipolygon inner way is outside</li> 310 * <li>{@link #CROSSING_WAYS}: Intersection between multipolygon ways</li> 311 * </ul> 312 * @param r relation 313 * @param polygon multipolygon 314 */ 315 private void checkGeometry(Relation r, Multipolygon polygon) { 316 List<Node> openNodes = polygon.getOpenEnds(); 317 if (!openNodes.isEmpty()) { 318 errors.add(TestError.builder(this, Severity.WARNING, NON_CLOSED_WAY) 319 .message(tr("Multipolygon is not closed")) 320 .primitives(addRelationIfNeeded(r, openNodes)) 321 .highlight(openNodes) 322 .build()); 323 } 324 325 // For painting is used Polygon class which works with ints only. For validation we need more precision 326 List<PolyData> innerPolygons = polygon.getInnerPolygons(); 327 List<PolyData> outerPolygons = polygon.getOuterPolygons(); 328 List<GeneralPath> innerPolygonsPaths = innerPolygons.isEmpty() ? Collections.<GeneralPath>emptyList() : createPolygons(innerPolygons); 329 List<GeneralPath> outerPolygonsPaths = createPolygons(outerPolygons); 330 for (int i = 0; i < outerPolygons.size(); i++) { 331 PolyData pdOuter = outerPolygons.get(i); 332 // Check for intersection between outer members 333 for (int j = i+1; j < outerPolygons.size(); j++) { 334 checkCrossingWays(r, outerPolygons, outerPolygonsPaths, pdOuter, j); 335 } 336 } 337 for (int i = 0; i < innerPolygons.size(); i++) { 338 PolyData pdInner = innerPolygons.get(i); 339 // Check for intersection between inner members 340 for (int j = i+1; j < innerPolygons.size(); j++) { 341 checkCrossingWays(r, innerPolygons, innerPolygonsPaths, pdInner, j); 342 } 343 // Check for intersection between inner and outer members 344 boolean outside = true; 345 for (int o = 0; o < outerPolygons.size(); o++) { 346 outside &= checkCrossingWays(r, outerPolygons, outerPolygonsPaths, pdInner, o) == Intersection.OUTSIDE; 347 } 348 if (outside) { 349 errors.add(TestError.builder(this, Severity.WARNING, INNER_WAY_OUTSIDE) 350 .message(tr("Multipolygon inner way is outside")) 351 .primitives(r) 352 .highlightNodePairs(Collections.singletonList(pdInner.getNodes())) 353 .build()); 354 } 355 } 356 } 357 358 private Intersection checkCrossingWays(Relation r, List<PolyData> polygons, List<GeneralPath> polygonsPaths, PolyData pd, int idx) { 359 Intersection intersection = getPolygonIntersection(polygonsPaths.get(idx), pd.getNodes()); 360 if (intersection == Intersection.CROSSING) { 361 PolyData pdOther = polygons.get(idx); 362 if (pdOther != null) { 363 errors.add(TestError.builder(this, Severity.WARNING, CROSSING_WAYS) 364 .message(tr("Intersection between multipolygon ways")) 365 .primitives(r) 366 .highlightNodePairs(Arrays.asList(pd.getNodes(), pdOther.getNodes())) 367 .build()); 368 } 369 } 370 return intersection; 371 } 372 373 /** 374 * Check for:<ul> 375 * <li>{@link #WRONG_MEMBER_ROLE}: No useful role for multipolygon member</li> 376 * <li>{@link #WRONG_MEMBER_TYPE}: Non-Way in multipolygon</li> 377 * </ul> 378 * @param r relation 379 */ 380 private void checkMembersAndRoles(Relation r) { 381 for (RelationMember rm : r.getMembers()) { 382 if (rm.isWay()) { 383 if (!(rm.hasRole("inner", "outer") || !rm.hasRole())) { 384 errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_ROLE) 385 .message(tr("No useful role for multipolygon member")) 386 .primitives(addRelationIfNeeded(r, rm.getMember())) 387 .build()); 388 } 389 } else { 390 if (!rm.hasRole("admin_centre", "label", "subarea", "land_area")) { 391 errors.add(TestError.builder(this, Severity.WARNING, WRONG_MEMBER_TYPE) 392 .message(tr("Non-Way in multipolygon")) 393 .primitives(addRelationIfNeeded(r, rm.getMember())) 394 .build()); 395 } 396 } 397 } 398 } 399 400 private static Collection<? extends OsmPrimitive> addRelationIfNeeded(Relation r, OsmPrimitive primitive) { 401 return addRelationIfNeeded(r, Collections.singleton(primitive)); 402 } 403 404 private static Collection<? extends OsmPrimitive> addRelationIfNeeded(Relation r, Collection<? extends OsmPrimitive> primitives) { 405 // add multipolygon in order to let user select something and fix the error 406 if (!primitives.contains(r)) { 407 // Diamond operator does not work with Java 9 here 408 @SuppressWarnings("unused") 409 List<OsmPrimitive> newPrimitives = new ArrayList<OsmPrimitive>(primitives); 410 newPrimitives.add(0, r); 411 return newPrimitives; 412 } else { 413 return primitives; 414 } 415 } 416 417 /** 418 * Check for:<ul> 419 * <li>{@link #REPEATED_MEMBER_DIFF_ROLE}: Multipolygon member(s) repeated with different role</li> 420 * <li>{@link #REPEATED_MEMBER_SAME_ROLE}: Multipolygon member(s) repeated with same role</li> 421 * </ul> 422 * @param r relation 423 * @return true if repeated members have been detected, false otherwise 424 */ 425 private boolean checkRepeatedWayMembers(Relation r) { 426 boolean hasDups = false; 427 Map<OsmPrimitive, List<RelationMember>> seenMemberPrimitives = new HashMap<>(); 428 for (RelationMember rm : r.getMembers()) { 429 List<RelationMember> list = seenMemberPrimitives.get(rm.getMember()); 430 if (list == null) { 431 list = new ArrayList<>(2); 432 seenMemberPrimitives.put(rm.getMember(), list); 433 } else { 434 hasDups = true; 435 } 436 list.add(rm); 437 } 438 if (hasDups) { 439 List<OsmPrimitive> repeatedSameRole = new ArrayList<>(); 440 List<OsmPrimitive> repeatedDiffRole = new ArrayList<>(); 441 for (Entry<OsmPrimitive, List<RelationMember>> e : seenMemberPrimitives.entrySet()) { 442 List<RelationMember> visited = e.getValue(); 443 if (e.getValue().size() == 1) 444 continue; 445 // we found a duplicate member, check if the roles differ 446 boolean rolesDiffer = false; 447 RelationMember rm = visited.get(0); 448 List<OsmPrimitive> primitives = new ArrayList<>(); 449 for (int i = 1; i < visited.size(); i++) { 450 RelationMember v = visited.get(i); 451 primitives.add(rm.getMember()); 452 if (!v.getRole().equals(rm.getRole())) { 453 rolesDiffer = true; 454 } 455 } 456 if (rolesDiffer) { 457 repeatedDiffRole.addAll(primitives); 458 } else { 459 repeatedSameRole.addAll(primitives); 460 } 461 } 462 addRepeatedMemberError(r, repeatedDiffRole, REPEATED_MEMBER_DIFF_ROLE, tr("Multipolygon member(s) repeated with different role")); 463 addRepeatedMemberError(r, repeatedSameRole, REPEATED_MEMBER_SAME_ROLE, tr("Multipolygon member(s) repeated with same role")); 464 } 465 return hasDups; 466 } 467 468 private void addRepeatedMemberError(Relation r, List<OsmPrimitive> repeatedMembers, int errorCode, String msg) { 469 if (!repeatedMembers.isEmpty()) { 470 List<OsmPrimitive> prims = new ArrayList<>(1 + repeatedMembers.size()); 471 prims.add(r); 472 prims.addAll(repeatedMembers); 473 errors.add(TestError.builder(this, Severity.WARNING, errorCode) 474 .message(msg) 475 .primitives(prims) 476 .highlight(repeatedMembers) 477 .build()); 478 } 479 } 480 481 @Override 482 public Command fixError(TestError testError) { 483 if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) { 484 ArrayList<OsmPrimitive> primitives = new ArrayList<>(testError.getPrimitives()); 485 if (primitives.size() >= 2 && primitives.get(0) instanceof Relation) { 486 Relation oldRel = (Relation) primitives.get(0); 487 Relation newRel = new Relation(oldRel); 488 List<OsmPrimitive> repeatedPrims = primitives.subList(1, primitives.size()); 489 List<RelationMember> oldMembers = oldRel.getMembers(); 490 491 List<RelationMember> newMembers = new ArrayList<>(); 492 HashSet<OsmPrimitive> toRemove = new HashSet<>(repeatedPrims); 493 HashSet<OsmPrimitive> found = new HashSet<>(repeatedPrims.size()); 494 for (RelationMember rm : oldMembers) { 495 if (toRemove.contains(rm.getMember())) { 496 if (!found.contains(rm.getMember())) { 497 found.add(rm.getMember()); 498 newMembers.add(rm); 499 } 500 } else { 501 newMembers.add(rm); 502 } 503 } 504 newRel.setMembers(newMembers); 505 return new ChangeCommand(oldRel, newRel); 506 } 507 } 508 return null; 509 } 510 511 @Override 512 public boolean isFixable(TestError testError) { 513 if (testError.getCode() == REPEATED_MEMBER_SAME_ROLE) 514 return true; 515 return false; 516 } 517}