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