Various spatial tree implementations.
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.
This library currently only supported points in 3D space.
3D point constructor.
3D point predicate.
Accessors for the x,y,z coordinates of a 3D point.
A K-D tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space.
Given a list of points, constructs and returns a K-D tree object.
Returns #t if the given object is a K-D tree, #f otherwise.
Returns #t if the given K-D tree object is empty, #f otherwise.
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.
Checks whether the K-D tree property holds for the given tree and all subtrees.
Returns a list with the points contained in the tree.
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.
- Improvements to internal representation
- 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 <http://www.gnu.org/licenses/>.