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