Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
d3-quadtree
Advanced tools
d3-quadtree - npm Package Compare versions
Comparing version 0.7.1 to 0.7.2
@@ -7,3 +7,3 @@ (function (global, factory) { | ||
| var version = "0.7.1"; | ||
| var version = "0.7.2"; | ||
@@ -99,10 +99,6 @@ function tree_add(d) { | ||
| var node = this._root, | ||
| parent, | ||
| i, | ||
| x0 = this._x0, | ||
| var x0 = this._x0, | ||
| y0 = this._y0, | ||
| x1 = this._x1, | ||
| y1 = this._y1, | ||
| z = x1 - x0; | ||
| y1 = this._y1; | ||
@@ -119,2 +115,7 @@ // If the quadtree has no extent, initialize them. | ||
| else if (x0 > x || x > x1 || y0 > y || y > y1) { | ||
| var z = x1 - x0, | ||
| node = this._root, | ||
| parent, | ||
| i; | ||
| switch (i = (y < (y0 + y1) / 2) << 1 | (x < (x0 + x1) / 2)) { | ||
@@ -146,2 +147,5 @@ case 0: { | ||
| // If the quadtree covers the point already, just return. | ||
| else return this; | ||
| this._x0 = x0; | ||
@@ -148,0 +152,0 @@ this._y0 = y0; |
@@ -1,1 +0,1 @@ | ||
| !function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i(t.d3_quadtree=t.d3_quadtree||{})}(this,function(t){"use strict";function i(t){var i=+this._x.call(null,t),e=+this._y.call(null,t);return r(this.cover(i,e),i,e,t)}function r(t,i,r,e){if(isNaN(i)||isNaN(r))return t;var n,h,s,o,a,u,l,_,f,y=t._root,x={data:e},c=t._x0,d=t._y0,v=t._x1,p=t._y1;if(!y)return t._root=x,t;for(;y.length;)if((u=i>=(h=(c+v)/2))?c=h:v=h,(l=r>=(s=(d+p)/2))?d=s:p=s,n=y,!(y=y[_=l<<1|u]))return n[_]=x,t;if(o=+t._x.call(null,y.data),a=+t._y.call(null,y.data),i===o&&r===a)return x.next=y,n?n[_]=x:t._root=x,t;do n=n?n[_]=new Array(4):t._root=new Array(4),(u=i>=(h=(c+v)/2))?c=h:v=h,(l=r>=(s=(d+p)/2))?d=s:p=s;while((_=l<<1|u)===(f=(a>=s)<<1|o>=h));return n[f]=y,n[_]=x,t}function e(t){var i,e,n,h,s=t.length,o=new Array(s),a=new Array(s),u=1/0,l=1/0,_=-(1/0),f=-(1/0);for(e=0;s>e;++e)isNaN(n=+this._x.call(null,i=t[e]))||isNaN(h=+this._y.call(null,i))||(o[e]=n,a[e]=h,u>n&&(u=n),n>_&&(_=n),l>h&&(l=h),h>f&&(f=h));for(u>_&&(u=this._x0,_=this._x1),l>f&&(l=this._y0,f=this._y1),this.cover(u,l).cover(_,f),e=0;s>e;++e)r(this,o[e],a[e],t[e]);return this}function n(t,i){if(isNaN(t=+t)||isNaN(i=+i))return this;var r,e,n=this._root,h=this._x0,s=this._y0,o=this._x1,a=this._y1,u=o-h;if(isNaN(h))o=(h=Math.floor(t))+1,a=(s=Math.floor(i))+1;else if(h>t||t>o||s>i||i>a){switch(e=((s+a)/2>i)<<1|(h+o)/2>t){case 0:do r=new Array(4),r[e]=n,n=r;while(u*=2,o=h+u,a=s+u,t>o||i>a);break;case 1:do r=new Array(4),r[e]=n,n=r;while(u*=2,h=o-u,a=s+u,h>t||i>a);break;case 2:do r=new Array(4),r[e]=n,n=r;while(u*=2,o=h+u,s=a-u,t>o||s>i);break;case 3:do r=new Array(4),r[e]=n,n=r;while(u*=2,h=o-u,s=a-u,h>t||s>i)}this._root&&this._root.length&&(this._root=n)}return this._x0=h,this._y0=s,this._x1=o,this._y1=a,this}function h(){var t=[];return this.visit(function(i){if(!i.length)do t.push(i.data);while(i=i.next)}),t}function s(t){return arguments.length?this.cover(+t[0][0],+t[0][1]).cover(+t[1][0],+t[1][1]):isNaN(this._x0)?void 0:[[this._x0,this._y0],[this._x1,this._y1]]}function o(t,i,r,e,n){this.node=t,this.x0=i,this.y0=r,this.x1=e,this.y1=n}function a(t,i){var r,e,n,h,s,a,u,l=1/0,_=this._x0,f=this._y0,y=this._x1,x=this._y1,c=[],d=this._root;for(d&&c.push(new o(d,_,f,y,x));a=c.pop();)if(!(!(d=a.node)||(e=a.x0)>y||(n=a.y0)>x||(h=a.x1)<_||(s=a.y1)<f))if(d.length){var v=(e+h)/2,p=(n+s)/2;c.push(new o(d[3],v,p,h,s),new o(d[2],e,p,v,s),new o(d[1],v,n,h,p),new o(d[0],e,n,v,p)),(u=(i>=p)<<1|t>=v)&&(a=c[c.length-1],c[c.length-1]=c[c.length-1-u],c[c.length-1-u]=a)}else{var w=t-+this._x.call(null,d.data),N=i-+this._y.call(null,d.data),g=w*w+N*N;if(l>g){var A=Math.sqrt(l=g);_=t-A,f=i-A,y=t+A,x=i+A,r=d.data}}return r}function u(t){if(isNaN(h=+this._x.call(null,t))||isNaN(s=+this._y.call(null,t)))return this;var i,r,e,n,h,s,o,a,u,l,_,f,y=this._root,x=this._x0,c=this._y0,d=this._x1,v=this._y1;if(!y)return this;if(y.length)for(;;){if((u=h>=(o=(x+d)/2))?x=o:d=o,(l=s>=(a=(c+v)/2))?c=a:v=a,i=y,!(y=y[_=l<<1|u]))return this;if(!y.length)break;(i[_+1&3]||i[_+2&3]||i[_+3&3])&&(r=i,f=_)}for(;y.data!==t;)if(e=y,!(y=y.next))return this;return(n=y.next)&&delete y.next,e?(n?e.next=n:delete e.next,this):i?(n?i[_]=n:delete i[_],(y=i[0]||i[1]||i[2]||i[3])&&y===(i[3]||i[2]||i[1]||i[0])&&!y.length&&(r?r[f]=y:this._root=y),this):(this._root=n,this)}function l(t){for(var i=0,r=t.length;r>i;++i)this.remove(t[i]);return this}function _(){return this._root}function f(){var t=0;return this.visit(function(i){if(!i.length)do++t;while(i=i.next)}),t}function y(t){var i,r,e,n,h,s,a=[],u=this._root;for(u&&a.push(new o(u,this._x0,this._y0,this._x1,this._y1));i=a.pop();)if(!t(u=i.node,e=i.x0,n=i.y0,h=i.x1,s=i.y1)&&u.length){var l=(e+h)/2,_=(n+s)/2;(r=u[3])&&a.push(new o(r,l,_,h,s)),(r=u[2])&&a.push(new o(r,e,_,l,s)),(r=u[1])&&a.push(new o(r,l,n,h,_)),(r=u[0])&&a.push(new o(r,e,n,l,_))}return this}function x(t){var i,r=[],e=[];for(this._root&&r.push(new o(this._root,this._x0,this._y0,this._x1,this._y1));i=r.pop();){var n=i.node;if(n.length){var h,s=i.x0,a=i.y0,u=i.x1,l=i.y1,_=(s+u)/2,f=(a+l)/2;(h=n[0])&&r.push(new o(h,s,a,_,f)),(h=n[1])&&r.push(new o(h,_,a,u,f)),(h=n[2])&&r.push(new o(h,s,f,_,l)),(h=n[3])&&r.push(new o(h,_,f,u,l))}e.push(i)}for(;i=e.pop();)t(i.node,i.x0,i.y0,i.x1,i.y1);return this}function c(t){return t[0]}function d(t){return arguments.length?(this._x=t,this):this._x}function v(t){return t[1]}function p(t){return arguments.length?(this._y=t,this):this._y}function w(t,i,r){var e=new N(null==i?c:i,null==r?v:r,NaN,NaN,NaN,NaN);return null==t?e:e.addAll(t)}function N(t,i,r,e,n,h){this._x=t,this._y=i,this._x0=r,this._y0=e,this._x1=n,this._y1=h,this._root=void 0}function g(t){for(var i={data:t.data},r=i;t=t.next;)r=r.next={data:t.data};return i}var A="0.7.1",b=w.prototype=N.prototype;b.copy=function(){var t,i,r=new N(this._x,this._y,this._x0,this._y0,this._x1,this._y1),e=this._root;if(!e)return r;if(!e.length)return r._root=g(e),r;for(t=[{source:e,target:r._root=new Array(4)}];e=t.pop();)for(var n=0;4>n;++n)(i=e.source[n])&&(i.length?t.push({source:i,target:e.target[n]=new Array(4)}):e.target[n]=g(i));return r},b.add=i,b.addAll=e,b.cover=n,b.data=h,b.extent=s,b.find=a,b.remove=u,b.removeAll=l,b.root=_,b.size=f,b.visit=y,b.visitAfter=x,b.x=d,b.y=p,t.version=A,t.quadtree=w}); | ||
| !function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i(t.d3_quadtree=t.d3_quadtree||{})}(this,function(t){"use strict";function i(t){var i=+this._x.call(null,t),e=+this._y.call(null,t);return r(this.cover(i,e),i,e,t)}function r(t,i,r,e){if(isNaN(i)||isNaN(r))return t;var n,h,s,o,a,u,l,_,f,y=t._root,x={data:e},c=t._x0,d=t._y0,v=t._x1,p=t._y1;if(!y)return t._root=x,t;for(;y.length;)if((u=i>=(h=(c+v)/2))?c=h:v=h,(l=r>=(s=(d+p)/2))?d=s:p=s,n=y,!(y=y[_=l<<1|u]))return n[_]=x,t;if(o=+t._x.call(null,y.data),a=+t._y.call(null,y.data),i===o&&r===a)return x.next=y,n?n[_]=x:t._root=x,t;do n=n?n[_]=new Array(4):t._root=new Array(4),(u=i>=(h=(c+v)/2))?c=h:v=h,(l=r>=(s=(d+p)/2))?d=s:p=s;while((_=l<<1|u)===(f=(a>=s)<<1|o>=h));return n[f]=y,n[_]=x,t}function e(t){var i,e,n,h,s=t.length,o=new Array(s),a=new Array(s),u=1/0,l=1/0,_=-(1/0),f=-(1/0);for(e=0;s>e;++e)isNaN(n=+this._x.call(null,i=t[e]))||isNaN(h=+this._y.call(null,i))||(o[e]=n,a[e]=h,u>n&&(u=n),n>_&&(_=n),l>h&&(l=h),h>f&&(f=h));for(u>_&&(u=this._x0,_=this._x1),l>f&&(l=this._y0,f=this._y1),this.cover(u,l).cover(_,f),e=0;s>e;++e)r(this,o[e],a[e],t[e]);return this}function n(t,i){if(isNaN(t=+t)||isNaN(i=+i))return this;var r=this._x0,e=this._y0,n=this._x1,h=this._y1;if(isNaN(r))n=(r=Math.floor(t))+1,h=(e=Math.floor(i))+1;else{if(!(r>t||t>n||e>i||i>h))return this;var s,o,a=n-r,u=this._root;switch(o=((e+h)/2>i)<<1|(r+n)/2>t){case 0:do s=new Array(4),s[o]=u,u=s;while(a*=2,n=r+a,h=e+a,t>n||i>h);break;case 1:do s=new Array(4),s[o]=u,u=s;while(a*=2,r=n-a,h=e+a,r>t||i>h);break;case 2:do s=new Array(4),s[o]=u,u=s;while(a*=2,n=r+a,e=h-a,t>n||e>i);break;case 3:do s=new Array(4),s[o]=u,u=s;while(a*=2,r=n-a,e=h-a,r>t||e>i)}this._root&&this._root.length&&(this._root=u)}return this._x0=r,this._y0=e,this._x1=n,this._y1=h,this}function h(){var t=[];return this.visit(function(i){if(!i.length)do t.push(i.data);while(i=i.next)}),t}function s(t){return arguments.length?this.cover(+t[0][0],+t[0][1]).cover(+t[1][0],+t[1][1]):isNaN(this._x0)?void 0:[[this._x0,this._y0],[this._x1,this._y1]]}function o(t,i,r,e,n){this.node=t,this.x0=i,this.y0=r,this.x1=e,this.y1=n}function a(t,i){var r,e,n,h,s,a,u,l=1/0,_=this._x0,f=this._y0,y=this._x1,x=this._y1,c=[],d=this._root;for(d&&c.push(new o(d,_,f,y,x));a=c.pop();)if(!(!(d=a.node)||(e=a.x0)>y||(n=a.y0)>x||(h=a.x1)<_||(s=a.y1)<f))if(d.length){var v=(e+h)/2,p=(n+s)/2;c.push(new o(d[3],v,p,h,s),new o(d[2],e,p,v,s),new o(d[1],v,n,h,p),new o(d[0],e,n,v,p)),(u=(i>=p)<<1|t>=v)&&(a=c[c.length-1],c[c.length-1]=c[c.length-1-u],c[c.length-1-u]=a)}else{var w=t-+this._x.call(null,d.data),N=i-+this._y.call(null,d.data),g=w*w+N*N;if(l>g){var A=Math.sqrt(l=g);_=t-A,f=i-A,y=t+A,x=i+A,r=d.data}}return r}function u(t){if(isNaN(h=+this._x.call(null,t))||isNaN(s=+this._y.call(null,t)))return this;var i,r,e,n,h,s,o,a,u,l,_,f,y=this._root,x=this._x0,c=this._y0,d=this._x1,v=this._y1;if(!y)return this;if(y.length)for(;;){if((u=h>=(o=(x+d)/2))?x=o:d=o,(l=s>=(a=(c+v)/2))?c=a:v=a,i=y,!(y=y[_=l<<1|u]))return this;if(!y.length)break;(i[_+1&3]||i[_+2&3]||i[_+3&3])&&(r=i,f=_)}for(;y.data!==t;)if(e=y,!(y=y.next))return this;return(n=y.next)&&delete y.next,e?(n?e.next=n:delete e.next,this):i?(n?i[_]=n:delete i[_],(y=i[0]||i[1]||i[2]||i[3])&&y===(i[3]||i[2]||i[1]||i[0])&&!y.length&&(r?r[f]=y:this._root=y),this):(this._root=n,this)}function l(t){for(var i=0,r=t.length;r>i;++i)this.remove(t[i]);return this}function _(){return this._root}function f(){var t=0;return this.visit(function(i){if(!i.length)do++t;while(i=i.next)}),t}function y(t){var i,r,e,n,h,s,a=[],u=this._root;for(u&&a.push(new o(u,this._x0,this._y0,this._x1,this._y1));i=a.pop();)if(!t(u=i.node,e=i.x0,n=i.y0,h=i.x1,s=i.y1)&&u.length){var l=(e+h)/2,_=(n+s)/2;(r=u[3])&&a.push(new o(r,l,_,h,s)),(r=u[2])&&a.push(new o(r,e,_,l,s)),(r=u[1])&&a.push(new o(r,l,n,h,_)),(r=u[0])&&a.push(new o(r,e,n,l,_))}return this}function x(t){var i,r=[],e=[];for(this._root&&r.push(new o(this._root,this._x0,this._y0,this._x1,this._y1));i=r.pop();){var n=i.node;if(n.length){var h,s=i.x0,a=i.y0,u=i.x1,l=i.y1,_=(s+u)/2,f=(a+l)/2;(h=n[0])&&r.push(new o(h,s,a,_,f)),(h=n[1])&&r.push(new o(h,_,a,u,f)),(h=n[2])&&r.push(new o(h,s,f,_,l)),(h=n[3])&&r.push(new o(h,_,f,u,l))}e.push(i)}for(;i=e.pop();)t(i.node,i.x0,i.y0,i.x1,i.y1);return this}function c(t){return t[0]}function d(t){return arguments.length?(this._x=t,this):this._x}function v(t){return t[1]}function p(t){return arguments.length?(this._y=t,this):this._y}function w(t,i,r){var e=new N(null==i?c:i,null==r?v:r,NaN,NaN,NaN,NaN);return null==t?e:e.addAll(t)}function N(t,i,r,e,n,h){this._x=t,this._y=i,this._x0=r,this._y0=e,this._x1=n,this._y1=h,this._root=void 0}function g(t){for(var i={data:t.data},r=i;t=t.next;)r=r.next={data:t.data};return i}var A="0.7.2",b=w.prototype=N.prototype;b.copy=function(){var t,i,r=new N(this._x,this._y,this._x0,this._y0,this._x1,this._y1),e=this._root;if(!e)return r;if(!e.length)return r._root=g(e),r;for(t=[{source:e,target:r._root=new Array(4)}];e=t.pop();)for(var n=0;4>n;++n)(i=e.source[n])&&(i.length?t.push({source:i,target:e.target[n]=new Array(4)}):e.target[n]=g(i));return r},b.add=i,b.addAll=e,b.cover=n,b.data=h,b.extent=s,b.find=a,b.remove=u,b.removeAll=l,b.root=_,b.size=f,b.visit=y,b.visitAfter=x,b.x=d,b.y=p,t.version=A,t.quadtree=w}); |
| export var name = "d3-quadtree"; | ||
| export var version = "0.7.1"; | ||
| export var version = "0.7.2"; | ||
| export var description = "Two-dimensional recursive spatial subdivision."; | ||
@@ -11,2 +11,2 @@ export var keywords = ["d3","quadtree"]; | ||
| export var scripts = {"pretest":"rm -rf build && mkdir build && json2module package.json > build/package.js && rollup -f umd -n d3_quadtree -o build/d3-quadtree.js -- index.js","test":"tape 'test/**/*-test.js' && eslint index.js src","prepublish":"npm run test && uglifyjs build/d3-quadtree.js -c -m -o build/d3-quadtree.min.js","postpublish":"VERSION=`node -e 'console.log(require(\"./package.json\").version)'`; git push && git push --tags && cp build/d3-quadtree.js ../d3.github.com/d3-quadtree.v0.7.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.7.min.js && cd ../d3.github.com && git add d3-quadtree.v0.7.js d3-quadtree.v0.7.min.js && git commit -m \"d3-quadtree ${VERSION}\" && git push && cd - && zip -j build/d3-quadtree.zip -- LICENSE README.md build/d3-quadtree.js build/d3-quadtree.min.js"}; | ||
| export var devDependencies = {"d3-array":"0.7","json2module":"0.0","rollup":"0.25","tape":"4","uglify-js":"2"}; | ||
| export var devDependencies = {"d3-array":"0.7","json2module":"0.0","rollup":"0.26","tape":"4","uglify-js":"2"}; |
| { | ||
| "name": "d3-quadtree", | ||
| "version": "0.7.1", | ||
| "version": "0.7.2", | ||
| "description": "Two-dimensional recursive spatial subdivision.", | ||
@@ -30,3 +30,3 @@ "keywords": [ | ||
| "json2module": "0.0", | ||
| "rollup": "0.25", | ||
| "rollup": "0.26", | ||
| "tape": "4", | ||
@@ -33,0 +33,0 @@ "uglify-js": "2" |
@@ -77,3 +77,3 @@ # d3-quadtree | ||
| Expands the quadtree to cover the specified point ⟨*x*,*y*⟩, and returns the quadtree. If the quadtree’s extent already covers the specified point, this method does nothing. If the quadtree has an extent, the extent is repeatedly doubled to cover the specified point, wrapping the [root](#quadtree_root) [node](#nodes) as necessary; if the quadtree is empty, the extent is initialized to the extent [[*x0*, *y0*], [*x1*, *y1*]] where *x0* = ⌊*x*⌋, *y0* = ⌊*y*⌋, *x1* = ⌈*x*⌉, and *y1* = ⌈*y*⌉. (Rounding is necessary such that if the extent is later doubled, the boundaries of existing quadrants do not change due to floating point error.) | ||
| Expands the quadtree to cover the specified point ⟨*x*,*y*⟩, and returns the quadtree. If the quadtree’s extent already covers the specified point, this method does nothing. If the quadtree has an extent, the extent is repeatedly doubled to cover the specified point, wrapping the [root](#quadtree_root) [node](#nodes) as necessary; if the quadtree is empty, the extent is initialized to the extent [[⌊*x*⌋, ⌊*y*⌋], [⌈*x*⌉, ⌈*y*⌉]]. (Rounding is necessary such that if the extent is later doubled, the boundaries of existing quadrants do not change due to floating point error.) | ||
@@ -80,0 +80,0 @@ <a name="quadtree_add" href="#quadtree_add">#</a> <i>quadtree</i>.<b>add</b>(<i>datum</i>) |
| export default function(x, y) { | ||
| if (isNaN(x = +x) || isNaN(y = +y)) return this; // ignore invalid points | ||
| var node = this._root, | ||
| parent, | ||
| i, | ||
| x0 = this._x0, | ||
| var x0 = this._x0, | ||
| y0 = this._y0, | ||
| x1 = this._x1, | ||
| y1 = this._y1, | ||
| z = x1 - x0; | ||
| y1 = this._y1; | ||
@@ -23,2 +19,7 @@ // If the quadtree has no extent, initialize them. | ||
| else if (x0 > x || x > x1 || y0 > y || y > y1) { | ||
| var z = x1 - x0, | ||
| node = this._root, | ||
| parent, | ||
| i; | ||
| switch (i = (y < (y0 + y1) / 2) << 1 | (x < (x0 + x1) / 2)) { | ||
@@ -50,2 +51,5 @@ case 0: { | ||
| // If the quadtree covers the point already, just return. | ||
| else return this; | ||
| this._x0 = x0; | ||
@@ -52,0 +56,0 @@ this._y0 = y0; |
New alerts
License Policy Violation
LicenseThis 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
LicenseThis 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
- increased by0.31%
45560
- Lines of code
- increased by0.54%
750
No dependency changes