d3-delaunay - npm Package Compare versions

Comparing version 3.1.7 to 4.0.0

dist/d3-delaunay.js

@@ -1,2 +0,2 @@
-// https://github.com/d3/d3-delaunay Version 3.1.7. Copyright 2018 Observable, Inc.
+// https://github.com/d3/d3-delaunay Version 4.0.0. Copyright 2018 Observable, Inc.
 // https://github.com/mapbox/delaunator Version 2.0.0. Copyright 2017, Mapbox, Inc.
@@ -516,6 +516,4 @@ (function (global, factory) {
         if (!((xmax = +xmax) >= (xmin = +xmin)) || !((ymax = +ymax) >= (ymin = +ymin))) throw new Error("invalid bounds");
-        const {points, halfedges, hull, triangles} = this.delaunay = delaunay;
+        const {points, hull, triangles} = this.delaunay = delaunay;
         const circumcenters = this.circumcenters = new Float64Array(triangles.length / 3 * 2);
-        const edges = this.edges = new Uint32Array(halfedges.length);
-        const index = this.index = new Uint32Array(points.length);
         const vectors = this.vectors = new Float64Array(points.length * 2);
@@ -525,33 +523,2 @@ this.xmax = xmax, this.xmin = xmin;
 
-        // Compute cell topology.
-        for (let i = 0, e = 0, m = halfedges.length; i < m; ++i) {
-          const t = triangles[i]; // Cell vertex.
-          if (index[t * 2] !== index[t * 2 + 1]) continue; // Already connected.
-          const e0 = index[t * 2] = e;
-          let j = i;
-
-          do { // Walk forward.
-            edges[e++] = Math.floor(j / 3);
-            j = halfedges[j];
-            if (j === -1) { // Went off the convex hull; walk backward.
-              const e1 = e;
-              j = i;
-              do {
-                j = halfedges[j % 3 === 0 ? j + 2 : j - 1];
-                if (j === -1 || triangles[j] !== t) break;
-                edges[e++] = Math.floor(j / 3);
-              } while (j !== i);
-              if (e1 < e) {
-                edges.subarray(e0, e1).reverse();
-                edges.subarray(e0, e).reverse();
-              }
-              break;
-            }
-            j = j % 3 === 2 ? j - 2 : j + 1;
-            if (triangles[j] !== t) break; // Bad triangulation; break early.
-          } while (j !== i);
-
-          index[t * 2 + 1] = e;
-        }
-
         // Compute circumcenters.
@@ -581,7 +548,11 @@ for (let i = 0, j = 0, n = triangles.length; i < n; i += 3, j += 2) {
         // Compute exterior cell rays.
-        for (let n = hull.length, p0, x0, y0, p1 = triangles[hull[n - 1]] * 2, x1 = points[p1], y1 = points[p1 + 1], i = 0; i < n; ++i) {
-          p0 = p1, x0 = x1, y0 = y1, p1 = triangles[hull[i]] * 2, x1 = points[p1], y1 = points[p1 + 1];
-          vectors[p0 * 2 + 2] = vectors[p1 * 2] = y0 - y1;
-          vectors[p0 * 2 + 3] = vectors[p1 * 2 + 1] = x1 - x0;
-        }
+        let node = hull;
+        let p0, p1 = node.i * 4;
+        let x0, x1 = node.x;
+        let y0, y1 = node.y;
+        do {
+          node = node.next, p0 = p1, x0 = x1, y0 = y1, p1 = node.i * 4, x1 = node.x, y1 = node.y;
+          vectors[p0 + 2] = vectors[p1] = y0 - y1;
+          vectors[p0 + 3] = vectors[p1 + 1] = x1 - x0;
+        } while (node !== hull);
       }
@@ -602,10 +573,12 @@ render(context) {
         }
-        for (let i = 0, n = hull.length; i < n; ++i) {
-          const t = Math.floor(hull[i] / 3) * 2;
+        let node = hull;
+        do {
+          node = node.next;
+          const t = Math.floor(node.t / 3) * 2;
           const x = circumcenters[t];
           const y = circumcenters[t + 1];
-          const v = triangles[hull[i]] * 4;
+          const v = node.i * 4;
           const p = this._project(x, y, vectors[v + 2], vectors[v + 3]);
           if (p) this._renderSegment(x, y, p[0], p[1], context);
-        }
+        } while (node !== hull);
         return buffer && buffer.value();
@@ -655,48 +628,17 @@ }
         if ((x = +x, x !== x) || (y = +y, y !== y)) return false;
-        return this._step(i, x, y) === i;
+        return this.delaunay._step(i, x, y) === i;
       }
-      find(x, y, i = 0) {
-        if ((x = +x, x !== x) || (y = +y, y !== y)) return -1;
-        let c;
-        while ((c = this._step(i, x, y)) >= 0 && c !== i) i = c;
-        return c;
-      }
-      _step(i, x, y) {
-        const {delaunay: {points, triangles}, edges, index} = this;
-        if (points.length === 0) return -1; // Empty triangulation.
-        const j0 = index[i * 2];
-        const j1 = index[i * 2 + 1];
-        if (j0 === j1) return -1; // Coincident point.
-        let c = i, k = edges[j0] * 3;
-        let dc = (x - points[c * 2]) ** 2 + (y - points[c * 2 + 1]) ** 2;
-        switch (i) { // Test previous point on triangle (for hull).
-          case triangles[k]: k = triangles[k + 2]; break;
-          case triangles[k + 1]: k = triangles[k]; break;
-          case triangles[k + 2]: k = triangles[k + 1]; break;
-        }
-        let dk = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
-        if (dk < dc) dc = dk, c = k;
-        for (let j = j0; j < j1; ++j) {
-          k = edges[j] * 3;
-          switch (i) { // Test next point on triangle.
-            case triangles[k]: k = triangles[k + 1]; break;
-            case triangles[k + 1]: k = triangles[k + 2]; break;
-            case triangles[k + 2]: k = triangles[k]; break;
-          }
-          dk = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
-          if (dk < dc) dc = dk, c = k;
-        }
-        return c;
-      }
       _cell(i) {
-        const {index, edges, circumcenters} = this;
-        const t0 = index[i * 2];
-        const t1 = index[i * 2 + 1];
-        if (t0 === t1) return null;
-        const points = new Float64Array((t1 - t0) * 2);
-        for (let t = t0, j = 0; t < t1; ++t, j += 2) {
-          const ti = edges[t] * 2;
-          points[j] = circumcenters[ti];
-          points[j + 1] = circumcenters[ti + 1];
-        }
+        const {circumcenters, delaunay: {inedges, halfedges, triangles}} = this;
+        const e0 = inedges[i];
+        if (e0 === -1) return null; // coincident point
+        const points = [];
+        let e = e0;
+        do {
+          const t = Math.floor(e / 3);
+          points.push(circumcenters[t * 2], circumcenters[t * 2 + 1]);
+          e = e % 3 === 2 ? e - 2 : e + 1;
+          if (triangles[e] !== i) break; // bad triangulation
+          e = halfedges[e];
+        } while (e !== e0 && e !== -1);
         return points;
@@ -846,4 +788,19 @@ }
         this.halfedges = halfedges;
