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 030public 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 EastNorth 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 Main.warn("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 if (!wayIds.isEmpty()) { 299 List<Way> waysToJoin = new ArrayList<Way>(); 300 for (Long wayId : wayIds) { 301 Way w = (Way) ds.getPrimitiveById(wayId, OsmPrimitiveType.WAY); 302 if (w != null && w.getNodesCount() > 0) { // fix #7173 (empty ways on purge) 303 waysToJoin.add(w); 304 } 305 } 306 if (!waysToJoin.isEmpty()) { 307 nodes.addAll(joinWays(waysToJoin).iterator().next().getNodes()); 308 } 309 } 310 resetPoly(); 311 } 312 } 313 314 private void resetPoly() { 315 poly.reset(); 316 buildPoly(); 317 bounds = null; 318 } 319 320 public void nodeMoved(NodeMovedEvent event) { 321 final Node n = event.getNode(); 322 boolean innerChanged = false; 323 for (PolyData inner : inners) { 324 if (inner.nodes.contains(n)) { 325 inner.resetPoly(); 326 innerChanged = true; 327 } 328 } 329 if (nodes.contains(n) || innerChanged) { 330 resetPoly(); 331 } 332 } 333 334 public void wayNodesChanged(WayNodesChangedEvent event) { 335 final Long wayId = event.getChangedWay().getUniqueId(); 336 boolean innerChanged = false; 337 for (PolyData inner : inners) { 338 if (inner.wayIds.contains(wayId)) { 339 inner.resetNodes(event.getDataset()); 340 innerChanged = true; 341 } 342 } 343 if (wayIds.contains(wayId) || innerChanged) { 344 resetNodes(event.getDataset()); 345 } 346 } 347 } 348 349 private final List<Way> innerWays = new ArrayList<Way>(); 350 private final List<Way> outerWays = new ArrayList<Way>(); 351 private final List<PolyData> innerPolygons = new ArrayList<PolyData>(); 352 private final List<PolyData> outerPolygons = new ArrayList<PolyData>(); 353 private final List<PolyData> combinedPolygons = new ArrayList<PolyData>(); 354 355 private boolean incomplete; 356 357 public Multipolygon(Relation r) { 358 load(r); 359 } 360 361 private void load(Relation r) { 362 MultipolygonRoleMatcher matcher = getMultipolygonRoleMatcher(); 363 364 // Fill inner and outer list with valid ways 365 for (RelationMember m : r.getMembers()) { 366 if (m.getMember().isIncomplete()) { 367 this.incomplete = true; 368 } else if (m.getMember().isDrawable()) { 369 if (m.isWay()) { 370 Way w = m.getWay(); 371 372 if (w.getNodesCount() < 2) { 373 continue; 374 } 375 376 if (matcher.isInnerRole(m.getRole())) { 377 innerWays.add(w); 378 } else if (matcher.isOuterRole(m.getRole())) { 379 outerWays.add(w); 380 } else if (!m.hasRole()) { 381 outerWays.add(w); 382 } // Remaining roles ignored 383 } // Non ways ignored 384 } 385 } 386 387 createPolygons(innerWays, innerPolygons); 388 createPolygons(outerWays, outerPolygons); 389 if (!outerPolygons.isEmpty()) { 390 addInnerToOuters(); 391 } 392 } 393 394 public final boolean isIncomplete() { 395 return incomplete; 396 } 397 398 private void createPolygons(List<Way> ways, List<PolyData> result) { 399 List<Way> waysToJoin = new ArrayList<Way>(); 400 for (Way way: ways) { 401 if (way.isClosed()) { 402 result.add(new PolyData(way)); 403 } else { 404 waysToJoin.add(way); 405 } 406 } 407 408 for (JoinedWay jw: joinWays(waysToJoin)) { 409 result.add(new PolyData(jw)); 410 } 411 } 412 413 public static Collection<JoinedWay> joinWays(Collection<Way> waysToJoin) 414 { 415 final Collection<JoinedWay> result = new ArrayList<JoinedWay>(); 416 final Way[] joinArray = waysToJoin.toArray(new Way[waysToJoin.size()]); 417 int left = waysToJoin.size(); 418 while (left > 0) { 419 Way w = null; 420 boolean selected = false; 421 List<Node> nodes = null; 422 Set<Long> wayIds = new HashSet<Long>(); 423 boolean joined = true; 424 while (joined && left > 0) { 425 joined = false; 426 for (int i = 0; i < joinArray.length && left != 0; ++i) { 427 if (joinArray[i] != null) { 428 Way c = joinArray[i]; 429 if (w == null) { 430 w = c; 431 selected = w.isSelected(); 432 joinArray[i] = null; 433 --left; 434 } else { 435 int mode = 0; 436 int cl = c.getNodesCount()-1; 437 int nl; 438 if (nodes == null) { 439 nl = w.getNodesCount()-1; 440 if (w.getNode(nl) == c.getNode(0)) { 441 mode = 21; 442 } else if (w.getNode(nl) == c.getNode(cl)) { 443 mode = 22; 444 } else if (w.getNode(0) == c.getNode(0)) { 445 mode = 11; 446 } else if (w.getNode(0) == c.getNode(cl)) { 447 mode = 12; 448 } 449 } else { 450 nl = nodes.size()-1; 451 if (nodes.get(nl) == c.getNode(0)) { 452 mode = 21; 453 } else if (nodes.get(0) == c.getNode(cl)) { 454 mode = 12; 455 } else if (nodes.get(0) == c.getNode(0)) { 456 mode = 11; 457 } else if (nodes.get(nl) == c.getNode(cl)) { 458 mode = 22; 459 } 460 } 461 if (mode != 0) { 462 joinArray[i] = null; 463 joined = true; 464 if (c.isSelected()) { 465 selected = true; 466 } 467 --left; 468 if (nodes == null) { 469 nodes = w.getNodes(); 470 wayIds.add(w.getUniqueId()); 471 } 472 nodes.remove((mode == 21 || mode == 22) ? nl : 0); 473 if (mode == 21) { 474 nodes.addAll(c.getNodes()); 475 } else if (mode == 12) { 476 nodes.addAll(0, c.getNodes()); 477 } else if (mode == 22) { 478 for (Node node : c.getNodes()) { 479 nodes.add(nl, node); 480 } 481 } else /* mode == 11 */ { 482 for (Node node : c.getNodes()) { 483 nodes.add(0, node); 484 } 485 } 486 wayIds.add(c.getUniqueId()); 487 } 488 } 489 } 490 } 491 } 492 493 if (nodes == null) { 494 nodes = w.getNodes(); 495 wayIds.add(w.getUniqueId()); 496 } 497 498 result.add(new JoinedWay(nodes, wayIds, selected)); 499 } 500 501 return result; 502 } 503 504 public PolyData findOuterPolygon(PolyData inner, List<PolyData> outerPolygons) { 505 506 // First try to test only bbox, use precise testing only if we don't get unique result 507 Rectangle2D innerBox = inner.getBounds(); 508 PolyData insidePolygon = null; 509 PolyData intersectingPolygon = null; 510 int insideCount = 0; 511 int intersectingCount = 0; 512 513 for (PolyData outer: outerPolygons) { 514 if (outer.getBounds().contains(innerBox)) { 515 insidePolygon = outer; 516 insideCount++; 517 } else if (outer.getBounds().intersects(innerBox)) { 518 intersectingPolygon = outer; 519 intersectingCount++; 520 } 521 } 522 523 if (insideCount == 1) 524 return insidePolygon; 525 else if (intersectingCount == 1) 526 return intersectingPolygon; 527 528 PolyData result = null; 529 for (PolyData combined : outerPolygons) { 530 Intersection c = combined.contains(inner.poly); 531 if (c != Intersection.OUTSIDE) 532 { 533 if (result == null || result.contains(combined.poly) != Intersection.INSIDE) { 534 result = combined; 535 } 536 } 537 } 538 return result; 539 } 540 541 private void addInnerToOuters() { 542 543 if (innerPolygons.isEmpty()) { 544 combinedPolygons.addAll(outerPolygons); 545 } else if (outerPolygons.size() == 1) { 546 PolyData combinedOuter = new PolyData(outerPolygons.get(0)); 547 for (PolyData inner: innerPolygons) { 548 combinedOuter.addInner(inner); 549 } 550 combinedPolygons.add(combinedOuter); 551 } else { 552 for (PolyData outer: outerPolygons) { 553 combinedPolygons.add(new PolyData(outer)); 554 } 555 556 for (PolyData pdInner: innerPolygons) { 557 PolyData o = findOuterPolygon(pdInner, combinedPolygons); 558 if (o == null) { 559 o = outerPolygons.get(0); 560 } 561 o.addInner(pdInner); 562 } 563 } 564 565 // Clear inner and outer polygons to reduce memory footprint 566 innerPolygons.clear(); 567 outerPolygons.clear(); 568 } 569 570 public List<Way> getOuterWays() { 571 return outerWays; 572 } 573 574 public List<Way> getInnerWays() { 575 return innerWays; 576 } 577 578 public List<PolyData> getCombinedPolygons() { 579 return combinedPolygons; 580 } 581}