d3-quadtree - npm Package Compare versions

Comparing version 0.5.0 to 0.6.0

build/d3-quadtree.js

@@ -7,14 +7,9 @@ (function (global, factory) {
 
-  var version = "0.5.0";
+  var version = "0.6.0";
 
-  function tree_add(point) {
-    if (isNaN(x = +point[0]) || isNaN(y = +point[1])) return this; // ignore invalid points
+  function tree_add(x, y) {
+    if (isNaN(x = +x) || isNaN(y = +y)) return; // ignore invalid points
 
-    // Expand the tree to cover the new point, if necessary.
-    this.cover(x, y);
-
-    var node = this._root,
+    var node = this.cover(x, y)._root,
         parent,
-        x,
-        y,
         x0 = this._x0,
@@ -34,18 +29,15 @@ y0 = this._y0,
     // If the tree is empty, initialize the root as a leaf.
-    if (!node) return this._root = {point: point}, this;
+    if (!node) return this._root = {x: x, y: y};
 
-    // Find the appropriate leaf node for the new point.
-    // If there is no leaf node, add it.
-    while (!node.point) {
+    // Find the existing leaf for the new point, or add it.
+    while (node.length) {
       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 parent[i] = {point: point}, this;
+      if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = {x: x, y: y};
     }
 
-    // If the new point is exactly coincident with the specified point, add it.
-    if (xp = node.point[0], yp = node.point[1], x === xp && y === yp) {
-      node = {point: point, next: node};
-      if (parent) parent[i] = node;
-      else this._root = node;
-      return this;
+    // Is the new point is exactly coincident with the existing point?
+    if (xp = node.x, yp = node.y, x === xp && y === yp) {
+      node = {x: x, y: y, next: node};
+      return parent ? parent[i] = node : this._root = node;
     }
@@ -59,6 +51,3 @@
     } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));
-
-    parent[i] = {point: point};
-    parent[j] = node;
-    return this;
+    return parent[j] = node, parent[i] = {x: x, y: y};
   }
@@ -106,3 +95,3 @@
         }
-        if (this._root && !this._root.point) this._root = node;
+        if (this._root && this._root.length) this._root = node;
       }
@@ -127,4 +116,6 @@
 
-  function tree_extent() {
-    if (!isNaN(this._x0)) return [[this._x0, this._y0], [this._x1, this._y1]];
+  function tree_extent(_) {
+    return arguments.length
+        ? this.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1])
+        : isNaN(this._x0) ? undefined : [[this._x0, this._y0], [this._x1, this._y1]];
   }
