source: project/wiki/eggref/4/spatial-trees @ 26816

Last change on this file since 26816 was 26816, checked in by Ivan Raikov, 9 years ago

spatial-trees version history update

File size: 3.8 KB
Line 
1[[tags:egg]]
2
3== spatial-trees
4
5Various spatial tree implementations.
6
7[[toc:]]
8
9== Usage
10
11(require-extension kd-tree)
12
13== Documentation
14
15The {{spatial-tree}} library is intended to contain a collection of
16spatial tree implementations. A spatial tree is a data structure for
17organizing and searching points in an n-dimensional space.  The
18present implementation code implements a single spatial tree
19structure, the [[http://en.wikipedia.org/wiki/K-d_tree|k-d tree]].
20
21=== Point
22
23This library currently only supported points in 3D space.
24
25<procedure>make-point3d:: DOUBLE * DOUBLE * DOUBLE -> POINT3D</procedure>
26
273D point constructor.
28
29<procedure>point3d? :: POINT3D -> BOOL</procedure>
30
313D 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
37Accessors for the x,y,z coordinates of a 3D point.
38
39=== KD-tree
40
41A K-D tree (short for k-dimensional tree) is a space-partitioning data
42structure for organizing points in a k-dimensional space.
43
44==== Constructors
45   
46<procedure>list->kd-tree:: POINT3D LIST -> KD-TREE</procedure>
47
48Given 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
54Returns {{#t}} if the given object is a K-D tree, {{#f}} otherwise.
55
56<procedure>kd-tree-empty? :: KD-TREE -> BOOL  </procedure>
57
58Returns {{#t}} if the given K-D tree object is empty, {{#f}} otherwise.
59
60<procedure>kd-tree-is-valid? :: KD-TREE -> BOOL  </procedure>
61
62Checks whether the K-D tree property holds for the given tree.
63Specifically, it tests that all points in the left subtree lie to the
64left of the plane, p is on the plane, and all points in the right
65subtree lie to the right.
66
67<procedure>kd-tree-all-subtrees-are-valid? :: KD-TREE -> BOOL </procedure>
68
69Checks whether the K-D tree property holds for the given tree and all
70subtrees.
71
72==== Accessors
73
74<procedure>kd-tree->list :: KD-TREE -> POINT3D LIST</procedure>
75
76Returns a list with the points contained in the tree.
77
78<procedure>kd-tree->list* :: KD-TREE -> (INT . POINT3D) LIST </procedure>
79
80Returns a list where every element has the form {{(i . p)}}, where i
81is 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
Note: See TracBrowser for help on using the repository browser.