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.
./configure make sudo make install PREFIX=/usr
The easiest way to install node-kdtree is to use the npm package manager:
npm install kdtree
Creating a tree
You may create a tree by instantiating a new
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
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:
tree.insert(39.285785, -76.610262, "USS Constellation");
Nearest neighbor searches
nearest method is used to find the point in the tree that is closest to a target point. For example:
> tree.nearest(39.273889, -76.738056); [39.272051, -76.731917, "Bill's Music, Inc."]
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.
nearestRange method is also provided, which allows us to find all of the points within a given range. For example:
> tree.nearestRange(0, 0, 3); [ [ 1, 1 ], [ 0, 2 ], [ 2, 0 ], [ 1, 0 ], [ 0, 1 ], [ 0, 0 ] ]
The first arguments to
nearestRange are the components of the point to begin searching at. The last argument is the search range.
node-kdtree is developed by Justin Ethier.
Thanks to John Tsiombikas for developing libkdtree!
Patches are welcome; please send via pull request on github.