• egg

## spatial-trees

Various spatial tree implementations.

## Usage

(require-extension kd-tree)

## Documentation

The spatial-tree library is intended to contain a collection of spatial tree implementations. A spatial tree is a data structure for organizing and searching points in an n-dimensional space. The present implementation code implements a single spatial tree structure, the k-d tree.

### Point

This library currently only supported 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

Ivan Raikov

### Version history

2.0
Improvements to internal representation
1.0
Initial release

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