Liking cljdoc? Tell your friends :D

# clj-kdtree

## Overview

A Kd-tree is a special type of binary tree that partitions points in a k-dimensional space. It can be used for efficient nearest-neighbor searches.

For more detail, refer to Wikipedia on Kd-trees.

## Usage

Add this to your project.clj `:dependencies` list:

``````[clj-kdtree "1.1.2"]
``````

#### Build

``````(require 'kdtree)

(def points [[8 8] [3 1] [6 6] [7 7] [1 3] [4 4] [5 5]])
;; Build a kdtree from a set of points
(def tree (kdtree/build-tree points))
(println "Tree:" tree)
``````

#### Nearest neighbor

Use tree to find neighbors for one point given a set of points:

``````(println "Four points closest to [2 2]:\n"
(kdtree/nearest-neighbor tree [2 2] 4))
``````

output:

``````Four points closest to [2 2]:
(#kdtree.Result{:point [1.0 3.0], :dist-squared 2.0}
#kdtree.Result{:point [3.0 1.0], :dist-squared 2.0}
#kdtree.Result{:point [4.0 4.0], :dist-squared 8.0}
#kdtree.Result{:point [5.0 5.0], :dist-squared 18.0})
``````

#### Interval search

Find all points inside interval:

``````(println "Points 1≤x≤4, 3≤y≤6\n"
(kdtree/interval-search tree [[1 4] [3 6]]))
``````

output:

``````Points 1≤x≤4, 3≤y≤6
[[1.0 3.0] [4.0 4.0]]
``````

#### Delete

Delete point and return new version of a tree. Doesn't change old tree.

``````(println "Four points with deletion:\n"
(-> tree
(kdtree/delete [1 3])
(kdtree/delete [3 1])
(kdtree/nearest-neighbor [2 2] 4)))
``````

output:

``````Four points with deletion:
(#kdtree.Result{:point [4.0 4.0], :dist-squared 8.0}
#kdtree.Result{:point [5.0 5.0], :dist-squared 18.0}
#kdtree.Result{:point [6.0 6.0], :dist-squared 32.0}
#kdtree.Result{:point [7.0 7.0], :dist-squared 50.0})
``````

#### Insert

Insert point and return new version of a tree. Doesn't change old tree.

``````(println "\n\nFour points with insertion:\n"
(-> tree
(kdtree/insert [1.5 1.5])
(kdtree/nearest-neighbor [2 2] 4)))
``````

output:

``````Four points with insertion:
(#kdtree.Result{:point [1.5 1.5], :dist-squared 0.5}
#kdtree.Result{:point [3.0 1.0], :dist-squared 2.0}
#kdtree.Result{:point [1.0 3.0], :dist-squared 2.0}
#kdtree.Result{:point [4.0 4.0], :dist-squared 8.0})
``````

To store arbitrary information in points you can use metadata attached to the points. All tree modification operations like `build-tree`, `insert` and `delete` retain metadata. All query operation like `nearest-neighbor` and `interval-search` return points with corresponded meta:

``````(def point (with-meta [0 0] {:value "Hello"}))
(def tree (kdtree/build-tree [point]))
(println "Meta:"
(meta (kdtree/nearest-neighbor tree [1 1])))
``````

output:

``````Meta: {:value Hello}
`````` 