@@ -159,11 +150,34 @@
     while (q = quads.pop()) {
-      node = q.node, x1 = q.x0, y1 = q.y0, x2 = q.x1, y2 = q.y1;
 
       // Stop searching if this quadrant can’t contain a closer node.
-      if (!node || x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) continue;
+      if (!(node = q.node)
+          || (x1 = q.x0) > x3
+          || (y1 = q.y0) > y3
+          || (x2 = q.x1) < x0
+          || (y2 = q.y1) < y0) continue;
 
+      // Bisect the current quadrant.
+      if (node.length) {
+        var xm = (x1 + x2) / 2,
+            ym = (y1 + y2) / 2;
+
+        quads.push(
+          new Quad(node[3], xm, ym, x2, y2),
+          new Quad(node[2], x1, ym, xm, y2),
+          new Quad(node[1], xm, y1, x2, ym),
+          new Quad(node[0], x1, y1, xm, ym)
+        );
+
+        // Visit the closest quadrant first.
+        if (i = (y >= ym) << 1 | (x >= xm)) {
+          q = quads[quads.length - 1];
+          quads[quads.length - 1] = quads[quads.length - 1 - i];
+          quads[quads.length - 1 - i] = q;
+        }
+      }
+
       // Visit this point. (Visiting coincident points isn’t necessary!)
-      if (node.point) {
-        var dx = x - node.point[0],
-            dy = y - node.point[1],
+      else {
+        var dx = x - node.x,
+            dy = y - node.y,
             d2 = dx * dx + dy * dy;
@@ -174,23 +188,5 @@ if (d2 < minDistance2) {
           x3 = x + d, y3 = y + d;
-          minPoint = node.point;
+          minPoint = node;
         }
       }
-
-      // Bisect the current quadrant.
-      var xm = (x1 + x2) / 2,
-          ym = (y1 + y2) / 2;
-
-      quads.push(
-        new Quad(node[3], xm, ym, x2, y2),
-        new Quad(node[2], x1, ym, xm, y2),
-        new Quad(node[1], xm, y1, x2, ym),
-        new Quad(node[0], x1, y1, xm, ym)
-      );
-
-      // Visit the closest quadrant first.
-      if (i = (y >= ym) << 1 | (x >= xm)) {
-        q = quads[quads.length - 1];
-        quads[quads.length - 1] = quads[quads.length - 1 - i];
-        quads[quads.length - 1 - i] = q;
-      }
     }
@@ -204,3 +200,3 @@
     this.visit(function(node) {
-      if (node.point) do points.push(node.point); while (node = node.next)
+      if (!node.length) do points.push(node); while (node = node.next)
     });
@@ -215,4 +211,5 @@ return points;
         previous,
-        x = +point[0],
-        y = +point[1],
+        next,
+        x = +point.x,
+        y = +point.y,
         x0 = this._x0,
@@ -234,7 +231,7 @@ y0 = this._y0,
     // While descending, also retain the deepest parent with a non-removed sibling.
-    if (!node.point) while (true) {
+    if (node.length) while (true) {
       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;
-      if (node.point) break;
+      if (!node.length) break;
       if (parent[(i + 1) & 3] || parent[(i + 2) & 3] || parent[(i + 3) & 3]) retainer = parent, j = i;
@@ -244,12 +241,13 @@ }
     // Find the point to remove.
-    while (node.point !== point) if (!(previous = node, node = node.next)) return false;
+    while (node !== point) if (!(previous = node, node = node.next)) return false;
+    if (next = node.next) delete node.next;
 
     // If there are multiple coincident points, remove just the point.
-    if (previous) return previous.next = node.next, true;
+    if (previous) return (next ? previous.next = next : delete previous.next), true;
 
     // If this is the root point, remove it.
-    if (!parent) return this._root = node.next, true;
+    if (!parent) return this._root = next, true;
 
     // Remove this leaf.
-    parent[i] = node.next;
+    next ? parent[i] = next : delete parent[i];
 
@@ -259,3 +257,3 @@ // If the parent now contains exactly one leaf, collapse superfluous parents.
         && node === (parent[3] || parent[2] || parent[1] || parent[0])
-        && node.point) {
+        && !node.length) {
       if (retainer) retainer[j] = node;
@@ -275,3 +273,3 @@ else this._root = node;
     this.visit(function(node) {
-      if (node.point) do ++size; while (node = node.next)
+      if (!node.length) do ++size; while (node = node.next)
     });
@@ -285,3 +283,3 @@ return size;
     while (q = quads.pop()) {
-      if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1)) {
+      if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1) && node.length) {
         var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
@@ -301,7 +299,10 @@ if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
     while (q = quads.pop()) {
-      var node = q.node, child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
-      if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
-      if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
-      if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
-      if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
+      var node = q.node;
+      if (node.length) {
+        var child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
+        if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
+        if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
+        if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
+        if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
+      }
       next.push(q);
@@ -315,16 +316,23 @@ }
 
-  function quadtree(_) {
-    var tree = new Quadtree(NaN, NaN, NaN, NaN);
-    return _ ? tree.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1]) : tree;
+  function quadtree() {
+    return new Quadtree;
   }
 
   function Quadtree(x0, y0, x1, y1) {
-    this._x0 = x0;
-    this._y0 = y0;
-    this._x1 = x1;
-    this._y1 = y1;
+    this._x0 = +x0;
+    this._y0 = +y0;
+    this._x1 = +x1;
+    this._y1 = +y1;
     this._root = undefined;
   }
 
