curve-matcher - npm Package Compare versions

Comparing version 1.1.0 to 1.1.1

dist/index.es5.js

@@ -18,4 +18,5 @@ /** @hidden */
 }); };
-var magnitude = function (vector) {
-    return Math.sqrt(Math.pow(vector.x, 2) + Math.pow(vector.y, 2));
+var magnitude = function (_a) {
+    var x = _a.x, y = _a.y;
+    return Math.sqrt(x * x + y * y);
 };
@@ -128,34 +129,33 @@ /**
  * based on http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf
- * @param curve1
- * @param curve2
+ * modified to be iterative and have better memory usage
  */
 var frechetDist = function (curve1, curve2) {
-    var results = [];
-    for (var i = 0; i < curve1.length; i++) {
-        results.push([]);
-        for (var j = 0; j < curve2.length; j++) {
-            results[i].push(-1);
-        }
-    }
-    var recursiveCalc = function (i, j) {
-        if (results[i][j] > -1)
-            return results[i][j];
+    var longCurve = curve1.length >= curve2.length ? curve1 : curve2;
+    var shortCurve = curve1.length >= curve2.length ? curve2 : curve1;
+    var calcVal = function (i, j, prevResultsCol, curResultsCol) {
         if (i === 0 && j === 0) {
-            results[i][j] = pointDistance(curve1[0], curve2[0]);
+            return pointDistance(longCurve[0], shortCurve[0]);
         }
-        else if (i > 0 && j === 0) {
-            results[i][j] = Math.max(recursiveCalc(i - 1, 0), pointDistance(curve1[i], curve2[0]));
+        if (i > 0 && j === 0) {
+            return Math.max(prevResultsCol[0], pointDistance(longCurve[i], shortCurve[0]));
         }
-        else if (i === 0 && j > 0) {
-            results[i][j] = Math.max(recursiveCalc(0, j - 1), pointDistance(curve1[0], curve2[j]));
+        var lastResult = curResultsCol[curResultsCol.length - 1];
+        if (i === 0 && j > 0) {
+            return Math.max(lastResult, pointDistance(longCurve[0], shortCurve[j]));
         }
-        else if (i > 0 && j > 0) {
-            results[i][j] = Math.max(Math.min(recursiveCalc(i - 1, j), recursiveCalc(i - 1, j - 1), recursiveCalc(i, j - 1)), pointDistance(curve1[i], curve2[j]));
+        return Math.max(Math.min(prevResultsCol[j], prevResultsCol[j - 1], lastResult), pointDistance(longCurve[i], shortCurve[j]));
+    };
+    var prevResultsCol = [];
+    for (var i = 0; i < longCurve.length; i++) {
+        var curResultsCol = [];
+        for (var j = 0; j < shortCurve.length; j++) {
+            // we only need the results from i - 1 and j - 1 to continue the calculation
+            // so we only need to hold onto the last column of calculated results
+            // prevResultsCol is results[i-1][:] in the original algorithm
+            // curResultsCol is results[i][:j-1] in the original algorithm
+            curResultsCol.push(calcVal(i, j, prevResultsCol, curResultsCol));
         }
-        else {
-            results[i][j] = Infinity;
-        }
-        return results[i][j];
-    };
-    return recursiveCalc(curve1.length - 1, curve2.length - 1);
+        prevResultsCol = curResultsCol;
+    }
+    return prevResultsCol[shortCurve.length - 1];
 };
@@ -162,0 +162,0 @@

dist/index.umd.js

@@ -24,4 +24,5 @@ (function (global, factory) {
   }); };
-  var magnitude = function (vector) {
-      return Math.sqrt(Math.pow(vector.x, 2) + Math.pow(vector.y, 2));
+  var magnitude = function (_a) {
+      var x = _a.x, y = _a.y;
+      return Math.sqrt(x * x + y * y);
   };
@@ -134,34 +135,33 @@ /**
    * based on http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf
-   * @param curve1
-   * @param curve2
+   * modified to be iterative and have better memory usage
    */
   var frechetDist = function (curve1, curve2) {
-      var results = [];
-      for (var i = 0; i < curve1.length; i++) {
-          results.push([]);
-          for (var j = 0; j < curve2.length; j++) {
-              results[i].push(-1);
-          }
-      }
-      var recursiveCalc = function (i, j) {
-          if (results[i][j] > -1)
-              return results[i][j];
+      var longCurve = curve1.length >= curve2.length ? curve1 : curve2;
+      var shortCurve = curve1.length >= curve2.length ? curve2 : curve1;
+      var calcVal = function (i, j, prevResultsCol, curResultsCol) {
           if (i === 0 && j === 0) {
-              results[i][j] = pointDistance(curve1[0], curve2[0]);
+              return pointDistance(longCurve[0], shortCurve[0]);
           }
-          else if (i > 0 && j === 0) {
-              results[i][j] = Math.max(recursiveCalc(i - 1, 0), pointDistance(curve1[i], curve2[0]));
+          if (i > 0 && j === 0) {
+              return Math.max(prevResultsCol[0], pointDistance(longCurve[i], shortCurve[0]));
           }
-          else if (i === 0 && j > 0) {
-              results[i][j] = Math.max(recursiveCalc(0, j - 1), pointDistance(curve1[0], curve2[j]));
+          var lastResult = curResultsCol[curResultsCol.length - 1];
+          if (i === 0 && j > 0) {
+              return Math.max(lastResult, pointDistance(longCurve[0], shortCurve[j]));
           }
-          else if (i > 0 && j > 0) {
-              results[i][j] = Math.max(Math.min(recursiveCalc(i - 1, j), recursiveCalc(i - 1, j - 1), recursiveCalc(i, j - 1)), pointDistance(curve1[i], curve2[j]));
+          return Math.max(Math.min(prevResultsCol[j], prevResultsCol[j - 1], lastResult), pointDistance(longCurve[i], shortCurve[j]));
+      };
+      var prevResultsCol = [];
+      for (var i = 0; i < longCurve.length; i++) {
+          var curResultsCol = [];
+          for (var j = 0; j < shortCurve.length; j++) {
+              // we only need the results from i - 1 and j - 1 to continue the calculation
+              // so we only need to hold onto the last column of calculated results
+              // prevResultsCol is results[i-1][:] in the original algorithm
+              // curResultsCol is results[i][:j-1] in the original algorithm
+              curResultsCol.push(calcVal(i, j, prevResultsCol, curResultsCol));
           }
-          else {
-              results[i][j] = Infinity;
-          }
-          return results[i][j];
-      };
-      return recursiveCalc(curve1.length - 1, curve2.length - 1);
+          prevResultsCol = curResultsCol;
+      }
+      return prevResultsCol[shortCurve.length - 1];
   };
@@ -168,0 +168,0 @@

dist/lib/frechetDistance.js

@@ -7,36 +7,35 @@ "use strict";
  * based on http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf
- * @param curve1
- * @param curve2
+ * modified to be iterative and have better memory usage
  */
 var frechetDist = function (curve1, curve2) {
-    var results = [];
-    for (var i = 0; i < curve1.length; i++) {
-        results.push([]);
-        for (var j = 0; j < curve2.length; j++) {
-            results[i].push(-1);
-        }
-    }
-    var recursiveCalc = function (i, j) {
-        if (results[i][j] > -1)
-            return results[i][j];
+    var longCurve = curve1.length >= curve2.length ? curve1 : curve2;
+    var shortCurve = curve1.length >= curve2.length ? curve2 : curve1;
+    var calcVal = function (i, j, prevResultsCol, curResultsCol) {
         if (i === 0 && j === 0) {
-            results[i][j] = geometry_1.pointDistance(curve1[0], curve2[0]);
+            return geometry_1.pointDistance(longCurve[0], shortCurve[0]);
         }
-        else if (i > 0 && j === 0) {
-            results[i][j] = Math.max(recursiveCalc(i - 1, 0), geometry_1.pointDistance(curve1[i], curve2[0]));
+        if (i > 0 && j === 0) {
+            return Math.max(prevResultsCol[0], geometry_1.pointDistance(longCurve[i], shortCurve[0]));
         }
-        else if (i === 0 && j > 0) {
-            results[i][j] = Math.max(recursiveCalc(0, j - 1), geometry_1.pointDistance(curve1[0], curve2[j]));
+        var lastResult = curResultsCol[curResultsCol.length - 1];
+        if (i === 0 && j > 0) {
+            return Math.max(lastResult, geometry_1.pointDistance(longCurve[0], shortCurve[j]));
         }
-        else if (i > 0 && j > 0) {
-            results[i][j] = Math.max(Math.min(recursiveCalc(i - 1, j), recursiveCalc(i - 1, j - 1), recursiveCalc(i, j - 1)), geometry_1.pointDistance(curve1[i], curve2[j]));
+        return Math.max(Math.min(prevResultsCol[j], prevResultsCol[j - 1], lastResult), geometry_1.pointDistance(longCurve[i], shortCurve[j]));
+    };
+    var prevResultsCol = [];
+    for (var i = 0; i < longCurve.length; i++) {
+        var curResultsCol = [];
+        for (var j = 0; j < shortCurve.length; j++) {
+            // we only need the results from i - 1 and j - 1 to continue the calculation
+            // so we only need to hold onto the last column of calculated results
+            // prevResultsCol is results[i-1][:] in the original algorithm
+            // curResultsCol is results[i][:j-1] in the original algorithm
+            curResultsCol.push(calcVal(i, j, prevResultsCol, curResultsCol));
         }
-        else {
-            results[i][j] = Infinity;
-        }
-        return results[i][j];
-    };
-    return recursiveCalc(curve1.length - 1, curve2.length - 1);
+        prevResultsCol = curResultsCol;
+    }
+    return prevResultsCol[shortCurve.length - 1];
 };
 exports.default = frechetDist;
 //# sourceMappingURL=frechetDistance.js.map

dist/lib/geometry.js

@@ -9,4 +9,5 @@ "use strict";
 }); };
-var magnitude = function (vector) {
-    return Math.sqrt(Math.pow(vector.x, 2) + Math.pow(vector.y, 2));
+var magnitude = function (_a) {
+    var x = _a.x, y = _a.y;
+    return Math.sqrt(x * x + y * y);
 };
@@ -13,0 +14,0 @@ /**

dist/types/frechetDistance.d.ts

 /**
  * Discrete Frechet distance between 2 curves
  * based on http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf
- * @param curve1
- * @param curve2
+ * modified to be iterative and have better memory usage
  */
 declare const frechetDist: (curve1: import("./geometry").Point[], curve2: import("./geometry").Point[]) => number;
 export default frechetDist;

package.json

 {
   "name": "curve-matcher",
-  "version": "1.1.0",
+  "version": "1.1.1",
   "description": "Curve matching using Fréchet distance and Procrustes analysis in JS",
@@ -5,0 +5,0 @@ "keywords": [

No alert changes

Improved metrics

Total package byte prevSize

106912

increased by0.95%

Worsened metrics

Lines of code

994

decreased by-0.1%

No dependency changes