node-kdtree is a node.js addon that defines a wrapper to libkdtree, allowing one to work with KD trees directly in node. A KD tree is a data structure that organizes points in a multi-dimensional space, and in particular is useful for performing efficient nearest neighbor searches.

Dependencies

The kdtree C library is required. In order to install, get the latest version from here and run the following commands:

./configure
make
sudo make install PREFIX=/usr

Installation

The easiest way to install node-kdtree is to use the npm package manager:

npm install kdtree

Usage

Creating a tree

You may create a tree by instantiating a new KDTree object:

var kd = require('kdtree');
var tree = new kd.KDTree(3); // A new tree for 3-dimensional points

When creating a new tree we can specify the dimensions of the data. For example, a three-dimensional tree will contain points of the form (x, y, z). If a dimension is not specified, the tree defaults to three dimensions.

Adding data to a tree

Data may be added to the tree using the insert method:

tree.insert(1, 2, 3);
tree.insert(10, 20, 30);

There must be one argument for each dimension of the data - for example, a three dimensional tree would have three arguments to insert. An optional data parameter may also be specified to store a data value alongside the point data:

nearest will return an array containing closest point, or an empty array if no points were found. As shown above, if the point contains a data value, that value will also be returned at the end of the array.

A nearestRange method is also provided, which allows us to find all of the points within a given range. For example: