Registry / data / kd-tree-javascript

kd-tree-javascript

JSON →
library1.0.3jsnpmunverified

The `kd-tree-javascript` library provides a basic but high-performance JavaScript implementation of the k-dimensional tree data structure. It's designed for organizing points in k-dimensional space, facilitating efficient range searches and nearest neighbor queries. Currently at version 1.0.3, the library uses a UMD (Universal Module Definition) pattern, allowing it to be used in browser environments (exposing global variables `kdTree` and `BinaryHeap`) and with module loaders like RequireJS. Its primary differentiator was its reported speed and simplicity for specific spatial data operations, as highlighted by various demos. Due to its last update being in 2017, the library is considered abandoned, meaning no further feature development, bug fixes, or security patches are expected.

data
npm install kd-tree-javascript
github ↗package ↗
INSTALL
IMPORT
SIG · KD-TREE-JAVASCRIPT
K
kd-tree-javascript
datajavascriptv1.0.3
Install
—
Import
—
Disk
—
Pass rate
0/ 6
Env Coverage0 / 6
glibc
18–22
musl
18–22
Install & Compatibility
Where this runs
tested against v? · npm install
Install × environment matrix
Each cell = how many times install + import succeeded across repeated harness runs. Partial = flaky.
glibc = Debian/Ubuntu slim · musl = Alpine Linux
musl
node 18–226 runs
build_error
glibc
node 18–226 runs
build_error
Code
Verified usage

Verified import paths — ran on the pinned version, not inferred.

kdTree (global)
✓ <!-- In HTML --> <script src="path/to/kdTree.js"></script> <script> const tree = new kdTree(points, distance, dimensions); </script>
✗ import { kdTree } from 'kd-tree-javascript';
When included directly via a `<script>` tag in a browser, `kdTree` and `BinaryHeap` are exposed as global variables (`window.kdTree`, `window.BinaryHeap`). This is the primary intended usage for browser environments.
kdTree (CommonJS)
✓ const ubilabs = require('kd-tree-javascript'); const tree = new ubilabs.kdTree(points, distance, dimensions);
✗ const { kdTree } = require('kd-tree-javascript');
In CommonJS environments (e.g., Node.js), the UMD module exports an object (often named `ubilabs` by convention) that contains `kdTree` and `BinaryHeap` as properties. Direct destructuring of `kdTree` from `require()` is not supported.
kdTree (RequireJS / AMD)
✓ requirejs(['path/to/kdTree.js'], function (ubilabs) { const tree = new ubilabs.kdTree(points, distance, dimensions); });
✗ const tree = new kdTree(points, distance, dimensions); // if not globally defined
When loaded via RequireJS or another AMD loader, the module passes an object containing `kdTree` and `BinaryHeap` to the callback function. The path should be relative to your RequireJS base URL.

This quickstart demonstrates how to create a k-d tree, insert points, define a distance function, and perform a nearest neighbor search.

var points = [ {x: 1, y: 2}, {x: 3, y: 4}, {x: 5, y: 6}, {x: 7, y: 8} ]; var distance = function(a, b){ return Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2); } // Assuming kdTree is globally available or imported via CommonJS/AMD as 'ubilabs' // For global: new kdTree(points, distance, ["x", "y"]); // For CommonJS: new ubilabs.kdTree(points, distance, ["x", "y"]); // For this example, we'll assume global/browser context as in README. var tree = new kdTree(points, distance, ["x", "y"]); var nearest = tree.nearest({ x: 5, y: 5 }, 2); console.log(nearest); // Expected output: // [ [ { x: 5, y: 6 }, 1 ], [ { x: 7, y: 8 }, 8 ] ] // (point {x:5,y:6} at distance 1, point {x:7,y:8} at distance 8)
Debug
Known issues
gotchaWhen loaded directly in a browser via a `<script>` tag, `kdTree` and `BinaryHeap` are exposed as global variables, which may conflict with other libraries or application code using the same names.
fix
Consider explicitly removing global variables if conflicts arise, or encapsulate usage within a self-executing function if not using a module loader.
affects: >=1.0.1
gotchaThe library has not been updated since October 2017, meaning there will be no further development, bug fixes, or security patches. Users should be aware of potential vulnerabilities or compatibility issues with newer JavaScript runtimes, browser versions, or evolving web standards.
fix
Evaluate alternatives if long-term support, active maintenance, or modern JavaScript features are required. Use with caution in new projects.
affects: >=1.0.3
gotchaThe k-d tree structure can become unbalanced with frequent insertions and deletions, leading to degraded query performance (approaching O(N) instead of O(log N)). The library does not provide automatic rebalancing.
fix
Periodically check the `balanceFactor()` of the tree. If performance is critical and the balance factor is high, rebuild the tree from scratch with existing points to restore balance.
affects: *
Errors
Common errors & fixes
ReferenceError: kdTree is not defined
The `kdTree` global variable was not loaded, likely due to an incorrect script path, missing `<script>` tag in HTML, or incorrect module import.
fix
Ensure the `kdTree.js` file is correctly linked in your HTML before other scripts using it, or use `require()` with the correct module path in a CommonJS environment.
TypeError: Cannot read properties of undefined (reading 'kdTree')
Occurs in CommonJS/RequireJS environments when the module is not correctly imported and assigned, or the property `kdTree` is accessed on an undefined module export.
fix
For CommonJS, use `const ubilabs = require('kd-tree-javascript');` and then `new ubilabs.kdTree(...)`. For RequireJS, ensure the module path is correct and the callback argument (e.g., `ubilabs`) is used as shown in the documentation.
Upgrade
Version history
1.0.3latest on npm
Audit
Dependencies

No dependency data recorded yet.

Agent activity
4 hits · last 30 days
node
4
Resources
githubhttps://github.com/ubilabs/kd-tree-javascript ↗
packagehttps://www.npmjs.com/package/kd-tree-javascript ↗
kd-tree-javascript — npm install kd-tree-javascript · libregistry