delaunator - npm Package Compare versions

Comparing version 2.0.2 to 2.0.3

delaunator.js

@@ -152,2 +152,3 @@ (function (global, factory) {
 
+            start = start.prev;
             e = start;
@@ -224,8 +225,3 @@ while (area(x$1, y$1, e.x, e.y, e.next.x, e.next.y) >= 0) {
     Delaunator.prototype._hashKey = function _hashKey (x, y) {
-        var dx = x - this._cx;
-        var dy = y - this._cy;
-        // use pseudo-angle: a measure that monotonically increases
-        // with real angle, but doesn't require expensive trigonometry
-        var p = 1 - dx / (Math.abs(dx) + Math.abs(dy));
-        return Math.floor((2 + (dy < 0 ? -p : p)) / 4 * this._hashSize);
+        return Math.floor(pseudoAngle(x - this._cx, y - this._cy) * this._hashSize);
     };
@@ -263,2 +259,4 @@
 
+        if (b === -1) { return ar; }
+
         var p0 = triangles[ar];
@@ -327,2 +325,8 @@ var pr = triangles[a];
 
+    // monotonically increases with real angle, but doesn't need expensive trigonometry
+    function pseudoAngle(dx, dy) {
+        var p = dx / (Math.abs(dx) + Math.abs(dy));
+        return (dy > 0 ? 3 - p : 1 + p) / 4; // [0..1)
+    }
+
     function dist(ax, ay, bx, by) {
@@ -329,0 +333,0 @@ var dx = ax - bx;

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,m=(l+v)/2,z=1/0,E=0;E<u;E++){var b=e(w,m,t[2*E],t[2*E+1]);b<z&&(x=E,z=b)}z=1/0;for(var k=0;k<u;k++)if(k!==x){var L=e(t[2*x],t[2*x+1],t[2*k],t[2*k+1]);L<z&&L>0&&(c=k,z=L)}for(var M=1/0,S=0;S<u;S++)if(S!==x&&S!==c){var T=i(t[2*x],t[2*x+1],t[2*c],t[2*c+1],t[2*S],t[2*S+1]);T<M&&(y=S,M=T)}if(M===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(r(t[2*x],t[2*x+1],t[2*c],t[2*c+1],t[2*y],t[2*y+1])<0){var A=c;c=y,y=A}var K=t[2*x],D=t[2*x+1],U=t[2*c],j=t[2*c+1],q=t[2*y],F=t[2*y+1],I=function(t,e,r,i,n,h){var s=r-t,a=i-e,o=n-t,l=h-e,f=s*s+a*a,v=o*o+l*l,u=s*l-a*o;return{x:t+.5*(l*f-a*v)/u,y:e+.5*(s*v-o*f)/u}}(K,D,U,j,q,F);this._cx=I.x,this._cy=I.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&&s(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,a(e,u,l=i+1),s(r,e[i],e[n],h,o)>0&&a(e,i,n),s(r,e[l],e[n],h,o)>0&&a(e,l,n),s(r,e[i],e[l],h,o)>0&&a(e,i,l),v=e[l];;){do{l++}while(s(r,e[l],v,h,o)<0);do{f--}while(s(r,e[f],v,h,o)>0);if(f<l)break;a(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,I.x,I.y),this._hashSize=Math.ceil(Math.sqrt(u)),this._hash=[];for(var N=0;N<this._hashSize;N++)this._hash[N]=null;var B=this.hull=n(t,x);this._hashEdge(B),B.t=0,B=n(t,c,B),this._hashEdge(B),B.t=1,B=n(t,y,B),this._hashEdge(B),B.t=2;var C=2*u-5,G=this.triangles=new Uint32Array(3*C),H=this.halfedges=new Int32Array(3*C);this.trianglesLen=0,this._addTriangle(x,c,y,-1,-1,-1);for(var J=0,O=void 0,P=void 0;J<d.length;J++){var Q=d[J],R=t[2*Q],V=t[2*Q+1];if((R!==O||V!==P)&&(O=R,P=V,!(R===K&&V===D||R===U&&V===j||R===q&&V===F))){var W=this._hashKey(R,V),X=W,Y=void 0;do{Y=this._hash[X],X=(X+1)%this._hashSize}while((!Y||Y.removed)&&X!==W);for(B=Y;r(R,V,B.x,B.y,B.next.x,B.next.y)>=0;)if((B=B.next)===Y)throw new Error("Something is wrong with the input points.");var Z=B===Y,$=this._addTriangle(B.i,Q,B.next.i,-1,-1,B.t);B.t=$,(B=n(t,Q,B)).t=this._legalize($+2);for(var tt=B.next;r(R,V,tt.x,tt.y,tt.next.x,tt.next.y)<0;)$=this._addTriangle(tt.i,Q,tt.next.i,tt.prev.t,-1,tt.t),tt.prev.t=this._legalize($+2),this.hull=h(tt),tt=tt.next;if(Z)for(tt=B.prev;r(R,V,tt.prev.x,tt.prev.y,tt.x,tt.y)<0;)$=this._addTriangle(tt.prev.i,Q,tt.i,-1,tt.t,tt.prev.t),this._legalize($+2),tt.prev.t=$,this.hull=h(tt),tt=tt.prev;this._hashEdge(B),this._hashEdge(B.prev)}}this.triangles=G.subarray(0,this.trianglesLen),this.halfedges=H.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)}function i(t,e,r,i,n,h){var s=r-t,a=i-e,o=n-t,l=h-e,f=s*s+a*a,v=o*o+l*l,u=s*l-a*o,d=.5*(l*f-a*v)/u,g=.5*(s*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 s(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 a(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),s=0;s<n;s++){var a=e[s];h[2*s]=r(a),h[2*s+1]=i(a)}return new t(h)},t.prototype._hashEdge=function(t){this._hash[this._hashKey(t.x,t.y)]=t},t.prototype._hashKey=function(t,e){var r=t-this._cx,i=e-this._cy,n=1-r/(Math.abs(r)+Math.abs(i));return Math.floor((2+(i<0?-n:n))/4*this._hashSize)},t.prototype._legalize=function(t){var e,r,i,n,h,s,a,o,l,f,v,u,d,g,_,p,x=this.triangles,c=this.coords,y=this.halfedges,w=y[t],m=t-t%3,z=w-w%3,E=m+(t+1)%3,b=m+(t+2)%3,k=z+(w+2)%3,L=x[b],M=x[t],S=x[E],T=x[k];if(e=c[2*L],r=c[2*L+1],i=c[2*M],n=c[2*M+1],h=c[2*S],s=c[2*S+1],a=c[2*T],o=c[2*T+1],(l=e-a)*((u=n-o)*(p=(d=h-a)*d+(g=s-o)*g)-(_=(v=i-a)*v+u*u)*g)-(f=r-o)*(v*p-_*d)+(l*l+f*f)*(v*g-u*d)<0){x[t]=T,x[w]=L;var A=y[k];if(-1===A){var K=this.hull;do{if(K.t===k){K.t=t;break}K=K.next}while(K!==this.hull)}this._link(t,A),this._link(w,y[b]),this._link(b,k);var D=z+(w+1)%3;return this._legalize(t),this._legalize(D)}return b},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 s=this.trianglesLen;return this.triangles[s]=t,this.triangles[s+1]=e,this.triangles[s+2]=r,this._link(s,i),this._link(s+1,n),this._link(s+2,h),this.trianglesLen+=3,s},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=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 p=t[2*g],_=t[2*g+1];p<o&&(o=p),_<l&&(l=_),p>f&&(f=p),_>v&&(v=_),d[g]=g}for(var x,c,y,w=(o+f)/2,m=(l+v)/2,z=1/0,E=0;E<u;E++){var b=e(w,m,t[2*E],t[2*E+1]);b<z&&(x=E,z=b)}z=1/0;for(var k=0;k<u;k++)if(k!==x){var L=e(t[2*x],t[2*x+1],t[2*k],t[2*k+1]);L<z&&L>0&&(c=k,z=L)}for(var M=1/0,S=0;S<u;S++)if(S!==x&&S!==c){var T=i(t[2*x],t[2*x+1],t[2*c],t[2*c+1],t[2*S],t[2*S+1]);T<M&&(y=S,M=T)}if(M===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(r(t[2*x],t[2*x+1],t[2*c],t[2*c+1],t[2*y],t[2*y+1])<0){var A=c;c=y,y=A}var K=t[2*x],D=t[2*x+1],U=t[2*c],j=t[2*c+1],q=t[2*y],F=t[2*y+1],I=function(t,e,r,i,n,h){var s=r-t,a=i-e,o=n-t,l=h-e,f=s*s+a*a,v=o*o+l*l,u=s*l-a*o;return{x:t+.5*(l*f-a*v)/u,y:e+.5*(s*v-o*f)/u}}(K,D,U,j,q,F);this._cx=I.x,this._cy=I.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&&s(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,a(e,u,l=i+1),s(r,e[i],e[n],h,o)>0&&a(e,i,n),s(r,e[l],e[n],h,o)>0&&a(e,l,n),s(r,e[i],e[l],h,o)>0&&a(e,i,l),v=e[l];;){do{l++}while(s(r,e[l],v,h,o)<0);do{f--}while(s(r,e[f],v,h,o)>0);if(f<l)break;a(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,I.x,I.y),this._hashSize=Math.ceil(Math.sqrt(u)),this._hash=[];for(var N=0;N<this._hashSize;N++)this._hash[N]=null;var B=this.hull=n(t,x);this._hashEdge(B),B.t=0,B=n(t,c,B),this._hashEdge(B),B.t=1,B=n(t,y,B),this._hashEdge(B),B.t=2;var C=2*u-5,G=this.triangles=new Uint32Array(3*C),H=this.halfedges=new Int32Array(3*C);this.trianglesLen=0,this._addTriangle(x,c,y,-1,-1,-1);for(var J=0,O=void 0,P=void 0;J<d.length;J++){var Q=d[J],R=t[2*Q],V=t[2*Q+1];if((R!==O||V!==P)&&(O=R,P=V,!(R===K&&V===D||R===U&&V===j||R===q&&V===F))){var W=this._hashKey(R,V),X=W,Y=void 0;do{Y=this._hash[X],X=(X+1)%this._hashSize}while((!Y||Y.removed)&&X!==W);for(B=Y=Y.prev;r(R,V,B.x,B.y,B.next.x,B.next.y)>=0;)if((B=B.next)===Y)throw new Error("Something is wrong with the input points.");var Z=B===Y,$=this._addTriangle(B.i,Q,B.next.i,-1,-1,B.t);B.t=$,(B=n(t,Q,B)).t=this._legalize($+2);for(var tt=B.next;r(R,V,tt.x,tt.y,tt.next.x,tt.next.y)<0;)$=this._addTriangle(tt.i,Q,tt.next.i,tt.prev.t,-1,tt.t),tt.prev.t=this._legalize($+2),this.hull=h(tt),tt=tt.next;if(Z)for(tt=B.prev;r(R,V,tt.prev.x,tt.prev.y,tt.x,tt.y)<0;)$=this._addTriangle(tt.prev.i,Q,tt.i,-1,tt.t,tt.prev.t),this._legalize($+2),tt.prev.t=$,this.hull=h(tt),tt=tt.prev;this._hashEdge(B),this._hashEdge(B.prev)}}this.triangles=G.subarray(0,this.trianglesLen),this.halfedges=H.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)}function i(t,e,r,i,n,h){var s=r-t,a=i-e,o=n-t,l=h-e,f=s*s+a*a,v=o*o+l*l,u=s*l-a*o,d=.5*(l*f-a*v)/u,g=.5*(s*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 s(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 a(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),s=0;s<n;s++){var a=e[s];h[2*s]=r(a),h[2*s+1]=i(a)}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,s=n-n%3,a=h+(t+1)%3,o=h+(t+2)%3,l=s+(n+2)%3;if(-1===n)return o;var f,v,u,d,g,p,_,x,c,y,w,m,z,E,b,k,L=e[o],M=e[t],S=e[a],T=e[l];if(f=r[2*L],v=r[2*L+1],u=r[2*M],d=r[2*M+1],g=r[2*S],p=r[2*S+1],_=r[2*T],x=r[2*T+1],(c=f-_)*((m=d-x)*(k=(z=g-_)*z+(E=p-x)*E)-(b=(w=u-_)*w+m*m)*E)-(y=v-x)*(w*k-b*z)+(c*c+y*y)*(w*E-m*z)<0){e[t]=T,e[n]=L;var A=i[l];if(-1===A){var K=this.hull;do{if(K.t===l){K.t=t;break}K=K.next}while(K!==this.hull)}this._link(t,A),this._link(n,i[o]),this._link(o,l);var D=s+(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 s=this.trianglesLen;return this.triangles[s]=t,this.triangles[s+1]=e,this.triangles[s+2]=r,this._link(s,i),this._link(s+1,n),this._link(s+2,h),this.trianglesLen+=3,s},t});

index.js

@@ -163,2 +163,3 @@
 
+            start = start.prev;
             e = start;
@@ -219,8 +220,3 @@ while (area(x, y, e.x, e.y, e.next.x, e.next.y) >= 0) {
     _hashKey(x, y) {
-        const dx = x - this._cx;
-        const dy = y - this._cy;
-        // use pseudo-angle: a measure that monotonically increases
-        // with real angle, but doesn't require expensive trigonometry
-        const p = 1 - dx / (Math.abs(dx) + Math.abs(dy));
-        return Math.floor((2 + (dy < 0 ? -p : p)) / 4 * this._hashSize);
+        return Math.floor(pseudoAngle(x - this._cx, y - this._cy) * this._hashSize);
     }
@@ -255,2 +251,4 @@
 
+        if (b === -1) return ar;
+
         const p0 = triangles[ar];
@@ -320,2 +318,8 @@ const pr = triangles[a];
 
+// monotonically increases with real angle, but doesn't need expensive trigonometry
+function pseudoAngle(dx, dy) {
+    const p = dx / (Math.abs(dx) + Math.abs(dy));
+    return (dy > 0 ? 3 - p : 1 + p) / 4; // [0..1)
+}
+
 function dist(ax, ay, bx, by) {
@@ -322,0 +326,0 @@ const dx = ax - bx;

package.json

 {
   "name": "delaunator",
-  "version": "2.0.2",
+  "version": "2.0.3",
   "description": "A really fast JavaScript library for Delaunay triangulation of 2D points",
@@ -30,3 +30,3 @@ "main": "delaunator.js",
     "start": "rollup -cw",
-    "prepublishOnly": "npm test && npm build"
+    "prepublishOnly": "npm test && npm run build"
   },
@@ -33,0 +33,0 @@ "files": [

README.md

@@ -12,4 +12,4 @@ # delaunator
 
+For Voronoi diagram computation, search, traversal and rendering, check out [d3-delaunay](https://github.com/d3/d3-delaunay) which is based on Delaunator.
 
-
 ## Example
@@ -40,4 +40,4 @@
 ```html
-<script src="https://unpkg.com/delaunator@2.0.1/delaunator.min.js"></script> <!-- minified build -->
-<script src="https://unpkg.com/delaunator@2.0.1/delaunator.js"></script> <!-- dev build -->
+<script src="https://unpkg.com/delaunator@2.0.2/delaunator.min.js"></script> <!-- minified build -->
+<script src="https://unpkg.com/delaunator@2.0.2/delaunator.js"></script> <!-- dev build -->
 ```
@@ -44,0 +44,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

40003

increased by0.73%

Lines of code

787

increased by0.51%

No dependency changes