https://kayaguides.com/_npm/delaunator%405.1.0/7b06abe7.js

1/**
2 * Bundled by jsDelivr using Rollup v4.62.2 and esbuild v0.28.1.
3 * Original file: /npm/[email protected]/index.js
4 *
5 * Do NOT use SRI with dynamically generated files! More information: https://www.jsdelivr.com/using-sri-with-dynamic-files
6 */
7import{orient2d as j}from"../[email protected]/b42f30a7.js";const C=Math.pow(2,-52),q=new Uint32Array(512);class Y{static from(t,i=Q,h=V){const r=t.length,l=new Float64Array(r*2);for(let n=0;n<r;n++){const o=t[n];l[2*n]=i(o),l[2*n+1]=h(o)}return new Y(l)}constructor(t){const i=t.length>>1;if(i>0&&typeof t[0]!="number")throw new Error("Expected coords to contain numbers.");this.coords=t;const h=Math.max(2*i-5,0);this._triangles=new Uint32Array(h*3),this._halfedges=new Int32Array(h*3),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.trianglesLen=0,this._cx=0,this._cy=0,this._hullStart=0,this.hull=this._triangles,this.triangles=this._triangles,this.halfedges=this._halfedges,this.update()}update(){const{coords:t,_hullPrev:i,_hullNext:h,_hullTri:r,_hullHash:l}=this,n=t.length>>1;let o=1/0,f=1/0,g=-1/0,m=-1/0;for(let e=0;e<n;e++){const u=t[2*e],a=t[2*e+1];u<o&&(o=u),a<f&&(f=a),u>g&&(g=u),a>m&&(m=a),this._ids[e]=e}const d=(o+g)/2,b=(f+m)/2;let c=0,y=0,w=0;for(let e=0,u=1/0;e<n;e++){const a=X(d,b,t[2*e],t[2*e+1]);a<u&&(c=e,u=a)}const T=t[2*c],M=t[2*c+1];for(let e=0,u=1/0;e<n;e++){if(e===c)continue;const a=X(T,M,t[2*e],t[2*e+1]);a<u&&a>0&&(y=e,u=a)}let U=t[2*y],k=t[2*y+1],G=1/0;for(let e=0;e<n;e++){if(e===c||e===y)continue;const u=B(T,M,U,k,t[2*e],t[2*e+1]);u<G&&(w=e,G=u)}let D=t[2*w],E=t[2*w+1];if(G===1/0){for(let a=0;a<n;a++)this._dists[a]=t[2*a]-t[0]||t[2*a+1]-t[1];L(this._ids,this._dists,0,n-1);const e=new Uint32Array(n);let u=0;for(let a=0,x=-1/0;a<n;a++){const A=this._ids[a],S=this._dists[A];S>x&&(e[u++]=A,x=S)}this.hull=e.subarray(0,u),this.triangles=new Uint32Array(0),this.halfedges=new Int32Array(0);return}if(j(T,M,U,k,D,E)<0){const e=y,u=U,a=k;y=w,U=D,k=E,w=e,D=u,E=a}const N=J(T,M,U,k,D,E);this._cx=N.x,this._cy=N.y;for(let e=0;e<n;e++)this._dists[e]=X(t[2*e],t[2*e+1],N.x,N.y);L(this._ids,this._dists,0,n-1),this._hullStart=c;let P=3;h[c]=i[w]=y,h[y]=i[c]=w,h[w]=i[y]=c,r[c]=0,r[y]=1,r[w]=2,l.fill(-1),l[this._hashKey(T,M)]=c,l[this._hashKey(U,k)]=y,l[this._hashKey(D,E)]=w,this.trianglesLen=0,this._addTriangle(c,y,w,-1,-1,-1);for(let e=0,u=0,a=0;e<this._ids.length;e++){const x=this._ids[e],A=t[2*x],S=t[2*x+1];if(e>0&&Math.abs(A-u)<=C&&Math.abs(S-a)<=C||(u=A,a=S,x===c||x===y||x===w))continue;let z=0;for(let H=0,F=this._hashKey(A,S);H<this._hashSize&&(z=l[(F+H)%this._hashSize],!(z!==-1&&z!==h[z]));H++);z=i[z];let _=z,p;for(;p=h[_],j(A,S,t[2*_],t[2*_+1],t[2*p],t[2*p+1])>=0;)if(_=p,_===z){_=-1;break}if(_===-1)continue;let K=this._addTriangle(_,x,h[_],-1,-1,r[_]);r[x]=this._legalize(K+2),r[_]=K,P++;let I=h[_];for(;p=h[I],j(A,S,t[2*I],t[2*I+1],t[2*p],t[2*p+1])<0;)K=this._addTriangle(I,x,p,r[x],-1,r[I]),r[x]=this._legalize(K+2),h[I]=I,P--,I=p;if(_===z)for(;p=i[_],j(A,S,t[2*p],t[2*p+1],t[2*_],t[2*_+1])<0;)K=this._addTriangle(p,x,_,-1,r[_],r[p]),this._legalize(K+2),r[p]=K,h[_]=_,P--,_=p;this._hullStart=i[x]=_,h[_]=i[I]=x,h[x]=I,l[this._hashKey(A,S)]=x,l[this._hashKey(t[2*_],t[2*_+1])]=_}this.hull=new Uint32Array(P);for(let e=0,u=this._hullStart;e<P;e++)this.hull[e]=u,u=h[u];this.triangles=this._triangles.subarray(0,this.trianglesLen),this.halfedges=this._halfedges.subarray(0,this.trianglesLen)}_hashKey(t,i){return Math.floor(O(t-this._cx,i-this._cy)*this._hashSize)%this._hashSize}_legalize(t){const{_triangles:i,_halfedges:h,coords:r}=this;let l=0,n=0;for(;;){const o=h[t],f=t-t%3;if(n=f+(t+2)%3,o===-1){if(l===0)break;t=q[--l];continue}const g=o-o%3,m=f+(t+1)%3,d=g+(o+2)%3,b=i[n],c=i[t],y=i[m],w=i[d];if(R(r[2*b],r[2*b+1],r[2*c],r[2*c+1],r[2*y],r[2*y+1],r[2*w],r[2*w+1])){i[t]=w,i[o]=b;const M=h[d];if(M===-1){let k=this._hullStart;do{if(this._hullTri[k]===d){this._hullTri[k]=t;break}k=this._hullPrev[k]}while(k!==this._hullStart)}this._link(t,M),this._link(o,h[n]),this._link(n,d);const U=g+(o+1)%3;l<q.length&&(q[l++]=U)}else{if(l===0)break;t=q[--l]}}return n}_link(t,i){this._halfedges[t]=i,i!==-1&&(this._halfedges[i]=t)}_addTriangle(t,i,h,r,l,n){const o=this.trianglesLen;return this._triangles[o]=t,this._triangles[o+1]=i,this._triangles[o+2]=h,this._link(o,r),this._link(o+1,l),this._link(o+2,n),this.trianglesLen+=3,o}}function O(s,t){const i=s/(Math.abs(s)+Math.abs(t));return(t>0?3-i:1+i)/4}function X(s,t,i,h){const r=s-i,l=t-h;return r*r+l*l}function R(s,t,i,h,r,l,n,o){const f=s-n,g=t-o,m=i-n,d=h-o,b=r-n,c=l-o,y=f*f+g*g,w=m*m+d*d,T=b*b+c*c;return f*(d*T-w*c)-g*(m*T-w*b)+y*(m*c-d*b)<0}function B(s,t,i,h,r,l){const n=i-s,o=h-t,f=r-s,g=l-t,m=n*n+o*o,d=f*f+g*g,b=.5/(n*g-o*f),c=(g*m-o*d)*b,y=(n*d-f*m)*b;return c*c+y*y}function J(s,t,i,h,r,l){const n=i-s,o=h-t,f=r-s,g=l-t,m=n*n+o*o,d=f*f+g*g,b=.5/(n*g-o*f),c=s+(g*m-o*d)*b,y=t+(n*d-f*m)*b;return{x:c,y}}function L(s,t,i,h){if(h-i<=20)for(let r=i+1;r<=h;r++){const l=s[r],n=t[l];let o=r-1;for(;o>=i&&t[s[o]]>n;)s[o+1]=s[o--];s[o+1]=l}else{const r=i+h>>1;let l=i+1,n=h;v(s,r,l),t[s[i]]>t[s[h]]&&v(s,i,h),t[s[l]]>t[s[h]]&&v(s,l,h),t[s[i]]>t[s[l]]&&v(s,i,l);const o=s[l],f=t[o];for(;;){do l++;while(t[s[l]]<f);do n--;while(t[s[n]]>f);if(n<l)break;v(s,l,n)}s[i+1]=s[n],s[n]=o,h-l+1>=n-i?(L(s,t,l,h),L(s,t,i,n-1)):(L(s,t,i,n-1),L(s,t,l,h))}}function v(s,t,i){const h=s[t];s[t]=s[i],s[i]=h}function Q(s){return s[0]}function V(s){return s[1]}export{Y as default};