Changeset 4385 in josm for trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java

Timestamp:

31.08.2011 15:29:36 (9 months ago)

Author:

bastiK

Message:

fixed #6190 - orthogonalize produces strange shapes

File:

• trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java (modified) (5 diffs)

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

@@ -14 +14 @@
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.Iterator;
 import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
 
 import javax.swing.JOptionPane;
@@ -161 +164 @@
                     }
                     else if (nodeList.isEmpty()) {
-                        // collect groups of ways with common nodes and orthogonalize each group separately.
-                        ArrayList<ArrayList<WayData>> groups = new ArrayList<ArrayList<WayData>>();
-                        for (WayData w: wayDataList) {
-                            boolean add = false;
-                            for (ArrayList<WayData> g: groups) {
-                                for (WayData groupedWay: g) {
-                                    if (!Collections.disjoint(w.way.getNodes(), groupedWay.way.getNodes())) {
-                                        add = true;
-                                        break;
-                                    }
-                                }
-                                if (add) {
-                                    g.add(w);
-                                }
-                            }
-                            if (!add) {
-                                ArrayList<WayData> newGroup = new ArrayList<WayData>();
-                                newGroup.add(w);
-                                groups.add(newGroup);
-                            }
-                        }
+                        List<ArrayList<WayData>> groups = buildGroups(wayDataList);
                         for (ArrayList<WayData> g: groups) {
                             commands.addAll(orthogonalize(g, nodeList));
@@ -208 +191 @@
                         tr("Selected Elements cannot be orthogonalized"),
                         JOptionPane.INFORMATION_MESSAGE);
+            }
+        }
+    }
+    
+    /**
+     * Collect groups of ways with common nodes in order to orthogonalize each group separately.
+     */
+    private static List<ArrayList<WayData>> buildGroups(ArrayList<WayData> wayDataList) {
+        List<ArrayList<WayData>> groups = new ArrayList<ArrayList<WayData>>();
+        Set<WayData> remaining = new HashSet<WayData>(wayDataList);
+        while (!remaining.isEmpty()) {
+            ArrayList<WayData> group = new ArrayList<WayData>();
+            groups.add(group);
+            Iterator<WayData> it = remaining.iterator();
+            WayData next = it.next();
+            it.remove();
+            extendGroupRec(group, next, new ArrayList<WayData>(remaining));
+            remaining.removeAll(group);
+        }
+        return groups;
+    }
+    
+    private static void extendGroupRec(List<WayData> group, WayData newGroupMember, List<WayData> remaining) {
+        group.add(newGroupMember);
+        for (int i = 0; i < remaining.size(); ++i) {
+            WayData candidate = remaining.get(i);
+            if (candidate == null) continue;
+            if (!Collections.disjoint(candidate.way.getNodes(), newGroupMember.way.getNodes())) {
+                remaining.set(i, null);
+                extendGroupRec(group, candidate, remaining);
             }
         }
@@ -302 +315 @@
             final HashSet<Node> s = new HashSet<Node>(allNodes);
             int s_size = s.size();
-            for (int dummy = 0; dummy < s_size; ++ dummy) {
+            for (int dummy = 0; dummy < s_size; ++dummy) {
                 if (s.isEmpty()) {
                     break;
@@ -522 +535 @@
     /**
      * Recognize angle to be approximately 0, 90, 180 or 270 degrees.
-     * returns a integral value, corresponding to a counter clockwise turn:
+     * returns an integral value, corresponding to a counter clockwise turn:
      */
     private static int angleToDirectionChange(double a, double deltaMax) throws RejectedAngleException {