1 | [[tags:egg]] |
---|
2 | [[toc:]] |
---|
3 | |
---|
4 | == kd-tree |
---|
5 | |
---|
6 | K-D tree implementation. |
---|
7 | |
---|
8 | == Documentation |
---|
9 | |
---|
10 | This library implements a [[http://en.wikipedia.org/wiki/K-d_tree|K-D |
---|
11 | tree]], which is a data structure for organizing and searching points |
---|
12 | in k-dimensional space. |
---|
13 | |
---|
14 | The K-D tree is a binary search tree in which every branching node |
---|
15 | contains a k-dimensional point, and every leaf node contains a set of |
---|
16 | points. Every branching node represents a splitting hyperplane that |
---|
17 | divides the space into two parts, known as half-spaces. |
---|
18 | |
---|
19 | Points to the left of the splitting hyperplane are contained in the |
---|
20 | left subtree of the node and points right of the hyperplane are |
---|
21 | contained in the right subtree. The splitting hyperplane is chosen so |
---|
22 | as to be perpendicular to one of the axes in the k-dimensional |
---|
23 | space. The axis at each branching level is chosen in a round-robin |
---|
24 | fashion. For instance, in 3-D space, at level 0, the chosen axis is X, |
---|
25 | so points are divided according to their X-coordinates; at level 1, |
---|
26 | the chosen axis is Y, so the points are divided according to their |
---|
27 | Y-coordinates; at the next branch level the chosen axis is Z, and so |
---|
28 | on. |
---|
29 | |
---|
30 | === K-dimensional point space |
---|
31 | |
---|
32 | Module {{kspace}} provides facilities for managament of K-dimensional point spaces. |
---|
33 | |
---|
34 | <procedure>make-space:: COORDS -> SPACE</procedure> |
---|
35 | |
---|
36 | Given a list of coordinate collections of length K, constructs a [[yasos]] |
---|
37 | K-dimensional point space object. The coordinate collections can be |
---|
38 | SRFI-4 f32vectors, or collection objects as defined in the [[yasos]] |
---|
39 | collections module. |
---|
40 | |
---|
41 | <procedure>space? :: OBJECT -> BOOL</procedure> |
---|
42 | K-dimensional point space predicate. |
---|
43 | |
---|
44 | <procedure>dimension :: OBJECT -> INT</procedure> |
---|
45 | Returns the dimensionality of the point space. |
---|
46 | |
---|
47 | <procedure>point :: OBJECT * INT -> REAL LIST</procedure> |
---|
48 | Returns the coordinates of the point at the given index. |
---|
49 | |
---|
50 | <procedure>coord :: OBJECT * INT * INT -> FLOAT</procedure> |
---|
51 | Returns the k'th coordinate of i'th point, starting from 0. |
---|
52 | |
---|
53 | <procedure>compare-coord :: SPACE * INT * INT * INT -> INT</procedure> |
---|
54 | Given 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> |
---|
57 | Returns the square of the Euclidean distance between the points at the given indices. |
---|
58 | |
---|
59 | <procedure>compare-distance :: SPACE * INT * INT -> INT</procedure> |
---|
60 | Compares 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> |
---|
67 | Given a {{kspace}} object, constructs and returns a [[yasos]] spatial map object. |
---|
68 | |
---|
69 | ==== Predicates |
---|
70 | |
---|
71 | <procedure>spatial-map? :: OBJECT -> BOOL</procedure> |
---|
72 | Returns {{#t}} if the given object is a spatial map, {{#f}} otherwise. |
---|
73 | |
---|
74 | <procedure>empty? :: OBJECT -> BOOL</procedure> |
---|
75 | Returns {{#t}} if the given spatial map object is empty, {{#f}} otherwise. |
---|
76 | |
---|
77 | <procedure>kd-tree-is-valid? :: OBJECT -> BOOL</procedure> |
---|
78 | Checks 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> |
---|
81 | Checks 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> |
---|
86 | Returns the underlying {{kspace}} object of the map. |
---|
87 | |
---|
88 | <procedure>spatial-map->list :: SPATIAL-MAP -> POINT LIST</procedure> |
---|
89 | Returns a list with the points contained in the spatial map. |
---|
90 | |
---|
91 | ==== Query procedures |
---|
92 | |
---|
93 | <procedure>nearest-neighbor :: SPATIAL-MAP * POINT -> POINT</procedure> |
---|
94 | Nearest neighbor of a point. |
---|
95 | |
---|
96 | <procedure>near-neighbors :: SPATIAL-MAP * POINT * RADIUS -> POINT LIST</procedure> |
---|
97 | Neighbors of a point within radius r. |
---|
98 | |
---|
99 | <procedure>k-nearest-neighbors :: SPATIAL-MAP * POINT * INT -> POINT LIST</procedure> |
---|
100 | K nearest neighbors of a point. |
---|
101 | |
---|
102 | <procedure>slice :: SPATIAL-MAP * AXIS * COORD * COORD -> POINT LIST</procedure> |
---|
103 | Returns all points between two planes. |
---|
104 | |
---|
105 | ==== Combinators |
---|
106 | |
---|
107 | <procedure>spatial-map-for-each :: SPATIAL-MAP * F -> VOID</procedure> |
---|
108 | Point iterator. |
---|
109 | |
---|
110 | <procedure>spatial-map-fold-right :: SPATIAL-MAP * F * INIT -> INIT</procedure> |
---|
111 | Fold on points. |
---|
112 | |
---|
113 | <procedure>spatial-map-fold-right* :: SPATIAL-MAP * F * INIT -> INIT</procedure> |
---|
114 | Fold 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 | |
---|