# kd-tree
K-D tree implementation in Chicken Scheme.
## Documentation
This library implements a K-D tree
(http://en.wikipedia.org/wiki/K-d_tree), which is a data structure for
organizing and searching points in k-dimensional space.
The K-D tree is a binary search tree in which every branching node
contains a k-dimensional point, and every leaf node contains a set of
points. Every branching node represents a splitting hyperplane that
divides the space into two parts, known as half-spaces.
Points to the left of the splitting hyperplane are contained in the
left subtree of the node and points right of the hyperplane are
contained in the right subtree. The splitting hyperplane is chosen so
as to be perpendicular to one of the axes in the k-dimensional
space. The axis at each branching level is chosen in a round-robin
fashion. For instance, in 3-D space, at level 0, the chosen axis is X,
so points are divided according to their X-coordinates; at level 1,
the chosen axis is Y, so the points are divided according to their
Y-coordinates; at the next branch level the chosen axis is Z, and so
on.
### Point
This library currently only supports points in 3D space.
make-point3d:: DOUBLE * DOUBLE * DOUBLE -> POINT3D
3D point constructor.
point3d? :: POINT3D -> BOOL
3D point predicate.
point3d-x :: POINT3D -> DOUBLE
point3d-y :: POINT3D -> DOUBLE
point3d-z :: POINT3D -> DOUBLE
Accessors for the x,y,z coordinates of a 3D point.
#### Constructors
list->kd-tree:: POINT3D LIST -> KD-TREE
Given a list of points, constructs and returns a K-D tree object.
#### Predicates
kd-tree? :: KD-TREE -> BOOL
Returns `#t` if the given object is a K-D tree, `#f` otherwise.
kd-tree-empty? :: KD-TREE -> BOOL
Returns `#t` if the given K-D tree object is empty, `#f` otherwise.
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.
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
kd-tree->list :: KD-TREE -> POINT3D LIST
Returns a list with the points contained in the tree.
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.
kd-tree-subtrees :: KD-TREE -> KD-TREE LIST
kd-tree-point :: KD-TREE -> POINT3D
#### Combinators
kd-tree-map
kd-tree-for-each
kd-tree-for-each*
kd-tree-fold-right
kd-tree-fold-right*
#### Query procedures
kd-tree-nearest-neighbor
kd-tree-near-neighbors
kd-tree-near-neighbors*
kd-tree-k-nearest-neighbors
kd-tree-slice
kd-tree-slice*
#### Modifiers
kd-tree-remove
## Examples
## Version history
- 5.0 : added list->kd-tree* procedure to KdTree class
- 4.1-4.8 : Using f64vector for internal point representation
- 4.0-4.1 : 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-2016 Ivan Raikov
>
> 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
> .