Changeset 28027 in osm

Timestamp:

2012-03-10T06:18:26+01:00 (13 years ago)

Author:

joshdoe

Message:

utilsplugin2, conflation: better assignment of nodes with Replace Geometry

Move Hungarian code from conflation to utilsplugin2, since the former depends on the latter already.

Location:

applications/editors/josm/plugins

Files:

• conflation/src/org/openstreetmap/josm/plugins/conflation/ConflationCandidateList.java (modified) (1 diff)
• conflation/src/org/openstreetmap/josm/plugins/conflation/ConflationToggleDialog.java (modified) (4 diffs)
• utilsplugin2/src/utilsplugin2/dumbutils/HungarianAlgorithm.java (moved) (moved from applications/editors/josm/plugins/conflation/src/org/openstreetmap/josm/plugins/conflation/HungarianAlgorithm.java ) (1 diff)
• utilsplugin2/src/utilsplugin2/dumbutils/ReplaceGeometryUtils.java (modified) (2 diffs)

applications/editors/josm/plugins/conflation/src/org/openstreetmap/josm/plugins/conflation/ConflationCandidateList.java

@@ -1 @@
-/*
- * To change this template, choose Tools | Templates
- * and open the template in the editor.
- */
 package org.openstreetmap.josm.plugins.conflation;
 

applications/editors/josm/plugins/conflation/src/org/openstreetmap/josm/plugins/conflation/ConflationToggleDialog.java

@@ -1 +1 @@
 package org.openstreetmap.josm.plugins.conflation;
 
+import utilsplugin2.dumbutils.HungarianAlgorithm;
 import java.awt.BorderLayout;
 import java.awt.Component;
@@ -206 +207 @@
         @Override
         public void actionPerformed(ActionEvent e) {
+            //FIXME: should layer listen for selection change?
             ConflationCandidate c = conflationLayer.getSelectedCandidate();
+            if (c.getReferenceLayer() != c.getSubjectLayer()) {
+                JOptionPane.showMessageDialog(Main.parent, tr("Conflation between layers isn't supported yet."),
+                        tr("Cannot conflate between layes"), JOptionPane.ERROR_MESSAGE);
+                return;
+            }
             if (ReplaceGeometryUtils.replace(c.getReferenceObject(), c.getSubjectObject())) {
                 candidates.remove(c);
@@ -331 +338 @@
             int n = subjectSelection.size();
             int m = referenceSelection.size();
-            int maxLen = Math.max(n, m);
-            double cost[][] = new double[maxLen][maxLen];
+            double cost[][] = new double[n][m];
 
             // calculate cost matrix
@@ -345 +351 @@
             OsmPrimitive subObject, refObject;
             candidates.clear();
-            for (int i = 0; i < maxLen; i++) {
+            for (int i = 0; i < n; i++) {
                 int subIdx = assignment[i][0];
                 int refIdx = assignment[i][1];

applications/editors/josm/plugins/utilsplugin2/src/utilsplugin2/dumbutils/HungarianAlgorithm.java

@@ -37 +37 @@
  */
 
-package org.openstreetmap.josm.plugins.conflation;
+package utilsplugin2.dumbutils;
 
 import static java.lang.Math.*;

applications/editors/josm/plugins/utilsplugin2/src/utilsplugin2/dumbutils/ReplaceGeometryUtils.java

@@ -256 +256 @@
         
         // Prepare a list of nodes that are not used anywhere except in the way
-        Collection<Node> nodePool = getUnimportantNodes(subjectWay);
+        List<Node> nodePool = getUnimportantNodes(subjectWay);
 
         // And the same for geometry, list nodes that can be freely deleted
-        Set<Node> geometryPool = new HashSet<Node>();
+        List<Node> geometryPool = new LinkedList<Node>();
         for( Node node : referenceWay.getNodes() ) {
             List<OsmPrimitive> referrers = node.getReferrers();
             if( node.isNew() && !node.isDeleted() && referrers.size() == 1
                     && referrers.get(0).equals(referenceWay) && !subjectWay.containsNode(node)
-                    && !hasInterestingKey(node))
+                    && !hasInterestingKey(node) && !geometryPool.contains(node))
                 geometryPool.add(node);
         }
 
         // Find new nodes that are closest to the old ones, remove matching old ones from the pool
+        // Assign node moves with least overall distance moved
         Map<Node, Node> nodeAssoc = new HashMap<Node, Node>();
-        for( Node n : geometryPool ) {
-            Node nearest = findNearestNode(n, nodePool);
-            if( nearest != null ) {
-                nodeAssoc.put(n, nearest);
-                nodePool.remove(nearest);
-            }
+        if (geometryPool.size() > 0 && nodePool.size() > 0) {
+            int gLen = geometryPool.size();
+            int nLen = nodePool.size();
+            double cost[][] = new double[nLen][gLen];
+
+            double maxDistance = Double.parseDouble(Main.pref.get("utilsplugin2.replace-geometry.max-distance", "1"));
+            for (int i = 0; i < nLen; i++) {
+                for (int j = 0; j < gLen; j++) {
+                    double d = nodePool.get(i).getCoor().distance(geometryPool.get(j).getCoor());
+                    if (d > maxDistance)
+                        cost[i][j] = Double.MAX_VALUE;
+                    else
+                        cost[i][j] = d;
+                }
+            }
+            int[][] assignment = HungarianAlgorithm.hgAlgorithm(cost, "min");
+            for (int i = 0; i < nLen; i++) {
+                int nIdx = assignment[i][0];
+                int gIdx = assignment[i][1];
+                if (cost[nIdx][gIdx] != Double.MAX_VALUE) {
+                    nodeAssoc.put(geometryPool.get(gIdx), nodePool.get(nIdx));
+                }
+            }
+        }
+        
+        // node will be moved, remove from pool
+        for (Node n : nodeAssoc.values()) {
+            nodePool.remove(n);
         }
 
@@ -319 +342 @@
      * @return 
      */
-    protected static Collection<Node> getUnimportantNodes(Way way) {
-        Set<Node> nodePool = new HashSet<Node>();
+    protected static List<Node> getUnimportantNodes(Way way) {
+        List<Node> nodePool = new LinkedList<Node>();
         for (Node n : way.getNodes()) {
             List<OsmPrimitive> referrers = n.getReferrers();
             if (!n.isDeleted() && referrers.size() == 1 && referrers.get(0).equals(way)
-                    && !hasInterestingKey(n)) {
+                    && !hasInterestingKey(n) && !nodePool.contains(n)) {
                 nodePool.add(n);
             }