k-d Tree JavaScript Library

1.0.3 · abandoned · verified Sun Apr 19

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.

Common errors

```
ReferenceError: kdTree is not defined
```
cause 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')
```
cause 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.

Warnings

gotcha When 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.
gotcha The 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.
gotcha The 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.

Install

npm install kd-tree-javascript npm
yarn add kd-tree-javascript yarn
pnpm add kd-tree-javascript pnpm

Imports

kdTree (global)
wrong:
```
import { kdTree } from 'kd-tree-javascript';
```
correct:
```

<script src="path/to/kdTree.js"></script>
<script>
  const tree = new kdTree(points, distance, dimensions);
</script>
```
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)
wrong:
```
const { kdTree } = require('kd-tree-javascript');
```
correct:
```
const ubilabs = require('kd-tree-javascript');
const tree = new ubilabs.kdTree(points, distance, dimensions);
```
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)
wrong:
```
const tree = new kdTree(points, distance, dimensions); // if not globally defined
```
correct:
```
requirejs(['path/to/kdTree.js'], function (ubilabs) {
  const tree = new ubilabs.kdTree(points, distance, dimensions);
});
```
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.

Quickstart

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)

view raw JSON →