Changeset 25007 in osm for applications

Timestamp:

2011-01-09T13:49:23+01:00 (14 years ago)

Author:

mzdila

Message:

• removing the best match according to description in #5421
• merging nearby nodes in second step

File:

• applications/editors/josm/plugins/simplifyarea/src/sk/zdila/josm/plugin/simplify/SimplifyAreaAction.java (modified) (6 diffs)

applications/editors/josm/plugins/simplifyarea/src/sk/zdila/josm/plugin/simplify/SimplifyAreaAction.java

@@ -10 +10 @@
 import java.awt.event.ActionEvent;
 import java.awt.event.KeyEvent;
-import java.util.ArrayList;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Map;
 
 import javax.swing.JOptionPane;
@@ -168 +169 @@
      */
         private SequenceCommand simplifyWay(final Way w) {
-        final double angleThreshold = Main.pref.getDouble("simplify-area.angle", 10);
-        final double mergeThreshold = Main.pref.getDouble("simplify-area.merge", 0.2);
-        final double areaThreshold = Main.pref.getDouble("simplify-area.area", 5.0);
-        final double distanceThreshold = Main.pref.getDouble("simplify-area.dist", 3);
+        final double angleThreshold = Main.pref.getDouble("simplify-area.angle.threshold", 10);
+        final double angleFactor = Main.pref.getDouble("simplify-area.angle.factor", 1.0);
+        final double mergeThreshold = Main.pref.getDouble("simplify-area.merge.threshold", 0.2);
+        final double areaThreshold = Main.pref.getDouble("simplify-area.area.threshold", 5.0);
+        final double areaFactor = Main.pref.getDouble("simplify-area.area.factor", 1.0);
+        final double distanceThreshold = Main.pref.getDouble("simplify-area.dist.threshold", 3);
+        final double distanceFactor = Main.pref.getDouble("simplify-area.dist.factor", 3);
 
         final List<Node> nodes = w.getNodes();
@@ -180 +184 @@
         }
 
-        final List<MoveCommand> moveCommandList = new ArrayList<MoveCommand>();
-
         final boolean closed = nodes.get(0).equals(nodes.get(size - 1));
-
-        final List<Node> newNodes = new ArrayList<Node>(size);
 
         if (closed) {
@@ -190 +190 @@
         }
 