-  function tree_copy() {
+  function leaf_copy(leaf) {
+    var copy = {x: leaf.x, y: leaf.y}, next = copy;
+    while (leaf = leaf.next) next = next.next = {x: leaf.x, y: leaf.y};
+    return copy;
+  }
+
+  var treeProto = quadtree.prototype = Quadtree.prototype;
+
+  treeProto.copy = function() {
     var copy = new Quadtree(this._x0, this._y0, this._x1, this._y1),
@@ -337,3 +345,3 @@ node = this._root,
 
-    if (node.point) return copy._root = leaf_copy(node), copy;
+    if (!node.length) return copy._root = leaf_copy(node), copy;
 
@@ -344,4 +352,4 @@ nodes = [{source: node, target: copy._root = new Array(4)}];
         if (child = node.source[i]) {
-          if (child.point) node.target[i] = leaf_copy(child);
-          else nodes.push({source: child, target: node.target[i] = new Array(4)});
+          if (child.length) nodes.push({source: child, target: node.target[i] = new Array(4)});
+          else node.target[i] = leaf_copy(child);
         }
@@ -352,13 +360,5 @@ }
     return copy;
-  }
+  };
 
-  function leaf_copy(leaf) {
-    var copy = {point: leaf.point}, next = copy;
-    while (leaf = leaf.next) next = next.next = {point: leaf.point};
-    return copy;
-  }
-
-  var treeProto = Quadtree.prototype = quadtree.prototype;
   treeProto.add = tree_add;
-  treeProto.copy = tree_copy;
   treeProto.cover = tree_cover;
@@ -365,0 +365,0 @@ treeProto.extent = tree_extent;

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

build/package.js

 export var name = "d3-quadtree";
-export var version = "0.5.0";
+export var version = "0.6.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.5.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.5.min.js && cd ../d3.github.com && git add d3-quadtree.v0.5.js d3-quadtree.v0.5.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.6.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.6.min.js && cd ../d3.github.com && git add d3-quadtree.v0.6.js d3-quadtree.v0.6.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.5.0",
+  "version": "0.6.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.5.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.5.min.js && cd ../d3.github.com && git add d3-quadtree.v0.5.js d3-quadtree.v0.5.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.6.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.6.min.js && cd ../d3.github.com && git add d3-quadtree.v0.6.js d3-quadtree.v0.6.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

@@ -14,6 +14,6 @@ # d3-quadtree
 
-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.5.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.6.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.5.min.js"></script>
+<script src="https://d3js.org/d3-quadtree.v0.6.min.js"></script>
 <script>
@@ -30,24 +30,10 @@
 
-<a name="quadtree" href="#quadtree">#</a> d3.<b>quadtree</b>([*extent*])
+<a name="quadtree" href="#quadtree">#</a> d3.<b>quadtree</b>()
 