-        this.hull = Uint32Array.from(hullIterable(hull));
+        this.hull = hull;
         this.triangles = triangles;
+        const inedges = this.inedges = new Int32Array(points.length / 2).fill(-1);
+        const outedges = this.outedges = new Int32Array(points.length / 2).fill(-1);
+
+        // Compute an index from each point to an (arbitrary) incoming halfedge.
+        for (let e = 0, n = halfedges.length; e < n; ++e) {
+          inedges[triangles[e % 3 === 2 ? e - 2 : e + 1]] = e;
+        }
+
+        // For points on the hull, index both the incoming and outgoing halfedges.
+        let node0, node1 = hull;
+        do {
+          node0 = node1, node1 = node1.next;
+          inedges[node1.i] = node0.t;
+          outedges[node0.i] = node1.t;
+        } while (node1 !== hull);
       }
@@ -853,2 +810,31 @@ voronoi(bounds) {
       }
+      find(x, y, i = 0) {
+        if ((x = +x, x !== x) || (y = +y, y !== y)) return -1;
+        let c;
+        while ((c = this._step(i, x, y)) >= 0 && c !== i) i = c;
+        return c;
+      }
+      _step(i, x, y) {
+        const {points, halfedges, triangles, inedges, outedges} = this;
+        const e0 = inedges[i];
+        if (e0 === -1) return -1; // coincident point
+        let c = i;
+        let dc = (x - points[i * 2]) ** 2 + (y - points[i * 2 + 1]) ** 2;
+        let e = e0;
+        do {
+          const t = triangles[e];
+          const dt = (x - points[t * 2]) ** 2 + (y - points[t * 2 + 1]) ** 2;
+          if (dt < dc) dc = dt, c = t;
+          e = e % 3 === 2 ? e - 2 : e + 1;
+          if (triangles[e] !== i) break; // bad triangulation
+          e = halfedges[e];
+          if (e === -1) {
+            const t = triangles[outedges[i]];
+            const dt = (x - points[t * 2]) ** 2 + (y - points[t * 2 + 1]) ** 2;
+            if (dt < dc) dc = dt, c = t;
+            break;
+          }
+        } while (e !== e0);
+        return c;
+      }
       render(context) {
@@ -880,10 +866,7 @@ const buffer = context == null ? context = new Path : undefined;
         const buffer = context == null ? context = new Path : undefined;
-        const {points, hull, triangles} = this;
-        const n = hull.length;
-        let i0, i1 = triangles[hull[n - 1]] * 2;
-        for (let i = 0; i < n; ++i) {
-          i0 = i1, i1 = triangles[hull[i]] * 2;
-          context.moveTo(points[i0], points[i0 + 1]);
-          context.lineTo(points[i1], points[i1 + 1]);
-        }
+        const {hull} = this;
+        let node = hull;
+        context.moveTo(node.x, node.y);
+        while (node = node.next, node !== hull) context.lineTo(node.x, node.y);
+        context.closePath();
         return buffer && buffer.value();
@@ -947,8 +930,2 @@ }
 
-    function* hullIterable(hull) {
-      let node = hull;
-      do yield node.t;
-      while ((node = node.next) !== hull);
-    }
-
     exports.Delaunay = Delaunay;
@@ -955,0 +932,0 @@ exports.Voronoi = Voronoi;

dist/d3-delaunay.min.js

