d3-octree - npm Package Compare versions

Comparing version 0.1.8 to 0.2.0

dist/d3-octree.js

@@ -1,6 +0,6 @@
-// https://github.com/vasturiano/d3-octree v0.1.8 Copyright 2020 Vasco Asturiano
+// https://github.com/vasturiano/d3-octree v0.2.0 Copyright 2021 Vasco Asturiano
 (function (global, factory) {
 typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
 typeof define === 'function' && define.amd ? define(['exports'], factory) :
-(global = global || self, factory(global.d3 = global.d3 || {}));
+(global = typeof globalThis !== 'undefined' ? globalThis : global || self, factory(global.d3 = global.d3 || {}));
 }(this, (function (exports) { 'use strict';
@@ -95,6 +95,4 @@
 
-  // If there were no (valid) points, inherit the existing extent.
-  if (x1 < x0) x0 = this._x0, x1 = this._x1;
-  if (y1 < y0) y0 = this._y0, y1 = this._y1;
-  if (z1 < z0) z0 = this._z0, z1 = this._z1;
+  // If there were no (valid) points, abort.
+  if (x0 > x1 || y0 > y1 || z0 > z1) return this;
 
@@ -132,4 +130,4 @@ // Expand the tree to cover the new points.
   // Otherwise, double repeatedly to cover.
-  else if (x0 > x || x > x1 || y0 > y || y > y1 || z0 > z || z > z1) {
-    var t = x1 - x0,
+  else {
+    var t = x1 - x0 || 1,
         node = this._root,
@@ -139,43 +137,15 @@ parent,
 
-    switch (i = (z < (z0 + z1) / 2) << 2 | (y < (y0 + y1) / 2) << 1 | (x < (x0 + x1) / 2)) {
-      case 0: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x1 = x0 + t, y1 = y0 + t, z1 = z0 + t, x > x1 || y > y1 || z > z1);
-        break;
+    while (x0 > x || x >= x1 || y0 > y || y >= y1 || z0 > z || z >= z1) {
+      i = (z < z0) << 2 | (y < y0) << 1 | (x < x0);
+      parent = new Array(8), parent[i] = node, node = parent, t *= 2;
+      switch (i) {
+        case 0: x1 = x0 + t, y1 = y0 + t, z1 = z0 + t; break;
+        case 1: x0 = x1 - t, y1 = y0 + t, z1 = z0 + t; break;
+        case 2: x1 = x0 + t, y0 = y1 - t, z1 = z0 + t; break;
+        case 3: x0 = x1 - t, y0 = y1 - t, z1 = z0 + t; break;
+        case 4: x1 = x0 + t, y1 = y0 + t, z0 = z1 - t; break;
+        case 5: x0 = x1 - t, y1 = y0 + t, z0 = z1 - t; break;
+        case 6: x1 = x0 + t, y0 = y1 - t, z0 = z1 - t; break;
+        case 7: x0 = x1 - t, y0 = y1 - t, z0 = z1 - t; break;
       }
-      case 1: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x0 = x1 - t, y1 = y0 + t, z1 = z0 + t, x0 > x || y > y1 || z > z1);
-        break;
-      }
-      case 2: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x1 = x0 + t, y0 = y1 - t, z1 = z0 + t, x > x1 || y0 > y || z > z1);
-        break;
-      }
-      case 3: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x0 = x1 - t, y0 = y1 - t, z1 = z0 + t, x0 > x || y0 > y || z > z1);
-        break;
-      }
-      case 4: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x1 = x0 + t, y1 = y0 + t, z0 = z1 - t, x > x1 || y > y1 || z0 > z);
-        break;
-      }
-      case 5: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x0 = x1 - t, y1 = y0 + t, z0 = z1 - t, x0 > x || y > y1 || z0 > z);
-        break;
-      }
-      case 6: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x1 = x0 + t, y0 = y1 - t, z0 = z1 - t, x > x1 || y0 > y || z0 > z);
-        break;
-      }
-      case 7: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x0 = x1 - t, y0 = y1 - t, z0 = z1 - t, x0 > x || y0 > y || z0 > z);
-        break;
-      }
     }
@@ -186,5 +156,2 @@
 
-  // If the octree covers the point already, just return.
-  else return this;
-
   this._x0 = x0;