-Creates a new, empty quadtree. If an *extent* [[*x0*, *y0*], [*x1*, *y1*]] is specified, the [extent](#quadtree_extent) is initialized according to the given values; otherwise, the extent is initially undefined. For example, to initialize a quadtree covering from ⟨0, 0⟩ to ⟨960, 960⟩:
+Creates a new, empty quadtree with an empty [extent](#quadtree_extent).
 
-```js
-var q = d3.quadtree([[0, 0], [960, 960]]);
-```
+<a name="quadtree_extent" href="#quadtree_extent">#</a> <i>quadtree</i>.<b>extent</b>([*extent*])
 
-Or, to add a few points using [method chaining](https://en.wikipedia.org/wiki/Method_chaining):
+If *extent* is specified, expands the quadtree to [cover](#quadtree_cover) the specified points [[*x0*, *y0*], [*x1*, *y1*]] and returns the quadtree. If *extent* is not specified, returns the quadtree’s current extent [[*x0*, *y0*], [*x1*, *y1*]], where *x0* and *y0* are the inclusive lower bounds and *x1* and *y1* are the inclusive upper bounds, or undefined if the quadtree has no extent. The extent may be expanded automatically by calling [*quadtree*.cover](#quadtree_cover) or [*quadtree*.add](#quadtree_add).
 
-```js
-var q = d3.quadtree([[0, 0], [960, 500]])
-    .add([  0,   0])
-    .add([100,   0])
-    .add([  0, 100])
-    .add([100, 100]);
-```
-
-<a name="quadtree_extent" href="#quadtree_extent">#</a> <i>quadtree</i>.<b>extent</b>()
-
-Returns the current extent [[*x0*, *y0*], [*x1*, *y1*]] of this quadtree, where *x0* and *y0* are the inclusive lower bounds and *x1* and *y1* are the inclusive upper bounds, or undefined if this quadtree has no extent. The extent may be initialized when the quadtree is [created](#quadtree), and is expanded by calling [*quadtree*.cover](#quadtree_cover) or [*quadtree*.add](#quadtree_add).
-
 <a name="quadtree_root" href="#quadtree_root">#</a> <i>quadtree</i>.<b>root</b>()
@@ -59,36 +45,31 @@
 
-Expands this quadtree to enclose the specified point ⟨*x*,*y*⟩, and returns this quadtree. If this quadtree’s extent already encloses the specified point, this method does nothing. If this quadtree has a defined and non-trivial extent, the extent is repeatedly doubled to enclose the specified point, wrapping the [root node](#quadtree_root) as necessary; if this quadtree has trivial bounds, *i.e.* if the lower bound ⟨*x0*,*y0*⟩ and upper bound ⟨*x1*,*y1*⟩ are coincident, the extent is expanded to enclose the specified point exactly; otherwise, if the quadtree has no extent, the extent is initialized to the trivial extent [[*x*, *y*], [*x*, *y*]].
+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 a defined and non-trivial extent, the extent is repeatedly doubled to cover the specified point, wrapping the [root](#quadtree_root) [node](#nodes) as necessary; if the quadtree has trivial bounds, *i.e.* if the lower bound ⟨*x0*,*y0*⟩ and upper bound ⟨*x1*,*y1*⟩ are coincident, the extent is expanded to cover the specified point exactly; otherwise, if the quadtree has no extent, the extent is initialized to the trivial extent [[*x*, *y*], [*x*, *y*]].
 
-<a name="quadtree_add" href="#quadtree_add">#</a> <i>quadtree</i>.<b>add</b>(<i>point</i>)
+<a name="quadtree_add" href="#quadtree_add">#</a> <i>quadtree</i>.<b>add</b>(<i>x</i>, <i>y</i>)
 
-Adds the specified new *point* to this quadtree and returns this *quadtree*. If the specified point is outside the current [extent](#quadtree_extent) of this quadtree, this quadtree is automatically expanded to [cover](#quadtree_cover) the new point. The point must be a two-element array of numbers [*x*, *y*] or an object with the following properties:
+Creates a new point ⟨*x*,*y*⟩ (a leaf [node](#nodes)), adds it to the quadtree, and returns it. If the new point is outside the current [extent](#quadtree_extent) of the quadtree, the quadtree is automatically expanded to [cover](#quadtree_cover) the new point.
 
-* `0` - the *x*-coordinate of the point
-* `1` - the *y*-coordinate of the point
-
-These properties **must not change** while the *point* is in the quadtree. To update a point’s position, first [remove](#quadtree_remove) the point, then update its position, and then re-add it to the quadtree. Alternatively, you may discard the existing quadtree entirely and create a new one from scratch; this may be more efficient if many of the points have moved.
-
 <a name="quadtree_remove" href="#quadtree_remove">#</a> <i>quadtree</i>.<b>remove</b>(<i>point</i>)
 
-Removes the specified *point* from this quadtree, returning true if the point was removed or false if this quadtree did not contain the specified point.
+Removes the specified *point* (a leaf [node](#nodes)) from the quadtree, returning true if the point was removed or false if the quadtree did not contain the specified point.
 
 <a name="quadtree_copy" href="#quadtree_copy">#</a> <i>quadtree</i>.<b>copy</b>()
 
-Returns a copy of this quadtree. All [nodes](#nodes) in the returned quadtree are identical copies of the corresponding node in this quadtree; however, the point objects are shared between the original and the copy.
+Returns a copy of the quadtree. All [nodes](#nodes) in the returned quadtree are identical copies of the corresponding node in the quadtree.
 
 <a name="quadtree_size" href="#quadtree_size">#</a> <i>quadtree</i>.<b>size</b>()
 
-Returns the total number of points in the quadtree.
+Returns the total number of points (leaf [nodes](#nodes)) in the quadtree.
 
 <a name="quadtree_points" href="#quadtree_points">#</a> <i>quadtree</i>.<b>points</b>()
 
-Returns an array of all points in the quadtree.
+Returns an array of all points (leaf [nodes](#nodes)) in the quadtree.
 
 <a name="quadtree_find" href="#quadtree_find">#</a> <i>quadtree</i>.<b>find</b>(<i>x</i>, <i>y</i>)
 
-Given a point ⟨*x*,*y*⟩, returns the closest point in this quadtree. If this quadtree is empty, returns undefined.
+Given a point ⟨*x*,*y*⟩, returns the closest point in the quadtree. If the quadtree is empty, returns undefined.
 
 <a name="quadtree_visit" href="#quadtree_visit">#</a> <i>quadtree</i>.<b>visit</b>(<i>callback</i>)
 
-Visits each [node](#nodes) 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*.)
+Visits each [node](#nodes) in the 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 the 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*.)
 
@@ -99,3 +80,3 @@ 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.
 
-Visits each [node](#nodes) 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*.
+Visits each [node](#nodes) in the 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 the 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*.
 
@@ -115,9 +96,12 @@ ### Nodes
 
-* `point` - the point, as passed to [*quadtree*.add](#quadtree_add)
+* `x` - the *x*-coordinate of the point, as passed to [*quadtree*.add](#quadtree_add)
+* `y` - the *y*-coordinate of the point, as passed to [*quadtree*.add](#quadtree_add)
 * `next` - the next point in this leaf, if any
 
-For example, to iterate over all points in a leaf node:
+The `length` property may be used to distinguish leaf nodes from internal nodes: it is undefined for leaf nodes, and 4 for internal nodes. For example, to iterate over all points in a leaf node:
 
 ```js
-if (node.point) do console.log(node.point); while (node = node.next)
+if (!node.length) do console.log(node); while (node = node.next)
 ```
+
+The point’s *x*- and *y*-coordinates **must not be modified** while the point is in the quadtree. To update a point’s position, [remove](#quadtree_remove) the point and then re-[add](#quadtree_add) it to the quadtree at the new position. Alternatively, you may discard the existing quadtree entirely and create a new one from scratch; this may be more efficient if many of the points have moved.

src/add.js

@@ -1,11 +0,6 @@
-export default function(point) {
-  if (isNaN(x = +point[0]) || isNaN(y = +point[1])) return this; // ignore invalid points
+export default function(x, y) {
+  if (isNaN(x = +x) || isNaN(y = +y)) return; // ignore invalid points
 
-  // Expand the tree to cover the new point, if necessary.
-  this.cover(x, y);
-
-  var node = this._root,
+  var node = this.cover(x, y)._root,
       parent,
-      x,
-      y,
       x0 = this._x0,
@@ -25,18 +20,15 @@ y0 = this._y0,
   // If the tree is empty, initialize the root as a leaf.
-  if (!node) return this._root = {point: point}, this;
+  if (!node) return this._root = {x: x, y: y};
 
-  // Find the appropriate leaf node for the new point.
-  // If there is no leaf node, add it.
-  while (!node.point) {
+  // Find the existing leaf for the new point, or add it.
+  while (node.length) {
     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 parent[i] = {point: point}, this;
+    if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = {x: x, y: y};
   }
 
-  // If the new point is exactly coincident with the specified point, add it.
-  if (xp = node.point[0], yp = node.point[1], x === xp && y === yp) {
-    node = {point: point, next: node};
-    if (parent) parent[i] = node;
-    else this._root = node;
-    return this;
+  // Is the new point is exactly coincident with the existing point?
+  if (xp = node.x, yp = node.y, x === xp && y === yp) {
+    node = {x: x, y: y, next: node};
+    return parent ? parent[i] = node : this._root = node;
   }
@@ -50,6 +42,3 @@
   } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));
-
-  parent[i] = {point: point};
-  parent[j] = node;
-  return this;
+  return parent[j] = node, parent[i] = {x: x, y: y};
 }

src/cover.js

@@ -41,3 +41,3 @@ export default function(x, y) {
       }
-      if (this._root && !this._root.point) this._root = node;
+      if (this._root && this._root.length) this._root = node;
     }
@@ -44,0 +44,0 @@

src/extent.js

@@ -1,3 +0,5 @@
-export default function() {
-  if (!isNaN(this._x0)) return [[this._x0, this._y0], [this._x1, this._y1]];
+export default function(_) {
+  return arguments.length
+      ? this.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1])
+      : isNaN(this._x0) ? undefined : [[this._x0, this._y0], [this._x1, this._y1]];
 }

src/find.js

@@ -22,11 +22,34 @@ import Quad from "./quad";
   while (q = quads.pop()) {
-    node = q.node, x1 = q.x0, y1 = q.y0, x2 = q.x1, y2 = q.y1;
 
     // Stop searching if this quadrant can’t contain a closer node.
-    if (!node || x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) continue;
+    if (!(node = q.node)
+        || (x1 = q.x0) > x3
+        || (y1 = q.y0) > y3
+        || (x2 = q.x1) < x0
+        || (y2 = q.y1) < y0) continue;
 
+    // Bisect the current quadrant.
+    if (node.length) {
+      var xm = (x1 + x2) / 2,
+          ym = (y1 + y2) / 2;
+
+      quads.push(
+        new Quad(node[3], xm, ym, x2, y2),
+        new Quad(node[2], x1, ym, xm, y2),
+        new Quad(node[1], xm, y1, x2, ym),
+        new Quad(node[0], x1, y1, xm, ym)
+      );
+
+      // Visit the closest quadrant first.
+      if (i = (y >= ym) << 1 | (x >= xm)) {
+        q = quads[quads.length - 1];
+        quads[quads.length - 1] = quads[quads.length - 1 - i];
+        quads[quads.length - 1 - i] = q;
+      }
+    }
+
     // Visit this point. (Visiting coincident points isn’t necessary!)
-    if (node.point) {
-      var dx = x - node.point[0],
-          dy = y - node.point[1],
+    else {
+      var dx = x - node.x,
+          dy = y - node.y,
           d2 = dx * dx + dy * dy;
@@ -37,23 +60,5 @@ if (d2 < minDistance2) {
         x3 = x + d, y3 = y + d;
-        minPoint = node.point;
+        minPoint = node;
       }
     }
-
-    // Bisect the current quadrant.
-    var xm = (x1 + x2) / 2,
-        ym = (y1 + y2) / 2;
-
-    quads.push(
-      new Quad(node[3], xm, ym, x2, y2),
-      new Quad(node[2], x1, ym, xm, y2),
-      new Quad(node[1], xm, y1, x2, ym),
-      new Quad(node[0], x1, y1, xm, ym)
-    );
-
-    // Visit the closest quadrant first.
-    if (i = (y >= ym) << 1 | (x >= xm)) {
-      q = quads[quads.length - 1];
-      quads[quads.length - 1] = quads[quads.length - 1 - i];
-      quads[quads.length - 1 - i] = q;
-    }
   }
@@ -60,0 +65,0 @@

src/points.js

 export default function() {
   var points = [];
   this.visit(function(node) {
-    if (node.point) do points.push(node.point); while (node = node.next)
+    if (!node.length) do points.push(node); while (node = node.next)
   });
   return points;
 }

src/quadtree.js

@@ -12,16 +12,23 @@ import tree_add from "./add";
 
-export default function quadtree(_) {
-  var tree = new Quadtree(NaN, NaN, NaN, NaN);
-  return _ ? tree.cover(+_[0][0], +_[0][1]).cover(+_[1][0], +_[1][1]) : tree;
+export default function quadtree() {
+  return new Quadtree;
 }
 
 function Quadtree(x0, y0, x1, y1) {
-  this._x0 = x0;
-  this._y0 = y0;
-  this._x1 = x1;
-  this._y1 = y1;
+  this._x0 = +x0;
+  this._y0 = +y0;
+  this._x1 = +x1;
+  this._y1 = +y1;
   this._root = undefined;
 }
 
-function tree_copy() {
+function leaf_copy(leaf) {
+  var copy = {x: leaf.x, y: leaf.y}, next = copy;
+  while (leaf = leaf.next) next = next.next = {x: leaf.x, y: leaf.y};
+  return copy;
+}
+
+var treeProto = quadtree.prototype = Quadtree.prototype;
+
+treeProto.copy = function() {
   var copy = new Quadtree(this._x0, this._y0, this._x1, this._y1),
@@ -34,3 +41,3 @@ node = this._root,
 
-  if (node.point) return copy._root = leaf_copy(node), copy;
+  if (!node.length) return copy._root = leaf_copy(node), copy;
 
@@ -41,4 +48,4 @@ nodes = [{source: node, target: copy._root = new Array(4)}];
       if (child = node.source[i]) {
-        if (child.point) node.target[i] = leaf_copy(child);
-        else nodes.push({source: child, target: node.target[i] = new Array(4)});
+        if (child.length) nodes.push({source: child, target: node.target[i] = new Array(4)});
+        else node.target[i] = leaf_copy(child);
       }
@@ -49,13 +56,5 @@ }
   return copy;
-}
+};
 
-function leaf_copy(leaf) {
-  var copy = {point: leaf.point}, next = copy;
-  while (leaf = leaf.next) next = next.next = {point: leaf.point};
-  return copy;
-}
-
-var treeProto = Quadtree.prototype = quadtree.prototype;
 treeProto.add = tree_add;
-treeProto.copy = tree_copy;
 treeProto.cover = tree_cover;
@@ -62,0 +61,0 @@ treeProto.extent = tree_extent;

src/remove.js

@@ -6,4 +6,5 @@ export default function(point) {
       previous,
-      x = +point[0],
-      y = +point[1],
+      next,
+      x = +point.x,
+      y = +point.y,
       x0 = this._x0,
@@ -25,7 +26,7 @@ y0 = this._y0,
   // While descending, also retain the deepest parent with a non-removed sibling.
-  if (!node.point) while (true) {
+  if (node.length) while (true) {
     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;
-    if (node.point) break;
+    if (!node.length) break;
     if (parent[(i + 1) & 3] || parent[(i + 2) & 3] || parent[(i + 3) & 3]) retainer = parent, j = i;
@@ -35,12 +36,13 @@ }
   // Find the point to remove.
-  while (node.point !== point) if (!(previous = node, node = node.next)) return false;
+  while (node !== point) if (!(previous = node, node = node.next)) return false;
+  if (next = node.next) delete node.next;
 
   // If there are multiple coincident points, remove just the point.
-  if (previous) return previous.next = node.next, true;
+  if (previous) return (next ? previous.next = next : delete previous.next), true;
 
   // If this is the root point, remove it.
-  if (!parent) return this._root = node.next, true;
+  if (!parent) return this._root = next, true;
 
   // Remove this leaf.
-  parent[i] = node.next;
+  next ? parent[i] = next : delete parent[i];
 
@@ -50,3 +52,3 @@ // If the parent now contains exactly one leaf, collapse superfluous parents.
       && node === (parent[3] || parent[2] || parent[1] || parent[0])
-      && node.point) {
+      && !node.length) {
     if (retainer) retainer[j] = node;
@@ -53,0 +55,0 @@ else this._root = node;

src/size.js

 export default function() {
   var size = 0;
   this.visit(function(node) {
-    if (node.point) do ++size; while (node = node.next)
+    if (!node.length) do ++size; while (node = node.next)
   });
   return size;
 }

src/visit.js

@@ -7,3 +7,3 @@ import Quad from "./quad";
   while (q = quads.pop()) {
-    if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1)) {
+    if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1) && node.length) {
       var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
@@ -10,0 +10,0 @@ if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));

src/visitAfter.js

@@ -7,7 +7,10 @@ import Quad from "./quad";
   while (q = quads.pop()) {
-    var node = q.node, child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
-    if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
-    if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
-    if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
-    if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
+    var node = q.node;
+    if (node.length) {
+      var child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
+      if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
+      if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
+      if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
+      if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
+    }
     next.push(q);
@@ -14,0 +17,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

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

Improved metrics

Lines of code

632

increased by0.32%

Number of medium supply chain risk alerts

0

decreased by-100%

Worsened metrics

Total package byte prevSize

38200

decreased by-0.96%

Number of lines in readme file

103

decreased by-13.45%

No dependency changes