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 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 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 /** 166 * Class representing a string of ways. 167 * 168 * The last node of one way is the first way of the next one. 169 * The string may or may not be closed. 170 */ 171 public static class JoinedWay { 172 protected final List<Node> nodes; 173 protected final Collection<Long> wayIds; 174 protected boolean selected; 175 176 /** 177 * Constructs a new {@code JoinedWay}. 178 * @param nodes list of nodes - must not be null 179 * @param wayIds list of way IDs - must not be null 180 * @param selected whether joined way is selected or not 181 */ 182 public JoinedWay(List<Node> nodes, Collection<Long> wayIds, boolean selected) { 183 this.nodes = new ArrayList<>(nodes); 184 this.wayIds = new ArrayList<>(wayIds); 185 this.selected = selected; 186 } 187 188 /** 189 * Replies the list of nodes. 190 * @return the list of nodes 191 */ 192 public List<Node> getNodes() { 193 return Collections.unmodifiableList(nodes); 194 } 195 196 /** 197 * Replies the list of way IDs. 198 * @return the list of way IDs 199 */ 200 public Collection<Long> getWayIds() { 201 return Collections.unmodifiableCollection(wayIds); 202 } 203 204 /** 205 * Determines if this is selected. 206 * @return {@code true} if this is selected 207 */ 208 public final boolean isSelected() { 209 return selected; 210 } 211 212 /** 213 * Sets whether this is selected 214 * @param selected {@code true} if this is selected 215 * @since 10312 216 */ 217 public final void setSelected(boolean selected) { 218 this.selected = selected; 219 } 220 221 /** 222 * Determines if this joined way is closed. 223 * @return {@code true} if this joined way is closed 224 */ 225 public boolean isClosed() { 226 return nodes.isEmpty() || getLastNode().equals(getFirstNode()); 227 } 228 229 /** 230 * Returns the first node. 231 * @return the first node 232 * @since 10312 233 */ 234 public Node getFirstNode() { 235 return nodes.get(0); 236 } 237 238 /** 239 * Returns the last node. 240 * @return the last node 241 * @since 10312 242 */ 243 public Node getLastNode() { 244 return nodes.get(nodes.size() - 1); 245 } 246 } 247 248 public static class PolyData extends JoinedWay { 249 public enum Intersection { 250 INSIDE, 251 OUTSIDE, 252 CROSSING 253 } 254 255 private final Path2D.Double poly; 256 private Rectangle2D bounds; 257 private final List<PolyData> inners; 258 259 /** 260 * Constructs a new {@code PolyData} from a closed way. 261 * @param closedWay closed way 262 */ 263 public PolyData(Way closedWay) { 264 this(closedWay.getNodes(), closedWay.isSelected(), Collections.singleton(closedWay.getUniqueId())); 265 } 266 267 /** 268 * Constructs a new {@code PolyData} from a {@link JoinedWay}. 269 * @param joinedWay joined way 270 */ 271 public PolyData(JoinedWay joinedWay) { 272 this(joinedWay.nodes, joinedWay.selected, joinedWay.wayIds); 273 } 274 275 private PolyData(List<Node> nodes, boolean selected, Collection<Long> wayIds) { 276 super(nodes, wayIds, selected); 277 this.inners = new ArrayList<>(); 278 this.poly = new Path2D.Double(); 279 this.poly.setWindingRule(Path2D.WIND_EVEN_ODD); 280 buildPoly(); 281 } 282 283 /** 284 * Constructs a new {@code PolyData} from an existing {@code PolyData}. 285 * @param copy existing instance 286 */ 287 public PolyData(PolyData copy) { 288 super(copy.nodes, copy.wayIds, copy.selected); 289 this.poly = (Path2D.Double) copy.poly.clone(); 290 this.inners = new ArrayList<>(copy.inners); 291 } 292 293 private void buildPoly() { 294 boolean initial = true; 295 for (Node n : nodes) { 296 EastNorth p = n.getEastNorth(); 297 if (p != null) { 298 if (initial) { 299 poly.moveTo(p.getX(), p.getY()); 300 initial = false; 301 } else { 302 poly.lineTo(p.getX(), p.getY()); 303 } 304 } 305 } 306 if (nodes.size() >= 3 && nodes.get(0) == nodes.get(nodes.size() - 1)) { 307 poly.closePath(); 308 } 309 for (PolyData inner : inners) { 310 appendInner(inner.poly); 311 } 312 } 313 314 public Intersection contains(Path2D.Double p) { 315 int contains = 0; 316 int total = 0; 317 double[] coords = new double[6]; 318 for (PathIterator it = p.getPathIterator(null); !it.isDone(); it.next()) { 319 switch (it.currentSegment(coords)) { 320 case PathIterator.SEG_MOVETO: 321 case PathIterator.SEG_LINETO: 322 if (poly.contains(coords[0], coords[1])) { 323 contains++; 324 } 325 total++; 326 break; 327 default: // Do nothing 328 } 329 } 330 if (contains == total) return Intersection.INSIDE; 331 if (contains == 0) return Intersection.OUTSIDE; 332 return Intersection.CROSSING; 333 } 334 335 public void addInner(PolyData inner) { 336 inners.add(inner); 337 appendInner(inner.poly); 338 } 339 340 private void appendInner(Path2D.Double inner) { 341 poly.append(inner.getPathIterator(null), false); 342 } 343 344 public Path2D.Double get() { 345 return poly; 346 } 347 348 public Rectangle2D getBounds() { 349 if (bounds == null) { 350 bounds = poly.getBounds2D(); 351 } 352 return bounds; 353 } 354 355 public List<PolyData> getInners() { 356 return Collections.unmodifiableList(inners); 357 } 358 359 private void resetNodes(DataSet dataSet) { 360 if (!nodes.isEmpty()) { 361 DataSet ds = dataSet; 362 // Find DataSet (can be null for several nodes when undoing nodes creation, see #7162) 363 for (Iterator<Node> it = nodes.iterator(); it.hasNext() && ds == null;) { 364 ds = it.next().getDataSet(); 365 } 366 nodes.clear(); 367 if (ds == null) { 368 // DataSet still not found. This should not happen, but a warning does no harm 369 Main.warn("DataSet not found while resetting nodes in Multipolygon. " + 370 "This should not happen, you may report it to JOSM developers."); 371 } else if (wayIds.size() == 1) { 372 Way w = (Way) ds.getPrimitiveById(wayIds.iterator().next(), OsmPrimitiveType.WAY); 373 nodes.addAll(w.getNodes()); 374 } else if (!wayIds.isEmpty()) { 375 List<Way> waysToJoin = new ArrayList<>(); 376 for (Long wayId : wayIds) { 377 Way w = (Way) ds.getPrimitiveById(wayId, OsmPrimitiveType.WAY); 378 if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge) 379 waysToJoin.add(w); 380 } 381 } 382 if (!waysToJoin.isEmpty()) { 383 nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes()); 384 } 385 } 386 resetPoly(); 387 } 388 } 389 390 private void resetPoly() { 391 poly.reset(); 392 buildPoly(); 393 bounds = null; 394 } 395 396 public void nodeMoved(NodeMovedEvent event) { 397 final Node n = event.getNode(); 398 boolean innerChanged = false; 399 for (PolyData inner : inners) { 400 if (inner.nodes.contains(n)) { 401 inner.resetPoly(); 402 innerChanged = true; 403 } 404 } 405 if (nodes.contains(n) || innerChanged) { 406 resetPoly(); 407 } 408 } 409 410 public void wayNodesChanged(WayNodesChangedEvent event) { 411 final Long wayId = event.getChangedWay().getUniqueId(); 412 boolean innerChanged = false; 413 for (PolyData inner : inners) { 414 if (inner.wayIds.contains(wayId)) { 415 inner.resetNodes(event.getDataset()); 416 innerChanged = true; 417 } 418 } 419 if (wayIds.contains(wayId) || innerChanged) { 420 resetNodes(event.getDataset()); 421 } 422 } 423 424 @Override 425 public boolean isClosed() { 426 if (nodes.size() < 3 || !getFirstNode().equals(getLastNode())) 427 return false; 428 for (PolyData inner : inners) { 429 if (!inner.isClosed()) 430 return false; 431 } 432 return true; 433 } 434 435 /** 436 * Calculate area and perimeter length in the given projection. 437 * 438 * @param projection the projection to use for the calculation, {@code null} defaults to {@link Main#getProjection()} 439 * @return area and perimeter 440 */ 441 public AreaAndPerimeter getAreaAndPerimeter(Projection projection) { 442 AreaAndPerimeter ap = Geometry.getAreaAndPerimeter(nodes, projection); 443 double area = ap.getArea(); 444 double perimeter = ap.getPerimeter(); 445 for (PolyData inner : inners) { 446 AreaAndPerimeter apInner = inner.getAreaAndPerimeter(projection); 447 area -= apInner.getArea(); 448 perimeter += apInner.getPerimeter(); 449 } 450 return new AreaAndPerimeter(area, perimeter); 451 } 452 } 453 454 private final List<Way> innerWays = new ArrayList<>(); 455 private final List<Way> outerWays = new ArrayList<>(); 456 private final List<PolyData> combinedPolygons = new ArrayList<>(); 457 private final List<Node> openEnds = new ArrayList<>(); 458 459 private boolean incomplete; 460 461 /** 462 * Constructs a new {@code Multipolygon} from a relation. 463 * @param r relation 464 */ 465 public Multipolygon(Relation r) { 466 load(r); 467 } 468 469 private void load(Relation r) { 470 MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher(); 471 472 // Fill inner and outer list with valid ways 473 for (RelationMember m : r.getMembers()) { 474 if (m.getMember().isIncomplete()) { 475 this.incomplete = true; 476 } else if (m.getMember().isDrawable() && m.isWay()) { 477 Way w = m.getWay(); 478 479 if (w.getNodesCount() < 2) { 480 continue; 481 } 482 483 if (matcher.isInnerRole(m.getRole())) { 484 innerWays.add(w); 485 } else if (!m.hasRole() || matcher.isOuterRole(m.getRole())) { 486 outerWays.add(w); 487 } // Remaining roles ignored 488 } // Non ways ignored 489 } 490 491 final List<PolyData> innerPolygons = new ArrayList<>(); 492 final List<PolyData> outerPolygons = new ArrayList<>(); 493 createPolygons(innerWays, innerPolygons); 494 createPolygons(outerWays, outerPolygons); 495 if (!outerPolygons.isEmpty()) { 496 addInnerToOuters(innerPolygons, outerPolygons); 497 } 498 } 499 500 /** 501 * Determines if this multipolygon is incomplete. 502 * @return {@code true} if this multipolygon is incomplete 503 */ 504 public final boolean isIncomplete() { 505 return incomplete; 506 } 507 508 private void createPolygons(List<Way> ways, List<PolyData> result) { 509 List<Way> waysToJoin = new ArrayList<>(); 510 for (Way way: ways) { 511 if (way.isClosed()) { 512 result.add(new PolyData(way)); 513 } else { 514 waysToJoin.add(way); 515 } 516 } 517 518 for (JoinedWay jw: joinWays(waysToJoin)) { 519 result.add(new PolyData(jw)); 520 if (!jw.isClosed()) { 521 openEnds.add(jw.getFirstNode()); 522 openEnds.add(jw.getLastNode()); 523 } 524 } 525 } 526 527 public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin) { 528 final Collection<JoinedWay> result = new ArrayList<>(); 529 final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]); 530 int left = waysToJoin.size(); 531 while (left > 0) { 532 Way w = null; 533 boolean selected = false; 534 List<Node> nodes = null; 535 Set<Long> wayIds = new HashSet<>(); 536 boolean joined = true; 537 while (joined && left > 0) { 538 joined = false; 539 for (int i = 0; i < joinArray.length && left != 0; ++i) { 540 if (joinArray[i] != null) { 541 Way c = joinArray[i]; 542 if (c.getNodesCount() == 0) { 543 continue; 544 } 545 if (w == null) { 546 w = c; 547 selected = w.isSelected(); 548 joinArray[i] = null; 549 --left; 550 } else { 551 int mode = 0; 552 int cl = c.getNodesCount()-1; 553 int nl; 554 if (nodes == null) { 555 nl = w.getNodesCount()-1; 556 if (w.getNode(nl) == c.getNode(0)) { 557 mode = 21; 558 } else if (w.getNode(nl) == c.getNode(cl)) { 559 mode = 22; 560 } else if (w.getNode(0) == c.getNode(0)) { 561 mode = 11; 562 } else if (w.getNode(0) == c.getNode(cl)) { 563 mode = 12; 564 } 565 } else { 566 nl = nodes.size()-1; 567 if (nodes.get(nl) == c.getNode(0)) { 568 mode = 21; 569 } else if (nodes.get(0) == c.getNode(cl)) { 570 mode = 12; 571 } else if (nodes.get(0) == c.getNode(0)) { 572 mode = 11; 573 } else if (nodes.get(nl) == c.getNode(cl)) { 574 mode = 22; 575 } 576 } 577 if (mode != 0) { 578 joinArray[i] = null; 579 joined = true; 580 if (c.isSelected()) { 581 selected = true; 582 } 583 --left; 584 if (nodes == null) { 585 nodes = w.getNodes(); 586 wayIds.add(w.getUniqueId()); 587 } 588 nodes.remove((mode == 21 || mode == 22) ? nl : 0); 589 if (mode == 21) { 590 nodes.addAll(c.getNodes()); 591 } else if (mode == 12) { 592 nodes.addAll(0, c.getNodes()); 593 } else if (mode == 22) { 594 for (Node node : c.getNodes()) { 595 nodes.add(nl, node); 596 } 597 } else /* mode == 11 */ { 598 for (Node node : c.getNodes()) { 599 nodes.add(0, node); 600 } 601 } 602 wayIds.add(c.getUniqueId()); 603 } 604 } 605 } 606 } 607 } 608 609 if (nodes == null && w != null) { 610 nodes = w.getNodes(); 611 wayIds.add(w.getUniqueId()); 612 } 613 614 if (nodes != null) { 615 result.add(new JoinedWay(nodes, wayIds, selected)); 616 } 617 } 618 619 return result; 620 } 621 622 public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) { 623 // First try to test only bbox, use precise testing only if we don't get unique result 624 Rectangle2D innerBox = inner.getBounds(); 625 PolyData insidePolygon = null; 626 PolyData intersectingPolygon = null; 627 int insideCount = 0; 628 int intersectingCount = 0; 629 630 for (PolyData outer: outerPolygons) { 631 if (outer.getBounds().contains(innerBox)) { 632 insidePolygon = outer; 633 insideCount++; 634 } else if (outer.getBounds().intersects(innerBox)) { 635 intersectingPolygon = outer; 636 intersectingCount++; 637 } 638 } 639 640 if (insideCount == 1) 641 return insidePolygon; 642 else if (intersectingCount == 1) 643 return intersectingPolygon; 644 645 PolyData result = null; 646 for (PolyData combined : outerPolygons) { 647 if (combined.contains(inner.poly) != Intersection.OUTSIDE 648 && (result == null || result.contains(combined.poly) == Intersection.INSIDE)) { 649 result = combined; 650 } 651 } 652 return result; 653 } 654 655 private void addInnerToOuters(List<PolyData> innerPolygons, List<PolyData> outerPolygons) { 656 if (innerPolygons.isEmpty()) { 657 combinedPolygons.addAll(outerPolygons); 658 } else if (outerPolygons.size() == 1) { 659 PolyData combinedOuter = new PolyData(outerPolygons.get(0)); 660 for (PolyData inner: innerPolygons) { 661 combinedOuter.addInner(inner); 662 } 663 combinedPolygons.add(combinedOuter); 664 } else { 665 for (PolyData outer: outerPolygons) { 666 combinedPolygons.add(new PolyData(outer)); 667 } 668 669 for (PolyData pdInner: innerPolygons) { 670 PolyData o = findOuterPolygon(pdInner, combinedPolygons); 671 if (o == null) { 672 o = outerPolygons.get(0); 673 } 674 o.addInner(pdInner); 675 } 676 } 677 } 678 679 /** 680 * Replies the list of outer ways. 681 * @return the list of outer ways 682 */ 683 public List<Way> getOuterWays() { 684 return Collections.unmodifiableList(outerWays); 685 } 686 687 /** 688 * Replies the list of inner ways. 689 * @return the list of inner ways 690 */ 691 public List<Way> getInnerWays() { 692 return Collections.unmodifiableList(innerWays); 693 } 694 695 /** 696 * Replies the list of combined polygons. 697 * @return the list of combined polygons 698 */ 699 public List<PolyData> getCombinedPolygons() { 700 return Collections.unmodifiableList(combinedPolygons); 701 } 702 703 /** 704 * Replies the list of inner polygons. 705 * @return the list of inner polygons 706 */ 707 public List<PolyData> getInnerPolygons() { 708 final List<PolyData> innerPolygons = new ArrayList<>(); 709 createPolygons(innerWays, innerPolygons); 710 return innerPolygons; 711 } 712 713 /** 714 * Replies the list of outer polygons. 715 * @return the list of outer polygons 716 */ 717 public List<PolyData> getOuterPolygons() { 718 final List<PolyData> outerPolygons = new ArrayList<>(); 719 createPolygons(outerWays, outerPolygons); 720 return outerPolygons; 721 } 722 723 /** 724 * Returns the start and end node of non-closed rings. 725 * @return the start and end node of non-closed rings. 726 */ 727 public List<Node> getOpenEnds() { 728 return Collections.unmodifiableList(openEnds); 729 } 730}