delaunator - npm Package Compare versions

Comparing version 3.0.1 to 3.0.2

delaunator.js

@@ -12,2 +12,21 @@ (function (global, factory) {
 
+        var n = coords.length >> 1;
+        if (n > 0 && typeof coords[0] !== 'number') { throw new Error('Expected coords to contain numbers.'); }
+
+        this.coords = coords;
+
+        // 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);
+
+        // 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
+
+        // populate an array of point indices; calculate input data bbox
+        var ids = new Uint32Array(n);
         var minX = Infinity;
@@ -18,9 +37,2 @@ var minY = Infinity;
 
-        var n = coords.length >> 1;
-        var ids = this.ids = new Uint32Array(n);
-
-        if (n > 0 && typeof coords[0] !== 'number') { throw new Error('Expected coords to contain numbers.'); }
-
-        this.coords = coords;
-
         for (var i = 0; i < n; i++) {
@@ -35,3 +47,2 @@ var x = coords[2 * i];
         }
-
         var cx = (minX + maxX) / 2;
@@ -43,3 +54,3 @@ var cy = (minY + maxY) / 2;
 
-        // pick a seed point close to the centroid
+        // pick a seed point close to the center
         for (var i$1 = 0; i$1 < n; i$1++) {
@@ -104,14 +115,10 @@ var d = dist(cx, cy, coords[2 * i$1], coords[2 * i$1 + 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);
+        }
+
         // sort the points by distance from the seed triangle circumcenter
-        quicksort(ids, coords, 0, ids.length - 1, center.x, center.y);
+        quicksort(ids, dists, 0, n - 1);
 
-        // initialize a hash table for storing edges of the advancing convex hull
-        this._hashSize = Math.ceil(Math.sqrt(n));
-        this._hash = new Int32Array(this._hashSize).fill(-1);
-
-        // initialize arrays for tracking the edges of the advancing convex hull
-        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
-
         // set up the seed triangle as the starting hull
@@ -129,18 +136,13 @@ this.hullStart = i0;
 
-        this._hash[this._hashKey(i0x, i0y)] = i0;
-        this._hash[this._hashKey(i1x, i1y)] = i1;
-        this._hash[this._hashKey(i2x, i2y)] = i2;
+        hullHash[this._hashKey(i0x, i0y)] = i0;
+        hullHash[this._hashKey(i1x, i1y)] = i1;
+        hullHash[this._hashKey(i2x, i2y)] = i2;
 
-        var maxTriangles = 2 * n - 5;
-        var triangles = this.triangles = new Uint32Array(maxTriangles * 3);
-        var halfedges = this.halfedges = new Int32Array(maxTriangles * 3);
-
         this.trianglesLen = 0;
-
         this._addTriangle(i0, i1, i2, -1, -1, -1);
 
         for (var k = 0, xp = (void 0), yp = (void 0); k < ids.length; k++) {
-            var i$5 = ids[k];
-            var x$2 = coords[2 * i$5];
-            var y$2 = coords[2 * i$5 + 1];
+            var i$6 = ids[k];
+            var x$2 = coords[2 * i$6];
+            var y$2 = coords[2 * i$6 + 1];
 
@@ -153,3 +155,3 @@ // skip near-duplicate points
             // skip seed triangle points
-            if (i$5 === i0 || i$5 === i1 || i$5 === i2) { continue; }
+            if (i$6 === i0 || i$6 === i1 || i$6 === i2) { continue; }
 
@@ -159,3 +161,3 @@ // find a visible edge on the convex hull using edge hash
             for (var j = 0, key = this._hashKey(x$2, y$2); j < this._hashSize; j++) {
-                start = this$1._hash[(key + j) % this$1._hashSize];
+                start = hullHash[(key + j) % this$1._hashSize];
                 if (start !== -1 && start !== hullNext[start]) { break; }
@@ -176,6 +178,6 @@ }
             // add the first triangle from the point
-            var t = this$1._addTriangle(e, i$5, hullNext[e], -1, -1, hullTri[e]);
+            var t = this$1._addTriangle(e, i$6, hullNext[e], -1, -1, hullTri[e]);
 
             // recursively flip triangles from the point until they satisfy the Delaunay condition
-            hullTri[i$5] = this$1._legalize(t + 2);
+            hullTri[i$6] = this$1._legalize(t + 2);
             hullTri[e] = t; // keep track of boundary triangles on the hull
@@ -187,4 +189,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$5, q, hullTri[i$5], -1, hullTri[n$1]);
-                hullTri[i$5] = this$1._legalize(t + 2);
+                t = this$1._addTriangle(n$1, i$6, q, hullTri[i$6], -1, hullTri[n$1]);
+                hullTri[i$6] = this$1._legalize(t + 2);
                 hullNext[n$1] = n$1; // mark as removed
@@ -198,3 +200,3 @@ 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$5, e, -1, hullTri[e], hullTri[q]);
+                    t = this$1._addTriangle(q, i$6, e, -1, hullTri[e], hullTri[q]);
                     this$1._legalize(t + 2);
@@ -209,14 +211,14 @@ hullTri[q] = t;
             // update the hull indices
-            this$1.hullStart = hullPrev[i$5] = e;
-            hullNext[e] = hullPrev[n$1] = i$5;
-            hullNext[i$5] = n$1;
+            this$1.hullStart = hullPrev[i$6] = e;
+            hullNext[e] = hullPrev[n$1] = i$6;
+            hullNext[i$6] = n$1;
 
             // save the two new edges in the hash table
-            this$1._hash[this$1._hashKey(x$2, y$2)] = i$5;
-            this$1._hash[this$1._hashKey(coords[2 * e], coords[2 * e + 1])] = e;
+            hullHash[this$1._hashKey(x$2, y$2)] = i$6;
+            hullHash[this$1._hashKey(coords[2 * e], coords[2 * e + 1])] = e;
         }
 
         this.hull = new Uint32Array(hullSize);
-        for (var i$6 = 0, e$1 = this.hullStart; i$6 < hullSize; i$6++) {
-            this$1.hull[i$6] = e$1;
+        for (var i$7 = 0, e$1 = this.hullStart; i$7 < hullSize; i$7++) {
+            this$1.hull[i$7] = e$1;
             e$1 = hullNext[e$1];
@@ -232,4 +234,4 @@ }
     Delaunator.from = function from (points, getX, getY) {
-        if (!getX) { getX = defaultGetX; }
-        if (!getY) { getY = defaultGetY; }
+            if ( getX === void 0 ) getX = defaultGetX;
+            if ( getY === void 0 ) getY = defaultGetY;
 
@@ -390,8 +392,8 @@ var n = points.length;
         var cl = ex * ex + ey * ey;
-        var d = dx * ey - dy * ex;
+        var d = 0.5 / (dx * ey - dy * ex);
 
-        var x = (ey * bl - dy * cl) * 0.5 / d;
-        var y = (dx * cl - ex * bl) * 0.5 / d;
+        var x = (ey * bl - dy * cl) * d;
+        var y = (dx * cl - ex * bl) * d;
 
-        return bl && cl && d && (x * x + y * y) || Infinity;
+        return x * x + y * y;
     }
@@ -407,6 +409,6 @@
         var cl = ex * ex + ey * ey;
-        var d = dx * ey - dy * ex;
+        var d = 0.5 / (dx * ey - dy * ex);
 
-        var x = ax + (ey * bl - dy * cl) * 0.5 / d;
-        var y = ay + (dx * cl - ex * bl) * 0.5 / d;
+        var x = ax + (ey * bl - dy * cl) * d;
+        var y = ay + (dx * cl - ex * bl) * d;
 
@@ -416,10 +418,9 @@ return {x: x, y: y};
 
-    function quicksort(ids, coords, left, right, cx, cy) {
-        var i, j, temp;
-
+    function quicksort(ids, dists, left, right) {
         if (right - left <= 20) {
-            for (i = left + 1; i <= right; i++) {
-                temp = ids[i];
-                j = i - 1;
-                while (j >= left && compare(coords, ids[j], temp, cx, cy) > 0) { ids[j + 1] = ids[j--]; }
+            for (var i = left + 1; i <= right; i++) {
+                var temp = ids[i];
+                var tempDist = dists[temp];
+                var j = i - 1;
+                while (j >= left && dists[ids[j]] > tempDist) { ids[j + 1] = ids[j--]; }
                 ids[j + 1] = temp;
@@ -429,25 +430,26 @@ }
             var median = (left + right) >> 1;
-            i = left + 1;
-            j = right;
-            swap(ids, median, i);
-            if (compare(coords, ids[left], ids[right], cx, cy) > 0) { swap(ids, left, right); }
-            if (compare(coords, ids[i], ids[right], cx, cy) > 0) { swap(ids, i, right); }
-            if (compare(coords, ids[left], ids[i], cx, cy) > 0) { swap(ids, left, i); }
+            var i$1 = left + 1;
+            var j$1 = right;
+            swap(ids, median, i$1);
+            if (dists[ids[left]] > dists[ids[right]]) { swap(ids, left, right); }
+            if (dists[ids[i$1]] > dists[ids[right]]) { swap(ids, i$1, right); }
+            if (dists[ids[left]] > dists[ids[i$1]]) { swap(ids, left, i$1); }
 
-            temp = ids[i];
+            var temp$1 = ids[i$1];
+            var tempDist$1 = dists[temp$1];
             while (true) {
-                do { i++; } while (compare(coords, ids[i], temp, cx, cy) < 0);
-                do { j--; } while (compare(coords, ids[j], temp, cx, cy) > 0);
-                if (j < i) { break; }
-                swap(ids, i, j);
+                do { i$1++; } while (dists[ids[i$1]] < tempDist$1);
+                do { j$1--; } while (dists[ids[j$1]] > tempDist$1);
+                if (j$1 < i$1) { break; }
+                swap(ids, i$1, j$1);
             }
-            ids[left + 1] = ids[j];
-            ids[j] = temp;
+            ids[left + 1] = ids[j$1];
+            ids[j$1] = temp$1;
 
-            if (right - i + 1 >= j - left) {
-                quicksort(ids, coords, i, right, cx, cy);
-                quicksort(ids, coords, left, j - 1, cx, cy);
+            if (right - i$1 + 1 >= j$1 - left) {
+                quicksort(ids, dists, i$1, right);
+                quicksort(ids, dists, left, j$1 - 1);
             } else {
-                quicksort(ids, coords, left, j - 1, cx, cy);
-                quicksort(ids, coords, i, right, cx, cy);
+                quicksort(ids, dists, left, j$1 - 1);
+                quicksort(ids, dists, i$1, right);
             }
@@ -457,8 +459,2 @@ }
 
-    function compare(coords, i, j, cx, cy) {
-        var d1 = dist(coords[2 * i], coords[2 * i + 1], cx, cy);
-        var d2 = dist(coords[2 * j], coords[2 * j + 1], cx, cy);
-        return (d1 - d2) || (coords[2 * i] - coords[2 * j]) || (coords[2 * i + 1] - coords[2 * j + 1]);
-    }
-
     function swap(arr, i, j) {
@@ -465,0 +461,0 @@ var tmp = arr[i];

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=1/0,l=1/0,o=-1/0,f=-1/0,u=i.length>>1,v=this.ids=new Uint32Array(u);if(u>0&&"number"!=typeof i[0])throw new Error("Expected coords to contain numbers.");this.coords=i;for(var _=0;_<u;_++){var d=i[2*_],g=i[2*_+1];d<n&&(n=d),g<l&&(l=g),d>o&&(o=d),g>f&&(f=g),v[_]=_}for(var y,c,w,p=(n+o)/2,b=(l+f)/2,x=1/0,z=0;z<u;z++){var S=r(p,b,i[2*z],i[2*z+1]);S<x&&(y=z,x=S)}var k=i[2*y],A=i[2*y+1];x=1/0;for(var T=0;T<u;T++)if(T!==y){var M=r(k,A,i[2*T],i[2*T+1]);M<x&&M>0&&(c=T,x=M)}for(var K=i[2*c],m=i[2*c+1],U=1/0,L=0;L<u;L++)if(L!==y&&L!==c){var N=a(k,A,K,m,i[2*L],i[2*L+1]);N<U&&(w=L,U=N)}var E=i[2*w],D=i[2*w+1];if(U===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(h(k,A,K,m,E,D)){var I=c,P=K,j=m;c=w,K=E,m=D,w=I,E=P,D=j}var q=function(t,i,r,h,a,s){var e=r-t,n=h-i,l=a-t,o=s-i,f=e*e+n*n,u=l*l+o*o,v=e*o-n*l;return{x:t+.5*(o*f-n*u)/v,y:i+.5*(e*u-l*f)/v}}(k,A,K,m,E,D);this._cx=q.x,this._cy=q.y,function t(i,r,h,a,n,l){var o,f,u;if(a-h<=20)for(o=h+1;o<=a;o++){for(u=i[o],f=o-1;f>=h&&s(r,i[f],u,n,l)>0;)i[f+1]=i[f--];i[f+1]=u}else{var v=h+a>>1;for(f=a,e(i,v,o=h+1),s(r,i[h],i[a],n,l)>0&&e(i,h,a),s(r,i[o],i[a],n,l)>0&&e(i,o,a),s(r,i[h],i[o],n,l)>0&&e(i,h,o),u=i[o];;){do{o++}while(s(r,i[o],u,n,l)<0);do{f--}while(s(r,i[f],u,n,l)>0);if(f<o)break;e(i,o,f)}i[h+1]=i[f],i[f]=u,a-o+1>=f-h?(t(i,r,o,a,n,l),t(i,r,h,f-1,n,l)):(t(i,r,h,f-1,n,l),t(i,r,o,a,n,l))}}(v,i,0,v.length-1,q.x,q.y),this._hashSize=Math.ceil(Math.sqrt(u)),this._hash=new Int32Array(this._hashSize).fill(-1);var F=this.hullPrev=new Uint32Array(u),B=this.hullNext=new Uint32Array(u),C=this.hullTri=new Uint32Array(u);this.hullStart=y;var G=3;B[y]=F[w]=c,B[c]=F[y]=w,B[w]=F[c]=y,C[y]=0,C[c]=1,C[w]=2,this._hash[this._hashKey(k,A)]=y,this._hash[this._hashKey(K,m)]=c,this._hash[this._hashKey(E,D)]=w;var H=2*u-5,J=this.triangles=new Uint32Array(3*H),O=this.halfedges=new Int32Array(3*H);this.trianglesLen=0,this._addTriangle(y,c,w,-1,-1,-1);for(var Q=0,R=void 0,V=void 0;Q<v.length;Q++){var W=v[Q],X=i[2*W],Y=i[2*W+1];if(!(Q>0&&Math.abs(X-R)<=t&&Math.abs(Y-V)<=t)&&(R=X,V=Y,W!==y&&W!==c&&W!==w)){for(var Z=0,$=0,tt=this._hashKey(X,Y);$<this._hashSize&&(-1===(Z=this._hash[(tt+$)%this._hashSize])||Z===B[Z]);$++);for(var it=Z=F[Z],rt=void 0;rt=B[it],!h(X,Y,i[2*it],i[2*it+1],i[2*rt],i[2*rt+1]);)if((it=rt)===Z){it=-1;break}if(-1!==it){var ht=this._addTriangle(it,W,B[it],-1,-1,C[it]);C[W]=this._legalize(ht+2),C[it]=ht,G++;for(var at=B[it];rt=B[at],h(X,Y,i[2*at],i[2*at+1],i[2*rt],i[2*rt+1]);)ht=this._addTriangle(at,W,rt,C[W],-1,C[at]),C[W]=this._legalize(ht+2),B[at]=at,G--,at=rt;if(it===Z)for(;h(X,Y,i[2*(rt=F[it])],i[2*rt+1],i[2*it],i[2*it+1]);)ht=this._addTriangle(rt,W,it,-1,C[it],C[rt]),this._legalize(ht+2),C[rt]=ht,B[it]=it,G--,it=rt;this.hullStart=F[W]=it,B[it]=F[at]=W,B[W]=at,this._hash[this._hashKey(X,Y)]=W,this._hash[this._hashKey(i[2*it],i[2*it+1])]=it}}}this.hull=new Uint32Array(G);for(var st=0,et=this.hullStart;st<G;st++)this.hull[st]=et,et=B[et];this.hullPrev=this.hullNext=this.hullTri=null,this.triangles=J.subarray(0,this.trianglesLen),this.halfedges=O.subarray(0,this.trianglesLen)};function r(t,i,r,h){var a=t-r,s=i-h;return a*a+s*s}function h(t,i,r,h,a,s){return(h-i)*(a-r)-(r-t)*(s-h)<0}function a(t,i,r,h,a,s){var e=r-t,n=h-i,l=a-t,o=s-i,f=e*e+n*n,u=l*l+o*o,v=e*o-n*l,_=.5*(o*f-n*u)/v,d=.5*(e*u-l*f)/v;return f&&u&&v&&_*_+d*d||1/0}function s(t,i,h,a,s){return r(t[2*i],t[2*i+1],a,s)-r(t[2*h],t[2*h+1],a,s)||t[2*i]-t[2*h]||t[2*i+1]-t[2*h+1]}function e(t,i,r){var h=t[i];t[i]=t[r],t[r]=h}function n(t){return t[0]}function l(t){return t[1]}return i.from=function(t,r,h){r||(r=n),h||(h=l);for(var a=t.length,s=new Float64Array(2*a),e=0;e<a;e++){var o=t[e];s[2*e]=r(o),s[2*e+1]=h(o)}return new i(s)},i.prototype._hashKey=function(t,i){return Math.floor((r=t-this._cx,h=i-this._cy,a=r/(Math.abs(r)+Math.abs(h)),(h>0?3-a:1+a)/4*this._hashSize))%this._hashSize;var r,h,a},i.prototype._legalize=function(t){var i=this.triangles,r=this.coords,h=this.halfedges,a=h[t],s=t-t%3,e=a-a%3,n=s+(t+1)%3,l=s+(t+2)%3,o=e+(a+2)%3;if(-1===a)return l;var f,u,v,_,d,g,y,c,w,p,b,x,z,S,k,A,T=i[l],M=i[t],K=i[n],m=i[o];if(f=r[2*T],u=r[2*T+1],v=r[2*M],_=r[2*M+1],d=r[2*K],g=r[2*K+1],y=r[2*m],c=r[2*m+1],(w=f-y)*((x=_-c)*(A=(z=d-y)*z+(S=g-c)*S)-(k=(b=v-y)*b+x*x)*S)-(p=u-c)*(b*A-k*z)+(w*w+p*p)*(b*S-x*z)<0){i[t]=m,i[a]=T;var U=h[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(a,h[l]),this._link(l,o);var N=e+(a+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,h,a,s){var e=this.trianglesLen;return this.triangles[e]=t,this.triangles[e+1]=i,this.triangles[e+2]=r,this._link(e,h),this._link(e+1,a),this._link(e+2,s),this.trianglesLen+=3,e},i});
+!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});

index.js

@@ -6,6 +6,3 @@
 
-    static from(points, getX, getY) {
-        if (!getX) getX = defaultGetX;
-        if (!getY) getY = defaultGetY;
-
+    static from(points, getX = defaultGetX, getY = defaultGetY) {
         const n = points.length;
@@ -24,2 +21,21 @@ const coords = new Float64Array(n * 2);
     constructor(coords) {
+        const n = coords.length >> 1;
+        if (n > 0 && typeof coords[0] !== 'number') throw new Error('Expected coords to contain numbers.');
+
+        this.coords = coords;
+
+        // 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);
+
+        // 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
+
+        // populate an array of point indices; calculate input data bbox
+        const ids = new Uint32Array(n);
         let minX = Infinity;
@@ -30,9 +46,2 @@ let minY = Infinity;
 
-        const n = coords.length >> 1;
-        const ids = this.ids = new Uint32Array(n);
-
-        if (n > 0 && typeof coords[0] !== 'number') throw new Error('Expected coords to contain numbers.');
-
-        this.coords = coords;
-
         for (let i = 0; i < n; i++) {
@@ -47,3 +56,2 @@ const x = coords[2 * i];
         }
-
         const cx = (minX + maxX) / 2;
@@ -55,3 +63,3 @@ const cy = (minY + maxY) / 2;
 
-        // pick a seed point close to the centroid
+        // pick a seed point close to the center
         for (let i = 0; i < n; i++) {
@@ -116,14 +124,10 @@ const d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);
 
+        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);
+        }
+
         // sort the points by distance from the seed triangle circumcenter
-        quicksort(ids, coords, 0, ids.length - 1, center.x, center.y);
+        quicksort(ids, dists, 0, n - 1);
 
-        // initialize a hash table for storing edges of the advancing convex hull
-        this._hashSize = Math.ceil(Math.sqrt(n));
-        this._hash = new Int32Array(this._hashSize).fill(-1);
-
-        // initialize arrays for tracking the edges of the advancing convex hull
-        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
-
         // set up the seed triangle as the starting hull
@@ -141,12 +145,7 @@ this.hullStart = i0;
 
-        this._hash[this._hashKey(i0x, i0y)] = i0;
-        this._hash[this._hashKey(i1x, i1y)] = i1;
-        this._hash[this._hashKey(i2x, i2y)] = i2;
+        hullHash[this._hashKey(i0x, i0y)] = i0;
+        hullHash[this._hashKey(i1x, i1y)] = i1;
+        hullHash[this._hashKey(i2x, i2y)] = i2;
 
-        const maxTriangles = 2 * n - 5;
-        const triangles = this.triangles = new Uint32Array(maxTriangles * 3);
-        const halfedges = this.halfedges = new Int32Array(maxTriangles * 3);
-
         this.trianglesLen = 0;
-
         this._addTriangle(i0, i1, i2, -1, -1, -1);
@@ -170,3 +169,3 @@
             for (let j = 0, key = this._hashKey(x, y); j < this._hashSize; j++) {
-                start = this._hash[(key + j) % this._hashSize];
+                start = hullHash[(key + j) % this._hashSize];
                 if (start !== -1 && start !== hullNext[start]) break;
@@ -222,4 +221,4 @@ }
             // save the two new edges in the hash table
-            this._hash[this._hashKey(x, y)] = i;
-            this._hash[this._hashKey(coords[2 * e], coords[2 * e + 1])] = e;
+            hullHash[this._hashKey(x, y)] = i;
+            hullHash[this._hashKey(coords[2 * e], coords[2 * e + 1])] = e;
         }
@@ -377,8 +376,8 @@
     const cl = ex * ex + ey * ey;
-    const d = dx * ey - dy * ex;
+    const d = 0.5 / (dx * ey - dy * ex);
 
-    const x = (ey * bl - dy * cl) * 0.5 / d;
-    const y = (dx * cl - ex * bl) * 0.5 / d;
+    const x = (ey * bl - dy * cl) * d;
+    const y = (dx * cl - ex * bl) * d;
 
-    return bl && cl && d && (x * x + y * y) || Infinity;
+    return x * x + y * y;
 }
@@ -394,6 +393,6 @@
     const cl = ex * ex + ey * ey;
-    const d = dx * ey - dy * ex;
+    const d = 0.5 / (dx * ey - dy * ex);
 
-    const x = ax + (ey * bl - dy * cl) * 0.5 / d;
-    const y = ay + (dx * cl - ex * bl) * 0.5 / d;
+    const x = ax + (ey * bl - dy * cl) * d;
+    const y = ay + (dx * cl - ex * bl) * d;
 
@@ -403,10 +402,9 @@ return {x, y};
 
-function quicksort(ids, coords, left, right, cx, cy) {
-    let i, j, temp;
-
+function quicksort(ids, dists, left, right) {
     if (right - left <= 20) {
-        for (i = left + 1; i <= right; i++) {
-            temp = ids[i];
-            j = i - 1;
-            while (j >= left && compare(coords, ids[j], temp, cx, cy) > 0) ids[j + 1] = ids[j--];
+        for (let i = left + 1; i <= right; i++) {
+            const temp = ids[i];
+            const tempDist = dists[temp];
+            let j = i - 1;
+            while (j >= left && dists[ids[j]] > tempDist) ids[j + 1] = ids[j--];
             ids[j + 1] = temp;
@@ -416,13 +414,14 @@ }
         const median = (left + right) >> 1;
-        i = left + 1;
-        j = right;
+        let i = left + 1;
+        let j = right;
         swap(ids, median, i);
-        if (compare(coords, ids[left], ids[right], cx, cy) > 0) swap(ids, left, right);
-        if (compare(coords, ids[i], ids[right], cx, cy) > 0) swap(ids, i, right);
-        if (compare(coords, ids[left], ids[i], cx, cy) > 0) swap(ids, left, i);
+        if (dists[ids[left]] > dists[ids[right]]) swap(ids, left, right);
+        if (dists[ids[i]] > dists[ids[right]]) swap(ids, i, right);
+        if (dists[ids[left]] > dists[ids[i]]) swap(ids, left, i);
 
-        temp = ids[i];
+        const temp = ids[i];
+        const tempDist = dists[temp];
         while (true) {
-            do i++; while (compare(coords, ids[i], temp, cx, cy) < 0);
-            do j--; while (compare(coords, ids[j], temp, cx, cy) > 0);
+            do i++; while (dists[ids[i]] < tempDist);
+            do j--; while (dists[ids[j]] > tempDist);
             if (j < i) break;
@@ -435,7 +434,7 @@ swap(ids, i, j);
         if (right - i + 1 >= j - left) {
-            quicksort(ids, coords, i, right, cx, cy);
-            quicksort(ids, coords, left, j - 1, cx, cy);
+            quicksort(ids, dists, i, right);
+            quicksort(ids, dists, left, j - 1);
         } else {
-            quicksort(ids, coords, left, j - 1, cx, cy);
-            quicksort(ids, coords, i, right, cx, cy);
+            quicksort(ids, dists, left, j - 1);
+            quicksort(ids, dists, i, right);
         }
@@ -445,8 +444,2 @@ }
 
-function compare(coords, i, j, cx, cy) {
-    const d1 = dist(coords[2 * i], coords[2 * i + 1], cx, cy);
-    const d2 = dist(coords[2 * j], coords[2 * j + 1], cx, cy);
-    return (d1 - d2) || (coords[2 * i] - coords[2 * j]) || (coords[2 * i + 1] - coords[2 * j + 1]);
-}
-
 function swap(arr, i, j) {
@@ -453,0 +446,0 @@ const tmp = arr[i];

package.json

 {
   "name": "delaunator",
-  "version": "3.0.1",
-  "description": "A really fast JavaScript library for Delaunay triangulation of 2D points",
+  "version": "3.0.2",
+  "description": "An incredibly fast JavaScript library for Delaunay triangulation of 2D points",
   "main": "delaunator.js",
@@ -11,8 +11,9 @@ "module": "index.js",
   "devDependencies": {
-    "eslint": "^5.5.0",
+    "c8": "^3.2.0",
+    "eslint": "^5.6.0",
     "eslint-config-mourner": "^3.0.0",
-    "esm": "^3.0.81",
-    "rollup": "^0.65.0",
+    "esm": "^3.0.84",
+    "rollup": "^0.66.2",
     "rollup-plugin-buble": "^0.19.2",
-    "rollup-plugin-terser": "^2.0.2",
+    "rollup-plugin-terser": "^3.0.0",
     "tape": "^4.9.1"
@@ -28,2 +29,3 @@ },
     "test": "node -r esm test.js",
+    "cov": "c8 node -r esm test.js && c8 report -r html",
     "bench": "node -r esm bench.js",
@@ -30,0 +32,0 @@ "build": "rollup -c",

README.md

@@ -1,4 +0,4 @@
-# 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)
+# 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)
 
-A really fast JavaScript library for
+An incredibly fast JavaScript library for
 [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) of 2D points.
@@ -13,4 +13,9 @@
 - [d3-geo-voronoi](https://github.com/Fil/d3-geo-voronoi) for Delaunay triangulations and Voronoi diagrams on a sphere (e.g. for geographic locations).
-- [fogleman/delaunay](https://github.com/fogleman/delaunay) is a port of Delaunator to Go.
 
+Ports to other languages:
+
+- [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)
+
 <img src="delaunator.png" alt="Delaunay triangulation example" width="600" />
@@ -57,8 +62,8 @@
 
-Constructs a delaunay triangulation object given a **typed array** of point coordinates of the form:
-`[x0, y0, x1, y1, ...]`.
+Constructs a delaunay triangulation object given an array of point coordinates of the form:
+`[x0, y0, x1, y1, ...]` (use a typed array for best performance).
 
 #### delaunay.triangles
 
-A flat `Int32Array` array of triangle vertex indices (each group of three numbers forms a triangle).
+A `Uint32Array` array of triangle vertex indices (each group of three numbers forms a triangle).
 All triangles are directed counterclockwise.
@@ -80,3 +85,3 @@
 
-A flat `Int32Array` array of triangle half-edge indices that allows you to traverse the triangulation.
+A `Int32Array` array of triangle half-edge indices that allows you to traverse the triangulation.
 `i`-th half-edge in the array corresponds to vertex `triangles[i]` the half-edge is coming from.
@@ -89,10 +94,19 @@ `halfedges[i]` is the index of a twin half-edge in an adjacent triangle
 
+#### delaunay.hull
+
+A `Uint32Array` array of indices that reference points on the convex hull of the input data, counter-clockwise.
+
+#### delaunay.coords
+
+An array of input coordinates in the form `[x0, y0, x1, y1, ....]`,
+of the type provided in the constructor (or `Float64Array` if you used `Delaunator.from`).
+
 ## Performance
 
 Benchmark results against other Delaunay JS libraries
-(`npm run bench` on Macbook Pro Retina 15" 2017, Node v10.9.0):
+(`npm run bench` on Macbook Pro Retina 15" 2017, Node v10.10.0):
 
 &nbsp; | uniform 100k | gauss 100k | grid 100k | degen 100k | uniform 1&nbsp;million | gauss 1&nbsp;million | grid 1&nbsp;million | degen 1&nbsp;million
 :-- | --: | --: | --: | --: | --: | --: | --: | --:
-**delaunator** | 97ms | 70ms | 81ms | 48ms | 1.28s | 1s | 988ms | 917ms
+**delaunator** | 95ms | 75ms | 68ms | 31ms | 1.15s | 1.11s | 979ms | 314ms
 [faster&#8209;delaunay](https://github.com/Bathlamos/delaunay-triangulation) | 473ms | 411ms | 272ms | 68ms | 4.27s | 4.62s | 4.3s | 810ms
@@ -99,0 +113,0 @@ [incremental&#8209;delaunay](https://github.com/mikolalysenko/incremental-delaunay) | 547ms | 505ms | 172ms | 528ms | 5.9s | 6.08s | 2.11s | 6.09s

No alert changes

Improved metrics

Total package byte prevSize

41641

increased by0.31%

Number of lines in readme file

123

increased by12.84%

Worsened metrics

Dev dependency count

8

increased by14.29%

Lines of code

755

decreased by-0.13%

No dependency changes