https://mouvement-municipal.fr/assets/vendor/delaunator/delaunator.index-4P-xcQO.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 q}from"robust-predicates";const F=Math.pow(2,-52),G=new Uint32Array(512);class C{static from(t,i=V,l=W){const r=t.length,h=new Float64Array(r*2);for(let n=0;n<r;n++){const o=t[n];h[2*n]=i(o),h[2*n+1]=l(o)}return new C(h)}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 l=Math.max(2*i-5,0);this._triangles=new Uint32Array(l*3),this._halfedges=new Int32Array(l*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).fill(-1),this._ids=new Uint32Array(i),this._dists=new Float64Array(i),this.update()}update(){const{coords:t,_hullPrev:i,_hullNext:l,_hullTri:r,_hullHash:h}=this,n=t.length>>1;let o=1/0,_=1/0,f=-1/0,b=-1/0;for(let s=0;s<n;s++){const c=t[2*s],g=t[2*s+1];c<o&&(o=c),g<_&&(_=g),c>f&&(f=c),g>b&&(b=g),this._ids[s]=s}const d=(o+f)/2,m=(_+b)/2;let w=1/0,u,y,p;for(let s=0;s<n;s++){const c=Y(d,m,t[2*s],t[2*s+1]);c<w&&(u=s,w=c)}const z=t[2*u],U=t[2*u+1];w=1/0;for(let s=0;s<n;s++){if(s===u)continue;const c=Y(z,U,t[2*s],t[2*s+1]);c<w&&c>0&&(y=s,w=c)}let A=t[2*y],L=t[2*y+1],H=1/0;for(let s=0;s<n;s++){if(s===u||s===y)continue;const c=J(z,U,A,L,t[2*s],t[2*s+1]);c<H&&(p=s,H=c)}let P=t[2*p],v=t[2*p+1];if(H===1/0){for(let g=0;g<n;g++)this._dists[g]=t[2*g]-t[0]||t[2*g+1]-t[1];E(this._ids,this._dists,0,n-1);const s=new Uint32Array(n);let c=0;for(let g=0,x=-1/0;g<n;g++){const S=this._ids[g];this._dists[S]>x&&(s[c++]=S,x=this._dists[S])}this.hull=s.subarray(0,c),this.triangles=new Uint32Array(0),this.halfedges=new Uint32Array(0);return}if(q(z,U,A,L,P,v)<0){const s=y,c=A,g=L;y=p,A=P,L=v,p=s,P=c,v=g}const j=Q(z,U,A,L,P,v);this._cx=j.x,this._cy=j.y;for(let s=0;s<n;s++)this._dists[s]=Y(t[2*s],t[2*s+1],j.x,j.y);E(this._ids,this._dists,0,n-1),this._hullStart=u;let D=3;l[u]=i[p]=y,l[y]=i[u]=p,l[p]=i[y]=u,r[u]=0,r[y]=1,r[p]=2,h.fill(-1),h[this._hashKey(z,U)]=u,h[this._hashKey(A,L)]=y,h[this._hashKey(P,v)]=p,this.trianglesLen=0,this._addTriangle(u,y,p,-1,-1,-1);for(let s=0,c,g;s<this._ids.length;s++){const x=this._ids[s],S=t[2*x],M=t[2*x+1];if(s>0&&Math.abs(S-c)<=F&&Math.abs(M-g)<=F||(c=S,g=M,x===u||x===y||x===p))continue;let T=0;for(let X=0,O=this._hashKey(S,M);X<this._hashSize&&(T=h[(O+X)%this._hashSize],!(T!==-1&&T!==l[T]));X++);T=i[T];let a=T,k;for(;k=l[a],q(S,M,t[2*a],t[2*a+1],t[2*k],t[2*k+1])>=0;)if(a=k,a===T){a=-1;break}if(a===-1)continue;let K=this._addTriangle(a,x,l[a],-1,-1,r[a]);r[x]=this._legalize(K+2),r[a]=K,D++;let I=l[a];for(;k=l[I],q(S,M,t[2*I],t[2*I+1],t[2*k],t[2*k+1])<0;)K=this._addTriangle(I,x,k,r[x],-1,r[I]),r[x]=this._legalize(K+2),l[I]=I,D--,I=k;if(a===T)for(;k=i[a],q(S,M,t[2*k],t[2*k+1],t[2*a],t[2*a+1])<0;)K=this._addTriangle(k,x,a,-1,r[a],r[k]),this._legalize(K+2),r[k]=K,l[a]=a,D--,a=k;this._hullStart=i[x]=a,l[a]=i[I]=x,l[x]=I,h[this._hashKey(S,M)]=x,h[this._hashKey(t[2*a],t[2*a+1])]=a}this.hull=new Uint32Array(D);for(let s=0,c=this._hullStart;s<D;s++)this.hull[s]=c,c=l[c];this.triangles=this._triangles.subarray(0,this.trianglesLen),this.halfedges=this._halfedges.subarray(0,this.trianglesLen)}_hashKey(t,i){return Math.floor(R(t-this._cx,i-this._cy)*this._hashSize)%this._hashSize}_legalize(t){const{_triangles:i,_halfedges:l,coords:r}=this;let h=0,n=0;for(;;){const o=l[t],_=t-t%3;if(n=_+(t+2)%3,o===-1){if(h===0)break;t=G[--h];continue}const f=o-o%3,b=_+(t+1)%3,d=f+(o+2)%3,m=i[n],w=i[t],u=i[b],y=i[d];if(B(r[2*m],r[2*m+1],r[2*w],r[2*w+1],r[2*u],r[2*u+1],r[2*y],r[2*y+1])){i[t]=y,i[o]=m;const z=l[d];if(z===-1){let A=this._hullStart;do{if(this._hullTri[A]===d){this._hullTri[A]=t;break}A=this._hullPrev[A]}while(A!==this._hullStart)}this._link(t,z),this._link(o,l[n]),this._link(n,d);const U=f+(o+1)%3;h<G.length&&(G[h++]=U)}else{if(h===0)break;t=G[--h]}}return n}_link(t,i){this._halfedges[t]=i,i!==-1&&(this._halfedges[i]=t)}_addTriangle(t,i,l,r,h,n){const o=this.trianglesLen;return this._triangles[o]=t,this._triangles[o+1]=i,this._triangles[o+2]=l,this._link(o,r),this._link(o+1,h),this._link(o+2,n),this.trianglesLen+=3,o}}function R(e,t){const i=e/(Math.abs(e)+Math.abs(t));return(t>0?3-i:1+i)/4}function Y(e,t,i,l){const r=e-i,h=t-l;return r*r+h*h}function B(e,t,i,l,r,h,n,o){const _=e-n,f=t-o,b=i-n,d=l-o,m=r-n,w=h-o,u=_*_+f*f,y=b*b+d*d,p=m*m+w*w;return _*(d*p-y*w)-f*(b*p-y*m)+u*(b*w-d*m)<0}function J(e,t,i,l,r,h){const n=i-e,o=l-t,_=r-e,f=h-t,b=n*n+o*o,d=_*_+f*f,m=.5/(n*f-o*_),w=(f*b-o*d)*m,u=(n*d-_*b)*m;return w*w+u*u}function Q(e,t,i,l,r,h){const n=i-e,o=l-t,_=r-e,f=h-t,b=n*n+o*o,d=_*_+f*f,m=.5/(n*f-o*_),w=e+(f*b-o*d)*m,u=t+(n*d-_*b)*m;return{x:w,y:u}}function E(e,t,i,l){if(l-i<=20)for(let r=i+1;r<=l;r++){const h=e[r],n=t[h];let o=r-1;for(;o>=i&&t[e[o]]>n;)e[o+1]=e[o--];e[o+1]=h}else{const r=i+l>>1;let h=i+1,n=l;N(e,r,h),t[e[i]]>t[e[l]]&&N(e,i,l),t[e[h]]>t[e[l]]&&N(e,h,l),t[e[i]]>t[e[h]]&&N(e,i,h);const o=e[h],_=t[o];for(;;){do h++;while(t[e[h]]<_);do n--;while(t[e[n]]>_);if(n<h)break;N(e,h,n)}e[i+1]=e[n],e[n]=o,l-h+1>=n-i?(E(e,t,h,l),E(e,t,i,n-1)):(E(e,t,i,n-1),E(e,t,h,l))}}function N(e,t,i){const l=e[t];e[t]=e[i],e[i]=l}function V(e){return e[0]}function W(e){return e[1]}export{C as default};