((section 2 "Outdated egg!" (p "This is an egg for CHICKEN 4, the unsupported old release.  You're almost certainly looking for " (int-link "/eggref/5/spatial-trees" "the CHICKEN 5 version of this egg") ", if it exists.") (p "If it does not exist, there may be equivalent functionality provided by another egg; have a look at the " (link "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")) (section 2 "spatial-trees" (p "Various spatial tree implementations.") (toc)) (section 2 "Usage" (p "(require-extension kd-tree)")) (section 2 "Documentation" (p "The " (tt "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 " (link "http://en.wikipedia.org/wiki/K-d_tree" "k-d tree") ".") (section 3 "Point" (p "This library currently only supported points in 3D space.") (def (sig (procedure "make-point3d:: DOUBLE * DOUBLE * DOUBLE -> POINT3D" (id make-point3d))) (p "3D point constructor.")) (def (sig (procedure "point3d? :: POINT3D -> BOOL" (id point3d?))) (p "3D point predicate.")) (def (sig (procedure "point3d-x :: POINT3D -> DOUBLE" (id point3d-x)) (procedure "point3d-y :: POINT3D -> DOUBLE" (id point3d-y)) (procedure "point3d-z :: POINT3D -> DOUBLE" (id point3d-z))) (p "Accessors for the x,y,z coordinates of a 3D point."))) (section 3 "KD-tree" (p "A K-D tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space.") (section 4 "Constructors" (pre "  ") (def (sig (procedure "list->kd-tree:: POINT3D LIST  -> KD-TREE" (id list->kd-tree))) (p "Given a list of points, constructs and returns a K-D tree object."))) (section 4 "Predicates" (def (sig (procedure "kd-tree? :: KD-TREE -> BOOL " (id kd-tree?))) (p "Returns " (tt "#t") " if the given object is a K-D tree, " (tt "#f") " otherwise.")) (def (sig (procedure "kd-tree-empty? :: KD-TREE -> BOOL  " (id kd-tree-empty?))) (p "Returns " (tt "#t") " if the given K-D tree object is empty, " (tt "#f") " otherwise.")) (def (sig (procedure "kd-tree-is-valid? :: KD-TREE -> BOOL  " (id kd-tree-is-valid?))) (p "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.")) (def (sig (procedure "kd-tree-all-subtrees-are-valid? :: KD-TREE -> BOOL " (id kd-tree-all-subtrees-are-valid?))) (p "Checks whether the K-D tree property holds for the given tree and all subtrees."))) (section 4 "Accessors" (def (sig (procedure "kd-tree->list :: KD-TREE -> POINT3D LIST" (id kd-tree->list))) (p "Returns a list with the points contained in the tree.")) (def (sig (procedure "kd-tree->list* :: KD-TREE -> (INT . POINT3D) LIST " (id kd-tree->list*))) (p "Returns a list where every element has the form " (tt "(i . p)") ", where i is the relative index of this point, and " (tt "p") " is the point.")) (def (sig (procedure "kd-tree-subtrees :: KD-TREE -> KD-TREE LIST" (id kd-tree-subtrees)))) (def (sig (procedure "kd-tree-point :: KD-TREE -> POINT3D  " (id kd-tree-point))))) (section 4 "Combinators" (def (sig (procedure "kd-tree-map " (id kd-tree-map)))) (def (sig (procedure "kd-tree-for-each " (id kd-tree-for-each)))) (def (sig (procedure "kd-tree-for-each* " (id kd-tree-for-each*)))) (def (sig (procedure "kd-tree-fold-right " (id kd-tree-fold-right)))) (def (sig (procedure "kd-tree-fold-right* " (id kd-tree-fold-right*))))) (section 4 "Query procedures" (def (sig (procedure "kd-tree-nearest-neighbor " (id kd-tree-nearest-neighbor)))) (def (sig (procedure "kd-tree-near-neighbors " (id kd-tree-near-neighbors)))) (def (sig (procedure "kd-tree-near-neighbors* " (id kd-tree-near-neighbors*)))) (def (sig (procedure "kd-tree-k-nearest-neighbors " (id kd-tree-k-nearest-neighbors)))) (def (sig (procedure "kd-tree-slice " (id kd-tree-slice)))) (def (sig (procedure "kd-tree-slice* " (id kd-tree-slice*))))) (section 4 "Modifiers" (def (sig (procedure "kd-tree-remove " (id kd-tree-remove))))))) (section 2 "Examples") (section 2 "About this egg" (section 3 "Author" (p (int-link "/users/ivan-raikov" "Ivan Raikov"))) (section 3 "Version history" (dl (dt "2.0") (dd "Improvements to internal representation") (dt "1.0") (dd "Initial release"))) (section 3 "License" (pre "Copyright 2012 Ivan Raikov and the Okinawa Institute of Science and Technology.\n\nThis program is free software: you can redistribute it and/or modify\nit under the terms of the GNU General Public License as published by\nthe Free Software Foundation, either version 3 of the License, or (at\nyour option) any later version.\n\nThis program is distributed in the hope that it will be useful, but\nWITHOUT ANY WARRANTY; without even the implied warranty of\nMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\nGeneral Public License for more details.\n\nA full copy of the GPL license can be found at\n<http://www.gnu.org/licenses/>."))))