-        // remove near nodes
-        for (int i = 0; i < size; i++) {
-            final boolean closing = closed && i == size - 1;
-            final Node n1 = closing ? nodes.get(0) : nodes.get(i);
-
-            if (newNodes.isEmpty()) {
-                newNodes.add(n1);
-                continue;
-            }
-
-            final Node n2 = newNodes.get(newNodes.size() - 1);
-
-            final LatLon coord1 = n1.getCoor();
-            final LatLon coord2 = n2.getCoor();
-
-            if (isRequiredNode(w, n1) || isRequiredNode(w, n2) || coord1.greatCircleDistance(coord2) > mergeThreshold) {
-                if (!closing) {
-                    newNodes.add(n1);
-                }
-            } else {
-                moveCommandList.add(new MoveCommand(n2, coord1.getCenter(coord2)));
-                if (closing) {
-                    newNodes.remove(0);
-                }
-            }
-        }
-
-        final int size2 = newNodes.size();
-
-        final List<Node> newNodes2 = new ArrayList<Node>(size2);
-
-        Node prevNode = null;
-        LatLon coord1 = null;
-        LatLon coord2 = null;
-
-        for (int i = 0, j = 0, len = size2 + (closed ? 2 : 1); i < len; i++, j++) {
-            final Node n = newNodes.get(j % newNodes.size());
-            final LatLon coord3 = n.getCoor();
-
-            if (coord1 != null) {
-//              System.out.print("AREA: " + computeArea(coord1, coord2, coord3) + "; ANGLE: " + computeConvectAngle(coord1, coord2, coord3) + "; XTE: " + crossTrackError(coord1, coord2, coord3));
-
-//              final double weight = isRequiredNode(w, prevNode) || !closed && i == len - 1 ? Double.MAX_VALUE :
-//                      computeConvectAngle(coord1, coord2, coord3) / angleThreshold +
-//                      computeArea(coord1, coord2, coord3) / areaThreshold +
-//                      Math.abs(crossTrackError(coord1, coord2, coord3)) / distanceThreshold;
-
-                if (isRequiredNode(w, prevNode) ||
-                                !closed && i == len - 1 || // don't remove last node of the not closed way
-                                computeConvectAngle(coord1, coord2, coord3) > angleThreshold ||
-                                computeArea(coord1, coord2, coord3) > areaThreshold ||
-                        Math.abs(crossTrackError(coord1, coord2, coord3)) > distanceThreshold) {
-                    newNodes2.add(prevNode);
-//                      System.out.println(" ... KEEP " + prevNode.getUniqueId());
-                } else {
-//                      System.out.println(" ... REMOVE " + prevNode.getUniqueId());
-                    coord2 = coord1; // at the end of the iteration preserve coord1
-                    newNodes.remove(prevNode);
-                    j--;
-                }
-            } else if (!closed && prevNode != null) {
-                newNodes2.add(prevNode);
-            }
-
-            coord1 = coord2;
-            coord2 = coord3;
-            prevNode = n;
-        }
+        // remove nodes within threshold
+
+        while (true) {
+                Node prevNode = null;
+                LatLon coord1 = null;
+                LatLon coord2 = null;
+
+                double minWeight = Double.MAX_VALUE;
+                Node bestMatch = null;
+
+                for (int i = 0, len = nodes.size() + (closed ? 2 : 1); i < len; i++) {
+                    final Node n = nodes.get(i % nodes.size());
+                    final LatLon coord3 = n.getCoor();
+
+                    if (coord1 != null) {
+                        final double angleWeight = computeConvectAngle(coord1, coord2, coord3) / angleThreshold;
+                        final double areaWeight = computeArea(coord1, coord2, coord3) / areaThreshold;
+                        final double distanceWeight = Math.abs(crossTrackError(coord1, coord2, coord3)) / distanceThreshold;
+
+                        final double weight = isRequiredNode(w, prevNode) ||
+                                !closed && i == len - 1 || // don't remove last node of the not closed way
+                                angleWeight > 1.0 || areaWeight > 1.0 || distanceWeight > 1.0 ? Double.MAX_VALUE :
+                                angleWeight * angleFactor + areaWeight * areaFactor + distanceWeight * distanceFactor;
+
+                        if (weight < minWeight) {
+                                minWeight = weight;
+                                bestMatch = prevNode;
+                        }
+                    }
+
+                    coord1 = coord2;
+                    coord2 = coord3;
+                    prevNode = n;
+                }
+
+                if (bestMatch == null) {
+                        break;
+                }
+
+                nodes.remove(bestMatch);
+        }
+
+
+        // average nearby nodes
+
+        final Map<Node, LatLon> coordMap = new HashMap<Node, LatLon>();
+        for (final Node n : nodes) {
+                coordMap.put(n, n.getCoor());
+        }
+
+        final Map<Node, MoveCommand> moveCommandList = new HashMap<Node, MoveCommand>();
+
+        while (true) {
+                double minDist = Double.MAX_VALUE;
+                Node node1 = null;
+                Node node2 = null;
+
+                for (int i = 0, len = nodes.size() + (closed ? 2 : 1); i < len; i++) {
+                    final Node n1 = nodes.get(i % nodes.size());
+                    final Node n2 = nodes.get((i + 1) % nodes.size());
+
+                    if (isRequiredNode(w, n1) || isRequiredNode(w, n2)) {
+                        continue;
+                    }
+
+                    final double dist = coordMap.get(n1).greatCircleDistance(coordMap.get(n2));
+                    if (dist < minDist && dist < mergeThreshold) {
+                        minDist = dist;
+                        node1 = n1;
+                        node2 = n2;
+                    }
+                }
+
+                if (node1 == null || node2 == null) {
+                        break;
+                }
+
+
+                final LatLon coord = coordMap.get(node1).getCenter(coordMap.get(node2));
+                coordMap.put(node1, coord);
+                        moveCommandList.put(node1, new MoveCommand(node1, coord));
+
+                        nodes.remove(node2);
+                coordMap.remove(node2);
+                moveCommandList.remove(node2);
+        }
+
 
         if (closed) {
-            newNodes2.add(newNodes2.get(0)); // set end node ( = start node)
-        }
-
-        final HashSet<Node> delNodes = new HashSet<Node>();
-        delNodes.addAll(nodes);
-        delNodes.removeAll(newNodes2);
+            nodes.add(nodes.get(0)); // set end node ( = start node)
+        }
+
+        final HashSet<Node> delNodes = new HashSet<Node>(w.getNodes());
+        delNodes.removeAll(nodes);
 
         if (delNodes.isEmpty()) {
@@ -273 +291 @@
         final Collection<Command> cmds = new LinkedList<Command>();
         final Way newWay = new Way(w);
-        newWay.setNodes(newNodes2);
-
-        cmds.addAll(moveCommandList);
+        newWay.setNodes(nodes);
+
+        cmds.addAll(moveCommandList.values());
         cmds.add(new ChangeCommand(w, newWay));
         cmds.add(new DeleteCommand(delNodes));
@@ -295 +313 @@
         final double p = (a + b + c) / 2.0;
 
-        return Math.sqrt(p * (p - a) * (p - b) * (p - c));
+        final double q = p * (p - a) * (p - b) * (p - c); // I found this negative in one case (:-o) when nodes were in line on a small area
+                return q < 0.0 ? 0.0 : Math.sqrt(q);
     }