delaunator - npm Package Compare versions

Comparing version 2.0.4 to 2.0.5

delaunator.js

@@ -7,2 +7,4 @@ (function (global, factory) {
 
+    var EPSILON = Math.pow(2, -52);
+
     var Delaunator = function Delaunator(coords) {
@@ -125,11 +127,9 @@ var this$1 = this;
 
-        var xp, yp;
-        for (var i$6 = 0, list = ids; i$6 < list.length; i$6 += 1) {
-            var i$5 = list[i$6];
-
+        for (var k = 0, xp = (void 0), yp = (void 0); k < ids.length; k++) {
+            var i$5 = ids[k];
             var x$2 = coords[2 * i$5];
             var y$2 = coords[2 * i$5 + 1];
 
-            // skip duplicate points
-            if (x$2 === xp && y$2 === yp) { continue; }
+            // skip near-duplicate points
+            if (k > 0 && Math.abs(x$2 - xp) <= EPSILON && Math.abs(y$2 - yp) <= EPSILON) { continue; }
             xp = x$2;
@@ -225,3 +225,3 @@ yp = y$2;
     Delaunator.prototype._hashKey = function _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;
     };
@@ -327,3 +327,3 @@
         var 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]
     }
@@ -330,0 +330,0 @@

delaunator.min.js

@@ -1,1 +0,1 @@
-!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?module.exports=e():"function"==typeof define&&define.amd?define(e):t.Delaunator=e()}(this,function(){"use strict";var t=function(t){var o=1/0,l=1/0,f=-1/0,v=-1/0,u=t.length>>1,d=this.ids=new Uint32Array(u);if(u>0&&"number"!=typeof t[0])throw new Error("Expected coords to contain numbers.");this.coords=t;for(var g=0;g<u;g++){var _=t[2*g],p=t[2*g+1];_<o&&(o=_),p<l&&(l=p),_>f&&(f=_),p>v&&(v=p),d[g]=g}for(var x,c,y,w=(o+f)/2,b=(l+v)/2,k=1/0,z=0;z<u;z++){var m=e(w,b,t[2*z],t[2*z+1]);m<k&&(x=z,k=m)}var E=t[2*x],A=t[2*x+1];k=1/0;for(var L=0;L<u;L++)if(L!==x){var M=e(E,A,t[2*L],t[2*L+1]);M<k&&M>0&&(c=L,k=M)}for(var T=t[2*c],S=t[2*c+1],K=1/0,D=0;D<u;D++)if(D!==x&&D!==c){var U=i(E,A,T,S,t[2*D],t[2*D+1]);U<K&&(y=D,K=U)}var j=t[2*y],q=t[2*y+1];if(K===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(r(E,A,T,S,j,q)){var F=c,I=T,N=S;c=y,T=j,S=q,y=F,j=I,q=N}var B=function(t,e,r,i,n,h){var a=r-t,s=i-e,o=n-t,l=h-e,f=a*a+s*s,v=o*o+l*l,u=a*l-s*o;return{x:t+.5*(l*f-s*v)/u,y:e+.5*(a*v-o*f)/u}}(E,A,T,S,j,q);this._cx=B.x,this._cy=B.y,function t(e,r,i,n,h,o){var l,f,v;if(n-i<=20)for(l=i+1;l<=n;l++){for(v=e[l],f=l-1;f>=i&&a(r,e[f],v,h,o)>0;)e[f+1]=e[f--];e[f+1]=v}else{var u=i+n>>1;for(f=n,s(e,u,l=i+1),a(r,e[i],e[n],h,o)>0&&s(e,i,n),a(r,e[l],e[n],h,o)>0&&s(e,l,n),a(r,e[i],e[l],h,o)>0&&s(e,i,l),v=e[l];;){do{l++}while(a(r,e[l],v,h,o)<0);do{f--}while(a(r,e[f],v,h,o)>0);if(f<l)break;s(e,l,f)}e[i+1]=e[f],e[f]=v,n-l+1>=f-i?(t(e,r,l,n,h,o),t(e,r,i,f-1,h,o)):(t(e,r,i,f-1,h,o),t(e,r,l,n,h,o))}}(d,t,0,d.length-1,B.x,B.y),this._hashSize=Math.ceil(Math.sqrt(u)),this._hash=new Array(this._hashSize);var C=this.hull=n(t,x);this._hashEdge(C),C.t=0,C=n(t,c,C),this._hashEdge(C),C.t=1,C=n(t,y,C),this._hashEdge(C),C.t=2;var G,H,J=2*u-5,O=this.triangles=new Uint32Array(3*J),P=this.halfedges=new Int32Array(3*J);this.trianglesLen=0,this._addTriangle(x,c,y,-1,-1,-1);for(var Q=0,R=d;Q<R.length;Q+=1){var V=R[Q],W=t[2*V],X=t[2*V+1];if((W!==G||X!==H)&&(G=W,H=X,V!==x&&V!==c&&V!==y)){var Y=this._hashKey(W,X),Z=Y,$=void 0;do{$=this._hash[Z],Z=(Z+1)%this._hashSize}while((!$||$.removed)&&Z!==Y);for(C=$=$.prev;!r(W,X,C.x,C.y,C.next.x,C.next.y);)if((C=C.next)===$){C=null;break}if(C){var tt=C===$,et=this._addTriangle(C.i,V,C.next.i,-1,-1,C.t);C.t=et,(C=n(t,V,C)).t=this._legalize(et+2);for(var rt=C.next;r(W,X,rt.x,rt.y,rt.next.x,rt.next.y);)et=this._addTriangle(rt.i,V,rt.next.i,rt.prev.t,-1,rt.t),rt.prev.t=this._legalize(et+2),this.hull=h(rt),rt=rt.next;if(tt)for(rt=C.prev;r(W,X,rt.prev.x,rt.prev.y,rt.x,rt.y);)et=this._addTriangle(rt.prev.i,V,rt.i,-1,rt.t,rt.prev.t),this._legalize(et+2),rt.prev.t=et,this.hull=h(rt),rt=rt.prev;this._hashEdge(C),this._hashEdge(C.prev)}}}this.triangles=O.subarray(0,this.trianglesLen),this.halfedges=P.subarray(0,this.trianglesLen)};function e(t,e,r,i){var n=t-r,h=e-i;return n*n+h*h}function r(t,e,r,i,n,h){return(i-e)*(n-r)-(r-t)*(h-i)<0}function i(t,e,r,i,n,h){var a=r-t,s=i-e,o=n-t,l=h-e,f=a*a+s*s,v=o*o+l*l,u=a*l-s*o,d=.5*(l*f-s*v)/u,g=.5*(a*v-o*f)/u;return f&&v&&u&&d*d+g*g||1/0}function n(t,e,r){var i={i:e,x:t[2*e],y:t[2*e+1],t:0,prev:null,next:null,removed:!1};return r?(i.next=r.next,i.prev=r,r.next.prev=i,r.next=i):(i.prev=i,i.next=i),i}function h(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function a(t,r,i,n,h){return e(t[2*r],t[2*r+1],n,h)-e(t[2*i],t[2*i+1],n,h)||t[2*r]-t[2*i]||t[2*r+1]-t[2*i+1]}function s(t,e,r){var i=t[e];t[e]=t[r],t[r]=i}function o(t){return t[0]}function l(t){return t[1]}return t.from=function(e,r,i){r||(r=o),i||(i=l);for(var n=e.length,h=new Float64Array(2*n),a=0;a<n;a++){var s=e[a];h[2*a]=r(s),h[2*a+1]=i(s)}return new t(h)},t.prototype._hashEdge=function(t){this._hash[this._hashKey(t.x,t.y)]=t},t.prototype._hashKey=function(t,e){return Math.floor((r=t-this._cx,i=e-this._cy,n=r/(Math.abs(r)+Math.abs(i)),(i>0?3-n:1+n)/4*this._hashSize));var r,i,n},t.prototype._legalize=function(t){var e=this.triangles,r=this.coords,i=this.halfedges,n=i[t],h=t-t%3,a=n-n%3,s=h+(t+1)%3,o=h+(t+2)%3,l=a+(n+2)%3;if(-1===n)return o;var f,v,u,d,g,_,p,x,c,y,w,b,k,z,m,E,A=e[o],L=e[t],M=e[s],T=e[l];if(f=r[2*A],v=r[2*A+1],u=r[2*L],d=r[2*L+1],g=r[2*M],_=r[2*M+1],p=r[2*T],x=r[2*T+1],(c=f-p)*((b=d-x)*(E=(k=g-p)*k+(z=_-x)*z)-(m=(w=u-p)*w+b*b)*z)-(y=v-x)*(w*E-m*k)+(c*c+y*y)*(w*z-b*k)<0){e[t]=T,e[n]=A;var S=i[l];if(-1===S){var K=this.hull;do{if(K.t===l){K.t=t;break}K=K.next}while(K!==this.hull)}this._link(t,S),this._link(n,i[o]),this._link(o,l);var D=a+(n+1)%3;return this._legalize(t),this._legalize(D)}return o},t.prototype._link=function(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)},t.prototype._addTriangle=function(t,e,r,i,n,h){var a=this.trianglesLen;return this.triangles[a]=t,this.triangles[a+1]=e,this.triangles[a+2]=r,this._link(a,i),this._link(a+1,n),this._link(a+2,h),this.trianglesLen+=3,a},t});
+!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?module.exports=e():"function"==typeof define&&define.amd?define(e):t.Delaunator=e()}(this,function(){"use strict";var t=Math.pow(2,-52),e=function(e){var l=1/0,f=1/0,v=-1/0,u=-1/0,d=e.length>>1,_=this.ids=new Uint32Array(d);if(d>0&&"number"!=typeof e[0])throw new Error("Expected coords to contain numbers.");this.coords=e;for(var g=0;g<d;g++){var p=e[2*g],x=e[2*g+1];p<l&&(l=p),x<f&&(f=x),p>v&&(v=p),x>u&&(u=x),_[g]=g}for(var c,y,w,b=(l+v)/2,z=(f+u)/2,k=1/0,m=0;m<d;m++){var E=r(b,z,e[2*m],e[2*m+1]);E<k&&(c=m,k=E)}var M=e[2*c],A=e[2*c+1];k=1/0;for(var L=0;L<d;L++)if(L!==c){var S=r(M,A,e[2*L],e[2*L+1]);S<k&&S>0&&(y=L,k=S)}for(var T=e[2*y],K=e[2*y+1],D=1/0,U=0;U<d;U++)if(U!==c&&U!==y){var j=n(M,A,T,K,e[2*U],e[2*U+1]);j<D&&(w=U,D=j)}var q=e[2*w],F=e[2*w+1];if(D===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(i(M,A,T,K,q,F)){var I=y,N=T,B=K;y=w,T=q,K=F,w=I,q=N,F=B}var C=function(t,e,r,i,n,h){var a=r-t,s=i-e,o=n-t,l=h-e,f=a*a+s*s,v=o*o+l*l,u=a*l-s*o;return{x:t+.5*(l*f-s*v)/u,y:e+.5*(a*v-o*f)/u}}(M,A,T,K,q,F);this._cx=C.x,this._cy=C.y,function t(e,r,i,n,h,a){var l,f,v;if(n-i<=20)for(l=i+1;l<=n;l++){for(v=e[l],f=l-1;f>=i&&s(r,e[f],v,h,a)>0;)e[f+1]=e[f--];e[f+1]=v}else{var u=i+n>>1;for(f=n,o(e,u,l=i+1),s(r,e[i],e[n],h,a)>0&&o(e,i,n),s(r,e[l],e[n],h,a)>0&&o(e,l,n),s(r,e[i],e[l],h,a)>0&&o(e,i,l),v=e[l];;){do{l++}while(s(r,e[l],v,h,a)<0);do{f--}while(s(r,e[f],v,h,a)>0);if(f<l)break;o(e,l,f)}e[i+1]=e[f],e[f]=v,n-l+1>=f-i?(t(e,r,l,n,h,a),t(e,r,i,f-1,h,a)):(t(e,r,i,f-1,h,a),t(e,r,l,n,h,a))}}(_,e,0,_.length-1,C.x,C.y),this._hashSize=Math.ceil(Math.sqrt(d)),this._hash=new Array(this._hashSize);var G=this.hull=h(e,c);this._hashEdge(G),G.t=0,G=h(e,y,G),this._hashEdge(G),G.t=1,G=h(e,w,G),this._hashEdge(G),G.t=2;var H=2*d-5,J=this.triangles=new Uint32Array(3*H),O=this.halfedges=new Int32Array(3*H);this.trianglesLen=0,this._addTriangle(c,y,w,-1,-1,-1);for(var P=0,Q=void 0,R=void 0;P<_.length;P++){var V=_[P],W=e[2*V],X=e[2*V+1];if(!(P>0&&Math.abs(W-Q)<=t&&Math.abs(X-R)<=t)&&(Q=W,R=X,V!==c&&V!==y&&V!==w)){var Y=this._hashKey(W,X),Z=Y,$=void 0;do{$=this._hash[Z],Z=(Z+1)%this._hashSize}while((!$||$.removed)&&Z!==Y);for(G=$=$.prev;!i(W,X,G.x,G.y,G.next.x,G.next.y);)if((G=G.next)===$){G=null;break}if(G){var tt=G===$,et=this._addTriangle(G.i,V,G.next.i,-1,-1,G.t);G.t=et,(G=h(e,V,G)).t=this._legalize(et+2);for(var rt=G.next;i(W,X,rt.x,rt.y,rt.next.x,rt.next.y);)et=this._addTriangle(rt.i,V,rt.next.i,rt.prev.t,-1,rt.t),rt.prev.t=this._legalize(et+2),this.hull=a(rt),rt=rt.next;if(tt)for(rt=G.prev;i(W,X,rt.prev.x,rt.prev.y,rt.x,rt.y);)et=this._addTriangle(rt.prev.i,V,rt.i,-1,rt.t,rt.prev.t),this._legalize(et+2),rt.prev.t=et,this.hull=a(rt),rt=rt.prev;this._hashEdge(G),this._hashEdge(G.prev)}}}this.triangles=J.subarray(0,this.trianglesLen),this.halfedges=O.subarray(0,this.trianglesLen)};function r(t,e,r,i){var n=t-r,h=e-i;return n*n+h*h}function i(t,e,r,i,n,h){return(i-e)*(n-r)-(r-t)*(h-i)<0}function n(t,e,r,i,n,h){var a=r-t,s=i-e,o=n-t,l=h-e,f=a*a+s*s,v=o*o+l*l,u=a*l-s*o,d=.5*(l*f-s*v)/u,_=.5*(a*v-o*f)/u;return f&&v&&u&&d*d+_*_||1/0}function h(t,e,r){var i={i:e,x:t[2*e],y:t[2*e+1],t:0,prev:null,next:null,removed:!1};return r?(i.next=r.next,i.prev=r,r.next.prev=i,r.next=i):(i.prev=i,i.next=i),i}function a(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function s(t,e,i,n,h){return r(t[2*e],t[2*e+1],n,h)-r(t[2*i],t[2*i+1],n,h)||t[2*e]-t[2*i]||t[2*e+1]-t[2*i+1]}function o(t,e,r){var i=t[e];t[e]=t[r],t[r]=i}function l(t){return t[0]}function f(t){return t[1]}return e.from=function(t,r,i){r||(r=l),i||(i=f);for(var n=t.length,h=new Float64Array(2*n),a=0;a<n;a++){var s=t[a];h[2*a]=r(s),h[2*a+1]=i(s)}return new e(h)},e.prototype._hashEdge=function(t){this._hash[this._hashKey(t.x,t.y)]=t},e.prototype._hashKey=function(t,e){return Math.floor((r=t-this._cx,i=e-this._cy,n=r/(Math.abs(r)+Math.abs(i)),(i>0?3-n:1+n)/4*this._hashSize))%this._hashSize;var r,i,n},e.prototype._legalize=function(t){var e=this.triangles,r=this.coords,i=this.halfedges,n=i[t],h=t-t%3,a=n-n%3,s=h+(t+1)%3,o=h+(t+2)%3,l=a+(n+2)%3;if(-1===n)return o;var f,v,u,d,_,g,p,x,c,y,w,b,z,k,m,E,M=e[o],A=e[t],L=e[s],S=e[l];if(f=r[2*M],v=r[2*M+1],u=r[2*A],d=r[2*A+1],_=r[2*L],g=r[2*L+1],p=r[2*S],x=r[2*S+1],(c=f-p)*((b=d-x)*(E=(z=_-p)*z+(k=g-x)*k)-(m=(w=u-p)*w+b*b)*k)-(y=v-x)*(w*E-m*z)+(c*c+y*y)*(w*k-b*z)<0){e[t]=S,e[n]=M;var T=i[l];if(-1===T){var K=this.hull;do{if(K.t===l){K.t=t;break}K=K.next}while(K!==this.hull)}this._link(t,T),this._link(n,i[o]),this._link(o,l);var D=a+(n+1)%3;return this._legalize(t),this._legalize(D)}return o},e.prototype._link=function(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)},e.prototype._addTriangle=function(t,e,r,i,n,h){var a=this.trianglesLen;return this.triangles[a]=t,this.triangles[a+1]=e,this.triangles[a+2]=r,this._link(a,i),this._link(a+1,n),this._link(a+2,h),this.trianglesLen+=3,a},e});

index.js

 
+const EPSILON = Math.pow(2, -52);
+
 export default class Delaunator {
@@ -135,9 +137,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;
@@ -217,3 +219,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;
     }
@@ -317,3 +319,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]
 }
