001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.osm.visitor.paint.relations; 003 004import java.awt.geom.Path2D; 005import java.awt.geom.PathIterator; 006import java.awt.geom.Rectangle2D; 007import java.util.ArrayList; 008import java.util.Collection; 009import java.util.Collections; 010import java.util.HashSet; 011import java.util.Iterator; 012import java.util.List; 013import java.util.Set; 014 015import org.openstreetmap.josm.Main; 016import org.openstreetmap.josm.data.Preferences.PreferenceChangeEvent; 017import org.openstreetmap.josm.data.Preferences.PreferenceChangedListener; 018import org.openstreetmap.josm.data.coor.EastNorth; 019import org.openstreetmap.josm.data.osm.DataSet; 020import org.openstreetmap.josm.data.osm.Node; 021import org.openstreetmap.josm.data.osm.OsmPrimitiveType; 022import org.openstreetmap.josm.data.osm.Relation; 023import org.openstreetmap.josm.data.osm.RelationMember; 024import org.openstreetmap.josm.data.osm.Way; 025import org.openstreetmap.josm.data.osm.event.NodeMovedEvent; 026import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent; 027import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.PolyData.Intersection; 028import org.openstreetmap.josm.data.projection.Projection; 029import org.openstreetmap.josm.tools.Geometry; 030import org.openstreetmap.josm.tools.Geometry.AreaAndPerimeter; 031 032/** 033 * Multipolygon data used to represent complex areas, see <a href="https://wiki.openstreetmap.org/wiki/Relation:multipolygon">wiki</a>. 034 * @since 2788 035 */ 036public class Multipolygon { 037 038 /** preference key for a collection of roles which indicate that the respective member belongs to an 039 * <em>outer</em> polygon. Default is <tt>outer</tt>. 040 */ 041 public static final String PREF_KEY_OUTER_ROLES = "mappaint.multipolygon.outer.roles"; 042 043 /** preference key for collection of role prefixes which indicate that the respective 044 * member belongs to an <em>outer</em> polygon. Default is empty. 045 */ 046 public static final String PREF_KEY_OUTER_ROLE_PREFIXES = "mappaint.multipolygon.outer.role-prefixes"; 047 048 /** preference key for a collection of roles which indicate that the respective member belongs to an 049 * <em>inner</em> polygon. Default is <tt>inner</tt>. 050 */ 051 public static final String PREF_KEY_INNER_ROLES = "mappaint.multipolygon.inner.roles"; 052 053 /** preference key for collection of role prefixes which indicate that the respective 054 * member belongs to an <em>inner</em> polygon. Default is empty. 055 */ 056 public static final String PREF_KEY_INNER_ROLE_PREFIXES = "mappaint.multipolygon.inner.role-prefixes"; 057 058 /** 059 * <p>Kind of strategy object which is responsible for deciding whether a given 060 * member role indicates that the member belongs to an <em>outer</em> or an 061 * <em>inner</em> polygon.</p> 062 * 063 * <p>The decision is taken based on preference settings, see the four preference keys 064 * above.</p> 065 */ 066 private static class MultipolygonRoleMatcher implements PreferenceChangedListener { 067 private final List<String> outerExactRoles = new ArrayList<>(); 068 private final List<String> outerRolePrefixes = new ArrayList<>(); 069 private final List<String> innerExactRoles = new ArrayList<>(); 070 private final List<String> innerRolePrefixes = new ArrayList<>(); 071 072 private void initDefaults() { 073 outerExactRoles.clear(); 074 outerRolePrefixes.clear(); 075 innerExactRoles.clear(); 076 innerRolePrefixes.clear(); 077 outerExactRoles.add("outer"); 078 innerExactRoles.add("inner"); 079 } 080 081 private static void setNormalized(Collection<String> literals, List<String> target) { 082 target.clear(); 083 for (String l: literals) { 084 if (l == null) { 085 continue; 086 } 087 l = l.trim(); 088 if (!target.contains(l)) { 089 target.add(l); 090 } 091 } 092 } 093 094 private void initFromPreferences() { 095 initDefaults(); 096 if (Main.pref == null) return; 097 Collection<String> literals; 098 literals = Main.pref.getCollection(PREF_KEY_OUTER_ROLES); 099 if (literals != null && !literals.isEmpty()) { 100 setNormalized(literals, outerExactRoles); 101 } 102 literals = Main.pref.getCollection(PREF_KEY_OUTER_ROLE_PREFIXES); 103 if (literals != null && !literals.isEmpty()) { 104 setNormalized(literals, outerRolePrefixes); 105 } 106 literals = Main.pref.getCollection(PREF_KEY_INNER_ROLES); 107 if (literals != null && !literals.isEmpty()) { 108 setNormalized(literals, innerExactRoles); 109 } 110 literals = Main.pref.getCollection(PREF_KEY_INNER_ROLE_PREFIXES); 111 if (literals != null && !literals.isEmpty()) { 112 setNormalized(literals, innerRolePrefixes); 113 } 114 } 115 116 @Override 117 public void preferenceChanged(PreferenceChangeEvent evt) { 118 if (PREF_KEY_INNER_ROLE_PREFIXES.equals(evt.getKey()) || 119 PREF_KEY_INNER_ROLES.equals(evt.getKey()) || 120 PREF_KEY_OUTER_ROLE_PREFIXES.equals(evt.getKey()) || 121 PREF_KEY_OUTER_ROLES.equals(evt.getKey())) { 122 initFromPreferences(); 123 } 124 } 125 126 public boolean isOuterRole(String role) { 127 if (role == null) return false; 128 for (String candidate: outerExactRoles) { 129 if (role.equals(candidate)) return true; 130 } 131 for (String candidate: outerRolePrefixes) { 132 if (role.startsWith(candidate)) return true; 133 } 134 return false; 135 } 136 137 public boolean isInnerRole(String role) { 138 if (role == null) return false; 139 for (String candidate: innerExactRoles) { 140 if (role.equals(candidate)) return true; 141 } 142 for (String candidate: innerRolePrefixes) { 143 if (role.startsWith(candidate)) return true; 144 } 145 return false; 146 } 147 } 148 149 /* 150 * Init a private global matcher object which will listen to preference changes. 151 */ 152 private static MultipolygonRoleMatcher roleMatcher; 153 154 private static synchronized MultipolygonRoleMatcher getMultipolygonRoleMatcher() { 155 if (roleMatcher == null) { 156 roleMatcher = new MultipolygonRoleMatcher(); 157 if (Main.pref != null) { 158 roleMatcher.initFromPreferences(); 159 Main.pref.addPreferenceChangeListener(roleMatcher); 160 } 161 } 162 return roleMatcher; 163 } 164 165 public static class JoinedWay { 166 private final List<Node> nodes; 167 private final Collection<Long> wayIds; 168 private final boolean selected; 169 170 public JoinedWay(List<Node> nodes, Collection<Long> wayIds, boolean selected) { 171 this.nodes = nodes; 172 this.wayIds = wayIds; 173 this.selected = selected; 174 } 175 176 public List<Node> getNodes() { 177 return nodes; 178 } 179 180 public Collection<Long> getWayIds() { 181 return wayIds; 182 } 183 184 public boolean isSelected() { 185 return selected; 186 } 187 188 public boolean isClosed() { 189 return nodes.isEmpty() || nodes.get(nodes.size() - 1).equals(nodes.get(0)); 190 } 191 } 192 193 public static class PolyData { 194 public enum Intersection { 195 INSIDE, 196 OUTSIDE, 197 CROSSING 198 } 199 200 private final Path2D.Double poly; 201 public boolean selected; 202 private Rectangle2D bounds; 203 private final Collection<Long> wayIds; 204 private final List<Node> nodes; 205 private final List<PolyData> inners; 206 207 public PolyData(Way closedWay) { 208 this(closedWay.getNodes(), closedWay.isSelected(), Collections.singleton(closedWay.getUniqueId())); 209 } 210 211 public PolyData(JoinedWay joinedWay) { 212 this(joinedWay.getNodes(), joinedWay.isSelected(), joinedWay.getWayIds()); 213 } 214 215 private PolyData(List<Node> nodes, boolean selected, Collection<Long> wayIds) { 216 this.wayIds = Collections.unmodifiableCollection(wayIds); 217 this.nodes = new ArrayList<>(nodes); 218 this.selected = selected; 219 this.inners = new ArrayList<>(); 220 this.poly = new Path2D.Double(); 221 this.poly.setWindingRule(Path2D.WIND_EVEN_ODD); 222 buildPoly(); 223 } 224 225 private void buildPoly() { 226 boolean initial = true; 227 for (Node n : nodes) { 228 EastNorth p = n.getEastNorth(); 229 if (p != null) { 230 if (initial) { 231 poly.moveTo(p.getX(), p.getY()); 232 initial = false; 233 } else { 234 poly.lineTo(p.getX(), p.getY()); 235 } 236 } 237 } 238 if (nodes.size() >= 3 && nodes.get(0) == nodes.get(nodes.size() - 1)) { 239 poly.closePath(); 240 } 241 for (PolyData inner : inners) { 242 appendInner(inner.poly); 243 } 244 } 245 246 public PolyData(PolyData copy) { 247 this.selected = copy.selected; 248 this.poly = (Path2D.Double) copy.poly.clone(); 249 this.wayIds = Collections.unmodifiableCollection(copy.wayIds); 250 this.nodes = new ArrayList<>(copy.nodes); 251 this.inners = new ArrayList<>(copy.inners); 252 } 253 254 public Intersection contains(Path2D.Double p) { 255 int contains = 0; 256 int total = 0; 257 double[] coords = new double[6]; 258 for (PathIterator it = p.getPathIterator(null); !it.isDone(); it.next()) { 259 switch (it.currentSegment(coords)) { 260 case PathIterator.SEG_MOVETO: 261 case PathIterator.SEG_LINETO: 262 if (poly.contains(coords[0], coords[1])) { 263 contains++; 264 } 265 total++; 266 } 267 } 268 if (contains == total) return Intersection.INSIDE; 269 if (contains == 0) return Intersection.OUTSIDE; 270 return Intersection.CROSSING; 271 } 272 273 public void addInner(PolyData inner) { 274 inners.add(inner); 275 appendInner(inner.poly); 276 } 277 278 private void appendInner(Path2D.Double inner) { 279 poly.append(inner.getPathIterator(null), false); 280 } 281 282 public Path2D.Double get() { 283 return poly; 284 } 285 286 public Rectangle2D getBounds() { 287 if (bounds == null) { 288 bounds = poly.getBounds2D(); 289 } 290 return bounds; 291 } 292 293 public Collection<Long> getWayIds() { 294 return wayIds; 295 } 296 297 public List<Node> getNodes() { 298 return nodes; 299 } 300 301 public List<PolyData> getInners() { 302 return inners; 303 } 304 305 private void resetNodes(DataSet dataSet) { 306 if (!nodes.isEmpty()) { 307 DataSet ds = dataSet; 308 // Find DataSet (can be null for several nodes when undoing nodes creation, see #7162) 309 for (Iterator<Node> it = nodes.iterator(); it.hasNext() && ds == null;) { 310 ds = it.next().getDataSet(); 311 } 312 nodes.clear(); 313 if (ds == null) { 314 // DataSet still not found. This should not happen, but a warning does no harm 315 Main.warn("DataSet not found while resetting nodes in Multipolygon. " + 316 "This should not happen, you may report it to JOSM developers."); 317 } else if (wayIds.size() == 1) { 318 Way w = (Way) ds.getPrimitiveById(wayIds.iterator().next(), OsmPrimitiveType.WAY); 319 nodes.addAll(w.getNodes()); 320 } else if (!wayIds.isEmpty()) { 321 List<Way> waysToJoin = new ArrayList<>(); 322 for (Long wayId : wayIds) { 323 Way w = (Way) ds.getPrimitiveById(wayId, OsmPrimitiveType.WAY); 324 if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge) 325 waysToJoin.add(w); 326 } 327 } 328 if (!waysToJoin.isEmpty()) { 329 nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes()); 330 } 331 } 332 resetPoly(); 333 } 334 } 335 336 private void resetPoly() { 337 poly.reset(); 338 buildPoly(); 339 bounds = null; 340 } 341 342 public void nodeMoved(NodeMovedEvent event) { 343 final Node n = event.getNode(); 344 boolean innerChanged = false; 345 for (PolyData inner : inners) { 346 if (inner.nodes.contains(n)) { 347 inner.resetPoly(); 348 innerChanged = true; 349 } 350 } 351 if (nodes.contains(n) || innerChanged) { 352 resetPoly(); 353 } 354 } 355 356 public void wayNodesChanged(WayNodesChangedEvent event) { 357 final Long wayId = event.getChangedWay().getUniqueId(); 358 boolean innerChanged = false; 359 for (PolyData inner : inners) { 360 if (inner.wayIds.contains(wayId)) { 361 inner.resetNodes(event.getDataset()); 362 innerChanged = true; 363 } 364 } 365 if (wayIds.contains(wayId) || innerChanged) { 366 resetNodes(event.getDataset()); 367 } 368 } 369 370 public boolean isClosed() { 371 if (nodes.size() < 3 || nodes.get(0) != nodes.get(nodes.size() - 1)) return false; 372 for (PolyData inner : inners) { 373 if (!inner.isClosed()) return false; 374 } 375 return true; 376 } 377 378 /** 379 * Calculate area and perimeter length in the given projection. 380 * 381 * @param projection the projection to use for the calculation, {@code null} defaults to {@link Main#getProjection()} 382 * @return area and perimeter 383 */ 384 public AreaAndPerimeter getAreaAndPerimeter(Projection projection) { 385 AreaAndPerimeter ap = Geometry.getAreaAndPerimeter(nodes, projection); 386 double area = ap.getArea(); 387 double perimeter = ap.getPerimeter(); 388 for (PolyData inner : inners) { 389 AreaAndPerimeter apInner = inner.getAreaAndPerimeter(projection); 390 area -= apInner.getArea(); 391 perimeter += apInner.getPerimeter(); 392 } 393 return new AreaAndPerimeter(area, perimeter); 394 } 395 } 396 397 private final List<Way> innerWays = new ArrayList<>(); 398 private final List<Way> outerWays = new ArrayList<>(); 399 private final List<PolyData> combinedPolygons = new ArrayList<>(); 400 private final List<Node> openEnds = new ArrayList<>(); 401 402 private boolean incomplete; 403 404 public Multipolygon(Relation r) { 405 load(r); 406 } 407 408 private void load(Relation r) { 409 MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher(); 410 411 // Fill inner and outer list with valid ways 412 for (RelationMember m : r.getMembers()) { 413 if (m.getMember().isIncomplete()) { 414 this.incomplete = true; 415 } else if (m.getMember().isDrawable()) { 416 if (m.isWay()) { 417 Way w = m.getWay(); 418 419 if (w.getNodesCount() < 2) { 420 continue; 421 } 422 423 if (matcher.isInnerRole(m.getRole())) { 424 innerWays.add(w); 425 } else if (matcher.isOuterRole(m.getRole())) { 426 outerWays.add(w); 427 } else if (!m.hasRole()) { 428 outerWays.add(w); 429 } // Remaining roles ignored 430 } // Non ways ignored 431 } 432 } 433 434 final List<PolyData> innerPolygons = new ArrayList<>(); 435 final List<PolyData> outerPolygons = new ArrayList<>(); 436 createPolygons(innerWays, innerPolygons); 437 createPolygons(outerWays, outerPolygons); 438 if (!outerPolygons.isEmpty()) { 439 addInnerToOuters(innerPolygons, outerPolygons); 440 } 441 } 442 443 public final boolean isIncomplete() { 444 return incomplete; 445 } 446 447 private void createPolygons(List<Way> ways, List<PolyData> result) { 448 List<Way> waysToJoin = new ArrayList<>(); 449 for (Way way: ways) { 450 if (way.isClosed()) { 451 result.add(new PolyData(way)); 452 } else { 453 waysToJoin.add(way); 454 } 455 } 456 457 for (JoinedWay jw: joinWays(waysToJoin)) { 458 result.add(new PolyData(jw)); 459 if (!jw.isClosed()) { 460 openEnds.add(jw.getNodes().get(0)); 461 openEnds.add(jw.getNodes().get(jw.getNodes().size() - 1)); 462 } 463 } 464 } 465 466 public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin) { 467 final Collection<JoinedWay> result = new ArrayList<>(); 468 final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]); 469 int left = waysToJoin.size(); 470 while (left > 0) { 471 Way w = null; 472 boolean selected = false; 473 List<Node> nodes = null; 474 Set<Long> wayIds = new HashSet<>(); 475 boolean joined = true; 476 while (joined && left > 0) { 477 joined = false; 478 for (int i = 0; i < joinArray.length && left != 0; ++i) { 479 if (joinArray[i] != null) { 480 Way c = joinArray[i]; 481 if (c.getNodesCount() == 0) { 482 continue; 483 } 484 if (w == null) { 485 w = c; 486 selected = w.isSelected(); 487 joinArray[i] = null; 488 --left; 489 } else { 490 int mode = 0; 491 int cl = c.getNodesCount()-1; 492 int nl; 493 if (nodes == null) { 494 nl = w.getNodesCount()-1; 495 if (w.getNode(nl) == c.getNode(0)) { 496 mode = 21; 497 } else if (w.getNode(nl) == c.getNode(cl)) { 498 mode = 22; 499 } else if (w.getNode(0) == c.getNode(0)) { 500 mode = 11; 501 } else if (w.getNode(0) == c.getNode(cl)) { 502 mode = 12; 503 } 504 } else { 505 nl = nodes.size()-1; 506 if (nodes.get(nl) == c.getNode(0)) { 507 mode = 21; 508 } else if (nodes.get(0) == c.getNode(cl)) { 509 mode = 12; 510 } else if (nodes.get(0) == c.getNode(0)) { 511 mode = 11; 512 } else if (nodes.get(nl) == c.getNode(cl)) { 513 mode = 22; 514 } 515 } 516 if (mode != 0) { 517 joinArray[i] = null; 518 joined = true; 519 if (c.isSelected()) { 520 selected = true; 521 } 522 --left; 523 if (nodes == null) { 524 nodes = w.getNodes(); 525 wayIds.add(w.getUniqueId()); 526 } 527 nodes.remove((mode == 21 || mode == 22) ? nl : 0); 528 if (mode == 21) { 529 nodes.addAll(c.getNodes()); 530 } else if (mode == 12) { 531 nodes.addAll(0, c.getNodes()); 532 } else if (mode == 22) { 533 for (Node node : c.getNodes()) { 534 nodes.add(nl, node); 535 } 536 } else /* mode == 11 */ { 537 for (Node node : c.getNodes()) { 538 nodes.add(0, node); 539 } 540 } 541 wayIds.add(c.getUniqueId()); 542 } 543 } 544 } 545 } 546 } 547 548 if (nodes == null && w != null) { 549 nodes = w.getNodes(); 550 wayIds.add(w.getUniqueId()); 551 } 552 553 result.add(new JoinedWay(nodes, wayIds, selected)); 554 } 555 556 return result; 557 } 558 559 public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) { 560 561 // First try to test only bbox, use precise testing only if we don't get unique result 562 Rectangle2D innerBox = inner.getBounds(); 563 PolyData insidePolygon = null; 564 PolyData intersectingPolygon = null; 565 int insideCount = 0; 566 int intersectingCount = 0; 567 568 for (PolyData outer: outerPolygons) { 569 if (outer.getBounds().contains(innerBox)) { 570 insidePolygon = outer; 571 insideCount++; 572 } else if (outer.getBounds().intersects(innerBox)) { 573 intersectingPolygon = outer; 574 intersectingCount++; 575 } 576 } 577 578 if (insideCount == 1) 579 return insidePolygon; 580 else if (intersectingCount == 1) 581 return intersectingPolygon; 582 583 PolyData result = null; 584 for (PolyData combined : outerPolygons) { 585 if (combined.contains(inner.poly) != Intersection.OUTSIDE) { 586 if (result == null || result.contains(combined.poly) == Intersection.INSIDE) { 587 result = combined; 588 } 589 } 590 } 591 return result; 592 } 593 594 private void addInnerToOuters(List<PolyData> innerPolygons, List<PolyData> outerPolygons) { 595 596 if (innerPolygons.isEmpty()) { 597 combinedPolygons.addAll(outerPolygons); 598 } else if (outerPolygons.size() == 1) { 599 PolyData combinedOuter = new PolyData(outerPolygons.get(0)); 600 for (PolyData inner: innerPolygons) { 601 combinedOuter.addInner(inner); 602 } 603 combinedPolygons.add(combinedOuter); 604 } else { 605 for (PolyData outer: outerPolygons) { 606 combinedPolygons.add(new PolyData(outer)); 607 } 608 609 for (PolyData pdInner: innerPolygons) { 610 PolyData o = findOuterPolygon(pdInner, combinedPolygons); 611 if (o == null) { 612 o = outerPolygons.get(0); 613 } 614 o.addInner(pdInner); 615 } 616 } 617 } 618 619 /** 620 * Replies the list of outer ways. 621 * @return the list of outer ways 622 */ 623 public List<Way> getOuterWays() { 624 return outerWays; 625 } 626 627 /** 628 * Replies the list of inner ways. 629 * @return the list of inner ways 630 */ 631 public List<Way> getInnerWays() { 632 return innerWays; 633 } 634 635 public List<PolyData> getCombinedPolygons() { 636 return combinedPolygons; 637 } 638 639 public List<PolyData> getInnerPolygons() { 640 final List<PolyData> innerPolygons = new ArrayList<>(); 641 createPolygons(innerWays, innerPolygons); 642 return innerPolygons; 643 } 644 645 public List<PolyData> getOuterPolygons() { 646 final List<PolyData> outerPolygons = new ArrayList<>(); 647 createPolygons(outerWays, outerPolygons); 648 return outerPolygons; 649 } 650 651 /** 652 * Returns the start and end node of non-closed rings. 653 * @return the start and end node of non-closed rings. 654 */ 655 public List<Node> getOpenEnds() { 656 return openEnds; 657 } 658}