delaunator - npm Package Compare versions

Comparing version 5.0.0 to 5.0.1

delaunator.js

@@ -5,3 +5,3 @@ (function (global, factory) {
 (global = typeof globalThis !== 'undefined' ? globalThis : global || self, global.Delaunator = factory());
-}(this, (function () { 'use strict';
+})(this, (function () { 'use strict';
 
@@ -268,4 +268,2 @@ const epsilon = 1.1102230246251565e-16;
 
-    if (detleft === 0 || detright === 0 || (detleft > 0) !== (detright > 0)) return det;
-
     const detsum = Math.abs(detleft + detright);
@@ -311,3 +309,3 @@ if (Math.abs(det) >= ccwerrboundA * detsum) return det;
         this._hullTri = new Uint32Array(n); // edge to adjacent triangle
-        this._hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash
+        this._hullHash = new Int32Array(this._hashSize); // angular edge hash
 
@@ -343,7 +341,6 @@ // temporary arrays for sorting points
 
-        let minDist = Infinity;
         let i0, i1, i2;
 
         // pick a seed point close to the center
-        for (let i = 0; i < n; i++) {
+        for (let i = 0, minDist = Infinity; i < n; i++) {
             const d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);
@@ -358,6 +355,4 @@ if (d < minDist) {
 
-        minDist = Infinity;
-
         // find the point closest to the seed
-        for (let i = 0; i < n; i++) {
+        for (let i = 0, minDist = Infinity; i < n; i++) {
             if (i === i0) continue;
@@ -398,5 +393,6 @@ const d = dist(i0x, i0y, coords[2 * i], coords[2 * i + 1]);
                 const id = this._ids[i];
-                if (this._dists[id] > d0) {
+                const d = this._dists[id];
+                if (d > d0) {
                     hull[j++] = id;
-                    d0 = this._dists[id];
+                    d0 = d;
                 }
@@ -763,2 +759,2 @@ }
 
-})));
+}));

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="undefined"!=typeof globalThis?globalThis:t||self).Delaunator=i()}(this,(function(){"use strict";const t=134217729;function i(t,i,s,e,n){let h,r,l,o,a=i[0],f=e[0],c=0,u=0;f>a==f>-a?(h=a,a=i[++c]):(h=f,f=e[++u]);let _=0;if(c<t&&u<s)for(f>a==f>-a?(r=a+h,l=h-(r-a),a=i[++c]):(r=f+h,l=h-(r-f),f=e[++u]),h=r,0!==l&&(n[_++]=l);c<t&&u<s;)f>a==f>-a?(r=h+a,o=r-h,l=h-(r-o)+(a-o),a=i[++c]):(r=h+f,o=r-h,l=h-(r-o)+(f-o),f=e[++u]),h=r,0!==l&&(n[_++]=l);for(;c<t;)r=h+a,o=r-h,l=h-(r-o)+(a-o),a=i[++c],h=r,0!==l&&(n[_++]=l);for(;u<s;)r=h+f,o=r-h,l=h-(r-o)+(f-o),f=e[++u],h=r,0!==l&&(n[_++]=l);return 0===h&&0!==_||(n[_++]=h),_}function s(t){return new Float64Array(t)}const e=s(4),n=s(8),h=s(12),r=s(16),l=s(4);function o(s,o,a,f,c,u){const _=(o-u)*(a-c),d=(s-c)*(f-u),g=_-d;if(0===_||0===d||_>0!=d>0)return g;const y=Math.abs(_+d);return Math.abs(g)>=33306690738754716e-32*y?g:-function(s,o,a,f,c,u,_){let d,g,y,w,b,A,k,M,p,x,S,T,z,U,m,K,L,v;const F=s-c,P=a-c,E=o-u,H=f-u;U=F*H,A=t*F,k=A-(A-F),M=F-k,A=t*H,p=A-(A-H),x=H-p,m=M*x-(U-k*p-M*p-k*x),K=E*P,A=t*E,k=A-(A-E),M=E-k,A=t*P,p=A-(A-P),x=P-p,L=M*x-(K-k*p-M*p-k*x),S=m-L,b=m-S,e[0]=m-(S+b)+(b-L),T=U+S,b=T-U,z=U-(T-b)+(S-b),S=z-K,b=z-S,e[1]=z-(S+b)+(b-K),v=T+S,b=v-T,e[2]=T-(v-b)+(S-b),e[3]=v;let I=function(t,i){let s=i[0];for(let e=1;e<t;e++)s+=i[e];return s}(4,e),N=22204460492503146e-32*_;if(I>=N||-I>=N)return I;if(b=s-F,d=s-(F+b)+(b-c),b=a-P,y=a-(P+b)+(b-c),b=o-E,g=o-(E+b)+(b-u),b=f-H,w=f-(H+b)+(b-u),0===d&&0===g&&0===y&&0===w)return I;if(N=11093356479670487e-47*_+33306690738754706e-32*Math.abs(I),I+=F*w+H*d-(E*y+P*g),I>=N||-I>=N)return I;U=d*H,A=t*d,k=A-(A-d),M=d-k,A=t*H,p=A-(A-H),x=H-p,m=M*x-(U-k*p-M*p-k*x),K=g*P,A=t*g,k=A-(A-g),M=g-k,A=t*P,p=A-(A-P),x=P-p,L=M*x-(K-k*p-M*p-k*x),S=m-L,b=m-S,l[0]=m-(S+b)+(b-L),T=U+S,b=T-U,z=U-(T-b)+(S-b),S=z-K,b=z-S,l[1]=z-(S+b)+(b-K),v=T+S,b=v-T,l[2]=T-(v-b)+(S-b),l[3]=v;const j=i(4,e,4,l,n);U=F*w,A=t*F,k=A-(A-F),M=F-k,A=t*w,p=A-(A-w),x=w-p,m=M*x-(U-k*p-M*p-k*x),K=E*y,A=t*E,k=A-(A-E),M=E-k,A=t*y,p=A-(A-y),x=y-p,L=M*x-(K-k*p-M*p-k*x),S=m-L,b=m-S,l[0]=m-(S+b)+(b-L),T=U+S,b=T-U,z=U-(T-b)+(S-b),S=z-K,b=z-S,l[1]=z-(S+b)+(b-K),v=T+S,b=v-T,l[2]=T-(v-b)+(S-b),l[3]=v;const q=i(j,n,4,l,h);U=d*w,A=t*d,k=A-(A-d),M=d-k,A=t*w,p=A-(A-w),x=w-p,m=M*x-(U-k*p-M*p-k*x),K=g*y,A=t*g,k=A-(A-g),M=g-k,A=t*y,p=A-(A-y),x=y-p,L=M*x-(K-k*p-M*p-k*x),S=m-L,b=m-S,l[0]=m-(S+b)+(b-L),T=U+S,b=T-U,z=U-(T-b)+(S-b),S=z-K,b=z-S,l[1]=z-(S+b)+(b-K),v=T+S,b=v-T,l[2]=T-(v-b)+(S-b),l[3]=v;const D=i(q,h,4,l,r);return r[D-1]}(s,o,a,f,c,u,y)}const a=Math.pow(2,-52),f=new Uint32Array(512);class c{static from(t,i=w,s=b){const e=t.length,n=new Float64Array(2*e);for(let h=0;h<e;h++){const e=t[h];n[2*h]=i(e),n[2*h+1]=s(e)}return new c(n)}constructor(t){const i=t.length>>1;if(i>0&&"number"!=typeof t[0])throw new Error("Expected coords to contain numbers.");this.coords=t;const s=Math.max(2*i-5,0);this._triangles=new Uint32Array(3*s),this._halfedges=new Int32Array(3*s),this._hashSize=Math.ceil(Math.sqrt(i)),this._hullPrev=new Uint32Array(i),this._hullNext=new Uint32Array(i),this._hullTri=new Uint32Array(i),this._hullHash=new Int32Array(this._hashSize).fill(-1),this._ids=new Uint32Array(i),this._dists=new Float64Array(i),this.update()}update(){const{coords:t,_hullPrev:i,_hullNext:s,_hullTri:e,_hullHash:n}=this,h=t.length>>1;let r=1/0,l=1/0,f=-1/0,c=-1/0;for(let i=0;i<h;i++){const s=t[2*i],e=t[2*i+1];s<r&&(r=s),e<l&&(l=e),s>f&&(f=s),e>c&&(c=e),this._ids[i]=i}const _=(r+f)/2,y=(l+c)/2;let w,b,A,k=1/0;for(let i=0;i<h;i++){const s=u(_,y,t[2*i],t[2*i+1]);s<k&&(w=i,k=s)}const M=t[2*w],p=t[2*w+1];k=1/0;for(let i=0;i<h;i++){if(i===w)continue;const s=u(M,p,t[2*i],t[2*i+1]);s<k&&s>0&&(b=i,k=s)}let x=t[2*b],S=t[2*b+1],T=1/0;for(let i=0;i<h;i++){if(i===w||i===b)continue;const s=d(M,p,x,S,t[2*i],t[2*i+1]);s<T&&(A=i,T=s)}let z=t[2*A],U=t[2*A+1];if(T===1/0){for(let i=0;i<h;i++)this._dists[i]=t[2*i]-t[0]||t[2*i+1]-t[1];g(this._ids,this._dists,0,h-1);const i=new Uint32Array(h);let s=0;for(let t=0,e=-1/0;t<h;t++){const n=this._ids[t];this._dists[n]>e&&(i[s++]=n,e=this._dists[n])}return this.hull=i.subarray(0,s),this.triangles=new Uint32Array(0),void(this.halfedges=new Uint32Array(0))}if(o(M,p,x,S,z,U)<0){const t=b,i=x,s=S;b=A,x=z,S=U,A=t,z=i,U=s}const m=function(t,i,s,e,n,h){const r=s-t,l=e-i,o=n-t,a=h-i,f=r*r+l*l,c=o*o+a*a,u=.5/(r*a-l*o);return{x:t+(a*f-l*c)*u,y:i+(r*c-o*f)*u}}(M,p,x,S,z,U);this._cx=m.x,this._cy=m.y;for(let i=0;i<h;i++)this._dists[i]=u(t[2*i],t[2*i+1],m.x,m.y);g(this._ids,this._dists,0,h-1),this._hullStart=w;let K=3;s[w]=i[A]=b,s[b]=i[w]=A,s[A]=i[b]=w,e[w]=0,e[b]=1,e[A]=2,n.fill(-1),n[this._hashKey(M,p)]=w,n[this._hashKey(x,S)]=b,n[this._hashKey(z,U)]=A,this.trianglesLen=0,this._addTriangle(w,b,A,-1,-1,-1);for(let h,r,l=0;l<this._ids.length;l++){const f=this._ids[l],c=t[2*f],u=t[2*f+1];if(l>0&&Math.abs(c-h)<=a&&Math.abs(u-r)<=a)continue;if(h=c,r=u,f===w||f===b||f===A)continue;let _=0;for(let t=0,i=this._hashKey(c,u);t<this._hashSize&&(_=n[(i+t)%this._hashSize],-1===_||_===s[_]);t++);_=i[_];let d,g=_;for(;d=s[g],o(c,u,t[2*g],t[2*g+1],t[2*d],t[2*d+1])>=0;)if(g=d,g===_){g=-1;break}if(-1===g)continue;let y=this._addTriangle(g,f,s[g],-1,-1,e[g]);e[f]=this._legalize(y+2),e[g]=y,K++;let k=s[g];for(;d=s[k],o(c,u,t[2*k],t[2*k+1],t[2*d],t[2*d+1])<0;)y=this._addTriangle(k,f,d,e[f],-1,e[k]),e[f]=this._legalize(y+2),s[k]=k,K--,k=d;if(g===_)for(;d=i[g],o(c,u,t[2*d],t[2*d+1],t[2*g],t[2*g+1])<0;)y=this._addTriangle(d,f,g,-1,e[g],e[d]),this._legalize(y+2),e[d]=y,s[g]=g,K--,g=d;this._hullStart=i[f]=g,s[g]=i[k]=f,s[f]=k,n[this._hashKey(c,u)]=f,n[this._hashKey(t[2*g],t[2*g+1])]=g}this.hull=new Uint32Array(K);for(let t=0,i=this._hullStart;t<K;t++)this.hull[t]=i,i=s[i];this.triangles=this._triangles.subarray(0,this.trianglesLen),this.halfedges=this._halfedges.subarray(0,this.trianglesLen)}_hashKey(t,i){return Math.floor(function(t,i){const s=t/(Math.abs(t)+Math.abs(i));return(i>0?3-s:1+s)/4}(t-this._cx,i-this._cy)*this._hashSize)%this._hashSize}_legalize(t){const{_triangles:i,_halfedges:s,coords:e}=this;let n=0,h=0;for(;;){const r=s[t],l=t-t%3;if(h=l+(t+2)%3,-1===r){if(0===n)break;t=f[--n];continue}const o=r-r%3,a=l+(t+1)%3,c=o+(r+2)%3,u=i[h],d=i[t],g=i[a],y=i[c];if(_(e[2*u],e[2*u+1],e[2*d],e[2*d+1],e[2*g],e[2*g+1],e[2*y],e[2*y+1])){i[t]=y,i[r]=u;const e=s[c];if(-1===e){let i=this._hullStart;do{if(this._hullTri[i]===c){this._hullTri[i]=t;break}i=this._hullPrev[i]}while(i!==this._hullStart)}this._link(t,e),this._link(r,s[h]),this._link(h,c);const l=o+(r+1)%3;n<f.length&&(f[n++]=l)}else{if(0===n)break;t=f[--n]}}return h}_link(t,i){this._halfedges[t]=i,-1!==i&&(this._halfedges[i]=t)}_addTriangle(t,i,s,e,n,h){const r=this.trianglesLen;return this._triangles[r]=t,this._triangles[r+1]=i,this._triangles[r+2]=s,this._link(r,e),this._link(r+1,n),this._link(r+2,h),this.trianglesLen+=3,r}}function u(t,i,s,e){const n=t-s,h=i-e;return n*n+h*h}function _(t,i,s,e,n,h,r,l){const o=t-r,a=i-l,f=s-r,c=e-l,u=n-r,_=h-l,d=f*f+c*c,g=u*u+_*_;return o*(c*g-d*_)-a*(f*g-d*u)+(o*o+a*a)*(f*_-c*u)<0}function d(t,i,s,e,n,h){const r=s-t,l=e-i,o=n-t,a=h-i,f=r*r+l*l,c=o*o+a*a,u=.5/(r*a-l*o),_=(a*f-l*c)*u,d=(r*c-o*f)*u;return _*_+d*d}function g(t,i,s,e){if(e-s<=20)for(let n=s+1;n<=e;n++){const e=t[n],h=i[e];let r=n-1;for(;r>=s&&i[t[r]]>h;)t[r+1]=t[r--];t[r+1]=e}else{let n=s+1,h=e;y(t,s+e>>1,n),i[t[s]]>i[t[e]]&&y(t,s,e),i[t[n]]>i[t[e]]&&y(t,n,e),i[t[s]]>i[t[n]]&&y(t,s,n);const r=t[n],l=i[r];for(;;){do{n++}while(i[t[n]]<l);do{h--}while(i[t[h]]>l);if(h<n)break;y(t,n,h)}t[s+1]=t[h],t[h]=r,e-n+1>=h-s?(g(t,i,n,e),g(t,i,s,h-1)):(g(t,i,s,h-1),g(t,i,n,e))}}function y(t,i,s){const e=t[i];t[i]=t[s],t[s]=e}function w(t){return t[0]}function b(t){return t[1]}return c}));
+!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?module.exports=i():"function"==typeof define&&define.amd?define(i):(t="undefined"!=typeof globalThis?globalThis:t||self).Delaunator=i()}(this,(function(){"use strict";const t=11102230246251565e-32,i=134217729,s=(3+8*t)*t;function e(t,i,s,e,n){let h,r,l,o,a=i[0],f=e[0],c=0,u=0;f>a==f>-a?(h=a,a=i[++c]):(h=f,f=e[++u]);let _=0;if(c<t&&u<s)for(f>a==f>-a?(r=a+h,l=h-(r-a),a=i[++c]):(r=f+h,l=h-(r-f),f=e[++u]),h=r,0!==l&&(n[_++]=l);c<t&&u<s;)f>a==f>-a?(r=h+a,o=r-h,l=h-(r-o)+(a-o),a=i[++c]):(r=h+f,o=r-h,l=h-(r-o)+(f-o),f=e[++u]),h=r,0!==l&&(n[_++]=l);for(;c<t;)r=h+a,o=r-h,l=h-(r-o)+(a-o),a=i[++c],h=r,0!==l&&(n[_++]=l);for(;u<s;)r=h+f,o=r-h,l=h-(r-o)+(f-o),f=e[++u],h=r,0!==l&&(n[_++]=l);return 0===h&&0!==_||(n[_++]=h),_}function n(t){return new Float64Array(t)}const h=22204460492503146e-32,r=11093356479670487e-47,l=n(4),o=n(8),a=n(12),f=n(16),c=n(4);function u(t,n,u,_,d,g){const y=(n-g)*(u-d),w=(t-d)*(_-g),b=y-w,A=Math.abs(y+w);return Math.abs(b)>=33306690738754716e-32*A?b:-function(t,n,u,_,d,g,y){let w,b,A,k,M,p,x,S,T,z,U,m,K,L,v,F,P,E;const H=t-d,I=u-d,N=n-g,j=_-g;L=H*j,p=i*H,x=p-(p-H),S=H-x,p=i*j,T=p-(p-j),z=j-T,v=S*z-(L-x*T-S*T-x*z),F=N*I,p=i*N,x=p-(p-N),S=N-x,p=i*I,T=p-(p-I),z=I-T,P=S*z-(F-x*T-S*T-x*z),U=v-P,M=v-U,l[0]=v-(U+M)+(M-P),m=L+U,M=m-L,K=L-(m-M)+(U-M),U=K-F,M=K-U,l[1]=K-(U+M)+(M-F),E=m+U,M=E-m,l[2]=m-(E-M)+(U-M),l[3]=E;let q=function(t,i){let s=i[0];for(let e=1;e<t;e++)s+=i[e];return s}(4,l),D=h*y;if(q>=D||-q>=D)return q;if(M=t-H,w=t-(H+M)+(M-d),M=u-I,A=u-(I+M)+(M-d),M=n-N,b=n-(N+M)+(M-g),M=_-j,k=_-(j+M)+(M-g),0===w&&0===b&&0===A&&0===k)return q;if(D=r*y+s*Math.abs(q),q+=H*k+j*w-(N*A+I*b),q>=D||-q>=D)return q;L=w*j,p=i*w,x=p-(p-w),S=w-x,p=i*j,T=p-(p-j),z=j-T,v=S*z-(L-x*T-S*T-x*z),F=b*I,p=i*b,x=p-(p-b),S=b-x,p=i*I,T=p-(p-I),z=I-T,P=S*z-(F-x*T-S*T-x*z),U=v-P,M=v-U,c[0]=v-(U+M)+(M-P),m=L+U,M=m-L,K=L-(m-M)+(U-M),U=K-F,M=K-U,c[1]=K-(U+M)+(M-F),E=m+U,M=E-m,c[2]=m-(E-M)+(U-M),c[3]=E;const B=e(4,l,4,c,o);L=H*k,p=i*H,x=p-(p-H),S=H-x,p=i*k,T=p-(p-k),z=k-T,v=S*z-(L-x*T-S*T-x*z),F=N*A,p=i*N,x=p-(p-N),S=N-x,p=i*A,T=p-(p-A),z=A-T,P=S*z-(F-x*T-S*T-x*z),U=v-P,M=v-U,c[0]=v-(U+M)+(M-P),m=L+U,M=m-L,K=L-(m-M)+(U-M),U=K-F,M=K-U,c[1]=K-(U+M)+(M-F),E=m+U,M=E-m,c[2]=m-(E-M)+(U-M),c[3]=E;const C=e(B,o,4,c,a);L=w*k,p=i*w,x=p-(p-w),S=w-x,p=i*k,T=p-(p-k),z=k-T,v=S*z-(L-x*T-S*T-x*z),F=b*A,p=i*b,x=p-(p-b),S=b-x,p=i*A,T=p-(p-A),z=A-T,P=S*z-(F-x*T-S*T-x*z),U=v-P,M=v-U,c[0]=v-(U+M)+(M-P),m=L+U,M=m-L,K=L-(m-M)+(U-M),U=K-F,M=K-U,c[1]=K-(U+M)+(M-F),E=m+U,M=E-m,c[2]=m-(E-M)+(U-M),c[3]=E;const G=e(C,a,4,c,f);return f[G-1]}(t,n,u,_,d,g,A)}const _=Math.pow(2,-52),d=new Uint32Array(512);class g{static from(t,i=M,s=p){const e=t.length,n=new Float64Array(2*e);for(let h=0;h<e;h++){const e=t[h];n[2*h]=i(e),n[2*h+1]=s(e)}return new g(n)}constructor(t){const i=t.length>>1;if(i>0&&"number"!=typeof t[0])throw new Error("Expected coords to contain numbers.");this.coords=t;const s=Math.max(2*i-5,0);this._triangles=new Uint32Array(3*s),this._halfedges=new Int32Array(3*s),this._hashSize=Math.ceil(Math.sqrt(i)),this._hullPrev=new Uint32Array(i),this._hullNext=new Uint32Array(i),this._hullTri=new Uint32Array(i),this._hullHash=new Int32Array(this._hashSize),this._ids=new Uint32Array(i),this._dists=new Float64Array(i),this.update()}update(){const{coords:t,_hullPrev:i,_hullNext:s,_hullTri:e,_hullHash:n}=this,h=t.length>>1;let r=1/0,l=1/0,o=-1/0,a=-1/0;for(let i=0;i<h;i++){const s=t[2*i],e=t[2*i+1];s<r&&(r=s),e<l&&(l=e),s>o&&(o=s),e>a&&(a=e),this._ids[i]=i}const f=(r+o)/2,c=(l+a)/2;let d,g,w;for(let i=0,s=1/0;i<h;i++){const e=y(f,c,t[2*i],t[2*i+1]);e<s&&(d=i,s=e)}const k=t[2*d],M=t[2*d+1];for(let i=0,s=1/0;i<h;i++){if(i===d)continue;const e=y(k,M,t[2*i],t[2*i+1]);e<s&&e>0&&(g=i,s=e)}let p=t[2*g],x=t[2*g+1],S=1/0;for(let i=0;i<h;i++){if(i===d||i===g)continue;const s=b(k,M,p,x,t[2*i],t[2*i+1]);s<S&&(w=i,S=s)}let T=t[2*w],z=t[2*w+1];if(S===1/0){for(let i=0;i<h;i++)this._dists[i]=t[2*i]-t[0]||t[2*i+1]-t[1];A(this._ids,this._dists,0,h-1);const i=new Uint32Array(h);let s=0;for(let t=0,e=-1/0;t<h;t++){const n=this._ids[t],h=this._dists[n];h>e&&(i[s++]=n,e=h)}return this.hull=i.subarray(0,s),this.triangles=new Uint32Array(0),void(this.halfedges=new Uint32Array(0))}if(u(k,M,p,x,T,z)<0){const t=g,i=p,s=x;g=w,p=T,x=z,w=t,T=i,z=s}const U=function(t,i,s,e,n,h){const r=s-t,l=e-i,o=n-t,a=h-i,f=r*r+l*l,c=o*o+a*a,u=.5/(r*a-l*o);return{x:t+(a*f-l*c)*u,y:i+(r*c-o*f)*u}}(k,M,p,x,T,z);this._cx=U.x,this._cy=U.y;for(let i=0;i<h;i++)this._dists[i]=y(t[2*i],t[2*i+1],U.x,U.y);A(this._ids,this._dists,0,h-1),this._hullStart=d;let m=3;s[d]=i[w]=g,s[g]=i[d]=w,s[w]=i[g]=d,e[d]=0,e[g]=1,e[w]=2,n.fill(-1),n[this._hashKey(k,M)]=d,n[this._hashKey(p,x)]=g,n[this._hashKey(T,z)]=w,this.trianglesLen=0,this._addTriangle(d,g,w,-1,-1,-1);for(let h,r,l=0;l<this._ids.length;l++){const o=this._ids[l],a=t[2*o],f=t[2*o+1];if(l>0&&Math.abs(a-h)<=_&&Math.abs(f-r)<=_)continue;if(h=a,r=f,o===d||o===g||o===w)continue;let c=0;for(let t=0,i=this._hashKey(a,f);t<this._hashSize&&(c=n[(i+t)%this._hashSize],-1===c||c===s[c]);t++);c=i[c];let y,b=c;for(;y=s[b],u(a,f,t[2*b],t[2*b+1],t[2*y],t[2*y+1])>=0;)if(b=y,b===c){b=-1;break}if(-1===b)continue;let A=this._addTriangle(b,o,s[b],-1,-1,e[b]);e[o]=this._legalize(A+2),e[b]=A,m++;let k=s[b];for(;y=s[k],u(a,f,t[2*k],t[2*k+1],t[2*y],t[2*y+1])<0;)A=this._addTriangle(k,o,y,e[o],-1,e[k]),e[o]=this._legalize(A+2),s[k]=k,m--,k=y;if(b===c)for(;y=i[b],u(a,f,t[2*y],t[2*y+1],t[2*b],t[2*b+1])<0;)A=this._addTriangle(y,o,b,-1,e[b],e[y]),this._legalize(A+2),e[y]=A,s[b]=b,m--,b=y;this._hullStart=i[o]=b,s[b]=i[k]=o,s[o]=k,n[this._hashKey(a,f)]=o,n[this._hashKey(t[2*b],t[2*b+1])]=b}this.hull=new Uint32Array(m);for(let t=0,i=this._hullStart;t<m;t++)this.hull[t]=i,i=s[i];this.triangles=this._triangles.subarray(0,this.trianglesLen),this.halfedges=this._halfedges.subarray(0,this.trianglesLen)}_hashKey(t,i){return Math.floor(function(t,i){const s=t/(Math.abs(t)+Math.abs(i));return(i>0?3-s:1+s)/4}(t-this._cx,i-this._cy)*this._hashSize)%this._hashSize}_legalize(t){const{_triangles:i,_halfedges:s,coords:e}=this;let n=0,h=0;for(;;){const r=s[t],l=t-t%3;if(h=l+(t+2)%3,-1===r){if(0===n)break;t=d[--n];continue}const o=r-r%3,a=l+(t+1)%3,f=o+(r+2)%3,c=i[h],u=i[t],_=i[a],g=i[f];if(w(e[2*c],e[2*c+1],e[2*u],e[2*u+1],e[2*_],e[2*_+1],e[2*g],e[2*g+1])){i[t]=g,i[r]=c;const e=s[f];if(-1===e){let i=this._hullStart;do{if(this._hullTri[i]===f){this._hullTri[i]=t;break}i=this._hullPrev[i]}while(i!==this._hullStart)}this._link(t,e),this._link(r,s[h]),this._link(h,f);const l=o+(r+1)%3;n<d.length&&(d[n++]=l)}else{if(0===n)break;t=d[--n]}}return h}_link(t,i){this._halfedges[t]=i,-1!==i&&(this._halfedges[i]=t)}_addTriangle(t,i,s,e,n,h){const r=this.trianglesLen;return this._triangles[r]=t,this._triangles[r+1]=i,this._triangles[r+2]=s,this._link(r,e),this._link(r+1,n),this._link(r+2,h),this.trianglesLen+=3,r}}function y(t,i,s,e){const n=t-s,h=i-e;return n*n+h*h}function w(t,i,s,e,n,h,r,l){const o=t-r,a=i-l,f=s-r,c=e-l,u=n-r,_=h-l,d=f*f+c*c,g=u*u+_*_;return o*(c*g-d*_)-a*(f*g-d*u)+(o*o+a*a)*(f*_-c*u)<0}function b(t,i,s,e,n,h){const r=s-t,l=e-i,o=n-t,a=h-i,f=r*r+l*l,c=o*o+a*a,u=.5/(r*a-l*o),_=(a*f-l*c)*u,d=(r*c-o*f)*u;return _*_+d*d}function A(t,i,s,e){if(e-s<=20)for(let n=s+1;n<=e;n++){const e=t[n],h=i[e];let r=n-1;for(;r>=s&&i[t[r]]>h;)t[r+1]=t[r--];t[r+1]=e}else{let n=s+1,h=e;k(t,s+e>>1,n),i[t[s]]>i[t[e]]&&k(t,s,e),i[t[n]]>i[t[e]]&&k(t,n,e),i[t[s]]>i[t[n]]&&k(t,s,n);const r=t[n],l=i[r];for(;;){do{n++}while(i[t[n]]<l);do{h--}while(i[t[h]]>l);if(h<n)break;k(t,n,h)}t[s+1]=t[h],t[h]=r,e-n+1>=h-s?(A(t,i,n,e),A(t,i,s,h-1)):(A(t,i,s,h-1),A(t,i,n,e))}}function k(t,i,s){const e=t[i];t[i]=t[s],t[s]=e}function M(t){return t[0]}function p(t){return t[1]}return g}));

