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