https://wingu.se/_npm/[email protected]/d4ec0aa1.js

1/**
2 * Bundled by jsDelivr using Rollup v2.79.2 and Terser v5.39.0.
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 t}from"../[email protected]/42820bfa.js";const s=Math.pow(2,-52),i=new Uint32Array(512);class h{static from(t,s=o,i=_){const e=t.length,n=new Float64Array(2*e);for(let h=0;h<e;h++){const e=t[h];n[2*h]=s(e),n[2*h+1]=i(e)}return new h(n)}constructor(t){const s=t.length>>1;if(s>0&&"number"!=typeof t[0])throw new Error("Expected coords to contain numbers.");this.coords=t;const i=Math.max(2*s-5,0);this._triangles=new Uint32Array(3*i),this._halfedges=new Int32Array(3*i),this._hashSize=Math.ceil(Math.sqrt(s)),this._hullPrev=new Uint32Array(s),this._hullNext=new Uint32Array(s),this._hullTri=new Uint32Array(s),this._hullHash=new Int32Array(this._hashSize),this._ids=new Uint32Array(s),this._dists=new Float64Array(s),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:i,_hullPrev:h,_hullNext:n,_hullTri:a,_hullHash:o}=this,_=i.length>>1;let c=1/0,f=1/0,u=-1/0,d=-1/0;for(let t=0;t<_;t++){const s=i[2*t],h=i[2*t+1];s<c&&(c=s),h<f&&(f=h),s>u&&(u=s),h>d&&(d=h),this._ids[t]=t}const g=(c+u)/2,y=(f+d)/2;let w=0,b=0,A=0;for(let t=0,s=1/0;t<_;t++){const h=e(g,y,i[2*t],i[2*t+1]);h<s&&(w=t,s=h)}const k=i[2*w],S=i[2*w+1];for(let t=0,s=1/0;t<_;t++){if(t===w)continue;const h=e(k,S,i[2*t],i[2*t+1]);h<s&&h>0&&(b=t,s=h)}let x=i[2*b],z=i[2*b+1],p=1/0;for(let t=0;t<_;t++){if(t===w||t===b)continue;const s=r(k,S,x,z,i[2*t],i[2*t+1]);s<p&&(A=t,p=s)}let M=i[2*A],T=i[2*A+1];if(p===1/0){for(let t=0;t<_;t++)this._dists[t]=i[2*t]-i[0]||i[2*t+1]-i[1];l(this._ids,this._dists,0,_-1);const t=new Uint32Array(_);let s=0;for(let i=0,h=-1/0;i<_;i++){const e=this._ids[i],n=this._dists[e];n>h&&(t[s++]=e,h=n)}return this.hull=t.subarray(0,s),this.triangles=new Uint32Array(0),void(this.halfedges=new Int32Array(0))}if(t(k,S,x,z,M,T)<0){const t=b,s=x,i=z;b=A,x=M,z=T,A=t,M=s,T=i}const U=function(t,s,i,h,e,n){const r=i-t,l=h-s,a=e-t,o=n-s,_=r*r+l*l,c=a*a+o*o,f=.5/(r*o-l*a);return{x:t+(o*_-l*c)*f,y:s+(r*c-a*_)*f}}(k,S,x,z,M,T);this._cx=U.x,this._cy=U.y;for(let t=0;t<_;t++)this._dists[t]=e(i[2*t],i[2*t+1],U.x,U.y);l(this._ids,this._dists,0,_-1),this._hullStart=w;let m=3;n[w]=h[A]=b,n[b]=h[w]=A,n[A]=h[b]=w,a[w]=0,a[b]=1,a[A]=2,o.fill(-1),o[this._hashKey(k,S)]=w,o[this._hashKey(x,z)]=b,o[this._hashKey(M,T)]=A,this.trianglesLen=0,this._addTriangle(w,b,A,-1,-1,-1);for(let e=0,r=0,l=0;e<this._ids.length;e++){const _=this._ids[e],c=i[2*_],f=i[2*_+1];if(e>0&&Math.abs(c-r)<=s&&Math.abs(f-l)<=s)continue;if(r=c,l=f,_===w||_===b||_===A)continue;let u=0;for(let t=0,s=this._hashKey(c,f);t<this._hashSize&&(u=o[(s+t)%this._hashSize],-1===u||u===n[u]);t++);u=h[u];let d,g=u;for(;d=n[g],t(c,f,i[2*g],i[2*g+1],i[2*d],i[2*d+1])>=0;)if(g=d,g===u){g=-1;break}if(-1===g)continue;let y=this._addTriangle(g,_,n[g],-1,-1,a[g]);a[_]=this._legalize(y+2),a[g]=y,m++;let k=n[g];for(;d=n[k],t(c,f,i[2*k],i[2*k+1],i[2*d],i[2*d+1])<0;)y=this._addTriangle(k,_,d,a[_],-1,a[k]),a[_]=this._legalize(y+2),n[k]=k,m--,k=d;if(g===u)for(;d=h[g],t(c,f,i[2*d],i[2*d+1],i[2*g],i[2*g+1])<0;)y=this._addTriangle(d,_,g,-1,a[g],a[d]),this._legalize(y+2),a[d]=y,n[g]=g,m--,g=d;this._hullStart=h[_]=g,n[g]=h[k]=_,n[_]=k,o[this._hashKey(c,f)]=_,o[this._hashKey(i[2*g],i[2*g+1])]=g}this.hull=new Uint32Array(m);for(let t=0,s=this._hullStart;t<m;t++)this.hull[t]=s,s=n[s];this.triangles=this._triangles.subarray(0,this.trianglesLen),this.halfedges=this._halfedges.subarray(0,this.trianglesLen)}_hashKey(t,s){return Math.floor(function(t,s){const i=t/(Math.abs(t)+Math.abs(s));return(s>0?3-i:1+i)/4}(t-this._cx,s-this._cy)*this._hashSize)%this._hashSize}_legalize(t){const{_triangles:s,_halfedges:h,coords:e}=this;let r=0,l=0;for(;;){const a=h[t],o=t-t%3;if(l=o+(t+2)%3,-1===a){if(0===r)break;t=i[--r];continue}const _=a-a%3,c=o+(t+1)%3,f=_+(a+2)%3,u=s[l],d=s[t],g=s[c],y=s[f];

7if(n(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])){s[t]=y,s[a]=u;const e=h[f];if(-1===e){let s=this._hullStart;do{if(this._hullTri[s]===f){this._hullTri[s]=t;break}s=this._hullPrev[s]}while(s!==this._hullStart)}this._link(t,e),this._link(a,h[l]),this._link(l,f);const n=_+(a+1)%3;r<i.length&&(i[r++]=n)}else{if(0===r)break;t=i[--r]}}return l}_link(t,s){this._halfedges[t]=s,-1!==s&&(this._halfedges[s]=t)}_addTriangle(t,s,i,h,e,n){const r=this.trianglesLen;return this._triangles[r]=t,this._triangles[r+1]=s,this._triangles[r+2]=i,this._link(r,h),this._link(r+1,e),this._link(r+2,n),this.trianglesLen+=3,r}}function e(t,s,i,h){const e=t-i,n=s-h;return e*e+n*n}function n(t,s,i,h,e,n,r,l){const a=t-r,o=s-l,_=i-r,c=h-l,f=e-r,u=n-l,d=_*_+c*c,g=f*f+u*u;return a*(c*g-d*u)-o*(_*g-d*f)+(a*a+o*o)*(_*u-c*f)<0}function r(t,s,i,h,e,n){const r=i-t,l=h-s,a=e-t,o=n-s,_=r*r+l*l,c=a*a+o*o,f=.5/(r*o-l*a),u=(o*_-l*c)*f,d=(r*c-a*_)*f;return u*u+d*d}function l(t,s,i,h){if(h-i<=20)for(let e=i+1;e<=h;e++){const h=t[e],n=s[h];let r=e-1;for(;r>=i&&s[t[r]]>n;)t[r+1]=t[r--];t[r+1]=h}else{let e=i+1,n=h;a(t,i+h>>1,e),s[t[i]]>s[t[h]]&&a(t,i,h),s[t[e]]>s[t[h]]&&a(t,e,h),s[t[i]]>s[t[e]]&&a(t,i,e);const r=t[e],o=s[r];for(;;){do{e++}while(s[t[e]]<o);do{n--}while(s[t[n]]>o);if(n<e)break;a(t,e,n)}t[i+1]=t[n],t[n]=r,h-e+1>=n-i?(l(t,s,e,h),l(t,s,i,n-1)):(l(t,s,i,n-1),l(t,s,e,h))}}function a(t,s,i){const h=t[s];t[s]=t[i],t[i]=h}function o(t){return t[0]}function _(t){return t[1]}export{h as default};