root / rgbdslam / gicp / ann_1.1.1 / src / kd_tree.h @ 9240aaa3
History | View | Annotate | Download (7.8 KB)
1 | 9240aaa3 | Alex | //----------------------------------------------------------------------
|
---|---|---|---|
2 | // File: kd_tree.h
|
||
3 | // Programmer: Sunil Arya and David Mount
|
||
4 | // Description: Declarations for standard kd-tree routines
|
||
5 | // Last modified: 05/03/05 (Version 1.1)
|
||
6 | //----------------------------------------------------------------------
|
||
7 | // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
|
||
8 | // David Mount. All Rights Reserved.
|
||
9 | //
|
||
10 | // This software and related documentation is part of the Approximate
|
||
11 | // Nearest Neighbor Library (ANN). This software is provided under
|
||
12 | // the provisions of the Lesser GNU Public License (LGPL). See the
|
||
13 | // file ../ReadMe.txt for further information.
|
||
14 | //
|
||
15 | // The University of Maryland (U.M.) and the authors make no
|
||
16 | // representations about the suitability or fitness of this software for
|
||
17 | // any purpose. It is provided "as is" without express or implied
|
||
18 | // warranty.
|
||
19 | //----------------------------------------------------------------------
|
||
20 | // History:
|
||
21 | // Revision 0.1 03/04/98
|
||
22 | // Initial release
|
||
23 | // Revision 1.1 05/03/05
|
||
24 | // Added fixed radius kNN search
|
||
25 | //----------------------------------------------------------------------
|
||
26 | |||
27 | #ifndef ANN_kd_tree_H
|
||
28 | #define ANN_kd_tree_H
|
||
29 | |||
30 | #include <ANN/ANNx.h> // all ANN includes |
||
31 | |||
32 | using namespace std; // make std:: available
|
||
33 | |||
34 | //----------------------------------------------------------------------
|
||
35 | // Generic kd-tree node
|
||
36 | //
|
||
37 | // Nodes in kd-trees are of two types, splitting nodes which contain
|
||
38 | // splitting information (a splitting hyperplane orthogonal to one
|
||
39 | // of the coordinate axes) and leaf nodes which contain point
|
||
40 | // information (an array of points stored in a bucket). This is
|
||
41 | // handled by making a generic class kd_node, which is essentially an
|
||
42 | // empty shell, and then deriving the leaf and splitting nodes from
|
||
43 | // this.
|
||
44 | //----------------------------------------------------------------------
|
||
45 | |||
46 | class ANNkd_node{ // generic kd-tree node (empty shell)
|
||
47 | public:
|
||
48 | virtual ~ANNkd_node() {} // virtual distroyer
|
||
49 | |||
50 | virtual void ann_search(ANNdist) = 0; // tree search |
||
51 | virtual void ann_pri_search(ANNdist) = 0; // priority search |
||
52 | virtual void ann_FR_search(ANNdist) = 0; // fixed-radius search |
||
53 | |||
54 | virtual void getStats( // get tree statistics |
||
55 | int dim, // dimension of space |
||
56 | ANNkdStats &st, // statistics
|
||
57 | ANNorthRect &bnd_box) = 0; // bounding box |
||
58 | // print node
|
||
59 | virtual void print(int level, ostream &out) = 0; |
||
60 | virtual void dump(ostream &out) = 0; // dump node |
||
61 | |||
62 | friend class ANNkd_tree; // allow kd-tree to access us
|
||
63 | }; |
||
64 | |||
65 | //----------------------------------------------------------------------
|
||
66 | // kd-splitting function:
|
||
67 | // kd_splitter is a pointer to a splitting routine for preprocessing.
|
||
68 | // Different splitting procedures result in different strategies
|
||
69 | // for building the tree.
|
||
70 | //----------------------------------------------------------------------
|
||
71 | |||
72 | typedef void (*ANNkd_splitter)( // splitting routine for kd-trees |
||
73 | ANNpointArray pa, // point array (unaltered)
|
||
74 | ANNidxArray pidx, // point indices (permuted on return)
|
||
75 | const ANNorthRect &bnds, // bounding rectangle for cell |
||
76 | int n, // number of points |
||
77 | int dim, // dimension of space |
||
78 | int &cut_dim, // cutting dimension (returned) |
||
79 | ANNcoord &cut_val, // cutting value (returned)
|
||
80 | int &n_lo); // num of points on low side (returned) |
||
81 | |||
82 | //----------------------------------------------------------------------
|
||
83 | // Leaf kd-tree node
|
||
84 | // Leaf nodes of the kd-tree store the set of points associated
|
||
85 | // with this bucket, stored as an array of point indices. These
|
||
86 | // are indices in the array points, which resides with the
|
||
87 | // root of the kd-tree. We also store the number of points
|
||
88 | // that reside in this bucket.
|
||
89 | //----------------------------------------------------------------------
|
||
90 | |||
91 | class ANNkd_leaf: public ANNkd_node // leaf node for kd-tree
|
||
92 | { |
||
93 | int n_pts; // no. points in bucket |
||
94 | ANNidxArray bkt; // bucket of points
|
||
95 | public:
|
||
96 | ANNkd_leaf( // constructor
|
||
97 | int n, // number of points |
||
98 | ANNidxArray b) // bucket
|
||
99 | { |
||
100 | n_pts = n; // number of points in bucket
|
||
101 | bkt = b; // the bucket
|
||
102 | } |
||
103 | |||
104 | ~ANNkd_leaf() { } // destructor (none)
|
||
105 | |||
106 | virtual void getStats( // get tree statistics |
||
107 | int dim, // dimension of space |
||
108 | ANNkdStats &st, // statistics
|
||
109 | ANNorthRect &bnd_box); // bounding box
|
||
110 | virtual void print(int level, ostream &out);// print node |
||
111 | virtual void dump(ostream &out); // dump node |
||
112 | |||
113 | virtual void ann_search(ANNdist); // standard search |
||
114 | virtual void ann_pri_search(ANNdist); // priority search |
||
115 | virtual void ann_FR_search(ANNdist); // fixed-radius search |
||
116 | }; |
||
117 | |||
118 | //----------------------------------------------------------------------
|
||
119 | // KD_TRIVIAL is a special pointer to an empty leaf node. Since
|
||
120 | // some splitting rules generate many (more than 50%) trivial
|
||
121 | // leaves, we use this one shared node to save space.
|
||
122 | //
|
||
123 | // The pointer is initialized to NULL, but whenever a kd-tree is
|
||
124 | // created, we allocate this node, if it has not already been
|
||
125 | // allocated. This node is *never* deallocated, so it produces
|
||
126 | // a small memory leak.
|
||
127 | //----------------------------------------------------------------------
|
||
128 | |||
129 | extern ANNkd_leaf *KD_TRIVIAL; // trivial (empty) leaf node |
||
130 | |||
131 | //----------------------------------------------------------------------
|
||
132 | // kd-tree splitting node.
|
||
133 | // Splitting nodes contain a cutting dimension and a cutting value.
|
||
134 | // These indicate the axis-parellel plane which subdivide the
|
||
135 | // box for this node. The extent of the bounding box along the
|
||
136 | // cutting dimension is maintained (this is used to speed up point
|
||
137 | // to box distance calculations) [we do not store the entire bounding
|
||
138 | // box since this may be wasteful of space in high dimensions].
|
||
139 | // We also store pointers to the 2 children.
|
||
140 | //----------------------------------------------------------------------
|
||
141 | |||
142 | class ANNkd_split : public ANNkd_node // splitting node of a kd-tree
|
||
143 | { |
||
144 | int cut_dim; // dim orthogonal to cutting plane |
||
145 | ANNcoord cut_val; // location of cutting plane
|
||
146 | ANNcoord cd_bnds[2]; // lower and upper bounds of |
||
147 | // rectangle along cut_dim
|
||
148 | ANNkd_ptr child[2]; // left and right children |
||
149 | public:
|
||
150 | ANNkd_split( // constructor
|
||
151 | int cd, // cutting dimension |
||
152 | ANNcoord cv, // cutting value
|
||
153 | ANNcoord lv, ANNcoord hv, // low and high values
|
||
154 | ANNkd_ptr lc=NULL, ANNkd_ptr hc=NULL) // children |
||
155 | { |
||
156 | cut_dim = cd; // cutting dimension
|
||
157 | cut_val = cv; // cutting value
|
||
158 | cd_bnds[ANN_LO] = lv; // lower bound for rectangle
|
||
159 | cd_bnds[ANN_HI] = hv; // upper bound for rectangle
|
||
160 | child[ANN_LO] = lc; // left child
|
||
161 | child[ANN_HI] = hc; // right child
|
||
162 | } |
||
163 | |||
164 | ~ANNkd_split() // destructor
|
||
165 | { |
||
166 | if (child[ANN_LO]!= NULL && child[ANN_LO]!= KD_TRIVIAL) |
||
167 | delete child[ANN_LO]; |
||
168 | if (child[ANN_HI]!= NULL && child[ANN_HI]!= KD_TRIVIAL) |
||
169 | delete child[ANN_HI]; |
||
170 | } |
||
171 | |||
172 | virtual void getStats( // get tree statistics |
||
173 | int dim, // dimension of space |
||
174 | ANNkdStats &st, // statistics
|
||
175 | ANNorthRect &bnd_box); // bounding box
|
||
176 | virtual void print(int level, ostream &out);// print node |
||
177 | virtual void dump(ostream &out); // dump node |
||
178 | |||
179 | virtual void ann_search(ANNdist); // standard search |
||
180 | virtual void ann_pri_search(ANNdist); // priority search |
||
181 | virtual void ann_FR_search(ANNdist); // fixed-radius search |
||
182 | }; |
||
183 | |||
184 | //----------------------------------------------------------------------
|
||
185 | // External entry points
|
||
186 | //----------------------------------------------------------------------
|
||
187 | |||
188 | ANNkd_ptr rkd_tree( // recursive construction of kd-tree
|
||
189 | ANNpointArray pa, // point array (unaltered)
|
||
190 | ANNidxArray pidx, // point indices to store in subtree
|
||
191 | int n, // number of points |
||
192 | int dim, // dimension of space |
||
193 | int bsp, // bucket space |
||
194 | ANNorthRect &bnd_box, // bounding box for current node
|
||
195 | ANNkd_splitter splitter); // splitting routine
|
||
196 | |||
197 | #endif |