You can edit this page using wiki syntax for markup.

Article contents:== Outdated egg! This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for [[/eggref/5/spatial-trees|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 [[https://wiki.call-cc.org/chicken-projects/egg-index-5.html|egg index]]. Otherwise, please consider porting this egg to the current version of CHICKEN. [[tags:egg]] == spatial-trees Various spatial tree implementations. [[toc:]] == 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 [[http://en.wikipedia.org/wiki/K-d_tree|k-d tree]]. === Point This library currently only supported points in 3D space. <procedure>make-point3d:: DOUBLE * DOUBLE * DOUBLE -> POINT3D</procedure> 3D point constructor. <procedure>point3d? :: POINT3D -> BOOL</procedure> 3D point predicate. <procedure>point3d-x :: POINT3D -> DOUBLE</procedure> <procedure>point3d-y :: POINT3D -> DOUBLE</procedure> <procedure>point3d-z :: POINT3D -> DOUBLE</procedure> 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</procedure> Given a list of points, constructs and returns a K-D tree object. ==== Predicates <procedure>kd-tree? :: KD-TREE -> BOOL </procedure> Returns {{#t}} if the given object is a K-D tree, {{#f}} otherwise. <procedure>kd-tree-empty? :: KD-TREE -> BOOL </procedure> Returns {{#t}} if the given K-D tree object is empty, {{#f}} otherwise. <procedure>kd-tree-is-valid? :: KD-TREE -> BOOL </procedure> 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 </procedure> Checks whether the K-D tree property holds for the given tree and all subtrees. ==== Accessors <procedure>kd-tree->list :: KD-TREE -> POINT3D LIST</procedure> Returns a list with the points contained in the tree. <procedure>kd-tree->list* :: KD-TREE -> (INT . POINT3D) LIST </procedure> 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> <procedure>kd-tree-point :: KD-TREE -> POINT3D </procedure> ==== Combinators <procedure>kd-tree-map </procedure> <procedure>kd-tree-for-each </procedure> <procedure>kd-tree-for-each* </procedure> <procedure>kd-tree-fold-right </procedure> <procedure>kd-tree-fold-right* </procedure> ==== Query procedures <procedure>kd-tree-nearest-neighbor </procedure> <procedure>kd-tree-near-neighbors </procedure> <procedure>kd-tree-near-neighbors* </procedure> <procedure>kd-tree-k-nearest-neighbors </procedure> <procedure>kd-tree-slice </procedure> <procedure>kd-tree-slice* </procedure> ==== Modifiers <procedure>kd-tree-remove </procedure> == Examples == About this egg === Author [[/users/ivan-raikov|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/>. Description of your changes:

I would like to authenticate

Spam control

What do you get when you multiply 4 by 2?