d3-quadtree - npm Package Compare versions

Comparing version 0.7.2 to 0.7.3

build/d3-quadtree.js

@@ -7,3 +7,3 @@ (function (global, factory) {
 
-  var version = "0.7.2";
+  var version = "0.7.3";
 
@@ -177,5 +177,4 @@ function tree_add(d) {
 
-  function tree_find(x, y) {
-    var minDistance2 = Infinity,
-        minPoint,
+  function tree_find(x, y, radius) {
+    var data,
         x0 = this._x0,
@@ -195,2 +194,8 @@ y0 = this._y0,
     if (node) quads.push(new Quad(node, x0, y0, x3, y3));
+    if (radius == null) radius = Infinity;
+    else {
+      x0 = x - radius, y0 = y - radius;
+      x3 = x + radius, y3 = y + radius;
+      radius *= radius;
+    }
 
@@ -231,7 +236,7 @@ while (q = quads.pop()) {
             d2 = dx * dx + dy * dy;
-        if (d2 < minDistance2) {
-          var d = Math.sqrt(minDistance2 = d2);
+        if (d2 < radius) {
+          var d = Math.sqrt(radius = d2);
           x0 = x - d, y0 = y - d;
           x3 = x + d, y3 = y + d;
-          minPoint = node.data;
+          data = node.data;
         }
@@ -241,3 +246,3 @@ }
 
-    return minPoint;
+    return data;
   }
@@ -244,0 +249,0 @@

build/d3-quadtree.min.js

@@ -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=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});
+!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,r){var e,n,h,s,a,u,l,_=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)),null==r?r=1/0:(_=t-r,f=i-r,y=t+r,x=i+r,r*=r);u=c.pop();)if(!(!(d=u.node)||(n=u.x0)>y||(h=u.y0)>x||(s=u.x1)<_||(a=u.y1)<f))if(d.length){var v=(n+s)/2,p=(h+a)/2;c.push(new o(d[3],v,p,s,a),new o(d[2],n,p,v,a),new o(d[1],v,h,s,p),new o(d[0],n,h,v,p)),(l=(i>=p)<<1|t>=v)&&(u=c[c.length-1],c[c.length-1]=c[c.length-1-l],c[c.length-1-l]=u)}else{var w=t-+this._x.call(null,d.data),N=i-+this._y.call(null,d.data),g=w*w+N*N;if(r>g){var A=Math.sqrt(r=g);_=t-A,f=i-A,y=t+A,x=i+A,e=d.data}}return e}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.3",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});

build/package.js

 export var name = "d3-quadtree";
-export var version = "0.7.2";
+export var version = "0.7.3";
 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.26","tape":"4","uglify-js":"2"};
+export var devDependencies = {"d3-array":"0.7","eslint":"2","json2module":"0.0","rollup":"0.26","tape":"4","uglify-js":"2"};

package.json

 {
   "name": "d3-quadtree",
-  "version": "0.7.2",
+  "version": "0.7.3",
   "description": "Two-dimensional recursive spatial subdivision.",
@@ -29,2 +29,3 @@ "keywords": [
     "d3-array": "0.7",
+    "eslint": "2",
     "json2module": "0.0",
@@ -31,0 +32,0 @@ "rollup": "0.26",

README.md

@@ -115,5 +115,5 @@ # d3-quadtree
 
-<a name="quadtree_find" href="#quadtree_find">#</a> <i>quadtree</i>.<b>find</b>(<i>x</i>, <i>y</i>)
+<a name="quadtree_find" href="#quadtree_find">#</a> <i>quadtree</i>.<b>find</b>(<i>x</i>, <i>y</i>[, <i>radius</i>])
 
-Given a point ⟨*x*,*y*⟩, returns the closest datum in the quadtree. If the quadtree is empty, returns undefined.
+Returns the datum closest to the position ⟨*x*,*y*⟩ with the given search *radius*. If *radius* is not specified, it defaults to infinity. If there is no datum within the search area, returns undefined.
 
@@ -120,0 +120,0 @@ <a name="quadtree_visit" href="#quadtree_visit">#</a> <i>quadtree</i>.<b>visit</b>(<i>callback</i>)

src/find.js

 import Quad from "./quad";
 
-export default function(x, y) {
-  var minDistance2 = Infinity,
-      minPoint,
+export default function(x, y, radius) {
+  var data,
       x0 = this._x0,
@@ -20,2 +19,8 @@ y0 = this._y0,
   if (node) quads.push(new Quad(node, x0, y0, x3, y3));
+  if (radius == null) radius = Infinity;
+  else {
+    x0 = x - radius, y0 = y - radius;
+    x3 = x + radius, y3 = y + radius;
+    radius *= radius;
+  }
 
@@ -56,7 +61,7 @@ while (q = quads.pop()) {
           d2 = dx * dx + dy * dy;
-      if (d2 < minDistance2) {
-        var d = Math.sqrt(minDistance2 = d2);
+      if (d2 < radius) {
+        var d = Math.sqrt(radius = d2);
         x0 = x - d, y0 = y - d;
         x3 = x + d, y3 = y + d;
-        minPoint = node.data;
+        data = node.data;
       }
@@ -66,3 +71,3 @@ }
 
-  return minPoint;
+  return data;
 }

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

45968

increased by0.9%

Lines of code

760

increased by1.33%

Worsened metrics

Dev dependency count

6

increased by20%

No dependency changes