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