@@ -320,0 +322,0 @@

package.json

 {
   "name": "delaunator",
-  "version": "2.0.4",
+  "version": "2.0.5",
   "description": "A really fast JavaScript library for Delaunay triangulation of 2D points",
@@ -24,3 +24,3 @@ "main": "delaunator.js",
   "scripts": {
-    "lint": "eslint index.js test.js bench.js rollup.config.js",
+    "lint": "eslint index.js test.js bench.js rollup.config.js docs/diagrams.js",
     "pretest": "npm run lint",
@@ -39,10 +39,3 @@ "test": "node -r esm test.js",
   "eslintConfig": {
-    "extends": "mourner",
-    "parserOptions": {
-      "sourceType": "module"
-    },
-    "rules": {
-      "no-var": "error",
-      "prefer-const": "error"
-    }
+    "extends": "mourner"
   },
@@ -49,0 +42,0 @@ "keywords": [

README.md

@@ -42,4 +42,4 @@ # delaunator [![Build Status](https://travis-ci.org/mapbox/delaunator.svg?branch=master)](https://travis-ci.org/mapbox/delaunator) [![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
 ```html
-<script src="https://unpkg.com/delaunator@2.0.3/delaunator.min.js"></script> <!-- minified build -->
-<script src="https://unpkg.com/delaunator@2.0.3/delaunator.js"></script> <!-- dev build -->
+<script src="https://unpkg.com/delaunator@2.0.4/delaunator.min.js"></script> <!-- minified build -->
+<script src="https://unpkg.com/delaunator@2.0.4/delaunator.js"></script> <!-- dev build -->
 ```
@@ -92,11 +92,12 @@
 
-&nbsp; | uniform 100k | uniform 1&nbsp;million | gauss 100k | gauss 1&nbsp;million | grid 100k | grid 1&nbsp;million | degen 100k | degen 1&nbsp;million
+&nbsp; | uniform 100k | gauss 100k | grid 100k | degen 100k | uniform 1&nbsp;million | gauss 1&nbsp;million | grid 1&nbsp;million | degen 1&nbsp;million
 :-- | --: | --: | --: | --: | --: | --: | --: | --:
-**delaunator** | 97ms | 1.28s | 70ms | 1s | 81ms | 988ms | 48ms | 917ms
-[faster&#8209;delaunay](https://github.com/Bathlamos/delaunay-triangulation) | 473ms | 4.27s | 411ms | 4.62s | 272ms | 4.3s | 68ms | 810ms
-[incremental&#8209;delaunay](https://github.com/mikolalysenko/incremental-delaunay) | 547ms | 5.9s | 505ms | 6.08s | 172ms | 2.11s | 528ms | 6.09s
-[d3&#8209;voronoi](https://github.com/d3/d3-voronoi) | 972ms | 15.04s | 909ms | 13.86s | 358ms | 5.55s | 720ms | 11.13s
-[delaunay&#8209;fast](https://github.com/ironwallaby/delaunay) | 3.8s | 132s | 4s | 138s | 12.57s | 399s | timeout | timeout
-[delaunay](https://github.com/darkskyapp/delaunay) | 4.85s | 156s | 5.73s | 178s | 15.05s | 326s | timeout | timeout
-[delaunay&#8209;triangulate](https://github.com/mikolalysenko/delaunay-triangulate) | 2.24s | OOM | 2.04s | OOM | OOM | OOM | 1.51s | OOM
+**delaunator** | 97ms | 70ms | 81ms | 48ms | 1.28s | 1s | 988ms | 917ms
+[faster&#8209;delaunay](https://github.com/Bathlamos/delaunay-triangulation) | 473ms | 411ms | 272ms | 68ms | 4.27s | 4.62s | 4.3s | 810ms
+[incremental&#8209;delaunay](https://github.com/mikolalysenko/incremental-delaunay) | 547ms | 505ms | 172ms | 528ms | 5.9s | 6.08s | 2.11s | 6.09s
+[d3&#8209;voronoi](https://github.com/d3/d3-voronoi) | 972ms | 909ms | 358ms | 720ms | 15.04s | 13.86s | 5.55s | 11.13s
+[delaunay&#8209;fast](https://github.com/ironwallaby/delaunay) | 3.8s | 4s | 12.57s | timeout | 132s | 138s | 399s | timeout
+[delaunay](https://github.com/darkskyapp/delaunay) | 4.85s | 5.73s | 15.05s | timeout | 156s | 178s | 326s | timeout
+[delaunay&#8209;triangulate](https://github.com/mikolalysenko/delaunay-triangulate) | 2.24s | 2.04s | OOM | 1.51s | OOM | OOM | OOM | OOM
+[cdt2d](https://github.com/mikolalysenko/cdt2d) | 45s | 51s | 118s | 17s | timeout | timeout | timeout | timeout
 
@@ -103,0 +104,0 @@ ## Papers

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

40494

increased by0.73%

Lines of code

790

increased by0.13%

Number of lines in readme file

109

increased by0.93%

No dependency changes