delaunay-fast - npm Package Compare versions

Comparing version 1.0.0 to 1.0.1

delaunay.js

@@ -6,3 +6,5 @@ var Delaunay;
 
-  function appendSupertriangleVertices(vertices) {
+  var EPSILON = 1.0 / 1048576.0;
+
+  function supertriangle(vertices) {
     var xmin = Number.POSITIVE_INFINITY,
@@ -27,59 +29,73 @@ ymin = Number.POSITIVE_INFINITY,
 
-    vertices.push(
+    return [
       [xmid - 20 * dmax, ymid -      dmax],
       [xmid            , ymid + 20 * dmax],
       [xmid + 20 * dmax, ymid -      dmax]
-    );
+    ];
   }
 
-  function triangle(vertices, i, j, k) {
-    var a = vertices[i],
-        b = vertices[j],
-        c = vertices[k],
-        A = b[0] - a[0],
-        B = b[1] - a[1],
-        C = c[0] - a[0],
-        D = c[1] - a[1],
-        E = A * (a[0] + b[0]) + B * (a[1] + b[1]),
-        F = C * (a[0] + c[0]) + D * (a[1] + c[1]),
-        G = 2 * (A * (c[1] - b[1]) - B * (c[0] - b[0])),
-        minx, miny, dx, dy, x, y;
+  function circumcircle(vertices, i, j, k) {
+    var x1 = vertices[i][0],
+        y1 = vertices[i][1],
+        x2 = vertices[j][0],
+        y2 = vertices[j][1],
+        x3 = vertices[k][0],
+        y3 = vertices[k][1],
+        fabsy1y2 = Math.abs(y1 - y2),
+        fabsy2y3 = Math.abs(y2 - y3),
+        xc, yc, m1, m2, mx1, mx2, my1, my2, dx, dy;
 
-    /* If the points of the triangle are collinear, then just find the
-     * extremes and use the midpoint as the center of the circumcircle. */
-    if(Math.abs(G) < 0.000001) {
-      minx = Math.min(a[0], b[0], c[0])
-      miny = Math.min(a[1], b[1], c[1])
-      dx   = (Math.max(a[0], b[0], c[0]) - minx) * 0.5;
-      dy   = (Math.max(a[1], b[1], c[1]) - miny) * 0.5;
-      x    = minx + dx;
-      y    = miny + dy;
+    /* Check for coincident points */
+    if(fabsy1y2 < EPSILON && fabsy2y3 < EPSILON)
+      throw new Error("Eek! Coincident points!");
+
+    if(fabsy1y2 < EPSILON) {
+      m2  = -((x3 - x2) / (y3 - y2));
+      mx2 = (x2 + x3) / 2.0;
+      my2 = (y2 + y3) / 2.0;
+      xc  = (x2 + x1) / 2.0;
+      yc  = m2 * (xc - mx2) + my2;
     }
 
+    else if(fabsy2y3 < EPSILON) {
+      m1  = -((x2 - x1) / (y2 - y1));
+      mx1 = (x1 + x2) / 2.0;
+      my1 = (y1 + y2) / 2.0;
+      xc  = (x3 + x2) / 2.0;
+      yc  = m1 * (xc - mx1) + my1;
+    }
+
     else {
-      x  = (D*E - B*F) / G;
-      y  = (A*F - C*E) / G;
-      dx = x - a[0]
-      dy = y - a[1]
+      m1  = -((x2 - x1) / (y2 - y1));
+      m2  = -((x3 - x2) / (y3 - y2));
+      mx1 = (x1 + x2) / 2.0;
+      mx2 = (x2 + x3) / 2.0;
+      my1 = (y1 + y2) / 2.0;
+      my2 = (y2 + y3) / 2.0;
+      xc  = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
+      yc  = (fabsy1y2 > fabsy2y3) ?
+        m1 * (xc - mx1) + my1 :
+        m2 * (xc - mx2) + my2;
     }
 
-    return {i: i, j: j, k: k, x: x, y: y, r: dx * dx + dy * dy};
+    dx = x2 - xc;
+    dy = y2 - yc;
+    return {i: i, j: j, k: k, x: xc, y: yc, r: dx * dx + dy * dy};
   }
 
   function dedup(edges) {
-    var j = edges.length,
-        a, b, i, m, n
+    var i, j, a, b, m, n;
 
-    outer: while(j) {
-      b = edges[--j]
-      a = edges[--j]
-      i = j
-      while(i) {
-        n = edges[--i]
-        m = edges[--i]
+    for(j = edges.length; j; ) {
+      b = edges[--j];
+      a = edges[--j];
+
+      for(i = j; i; ) {
+        n = edges[--i];
+        m = edges[--i];
+
         if((a === m && b === n) || (a === n && b === m)) {
-          edges.splice(j, 2)
-          edges.splice(i, 2)
-          j -= 2
-          continue outer
+          edges.splice(j, 2);
+          edges.splice(i, 2);
+          break;
         }
@@ -93,3 +109,3 @@ }
       var n = vertices.length,
-          i, j, indices, open, closed, edges, dx, dy, a, b, c;
+          i, j, indices, st, open, closed, edges, dx, dy, a, b, c;
 
@@ -109,4 +125,4 @@ /* Bail if there aren't enough vertices to form any triangles. */
 
-      /* Make an array of indices into the vertex array, sorted by the vertices'
-       * x-position. */
+      /* Make an array of indices into the vertex array, sorted by the
+       * vertices' x-position. */
       indices = new Array(n);
@@ -117,3 +133,5 @@
 
-      indices.sort(function(i, j) { return vertices[j][0] - vertices[i][0]; });
+      indices.sort(function(i, j) {
+        return vertices[j][0] - vertices[i][0];
+      });
 
@@ -123,8 +141,9 @@ /* Next, find the vertices of the supertriangle (which contains all other
        * array. */
-      appendSupertriangleVertices(vertices);
+      st = supertriangle(vertices);
+      vertices.push(st[0], st[1], st[2]);
       
-      /* Initialize the open list (containing the supertriangle and nothing else)
-       * and the closed list (which is empty since we havn't processed any
-       * triangles yet). */
-      open   = [triangle(vertices, n + 0, n + 1, n + 2)];
+      /* Initialize the open list (containing the supertriangle and nothing
+       * else) and the closed list (which is empty since we havn't processed
+       * any triangles yet). */
+      open   = [circumcircle(vertices, n + 0, n + 1, n + 2)];
       closed = [];
@@ -134,5 +153,4 @@ edges  = [];
       /* Incrementally add each vertex to the mesh. */
-      for(i = indices.length; i--; ) {
+      for(i = indices.length; i--; edges.length = 0) {
         c = indices[i];
-        edges.length = 0;
 
@@ -155,3 +173,3 @@ /* For each open triangle, check to see if the current point is
           dy = vertices[c][1] - open[j].y;
-          if(dx * dx + dy * dy > open[j].r)
+          if(dx * dx + dy * dy - open[j].r > EPSILON)
             continue;
@@ -175,3 +193,3 @@
           a = edges[--j];
-          open.push(triangle(vertices, a, b, c));
+          open.push(circumcircle(vertices, a, b, c));
         }
@@ -181,4 +199,4 @@ }
       /* Copy any remaining open triangles to the closed list, and then
-       * remove any triangles that share a vertex with the supertriangle, building
-       * a list of triplets that represent triangles. */
+       * remove any triangles that share a vertex with the supertriangle,
+       * building a list of triplets that represent triangles. */
       for(i = open.length; i--; )
@@ -185,0 +203,0 @@ closed.push(open[i]);

package.json

 {
   "name": "delaunay-fast",
-  "version": "1.0.0",
+  "version": "1.0.1",
   "description": "Fast Delaunay Triangulation in JavaScript",
@@ -5,0 +5,0 @@ "main": "delaunay.js",

No alert changes

Improved metrics

Total package byte prevSize

9867

increased by3.99%

Lines of code

194

increased by7.18%

No dependency changes