root / rgbdslam / gicp / ann_1.1.1 / include / ANN / ANN.h @ 9240aaa3
History | View | Annotate | Download (33.9 KB)
1 |
//----------------------------------------------------------------------
|
---|---|
2 |
// File: ANN.h
|
3 |
// Programmer: Sunil Arya and David Mount
|
4 |
// Last modified: 05/03/05 (Release 1.1)
|
5 |
// Description: Basic include file for approximate nearest
|
6 |
// neighbor searching.
|
7 |
//----------------------------------------------------------------------
|
8 |
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
|
9 |
// David Mount. All Rights Reserved.
|
10 |
//
|
11 |
// This software and related documentation is part of the Approximate
|
12 |
// Nearest Neighbor Library (ANN). This software is provided under
|
13 |
// the provisions of the Lesser GNU Public License (LGPL). See the
|
14 |
// file ../ReadMe.txt for further information.
|
15 |
//
|
16 |
// The University of Maryland (U.M.) and the authors make no
|
17 |
// representations about the suitability or fitness of this software for
|
18 |
// any purpose. It is provided "as is" without express or implied
|
19 |
// warranty.
|
20 |
//----------------------------------------------------------------------
|
21 |
// History:
|
22 |
// Revision 0.1 03/04/98
|
23 |
// Initial release
|
24 |
// Revision 1.0 04/01/05
|
25 |
// Added copyright and revision information
|
26 |
// Added ANNcoordPrec for coordinate precision.
|
27 |
// Added methods theDim, nPoints, maxPoints, thePoints to ANNpointSet.
|
28 |
// Cleaned up C++ structure for modern compilers
|
29 |
// Revision 1.1 05/03/05
|
30 |
// Added fixed-radius k-NN searching
|
31 |
//----------------------------------------------------------------------
|
32 |
|
33 |
//----------------------------------------------------------------------
|
34 |
// ANN - approximate nearest neighbor searching
|
35 |
// ANN is a library for approximate nearest neighbor searching,
|
36 |
// based on the use of standard and priority search in kd-trees
|
37 |
// and balanced box-decomposition (bbd) trees. Here are some
|
38 |
// references to the main algorithmic techniques used here:
|
39 |
//
|
40 |
// kd-trees:
|
41 |
// Friedman, Bentley, and Finkel, ``An algorithm for finding
|
42 |
// best matches in logarithmic expected time,'' ACM
|
43 |
// Transactions on Mathematical Software, 3(3):209-226, 1977.
|
44 |
//
|
45 |
// Priority search in kd-trees:
|
46 |
// Arya and Mount, ``Algorithms for fast vector quantization,''
|
47 |
// Proc. of DCC '93: Data Compression Conference, eds. J. A.
|
48 |
// Storer and M. Cohn, IEEE Press, 1993, 381-390.
|
49 |
//
|
50 |
// Approximate nearest neighbor search and bbd-trees:
|
51 |
// Arya, Mount, Netanyahu, Silverman, and Wu, ``An optimal
|
52 |
// algorithm for approximate nearest neighbor searching,''
|
53 |
// 5th Ann. ACM-SIAM Symposium on Discrete Algorithms,
|
54 |
// 1994, 573-582.
|
55 |
//----------------------------------------------------------------------
|
56 |
|
57 |
#ifndef ANN_H
|
58 |
#define ANN_H
|
59 |
|
60 |
#ifdef WIN32
|
61 |
//----------------------------------------------------------------------
|
62 |
// For Microsoft Visual C++, externally accessible symbols must be
|
63 |
// explicitly indicated with DLL_API, which is somewhat like "extern."
|
64 |
//
|
65 |
// The following ifdef block is the standard way of creating macros
|
66 |
// which make exporting from a DLL simpler. All files within this DLL
|
67 |
// are compiled with the DLL_EXPORTS preprocessor symbol defined on the
|
68 |
// command line. In contrast, projects that use (or import) the DLL
|
69 |
// objects do not define the DLL_EXPORTS symbol. This way any other
|
70 |
// project whose source files include this file see DLL_API functions as
|
71 |
// being imported from a DLL, wheras this DLL sees symbols defined with
|
72 |
// this macro as being exported.
|
73 |
//----------------------------------------------------------------------
|
74 |
#ifdef DLL_EXPORTS
|
75 |
#define DLL_API __declspec(dllexport)
|
76 |
#else
|
77 |
#define DLL_API __declspec(dllimport)
|
78 |
#endif
|
79 |
//----------------------------------------------------------------------
|
80 |
// DLL_API is ignored for all other systems
|
81 |
//----------------------------------------------------------------------
|
82 |
#else
|
83 |
#define DLL_API
|
84 |
#endif
|
85 |
|
86 |
//----------------------------------------------------------------------
|
87 |
// basic includes
|
88 |
//----------------------------------------------------------------------
|
89 |
|
90 |
#include <cstdlib> // exit(int) |
91 |
#include <cmath> // math includes |
92 |
#include <iostream> // I/O streams |
93 |
|
94 |
//----------------------------------------------------------------------
|
95 |
// Limits
|
96 |
// There are a number of places where we use the maximum double value as
|
97 |
// default initializers (and others may be used, depending on the
|
98 |
// data/distance representation). These can usually be found in limits.h
|
99 |
// (as LONG_MAX, INT_MAX) or in float.h (as DBL_MAX, FLT_MAX).
|
100 |
//
|
101 |
// Not all systems have these files. If you are using such a system,
|
102 |
// you should set the preprocessor symbol ANN_NO_LIMITS_H when
|
103 |
// compiling, and modify the statements below to generate the
|
104 |
// appropriate value. For practical purposes, this does not need to be
|
105 |
// the maximum double value. It is sufficient that it be at least as
|
106 |
// large than the maximum squared distance between between any two
|
107 |
// points.
|
108 |
//----------------------------------------------------------------------
|
109 |
#ifdef ANN_NO_LIMITS_H // limits.h unavailable |
110 |
#include <cvalues> // replacement for limits.h |
111 |
const double ANN_DBL_MAX = MAXDOUBLE; // insert maximum double |
112 |
#else
|
113 |
#include <climits> |
114 |
#include <cfloat> |
115 |
const double ANN_DBL_MAX = DBL_MAX; |
116 |
#endif
|
117 |
|
118 |
#define ANNversion "1.1.1" // ANN version and information |
119 |
#define ANNversionCmt "" |
120 |
#define ANNcopyright "David M. Mount and Sunil Arya" |
121 |
#define ANNlatestRev "Aug 4, 2006" |
122 |
|
123 |
//----------------------------------------------------------------------
|
124 |
// ANNbool
|
125 |
// This is a simple boolean type. Although ANSI C++ is supposed
|
126 |
// to support the type bool, some compilers do not have it.
|
127 |
//----------------------------------------------------------------------
|
128 |
|
129 |
enum ANNbool {ANNfalse = 0, ANNtrue = 1}; // ANN boolean type (non ANSI C++) |
130 |
|
131 |
//----------------------------------------------------------------------
|
132 |
// ANNcoord, ANNdist
|
133 |
// ANNcoord and ANNdist are the types used for representing
|
134 |
// point coordinates and distances. They can be modified by the
|
135 |
// user, with some care. It is assumed that they are both numeric
|
136 |
// types, and that ANNdist is generally of an equal or higher type
|
137 |
// from ANNcoord. A variable of type ANNdist should be large
|
138 |
// enough to store the sum of squared components of a variable
|
139 |
// of type ANNcoord for the number of dimensions needed in the
|
140 |
// application. For example, the following combinations are
|
141 |
// legal:
|
142 |
//
|
143 |
// ANNcoord ANNdist
|
144 |
// --------- -------------------------------
|
145 |
// short short, int, long, float, double
|
146 |
// int int, long, float, double
|
147 |
// long long, float, double
|
148 |
// float float, double
|
149 |
// double double
|
150 |
//
|
151 |
// It is the user's responsibility to make sure that overflow does
|
152 |
// not occur in distance calculation.
|
153 |
//----------------------------------------------------------------------
|
154 |
|
155 |
typedef double ANNcoord; // coordinate data type |
156 |
typedef double ANNdist; // distance data type |
157 |
|
158 |
//----------------------------------------------------------------------
|
159 |
// ANNidx
|
160 |
// ANNidx is a point index. When the data structure is built, the
|
161 |
// points are given as an array. Nearest neighbor results are
|
162 |
// returned as an integer index into this array. To make it
|
163 |
// clearer when this is happening, we define the integer type
|
164 |
// ANNidx. Indexing starts from 0.
|
165 |
//
|
166 |
// For fixed-radius near neighbor searching, it is possible that
|
167 |
// there are not k nearest neighbors within the search radius. To
|
168 |
// indicate this, the algorithm returns ANN_NULL_IDX as its result.
|
169 |
// It should be distinguishable from any valid array index.
|
170 |
//----------------------------------------------------------------------
|
171 |
|
172 |
typedef int ANNidx; // point index |
173 |
const ANNidx ANN_NULL_IDX = -1; // a NULL point index |
174 |
|
175 |
//----------------------------------------------------------------------
|
176 |
// Infinite distance:
|
177 |
// The code assumes that there is an "infinite distance" which it
|
178 |
// uses to initialize distances before performing nearest neighbor
|
179 |
// searches. It should be as larger or larger than any legitimate
|
180 |
// nearest neighbor distance.
|
181 |
//
|
182 |
// On most systems, these should be found in the standard include
|
183 |
// file <limits.h> or possibly <float.h>. If you do not have these
|
184 |
// file, some suggested values are listed below, assuming 64-bit
|
185 |
// long, 32-bit int and 16-bit short.
|
186 |
//
|
187 |
// ANNdist ANN_DIST_INF Values (see <limits.h> or <float.h>)
|
188 |
// ------- ------------ ------------------------------------
|
189 |
// double DBL_MAX 1.79769313486231570e+308
|
190 |
// float FLT_MAX 3.40282346638528860e+38
|
191 |
// long LONG_MAX 0x7fffffffffffffff
|
192 |
// int INT_MAX 0x7fffffff
|
193 |
// short SHRT_MAX 0x7fff
|
194 |
//----------------------------------------------------------------------
|
195 |
|
196 |
const ANNdist ANN_DIST_INF = ANN_DBL_MAX;
|
197 |
|
198 |
//----------------------------------------------------------------------
|
199 |
// Significant digits for tree dumps:
|
200 |
// When floating point coordinates are used, the routine that dumps
|
201 |
// a tree needs to know roughly how many significant digits there
|
202 |
// are in a ANNcoord, so it can output points to full precision.
|
203 |
// This is defined to be ANNcoordPrec. On most systems these
|
204 |
// values can be found in the standard include files <limits.h> or
|
205 |
// <float.h>. For integer types, the value is essentially ignored.
|
206 |
//
|
207 |
// ANNcoord ANNcoordPrec Values (see <limits.h> or <float.h>)
|
208 |
// -------- ------------ ------------------------------------
|
209 |
// double DBL_DIG 15
|
210 |
// float FLT_DIG 6
|
211 |
// long doesn't matter 19
|
212 |
// int doesn't matter 10
|
213 |
// short doesn't matter 5
|
214 |
//----------------------------------------------------------------------
|
215 |
|
216 |
#ifdef DBL_DIG // number of sig. bits in ANNcoord |
217 |
const int ANNcoordPrec = DBL_DIG; |
218 |
#else
|
219 |
const int ANNcoordPrec = 15; // default precision |
220 |
#endif
|
221 |
|
222 |
//----------------------------------------------------------------------
|
223 |
// Self match?
|
224 |
// In some applications, the nearest neighbor of a point is not
|
225 |
// allowed to be the point itself. This occurs, for example, when
|
226 |
// computing all nearest neighbors in a set. By setting the
|
227 |
// parameter ANN_ALLOW_SELF_MATCH to ANNfalse, the nearest neighbor
|
228 |
// is the closest point whose distance from the query point is
|
229 |
// strictly positive.
|
230 |
//----------------------------------------------------------------------
|
231 |
|
232 |
const ANNbool ANN_ALLOW_SELF_MATCH = ANNtrue;
|
233 |
|
234 |
//----------------------------------------------------------------------
|
235 |
// Norms and metrics:
|
236 |
// ANN supports any Minkowski norm for defining distance. In
|
237 |
// particular, for any p >= 1, the L_p Minkowski norm defines the
|
238 |
// length of a d-vector (v0, v1, ..., v(d-1)) to be
|
239 |
//
|
240 |
// (|v0|^p + |v1|^p + ... + |v(d-1)|^p)^(1/p),
|
241 |
//
|
242 |
// (where ^ denotes exponentiation, and |.| denotes absolute
|
243 |
// value). The distance between two points is defined to be the
|
244 |
// norm of the vector joining them. Some common distance metrics
|
245 |
// include
|
246 |
//
|
247 |
// Euclidean metric p = 2
|
248 |
// Manhattan metric p = 1
|
249 |
// Max metric p = infinity
|
250 |
//
|
251 |
// In the case of the max metric, the norm is computed by taking
|
252 |
// the maxima of the absolute values of the components. ANN is
|
253 |
// highly "coordinate-based" and does not support general distances
|
254 |
// functions (e.g. those obeying just the triangle inequality). It
|
255 |
// also does not support distance functions based on
|
256 |
// inner-products.
|
257 |
//
|
258 |
// For the purpose of computing nearest neighbors, it is not
|
259 |
// necessary to compute the final power (1/p). Thus the only
|
260 |
// component that is used by the program is |v(i)|^p.
|
261 |
//
|
262 |
// ANN parameterizes the distance computation through the following
|
263 |
// macros. (Macros are used rather than procedures for
|
264 |
// efficiency.) Recall that the distance between two points is
|
265 |
// given by the length of the vector joining them, and the length
|
266 |
// or norm of a vector v is given by formula:
|
267 |
//
|
268 |
// |v| = ROOT(POW(v0) # POW(v1) # ... # POW(v(d-1)))
|
269 |
//
|
270 |
// where ROOT, POW are unary functions and # is an associative and
|
271 |
// commutative binary operator mapping the following types:
|
272 |
//
|
273 |
// ** POW: ANNcoord --> ANNdist
|
274 |
// ** #: ANNdist x ANNdist --> ANNdist
|
275 |
// ** ROOT: ANNdist (>0) --> double
|
276 |
//
|
277 |
// For early termination in distance calculation (partial distance
|
278 |
// calculation) we assume that POW and # together are monotonically
|
279 |
// increasing on sequences of arguments, meaning that for all
|
280 |
// v0..vk and y:
|
281 |
//
|
282 |
// POW(v0) #...# POW(vk) <= (POW(v0) #...# POW(vk)) # POW(y).
|
283 |
//
|
284 |
// Incremental Distance Calculation:
|
285 |
// The program uses an optimized method of computing distances for
|
286 |
// kd-trees and bd-trees, called incremental distance calculation.
|
287 |
// It is used when distances are to be updated when only a single
|
288 |
// coordinate of a point has been changed. In order to use this,
|
289 |
// we assume that there is an incremental update function DIFF(x,y)
|
290 |
// for #, such that if:
|
291 |
//
|
292 |
// s = x0 # ... # xi # ... # xk
|
293 |
//
|
294 |
// then if s' is equal to s but with xi replaced by y, that is,
|
295 |
//
|
296 |
// s' = x0 # ... # y # ... # xk
|
297 |
//
|
298 |
// then the length of s' can be computed by:
|
299 |
//
|
300 |
// |s'| = |s| # DIFF(xi,y).
|
301 |
//
|
302 |
// Thus, if # is + then DIFF(xi,y) is (yi-x). For the L_infinity
|
303 |
// norm we make use of the fact that in the program this function
|
304 |
// is only invoked when y > xi, and hence DIFF(xi,y)=y.
|
305 |
//
|
306 |
// Finally, for approximate nearest neighbor queries we assume
|
307 |
// that POW and ROOT are related such that
|
308 |
//
|
309 |
// v*ROOT(x) = ROOT(POW(v)*x)
|
310 |
//
|
311 |
// Here are the values for the various Minkowski norms:
|
312 |
//
|
313 |
// L_p: p even: p odd:
|
314 |
// ------------------------- ------------------------
|
315 |
// POW(v) = v^p POW(v) = |v|^p
|
316 |
// ROOT(x) = x^(1/p) ROOT(x) = x^(1/p)
|
317 |
// # = + # = +
|
318 |
// DIFF(x,y) = y - x DIFF(x,y) = y - x
|
319 |
//
|
320 |
// L_inf:
|
321 |
// POW(v) = |v|
|
322 |
// ROOT(x) = x
|
323 |
// # = max
|
324 |
// DIFF(x,y) = y
|
325 |
//
|
326 |
// By default the Euclidean norm is assumed. To change the norm,
|
327 |
// uncomment the appropriate set of macros below.
|
328 |
//----------------------------------------------------------------------
|
329 |
|
330 |
//----------------------------------------------------------------------
|
331 |
// Use the following for the Euclidean norm
|
332 |
//----------------------------------------------------------------------
|
333 |
#define ANN_POW(v) ((v)*(v))
|
334 |
#define ANN_ROOT(x) sqrt(x)
|
335 |
#define ANN_SUM(x,y) ((x) + (y))
|
336 |
#define ANN_DIFF(x,y) ((y) - (x))
|
337 |
|
338 |
//----------------------------------------------------------------------
|
339 |
// Use the following for the L_1 (Manhattan) norm
|
340 |
//----------------------------------------------------------------------
|
341 |
// #define ANN_POW(v) fabs(v)
|
342 |
// #define ANN_ROOT(x) (x)
|
343 |
// #define ANN_SUM(x,y) ((x) + (y))
|
344 |
// #define ANN_DIFF(x,y) ((y) - (x))
|
345 |
|
346 |
//----------------------------------------------------------------------
|
347 |
// Use the following for a general L_p norm
|
348 |
//----------------------------------------------------------------------
|
349 |
// #define ANN_POW(v) pow(fabs(v),p)
|
350 |
// #define ANN_ROOT(x) pow(fabs(x),1/p)
|
351 |
// #define ANN_SUM(x,y) ((x) + (y))
|
352 |
// #define ANN_DIFF(x,y) ((y) - (x))
|
353 |
|
354 |
//----------------------------------------------------------------------
|
355 |
// Use the following for the L_infinity (Max) norm
|
356 |
//----------------------------------------------------------------------
|
357 |
// #define ANN_POW(v) fabs(v)
|
358 |
// #define ANN_ROOT(x) (x)
|
359 |
// #define ANN_SUM(x,y) ((x) > (y) ? (x) : (y))
|
360 |
// #define ANN_DIFF(x,y) (y)
|
361 |
|
362 |
//----------------------------------------------------------------------
|
363 |
// Array types
|
364 |
// The following array types are of basic interest. A point is
|
365 |
// just a dimensionless array of coordinates, a point array is a
|
366 |
// dimensionless array of points. A distance array is a
|
367 |
// dimensionless array of distances and an index array is a
|
368 |
// dimensionless array of point indices. The latter two are used
|
369 |
// when returning the results of k-nearest neighbor queries.
|
370 |
//----------------------------------------------------------------------
|
371 |
|
372 |
typedef ANNcoord* ANNpoint; // a point |
373 |
typedef ANNpoint* ANNpointArray; // an array of points |
374 |
typedef ANNdist* ANNdistArray; // an array of distances |
375 |
typedef ANNidx* ANNidxArray; // an array of point indices |
376 |
|
377 |
//----------------------------------------------------------------------
|
378 |
// Basic point and array utilities:
|
379 |
// The following procedures are useful supplements to ANN's nearest
|
380 |
// neighbor capabilities.
|
381 |
//
|
382 |
// annDist():
|
383 |
// Computes the (squared) distance between a pair of points.
|
384 |
// Note that this routine is not used internally by ANN for
|
385 |
// computing distance calculations. For reasons of efficiency
|
386 |
// this is done using incremental distance calculation. Thus,
|
387 |
// this routine cannot be modified as a method of changing the
|
388 |
// metric.
|
389 |
//
|
390 |
// Because points (somewhat like strings in C) are stored as
|
391 |
// pointers. Consequently, creating and destroying copies of
|
392 |
// points may require storage allocation. These procedures do
|
393 |
// this.
|
394 |
//
|
395 |
// annAllocPt() and annDeallocPt():
|
396 |
// Allocate a deallocate storage for a single point, and
|
397 |
// return a pointer to it. The argument to AllocPt() is
|
398 |
// used to initialize all components.
|
399 |
//
|
400 |
// annAllocPts() and annDeallocPts():
|
401 |
// Allocate and deallocate an array of points as well a
|
402 |
// place to store their coordinates, and initializes the
|
403 |
// points to point to their respective coordinates. It
|
404 |
// allocates point storage in a contiguous block large
|
405 |
// enough to store all the points. It performs no
|
406 |
// initialization.
|
407 |
//
|
408 |
// annCopyPt():
|
409 |
// Creates a copy of a given point, allocating space for
|
410 |
// the new point. It returns a pointer to the newly
|
411 |
// allocated copy.
|
412 |
//----------------------------------------------------------------------
|
413 |
|
414 |
DLL_API ANNdist annDist( |
415 |
int dim, // dimension of space |
416 |
ANNpoint p, // points
|
417 |
ANNpoint q); |
418 |
|
419 |
DLL_API ANNpoint annAllocPt( |
420 |
int dim, // dimension |
421 |
ANNcoord c = 0); // coordinate value (all equal) |
422 |
|
423 |
DLL_API ANNpointArray annAllocPts( |
424 |
int n, // number of points |
425 |
int dim); // dimension |
426 |
|
427 |
DLL_API void annDeallocPt(
|
428 |
ANNpoint &p); // deallocate 1 point
|
429 |
|
430 |
DLL_API void annDeallocPts(
|
431 |
ANNpointArray &pa); // point array
|
432 |
|
433 |
DLL_API ANNpoint annCopyPt( |
434 |
int dim, // dimension |
435 |
ANNpoint source); // point to copy
|
436 |
|
437 |
//----------------------------------------------------------------------
|
438 |
//Overall structure: ANN supports a number of different data structures
|
439 |
//for approximate and exact nearest neighbor searching. These are:
|
440 |
//
|
441 |
// ANNbruteForce A simple brute-force search structure.
|
442 |
// ANNkd_tree A kd-tree tree search structure. ANNbd_tree
|
443 |
// A bd-tree tree search structure (a kd-tree with shrink
|
444 |
// capabilities).
|
445 |
//
|
446 |
// At a minimum, each of these data structures support k-nearest
|
447 |
// neighbor queries. The nearest neighbor query, annkSearch,
|
448 |
// returns an integer identifier and the distance to the nearest
|
449 |
// neighbor(s) and annRangeSearch returns the nearest points that
|
450 |
// lie within a given query ball.
|
451 |
//
|
452 |
// Each structure is built by invoking the appropriate constructor
|
453 |
// and passing it (at a minimum) the array of points, the total
|
454 |
// number of points and the dimension of the space. Each structure
|
455 |
// is also assumed to support a destructor and member functions
|
456 |
// that return basic information about the point set.
|
457 |
//
|
458 |
// Note that the array of points is not copied by the data
|
459 |
// structure (for reasons of space efficiency), and it is assumed
|
460 |
// to be constant throughout the lifetime of the search structure.
|
461 |
//
|
462 |
// The search algorithm, annkSearch, is given the query point (q),
|
463 |
// and the desired number of nearest neighbors to report (k), and
|
464 |
// the error bound (eps) (whose default value is 0, implying exact
|
465 |
// nearest neighbors). It returns two arrays which are assumed to
|
466 |
// contain at least k elements: one (nn_idx) contains the indices
|
467 |
// (within the point array) of the nearest neighbors and the other
|
468 |
// (dd) contains the squared distances to these nearest neighbors.
|
469 |
//
|
470 |
// The search algorithm, annkFRSearch, is a fixed-radius kNN
|
471 |
// search. In addition to a query point, it is given a (squared)
|
472 |
// radius bound. (This is done for consistency, because the search
|
473 |
// returns distances as squared quantities.) It does two things.
|
474 |
// First, it computes the k nearest neighbors within the radius
|
475 |
// bound, and second, it returns the total number of points lying
|
476 |
// within the radius bound. It is permitted to set k = 0, in which
|
477 |
// case it effectively answers a range counting query. If the
|
478 |
// error bound epsilon is positive, then the search is approximate
|
479 |
// in the sense that it is free to ignore any point that lies
|
480 |
// outside a ball of radius r/(1+epsilon), where r is the given
|
481 |
// (unsquared) radius bound.
|
482 |
//
|
483 |
// The generic object from which all the search structures are
|
484 |
// dervied is given below. It is a virtual object, and is useless
|
485 |
// by itself.
|
486 |
//----------------------------------------------------------------------
|
487 |
|
488 |
class DLL_API ANNpointSet { |
489 |
public:
|
490 |
virtual ~ANNpointSet() {} // virtual distructor
|
491 |
|
492 |
virtual void annkSearch( // approx k near neighbor search |
493 |
ANNpoint q, // query point
|
494 |
int k, // number of near neighbors to return |
495 |
ANNidxArray nn_idx, // nearest neighbor array (modified)
|
496 |
ANNdistArray dd, // dist to near neighbors (modified)
|
497 |
double eps=0.0 // error bound |
498 |
) = 0; // pure virtual (defined elsewhere) |
499 |
|
500 |
virtual int annkFRSearch( // approx fixed-radius kNN search |
501 |
ANNpoint q, // query point
|
502 |
ANNdist sqRad, // squared radius
|
503 |
int k = 0, // number of near neighbors to return |
504 |
ANNidxArray nn_idx = NULL, // nearest neighbor array (modified) |
505 |
ANNdistArray dd = NULL, // dist to near neighbors (modified) |
506 |
double eps=0.0 // error bound |
507 |
) = 0; // pure virtual (defined elsewhere) |
508 |
|
509 |
virtual int theDim() = 0; // return dimension of space |
510 |
virtual int nPoints() = 0; // return number of points |
511 |
// return pointer to points
|
512 |
virtual ANNpointArray thePoints() = 0;
|
513 |
}; |
514 |
|
515 |
//----------------------------------------------------------------------
|
516 |
// Brute-force nearest neighbor search:
|
517 |
// The brute-force search structure is very simple but inefficient.
|
518 |
// It has been provided primarily for the sake of comparison with
|
519 |
// and validation of the more complex search structures.
|
520 |
//
|
521 |
// Query processing is the same as described above, but the value
|
522 |
// of epsilon is ignored, since all distance calculations are
|
523 |
// performed exactly.
|
524 |
//
|
525 |
// WARNING: This data structure is very slow, and should not be
|
526 |
// used unless the number of points is very small.
|
527 |
//
|
528 |
// Internal information:
|
529 |
// ---------------------
|
530 |
// This data structure bascially consists of the array of points
|
531 |
// (each a pointer to an array of coordinates). The search is
|
532 |
// performed by a simple linear scan of all the points.
|
533 |
//----------------------------------------------------------------------
|
534 |
|
535 |
class DLL_API ANNbruteForce: public ANNpointSet { |
536 |
int dim; // dimension |
537 |
int n_pts; // number of points |
538 |
ANNpointArray pts; // point array
|
539 |
public:
|
540 |
ANNbruteForce( // constructor from point array
|
541 |
ANNpointArray pa, // point array
|
542 |
int n, // number of points |
543 |
int dd); // dimension |
544 |
|
545 |
~ANNbruteForce(); // destructor
|
546 |
|
547 |
void annkSearch( // approx k near neighbor search |
548 |
ANNpoint q, // query point
|
549 |
int k, // number of near neighbors to return |
550 |
ANNidxArray nn_idx, // nearest neighbor array (modified)
|
551 |
ANNdistArray dd, // dist to near neighbors (modified)
|
552 |
double eps=0.0); // error bound |
553 |
|
554 |
int annkFRSearch( // approx fixed-radius kNN search |
555 |
ANNpoint q, // query point
|
556 |
ANNdist sqRad, // squared radius
|
557 |
int k = 0, // number of near neighbors to return |
558 |
ANNidxArray nn_idx = NULL, // nearest neighbor array (modified) |
559 |
ANNdistArray dd = NULL, // dist to near neighbors (modified) |
560 |
double eps=0.0); // error bound |
561 |
|
562 |
int theDim() // return dimension of space |
563 |
{ return dim; }
|
564 |
|
565 |
int nPoints() // return number of points |
566 |
{ return n_pts; }
|
567 |
|
568 |
ANNpointArray thePoints() // return pointer to points
|
569 |
{ return pts; }
|
570 |
}; |
571 |
|
572 |
//----------------------------------------------------------------------
|
573 |
// kd- and bd-tree splitting and shrinking rules
|
574 |
// kd-trees supports a collection of different splitting rules.
|
575 |
// In addition to the standard kd-tree splitting rule proposed
|
576 |
// by Friedman, Bentley, and Finkel, we have introduced a
|
577 |
// number of other splitting rules, which seem to perform
|
578 |
// as well or better (for the distributions we have tested).
|
579 |
//
|
580 |
// The splitting methods given below allow the user to tailor
|
581 |
// the data structure to the particular data set. They are
|
582 |
// are described in greater details in the kd_split.cc source
|
583 |
// file. The method ANN_KD_SUGGEST is the method chosen (rather
|
584 |
// subjectively) by the implementors as the one giving the
|
585 |
// fastest performance, and is the default splitting method.
|
586 |
//
|
587 |
// As with splitting rules, there are a number of different
|
588 |
// shrinking rules. The shrinking rule ANN_BD_NONE does no
|
589 |
// shrinking (and hence produces a kd-tree tree). The rule
|
590 |
// ANN_BD_SUGGEST uses the implementors favorite rule.
|
591 |
//----------------------------------------------------------------------
|
592 |
|
593 |
enum ANNsplitRule {
|
594 |
ANN_KD_STD = 0, // the optimized kd-splitting rule |
595 |
ANN_KD_MIDPT = 1, // midpoint split |
596 |
ANN_KD_FAIR = 2, // fair split |
597 |
ANN_KD_SL_MIDPT = 3, // sliding midpoint splitting method |
598 |
ANN_KD_SL_FAIR = 4, // sliding fair split method |
599 |
ANN_KD_SUGGEST = 5}; // the authors' suggestion for best |
600 |
const int ANN_N_SPLIT_RULES = 6; // number of split rules |
601 |
|
602 |
enum ANNshrinkRule {
|
603 |
ANN_BD_NONE = 0, // no shrinking at all (just kd-tree) |
604 |
ANN_BD_SIMPLE = 1, // simple splitting |
605 |
ANN_BD_CENTROID = 2, // centroid splitting |
606 |
ANN_BD_SUGGEST = 3}; // the authors' suggested choice |
607 |
const int ANN_N_SHRINK_RULES = 4; // number of shrink rules |
608 |
|
609 |
//----------------------------------------------------------------------
|
610 |
// kd-tree:
|
611 |
// The main search data structure supported by ANN is a kd-tree.
|
612 |
// The main constructor is given a set of points and a choice of
|
613 |
// splitting method to use in building the tree.
|
614 |
//
|
615 |
// Construction:
|
616 |
// -------------
|
617 |
// The constructor is given the point array, number of points,
|
618 |
// dimension, bucket size (default = 1), and the splitting rule
|
619 |
// (default = ANN_KD_SUGGEST). The point array is not copied, and
|
620 |
// is assumed to be kept constant throughout the lifetime of the
|
621 |
// search structure. There is also a "load" constructor that
|
622 |
// builds a tree from a file description that was created by the
|
623 |
// Dump operation.
|
624 |
//
|
625 |
// Search:
|
626 |
// -------
|
627 |
// There are two search methods:
|
628 |
//
|
629 |
// Standard search (annkSearch()):
|
630 |
// Searches nodes in tree-traversal order, always visiting
|
631 |
// the closer child first.
|
632 |
// Priority search (annkPriSearch()):
|
633 |
// Searches nodes in order of increasing distance of the
|
634 |
// associated cell from the query point. For many
|
635 |
// distributions the standard search seems to work just
|
636 |
// fine, but priority search is safer for worst-case
|
637 |
// performance.
|
638 |
//
|
639 |
// Printing:
|
640 |
// ---------
|
641 |
// There are two methods provided for printing the tree. Print()
|
642 |
// is used to produce a "human-readable" display of the tree, with
|
643 |
// indenation, which is handy for debugging. Dump() produces a
|
644 |
// format that is suitable reading by another program. There is a
|
645 |
// "load" constructor, which constructs a tree which is assumed to
|
646 |
// have been saved by the Dump() procedure.
|
647 |
//
|
648 |
// Performance and Structure Statistics:
|
649 |
// -------------------------------------
|
650 |
// The procedure getStats() collects statistics information on the
|
651 |
// tree (its size, height, etc.) See ANNperf.h for information on
|
652 |
// the stats structure it returns.
|
653 |
//
|
654 |
// Internal information:
|
655 |
// ---------------------
|
656 |
// The data structure consists of three major chunks of storage.
|
657 |
// The first (implicit) storage are the points themselves (pts),
|
658 |
// which have been provided by the users as an argument to the
|
659 |
// constructor, or are allocated dynamically if the tree is built
|
660 |
// using the load constructor). These should not be changed during
|
661 |
// the lifetime of the search structure. It is the user's
|
662 |
// responsibility to delete these after the tree is destroyed.
|
663 |
//
|
664 |
// The second is the tree itself (which is dynamically allocated in
|
665 |
// the constructor) and is given as a pointer to its root node
|
666 |
// (root). These nodes are automatically deallocated when the tree
|
667 |
// is deleted. See the file src/kd_tree.h for further information
|
668 |
// on the structure of the tree nodes.
|
669 |
//
|
670 |
// Each leaf of the tree does not contain a pointer directly to a
|
671 |
// point, but rather contains a pointer to a "bucket", which is an
|
672 |
// array consisting of point indices. The third major chunk of
|
673 |
// storage is an array (pidx), which is a large array in which all
|
674 |
// these bucket subarrays reside. (The reason for storing them
|
675 |
// separately is the buckets are typically small, but of varying
|
676 |
// sizes. This was done to avoid fragmentation.) This array is
|
677 |
// also deallocated when the tree is deleted.
|
678 |
//
|
679 |
// In addition to this, the tree consists of a number of other
|
680 |
// pieces of information which are used in searching and for
|
681 |
// subsequent tree operations. These consist of the following:
|
682 |
//
|
683 |
// dim Dimension of space
|
684 |
// n_pts Number of points currently in the tree
|
685 |
// n_max Maximum number of points that are allowed
|
686 |
// in the tree
|
687 |
// bkt_size Maximum bucket size (no. of points per leaf)
|
688 |
// bnd_box_lo Bounding box low point
|
689 |
// bnd_box_hi Bounding box high point
|
690 |
// splitRule Splitting method used
|
691 |
//
|
692 |
//----------------------------------------------------------------------
|
693 |
|
694 |
//----------------------------------------------------------------------
|
695 |
// Some types and objects used by kd-tree functions
|
696 |
// See src/kd_tree.h and src/kd_tree.cpp for definitions
|
697 |
//----------------------------------------------------------------------
|
698 |
class ANNkdStats; // stats on kd-tree
|
699 |
class ANNkd_node; // generic node in a kd-tree
|
700 |
typedef ANNkd_node* ANNkd_ptr; // pointer to a kd-tree node |
701 |
|
702 |
class DLL_API ANNkd_tree: public ANNpointSet { |
703 |
protected:
|
704 |
int dim; // dimension of space |
705 |
int n_pts; // number of points in tree |
706 |
int bkt_size; // bucket size |
707 |
ANNpointArray pts; // the points
|
708 |
ANNidxArray pidx; // point indices (to pts array)
|
709 |
ANNkd_ptr root; // root of kd-tree
|
710 |
ANNpoint bnd_box_lo; // bounding box low point
|
711 |
ANNpoint bnd_box_hi; // bounding box high point
|
712 |
|
713 |
void SkeletonTree( // construct skeleton tree |
714 |
int n, // number of points |
715 |
int dd, // dimension |
716 |
int bs, // bucket size |
717 |
ANNpointArray pa = NULL, // point array (optional) |
718 |
ANNidxArray pi = NULL); // point indices (optional) |
719 |
|
720 |
public:
|
721 |
ANNkd_tree( // build skeleton tree
|
722 |
int n = 0, // number of points |
723 |
int dd = 0, // dimension |
724 |
int bs = 1); // bucket size |
725 |
|
726 |
ANNkd_tree( // build from point array
|
727 |
ANNpointArray pa, // point array
|
728 |
int n, // number of points |
729 |
int dd, // dimension |
730 |
int bs = 1, // bucket size |
731 |
ANNsplitRule split = ANN_KD_SUGGEST); // splitting method
|
732 |
|
733 |
ANNkd_tree( // build from dump file
|
734 |
std::istream& in); // input stream for dump file
|
735 |
|
736 |
~ANNkd_tree(); // tree destructor
|
737 |
|
738 |
void annkSearch( // approx k near neighbor search |
739 |
ANNpoint q, // query point
|
740 |
int k, // number of near neighbors to return |
741 |
ANNidxArray nn_idx, // nearest neighbor array (modified)
|
742 |
ANNdistArray dd, // dist to near neighbors (modified)
|
743 |
double eps=0.0); // error bound |
744 |
|
745 |
void annkPriSearch( // priority k near neighbor search |
746 |
ANNpoint q, // query point
|
747 |
int k, // number of near neighbors to return |
748 |
ANNidxArray nn_idx, // nearest neighbor array (modified)
|
749 |
ANNdistArray dd, // dist to near neighbors (modified)
|
750 |
double eps=0.0); // error bound |
751 |
|
752 |
int annkFRSearch( // approx fixed-radius kNN search |
753 |
ANNpoint q, // the query point
|
754 |
ANNdist sqRad, // squared radius of query ball
|
755 |
int k, // number of neighbors to return |
756 |
ANNidxArray nn_idx = NULL, // nearest neighbor array (modified) |
757 |
ANNdistArray dd = NULL, // dist to near neighbors (modified) |
758 |
double eps=0.0); // error bound |
759 |
|
760 |
int theDim() // return dimension of space |
761 |
{ return dim; }
|
762 |
|
763 |
int nPoints() // return number of points |
764 |
{ return n_pts; }
|
765 |
|
766 |
ANNpointArray thePoints() // return pointer to points
|
767 |
{ return pts; }
|
768 |
|
769 |
virtual void Print( // print the tree (for debugging) |
770 |
ANNbool with_pts, // print points as well?
|
771 |
std::ostream& out); // output stream
|
772 |
|
773 |
virtual void Dump( // dump entire tree |
774 |
ANNbool with_pts, // print points as well?
|
775 |
std::ostream& out); // output stream
|
776 |
|
777 |
virtual void getStats( // compute tree statistics |
778 |
ANNkdStats& st); // the statistics (modified)
|
779 |
}; |
780 |
|
781 |
//----------------------------------------------------------------------
|
782 |
// Box decomposition tree (bd-tree)
|
783 |
// The bd-tree is inherited from a kd-tree. The main difference
|
784 |
// in the bd-tree and the kd-tree is a new type of internal node
|
785 |
// called a shrinking node (in the kd-tree there is only one type
|
786 |
// of internal node, a splitting node). The shrinking node
|
787 |
// makes it possible to generate balanced trees in which the
|
788 |
// cells have bounded aspect ratio, by allowing the decomposition
|
789 |
// to zoom in on regions of dense point concentration. Although
|
790 |
// this is a nice idea in theory, few point distributions are so
|
791 |
// densely clustered that this is really needed.
|
792 |
//----------------------------------------------------------------------
|
793 |
|
794 |
class DLL_API ANNbd_tree: public ANNkd_tree { |
795 |
public:
|
796 |
ANNbd_tree( // build skeleton tree
|
797 |
int n, // number of points |
798 |
int dd, // dimension |
799 |
int bs = 1) // bucket size |
800 |
: ANNkd_tree(n, dd, bs) {} // build base kd-tree
|
801 |
|
802 |
ANNbd_tree( // build from point array
|
803 |
ANNpointArray pa, // point array
|
804 |
int n, // number of points |
805 |
int dd, // dimension |
806 |
int bs = 1, // bucket size |
807 |
ANNsplitRule split = ANN_KD_SUGGEST, // splitting rule
|
808 |
ANNshrinkRule shrink = ANN_BD_SUGGEST); // shrinking rule
|
809 |
|
810 |
ANNbd_tree( // build from dump file
|
811 |
std::istream& in); // input stream for dump file
|
812 |
}; |
813 |
|
814 |
//----------------------------------------------------------------------
|
815 |
// Other functions
|
816 |
// annMaxPtsVisit Sets a limit on the maximum number of points
|
817 |
// to visit in the search.
|
818 |
// annClose Can be called when all use of ANN is finished.
|
819 |
// It clears up a minor memory leak.
|
820 |
//----------------------------------------------------------------------
|
821 |
|
822 |
DLL_API void annMaxPtsVisit( // max. pts to visit in search |
823 |
int maxPts); // the limit |
824 |
|
825 |
DLL_API void annClose(); // called to end use of ANN |
826 |
|
827 |
#endif
|