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