1 | [[tags:egg]] |
---|
2 | |
---|
3 | == spatial-trees |
---|
4 | |
---|
5 | Various spatial tree implementations. |
---|
6 | |
---|
7 | [[toc:]] |
---|
8 | |
---|
9 | == Usage |
---|
10 | |
---|
11 | (require-extension kd-tree) |
---|
12 | |
---|
13 | == Documentation |
---|
14 | |
---|
15 | The {{spatial-tree}} library is intended to contain a collection of |
---|
16 | spatial tree implementations. A spatial tree is a data structure for |
---|
17 | organizing and searching points in an n-dimensional space. The |
---|
18 | present implementation code implements a single spatial tree |
---|
19 | structure, the [[http://en.wikipedia.org/wiki/K-d_tree|k-d tree]]. |
---|
20 | |
---|
21 | === Point |
---|
22 | |
---|
23 | This library currently only supported points in 3D space. |
---|
24 | |
---|
25 | <procedure>make-point3d:: DOUBLE * DOUBLE * DOUBLE -> POINT3D</procedure> |
---|
26 | |
---|
27 | 3D point constructor. |
---|
28 | |
---|
29 | <procedure>point3d? :: POINT3D -> BOOL</procedure> |
---|
30 | |
---|
31 | 3D point predicate. |
---|
32 | |
---|
33 | <procedure>point3d-x :: POINT3D -> DOUBLE</procedure> |
---|
34 | <procedure>point3d-y :: POINT3D -> DOUBLE</procedure> |
---|
35 | <procedure>point3d-z :: POINT3D -> DOUBLE</procedure> |
---|
36 | |
---|
37 | Accessors for the x,y,z coordinates of a 3D point. |
---|
38 | |
---|
39 | === KD-tree |
---|
40 | |
---|
41 | A K-D tree (short for k-dimensional tree) is a space-partitioning data |
---|
42 | structure for organizing points in a k-dimensional space. |
---|
43 | |
---|
44 | ==== Constructors |
---|
45 | |
---|
46 | <procedure>list->kd-tree:: POINT3D LIST -> KD-TREE</procedure> |
---|
47 | |
---|
48 | Given a list of points, constructs and returns a K-D tree object. |
---|
49 | |
---|
50 | ==== Predicates |
---|
51 | |
---|
52 | <procedure>kd-tree? :: KD-TREE -> BOOL </procedure> |
---|
53 | |
---|
54 | Returns {{#t}} if the given object is a K-D tree, {{#f}} otherwise. |
---|
55 | |
---|
56 | <procedure>kd-tree-empty? :: KD-TREE -> BOOL </procedure> |
---|
57 | |
---|
58 | Returns {{#t}} if the given K-D tree object is empty, {{#f}} otherwise. |
---|
59 | |
---|
60 | <procedure>kd-tree-is-valid? :: KD-TREE -> BOOL </procedure> |
---|
61 | |
---|
62 | Checks whether the K-D tree property holds for the given tree. |
---|
63 | Specifically, it tests that all points in the left subtree lie to the |
---|
64 | left of the plane, p is on the plane, and all points in the right |
---|
65 | subtree lie to the right. |
---|
66 | |
---|
67 | <procedure>kd-tree-all-subtrees-are-valid? :: KD-TREE -> BOOL </procedure> |
---|
68 | |
---|
69 | Checks whether the K-D tree property holds for the given tree and all |
---|
70 | subtrees. |
---|
71 | |
---|
72 | ==== Accessors |
---|
73 | |
---|
74 | <procedure>kd-tree->list :: KD-TREE -> POINT3D LIST</procedure> |
---|
75 | |
---|
76 | Returns a list with the points contained in the tree. |
---|
77 | |
---|
78 | <procedure>kd-tree->list* :: KD-TREE -> (INT . POINT3D) LIST </procedure> |
---|
79 | |
---|
80 | Returns a list where every element has the form {{(i . p)}}, where i |
---|
81 | is the relative index of this point, and {{p}} is the point. |
---|
82 | |
---|
83 | <procedure>kd-tree-subtrees :: KD-TREE -> KD-TREE LIST</procedure> |
---|
84 | |
---|
85 | <procedure>kd-tree-point :: KD-TREE -> POINT3D </procedure> |
---|
86 | |
---|
87 | ==== Combinators |
---|
88 | |
---|
89 | <procedure>kd-tree-map </procedure> |
---|
90 | |
---|
91 | <procedure>kd-tree-for-each </procedure> |
---|
92 | |
---|
93 | <procedure>kd-tree-for-each* </procedure> |
---|
94 | |
---|
95 | <procedure>kd-tree-fold-right </procedure> |
---|
96 | |
---|
97 | <procedure>kd-tree-fold-right* </procedure> |
---|
98 | |
---|
99 | ==== Query procedures |
---|
100 | |
---|
101 | <procedure>kd-tree-nearest-neighbor </procedure> |
---|
102 | |
---|
103 | <procedure>kd-tree-near-neighbors </procedure> |
---|
104 | |
---|
105 | <procedure>kd-tree-near-neighbors* </procedure> |
---|
106 | |
---|
107 | <procedure>kd-tree-k-nearest-neighbors </procedure> |
---|
108 | |
---|
109 | <procedure>kd-tree-slice </procedure> |
---|
110 | |
---|
111 | <procedure>kd-tree-slice* </procedure> |
---|
112 | |
---|
113 | ==== Modifiers |
---|
114 | |
---|
115 | <procedure>kd-tree-remove </procedure> |
---|
116 | |
---|
117 | |
---|
118 | == Examples |
---|
119 | |
---|
120 | |
---|
121 | == About this egg |
---|
122 | |
---|
123 | |
---|
124 | === Author |
---|
125 | |
---|
126 | [[/users/ivan-raikov|Ivan Raikov]] |
---|
127 | |
---|
128 | === Version history |
---|
129 | |
---|
130 | ; 2.0 : Improvements to internal representation |
---|
131 | ; 1.0 : Initial release |
---|
132 | |
---|
133 | === License |
---|
134 | |
---|
135 | |
---|
136 | Copyright 2012 Ivan Raikov and the Okinawa Institute of Science and Technology. |
---|
137 | |
---|
138 | This program is free software: you can redistribute it and/or modify |
---|
139 | it under the terms of the GNU General Public License as published by |
---|
140 | the Free Software Foundation, either version 3 of the License, or (at |
---|
141 | your option) any later version. |
---|
142 | |
---|
143 | This program is distributed in the hope that it will be useful, but |
---|
144 | WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
145 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
146 | General Public License for more details. |
---|
147 | |
---|
148 | A full copy of the GPL license can be found at |
---|
149 | <http://www.gnu.org/licenses/>. |
---|
150 | |
---|