index.js

@@ -38,3 +38,3 @@
         this._hullTri = new Uint32Array(n); // edge to adjacent triangle
-        this._hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash
+        this._hullHash = new Int32Array(this._hashSize); // angular edge hash
 
@@ -70,7 +70,6 @@ // temporary arrays for sorting points
 
-        let minDist = Infinity;
         let i0, i1, i2;
 
         // pick a seed point close to the center
-        for (let i = 0; i < n; i++) {
+        for (let i = 0, minDist = Infinity; i < n; i++) {
             const d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);
@@ -85,6 +84,4 @@ if (d < minDist) {
 
-        minDist = Infinity;
-
         // find the point closest to the seed
-        for (let i = 0; i < n; i++) {
+        for (let i = 0, minDist = Infinity; i < n; i++) {
             if (i === i0) continue;
@@ -125,5 +122,6 @@ const d = dist(i0x, i0y, coords[2 * i], coords[2 * i + 1]);
                 const id = this._ids[i];
-                if (this._dists[id] > d0) {
+                const d = this._dists[id];
+                if (d > d0) {
                     hull[j++] = id;
-                    d0 = this._dists[id];
+                    d0 = d;
                 }
@@ -130,0 +128,0 @@ }

package.json

 {
   "name": "delaunator",
-  "version": "5.0.0",
+  "version": "5.0.1",
   "description": "An incredibly fast JavaScript library for Delaunay triangulation of 2D points",
@@ -12,12 +12,10 @@ "main": "index.js",
   "dependencies": {
-    "robust-predicates": "^3.0.0"
+    "robust-predicates": "^3.0.2"
   },
   "devDependencies": {
-    "@rollup/plugin-node-resolve": "^11.2.0",
-    "c8": "^7.6.0",
-    "eslint": "^7.22.0",
+    "@rollup/plugin-node-resolve": "^15.2.3",
+    "@rollup/plugin-terser": "^0.4.4",
+    "eslint": "^8.56.0",
     "eslint-config-mourner": "^3.0.0",
-    "rollup": "^2.42.4",
-    "rollup-plugin-terser": "^7.0.2",
-    "tape": "^5.2.2"
+    "rollup": "^4.9.6"
   },
@@ -31,4 +29,4 @@ "repository": {
     "pretest": "npm run lint",
-    "test": "node test/test.js",
-    "cov": "c8 node test/test.js && c8 report -r html",
+    "test": "node --test-reporter spec test/test.js",
+    "cov": "node --experimental-test-coverage test/test.js",
     "bench": "node bench.js",
@@ -35,0 +33,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) [![](https://badgen.net/bundlephobia/minzip/delaunator)](https://unpkg.com/delaunator)
+# Delaunator [![Build Status](https://app.travis-ci.com/mapbox/delaunator.svg?branch=main)](https://app.travis-ci.com/mapbox/delaunator) [![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects) [![](https://badgen.net/bundlephobia/minzip/delaunator)](https://unpkg.com/delaunator)
 
-An incredibly fast JavaScript library for
+An incredibly fast and robust JavaScript library for
 [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) of 2D points.
@@ -16,19 +16,8 @@
 
-### Ports to other languages
-
-- [delaunator-rs](https://github.com/mourner/delaunator-rs) (Rust)
-- [fogleman/delaunay](https://github.com/fogleman/delaunay) (Go)
-- [delaunator-cpp](https://github.com/abellgithub/delaunator-cpp) (C++)
-- [delaunator-sharp](https://github.com/nol1fe/delaunator-sharp) (C#)
-- [delaunator-ruby](https://github.com/hendrixfan/delaunator-ruby) (Ruby)
-- [Delaunator-Python](https://github.com/HakanSeven12/Delaunator-Python) (Python)
-- [hx-delaunator](https://github.com/dmitryhryppa/hx-delaunator) (Haxe)
-- [ricardomatias/delaunator](https://github.com/ricardomatias/delaunator) (Kotlin)
-
 ## Example
 
 ```js
-const points = [[168, 180], [168, 178], [168, 179], [168, 181], [168, 183], ...];
+const coords = [168,180, 168,178, 168,179, 168,181, 168,183, ...];
 
-const delaunay = Delaunator.from(points);
+const delaunay = new Delaunator(coords);
 console.log(delaunay.triangles);
@@ -40,17 +29,20 @@ // [623, 636, 619,  636, 444, 619, ...]
 
-Install with NPM (`npm install delaunator`) or Yarn (`yarn add delaunator`), then:
+Install with NPM (`npm install delaunator`) or Yarn (`yarn add delaunator`), then import as an ES module:
 
 ```js
-// import as an ES module
 import Delaunator from 'delaunator';
+```
 
-// or require in Node / Browserify
-const Delaunator = require('delaunator');
+To use as a module in a browser:
+
+```html
+<script type="module">
+    import Delaunator from 'https://cdn.skypack.dev/delaunator@5.0.0';
+</script>
 ```
 
-Or use a browser build directly:
+Or use a browser UMD build that exposes a `Delaunator` global variable:
 
 ```html
-<script src="https://unpkg.com/delaunator@4.0.1/delaunator.min.js"></script> <!-- minified build -->
-<script src="https://unpkg.com/delaunator@4.0.1/delaunator.js"></script> <!-- dev build -->
+<script src="https://unpkg.com/delaunator@5.0.0/delaunator.min.js"></script>
 ```
@@ -60,2 +52,7 @@
 
+#### new Delaunator(coords)
+
+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).
+
 #### Delaunator.from(points[, getX, getY])
@@ -67,7 +64,2 @@
 
-#### new Delaunator(coords)
-
-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
@@ -137,1 +129,18 @@
 - [A faster circle-sweep Delaunay triangulation algorithm](http://cglab.ca/~biniaz/papers/Sweep%20Circle.pdf), 2011, Ahmad Biniaz and Gholamhossein Dastghaibyfard
+
+## Robustness
+
+Delaunator should produce valid output even on highly degenerate input. It does so by depending on [robust-predicates](https://github.com/mourner/robust-predicates), a modern port of Jonathan Shewchuk's robust geometric predicates, an industry standard in computational geometry.
+
+## Ports to other languages
+
+- [delaunator-rs](https://github.com/mourner/delaunator-rs) (Rust)
+- [fogleman/delaunay](https://github.com/fogleman/delaunay) (Go)
+- [delaunator-cpp](https://github.com/abellgithub/delaunator-cpp) (C++)
+- [delaunator-sharp](https://github.com/nol1fe/delaunator-sharp) (C#)
+- [delaunator-ruby](https://github.com/hendrixfan/delaunator-ruby) (Ruby)
+- [Delaunator-Python](https://github.com/HakanSeven12/Delaunator-Python) (Python)
+- [ricardomatias/delaunator](https://github.com/ricardomatias/delaunator) (Kotlin)
+- [delaunator-java](https://github.com/waveware4ai/delaunator-java) (Java)
+- [delaunay-Stata](https://github.com/asjadnaqvi/stata-delaunay-voronoi) (Stata/Mata)
+- [Delaunator.jl](https://github.com/JuliaGeometry/Delaunator.jl) (Julia)

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

55274

increased by0.51%

Dev dependency count

5

decreased by-28.57%

Number of lines in readme file

142

increased by6.77%

Worsened metrics

Lines of code

1078

decreased by-0.28%

Dependency changes

• Updatedrobust-predicates@^3.0.2