kdbush - npm Package Compare versions

Comparing version 3.0.0 to 4.0.0

kdbush.js

 (function (global, factory) {
 typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :
 typeof define === 'function' && define.amd ? define(factory) :
-(global.KDBush = factory());
-}(this, (function () { 'use strict';
+(global = typeof globalThis !== 'undefined' ? globalThis : global || self, global.KDBush = factory());
+})(this, (function () { 'use strict';
 
-function sortKD(ids, coords, nodeSize, left, right, depth) {
-    if (right - left <= nodeSize) { return; }
+const ARRAY_TYPES = [
+    Int8Array, Uint8Array, Uint8ClampedArray, Int16Array, Uint16Array,
+    Int32Array, Uint32Array, Float32Array, Float64Array
+];
 
-    var m = (left + right) >> 1;
+/** @typedef {Int8ArrayConstructor | Uint8ArrayConstructor | Uint8ClampedArrayConstructor | Int16ArrayConstructor | Uint16ArrayConstructor | Int32ArrayConstructor | Uint32ArrayConstructor | Float32ArrayConstructor | Float64ArrayConstructor} TypedArrayConstructor */
 
-    select(ids, coords, m, left, right, depth % 2);
+const VERSION = 1; // serialized format version
+const HEADER_SIZE = 8;
 
-    sortKD(ids, coords, nodeSize, left, m - 1, depth + 1);
-    sortKD(ids, coords, nodeSize, m + 1, right, depth + 1);
-}
+class KDBush {
 
-function select(ids, coords, k, left, right, inc) {
-
-    while (right > left) {
-        if (right - left > 600) {
-            var n = right - left + 1;
-            var m = k - left + 1;
-            var z = Math.log(n);
-            var s = 0.5 * Math.exp(2 * z / 3);
-            var sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
-            var newLeft = Math.max(left, Math.floor(k - m * s / n + sd));
-            var newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));
-            select(ids, coords, k, newLeft, newRight, inc);
+    /**
+     * Creates an index from raw `ArrayBuffer` data.
+     * @param {ArrayBuffer} data
+     */
+    static from(data) {
+        if (!(data instanceof ArrayBuffer)) {
+            throw new Error('Data must be an instance of ArrayBuffer.');
         }
+        const [magic, versionAndType] = new Uint8Array(data, 0, 2);
+        if (magic !== 0xdb) {
+            throw new Error('Data does not appear to be in a KDBush format.');
+        }
+        const version = versionAndType >> 4;
+        if (version !== VERSION) {
+            throw new Error(`Got v${version} data when expected v${VERSION}.`);
+        }
+        const ArrayType = ARRAY_TYPES[versionAndType & 0x0f];
+        if (!ArrayType) {
+            throw new Error('Unrecognized array type.');
+        }
+        const [nodeSize] = new Uint16Array(data, 2, 1);
+        const [numItems] = new Uint32Array(data, 4, 1);
 
-        var t = coords[2 * k + inc];
-        var i = left;
-        var j = right;
+        return new KDBush(numItems, nodeSize, ArrayType, data);
+    }
 
-        swapItem(ids, coords, left, k);
-        if (coords[2 * right + inc] > t) { swapItem(ids, coords, left, right); }
+    /**
+     * Creates an index that will hold a given number of items.
+     * @param {number} numItems
+     * @param {number} [nodeSize=64] Size of the KD-tree node (64 by default).
+     * @param {TypedArrayConstructor} [ArrayType=Float64Array] The array type used for coordinates storage (`Float64Array` by default).
+     * @param {ArrayBuffer} [data] (For internal use only)
+     */
+    constructor(numItems, nodeSize = 64, ArrayType = Float64Array, data) {
+        if (isNaN(numItems) || numItems <= 0) throw new Error(`Unpexpected numItems value: ${numItems}.`);
 
-        while (i < j) {
-            swapItem(ids, coords, i, j);
-            i++;
-            j--;
-            while (coords[2 * i + inc] < t) { i++; }
-            while (coords[2 * j + inc] > t) { j--; }
+        this.numItems = +numItems;
+        this.nodeSize = Math.min(Math.max(+nodeSize, 2), 65535);
+        this.ArrayType = ArrayType;
+        this.IndexArrayType = numItems < 65536 ? Uint16Array : Uint32Array;
+
+        const arrayTypeIndex = ARRAY_TYPES.indexOf(this.ArrayType);
+        const coordsByteSize = numItems * 2 * this.ArrayType.BYTES_PER_ELEMENT;
+        const idsByteSize = numItems * this.IndexArrayType.BYTES_PER_ELEMENT;
+        const padCoords = (8 - idsByteSize % 8) % 8;
+
+        if (arrayTypeIndex < 0) {
+            throw new Error(`Unexpected typed array class: ${ArrayType}.`);
         }
 
-        if (coords[2 * left + inc] === t) { swapItem(ids, coords, left, j); }
-        else {
-            j++;
-            swapItem(ids, coords, j, right);
+        if (data && (data instanceof ArrayBuffer)) { // reconstruct an index from a buffer
+            this.data = data;
+            this.ids = new this.IndexArrayType(this.data, HEADER_SIZE, numItems);
+            this.coords = new this.ArrayType(this.data, HEADER_SIZE + idsByteSize + padCoords, numItems * 2);
+            this._pos = numItems * 2;
+            this._finished = true;
+        } else { // initialize a new index
+            this.data = new ArrayBuffer(HEADER_SIZE + coordsByteSize + idsByteSize + padCoords);
+            this.ids = new this.IndexArrayType(this.data, HEADER_SIZE, numItems);
+            this.coords = new this.ArrayType(this.data, HEADER_SIZE + idsByteSize + padCoords, numItems * 2);
+            this._pos = 0;
+            this._finished = false;
+
+            // set header
+            new Uint8Array(this.data, 0, 2).set([0xdb, (VERSION << 4) + arrayTypeIndex]);
+            new Uint16Array(this.data, 2, 1)[0] = nodeSize;
+            new Uint32Array(this.data, 4, 1)[0] = numItems;
         }
+    }
 
-        if (j <= k) { left = j + 1; }
-        if (k <= j) { right = j - 1; }
+    /**
+     * Add a point to the index.
+     * @param {number} x
+     * @param {number} y
+     * @returns {number} An incremental index associated with the added item (starting from `0`).
+     */
+    add(x, y) {
+        const index = this._pos >> 1;
+        this.ids[index] = index;
+        this.coords[this._pos++] = x;
+        this.coords[this._pos++] = y;
+        return index;
     }
-}
 
-function swapItem(ids, coords, i, j) {
-    swap(ids, i, j);
-    swap(coords, 2 * i, 2 * j);
-    swap(coords, 2 * i + 1, 2 * j + 1);
-}
+    /**
+     * Perform indexing of the added points.
+     */
+    finish() {
+        const numAdded = this._pos >> 1;
+        if (numAdded !== this.numItems) {
+            throw new Error(`Added ${numAdded} items when expected ${this.numItems}.`);
+        }
+        // kd-sort both arrays for efficient search
+        sort(this.ids, this.coords, this.nodeSize, 0, this.numItems - 1, 0);
 
-function swap(arr, i, j) {
-    var tmp = arr[i];
-    arr[i] = arr[j];
-    arr[j] = tmp;
-}
+        this._finished = true;
+        return this;
+    }
 
-function range(ids, coords, minX, minY, maxX, maxY, nodeSize) {
-    var stack = [0, ids.length - 1, 0];
-    var result = [];
-    var x, y;
+    /**
+     * Search the index for items within a given bounding box.
+     * @param {number} minX
+     * @param {number} minY
+     * @param {number} maxX
+     * @param {number} maxY
+     * @returns {number[]} An array of indices correponding to the found items.
+     */
+    range(minX, minY, maxX, maxY) {
+        if (!this._finished) throw new Error('Data not yet indexed - call index.finish().');
 
-    while (stack.length) {
-        var axis = stack.pop();
-        var right = stack.pop();
-        var left = stack.pop();
+        const {ids, coords, nodeSize} = this;
+        const stack = [0, ids.length - 1, 0];
+        const result = [];
 
-        if (right - left <= nodeSize) {
-            for (var i = left; i <= right; i++) {
-                x = coords[2 * i];
-                y = coords[2 * i + 1];
-                if (x >= minX && x <= maxX && y >= minY && y <= maxY) { result.push(ids[i]); }
+        // recursively search for items in range in the kd-sorted arrays
+        while (stack.length) {
+            const axis = stack.pop() || 0;
+            const right = stack.pop() || 0;
+            const left = stack.pop() || 0;
+
+            // if we reached "tree node", search linearly
+            if (right - left <= nodeSize) {
+                for (let i = left; i <= right; i++) {
+                    const x = coords[2 * i];
+                    const y = coords[2 * i + 1];
+                    if (x >= minX && x <= maxX && y >= minY && y <= maxY) result.push(ids[i]);
+                }
+                continue;
             }
-            continue;
-        }
 
-        var m = Math.floor((left + right) / 2);
+            // otherwise find the middle index
+            const m = (left + right) >> 1;
 
-        x = coords[2 * m];
-        y = coords[2 * m + 1];
+            // include the middle item if it's in range
+            const x = coords[2 * m];
+            const y = coords[2 * m + 1];
+            if (x >= minX && x <= maxX && y >= minY && y <= maxY) result.push(ids[m]);
 
-        if (x >= minX && x <= maxX && y >= minY && y <= maxY) { result.push(ids[m]); }
+            // queue search in halves that intersect the query
+            if (axis === 0 ? minX <= x : minY <= y) {
+                stack.push(left);
+                stack.push(m - 1);
+                stack.push(1 - axis);
+            }
+            if (axis === 0 ? maxX >= x : maxY >= y) {
+                stack.push(m + 1);
+                stack.push(right);
+                stack.push(1 - axis);
+            }
+        }
 
-        var nextAxis = (axis + 1) % 2;
-
-        if (axis === 0 ? minX <= x : minY <= y) {
-            stack.push(left);
-            stack.push(m - 1);
-            stack.push(nextAxis);
-        }
-        if (axis === 0 ? maxX >= x : maxY >= y) {
-            stack.push(m + 1);
-            stack.push(right);
-            stack.push(nextAxis);
-        }
+        return result;
     }
 
-    return result;
-}
+    /**
+     * Search the index for items within a given radius.
+     * @param {number} qx
+     * @param {number} qy
+     * @param {number} r Query radius.
+     * @returns {number[]} An array of indices correponding to the found items.
+     */
+    within(qx, qy, r) {
+        if (!this._finished) throw new Error('Data not yet indexed - call index.finish().');
 
-function within(ids, coords, qx, qy, r, nodeSize) {
-    var stack = [0, ids.length - 1, 0];
-    var result = [];
-    var r2 = r * r;
+        const {ids, coords, nodeSize} = this;
+        const stack = [0, ids.length - 1, 0];
+        const result = [];
+        const r2 = r * r;
 
-    while (stack.length) {
-        var axis = stack.pop();
-        var right = stack.pop();
-        var left = stack.pop();
+        // recursively search for items within radius in the kd-sorted arrays
+        while (stack.length) {
+            const axis = stack.pop() || 0;
+            const right = stack.pop() || 0;
+            const left = stack.pop() || 0;
 
-        if (right - left <= nodeSize) {
-            for (var i = left; i <= right; i++) {
-                if (sqDist(coords[2 * i], coords[2 * i + 1], qx, qy) <= r2) { result.push(ids[i]); }
+            // if we reached "tree node", search linearly
+            if (right - left <= nodeSize) {
+                for (let i = left; i <= right; i++) {
+                    if (sqDist(coords[2 * i], coords[2 * i + 1], qx, qy) <= r2) result.push(ids[i]);
+                }
+                continue;
             }
-            continue;
-        }
 
-        var m = Math.floor((left + right) / 2);
+            // otherwise find the middle index
+            const m = (left + right) >> 1;
 
-        var x = coords[2 * m];
-        var y = coords[2 * m + 1];
+            // include the middle item if it's in range
+            const x = coords[2 * m];
+            const y = coords[2 * m + 1];
+            if (sqDist(x, y, qx, qy) <= r2) result.push(ids[m]);
 
-        if (sqDist(x, y, qx, qy) <= r2) { result.push(ids[m]); }
+            // queue search in halves that intersect the query
+            if (axis === 0 ? qx - r <= x : qy - r <= y) {
+                stack.push(left);
+                stack.push(m - 1);
+                stack.push(1 - axis);
+            }
+            if (axis === 0 ? qx + r >= x : qy + r >= y) {
+                stack.push(m + 1);
+                stack.push(right);
+                stack.push(1 - axis);
+            }
+        }
 
-        var nextAxis = (axis + 1) % 2;
-
-        if (axis === 0 ? qx - r <= x : qy - r <= y) {
-            stack.push(left);
-            stack.push(m - 1);
-            stack.push(nextAxis);
-        }
-        if (axis === 0 ? qx + r >= x : qy + r >= y) {
-            stack.push(m + 1);
-            stack.push(right);
-            stack.push(nextAxis);
-        }
+        return result;
     }
-
-    return result;
 }
 
-function sqDist(ax, ay, bx, by) {
-    var dx = ax - bx;
-    var dy = ay - by;
-    return dx * dx + dy * dy;
+/**
+ * @param {Uint16Array | Uint32Array} ids
+ * @param {InstanceType<TypedArrayConstructor>} coords
+ * @param {number} nodeSize
+ * @param {number} left
+ * @param {number} right
+ * @param {number} axis
+ */
+function sort(ids, coords, nodeSize, left, right, axis) {
+    if (right - left <= nodeSize) return;
+
+    const m = (left + right) >> 1; // middle index
+
+    // sort ids and coords around the middle index so that the halves lie
+    // either left/right or top/bottom correspondingly (taking turns)
+    select(ids, coords, m, left, right, axis);
+
+    // recursively kd-sort first half and second half on the opposite axis
+    sort(ids, coords, nodeSize, left, m - 1, 1 - axis);
+    sort(ids, coords, nodeSize, m + 1, right, 1 - axis);
 }
 
-var defaultGetX = function (p) { return p[0]; };
-var defaultGetY = function (p) { return p[1]; };
+/**
+ * Custom Floyd-Rivest selection algorithm: sort ids and coords so that
+ * [left..k-1] items are smaller than k-th item (on either x or y axis)
+ * @param {Uint16Array | Uint32Array} ids
+ * @param {InstanceType<TypedArrayConstructor>} coords
+ * @param {number} k
+ * @param {number} left
+ * @param {number} right
+ * @param {number} axis
+ */
+function select(ids, coords, k, left, right, axis) {
 
-var KDBush = function KDBush(points, getX, getY, nodeSize, ArrayType) {
-    if ( getX === void 0 ) getX = defaultGetX;
-    if ( getY === void 0 ) getY = defaultGetY;
-    if ( nodeSize === void 0 ) nodeSize = 64;
-    if ( ArrayType === void 0 ) ArrayType = Float64Array;
+    while (right > left) {
+        if (right - left > 600) {
+            const n = right - left + 1;
+            const m = k - left + 1;
+            const z = Math.log(n);
+            const s = 0.5 * Math.exp(2 * z / 3);
+            const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
+            const newLeft = Math.max(left, Math.floor(k - m * s / n + sd));
+            const newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));
+            select(ids, coords, k, newLeft, newRight, axis);
+        }
 
-    this.nodeSize = nodeSize;
-    this.points = points;
+        const t = coords[2 * k + axis];
+        let i = left;
+        let j = right;
 
-    var IndexArrayType = points.length < 65536 ? Uint16Array : Uint32Array;
+        swapItem(ids, coords, left, k);
+        if (coords[2 * right + axis] > t) swapItem(ids, coords, left, right);
 
-    var ids = this.ids = new IndexArrayType(points.length);
-    var coords = this.coords = new ArrayType(points.length * 2);
+        while (i < j) {
+            swapItem(ids, coords, i, j);
+            i++;
+            j--;
+            while (coords[2 * i + axis] < t) i++;
+            while (coords[2 * j + axis] > t) j--;
+        }
 
-    for (var i = 0; i < points.length; i++) {
-        ids[i] = i;
-        coords[2 * i] = getX(points[i]);
-        coords[2 * i + 1] = getY(points[i]);
+        if (coords[2 * left + axis] === t) swapItem(ids, coords, left, j);
+        else {
+            j++;
+            swapItem(ids, coords, j, right);
+        }
+
+        if (j <= k) left = j + 1;
+        if (k <= j) right = j - 1;
     }
+}
 
-    sortKD(ids, coords, nodeSize, 0, ids.length - 1, 0);
-};
+/**
+ * @param {Uint16Array | Uint32Array} ids
+ * @param {InstanceType<TypedArrayConstructor>} coords
+ * @param {number} i
+ * @param {number} j
+ */
+function swapItem(ids, coords, i, j) {
+    swap(ids, i, j);
+    swap(coords, 2 * i, 2 * j);
+    swap(coords, 2 * i + 1, 2 * j + 1);
+}
 
-KDBush.prototype.range = function range$1 (minX, minY, maxX, maxY) {
-    return range(this.ids, this.coords, minX, minY, maxX, maxY, this.nodeSize);
-};
+/**
+ * @param {InstanceType<TypedArrayConstructor>} arr
+ * @param {number} i
+ * @param {number} j
+ */
+function swap(arr, i, j) {
+    const tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+}
 
-KDBush.prototype.within = function within$1 (x, y, r) {
-    return within(this.ids, this.coords, x, y, r, this.nodeSize);
-};
+/**
+ * @param {number} ax
+ * @param {number} ay
+ * @param {number} bx
+ * @param {number} by
+ */
+function sqDist(ax, ay, bx, by) {
+    const dx = ax - bx;
+    const dy = ay - by;
+    return dx * dx + dy * dy;
+}
 
 return KDBush;
 
-})));
+}));

kdbush.min.js

@@ -1,1 +0,1 @@
-!function(t,o){"object"==typeof exports&&"undefined"!=typeof module?module.exports=o():"function"==typeof define&&define.amd?define(o):t.KDBush=o()}(this,function(){"use strict";function t(n,r,i,e,h,u){if(!(h-e<=i)){var s=e+h>>1;!function t(n,r,i,e,h,u){for(;h>e;){if(h-e>600){var s=h-e+1,f=i-e+1,p=Math.log(s),a=.5*Math.exp(2*p/3),d=.5*Math.sqrt(p*a*(s-a)/s)*(f-s/2<0?-1:1),v=Math.max(e,Math.floor(i-f*a/s+d)),c=Math.min(h,Math.floor(i+(s-f)*a/s+d));t(n,r,i,v,c,u)}var l=r[2*i+u],g=e,M=h;for(o(n,r,e,i),r[2*h+u]>l&&o(n,r,e,h);g<M;){for(o(n,r,g,M),g++,M--;r[2*g+u]<l;)g++;for(;r[2*M+u]>l;)M--}r[2*e+u]===l?o(n,r,e,M):o(n,r,++M,h),M<=i&&(e=M+1),i<=M&&(h=M-1)}}(n,r,s,e,h,u%2),t(n,r,i,e,s-1,u+1),t(n,r,i,s+1,h,u+1)}}function o(t,o,r,i){n(t,r,i),n(o,2*r,2*i),n(o,2*r+1,2*i+1)}function n(t,o,n){var r=t[o];t[o]=t[n],t[n]=r}function r(t,o,n,r){var i=t-n,e=o-r;return i*i+e*e}var i=function(t){return t[0]},e=function(t){return t[1]},h=function(o,n,r,h,u){void 0===n&&(n=i),void 0===r&&(r=e),void 0===h&&(h=64),void 0===u&&(u=Float64Array),this.nodeSize=h,this.points=o;for(var s=o.length<65536?Uint16Array:Uint32Array,f=this.ids=new s(o.length),p=this.coords=new u(2*o.length),a=0;a<o.length;a++)f[a]=a,p[2*a]=n(o[a]),p[2*a+1]=r(o[a]);t(f,p,h,0,f.length-1,0)};return h.prototype.range=function(t,o,n,r){return function(t,o,n,r,i,e,h){for(var u,s,f=[0,t.length-1,0],p=[];f.length;){var a=f.pop(),d=f.pop(),v=f.pop();if(d-v<=h)for(var c=v;c<=d;c++)u=o[2*c],s=o[2*c+1],u>=n&&u<=i&&s>=r&&s<=e&&p.push(t[c]);else{var l=Math.floor((v+d)/2);u=o[2*l],s=o[2*l+1],u>=n&&u<=i&&s>=r&&s<=e&&p.push(t[l]);var g=(a+1)%2;(0===a?n<=u:r<=s)&&(f.push(v),f.push(l-1),f.push(g)),(0===a?i>=u:e>=s)&&(f.push(l+1),f.push(d),f.push(g))}}return p}(this.ids,this.coords,t,o,n,r,this.nodeSize)},h.prototype.within=function(t,o,n){return function(t,o,n,i,e,h){for(var u=[0,t.length-1,0],s=[],f=e*e;u.length;){var p=u.pop(),a=u.pop(),d=u.pop();if(a-d<=h)for(var v=d;v<=a;v++)r(o[2*v],o[2*v+1],n,i)<=f&&s.push(t[v]);else{var c=Math.floor((d+a)/2),l=o[2*c],g=o[2*c+1];r(l,g,n,i)<=f&&s.push(t[c]);var M=(p+1)%2;(0===p?n-e<=l:i-e<=g)&&(u.push(d),u.push(c-1),u.push(M)),(0===p?n+e>=l:i+e>=g)&&(u.push(c+1),u.push(a),u.push(M))}}return s}(this.ids,this.coords,t,o,n,this.nodeSize)},h});
+!function(t,r){"object"==typeof exports&&"undefined"!=typeof module?module.exports=r():"function"==typeof define&&define.amd?define(r):(t="undefined"!=typeof globalThis?globalThis:t||self).KDBush=r()}(this,(function(){"use strict";const t=[Int8Array,Uint8Array,Uint8ClampedArray,Int16Array,Uint16Array,Int32Array,Uint32Array,Float32Array,Float64Array];class r{static from(n){if(!(n instanceof ArrayBuffer))throw new Error("Data must be an instance of ArrayBuffer.");const[s,e]=new Uint8Array(n,0,2);if(219!==s)throw new Error("Data does not appear to be in a KDBush format.");const i=e>>4;if(1!==i)throw new Error(`Got v${i} data when expected v1.`);const o=t[15&e];if(!o)throw new Error("Unrecognized array type.");const[h]=new Uint16Array(n,2,1),[a]=new Uint32Array(n,4,1);return new r(a,h,o,n)}constructor(r,n=64,s=Float64Array,e){if(isNaN(r)||r<=0)throw new Error(`Unpexpected numItems value: ${r}.`);this.numItems=+r,this.nodeSize=Math.min(Math.max(+n,2),65535),this.ArrayType=s,this.IndexArrayType=r<65536?Uint16Array:Uint32Array;const i=t.indexOf(this.ArrayType),o=2*r*this.ArrayType.BYTES_PER_ELEMENT,h=r*this.IndexArrayType.BYTES_PER_ELEMENT,a=(8-h%8)%8;if(i<0)throw new Error(`Unexpected typed array class: ${s}.`);e&&e instanceof ArrayBuffer?(this.data=e,this.ids=new this.IndexArrayType(this.data,8,r),this.coords=new this.ArrayType(this.data,8+h+a,2*r),this._pos=2*r,this._finished=!0):(this.data=new ArrayBuffer(8+o+h+a),this.ids=new this.IndexArrayType(this.data,8,r),this.coords=new this.ArrayType(this.data,8+h+a,2*r),this._pos=0,this._finished=!1,new Uint8Array(this.data,0,2).set([219,16+i]),new Uint16Array(this.data,2,1)[0]=n,new Uint32Array(this.data,4,1)[0]=r)}add(t,r){const n=this._pos>>1;return this.ids[n]=n,this.coords[this._pos++]=t,this.coords[this._pos++]=r,n}finish(){const t=this._pos>>1;if(t!==this.numItems)throw new Error(`Added ${t} items when expected ${this.numItems}.`);return n(this.ids,this.coords,this.nodeSize,0,this.numItems-1,0),this._finished=!0,this}range(t,r,n,s){if(!this._finished)throw new Error("Data not yet indexed - call index.finish().");const{ids:e,coords:i,nodeSize:o}=this,h=[0,e.length-1,0],a=[];for(;h.length;){const d=h.pop()||0,f=h.pop()||0,p=h.pop()||0;if(f-p<=o){for(let o=p;o<=f;o++){const h=i[2*o],d=i[2*o+1];h>=t&&h<=n&&d>=r&&d<=s&&a.push(e[o])}continue}const c=p+f>>1,u=i[2*c],y=i[2*c+1];u>=t&&u<=n&&y>=r&&y<=s&&a.push(e[c]),(0===d?t<=u:r<=y)&&(h.push(p),h.push(c-1),h.push(1-d)),(0===d?n>=u:s>=y)&&(h.push(c+1),h.push(f),h.push(1-d))}return a}within(t,r,n){if(!this._finished)throw new Error("Data not yet indexed - call index.finish().");const{ids:s,coords:e,nodeSize:i}=this,h=[0,s.length-1,0],a=[],d=n*n;for(;h.length;){const f=h.pop()||0,p=h.pop()||0,c=h.pop()||0;if(p-c<=i){for(let n=c;n<=p;n++)o(e[2*n],e[2*n+1],t,r)<=d&&a.push(s[n]);continue}const u=c+p>>1,y=e[2*u],w=e[2*u+1];o(y,w,t,r)<=d&&a.push(s[u]),(0===f?t-n<=y:r-n<=w)&&(h.push(c),h.push(u-1),h.push(1-f)),(0===f?t+n>=y:r+n>=w)&&(h.push(u+1),h.push(p),h.push(1-f))}return a}}function n(t,r,e,i,o,h){if(o-i<=e)return;const a=i+o>>1;s(t,r,a,i,o,h),n(t,r,e,i,a-1,1-h),n(t,r,e,a+1,o,1-h)}function s(t,r,n,i,o,h){for(;o>i;){if(o-i>600){const e=o-i+1,a=n-i+1,d=Math.log(e),f=.5*Math.exp(2*d/3),p=.5*Math.sqrt(d*f*(e-f)/e)*(a-e/2<0?-1:1);s(t,r,n,Math.max(i,Math.floor(n-a*f/e+p)),Math.min(o,Math.floor(n+(e-a)*f/e+p)),h)}const a=r[2*n+h];let d=i,f=o;for(e(t,r,i,n),r[2*o+h]>a&&e(t,r,i,o);d<f;){for(e(t,r,d,f),d++,f--;r[2*d+h]<a;)d++;for(;r[2*f+h]>a;)f--}r[2*i+h]===a?e(t,r,i,f):(f++,e(t,r,f,o)),f<=n&&(i=f+1),n<=f&&(o=f-1)}}function e(t,r,n,s){i(t,n,s),i(r,2*n,2*s),i(r,2*n+1,2*s+1)}function i(t,r,n){const s=t[r];t[r]=t[n],t[n]=s}function o(t,r,n,s){const e=t-n,i=r-s;return e*e+i*i}return r}));

package.json

 {
   "name": "kdbush",
-  "version": "3.0.0",
+  "version": "4.0.0",
   "description": "A very fast static 2D index for points based on kd-tree.",
-  "module": "src/index.js",
+  "type": "module",
   "main": "kdbush.js",
-  "jsdelivr": "kdbush.min.js",
-  "unpkg": "kdbush.min.js",
+  "module": "index.js",
+  "exports": "./index.js",
+  "types": "index.d.ts",
+  "sideEffects": false,
   "repository": {
@@ -14,16 +16,14 @@ "type": "git",
   "devDependencies": {
-    "eslint": "^5.5.0",
+    "@rollup/plugin-terser": "^0.4.1",
+    "eslint": "^8.38.0",
     "eslint-config-mourner": "^3.0.0",
-    "esm": "^3.0.82",
-    "rollup": "^0.65.2",
-    "rollup-plugin-buble": "^0.19.2",
-    "rollup-plugin-terser": "^2.0.2",
-    "tape": "^4.9.1"
+    "rollup": "^3.20.6",
+    "typescript": "^5.0.4"
   },
   "scripts": {
-    "pretest": "eslint src test.js bench.js rollup.config.js",
-    "test": "tape -r esm test.js",
-    "bench": "node -r esm bench.js",
+    "pretest": "eslint index.js test.js bench.js rollup.config.js",
+    "test": "tsc && node test.js",
+    "bench": "node bench.js",
     "build": "rollup -c",
-    "prepublishOnly": "npm run build"
+    "prepublishOnly": "npm run test && npm run build"
   },
@@ -45,3 +45,3 @@ "eslintConfig": {
     "kdbush.min.js",
-    "src"
+    "index.d.ts"
   ],
@@ -48,0 +48,0 @@ "author": "Vladimir Agafonkin",

README.md

@@ -1,2 +0,2 @@
-## KDBush [![Build Status](https://travis-ci.org/mourner/kdbush.svg?branch=master)](https://travis-ci.org/mourner/kdbush) [![Simply Awesome](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
+## KDBush
 
@@ -6,10 +6,41 @@ A very fast static spatial index for 2D points based on a flat KD-tree.
 
-- points only — no rectangles
-- static — you can't add/remove items
-- indexing is 5-8 times faster
+- **Points only** — no rectangles.
+- **Static** — you can't add/remove items after initial indexing.
+- **Faster** indexing and search, with lower **memory** footprint.
+- Index is stored as a single **array buffer** (so you can [transfer](https://developer.mozilla.org/en-US/docs/Glossary/Transferable_objects) it between threads or store it as a compact file).
 
+
+If you need a static index for rectangles, not only points, see [Flatbush](https://github.com/mourner/flatbush). When indexing points, KDBush has the advantage of taking ~2x less memory than Flatbush.
+
+[![Build Status](https://github.com/mourner/kdbush/workflows/Node/badge.svg?branch=master)](https://github.com/mourner/kdbush/actions)
+[![Simply Awesome](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
+
+## Usage
+
 ```js
-const index = new KDBush(points);         // make an index
-const ids1 = index.range(10, 10, 20, 20); // bbox search - minX, minY, maxX, maxY
-const ids2 = index.within(10, 10, 5);     // radius search - x, y, radius
+// initialize KDBush for 1000 items
+const index = new KDBush(1000);
+
+// fill it with 1000 points
+for (const {x, y} of items) {
+    index.add(x, y);
+}
+
+// perform the indexing
+index.finish();
+
+// make a bounding box query
+const foundIds = index.range(minX, minY, maxX, maxY);
+
+// map ids to original items
+const foundItems = foundIds.map(i => items[i]);
+
+// make a radius query
+const neighborIds = index.within(x, y, 5);
+
+// instantly transfer the index from a worker to the main thread
+postMessage(index.data, [index.data]);
+
+// reconstruct the index from a raw array buffer
+const index = Flatbush.from(e.data);
 ```
@@ -19,16 +50,20 @@
 
-Install using NPM (`npm install kdbush`) or Yarn (`yarn add kdbush`), then:
+Install with NPM: `npm install kdbush`, then import as a module:
 
 ```js
-// import as a ES module
 import KDBush from 'kdbush';
+```
 
-// or require in Node / Browserify
-const KDBush = require('kdbush');
+Or use as a module directly in the browser with [jsDelivr](https://www.jsdelivr.com/esm):
+
+```html
+<script type="module">
+    import KDBush from 'https://cdn.jsdelivr.net/npm/kdbush/+esm';
+</script>
 ```
 
-Or use a browser build directly:
+Alternatively, there's a browser bundle with a `KDBush` global variable:
 
 ```html
-<script src="https://unpkg.com/kdbush@2.0.0/kdbush.min.js"></script>
+<script src="https://cdn.jsdelivr.net/npm/kdbush"></script>
 ```
@@ -38,23 +73,17 @@
 
-#### new KDBush(points[, getX, getY, nodeSize, arrayType])
+#### new KDBush(numItems[, nodeSize, ArrayType])
 
-Creates an index from the given points.
+Creates an index that will hold a given number of points (`numItems`). Additionally accepts:
 
-- `points`: Input array of points.
-- `getX`, `getY`: Functions to get `x` and `y` from an input point. By default, it assumes `[x, y]` format.
 - `nodeSize`: Size of the KD-tree node, `64` by default. Higher means faster indexing but slower search, and vise versa.
-- `arrayType`: Array type to use for storing coordinate values. `Float64Array` by default, but if your coordinates are integer values, `Int32Array` makes things a bit faster.
+- `ArrayType`: Array type to use for storing coordinate values. `Float64Array` by default, but if your coordinates are integer values, `Int32Array` makes the index faster and smaller.
 
-```js
-const index = kdbush(points, p => p.x, p => p.y, 64, Int32Array);
-```
+#### index.add(x, y)
 
+Adds a given point to the index. Returns a zero-based, incremental number that represents the newly added point.
+
 #### index.range(minX, minY, maxX, maxY)
 
-Finds all items within the given bounding box and returns an array of indices that refer to the items in the original `points` input array.
+Finds all items within the given bounding box and returns an array of indices that refer to the order the items were added (the values returned by `index.add(x, y)`).
 
-```js
-const results = index.range(10, 10, 20, 20).map(id => points[id]);
-```
-
 #### index.within(x, y, radius)
@@ -64,4 +93,14 @@
 
-```js
-const results = index.within(10, 10, 5).map(id => points[id]);
-```
+#### `KDBush.from(data)`
+
+Recreates a KDBush index from raw `ArrayBuffer` data
+(that's exposed as `index.data` on a previously indexed KDBush instance).
+Very useful for transferring or sharing indices between threads or storing them in a file.
+
+### Properties
+
+- `data`: array buffer that holds the index.
+- `numItems`: number of stored items.
+- `nodeSize`: number of items in a KD-tree node.
+- `ArrayType`: array type used for internal coordinates storage.
+- `IndexArrayType`: array type used for internal item indices storage.

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

Improved metrics

Total package byte prevSize

23046

increased by35.96%

Dev dependency count

5

decreased by-28.57%

Lines of code

357

increased by15.53%

Number of lines in readme file

103

increased by60.94%

Is type module

Yes

Worsened metrics

Number of package files

6

decreased by-33.33%

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes