Changeset 28116 in osm for applications/editors/josm/plugins/utilsplugin2

Timestamp:

2012-03-19T01:57:46+01:00 (13 years ago)

Author:

joshdoe

Message:

utilsplugin2: use improved assignment method for Replace Geometry (see #josm7295)

Location:

applications/editors/josm/plugins/utilsplugin2/src

Files:

• edu (added)
• edu/princeton (added)
• edu/princeton/cs (added)
• edu/princeton/cs/algs4 (added)
• edu/princeton/cs/algs4/AssignmentProblem.java (added)
• edu/princeton/cs/algs4/Bag.java (added)
• edu/princeton/cs/algs4/DijkstraSP.java (added)
• edu/princeton/cs/algs4/DirectedEdge.java (added)
• edu/princeton/cs/algs4/EdgeWeightedDigraph.java (added)
• edu/princeton/cs/algs4/IndexMinPQ.java (added)
• edu/princeton/cs/algs4/Stack.java (added)
• org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/HungarianAlgorithm.java (deleted)
• org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/ReplaceGeometryUtils.java (modified) (4 diffs)

applications/editors/josm/plugins/utilsplugin2/src/org/openstreetmap/josm/plugins/utilsplugin2/replacegeometry/ReplaceGeometryUtils.java

@@ -1 +1 @@
 package org.openstreetmap.josm.plugins.utilsplugin2.replacegeometry;
 
+import edu.princeton.cs.algs4.AssignmentProblem;
 import java.awt.geom.Area;
 import java.awt.geom.Point2D;
@@ -264 +265 @@
         }
 
-        boolean useHungarian = Main.pref.getBoolean("utilsplugin2.replace-geometry.robustAssignment", false);
+        boolean useRobust = Main.pref.getBoolean("utilsplugin2.replace-geometry.robustAssignment", true);
         
         // Find new nodes that are closest to the old ones, remove matching old ones from the pool
@@ -270 +271 @@
         Map<Node, Node> nodeAssoc = new HashMap<Node, Node>();
         if (geometryPool.size() > 0 && nodePool.size() > 0) {
-            if (useHungarian) {  // use robust, but slower assignment
+            if (useRobust) {  // use robust, but slower assignment
                 int gLen = geometryPool.size();
                 int nLen = nodePool.size();
-                double cost[][] = new double[nLen][gLen];
+                int N = Math.max(gLen, nLen);
+                double cost[][] = new double[N][N];
+                for (int i = 0; i < N; i++) {
+                    for (int j = 0; j < N; j++) {
+                        cost[i][j] = Double.MAX_VALUE;
+                    }
+                }
 
                 double maxDistance = Double.parseDouble(Main.pref.get("utilsplugin2.replace-geometry.max-distance", "1"));
@@ -286 +293 @@
                     }
                 }
-                int[][] assignment = HungarianAlgorithm.hgAlgorithm(cost, "min");
-                for (int i = 0; i < nLen; i++) {
-                    int nIdx = assignment[i][0];
-                    int gIdx = assignment[i][1];
+                AssignmentProblem assignment = new AssignmentProblem(cost);
+                for (int i = 0; i < N; i++) {
+                    int nIdx = i;
+                    int gIdx = assignment.sol(i);
                     if (cost[nIdx][gIdx] != Double.MAX_VALUE) {
                         nodeAssoc.put(geometryPool.get(gIdx), nodePool.get(nIdx));