Changeset 3554 in josm for trunk/src

Timestamp:

2010-09-22T22:28:06+02:00 (14 years ago)

Author:

bastiK

Message:

see #5179 (patch by viesturs) - improve join areas

File:

• trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (modified) (37 diffs)

trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java

@@ -2 +2 @@
 package org.openstreetmap.josm.actions;
 
+import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.combineTigerTags;
+import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.completeTagCollectionForEditing;
+import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.normalizeTagCollectionBeforeEditing;
 import static org.openstreetmap.josm.tools.I18n.marktr;
 import static org.openstreetmap.josm.tools.I18n.tr;
 import static org.openstreetmap.josm.tools.I18n.trn;
 
-import java.awt.GridBagLayout;
 import java.awt.event.ActionEvent;
 import java.awt.event.KeyEvent;
@@ -14 +16 @@
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
-import java.util.Map.Entry;
 import java.util.Set;
 import java.util.TreeMap;
-import java.util.TreeSet;
-
-import javax.swing.Box;
-import javax.swing.JComboBox;
-import javax.swing.JLabel;
+
 import javax.swing.JOptionPane;
-import javax.swing.JPanel;
 
 import org.openstreetmap.josm.Main;
+import org.openstreetmap.josm.actions.ReverseWayAction.ReverseWayResult;
 import org.openstreetmap.josm.actions.SplitWayAction.SplitWayResult;
 import org.openstreetmap.josm.command.AddCommand;
@@ -37 +36 @@
 import org.openstreetmap.josm.command.DeleteCommand;
 import org.openstreetmap.josm.command.SequenceCommand;
+import org.openstreetmap.josm.corrector.UserCancelException;
 import org.openstreetmap.josm.data.UndoRedoHandler;
 import org.openstreetmap.josm.data.coor.EastNorth;
@@ -45 +45 @@
 import org.openstreetmap.josm.data.osm.Relation;
 import org.openstreetmap.josm.data.osm.RelationMember;
-import org.openstreetmap.josm.data.osm.TigerUtils;
+import org.openstreetmap.josm.data.osm.TagCollection;
 import org.openstreetmap.josm.data.osm.Way;
-import org.openstreetmap.josm.gui.ExtendedDialog;
-import org.openstreetmap.josm.tools.GBC;
+import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
+import org.openstreetmap.josm.tools.Pair;
 import org.openstreetmap.josm.tools.Shortcut;
 
@@ -56 +56 @@
     private int cmdsCount = 0;
 