@@ -1,3 +0,3 @@
-// https://github.com/d3/d3-delaunay Version 3.1.7. Copyright 2018 Observable, Inc.
+// https://github.com/d3/d3-delaunay Version 4.0.0. Copyright 2018 Observable, Inc.
 // https://github.com/mapbox/delaunator Version 2.0.0. 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";function e(t){if(!ArrayBuffer.isView(t))throw new Error("Expected coords to be a typed array.");var e=1/0,a=1/0,u=-1/0,c=-1/0,f=t.length>>1,g=this.ids=new Uint32Array(f);this.coords=t;for(var x=0;x<f;x++){var _=t[2*x],d=t[2*x+1];_<e&&(e=_),d<a&&(a=d),_>u&&(u=_),d>c&&(c=d),g[x]=x}var y,m,v,p=(e+u)/2,w=(a+c)/2,T=1/0;for(x=0;x<f;x++){var b=i(p,w,t[2*x],t[2*x+1]);b<T&&(y=x,T=b)}for(T=1/0,x=0;x<f;x++)x!==y&&(b=i(t[2*y],t[2*y+1],t[2*x],t[2*x+1]))<T&&b>0&&(m=x,T=b);var $=1/0;for(x=0;x<f;x++)if(x!==y&&x!==m){var k=s(t[2*y],t[2*y+1],t[2*m],t[2*m+1],t[2*x],t[2*x+1]);k<$&&(v=x,$=k)}if($===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(n(t[2*y],t[2*y+1],t[2*m],t[2*m+1],t[2*v],t[2*v+1])<0){var M=m;m=v,v=M}var A=t[2*y],P=t[2*y+1],E=t[2*m],S=t[2*m+1],z=t[2*v],F=t[2*v+1],L=function(t,e,i,n,s,r){var h=(i-=t)*i+(n-=e)*n,l=(s-=t)*s+(r-=e)*r,o=i*r-n*s;return{x:t+.5*(r*h-n*l)/o,y:e+.5*(i*l-s*h)/o}}(A,P,E,S,z,F);for(this._cx=L.x,this._cy=L.y,function t(e,i,n,s,r,h){var a,u,c;if(s-n<=20)for(a=n+1;a<=s;a++){for(c=e[a],u=a-1;u>=n&&l(i,e[u],c,r,h)>0;)e[u+1]=e[u--];e[u+1]=c}else{var f=n+s>>1;for(u=s,o(e,f,a=n+1),l(i,e[n],e[s],r,h)>0&&o(e,n,s),l(i,e[a],e[s],r,h)>0&&o(e,a,s),l(i,e[n],e[a],r,h)>0&&o(e,n,a),c=e[a];;){do{a++}while(l(i,e[a],c,r,h)<0);do{u--}while(l(i,e[u],c,r,h)>0);if(u<a)break;o(e,a,u)}e[n+1]=e[u],e[u]=c,s-a+1>=u-n?(t(e,i,a,s,r,h),t(e,i,n,u-1,r,h)):(t(e,i,n,u-1,r,h),t(e,i,a,s,r,h))}}(g,t,0,g.length-1,L.x,L.y),this._hashSize=Math.ceil(Math.sqrt(f)),this._hash=[],x=0;x<this._hashSize;x++)this._hash[x]=null;var j=this.hull=r(t,y);this._hashEdge(j),j.t=0,j=r(t,m,j),this._hashEdge(j),j.t=1,j=r(t,v,j),this._hashEdge(j),j.t=2;var U,I,H=2*f-5,K=this.triangles=new Uint32Array(3*H),B=this.halfedges=new Int32Array(3*H);this.trianglesLen=0,this._addTriangle(y,m,v,-1,-1,-1);for(var C=0;C<g.length;C++)if(_=t[2*(x=g[C])],d=t[2*x+1],!(_===U&&d===I||(U=_,I=d,_===A&&d===P||_===E&&d===S||_===z&&d===F))){var D,V=this._hashKey(_,d),Z=V;do{D=this._hash[Z],Z=(Z+1)%this._hashSize}while((!D||D.removed)&&Z!==V);for(j=D;n(_,d,j.x,j.y,j.next.x,j.next.y)>=0;)if((j=j.next)===D)throw new Error("Something is wrong with the input points.");var q=j===D,N=this._addTriangle(j.i,x,j.next.i,-1,-1,j.t);j.t=N,(j=r(t,x,j)).t=this._legalize(N+2),j.prev.prev.t===B[N+1]&&(j.prev.prev.t=N+2);for(var O=j.next;n(_,d,O.x,O.y,O.next.x,O.next.y)<0;)N=this._addTriangle(O.i,x,O.next.i,O.prev.t,-1,O.t),O.prev.t=this._legalize(N+2),this.hull=h(O),O=O.next;if(q)for(O=j.prev;n(_,d,O.prev.x,O.prev.y,O.x,O.y)<0;)N=this._addTriangle(O.prev.i,x,O.i,-1,O.t,O.prev.t),this._legalize(N+2),O.prev.t=N,this.hull=h(O),O=O.prev;this._hashEdge(j),this._hashEdge(j.prev)}this.triangles=K.subarray(0,this.trianglesLen),this.halfedges=B.subarray(0,this.trianglesLen)}function i(t,e,i,n){var s=t-i,r=e-n;return s*s+r*r}function n(t,e,i,n,s,r){return(n-e)*(s-i)-(i-t)*(r-n)}function s(t,e,i,n,s,r){var h=(i-=t)*i+(n-=e)*n,l=(s-=t)*s+(r-=e)*r;if(0===h||0===l)return 1/0;var o=i*r-n*s;if(0===o)return 1/0;var a=.5*(r*h-n*l)/o,u=.5*(i*l-s*h)/o;return a*a+u*u}function r(t,e,i){var 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 h(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function l(t,e,n,s,r){return i(t[2*e],t[2*e+1],s,r)-i(t[2*n],t[2*n+1],s,r)||t[2*e]-t[2*n]||t[2*e+1]-t[2*n+1]}function o(t,e,i){var n=t[e];t[e]=t[i],t[i]=n}function a(t){return t[0]}function u(t){return t[1]}e.from=function(t,i,n){i||(i=a),n||(n=u);for(var s=t.length,r=new Float64Array(2*s),h=0;h<s;h++){var l=t[h];r[2*h]=i(l),r[2*h+1]=n(l)}return new e(r)},e.prototype={_hashEdge:function(t){this._hash[this._hashKey(t.x,t.y)]=t},_hashKey:function(t,e){var i=t-this._cx,n=e-this._cy,s=1-i/(Math.abs(i)+Math.abs(n));return Math.floor((2+(n<0?-s:s))/4*this._hashSize)},_legalize:function(t){var e,i,n,s,r,h,l,o,a,u,c=this.triangles,f=this.coords,g=this.halfedges,x=g[t],_=t-t%3,d=x-x%3,y=_+(t+1)%3,m=_+(t+2)%3,v=d+(x+2)%3,p=c[m],w=c[t],T=c[y],b=c[v];if(e=f[2*p],i=f[2*p+1],n=f[2*w],s=f[2*w+1],r=f[2*T],h=f[2*T+1],l=f[2*b],o=f[2*b+1],a=(n-=l)*n+(s-=o)*s,u=(r-=l)*r+(h-=o)*h,(e-=l)*(s*u-a*h)-(i-=o)*(n*u-a*r)+(e*e+i*i)*(n*h-s*r)<0){c[t]=b,c[x]=p,this._link(t,g[v]),this._link(x,g[m]),this._link(m,v);var $=d+(x+1)%3;return this._legalize(t),this._legalize($)}return m},_link:function(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)},_addTriangle:function(t,e,i,n,s,r){var h=this.trianglesLen;return this.triangles[h]=t,this.triangles[h+1]=e,this.triangles[h+2]=i,this._link(h,n),this._link(h+1,s),this._link(h+2,r),this.trianglesLen+=3,h}};class c{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)>epsilon||Math.abs(this._y1-s)>epsilon)&&(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 f{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 g{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:r,halfedges:h,hull:l,triangles:o}=this.delaunay=t,a=this.circumcenters=new Float64Array(o.length/3*2),u=this.edges=new Uint32Array(h.length),c=this.index=new Uint32Array(r.length),f=this.vectors=new Float64Array(2*r.length);this.xmax=n,this.xmin=e,this.ymax=s,this.ymin=i;for(let t=0,e=0,i=h.length;t<i;++t){const i=o[t];if(c[2*i]!==c[2*i+1])continue;const n=c[2*i]=e;let s=t;do{if(u[e++]=Math.floor(s/3),-1===(s=h[s])){const r=e;s=t;do{if(-1===(s=h[s%3==0?s+2:s-1])||o[s]!==i)break;u[e++]=Math.floor(s/3)}while(s!==t);r<e&&(u.subarray(n,r).reverse(),u.subarray(n,e).reverse());break}if(o[s=s%3==2?s-2:s+1]!==i)break}while(s!==t);c[2*i+1]=e}for(let t=0,e=0,i=o.length;t<i;t+=3,e+=2){const i=2*o[t],n=2*o[t+1],s=2*o[t+2],h=r[i],l=r[i+1],u=r[n],c=r[n+1],f=r[s],g=r[s+1],x=h-u,_=h-f,d=l-c,y=l-g,m=h*h+l*l,v=m-u*u-c*c,p=m-f*f-g*g,w=2*(_*d-x*y);a[e]=(d*p-y*v)/w,a[e+1]=(_*v-x*p)/w}for(let t,e,i,n=l.length,s=2*o[l[n-1]],h=r[s],a=r[s+1],u=0;u<n;++u)t=s,e=h,i=a,h=r[s=2*o[l[u]]],a=r[s+1],f[2*t+2]=f[2*s]=i-a,f[2*t+3]=f[2*s+1]=h-e}render(t){const e=null==t?t=new c:void 0,{delaunay:{halfedges:i,hull:n,triangles:s},circumcenters:r,vectors:h}=this;for(let e=0,n=i.length;e<n;++e){const n=i[e];if(n<e)continue;const s=2*Math.floor(e/3),h=2*Math.floor(n/3),l=r[s],o=r[s+1],a=r[h],u=r[h+1];this._renderSegment(l,o,a,u,t)}for(let e=0,i=n.length;e<i;++e){const i=2*Math.floor(n[e]/3),l=r[i],o=r[i+1],a=4*s[n[e]],u=this._project(l,o,h[a+2],h[a+3]);u&&this._renderSegment(l,o,u[0],u[1],t)}return e&&e.value()}renderBounds(t){const e=null==t?t=new c: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 c: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 f;return this.renderCell(t,e),e.value()}_renderSegment(t,e,i,n,s){let r;const h=this._regioncode(t,e),l=this._regioncode(i,n);0===h&&0===l?(s.moveTo(t,e),s.lineTo(i,n)):(r=this._clipSegment(t,e,i,n,h,l))&&(s.moveTo(r[0],r[1]),s.lineTo(r[2],r[3]))}contains(t,e,i){return(e=+e)==e&&(i=+i)==i&&this._step(t,e,i)===t}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{delaunay:{points:n,triangles:s},edges:r,index:h}=this;if(0===n.length)return-1;const l=h[2*t],o=h[2*t+1];if(l===o)return-1;let a=t,u=3*r[l],c=(e-n[2*a])**2+(i-n[2*a+1])**2;switch(t){case s[u]:u=s[u+2];break;case s[u+1]:u=s[u];break;case s[u+2]:u=s[u+1]}let f=(e-n[2*u])**2+(i-n[2*u+1])**2;f<c&&(c=f,a=u);for(let h=l;h<o;++h){switch(u=3*r[h],t){case s[u]:u=s[u+1];break;case s[u+1]:u=s[u+2];break;case s[u+2]:u=s[u]}(f=(e-n[2*u])**2+(i-n[2*u+1])**2)<c&&(c=f,a=u)}return a}_cell(t){const{index:e,edges:i,circumcenters:n}=this,s=e[2*t],r=e[2*t+1];if(s===r)return null;const h=new Float64Array(2*(r-s));for(let t=s,e=0;t<r;++t,e+=2){const s=2*i[t];h[e]=n[s],h[e+1]=n[s+1]}return h}_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,r,h,l,o=null,a=e[i-2],u=e[i-1],c=this._regioncode(a,u);for(let f=0;f<i;f+=2)if(n=a,s=u,a=e[f],u=e[f+1],r=c,c=this._regioncode(a,u),0===r&&0===c)h=l,l=0,o?o.push(a,u):o=[a,u];else{let e,i,f,g,x;if(0===r){if(null===(e=this._clipSegment(n,s,a,u,r,c)))continue;[i,f,g,x]=e}else{if(null===(e=this._clipSegment(a,u,n,s,c,r)))continue;[g,x,i,f]=e,h=l,l=this._edgecode(i,f),h&&l&&this._edge(t,h,l,o,o.length),o?o.push(i,f):o=[i,f]}h=l,l=this._edgecode(g,x),h&&l&&this._edge(t,h,l,o,o.length),o?o.push(g,x):o=[g,x]}if(o)h=l,l=this._edgecode(o[0],o[1]),h&&l&&this._edge(t,h,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,r){for(;;){if(0===s&&0===r)return[t,e,i,n];if(s&r)return null;let h,l,o=s||r;8&o?(h=t+(i-t)*(this.ymax-e)/(n-e),l=this.ymax):4&o?(h=t+(i-t)*(this.ymin-e)/(n-e),l=this.ymin):2&o?(l=e+(n-e)*(this.xmax-t)/(i-t),h=this.xmax):(l=e+(n-e)*(this.xmin-t)/(i-t),h=this.xmin),s?(t=h,e=l,s=this._regioncode(t,e)):(i=h,n=l,r=this._regioncode(i,n))}}_clipInfinite(t,e,i,n,s,r){let h,l=Array.from(e);if((h=this._project(l[0],l[1],i,n))&&l.unshift(h[0],h[1]),(h=this._project(l[l.length-2],l[l.length-1],s,r))&&l.push(h[0],h[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,r;switch(e){case 5:e=4;continue;case 4:e=6,i=this.xmax,r=this.ymin;break;case 6:e=2;continue;case 2:e=10,i=this.xmax,r=this.ymax;break;case 10:e=8;continue;case 8:e=9,i=this.xmin,r=this.ymax;break;case 9:e=1;continue;case 1:e=5,i=this.xmin,r=this.ymin}n[s]===i&&n[s+1]===r||!this.contains(t,i,r)||(n.splice(s,0,i,r),s+=2)}return s}_project(t,e,i,n){let s,r,h,l=1/0;if(n<0){if(e<=this.ymin)return null;(s=(this.ymin-e)/n)<l&&(h=this.ymin,r=t+(l=s)*i)}else if(n>0){if(e>=this.ymax)return null;(s=(this.ymax-e)/n)<l&&(h=this.ymax,r=t+(l=s)*i)}if(i>0){if(t>=this.xmax)return null;(s=(this.xmax-t)/i)<l&&(r=this.xmax,h=e+(l=s)*n)}else if(i<0){if(t<=this.xmin)return null;(s=(this.xmin-t)/i)<l&&(r=this.xmin,h=e+(l=s)*n)}return[r,h]}_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 x=2*Math.PI;class _{constructor(t){const{halfedges:i,hull:n,triangles:s}=new e(t);this.points=t,this.halfedges=i,this.hull=Uint32Array.from(function*(t){let e=t;do{yield e.t}while((e=e.next)!==t)}(n)),this.triangles=s}voronoi(t){return new g(this,t)}render(t){const e=null==t?t=new c:void 0,{points:i,halfedges:n,triangles:s}=this;for(let e=0,r=n.length;e<r;++e){const r=n[e];if(r<e)continue;const h=2*s[e],l=2*s[r];t.moveTo(i[h],i[h+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 c:void 0,{points:n}=this;for(let i=0,s=n.length;i<s;i+=2){const s=n[i],r=n[i+1];t.moveTo(s+e,r),t.arc(s,r,e,0,x)}return i&&i.value()}renderHull(t){const e=null==t?t=new c:void 0,{points:i,hull:n,triangles:s}=this,r=n.length;let h,l=2*s[n[r-1]];for(let e=0;e<r;++e)h=l,l=2*s[n[e]],t.moveTo(i[h],i[h+1]),t.lineTo(i[l],i[l+1]);return e&&e.value()}hullPolygon(){const t=new f;return this.renderHull(t),t.value()}renderTriangle(t,e){const i=null==e?e=new c:void 0,{points:n,triangles:s}=this,r=2*s[t*=3],h=2*s[t+1],l=2*s[t+2];return e.moveTo(n[r],n[r+1]),e.lineTo(n[h],n[h+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 f;return this.renderTriangle(t,e),e.value()}}_.from=function(t,e=function(t){return t[0]},i=function(t){return t[1]},n){return new _("length"in t?function(t,e,i,n){const s=t.length,r=new Float64Array(2*s);for(let h=0;h<s;++h){const s=t[h];r[2*h]=e.call(n,s,h,t),r[2*h+1]=i.call(n,s,h,t)}return r}(t,e,i,n):Float64Array.from(function*(t,e,i,n){let s=0;for(const r of t)yield e.call(n,r,s,t),yield i.call(n,r,s,t),++s}(t,e,i,n)))},t.Delaunay=_,t.Voronoi=g,Object.defineProperty(t,"__esModule",{value:!0})});
