d3-quadtree - npm Package Compare versions

Comparing version 0.3.0 to 0.4.0

build/d3-quadtree.js

@@ -7,40 +7,29 @@ (function (global, factory) {
 
-  var version = "0.3.0";
+  var version = "0.4.0";
 
-  function constant(x) {
-    return function() {
-      return x;
-    };
-  }
+  function tree_add(point) {
+    if (isNaN(x = +point.x) || isNaN(y = +point.y)) return this; // ignore invalid points
 
-  function Leaf(point) {
-    this.point = point;
-  }
-
-  function root_add(point) {
-    if (isNaN(x = point[0]) || isNaN(y = point[1])) return; // ignore invalid points
-
-    var point0,
-        node = this._root,
+    var node = this._root,
         parent,
-        grandparent,
-        x,
-        y,
-        xm,
-        ym,
-        x0 = this._x0,
-        y0 = this._y0,
-        x1 = this._x1,
-        y1 = this._y1,
+        point0,
+        x, y,
+        xm, ym,
+        xp, yp,
+        x0 = this._x0, y0 = this._y0,
+        x1 = this._x1, y1 = this._y1,
         right,
         bottom,
         i,
-        i0;
+        j;
 
+    // Check if this point was previously in a quadtree!
+    if (point.next) delete point.next;
+
     // If the tree is empty, initialize the root as a leaf.
     if (!node) {
-      this._root = new Leaf(point);
+      this._root = {point: point};
       this._x0 = this._x1 = x;
       this._y0 = this._y1 = y;
-      return;
+      return this;
     }
@@ -63,29 +52,27 @@
     // Find the appropriate leaf node for the new point.
-    do {
+    // If there is no leaf node, add it.
+    while (!(point0 = node.point)) {
       if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
       if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
-      grandparent = parent, parent = node, node = node[i0 = i, i = bottom << 1 | right];
-    } while (node);
+      if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = {point: point}, this;
+    }
 
-    // If the new point is in an empty node, just add it.
-    if (!(point0 = parent.point)) return void (parent[i] = new Leaf(point));
-
     // If the new point is exactly coincident with the specified point, add it.
-    if (x === point0[0] && y === point0[1]) {
-      point.next = point0;
-      parent.point = point;
-      return;
+    if (xp = point0.x, yp = point0.y, x === xp && y === yp) {
+      node = {point: point, next: node};
+      if (parent) parent[i] = node;
+      else this._root = node;
+      return this;
     }
 
     // Otherwise, split the leaf node until the old and new point are separated.
-    parent = grandparent[i0] = new Array(4);
-    while (i === (i0 = (point0[1] >= ym) << 1 | (point0[0] >= xm))) {
+    do {
       parent = parent[i] = new Array(4);
       if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
       if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
-      i = bottom << 1 | right;
-    }
+    } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));
 
-    parent[i0] = new Leaf(point0);
-    parent[i] = new Leaf(point);
+    parent[i] = {point: point};
+    parent[j] = node;
+    return this;
   }
@@ -101,3 +88,18 @@
 
-  function root_eachAfter(callback) {
+  function tree_visit(callback) {
+    var quads = [], q, node = this._root, child, x0, y0, x1, y1;
+    if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1));
+    while (q = quads.pop()) {
+      if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1)) {
+        var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
+        if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
+        if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
+        if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
+        if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
+      }
+    }
+    return this;
+  }
+
+  function tree_visitAfter(callback) {
     var quads = [], next = [], q;
@@ -119,18 +121,3 @@ if (this._root) quads.push(new Quad(this._root, this._x0, this._y0, this._x1, this._y1));
 
-  function root_eachBefore(callback) {
-    var quads = [], q, node = this._root, child, x0, y0, x1, y1;
-    if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1));
-    while (q = quads.pop()) {
-      if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1)) {
-        var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
-        if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
-        if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
-        if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
-        if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
-      }
-    }
-    return this;
-  }
-
-  function root_find(x, y) {
+  function tree_find(x, y) {
     var minDistance2 = Infinity,
@@ -159,6 +146,6 @@ minPoint,
 
-      // Visit this point.
+      // Visit this point. (Visiting coincident points isn’t necessary!)
       if (node.point) {
-        var dx = x - node.point[0],
-            dy = y - node.point[1],
+        var dx = x - node.point.x,
+            dy = y - node.point.y,
             d2 = dx * dx + dy * dy;
@@ -195,75 +182,55 @@ if (d2 < minDistance2) {
 
-  function Root() {
-    this._x0 =
-    this._y0 =
-    this._x1 =
-    this._y1 = NaN;
-    this._root = null;
-  }
+  function tree_remove(point) {
+    var parent,
+        node = this._root,
+        previous,
+        xm, ym,
+        x = +point.x, y = +point.y,
+        x0 = this._x0, y0 = this._y0,
+        x1 = this._x1, y1 = this._y1,
+        right,
+        bottom,
+        i;
 
-  var rootProto = Root.prototype;
-  rootProto.add = root_add;
-  rootProto.eachAfter = root_eachAfter;
-  rootProto.eachBefore = root_eachBefore;
-  rootProto.find = root_find;
+    // If the tree is empty, initialize the root as a leaf.
+    if (!node) return false;
 
-  function defaultX(d) {
-    return d[0];
-  }
-
-  function defaultY(d) {
-    return d[1];
-  }
-
-  function quadtree() {
-    var x = defaultX,
-        y = defaultY,
-        ox,
-        oy,
-        l;
-
-    function quadtree(data) {
-      var d, i, n = data.length, p,
-          xi, yi,
-          x0 = -Infinity,
-          y0 = -Infinity,
-          x1 = Infinity,
-          y1 = Infinity,
-          root = new Root;
-
-      if (ox != null) {
-        root._root = new Array(4);
-        root._x0 = x0 = ox, root._x1 = x1 = ox + l;
-        root._y0 = y0 = oy, root._y1 = y1 = oy + l;
-      }
-
-      for (i = 0; i < n; ++i) {
-        xi = +x(d = data[i], i, data), yi = +y(d, i, data);
-        if (x0 > xi || xi >= x1 || y0 > yi || yi >= y1) continue;
-        p = [xi, yi], p.data = d, p.index = i;
-        root.add(p);
-      }
-
-      return root;
+    // Find the leaf node for the point.
+    while (!node.point) {
+      if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
+      if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
+      if (!(parent = node, node = node[i = bottom << 1 | right])) return false;
     }
 
-    quadtree.x = function(_) {
-      return arguments.length ? (x = typeof _ === "function" ? _ : constant(+_), quadtree) : x;
-    };
+    // Find the point to remove.
+    while (node.point !== point) if (!(previous = node, node = node.next)) return false;
 
-    quadtree.y = function(_) {
-      return arguments.length ? (y = typeof _ === "function" ? _ : constant(+_), quadtree) : y;
-    };
+    // Remove the point, or the leaf if it’s the only point.
+    if (previous) previous.next = node.next;
+    else if (parent) parent[i] = node.next;
+    else this._root = node.next;
+    return true;
+  }
 
-    quadtree.extent = function(_) {
-      return arguments.length ? (_ == null ? ox = oy = l = null : (ox = +_[0][0], oy = +_[0][1], l = Math.max(_[1][0] - ox, _[1][1] - oy)), quadtree) : ox == null ? null : [[ox, oy], [ox + l, oy + l]];
-    };
+  function quadtree(x0, y0, x1, y1) {
+    if (arguments.length === 2) x1 = x0, y1 = y0, x0 = y0 = 0;
+    return new Quadtree(x0, y0, x1, y1);
+  }
 
-    quadtree.size = function(_) {
-      return arguments.length ? (_ == null ? ox = oy = l = null : (ox = oy = 0, l = Math.max(+_[0], +_[1])), quadtree) : ox == null ? null : [l, l];
-    };
-
-    return quadtree;
+  function Quadtree(x0, y0, x1, y1) {
+    var dx = (x1 = +x1) - (x0 = +x0), dy = (y1 = +y1) - (y0 = +y0);
+    if (dy > dx) x1 = (x0 -= (dy - dx) / 2) + dy;
+    else y1 = (y0 -= (dx - dy) / 2) + dx;
+    this._x0 = x0, this._y0 = y0;
+    this._x1 = x1, this._y1 = y1;
+    this._root = isNaN(dx) || isNaN(dy) ? undefined : new Array(4);
   }
 
+  var treeProto = Quadtree.prototype = quadtree.prototype;
+  treeProto.add = tree_add;
+  treeProto.visit = tree_visit;
+  treeProto.visitAfter = tree_visitAfter;
+  treeProto.find = tree_find;
+  treeProto.remove = tree_remove;
+
   exports.version = version;
@@ -270,0 +237,0 @@ exports.quadtree = quadtree;

build/d3-quadtree.min.js

@@ -1,1 +0,1 @@
-!function(t,n){"object"==typeof exports&&"undefined"!=typeof module?n(exports):"function"==typeof define&&define.amd?define(["exports"],n):n(t.d3_quadtree=t.d3_quadtree||{})}(this,function(t){"use strict";function n(t){return function(){return t}}function e(t){this.point=t}function i(t){if(!isNaN(o=t[0])&&!isNaN(h=t[1])){var n,i,r,o,h,s,u,a,f,_,y,p=this._root,x=this._x0,l=this._y0,w=this._x1,d=this._y1;if(!p)return this._root=new e(t),this._x0=this._x1=o,void(this._y0=this._y1=h);if(x>o||o>w||l>h||h>d){switch(s=x===w?Math.max(Math.abs(x-o),Math.abs(l-h)):2*(w-x),_=((l+d)/2>h)<<1|(x+w)/2>o){case 0:do i=new Array(4),i[_]=p,p=i,w=x+s,d=l+s,s*=2;while(o>w||h>d);break;case 1:do i=new Array(4),i[_]=p,p=i,x=w-s,d=l+s,s*=2;while(x>o||h>d);break;case 2:do i=new Array(4),i[_]=p,p=i,w=x+s,l=d-s,s*=2;while(o>w||l>h);break;case 3:do i=new Array(4),i[_]=p,p=i,x=w-s,l=d-s,s*=2;while(x>o||l>h)}this._root=p,this._x0=x,this._x1=w,this._y0=l,this._y1=d}do(a=o>=(s=(x+w)/2))?x=s:w=s,(f=h>=(u=(l+d)/2))?l=u:d=u,r=i,i=p,p=p[(y=_,_=f<<1|a)];while(p);if(!(n=i.point))return void(i[_]=new e(t));if(o===n[0]&&h===n[1])return t.next=n,void(i.point=t);for(i=r[y]=new Array(4);_===(y=(n[1]>=u)<<1|n[0]>=s);)i=i[_]=new Array(4),(a=o>=(s=(x+w)/2))?x=s:w=s,(f=h>=(u=(l+d)/2))?l=u:d=u,_=f<<1|a;i[y]=new e(n),i[_]=new e(t)}}function r(t,n,e,i,r){this.node=t,this.x0=n,this.y0=e,this.x1=i,this.y1=r}function o(t){var n,e=[],i=[];for(this._root&&e.push(new r(this._root,this._x0,this._y0,this._x1,this._y1));n=e.pop();){var o,h=n.node,s=n.x0,u=n.y0,a=n.x1,f=n.y1,_=(s+a)/2,y=(u+f)/2;(o=h[0])&&e.push(new r(o,s,u,_,y)),(o=h[1])&&e.push(new r(o,_,u,a,y)),(o=h[2])&&e.push(new r(o,s,y,_,f)),(o=h[3])&&e.push(new r(o,_,y,a,f)),i.push(n)}for(;n=i.pop();)t(n.node,n.x0,n.y0,n.x1,n.y1);return this}function h(t){var n,e,i,o,h,s,u=[],a=this._root;for(a&&u.push(new r(a,this._x0,this._y0,this._x1,this._y1));n=u.pop();)if(!t(a=n.node,i=n.x0,o=n.y0,h=n.x1,s=n.y1)){var f=(i+h)/2,_=(o+s)/2;(e=a[3])&&u.push(new r(e,f,_,h,s)),(e=a[2])&&u.push(new r(e,i,_,f,s)),(e=a[1])&&u.push(new r(e,f,o,h,_)),(e=a[0])&&u.push(new r(e,i,o,f,_))}return this}function s(t,n){var e,i,o,h,s,u,a,f=1/0,_=this._x0,y=this._y0,p=this._x1,x=this._y1,l=[],w=this._root;for(w&&l.push(new r(w,_,y,p,x));u=l.pop();)if(w=u.node,i=u.x0,o=u.y0,h=u.x1,s=u.y1,!(!w||i>p||o>x||_>h||y>s)){if(w.point){var d=t-w.point[0],c=n-w.point[1],v=d*d+c*c;if(f>v){var g=Math.sqrt(f=v);_=t-g,y=n-g,p=t+g,x=n+g,e=w.point}}var A=(i+h)/2,b=(o+s)/2;l.push(new r(w[3],A,b,h,s),new r(w[2],i,b,A,s),new r(w[1],A,o,h,b),new r(w[0],i,o,A,b)),(a=(n>=b)<<1|t>=A)&&(u=l[l.length-1],l[l.length-1]=l[l.length-1-a],l[l.length-1-a]=u)}return e}function u(){this._x0=this._y0=this._x1=this._y1=NaN,this._root=null}function a(t){return t[0]}function f(t){return t[1]}function _(){function t(t){var n,s,a,f,_,y=t.length,p=-(1/0),x=-(1/0),l=1/0,w=1/0,d=new u;for(null!=e&&(d._root=new Array(4),d._x0=p=e,d._x1=l=e+r,d._y0=x=i,d._y1=w=i+r),s=0;y>s;++s)f=+o(n=t[s],s,t),_=+h(n,s,t),p>f||f>=l||x>_||_>=w||(a=[f,_],a.data=n,a.index=s,d.add(a));return d}var e,i,r,o=a,h=f;return t.x=function(e){return arguments.length?(o="function"==typeof e?e:n(+e),t):o},t.y=function(e){return arguments.length?(h="function"==typeof e?e:n(+e),t):h},t.extent=function(n){return arguments.length?(null==n?e=i=r=null:(e=+n[0][0],i=+n[0][1],r=Math.max(n[1][0]-e,n[1][1]-i)),t):null==e?null:[[e,i],[e+r,i+r]]},t.size=function(n){return arguments.length?(null==n?e=i=r=null:(e=i=0,r=Math.max(+n[0],+n[1])),t):null==e?null:[r,r]},t}var y="0.3.0",p=u.prototype;p.add=i,p.eachAfter=o,p.eachBefore=h,p.find=s,t.version=y,t.quadtree=_});
+!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){if(isNaN(n=+t.x)||isNaN(s=+t.y))return this;var i,e,n,s,h,r,o,_,u,p,x,a,y=this._root,f=this._x0,w=this._y0,d=this._x1,c=this._y1;if(t.next&&delete t.next,!y)return this._root={point:t},this._x0=this._x1=n,this._y0=this._y1=s,this;if(f>n||n>d||w>s||s>c){switch(h=f===d?Math.max(Math.abs(f-n),Math.abs(w-s)):2*(d-f),x=((w+c)/2>s)<<1|(f+d)/2>n){case 0:do i=new Array(4),i[x]=y,y=i,d=f+h,c=w+h,h*=2;while(n>d||s>c);break;case 1:do i=new Array(4),i[x]=y,y=i,f=d-h,c=w+h,h*=2;while(f>n||s>c);break;case 2:do i=new Array(4),i[x]=y,y=i,d=f+h,w=c-h,h*=2;while(n>d||w>s);break;case 3:do i=new Array(4),i[x]=y,y=i,f=d-h,w=c-h,h*=2;while(f>n||w>s)}this._root=y,this._x0=f,this._x1=d,this._y0=w,this._y1=c}for(;!(e=y.point);)if((u=n>=(h=(f+d)/2))?f=h:d=h,(p=s>=(r=(w+c)/2))?w=r:c=r,i=y,!(y=y[x=p<<1|u]))return i[x]={point:t},this;if(o=e.x,_=e.y,n===o&&s===_)return y={point:t,next:y},i?i[x]=y:this._root=y,this;do i=i[x]=new Array(4),(u=n>=(h=(f+d)/2))?f=h:d=h,(p=s>=(r=(w+c)/2))?w=r:c=r;while((x=p<<1|u)===(a=(_>=r)<<1|o>=h));return i[x]={point:t},i[a]=y,this}function e(t,i,e,n,s){this.node=t,this.x0=i,this.y0=e,this.x1=n,this.y1=s}function n(t){var i,n,s,h,r,o,_=[],u=this._root;for(u&&_.push(new e(u,this._x0,this._y0,this._x1,this._y1));i=_.pop();)if(!t(u=i.node,s=i.x0,h=i.y0,r=i.x1,o=i.y1)){var p=(s+r)/2,x=(h+o)/2;(n=u[3])&&_.push(new e(n,p,x,r,o)),(n=u[2])&&_.push(new e(n,s,x,p,o)),(n=u[1])&&_.push(new e(n,p,h,r,x)),(n=u[0])&&_.push(new e(n,s,h,p,x))}return this}function s(t){var i,n=[],s=[];for(this._root&&n.push(new e(this._root,this._x0,this._y0,this._x1,this._y1));i=n.pop();){var h,r=i.node,o=i.x0,_=i.y0,u=i.x1,p=i.y1,x=(o+u)/2,a=(_+p)/2;(h=r[0])&&n.push(new e(h,o,_,x,a)),(h=r[1])&&n.push(new e(h,x,_,u,a)),(h=r[2])&&n.push(new e(h,o,a,x,p)),(h=r[3])&&n.push(new e(h,x,a,u,p)),s.push(i)}for(;i=s.pop();)t(i.node,i.x0,i.y0,i.x1,i.y1);return this}function h(t,i){var n,s,h,r,o,_,u,p=1/0,x=this._x0,a=this._y0,y=this._x1,f=this._y1,w=[],d=this._root;for(d&&w.push(new e(d,x,a,y,f));_=w.pop();)if(d=_.node,s=_.x0,h=_.y0,r=_.x1,o=_.y1,!(!d||s>y||h>f||x>r||a>o)){if(d.point){var c=t-d.point.x,v=i-d.point.y,l=c*c+v*v;if(p>l){var N=Math.sqrt(p=l);x=t-N,a=i-N,y=t+N,f=i+N,n=d.point}}var A=(s+r)/2,b=(h+o)/2;w.push(new e(d[3],A,b,r,o),new e(d[2],s,b,A,o),new e(d[1],A,h,r,b),new e(d[0],s,h,A,b)),(u=(i>=b)<<1|t>=A)&&(_=w[w.length-1],w[w.length-1]=w[w.length-1-u],w[w.length-1-u]=_)}return n}function r(t){var i,e,n,s,h,r,o,_=this._root,u=+t.x,p=+t.y,x=this._x0,a=this._y0,y=this._x1,f=this._y1;if(!_)return!1;for(;!_.point;)if((h=u>=(n=(x+y)/2))?x=n:y=n,(r=p>=(s=(a+f)/2))?a=s:f=s,i=_,!(_=_[o=r<<1|h]))return!1;for(;_.point!==t;)if(e=_,!(_=_.next))return!1;return e?e.next=_.next:i?i[o]=_.next:this._root=_.next,!0}function o(t,i,e,n){return 2===arguments.length&&(e=t,n=i,t=i=0),new _(t,i,e,n)}function _(t,i,e,n){var s=(e=+e)-(t=+t),h=(n=+n)-(i=+i);h>s?e=(t-=(h-s)/2)+h:n=(i-=(s-h)/2)+s,this._x0=t,this._y0=i,this._x1=e,this._y1=n,this._root=isNaN(s)||isNaN(h)?void 0:new Array(4)}var u="0.4.0",p=_.prototype=o.prototype;p.add=i,p.visit=n,p.visitAfter=s,p.find=h,p.remove=r,t.version=u,t.quadtree=o});

build/package.js

 export var name = "d3-quadtree";
-export var version = "0.3.0";
+export var version = "0.4.0";
 export var description = "Two-dimensional recursive spatial subdivision.";
@@ -10,3 +10,3 @@ export var keywords = ["d3","quadtree"];
 export var repository = {"type":"git","url":"https://github.com/d3/d3-quadtree.git"};
-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.3.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.3.min.js && cd ../d3.github.com && git add d3-quadtree.v0.3.js d3-quadtree.v0.3.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 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.4.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.4.min.js && cd ../d3.github.com && git add d3-quadtree.v0.4.js d3-quadtree.v0.4.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"};

package.json

 {
   "name": "d3-quadtree",
-  "version": "0.3.0",
+  "version": "0.4.0",
   "description": "Two-dimensional recursive spatial subdivision.",
@@ -25,3 +25,3 @@ "keywords": [
     "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.3.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.3.min.js && cd ../d3.github.com && git add d3-quadtree.v0.3.js d3-quadtree.v0.3.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"
+    "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.4.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.4.min.js && cd ../d3.github.com && git add d3-quadtree.v0.4.js d3-quadtree.v0.4.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"
   },
@@ -28,0 +28,0 @@ "devDependencies": {

README.md

 # d3-quadtree
 
-A [quadtree](https://en.wikipedia.org/wiki/Quadtree) is a two-dimensional recursive spatial subdivision. This implementation uses square partitions, dividing each square into four equally-sized squares. Each point exists in a unique node; if multiple points are in the same position, some points may be stored on internal nodes rather than leaf nodes. Quadtrees can be used to accelerate various spatial operations, such as the Barnes-Hut approximation for computing n-body forces, or collision detection.
+A [quadtree](https://en.wikipedia.org/wiki/Quadtree) is a two-dimensional recursive spatial subdivision. This implementation uses square partitions, dividing each square into four equally-sized squares. Each point exists in a unique node; if multiple points are in the same position, some points may be stored on internal nodes rather than leaf nodes. Quadtrees can be used to accelerate various spatial operations, such as the [Barnes–Hut approximation](https://en.wikipedia.org/wiki/Barnes–Hut_simulation) for computing many-body forces, or collision detection.
 
@@ -14,6 +14,6 @@ <a href="http://bl.ocks.org/mbostock/9078690"><img src="http://bl.ocks.org/mbostock/raw/9078690/thumbnail.png" width="202"></a>
 
-If you use NPM, `npm install d3-quadtree`. Otherwise, download the [latest release](https://github.com/d3/d3-quadtree/releases/latest). You can also load directly from [d3js.org](https://d3js.org), either as a [standalone library](https://d3js.org/d3-quadtree.v0.3.min.js) or as part of [D3 4.0 alpha](https://github.com/mbostock/d3/tree/4). AMD, CommonJS, and vanilla environments are supported. In vanilla, a `d3_quadtree` global is exported:
+If you use NPM, `npm install d3-quadtree`. Otherwise, download the [latest release](https://github.com/d3/d3-quadtree/releases/latest). You can also load directly from [d3js.org](https://d3js.org), either as a [standalone library](https://d3js.org/d3-quadtree.v0.4.min.js) or as part of [D3 4.0 alpha](https://github.com/mbostock/d3/tree/4). AMD, CommonJS, and vanilla environments are supported. In vanilla, a `d3_quadtree` global is exported:
 
 ```html
-<script src="https://d3js.org/d3-quadtree.v0.3.min.js"></script>
+<script src="https://d3js.org/d3-quadtree.v0.4.min.js"></script>
 <script>
@@ -30,86 +30,61 @@
 
-<a name="quadtree" href="#quadtree">#</a> d3.<b>quadtree</b>()
+<a name="quadtree" href="#quadtree">#</a> d3.<b>quadtree</b>([[<i>x0</i>, <i>y0</i>, ]<i>x1</i>, <i>y1</i>])
 
-Creates a new quadtree generator with the default [*x*-accessor](#quadtree_x), [*y*-accessor](#quadtree_y) and [extent](#quadtree_extent). The returned generator can be used to [create](#_quadtree) any number of quadtree roots from data.
+Creates a new, empty quadtree with the initial bounds *x0*, *y0*, *x1*, *y1*, where *x0* and *y0* are the inclusive lower bounds of the extent and *x1* and *y1* are the inclusive upper bounds. If the initial bounds are not specified, the bounds will be inferred as points are [added](#quadtree_add) to the quadtree.
 
-<a name="_quadtree" href="#_quadtree">#</a> <i>quadtree</i>(<i>data</i>)
+If only the upper bounds *x1* and *y1* are specified, the lower bounds *x0* and *y0* are assumed to be 0. If the specified bounds are not square, the shorter side is expanded to produce square bounds while retaining the original center. Thus, the following statements are therefore equivalent:
 
-Constructs a new [quadtree root node](#quadtree-nodes) for the specified array of *data*. The *x*- and *y*-coordinates of each data point are determined using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors; each point in the quadtree is represented as a two-element array of numbers [*x*, *y*] with the following additional properties:
-
-* `data` - the datum associated with this node.
-* `index` - the index of the datum associated with this node.
-
-<a name="quadtree_x" href="#quadtree_x">#</a> <i>quadtree</i>.<b>x</b>([<i>x</i>])
-
-If *x* is specified, sets the *x*-coordinate accessor and returns this quadtree generator. If *x* is not specified, returns the current *x*-coordinate accessor, which defaults to:
-
 ```js
-function x(d) {
-  return d[0];
-}
+var q = d3.quadtree(960, 500);
+var q = d3.quadtree(0, 0, 960, 500);
+var q = d3.quadtree(0, -230, 960, 730);
 ```
 
-For each point added to the quadtree, the *x*-accessor is invoked, being passed the current datum `d` and index `i`. The *x*-accessor must then return a numeric value indicating the *x*-coordinate of the point corresponding to the given datum. The *x*-accessor may also be defined as a constant number rather than a function, if desired.
+If an added point is outside the current bounds of this quadtree, this quadtree is expanded by repeatedly doubling its width and height until the new point is contained.
 
-<a name="quadtree_y" href="#quadtree_y">#</a> <i>quadtree</i>.<b>y</b>([<i>y</i>])
+<a name="quadtree_add" href="#quadtree_add">#</a> <i>quadtree</i>.<b>add</b>(<i>point</i>)
 
-If *y* is specified, sets the y-coordinate accessor and returns this quadtree generator. If *y* is not specified, returns the current *y*-coordinate accessor, which defaults to:
+Adds the specified new *point* to this quadtree and returns this *quadtree*. The point must have the following properties:
 
-```js
-function y(d) {
-  return d[1];
-}
-```
+* `x` - the *x*-coordinate of the point
+* `y` - the *y*-coordinate of the point
 
-For each point added to the quadtree, the *y*-accessor is invoked, being passed the current datum `d` and index `i`. The *y*-accessor must then return a numeric value indicating the *y*-coordinate of the point corresponding to the given datum. The *y*-accessor may also be defined as a constant number rather than a function, if desired.
+By returning this quadtree, this method allows [method chaining](https://en.wikipedia.org/wiki/Method_chaining). For example:
 
-<a name="quadtree_extent" href="#quadtree_extent">#</a> <i>quadtree</i>.<b>extent</b>([<i>extent</i>])
-
-If *extent* is specified, sets the current extent and returns this quadtree generator. The *extent* must be specified as a two-dimensional array [​[*x0*, *y0*], [​*x1*, *y1*]​], where *x0* and *y0* are the inclusive lower bounds of the extent and *x1* and *y1* are the exclusive upper bounds, or null. If *extent* is not specified, returns the current extent, which defaults to null. When the extent is not null, any point outside the extent is ignored when [constructing the quadtree](#_quadtree).
-
-<a name="quadtree_size" href="#quadtree_size">#</a> <i>quadtree</i>.<b>size</b>([<i>size</i>])
-
-If *size* is specified, sets the current extent and returns this quadtree generator. The *size* must be specified as a two-element array of numbers [[​*x1*, *y1*]​], where *x1* and *y1* are the exclusive upper bounds, or null; the lower bounds of the extent are implicitly ⟨0,0⟩. If *size* is not specified, returns the current upper bounds of the extent, which defaults to null. When the extent is not null, any point outside the extent is ignored when [constructing the quadtree](#_quadtree).
-
-This is a convenience method for setting the [extent](#quadtree_extent) where the lower bounds of the extent are ⟨0,0⟩. For example, this:
-
 ```js
-quadtree.size([960, 500]);
+var q = d3.quadtree(960, 500)
+    .add({x:   0, y:   0})
+    .add({x: 100, y:   0})
+    .add({x:   0, y: 100})
+    .add({x: 100, y: 100});
 ```
 
-Is equivalent to this:
+<a name="quadtree_find" href="#quadtree_find">#</a> <i>quadtree</i>.<b>find</b>(<i>x</i>, <i>y</i>)
 
-```js
-quadtree.extent([[0, 0], [960, 500]]);
-```
+Given a point ⟨*x*,*y*⟩, returns the closest point in this quadtree. If this quadtree is empty, returns undefined.
 
-### Quadtree Nodes
+<a name="quadtree_visit" href="#quadtree_visit">#</a> <i>quadtree</i>.<b>visit</b>(<i>callback</i>)
 
-Internal nodes of the quadtree are represented as sparse four-element arrays in left-to-right, top-to-bottom order:
+Visits each node in this quadtree in pre-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds, and returns this quadtree. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.)
 
-* `0` - the top-left quadrant
-* `1` - the top-right quadrant
-* `2` - the bottom-left quadrant
-* `3` - the bottom-right quadrant
+Internal nodes of the quadtree are represented as four-element arrays in left-to-right, top-to-bottom order:
 
-Leaf nodes of the quadtree are represent as objects with the following property:
+* `0` - the top-left quadrant, if any
+* `1` - the top-right quadrant, if any
+* `2` - the bottom-left quadrant, if any
+* `3` - the bottom-right quadrant, if any
 
-* `point` - a two-element array of numbers [*x*, *y*]
+Each child quadrant may be undefined if the specified quadrant is empty.
 
-If there are multiple coincident points in the quadtree, then *point*.next forms a linked list of coincident points.
+Leaf nodes are represented as objects with the following properties:
 
-<a name="root_add" href="#root_add">#</a> <i>root</i>.<b>add</b>(<i>point</i>)
+* `point` - the point, as passed to [*quadtree*.add](#quadtree_add)
+* `next` - the next point in this leaf, if any
 
-Adds the specified new *point* to this quadtree and returns *root*. The point must be represented as a two-element array of numbers [*x*, *y*].
+If the *callback* returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited. This can be used to quickly visit only parts of the tree, for example when using the [Barnes–Hut approximation](https://en.wikipedia.org/wiki/Barnes–Hut_simulation). Note, however, that child quadrants are always visited in sibling order: top-left, top-right, bottom-left, bottom-right. In cases such as [search](#quadtree_find), visiting siblings in a specific order may be faster.
 
-<a name="root_find" href="#root_find">#</a> <i>root</i>.<b>find</b>(<i>x</i>, <i>y</i>)
+<a name="quadtree_visitAfter" href="#quadtree_visitAfter">#</a> <i>root</i>.<b>visitAfter</b>(<i>callback</i>)
 
-Given a point ⟨*x*,*y*⟩, returns the closest point in this quadtree.
+Visits each node in this quadtree in post-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds, and returns this quadtree. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) Returns *root*.
 
-<a name="root_eachBefore" href="#root_eachBefore">#</a> <i>root</i>.<b>eachBefore</b>(<i>callback</i>)
-
-Visits each node in this quadtree in pre-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) Returns *root*. If the *callback* returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited.
-
-<a name="root_eachAfter" href="#root_eachAfter">#</a> <i>root</i>.<b>eachAfter</b>(<i>callback</i>)
-
-Visits each node in this quadtree in post-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) Returns *root*.
+See [*quadtree*.visit](#quadtree_visit) for a description of the *node* data structure.

src/add.js

@@ -1,29 +0,26 @@
-import Leaf from "./leaf";
-
 export default function(point) {
-  if (isNaN(x = point[0]) || isNaN(y = point[1])) return; // ignore invalid points
+  if (isNaN(x = +point.x) || isNaN(y = +point.y)) return this; // ignore invalid points
 
-  var point0,
-      node = this._root,
+  var node = this._root,
       parent,
-      grandparent,
-      x,
-      y,
-      xm,
-      ym,
-      x0 = this._x0,
-      y0 = this._y0,
-      x1 = this._x1,
-      y1 = this._y1,
+      point0,
+      x, y,
+      xm, ym,
+      xp, yp,
+      x0 = this._x0, y0 = this._y0,
+      x1 = this._x1, y1 = this._y1,
       right,
       bottom,
       i,
-      i0;
+      j;
 
+  // Check if this point was previously in a quadtree!
+  if (point.next) delete point.next;
+
   // If the tree is empty, initialize the root as a leaf.
   if (!node) {
-    this._root = new Leaf(point);
+    this._root = {point: point};
     this._x0 = this._x1 = x;
     this._y0 = this._y1 = y;
-    return;
+    return this;
   }
@@ -46,29 +43,27 @@
   // Find the appropriate leaf node for the new point.
-  do {
+  // If there is no leaf node, add it.
+  while (!(point0 = node.point)) {
     if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
     if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
-    grandparent = parent, parent = node, node = node[i0 = i, i = bottom << 1 | right];
-  } while (node);
+    if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = {point: point}, this;
+  }
 
-  // If the new point is in an empty node, just add it.
-  if (!(point0 = parent.point)) return void (parent[i] = new Leaf(point));
-
   // If the new point is exactly coincident with the specified point, add it.
-  if (x === point0[0] && y === point0[1]) {
-    point.next = point0;
-    parent.point = point;
-    return;
+  if (xp = point0.x, yp = point0.y, x === xp && y === yp) {
+    node = {point: point, next: node};
+    if (parent) parent[i] = node;
+    else this._root = node;
+    return this;
   }
 
   // Otherwise, split the leaf node until the old and new point are separated.
-  parent = grandparent[i0] = new Array(4);
-  while (i === (i0 = (point0[1] >= ym) << 1 | (point0[0] >= xm))) {
+  do {
     parent = parent[i] = new Array(4);
     if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
     if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
-    i = bottom << 1 | right;
-  }
+  } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));
 
-  parent[i0] = new Leaf(point0);
-  parent[i] = new Leaf(point);
+  parent[i] = {point: point};
+  parent[j] = node;
+  return this;
 }

src/find.js

@@ -27,6 +27,6 @@ import Quad from "./quad";
 
-    // Visit this point.
+    // Visit this point. (Visiting coincident points isn’t necessary!)
     if (node.point) {
-      var dx = x - node.point[0],
-          dy = y - node.point[1],
+      var dx = x - node.point.x,
+          dy = y - node.point.y,
           d2 = dx * dx + dy * dy;
@@ -33,0 +33,0 @@ if (d2 < minDistance2) {

src/quadtree.js

@@ -1,61 +0,26 @@
-import constant from "./constant";
-import Root from "./root";
+import tree_add from "./add";
+import tree_visit from "./visit";
+import tree_visitAfter from "./visitAfter";
+import tree_find from "./find";
+import tree_remove from "./remove";
 
-function defaultX(d) {
-  return d[0];
+export default function quadtree(x0, y0, x1, y1) {
+  if (arguments.length === 2) x1 = x0, y1 = y0, x0 = y0 = 0;
+  return new Quadtree(x0, y0, x1, y1);
 }
 
-function defaultY(d) {
-  return d[1];
+function Quadtree(x0, y0, x1, y1) {
+  var dx = (x1 = +x1) - (x0 = +x0), dy = (y1 = +y1) - (y0 = +y0);
+  if (dy > dx) x1 = (x0 -= (dy - dx) / 2) + dy;
+  else y1 = (y0 -= (dx - dy) / 2) + dx;
+  this._x0 = x0, this._y0 = y0;
+  this._x1 = x1, this._y1 = y1;
+  this._root = isNaN(dx) || isNaN(dy) ? undefined : new Array(4);
 }
 
-export default function() {
-  var x = defaultX,
-      y = defaultY,
-      ox,
-      oy,
-      l;
-
-  function quadtree(data) {
-    var d, i, n = data.length, p,
-        xi, yi,
-        x0 = -Infinity,
-        y0 = -Infinity,
-        x1 = Infinity,
-        y1 = Infinity,
-        root = new Root;
-
-    if (ox != null) {
-      root._root = new Array(4);
-      root._x0 = x0 = ox, root._x1 = x1 = ox + l;
-      root._y0 = y0 = oy, root._y1 = y1 = oy + l;
-    }
-
-    for (i = 0; i < n; ++i) {
-      xi = +x(d = data[i], i, data), yi = +y(d, i, data);
-      if (x0 > xi || xi >= x1 || y0 > yi || yi >= y1) continue;
-      p = [xi, yi], p.data = d, p.index = i;
-      root.add(p);
-    }
-
-    return root;
-  }
-
-  quadtree.x = function(_) {
-    return arguments.length ? (x = typeof _ === "function" ? _ : constant(+_), quadtree) : x;
-  };
-
-  quadtree.y = function(_) {
-    return arguments.length ? (y = typeof _ === "function" ? _ : constant(+_), quadtree) : y;
-  };
-
-  quadtree.extent = function(_) {
-    return arguments.length ? (_ == null ? ox = oy = l = null : (ox = +_[0][0], oy = +_[0][1], l = Math.max(_[1][0] - ox, _[1][1] - oy)), quadtree) : ox == null ? null : [[ox, oy], [ox + l, oy + l]];
-  };
-
-  quadtree.size = function(_) {
-    return arguments.length ? (_ == null ? ox = oy = l = null : (ox = oy = 0, l = Math.max(+_[0], +_[1])), quadtree) : ox == null ? null : [l, l];
-  };
-
-  return quadtree;
-}
+var treeProto = Quadtree.prototype = quadtree.prototype;
+treeProto.add = tree_add;
+treeProto.visit = tree_visit;
+treeProto.visitAfter = tree_visitAfter;
+treeProto.find = tree_find;
+treeProto.remove = tree_remove;

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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Worsened metrics

Total package byte prevSize

29646

decreased by-7.49%

Number of package files

16

decreased by-11.11%

Lines of code

415

decreased by-11.13%

Number of lines in readme file

89

decreased by-21.93%

No dependency changes