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 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 private static MultipolygonRoleMatcher getMultipolygonRoleMatcher() { 152 if (roleMatcher == null) { 153 roleMatcher = new MultipolygonRoleMatcher(); 154 if (Main.pref != null){ 155 roleMatcher.initFromPreferences(); 156 Main.pref.addPreferenceChangeListener(roleMatcher); 157 } 158 } 159 return roleMatcher; 160 } 161 162 public static class JoinedWay { 163 private final List<Node> nodes; 164 private final Collection<Long> wayIds; 165 private final boolean selected; 166 167 public JoinedWay(List<Node> nodes, Collection<Long> wayIds, boolean selected) { 168 this.nodes = nodes; 169 this.wayIds = wayIds; 170 this.selected = selected; 171 } 172 173 public List<Node> getNodes() { 174 return nodes; 175 } 176 177 public Collection<Long> getWayIds() { 178 return wayIds; 179 } 180 181 public boolean isSelected() { 182 return selected; 183 } 184 185 public boolean isClosed() { 186 return nodes.isEmpty() || nodes.get(nodes.size() - 1).equals(nodes.get(0)); 187 } 188 } 189 190 public static class PolyData { 191 public enum Intersection {INSIDE, OUTSIDE, CROSSING} 192 193 private final Path2D.Double poly; 194 public boolean selected; 195 private Rectangle2D bounds; 196 private final Collection<Long> wayIds; 197 private final List<Node> nodes; 198 private final List<PolyData> inners; 199 200 public PolyData(Way closedWay) { 201 this(closedWay.getNodes(), closedWay.isSelected(), Collections.singleton(closedWay.getUniqueId())); 202 } 203 204 public PolyData(JoinedWay joinedWay) { 205 this(joinedWay.getNodes(), joinedWay.isSelected(), joinedWay.getWayIds()); 206 } 207 208 private PolyData(List<Node> nodes, boolean selected, Collection<Long> wayIds) { 209 this.wayIds = Collections.unmodifiableCollection(wayIds); 210 this.nodes = new ArrayList<>(nodes); 211 this.selected = selected; 212 this.inners = new ArrayList<>(); 213 this.poly = new Path2D.Double(); 214 this.poly.setWindingRule(Path2D.WIND_EVEN_ODD); 215 buildPoly(); 216 } 217 218 private void buildPoly() { 219 boolean initial = true; 220 for (Node n : nodes) { 221 EastNorth p = n.getEastNorth(); 222 if (p != null) { 223 if (initial) { 224 poly.moveTo(p.getX(), p.getY()); 225 initial = false; 226 } else { 227 poly.lineTo(p.getX(), p.getY()); 228 } 229 } 230 } 231 if (!initial) { // fix #7593 232 poly.closePath(); 233 } 234 for (PolyData inner : inners) { 235 appendInner(inner.poly); 236 } 237 } 238 239 public PolyData(PolyData copy) { 240 this.selected = copy.selected; 241 this.poly = (Double) copy.poly.clone(); 242 this.wayIds = Collections.unmodifiableCollection(copy.wayIds); 243 this.nodes = new ArrayList<>(copy.nodes); 244 this.inners = new ArrayList<>(copy.inners); 245 } 246 247 public Intersection contains(Path2D.Double p) { 248 int contains = 0; 249 int total = 0; 250 double[] coords = new double[6]; 251 for (PathIterator it = p.getPathIterator(null); !it.isDone(); it.next()) { 252 switch (it.currentSegment(coords)) { 253 case PathIterator.SEG_MOVETO: 254 case PathIterator.SEG_LINETO: 255 if (poly.contains(coords[0], coords[1])) { 256 contains++; 257 } 258 total++; 259 } 260 } 261 if (contains == total) return Intersection.INSIDE; 262 if (contains == 0) return Intersection.OUTSIDE; 263 return Intersection.CROSSING; 264 } 265 266 public void addInner(PolyData inner) { 267 inners.add(inner); 268 appendInner(inner.poly); 269 } 270 271 private void appendInner(Path2D.Double inner) { 272 poly.append(inner.getPathIterator(null), false); 273 } 274 275 public Path2D.Double get() { 276 return poly; 277 } 278 279 public Rectangle2D getBounds() { 280 if (bounds == null) { 281 bounds = poly.getBounds2D(); 282 } 283 return bounds; 284 } 285 286 public Collection<Long> getWayIds() { 287 return wayIds; 288 } 289 290 private void resetNodes(DataSet dataSet) { 291 if (!nodes.isEmpty()) { 292 DataSet ds = dataSet; 293 // Find DataSet (can be null for several nodes when undoing nodes creation, see #7162) 294 for (Iterator<Node> it = nodes.iterator(); it.hasNext() && ds == null; ) { 295 ds = it.next().getDataSet(); 296 } 297 nodes.clear(); 298 if (ds == null) { 299 // DataSet still not found. This should not happen, but a warning does no harm 300 Main.warn("DataSet not found while resetting nodes in Multipolygon. This should not happen, you may report it to JOSM developers."); 301 } else if (wayIds.size() == 1) { 302 Way w = (Way) ds.getPrimitiveById(wayIds.iterator().next(), OsmPrimitiveType.WAY); 303 nodes.addAll(w.getNodes()); 304 } else if (!wayIds.isEmpty()) { 305 List<Way> waysToJoin = new ArrayList<>(); 306 for (Long wayId : wayIds) { 307 Way w = (Way) ds.getPrimitiveById(wayId, OsmPrimitiveType.WAY); 308 if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge) 309 waysToJoin.add(w); 310 } 311 } 312 if (!waysToJoin.isEmpty()) { 313 nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes()); 314 } 315 } 316 resetPoly(); 317 } 318 } 319 320 private void resetPoly() { 321 poly.reset(); 322 buildPoly(); 323 bounds = null; 324 } 325 326 public void nodeMoved(NodeMovedEvent event) { 327 final Node n = event.getNode(); 328 boolean innerChanged = false; 329 for (PolyData inner : inners) { 330 if (inner.nodes.contains(n)) { 331 inner.resetPoly(); 332 innerChanged = true; 333 } 334 } 335 if (nodes.contains(n) || innerChanged) { 336 resetPoly(); 337 } 338 } 339 340 public void wayNodesChanged(WayNodesChangedEvent event) { 341 final Long wayId = event.getChangedWay().getUniqueId(); 342 boolean innerChanged = false; 343 for (PolyData inner : inners) { 344 if (inner.wayIds.contains(wayId)) { 345 inner.resetNodes(event.getDataset()); 346 innerChanged = true; 347 } 348 } 349 if (wayIds.contains(wayId) || innerChanged) { 350 resetNodes(event.getDataset()); 351 } 352 } 353 } 354 355 private final List<Way> innerWays = new ArrayList<>(); 356 private final List<Way> outerWays = new ArrayList<>(); 357 private final List<PolyData> innerPolygons = new ArrayList<>(); 358 private final List<PolyData> outerPolygons = new ArrayList<>(); 359 private final List<PolyData> combinedPolygons = new ArrayList<>(); 360 361 private boolean incomplete; 362 363 public Multipolygon(Relation r) { 364 load(r); 365 } 366 367 private final void load(Relation r) { 368 MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher(); 369 370 // Fill inner and outer list with valid ways 371 for (RelationMember m : r.getMembers()) { 372 if (m.getMember().isIncomplete()) { 373 this.incomplete = true; 374 } else if (m.getMember().isDrawable()) { 375 if (m.isWay()) { 376 Way w = m.getWay(); 377 378 if (w.getNodesCount() < 2) { 379 continue; 380 } 381 382 if (matcher.isInnerRole(m.getRole())) { 383 innerWays.add(w); 384 } else if (matcher.isOuterRole(m.getRole())) { 385 outerWays.add(w); 386 } else if (!m.hasRole()) { 387 outerWays.add(w); 388 } // Remaining roles ignored 389 } // Non ways ignored 390 } 391 } 392 393 createPolygons(innerWays, innerPolygons); 394 createPolygons(outerWays, outerPolygons); 395 if (!outerPolygons.isEmpty()) { 396 addInnerToOuters(); 397 } 398 } 399 400 public final boolean isIncomplete() { 401 return incomplete; 402 } 403 404 private void createPolygons(List<Way> ways, List<PolyData> result) { 405 List<Way> waysToJoin = new ArrayList<>(); 406 for (Way way: ways) { 407 if (way.isClosed()) { 408 result.add(new PolyData(way)); 409 } else { 410 waysToJoin.add(way); 411 } 412 } 413 414 for (JoinedWay jw: joinWays(waysToJoin)) { 415 result.add(new PolyData(jw)); 416 } 417 } 418 419 public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin) { 420 final Collection<JoinedWay> result = new ArrayList<>(); 421 final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]); 422 int left = waysToJoin.size(); 423 while (left > 0) { 424 Way w = null; 425 boolean selected = false; 426 List<Node> nodes = null; 427 Set<Long> wayIds = new HashSet<>(); 428 boolean joined = true; 429 while (joined && left > 0) { 430 joined = false; 431 for (int i = 0; i < joinArray.length && left != 0; ++i) { 432 if (joinArray[i] != null) { 433 Way c = joinArray[i]; 434 if (c.getNodesCount() == 0) { 435 continue; 436 } 437 if (w == null) { 438 w = c; 439 selected = w.isSelected(); 440 joinArray[i] = null; 441 --left; 442 } else { 443 int mode = 0; 444 int cl = c.getNodesCount()-1; 445 int nl; 446 if (nodes == null) { 447 nl = w.getNodesCount()-1; 448 if (w.getNode(nl) == c.getNode(0)) { 449 mode = 21; 450 } else if (w.getNode(nl) == c.getNode(cl)) { 451 mode = 22; 452 } else if (w.getNode(0) == c.getNode(0)) { 453 mode = 11; 454 } else if (w.getNode(0) == c.getNode(cl)) { 455 mode = 12; 456 } 457 } else { 458 nl = nodes.size()-1; 459 if (nodes.get(nl) == c.getNode(0)) { 460 mode = 21; 461 } else if (nodes.get(0) == c.getNode(cl)) { 462 mode = 12; 463 } else if (nodes.get(0) == c.getNode(0)) { 464 mode = 11; 465 } else if (nodes.get(nl) == c.getNode(cl)) { 466 mode = 22; 467 } 468 } 469 if (mode != 0) { 470 joinArray[i] = null; 471 joined = true; 472 if (c.isSelected()) { 473 selected = true; 474 } 475 --left; 476 if (nodes == null) { 477 nodes = w.getNodes(); 478 wayIds.add(w.getUniqueId()); 479 } 480 nodes.remove((mode == 21 || mode == 22) ? nl : 0); 481 if (mode == 21) { 482 nodes.addAll(c.getNodes()); 483 } else if (mode == 12) { 484 nodes.addAll(0, c.getNodes()); 485 } else if (mode == 22) { 486 for (Node node : c.getNodes()) { 487 nodes.add(nl, node); 488 } 489 } else /* mode == 11 */ { 490 for (Node node : c.getNodes()) { 491 nodes.add(0, node); 492 } 493 } 494 wayIds.add(c.getUniqueId()); 495 } 496 } 497 } 498 } 499 } 500 501 if (nodes == null && w != null) { 502 nodes = w.getNodes(); 503 wayIds.add(w.getUniqueId()); 504 } 505 506 result.add(new JoinedWay(nodes, wayIds, selected)); 507 } 508 509 return result; 510 } 511 512 public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) { 513 514 // First try to test only bbox, use precise testing only if we don't get unique result 515 Rectangle2D innerBox = inner.getBounds(); 516 PolyData insidePolygon = null; 517 PolyData intersectingPolygon = null; 518 int insideCount = 0; 519 int intersectingCount = 0; 520 521 for (PolyData outer: outerPolygons) { 522 if (outer.getBounds().contains(innerBox)) { 523 insidePolygon = outer; 524 insideCount++; 525 } else if (outer.getBounds().intersects(innerBox)) { 526 intersectingPolygon = outer; 527 intersectingCount++; 528 } 529 } 530 531 if (insideCount == 1) 532 return insidePolygon; 533 else if (intersectingCount == 1) 534 return intersectingPolygon; 535 536 PolyData result = null; 537 for (PolyData combined : outerPolygons) { 538 if (combined.contains(inner.poly) != Intersection.OUTSIDE) { 539 if (result == null || result.contains(combined.poly) == Intersection.INSIDE) { 540 result = combined; 541 } 542 } 543 } 544 return result; 545 } 546 547 private final void addInnerToOuters() { 548 549 if (innerPolygons.isEmpty()) { 550 combinedPolygons.addAll(outerPolygons); 551 } else if (outerPolygons.size() == 1) { 552 PolyData combinedOuter = new PolyData(outerPolygons.get(0)); 553 for (PolyData inner: innerPolygons) { 554 combinedOuter.addInner(inner); 555 } 556 combinedPolygons.add(combinedOuter); 557 } else { 558 for (PolyData outer: outerPolygons) { 559 combinedPolygons.add(new PolyData(outer)); 560 } 561 562 for (PolyData pdInner: innerPolygons) { 563 PolyData o = findOuterPolygon(pdInner, combinedPolygons); 564 if (o == null) { 565 o = outerPolygons.get(0); 566 } 567 o.addInner(pdInner); 568 } 569 } 570 571 // Clear inner and outer polygons to reduce memory footprint 572 innerPolygons.clear(); 573 outerPolygons.clear(); 574 } 575 576 /** 577 * Replies the list of outer ways. 578 * @return the list of outer ways 579 */ 580 public List<Way> getOuterWays() { 581 return outerWays; 582 } 583 584 /** 585 * Replies the list of inner ways. 586 * @return the list of inner ways 587 */ 588 public List<Way> getInnerWays() { 589 return innerWays; 590 } 591 592 public List<PolyData> getCombinedPolygons() { 593 return combinedPolygons; 594 } 595}