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