You are looking at historical revision 27350 of this page. It may differ significantly from its current revision.

## kd-tree

K-D tree implementation.

## Usage

(require-extension kd-tree)

## Documentation

This library implements a K-D tree, a data structure for organizing and searching points in an n-dimensional space. http://en.wikipedia.org/wiki/K-d_tree.

### Point

This library currently only supports points in 3D space.

*[procedure]*

`make-point3d:: DOUBLE * DOUBLE * DOUBLE -> POINT3D`

3D point constructor.

*[procedure]*

`point3d? :: POINT3D -> BOOL`

3D point predicate.

*[procedure]*

`point3d-x :: POINT3D -> DOUBLE`

*[procedure]*

`point3d-y :: POINT3D -> DOUBLE`

*[procedure]*

`point3d-z :: POINT3D -> DOUBLE`

Accessors for the x,y,z coordinates of a 3D point.

### KD-tree

A K-D tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space.

#### Constructors

*[procedure]*

`list->kd-tree:: POINT3D LIST -> KD-TREE`

Given a list of points, constructs and returns a K-D tree object.

#### Predicates

*[procedure]*

`kd-tree? :: KD-TREE -> BOOL`

Returns `#t` if the given object is a K-D tree, `#f` otherwise.

*[procedure]*

`kd-tree-empty? :: KD-TREE -> BOOL`

Returns `#t` if the given K-D tree object is empty, `#f` otherwise.

*[procedure]*

`kd-tree-is-valid? :: KD-TREE -> BOOL`

Checks whether the K-D tree property holds for the given tree. Specifically, it tests that all points in the left subtree lie to the left of the plane, p is on the plane, and all points in the right subtree lie to the right.

*[procedure]*

`kd-tree-all-subtrees-are-valid? :: KD-TREE -> BOOL`

Checks whether the K-D tree property holds for the given tree and all subtrees.

#### Accessors

*[procedure]*

`kd-tree->list :: KD-TREE -> POINT3D LIST`

Returns a list with the points contained in the tree.

*[procedure]*

`kd-tree->list* :: KD-TREE -> (INT . POINT3D) LIST`

Returns a list where every element has the form `(i . p)`, where i is the relative index of this point, and `p` is the point.

*[procedure]*

`kd-tree-subtrees :: KD-TREE -> KD-TREE LIST`

*[procedure]*

`kd-tree-point :: KD-TREE -> POINT3D`

#### Combinators

*[procedure]*

`kd-tree-map`

*[procedure]*

`kd-tree-for-each`

*[procedure]*

`kd-tree-for-each*`

*[procedure]*

`kd-tree-fold-right`

*[procedure]*

`kd-tree-fold-right*`

#### Query procedures

*[procedure]*

`kd-tree-nearest-neighbor`

*[procedure]*

`kd-tree-near-neighbors`

*[procedure]*

`kd-tree-near-neighbors*`

*[procedure]*

`kd-tree-k-nearest-neighbors`

*[procedure]*

`kd-tree-slice`

*[procedure]*

`kd-tree-slice*`

#### Modifiers

*[procedure]*

`kd-tree-remove`

## Examples

## About this egg

### Author

### Version history

- 4.0
- Added with-distance? flag to kd-tree-near-neighbors
- 3.2
- Bug fix in kd-tree-near-neighbors
- 2.0
- Improvements to internal representation
- 1.0
- Initial release

### License

Copyright 2012 Ivan Raikov and the Okinawa Institute of Science and Technology. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the GPL license can be found at <http://www.gnu.org/licenses/>.