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