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

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

kd-tree doc fixes

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