d3-geo-voronoi - npm Package Compare versions

Comparing version 1.5.0 to 1.6.0

dist/d3-geo-voronoi.js

@@ -1,2 +0,2 @@
-// https://github.com/Fil/d3-geo-voronoi Version 1.5.0. Copyright 2019 Philippe Rivière.
+// https://github.com/Fil/d3-geo-voronoi Version 1.6.0. Copyright 2019 Philippe Rivière.
 (function (global, factory) {
@@ -184,8 +184,8 @@ typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports, require('d3-delaunay'), require('d3-geo'), require('d3-array'), require('d3-tricontour')) :
 
-  zeros.forEach(i => (points[i] = [FAR / 2, i]));
+  zeros.forEach(i => (points[i] = [FAR, 0]));
 
   // Add infinite horizon points
-  for (let i = 0; i < 4; i++) {
-    points.push([FAR * cos((i / 2) * pi), FAR * sin((i / 2) * pi)]);
-  }
+  points.push([0,FAR]);
+  points.push([-FAR,0]);
+  points.push([0,-FAR]);
 
@@ -197,8 +197,25 @@ const delaunay = d3Delaunay.Delaunay.from(points);
   // clean up the triangulation
-  const {triangles} = delaunay;
-  for (let i = 0, l = triangles.length; i < l; i++) {
-    if (triangles[i] > points.length - 4 - 1)
+  const {triangles, halfedges, inedges} = delaunay;
+  const degenerate = [];
+  for (let i = 0, l = halfedges.length; i < l; i++) {
+    if (halfedges[i] < 0) {
+      const j = i % 3 == 2 ? i - 2 : i + 1;
+      const k = i % 3 == 0 ? i + 2 : i - 1;
+      const a = halfedges[j];
+      const b = halfedges[k];
+      halfedges[a] = b;
+      halfedges[b] = a;
+      halfedges[j] = halfedges[k] = -1;
+      triangles[i] = triangles[j] = triangles[k] = pivot;
+      inedges[triangles[a]] = a % 3 == 0 ? a + 2 : a - 1;
+      inedges[triangles[b]] = b % 3 == 0 ? b + 2 : b - 1;
+      degenerate.push(Math.min(i,j,k));
+      i += 2 - i % 3;
+    } else if (triangles[i] > points.length - 3 - 1) {
       triangles[i] = pivot;
+    }
   }
-
+  
+  // there should always be 4 degenerate triangles
+  // console.warn(degenerate);
   return delaunay;
@@ -211,2 +228,3 @@ }
   triangles.forEach(tri => {
+    if (tri[0] === tri[1]) return;
     if (excess(tri.map(i => points[i])) < 0) return;
@@ -230,3 +248,3 @@ for (let i = 0, j; i < 3; i++) {
       c = triangles[3 * i + 2];
-    if (a !== b && b !== c && c !== a) {
+    if (a !== b && b !== c) {
       geo_triangles.push([a, c, b]);
@@ -233,0 +251,0 @@ }

dist/d3-geo-voronoi.min.js

@@ -1,1 +0,1 @@
-(function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("d3-delaunay"),require("d3-geo"),require("d3-array"),require("d3-tricontour")):"function"==typeof define&&define.amd?define(["exports","d3-delaunay","d3-geo","d3-array","d3-tricontour"],t):t(e.d3=e.d3||{},e.d3,e.d3,e.d3,e.d3)})(this,function(e,t,n,r,o){"use strict";var i=Math.PI,u=i/2,a=180/i,l=i/180,s=Math.atan2,c=Math.cos,f=Math.max,p=Math.min,d=Math.sin,h=Math.sign||function(e){return e>0?1:e<0?-1:0},g=Math.sqrt;function y(e,t){return e[0]*t[0]+e[1]*t[1]+e[2]*t[2]}function m(e,t){return[e[1]*t[2]-e[2]*t[1],e[2]*t[0]-e[0]*t[2],e[0]*t[1]-e[1]*t[0]]}function v(e,t){return[e[0]+t[0],e[1]+t[1],e[2]+t[2]]}function _(e){var t=g(e[0]*e[0]+e[1]*e[1]+e[2]*e[2]);return[e[0]/t,e[1]/t,e[2]/t]}function b(e){return[s(e[1],e[0])*a,(t=f(-1,p(1,e[2])),(t>1?u:t<-1?-u:Math.asin(t))*a)];var t}function j(e){var t=e[0]*l,n=e[1]*l,r=c(n);return[r*c(t),r*d(t),d(n)]}function M(e){return y((e=e.map(e=>j(e)))[0],m(e[2],e[1]))}function E(e){const o=function(e){if(e.length<2)return{};let r=0;for(;isNaN(e[r][0]+e[r][1])&&r++<e.length;);const o=n.geoRotation(e[r]),u=n.geoStereographic().translate([0,0]).scale(1).rotate(o.invert([180,0])),a=[];let l=1;for(let t=0,n=(e=e.map(u)).length;t<n;t++){let n=e[t][0]**2+e[t][1]**2;!isFinite(n)||n>1e32?a.push(t):n>l&&(l=n)}const s=1e6*g(l);a.forEach(t=>e[t]=[s/2,t]);for(let t=0;t<4;t++)e.push([s*c(t/2*i),s*d(t/2*i)]);const f=t.Delaunay.from(e);f.projection=u;const{triangles:p}=f;for(let t=0,n=p.length;t<n;t++)p[t]>e.length-4-1&&(p[t]=r);return f}(e),u=function(e){const{triangles:t}=e;if(!t)return[];const n=[];for(let e=0,r=t.length/3;e<r;e++){const r=t[3*e],o=t[3*e+1],i=t[3*e+2];r!==o&&o!==i&&i!==r&&n.push([r,i,o])}return n}(o),a=function(e,t){const n={};return 2===t.length?[[0,1]]:(e.forEach(e=>{if(!(M(e.map(e=>t[e]))<0))for(let t,o=0;o<3;o++)t=(o+1)%3,n[r.extent([e[o],e[t]]).join("-")]=!0}),Object.keys(n).map(e=>e.split("-").map(Number)))}(u,e),l=function(e,t){const n=[];return e.forEach((e,t)=>{for(let t=0;t<3;t++){const r=e[t],o=e[(t+1)%3];n[r]=n[r]||[],n[r].push(o)}}),0===e.length&&(2===t?(n[0]=[1],n[1]=[0]):1===t&&(n[0]=[])),n}(u,e.length),s=function(e,t){function n(e,t){let n=e[0]-t[0],r=e[1]-t[1],o=e[2]-t[2];return n*n+r*r+o*o}return function(r,o,i){void 0===i&&(i=0);let u,a,l=i;const s=j([r,o]);do{u=i,i=null,a=n(s,j(t[u])),e[u].forEach(e=>{let r=n(s,j(t[e]));if(r<a)return a=r,i=e,void(l=e)})}while(null!==i);return l}}(l,e),f=function(e,t){return e.map(e=>{const n=e.map(e=>t[e]).map(j);return b(_(v(v(m(n[1],n[0]),m(n[2],n[1])),m(n[0],n[2]))))})}(u,e),{polygons:p,centers:h}=function(e,t,n){const r=[],o=e.slice();if(0===t.length){if(n.length<2)return{polygons:r,centers:o};if(2===n.length){const e=j(n[0]),t=j(n[1]),u=_(v(e,t)),a=_(m(e,t)),l=m(u,a),s=[u,m(u,l),m(m(u,l),l),m(m(m(u,l),l),l)].map(b).map(i);return r.push(s),r.push(s.slice().reverse()),{polygons:r,centers:o}}}function i(e){let n=-1;return o.slice(t.length,1/0).forEach((r,o)=>{r[0]===e[0]&&r[1]===e[1]&&(n=o+t.length)}),n<0&&(n=o.length,o.push(e)),n}return t.forEach((e,t)=>{for(let n=0;n<3;n++){const o=e[n],i=e[(n+1)%3],u=e[(n+2)%3];r[o]=r[o]||[],r[o].push([i,u,t,[o,i,u]])}}),{polygons:r.map(e=>{const t=[e[0][2]];let r=e[0][1];for(let n=1;n<e.length;n++)for(let n=0;n<e.length;n++)if(e[n][0]==r){r=e[n][1],t.push(e[n][2]);break}if(t.length>2)return t;if(2==t.length){const r=x(n[e[0][3][0]],n[e[0][3][1]],o[t[0]]),u=x(n[e[0][3][2]],n[e[0][3][0]],o[t[0]]),a=i(r),l=i(u);return[t[0],l,t[1],a]}}),centers:o}}(f,u,e),y=function(e){const t=[];return e.forEach(e=>{if(!e)return;let n=e[e.length-1];for(let r of e)r>n&&t.push([n,r]),n=r}),t}(p),E=function(e,t){const n={},r=[];e.map(e=>{if(!(M(e.map(e=>t[e>t.length?0:e]))<0))for(let t=0;t<3;t++){let r=[e[t],e[(t+1)%3]],o=`${r[1]}-${r[0]}`;n[o]?delete n[o]:n[r.join("-")]=!0}});const o={};let i;if(Object.keys(n).forEach(e=>{e=e.split("-").map(Number),o[e[0]]=e[1],i=e[0]}),void 0===i)return r;let u=i;do{r.push(u);let e=o[u];o[u]=-1,u=e}while(u>-1&&u!==i);return r}(u,e),F=function(e,t){return function(n){const o={},i={};return e.forEach((e,t)=>{const r=e.join("-");o[r]=n[t],i[r]=!0}),t.forEach(e=>{let t=0,n=-1;for(var u=0;u<3;u++){let i=r.extent([e[u],e[(u+1)%3]]).join("-");o[i]>t&&(t=o[i],n=i)}i[n]=!1}),e.map(e=>i[e.join("-")])}}(a,u);return{delaunay:o,edges:a,triangles:u,centers:h,neighbors:l,polygons:p,mesh:y,hull:E,urquhart:F,find:s}}function x(e,t,n){e=j(e),t=j(t),n=j(n);const r=h(y(m(t,e),n));return b(_(v(e,t)).map(e=>r*e))}e.geoDelaunay=E,e.geoVoronoi=function(e){const t=function(e){if(t.delaunay=null,t._data=e,"object"==typeof t._data&&"FeatureCollection"===t._data.type&&(t._data=t._data.features),"object"==typeof t._data){const e=t._data.map(e=>[t._vx(e),t._vy(e),e]).filter(e=>isFinite(e[0]+e[1]));t.points=e.map(e=>[e[0],e[1]]),t.valid=e.map(e=>e[2]),t.delaunay=E(t.points)}return t};return t._vx=function(e){return"object"==typeof e&&"type"in e?n.geoCentroid(e)[0]:0 in e?e[0]:void 0},t._vy=function(e){return"object"==typeof e&&"type"in e?n.geoCentroid(e)[1]:1 in e?e[1]:void 0},t.x=function(e){return e?(t._vx=e,t):t._vx},t.y=function(e){return e?(t._vy=e,t):t._vy},t.polygons=function(e){if(void 0!==e&&t(e),!t.delaunay)return!1;const n={type:"FeatureCollection",features:[]};return 0===t.valid.length?n:(t.delaunay.polygons.forEach((e,r)=>n.features.push({type:"Feature",geometry:e?{type:"Polygon",coordinates:[[...e,e[0]].map(e=>t.delaunay.centers[e])]}:null,properties:{site:t.valid[r],sitecoordinates:t.points[r],neighbours:t.delaunay.neighbors[r]}})),1===t.valid.length&&n.features.push({type:"Feature",geometry:{type:"Sphere"},properties:{site:t.valid[0],sitecoordinates:t.points[0],neighbours:[]}}),n)},t.triangles=function(e){return void 0!==e&&t(e),!!t.delaunay&&{type:"FeatureCollection",features:t.delaunay.triangles.map((e,n)=>((e=e.map(e=>t.points[e])).center=t.delaunay.centers[n],e)).filter(e=>M(e)>0).map(e=>({type:"Feature",properties:{circumcenter:e.center},geometry:{type:"Polygon",coordinates:[[...e,e[0]]]}}))}},t.links=function(e){if(void 0!==e&&t(e),!t.delaunay)return!1;const r=t.delaunay.edges.map(e=>n.geoDistance(t.points[e[0]],t.points[e[1]])),o=t.delaunay.urquhart(r);return{type:"FeatureCollection",features:t.delaunay.edges.map((e,n)=>({type:"Feature",properties:{source:t.valid[e[0]],target:t.valid[e[1]],length:r[n],urquhart:!!o[n]},geometry:{type:"LineString",coordinates:[t.points[e[0]],t.points[e[1]]]}}))}},t.mesh=function(e){return void 0!==e&&t(e),!!t.delaunay&&{type:"MultiLineString",coordinates:t.delaunay.edges.map(e=>[t.points[e[0]],t.points[e[1]]])}},t.cellMesh=function(e){if(void 0!==e&&t(e),!t.delaunay)return!1;const{centers:n,polygons:r}=t.delaunay,o=[];for(const e of r)if(e)for(let t=e.length,r=e[t-1],i=e[0],u=0;u<t;r=i,i=e[++u])i>r&&o.push([n[r],n[i]]);return{type:"MultiLineString",coordinates:o}},t._found=void 0,t.find=function(e,r,o){if(t._found=t.delaunay.find(e,r,t._found),!o||n.geoDistance([e,r],t.points[t._found])<o)return t._found},t.hull=function(e){void 0!==e&&t(e);const n=t.delaunay.hull,r=t.points;return 0===n.length?null:{type:"Polygon",coordinates:[[...n.map(e=>r[e]),r[n[0]]]]}},e?t(e):t},e.geoContour=function(){let e;return o.tricontour().triangulate((t,n,r)=>(e=E(t.map(e=>[n(e),r(e)]))).delaunay).pointInterpolate((t,r,o)=>{const{points:i,projection:u}=e.delaunay,a=u.invert([i[2*t],i[2*t+1]]),l=u.invert([i[2*r],i[2*r+1]]);return n.geoInterpolate(a,l)(o)}).ringsort(e=>(e.length&&!e[0].reversed&&(e.forEach(e=>e.reverse()),e[0].reversed=!0),[e]))},Object.defineProperty(e,"__esModule",{value:!0})});
+(function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("d3-delaunay"),require("d3-geo"),require("d3-array"),require("d3-tricontour")):"function"==typeof define&&define.amd?define(["exports","d3-delaunay","d3-geo","d3-array","d3-tricontour"],t):t(e.d3=e.d3||{},e.d3,e.d3,e.d3,e.d3)})(this,function(e,t,n,r,o){"use strict";var i=Math.PI,u=i/2,a=180/i,s=i/180,l=Math.atan2,c=Math.cos,f=Math.max,p=Math.min,d=Math.sin,h=Math.sign||function(e){return e>0?1:e<0?-1:0},g=Math.sqrt;function y(e,t){return e[0]*t[0]+e[1]*t[1]+e[2]*t[2]}function m(e,t){return[e[1]*t[2]-e[2]*t[1],e[2]*t[0]-e[0]*t[2],e[0]*t[1]-e[1]*t[0]]}function v(e,t){return[e[0]+t[0],e[1]+t[1],e[2]+t[2]]}function _(e){var t=g(e[0]*e[0]+e[1]*e[1]+e[2]*e[2]);return[e[0]/t,e[1]/t,e[2]/t]}function b(e){return[l(e[1],e[0])*a,(t=f(-1,p(1,e[2])),(t>1?u:t<-1?-u:Math.asin(t))*a)];var t}function j(e){var t=e[0]*s,n=e[1]*s,r=c(n);return[r*c(t),r*d(t),d(n)]}function M(e){return y((e=e.map(e=>j(e)))[0],m(e[2],e[1]))}function E(e){const o=function(e){if(e.length<2)return{};let r=0;for(;isNaN(e[r][0]+e[r][1])&&r++<e.length;);const o=n.geoRotation(e[r]),i=n.geoStereographic().translate([0,0]).scale(1).rotate(o.invert([180,0])),u=[];let a=1;for(let t=0,n=(e=e.map(i)).length;t<n;t++){let n=e[t][0]**2+e[t][1]**2;!isFinite(n)||n>1e32?u.push(t):n>a&&(a=n)}const s=1e6*g(a);u.forEach(t=>e[t]=[s,0]),e.push([0,s]),e.push([-s,0]),e.push([0,-s]);const l=t.Delaunay.from(e);l.projection=i;const{triangles:c,halfedges:f,inedges:p}=l,d=[];for(let t=0,n=f.length;t<n;t++)if(f[t]<0){const e=t%3==2?t-2:t+1,n=t%3==0?t+2:t-1,o=f[e],i=f[n];f[o]=i,f[i]=o,f[e]=f[n]=-1,c[t]=c[e]=c[n]=r,p[c[o]]=o%3==0?o+2:o-1,p[c[i]]=i%3==0?i+2:i-1,d.push(Math.min(t,e,n)),t+=2-t%3}else c[t]>e.length-3-1&&(c[t]=r);return l}(e),i=function(e){const{triangles:t}=e;if(!t)return[];const n=[];for(let e=0,r=t.length/3;e<r;e++){const r=t[3*e],o=t[3*e+1],i=t[3*e+2];r!==o&&o!==i&&n.push([r,i,o])}return n}(o),u=function(e,t){const n={};return 2===t.length?[[0,1]]:(e.forEach(e=>{if(e[0]!==e[1]&&!(M(e.map(e=>t[e]))<0))for(let t,o=0;o<3;o++)t=(o+1)%3,n[r.extent([e[o],e[t]]).join("-")]=!0}),Object.keys(n).map(e=>e.split("-").map(Number)))}(i,e),a=function(e,t){const n=[];return e.forEach((e,t)=>{for(let t=0;t<3;t++){const r=e[t],o=e[(t+1)%3];n[r]=n[r]||[],n[r].push(o)}}),0===e.length&&(2===t?(n[0]=[1],n[1]=[0]):1===t&&(n[0]=[])),n}(i,e.length),s=function(e,t){function n(e,t){let n=e[0]-t[0],r=e[1]-t[1],o=e[2]-t[2];return n*n+r*r+o*o}return function(r,o,i){void 0===i&&(i=0);let u,a,s=i;const l=j([r,o]);do{u=i,i=null,a=n(l,j(t[u])),e[u].forEach(e=>{let r=n(l,j(t[e]));if(r<a)return a=r,i=e,void(s=e)})}while(null!==i);return s}}(a,e),l=function(e,t){return e.map(e=>{const n=e.map(e=>t[e]).map(j);return b(_(v(v(m(n[1],n[0]),m(n[2],n[1])),m(n[0],n[2]))))})}(i,e),{polygons:c,centers:f}=function(e,t,n){const r=[],o=e.slice();if(0===t.length){if(n.length<2)return{polygons:r,centers:o};if(2===n.length){const e=j(n[0]),t=j(n[1]),u=_(v(e,t)),a=_(m(e,t)),s=m(u,a),l=[u,m(u,s),m(m(u,s),s),m(m(m(u,s),s),s)].map(b).map(i);return r.push(l),r.push(l.slice().reverse()),{polygons:r,centers:o}}}function i(e){let n=-1;return o.slice(t.length,1/0).forEach((r,o)=>{r[0]===e[0]&&r[1]===e[1]&&(n=o+t.length)}),n<0&&(n=o.length,o.push(e)),n}return t.forEach((e,t)=>{for(let n=0;n<3;n++){const o=e[n],i=e[(n+1)%3],u=e[(n+2)%3];r[o]=r[o]||[],r[o].push([i,u,t,[o,i,u]])}}),{polygons:r.map(e=>{const t=[e[0][2]];let r=e[0][1];for(let n=1;n<e.length;n++)for(let n=0;n<e.length;n++)if(e[n][0]==r){r=e[n][1],t.push(e[n][2]);break}if(t.length>2)return t;if(2==t.length){const r=x(n[e[0][3][0]],n[e[0][3][1]],o[t[0]]),u=x(n[e[0][3][2]],n[e[0][3][0]],o[t[0]]),a=i(r),s=i(u);return[t[0],s,t[1],a]}}),centers:o}}(l,i,e),p=function(e){const t=[];return e.forEach(e=>{if(!e)return;let n=e[e.length-1];for(let r of e)r>n&&t.push([n,r]),n=r}),t}(c),d=function(e,t){const n={},r=[];e.map(e=>{if(!(M(e.map(e=>t[e>t.length?0:e]))<0))for(let t=0;t<3;t++){let r=[e[t],e[(t+1)%3]],o=`${r[1]}-${r[0]}`;n[o]?delete n[o]:n[r.join("-")]=!0}});const o={};let i;if(Object.keys(n).forEach(e=>{e=e.split("-").map(Number),o[e[0]]=e[1],i=e[0]}),void 0===i)return r;let u=i;do{r.push(u);let e=o[u];o[u]=-1,u=e}while(u>-1&&u!==i);return r}(i,e),h=function(e,t){return function(n){const o={},i={};return e.forEach((e,t)=>{const r=e.join("-");o[r]=n[t],i[r]=!0}),t.forEach(e=>{let t=0,n=-1;for(var u=0;u<3;u++){let i=r.extent([e[u],e[(u+1)%3]]).join("-");o[i]>t&&(t=o[i],n=i)}i[n]=!1}),e.map(e=>i[e.join("-")])}}(u,i);return{delaunay:o,edges:u,triangles:i,centers:f,neighbors:a,polygons:c,mesh:p,hull:d,urquhart:h,find:s}}function x(e,t,n){e=j(e),t=j(t),n=j(n);const r=h(y(m(t,e),n));return b(_(v(e,t)).map(e=>r*e))}e.geoDelaunay=E,e.geoVoronoi=function(e){const t=function(e){if(t.delaunay=null,t._data=e,"object"==typeof t._data&&"FeatureCollection"===t._data.type&&(t._data=t._data.features),"object"==typeof t._data){const e=t._data.map(e=>[t._vx(e),t._vy(e),e]).filter(e=>isFinite(e[0]+e[1]));t.points=e.map(e=>[e[0],e[1]]),t.valid=e.map(e=>e[2]),t.delaunay=E(t.points)}return t};return t._vx=function(e){return"object"==typeof e&&"type"in e?n.geoCentroid(e)[0]:0 in e?e[0]:void 0},t._vy=function(e){return"object"==typeof e&&"type"in e?n.geoCentroid(e)[1]:1 in e?e[1]:void 0},t.x=function(e){return e?(t._vx=e,t):t._vx},t.y=function(e){return e?(t._vy=e,t):t._vy},t.polygons=function(e){if(void 0!==e&&t(e),!t.delaunay)return!1;const n={type:"FeatureCollection",features:[]};return 0===t.valid.length?n:(t.delaunay.polygons.forEach((e,r)=>n.features.push({type:"Feature",geometry:e?{type:"Polygon",coordinates:[[...e,e[0]].map(e=>t.delaunay.centers[e])]}:null,properties:{site:t.valid[r],sitecoordinates:t.points[r],neighbours:t.delaunay.neighbors[r]}})),1===t.valid.length&&n.features.push({type:"Feature",geometry:{type:"Sphere"},properties:{site:t.valid[0],sitecoordinates:t.points[0],neighbours:[]}}),n)},t.triangles=function(e){return void 0!==e&&t(e),!!t.delaunay&&{type:"FeatureCollection",features:t.delaunay.triangles.map((e,n)=>((e=e.map(e=>t.points[e])).center=t.delaunay.centers[n],e)).filter(e=>M(e)>0).map(e=>({type:"Feature",properties:{circumcenter:e.center},geometry:{type:"Polygon",coordinates:[[...e,e[0]]]}}))}},t.links=function(e){if(void 0!==e&&t(e),!t.delaunay)return!1;const r=t.delaunay.edges.map(e=>n.geoDistance(t.points[e[0]],t.points[e[1]])),o=t.delaunay.urquhart(r);return{type:"FeatureCollection",features:t.delaunay.edges.map((e,n)=>({type:"Feature",properties:{source:t.valid[e[0]],target:t.valid[e[1]],length:r[n],urquhart:!!o[n]},geometry:{type:"LineString",coordinates:[t.points[e[0]],t.points[e[1]]]}}))}},t.mesh=function(e){return void 0!==e&&t(e),!!t.delaunay&&{type:"MultiLineString",coordinates:t.delaunay.edges.map(e=>[t.points[e[0]],t.points[e[1]]])}},t.cellMesh=function(e){if(void 0!==e&&t(e),!t.delaunay)return!1;const{centers:n,polygons:r}=t.delaunay,o=[];for(const e of r)if(e)for(let t=e.length,r=e[t-1],i=e[0],u=0;u<t;r=i,i=e[++u])i>r&&o.push([n[r],n[i]]);return{type:"MultiLineString",coordinates:o}},t._found=void 0,t.find=function(e,r,o){if(t._found=t.delaunay.find(e,r,t._found),!o||n.geoDistance([e,r],t.points[t._found])<o)return t._found},t.hull=function(e){void 0!==e&&t(e);const n=t.delaunay.hull,r=t.points;return 0===n.length?null:{type:"Polygon",coordinates:[[...n.map(e=>r[e]),r[n[0]]]]}},e?t(e):t},e.geoContour=function(){let e;return o.tricontour().triangulate((t,n,r)=>(e=E(t.map(e=>[n(e),r(e)]))).delaunay).pointInterpolate((t,r,o)=>{const{points:i,projection:u}=e.delaunay,a=u.invert([i[2*t],i[2*t+1]]),s=u.invert([i[2*r],i[2*r+1]]);return n.geoInterpolate(a,s)(o)}).ringsort(e=>(e.length&&!e[0].reversed&&(e.forEach(e=>e.reverse()),e[0].reversed=!0),[e]))},Object.defineProperty(e,"__esModule",{value:!0})});

package.json

 {
   "name": "d3-geo-voronoi",
-  "version": "1.5.0",
+  "version": "1.6.0",
   "description": "Spherical Voronoi Diagram and Delaunay Triangulation",
@@ -5,0 +5,0 @@ "keywords": [

src/delaunay.js

@@ -140,8 +140,8 @@ //
 
-  zeros.forEach(i => (points[i] = [FAR / 2, i]));
+  zeros.forEach(i => (points[i] = [FAR, 0]));
 
   // Add infinite horizon points
-  for (let i = 0; i < 4; i++) {
-    points.push([FAR * cos((i / 2) * pi), FAR * sin((i / 2) * pi)]);
-  }
+  points.push([0,FAR]);
+  points.push([-FAR,0]);
+  points.push([0,-FAR]);
 
@@ -153,8 +153,25 @@ const delaunay = Delaunay.from(points);
   // clean up the triangulation
-  const {triangles} = delaunay;
-  for (let i = 0, l = triangles.length; i < l; i++) {
-    if (triangles[i] > points.length - 4 - 1)
+  const {triangles, halfedges, inedges} = delaunay;
+  const degenerate = [];
+  for (let i = 0, l = halfedges.length; i < l; i++) {
+    if (halfedges[i] < 0) {
+      const j = i % 3 == 2 ? i - 2 : i + 1;
+      const k = i % 3 == 0 ? i + 2 : i - 1;
+      const a = halfedges[j];
+      const b = halfedges[k];
+      halfedges[a] = b;
+      halfedges[b] = a;
+      halfedges[j] = halfedges[k] = -1;
+      triangles[i] = triangles[j] = triangles[k] = pivot;
+      inedges[triangles[a]] = a % 3 == 0 ? a + 2 : a - 1;
+      inedges[triangles[b]] = b % 3 == 0 ? b + 2 : b - 1;
+      degenerate.push(Math.min(i,j,k));
+      i += 2 - i % 3;
+    } else if (triangles[i] > points.length - 3 - 1) {
       triangles[i] = pivot;
+    }
   }
-
+  
+  // there should always be 4 degenerate triangles
+  // console.warn(degenerate);
   return delaunay;
@@ -167,2 +184,3 @@ }
   triangles.forEach(tri => {
+    if (tri[0] === tri[1]) return;
     if (excess(tri.map(i => points[i])) < 0) return;
@@ -186,3 +204,3 @@ for (let i = 0, j; i < 3; i++) {
       c = triangles[3 * i + 2];
-    if (a !== b && b !== c && c !== a) {
+    if (a !== b && b !== c) {
       geo_triangles.push([a, c, b]);
@@ -189,0 +207,0 @@ }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

78441

increased by1.93%

Lines of code

1836

increased by2%

No dependency changes