delaunator - npm Package Compare versions

Comparing version 3.0.2 to 4.0.0

delaunator.js

 (function (global, factory) {
     typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :
     typeof define === 'function' && define.amd ? define(factory) :
-    (global.Delaunator = factory());
-}(this, (function () { 'use strict';
+    (global = global || self, global.Delaunator = factory());
+}(this, function () { 'use strict';
 
     var EPSILON = Math.pow(2, -52);
+    var EDGE_STACK = new Uint32Array(512);
 
     var Delaunator = function Delaunator(coords) {
-        var this$1 = this;
-
         var n = coords.length >> 1;
@@ -18,15 +17,46 @@ if (n > 0 && typeof coords[0] !== 'number') { throw new Error('Expected coords to contain numbers.'); }
         // arrays that will store the triangulation graph
-        var maxTriangles = 2 * n - 5;
-        var triangles = this.triangles = new Uint32Array(maxTriangles * 3);
-        var halfedges = this.halfedges = new Int32Array(maxTriangles * 3);
+        var maxTriangles = Math.max(2 * n - 5, 0);
+        this._triangles = new Uint32Array(maxTriangles * 3);
+        this._halfedges = new Int32Array(maxTriangles * 3);
 
         // temporary arrays for tracking the edges of the advancing convex hull
         this._hashSize = Math.ceil(Math.sqrt(n));
-        var hullPrev = this.hullPrev = new Uint32Array(n); // edge to prev edge
-        var hullNext = this.hullNext = new Uint32Array(n); // edge to next edge
-        var hullTri = this.hullTri = new Uint32Array(n); // edge to adjacent triangle
-        var hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash
+        this._hullPrev = new Uint32Array(n); // edge to prev edge
+        this._hullNext = new Uint32Array(n); // edge to next edge
+        this._hullTri = new Uint32Array(n); // edge to adjacent triangle
+        this._hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash
 
+        // temporary arrays for sorting points
+        this._ids = new Uint32Array(n);
+        this._dists = new Float64Array(n);
+
+        this.update();
+    };
+
+    Delaunator.from = function from (points, getX, getY) {
+            if ( getX === void 0 ) getX = defaultGetX;
+            if ( getY === void 0 ) getY = defaultGetY;
+
+        var n = points.length;
+        var coords = new Float64Array(n * 2);
+
+        for (var i = 0; i < n; i++) {
+            var p = points[i];
+            coords[2 * i] = getX(p);
+            coords[2 * i + 1] = getY(p);
+        }
+
+        return new Delaunator(coords);
+    };
+
+    Delaunator.prototype.update = function update () {
+        var ref =  this;
+            var coords = ref.coords;
+            var hullPrev = ref._hullPrev;
+            var hullNext = ref._hullNext;
+            var hullTri = ref._hullTri;
+            var hullHash = ref._hullHash;
+        var n = coords.length >> 1;
+
         // populate an array of point indices; calculate input data bbox
-        var ids = new Uint32Array(n);
         var minX = Infinity;
@@ -44,3 +74,3 @@ var minY = Infinity;
             if (y > maxY) { maxY = y; }
-            ids[i] = i;
+            this._ids[i] = i;
         }
@@ -93,3 +123,21 @@ var cx = (minX + maxX) / 2;
         if (minRadius === Infinity) {
-            throw new Error('No Delaunay triangulation exists for this input.');
+            // order collinear points by dx (or dy if all x are identical)
+            // and return the list as a hull
+            for (var i$4 = 0; i$4 < n; i$4++) {
+                this._dists[i$4] = (coords[2 * i$4] - coords[0]) || (coords[2 * i$4 + 1] - coords[1]);
+            }
+            quicksort(this._ids, this._dists, 0, n - 1);
+            var hull = new Uint32Array(n);
+            var j = 0;
+            for (var i$5 = 0, d0 = -Infinity; i$5 < n; i$5++) {
+                var id = this._ids[i$5];
+                if (this._dists[id] > d0) {
+                    hull[j++] = id;
+                    d0 = this._dists[id];
+                }
+            }
+            this.hull = hull.subarray(0, j);
+            this.triangles = new Uint32Array(0);
+            this.halfedges = new Uint32Array(0);
+            return;
         }
@@ -99,3 +147,3 @@
         if (orient(i0x, i0y, i1x, i1y, i2x, i2y)) {
-            var i$4 = i1;
+            var i$6 = i1;
             var x$1 = i1x;
@@ -106,3 +154,3 @@ var y$1 = i1y;
             i1y = i2y;
-            i2 = i$4;
+            i2 = i$6;
             i2x = x$1;
@@ -116,12 +164,11 @@ i2y = y$1;
 
-        var dists = new Float64Array(n);
-        for (var i$5 = 0; i$5 < n; i$5++) {
-            dists[i$5] = dist(coords[2 * i$5], coords[2 * i$5 + 1], center.x, center.y);
+        for (var i$7 = 0; i$7 < n; i$7++) {
+            this._dists[i$7] = dist(coords[2 * i$7], coords[2 * i$7 + 1], center.x, center.y);
         }
 
         // sort the points by distance from the seed triangle circumcenter
-        quicksort(ids, dists, 0, n - 1);
+        quicksort(this._ids, this._dists, 0, n - 1);
 
         // set up the seed triangle as the starting hull
-        this.hullStart = i0;
+        this._hullStart = i0;
         var hullSize = 3;
@@ -137,2 +184,3 @@
 
+        hullHash.fill(-1);
         hullHash[this._hashKey(i0x, i0y)] = i0;
@@ -145,6 +193,6 @@ hullHash[this._hashKey(i1x, i1y)] = i1;
 
-        for (var k = 0, xp = (void 0), yp = (void 0); k < ids.length; k++) {
-            var i$6 = ids[k];
-            var x$2 = coords[2 * i$6];
-            var y$2 = coords[2 * i$6 + 1];
+        for (var k = 0, xp = (void 0), yp = (void 0); k < this._ids.length; k++) {
+            var i$8 = this._ids[k];
+            var x$2 = coords[2 * i$8];
+            var y$2 = coords[2 * i$8 + 1];
 
@@ -157,8 +205,8 @@ // skip near-duplicate points
             // skip seed triangle points
-            if (i$6 === i0 || i$6 === i1 || i$6 === i2) { continue; }
+            if (i$8 === i0 || i$8 === i1 || i$8 === i2) { continue; }
 
             // find a visible edge on the convex hull using edge hash
             var start = 0;
-            for (var j = 0, key = this._hashKey(x$2, y$2); j < this._hashSize; j++) {
-                start = hullHash[(key + j) % this$1._hashSize];
+            for (var j$1 = 0, key = this._hashKey(x$2, y$2); j$1 < this._hashSize; j$1++) {
+                start = hullHash[(key + j$1) % this._hashSize];
                 if (start !== -1 && start !== hullNext[start]) { break; }
@@ -179,6 +227,6 @@ }
             // add the first triangle from the point
-            var t = this$1._addTriangle(e, i$6, hullNext[e], -1, -1, hullTri[e]);
+            var t = this._addTriangle(e, i$8, hullNext[e], -1, -1, hullTri[e]);
 
             // recursively flip triangles from the point until they satisfy the Delaunay condition
-            hullTri[i$6] = this$1._legalize(t + 2);
+            hullTri[i$8] = this._legalize(t + 2);
             hullTri[e] = t; // keep track of boundary triangles on the hull
@@ -190,4 +238,4 @@ hullSize++;
             while (q = hullNext[n$1], orient(x$2, y$2, coords[2 * n$1], coords[2 * n$1 + 1], coords[2 * q], coords[2 * q + 1])) {
-                t = this$1._addTriangle(n$1, i$6, q, hullTri[i$6], -1, hullTri[n$1]);
-                hullTri[i$6] = this$1._legalize(t + 2);
+                t = this._addTriangle(n$1, i$8, q, hullTri[i$8], -1, hullTri[n$1]);
+                hullTri[i$8] = this._legalize(t + 2);
                 hullNext[n$1] = n$1; // mark as removed
@@ -201,4 +249,4 @@ hullSize--;
                 while (q = hullPrev[e], orient(x$2, y$2, coords[2 * q], coords[2 * q + 1], coords[2 * e], coords[2 * e + 1])) {
-                    t = this$1._addTriangle(q, i$6, e, -1, hullTri[e], hullTri[q]);
-                    this$1._legalize(t + 2);
+                    t = this._addTriangle(q, i$8, e, -1, hullTri[e], hullTri[q]);
+                    this._legalize(t + 2);
                     hullTri[q] = t;
@@ -212,39 +260,22 @@ hullNext[e] = e; // mark as removed
             // update the hull indices
-            this$1.hullStart = hullPrev[i$6] = e;
-            hullNext[e] = hullPrev[n$1] = i$6;
-            hullNext[i$6] = n$1;
+            this._hullStart = hullPrev[i$8] = e;
+            hullNext[e] = hullPrev[n$1] = i$8;
+            hullNext[i$8] = n$1;
 
             // save the two new edges in the hash table
-            hullHash[this$1._hashKey(x$2, y$2)] = i$6;
-            hullHash[this$1._hashKey(coords[2 * e], coords[2 * e + 1])] = e;
+            hullHash[this._hashKey(x$2, y$2)] = i$8;
+            hullHash[this._hashKey(coords[2 * e], coords[2 * e + 1])] = e;
         }
 
         this.hull = new Uint32Array(hullSize);
-        for (var i$7 = 0, e$1 = this.hullStart; i$7 < hullSize; i$7++) {
-            this$1.hull[i$7] = e$1;
+        for (var i$9 = 0, e$1 = this._hullStart; i$9 < hullSize; i$9++) {
+            this.hull[i$9] = e$1;
             e$1 = hullNext[e$1];
         }
-        this.hullPrev = this.hullNext = this.hullTri = null; // get rid of temporary arrays
 
         // trim typed triangle mesh arrays
-        this.triangles = triangles.subarray(0, this.trianglesLen);
-        this.halfedges = halfedges.subarray(0, this.trianglesLen);
+        this.triangles = this._triangles.subarray(0, this.trianglesLen);
+        this.halfedges = this._halfedges.subarray(0, this.trianglesLen);
     };
 
-    Delaunator.from = function from (points, getX, getY) {
-            if ( getX === void 0 ) getX = defaultGetX;
-            if ( getY === void 0 ) getY = defaultGetY;
-
-        var n = points.length;
-        var coords = new Float64Array(n * 2);
-
-        for (var i = 0; i < n; i++) {
-            var p = points[i];
-            coords[2 * i] = getX(p);
-            coords[2 * i + 1] = getY(p);
-        }
-
-        return new Delaunator(coords);
-    };
-
     Delaunator.prototype._hashKey = function _hashKey (x, y) {
@@ -255,71 +286,84 @@ return Math.floor(pseudoAngle(x - this._cx, y - this._cy) * this._hashSize) % this._hashSize;
     Delaunator.prototype._legalize = function _legalize (a) {
-            var this$1 = this;
-
         var ref = this;
-            var triangles = ref.triangles;
+            var triangles = ref._triangles;
+            var halfedges = ref._halfedges;
             var coords = ref.coords;
-            var halfedges = ref.halfedges;
 
-        var b = halfedges[a];
+        var i = 0;
+        var ar = 0;
 
-        /* if the pair of triangles doesn't satisfy the Delaunay condition
-         * (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
-         * then do the same check/flip recursively for the new pair of triangles
-         *
-         *       pl                pl
-         *      /||\              /  \
-         *   al/ || \bl        al/\a
-         *    /  ||  \          /  \
-         *   /  a||b  \flip/___ar___\
-         * p0\   ||   /p1   =>   p0\---bl---/p1
-         *    \  ||  /          \  /
-         *   ar\ || /br         b\/br
-         *      \||/              \  /
-         *       pr                pr
-         */
-        var a0 = a - a % 3;
-        var b0 = b - b % 3;
+        // recursion eliminated with a fixed-size stack
+        while (true) {
+            var b = halfedges[a];
 
-        var al = a0 + (a + 1) % 3;
-        var ar = a0 + (a + 2) % 3;
-        var bl = b0 + (b + 2) % 3;
+            /* if the pair of triangles doesn't satisfy the Delaunay condition
+             * (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
+             * then do the same check/flip recursively for the new pair of triangles
+             *
+             *       pl                pl
+             *      /||\              /  \
+             *   al/ || \bl        al/\a
+             *    /  ||  \          /  \
+             *   /  a||b  \flip/___ar___\
+             * p0\   ||   /p1   =>   p0\---bl---/p1
+             *    \  ||  /          \  /
+             *   ar\ || /br         b\/br
+             *      \||/              \  /
+             *       pr                pr
+             */
+            var a0 = a - a % 3;
+            ar = a0 + (a + 2) % 3;
 
-        if (b === -1) { return ar; }
+            if (b === -1) { // convex hull edge
+                if (i === 0) { break; }
+                a = EDGE_STACK[--i];
+                continue;
+            }
 
-        var p0 = triangles[ar];
-        var pr = triangles[a];
-        var pl = triangles[al];
-        var p1 = triangles[bl];
+            var b0 = b - b % 3;
+            var al = a0 + (a + 1) % 3;
+            var bl = b0 + (b + 2) % 3;
 
-        var illegal = inCircle(
-            coords[2 * p0], coords[2 * p0 + 1],
-            coords[2 * pr], coords[2 * pr + 1],
-            coords[2 * pl], coords[2 * pl + 1],
-            coords[2 * p1], coords[2 * p1 + 1]);
+            var p0 = triangles[ar];
+            var pr = triangles[a];
+            var pl = triangles[al];
+            var p1 = triangles[bl];
 
-        if (illegal) {
-            triangles[a] = p1;
-            triangles[b] = p0;
+            var illegal = inCircle(
+                coords[2 * p0], coords[2 * p0 + 1],
+                coords[2 * pr], coords[2 * pr + 1],
+                coords[2 * pl], coords[2 * pl + 1],
+                coords[2 * p1], coords[2 * p1 + 1]);
 
-            var hbl = halfedges[bl];
+            if (illegal) {
+                triangles[a] = p1;
+                triangles[b] = p0;
 
-            // edge swapped on the other side of the hull (rare); fix the halfedge reference
-            if (hbl === -1) {
-                var e = this.hullStart;
-                do {
-                    if (this$1.hullTri[e] === bl) {
-                        this$1.hullTri[e] = a;
-                        break;
-                    }
-                    e = this$1.hullNext[e];
-                } while (e !== this.hullStart);
-            }
-            this._link(a, hbl);
-            this._link(b, halfedges[ar]);
-            this._link(ar, bl);
+                var hbl = halfedges[bl];
 
-            var br = b0 + (b + 1) % 3;
+                // edge swapped on the other side of the hull (rare); fix the halfedge reference
+                if (hbl === -1) {
+                    var e = this._hullStart;
+                    do {
+                        if (this._hullTri[e] === bl) {
+                            this._hullTri[e] = a;
+                            break;
+                        }
+                        e = this._hullPrev[e];
+                    } while (e !== this._hullStart);
+                }
+                this._link(a, hbl);
+                this._link(b, halfedges[ar]);
+                this._link(ar, bl);
 
-            this._legalize(a);
-            return this._legalize(br);
+                var br = b0 + (b + 1) % 3;
+
+                // don't worry about hitting the cap: it can only happen on extremely degenerate input
+                if (i < EDGE_STACK.length) {
+                    EDGE_STACK[i++] = br;
+                }
+            } else {
+                if (i === 0) { break; }
+                a = EDGE_STACK[--i];
+            }
         }
@@ -331,4 +375,4 @@
     Delaunator.prototype._link = function _link (a, b) {
-        this.halfedges[a] = b;
-        if (b !== -1) { this.halfedges[b] = a; }
+        this._halfedges[a] = b;
+        if (b !== -1) { this._halfedges[b] = a; }
     };
@@ -340,5 +384,5 @@
 
-        this.triangles[t] = i0;
-        this.triangles[t + 1] = i1;
-        this.triangles[t + 2] = i2;
+        this._triangles[t] = i0;
+        this._triangles[t + 1] = i1;
+        this._triangles[t + 2] = i2;
 
@@ -473,2 +517,2 @@ this._link(t, a);
 
-})));
+}));

delaunator.min.js

@@ -1,1 +0,1 @@
-!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?module.exports=i():"function"==typeof define&&define.amd?define(i):t.Delaunator=i()}(this,function(){"use strict";var t=Math.pow(2,-52),i=function(i){var n=i.length>>1;if(n>0&&"number"!=typeof i[0])throw new Error("Expected coords to contain numbers.");this.coords=i;var s=2*n-5,l=this.triangles=new Uint32Array(3*s),o=this.halfedges=new Int32Array(3*s);this._hashSize=Math.ceil(Math.sqrt(n));for(var f=this.hullPrev=new Uint32Array(n),u=this.hullNext=new Uint32Array(n),v=this.hullTri=new Uint32Array(n),d=new Int32Array(this._hashSize).fill(-1),_=new Uint32Array(n),y=1/0,g=1/0,c=-1/0,w=-1/0,p=0;p<n;p++){var b=i[2*p],x=i[2*p+1];b<y&&(y=b),x<g&&(g=x),b>c&&(c=b),x>w&&(w=x),_[p]=p}for(var z,S,k,A=(y+c)/2,T=(g+w)/2,M=1/0,K=0;K<n;K++){var m=r(A,T,i[2*K],i[2*K+1]);m<M&&(z=K,M=m)}var U=i[2*z],L=i[2*z+1];M=1/0;for(var N=0;N<n;N++)if(N!==z){var E=r(U,L,i[2*N],i[2*N+1]);E<M&&E>0&&(S=N,M=E)}for(var D=i[2*S],F=i[2*S+1],I=1/0,P=0;P<n;P++)if(P!==z&&P!==S){var j=h(U,L,D,F,i[2*P],i[2*P+1]);j<I&&(k=P,I=j)}var q=i[2*k],B=i[2*k+1];if(I===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(a(U,L,D,F,q,B)){var C=S,G=D,H=F;S=k,D=q,F=B,k=C,q=G,B=H}var J=function(t,i,r,a,h,e){var n=r-t,s=a-i,l=h-t,o=e-i,f=n*n+s*s,u=l*l+o*o,v=.5/(n*o-s*l);return{x:t+(o*f-s*u)*v,y:i+(n*u-l*f)*v}}(U,L,D,F,q,B);this._cx=J.x,this._cy=J.y;for(var O=new Float64Array(n),Q=0;Q<n;Q++)O[Q]=r(i[2*Q],i[2*Q+1],J.x,J.y);!function t(i,r,a,h){if(h-a<=20)for(var n=a+1;n<=h;n++){for(var s=i[n],l=r[s],o=n-1;o>=a&&r[i[o]]>l;)i[o+1]=i[o--];i[o+1]=s}else{var f=a+h>>1,u=a+1,v=h;e(i,f,u),r[i[a]]>r[i[h]]&&e(i,a,h),r[i[u]]>r[i[h]]&&e(i,u,h),r[i[a]]>r[i[u]]&&e(i,a,u);for(var d=i[u],_=r[d];;){do{u++}while(r[i[u]]<_);do{v--}while(r[i[v]]>_);if(v<u)break;e(i,u,v)}i[a+1]=i[v],i[v]=d,h-u+1>=v-a?(t(i,r,u,h),t(i,r,a,v-1)):(t(i,r,a,v-1),t(i,r,u,h))}}(_,O,0,n-1),this.hullStart=z;var R=3;u[z]=f[k]=S,u[S]=f[z]=k,u[k]=f[S]=z,v[z]=0,v[S]=1,v[k]=2,d[this._hashKey(U,L)]=z,d[this._hashKey(D,F)]=S,d[this._hashKey(q,B)]=k,this.trianglesLen=0,this._addTriangle(z,S,k,-1,-1,-1);for(var V=0,W=void 0,X=void 0;V<_.length;V++){var Y=_[V],Z=i[2*Y],$=i[2*Y+1];if(!(V>0&&Math.abs(Z-W)<=t&&Math.abs($-X)<=t)&&(W=Z,X=$,Y!==z&&Y!==S&&Y!==k)){for(var tt=0,it=0,rt=this._hashKey(Z,$);it<this._hashSize&&(-1===(tt=d[(rt+it)%this._hashSize])||tt===u[tt]);it++);for(var at=tt=f[tt],ht=void 0;ht=u[at],!a(Z,$,i[2*at],i[2*at+1],i[2*ht],i[2*ht+1]);)if((at=ht)===tt){at=-1;break}if(-1!==at){var et=this._addTriangle(at,Y,u[at],-1,-1,v[at]);v[Y]=this._legalize(et+2),v[at]=et,R++;for(var nt=u[at];ht=u[nt],a(Z,$,i[2*nt],i[2*nt+1],i[2*ht],i[2*ht+1]);)et=this._addTriangle(nt,Y,ht,v[Y],-1,v[nt]),v[Y]=this._legalize(et+2),u[nt]=nt,R--,nt=ht;if(at===tt)for(;a(Z,$,i[2*(ht=f[at])],i[2*ht+1],i[2*at],i[2*at+1]);)et=this._addTriangle(ht,Y,at,-1,v[at],v[ht]),this._legalize(et+2),v[ht]=et,u[at]=at,R--,at=ht;this.hullStart=f[Y]=at,u[at]=f[nt]=Y,u[Y]=nt,d[this._hashKey(Z,$)]=Y,d[this._hashKey(i[2*at],i[2*at+1])]=at}}}this.hull=new Uint32Array(R);for(var st=0,lt=this.hullStart;st<R;st++)this.hull[st]=lt,lt=u[lt];this.hullPrev=this.hullNext=this.hullTri=null,this.triangles=l.subarray(0,this.trianglesLen),this.halfedges=o.subarray(0,this.trianglesLen)};function r(t,i,r,a){var h=t-r,e=i-a;return h*h+e*e}function a(t,i,r,a,h,e){return(a-i)*(h-r)-(r-t)*(e-a)<0}function h(t,i,r,a,h,e){var n=r-t,s=a-i,l=h-t,o=e-i,f=n*n+s*s,u=l*l+o*o,v=.5/(n*o-s*l),d=(o*f-s*u)*v,_=(n*u-l*f)*v;return d*d+_*_}function e(t,i,r){var a=t[i];t[i]=t[r],t[r]=a}function n(t){return t[0]}function s(t){return t[1]}return i.from=function(t,r,a){void 0===r&&(r=n),void 0===a&&(a=s);for(var h=t.length,e=new Float64Array(2*h),l=0;l<h;l++){var o=t[l];e[2*l]=r(o),e[2*l+1]=a(o)}return new i(e)},i.prototype._hashKey=function(t,i){return Math.floor((r=t-this._cx,a=i-this._cy,h=r/(Math.abs(r)+Math.abs(a)),(a>0?3-h:1+h)/4*this._hashSize))%this._hashSize;var r,a,h},i.prototype._legalize=function(t){var i=this.triangles,r=this.coords,a=this.halfedges,h=a[t],e=t-t%3,n=h-h%3,s=e+(t+1)%3,l=e+(t+2)%3,o=n+(h+2)%3;if(-1===h)return l;var f,u,v,d,_,y,g,c,w,p,b,x,z,S,k,A,T=i[l],M=i[t],K=i[s],m=i[o];if(f=r[2*T],u=r[2*T+1],v=r[2*M],d=r[2*M+1],_=r[2*K],y=r[2*K+1],g=r[2*m],c=r[2*m+1],(w=f-g)*((x=d-c)*(A=(z=_-g)*z+(S=y-c)*S)-(k=(b=v-g)*b+x*x)*S)-(p=u-c)*(b*A-k*z)+(w*w+p*p)*(b*S-x*z)<0){i[t]=m,i[h]=T;var U=a[o];if(-1===U){var L=this.hullStart;do{if(this.hullTri[L]===o){this.hullTri[L]=t;break}L=this.hullNext[L]}while(L!==this.hullStart)}this._link(t,U),this._link(h,a[l]),this._link(l,o);var N=n+(h+1)%3;return this._legalize(t),this._legalize(N)}return l},i.prototype._link=function(t,i){this.halfedges[t]=i,-1!==i&&(this.halfedges[i]=t)},i.prototype._addTriangle=function(t,i,r,a,h,e){var n=this.trianglesLen;return this.triangles[n]=t,this.triangles[n+1]=i,this.triangles[n+2]=r,this._link(n,a),this._link(n+1,h),this._link(n+2,e),this.trianglesLen+=3,n},i});
+!function(i,t){"object"==typeof exports&&"undefined"!=typeof module?module.exports=t():"function"==typeof define&&define.amd?define(t):(i=i||self).Delaunator=t()}(this,function(){"use strict";var i=Math.pow(2,-52),t=new Uint32Array(512),r=function(i){var t=i.length>>1;if(t>0&&"number"!=typeof i[0])throw new Error("Expected coords to contain numbers.");this.coords=i;var r=Math.max(2*t-5,0);this._triangles=new Uint32Array(3*r),this._halfedges=new Int32Array(3*r),this._hashSize=Math.ceil(Math.sqrt(t)),this._hullPrev=new Uint32Array(t),this._hullNext=new Uint32Array(t),this._hullTri=new Uint32Array(t),this._hullHash=new Int32Array(this._hashSize).fill(-1),this._ids=new Uint32Array(t),this._dists=new Float64Array(t),this.update()};function s(i,t,r,s){var h=i-r,a=t-s;return h*h+a*a}function h(i,t,r,s,h,a){return(s-t)*(h-r)-(r-i)*(a-s)<0}function a(i,t,r,s,h,a){var e=r-i,n=s-t,l=h-i,o=a-t,_=e*e+n*n,f=l*l+o*o,d=.5/(e*o-n*l),v=(o*_-n*f)*d,u=(e*f-l*_)*d;return v*v+u*u}function e(i,t,r,s){if(s-r<=20)for(var h=r+1;h<=s;h++){for(var a=i[h],l=t[a],o=h-1;o>=r&&t[i[o]]>l;)i[o+1]=i[o--];i[o+1]=a}else{var _=r+1,f=s;n(i,r+s>>1,_),t[i[r]]>t[i[s]]&&n(i,r,s),t[i[_]]>t[i[s]]&&n(i,_,s),t[i[r]]>t[i[_]]&&n(i,r,_);for(var d=i[_],v=t[d];;){do{_++}while(t[i[_]]<v);do{f--}while(t[i[f]]>v);if(f<_)break;n(i,_,f)}i[r+1]=i[f],i[f]=d,s-_+1>=f-r?(e(i,t,_,s),e(i,t,r,f-1)):(e(i,t,r,f-1),e(i,t,_,s))}}function n(i,t,r){var s=i[t];i[t]=i[r],i[r]=s}function l(i){return i[0]}function o(i){return i[1]}return r.from=function(i,t,s){void 0===t&&(t=l),void 0===s&&(s=o);for(var h=i.length,a=new Float64Array(2*h),e=0;e<h;e++){var n=i[e];a[2*e]=t(n),a[2*e+1]=s(n)}return new r(a)},r.prototype.update=function(){for(var t=this.coords,r=this._hullPrev,n=this._hullNext,l=this._hullTri,o=this._hullHash,_=t.length>>1,f=1/0,d=1/0,v=-1/0,u=-1/0,y=0;y<_;y++){var g=t[2*y],c=t[2*y+1];g<f&&(f=g),c<d&&(d=c),g>v&&(v=g),c>u&&(u=c),this._ids[y]=y}for(var w,p,b,A=(f+v)/2,k=(d+u)/2,x=1/0,S=0;S<_;S++){var z=s(A,k,t[2*S],t[2*S+1]);z<x&&(w=S,x=z)}var U=t[2*w],M=t[2*w+1];x=1/0;for(var T=0;T<_;T++)if(T!==w){var m=s(U,M,t[2*T],t[2*T+1]);m<x&&m>0&&(p=T,x=m)}for(var K=t[2*p],L=t[2*p+1],P=1/0,E=0;E<_;E++)if(E!==w&&E!==p){var F=a(U,M,K,L,t[2*E],t[2*E+1]);F<P&&(b=E,P=F)}var H=t[2*b],I=t[2*b+1];if(P===1/0){for(var N=0;N<_;N++)this._dists[N]=t[2*N]-t[0]||t[2*N+1]-t[1];e(this._ids,this._dists,0,_-1);for(var j=new Uint32Array(_),q=0,D=0,B=-1/0;D<_;D++){var C=this._ids[D];this._dists[C]>B&&(j[q++]=C,B=this._dists[C])}return this.hull=j.subarray(0,q),this.triangles=new Uint32Array(0),void(this.halfedges=new Uint32Array(0))}if(h(U,M,K,L,H,I)){var G=p,J=K,O=L;p=b,K=H,L=I,b=G,H=J,I=O}var Q=function(i,t,r,s,h,a){var e=r-i,n=s-t,l=h-i,o=a-t,_=e*e+n*n,f=l*l+o*o,d=.5/(e*o-n*l);return{x:i+(o*_-n*f)*d,y:t+(e*f-l*_)*d}}(U,M,K,L,H,I);this._cx=Q.x,this._cy=Q.y;for(var R=0;R<_;R++)this._dists[R]=s(t[2*R],t[2*R+1],Q.x,Q.y);e(this._ids,this._dists,0,_-1),this._hullStart=w;var V=3;n[w]=r[b]=p,n[p]=r[w]=b,n[b]=r[p]=w,l[w]=0,l[p]=1,l[b]=2,o.fill(-1),o[this._hashKey(U,M)]=w,o[this._hashKey(K,L)]=p,o[this._hashKey(H,I)]=b,this.trianglesLen=0,this._addTriangle(w,p,b,-1,-1,-1);for(var W=0,X=void 0,Y=void 0;W<this._ids.length;W++){var Z=this._ids[W],$=t[2*Z],ii=t[2*Z+1];if(!(W>0&&Math.abs($-X)<=i&&Math.abs(ii-Y)<=i)&&(X=$,Y=ii,Z!==w&&Z!==p&&Z!==b)){for(var ti=0,ri=0,si=this._hashKey($,ii);ri<this._hashSize&&(-1===(ti=o[(si+ri)%this._hashSize])||ti===n[ti]);ri++);for(var hi=ti=r[ti],ai=void 0;ai=n[hi],!h($,ii,t[2*hi],t[2*hi+1],t[2*ai],t[2*ai+1]);)if((hi=ai)===ti){hi=-1;break}if(-1!==hi){var ei=this._addTriangle(hi,Z,n[hi],-1,-1,l[hi]);l[Z]=this._legalize(ei+2),l[hi]=ei,V++;for(var ni=n[hi];ai=n[ni],h($,ii,t[2*ni],t[2*ni+1],t[2*ai],t[2*ai+1]);)ei=this._addTriangle(ni,Z,ai,l[Z],-1,l[ni]),l[Z]=this._legalize(ei+2),n[ni]=ni,V--,ni=ai;if(hi===ti)for(;h($,ii,t[2*(ai=r[hi])],t[2*ai+1],t[2*hi],t[2*hi+1]);)ei=this._addTriangle(ai,Z,hi,-1,l[hi],l[ai]),this._legalize(ei+2),l[ai]=ei,n[hi]=hi,V--,hi=ai;this._hullStart=r[Z]=hi,n[hi]=r[ni]=Z,n[Z]=ni,o[this._hashKey($,ii)]=Z,o[this._hashKey(t[2*hi],t[2*hi+1])]=hi}}}this.hull=new Uint32Array(V);for(var li=0,oi=this._hullStart;li<V;li++)this.hull[li]=oi,oi=n[oi];this.triangles=this._triangles.subarray(0,this.trianglesLen),this.halfedges=this._halfedges.subarray(0,this.trianglesLen)},r.prototype._hashKey=function(i,t){return Math.floor((r=i-this._cx,s=t-this._cy,h=r/(Math.abs(r)+Math.abs(s)),(s>0?3-h:1+h)/4*this._hashSize))%this._hashSize;var r,s,h},r.prototype._legalize=function(i){for(var r,s,h,a,e,n,l,o,_,f,d,v,u,y,g,c,w=this._triangles,p=this._halfedges,b=this.coords,A=0,k=0;;){var x=p[i],S=i-i%3;if(k=S+(i+2)%3,-1!==x){var z=x-x%3,U=S+(i+1)%3,M=z+(x+2)%3,T=w[k],m=w[i],K=w[U],L=w[M];if(r=b[2*T],s=b[2*T+1],h=b[2*m],a=b[2*m+1],e=b[2*K],n=b[2*K+1],l=b[2*L],o=b[2*L+1],_=void 0,f=void 0,d=void 0,v=void 0,u=void 0,y=void 0,void 0,g=void 0,c=void 0,(_=r-l)*((v=a-o)*(c=(u=e-l)*u+(y=n-o)*y)-(g=(d=h-l)*d+v*v)*y)-(f=s-o)*(d*c-g*u)+(_*_+f*f)*(d*y-v*u)<0){w[i]=L,w[x]=T;var P=p[M];if(-1===P){var E=this._hullStart;do{if(this._hullTri[E]===M){this._hullTri[E]=i;break}E=this._hullPrev[E]}while(E!==this._hullStart)}this._link(i,P),this._link(x,p[k]),this._link(k,M);var F=z+(x+1)%3;A<t.length&&(t[A++]=F)}else{if(0===A)break;i=t[--A]}}else{if(0===A)break;i=t[--A]}}return k},r.prototype._link=function(i,t){this._halfedges[i]=t,-1!==t&&(this._halfedges[t]=i)},r.prototype._addTriangle=function(i,t,r,s,h,a){var e=this.trianglesLen;return this._triangles[e]=i,this._triangles[e+1]=t,this._triangles[e+2]=r,this._link(e,s),this._link(e+1,h),this._link(e+2,a),this.trianglesLen+=3,e},r});

index.js

 
 const EPSILON = Math.pow(2, -52);
+const EDGE_STACK = new Uint32Array(512);
 
@@ -26,15 +27,25 @@ export default class Delaunator {
         // arrays that will store the triangulation graph
-        const maxTriangles = 2 * n - 5;
-        const triangles = this.triangles = new Uint32Array(maxTriangles * 3);
-        const halfedges = this.halfedges = new Int32Array(maxTriangles * 3);
+        const maxTriangles = Math.max(2 * n - 5, 0);
+        this._triangles = new Uint32Array(maxTriangles * 3);
+        this._halfedges = new Int32Array(maxTriangles * 3);
 
         // temporary arrays for tracking the edges of the advancing convex hull
         this._hashSize = Math.ceil(Math.sqrt(n));
-        const hullPrev = this.hullPrev = new Uint32Array(n); // edge to prev edge
-        const hullNext = this.hullNext = new Uint32Array(n); // edge to next edge
-        const hullTri = this.hullTri = new Uint32Array(n); // edge to adjacent triangle
-        const hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash
+        this._hullPrev = new Uint32Array(n); // edge to prev edge
+        this._hullNext = new Uint32Array(n); // edge to next edge
+        this._hullTri = new Uint32Array(n); // edge to adjacent triangle
+        this._hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash
 
+        // temporary arrays for sorting points
+        this._ids = new Uint32Array(n);
+        this._dists = new Float64Array(n);
+
+        this.update();
+    }
+
+    update() {
+        const {coords, _hullPrev: hullPrev, _hullNext: hullNext, _hullTri: hullTri, _hullHash: hullHash} =  this;
+        const n = coords.length >> 1;
+
         // populate an array of point indices; calculate input data bbox
-        const ids = new Uint32Array(n);
         let minX = Infinity;
@@ -52,3 +63,3 @@ let minY = Infinity;
             if (y > maxY) maxY = y;
-            ids[i] = i;
+            this._ids[i] = i;
         }
@@ -101,3 +112,21 @@ const cx = (minX + maxX) / 2;
         if (minRadius === Infinity) {
-            throw new Error('No Delaunay triangulation exists for this input.');
+            // order collinear points by dx (or dy if all x are identical)
+            // and return the list as a hull
+            for (let i = 0; i < n; i++) {
+                this._dists[i] = (coords[2 * i] - coords[0]) || (coords[2 * i + 1] - coords[1]);
+            }
+            quicksort(this._ids, this._dists, 0, n - 1);
+            const hull = new Uint32Array(n);
+            let j = 0;
+            for (let i = 0, d0 = -Infinity; i < n; i++) {
+                const id = this._ids[i];
+                if (this._dists[id] > d0) {
+                    hull[j++] = id;
+                    d0 = this._dists[id];
+                }
+            }
+            this.hull = hull.subarray(0, j);
+            this.triangles = new Uint32Array(0);
+            this.halfedges = new Uint32Array(0);
+            return;
         }
@@ -122,12 +151,11 @@
 
-        const dists = new Float64Array(n);
         for (let i = 0; i < n; i++) {
-            dists[i] = dist(coords[2 * i], coords[2 * i + 1], center.x, center.y);
+            this._dists[i] = dist(coords[2 * i], coords[2 * i + 1], center.x, center.y);
         }
 
         // sort the points by distance from the seed triangle circumcenter
-        quicksort(ids, dists, 0, n - 1);
+        quicksort(this._ids, this._dists, 0, n - 1);
 
         // set up the seed triangle as the starting hull
-        this.hullStart = i0;
+        this._hullStart = i0;
         let hullSize = 3;
@@ -143,2 +171,3 @@
 
+        hullHash.fill(-1);
         hullHash[this._hashKey(i0x, i0y)] = i0;
@@ -151,4 +180,4 @@ hullHash[this._hashKey(i1x, i1y)] = i1;
 
-        for (let k = 0, xp, yp; k < ids.length; k++) {
-            const i = ids[k];
+        for (let k = 0, xp, yp; k < this._ids.length; k++) {
+            const i = this._ids[k];
             const x = coords[2 * i];
@@ -214,3 +243,3 @@ const y = coords[2 * i + 1];
             // update the hull indices
-            this.hullStart = hullPrev[i] = e;
+            this._hullStart = hullPrev[i] = e;
             hullNext[e] = hullPrev[n] = i;
@@ -225,11 +254,10 @@ hullNext[i] = n;
         this.hull = new Uint32Array(hullSize);
-        for (let i = 0, e = this.hullStart; i < hullSize; i++) {
+        for (let i = 0, e = this._hullStart; i < hullSize; i++) {
             this.hull[i] = e;
             e = hullNext[e];
         }
-        this.hullPrev = this.hullNext = this.hullTri = null; // get rid of temporary arrays
 
         // trim typed triangle mesh arrays
-        this.triangles = triangles.subarray(0, this.trianglesLen);
-        this.halfedges = halfedges.subarray(0, this.trianglesLen);
+        this.triangles = this._triangles.subarray(0, this.trianglesLen);
+        this.halfedges = this._halfedges.subarray(0, this.trianglesLen);
     }
@@ -242,66 +270,81 @@
     _legalize(a) {
-        const {triangles, coords, halfedges} = this;
+        const {_triangles: triangles, _halfedges: halfedges, coords} = this;
 
-        const b = halfedges[a];
+        let i = 0;
+        let ar = 0;
 
-        /* if the pair of triangles doesn't satisfy the Delaunay condition
-         * (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
-         * then do the same check/flip recursively for the new pair of triangles
-         *
-         *           pl                    pl
-         *          /||\                  /  \
-         *       al/ || \bl            al/    \a
-         *        /  ||  \              /      \
-         *       /  a||b  \    flip    /___ar___\
-         *     p0\   ||   /p1   =>   p0\---bl---/p1
-         *        \  ||  /              \      /
-         *       ar\ || /br             b\    /br
-         *          \||/                  \  /
-         *           pr                    pr
-         */
-        const a0 = a - a % 3;
-        const b0 = b - b % 3;
+        // recursion eliminated with a fixed-size stack
+        while (true) {
+            const b = halfedges[a];
 
-        const al = a0 + (a + 1) % 3;
-        const ar = a0 + (a + 2) % 3;
-        const bl = b0 + (b + 2) % 3;
+            /* if the pair of triangles doesn't satisfy the Delaunay condition
+             * (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
+             * then do the same check/flip recursively for the new pair of triangles
+             *
+             *           pl                    pl
+             *          /||\                  /  \
+             *       al/ || \bl            al/    \a
+             *        /  ||  \              /      \
+             *       /  a||b  \    flip    /___ar___\
+             *     p0\   ||   /p1   =>   p0\---bl---/p1
+             *        \  ||  /              \      /
+             *       ar\ || /br             b\    /br
+             *          \||/                  \  /
+             *           pr                    pr
+             */
+            const a0 = a - a % 3;
+            ar = a0 + (a + 2) % 3;
 
-        if (b === -1) return ar;
+            if (b === -1) { // convex hull edge
+                if (i === 0) break;
+                a = EDGE_STACK[--i];
+                continue;
+            }
 
-        const p0 = triangles[ar];
-        const pr = triangles[a];
-        const pl = triangles[al];
-        const p1 = triangles[bl];
+            const b0 = b - b % 3;
+            const al = a0 + (a + 1) % 3;
+            const bl = b0 + (b + 2) % 3;
 
-        const illegal = inCircle(
-            coords[2 * p0], coords[2 * p0 + 1],
-            coords[2 * pr], coords[2 * pr + 1],
-            coords[2 * pl], coords[2 * pl + 1],
-            coords[2 * p1], coords[2 * p1 + 1]);
+            const p0 = triangles[ar];
+            const pr = triangles[a];
+            const pl = triangles[al];
+            const p1 = triangles[bl];
 
-        if (illegal) {
-            triangles[a] = p1;
-            triangles[b] = p0;
+            const illegal = inCircle(
+                coords[2 * p0], coords[2 * p0 + 1],
+                coords[2 * pr], coords[2 * pr + 1],
+                coords[2 * pl], coords[2 * pl + 1],
+                coords[2 * p1], coords[2 * p1 + 1]);
 
-            const hbl = halfedges[bl];
+            if (illegal) {
+                triangles[a] = p1;
+                triangles[b] = p0;
 
-            // edge swapped on the other side of the hull (rare); fix the halfedge reference
-            if (hbl === -1) {
-                let e = this.hullStart;
-                do {
-                    if (this.hullTri[e] === bl) {
-                        this.hullTri[e] = a;
-                        break;
-                    }
-                    e = this.hullNext[e];
-                } while (e !== this.hullStart);
-            }
-            this._link(a, hbl);
-            this._link(b, halfedges[ar]);
-            this._link(ar, bl);
+                const hbl = halfedges[bl];
 
-            const br = b0 + (b + 1) % 3;
+                // edge swapped on the other side of the hull (rare); fix the halfedge reference
+                if (hbl === -1) {
+                    let e = this._hullStart;
+                    do {
+                        if (this._hullTri[e] === bl) {
+                            this._hullTri[e] = a;
+                            break;
+                        }
+                        e = this._hullPrev[e];
+                    } while (e !== this._hullStart);
+                }
+                this._link(a, hbl);
+                this._link(b, halfedges[ar]);
+                this._link(ar, bl);
 
-            this._legalize(a);
-            return this._legalize(br);
+                const br = b0 + (b + 1) % 3;
+
+                // don't worry about hitting the cap: it can only happen on extremely degenerate input
+                if (i < EDGE_STACK.length) {
+                    EDGE_STACK[i++] = br;
+                }
+            } else {
+                if (i === 0) break;
+                a = EDGE_STACK[--i];
+            }
         }
@@ -313,4 +356,4 @@
     _link(a, b) {
-        this.halfedges[a] = b;
-        if (b !== -1) this.halfedges[b] = a;
+        this._halfedges[a] = b;
+        if (b !== -1) this._halfedges[b] = a;
     }
@@ -322,5 +365,5 @@
 
-        this.triangles[t] = i0;
-        this.triangles[t + 1] = i1;
-        this.triangles[t + 2] = i2;
+        this._triangles[t] = i0;
+        this._triangles[t + 1] = i1;
+        this._triangles[t + 2] = i2;
 
@@ -327,0 +370,0 @@ this._link(t, a);

package.json

 {
   "name": "delaunator",
-  "version": "3.0.2",
+  "version": "4.0.0",
   "description": "An incredibly fast JavaScript library for Delaunay triangulation of 2D points",
@@ -11,10 +11,10 @@ "main": "delaunator.js",
   "devDependencies": {
-    "c8": "^3.2.0",
-    "eslint": "^5.6.0",
+    "c8": "^5.0.1",
+    "eslint": "^5.16.0",
     "eslint-config-mourner": "^3.0.0",
-    "esm": "^3.0.84",
-    "rollup": "^0.66.2",
-    "rollup-plugin-buble": "^0.19.2",
-    "rollup-plugin-terser": "^3.0.0",
-    "tape": "^4.9.1"
+    "esm": "^3.2.25",
+    "rollup": "^1.15.6",
+    "rollup-plugin-buble": "^0.19.6",
+    "rollup-plugin-terser": "^5.0.0",
+    "tape": "^4.10.2"
   },
@@ -26,6 +26,6 @@ "repository": {
   "scripts": {
-    "lint": "eslint index.js test.js bench.js rollup.config.js docs/diagrams.js",
+    "lint": "eslint index.js test/test.js bench.js rollup.config.js docs/diagrams.js",
     "pretest": "npm run lint",
-    "test": "node -r esm test.js",
-    "cov": "c8 node -r esm test.js && c8 report -r html",
+    "test": "node -r esm test/test.js",
+    "cov": "c8 node -r esm test/test.js && c8 report -r html",
     "bench": "node -r esm bench.js",
@@ -32,0 +32,0 @@ "build": "rollup -c",

README.md

@@ -9,3 +9,3 @@ # Delaunator [![Build Status](https://travis-ci.org/mapbox/delaunator.svg?branch=master)](https://travis-ci.org/mapbox/delaunator) [![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
 
-Projects based on Delaunator:
+### Projects based on Delaunator
 
@@ -15,7 +15,7 @@ - [d3-delaunay](https://github.com/d3/d3-delaunay) for Voronoi diagrams, search, traversal and rendering.
 
-Ports to other languages:
+### Ports to other languages
 
+- [delaunator-rs](https://github.com/mourner/delaunator-rs) (Rust)
 - [fogleman/delaunay](https://github.com/fogleman/delaunay) (Go)
-- [delaunator-rs](https://github.com/mourner/delaunator-rs) (Rust, a work in progress)
-- [delaunator-cpp](https://github.com/delfrrr/delaunator-cpp) (C++, a work in progress)
+- [delaunator-cpp](https://github.com/delfrrr/delaunator-cpp) (C++)
 
@@ -49,4 +49,4 @@ <img src="delaunator.png" alt="Delaunay triangulation example" width="600" />
 ```html
-<script src="https://unpkg.com/delaunator@3.0.1/delaunator.min.js"></script> <!-- minified build -->
-<script src="https://unpkg.com/delaunator@3.0.1/delaunator.js"></script> <!-- dev build -->
+<script src="https://unpkg.com/delaunator@3.0.2/delaunator.min.js"></script> <!-- minified build -->
+<script src="https://unpkg.com/delaunator@3.0.2/delaunator.js"></script> <!-- dev build -->
 ```
@@ -103,2 +103,7 @@
 
+#### delaunay.update()
+
+Updates the triangulation if you modified `delaunay.coords` values in place, avoiding expensive memory allocations.
+Useful for iterative relaxation algorithms such as [Lloyd's](https://en.wikipedia.org/wiki/Lloyd%27s_algorithm).
+
 ## Performance
@@ -111,3 +116,3 @@
 :-- | --: | --: | --: | --: | --: | --: | --: | --:
-**delaunator** | 95ms | 75ms | 68ms | 31ms | 1.15s | 1.11s | 979ms | 314ms
+**delaunator** | 82ms | 61ms | 66ms | 25ms | 1.07s | 950ms | 830ms | 278ms
 [faster&#8209;delaunay](https://github.com/Bathlamos/delaunay-triangulation) | 473ms | 411ms | 272ms | 68ms | 4.27s | 4.62s | 4.3s | 810ms
@@ -114,0 +119,0 @@ [incremental&#8209;delaunay](https://github.com/mikolalysenko/incremental-delaunay) | 547ms | 505ms | 172ms | 528ms | 5.9s | 6.08s | 2.11s | 6.09s

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

45958

increased by10.37%

Lines of code

839

increased by11.13%

Number of lines in readme file

128

increased by4.07%

No dependency changes