+!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";function e(t){if(!ArrayBuffer.isView(t))throw new Error("Expected coords to be a typed array.");var e=1/0,a=1/0,u=-1/0,c=-1/0,f=t.length>>1,x=this.ids=new Uint32Array(f);this.coords=t;for(var _=0;_<f;_++){var g=t[2*_],d=t[2*_+1];g<e&&(e=g),d<a&&(a=d),g>u&&(u=g),d>c&&(c=d),x[_]=_}var y,m,v,p=(e+u)/2,w=(a+c)/2,T=1/0;for(_=0;_<f;_++){var $=i(p,w,t[2*_],t[2*_+1]);$<T&&(y=_,T=$)}for(T=1/0,_=0;_<f;_++)_!==y&&($=i(t[2*y],t[2*y+1],t[2*_],t[2*_+1]))<T&&$>0&&(m=_,T=$);var b=1/0;for(_=0;_<f;_++)if(_!==y&&_!==m){var M=s(t[2*y],t[2*y+1],t[2*m],t[2*m+1],t[2*_],t[2*_+1]);M<b&&(v=_,b=M)}if(b===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(n(t[2*y],t[2*y+1],t[2*m],t[2*m+1],t[2*v],t[2*v+1])<0){var P=m;m=v,v=P}var k=t[2*y],A=t[2*y+1],E=t[2*m],S=t[2*m+1],z=t[2*v],F=t[2*v+1],L=function(t,e,i,n,s,r){var h=(i-=t)*i+(n-=e)*n,l=(s-=t)*s+(r-=e)*r,o=i*r-n*s;return{x:t+.5*(r*h-n*l)/o,y:e+.5*(i*l-s*h)/o}}(k,A,E,S,z,F);for(this._cx=L.x,this._cy=L.y,function t(e,i,n,s,r,h){var a,u,c;if(s-n<=20)for(a=n+1;a<=s;a++){for(c=e[a],u=a-1;u>=n&&l(i,e[u],c,r,h)>0;)e[u+1]=e[u--];e[u+1]=c}else{var f=n+s>>1;for(u=s,o(e,f,a=n+1),l(i,e[n],e[s],r,h)>0&&o(e,n,s),l(i,e[a],e[s],r,h)>0&&o(e,a,s),l(i,e[n],e[a],r,h)>0&&o(e,n,a),c=e[a];;){do{a++}while(l(i,e[a],c,r,h)<0);do{u--}while(l(i,e[u],c,r,h)>0);if(u<a)break;o(e,a,u)}e[n+1]=e[u],e[u]=c,s-a+1>=u-n?(t(e,i,a,s,r,h),t(e,i,n,u-1,r,h)):(t(e,i,n,u-1,r,h),t(e,i,a,s,r,h))}}(x,t,0,x.length-1,L.x,L.y),this._hashSize=Math.ceil(Math.sqrt(f)),this._hash=[],_=0;_<this._hashSize;_++)this._hash[_]=null;var j=this.hull=r(t,y);this._hashEdge(j),j.t=0,j=r(t,m,j),this._hashEdge(j),j.t=1,j=r(t,v,j),this._hashEdge(j),j.t=2;var I,H,K=2*f-5,B=this.triangles=new Uint32Array(3*K),C=this.halfedges=new Int32Array(3*K);this.trianglesLen=0,this._addTriangle(y,m,v,-1,-1,-1);for(var D=0;D<x.length;D++)if(g=t[2*(_=x[D])],d=t[2*_+1],!(g===I&&d===H||(I=g,H=d,g===k&&d===A||g===E&&d===S||g===z&&d===F))){var U,V=this._hashKey(g,d),Z=V;do{U=this._hash[Z],Z=(Z+1)%this._hashSize}while((!U||U.removed)&&Z!==V);for(j=U;n(g,d,j.x,j.y,j.next.x,j.next.y)>=0;)if((j=j.next)===U)throw new Error("Something is wrong with the input points.");var q=j===U,N=this._addTriangle(j.i,_,j.next.i,-1,-1,j.t);j.t=N,(j=r(t,_,j)).t=this._legalize(N+2),j.prev.prev.t===C[N+1]&&(j.prev.prev.t=N+2);for(var O=j.next;n(g,d,O.x,O.y,O.next.x,O.next.y)<0;)N=this._addTriangle(O.i,_,O.next.i,O.prev.t,-1,O.t),O.prev.t=this._legalize(N+2),this.hull=h(O),O=O.next;if(q)for(O=j.prev;n(g,d,O.prev.x,O.prev.y,O.x,O.y)<0;)N=this._addTriangle(O.prev.i,_,O.i,-1,O.t,O.prev.t),this._legalize(N+2),O.prev.t=N,this.hull=h(O),O=O.prev;this._hashEdge(j),this._hashEdge(j.prev)}this.triangles=B.subarray(0,this.trianglesLen),this.halfedges=C.subarray(0,this.trianglesLen)}function i(t,e,i,n){var s=t-i,r=e-n;return s*s+r*r}function n(t,e,i,n,s,r){return(n-e)*(s-i)-(i-t)*(r-n)}function s(t,e,i,n,s,r){var h=(i-=t)*i+(n-=e)*n,l=(s-=t)*s+(r-=e)*r;if(0===h||0===l)return 1/0;var o=i*r-n*s;if(0===o)return 1/0;var a=.5*(r*h-n*l)/o,u=.5*(i*l-s*h)/o;return a*a+u*u}function r(t,e,i){var 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 h(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function l(t,e,n,s,r){return i(t[2*e],t[2*e+1],s,r)-i(t[2*n],t[2*n+1],s,r)||t[2*e]-t[2*n]||t[2*e+1]-t[2*n+1]}function o(t,e,i){var n=t[e];t[e]=t[i],t[i]=n}function a(t){return t[0]}function u(t){return t[1]}e.from=function(t,i,n){i||(i=a),n||(n=u);for(var s=t.length,r=new Float64Array(2*s),h=0;h<s;h++){var l=t[h];r[2*h]=i(l),r[2*h+1]=n(l)}return new e(r)},e.prototype={_hashEdge:function(t){this._hash[this._hashKey(t.x,t.y)]=t},_hashKey:function(t,e){var i=t-this._cx,n=e-this._cy,s=1-i/(Math.abs(i)+Math.abs(n));return Math.floor((2+(n<0?-s:s))/4*this._hashSize)},_legalize:function(t){var e,i,n,s,r,h,l,o,a,u,c=this.triangles,f=this.coords,x=this.halfedges,_=x[t],g=t-t%3,d=_-_%3,y=g+(t+1)%3,m=g+(t+2)%3,v=d+(_+2)%3,p=c[m],w=c[t],T=c[y],$=c[v];if(e=f[2*p],i=f[2*p+1],n=f[2*w],s=f[2*w+1],r=f[2*T],h=f[2*T+1],l=f[2*$],o=f[2*$+1],a=(n-=l)*n+(s-=o)*s,u=(r-=l)*r+(h-=o)*h,(e-=l)*(s*u-a*h)-(i-=o)*(n*u-a*r)+(e*e+i*i)*(n*h-s*r)<0){c[t]=$,c[_]=p,this._link(t,x[v]),this._link(_,x[m]),this._link(m,v);var b=d+(_+1)%3;return this._legalize(t),this._legalize(b)}return m},_link:function(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)},_addTriangle:function(t,e,i,n,s,r){var h=this.trianglesLen;return this.triangles[h]=t,this.triangles[h+1]=e,this.triangles[h+2]=i,this._link(h,n),this._link(h+1,s),this._link(h+2,r),this.trianglesLen+=3,h}};class c{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)>epsilon||Math.abs(this._y1-s)>epsilon)&&(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 f{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 x{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:r,hull:h,triangles:l}=this.delaunay=t,o=this.circumcenters=new Float64Array(l.length/3*2),a=this.vectors=new Float64Array(2*r.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],h=r[i],a=r[i+1],u=r[n],c=r[n+1],f=r[s],x=r[s+1],_=h-u,g=h-f,d=a-c,y=a-x,m=h*h+a*a,v=m-u*u-c*c,p=m-f*f-x*x,w=2*(g*d-_*y);o[e]=(d*p-y*v)/w,o[e+1]=(g*v-_*p)/w}let u,c,f,x=h,_=4*x.i,g=x.x,d=x.y;do{u=_,c=g,f=d,_=4*(x=x.next).i,g=x.x,d=x.y,a[u+2]=a[_]=f-d,a[u+3]=a[_+1]=g-c}while(x!==h)}render(t){const e=null==t?t=new c:void 0,{delaunay:{halfedges:i,hull:n,triangles:s},circumcenters:r,vectors:h}=this;for(let e=0,n=i.length;e<n;++e){const n=i[e];if(n<e)continue;const s=2*Math.floor(e/3),h=2*Math.floor(n/3),l=r[s],o=r[s+1],a=r[h],u=r[h+1];this._renderSegment(l,o,a,u,t)}let l=n;do{l=l.next;const e=2*Math.floor(l.t/3),i=r[e],n=r[e+1],s=4*l.i,o=this._project(i,n,h[s+2],h[s+3]);o&&this._renderSegment(i,n,o[0],o[1],t)}while(l!==n);return e&&e.value()}renderBounds(t){const e=null==t?t=new c: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 c: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 f;return this.renderCell(t,e),e.value()}_renderSegment(t,e,i,n,s){let r;const h=this._regioncode(t,e),l=this._regioncode(i,n);0===h&&0===l?(s.moveTo(t,e),s.lineTo(i,n)):(r=this._clipSegment(t,e,i,n,h,l))&&(s.moveTo(r[0],r[1]),s.lineTo(r[2],r[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,r=i[t];if(-1===r)return null;const h=[];let l=r;do{const i=Math.floor(l/3);if(h.push(e[2*i],e[2*i+1]),s[l=l%3==2?l-2:l+1]!==t)break;l=n[l]}while(l!==r&&-1!==l);return h}_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,r,h,l,o=null,a=e[i-2],u=e[i-1],c=this._regioncode(a,u);for(let f=0;f<i;f+=2)if(n=a,s=u,a=e[f],u=e[f+1],r=c,c=this._regioncode(a,u),0===r&&0===c)h=l,l=0,o?o.push(a,u):o=[a,u];else{let e,i,f,x,_;if(0===r){if(null===(e=this._clipSegment(n,s,a,u,r,c)))continue;[i,f,x,_]=e}else{if(null===(e=this._clipSegment(a,u,n,s,c,r)))continue;[x,_,i,f]=e,h=l,l=this._edgecode(i,f),h&&l&&this._edge(t,h,l,o,o.length),o?o.push(i,f):o=[i,f]}h=l,l=this._edgecode(x,_),h&&l&&this._edge(t,h,l,o,o.length),o?o.push(x,_):o=[x,_]}if(o)h=l,l=this._edgecode(o[0],o[1]),h&&l&&this._edge(t,h,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,r){for(;;){if(0===s&&0===r)return[t,e,i,n];if(s&r)return null;let h,l,o=s||r;8&o?(h=t+(i-t)*(this.ymax-e)/(n-e),l=this.ymax):4&o?(h=t+(i-t)*(this.ymin-e)/(n-e),l=this.ymin):2&o?(l=e+(n-e)*(this.xmax-t)/(i-t),h=this.xmax):(l=e+(n-e)*(this.xmin-t)/(i-t),h=this.xmin),s?(t=h,e=l,s=this._regioncode(t,e)):(i=h,n=l,r=this._regioncode(i,n))}}_clipInfinite(t,e,i,n,s,r){let h,l=Array.from(e);if((h=this._project(l[0],l[1],i,n))&&l.unshift(h[0],h[1]),(h=this._project(l[l.length-2],l[l.length-1],s,r))&&l.push(h[0],h[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,r;switch(e){case 5:e=4;continue;case 4:e=6,i=this.xmax,r=this.ymin;break;case 6:e=2;continue;case 2:e=10,i=this.xmax,r=this.ymax;break;case 10:e=8;continue;case 8:e=9,i=this.xmin,r=this.ymax;break;case 9:e=1;continue;case 1:e=5,i=this.xmin,r=this.ymin}n[s]===i&&n[s+1]===r||!this.contains(t,i,r)||(n.splice(s,0,i,r),s+=2)}return s}_project(t,e,i,n){let s,r,h,l=1/0;if(n<0){if(e<=this.ymin)return null;(s=(this.ymin-e)/n)<l&&(h=this.ymin,r=t+(l=s)*i)}else if(n>0){if(e>=this.ymax)return null;(s=(this.ymax-e)/n)<l&&(h=this.ymax,r=t+(l=s)*i)}if(i>0){if(t>=this.xmax)return null;(s=(this.xmax-t)/i)<l&&(r=this.xmax,h=e+(l=s)*n)}else if(i<0){if(t<=this.xmin)return null;(s=(this.xmin-t)/i)<l&&(r=this.xmin,h=e+(l=s)*n)}return[r,h]}_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 r=this.inedges=new Int32Array(t.length/2).fill(-1),h=this.outedges=new Int32Array(t.length/2).fill(-1);for(let t=0,e=i.length;t<e;++t)r[s[t%3==2?t-2:t+1]]=t;let l,o=n;do{l=o,r[(o=o.next).i]=l.t,h[l.i]=o.t}while(o!==n)}voronoi(t){return new x(this,t)}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{points:n,halfedges:s,triangles:r,inedges:h,outedges:l}=this,o=h[t];if(-1===o)return-1;let a=t,u=(e-n[2*t])**2+(i-n[2*t+1])**2,c=o;do{const h=r[c],o=(e-n[2*h])**2+(i-n[2*h+1])**2;if(o<u&&(u=o,a=h),r[c=c%3==2?c-2:c+1]!==t)break;if(-1===(c=s[c])){const s=r[l[t]],h=(e-n[2*s])**2+(i-n[2*s+1])**2;h<u&&(u=h,a=s);break}}while(c!==o);return a}render(t){const e=null==t?t=new c:void 0,{points:i,halfedges:n,triangles:s}=this;for(let e=0,r=n.length;e<r;++e){const r=n[e];if(r<e)continue;const h=2*s[e],l=2*s[r];t.moveTo(i[h],i[h+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 c:void 0,{points:n}=this;for(let i=0,s=n.length;i<s;i+=2){const s=n[i],r=n[i+1];t.moveTo(s+e,r),t.arc(s,r,e,0,_)}return i&&i.value()}renderHull(t){const e=null==t?t=new c: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 f;return this.renderHull(t),t.value()}renderTriangle(t,e){const i=null==e?e=new c:void 0,{points:n,triangles:s}=this,r=2*s[t*=3],h=2*s[t+1],l=2*s[t+2];return e.moveTo(n[r],n[r+1]),e.lineTo(n[h],n[h+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 f;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,r=new Float64Array(2*s);for(let h=0;h<s;++h){const s=t[h];r[2*h]=e.call(n,s,h,t),r[2*h+1]=i.call(n,s,h,t)}return r}(t,e,i,n):Float64Array.from(function*(t,e,i,n){let s=0;for(const r of t)yield e.call(n,r,s,t),yield i.call(n,r,s,t),++s}(t,e,i,n)))},t.Delaunay=g,t.Voronoi=x,Object.defineProperty(t,"__esModule",{value:!0})});

