{"id":11206,"library":"kd-tree-javascript","title":"k-d Tree JavaScript Library","description":"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.","status":"abandoned","version":"1.0.3","language":"javascript","source_language":"en","source_url":"https://github.com/ubilabs/kd-tree-javascript","tags":["javascript"],"install":[{"cmd":"npm install kd-tree-javascript","lang":"bash","label":"npm"},{"cmd":"yarn add kd-tree-javascript","lang":"bash","label":"yarn"},{"cmd":"pnpm add kd-tree-javascript","lang":"bash","label":"pnpm"}],"dependencies":[],"imports":[{"note":"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.","wrong":"import { kdTree } from 'kd-tree-javascript';","symbol":"kdTree (global)","correct":"<!-- In HTML -->\n<script src=\"path/to/kdTree.js\"></script>\n<script>\n  const tree = new kdTree(points, distance, dimensions);\n</script>"},{"note":"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.","wrong":"const { kdTree } = require('kd-tree-javascript');","symbol":"kdTree (CommonJS)","correct":"const ubilabs = require('kd-tree-javascript');\nconst tree = new ubilabs.kdTree(points, distance, dimensions);"},{"note":"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.","wrong":"const tree = new kdTree(points, distance, dimensions); // if not globally defined","symbol":"kdTree (RequireJS / AMD)","correct":"requirejs(['path/to/kdTree.js'], function (ubilabs) {\n  const tree = new ubilabs.kdTree(points, distance, dimensions);\n});"}],"quickstart":{"code":"var points = [\n  {x: 1, y: 2},\n  {x: 3, y: 4},\n  {x: 5, y: 6},\n  {x: 7, y: 8}\n];\n\nvar distance = function(a, b){\n  return Math.pow(a.x - b.x, 2) +  Math.pow(a.y - b.y, 2);\n}\n\n// Assuming kdTree is globally available or imported via CommonJS/AMD as 'ubilabs'\n// For global: new kdTree(points, distance, [\"x\", \"y\"]);\n// For CommonJS: new ubilabs.kdTree(points, distance, [\"x\", \"y\"]);\n// For this example, we'll assume global/browser context as in README.\nvar tree = new kdTree(points, distance, [\"x\", \"y\"]);\n\nvar nearest = tree.nearest({ x: 5, y: 5 }, 2);\n\nconsole.log(nearest);\n// Expected output: \n// [ [ { x: 5, y: 6 }, 1 ], [ { x: 7, y: 8 }, 8 ] ]\n// (point {x:5,y:6} at distance 1, point {x:7,y:8} at distance 8)","lang":"javascript","description":"This quickstart demonstrates how to create a k-d tree, insert points, define a distance function, and perform a nearest neighbor search."},"warnings":[{"fix":"Consider explicitly removing global variables if conflicts arise, or encapsulate usage within a self-executing function if not using a module loader.","message":"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.","severity":"gotcha","affected_versions":">=1.0.1"},{"fix":"Evaluate alternatives if long-term support, active maintenance, or modern JavaScript features are required. Use with caution in new projects.","message":"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.","severity":"gotcha","affected_versions":">=1.0.3"},{"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.","message":"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.","severity":"gotcha","affected_versions":"*"}],"env_vars":null,"last_verified":"2026-04-19T00:00:00.000Z","next_check":"2026-07-18T00:00:00.000Z","problems":[{"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.","cause":"The `kdTree` global variable was not loaded, likely due to an incorrect script path, missing `<script>` tag in HTML, or incorrect module import.","error":"ReferenceError: kdTree is not defined"},{"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.","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.","error":"TypeError: Cannot read properties of undefined (reading 'kdTree')"}],"ecosystem":"npm"}