Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

spatial-trees

Various spatial tree implementations.

  1. Outdated egg!
  2. spatial-trees
  3. Usage
  4. Documentation
    1. Point
    2. KD-tree
      1. Constructors
      2. Predicates
      3. Accessors
      4. Combinators
      5. Query procedures
      6. Modifiers
  5. Examples
  6. About this egg
    1. Author
    2. Version history
    3. License

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

About this egg

Author

Ivan Raikov

Version history
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/>.