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