# kdtree

Basic libkdtree binding to node

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:

```
tree.insert(39.285785, -76.610262, "USS Constellation");
```

###Nearest neighbor searches
The `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.

A `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.

##API

##Credits

node-kdtree is developed by Justin Ethier.

Thanks to John Tsiombikas for developing libkdtree!

Patches are welcome; please send via pull request on github.