source: project/wiki/eggref/4/kd-tree @ 27043

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

copied spatial-trees doc page to kd-tree

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