Changeset 14970 in josm for trunk/src/org/openstreetmap

Timestamp:

2019-04-07T19:03:21+02:00 (6 years ago)

Author:

GerdP

Message:

see #16102: Drastically improve performance for SimplifyWayAction when used with very complex ways.
For a kml file produced by brouter with ~50000 points the import took > 50 seconds, now it is done in 1.5 seconds.

File:

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

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

@@ -134 +134 @@
      * @param way the way to be simplified
      * @param node the node to check
+     * @param multipleUseNodes set of nodes which is used more than once in the way
      * @return true if <code>node</code> is a required node which can't be removed
      * in order to simplify the way.
      */
-    protected static boolean isRequiredNode(Way way, Node node) {
+    protected static boolean isRequiredNode(Way way, Node node, Set<Node> multipleUseNodes) {
         boolean isRequired = node.isTagged();
-        if (!isRequired) {
+        if (!isRequired && multipleUseNodes.contains(node)) {
             int frequency = Collections.frequency(way.getNodes(), node);
             if ((way.getNode(0) == node) && (way.getNode(way.getNodesCount()-1) == node)) {
@@ -164 +165 @@
     public final SequenceCommand simplifyWay(Way w) {
         return simplifyWay(w, Config.getPref().getDouble("simplify-way.max-error", 3.0));
+    }
+
+    /**
+     * Calculate a set of nodes which occurs more than once in the way
+     * @param w the way
+     * @return a set of nodes which occurs more than once in the way
+     */
+    private static Set<Node> getMultiUseNodes(Way w) {
+        Set<Node> multipleUseNodes = new HashSet<>();
+        Set<Node> allNodes = new HashSet<>();
+        for (Node n : w.getNodes()) {
+            if (!allNodes.add(n))
+                multipleUseNodes.add(n);
+        }
+        return multipleUseNodes;
     }
 
@@ -177 +193 @@
         int lower = 0;
         int i = 0;
+
+        Set<Node> multipleUseNodes = getMultiUseNodes(w);
         List<Node> newNodes = new ArrayList<>(w.getNodesCount());
         while (i < w.getNodesCount()) {
-            if (isRequiredNode(w, w.getNode(i))) {
+            if (isRequiredNode(w, w.getNode(i), multipleUseNodes)) {
                 // copy a required node to the list of new nodes. Simplify not possible
                 newNodes.add(w.getNode(i));
@@ -188 +206 @@
             i++;
             // find the longest sequence of not required nodes ...
-            while (i < w.getNodesCount() && !isRequiredNode(w, w.getNode(i))) {
+            while (i < w.getNodesCount() && !isRequiredNode(w, w.getNode(i), multipleUseNodes)) {
                 i++;
             }
@@ -198 +216 @@
 
         // Closed way, check if the first node could also be simplified ...
-        if (newNodes.size() > 3 && newNodes.get(0) == newNodes.get(newNodes.size() - 1) && !isRequiredNode(w, newNodes.get(0))) {
+        if (newNodes.size() > 3 && newNodes.get(0) == newNodes.get(newNodes.size() - 1) && !isRequiredNode(w, newNodes.get(0), multipleUseNodes)) {
             final List<Node> l1 = Arrays.asList(newNodes.get(newNodes.size() - 2), newNodes.get(0), newNodes.get(1));
             final List<Node> l2 = new ArrayList<>(3);