New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

d3-delaunay

Package Overview
Dependencies
Maintainers
1
Versions
41
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

d3-delaunay - npm Package Compare versions

Comparing version 4.1.4 to 4.1.5

18

dist/d3-delaunay.js

@@ -1,3 +0,3 @@

// https://github.com/d3/d3-delaunay v4.1.4 Copyright 2018 Mike Bostock
// https://github.com/mapbox/delaunator v2.0.4. Copyright 2017 Mapbox, Inc.
// https://github.com/d3/d3-delaunay v4.1.5 Copyright 2018 Mike Bostock
// https://github.com/mapbox/delaunator v2.0.5. Copyright 2017 Mapbox, Inc.
(function (global, factory) {

@@ -9,2 +9,4 @@ typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :

const EPSILON = Math.pow(2, -52);
class Delaunator {

@@ -143,9 +145,9 @@

let xp, yp;
for (const i of ids) {
for (let k = 0, xp, yp; k < ids.length; k++) {
const i = ids[k];
const x = coords[2 * i];
const y = coords[2 * i + 1];
// skip duplicate points
if (x === xp && y === yp) continue;
// skip near-duplicate points
if (k > 0 && Math.abs(x - xp) <= EPSILON && Math.abs(y - yp) <= EPSILON) continue;
xp = x;

@@ -225,3 +227,3 @@ yp = y;

_hashKey(x, y) {
return Math.floor(pseudoAngle(x - this._cx, y - this._cy) * this._hashSize);
return Math.floor(pseudoAngle(x - this._cx, y - this._cy) * this._hashSize) % this._hashSize;
}

@@ -325,3 +327,3 @@

const p = dx / (Math.abs(dx) + Math.abs(dy));
return (dy > 0 ? 3 - p : 1 + p) / 4; // [0..1)
return (dy > 0 ? 3 - p : 1 + p) / 4; // [0..1]
}

@@ -328,0 +330,0 @@

6

dist/d3-delaunay.min.js

@@ -1,3 +0,3 @@

// https://github.com/d3/d3-delaunay v4.1.4 Copyright 2018 Mike Bostock
// https://github.com/mapbox/delaunator v2.0.4. Copyright 2017 Mapbox, Inc.
!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(t.d3=t.d3||{})}(this,function(t){"use strict";class e{static from(t,i,n){i||(i=a),n||(n=c);const s=t.length,h=new Float64Array(2*s);for(let e=0;e<s;e++){const s=t[e];h[2*e]=i(s),h[2*e+1]=n(s)}return new e(h)}constructor(t){let e=1/0,a=1/0,c=-1/0,u=-1/0;const f=t.length>>1,x=this.ids=new Uint32Array(f);if(f>0&&"number"!=typeof t[0])throw new Error("Expected coords to contain numbers.");this.coords=t;for(let i=0;i<f;i++){const n=t[2*i],s=t[2*i+1];n<e&&(e=n),s<a&&(a=s),n>c&&(c=n),s>u&&(u=s),x[i]=i}const d=(e+c)/2,_=(a+u)/2;let g,y,m,p=1/0;for(let e=0;e<f;e++){const n=i(d,_,t[2*e],t[2*e+1]);n<p&&(g=e,p=n)}const v=t[2*g],w=t[2*g+1];p=1/0;for(let e=0;e<f;e++){if(e===g)continue;const n=i(v,w,t[2*e],t[2*e+1]);n<p&&n>0&&(y=e,p=n)}let T=t[2*y],b=t[2*y+1],$=1/0;for(let e=0;e<f;e++){if(e===g||e===y)continue;const i=s(v,w,T,b,t[2*e],t[2*e+1]);i<$&&(m=e,$=i)}let M=t[2*m],P=t[2*m+1];if($===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(n(v,w,T,b,M,P)){const t=y,e=T,i=b;y=m,T=M,b=P,m=t,M=e,P=i}const k=function(t,e,i,n,s,h){const r=i-t,l=n-e,o=s-t,a=h-e,c=r*r+l*l,u=o*o+a*a,f=r*a-l*o;return{x:t+.5*(a*c-l*u)/f,y:e+.5*(r*u-o*c)/f}}(v,w,T,b,M,P);this._cx=k.x,this._cy=k.y,function t(e,i,n,s,h,r){let a,c,u;if(s-n<=20)for(a=n+1;a<=s;a++){for(u=e[a],c=a-1;c>=n&&l(i,e[c],u,h,r)>0;)e[c+1]=e[c--];e[c+1]=u}else{const f=n+s>>1;for(c=s,o(e,f,a=n+1),l(i,e[n],e[s],h,r)>0&&o(e,n,s),l(i,e[a],e[s],h,r)>0&&o(e,a,s),l(i,e[n],e[a],h,r)>0&&o(e,n,a),u=e[a];;){do{a++}while(l(i,e[a],u,h,r)<0);do{c--}while(l(i,e[c],u,h,r)>0);if(c<a)break;o(e,a,c)}e[n+1]=e[c],e[c]=u,s-a+1>=c-n?(t(e,i,a,s,h,r),t(e,i,n,c-1,h,r)):(t(e,i,n,c-1,h,r),t(e,i,a,s,h,r))}}(x,t,0,x.length-1,k.x,k.y),this._hashSize=Math.ceil(Math.sqrt(f)),this._hash=new Array(this._hashSize);let A=this.hull=h(t,g);this._hashEdge(A),A.t=0,A=h(t,y,A),this._hashEdge(A),A.t=1,A=h(t,m,A),this._hashEdge(A),A.t=2;const E=2*f-5,S=this.triangles=new Uint32Array(3*E),z=this.halfedges=new Int32Array(3*E);let F,L;this.trianglesLen=0,this._addTriangle(g,y,m,-1,-1,-1);for(const e of x){const i=t[2*e],s=t[2*e+1];if(i===F&&s===L)continue;if(F=i,L=s,e===g||e===y||e===m)continue;const l=this._hashKey(i,s);let o,a=l;do{o=this._hash[a],a=(a+1)%this._hashSize}while((!o||o.removed)&&a!==l);for(A=o=o.prev;!n(i,s,A.x,A.y,A.next.x,A.next.y);)if((A=A.next)===o){A=null;break}if(!A)continue;const c=A===o;let u=this._addTriangle(A.i,e,A.next.i,-1,-1,A.t);A.t=u,(A=h(t,e,A)).t=this._legalize(u+2);let f=A.next;for(;n(i,s,f.x,f.y,f.next.x,f.next.y);)u=this._addTriangle(f.i,e,f.next.i,f.prev.t,-1,f.t),f.prev.t=this._legalize(u+2),this.hull=r(f),f=f.next;if(c)for(f=A.prev;n(i,s,f.prev.x,f.prev.y,f.x,f.y);)u=this._addTriangle(f.prev.i,e,f.i,-1,f.t,f.prev.t),this._legalize(u+2),f.prev.t=u,this.hull=r(f),f=f.prev;this._hashEdge(A),this._hashEdge(A.prev)}this.triangles=S.subarray(0,this.trianglesLen),this.halfedges=z.subarray(0,this.trianglesLen)}_hashEdge(t){this._hash[this._hashKey(t.x,t.y)]=t}_hashKey(t,e){return Math.floor(function(t,e){const i=t/(Math.abs(t)+Math.abs(e));return(e>0?3-i:1+i)/4}(t-this._cx,e-this._cy)*this._hashSize)}_legalize(t){const{triangles:e,coords:i,halfedges:n}=this,s=n[t],h=t-t%3,r=s-s%3,l=h+(t+1)%3,o=h+(t+2)%3,a=r+(s+2)%3;if(-1===s)return o;const c=e[o],u=e[t],f=e[l],x=e[a];if(function(t,e,i,n,s,h,r,l){const o=t-r,a=e-l,c=i-r,u=n-l,f=s-r,x=h-l,d=c*c+u*u,_=f*f+x*x;return o*(u*_-d*x)-a*(c*_-d*f)+(o*o+a*a)*(c*x-u*f)<0}(i[2*c],i[2*c+1],i[2*u],i[2*u+1],i[2*f],i[2*f+1],i[2*x],i[2*x+1])){e[t]=x,e[s]=c;const i=n[a];if(-1===i){let e=this.hull;do{if(e.t===a){e.t=t;break}e=e.next}while(e!==this.hull)}this._link(t,i),this._link(s,n[o]),this._link(o,a);const h=r+(s+1)%3;return this._legalize(t),this._legalize(h)}return o}_link(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)}_addTriangle(t,e,i,n,s,h){const r=this.trianglesLen;return this.triangles[r]=t,this.triangles[r+1]=e,this.triangles[r+2]=i,this._link(r,n),this._link(r+1,s),this._link(r+2,h),this.trianglesLen+=3,r}}function i(t,e,i,n){const s=t-i,h=e-n;return s*s+h*h}function n(t,e,i,n,s,h){return(n-e)*(s-i)-(i-t)*(h-n)<0}function s(t,e,i,n,s,h){const r=i-t,l=n-e,o=s-t,a=h-e,c=r*r+l*l,u=o*o+a*a,f=r*a-l*o,x=.5*(a*c-l*u)/f,d=.5*(r*u-o*c)/f;return c&&u&&f&&x*x+d*d||1/0}function h(t,e,i){const n={i:e,x:t[2*e],y:t[2*e+1],t:0,prev:null,next:null,removed:!1};return i?(n.next=i.next,n.prev=i,i.next.prev=n,i.next=n):(n.prev=n,n.next=n),n}function r(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function l(t,e,n,s,h){return i(t[2*e],t[2*e+1],s,h)-i(t[2*n],t[2*n+1],s,h)||t[2*e]-t[2*n]||t[2*e+1]-t[2*n+1]}function o(t,e,i){const n=t[e];t[e]=t[i],t[i]=n}function a(t){return t[0]}function c(t){return t[1]}const u=1e-6;class f{constructor(){this._x0=this._y0=this._x1=this._y1=null,this._=""}moveTo(t,e){this._+=`M${this._x0=this._x1=+t},${this._y0=this._y1=+e}`}closePath(){null!==this._x1&&(this._x1=this._x0,this._y1=this._y0,this._+="Z")}lineTo(t,e){this._+=`L${this._x1=+t},${this._y1=+e}`}arc(t,e,i){const n=(t=+t)+(i=+i),s=e=+e;if(i<0)throw new Error("negative radius");null===this._x1?this._+=`M${n},${s}`:(Math.abs(this._x1-n)>u||Math.abs(this._y1-s)>u)&&(this._+="L"+n+","+s),i&&(this._+=`A${i},${i},0,1,1,${t-i},${e}A${i},${i},0,1,1,${this._x1=n},${this._y1=s}`)}rect(t,e,i,n){this._+=`M${this._x0=this._x1=+t},${this._y0=this._y1=+e}h${+i}v${+n}h${-i}Z`}value(){return this._||null}}class x{constructor(){this._=[]}moveTo(t,e){this._.push([t,e])}closePath(){this._.push(this._[0].slice())}lineTo(t,e){this._.push([t,e])}value(){return this._.length?this._:null}}class d{constructor(t,[e,i,n,s]=[0,0,960,500]){if(!((n=+n)>=(e=+e)&&(s=+s)>=(i=+i)))throw new Error("invalid bounds");const{points:h,hull:r,triangles:l}=this.delaunay=t,o=this.circumcenters=new Float64Array(l.length/3*2),a=this.vectors=new Float64Array(2*h.length);this.xmax=n,this.xmin=e,this.ymax=s,this.ymin=i;for(let t=0,e=0,i=l.length;t<i;t+=3,e+=2){const i=2*l[t],n=2*l[t+1],s=2*l[t+2],r=h[i],a=h[i+1],c=h[n],u=h[n+1],f=h[s],x=h[s+1],d=r-c,_=r-f,g=a-u,y=a-x,m=r*r+a*a,p=m-c*c-u*u,v=m-f*f-x*x,w=2*(_*g-d*y);o[e]=(g*v-y*p)/w,o[e+1]=(_*p-d*v)/w}let c,u,f,x=r,d=4*x.i,_=x.x,g=x.y;do{c=d,u=_,f=g,d=4*(x=x.next).i,_=x.x,g=x.y,a[c+2]=a[d]=f-g,a[c+3]=a[d+1]=_-u}while(x!==r)}render(t){const e=null==t?t=new f:void 0,{delaunay:{halfedges:i,hull:n},circumcenters:s,vectors:h}=this;for(let e=0,n=i.length;e<n;++e){const n=i[e];if(n<e)continue;const h=2*Math.floor(e/3),r=2*Math.floor(n/3),l=s[h],o=s[h+1],a=s[r],c=s[r+1];this._renderSegment(l,o,a,c,t)}let r=n;do{r=r.next;const e=2*Math.floor(r.t/3),i=s[e],n=s[e+1],l=4*r.i,o=this._project(i,n,h[l+2],h[l+3]);o&&this._renderSegment(i,n,o[0],o[1],t)}while(r!==n);return e&&e.value()}renderBounds(t){const e=null==t?t=new f:void 0;return t.rect(this.xmin,this.ymin,this.xmax-this.xmin,this.ymax-this.ymin),e&&e.value()}renderCell(t,e){const i=null==e?e=new f:void 0,n=this._clip(t);if(null!==n){e.moveTo(n[0],n[1]);for(let t=2,i=n.length;t<i;t+=2)e.lineTo(n[t],n[t+1]);return e.closePath(),i&&i.value()}}*cellPolygons(){const{delaunay:{points:t}}=this;for(let e=0,i=t.length/2;e<i;++e){const t=this.cellPolygon(e);t&&(yield t)}}cellPolygon(t){const e=new x;return this.renderCell(t,e),e.value()}_renderSegment(t,e,i,n,s){let h;const r=this._regioncode(t,e),l=this._regioncode(i,n);0===r&&0===l?(s.moveTo(t,e),s.lineTo(i,n)):(h=this._clipSegment(t,e,i,n,r,l))&&(s.moveTo(h[0],h[1]),s.lineTo(h[2],h[3]))}contains(t,e,i){return(e=+e)==e&&(i=+i)==i&&this.delaunay._step(t,e,i)===t}_cell(t){const{circumcenters:e,delaunay:{inedges:i,halfedges:n,triangles:s}}=this,h=i[t];if(-1===h)return null;const r=[];let l=h;do{const i=Math.floor(l/3);if(r.push(e[2*i],e[2*i+1]),s[l=l%3==2?l-2:l+1]!==t)break;l=n[l]}while(l!==h&&-1!==l);return r}_clip(t){const e=this._cell(t);if(null===e)return null;const{vectors:i}=this,n=4*t;return i[n]||i[n+1]?this._clipInfinite(t,e,i[n],i[n+1],i[n+2],i[n+3]):this._clipFinite(t,e)}_clipFinite(t,e){const i=e.length;let n,s,h,r,l,o=null,a=e[i-2],c=e[i-1],u=this._regioncode(a,c);for(let f=0;f<i;f+=2)if(n=a,s=c,a=e[f],c=e[f+1],h=u,u=this._regioncode(a,c),0===h&&0===u)r=l,l=0,o?o.push(a,c):o=[a,c];else{let e,i,f,x,d;if(0===h){if(null===(e=this._clipSegment(n,s,a,c,h,u)))continue;[i,f,x,d]=e}else{if(null===(e=this._clipSegment(a,c,n,s,u,h)))continue;[x,d,i,f]=e,r=l,l=this._edgecode(i,f),r&&l&&this._edge(t,r,l,o,o.length),o?o.push(i,f):o=[i,f]}r=l,l=this._edgecode(x,d),r&&l&&this._edge(t,r,l,o,o.length),o?o.push(x,d):o=[x,d]}if(o)r=l,l=this._edgecode(o[0],o[1]),r&&l&&this._edge(t,r,l,o,o.length);else if(this.contains(t,(this.xmin+this.xmax)/2,(this.ymin+this.ymax)/2))return[this.xmax,this.ymin,this.xmax,this.ymax,this.xmin,this.ymax,this.xmin,this.ymin];return o}_clipSegment(t,e,i,n,s,h){for(;;){if(0===s&&0===h)return[t,e,i,n];if(s&h)return null;let r,l,o=s||h;8&o?(r=t+(i-t)*(this.ymax-e)/(n-e),l=this.ymax):4&o?(r=t+(i-t)*(this.ymin-e)/(n-e),l=this.ymin):2&o?(l=e+(n-e)*(this.xmax-t)/(i-t),r=this.xmax):(l=e+(n-e)*(this.xmin-t)/(i-t),r=this.xmin),s?(t=r,e=l,s=this._regioncode(t,e)):(i=r,n=l,h=this._regioncode(i,n))}}_clipInfinite(t,e,i,n,s,h){let r,l=Array.from(e);if((r=this._project(l[0],l[1],i,n))&&l.unshift(r[0],r[1]),(r=this._project(l[l.length-2],l[l.length-1],s,h))&&l.push(r[0],r[1]),l=this._clipFinite(t,l))for(let e,i=0,n=l.length,s=this._edgecode(l[n-2],l[n-1]);i<n;i+=2)e=s,s=this._edgecode(l[i],l[i+1]),e&&s&&(i=this._edge(t,e,s,l,i),n=l.length);else this.contains(t,(this.xmin+this.xmax)/2,(this.ymin+this.ymax)/2)&&(l=[this.xmin,this.ymin,this.xmax,this.ymin,this.xmax,this.ymax,this.xmin,this.ymax]);return l}_edge(t,e,i,n,s){for(;e!==i;){let i,h;switch(e){case 5:e=4;continue;case 4:e=6,i=this.xmax,h=this.ymin;break;case 6:e=2;continue;case 2:e=10,i=this.xmax,h=this.ymax;break;case 10:e=8;continue;case 8:e=9,i=this.xmin,h=this.ymax;break;case 9:e=1;continue;case 1:e=5,i=this.xmin,h=this.ymin}n[s]===i&&n[s+1]===h||!this.contains(t,i,h)||(n.splice(s,0,i,h),s+=2)}return s}_project(t,e,i,n){let s,h,r,l=1/0;if(n<0){if(e<=this.ymin)return null;(s=(this.ymin-e)/n)<l&&(r=this.ymin,h=t+(l=s)*i)}else if(n>0){if(e>=this.ymax)return null;(s=(this.ymax-e)/n)<l&&(r=this.ymax,h=t+(l=s)*i)}if(i>0){if(t>=this.xmax)return null;(s=(this.xmax-t)/i)<l&&(h=this.xmax,r=e+(l=s)*n)}else if(i<0){if(t<=this.xmin)return null;(s=(this.xmin-t)/i)<l&&(h=this.xmin,r=e+(l=s)*n)}return[h,r]}_edgecode(t,e){return(t===this.xmin?1:t===this.xmax?2:0)|(e===this.ymin?4:e===this.ymax?8:0)}_regioncode(t,e){return(t<this.xmin?1:t>this.xmax?2:0)|(e<this.ymin?4:e>this.ymax?8:0)}}const _=2*Math.PI;class g{constructor(t){const{halfedges:i,hull:n,triangles:s}=new e(t);this.points=t,this.halfedges=i,this.hull=n,this.triangles=s;const h=this.inedges=new Int32Array(t.length/2).fill(-1),r=this.outedges=new Int32Array(t.length/2).fill(-1);for(let t=0,e=i.length;t<e;++t)h[s[t%3==2?t-2:t+1]]=t;let l,o=n;do{l=o,h[(o=o.next).i]=l.t,r[l.i]=o.t}while(o!==n)}voronoi(t){return new d(this,t)}*neighbors(t){const{inedges:e,outedges:i,halfedges:n,triangles:s}=this,h=e[t];if(-1===h)return;let r=h;do{if(yield s[r],s[r=r%3==2?r-2:r+1]!==t)return;if(-1===(r=n[r]))return yield s[i[t]]}while(r!==h)}find(t,e,i=0){if((t=+t)!=t||(e=+e)!=e)return-1;let n;for(;(n=this._step(i,t,e))>=0&&n!==i;)i=n;return n}_step(t,e,i){const{inedges:n,points:s}=this;if(-1===n[t])return-1;let h=t,r=(e-s[2*t])**2+(i-s[2*t+1])**2;for(const n of this.neighbors(t)){const t=(e-s[2*n])**2+(i-s[2*n+1])**2;t<r&&(r=t,h=n)}return h}render(t){const e=null==t?t=new f:void 0,{points:i,halfedges:n,triangles:s}=this;for(let e=0,h=n.length;e<h;++e){const h=n[e];if(h<e)continue;const r=2*s[e],l=2*s[h];t.moveTo(i[r],i[r+1]),t.lineTo(i[l],i[l+1])}return this.renderHull(t),e&&e.value()}renderPoints(t,e=2){const i=null==t?t=new f:void 0,{points:n}=this;for(let i=0,s=n.length;i<s;i+=2){const s=n[i],h=n[i+1];t.moveTo(s+e,h),t.arc(s,h,e,0,_)}return i&&i.value()}renderHull(t){const e=null==t?t=new f:void 0,{hull:i}=this;let n=i;for(t.moveTo(n.x,n.y);(n=n.next)!==i;)t.lineTo(n.x,n.y);return t.closePath(),e&&e.value()}hullPolygon(){const t=new x;return this.renderHull(t),t.value()}renderTriangle(t,e){const i=null==e?e=new f:void 0,{points:n,triangles:s}=this,h=2*s[t*=3],r=2*s[t+1],l=2*s[t+2];return e.moveTo(n[h],n[h+1]),e.lineTo(n[r],n[r+1]),e.lineTo(n[l],n[l+1]),e.closePath(),i&&i.value()}*trianglePolygons(){const{triangles:t}=this;for(let e=0,i=t.length/3;e<i;++e)yield this.trianglePolygon(e)}trianglePolygon(t){const e=new x;return this.renderTriangle(t,e),e.value()}}g.from=function(t,e=function(t){return t[0]},i=function(t){return t[1]},n){return new g("length"in t?function(t,e,i,n){const s=t.length,h=new Float64Array(2*s);for(let r=0;r<s;++r){const s=t[r];h[2*r]=e.call(n,s,r,t),h[2*r+1]=i.call(n,s,r,t)}return h}(t,e,i,n):Float64Array.from(function*(t,e,i,n){let s=0;for(const h of t)yield e.call(n,h,s,t),yield i.call(n,h,s,t),++s}(t,e,i,n)))},t.Delaunay=g,t.Voronoi=d,Object.defineProperty(t,"__esModule",{value:!0})});
// https://github.com/d3/d3-delaunay v4.1.5 Copyright 2018 Mike Bostock
// https://github.com/mapbox/delaunator v2.0.5. Copyright 2017 Mapbox, Inc.
!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(t.d3=t.d3||{})}(this,function(t){"use strict";const e=Math.pow(2,-52);class i{static from(t,e,n){e||(e=c),n||(n=u);const s=t.length,h=new Float64Array(2*s);for(let i=0;i<s;i++){const s=t[i];h[2*i]=e(s),h[2*i+1]=n(s)}return new i(h)}constructor(t){let i=1/0,c=1/0,u=-1/0,f=-1/0;const x=t.length>>1,d=this.ids=new Uint32Array(x);if(x>0&&"number"!=typeof t[0])throw new Error("Expected coords to contain numbers.");this.coords=t;for(let e=0;e<x;e++){const n=t[2*e],s=t[2*e+1];n<i&&(i=n),s<c&&(c=s),n>u&&(u=n),s>f&&(f=s),d[e]=e}const _=(i+u)/2,g=(c+f)/2;let y,m,p,v=1/0;for(let e=0;e<x;e++){const i=n(_,g,t[2*e],t[2*e+1]);i<v&&(y=e,v=i)}const w=t[2*y],T=t[2*y+1];v=1/0;for(let e=0;e<x;e++){if(e===y)continue;const i=n(w,T,t[2*e],t[2*e+1]);i<v&&i>0&&(m=e,v=i)}let b=t[2*m],M=t[2*m+1],$=1/0;for(let e=0;e<x;e++){if(e===y||e===m)continue;const i=h(w,T,b,M,t[2*e],t[2*e+1]);i<$&&(p=e,$=i)}let P=t[2*p],k=t[2*p+1];if($===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(s(w,T,b,M,P,k)){const t=m,e=b,i=M;m=p,b=P,M=k,p=t,P=e,k=i}const A=function(t,e,i,n,s,h){const r=i-t,l=n-e,o=s-t,a=h-e,c=r*r+l*l,u=o*o+a*a,f=r*a-l*o;return{x:t+.5*(a*c-l*u)/f,y:e+.5*(r*u-o*c)/f}}(w,T,b,M,P,k);this._cx=A.x,this._cy=A.y,function t(e,i,n,s,h,r){let l,c,u;if(s-n<=20)for(l=n+1;l<=s;l++){for(u=e[l],c=l-1;c>=n&&o(i,e[c],u,h,r)>0;)e[c+1]=e[c--];e[c+1]=u}else{const f=n+s>>1;for(c=s,a(e,f,l=n+1),o(i,e[n],e[s],h,r)>0&&a(e,n,s),o(i,e[l],e[s],h,r)>0&&a(e,l,s),o(i,e[n],e[l],h,r)>0&&a(e,n,l),u=e[l];;){do{l++}while(o(i,e[l],u,h,r)<0);do{c--}while(o(i,e[c],u,h,r)>0);if(c<l)break;a(e,l,c)}e[n+1]=e[c],e[c]=u,s-l+1>=c-n?(t(e,i,l,s,h,r),t(e,i,n,c-1,h,r)):(t(e,i,n,c-1,h,r),t(e,i,l,s,h,r))}}(d,t,0,d.length-1,A.x,A.y),this._hashSize=Math.ceil(Math.sqrt(x)),this._hash=new Array(this._hashSize);let S=this.hull=r(t,y);this._hashEdge(S),S.t=0,S=r(t,m,S),this._hashEdge(S),S.t=1,S=r(t,p,S),this._hashEdge(S),S.t=2;const z=2*x-5,E=this.triangles=new Uint32Array(3*z),F=this.halfedges=new Int32Array(3*z);this.trianglesLen=0,this._addTriangle(y,m,p,-1,-1,-1);for(let i,n,h=0;h<d.length;h++){const o=d[h],a=t[2*o],c=t[2*o+1];if(h>0&&Math.abs(a-i)<=e&&Math.abs(c-n)<=e)continue;if(i=a,n=c,o===y||o===m||o===p)continue;const u=this._hashKey(a,c);let f,x=u;do{f=this._hash[x],x=(x+1)%this._hashSize}while((!f||f.removed)&&x!==u);for(S=f=f.prev;!s(a,c,S.x,S.y,S.next.x,S.next.y);)if((S=S.next)===f){S=null;break}if(!S)continue;const _=S===f;let g=this._addTriangle(S.i,o,S.next.i,-1,-1,S.t);S.t=g,(S=r(t,o,S)).t=this._legalize(g+2);let v=S.next;for(;s(a,c,v.x,v.y,v.next.x,v.next.y);)g=this._addTriangle(v.i,o,v.next.i,v.prev.t,-1,v.t),v.prev.t=this._legalize(g+2),this.hull=l(v),v=v.next;if(_)for(v=S.prev;s(a,c,v.prev.x,v.prev.y,v.x,v.y);)g=this._addTriangle(v.prev.i,o,v.i,-1,v.t,v.prev.t),this._legalize(g+2),v.prev.t=g,this.hull=l(v),v=v.prev;this._hashEdge(S),this._hashEdge(S.prev)}this.triangles=E.subarray(0,this.trianglesLen),this.halfedges=F.subarray(0,this.trianglesLen)}_hashEdge(t){this._hash[this._hashKey(t.x,t.y)]=t}_hashKey(t,e){return Math.floor(function(t,e){const i=t/(Math.abs(t)+Math.abs(e));return(e>0?3-i:1+i)/4}(t-this._cx,e-this._cy)*this._hashSize)%this._hashSize}_legalize(t){const{triangles:e,coords:i,halfedges:n}=this,s=n[t],h=t-t%3,r=s-s%3,l=h+(t+1)%3,o=h+(t+2)%3,a=r+(s+2)%3;if(-1===s)return o;const c=e[o],u=e[t],f=e[l],x=e[a];if(function(t,e,i,n,s,h,r,l){const o=t-r,a=e-l,c=i-r,u=n-l,f=s-r,x=h-l,d=c*c+u*u,_=f*f+x*x;return o*(u*_-d*x)-a*(c*_-d*f)+(o*o+a*a)*(c*x-u*f)<0}(i[2*c],i[2*c+1],i[2*u],i[2*u+1],i[2*f],i[2*f+1],i[2*x],i[2*x+1])){e[t]=x,e[s]=c;const i=n[a];if(-1===i){let e=this.hull;do{if(e.t===a){e.t=t;break}e=e.next}while(e!==this.hull)}this._link(t,i),this._link(s,n[o]),this._link(o,a);const h=r+(s+1)%3;return this._legalize(t),this._legalize(h)}return o}_link(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)}_addTriangle(t,e,i,n,s,h){const r=this.trianglesLen;return this.triangles[r]=t,this.triangles[r+1]=e,this.triangles[r+2]=i,this._link(r,n),this._link(r+1,s),this._link(r+2,h),this.trianglesLen+=3,r}}function n(t,e,i,n){const s=t-i,h=e-n;return s*s+h*h}function s(t,e,i,n,s,h){return(n-e)*(s-i)-(i-t)*(h-n)<0}function h(t,e,i,n,s,h){const r=i-t,l=n-e,o=s-t,a=h-e,c=r*r+l*l,u=o*o+a*a,f=r*a-l*o,x=.5*(a*c-l*u)/f,d=.5*(r*u-o*c)/f;return c&&u&&f&&x*x+d*d||1/0}function r(t,e,i){const n={i:e,x:t[2*e],y:t[2*e+1],t:0,prev:null,next:null,removed:!1};return i?(n.next=i.next,n.prev=i,i.next.prev=n,i.next=n):(n.prev=n,n.next=n),n}function l(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function o(t,e,i,s,h){return n(t[2*e],t[2*e+1],s,h)-n(t[2*i],t[2*i+1],s,h)||t[2*e]-t[2*i]||t[2*e+1]-t[2*i+1]}function a(t,e,i){const n=t[e];t[e]=t[i],t[i]=n}function c(t){return t[0]}function u(t){return t[1]}const f=1e-6;class x{constructor(){this._x0=this._y0=this._x1=this._y1=null,this._=""}moveTo(t,e){this._+=`M${this._x0=this._x1=+t},${this._y0=this._y1=+e}`}closePath(){null!==this._x1&&(this._x1=this._x0,this._y1=this._y0,this._+="Z")}lineTo(t,e){this._+=`L${this._x1=+t},${this._y1=+e}`}arc(t,e,i){const n=(t=+t)+(i=+i),s=e=+e;if(i<0)throw new Error("negative radius");null===this._x1?this._+=`M${n},${s}`:(Math.abs(this._x1-n)>f||Math.abs(this._y1-s)>f)&&(this._+="L"+n+","+s),i&&(this._+=`A${i},${i},0,1,1,${t-i},${e}A${i},${i},0,1,1,${this._x1=n},${this._y1=s}`)}rect(t,e,i,n){this._+=`M${this._x0=this._x1=+t},${this._y0=this._y1=+e}h${+i}v${+n}h${-i}Z`}value(){return this._||null}}class d{constructor(){this._=[]}moveTo(t,e){this._.push([t,e])}closePath(){this._.push(this._[0].slice())}lineTo(t,e){this._.push([t,e])}value(){return this._.length?this._:null}}class _{constructor(t,[e,i,n,s]=[0,0,960,500]){if(!((n=+n)>=(e=+e)&&(s=+s)>=(i=+i)))throw new Error("invalid bounds");const{points:h,hull:r,triangles:l}=this.delaunay=t,o=this.circumcenters=new Float64Array(l.length/3*2),a=this.vectors=new Float64Array(2*h.length);this.xmax=n,this.xmin=e,this.ymax=s,this.ymin=i;for(let t=0,e=0,i=l.length;t<i;t+=3,e+=2){const i=2*l[t],n=2*l[t+1],s=2*l[t+2],r=h[i],a=h[i+1],c=h[n],u=h[n+1],f=h[s],x=h[s+1],d=r-c,_=r-f,g=a-u,y=a-x,m=r*r+a*a,p=m-c*c-u*u,v=m-f*f-x*x,w=2*(_*g-d*y);o[e]=(g*v-y*p)/w,o[e+1]=(_*p-d*v)/w}let c,u,f,x=r,d=4*x.i,_=x.x,g=x.y;do{c=d,u=_,f=g,d=4*(x=x.next).i,_=x.x,g=x.y,a[c+2]=a[d]=f-g,a[c+3]=a[d+1]=_-u}while(x!==r)}render(t){const e=null==t?t=new x:void 0,{delaunay:{halfedges:i,hull:n},circumcenters:s,vectors:h}=this;for(let e=0,n=i.length;e<n;++e){const n=i[e];if(n<e)continue;const h=2*Math.floor(e/3),r=2*Math.floor(n/3),l=s[h],o=s[h+1],a=s[r],c=s[r+1];this._renderSegment(l,o,a,c,t)}let r=n;do{r=r.next;const e=2*Math.floor(r.t/3),i=s[e],n=s[e+1],l=4*r.i,o=this._project(i,n,h[l+2],h[l+3]);o&&this._renderSegment(i,n,o[0],o[1],t)}while(r!==n);return e&&e.value()}renderBounds(t){const e=null==t?t=new x:void 0;return t.rect(this.xmin,this.ymin,this.xmax-this.xmin,this.ymax-this.ymin),e&&e.value()}renderCell(t,e){const i=null==e?e=new x:void 0,n=this._clip(t);if(null!==n){e.moveTo(n[0],n[1]);for(let t=2,i=n.length;t<i;t+=2)e.lineTo(n[t],n[t+1]);return e.closePath(),i&&i.value()}}*cellPolygons(){const{delaunay:{points:t}}=this;for(let e=0,i=t.length/2;e<i;++e){const t=this.cellPolygon(e);t&&(yield t)}}cellPolygon(t){const e=new d;return this.renderCell(t,e),e.value()}_renderSegment(t,e,i,n,s){let h;const r=this._regioncode(t,e),l=this._regioncode(i,n);0===r&&0===l?(s.moveTo(t,e),s.lineTo(i,n)):(h=this._clipSegment(t,e,i,n,r,l))&&(s.moveTo(h[0],h[1]),s.lineTo(h[2],h[3]))}contains(t,e,i){return(e=+e)==e&&(i=+i)==i&&this.delaunay._step(t,e,i)===t}_cell(t){const{circumcenters:e,delaunay:{inedges:i,halfedges:n,triangles:s}}=this,h=i[t];if(-1===h)return null;const r=[];let l=h;do{const i=Math.floor(l/3);if(r.push(e[2*i],e[2*i+1]),s[l=l%3==2?l-2:l+1]!==t)break;l=n[l]}while(l!==h&&-1!==l);return r}_clip(t){const e=this._cell(t);if(null===e)return null;const{vectors:i}=this,n=4*t;return i[n]||i[n+1]?this._clipInfinite(t,e,i[n],i[n+1],i[n+2],i[n+3]):this._clipFinite(t,e)}_clipFinite(t,e){const i=e.length;let n,s,h,r,l,o=null,a=e[i-2],c=e[i-1],u=this._regioncode(a,c);for(let f=0;f<i;f+=2)if(n=a,s=c,a=e[f],c=e[f+1],h=u,u=this._regioncode(a,c),0===h&&0===u)r=l,l=0,o?o.push(a,c):o=[a,c];else{let e,i,f,x,d;if(0===h){if(null===(e=this._clipSegment(n,s,a,c,h,u)))continue;[i,f,x,d]=e}else{if(null===(e=this._clipSegment(a,c,n,s,u,h)))continue;[x,d,i,f]=e,r=l,l=this._edgecode(i,f),r&&l&&this._edge(t,r,l,o,o.length),o?o.push(i,f):o=[i,f]}r=l,l=this._edgecode(x,d),r&&l&&this._edge(t,r,l,o,o.length),o?o.push(x,d):o=[x,d]}if(o)r=l,l=this._edgecode(o[0],o[1]),r&&l&&this._edge(t,r,l,o,o.length);else if(this.contains(t,(this.xmin+this.xmax)/2,(this.ymin+this.ymax)/2))return[this.xmax,this.ymin,this.xmax,this.ymax,this.xmin,this.ymax,this.xmin,this.ymin];return o}_clipSegment(t,e,i,n,s,h){for(;;){if(0===s&&0===h)return[t,e,i,n];if(s&h)return null;let r,l,o=s||h;8&o?(r=t+(i-t)*(this.ymax-e)/(n-e),l=this.ymax):4&o?(r=t+(i-t)*(this.ymin-e)/(n-e),l=this.ymin):2&o?(l=e+(n-e)*(this.xmax-t)/(i-t),r=this.xmax):(l=e+(n-e)*(this.xmin-t)/(i-t),r=this.xmin),s?(t=r,e=l,s=this._regioncode(t,e)):(i=r,n=l,h=this._regioncode(i,n))}}_clipInfinite(t,e,i,n,s,h){let r,l=Array.from(e);if((r=this._project(l[0],l[1],i,n))&&l.unshift(r[0],r[1]),(r=this._project(l[l.length-2],l[l.length-1],s,h))&&l.push(r[0],r[1]),l=this._clipFinite(t,l))for(let e,i=0,n=l.length,s=this._edgecode(l[n-2],l[n-1]);i<n;i+=2)e=s,s=this._edgecode(l[i],l[i+1]),e&&s&&(i=this._edge(t,e,s,l,i),n=l.length);else this.contains(t,(this.xmin+this.xmax)/2,(this.ymin+this.ymax)/2)&&(l=[this.xmin,this.ymin,this.xmax,this.ymin,this.xmax,this.ymax,this.xmin,this.ymax]);return l}_edge(t,e,i,n,s){for(;e!==i;){let i,h;switch(e){case 5:e=4;continue;case 4:e=6,i=this.xmax,h=this.ymin;break;case 6:e=2;continue;case 2:e=10,i=this.xmax,h=this.ymax;break;case 10:e=8;continue;case 8:e=9,i=this.xmin,h=this.ymax;break;case 9:e=1;continue;case 1:e=5,i=this.xmin,h=this.ymin}n[s]===i&&n[s+1]===h||!this.contains(t,i,h)||(n.splice(s,0,i,h),s+=2)}return s}_project(t,e,i,n){let s,h,r,l=1/0;if(n<0){if(e<=this.ymin)return null;(s=(this.ymin-e)/n)<l&&(r=this.ymin,h=t+(l=s)*i)}else if(n>0){if(e>=this.ymax)return null;(s=(this.ymax-e)/n)<l&&(r=this.ymax,h=t+(l=s)*i)}if(i>0){if(t>=this.xmax)return null;(s=(this.xmax-t)/i)<l&&(h=this.xmax,r=e+(l=s)*n)}else if(i<0){if(t<=this.xmin)return null;(s=(this.xmin-t)/i)<l&&(h=this.xmin,r=e+(l=s)*n)}return[h,r]}_edgecode(t,e){return(t===this.xmin?1:t===this.xmax?2:0)|(e===this.ymin?4:e===this.ymax?8:0)}_regioncode(t,e){return(t<this.xmin?1:t>this.xmax?2:0)|(e<this.ymin?4:e>this.ymax?8:0)}}const g=2*Math.PI;class y{constructor(t){const{halfedges:e,hull:n,triangles:s}=new i(t);this.points=t,this.halfedges=e,this.hull=n,this.triangles=s;const h=this.inedges=new Int32Array(t.length/2).fill(-1),r=this.outedges=new Int32Array(t.length/2).fill(-1);for(let t=0,i=e.length;t<i;++t)h[s[t%3==2?t-2:t+1]]=t;let l,o=n;do{l=o,h[(o=o.next).i]=l.t,r[l.i]=o.t}while(o!==n)}voronoi(t){return new _(this,t)}*neighbors(t){const{inedges:e,outedges:i,halfedges:n,triangles:s}=this,h=e[t];if(-1===h)return;let r=h;do{if(yield s[r],s[r=r%3==2?r-2:r+1]!==t)return;if(-1===(r=n[r]))return yield s[i[t]]}while(r!==h)}find(t,e,i=0){if((t=+t)!=t||(e=+e)!=e)return-1;let n;for(;(n=this._step(i,t,e))>=0&&n!==i;)i=n;return n}_step(t,e,i){const{inedges:n,points:s}=this;if(-1===n[t])return-1;let h=t,r=(e-s[2*t])**2+(i-s[2*t+1])**2;for(const n of this.neighbors(t)){const t=(e-s[2*n])**2+(i-s[2*n+1])**2;t<r&&(r=t,h=n)}return h}render(t){const e=null==t?t=new x:void 0,{points:i,halfedges:n,triangles:s}=this;for(let e=0,h=n.length;e<h;++e){const h=n[e];if(h<e)continue;const r=2*s[e],l=2*s[h];t.moveTo(i[r],i[r+1]),t.lineTo(i[l],i[l+1])}return this.renderHull(t),e&&e.value()}renderPoints(t,e=2){const i=null==t?t=new x:void 0,{points:n}=this;for(let i=0,s=n.length;i<s;i+=2){const s=n[i],h=n[i+1];t.moveTo(s+e,h),t.arc(s,h,e,0,g)}return i&&i.value()}renderHull(t){const e=null==t?t=new x:void 0,{hull:i}=this;let n=i;for(t.moveTo(n.x,n.y);(n=n.next)!==i;)t.lineTo(n.x,n.y);return t.closePath(),e&&e.value()}hullPolygon(){const t=new d;return this.renderHull(t),t.value()}renderTriangle(t,e){const i=null==e?e=new x:void 0,{points:n,triangles:s}=this,h=2*s[t*=3],r=2*s[t+1],l=2*s[t+2];return e.moveTo(n[h],n[h+1]),e.lineTo(n[r],n[r+1]),e.lineTo(n[l],n[l+1]),e.closePath(),i&&i.value()}*trianglePolygons(){const{triangles:t}=this;for(let e=0,i=t.length/3;e<i;++e)yield this.trianglePolygon(e)}trianglePolygon(t){const e=new d;return this.renderTriangle(t,e),e.value()}}y.from=function(t,e=function(t){return t[0]},i=function(t){return t[1]},n){return new y("length"in t?function(t,e,i,n){const s=t.length,h=new Float64Array(2*s);for(let r=0;r<s;++r){const s=t[r];h[2*r]=e.call(n,s,r,t),h[2*r+1]=i.call(n,s,r,t)}return h}(t,e,i,n):Float64Array.from(function*(t,e,i,n){let s=0;for(const h of t)yield e.call(n,h,s,t),yield i.call(n,h,s,t),++s}(t,e,i,n)))},t.Delaunay=y,t.Voronoi=_,Object.defineProperty(t,"__esModule",{value:!0})});

2

package.json
{
"name": "d3-delaunay",
"version": "4.1.4",
"version": "4.1.5",
"description": "Compute the Voronoi diagram of a set of two-dimensional points.",

@@ -5,0 +5,0 @@ "keywords": [

yarn.lock

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc