001 // License: GPL. Copyright 2007 by Immanuel Scholz and others
002 package org.openstreetmap.josm.actions;
003
004 import static org.openstreetmap.josm.tools.I18n.marktr;
005 import static org.openstreetmap.josm.tools.I18n.tr;
006 import static org.openstreetmap.josm.tools.I18n.trn;
007
008 import java.awt.event.ActionEvent;
009 import java.awt.event.KeyEvent;
010 import java.awt.geom.Area;
011 import java.util.ArrayList;
012 import java.util.Collection;
013 import java.util.Collections;
014 import java.util.HashMap;
015 import java.util.HashSet;
016 import java.util.LinkedHashSet;
017 import java.util.LinkedList;
018 import java.util.List;
019 import java.util.Map;
020 import java.util.Set;
021 import java.util.TreeMap;
022
023 import javax.swing.JOptionPane;
024
025 import org.openstreetmap.josm.Main;
026 import org.openstreetmap.josm.actions.ReverseWayAction.ReverseWayResult;
027 import org.openstreetmap.josm.actions.SplitWayAction.SplitWayResult;
028 import org.openstreetmap.josm.command.AddCommand;
029 import org.openstreetmap.josm.command.ChangeCommand;
030 import org.openstreetmap.josm.command.Command;
031 import org.openstreetmap.josm.command.DeleteCommand;
032 import org.openstreetmap.josm.command.SequenceCommand;
033 import org.openstreetmap.josm.corrector.UserCancelException;
034 import org.openstreetmap.josm.data.UndoRedoHandler;
035 import org.openstreetmap.josm.data.coor.EastNorth;
036 import org.openstreetmap.josm.data.osm.DataSet;
037 import org.openstreetmap.josm.data.osm.Node;
038 import org.openstreetmap.josm.data.osm.NodePositionComparator;
039 import org.openstreetmap.josm.data.osm.OsmPrimitive;
040 import org.openstreetmap.josm.data.osm.Relation;
041 import org.openstreetmap.josm.data.osm.RelationMember;
042 import org.openstreetmap.josm.data.osm.TagCollection;
043 import org.openstreetmap.josm.data.osm.Way;
044 import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
045 import org.openstreetmap.josm.tools.Geometry;
046 import org.openstreetmap.josm.tools.Pair;
047 import org.openstreetmap.josm.tools.Shortcut;
048
049
050 /**
051 * Join Areas (i.e. closed ways and multipolygons)
052 */
053 public class JoinAreasAction extends JosmAction {
054 // This will be used to commit commands and unite them into one large command sequence at the end
055 private LinkedList<Command> cmds = new LinkedList<Command>();
056 private int cmdsCount = 0;
057
058
059 /**
060 * This helper class describes join ares action result.
061 * @author viesturs
062 *
063 */
064 public static class JoinAreasResult {
065
066 public boolean mergeSuccessful;
067 public boolean hasChanges;
068 public boolean hasRelationProblems;
069
070 public List<Multipolygon> polygons;
071 }
072
073 public static class Multipolygon {
074 public Way outerWay;
075 public List<Way> innerWays;
076
077 public Relation relation;
078
079 public Multipolygon(Way way) {
080 outerWay = way;
081 innerWays = new ArrayList<Way>();
082 }
083 }
084
085 // HelperClass
086 // Saves a relation and a role an OsmPrimitve was part of until it was stripped from all relations
087 private static class RelationRole {
088 public final Relation rel;
089 public final String role;
090 public RelationRole(Relation rel, String role) {
091 this.rel = rel;
092 this.role = role;
093 }
094
095 @Override
096 public int hashCode() {
097 return rel.hashCode();
098 }
099
100 @Override
101 public boolean equals(Object other) {
102 if (!(other instanceof RelationRole)) return false;
103 RelationRole otherMember = (RelationRole) other;
104 return otherMember.role.equals(role) && otherMember.rel.equals(rel);
105 }
106 }
107
108
109 //HelperClass
110 //saves a way and the "inside" side
111 // insideToTheLeft: if true left side is "in", false -right side is "in". Left and right are determined along the orientation of way.
112 public static class WayInPolygon {
113 public final Way way;
114 public boolean insideToTheRight;
115
116 public WayInPolygon(Way _way, boolean _insideRight) {
117 this.way = _way;
118 this.insideToTheRight = _insideRight;
119 }
120
121 @Override
122 public int hashCode() {
123 return way.hashCode();
124 }
125
126 @Override
127 public boolean equals(Object other) {
128 if (!(other instanceof WayInPolygon)) return false;
129 WayInPolygon otherMember = (WayInPolygon) other;
130 return otherMember.way.equals(this.way) && otherMember.insideToTheRight == this.insideToTheRight;
131 }
132 }
133
134 /**
135 * This helper class describes a polygon, assembled from several ways.
136 * @author viesturs
137 *
138 */
139 public static class AssembledPolygon {
140 public List<WayInPolygon> ways;
141
142 public AssembledPolygon(List<WayInPolygon> boundary) {
143 this.ways = boundary;
144 }
145
146 public List<Node> getNodes() {
147 List<Node> nodes = new ArrayList<Node>();
148 for (WayInPolygon way : this.ways) {
149 //do not add the last node as it will be repeated in the next way
150 if (way.insideToTheRight) {
151 for (int pos = 0; pos < way.way.getNodesCount() - 1; pos++) {
152 nodes.add(way.way.getNode(pos));
153 }
154 }
155 else {
156 for (int pos = way.way.getNodesCount() - 1; pos > 0; pos--) {
157 nodes.add(way.way.getNode(pos));
158 }
159 }
160 }
161
162 return nodes;
163 }
164 }
165
166 public static class AssembledMultipolygon {
167 public AssembledPolygon outerWay;
168 public List<AssembledPolygon> innerWays;
169
170 public AssembledMultipolygon(AssembledPolygon way) {
171 outerWay = way;
172 innerWays = new ArrayList<AssembledPolygon>();
173 }
174 }
175
176 /**
177 * This hepler class implements algorithm traversing trough connected ways.
178 * Assumes you are going in clockwise orientation.
179 * @author viesturs
180 *
181 */
182 private static class WayTraverser {
183
184 private Set<WayInPolygon> availableWays;
185 private WayInPolygon lastWay;
186 private boolean lastWayReverse;
187
188 public WayTraverser(Collection<WayInPolygon> ways) {
189
190 availableWays = new HashSet<WayInPolygon>(ways);
191 lastWay = null;
192 }
193
194 public void removeWays(Collection<WayInPolygon> ways) {
195 availableWays.removeAll(ways);
196 }
197
198 public boolean hasWays() {
199 return availableWays.size() > 0;
200 }
201
202 public WayInPolygon startNewWay(WayInPolygon way) {
203 lastWay = way;
204 lastWayReverse = !lastWay.insideToTheRight;
205
206 return lastWay;
207 }
208
209 public WayInPolygon startNewWay() {
210 if (availableWays.isEmpty()) {
211 lastWay = null;
212 } else {
213 lastWay = availableWays.iterator().next();
214 lastWayReverse = !lastWay.insideToTheRight;
215 }
216
217 return lastWay;
218 }
219
220
221 public WayInPolygon advanceNextLeftmostWay() {
222 return advanceNextWay(false);
223 }
224
225 public WayInPolygon advanceNextRightmostWay() {
226 return advanceNextWay(true);
227 }
228
229 private WayInPolygon advanceNextWay(boolean rightmost) {
230
231 Node headNode = !lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
232 Node prevNode = !lastWayReverse ? lastWay.way.getNode(lastWay.way.getNodesCount() - 2) : lastWay.way.getNode(1);
233
234 //find best next way
235 WayInPolygon bestWay = null;
236 Node bestWayNextNode = null;
237 boolean bestWayReverse = false;
238
239 for (WayInPolygon way : availableWays) {
240 if (way.way.firstNode().equals(headNode)) {
241 //start adjacent to headNode
242 Node nextNode = way.way.getNode(1);
243
244 if (nextNode.equals(prevNode))
245 {
246 //this is the path we came from - ignore it.
247 }
248 else if (bestWay == null || (Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) {
249 //the new way is better
250 bestWay = way;
251 bestWayReverse = false;
252 bestWayNextNode = nextNode;
253 }
254 }
255
256 if (way.way.lastNode().equals(headNode)) {
257 //end adjacent to headNode
258 Node nextNode = way.way.getNode(way.way.getNodesCount() - 2);
259
260 if (nextNode.equals(prevNode)) {
261 //this is the path we came from - ignore it.
262 }
263 else if (bestWay == null || (Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) {
264 //the new way is better
265 bestWay = way;
266 bestWayReverse = true;
267 bestWayNextNode = nextNode;
268 }
269 }
270 }
271
272 lastWay = bestWay;
273 lastWayReverse = bestWayReverse;
274
275 return lastWay;
276 }
277
278 public boolean isLastWayInsideToTheRight() {
279 return lastWayReverse != lastWay.insideToTheRight;
280 }
281
282 public Node getLastWayStartNode() {
283 return lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
284 }
285
286 public Node getLastWayEndNode() {
287 return lastWayReverse ? lastWay.way.firstNode() : lastWay.way.lastNode();
288 }
289 }
290
291 /**
292 * Helper storage class for finding findOuterWays
293 * @author viesturs
294 */
295 static class PolygonLevel {
296 public final int level;
297 public final AssembledMultipolygon pol;
298
299 public PolygonLevel(AssembledMultipolygon _pol, int _level) {
300 pol = _pol;
301 level = _level;
302 }
303 }
304
305 // Adds the menu entry, Shortcuts, etc.
306 public JoinAreasAction() {
307 super(tr("Join overlapping Areas"), "joinareas", tr("Joins areas that overlap each other"),
308 Shortcut.registerShortcut("tools:joinareas", tr("Tool: {0}", tr("Join overlapping Areas")),
309 KeyEvent.VK_J, Shortcut.SHIFT), true);
310 }
311
312 /**
313 * Gets called whenever the shortcut is pressed or the menu entry is selected
314 * Checks whether the selected objects are suitable to join and joins them if so
315 */
316 public void actionPerformed(ActionEvent e) {
317 LinkedList<Way> ways = new LinkedList<Way>(Main.main.getCurrentDataSet().getSelectedWays());
318
319 if (ways.isEmpty()) {
320 JOptionPane.showMessageDialog(Main.parent, tr("Please select at least one closed way that should be joined."));
321 return;
322 }
323
324 List<Node> allNodes = new ArrayList<Node>();
325 for (Way way : ways) {
326 if (!way.isClosed()) {
327 JOptionPane.showMessageDialog(Main.parent, tr("One of the selected ways is not closed and therefore cannot be joined."));
328 return;
329 }
330
331 allNodes.addAll(way.getNodes());
332 }
333
334 // TODO: Only display this warning when nodes outside dataSourceArea are deleted
335 Area dataSourceArea = Main.main.getCurrentDataSet().getDataSourceArea();
336 boolean ok = Command.checkAndConfirmOutlyingOperation("joinarea", tr("Join area confirmation"),
337 trn("The selected way has nodes outside of the downloaded data region.",
338 "The selected ways have nodes outside of the downloaded data region.",
339 ways.size()) + "<br/>"
340 + tr("This can lead to nodes being deleted accidentally.") + "<br/>"
341 + tr("Are you really sure to continue?")
342 + tr("Please abort if you are not sure"),
343 tr("The selected area is incomplete. Continue?"),
344 dataSourceArea, allNodes, null);
345 if(!ok) return;
346
347 //analyze multipolygon relations and collect all areas
348 List<Multipolygon> areas = collectMultipolygons(ways);
349
350 if (areas == null)
351 //too complex multipolygon relations found
352 return;
353
354 if (!testJoin(areas)) {
355 JOptionPane.showMessageDialog(Main.parent, tr("No intersection found. Nothing was changed."));
356 return;
357 }
358
359 if (!resolveTagConflicts(areas))
360 return;
361 //user canceled, do nothing.
362
363 try {
364 JoinAreasResult result = joinAreas(areas);
365
366 if (result.hasChanges) {
367
368 List<Way> allWays = new ArrayList<Way>();
369 for (Multipolygon pol : result.polygons) {
370 allWays.add(pol.outerWay);
371 allWays.addAll(pol.innerWays);
372 }
373 DataSet ds = Main.main.getCurrentDataSet();
374 ds.setSelected(allWays);
375 Main.map.mapView.repaint();
376 } else {
377 JOptionPane.showMessageDialog(Main.parent, tr("No intersection found. Nothing was changed."));
378 }
379 }
380 catch (UserCancelException exception) {
381 //revert changes
382 //FIXME: this is dirty hack
383 makeCommitsOneAction(tr("Reverting changes"));
384 Main.main.undoRedo.undo();
385 Main.main.undoRedo.redoCommands.clear();
386 }
387 }
388
389 /**
390 * Tests if the areas have some intersections to join.
391 * @param areas
392 * @return
393 */
394 private boolean testJoin(List<Multipolygon> areas) {
395 List<Way> allStartingWays = new ArrayList<Way>();
396
397 for (Multipolygon area : areas) {
398 allStartingWays.add(area.outerWay);
399 allStartingWays.addAll(area.innerWays);
400 }
401
402 //find intersection points
403 Set<Node> nodes = Geometry.addIntersections(allStartingWays, true, cmds);
404 return nodes.size() > 0;
405 }
406
407 /**
408 * Will join two or more overlapping areas
409 * @param areas - list of areas to join
410 * @return new area formed.
411 */
412 private JoinAreasResult joinAreas(List<Multipolygon> areas) throws UserCancelException {
413
414 JoinAreasResult result = new JoinAreasResult();
415 result.hasChanges = false;
416
417 List<Way> allStartingWays = new ArrayList<Way>();
418 List<Way> innerStartingWays = new ArrayList<Way>();
419 List<Way> outerStartingWays = new ArrayList<Way>();
420
421 for (Multipolygon area : areas) {
422 outerStartingWays.add(area.outerWay);
423 innerStartingWays.addAll(area.innerWays);
424 }
425
426 allStartingWays.addAll(innerStartingWays);
427 allStartingWays.addAll(outerStartingWays);
428
429 //first remove nodes in the same coordinate
430 boolean removedDuplicates = false;
431 removedDuplicates |= removeDuplicateNodes(allStartingWays);
432
433 if (removedDuplicates) {
434 result.hasChanges = true;
435 commitCommands(marktr("Removed duplicate nodes"));
436 }
437
438 //find intersection points
439 Set<Node> nodes = Geometry.addIntersections(allStartingWays, false, cmds);
440
441 //no intersections, return.
442 if (nodes.isEmpty())
443 return result;
444 commitCommands(marktr("Added node on all intersections"));
445
446 ArrayList<RelationRole> relations = new ArrayList<RelationRole>();
447
448 // Remove ways from all relations so ways can be combined/split quietly
449 for (Way way : allStartingWays) {
450 relations.addAll(removeFromAllRelations(way));
451 }
452
453 // Don't warn now, because it will really look corrupted
454 boolean warnAboutRelations = relations.size() > 0 && allStartingWays.size() > 1;
455
456 ArrayList<WayInPolygon> preparedWays = new ArrayList<WayInPolygon>();
457
458 for (Way way : outerStartingWays) {
459 ArrayList<Way> splitWays = splitWayOnNodes(way, nodes);
460 preparedWays.addAll(markWayInsideSide(splitWays, false));
461 }
462
463 for (Way way : innerStartingWays) {
464 ArrayList<Way> splitWays = splitWayOnNodes(way, nodes);
465 preparedWays.addAll(markWayInsideSide(splitWays, true));
466 }
467
468 // Find boundary ways
469 ArrayList<Way> discardedWays = new ArrayList<Way>();
470 List<AssembledPolygon> bounadries = findBoundaryPolygons(preparedWays, discardedWays);
471
472 //find polygons
473 List<AssembledMultipolygon> preparedPolygons = findPolygons(bounadries);
474
475
476 //assemble final polygons
477 List<Multipolygon> polygons = new ArrayList<Multipolygon>();
478 Set<Relation> relationsToDelete = new LinkedHashSet<Relation>();
479
480 for (AssembledMultipolygon pol : preparedPolygons) {
481
482 //create the new ways
483 Multipolygon resultPol = joinPolygon(pol);
484
485 //create multipolygon relation, if necessary.
486 RelationRole ownMultipolygonRelation = addOwnMultigonRelation(resultPol.innerWays, resultPol.outerWay);
487
488 //add back the original relations, merged with our new multipolygon relation
489 fixRelations(relations, resultPol.outerWay, ownMultipolygonRelation, relationsToDelete);
490
491 //strip tags from inner ways
492 //TODO: preserve tags on existing inner ways
493 stripTags(resultPol.innerWays);
494
495 polygons.add(resultPol);
496 }
497
498 commitCommands(marktr("Assemble new polygons"));
499
500 for(Relation rel: relationsToDelete) {
501 cmds.add(new DeleteCommand(rel));
502 }
503
504 commitCommands(marktr("Delete relations"));
505
506 // Delete the discarded inner ways
507 if (discardedWays.size() > 0) {
508 cmds.add(DeleteCommand.delete(Main.map.mapView.getEditLayer(), discardedWays, true));
509 commitCommands(marktr("Delete Ways that are not part of an inner multipolygon"));
510 }
511
512 makeCommitsOneAction(marktr("Joined overlapping areas"));
513
514 if (warnAboutRelations) {
515 JOptionPane.showMessageDialog(Main.parent, tr("Some of the ways were part of relations that have been modified. Please verify no errors have been introduced."));
516 }
517
518 result.hasChanges = true;
519 result.mergeSuccessful = true;
520 result.polygons = polygons;
521 return result;
522 }
523
524 /**
525 * Checks if tags of two given ways differ, and presents the user a dialog to solve conflicts
526 * @param Way First way to check
527 * @param Way Second Way to check
528 * @return boolean True if all conflicts are resolved, False if conflicts remain.
529 */
530 private boolean resolveTagConflicts(List<Multipolygon> polygons) {
531
532 List<Way> ways = new ArrayList<Way>();
533
534 for (Multipolygon pol : polygons) {
535 ways.add(pol.outerWay);
536 ways.addAll(pol.innerWays);
537 }
538
539 if (ways.size() < 2) {
540 return true;
541 }
542
543 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
544 try {
545 cmds.addAll(CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, ways));
546 commitCommands(marktr("Fix tag conflicts"));
547 return true;
548 } catch (UserCancelException ex) {
549 return false;
550 }
551 }
552
553 /**
554 * This method removes duplicate points (if any) from the input way.
555 * @param way the way to process
556 * @return true if any changes where made
557 */
558 private boolean removeDuplicateNodes(List<Way> ways) {
559 //TODO: maybe join nodes with JoinNodesAction, rather than reconnect the ways.
560
561 Map<Node, Node> nodeMap = new TreeMap<Node, Node>(new NodePositionComparator());
562 int totalNodesRemoved = 0;
563
564 for (Way way : ways) {
565 if (way.getNodes().size() < 2) {
566 continue;
567 }
568
569 int nodesRemoved = 0;
570 List<Node> newNodes = new ArrayList<Node>();
571 Node prevNode = null;
572
573 for (Node node : way.getNodes()) {
574 if (!nodeMap.containsKey(node)) {
575 //new node
576 nodeMap.put(node, node);
577
578 //avoid duplicate nodes
579 if (prevNode != node) {
580 newNodes.add(node);
581 } else {
582 nodesRemoved ++;
583 }
584 } else {
585 //node with same coordinates already exists, substitute with existing node
586 Node representator = nodeMap.get(node);
587
588 if (representator != node) {
589 nodesRemoved ++;
590 }
591
592 //avoid duplicate node
593 if (prevNode != representator) {
594 newNodes.add(representator);
595 }
596 }
597 prevNode = node;
598 }
599
600 if (nodesRemoved > 0) {
601
602 if (newNodes.size() == 1) { //all nodes in the same coordinate - add one more node, to have closed way.
603 newNodes.add(newNodes.get(0));
604 }
605
606 Way newWay=new Way(way);
607 newWay.setNodes(newNodes);
608 cmds.add(new ChangeCommand(way, newWay));
609 totalNodesRemoved += nodesRemoved;
610 }
611 }
612
613 return totalNodesRemoved > 0;
614 }
615
616 /**
617 * Commits the command list with a description
618 * @param String The description of what the commands do
619 */
620 private void commitCommands(String description) {
621 switch(cmds.size()) {
622 case 0:
623 return;
624 case 1:
625 Main.main.undoRedo.add(cmds.getFirst());
626 break;
627 default:
628 Command c = new SequenceCommand(tr(description), cmds);
629 Main.main.undoRedo.add(c);
630 break;
631 }
632
633 cmds.clear();
634 cmdsCount++;
635 }
636
637 /**
638 * This method analyzes the way and assigns each part what direction polygon "inside" is.
639 * @param parts the split parts of the way
640 * @param isInner - if true, reverts the direction (for multipolygon islands)
641 * @return list of parts, marked with the inside orientation.
642 */
643 private ArrayList<WayInPolygon> markWayInsideSide(List<Way> parts, boolean isInner) {
644
645 ArrayList<WayInPolygon> result = new ArrayList<WayInPolygon>();
646
647 //prepare prev and next maps
648 Map<Way, Way> nextWayMap = new HashMap<Way, Way>();
649 Map<Way, Way> prevWayMap = new HashMap<Way, Way>();
650
651 for (int pos = 0; pos < parts.size(); pos ++) {
652
653 if (!parts.get(pos).lastNode().equals(parts.get((pos + 1) % parts.size()).firstNode()))
654 throw new RuntimeException("Way not circular");
655
656 nextWayMap.put(parts.get(pos), parts.get((pos + 1) % parts.size()));
657 prevWayMap.put(parts.get(pos), parts.get((pos + parts.size() - 1) % parts.size()));
658 }
659
660 //find the node with minimum y - it's guaranteed to be outer. (What about the south pole?)
661 Way topWay = null;
662 Node topNode = null;
663 int topIndex = 0;
664 double minY = Double.POSITIVE_INFINITY;
665
666 for (Way way : parts) {
667 for (int pos = 0; pos < way.getNodesCount(); pos ++) {
668 Node node = way.getNode(pos);
669
670 if (node.getEastNorth().getY() < minY) {
671 minY = node.getEastNorth().getY();
672 topWay = way;
673 topNode = node;
674 topIndex = pos;
675 }
676 }
677 }
678
679 //get the upper way and it's orientation.
680
681 boolean wayClockwise; // orientation of the top way.
682
683 if (topNode.equals(topWay.firstNode()) || topNode.equals(topWay.lastNode())) {
684 Node headNode = null; // the node at junction
685 Node prevNode = null; // last node from previous path
686 wayClockwise = false;
687
688 //node is in split point - find the outermost way from this point
689
690 headNode = topNode;
691 //make a fake node that is downwards from head node (smaller Y). It will be a division point between paths.
692 prevNode = new Node(new EastNorth(headNode.getEastNorth().getX(), headNode.getEastNorth().getY() - 1e5));
693
694 topWay = null;
695 wayClockwise = false;
696 Node bestWayNextNode = null;
697
698 for (Way way : parts) {
699 if (way.firstNode().equals(headNode)) {
700 Node nextNode = way.getNode(1);
701
702 if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) {
703 //the new way is better
704 topWay = way;
705 wayClockwise = true;
706 bestWayNextNode = nextNode;
707 }
708 }
709
710 if (way.lastNode().equals(headNode)) {
711 //end adjacent to headNode
712 Node nextNode = way.getNode(way.getNodesCount() - 2);
713
714 if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) {
715 //the new way is better
716 topWay = way;
717 wayClockwise = false;
718 bestWayNextNode = nextNode;
719 }
720 }
721 }
722 } else {
723 //node is inside way - pick the clockwise going end.
724 Node prev = topWay.getNode(topIndex - 1);
725 Node next = topWay.getNode(topIndex + 1);
726
727 //there will be no parallel segments in the middle of way, so all fine.
728 wayClockwise = Geometry.angleIsClockwise(prev, topNode, next);
729 }
730
731 Way curWay = topWay;
732 boolean curWayInsideToTheRight = wayClockwise ^ isInner;
733
734 //iterate till full circle is reached
735 while (true) {
736
737 //add cur way
738 WayInPolygon resultWay = new WayInPolygon(curWay, curWayInsideToTheRight);
739 result.add(resultWay);
740
741 //process next way
742 Way nextWay = nextWayMap.get(curWay);
743 Node prevNode = curWay.getNode(curWay.getNodesCount() - 2);
744 Node headNode = curWay.lastNode();
745 Node nextNode = nextWay.getNode(1);
746
747 if (nextWay == topWay) {
748 //full loop traversed - all done.
749 break;
750 }
751
752 //find intersecting segments
753 // the intersections will look like this:
754 //
755 // ^
756 // |
757 // X wayBNode
758 // |
759 // wayB |
760 // |
761 // curWay | nextWay
762 //----X----------------->X----------------------X---->
763 // prevNode ^headNode nextNode
764 // |
765 // |
766 // wayA |
767 // |
768 // X wayANode
769 // |
770
771 int intersectionCount = 0;
772
773 for (Way wayA : parts) {
774
775 if (wayA == curWay) {
776 continue;
777 }
778
779 if (wayA.lastNode().equals(headNode)) {
780
781 Way wayB = nextWayMap.get(wayA);
782
783 //test if wayA is opposite wayB relative to curWay and nextWay
784
785 Node wayANode = wayA.getNode(wayA.getNodesCount() - 2);
786 Node wayBNode = wayB.getNode(1);
787
788 boolean wayAToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode);
789 boolean wayBToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode);
790
791 if (wayAToTheRight != wayBToTheRight) {
792 intersectionCount ++;
793 }
794 }
795 }
796
797 //if odd number of crossings, invert orientation
798 if (intersectionCount % 2 == 1) {
799 curWayInsideToTheRight = !curWayInsideToTheRight;
800 }
801
802 curWay = nextWay;
803 }
804
805 return result;
806 }
807
808 /**
809 * This is a method splits way into smaller parts, using the prepared nodes list as split points.
810 * Uses SplitWayAction.splitWay for the heavy lifting.
811 * @return list of split ways (or original ways if no splitting is done).
812 */
813 private ArrayList<Way> splitWayOnNodes(Way way, Set<Node> nodes) {
814
815 ArrayList<Way> result = new ArrayList<Way>();
816 List<List<Node>> chunks = buildNodeChunks(way, nodes);
817
818 if (chunks.size() > 1) {
819 SplitWayResult split = SplitWayAction.splitWay(Main.map.mapView.getEditLayer(), way, chunks, Collections.<OsmPrimitive>emptyList());
820
821 //execute the command, we need the results
822 cmds.add(split.getCommand());
823 commitCommands(marktr("Split ways into fragments"));
824
825 result.add(split.getOriginalWay());
826 result.addAll(split.getNewWays());
827 } else {
828 //nothing to split
829 result.add(way);
830 }
831
832 return result;
833 }
834
835 /**
836 * Simple chunking version. Does not care about circular ways and result being
837 * proper, we will glue it all back together later on.
838 * @param way the way to chunk
839 * @param splitNodes the places where to cut.
840 * @return list of node paths to produce.
841 */
842 private List<List<Node>> buildNodeChunks(Way way, Collection<Node> splitNodes) {
843 List<List<Node>> result = new ArrayList<List<Node>>();
844 List<Node> curList = new ArrayList<Node>();
845
846 for (Node node : way.getNodes()) {
847 curList.add(node);
848 if (curList.size() > 1 && splitNodes.contains(node)) {
849 result.add(curList);
850 curList = new ArrayList<Node>();
851 curList.add(node);
852 }
853 }
854
855 if (curList.size() > 1) {
856 result.add(curList);
857 }
858
859 return result;
860 }
861
862
863 /**
864 * This method finds witch ways are outer and witch are inner.
865 * @param boundaryWays
866 * @return
867 */
868 private List<AssembledMultipolygon> findPolygons(Collection<AssembledPolygon> boundaries) {
869
870 List<PolygonLevel> list = findOuterWaysImpl(0, boundaries);
871 List<AssembledMultipolygon> result = new ArrayList<AssembledMultipolygon>();
872
873 //take every other level
874 for (PolygonLevel pol : list) {
875 if (pol.level % 2 == 0) {
876 result.add(pol.pol);
877 }
878 }
879
880 return result;
881 }
882
883 /**
884 * Collects outer way and corresponding inner ways from all boundaries.
885 * @param boundaryWays
886 * @return the outermostWay.
887 */
888 private List<PolygonLevel> findOuterWaysImpl(int level, Collection<AssembledPolygon> boundaryWays) {
889
890 //TODO: bad performance for deep nestings...
891 List<PolygonLevel> result = new ArrayList<PolygonLevel>();
892
893 for (AssembledPolygon outerWay : boundaryWays) {
894
895 boolean outerGood = true;
896 List<AssembledPolygon> innerCandidates = new ArrayList<AssembledPolygon>();
897
898 for (AssembledPolygon innerWay : boundaryWays) {
899 if (innerWay == outerWay) {
900 continue;
901 }
902
903 if (wayInsideWay(outerWay, innerWay)) {
904 outerGood = false;
905 break;
906 } else if (wayInsideWay(innerWay, outerWay)) {
907 innerCandidates.add(innerWay);
908 }
909 }
910
911 if (!outerGood) {
912 continue;
913 }
914
915 //add new outer polygon
916 AssembledMultipolygon pol = new AssembledMultipolygon(outerWay);
917 PolygonLevel polLev = new PolygonLevel(pol, level);
918
919 //process inner ways
920 if (innerCandidates.size() > 0) {
921 List<PolygonLevel> innerList = findOuterWaysImpl(level + 1, innerCandidates);
922 result.addAll(innerList);
923
924 for (PolygonLevel pl : innerList) {
925 if (pl.level == level + 1) {
926 pol.innerWays.add(pl.pol.outerWay);
927 }
928 }
929 }
930
931 result.add(polLev);
932 }
933
934 return result;
935 }
936
937 /**
938 * Finds all ways that form inner or outer boundaries.
939 * @param Collection<Way> A list of (splitted) ways that form a multigon and share common end nodes on intersections.
940 * @param Collection<Way> this list is filled with ways that are to be discarded
941 * @return Collection<Collection<Way>> A list of ways that form the outer and inner boundaries of the multigon.
942 */
943 public static List<AssembledPolygon> findBoundaryPolygons(Collection<WayInPolygon> multigonWays, List<Way> discardedResult) {
944 //first find all discardable ways, by getting outer shells.
945 //this will produce incorrect boundaries in some cases, but second pass will fix it.
946
947 List<WayInPolygon> discardedWays = new ArrayList<WayInPolygon>();
948 Set<WayInPolygon> processedWays = new HashSet<WayInPolygon>();
949 WayTraverser traverser = new WayTraverser(multigonWays);
950
951 for (WayInPolygon startWay : multigonWays) {
952 if (processedWays.contains(startWay)) {
953 continue;
954 }
955
956 traverser.startNewWay(startWay);
957
958 List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
959 WayInPolygon lastWay = startWay;
960
961 while (true) {
962 boundary.add(lastWay);
963
964 WayInPolygon bestWay = traverser.advanceNextLeftmostWay();
965 boolean wayInsideToTheRight = bestWay == null ? false : traverser.isLastWayInsideToTheRight();
966
967 if (bestWay == null || processedWays.contains(bestWay) || !wayInsideToTheRight) {
968 //bad segment chain - proceed to discard it
969 lastWay = null;
970 break;
971 } else if (boundary.contains(bestWay)) {
972 //traversed way found - close the way
973 lastWay = bestWay;
974 break;
975 } else {
976 //proceed to next segment
977 lastWay = bestWay;
978 }
979 }
980
981 if (lastWay != null) {
982 //way good
983 processedWays.addAll(boundary);
984
985 //remove junk segments at the start
986 while (boundary.get(0) != lastWay) {
987 discardedWays.add(boundary.get(0));
988 boundary.remove(0);
989 }
990 } else {
991 //way bad
992 discardedWays.addAll(boundary);
993 processedWays.addAll(boundary);
994 }
995 }
996
997 //now we have removed junk segments, collect the real result ways
998
999 traverser.removeWays(discardedWays);
1000
1001 List<AssembledPolygon> result = new ArrayList<AssembledPolygon>();
1002
1003 while (traverser.hasWays()) {
1004
1005 WayInPolygon startWay = traverser.startNewWay();
1006 List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
1007 WayInPolygon curWay = startWay;
1008
1009 do {
1010 boundary.add(curWay);
1011 curWay = traverser.advanceNextRightmostWay();
1012
1013 //should not happen
1014 if (curWay == null || !traverser.isLastWayInsideToTheRight())
1015 throw new RuntimeException("Join areas internal error.");
1016
1017 } while (curWay != startWay);
1018
1019 //build result
1020 traverser.removeWays(boundary);
1021 result.add(new AssembledPolygon(boundary));
1022 }
1023
1024 for (WayInPolygon way : discardedWays) {
1025 discardedResult.add(way.way);
1026 }
1027
1028 //split inner polygons that have several touching parts.
1029 result = fixTouchingPolygons(result);
1030
1031 return result;
1032 }
1033
1034 /**
1035 * This method checks if polygons have several touching parts and splits them in several polygons.
1036 * @param polygon the polygon to process.
1037 */
1038 public static List<AssembledPolygon> fixTouchingPolygons(List<AssembledPolygon> polygons)
1039 {
1040 List<AssembledPolygon> newPolygons = new ArrayList<AssembledPolygon>();
1041
1042 for (AssembledPolygon innerPart : polygons) {
1043 WayTraverser traverser = new WayTraverser(innerPart.ways);
1044
1045 while (traverser.hasWays()) {
1046
1047 WayInPolygon startWay = traverser.startNewWay();
1048 List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
1049 WayInPolygon curWay = startWay;
1050
1051 Node startNode = traverser.getLastWayStartNode();
1052 boundary.add(curWay);
1053
1054 while (startNode != traverser.getLastWayEndNode()) {
1055 curWay = traverser.advanceNextLeftmostWay();
1056 boundary.add(curWay);
1057
1058 //should not happen
1059 if (curWay == null || !traverser.isLastWayInsideToTheRight())
1060 throw new RuntimeException("Join areas internal error.");
1061 }
1062
1063 //build result
1064 traverser.removeWays(boundary);
1065 newPolygons.add(new AssembledPolygon(boundary));
1066 }
1067 }
1068
1069 return newPolygons;
1070 }
1071
1072 /**
1073 * Tests if way is inside other way
1074 * @param outside
1075 * @param inside
1076 * @return
1077 */
1078 public static boolean wayInsideWay(AssembledPolygon inside, AssembledPolygon outside) {
1079 Set<Node> outsideNodes = new HashSet<Node>(outside.getNodes());
1080 List<Node> insideNodes = inside.getNodes();
1081
1082 for (Node insideNode : insideNodes) {
1083
1084 if (!outsideNodes.contains(insideNode))
1085 //simply test the one node
1086 return Geometry.nodeInsidePolygon(insideNode, outside.getNodes());
1087 }
1088
1089 //all nodes shared.
1090 return false;
1091 }
1092
1093 /**
1094 * Joins the lists of ways.
1095 * @param Collection<Way> The list of outer ways that belong to that multigon.
1096 * @return Way The newly created outer way
1097 */
1098 private Multipolygon joinPolygon(AssembledMultipolygon polygon) throws UserCancelException {
1099 Multipolygon result = new Multipolygon(joinWays(polygon.outerWay.ways));
1100
1101 for (AssembledPolygon pol : polygon.innerWays) {
1102 result.innerWays.add(joinWays(pol.ways));
1103 }
1104
1105 return result;
1106 }
1107
1108 /**
1109 * Joins the outer ways and deletes all short ways that can't be part of a multipolygon anyway.
1110 * @param Collection<Way> The list of outer ways that belong to that multigon.
1111 * @return Way The newly created outer way
1112 */
1113 private Way joinWays(List<WayInPolygon> ways) throws UserCancelException {
1114
1115 //leave original orientation, if all paths are reverse.
1116 boolean allReverse = true;
1117 for (WayInPolygon way : ways) {
1118 allReverse &= !way.insideToTheRight;
1119 }
1120
1121 if (allReverse) {
1122 for (WayInPolygon way : ways) {
1123 way.insideToTheRight = !way.insideToTheRight;
1124 }
1125 }
1126
1127 Way joinedWay = joinOrientedWays(ways);
1128
1129 //should not happen
1130 if (joinedWay == null || !joinedWay.isClosed())
1131 throw new RuntimeException("Join areas internal error.");
1132
1133 return joinedWay;
1134 }
1135
1136 /**
1137 * Joins a list of ways (using CombineWayAction and ReverseWayAction as specified in WayInPath)
1138 * @param ArrayList<Way> The list of ways to join and reverse
1139 * @return Way The newly created way
1140 */
1141 private Way joinOrientedWays(List<WayInPolygon> ways) throws UserCancelException{
1142 if (ways.size() < 2)
1143 return ways.get(0).way;
1144
1145 // This will turn ways so all of them point in the same direction and CombineAction won't bug
1146 // the user about this.
1147
1148 //TODO: ReverseWay and Combine way are really slow and we use them a lot here. This slows down large joins.
1149 List<Way> actionWays = new ArrayList<Way>(ways.size());
1150
1151 for (WayInPolygon way : ways) {
1152 actionWays.add(way.way);
1153
1154 if (!way.insideToTheRight) {
1155 ReverseWayResult res = ReverseWayAction.reverseWay(way.way);
1156 Main.main.undoRedo.add(res.getReverseCommand());
1157 cmdsCount++;
1158 }
1159 }
1160
1161 Pair<Way, Command> result = CombineWayAction.combineWaysWorker(actionWays);
1162
1163 Main.main.undoRedo.add(result.b);
1164 cmdsCount ++;
1165
1166 return result.a;
1167 }
1168
1169 /**
1170 * This method analyzes multipolygon relationships of given ways and collects addition inner ways to consider.
1171 * @param selectedWays the selected ways
1172 * @return list of polygons, or null if too complex relation encountered.
1173 */
1174 private List<Multipolygon> collectMultipolygons(List<Way> selectedWays) {
1175
1176 List<Multipolygon> result = new ArrayList<Multipolygon>();
1177
1178 //prepare the lists, to minimize memory allocation.
1179 List<Way> outerWays = new ArrayList<Way>();
1180 List<Way> innerWays = new ArrayList<Way>();
1181
1182 Set<Way> processedOuterWays = new LinkedHashSet<Way>();
1183 Set<Way> processedInnerWays = new LinkedHashSet<Way>();
1184
1185 for (Relation r : OsmPrimitive.getParentRelations(selectedWays)) {
1186 if (r.isDeleted() || !r.isMultipolygon()) {
1187 continue;
1188 }
1189
1190 boolean hasKnownOuter = false;
1191 outerWays.clear();
1192 innerWays.clear();
1193
1194 for (RelationMember rm : r.getMembers()) {
1195 if (rm.getRole().equalsIgnoreCase("outer")) {
1196 outerWays.add(rm.getWay());
1197 hasKnownOuter |= selectedWays.contains(rm.getWay());
1198 }
1199 else if (rm.getRole().equalsIgnoreCase("inner")) {
1200 innerWays.add(rm.getWay());
1201 }
1202 }
1203
1204 if (!hasKnownOuter) {
1205 continue;
1206 }
1207
1208 if (outerWays.size() > 1) {
1209 JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle multipolygon relations with multiple outer ways."));
1210 return null;
1211 }
1212
1213 Way outerWay = outerWays.get(0);
1214
1215 //retain only selected inner ways
1216 innerWays.retainAll(selectedWays);
1217
1218 if (processedOuterWays.contains(outerWay)) {
1219 JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is outer in multiple multipolygon relations."));
1220 return null;
1221 }
1222
1223 if (processedInnerWays.contains(outerWay)) {
1224 JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations."));
1225 return null;
1226 }
1227
1228 for (Way way :innerWays)
1229 {
1230 if (processedOuterWays.contains(way)) {
1231 JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations."));
1232 return null;
1233 }
1234
1235 if (processedInnerWays.contains(way)) {
1236 JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is inner in multiple multipolygon relations."));
1237 return null;
1238 }
1239 }
1240
1241 processedOuterWays.add(outerWay);
1242 processedInnerWays.addAll(innerWays);
1243
1244 Multipolygon pol = new Multipolygon(outerWay);
1245 pol.innerWays.addAll(innerWays);
1246 pol.relation = r;
1247
1248 result.add(pol);
1249 }
1250
1251 //add remaining ways, not in relations
1252 for (Way way : selectedWays) {
1253 if (processedOuterWays.contains(way) || processedInnerWays.contains(way)) {
1254 continue;
1255 }
1256
1257 result.add(new Multipolygon(way));
1258 }
1259
1260 return result;
1261 }
1262
1263 /**
1264 * This method filters the list of relations that form the multipolygons.
1265 * @param relations
1266 * @param polygons
1267 * @return
1268 */
1269 private List<Relation> filterOwnMultipolygonRelations(Collection<Relation> relations, List<Multipolygon> polygons) {
1270
1271 List<Relation> relationsToRemove = new ArrayList<Relation>();
1272
1273 for (Multipolygon m : polygons) {
1274 if (m.relation != null) {
1275 relationsToRemove.add(m.relation);
1276 }
1277 }
1278
1279 List<Relation> result = new ArrayList<Relation>();
1280
1281 result.addAll(relations);
1282 result.removeAll(relationsToRemove);
1283 return result;
1284 }
1285
1286 /**
1287 * Will add own multipolygon relation to the "previously existing" relations. Fixup is done by fixRelations
1288 * @param Collection<Way> List of already closed inner ways
1289 * @param Way The outer way
1290 * @param ArrayList<RelationRole> The list of relation with roles to add own relation to
1291 */
1292 private RelationRole addOwnMultigonRelation(Collection<Way> inner, Way outer) {
1293 if (inner.size() == 0) return null;
1294 // Create new multipolygon relation and add all inner ways to it
1295 Relation newRel = new Relation();
1296 newRel.put("type", "multipolygon");
1297 for (Way w : inner) {
1298 newRel.addMember(new RelationMember("inner", w));
1299 }
1300 cmds.add(new AddCommand(newRel));
1301
1302 // We don't add outer to the relation because it will be handed to fixRelations()
1303 // which will then do the remaining work.
1304 return new RelationRole(newRel, "outer");
1305 }
1306
1307 /**
1308 * Removes a given OsmPrimitive from all relations
1309 * @param OsmPrimitive Element to remove from all relations
1310 * @return ArrayList<RelationRole> List of relations with roles the primitives was part of
1311 */
1312 private ArrayList<RelationRole> removeFromAllRelations(OsmPrimitive osm) {
1313 ArrayList<RelationRole> result = new ArrayList<RelationRole>();
1314
1315 for (Relation r : Main.main.getCurrentDataSet().getRelations()) {
1316 if (r.isDeleted()) {
1317 continue;
1318 }
1319 for (RelationMember rm : r.getMembers()) {
1320 if (rm.getMember() != osm) {
1321 continue;
1322 }
1323
1324 Relation newRel = new Relation(r);
1325 List<RelationMember> members = newRel.getMembers();
1326 members.remove(rm);
1327 newRel.setMembers(members);
1328
1329 cmds.add(new ChangeCommand(r, newRel));
1330 RelationRole saverel = new RelationRole(r, rm.getRole());
1331 if (!result.contains(saverel)) {
1332 result.add(saverel);
1333 }
1334 break;
1335 }
1336 }
1337
1338 commitCommands(marktr("Removed Element from Relations"));
1339 return result;
1340 }
1341
1342 /**
1343 * Adds the previously removed relations again to the outer way. If there are multiple multipolygon
1344 * relations where the joined areas were in "outer" role a new relation is created instead with all
1345 * members of both. This function depends on multigon relations to be valid already, it won't fix them.
1346 * @param ArrayList<RelationRole> List of relations with roles the (original) ways were part of
1347 * @param Way The newly created outer area/way
1348 * @param relationsToDelete - set of relations to delete.
1349 */
1350 private void fixRelations(ArrayList<RelationRole> rels, Way outer, RelationRole ownMultipol, Set<Relation> relationsToDelete) {
1351 ArrayList<RelationRole> multiouters = new ArrayList<RelationRole>();
1352
1353 if (ownMultipol != null){
1354 multiouters.add(ownMultipol);
1355 }
1356
1357 for (RelationRole r : rels) {
1358 if (r.rel.isMultipolygon() && r.role.equalsIgnoreCase("outer")) {
1359 multiouters.add(r);
1360 continue;
1361 }
1362 // Add it back!
1363 Relation newRel = new Relation(r.rel);
1364 newRel.addMember(new RelationMember(r.role, outer));
1365 cmds.add(new ChangeCommand(r.rel, newRel));
1366 }
1367
1368 Relation newRel = null;
1369 switch (multiouters.size()) {
1370 case 0:
1371 return;
1372 case 1:
1373 // Found only one to be part of a multipolygon relation, so just add it back as well
1374 newRel = new Relation(multiouters.get(0).rel);
1375 newRel.addMember(new RelationMember(multiouters.get(0).role, outer));
1376 cmds.add(new ChangeCommand(multiouters.get(0).rel, newRel));
1377 return;
1378 default:
1379 // Create a new relation with all previous members and (Way)outer as outer.
1380 newRel = new Relation();
1381 for (RelationRole r : multiouters) {
1382 // Add members
1383 for (RelationMember rm : r.rel.getMembers())
1384 if (!newRel.getMembers().contains(rm)) {
1385 newRel.addMember(rm);
1386 }
1387 // Add tags
1388 for (String key : r.rel.keySet()) {
1389 newRel.put(key, r.rel.get(key));
1390 }
1391 // Delete old relation
1392 relationsToDelete.add(r.rel);
1393 }
1394 newRel.addMember(new RelationMember("outer", outer));
1395 cmds.add(new AddCommand(newRel));
1396 }
1397 }
1398
1399 /**
1400 * @param Collection<Way> The List of Ways to remove all tags from
1401 */
1402 private void stripTags(Collection<Way> ways) {
1403 for (Way w : ways) {
1404 stripTags(w);
1405 }
1406 /* I18N: current action printed in status display */
1407 commitCommands(marktr("Remove tags from inner ways"));
1408 }
1409
1410 /**
1411 * @param Way The Way to remove all tags from
1412 */
1413 private void stripTags(Way x) {
1414 if (x.getKeys() == null)
1415 return;
1416 Way y = new Way(x);
1417 for (String key : x.keySet()) {
1418 y.remove(key);
1419 }
1420 cmds.add(new ChangeCommand(x, y));
1421 }
1422
1423 /**
1424 * Takes the last cmdsCount actions back and combines them into a single action
1425 * (for when the user wants to undo the join action)
1426 * @param String The commit message to display
1427 */
1428 private void makeCommitsOneAction(String message) {
1429 UndoRedoHandler ur = Main.main.undoRedo;
1430 cmds.clear();
1431 int i = Math.max(ur.commands.size() - cmdsCount, 0);
1432 for (; i < ur.commands.size(); i++) {
1433 cmds.add(ur.commands.get(i));
1434 }
1435
1436 for (i = 0; i < cmds.size(); i++) {
1437 ur.undo();
1438 }
1439
1440 commitCommands(message == null ? marktr("Join Areas Function") : message);
1441 cmdsCount = 0;
1442 }
1443
1444 @Override
1445 protected void updateEnabledState() {
1446 if (getCurrentDataSet() == null) {
1447 setEnabled(false);
1448 } else {
1449 updateEnabledState(getCurrentDataSet().getSelected());
1450 }
1451 }
1452
1453 @Override
1454 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
1455 setEnabled(selection != null && !selection.isEmpty());
1456 }
1457 }