source: project/wiki/eggref/5/kd-tree @ 37232

Last change on this file since 37232 was 37232, checked in by Ivan Raikov, 9 months ago

kd-tree doc link fixes

File size: 6.4 KB
Line 
1= kd-tree
2
3K-D tree implementation in Chicken Scheme.
4
5== Documentation
6
7This library implements a [[http://en.wikipedia.org/wiki/K-d_tree|K-D
8tree]], which is a data structure for organizing and searching points
9in k-dimensional space.
10
11The K-D tree is a binary search tree in which every branching node
12contains a k-dimensional point, and every leaf node contains a set of
13points. Every branching node represents a splitting hyperplane that
14divides the space into two parts, known as half-spaces.
15
16Points to the left of the splitting hyperplane are contained in the
17left subtree of the node and points right of the hyperplane are
18contained in the right subtree. The splitting hyperplane is chosen so
19as to be perpendicular to one of the axes in the k-dimensional
20space. The axis at each branching level is chosen in a round-robin
21fashion. For instance, in 3-D space, at level 0, the chosen axis is X,
22so points are divided according to their X-coordinates; at level 1,
23the chosen axis is Y, so the points are divided according to their
24Y-coordinates; at the next branch level the chosen axis is Z, and so
25on.
26
27=== K-dimensional point space
28
29Module {{kspace}} provides facilities for managament of K-dimensional point spaces.
30
31<procedure>make-space:: COORDS -> SPACE</procedure>
32
33Given a list of coordinate collections of length K, constructs a [[yasos]]
34K-dimensional point space object. The coordinate collections can be
35SRFI-4 f32vectors, or collection objects as defined in the [[yasos]]
36collections module.
37
38<procedure>space? :: OBJECT -> BOOL</procedure>
39K-dimensional point space predicate.
40
41<procedure>dimension :: OBJECT -> INT</procedure>
42Returns the dimensionality of the point space.
43
44<procedure>point :: OBJECT * INT -> REAL LIST</procedure>
45Returns the coordinates of the point at the given index.
46
47<procedure>coord :: OBJECT * INT * INT -> FLOAT</procedure>
48Returns the k'th coordinate of i'th point, starting from 0.
49
50<procedure>compare-coord :: SPACE * INT * INT * INT -> INT</procedure>
51Given the indices of two points and a coordinate index, compares the respective coordinates of the two points and returns -1, 0, or 1, depending on whether the coordinates are less than, equal, or greater than each other.
52
53<procedure>squared-distance :: SPACE * INT * INT -> FLOAT</procedure>
54Returns the square of the Euclidean distance between the points at the given indices.
55
56<procedure>compare-distance :: SPACE * INT * INT -> INT</procedure>
57Compares the square of the Euclidean distance between the points at the given indices.
58
59=== K-D tree interface
60
61==== Constructors
62
63<procedure>make-kd-tree:: SPACE -> OBJECT</procedure>
64Given a {{kspace}} object, constructs and returns a [[yasos]] spatial map object.
65
66==== Predicates
67
68<procedure>spatial-map? :: OBJECT -> BOOL</procedure>
69Returns {{#t}} if the given object is a spatial map, {{#f}} otherwise.
70
71<procedure>empty? :: OBJECT -> BOOL</procedure>
72Returns {{#t}} if the given spatial map object is empty, {{#f}} otherwise.
73
74<procedure>kd-tree-is-valid? :: OBJECT -> BOOL</procedure>
75Checks whether the K-D tree property holds for the given spatial map. 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.
76
77<procedure>kd-tree-all-subtrees-are-valid? :: KD-TREE -> BOOL</procedure>
78Checks whether the K-D tree property holds for the given spatial map and all subtrees.
79
80==== Accessors
81
82<procedure>get-kspace :: OBJECT -> KSPACE</procedure>
83Returns the underlying {{kspace}} object of the map.
84
85<procedure>spatial-map->list :: KD-TREE -> POINT LIST</procedure>
86Returns a list with the points contained in the spatial map.
87
88==== Query procedures
89
90<procedure>nearest-neighbor :: SPATIAL-MAP * POINT -> POINT</procedure>
91Nearest neighbor of a point.
92
93<procedure>near-neighbors :: SPATIAL-MAP * POINT * RADIUS -> POINT LIST</procedure>
94Neighbors of a point within radius r.
95
96<procedure>k-nearest-neighbors :: SPATIAL-MAP * POINT * INT -> POINT LIST</procedure>
97K nearest neighbors of a point.
98
99<procedure>slice :: SPATIAL-MAP * AXIS * COORD * COORD -> POINT LIST</procedure>
100Returns all points between two planes.
101
102==== Combinators
103
104<procedure>spatial-map-for-each :: SPATIAL-MAP * F -> VOID</procedure>
105Point iterator.
106
107<procedure>spatial-map-fold-right :: SPATIAL-MAP * F * INIT -> INIT</procedure>
108Fold on points.
109
110<procedure>spatial-map-fold-right* :: SPATIAL-MAP * F * INIT -> INIT</procedure>
111Fold on points and their indices.
112
113==== Modifiers
114
115<procedure>kd-tree-remove :: SPATIAL-MAP * POINT -> SPATIAL-MAP</procedure>
116
117== Examples
118
119<enscript highlight="scheme">
120(import scheme (chicken base)
121        yasos random-mtzig kspace kd-tree)
122
123(let* (
124       (n (inexact->exact 1e5)) (k 40) (r 1.0) (randst (init 9))
125       
126       ;; generate random coordinates
127       (xs (randn/f32! n randst))
128       (ys (randn/f32! n randst))
129       (zs (randn/f32! n randst))
130       ;; create a kspace
131       (pts (list xs ys zs))
132       (kspace3d (make-space pts))
133       ;; create the spatial map
134       (kdt (make-kd-tree kspace3d))
135       ;; choose a random point index
136       (xi (inexact->exact (modulo (random! randst) n)))
137       ;; retrieve the coordinates of the chosen point
138       (x  (point kspace3d xi))
139       )
140
141    (print "nearest-neighbor of " x ": " (nearest-neighbor kdt x))
142    (print k " nearest neighbors of " x ": " (k-nearest-neighbors kdt x k))
143    (print "near neighbors of " x " within " r ": " (near-neighbors kdt k r))
144
145)
146
147</enscript>
148
149== Version history
150
151* 6.0 : refactored to use yasos, ported to CHICKEN 5
152* 5.0 : added list->kd-tree* procedure to KdTree class
153* 4.1-4.8 : Using f64vector for internal point representation
154* 4.0-4.1 : Added with-distance? flag to kd-tree-near-neighbors
155* 3.2 : Bug fix in kd-tree-near-neighbors
156* 2.0 : Improvements to internal representation
157* 1.0 : Initial release
158
159== License
160
161 Copyright 2012-2019 Ivan Raikov
162 
163 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.
164 
165 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.
166 
167 A full copy of the GPL license can be found at http://www.gnu.org/licenses/.
168
Note: See TracBrowser for help on using the repository browser.