001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.actions; 003 004import static org.openstreetmap.josm.tools.I18n.marktr; 005import static org.openstreetmap.josm.tools.I18n.tr; 006import static org.openstreetmap.josm.tools.I18n.trn; 007 008import java.awt.event.ActionEvent; 009import java.awt.event.KeyEvent; 010import java.util.ArrayList; 011import java.util.Collection; 012import java.util.Collections; 013import java.util.HashMap; 014import java.util.HashSet; 015import java.util.LinkedHashSet; 016import java.util.LinkedList; 017import java.util.List; 018import java.util.Map; 019import java.util.Objects; 020import java.util.Set; 021import java.util.TreeMap; 022import java.util.stream.Collectors; 023 024import javax.swing.JOptionPane; 025 026import org.openstreetmap.josm.actions.ReverseWayAction.ReverseWayResult; 027import org.openstreetmap.josm.command.AddCommand; 028import org.openstreetmap.josm.command.ChangeMembersCommand; 029import org.openstreetmap.josm.command.ChangeNodesCommand; 030import org.openstreetmap.josm.command.ChangePropertyCommand; 031import org.openstreetmap.josm.command.Command; 032import org.openstreetmap.josm.command.DeleteCommand; 033import org.openstreetmap.josm.command.SequenceCommand; 034import org.openstreetmap.josm.command.SplitWayCommand; 035import org.openstreetmap.josm.data.UndoRedoHandler; 036import org.openstreetmap.josm.data.coor.EastNorth; 037import org.openstreetmap.josm.data.osm.AbstractPrimitive; 038import org.openstreetmap.josm.data.osm.DataSet; 039import org.openstreetmap.josm.data.osm.Node; 040import org.openstreetmap.josm.data.osm.NodePositionComparator; 041import org.openstreetmap.josm.data.osm.OsmPrimitive; 042import org.openstreetmap.josm.data.osm.Relation; 043import org.openstreetmap.josm.data.osm.RelationMember; 044import org.openstreetmap.josm.data.osm.TagCollection; 045import org.openstreetmap.josm.data.osm.Way; 046import org.openstreetmap.josm.gui.Notification; 047import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog; 048import org.openstreetmap.josm.gui.layer.OsmDataLayer; 049import org.openstreetmap.josm.tools.Geometry; 050import org.openstreetmap.josm.tools.JosmRuntimeException; 051import org.openstreetmap.josm.tools.Logging; 052import org.openstreetmap.josm.tools.Pair; 053import org.openstreetmap.josm.tools.Shortcut; 054import org.openstreetmap.josm.tools.UserCancelException; 055import org.openstreetmap.josm.tools.Utils; 056 057/** 058 * Join Areas (i.e. closed ways and multipolygons). 059 * @since 2575 060 */ 061public class JoinAreasAction extends JosmAction { 062 // This will be used to commit commands and unite them into one large command sequence at the end 063 private final transient LinkedList<Command> executedCmds = new LinkedList<>(); 064 private final transient LinkedList<Command> cmds = new LinkedList<>(); 065 private DataSet ds; 066 private final transient List<Relation> addedRelations = new LinkedList<>(); 067 private final boolean addUndoRedo; 068 069 /** 070 * This helper class describes join areas action result. 071 * @author viesturs 072 */ 073 public static class JoinAreasResult { 074 075 private final boolean hasChanges; 076 private final List<Multipolygon> polygons; 077 078 /** 079 * Constructs a new {@code JoinAreasResult}. 080 * @param hasChanges whether the result has changes 081 * @param polygons the result polygons, can be null 082 */ 083 public JoinAreasResult(boolean hasChanges, List<Multipolygon> polygons) { 084 this.hasChanges = hasChanges; 085 this.polygons = polygons; 086 } 087 088 /** 089 * Determines if the result has changes. 090 * @return {@code true} if the result has changes 091 */ 092 public final boolean hasChanges() { 093 return hasChanges; 094 } 095 096 /** 097 * Returns the result polygons, can be null. 098 * @return the result polygons, can be null 099 */ 100 public final List<Multipolygon> getPolygons() { 101 return polygons; 102 } 103 } 104 105 /** 106 * A record class to store how a multipolygon is constructed 107 */ 108 public static class Multipolygon { 109 private final Way outerWay; 110 private final List<Way> innerWays; 111 112 /** 113 * Constructs a new {@code Multipolygon}. 114 * @param way outer way 115 */ 116 public Multipolygon(Way way) { 117 outerWay = Objects.requireNonNull(way, "way"); 118 innerWays = new ArrayList<>(); 119 } 120 121 /** 122 * Returns the outer way. 123 * @return the outer way 124 */ 125 public final Way getOuterWay() { 126 return outerWay; 127 } 128 129 /** 130 * Returns the inner ways. 131 * @return the inner ways 132 */ 133 public final List<Way> getInnerWays() { 134 return innerWays; 135 } 136 } 137 138 // HelperClass 139 // Saves a relation and a role an OsmPrimitive was part of until it was stripped from all relations 140 private static class RelationRole { 141 public final Relation rel; 142 public final String role; 143 144 RelationRole(Relation rel, String role) { 145 this.rel = rel; 146 this.role = role; 147 } 148 149 @Override 150 public int hashCode() { 151 return Objects.hash(rel, role); 152 } 153 154 @Override 155 public boolean equals(Object other) { 156 if (this == other) return true; 157 if (other == null || getClass() != other.getClass()) return false; 158 RelationRole that = (RelationRole) other; 159 return Objects.equals(rel, that.rel) && 160 Objects.equals(role, that.role); 161 } 162 } 163 164 /** 165 * HelperClass - saves a way and the "inside" side. 166 * <p> 167 * insideToTheLeft: if true left side is "in", false -right side is "in". 168 * Left and right are determined along the orientation of way. 169 */ 170 public static class WayInPolygon { 171 public final Way way; 172 public boolean insideToTheRight; 173 174 public WayInPolygon(Way way, boolean insideRight) { 175 this.way = way; 176 this.insideToTheRight = insideRight; 177 } 178 179 @Override 180 public int hashCode() { 181 return Objects.hash(way, insideToTheRight); 182 } 183 184 @Override 185 public boolean equals(Object other) { 186 if (this == other) return true; 187 if (other == null || getClass() != other.getClass()) return false; 188 WayInPolygon that = (WayInPolygon) other; 189 return insideToTheRight == that.insideToTheRight && 190 Objects.equals(way, that.way); 191 } 192 193 @Override 194 public String toString() { 195 return "w" + way.getUniqueId() + " " + way.getNodesCount() + " nodes"; 196 } 197 } 198 199 /** 200 * This helper class describes a polygon, assembled from several ways. 201 * @author viesturs 202 * 203 */ 204 public static class AssembledPolygon { 205 public List<WayInPolygon> ways; 206 207 public AssembledPolygon(List<WayInPolygon> boundary) { 208 this.ways = boundary; 209 } 210 211 public List<Node> getNodes() { 212 List<Node> nodes = new ArrayList<>(); 213 for (WayInPolygon way : this.ways) { 214 //do not add the last node as it will be repeated in the next way 215 if (way.insideToTheRight) { 216 for (int pos = 0; pos < way.way.getNodesCount() - 1; pos++) { 217 nodes.add(way.way.getNode(pos)); 218 } 219 } else { 220 for (int pos = way.way.getNodesCount() - 1; pos > 0; pos--) { 221 nodes.add(way.way.getNode(pos)); 222 } 223 } 224 } 225 226 return nodes; 227 } 228 229 /** 230 * Inverse inside and outside 231 */ 232 public void reverse() { 233 for (WayInPolygon way: ways) { 234 way.insideToTheRight = !way.insideToTheRight; 235 } 236 Collections.reverse(ways); 237 } 238 } 239 240 /** 241 * A multipolygon with a list of inner ways and an assembled polygon for the outer way 242 */ 243 public static class AssembledMultipolygon { 244 /** The outer way of the multipolygon */ 245 public AssembledPolygon outerWay; 246 /** The inner polygons of the multipolygon */ 247 public List<AssembledPolygon> innerWays; 248 249 /** 250 * Create a new {@link AssembledMultipolygon} 251 * @param way The outer way 252 */ 253 public AssembledMultipolygon(AssembledPolygon way) { 254 outerWay = way; 255 innerWays = new ArrayList<>(); 256 } 257 } 258 259 /** 260 * This helper class implements algorithm traversing through connected ways. 261 * Assumes you are going in clockwise orientation. 262 * @author viesturs 263 */ 264 private static class WayTraverser { 265 266 /** Set of {@link WayInPolygon} to be joined by walk algorithm */ 267 private final Set<WayInPolygon> availableWays; 268 /** Current state of walk algorithm */ 269 private WayInPolygon lastWay; 270 /** Direction of current way */ 271 private boolean lastWayReverse; 272 273 /** Constructor 274 * @param ways available ways 275 */ 276 WayTraverser(Collection<WayInPolygon> ways) { 277 availableWays = new LinkedHashSet<>(ways); 278 lastWay = null; 279 } 280 281 /** 282 * Remove ways from available ways 283 * @param ways Collection of WayInPolygon 284 */ 285 public void removeWays(Collection<WayInPolygon> ways) { 286 availableWays.removeAll(ways); 287 } 288 289 /** 290 * Remove a single way from available ways 291 * @param way WayInPolygon 292 */ 293 public void removeWay(WayInPolygon way) { 294 availableWays.remove(way); 295 } 296 297 /** 298 * Reset walk algorithm to a new start point 299 * @param way New start point 300 */ 301 public void setStartWay(WayInPolygon way) { 302 lastWay = way; 303 lastWayReverse = !way.insideToTheRight; 304 } 305 306 /** 307 * Reset walk algorithm to a new start point. 308 * @return The new start point or null if no available way remains 309 */ 310 public WayInPolygon startNewWay() { 311 if (availableWays.isEmpty()) { 312 lastWay = null; 313 } else { 314 lastWay = availableWays.iterator().next(); 315 lastWayReverse = !lastWay.insideToTheRight; 316 } 317 318 return lastWay; 319 } 320 321 /** 322 * Walking through {@link WayInPolygon} segments, head node is the current position 323 * @return Head node 324 */ 325 private Node getHeadNode() { 326 return !lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode(); 327 } 328 329 /** 330 * Node just before head node. 331 * @return Previous node 332 */ 333 private Node getPrevNode() { 334 return !lastWayReverse ? lastWay.way.getNode(lastWay.way.getNodesCount() - 2) : lastWay.way.getNode(1); 335 } 336 337 /** 338 * Returns oriented angle (N1N2, N1N3) in range [0; 2*Math.PI[ 339 * @param n1 first node 340 * @param n2 second node 341 * @param n3 third node 342 * @return oriented angle (N1N2, N1N3) in range [0; 2*Math.PI[ 343 */ 344 private static double getAngle(Node n1, Node n2, Node n3) { 345 EastNorth en1 = n1.getEastNorth(); 346 EastNorth en2 = n2.getEastNorth(); 347 EastNorth en3 = n3.getEastNorth(); 348 double angle = Math.atan2(en3.getY() - en1.getY(), en3.getX() - en1.getX()) - 349 Math.atan2(en2.getY() - en1.getY(), en2.getX() - en1.getX()); 350 while (angle >= 2*Math.PI) { 351 angle -= 2*Math.PI; 352 } 353 while (angle < 0) { 354 angle += 2*Math.PI; 355 } 356 return angle; 357 } 358 359 /** 360 * Get the next way creating a clockwise path, ensure it is the most right way. #7959 361 * @return The next way. 362 */ 363 public WayInPolygon walk() { 364 Node headNode = getHeadNode(); 365 Node prevNode = getPrevNode(); 366 367 double headAngle = Math.atan2(headNode.getEastNorth().east() - prevNode.getEastNorth().east(), 368 headNode.getEastNorth().north() - prevNode.getEastNorth().north()); 369 double bestAngle = 0; 370 371 //find best next way 372 WayInPolygon bestWay = null; 373 boolean bestWayReverse = false; 374 375 for (WayInPolygon way : availableWays) { 376 Node nextNode; 377 378 // Check for a connected way 379 if (way.way.firstNode().equals(headNode) && way.insideToTheRight) { 380 nextNode = way.way.getNode(1); 381 } else if (way.way.lastNode().equals(headNode) && !way.insideToTheRight) { 382 nextNode = way.way.getNode(way.way.getNodesCount() - 2); 383 } else { 384 continue; 385 } 386 387 if (nextNode == prevNode) { 388 // go back 389 lastWay = way; 390 lastWayReverse = !way.insideToTheRight; 391 return lastWay; 392 } 393 394 double angle = Math.atan2(nextNode.getEastNorth().east() - headNode.getEastNorth().east(), 395 nextNode.getEastNorth().north() - headNode.getEastNorth().north()) - headAngle; 396 if (angle > Math.PI) 397 angle -= 2*Math.PI; 398 if (angle <= -Math.PI) 399 angle += 2*Math.PI; 400 401 // Now we have a valid candidate way, is it better than the previous one ? 402 if (bestWay == null || angle > bestAngle) { 403 //the new way is better 404 bestWay = way; 405 bestWayReverse = !way.insideToTheRight; 406 bestAngle = angle; 407 } 408 } 409 410 lastWay = bestWay; 411 lastWayReverse = bestWayReverse; 412 return lastWay; 413 } 414 415 /** 416 * Search for another way coming to the same head node at left side from last way. #9951 417 * @return left way or null if none found 418 */ 419 public WayInPolygon leftComingWay() { 420 Node headNode = getHeadNode(); 421 Node prevNode = getPrevNode(); 422 423 WayInPolygon mostLeft = null; // most left way connected to head node 424 boolean comingToHead = false; // true if candidate come to head node 425 double angle = 2*Math.PI; 426 427 for (WayInPolygon candidateWay : availableWays) { 428 boolean candidateComingToHead; 429 Node candidatePrevNode; 430 431 if (candidateWay.way.firstNode().equals(headNode)) { 432 candidateComingToHead = !candidateWay.insideToTheRight; 433 candidatePrevNode = candidateWay.way.getNode(1); 434 } else if (candidateWay.way.lastNode().equals(headNode)) { 435 candidateComingToHead = candidateWay.insideToTheRight; 436 candidatePrevNode = candidateWay.way.getNode(candidateWay.way.getNodesCount() - 2); 437 } else 438 continue; 439 if (candidateComingToHead && candidateWay.equals(lastWay)) 440 continue; 441 442 double candidateAngle = getAngle(headNode, candidatePrevNode, prevNode); 443 444 if (mostLeft == null || candidateAngle < angle || (Utils.equalsEpsilon(candidateAngle, angle) && !candidateComingToHead)) { 445 // Candidate is most left 446 mostLeft = candidateWay; 447 comingToHead = candidateComingToHead; 448 angle = candidateAngle; 449 } 450 } 451 452 return comingToHead ? mostLeft : null; 453 } 454 } 455 456 /** 457 * Helper storage class for finding findOuterWays 458 * @author viesturs 459 */ 460 static class PolygonLevel { 461 public final int level; 462 public final AssembledMultipolygon pol; 463 464 PolygonLevel(AssembledMultipolygon pol, int level) { 465 this.pol = pol; 466 this.level = level; 467 } 468 } 469 470 /** 471 * Constructs a new {@code JoinAreasAction}. 472 */ 473 public JoinAreasAction() { 474 this(true); 475 } 476 477 /** 478 * Constructs a new {@code JoinAreasAction} with optional shortcut and adapters. 479 * @param addShortcutToolbarAdapters controls whether the shortcut should be registered or not, 480 * as for toolbar registration, adapters creation and undo/redo integration 481 * @since 11611 482 */ 483 public JoinAreasAction(boolean addShortcutToolbarAdapters) { 484 super(tr("Join overlapping Areas"), "joinareas", tr("Joins areas that overlap each other"), addShortcutToolbarAdapters ? 485 Shortcut.registerShortcut("tools:joinareas", tr("Tools: {0}", tr("Join overlapping Areas")), KeyEvent.VK_J, Shortcut.SHIFT) 486 : null, addShortcutToolbarAdapters, null, addShortcutToolbarAdapters); 487 addUndoRedo = addShortcutToolbarAdapters; 488 } 489 490 /** 491 * Gets called whenever the shortcut is pressed or the menu entry is selected. 492 * Checks whether the selected objects are suitable to join and joins them if so. 493 */ 494 @Override 495 public void actionPerformed(ActionEvent e) { 496 join(getLayerManager().getEditDataSet().getSelectedWays()); 497 clearFields(); 498 } 499 500 private void clearFields() { 501 ds = null; 502 cmds.clear(); 503 addedRelations.clear(); 504 } 505 506 /** 507 * Joins the given ways. 508 * @param ways Ways to join 509 * @since 7534 510 */ 511 public void join(Collection<Way> ways) { 512 clearFields(); 513 514 if (ways.isEmpty()) { 515 new Notification( 516 tr("Please select at least one closed way that should be joined.")) 517 .setIcon(JOptionPane.INFORMATION_MESSAGE) 518 .show(); 519 return; 520 } 521 522 List<Node> allNodes = new ArrayList<>(); 523 for (Way way : ways) { 524 if (!way.isClosed()) { 525 new Notification( 526 tr("One of the selected ways is not closed and therefore cannot be joined.")) 527 .setIcon(JOptionPane.INFORMATION_MESSAGE) 528 .show(); 529 return; 530 } 531 532 allNodes.addAll(way.getNodes()); 533 } 534 535 // TODO: Only display this warning when nodes outside dataSourceArea are deleted 536 boolean ok = checkAndConfirmOutlyingOperation("joinarea", tr("Join area confirmation"), 537 trn("The selected way has nodes which can have other referrers not yet downloaded.", 538 "The selected ways have nodes which can have other referrers not yet downloaded.", 539 ways.size()) + "<br/>" 540 + tr("This can lead to nodes being deleted accidentally.") + "<br/>" 541 + tr("Are you really sure to continue?") 542 + ' ' 543 + tr("Please abort if you are not sure"), 544 tr("The selected area is incomplete. Continue?"), 545 allNodes, null); 546 if (!ok) return; 547 548 //analyze multipolygon relations and collect all areas 549 List<Multipolygon> areas = collectMultipolygons(ways); 550 551 if (areas == null) 552 //too complex multipolygon relations found 553 return; 554 555 if (!testJoin(areas)) { 556 new Notification( 557 tr("No intersection found. Nothing was changed.")) 558 .setIcon(JOptionPane.INFORMATION_MESSAGE) 559 .show(); 560 return; 561 } 562 563 if (!resolveTagConflicts(areas)) 564 return; 565 //user canceled, do nothing. 566 567 try { 568 // Do the job of joining areas 569 JoinAreasResult result = joinAreas(areas); 570 571 if (result.hasChanges) { 572 // move tags from ways to newly created relations 573 // TODO: do we need to also move tags for the modified relations? 574 for (Relation r: addedRelations) { 575 cmds.addAll(CreateMultipolygonAction.removeTagsFromWaysIfNeeded(r)); 576 } 577 commitCommands(tr("Move tags from ways to relations")); 578 579 commitExecuted(); 580 581 if (result.polygons != null && ds != null) { 582 List<Way> allWays = new ArrayList<>(); 583 for (Multipolygon pol : result.polygons) { 584 allWays.add(pol.outerWay); 585 allWays.addAll(pol.innerWays); 586 } 587 ds.setSelected(allWays); 588 } 589 } else { 590 new Notification( 591 tr("No intersection found. Nothing was changed.")) 592 .setIcon(JOptionPane.INFORMATION_MESSAGE) 593 .show(); 594 } 595 } catch (UserCancelException exception) { 596 Logging.trace(exception); 597 tryUndo(); 598 } catch (JosmRuntimeException | IllegalArgumentException exception) { 599 Logging.trace(exception); 600 tryUndo(); 601 throw exception; 602 } 603 } 604 605 private void tryUndo() { 606 cmds.clear(); 607 if (!executedCmds.isEmpty()) { 608 // revert all executed commands 609 ds = executedCmds.getFirst().getAffectedDataSet(); 610 ds.update(() -> { 611 while (!executedCmds.isEmpty()) { 612 executedCmds.removeLast().undoCommand(); 613 } 614 }); 615 } 616 } 617 618 /** 619 * Tests if the areas have some intersections to join. 620 * @param areas Areas to test 621 * @return {@code true} if areas are joinable 622 */ 623 private boolean testJoin(List<Multipolygon> areas) { 624 List<Way> allStartingWays = new ArrayList<>(); 625 626 for (Multipolygon area : areas) { 627 allStartingWays.add(area.outerWay); 628 allStartingWays.addAll(area.innerWays); 629 } 630 631 //find intersection points 632 Set<Node> nodes = Geometry.addIntersections(allStartingWays, true, cmds); 633 return !nodes.isEmpty(); 634 } 635 636 /** 637 * Will join two or more overlapping areas 638 * @param areas list of areas to join 639 * @return new area formed. 640 * @throws UserCancelException if user cancels the operation 641 * @since 15852 : visibility changed from public to private 642 */ 643 private JoinAreasResult joinAreas(List<Multipolygon> areas) throws UserCancelException { 644 645 // see #11026 - Because <ways> is a dynamic filtered (on ways) of a filtered (on selected objects) collection, 646 // retrieve effective dataset before joining the ways (which affects the selection, thus, the <ways> collection) 647 // Dataset retrieving allows to call this code without relying on Main.getCurrentDataSet(), thus, on a mapview instance 648 if (!areas.isEmpty()) { 649 ds = areas.get(0).getOuterWay().getDataSet(); 650 } 651 652 boolean hasChanges = false; 653 654 List<Way> allStartingWays = new ArrayList<>(); 655 List<Way> innerStartingWays = new ArrayList<>(); 656 List<Way> outerStartingWays = new ArrayList<>(); 657 658 for (Multipolygon area : areas) { 659 outerStartingWays.add(area.outerWay); 660 innerStartingWays.addAll(area.innerWays); 661 } 662 663 allStartingWays.addAll(innerStartingWays); 664 allStartingWays.addAll(outerStartingWays); 665 666 //first remove nodes in the same coordinate 667 boolean removedDuplicates = removeDuplicateNodes(allStartingWays); 668 669 if (removedDuplicates) { 670 hasChanges = true; 671 Set<Node> oldNodes = new LinkedHashSet<>(); 672 allStartingWays.forEach(w -> oldNodes.addAll(w.getNodes())); 673 commitCommands(marktr("Removed duplicate nodes")); 674 // remove now unconnected nodes without tags 675 List<Node> toRemove = oldNodes.stream().filter( 676 n -> n.isReferrersDownloaded() && !n.hasKeys() && n.getReferrers().isEmpty()) 677 .collect(Collectors.toList()); 678 if (!toRemove.isEmpty()) { 679 cmds.add(new DeleteCommand(toRemove)); 680 commitCommands(marktr("Removed now unreferrenced nodes")); 681 } 682 } 683 684 //find intersection points 685 Set<Node> nodes = Geometry.addIntersections(allStartingWays, false, cmds); 686 687 //no intersections, return. 688 if (nodes.isEmpty()) 689 return new JoinAreasResult(hasChanges, null); 690 commitCommands(marktr("Added node on all intersections")); 691 692 List<RelationRole> relations = new ArrayList<>(); 693 694 // Remove ways from all relations so ways can be combined/split quietly 695 for (Way way : allStartingWays) { 696 relations.addAll(removeFromAllRelations(way)); 697 } 698 699 // Don't warn now, because it will really look corrupted 700 boolean warnAboutRelations = !relations.isEmpty() && allStartingWays.size() > 1; 701 702 List<WayInPolygon> preparedWays = new ArrayList<>(); 703 704 // maps oldest way referring to start of each part 705 Map<Node, Way> oldestWayMap = new HashMap<>(); 706 707 for (Way way : outerStartingWays) { 708 List<Way> splitWays = splitWayOnNodes(way, nodes, oldestWayMap); 709 preparedWays.addAll(markWayInsideSide(splitWays, false)); 710 } 711 712 for (Way way : innerStartingWays) { 713 List<Way> splitWays = splitWayOnNodes(way, nodes, oldestWayMap); 714 preparedWays.addAll(markWayInsideSide(splitWays, true)); 715 } 716 717 // Find boundary ways 718 List<Way> discardedWays = new ArrayList<>(); 719 List<AssembledPolygon> boundaries = findBoundaryPolygons(preparedWays, discardedWays); 720 721 // see #9599 722 if (discardedWays.stream().anyMatch(w -> !w.isNew())) { 723 for (AssembledPolygon ring : boundaries) { 724 for (int k = 0; k < ring.ways.size(); k++) { 725 WayInPolygon ringWay = ring.ways.get(k); 726 Way older = keepOlder(ringWay.way, oldestWayMap, discardedWays); 727 728 if (ringWay.way != older) { 729 WayInPolygon repl = new WayInPolygon(older, ringWay.insideToTheRight); 730 ring.ways.set(k, repl); 731 } 732 } 733 } 734 commitCommands(marktr("Keep older versions")); 735 } 736 737 //find polygons 738 List<AssembledMultipolygon> preparedPolygons = findPolygons(boundaries); 739 740 //assemble final polygons 741 List<Multipolygon> polygons = new ArrayList<>(); 742 Set<Relation> relationsToDelete = new LinkedHashSet<>(); 743 744 for (AssembledMultipolygon pol : preparedPolygons) { 745 746 //create the new ways 747 Multipolygon resultPol = joinPolygon(pol); 748 749 //create multipolygon relation, if necessary. 750 RelationRole ownMultipolygonRelation = addOwnMultipolygonRelation(resultPol.innerWays); 751 752 //add back the original relations, merged with our new multipolygon relation 753 fixRelations(relations, resultPol.outerWay, ownMultipolygonRelation, relationsToDelete); 754 755 //strip tags from inner ways 756 //TODO: preserve tags on existing inner ways 757 stripTags(resultPol.innerWays); 758 759 polygons.add(resultPol); 760 } 761 762 commitCommands(marktr("Assemble new polygons")); 763 764 for (Relation rel: relationsToDelete) { 765 cmds.add(new DeleteCommand(rel)); 766 } 767 768 commitCommands(marktr("Delete relations")); 769 770 // Delete the discarded inner ways 771 if (!discardedWays.isEmpty()) { 772 Command deleteCmd = DeleteCommand.delete(discardedWays, true); 773 if (deleteCmd != null) { 774 cmds.add(deleteCmd); 775 commitCommands(marktr("Delete Ways that are not part of an inner multipolygon")); 776 } 777 } 778 779 if (warnAboutRelations) { 780 new Notification( 781 tr("Some of the ways were part of relations that have been modified.<br>Please verify no errors have been introduced.")) 782 .setIcon(JOptionPane.INFORMATION_MESSAGE) 783 .setDuration(Notification.TIME_LONG) 784 .show(); 785 } 786 787 return new JoinAreasResult(true, polygons); 788 } 789 790 /** 791 * Create copy of given way using an older id so that we don't create a new way instead of a modified old one. 792 * @param way the way to check 793 * @param oldestWayMap nodes from old ways 794 * @param discardedWays collection of ways which will be deleted (modified) 795 * @return a copy of the way with an older id or the way itself 796 */ 797 private Way keepOlder(Way way, Map<Node, Way> oldestWayMap, List<Way> discardedWays) { 798 Way oldest = null; 799 for (Node n : way.getNodes()) { 800 Way orig = oldestWayMap .get(n); 801 if (orig != null && (oldest == null || oldest.getUniqueId() > orig.getUniqueId()) 802 && discardedWays.contains(orig)) { 803 oldest = orig; 804 } 805 } 806 if (oldest != null) { 807 discardedWays.remove(oldest); 808 discardedWays.add(way); 809 cmds.add(new ChangeNodesCommand(oldest, way.getNodes())); 810 return oldest; 811 } 812 return way; 813 } 814 815 /** 816 * Checks if tags of two given ways differ, and presents the user a dialog to solve conflicts 817 * @param polygons ways to check 818 * @return {@code true} if all conflicts are resolved, {@code false} if conflicts remain. 819 */ 820 private boolean resolveTagConflicts(List<Multipolygon> polygons) { 821 822 List<Way> ways = new ArrayList<>(); 823 824 for (Multipolygon pol : polygons) { 825 ways.add(pol.outerWay); 826 ways.addAll(pol.innerWays); 827 } 828 829 if (ways.size() < 2) { 830 return true; 831 } 832 833 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways); 834 try { 835 cmds.addAll(CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, ways)); 836 commitCommands(marktr("Fix tag conflicts")); 837 return true; 838 } catch (UserCancelException ex) { 839 Logging.trace(ex); 840 return false; 841 } 842 } 843 844 /** 845 * This method removes duplicate points (if any) from the input ways. 846 * @param ways the ways to process 847 * @return {@code true} if any changes where made 848 */ 849 private boolean removeDuplicateNodes(List<Way> ways) { 850 Map<Node, Node> nodeMap = new TreeMap<>(new NodePositionComparator()); 851 int totalWaysModified = 0; 852 853 for (Way way : ways) { 854 if (way.getNodes().size() < 2) { 855 continue; 856 } 857 858 List<Node> newNodes = new ArrayList<>(); 859 Node prevNode = null; 860 boolean modifyWay = false; 861 862 for (Node node : way.getNodes()) { 863 Node representator = nodeMap.get(node); 864 if (representator == null) { 865 //new node 866 nodeMap.put(node, node); 867 representator = node; 868 } else { 869 //node with same coordinates already exists, substitute with existing node 870 if (representator != node) { 871 modifyWay = true; 872 } 873 } 874 //avoid duplicate node 875 if (prevNode != representator) { 876 newNodes.add(representator); 877 prevNode = representator; 878 } else { 879 modifyWay = true; 880 } 881 } 882 883 if (modifyWay) { 884 885 if (newNodes.size() == 1) { //all nodes in the same coordinate - add one more node, to have closed way. 886 newNodes.add(newNodes.get(0)); 887 } 888 889 cmds.add(new ChangeNodesCommand(way, newNodes)); 890 ++totalWaysModified; 891 } 892 } 893 return totalWaysModified > 0; 894 } 895 896 /** 897 * Commits the command list with a description 898 * @param description The description of what the commands do 899 */ 900 private void commitCommands(String description) { 901 switch (cmds.size()) { 902 case 0: 903 return; 904 case 1: 905 commitCommand(cmds.getFirst()); 906 break; 907 default: 908 commitCommand(new SequenceCommand(tr(description), cmds)); 909 break; 910 } 911 912 cmds.clear(); 913 } 914 915 private void commitCommand(Command c) { 916 c.executeCommand(); 917 executedCmds.add(c); 918 } 919 920 /** 921 * Add all executed commands as one command to the undo stack without executing them again. 922 */ 923 private void commitExecuted() { 924 cmds.clear(); 925 if (addUndoRedo && !executedCmds.isEmpty()) { 926 UndoRedoHandler ur = UndoRedoHandler.getInstance(); 927 if (executedCmds.size() == 1) { 928 ur.add(executedCmds.getFirst(), false); 929 } else { 930 ur.add(new JoinAreaCommand(executedCmds), false); 931 } 932 } 933 executedCmds.clear(); 934 } 935 936 /** 937 * This method analyzes the way and assigns each part what direction polygon "inside" is. 938 * @param parts the split parts of the way 939 * @param isInner - if true, reverts the direction (for multipolygon islands) 940 * @return list of parts, marked with the inside orientation. 941 * @throws IllegalArgumentException if parts is empty or not circular 942 */ 943 private static List<WayInPolygon> markWayInsideSide(List<Way> parts, boolean isInner) { 944 945 //prepare next map 946 Map<Way, Way> nextWayMap = new HashMap<>(); 947 948 for (int pos = 0; pos < parts.size(); pos++) { 949 950 if (!parts.get(pos).lastNode().equals(parts.get((pos + 1) % parts.size()).firstNode())) 951 throw new IllegalArgumentException("Way not circular"); 952 953 nextWayMap.put(parts.get(pos), parts.get((pos + 1) % parts.size())); 954 } 955 956 //find the node with minimum y - it's guaranteed to be outer. (What about the south pole?) 957 Way topWay = null; 958 Node topNode = null; 959 int topIndex = 0; 960 double minY = Double.POSITIVE_INFINITY; 961 962 for (Way way : parts) { 963 for (int pos = 0; pos < way.getNodesCount(); pos++) { 964 Node node = way.getNode(pos); 965 966 if (node.getEastNorth().getY() < minY) { 967 minY = node.getEastNorth().getY(); 968 topWay = way; 969 topNode = node; 970 topIndex = pos; 971 } 972 } 973 } 974 975 if (topWay == null || topNode == null) { 976 throw new IllegalArgumentException(); 977 } 978 979 //get the upper way and it's orientation. 980 981 boolean wayClockwise; // orientation of the top way. 982 983 if (topNode.equals(topWay.firstNode()) || topNode.equals(topWay.lastNode())) { 984 Node headNode; // the node at junction 985 Node prevNode; // last node from previous path 986 987 //node is in split point - find the outermost way from this point 988 989 headNode = topNode; 990 //make a fake node that is downwards from head node (smaller Y). It will be a division point between paths. 991 prevNode = new Node(new EastNorth(headNode.getEastNorth().getX(), headNode.getEastNorth().getY() - 1e5)); 992 993 topWay = null; 994 wayClockwise = false; 995 Node bestWayNextNode = null; 996 997 for (Way way : parts) { 998 if (way.firstNode().equals(headNode)) { 999 Node nextNode = way.getNode(1); 1000 1001 if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { 1002 //the new way is better 1003 topWay = way; 1004 wayClockwise = true; 1005 bestWayNextNode = nextNode; 1006 } 1007 } 1008 1009 if (way.lastNode().equals(headNode)) { 1010 //end adjacent to headNode 1011 Node nextNode = way.getNode(way.getNodesCount() - 2); 1012 1013 if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { 1014 //the new way is better 1015 topWay = way; 1016 wayClockwise = false; 1017 bestWayNextNode = nextNode; 1018 } 1019 } 1020 } 1021 } else { 1022 //node is inside way - pick the clockwise going end. 1023 Node prev = topWay.getNode(topIndex - 1); 1024 Node next = topWay.getNode(topIndex + 1); 1025 1026 //there will be no parallel segments in the middle of way, so all fine. 1027 wayClockwise = Geometry.angleIsClockwise(prev, topNode, next); 1028 } 1029 1030 Way curWay = topWay; 1031 boolean curWayInsideToTheRight = wayClockwise ^ isInner; 1032 List<WayInPolygon> result = new ArrayList<>(); 1033 1034 //iterate till full circle is reached 1035 while (curWay != null) { 1036 1037 //add cur way 1038 WayInPolygon resultWay = new WayInPolygon(curWay, curWayInsideToTheRight); 1039 result.add(resultWay); 1040 1041 //process next way 1042 Way nextWay = nextWayMap.get(curWay); 1043 Node prevNode = curWay.getNode(curWay.getNodesCount() - 2); 1044 Node headNode = curWay.lastNode(); 1045 Node nextNode = nextWay.getNode(1); 1046 1047 if (nextWay == topWay) { 1048 //full loop traversed - all done. 1049 break; 1050 } 1051 1052 //find intersecting segments 1053 // the intersections will look like this: 1054 // 1055 // ^ 1056 // | 1057 // X wayBNode 1058 // | 1059 // wayB | 1060 // | 1061 // curWay | nextWay 1062 //----X----------------->X----------------------X----> 1063 // prevNode ^headNode nextNode 1064 // | 1065 // | 1066 // wayA | 1067 // | 1068 // X wayANode 1069 // | 1070 1071 int intersectionCount = 0; 1072 1073 for (Way wayA : parts) { 1074 1075 if (wayA == curWay) { 1076 continue; 1077 } 1078 1079 if (wayA.lastNode().equals(headNode)) { 1080 1081 Way wayB = nextWayMap.get(wayA); 1082 1083 //test if wayA is opposite wayB relative to curWay and nextWay 1084 1085 Node wayANode = wayA.getNode(wayA.getNodesCount() - 2); 1086 Node wayBNode = wayB.getNode(1); 1087 1088 boolean wayAToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode); 1089 boolean wayBToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode); 1090 1091 if (wayAToTheRight != wayBToTheRight) { 1092 intersectionCount++; 1093 } 1094 } 1095 } 1096 1097 //if odd number of crossings, invert orientation 1098 if (intersectionCount % 2 != 0) { 1099 curWayInsideToTheRight = !curWayInsideToTheRight; 1100 } 1101 1102 curWay = nextWay; 1103 } 1104 1105 revertDuplicateTwoNodeWays(result); 1106 1107 return result; 1108 } 1109 1110 /** 1111 * Correct possible error in markWayInsideSide result when splitting a self-intersecting way. 1112 * If we have two ways with the same two nodes and the same direction there must be a self intersection. 1113 * Change the direction flag for the latter of the two ways. The result is that difference between the number 1114 * of ways with insideToTheRight = {@code true} and those with insideToTheRight = {@code false} 1115 * differs by 0 or 1, not more. 1116 * <p>See #10511 1117 * @param parts the parts of a single closed way 1118 */ 1119 private static void revertDuplicateTwoNodeWays(List<WayInPolygon> parts) { 1120 for (int i = 0; i < parts.size(); i++) { 1121 WayInPolygon w1 = parts.get(i); 1122 if (w1.way.getNodesCount() != 2) 1123 continue; 1124 for (int j = i + 1; j < parts.size(); j++) { 1125 WayInPolygon w2 = parts.get(j); 1126 if (w2.way.getNodesCount() == 2 && w1.insideToTheRight == w2.insideToTheRight 1127 && w1.way.firstNode() == w2.way.firstNode() && w1.way.lastNode() == w2.way.lastNode()) { 1128 w2.insideToTheRight = !w2.insideToTheRight; 1129 } 1130 } 1131 } 1132 } 1133 1134 /** 1135 * This is a method that splits way into smaller parts, using the prepared nodes list as split points. 1136 * Uses {@link SplitWayCommand#splitWay} for the heavy lifting. 1137 * @param way way to split 1138 * @param nodes split points 1139 * @param oldestWayMap nodes from old ways (modified here) 1140 * @return list of split ways (or original way if no splitting is done). 1141 */ 1142 private List<Way> splitWayOnNodes(Way way, Set<Node> nodes, Map<Node, Way> oldestWayMap) { 1143 1144 List<Way> result = new ArrayList<>(); 1145 List<List<Node>> chunks = buildNodeChunks(way, nodes); 1146 1147 if (chunks.size() > 1) { 1148 SplitWayCommand split = SplitWayCommand.splitWay(way, chunks, 1149 Collections.emptyList(), SplitWayCommand.Strategy.keepFirstChunk()); 1150 1151 if (split != null) { 1152 //execute the command, we need the results 1153 cmds.add(split); 1154 commitCommands(marktr("Split ways into fragments")); 1155 1156 result.add(split.getOriginalWay()); 1157 result.addAll(split.getNewWays()); 1158 1159 // see #9599 1160 if (!way.isNew() && result.size() > 1) { 1161 for (Way part : result) { 1162 Node n = part.firstNode(); 1163 Way old = oldestWayMap.get(n); 1164 if (old == null || old.getUniqueId() > way.getUniqueId()) { 1165 oldestWayMap.put(n, way); 1166 } 1167 } 1168 } 1169 } 1170 } 1171 if (result.isEmpty()) { 1172 //nothing to split 1173 result.add(way); 1174 } 1175 return result; 1176 } 1177 1178 /** 1179 * Simple chunking version. Does not care about circular ways and result being 1180 * proper, we will glue it all back together later on. 1181 * @param way the way to chunk 1182 * @param splitNodes the places where to cut. 1183 * @return list of node paths to produce. 1184 */ 1185 private static List<List<Node>> buildNodeChunks(Way way, Collection<Node> splitNodes) { 1186 List<List<Node>> result = new ArrayList<>(); 1187 List<Node> curList = new ArrayList<>(); 1188 1189 for (Node node : way.getNodes()) { 1190 curList.add(node); 1191 if (curList.size() > 1 && splitNodes.contains(node)) { 1192 result.add(curList); 1193 curList = new ArrayList<>(); 1194 curList.add(node); 1195 } 1196 } 1197 1198 if (curList.size() > 1) { 1199 result.add(curList); 1200 } 1201 1202 return result; 1203 } 1204 1205 /** 1206 * This method finds which ways are outer and which are inner. 1207 * @param boundaries list of joined boundaries to search in 1208 * @return outer ways 1209 */ 1210 private static List<AssembledMultipolygon> findPolygons(Collection<AssembledPolygon> boundaries) { 1211 1212 List<PolygonLevel> list = findOuterWaysImpl(0, boundaries); 1213 List<AssembledMultipolygon> result = new ArrayList<>(); 1214 1215 //take every other level 1216 for (PolygonLevel pol : list) { 1217 if (pol.level % 2 == 0) { 1218 result.add(pol.pol); 1219 } 1220 } 1221 1222 return result; 1223 } 1224 1225 /** 1226 * Collects outer way and corresponding inner ways from all boundaries. 1227 * @param level depth level 1228 * @param boundaryWays list of joined boundaries to search in 1229 * @return the outermost Way. 1230 */ 1231 private static List<PolygonLevel> findOuterWaysImpl(int level, Collection<AssembledPolygon> boundaryWays) { 1232 1233 //TODO: bad performance for deep nestings... 1234 List<PolygonLevel> result = new ArrayList<>(); 1235 1236 for (AssembledPolygon outerWay : boundaryWays) { 1237 1238 boolean outerGood = true; 1239 List<AssembledPolygon> innerCandidates = new ArrayList<>(); 1240 1241 for (AssembledPolygon innerWay : boundaryWays) { 1242 if (innerWay == outerWay) { 1243 continue; 1244 } 1245 1246 if (wayInsideWay(outerWay, innerWay)) { 1247 outerGood = false; 1248 break; 1249 } else if (wayInsideWay(innerWay, outerWay)) { 1250 innerCandidates.add(innerWay); 1251 } 1252 } 1253 1254 if (!outerGood) { 1255 continue; 1256 } 1257 1258 //add new outer polygon 1259 AssembledMultipolygon pol = new AssembledMultipolygon(outerWay); 1260 PolygonLevel polLev = new PolygonLevel(pol, level); 1261 1262 //process inner ways 1263 if (!innerCandidates.isEmpty()) { 1264 List<PolygonLevel> innerList = findOuterWaysImpl(level + 1, innerCandidates); 1265 result.addAll(innerList); 1266 1267 for (PolygonLevel pl : innerList) { 1268 if (pl.level == level + 1) { 1269 pol.innerWays.add(pl.pol.outerWay); 1270 } 1271 } 1272 } 1273 1274 result.add(polLev); 1275 } 1276 1277 return result; 1278 } 1279 1280 /** 1281 * Finds all ways that form inner or outer boundaries. 1282 * @param multigonWays A list of (splitted) ways that form a multigon and share common end nodes on intersections. 1283 * @param discardedResult this list is filled with ways that are to be discarded 1284 * @return A list of ways that form the outer and inner boundaries of the multigon. 1285 */ 1286 public static List<AssembledPolygon> findBoundaryPolygons(Collection<WayInPolygon> multigonWays, 1287 List<Way> discardedResult) { 1288 // In multigonWays collection, some way are just a point (i.e. way like nodeA-nodeA) 1289 // This seems to appear when is apply over invalid way like #9911 test-case 1290 // Remove all of these way to make the next work. 1291 List<WayInPolygon> cleanMultigonWays = new ArrayList<>(); 1292 for (WayInPolygon way: multigonWays) { 1293 if (way.way.getNodesCount() != 2 || !way.way.isClosed()) 1294 cleanMultigonWays.add(way); 1295 } 1296 WayTraverser traverser = new WayTraverser(cleanMultigonWays); 1297 List<AssembledPolygon> result = new ArrayList<>(); 1298 1299 WayInPolygon startWay; 1300 while ((startWay = traverser.startNewWay()) != null) { 1301 List<WayInPolygon> path = new ArrayList<>(); 1302 List<WayInPolygon> startWays = new ArrayList<>(); 1303 path.add(startWay); 1304 while (true) { 1305 WayInPolygon leftComing; 1306 while ((leftComing = traverser.leftComingWay()) != null) { 1307 if (startWays.contains(leftComing)) 1308 break; 1309 // Need restart traverser walk 1310 path.clear(); 1311 path.add(leftComing); 1312 traverser.setStartWay(leftComing); 1313 startWays.add(leftComing); 1314 break; 1315 } 1316 WayInPolygon nextWay = traverser.walk(); 1317 if (nextWay == null) 1318 throw new JosmRuntimeException("Join areas internal error."); 1319 if (path.get(0) == nextWay) { 1320 // path is closed -> stop here 1321 AssembledPolygon ring = new AssembledPolygon(path); 1322 if (ring.getNodes().size() <= 2) { 1323 // Invalid ring (2 nodes) -> remove 1324 traverser.removeWays(path); 1325 for (WayInPolygon way: path) { 1326 discardedResult.add(way.way); 1327 } 1328 } else { 1329 // Close ring -> add 1330 result.add(ring); 1331 traverser.removeWays(path); 1332 } 1333 break; 1334 } 1335 if (path.contains(nextWay)) { 1336 // Inner loop -> remove 1337 int index = path.indexOf(nextWay); 1338 while (path.size() > index) { 1339 WayInPolygon currentWay = path.get(index); 1340 discardedResult.add(currentWay.way); 1341 traverser.removeWay(currentWay); 1342 path.remove(index); 1343 } 1344 traverser.setStartWay(path.get(index-1)); 1345 } else { 1346 path.add(nextWay); 1347 } 1348 } 1349 } 1350 1351 return fixTouchingPolygons(result); 1352 } 1353 1354 /** 1355 * This method checks if polygons have several touching parts and splits them in several polygons. 1356 * @param polygons the polygons to process. 1357 * @return the resulting list of polygons 1358 */ 1359 public static List<AssembledPolygon> fixTouchingPolygons(List<AssembledPolygon> polygons) { 1360 List<AssembledPolygon> newPolygons = new ArrayList<>(); 1361 1362 for (AssembledPolygon ring : polygons) { 1363 ring.reverse(); 1364 WayTraverser traverser = new WayTraverser(ring.ways); 1365 WayInPolygon startWay; 1366 1367 while ((startWay = traverser.startNewWay()) != null) { 1368 List<WayInPolygon> simpleRingWays = new ArrayList<>(); 1369 simpleRingWays.add(startWay); 1370 WayInPolygon nextWay; 1371 while ((nextWay = traverser.walk()) != startWay) { 1372 if (nextWay == null) 1373 throw new JosmRuntimeException("Join areas internal error."); 1374 simpleRingWays.add(nextWay); 1375 } 1376 traverser.removeWays(simpleRingWays); 1377 AssembledPolygon simpleRing = new AssembledPolygon(simpleRingWays); 1378 simpleRing.reverse(); 1379 newPolygons.add(simpleRing); 1380 } 1381 } 1382 1383 return newPolygons; 1384 } 1385 1386 /** 1387 * Tests if way is inside other way 1388 * @param outside outer polygon description 1389 * @param inside inner polygon description 1390 * @return {@code true} if inner is inside outer 1391 */ 1392 public static boolean wayInsideWay(AssembledPolygon inside, AssembledPolygon outside) { 1393 Set<Node> outsideNodes = new HashSet<>(outside.getNodes()); 1394 List<Node> insideNodes = inside.getNodes(); 1395 1396 for (Node insideNode : insideNodes) { 1397 1398 if (!outsideNodes.contains(insideNode)) 1399 //simply test the one node 1400 return Geometry.nodeInsidePolygon(insideNode, outside.getNodes()); 1401 } 1402 1403 //all nodes shared. 1404 return false; 1405 } 1406 1407 /** 1408 * Joins the lists of ways. 1409 * @param polygon The list of outer ways that belong to that multipolygon. 1410 * @return The newly created outer way 1411 * @throws UserCancelException if user cancels the operation 1412 */ 1413 private Multipolygon joinPolygon(AssembledMultipolygon polygon) throws UserCancelException { 1414 Multipolygon result = new Multipolygon(joinWays(polygon.outerWay.ways)); 1415 1416 for (AssembledPolygon pol : polygon.innerWays) { 1417 result.innerWays.add(joinWays(pol.ways)); 1418 } 1419 1420 return result; 1421 } 1422 1423 /** 1424 * Joins the outer ways and deletes all short ways that can't be part of a multipolygon anyway. 1425 * @param ways The list of outer ways that belong to that multigon. 1426 * @return The newly created outer way 1427 * @throws UserCancelException if user cancels the operation 1428 */ 1429 private Way joinWays(List<WayInPolygon> ways) throws UserCancelException { 1430 1431 //leave original orientation, if all paths are reverse. 1432 boolean allReverse = true; 1433 for (WayInPolygon way : ways) { 1434 allReverse &= !way.insideToTheRight; 1435 } 1436 1437 if (allReverse) { 1438 for (WayInPolygon way : ways) { 1439 way.insideToTheRight = !way.insideToTheRight; 1440 } 1441 } 1442 1443 Way joinedWay = joinOrientedWays(ways); 1444 1445 //should not happen 1446 if (joinedWay == null || !joinedWay.isClosed()) 1447 throw new JosmRuntimeException("Join areas internal error."); 1448 1449 return joinedWay; 1450 } 1451 1452 /** 1453 * Joins a list of ways (using CombineWayAction and ReverseWayAction as specified in WayInPath) 1454 * @param ways The list of ways to join and reverse 1455 * @return The newly created way 1456 * @throws UserCancelException if user cancels the operation 1457 */ 1458 private Way joinOrientedWays(List<WayInPolygon> ways) throws UserCancelException { 1459 if (ways.size() < 2) 1460 return ways.get(0).way; 1461 1462 // This will turn ways so all of them point in the same direction and CombineAction won't bug 1463 // the user about this. 1464 1465 List<Way> actionWays = new ArrayList<>(ways.size()); 1466 int oldestPos = 0; 1467 Way oldest = ways.get(0).way; 1468 for (WayInPolygon way : ways) { 1469 actionWays.add(way.way); 1470 if (oldest.isNew() || (!way.way.isNew() && oldest.getUniqueId() > way.way.getUniqueId())) { 1471 oldest = way.way; 1472 oldestPos = actionWays.size() - 1; 1473 } 1474 1475 if (!way.insideToTheRight) { 1476 ReverseWayResult res = ReverseWayAction.reverseWay(way.way); 1477 commitCommand(res.getReverseCommand()); 1478 } 1479 } 1480 1481 // see #9599: Help CombineWayAction to use the oldest way 1482 Collections.rotate(actionWays, actionWays.size() - oldestPos); 1483 1484 Pair<Way, Command> result = CombineWayAction.combineWaysWorker(actionWays); 1485 if (result == null) { 1486 throw new JosmRuntimeException("Join areas internal error."); 1487 } 1488 commitCommand(result.b); 1489 1490 return result.a; 1491 } 1492 1493 /** 1494 * This method analyzes multipolygon relationships of given ways and collects addition inner ways to consider. 1495 * @param selectedWays the selected ways 1496 * @return list of polygons, or null if too complex relation encountered. 1497 */ 1498 public static List<Multipolygon> collectMultipolygons(Collection<Way> selectedWays) { 1499 1500 List<Multipolygon> result = new ArrayList<>(); 1501 1502 //prepare the lists, to minimize memory allocation. 1503 List<Way> outerWays = new ArrayList<>(); 1504 List<Way> innerWays = new ArrayList<>(); 1505 1506 Set<Way> processedOuterWays = new LinkedHashSet<>(); 1507 Set<Way> processedInnerWays = new LinkedHashSet<>(); 1508 1509 for (Relation r : OsmPrimitive.getParentRelations(selectedWays)) { 1510 if (r.isDeleted() || !r.isMultipolygon()) { 1511 continue; 1512 } 1513 1514 boolean hasKnownOuter = false; 1515 outerWays.clear(); 1516 innerWays.clear(); 1517 1518 for (RelationMember rm : r.getMembers()) { 1519 if (!rm.isWay()) 1520 continue; 1521 if ("outer".equalsIgnoreCase(rm.getRole())) { 1522 outerWays.add(rm.getWay()); 1523 hasKnownOuter |= selectedWays.contains(rm.getWay()); 1524 } else if ("inner".equalsIgnoreCase(rm.getRole())) { 1525 innerWays.add(rm.getWay()); 1526 } 1527 } 1528 1529 if (!hasKnownOuter) { 1530 continue; 1531 } 1532 1533 if (outerWays.size() > 1) { 1534 new Notification( 1535 tr("Sorry. Cannot handle multipolygon relations with multiple outer ways.")) 1536 .setIcon(JOptionPane.INFORMATION_MESSAGE) 1537 .show(); 1538 return null; 1539 } 1540 1541 Way outerWay = outerWays.get(0); 1542 1543 //retain only selected inner ways 1544 innerWays.retainAll(selectedWays); 1545 1546 if (!innerWays.isEmpty() && selectedWays.contains(outerWay)) { 1547 // see #18744 1548 new Notification(tr("Cannot join inner and outer ways of a multipolygon")) 1549 .setIcon(JOptionPane.INFORMATION_MESSAGE) 1550 .show(); 1551 return null; 1552 } 1553 1554 if (processedOuterWays.contains(outerWay)) { 1555 new Notification( 1556 tr("Sorry. Cannot handle way that is outer in multiple multipolygon relations.")) 1557 .setIcon(JOptionPane.INFORMATION_MESSAGE) 1558 .show(); 1559 return null; 1560 } 1561 1562 if (processedInnerWays.contains(outerWay)) { 1563 new Notification( 1564 tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations.")) 1565 .setIcon(JOptionPane.INFORMATION_MESSAGE) 1566 .show(); 1567 return null; 1568 } 1569 1570 for (Way way :innerWays) { 1571 if (processedOuterWays.contains(way)) { 1572 new Notification( 1573 tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations.")) 1574 .setIcon(JOptionPane.INFORMATION_MESSAGE) 1575 .show(); 1576 return null; 1577 } 1578 1579 if (processedInnerWays.contains(way)) { 1580 new Notification( 1581 tr("Sorry. Cannot handle way that is inner in multiple multipolygon relations.")) 1582 .setIcon(JOptionPane.INFORMATION_MESSAGE) 1583 .show(); 1584 return null; 1585 } 1586 } 1587 1588 processedOuterWays.add(outerWay); 1589 processedInnerWays.addAll(innerWays); 1590 1591 Multipolygon pol = new Multipolygon(outerWay); 1592 pol.innerWays.addAll(innerWays); 1593 1594 result.add(pol); 1595 } 1596 1597 //add remaining ways, not in relations 1598 for (Way way : selectedWays) { 1599 if (processedOuterWays.contains(way) || processedInnerWays.contains(way)) { 1600 continue; 1601 } 1602 1603 result.add(new Multipolygon(way)); 1604 } 1605 1606 return result; 1607 } 1608 1609 /** 1610 * Will add own multipolygon relation to the "previously existing" relations. Fixup is done by fixRelations 1611 * @param inner List of already closed inner ways 1612 * @return The list of relation with roles to add own relation to 1613 */ 1614 private RelationRole addOwnMultipolygonRelation(Collection<Way> inner) { 1615 if (inner.isEmpty()) return null; 1616 OsmDataLayer layer = getLayerManager().getEditLayer(); 1617 // Create new multipolygon relation and add all inner ways to it 1618 Relation newRel = new Relation(); 1619 newRel.put("type", "multipolygon"); 1620 for (Way w : inner) { 1621 newRel.addMember(new RelationMember("inner", w)); 1622 } 1623 cmds.add(layer != null ? new AddCommand(layer.getDataSet(), newRel) : 1624 new AddCommand(inner.iterator().next().getDataSet(), newRel)); 1625 addedRelations.add(newRel); 1626 1627 // We don't add outer to the relation because it will be handed to fixRelations() 1628 // which will then do the remaining work. 1629 return new RelationRole(newRel, "outer"); 1630 } 1631 1632 /** 1633 * Removes a given OsmPrimitive from all relations. 1634 * @param osm Element to remove from all relations 1635 * @return List of relations with roles the primitives was part of 1636 */ 1637 private List<RelationRole> removeFromAllRelations(OsmPrimitive osm) { 1638 List<RelationRole> result = new ArrayList<>(); 1639 1640 for (Relation r : osm.getDataSet().getRelations()) { 1641 if (r.isDeleted()) { 1642 continue; 1643 } 1644 for (RelationMember rm : r.getMembers()) { 1645 if (rm.getMember() != osm) { 1646 continue; 1647 } 1648 1649 List<RelationMember> members = r.getMembers(); 1650 members.remove(rm); 1651 1652 cmds.add(new ChangeMembersCommand(r, members)); 1653 RelationRole saverel = new RelationRole(r, rm.getRole()); 1654 if (!result.contains(saverel)) { 1655 result.add(saverel); 1656 } 1657 break; 1658 } 1659 } 1660 1661 commitCommands(marktr("Removed Element from Relations")); 1662 return result; 1663 } 1664 1665 /** 1666 * Adds the previously removed relations again to the outer way. If there are multiple multipolygon 1667 * relations where the joined areas were in "outer" role a new relation is created instead with all 1668 * members of both. This function depends on multigon relations to be valid already, it won't fix them. 1669 * @param rels List of relations with roles the (original) ways were part of 1670 * @param outer The newly created outer area/way 1671 * @param ownMultipol elements to directly add as outer 1672 * @param relationsToDelete set of relations to delete. 1673 */ 1674 private void fixRelations(List<RelationRole> rels, Way outer, RelationRole ownMultipol, Set<Relation> relationsToDelete) { 1675 List<RelationRole> multiouters = new ArrayList<>(); 1676 1677 if (ownMultipol != null) { 1678 multiouters.add(ownMultipol); 1679 } 1680 1681 for (RelationRole r : rels) { 1682 if (r.rel.isMultipolygon() && "outer".equalsIgnoreCase(r.role)) { 1683 multiouters.add(r); 1684 continue; 1685 } 1686 // Add it back! 1687 List<RelationMember> modifiedMembers = new ArrayList<>(r.rel.getMembers()); 1688 modifiedMembers.add(new RelationMember(r.role, outer)); 1689 cmds.add(new ChangeMembersCommand(r.rel, modifiedMembers)); 1690 } 1691 1692 switch (multiouters.size()) { 1693 case 0: 1694 return; 1695 case 1: 1696 // Found only one to be part of a multipolygon relation, so just add it back as well 1697 RelationRole soleOuter = multiouters.get(0); 1698 List<RelationMember> modifiedMembers = new ArrayList<>(soleOuter.rel.getMembers()); 1699 modifiedMembers.add(new RelationMember(soleOuter.role, outer)); 1700 cmds.add(new ChangeMembersCommand(ds, soleOuter.rel, modifiedMembers)); 1701 return; 1702 default: 1703 // Create a new relation with all previous members and (Way)outer as outer. 1704 Relation newRel = new Relation(); 1705 for (RelationRole r : multiouters) { 1706 // Add members 1707 for (RelationMember rm : r.rel.getMembers()) { 1708 if (!newRel.getMembers().contains(rm)) { 1709 newRel.addMember(rm); 1710 } 1711 } 1712 // Add tags 1713 r.rel.visitKeys((p, key, value) -> newRel.put(key, value)); 1714 // Delete old relation 1715 relationsToDelete.add(r.rel); 1716 } 1717 newRel.addMember(new RelationMember("outer", outer)); 1718 cmds.add(new AddCommand(ds, newRel)); 1719 } 1720 } 1721 1722 /** 1723 * Remove all tags from the all the way 1724 * @param ways The List of Ways to remove all tags from 1725 */ 1726 private void stripTags(Collection<Way> ways) { 1727 Map<String, String> tagsToRemove = new HashMap<>(); 1728 ways.stream().flatMap(AbstractPrimitive::keys).forEach(k -> tagsToRemove.put(k, null)); 1729 if (tagsToRemove.isEmpty()) 1730 return; 1731 cmds.add(new ChangePropertyCommand(new ArrayList<>(ways), tagsToRemove)); 1732 /* I18N: current action printed in status display */ 1733 commitCommands(marktr("Remove tags from inner ways")); 1734 } 1735 1736 @Override 1737 protected void updateEnabledState() { 1738 updateEnabledStateOnCurrentSelection(); 1739 } 1740 1741 @Override 1742 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) { 1743 updateEnabledStateOnModifiableSelection(selection); 1744 } 1745 1746 private static class JoinAreaCommand extends SequenceCommand { 1747 JoinAreaCommand(Collection<Command> sequenz) { 1748 super(tr("Joined overlapping areas"), sequenz, true); 1749 setSequenceComplete(true); 1750 } 1751 1752 @Override 1753 public void undoCommand() { 1754 getAffectedDataSet().update(super::undoCommand); 1755 } 1756 1757 @Override 1758 public boolean executeCommand() { 1759 return getAffectedDataSet().update(super::executeCommand); 1760 } 1761 } 1762}