+
     /**
      * This helper class describes join ares action result.
@@ -63 +64 @@
     public static class JoinAreasResult {
 
-        public Way outerWay;
-        public List<Way> innerWays;
-
         public boolean mergeSuccessful;
         public boolean hasChanges;
         public boolean hasRelationProblems;
-    }
-
-    // HelperClass
-    // Saves a node and two positions where to insert the node into the ways
-    private static class NodeToSegs implements Comparable<NodeToSegs> {
-        public int pos;
-        public Node n;
-        public double dis;
-        public NodeToSegs(int pos, Node n, LatLon dis) {
-            this.pos = pos;
-            this.n = n;
-            this.dis = n.getCoor().greatCircleDistance(dis);
-        }
-
-        public int compareTo(NodeToSegs o) {
-            if(this.pos == o.pos)
-                return (this.dis - o.dis) > 0 ? 1 : -1;
-                return this.pos - o.pos;
-        }
-
-        @Override
-        public int hashCode() {
-            return pos;
-        }
-
-        @Override
-        public boolean equals(Object o) {
-            if (o instanceof NodeToSegs)
-                return compareTo((NodeToSegs) o) == 0;
-            else
-                return false;
+
+        public List<Multipolygon> polygons;
+    }
+
+    public static class Multipolygon {
+        public Way outerWay;
+        public List<Way> innerWays;
+
+        public Relation relation;
+
+        public Multipolygon(Way way) {
+            outerWay = way;
+            innerWays = new ArrayList<Way>();
         }
     }
@@ -126 +106 @@
     }
 
-    /**
-     * HelperClass
-     * saves a way and the "inside" side
-     * insideToTheLeft: if true left side is "in", false -right side is "in".
-     * Left and right are determined along the orientation of way.
-     */
-    private static class WayInPath {
+
+    //HelperClass
+    //saves a way and the "inside" side
+    // insideToTheLeft: if true left side is "in", false -right side is "in". Left and right are determined along the orientation of way.
+    private static class WayInPolygon {
         public final Way way;
-        public boolean insideToTheLeft;
-
-        public WayInPath(Way way, boolean insideLeft) {
-            this.way = way;
-            this.insideToTheLeft = insideLeft;
+        public boolean insideToTheRight;
+
+        public WayInPolygon(Way _way, boolean _insideRight) {
+            this.way = _way;
+            this.insideToTheRight = _insideRight;
         }
 
@@ -148 +126 @@
         @Override
         public boolean equals(Object other) {
-            if (!(other instanceof WayInPath))
-                return false;
-            WayInPath otherMember = (WayInPath) other;
-            return otherMember.way.equals(this.way) && otherMember.insideToTheLeft == this.insideToTheLeft;
-        }
-    }
+            if (!(other instanceof WayInPolygon)) return false;
+            WayInPolygon otherMember = (WayInPolygon) other;
+            return otherMember.way.equals(this.way) && otherMember.insideToTheRight == this.insideToTheRight;
+        }
+    }
+
+    /**
+     * This helper class describes a polygon, assembled from several ways.
+     * @author viesturs
+     *
+     */
+    private static class AssembledPolygon {
+        public List<WayInPolygon> ways;
+
+        public AssembledPolygon(List<WayInPolygon> boundary) {
+            this.ways = boundary;
+        }
+
+        public List<Node> getNodes() {
+            List<Node> nodes = new ArrayList<Node>();
+            for (WayInPolygon way : this.ways) {
+                //do not add the last node as it will be repeated in the next way
+                if (way.insideToTheRight) {
+                    for (int pos = 0; pos < way.way.getNodesCount() - 1; pos++) {
+                        nodes.add(way.way.getNode(pos));
+                    }
+                }
+                else {
+                    for (int pos = way.way.getNodesCount() - 1; pos > 0; pos--) {
+                        nodes.add(way.way.getNode(pos));
+                    }
+                }
+            }
+
+            return nodes;
+        }
+    }
+
+
+    public static class AssembledMultipolygon {
+        public AssembledPolygon outerWay;
+        public List<AssembledPolygon> innerWays;
+
+        public AssembledMultipolygon(AssembledPolygon way) {
+            outerWay = way;
+            innerWays = new ArrayList<AssembledPolygon>();
+        }
+    }
+
+    /**
+     * This hepler class implements algorithm traversing trough connected ways.
+     * Assumes you are going in clockwise orientation.
+     * @author viesturs
+     *
+     */
+    private static class WayTraverser {
+
+        private Set<WayInPolygon> availableWays;
+        private WayInPolygon lastWay;
+        private boolean lastWayReverse;
+
+        public WayTraverser(Collection<WayInPolygon> ways) {
+
+            availableWays = new HashSet<WayInPolygon>(ways);
+            lastWay = null;
+        }
+
+        public void removeWays(Collection<WayInPolygon> ways) {
+            availableWays.removeAll(ways);
+        }
+
+        public boolean hasWays() {
+            return availableWays.size() > 0;
+        }
+
+        public WayInPolygon startNewWay(WayInPolygon way) {
+            lastWay = way;
+            lastWayReverse = !lastWay.insideToTheRight;
+
+            return lastWay;
+        }
+
+        public WayInPolygon startNewWay() {
+            if (availableWays.size() == 0) {
+                lastWay = null;
+            } else {
+                lastWay = availableWays.iterator().next();
+                lastWayReverse = !lastWay.insideToTheRight;
+            }
+
+            return lastWay;
+        }
+
+
+        public  WayInPolygon advanceNextLeftmostWay() {
+            return advanceNextWay(false);
+        }
+
+        public  WayInPolygon advanceNextRightmostWay() {
+            return advanceNextWay(true);
+        }
+
+        private WayInPolygon advanceNextWay(boolean rightmost) {
+
+            Node headNode = !lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
+            Node prevNode = !lastWayReverse ? lastWay.way.getNode(lastWay.way.getNodesCount() - 2) : lastWay.way.getNode(1);
+
+            //find best next way
+            WayInPolygon bestWay = null;
+            Node bestWayNextNode = null;
+            boolean bestWayReverse = false;
+
+            for (WayInPolygon way : availableWays) {
+                if (way.way.firstNode().equals(headNode)) {
+                    //start adjacent to headNode
+                    Node nextNode = way.way.getNode(1);
+
+                    if (nextNode.equals(prevNode))
+                    {
+                        //this is the path we came from - ignore it.
+                    }
+                    else if (bestWay == null || (isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) {
+                        //the new way is better
+                        bestWay = way;
+                        bestWayReverse = false;
+                        bestWayNextNode = nextNode;
+                    }
+                }
+
+                if (way.way.lastNode().equals(headNode)) {
+                    //end adjacent to headNode
+                    Node nextNode = way.way.getNode(way.way.getNodesCount() - 2);
+
+                    if (nextNode.equals(prevNode)) {
+                        //this is the path we came from - ignore it.
+                    }
+                    else if (bestWay == null || (isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) {
+                        //the new way is better
+                        bestWay = way;
+                        bestWayReverse = true;
+                        bestWayNextNode = nextNode;
+                    }
+                }
+            }
+
+            lastWay = bestWay;
+            lastWayReverse = bestWayReverse;
+
+            return lastWay;
+        }
+
+        public boolean isLastWayInsideToTheRight() {
+            return lastWayReverse != lastWay.insideToTheRight;
+        }
+
+        public Node getLastWayStartNode() {
+            return lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
+        }
+
+        public Node getLastWayEndNode() {
+            return lastWayReverse ? lastWay.way.firstNode() : lastWay.way.lastNode();
+        }
+    }
+
+    /**
+     * Provides some node order , based on coordinates, nodes with equal coordinates are equal.
+     * @author viesturs
+     *
+     */
+    private class NodePositionComparator implements Comparator<Node> {
+
+        @Override
+        public int compare(Node n1, Node n2) {
+
+            double dLat = n1.getCoor().lat() - n2.getCoor().lat();
+            double dLon = n1.getCoor().lon() - n2.getCoor().lon();
+
+            if (dLat > 0)
+                return 1;
+            else if (dLat < 0)
+                return -1;
+            else if (dLon == 0) //dlat is 0 here
+                return 0;
+            else
+                return dLon > 0 ? 1 : -1;
+        }
+    }
+
+
+    /**
+     * Helper storage class for finding findOuterWays
+     * @author viesturs
+     */
+    static class PolygonLevel {
+        public final int level;
+        public final AssembledMultipolygon pol;
+
+        public PolygonLevel(AssembledMultipolygon _pol, int _level) {
+            pol = _pol;
+            level = _level;
+        }
+    }
+
 
     // Adds the menu entry, Shortcuts, etc.
@@ -173 +348 @@
         }
 
-        // Too many ways
-        if(ways.size() > 2) {
-            JOptionPane.showMessageDialog(Main.parent, tr("Only up to two areas can be joined at the moment."));
-            return;
-        }
-
         List<Node> allNodes = new ArrayList<Node>();
-        for (Way way: ways) {
-            if(!way.isClosed()) {
+        for (Way way : ways) {
+            if (!way.isClosed()) {
                 JOptionPane.showMessageDialog(Main.parent, tr("\"{0}\" is not closed and therefore cannot be joined.", way.getName()));
                 return;
@@ -192 +361 @@
         Area dataSourceArea = Main.main.getCurrentDataSet().getDataSourceArea();
         if (dataSourceArea != null) {
-            for (Node node: allNodes) {
+            for (Node node : allNodes) {
                 if (!dataSourceArea.contains(node.getCoor())) {
                     int option = JOptionPane.showConfirmDialog(Main.parent,
@@ -209 +378 @@
         }
 
-        if (checkForTagConflicts(ways.getFirst(), ways.getLast()))
-            //there was conflicts and user canceled abort the action.
+        //analyze multipolygon relations and collect all areas
+        List<Multipolygon> areas = collectMultipolygons(ways);
+
+        if (areas == null)
+            //too complex multipolygon relations found
             return;
 
-
-        JoinAreasResult result = joinAreas(ways.getFirst(), ways.getLast());
-
-        if (result.hasChanges) {
-            Main.map.mapView.repaint();
-            DataSet ds = Main.main.getCurrentDataSet();
-            ds.fireSelectionChanged();
-        } else {
+        if (!testJoin(areas)) {
             JOptionPane.showMessageDialog(Main.parent, tr("No intersection found. Nothing was changed."));
-        }
-    }
-
-    /**
-     * Will join two overlapping areas
-     * @param Way First way/area
-     * @param Way Second way/area
-     */
-    private JoinAreasResult joinAreas(Way a, Way b) {
+            return;
+        }
+
+        if (!resolveTagConflicts(areas))
+            return;
+        //user cancelled, do nothing.
+
+        try {
+            JoinAreasResult result = joinAreas(areas);
+
+            if (result.hasChanges) {
+
+                Main.map.mapView.repaint();
+                DataSet ds = Main.main.getCurrentDataSet();
+                ds.fireSelectionChanged();
+            } else {
+                JOptionPane.showMessageDialog(Main.parent, tr("No intersection found. Nothing was changed."));
+            }
+        }
+        catch (UserCancelException exception) {
+            //revert changes
+            //FIXME: this is dirty hack
+            makeCommitsOneAction(tr("Reverting changes"));
+            Main.main.undoRedo.undo();
+            Main.main.undoRedo.redoCommands.clear();
+        }
+    }
+
+
+    /**
+     * Tests if the areas have some intersections to join.
+     * @param areas
+     * @return
+     */
+    private boolean testJoin(List<Multipolygon> areas) {
+        List<Way> allStartingWays = new ArrayList<Way>();
+
+        for (Multipolygon area : areas) {
+            allStartingWays.add(area.outerWay);
+            allStartingWays.addAll(area.innerWays);
+        }
+
+        //find intersection points
+        ArrayList<Node> nodes = addIntersections(allStartingWays, true);
+        return nodes.size() > 0;
+    }
+
+    /**
+     * Will join two or more overlapping areas
+     * @param areas - list of areas to join
+     * @return new area formed.
+     */
+    private JoinAreasResult joinAreas(List<Multipolygon> areas) throws UserCancelException {
 
         JoinAreasResult result = new JoinAreasResult();
         result.hasChanges = false;
 
-        // Fix self-overlapping first or other errors
-        boolean same = a.equals(b);
-        if(!same) {
-            int i = 0;
-
-            //join each area with itself, fixing self-crossings.
-            JoinAreasResult resultA = joinAreas(a, a);
-            JoinAreasResult resultB = joinAreas(b, b);
-
-            if (resultA.mergeSuccessful) {
-                a = resultA.outerWay;
-                ++i;
-            }
-            if(resultB.mergeSuccessful) {
-                b = resultB.outerWay;
-                ++i;
-            }
-
-            result.hasChanges = i > 0;
-            cmdsCount = i;
-        }
-
-        ArrayList<Node> nodes = addIntersections(a, b);
+        List<Way> allStartingWays = new ArrayList<Way>();
+        List<Way> innerStartingWays = new ArrayList<Way>();
+        List<Way> outerStartingWays = new ArrayList<Way>();
+
+        for (Multipolygon area : areas) {
+            outerStartingWays.add(area.outerWay);
+            innerStartingWays.addAll(area.innerWays);
+        }
+
+        allStartingWays.addAll(innerStartingWays);
+        allStartingWays.addAll(outerStartingWays);
+
+        //first remove nodes in the same coordinate
+        boolean removedDuplicates = false;
+        removedDuplicates |= removeDuplicateNodes(allStartingWays);
+
+        if (removedDuplicates) {
+            result.hasChanges = true;
+            commitCommands(marktr("Removed duplicate nodes"));
+        }
+
+        //find intersection points
+        ArrayList<Node> nodes = addIntersections(allStartingWays, false);
 
         //no intersections, return.
-        if(nodes.size() == 0) return result;
+        if (nodes.size() == 0) return result;
         commitCommands(marktr("Added node on all intersections"));
 
+        ArrayList<RelationRole> relations = new ArrayList<RelationRole>();
+
         // Remove ways from all relations so ways can be combined/split quietly
-        ArrayList<RelationRole> relations = removeFromRelations(a);
-        if(!same) {
-            relations.addAll(removeFromRelations(b));
+        for (Way way : allStartingWays) {
+            relations.addAll(removeFromAllRelations(way));
         }
 
         // Don't warn now, because it will really look corrupted
-        boolean warnAboutRelations = relations.size() > 0;
-
-        ArrayList<Way> allWays = splitWaysOnNodes(a, b, nodes);
-
-        // Find inner ways save them to a list
-        ArrayList<WayInPath> outerWays = findOuterWays(allWays);
-        ArrayList<Way> innerWays = findInnerWays(allWays, outerWays);
-
-        // Join outer ways
-        Way outerWay = joinOuterWays(outerWays);
-
-        // Fix Multipolygons if there are any
-        List<Way> newInnerWays = fixMultipolygons(innerWays, outerWay, same);
-
-        // Delete the remaining inner ways
-        if(innerWays != null && innerWays.size() > 0) {
-            cmds.add(DeleteCommand.delete(Main.map.mapView.getEditLayer(), innerWays, true));
+        boolean warnAboutRelations = relations.size() > 0 && allStartingWays.size() > 1;
+
+        ArrayList<WayInPolygon> preparedWays = new ArrayList<WayInPolygon>();
+
+        for (Way way : outerStartingWays) {
+            ArrayList<Way> splitWays = splitWayOnNodes(way, nodes);
+            preparedWays.addAll(markWayInsideSide(splitWays, false));
+        }
+
+        for (Way way : innerStartingWays) {
+            ArrayList<Way> splitWays = splitWayOnNodes(way, nodes);
+            preparedWays.addAll(markWayInsideSide(splitWays, true));
+        }
+
+        // Find boundary ways
+        ArrayList<Way> discardedWays = new ArrayList<Way>();
+        List<AssembledPolygon> bounadries = findBoundaryPolygons(preparedWays, discardedWays);
+
+        //find polygons
+        List<AssembledMultipolygon> preparedPolygons = findPolygons(bounadries);
+
+        //assemble final ways
+        List<Multipolygon> polygons = new ArrayList<Multipolygon>();
+        for (AssembledMultipolygon pol : preparedPolygons) {
+            polygons.add(joinPolygon(pol));
+        }
+
+        // Delete the discarded inner ways
+        if (discardedWays.size() > 0) {
+            cmds.add(DeleteCommand.delete(Main.map.mapView.getEditLayer(), discardedWays, true));
         }
         commitCommands(marktr("Delete Ways that are not part of an inner multipolygon"));
 
         // We can attach our new multipolygon relation and pretend it has always been there
-        addOwnMultigonRelation(newInnerWays, outerWay, relations);
-        fixRelations(relations, outerWay);
+        for (Multipolygon pol : polygons) {
+            addOwnMultigonRelation(pol.innerWays, pol.outerWay, relations);
+            fixRelations(relations, pol.outerWay);
+        }
+
         commitCommands(marktr("Fix relations"));
 
-        stripTags(newInnerWays);
-
-        makeCommitsOneAction(
-                same
-                ? marktr("Joined self-overlapping area")
-                        : marktr("Joined overlapping areas")
-        );
-
-        if(warnAboutRelations) {
+        for (Multipolygon pol : polygons) {
+            stripTags(pol.innerWays);
+        }
+
+        makeCommitsOneAction(marktr("Joined overlapping areas"));
+
+        if (warnAboutRelations) {
             JOptionPane.showMessageDialog(Main.parent, tr("Some of the ways were part of relations that have been modified. Please verify no errors have been introduced."));
         }
@@ -309 +533 @@
         result.hasChanges = true;
         result.mergeSuccessful = true;
-        result.outerWay = outerWay;
-        result.innerWays = newInnerWays;
-
+        result.polygons = polygons;
         return result;
     }
@@ -319 +541 @@
      * @param Way First way to check
      * @param Way Second Way to check
-     * @return boolean True if not all conflicts could be resolved, False if everything's fine
-     */
-    private boolean checkForTagConflicts(Way a, Way b) {
-        ArrayList<Way> ways = new ArrayList<Way>();
-        ways.add(a);
-        ways.add(b);
-
-        // FIXME: This is mostly copied and pasted from CombineWayAction.java and one day should be moved into tools
-        // We have TagCollection handling for that now - use it here as well
-        Map<String, Set<String>> props = new TreeMap<String, Set<String>>();
-        for (Way w : ways) {
-            for (String key: w.keySet()) {
-                if (!props.containsKey(key)) {
-                    props.put(key, new TreeSet<String>());
-                }
-                props.get(key).add(w.get(key));
-            }
-        }
-
-        Way ax = new Way(a);
-        Way bx = new Way(b);
-
-        Map<String, JComboBox> components = new HashMap<String, JComboBox>();
-        JPanel p = new JPanel(new GridBagLayout());
-        for (Entry<String, Set<String>> e : props.entrySet()) {
-            if (TigerUtils.isTigerTag(e.getKey())) {
-                String combined = TigerUtils.combineTags(e.getKey(), e.getValue());
-                ax.put(e.getKey(), combined);
-                bx.put(e.getKey(), combined);
-            } else if (e.getValue().size() > 1) {
-                if("created_by".equals(e.getKey()))
-                {
-                    ax.remove("created_by");
-                    bx.remove("created_by");
+     * @return boolean True if all conflicts are resolved, False if conflicts remain.
+     */
+    private boolean resolveTagConflicts(List<Multipolygon> polygons) {
+
+        List<Way> ways = new ArrayList<Way>();
+
+        for (Multipolygon pol : polygons) {
+            ways.add(pol.outerWay);
+            ways.addAll(pol.innerWays);
+        }
+
+        if (ways.size() < 2)
+            return true;
+
+        //mostly copied from CombineWayAction.java.
+        TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
+        TagCollection completeWayTags = new TagCollection(wayTags);
+        combineTigerTags(completeWayTags);
+        normalizeTagCollectionBeforeEditing(completeWayTags, ways);
+        TagCollection tagsToEdit = new TagCollection(completeWayTags);
+        completeTagCollectionForEditing(tagsToEdit);
+
+        CombinePrimitiveResolverDialog dialog = CombinePrimitiveResolverDialog.getInstance();
+        dialog.getTagConflictResolverModel().populate(tagsToEdit, completeWayTags.getKeysWithMultipleValues());
+        dialog.setTargetPrimitive(ways.get(0));
+        Collection<Relation> parentRelations = CombineWayAction.getParentRelations(ways);
+        parentRelations = filterOwnMultipolygonRelations(parentRelations, polygons);
+        dialog.getRelationMemberConflictResolverModel().populate(
+                parentRelations,
+                ways
+        );
+        dialog.prepareDefaultDecisions();
+
+        // resolve tag conflicts if necessary
+        //
+        if (!completeWayTags.isApplicableToPrimitive() || !parentRelations.isEmpty()) {
+            dialog.setVisible(true);
+            if (dialog.isCancelled())
+                return false;
+        }
+
+        for (Way way : ways) {
+            dialog.setTargetPrimitive(way);
+            cmds.addAll(dialog.buildResolutionCommands());
+        }
+
+        commitCommands(marktr("Fix tag conflicts"));
+        return true;
+    }
+
+
+    /**
+     * This method removes duplicate points (if any) from the input way.
+     * @param way the way to process
+     * @return true if any changes where made
+     */
+    private boolean removeDuplicateNodes(List<Way> ways) {
+        //TODO: maybe join nodes with JoinNodesAction, rather than reconnect the ways.
+
+        Map<Node, Node> nodeMap = new TreeMap<Node, Node>(new NodePositionComparator());
+        int totalNodesRemoved = 0;
+
+        for (Way way : ways) {
+            if (way.getNodes().size() < 2) {
+                continue;
+            }
+
+            int nodesRemoved = 0;
+            List<Node> newNodes = new ArrayList<Node>();
+            Node prevNode = null;
+
+            for (Node node : way.getNodes()) {
+                if (!nodeMap.containsKey(node)) {
+                    //new node
+                    nodeMap.put(node, node);
+
+                    //avoid duplicate nodes
+                    if (prevNode != node) {
+                        newNodes.add(node);
+                    } else {
+                        nodesRemoved ++;
+                    }
                 } else {
-                    JComboBox c = new JComboBox(e.getValue().toArray());
-                    c.setEditable(true);
-                    p.add(new JLabel(e.getKey()), GBC.std());
-                    p.add(Box.createHorizontalStrut(10), GBC.std());
-                    p.add(c, GBC.eol());
-                    components.put(e.getKey(), c);
-                }
-            } else {
-                String val = e.getValue().iterator().next();
-                ax.put(e.getKey(), val);
-                bx.put(e.getKey(), val);
-            }
-        }
-
-        if (components.isEmpty())
-            return false; // No conflicts found
-
-        ExtendedDialog ed = new ExtendedDialog(Main.parent,
-                tr("Enter values for all conflicts."),
-                new String[] {tr("Solve Conflicts"), tr("Cancel")});
-        ed.setButtonIcons(new String[] {"dialogs/conflict.png", "cancel.png"});
-        ed.setContent(p);
-        ed.showDialog();
-
-        if (ed.getValue() != 1) return true; // user cancel, unresolvable conflicts
-
-        for (Entry<String, JComboBox> e : components.entrySet()) {
-            String val = e.getValue().getEditor().getItem().toString();
-            ax.put(e.getKey(), val);
-            bx.put(e.getKey(), val);
-        }
-
-        cmds.add(new ChangeCommand(a, ax));
-        cmds.add(new ChangeCommand(b, bx));
-        commitCommands(marktr("Fix tag conflicts"));
-        return false;
-    }
-
-    /**
-     * Will find all intersection and add nodes there for two given ways
-     * @param Way First way
-     * @param Way Second way
-     * @return ArrayList<OsmPrimitive> List of new nodes
-     */
-    private ArrayList<Node> addIntersections(Way a, Way b) {
-        boolean same = a.equals(b);
-        int nodesSizeA = a.getNodesCount();
-        int nodesSizeB = b.getNodesCount();
-
-        ArrayList<Node> nodes = new ArrayList<Node>();
-        ArrayList<NodeToSegs> nodesA = new ArrayList<NodeToSegs>();
-        ArrayList<NodeToSegs> nodesB = new ArrayList<NodeToSegs>();
-
-        for (int i = (same ? 1 : 0); i < nodesSizeA - 1; i++) {
-            for (int j = (same ? i + 2 : 0); j < nodesSizeB - 1; j++) {
-                // Avoid re-adding nodes that already exist on (some) intersections
-                if(a.getNode(i).equals(b.getNode(j)) || a.getNode(i+1).equals(b.getNode(j)))   {
-                    nodes.add(b.getNode(j));
-                    continue;
-                } else
-                    if(a.getNode(i).equals(b.getNode(j+1)) || a.getNode(i+1).equals(b.getNode(j+1))) {
-                        nodes.add(b.getNode(j+1));
-                        continue;
+                    //node with same coordinates already exists, substitute with existing node
+                    Node representator = nodeMap.get(node);
+
+                    if (representator != node) {
+                        nodesRemoved ++;
                     }
-                LatLon intersection = getLineLineIntersection(
-                        a.getNode(i)  .getEastNorth().east(), a.getNode(i)  .getEastNorth().north(),
-                        a.getNode(i+1).getEastNorth().east(), a.getNode(i+1).getEastNorth().north(),
-                        b.getNode(j)  .getEastNorth().east(), b.getNode(j)  .getEastNorth().north(),
-                        b.getNode(j+1).getEastNorth().east(), b.getNode(j+1).getEastNorth().north());
-                if(intersection == null) {
-                    continue;
-                }
-
-                // Create the node. Adding them to the ways must be delayed because we still loop over them
-                Node n = new Node(intersection);
-                cmds.add(new AddCommand(n));
-                nodes.add(n);
-                // The distance is needed to sort and add the nodes in direction of the way
-                nodesA.add(new NodeToSegs(i,  n, a.getNode(i).getCoor()));
-                if(same) {
-                    nodesA.add(new NodeToSegs(j,  n, a.getNode(j).getCoor()));
-                } else {
-                    nodesB.add(new NodeToSegs(j,  n, b.getNode(j).getCoor()));
-                }
-            }
-        }
-
-        addNodesToWay(a, nodesA);
-        if(!same) {
-            addNodesToWay(b, nodesB);
-        }
-
-        return nodes;
+
+                    //avoid duplicate node
+                    if (prevNode != representator) {
+                        newNodes.add(representator);
+                    }
+                }
+                prevNode = node;
+            }
+
+            if (nodesRemoved > 0) {
+
+                if (newNodes.size() == 1) { //all nodes in the same coordinate - add one more node, to have closed way.
+                    newNodes.add(newNodes.get(0));
+                }
+
+                Way newWay=new Way(way);
+                newWay.setNodes(newNodes);
+                cmds.add(new ChangeCommand(way, newWay));
+                totalNodesRemoved += nodesRemoved;
+            }
+        }
+
+        return totalNodesRemoved > 0;
+    }
+
+
+
+    /**
+     * Will find all intersection and add nodes there for list of given ways. Handles self-intersections too.
+     * And make commands to add the intersection points to ways.
+     * @param List<Way> - a list of ways to test
+     * @return ArrayList<Node> List of new nodes
+     * Prerequisite: no two nodes have the same coordinates.
+     */
+    private ArrayList<Node> addIntersections(List<Way> ways, boolean test) {
+        //TODO: this is a bit slow - O( (number of nodes)^2 + numberOfIntersections * numberOfNodes )
+
+        //stupid java, cannot instantiate array of generic classes..
+        @SuppressWarnings("unchecked")
+        ArrayList<Node>[] newNodes = new ArrayList[ways.size()];
+        boolean[] changedWays = new boolean[ways.size()];
+
+        Set<Node> intersectionNodes = new LinkedHashSet<Node>();
+
+        for (int pos = 0; pos < ways.size(); pos ++) {
+            newNodes[pos] = new ArrayList<Node>(ways.get(pos).getNodes());
+            changedWays[pos] = false;
+        }
+
+        //iterate over all segment pairs and introduce the intersections
+
+        Comparator<Node> coordsComparator = new NodePositionComparator();
+
+        int seg1Way = 0;
+        int seg1Pos = -1;
+
+        while (true) {
+            //advance to next segment
+            seg1Pos++;
+            if (seg1Pos > newNodes[seg1Way].size() - 2) {
+                seg1Way++;
+                seg1Pos = 0;
+
+                if (seg1Way == ways.size()) { //finished
+                    break;
+                }
+            }
+
+
+            //iterate over secondary segment
+
+            int seg2Way = seg1Way;
+            int seg2Pos = seg1Pos + 1;//skip the adjacent segment
+
+            while (true) {
+
+                //advance to next segment
+                seg2Pos++;
+                if (seg2Pos > newNodes[seg2Way].size() - 2) {
+                    seg2Way++;
+                    seg2Pos = 0;
+
+                    if (seg2Way == ways.size()) { //finished
+                        break;
+                    }
+                }
+
+                //need to get them again every time, because other segments may be changed
+                Node seg1Node1 = newNodes[seg1Way].get(seg1Pos);
+                Node seg1Node2 = newNodes[seg1Way].get(seg1Pos + 1);
+                Node seg2Node1 = newNodes[seg2Way].get(seg2Pos);
+                Node seg2Node2 = newNodes[seg2Way].get(seg2Pos + 1);
+
+                int commonCount = 0;
+                //test if we have common nodes to add.
+                if (seg1Node1 == seg2Node1 || seg1Node1 == seg2Node2) {
+                    commonCount ++;
+
+                    if (seg1Way == seg2Way &&
+                            seg1Pos == 0 &&
+                            seg2Pos == newNodes[seg2Way].size() -2) {
+                        //do not add - this is first and last segment of the same way.
+                    } else {
+                        intersectionNodes.add(seg1Node1);
+                    }
+                }
+
+                if (seg1Node2 == seg2Node1 || seg1Node2 == seg2Node2) {
+                    commonCount ++;
+
+                    intersectionNodes.add(seg1Node2);
+                }
+
+                //no common nodes - find intersection
+                if (commonCount == 0) {
+                    LatLon intersection = getLineLineIntersection(
+                            seg1Node1.getEastNorth().east(), seg1Node1.getEastNorth().north(),
+                            seg1Node2.getEastNorth().east(), seg1Node2.getEastNorth().north(),
+                            seg2Node1.getEastNorth().east(), seg2Node1.getEastNorth().north(),
+                            seg2Node2.getEastNorth().east(), seg2Node2.getEastNorth().north());
+
+                    if (intersection != null) {
+                        if (test) {
+                            intersectionNodes.add(seg2Node1);
+                            return new ArrayList<Node>(intersectionNodes);
+                        }
+
+                        Node newNode = new Node(intersection);
+                        Node intNode = newNode;
+                        boolean insertInSeg1 = false;
+                        boolean insertInSeg2 = false;
+
+                        //find if the intersection point is at end point of one of the segments, if so use that point
+
+                        //segment 1
+                        if (coordsComparator.compare(newNode, seg1Node1) == 0) {
+                            intNode = seg1Node1;
+                        } else if (coordsComparator.compare(newNode, seg1Node2) == 0) {
+                            intNode = seg1Node2;
+                        } else {
+                            insertInSeg1 = true;
+                        }
+
+                        //segment 2
+                        if (coordsComparator.compare(newNode, seg2Node1) == 0) {
+                            intNode = seg2Node1;
+                        } else if (coordsComparator.compare(newNode, seg2Node2) == 0) {
+                            intNode = seg2Node2;
+                        } else {
+                            insertInSeg2 = true;
+                        }
+
+                        if (insertInSeg1) {
+                            newNodes[seg1Way].add(seg1Pos +1, intNode);
+                            changedWays[seg1Way] = true;
+
+                            //fix seg2 position, as indexes have changed, seg2Pos is always bigger than seg1Pos on the same segment.
+                            if (seg2Way == seg1Way) {
+                                seg2Pos ++;
+                            }
+                        }
+
+                        if (insertInSeg2) {
+                            newNodes[seg2Way].add(seg2Pos +1, intNode);
+                            changedWays[seg2Way] = true;
+
+                            //Do not need to compare again to already split segment
+                            seg2Pos ++;
+                        }
+
+                        intersectionNodes.add(intNode);
+
+                        if (intNode == newNode) {
+                            cmds.add(new AddCommand(intNode));
+                        }
+                    }
+                }
+                else if (test && intersectionNodes.size() > 0)
+                    return new ArrayList<Node>(intersectionNodes);
+            }
+        }
+
+        for (int pos = 0; pos < ways.size(); pos ++) {
+            if (changedWays[pos] == false) {
+                continue;
+            }
+
+            Way way = ways.get(pos);
+            Way newWay = new Way(way);
+            newWay.setNodes(newNodes[pos]);
+
+            cmds.add(new ChangeCommand(way, newWay));
+        }
+
+        return new ArrayList<Node>(intersectionNodes);
     }
 
@@ -470 +848 @@
         // Solve the equations
         double det = a1*b2 - a2*b1;
-        if(det == 0) return null; // Lines are parallel
+        if (det == 0) return null; // Lines are parallel
 
         return Main.proj.eastNorth2latlon(new EastNorth(
@@ -478 +856 @@
     }
 
-    /**
-     * Inserts given nodes with positions into the given ways
-     * @param Way The way to insert the nodes into
-     * @param Collection<NodeToSegs> The list of nodes with positions to insert
-     */
-    private void addNodesToWay(Way a, ArrayList<NodeToSegs> nodes) {
-        if(nodes.size() == 0)
-            return;
-        Way ax=new Way(a);
-        Collections.sort(nodes);
-
-        int numOfAdds = 1;
-        for(NodeToSegs n : nodes) {
-            ax.addNode(n.pos + numOfAdds, n.n);
-            numOfAdds++;
-        }
-
-        cmds.add(new ChangeCommand(a, ax));
-    }
+
 
     /**
@@ -519 +879 @@
     }
 
-    /**
-     * Removes a given OsmPrimitive from all relations
-     * @param OsmPrimitive Element to remove from all relations
-     * @return ArrayList<RelationRole> List of relations with roles the primitives was part of
-     */
-    private ArrayList<RelationRole> removeFromRelations(OsmPrimitive osm) {
-        ArrayList<RelationRole> result = new ArrayList<RelationRole>();
-        for (Relation r : Main.main.getCurrentDataSet().getRelations()) {
-            if (r.isDeleted()) {
-                continue;
-            }
-            for (RelationMember rm : r.getMembers()) {
-                if (rm.getMember() != osm) {
+
+    /**
+     * This method analyzes the way and assigns each part what direction polygon "inside" is.
+     * @param parts the split parts of the way
+     * @param isInner - if true, reverts the direction (for multipolygon islands)
+     * @return list of parts, marked with the inside orientation.
+     */
+    private ArrayList<WayInPolygon> markWayInsideSide(List<Way> parts, boolean isInner) {
+
+        ArrayList<WayInPolygon> result = new ArrayList<WayInPolygon>();
+
+        //prepare prev and next maps
+        Map<Way, Way> nextWayMap = new HashMap<Way, Way>();
+        Map<Way, Way> prevWayMap = new HashMap<Way, Way>();
+
+        for (int pos = 0; pos < parts.size(); pos ++) {
+
+            if (!parts.get(pos).lastNode().equals(parts.get((pos + 1) % parts.size()).firstNode()))
+                throw new RuntimeException("Way not circular");
+
+            nextWayMap.put(parts.get(pos), parts.get((pos + 1) % parts.size()));
+            prevWayMap.put(parts.get(pos), parts.get((pos + parts.size() - 1) % parts.size()));
+        }
+
+        //find the node with minimum y - it's guaranteed to be outer. (What about the south pole?)
+        Way topWay = null;
+        Node topNode = null;
+        int topIndex = 0;
+        double minY = Double.POSITIVE_INFINITY;
+
+        for (Way way : parts) {
+            for (int pos = 0; pos < way.getNodesCount(); pos ++) {
+                Node node = way.getNode(pos);
+
+                if (node.getEastNorth().getY() < minY) {
+                    minY = node.getEastNorth().getY();
+                    topWay = way;
+                    topNode = node;
+                    topIndex = pos;
+                }
+            }
+        }
+
+        //get the upper way and it's orientation.
+
+        boolean wayClockwise; // orientation of the top way.
+
+        if (topNode.equals(topWay.firstNode()) || topNode.equals(topWay.lastNode())) {
+            Node headNode = null; // the node at junction
+            Node prevNode = null; // last node from previous path
+            wayClockwise = false;
+
+            //node is in split point - find the outermost way from this point
+
+            headNode = topNode;
+            //make a fake node that is downwards from head node (smaller Y). It will be a division point between paths.
+            prevNode = new Node(new EastNorth(headNode.getEastNorth().getX(), headNode.getEastNorth().getY() - 1e5));
+
+            topWay = null;
+            wayClockwise = false;
+            Node bestWayNextNode = null;
+
+            for (Way way : parts) {
+                if (way.firstNode().equals(headNode)) {
+                    Node nextNode = way.getNode(1);
+
+                    if (topWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) {
+                        //the new way is better
+                        topWay = way;
+                        wayClockwise = true;
+                        bestWayNextNode = nextNode;
+                    }
+                }
+
+                if (way.lastNode().equals(headNode)) {
+                    //end adjacent to headNode
+                    Node nextNode = way.getNode(way.getNodesCount() - 2);
+
+                    if (topWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) {
+                        //the new way is better
+                        topWay = way;
+                        wayClockwise = false;
+                        bestWayNextNode = nextNode;
+                    }
+                }
+            }
+        } else {
+            //node is inside way - pick the clockwise going end.
+            Node prev = topWay.getNode(topIndex - 1);
+            Node next = topWay.getNode(topIndex + 1);
+
+            //there will be no parallel segments in the middle of way, so all fine.
+            wayClockwise = angleIsClockwise(prev, topNode, next);
+        }
+
+        Way curWay = topWay;
+        boolean curWayInsideToTheRight = wayClockwise ^ isInner;
+
+        //iterate till full circle is reached
+        while (true) {
+
+            //add cur way
+            WayInPolygon resultWay = new WayInPolygon(curWay, curWayInsideToTheRight);
+            result.add(resultWay);
+
+            //process next way
+            Way nextWay = nextWayMap.get(curWay);
+            Node prevNode = curWay.getNode(curWay.getNodesCount() - 2);
+            Node headNode = curWay.lastNode();
+            Node nextNode = nextWay.getNode(1);
+
+            if (nextWay == topWay) {
+                //full loop traversed - all done.
+                break;
+            }
+
+
+            //find intersecting segments
+            // the intersections will look like this:
+            //
+            //                       ^
+            //                       |
+            //                       X wayBNode
+            //                       |
+            //                  wayB |
+            //                       |
+            //             curWay    |       nextWay
+            //----X----------------->X----------------------X---->
+            //    prevNode           ^headNode              nextNode
+            //                       |
+            //                       |
+            //                  wayA |
+            //                       |
+            //                       X wayANode
+            //                       |
+
+            int intersectionCount = 0;
+
+            for (Way wayA : parts) {
+
+                if (wayA == curWay) {
                     continue;
                 }
 
-                Relation newRel = new Relation(r);
-                List<RelationMember> members = newRel.getMembers();
-                members.remove(rm);
-                newRel.setMembers(members);
-
-                cmds.add(new ChangeCommand(r, newRel));
-                RelationRole saverel =  new RelationRole(r, rm.getRole());
-                if(!result.contains(saverel)) {
-                    result.add(saverel);
-                }
-                break;
-            }
-        }
-
-        commitCommands(marktr("Removed Element from Relations"));
+                if (wayA.lastNode().equals(headNode)) {
+
+                    Way wayB = nextWayMap.get(wayA);
+
+                    //test if wayA is opposite wayB relative to curWay and nextWay
+
+                    Node wayANode = wayA.getNode(wayA.getNodesCount() - 2);
+                    Node wayBNode = wayB.getNode(1);
+
+                    boolean wayAToTheRight = isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode);
+                    boolean wayBToTheRight = isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode);
+
+                    if (wayAToTheRight != wayBToTheRight) {
+                        intersectionCount ++;
+                    }
+                }
+            }
+
+            //if odd number of crossings, invert orientation
+            if (intersectionCount % 2 == 1) {
+                curWayInsideToTheRight = !curWayInsideToTheRight;
+            }
+
+            curWay = nextWay;
+        }
+
         return result;
     }
 
     /**
-     * This method splits ways into smaller parts, using the prepared nodes list as split points.
-     * Uses SplitWayAction.splitWay for the heavy lifting.
+     * This is a method splits way into smaller parts, using the prepared nodes list as split points.
+     * Uses  SplitWayAction.splitWay for the heavy lifting.
      * @return list of split ways (or original ways if no splitting is done).
      */
-    private ArrayList<Way> splitWaysOnNodes(Way a, Way b, Collection<Node> nodes) {
+    private ArrayList<Way> splitWayOnNodes(Way way, Collection<Node> nodes) {
 
         ArrayList<Way> result = new ArrayList<Way>();
-        List<Way> ways = new ArrayList<Way>();
-        ways.add(a);
-        ways.add(b);
-
-        for (Way way: ways) {
-            List<List<Node>> chunks = buildNodeChunks(way, nodes);
+        List<List<Node>> chunks = buildNodeChunks(way, nodes);
+
+        if (chunks.size() > 1) {
             SplitWayResult split = SplitWayAction.splitWay(Main.map.mapView.getEditLayer(), way, chunks, Collections.<OsmPrimitive>emptyList());
 
             //execute the command, we need the results
-            Main.main.undoRedo.add(split.getCommand());
-            cmdsCount ++;
+            cmds.add(split.getCommand());
+            commitCommands(marktr("Split ways into fragments"));
 
             result.add(split.getOriginalWay());
             result.addAll(split.getNewWays());
+        } else {
+            //nothing to split
+            result.add(way);
         }
 
         return result;
     }
+
 
     /**
@@ -584 +1084 @@
      * @param way the way to chunk
      * @param splitNodes the places where to cut.
-     * @return list of node segments to produce.
-     */
-    private List<List<Node>> buildNodeChunks(Way way, Collection<Node> splitNodes)
-    {
+     * @return list of node paths to produce.
+     */
+    private List<List<Node>> buildNodeChunks(Way way, Collection<Node> splitNodes) {
         List<List<Node>> result = new ArrayList<List<Node>>();
         List<Node> curList = new ArrayList<Node>();
 
-        for(Node node: way.getNodes()){
+        for (Node node : way.getNodes()) {
             curList.add(node);
-            if (curList.size() > 1 && splitNodes.contains(node)){
+            if (curList.size() > 1 && splitNodes.contains(node)) {
                 result.add(curList);
                 curList = new ArrayList<Node>();
@@ -600 +1099 @@
         }
 
-        if (curList.size() > 1)
-        {
+        if (curList.size() > 1) {
             result.add(curList);
         }
@@ -608 +1106 @@
     }
 
-    /**
-     * Returns all nodes for given ways
-     * @param Collection<Way> The list of ways which nodes are to be returned
-     * @return Collection<Node> The list of nodes the ways contain
-     */
-    private Collection<Node> getNodesFromWays(Collection<Way> ways) {
-        Collection<Node> allNodes = new ArrayList<Node>();
-        for(Way w: ways) {
-            allNodes.addAll(w.getNodes());
-        }
-        return allNodes;
-    }
-
-    /**
-     * Gets all inner ways given all ways and outer ways.
-     * @param multigonWays
-     * @param outerWays
-     * @return list of inner ways.
-     */
-    private ArrayList<Way> findInnerWays(Collection<Way> multigonWays, Collection<WayInPath> outerWays) {
-        ArrayList<Way> innerWays = new ArrayList<Way>();
-        Set<Way> outerSet = new HashSet<Way>();
-
-        for(WayInPath w: outerWays) {
-            outerSet.add(w.way);
-        }
-
-        for(Way way: multigonWays) {
-            if (!outerSet.contains(way)) {
-                innerWays.add(way);
-            }
-        }
-
-        return innerWays;
-    }
-
-
-    /**
-     * Finds all ways for a given list of Ways that form the outer hull.
-     * This works by starting with one node and traversing the multigon clockwise, always picking the leftmost path.
-     * Prerequisites - the ways must not intersect and have common end nodes where they meet.
-     * @param Collection<Way> A list of (splitted) ways that form a multigon
-     * @return Collection<Way> A list of ways that form the outer boundary of the multigon.
-     */
-    private static ArrayList<WayInPath> findOuterWays(Collection<Way> multigonWays) {
-
-        //find the node with minimum lat - it's guaranteed to be outer. (What about the south pole?)
-        Way bestWay = null;
-        Node topNode = null;
-        int topIndex = 0;
-        double minLat = Double.POSITIVE_INFINITY;
-
-        for(Way way: multigonWays) {
-            for (int pos = 0; pos < way.getNodesCount(); pos ++) {
-                Node node = way.getNode(pos);
-
-                if (node.getCoor().lat() < minLat) {
-                    minLat = node.getCoor().lat();
-                    bestWay = way;
-                    topNode = node;
-                    topIndex = pos;
-                }
-            }
-        }
-
-        //get two final nodes from best way to mark as starting point and orientation.
-        Node headNode = null;
-        Node prevNode = null;
-
-        if (topNode.equals(bestWay.firstNode()) || topNode.equals(bestWay.lastNode())) {
-            //node is in split point
-            headNode = topNode;
-            //make a fake node that is downwards from head node (smaller latitude). It will be a division point between paths.
-            prevNode = new Node(new LatLon(headNode.getCoor().lat() - 1000, headNode.getCoor().lon()));
-        } else {
-            //node is inside way - pick the clockwise going end.
-            Node prev = bestWay.getNode(topIndex - 1);
-            Node next = bestWay.getNode(topIndex + 1);
-
-            if (angleIsClockwise(prev, topNode, next)) {
-                headNode = bestWay.lastNode();
-                prevNode = bestWay.getNode(bestWay.getNodesCount() - 2);
-            }
-            else {
-                headNode = bestWay.firstNode();
-                prevNode = bestWay.getNode(1);
-            }
-        }
-
-        Set<Way> outerWays = new HashSet<Way>();
-        ArrayList<WayInPath> result = new ArrayList<WayInPath>();
-
-        //iterate till full circle is reached
-        while (true) {
-
-            bestWay = null;
-            Node bestWayNextNode = null;
-            boolean bestWayReverse = false;
-
-            for (Way way: multigonWays) {
-                boolean wayReverse;
-                Node nextNode;
-
-                if (way.firstNode().equals(headNode)) {
-                    //start adjacent to headNode
-                    nextNode = way.getNode(1);
-                    wayReverse = false;
-
-                    if (nextNode.equals(prevNode)) {
-                        //this is the path we came from - ignore it.
-                    } else if (bestWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) {
-                        //the new way is better
-                        bestWay = way;
-                        bestWayReverse = wayReverse;
-                        bestWayNextNode = nextNode;
+
+    /**
+     * This method finds witch ways are outer and witch are inner.
+     * @param boundaryWays
+     * @return
+     */
+    private List<AssembledMultipolygon> findPolygons(Collection<AssembledPolygon> boundaries) {
+
+        List<PolygonLevel> list = findOuterWaysImpl(0, boundaries);
+        List<AssembledMultipolygon> result = new ArrayList<AssembledMultipolygon>();
+
+        //take every other level
+        for (PolygonLevel pol : list) {
+            if (pol.level % 2 == 0) {
+                result.add(pol.pol);
+            }
+        }
+
+        return result;
+    }
+
+    /**
+     * Collects outer way and corresponding inner ways from all boundaries.
+     * @param boundaryWays
+     * @return the outermostWay.
+     */
+    private List<PolygonLevel> findOuterWaysImpl(int level, Collection<AssembledPolygon> boundaryWays) {
+
+        //TODO: bad performance for deep nestings...
+        List<PolygonLevel> result = new ArrayList<PolygonLevel>();
+
+        for (AssembledPolygon outerWay : boundaryWays) {
+
+            boolean outerGood = true;
+            List<AssembledPolygon> innerCandidates = new ArrayList<AssembledPolygon>();
+
+            for (AssembledPolygon innerWay : boundaryWays) {
+                if (innerWay == outerWay) {
+                    continue;
+                }
+
+                if (wayInsideWay(outerWay, innerWay)) {
+                    outerGood = false;
+                    break;
+                } else if (wayInsideWay(innerWay, outerWay)) {
+                    innerCandidates.add(innerWay);
+                }
+            }
+
+            if (!outerGood) {
+                continue;
+            }
+
+            //add new outer polygon
+            AssembledMultipolygon pol = new AssembledMultipolygon(outerWay);
+            PolygonLevel polLev = new PolygonLevel(pol, level);
+
+            //process inner ways
+            if (innerCandidates.size() > 0) {
+                List<PolygonLevel> innerList = findOuterWaysImpl(level + 1, innerCandidates);
+                result.addAll(innerList);
+
+                for (PolygonLevel pl : innerList) {
+                    if (pl.level == level + 1) {
+                        pol.innerWays.add(pl.pol.outerWay);
                     }
                 }
-
-                if (way.lastNode().equals(headNode)) {
-                    //end adjacent to headNode
-                    nextNode = way.getNode(way.getNodesCount() - 2);
-                    wayReverse = true;
-
-                    if (nextNode.equals(prevNode)) {
-                        //this is the path we came from - ignore it.
-                    } else if (bestWay == null || !isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) {
-                        //the new way is better
-                        bestWay = way;
-                        bestWayReverse = wayReverse;
-                        bestWayNextNode = nextNode;
-                    }
-                }
-            }
-
-            if (bestWay == null)
-                throw new RuntimeException();
-            else if (outerWays.contains(bestWay)) {
-                break; //full circle reached, terminate.
+            }
+
+            result.add(polLev);
+        }
+
+        return result;
+    }
+
+
+
+    /**
+     * Finds all ways that form inner or outer boundaries.
+     * @param Collection<Way> A list of (splitted) ways that form a multigon and share common end nodes on intersections.
+     * @param Collection<Way> this list is filled with ways that are to be discarded
+     * @return Collection<Collection<Way>> A list of ways that form the outer and inner boundaries of the multigon.
+     */
+    public static List<AssembledPolygon> findBoundaryPolygons(Collection<WayInPolygon> multigonWays, List<Way> discardedResult) {
+        //first find all discardable ways, by getting outer shells.
+        //this will produce incorrect boundaries in some cases, but second pass will fix it.
+
+        List<WayInPolygon> discardedWays = new ArrayList<WayInPolygon>();
+        Set<WayInPolygon> processedWays = new HashSet<WayInPolygon>();
+        WayTraverser traverser = new WayTraverser(multigonWays);
+
+        for (WayInPolygon startWay : multigonWays) {
+            if (processedWays.contains(startWay)) {
+                continue;
+            }
+
+            traverser.startNewWay(startWay);
+
+            List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
+            WayInPolygon lastWay = startWay;
+
+            while (true) {
+                boundary.add(lastWay);
+
+                WayInPolygon bestWay = traverser.advanceNextLeftmostWay();
+                boolean wayInsideToTheRight = bestWay == null ? false : traverser.isLastWayInsideToTheRight();
+
+                if (bestWay == null || processedWays.contains(bestWay) || !wayInsideToTheRight) {
+                    //bad segment chain - proceed to discard it
+                    lastWay = null;
+                    break;
+                } else if (boundary.contains(bestWay)) {
+                    //traversed way found - close the way
+                    lastWay = bestWay;
+                    break;
+                } else {
+                    //proceed to next segment
+                    lastWay = bestWay;
+                }
+            }
+
+            if (lastWay != null) {
+                //way good
+                processedWays.addAll(boundary);
+
+                //remove junk segments at the start
+                while (boundary.get(0) != lastWay) {
+                    discardedWays.add(boundary.get(0));
+                    boundary.remove(0);
+                }
             } else {
-                //add to outer ways, repeat.
-                outerWays.add(bestWay);
-                result.add(new WayInPath(bestWay, bestWayReverse));
-                headNode = bestWayReverse ? bestWay.firstNode() : bestWay.lastNode();
-                prevNode = bestWayReverse ? bestWay.getNode(1) : bestWay.getNode(bestWay.getNodesCount() - 2);
-            }
-        }
+                //way bad
+                discardedWays.addAll(boundary);
+                processedWays.addAll(boundary);
+            }
+        }
+
+        //now we have removed junk segments, collect the real result ways
+
+        traverser.removeWays(discardedWays);
+
+        List<AssembledPolygon> result = new ArrayList<AssembledPolygon>();
+
+        while (traverser.hasWays()) {
+
+            WayInPolygon startWay = traverser.startNewWay();
+            List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
+            WayInPolygon curWay = startWay;
+
+            do {
+                boundary.add(curWay);
+                curWay = traverser.advanceNextRightmostWay();
+
+                //should not happen
+                if (curWay == null || !traverser.isLastWayInsideToTheRight())
+                    throw new RuntimeException("Join areas internal error.");
+
+            } while (curWay != startWay);
+
+            //build result
+            traverser.removeWays(boundary);
+            result.add(new AssembledPolygon(boundary));
+        }
+
+        for (WayInPolygon way : discardedWays) {
+            discardedResult.add(way.way);
+        }
+
+        //split inner polygons that have several touching parts.
+        result = fixTouchingPolygons(result);
 
         return result;
     }
+
+
+    /**
+     * This method checks if polygons have several touching parts and splits them in several polygons.
+     * @param polygon the polygon to process.
+     */
+    public static List<AssembledPolygon> fixTouchingPolygons(List<AssembledPolygon> polygons)
+    {
+        List<AssembledPolygon> newPolygons = new ArrayList<AssembledPolygon>();
+
+        for (AssembledPolygon innerPart : polygons) {
+            WayTraverser traverser = new WayTraverser(innerPart.ways);
+
+            while (traverser.hasWays()) {
+
+                WayInPolygon startWay = traverser.startNewWay();
+                List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
+                WayInPolygon curWay = startWay;
+
+                Node startNode = traverser.getLastWayStartNode();
+                boundary.add(curWay);
+
+                while (startNode != traverser.getLastWayEndNode()) {
+                    curWay = traverser.advanceNextLeftmostWay();
+                    boundary.add(curWay);
+
+                    //should not happen
+                    if (curWay == null || !traverser.isLastWayInsideToTheRight())
+                        throw new RuntimeException("Join areas internal error.");
+                }
+
+                //build result
+                traverser.removeWays(boundary);
+                newPolygons.add(new AssembledPolygon(boundary));
+            }
+        }
+
+        return newPolygons;
+    }
+
 
     /**
@@ -766 +1328 @@
      * @return true if to the right side, false otherwise
      */
-    public static boolean isToTheRightSideOfLine(Node lineP1, Node lineP2, Node lineP3, Node testPoint)
-    {
+    public static boolean isToTheRightSideOfLine(Node lineP1, Node lineP2, Node lineP3, Node testPoint) {
         boolean pathBendToRight = angleIsClockwise(lineP1, lineP2, lineP3);
         boolean rightOfSeg1 = angleIsClockwise(lineP1, lineP2, testPoint);
@@ -785 +1346 @@
      * @return true if first vector is clockwise before second vector.
      */
-    public static boolean angleIsClockwise(Node commonNode, Node firstNode, Node secondNode)
-    {
-        double dla1 = (firstNode.getCoor().lat() - commonNode.getCoor().lat());
-        double dla2 = (secondNode.getCoor().lat() - commonNode.getCoor().lat());
-        double dlo1 = (firstNode.getCoor().lon() - commonNode.getCoor().lon());
-        double dlo2 = (secondNode.getCoor().lon() - commonNode.getCoor().lon());
-
-        return dla1 * dlo2 - dlo1 * dla2 > 0;
+
+    public static boolean angleIsClockwise(Node commonNode, Node firstNode, Node secondNode) {
+        double dy1 = (firstNode.getEastNorth().getY() - commonNode.getEastNorth().getY());
+        double dy2 = (secondNode.getEastNorth().getY() - commonNode.getEastNorth().getY());
+        double dx1 = (firstNode.getEastNorth().getX() - commonNode.getEastNorth().getX());
+        double dx2 = (secondNode.getEastNorth().getX() - commonNode.getEastNorth().getX());
+
+        return dy1 * dx2 - dx1 * dy2 > 0;
+    }
+
+
+    /**
+     * Tests if way is inside other way
+     * @param outside
+     * @param inside
+     * @return
+     */
+    public static boolean wayInsideWay(AssembledPolygon inside, AssembledPolygon outside) {
+        Set<Node> outsideNodes = new HashSet<Node>(outside.getNodes());
+
+        for (Node insideNode : inside.getNodes()) {
+
+            if (!outsideNodes.contains(insideNode))
+                //simply test the one node
+                return nodeInsidePolygon(insideNode, outside.getNodes());
+        }
+
+        //all nodes shared.
+        return false;
     }
 
@@ -802 +1384 @@
      * FIXME: this should probably be moved to tools..
      */
-    public static boolean nodeInsidePolygon(ArrayList<Node> polygonNodes, Node point)
-    {
+    public static boolean nodeInsidePolygon(Node point, List<Node> polygonNodes) {
         if (polygonNodes.size() < 3)
             return false;
@@ -813 +1394 @@
         Node oldPoint = polygonNodes.get(polygonNodes.size() - 1);
 
-        for(Node newPoint: polygonNodes)
-        {
+        for (Node newPoint : polygonNodes) {
             //skip duplicate points
             if (newPoint.equals(oldPoint)) {
@@ -821 +1401 @@
 
             //order points so p1.lat <= p2.lat;
-            if (newPoint.getCoor().lat() > oldPoint.getCoor().lat())
-            {
+            if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) {
                 p1 = oldPoint;
                 p2 = newPoint;
-            }
-            else
-            {
+            } else {
                 p1 = newPoint;
                 p2 = oldPoint;
@@ -833 +1410 @@
 
             //test if the line is crossed and if so invert the inside flag.
-            if ((newPoint.getCoor().lat() < point.getCoor().lat()) == (point.getCoor().lat() <= oldPoint.getCoor().lat())
-                    && (point.getCoor().lon() - p1.getCoor().lon()) * (p2.getCoor().lat() - p1.getCoor().lat())
-                    < (p2.getCoor().lon() - p1.getCoor().lon()) * (point.getCoor().lat() - p1.getCoor().lat()))
+            if ((newPoint.getEastNorth().getY() < point.getEastNorth().getY()) == (point.getEastNorth().getY() <= oldPoint.getEastNorth().getY())
+                    && (point.getEastNorth().getX() - p1.getEastNorth().getX()) * (p2.getEastNorth().getY() - p1.getEastNorth().getY())
+                    < (p2.getEastNorth().getX() - p1.getEastNorth().getX()) * (point.getEastNorth().getY() - p1.getEastNorth().getY()))
             {
                 inside = !inside;
@@ -845 +1422 @@
         return inside;
     }
+
+
+    /**
+     * Joins the lists of ways.
+     * @param Collection<Way> The list of outer ways that belong to that multigon.
+     * @return Way The newly created outer way
+     */
+    private Multipolygon  joinPolygon(AssembledMultipolygon polygon) throws UserCancelException {
+        Multipolygon result = new Multipolygon(joinWays(polygon.outerWay.ways));
+
+        for (AssembledPolygon pol : polygon.innerWays) {
+            result.innerWays.add(joinWays(pol.ways));
+        }
+
+        return result;
+    }
+
 
     /**
@@ -851 +1445 @@
      * @return Way The newly created outer way
      */
-    private Way joinOuterWays(ArrayList<WayInPath> outerWays) {
+    private Way joinWays(List<WayInPolygon> ways) throws UserCancelException {
 
         //leave original orientation, if all paths are reverse.
         boolean allReverse = true;
-        for(WayInPath way: outerWays) {
-            allReverse &= way.insideToTheLeft;
+        for (WayInPolygon way : ways) {
+            allReverse &= !way.insideToTheRight;
         }
 
         if (allReverse) {
-            for(WayInPath way: outerWays){
-                way.insideToTheLeft = !way.insideToTheLeft;
-            }
-        }
-
-        commitCommands(marktr("Join Areas: Remove Short Ways"));
-        Way joinedWay = joinOrientedWays(outerWays);
-        if (joinedWay != null)
-            return closeWay(joinedWay);
-        else
-            return null;
-    }
-
-    /**
-     * Ensures a way is closed. If it isn't, last and first node are connected.
-     * @param Way the way to ensure it's closed
-     * @return Way The joined way.
-     */
-    private Way closeWay(Way w) {
-        if(w.isClosed())
-            return w;
-        Main.main.getCurrentDataSet().setSelected(w);
-        Way wnew = new Way(w);
-        wnew.addNode(wnew.firstNode());
-        cmds.add(new ChangeCommand(w, wnew));
-        commitCommands(marktr("Closed Way"));
-        return (Way)(Main.main.getCurrentDataSet().getSelectedWays().toArray())[0];
-    }
+            for (WayInPolygon way : ways) {
+                way.insideToTheRight = !way.insideToTheRight;
+            }
+        }
+
+        Way joinedWay = joinOrientedWays(ways);
+
+        //should not happen
+        if (joinedWay == null || !joinedWay.isClosed())
+            throw new RuntimeException("Join areas internal error.");
+
+        return joinedWay;
+    }
+
 
     /**
@@ -894 +1474 @@
      * @return Way The newly created way
      */
-    private Way joinOrientedWays(ArrayList<WayInPath> ways) {
-        if(ways.size() < 2)
+    private Way joinOrientedWays(List<WayInPolygon> ways) throws UserCancelException{
+        if (ways.size() < 2)
             return ways.get(0).way;
 
@@ -901 +1481 @@
         // the user about this.
 
+        //TODO: ReverseWay and Combine way are really slow and we use them a lot here. This slows down large joins.
         List<Way> actionWays = new ArrayList<Way>(ways.size());
 
-        for(WayInPath way : ways) {
+        for (WayInPolygon way : ways) {
             actionWays.add(way.way);
 
-            if (way.insideToTheLeft) {
-                Main.main.getCurrentDataSet().setSelected(way.way);
-                new ReverseWayAction().actionPerformed(null);
+            if (!way.insideToTheRight) {
+                ReverseWayResult res = ReverseWayAction.reverseWay(way.way);
+                Main.main.undoRedo.add(res.getReverseCommand());
                 cmdsCount++;
             }
         }
 
-        Way result = new CombineWayAction().combineWays(actionWays);
-
-        if(result != null) {
-            cmdsCount++;
-        }
+        Pair<Way, Command> result = CombineWayAction.combineWaysWorker(actionWays);
+
+        Main.main.undoRedo.add(result.b);
+        cmdsCount ++;
+
+        return result.a;
+    }
+
+
+    /**
+     * This method analyzes multipolygon relationships of given ways and collects addition inner ways to consider.
+     * @param selectedWays the selected ways
+     * @return list of polygons, or null if too complex relation encountered.
+     */
+    private List<Multipolygon> collectMultipolygons(List<Way> selectedWays) {
+
+        List<Multipolygon> result = new ArrayList<Multipolygon>();
+
+        //prepare the lists, to minimize memory allocation.
+        List<Way> outerWays = new ArrayList<Way>();
+        List<Way> innerWays = new ArrayList<Way>();
+
+        Set<Way> processedOuterWays = new LinkedHashSet<Way>();
+        Set<Way> processedInnerWays = new LinkedHashSet<Way>();
+
+        for (Relation r : CombineWayAction.getParentRelations(selectedWays)) {
+            if (r.isDeleted() ||
+                    r.get("type") == null ||
+                    !r.get("type").equalsIgnoreCase("multipolygon")) {
+                continue;
+            }
+
+            boolean hasKnownOuter = false;
+            outerWays.clear();
+            innerWays.clear();
+
+            for (RelationMember rm : r.getMembers()) {
+                if (rm.getRole().equalsIgnoreCase("outer")) {
+                    outerWays.add(rm.getWay());
+                    hasKnownOuter |= selectedWays.contains(rm.getWay());
+                }
+                else if (rm.getRole().equalsIgnoreCase("inner")) {
+                    innerWays.add(rm.getWay());
+                }
+            }
+
+            if (!hasKnownOuter) {
+                continue;
+            }
+
+            if (outerWays.size() > 1) {
+                JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle multipolygon relations with multiple outer ways."));
+                return null;
+            }
+
+            Way outerWay = outerWays.get(0);
+
+            //retain only selected inner ways
+            innerWays.retainAll(selectedWays);
+
+            if (processedOuterWays.contains(outerWay)) {
+                JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is outer in multiple multipolygon relations."));
+                return null;
+            }
+
+            if (processedInnerWays.contains(outerWay)) {
+                JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations."));
+                return null;
+            }
+
+            for (Way way :innerWays)
+            {
+                if (processedOuterWays.contains(way)) {
+                    JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations."));
+                    return null;
+                }
+
+                if (processedInnerWays.contains(way)) {
+                    JOptionPane.showMessageDialog(Main.parent, tr("Sorry. Cannot handle way that is inner in multiple multipolygon relations."));
+                    return null;
+                }
+            }
+
+            processedOuterWays.add(outerWay);
+            processedInnerWays.addAll(innerWays);
+
+            Multipolygon pol = new Multipolygon(outerWay);
+            pol.innerWays.addAll(innerWays);
+            pol.relation = r;
+
+            result.add(pol);
+        }
+
+        //add remaining ways, not in relations
+        for (Way way : selectedWays) {
+            if (processedOuterWays.contains(way) || processedInnerWays.contains(way)) {
+                continue;
+            }
+
+            result.add(new Multipolygon(way));
+        }
+
         return result;
     }
 
-    /**
-     * Joins a list of ways (using CombineWayAction and ReverseWayAction if necessary to quiet the former)
-     * @param ArrayList<Way> The list of ways to join
-     * @return Way The newly created way
-     */
-    private Way joinWays(ArrayList<Way> ways) {
-        if(ways.size() < 2)
-            return ways.get(0);
-
-        // This will turn ways so all of them point in the same direction and CombineAction won't bug
-        // the user about this.
-        Way a = null;
-        for (Way b : ways) {
-            if(a == null) {
-                a = b;
-                continue;
-            }
-            if(a.getNode(0).equals(b.getNode(0)) ||
-                    a.getNode(a.getNodesCount()-1).equals(b.getNode(b.getNodesCount()-1))) {
-                Main.main.getCurrentDataSet().setSelected(b);
-                new ReverseWayAction().actionPerformed(null);
-                cmdsCount++;
-            }
-            a = b;
-        }
-        if ((a = new CombineWayAction().combineWays(ways)) != null) {
-            cmdsCount++;
-        }
-        return a;
-    }
-
-    /**
-     * Finds all ways that may be part of a multipolygon relation and removes them from the given list.
-     * It will automatically combine "good" ways
-     * @param Collection<Way> The list of inner ways to check
-     * @param Way The newly created outer way
-     * @return ArrayList<Way> The List of newly created inner ways
-     */
-    private ArrayList<Way> fixMultipolygons(Collection<Way> uninterestingWays, Way outerWay, boolean selfintersect) {
-        Collection<Node> innerNodes = getNodesFromWays(uninterestingWays);
-        Collection<Node> outerNodes = outerWay.getNodes();
-
-        // The newly created inner ways. uninterestingWays is passed by reference and therefore modified in-place
-        ArrayList<Way> newInnerWays = new ArrayList<Way>();
-
-        // Now we need to find all inner ways that contain a remaining node, but no outer nodes
-        // Remaining nodes are those that contain to more than one way. All nodes that belong to an
-        // inner multigon part will have at least two ways, so we can use this to find which ways do
-        // belong to the multigon.
-        ArrayList<Way> possibleWays = new ArrayList<Way>();
-        wayIterator: for(Way w : uninterestingWays) {
-            boolean hasInnerNodes = false;
-            for(Node n : w.getNodes()) {
-                if(outerNodes.contains(n)) {
-                    if(!selfintersect) { // allow outer point for self intersection
-                        continue wayIterator;
-                    }
-                }
-                else if(!hasInnerNodes && innerNodes.contains(n)) {
-                    hasInnerNodes = true;
-                }
-            }
-            if(!hasInnerNodes || w.getNodesCount() < 2) {
-                continue;
-            }
-            possibleWays.add(w);
-        }
-
-        // This removes unnecessary ways that might have been added.
-        removeAlmostAlikeWays(possibleWays);
-
-        // loop twice
-        // in k == 0 prefer ways which allow no Y-joining (i.e. which have only 1 solution)
-        for(int k = 0; k < 2; ++k)
-        {
-            // Join all ways that have one start/ending node in common
-            Way joined = null;
-            outerIterator: do {
-                removePartlyUnconnectedWays(possibleWays);
-                joined = null;
-                for(Way w1 : possibleWays) {
-                    if(w1.isClosed()) {
-                        if(!wayIsCollapsed(w1)) {
-                            uninterestingWays.remove(w1);
-                            newInnerWays.add(w1);
-                        }
-                        joined = w1;
-                        possibleWays.remove(w1);
-                        continue outerIterator;
-                    }
-                    ArrayList<Way> secondary = new ArrayList<Way>();
-                    for(Way w2 : possibleWays) {
-                        int i = 0;
-                        // w2 cannot be closed, otherwise it would have been removed above
-                        if(w1.equals(w2)) {
-                            continue;
-                        }
-                        if(w2.isFirstLastNode(w1.firstNode())) {
-                            ++i;
-                        }
-                        if(w2.isFirstLastNode(w1.lastNode())) {
-                            ++i;
-                        }
-                        if(i == 2) // this way closes w1 - take it!
-                        {
-                            if(secondary.size() > 0) {
-                                secondary.clear();
-                            }
-                            secondary.add(w2);
-                            break;
-                        }
-                        else if(i > 0) {
-                            secondary.add(w2);
-                        }
-                    }
-                    if(k == 0 ? secondary.size() == 1 : secondary.size() > 0)
-                    {
-                        ArrayList<Way> joinThem = new ArrayList<Way>();
-                        joinThem.add(w1);
-                        joinThem.add(secondary.get(0));
-                        // Although we joined the ways, we cannot simply assume that they are closed
-                        if((joined = joinWays(joinThem)) != null)
-                        {
-                            uninterestingWays.removeAll(joinThem);
-                            possibleWays.removeAll(joinThem);
-
-                            //List<Node> nodes = joined.getNodes();
-                            // check if we added too much
-                            /*for(int i = 1; i < nodes.size()-2; ++i)
-                            {
-                                if(nodes.get(i) == nodes.get(nodes.size()-1))
-                                    System.out.println("Joining of ways produced unexpecteded result\n");
-                            }*/
-                            uninterestingWays.add(joined);
-                            possibleWays.add(joined);
-                            continue outerIterator;
-                        }
-                    }
-                }
-            } while(joined != null);
-        }
-        return newInnerWays;
-    }
-
-    /**
-     * Removes almost alike ways (= ways that are on top of each other for all nodes)
-     * @param ArrayList<Way> the ways to remove almost-duplicates from
-     */
-    private void removeAlmostAlikeWays(ArrayList<Way> ways) {
-        Collection<Way> removables = new ArrayList<Way>();
-        outer: for(int i=0; i < ways.size(); i++) {
-            Way a = ways.get(i);
-            for(int j=i+1; j < ways.size(); j++) {
-                Way b = ways.get(j);
-                List<Node> revNodes = new ArrayList<Node>(b.getNodes());
-                Collections.reverse(revNodes);
-                if(a.getNodes().equals(b.getNodes()) || a.getNodes().equals(revNodes)) {
-                    removables.add(a);
-                    continue outer;
-                }
-            }
-        }
-        ways.removeAll(removables);
-    }
-
-    /**
-     * Removes ways from the given list whose starting or ending node doesn't
-     * connect to other ways from the same list (it's like removing spikes).
-     * @param ArrayList<Way> The list of ways to remove "spikes" from
-     */
-    private void removePartlyUnconnectedWays(ArrayList<Way> ways) {
-        List<Way> removables = new ArrayList<Way>();
-        for(Way a : ways) {
-            if(a.isClosed()) {
-                continue;
-            }
-            boolean connectedStart = false;
-            boolean connectedEnd = false;
-            for(Way b : ways) {
-                if(a.equals(b)) {
-                    continue;
-                }
-                if(b.isFirstLastNode(a.firstNode())) {
-                    connectedStart = true;
-                }
-                if(b.isFirstLastNode(a.lastNode())) {
-                    connectedEnd = true;
-                }
-            }
-            if(!connectedStart || !connectedEnd) {
-                removables.add(a);
-            }
-        }
-        ways.removeAll(removables);
-    }
-
-    /**
-     * Checks if a way is collapsed (i.e. looks like <---->)
-     * @param Way A *closed* way to check if it is collapsed
-     * @return boolean If the closed way is collapsed or not
-     */
-    private boolean wayIsCollapsed(Way w) {
-        if(w.getNodesCount() <= 3) return true;
-
-        // If a way contains more than one node twice, it must be collapsed (only start/end node may be the same)
-        Way x = new Way(w);
-        int count = 0;
-        for(Node n : w.getNodes()) {
-            x.removeNode(n);
-            if(x.containsNode(n)) {
-                count++;
-            }
-            if(count == 2) return true;
-        }
-        return false;
-    }
+
+    /**
+     * This method filters the list of relations that form the multipolygons.
+     * @param relations
+     * @param polygons
+     * @return
+     */
+    private List<Relation> filterOwnMultipolygonRelations(Collection<Relation> relations, List<Multipolygon> polygons) {
+
+        List<Relation> relationsToRemove = new ArrayList<Relation>();
+
+        for (Multipolygon m : polygons) {
+            if (m.relation != null) {
+                relationsToRemove.add(m.relation);
+            }
+        }
+
+        List<Relation> result = new ArrayList<Relation>();
+
+        result.addAll(relations);
+        result.removeAll(relationsToRemove);
+        return result;
+    }
+
 
     /**
@@ -1145 +1631 @@
      */
     private void addOwnMultigonRelation(Collection<Way> inner, Way outer, ArrayList<RelationRole> rels) {
-        if(inner.size() == 0) return;
+        if (inner.size() == 0) return;
         // Create new multipolygon relation and add all inner ways to it
         Relation newRel = new Relation();
         newRel.put("type", "multipolygon");
-        for(Way w : inner) {
+        for (Way w : inner) {
             newRel.addMember(new RelationMember("inner", w));
         }
@@ -1161 +1647 @@
     }
 
+
+    /**
+     * Removes a given OsmPrimitive from all relations
+     * @param OsmPrimitive Element to remove from all relations
+     * @return ArrayList<RelationRole> List of relations with roles the primitives was part of
+     */
+    private ArrayList<RelationRole> removeFromAllRelations(OsmPrimitive osm) {
+        ArrayList<RelationRole> result = new ArrayList<RelationRole>();
+
+        for (Relation r : Main.main.getCurrentDataSet().getRelations()) {
+            if (r.isDeleted()) {
+                continue;
+            }
+            for (RelationMember rm : r.getMembers()) {
+                if (rm.getMember() != osm) {
+                    continue;
+                }
+
+                Relation newRel = new Relation(r);
+                List<RelationMember> members = newRel.getMembers();
+                members.remove(rm);
+                newRel.setMembers(members);
+
+                cmds.add(new ChangeCommand(r, newRel));
+                RelationRole saverel =  new RelationRole(r, rm.getRole());
+                if (!result.contains(saverel)) {
+                    result.add(saverel);
+                }
+                break;
+            }
+        }
+
+        commitCommands(marktr("Removed Element from Relations"));
+        return result;
+    }
+
+
     /**
      * Adds the previously removed relations again to the outer way. If there are multiple multipolygon
@@ -1170 +1693 @@
     private void fixRelations(ArrayList<RelationRole> rels, Way outer) {
         ArrayList<RelationRole> multiouters = new ArrayList<RelationRole>();
-        for(RelationRole r : rels) {
-            if( r.rel.get("type") != null &&
+        for (RelationRole r : rels) {
+            if (r.rel.get("type") != null &&
                     r.rel.get("type").equalsIgnoreCase("multipolygon") &&
                     r.role.equalsIgnoreCase("outer")
@@ -1185 +1708 @@
 
         Relation newRel = null;
-        switch(multiouters.size()) {
+        switch (multiouters.size()) {
         case 0:
             return;
@@ -1197 +1720 @@
             // Create a new relation with all previous members and (Way)outer as outer.
             newRel = new Relation();
-            for(RelationRole r : multiouters) {
+            for (RelationRole r : multiouters) {
                 // Add members
-                for(RelationMember rm : r.rel.getMembers())
-                    if(!newRel.getMembers().contains(rm)) {
+                for (RelationMember rm : r.rel.getMembers())
+                    if (!newRel.getMembers().contains(rm)) {
                         newRel.addMember(rm);
                     }
@@ -1219 +1742 @@
      */
     private void stripTags(Collection<Way> ways) {
-        for(Way w: ways) {
+        for (Way w : ways) {
             stripTags(w);
         }
@@ -1229 +1752 @@
      */
     private void stripTags(Way x) {
-        if(x.getKeys() == null) return;
+        if (x.getKeys() == null)
+            return;
         Way y = new Way(x);
         for (String key : x.keySet()) {
@@ -1246 +1770 @@
         cmds.clear();
         int i = Math.max(ur.commands.size() - cmdsCount, 0);
-        for(; i < ur.commands.size(); i++) {
+        for (; i < ur.commands.size(); i++) {
             cmds.add(ur.commands.get(i));
         }
 
-        for(i = 0; i < cmds.size(); i++) {
+        for (i = 0; i < cmds.size(); i++) {
             ur.undo();
         }