@@ -191,0 +158,0 @@ this._y0 = y0;

dist/d3-octree.min.js

@@ -1,2 +0,2 @@
-// https://github.com/vasturiano/d3-octree v0.1.8 Copyright 2020 Vasco Asturiano
-!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i((t=t||self).d3=t.d3||{})}(this,(function(t){"use strict";function i(t,i,e,n,s){if(isNaN(i)||isNaN(e)||isNaN(n))return t;var r,h,o,a,l,_,u,f,c,y,x,w,d=t._root,p={data:s},z=t._x0,N=t._y0,v=t._z0,g=t._x1,A=t._y1,b=t._z1;if(!d)return t._root=p,t;for(;d.length;)if((f=i>=(h=(z+g)/2))?z=h:g=h,(c=e>=(o=(N+A)/2))?N=o:A=o,(y=n>=(a=(v+b)/2))?v=a:b=a,r=d,!(d=d[x=y<<2|c<<1|f]))return r[x]=p,t;if(l=+t._x.call(null,d.data),_=+t._y.call(null,d.data),u=+t._z.call(null,d.data),i===l&&e===_&&n===u)return p.next=d,r?r[x]=p:t._root=p,t;do{r=r?r[x]=new Array(8):t._root=new Array(8),(f=i>=(h=(z+g)/2))?z=h:g=h,(c=e>=(o=(N+A)/2))?N=o:A=o,(y=n>=(a=(v+b)/2))?v=a:b=a}while((x=y<<2|c<<1|f)==(w=(u>=a)<<2|(_>=o)<<1|l>=h));return r[w]=d,r[x]=p,t}function e(t,i,e,n,s,r,h){this.node=t,this.x0=i,this.y0=e,this.z0=n,this.x1=s,this.y1=r,this.z1=h}function n(t){return t[0]}function s(t){return t[1]}function r(t){return t[2]}function h(t,i,e,h){var a=new o(null==i?n:i,null==e?s:e,null==h?r:h,NaN,NaN,NaN,NaN,NaN,NaN);return null==t?a:a.addAll(t)}function o(t,i,e,n,s,r,h,o,a){this._x=t,this._y=i,this._z=e,this._x0=n,this._y0=s,this._z0=r,this._x1=h,this._y1=o,this._z1=a,this._root=void 0}function a(t){for(var i={data:t.data},e=i;t=t.next;)e=e.next={data:t.data};return i}var l=h.prototype=o.prototype;l.copy=function(){var t,i,e=new o(this._x,this._y,this._z,this._x0,this._y0,this._z0,this._x1,this._y1,this._z1),n=this._root;if(!n)return e;if(!n.length)return e._root=a(n),e;for(t=[{source:n,target:e._root=new Array(8)}];n=t.pop();)for(var s=0;s<8;++s)(i=n.source[s])&&(i.length?t.push({source:i,target:n.target[s]=new Array(8)}):n.target[s]=a(i));return e},l.add=function(t){var e=+this._x.call(null,t),n=+this._y.call(null,t),s=+this._z.call(null,t);return i(this.cover(e,n,s),e,n,s,t)},l.addAll=function(t){var e,n,s,r,h,o=t.length,a=new Array(o),l=new Array(o),_=new Array(o),u=1/0,f=1/0,c=1/0,y=-1/0,x=-1/0,w=-1/0;for(n=0;n<o;++n)isNaN(s=+this._x.call(null,e=t[n]))||isNaN(r=+this._y.call(null,e))||isNaN(h=+this._z.call(null,e))||(a[n]=s,l[n]=r,_[n]=h,s<u&&(u=s),s>y&&(y=s),r<f&&(f=r),r>x&&(x=r),h<c&&(c=h),h>w&&(w=h));for(y<u&&(u=this._x0,y=this._x1),x<f&&(f=this._y0,x=this._y1),w<c&&(c=this._z0,w=this._z1),this.cover(u,f,c).cover(y,x,w),n=0;n<o;++n)i(this,a[n],l[n],_[n],t[n]);return this},l.cover=function(t,i,e){if(isNaN(t=+t)||isNaN(i=+i)||isNaN(e=+e))return this;var n=this._x0,s=this._y0,r=this._z0,h=this._x1,o=this._y1,a=this._z1;if(isNaN(n))h=(n=Math.floor(t))+1,o=(s=Math.floor(i))+1,a=(r=Math.floor(e))+1;else{if(!(n>t||t>h||s>i||i>o||r>e||e>a))return this;var l,_,u=h-n,f=this._root;switch(_=(e<(r+a)/2)<<2|(i<(s+o)/2)<<1|t<(n+h)/2){case 0:do{(l=new Array(8))[_]=f,f=l}while(o=s+(u*=2),a=r+u,t>(h=n+u)||i>o||e>a);break;case 1:do{(l=new Array(8))[_]=f,f=l}while(o=s+(u*=2),a=r+u,(n=h-u)>t||i>o||e>a);break;case 2:do{(l=new Array(8))[_]=f,f=l}while(s=o-(u*=2),a=r+u,t>(h=n+u)||s>i||e>a);break;case 3:do{(l=new Array(8))[_]=f,f=l}while(s=o-(u*=2),a=r+u,(n=h-u)>t||s>i||e>a);break;case 4:do{(l=new Array(8))[_]=f,f=l}while(o=s+(u*=2),r=a-u,t>(h=n+u)||i>o||r>e);break;case 5:do{(l=new Array(8))[_]=f,f=l}while(o=s+(u*=2),r=a-u,(n=h-u)>t||i>o||r>e);break;case 6:do{(l=new Array(8))[_]=f,f=l}while(s=o-(u*=2),r=a-u,t>(h=n+u)||s>i||r>e);break;case 7:do{(l=new Array(8))[_]=f,f=l}while(s=o-(u*=2),r=a-u,(n=h-u)>t||s>i||r>e)}this._root&&this._root.length&&(this._root=f)}return this._x0=n,this._y0=s,this._z0=r,this._x1=h,this._y1=o,this._z1=a,this},l.data=function(){var t=[];return this.visit((function(i){if(!i.length)do{t.push(i.data)}while(i=i.next)})),t},l.extent=function(t){return arguments.length?this.cover(+t[0][0],+t[0][1],+t[0][2]).cover(+t[1][0],+t[1][1],+t[1][2]):isNaN(this._x0)?void 0:[[this._x0,this._y0,this._z0],[this._x1,this._y1,this._z1]]},l.find=function(t,i,n,s){var r,h,o,a,l,_,u,f,c,y=this._x0,x=this._y0,w=this._z0,d=this._x1,p=this._y1,z=this._z1,N=[],v=this._root;for(v&&N.push(new e(v,y,x,w,d,p,z)),null==s?s=1/0:(y=t-s,x=i-s,w=n-s,d=t+s,p=i+s,z=n+s,s*=s);f=N.pop();)if(!(!(v=f.node)||(h=f.x0)>d||(o=f.y0)>p||(a=f.z0)>z||(l=f.x1)<y||(_=f.y1)<x||(u=f.z1)<w))if(v.length){var g=(h+l)/2,A=(o+_)/2,b=(a+u)/2;N.push(new e(v[7],g,A,b,l,_,u),new e(v[6],h,A,b,g,_,u),new e(v[5],g,o,b,l,A,u),new e(v[4],h,o,b,g,A,u),new e(v[3],g,A,a,l,_,b),new e(v[2],h,A,a,g,_,b),new e(v[1],g,o,a,l,A,b),new e(v[0],h,o,a,g,A,b)),(c=(n>=b)<<2|(i>=A)<<1|t>=g)&&(f=N[N.length-1],N[N.length-1]=N[N.length-1-c],N[N.length-1-c]=f)}else{var k=t-+this._x.call(null,v.data),m=i-+this._y.call(null,v.data),M=n-+this._z.call(null,v.data),j=k*k+m*m+M*M;if(j<s){var q=Math.sqrt(s=j);y=t-q,x=i-q,w=n-q,d=t+q,p=i+q,z=n+q,r=v.data}}return r},l.remove=function(t){if(isNaN(r=+this._x.call(null,t))||isNaN(h=+this._y.call(null,t))||isNaN(o=+this._z.call(null,t)))return this;var i,e,n,s,r,h,o,a,l,_,u,f,c,y,x,w=this._root,d=this._x0,p=this._y0,z=this._z0,N=this._x1,v=this._y1,g=this._z1;if(!w)return this;if(w.length)for(;;){if((u=r>=(a=(d+N)/2))?d=a:N=a,(f=h>=(l=(p+v)/2))?p=l:v=l,(c=o>=(_=(z+g)/2))?z=_:g=_,i=w,!(w=w[y=c<<2|f<<1|u]))return this;if(!w.length)break;(i[y+1&7]||i[y+2&7]||i[y+3&7]||i[y+4&7]||i[y+5&7]||i[y+6&7]||i[y+7&7])&&(e=i,x=y)}for(;w.data!==t;)if(n=w,!(w=w.next))return this;return(s=w.next)&&delete w.next,n?(s?n.next=s:delete n.next,this):i?(s?i[y]=s:delete i[y],(w=i[0]||i[1]||i[2]||i[3]||i[4]||i[5]||i[6]||i[7])&&w===(i[7]||i[6]||i[5]||i[4]||i[3]||i[2]||i[1]||i[0])&&!w.length&&(e?e[x]=w:this._root=w),this):(this._root=s,this)},l.removeAll=function(t){for(var i=0,e=t.length;i<e;++i)this.remove(t[i]);return this},l.root=function(){return this._root},l.size=function(){var t=0;return this.visit((function(i){if(!i.length)do{++t}while(i=i.next)})),t},l.visit=function(t){var i,n,s,r,h,o,a,l,_=[],u=this._root;for(u&&_.push(new e(u,this._x0,this._y0,this._z0,this._x1,this._y1,this._z1));i=_.pop();)if(!t(u=i.node,s=i.x0,r=i.y0,h=i.z0,o=i.x1,a=i.y1,l=i.z1)&&u.length){var f=(s+o)/2,c=(r+a)/2,y=(h+l)/2;(n=u[7])&&_.push(new e(n,f,c,y,o,a,l)),(n=u[6])&&_.push(new e(n,s,c,y,f,a,l)),(n=u[5])&&_.push(new e(n,f,r,y,o,c,l)),(n=u[4])&&_.push(new e(n,s,r,y,f,c,l)),(n=u[3])&&_.push(new e(n,f,c,h,o,a,y)),(n=u[2])&&_.push(new e(n,s,c,h,f,a,y)),(n=u[1])&&_.push(new e(n,f,r,h,o,c,y)),(n=u[0])&&_.push(new e(n,s,r,h,f,c,y))}return this},l.visitAfter=function(t){var i,n=[],s=[];for(this._root&&n.push(new e(this._root,this._x0,this._y0,this._z0,this._x1,this._y1,this._z1));i=n.pop();){var r=i.node;if(r.length){var h,o=i.x0,a=i.y0,l=i.z0,_=i.x1,u=i.y1,f=i.z1,c=(o+_)/2,y=(a+u)/2,x=(l+f)/2;(h=r[0])&&n.push(new e(h,o,a,l,c,y,x)),(h=r[1])&&n.push(new e(h,c,a,l,_,y,x)),(h=r[2])&&n.push(new e(h,o,y,l,c,u,x)),(h=r[3])&&n.push(new e(h,c,y,l,_,u,x)),(h=r[4])&&n.push(new e(h,o,a,x,c,y,f)),(h=r[5])&&n.push(new e(h,c,a,x,_,y,f)),(h=r[6])&&n.push(new e(h,o,y,x,c,u,f)),(h=r[7])&&n.push(new e(h,c,y,x,_,u,f))}s.push(i)}for(;i=s.pop();)t(i.node,i.x0,i.y0,i.z0,i.x1,i.y1,i.z1);return this},l.x=function(t){return arguments.length?(this._x=t,this):this._x},l.y=function(t){return arguments.length?(this._y=t,this):this._y},l.z=function(t){return arguments.length?(this._z=t,this):this._z},t.octree=h,Object.defineProperty(t,"__esModule",{value:!0})}));
+// https://github.com/vasturiano/d3-octree v0.2.0 Copyright 2021 Vasco Asturiano
+!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i((t="undefined"!=typeof globalThis?globalThis:t||self).d3=t.d3||{})}(this,(function(t){"use strict";function i(t,i,n,e,s){if(isNaN(i)||isNaN(n)||isNaN(e))return t;var h,r,o,a,l,u,_,f,c,y,x,d,p=t._root,w={data:s},z=t._x0,N=t._y0,v=t._z0,g=t._x1,b=t._y1,A=t._z1;if(!p)return t._root=w,t;for(;p.length;)if((f=i>=(r=(z+g)/2))?z=r:g=r,(c=n>=(o=(N+b)/2))?N=o:b=o,(y=e>=(a=(v+A)/2))?v=a:A=a,h=p,!(p=p[x=y<<2|c<<1|f]))return h[x]=w,t;if(l=+t._x.call(null,p.data),u=+t._y.call(null,p.data),_=+t._z.call(null,p.data),i===l&&n===u&&e===_)return w.next=p,h?h[x]=w:t._root=w,t;do{h=h?h[x]=new Array(8):t._root=new Array(8),(f=i>=(r=(z+g)/2))?z=r:g=r,(c=n>=(o=(N+b)/2))?N=o:b=o,(y=e>=(a=(v+A)/2))?v=a:A=a}while((x=y<<2|c<<1|f)==(d=(_>=a)<<2|(u>=o)<<1|l>=r));return h[d]=p,h[x]=w,t}function n(t,i,n,e,s,h,r){this.node=t,this.x0=i,this.y0=n,this.z0=e,this.x1=s,this.y1=h,this.z1=r}function e(t){return t[0]}function s(t){return t[1]}function h(t){return t[2]}function r(t,i,n,r){var a=new o(null==i?e:i,null==n?s:n,null==r?h:r,NaN,NaN,NaN,NaN,NaN,NaN);return null==t?a:a.addAll(t)}function o(t,i,n,e,s,h,r,o,a){this._x=t,this._y=i,this._z=n,this._x0=e,this._y0=s,this._z0=h,this._x1=r,this._y1=o,this._z1=a,this._root=void 0}function a(t){for(var i={data:t.data},n=i;t=t.next;)n=n.next={data:t.data};return i}var l=r.prototype=o.prototype;l.copy=function(){var t,i,n=new o(this._x,this._y,this._z,this._x0,this._y0,this._z0,this._x1,this._y1,this._z1),e=this._root;if(!e)return n;if(!e.length)return n._root=a(e),n;for(t=[{source:e,target:n._root=new Array(8)}];e=t.pop();)for(var s=0;s<8;++s)(i=e.source[s])&&(i.length?t.push({source:i,target:e.target[s]=new Array(8)}):e.target[s]=a(i));return n},l.add=function(t){var n=+this._x.call(null,t),e=+this._y.call(null,t),s=+this._z.call(null,t);return i(this.cover(n,e,s),n,e,s,t)},l.addAll=function(t){var n,e,s,h,r,o=t.length,a=new Array(o),l=new Array(o),u=new Array(o),_=1/0,f=1/0,c=1/0,y=-1/0,x=-1/0,d=-1/0;for(e=0;e<o;++e)isNaN(s=+this._x.call(null,n=t[e]))||isNaN(h=+this._y.call(null,n))||isNaN(r=+this._z.call(null,n))||(a[e]=s,l[e]=h,u[e]=r,s<_&&(_=s),s>y&&(y=s),h<f&&(f=h),h>x&&(x=h),r<c&&(c=r),r>d&&(d=r));if(_>y||f>x||c>d)return this;for(this.cover(_,f,c).cover(y,x,d),e=0;e<o;++e)i(this,a[e],l[e],u[e],t[e]);return this},l.cover=function(t,i,n){if(isNaN(t=+t)||isNaN(i=+i)||isNaN(n=+n))return this;var e=this._x0,s=this._y0,h=this._z0,r=this._x1,o=this._y1,a=this._z1;if(isNaN(e))r=(e=Math.floor(t))+1,o=(s=Math.floor(i))+1,a=(h=Math.floor(n))+1;else{for(var l,u,_=r-e||1,f=this._root;e>t||t>=r||s>i||i>=o||h>n||n>=a;)switch(u=(n<h)<<2|(i<s)<<1|t<e,(l=new Array(8))[u]=f,f=l,_*=2,u){case 0:r=e+_,o=s+_,a=h+_;break;case 1:e=r-_,o=s+_,a=h+_;break;case 2:r=e+_,s=o-_,a=h+_;break;case 3:e=r-_,s=o-_,a=h+_;break;case 4:r=e+_,o=s+_,h=a-_;break;case 5:e=r-_,o=s+_,h=a-_;break;case 6:r=e+_,s=o-_,h=a-_;break;case 7:e=r-_,s=o-_,h=a-_}this._root&&this._root.length&&(this._root=f)}return this._x0=e,this._y0=s,this._z0=h,this._x1=r,this._y1=o,this._z1=a,this},l.data=function(){var t=[];return this.visit((function(i){if(!i.length)do{t.push(i.data)}while(i=i.next)})),t},l.extent=function(t){return arguments.length?this.cover(+t[0][0],+t[0][1],+t[0][2]).cover(+t[1][0],+t[1][1],+t[1][2]):isNaN(this._x0)?void 0:[[this._x0,this._y0,this._z0],[this._x1,this._y1,this._z1]]},l.find=function(t,i,e,s){var h,r,o,a,l,u,_,f,c,y=this._x0,x=this._y0,d=this._z0,p=this._x1,w=this._y1,z=this._z1,N=[],v=this._root;for(v&&N.push(new n(v,y,x,d,p,w,z)),null==s?s=1/0:(y=t-s,x=i-s,d=e-s,p=t+s,w=i+s,z=e+s,s*=s);f=N.pop();)if(!(!(v=f.node)||(r=f.x0)>p||(o=f.y0)>w||(a=f.z0)>z||(l=f.x1)<y||(u=f.y1)<x||(_=f.z1)<d))if(v.length){var g=(r+l)/2,b=(o+u)/2,A=(a+_)/2;N.push(new n(v[7],g,b,A,l,u,_),new n(v[6],r,b,A,g,u,_),new n(v[5],g,o,A,l,b,_),new n(v[4],r,o,A,g,b,_),new n(v[3],g,b,a,l,u,A),new n(v[2],r,b,a,g,u,A),new n(v[1],g,o,a,l,b,A),new n(v[0],r,o,a,g,b,A)),(c=(e>=A)<<2|(i>=b)<<1|t>=g)&&(f=N[N.length-1],N[N.length-1]=N[N.length-1-c],N[N.length-1-c]=f)}else{var k=t-+this._x.call(null,v.data),m=i-+this._y.call(null,v.data),M=e-+this._z.call(null,v.data),j=k*k+m*m+M*M;if(j<s){var T=Math.sqrt(s=j);y=t-T,x=i-T,d=e-T,p=t+T,w=i+T,z=e+T,h=v.data}}return h},l.remove=function(t){if(isNaN(h=+this._x.call(null,t))||isNaN(r=+this._y.call(null,t))||isNaN(o=+this._z.call(null,t)))return this;var i,n,e,s,h,r,o,a,l,u,_,f,c,y,x,d=this._root,p=this._x0,w=this._y0,z=this._z0,N=this._x1,v=this._y1,g=this._z1;if(!d)return this;if(d.length)for(;;){if((_=h>=(a=(p+N)/2))?p=a:N=a,(f=r>=(l=(w+v)/2))?w=l:v=l,(c=o>=(u=(z+g)/2))?z=u:g=u,i=d,!(d=d[y=c<<2|f<<1|_]))return this;if(!d.length)break;(i[y+1&7]||i[y+2&7]||i[y+3&7]||i[y+4&7]||i[y+5&7]||i[y+6&7]||i[y+7&7])&&(n=i,x=y)}for(;d.data!==t;)if(e=d,!(d=d.next))return this;return(s=d.next)&&delete d.next,e?(s?e.next=s:delete e.next,this):i?(s?i[y]=s:delete i[y],(d=i[0]||i[1]||i[2]||i[3]||i[4]||i[5]||i[6]||i[7])&&d===(i[7]||i[6]||i[5]||i[4]||i[3]||i[2]||i[1]||i[0])&&!d.length&&(n?n[x]=d:this._root=d),this):(this._root=s,this)},l.removeAll=function(t){for(var i=0,n=t.length;i<n;++i)this.remove(t[i]);return this},l.root=function(){return this._root},l.size=function(){var t=0;return this.visit((function(i){if(!i.length)do{++t}while(i=i.next)})),t},l.visit=function(t){var i,e,s,h,r,o,a,l,u=[],_=this._root;for(_&&u.push(new n(_,this._x0,this._y0,this._z0,this._x1,this._y1,this._z1));i=u.pop();)if(!t(_=i.node,s=i.x0,h=i.y0,r=i.z0,o=i.x1,a=i.y1,l=i.z1)&&_.length){var f=(s+o)/2,c=(h+a)/2,y=(r+l)/2;(e=_[7])&&u.push(new n(e,f,c,y,o,a,l)),(e=_[6])&&u.push(new n(e,s,c,y,f,a,l)),(e=_[5])&&u.push(new n(e,f,h,y,o,c,l)),(e=_[4])&&u.push(new n(e,s,h,y,f,c,l)),(e=_[3])&&u.push(new n(e,f,c,r,o,a,y)),(e=_[2])&&u.push(new n(e,s,c,r,f,a,y)),(e=_[1])&&u.push(new n(e,f,h,r,o,c,y)),(e=_[0])&&u.push(new n(e,s,h,r,f,c,y))}return this},l.visitAfter=function(t){var i,e=[],s=[];for(this._root&&e.push(new n(this._root,this._x0,this._y0,this._z0,this._x1,this._y1,this._z1));i=e.pop();){var h=i.node;if(h.length){var r,o=i.x0,a=i.y0,l=i.z0,u=i.x1,_=i.y1,f=i.z1,c=(o+u)/2,y=(a+_)/2,x=(l+f)/2;(r=h[0])&&e.push(new n(r,o,a,l,c,y,x)),(r=h[1])&&e.push(new n(r,c,a,l,u,y,x)),(r=h[2])&&e.push(new n(r,o,y,l,c,_,x)),(r=h[3])&&e.push(new n(r,c,y,l,u,_,x)),(r=h[4])&&e.push(new n(r,o,a,x,c,y,f)),(r=h[5])&&e.push(new n(r,c,a,x,u,y,f)),(r=h[6])&&e.push(new n(r,o,y,x,c,_,f)),(r=h[7])&&e.push(new n(r,c,y,x,u,_,f))}s.push(i)}for(;i=s.pop();)t(i.node,i.x0,i.y0,i.z0,i.x1,i.y1,i.z1);return this},l.x=function(t){return arguments.length?(this._x=t,this):this._x},l.y=function(t){return arguments.length?(this._y=t,this):this._y},l.z=function(t){return arguments.length?(this._z=t,this):this._z},t.octree=r,Object.defineProperty(t,"__esModule",{value:!0})}));

