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