delaunay - npm Package Compare versions

Comparing version 0.3.2 to 0.4.0

lib/barycentric.js

@@ -43,3 +43,3 @@ var Barycentric;
       for(i = coordinates.length; i--; ) {
-        if(coordinates[i] < 0)
+        if(coordinates[i] < 0.0)
           return null;
@@ -50,3 +50,3 @@
 
-      return sum <= 1 ? coordinates : null;
+      return sum <= 1.0 ? coordinates : null;
     }
@@ -53,0 +53,0 @@ };

lib/delaunay.js

@@ -30,5 +30,8 @@ /* This is a JavaScript implementation of Delaunay triangulation. Ideally, it
   Simplex.prototype = {
+    passed: function(vertex, n) {
+      var d = vertex[0] - this.center[0];
+      return d > 0.0 && d * d > this.radius;
+    },
     contains: function(vertex, n) {
-      var r = Delaunay.distanceSquared(this.center, vertex, n);
-      return r <= this.radius;
+      return Delaunay.distanceSquared(this.center, vertex, n) <= this.radius;
     },
@@ -258,4 +261,2 @@ /* FIXME: This can be done more efficiently, since the vertices are already
     },
-    /* FIXME: By sorting the objects on an axis (preferably the longest axis),
-     * this function can be made O(n log n). */
     triangulate: function(objects, key) {
@@ -273,3 +274,25 @@ var v = objects.length,
 
-      /* Add the vertices of the bounding simplex to the object list. */
+      if(n < 2 || n > 3)
+        throw new Error("The Delaunay module currently only supports 2D or 3D data.");
+
+      /* Sort the objects on an axis so we can get O(n log n) behavior. Sadly,
+       * we also need to keep track of their original position in the array, so
+       * we wrap the objects to track that and then unwrap them again. */
+      for(i = objects.length; i--; )
+        objects[i] = {index: i, position: objects[i]};
+
+      /* FIXME: It'd be better to sort on the longest axis, rather than on an
+       * arbitrary axis, since it'll lower the constant factor. */
+      objects.sort(function(a, b) { return b.position[0] - a.position[0]; });
+
+      var indices = new Array(objects.length);
+
+      for(i = objects.length; i--; ) {
+        indices[i] = objects[i].index;
+        objects[i] = objects[i].position;
+      }
+
+      /* Add the vertices of the bounding simplex to the object list. It's okay
+       * that these vertices aren't sorted like the others, since they're never
+       * going to be iterated over. */
       Array.prototype.push.apply(
@@ -286,12 +309,24 @@ objects,
 
-      var simplices = [new Simplex(list, objects, n)],
-          edges = [];
+      var open   = [new Simplex(list, objects, n)],
+          closed = [],
+          edges  = [];
 
       for(i = v; i--; edges.length = 0) {
-        for(j = simplices.length; j--; )
-          if(simplices[j].contains(objects[i], n)) {
-            simplices[j].addEdges(n, edges);
-            simplices.splice(j, 1);
+        for(j = open.length; j--; ) {
+          /* If this vertex is past the simplex, then we're never going to
+           * intersect it again, so remove it from the open list and move it to
+           * the closed list. */
+          if(open[j].passed(objects[i], n)) {
+            closed.push(open[j]);
+            open.splice(j, 1);
           }
 
+          /* Otherwise, if the simplex contains the vertex, it needs to get
+           * split apart. */
+          else if(open[j].contains(objects[i], n)) {
+            open[j].addEdges(n, edges);
+            open.splice(j, 1);
+          }
+        }
+
         Delaunay.removeDuplicateEdges(edges);
@@ -301,17 +336,22 @@
           edges[j].unshift(i);
-          simplices.push(new Simplex(edges[j], objects, n));
+          open.push(new Simplex(edges[j], objects, n));
         }
       }
 
+      /* Move all open simplices into the closed list. */
+      Array.prototype.push.apply(closed, open);
+      open.length = 0;
+
       /* Build and return the final list of simplex vertex indices. */
       list.length = 0;
 
-      simplex: for(i = simplices.length; i--; ) {
+      simplex: for(i = closed.length; i--; ) {
         /* If any of the vertices are from the bounding simplex, skip adding
          * this simplex to the output list. */
-        for(j = simplices[i].vertices.length; j--; )
-          if(simplices[i].vertices[j] >= v)
+        for(j = closed[i].vertices.length; j--; )
+          if(closed[i].vertices[j] >= v)
             continue simplex;
 
-        Array.prototype.push.apply(list, simplices[i].vertices);
+        for(j = 0; j < closed[i].vertices.length; j++)
+          list.push(indices[closed[i].vertices[j]]);
       }
@@ -318,0 +358,0 @@

package.json

 {
   "name": "delaunay",
-  "version": "0.3.2",
+  "version": "0.4.0",
   "description": "Delaunay triangulation in arbitrary dimensions",
@@ -5,0 +5,0 @@ "keywords": [

spec/delaunay.spec.js

@@ -241,12 +241,12 @@ var Delaunay = require("../lib/delaunay");
         )).toEqual([
-          0, 2, 3,
-          0, 1, 2,
-          1, 2, 5,
-          1, 4, 5,
-          2, 3, 7,
-          2, 5, 7,
-          3, 7, 8,
-          4, 5, 6,
-          5, 6, 7,
-          6, 7, 8
+          8, 3, 7,
+          8, 7, 6,
+          3, 0, 2,
+          3, 7, 2,
+          7, 2, 5,
+          0, 2, 1,
+          7, 5, 6,
+          2, 5, 1,
+          5, 6, 4,
+          5, 1, 4
         ]);
@@ -253,0 +253,0 @@ });

No alert changes

Improved metrics

Total package byte prevSize

36100

5.14%

Lines of code

815

4.22%

No dependency changes