package.json

 {
   "name": "d3-octree",
-  "version": "0.1.8",
+  "version": "0.2.0",
   "description": "Three-dimensional recursive spatial subdivision.",
@@ -25,2 +25,3 @@ "keywords": [
   },
+  "sideEffects": false,
   "scripts": {
@@ -36,8 +37,8 @@ "pretest": "rollup -c",
   "devDependencies": {
-    "d3-array": "^2.4.0",
-    "eslint": "^6.8.0",
-    "rollup": "^2.0.6",
-    "rollup-plugin-terser": "^5.3.0",
-    "tape": "^4.13.2"
+    "d3-array": "^2.12.0",
+    "eslint": "^7.22.0",
+    "rollup": "^2.41.4",
+    "rollup-plugin-terser": "^7.0.2",
+    "tape": "^5.2.2"
   }
 }

README.md

@@ -158,2 +158,22 @@ d3-octree
 
+As an example, the following visits the octree and returns all the nodes within a cubic extent [xmin, ymin, zmin, xmax, ymax, zmax], ignoring octants that cannot possibly contain any such node:
+
+```js
+function search(octree, xmin, ymin, zmin, xmax, ymax, zmax) {
+  const results = [];
+  octree.visit(function(node, x1, y1, z1, x2, y2, z2) {
+    if (!node.length) {
+      do {
+        var d = node.data;
+        if (d[0] >= xmin && d[0] < xmax && d[1] >= ymin && d[1] < ymax && d[2] >= zmin && d[2] < zmax) {
+          results.push(d);
+        }
+      } while (node = node.next);
+    }
+    return x1 >= xmax || y1 >= ymax || z1 >= zmax || x2 < xmin || y2 < ymin || z2 < zmin;
+  });
+  return results;
+}
+```
+
 <a name="octree_visitAfter" href="#octree_visitAfter">#</a> <i>octree</i>.<b>visitAfter</b>(<i>callback</i>)
@@ -160,0 +180,0 @@ [<>](https://github.com/vasturiano/d3-octree/blob/master/src/visitAfter.js "Source")

src/add.js

@@ -88,6 +88,4 @@ export default function(d) {
 
-  // If there were no (valid) points, inherit the existing extent.
-  if (x1 < x0) x0 = this._x0, x1 = this._x1;
-  if (y1 < y0) y0 = this._y0, y1 = this._y1;
-  if (z1 < z0) z0 = this._z0, z1 = this._z1;
+  // If there were no (valid) points, abort.
+  if (x0 > x1 || y0 > y1 || z0 > z1) return this;
 
@@ -94,0 +92,0 @@ // Expand the tree to cover the new points.

src/cover.js

@@ -21,4 +21,4 @@ export default function(x, y, z) {
   // Otherwise, double repeatedly to cover.
-  else if (x0 > x || x > x1 || y0 > y || y > y1 || z0 > z || z > z1) {
-    var t = x1 - x0,
+  else {
+    var t = x1 - x0 || 1,
         node = this._root,
@@ -28,43 +28,15 @@ parent,
 
-    switch (i = (z < (z0 + z1) / 2) << 2 | (y < (y0 + y1) / 2) << 1 | (x < (x0 + x1) / 2)) {
-      case 0: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x1 = x0 + t, y1 = y0 + t, z1 = z0 + t, x > x1 || y > y1 || z > z1);
-        break;
+    while (x0 > x || x >= x1 || y0 > y || y >= y1 || z0 > z || z >= z1) {
+      i = (z < z0) << 2 | (y < y0) << 1 | (x < x0);
+      parent = new Array(8), parent[i] = node, node = parent, t *= 2;
+      switch (i) {
+        case 0: x1 = x0 + t, y1 = y0 + t, z1 = z0 + t; break;
+        case 1: x0 = x1 - t, y1 = y0 + t, z1 = z0 + t; break;
+        case 2: x1 = x0 + t, y0 = y1 - t, z1 = z0 + t; break;
+        case 3: x0 = x1 - t, y0 = y1 - t, z1 = z0 + t; break;
+        case 4: x1 = x0 + t, y1 = y0 + t, z0 = z1 - t; break;
+        case 5: x0 = x1 - t, y1 = y0 + t, z0 = z1 - t; break;
+        case 6: x1 = x0 + t, y0 = y1 - t, z0 = z1 - t; break;
+        case 7: x0 = x1 - t, y0 = y1 - t, z0 = z1 - t; break;
       }
-      case 1: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x0 = x1 - t, y1 = y0 + t, z1 = z0 + t, x0 > x || y > y1 || z > z1);
-        break;
-      }
-      case 2: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x1 = x0 + t, y0 = y1 - t, z1 = z0 + t, x > x1 || y0 > y || z > z1);
-        break;
-      }
-      case 3: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x0 = x1 - t, y0 = y1 - t, z1 = z0 + t, x0 > x || y0 > y || z > z1);
-        break;
-      }
-      case 4: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x1 = x0 + t, y1 = y0 + t, z0 = z1 - t, x > x1 || y > y1 || z0 > z);
-        break;
-      }
-      case 5: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x0 = x1 - t, y1 = y0 + t, z0 = z1 - t, x0 > x || y > y1 || z0 > z);
-        break;
-      }
-      case 6: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x1 = x0 + t, y0 = y1 - t, z0 = z1 - t, x > x1 || y0 > y || z0 > z);
-        break;
-      }
-      case 7: {
-        do parent = new Array(8), parent[i] = node, node = parent;
-        while (t *= 2, x0 = x1 - t, y0 = y1 - t, z0 = z1 - t, x0 > x || y0 > y || z0 > z);
-        break;
-      }
     }
@@ -75,5 +47,2 @@
 
-  // If the octree covers the point already, just return.
-  else return this;
-
   this._x0 = x0;
@@ -80,0 +49,0 @@ this._y0 = y0;

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

Number of lines in readme file

218

increased by10.1%

Worsened metrics

Total package byte prevSize

52775

decreased by-3.74%

Lines of code

871

decreased by-6.94%

No dependency changes