package.json

 {
   "name": "d3-delaunay",
-  "version": "3.1.7",
+  "version": "4.0.0",
   "description": "Compute the Voronoi diagram of a set of two-dimensional points.",
@@ -5,0 +5,0 @@ "keywords": [

README.md

@@ -66,15 +66,4 @@ # d3-delaunay
 
-The convex hull as an a Uint32Array [*i0*, *i1*, …] of triangle vertex indexes. For example, to render the exterior edges of the Delaunay triangulation:
+TODO …
 
-```js
-const {hull, triangles} = delaunay;
-const n = hull.length;
-let i0, i1 = triangles[hull[n - 1]] * 2;
-for (let i = 0; i < n; ++i) {
-  i0 = i1, i1 = triangles[hull[i]] * 2;
-  context.moveTo(points[i0], points[i0 + 1]);
-  context.lineTo(points[i1], points[i1 + 1]);
-}
-```
-
 See also [*delaunay*.renderHull](#delaunay_renderHull).
@@ -99,2 +88,14 @@
 
+<a href="#delaunay_inedges" name="delaunay_inedges">#</a> <i>delaunay</i>.<b>inedges</b>
+
+TODO …
+
+<a href="#delaunay_outedges" name="delaunay_outedges">#</a> <i>delaunay</i>.<b>outedges</b>
+
+TODO …
+
+<a href="#delaunay_find" name="delaunay_find">#</a> <i>delaunay</i>.<b>find</b>(<i>x</i>, <i>y</i>[, <i>i</i>]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")
+
+Returns the index of the input point that is closest to the specified point ⟨*x*, *y*⟩. The search is started at the specified point *i*. If *i* is not specified, it defaults to zero.
+
 <a href="#delaunay_render" name="delaunay_render">#</a> <i>delaunay</i>.<b>render</b>([<i>context</i>]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")
@@ -136,13 +137,5 @@
 
-<a href="#voronoi_edges" name="voronoi_edges">#</a> <i>voronoi</i>.<b>edges</b>
-
-…
-
-<a href="#voronoi_index" name="voronoi_index">#</a> <i>voronoi</i>.<b>index</b>
-
-…
-
 <a href="#voronoi_vectors" name="voronoi_vectors">#</a> <i>voronoi</i>.<b>vectors</b>
 
-…
+An Uint64Array [*vx0*, *vy0*, *wx0*, *wy0*, …] where each non-zero quadruple describes an open (infinite) cell on the outer hull, giving the directions of two open half-lines.
 
@@ -156,6 +149,2 @@ <a href="#voronoi_xmin" name="voronoi_xmin">#</a> <i>voronoi</i>.<b>xmin</b><br>
 
-<a href="#voronoi_find" name="voronoi_find">#</a> <i>voronoi</i>.<b>find</b>(<i>x</i>, <i>y</i>[, <i>i</i>]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js "Source")
-
-Returns the index of the cell that contains the specified point ⟨*x*, *y*⟩. The search is started at the specified point *i*. If *i* is not specified, it defaults to zero. (This method is not affected by the associated Voronoi diagram’s viewport [bounds](#voronoi_xmin).)
-
 <a href="#voronoi_contains" name="voronoi_contains">#</a> <i>voronoi</i>.<b>contains</b>(<i>i</i>, <i>x</i>, <i>y</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/cell.js "Source")
@@ -162,0 +151,0 @@

src/delaunay.js

 import Delaunator from "delaunator";
-import Path from "./path";
-import Polygon from "./polygon";
+import Path from "./path.js";
+import Polygon from "./polygon.js";
 import Voronoi from "./voronoi.js";
@@ -21,4 +21,19 @@
     this.halfedges = halfedges;
-    this.hull = Uint32Array.from(hullIterable(hull));
+    this.hull = hull;
     this.triangles = triangles;
+    const inedges = this.inedges = new Int32Array(points.length / 2).fill(-1);
+    const outedges = this.outedges = new Int32Array(points.length / 2).fill(-1);
+
+    // Compute an index from each point to an (arbitrary) incoming halfedge.
+    for (let e = 0, n = halfedges.length; e < n; ++e) {
+      inedges[triangles[e % 3 === 2 ? e - 2 : e + 1]] = e;
+    }
+
+    // For points on the hull, index both the incoming and outgoing halfedges.
+    let node0, node1 = hull;
+    do {
+      node0 = node1, node1 = node1.next;
+      inedges[node1.i] = node0.t;
+      outedges[node0.i] = node1.t;
+    } while (node1 !== hull);
   }
@@ -28,2 +43,31 @@ voronoi(bounds) {
   }
+  find(x, y, i = 0) {
+    if ((x = +x, x !== x) || (y = +y, y !== y)) return -1;
+    let c;
+    while ((c = this._step(i, x, y)) >= 0 && c !== i) i = c;
+    return c;
+  }
+  _step(i, x, y) {
+    const {points, halfedges, triangles, inedges, outedges} = this;
+    const e0 = inedges[i];
+    if (e0 === -1) return -1; // coincident point
+    let c = i;
+    let dc = (x - points[i * 2]) ** 2 + (y - points[i * 2 + 1]) ** 2;
+    let e = e0;
+    do {
+      const t = triangles[e];
+      const dt = (x - points[t * 2]) ** 2 + (y - points[t * 2 + 1]) ** 2;
+      if (dt < dc) dc = dt, c = t;
+      e = e % 3 === 2 ? e - 2 : e + 1;
+      if (triangles[e] !== i) break; // bad triangulation
+      e = halfedges[e];
+      if (e === -1) {
+        const t = triangles[outedges[i]];
+        const dt = (x - points[t * 2]) ** 2 + (y - points[t * 2 + 1]) ** 2;
+        if (dt < dc) dc = dt, c = t;
+        break;
+      }
+    } while (e !== e0);
+    return c;
+  }
   render(context) {
@@ -55,10 +99,7 @@ const buffer = context == null ? context = new Path : undefined;
     const buffer = context == null ? context = new Path : undefined;
-    const {points, hull, triangles} = this;
-    const n = hull.length;
-    let i0, i1 = triangles[hull[n - 1]] * 2;
-    for (let i = 0; i < n; ++i) {
-      i0 = i1, i1 = triangles[hull[i]] * 2;
-      context.moveTo(points[i0], points[i0 + 1]);
-      context.lineTo(points[i1], points[i1 + 1]);
-    }
+    const {hull} = this;
+    let node = hull;
+    context.moveTo(node.x, node.y);
+    while (node = node.next, node !== hull) context.lineTo(node.x, node.y);
+    context.closePath();
     return buffer && buffer.value();
@@ -121,7 +162,1 @@ }
 }
-
-function* hullIterable(hull) {
-  let node = hull;
-  do yield node.t;
-  while ((node = node.next) !== hull);
-}

src/voronoi.js

@@ -1,3 +0,3 @@
-import Path from "./path";
-import Polygon from "./polygon";
+import Path from "./path.js";
+import Polygon from "./polygon.js";
 
@@ -7,6 +7,4 @@ export default class Voronoi {
     if (!((xmax = +xmax) >= (xmin = +xmin)) || !((ymax = +ymax) >= (ymin = +ymin))) throw new Error("invalid bounds");
-    const {points, halfedges, hull, triangles} = this.delaunay = delaunay;
+    const {points, hull, triangles} = this.delaunay = delaunay;
     const circumcenters = this.circumcenters = new Float64Array(triangles.length / 3 * 2);
-    const edges = this.edges = new Uint32Array(halfedges.length);
-    const index = this.index = new Uint32Array(points.length);
     const vectors = this.vectors = new Float64Array(points.length * 2);
@@ -16,33 +14,2 @@ this.xmax = xmax, this.xmin = xmin;
 
-    // Compute cell topology.
-    for (let i = 0, e = 0, m = halfedges.length; i < m; ++i) {
-      const t = triangles[i]; // Cell vertex.
-      if (index[t * 2] !== index[t * 2 + 1]) continue; // Already connected.
-      const e0 = index[t * 2] = e;
-      let j = i;
-
-      do { // Walk forward.
-        edges[e++] = Math.floor(j / 3);
-        j = halfedges[j];
-        if (j === -1) { // Went off the convex hull; walk backward.
-          const e1 = e;
-          j = i;
-          do {
-            j = halfedges[j % 3 === 0 ? j + 2 : j - 1];
-            if (j === -1 || triangles[j] !== t) break;
-            edges[e++] = Math.floor(j / 3);
-          } while (j !== i);
-          if (e1 < e) {
-            edges.subarray(e0, e1).reverse();
-            edges.subarray(e0, e).reverse();
-          }
-          break;
-        }
-        j = j % 3 === 2 ? j - 2 : j + 1;
-        if (triangles[j] !== t) break; // Bad triangulation; break early.
-      } while (j !== i);
-
-      index[t * 2 + 1] = e;
-    }
-
     // Compute circumcenters.
@@ -72,7 +39,11 @@ for (let i = 0, j = 0, n = triangles.length; i < n; i += 3, j += 2) {
     // Compute exterior cell rays.
-    for (let n = hull.length, p0, x0, y0, p1 = triangles[hull[n - 1]] * 2, x1 = points[p1], y1 = points[p1 + 1], i = 0; i < n; ++i) {
-      p0 = p1, x0 = x1, y0 = y1, p1 = triangles[hull[i]] * 2, x1 = points[p1], y1 = points[p1 + 1];
-      vectors[p0 * 2 + 2] = vectors[p1 * 2] = y0 - y1;
-      vectors[p0 * 2 + 3] = vectors[p1 * 2 + 1] = x1 - x0;
-    }
+    let node = hull;
+    let p0, p1 = node.i * 4;
+    let x0, x1 = node.x;
+    let y0, y1 = node.y;
+    do {
+      node = node.next, p0 = p1, x0 = x1, y0 = y1, p1 = node.i * 4, x1 = node.x, y1 = node.y;
+      vectors[p0 + 2] = vectors[p1] = y0 - y1;
+      vectors[p0 + 3] = vectors[p1 + 1] = x1 - x0;
+    } while (node !== hull);
   }
@@ -93,10 +64,12 @@ render(context) {
     }
-    for (let i = 0, n = hull.length; i < n; ++i) {
-      const t = Math.floor(hull[i] / 3) * 2;
+    let node = hull;
+    do {
+      node = node.next;
+      const t = Math.floor(node.t / 3) * 2;
       const x = circumcenters[t];
       const y = circumcenters[t + 1];
-      const v = triangles[hull[i]] * 4;
+      const v = node.i * 4;
       const p = this._project(x, y, vectors[v + 2], vectors[v + 3]);
       if (p) this._renderSegment(x, y, p[0], p[1], context);
-    }
+    } while (node !== hull);
     return buffer && buffer.value();
@@ -146,48 +119,17 @@ }
     if ((x = +x, x !== x) || (y = +y, y !== y)) return false;
-    return this._step(i, x, y) === i;
+    return this.delaunay._step(i, x, y) === i;
   }
-  find(x, y, i = 0) {
-    if ((x = +x, x !== x) || (y = +y, y !== y)) return -1;
-    let c;
-    while ((c = this._step(i, x, y)) >= 0 && c !== i) i = c;
-    return c;
-  }
-  _step(i, x, y) {
-    const {delaunay: {points, triangles}, edges, index} = this;
-    if (points.length === 0) return -1; // Empty triangulation.
-    const j0 = index[i * 2];
-    const j1 = index[i * 2 + 1];
-    if (j0 === j1) return -1; // Coincident point.
-    let c = i, k = edges[j0] * 3;
-    let dc = (x - points[c * 2]) ** 2 + (y - points[c * 2 + 1]) ** 2;
-    switch (i) { // Test previous point on triangle (for hull).
-      case triangles[k]: k = triangles[k + 2]; break;
-      case triangles[k + 1]: k = triangles[k]; break;
-      case triangles[k + 2]: k = triangles[k + 1]; break;
-    }
-    let dk = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
-    if (dk < dc) dc = dk, c = k;
-    for (let j = j0; j < j1; ++j) {
-      k = edges[j] * 3;
-      switch (i) { // Test next point on triangle.
-        case triangles[k]: k = triangles[k + 1]; break;
-        case triangles[k + 1]: k = triangles[k + 2]; break;
-        case triangles[k + 2]: k = triangles[k]; break;
-      }
-      dk = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
-      if (dk < dc) dc = dk, c = k;
-    }
-    return c;
-  }
   _cell(i) {
-    const {index, edges, circumcenters} = this;
-    const t0 = index[i * 2];
-    const t1 = index[i * 2 + 1];
-    if (t0 === t1) return null;
-    const points = new Float64Array((t1 - t0) * 2);
-    for (let t = t0, j = 0; t < t1; ++t, j += 2) {
-      const ti = edges[t] * 2;
-      points[j] = circumcenters[ti];
-      points[j + 1] = circumcenters[ti + 1];
-    }
+    const {circumcenters, delaunay: {inedges, halfedges, triangles}} = this;
+    const e0 = inedges[i];
+    if (e0 === -1) return null; // coincident point
+    const points = [];
+    let e = e0;
+    do {
+      const t = Math.floor(e / 3);
+      points.push(circumcenters[t * 2], circumcenters[t * 2 + 1]);
+      e = e % 3 === 2 ? e - 2 : e + 1;
+      if (triangles[e] !== i) break; // bad triangulation
+      e = halfedges[e];
+    } while (e !== e0 && e !== -1);
     return points;
@@ -194,0 +136,0 @@ }

No alert changes

Worsened metrics

Total package byte prevSize

75569

decreased by-3.71%

Lines of code

1354

decreased by-3.15%

Number of lines in readme file

167

decreased by-6.18%

No dependency changes