kd-trees in Clojure
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
test/kdtree
.gitignore
LICENSE
README.md
project.clj
todo.org

README.md

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.2.0"]

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})

Metadata

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}

License

Copyright (C) 2009-2015 Brendan Ribera and contributors. All rights reserved.

Distributed under the MIT License; see the file LICENSE at the root of this distribution.