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