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