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


Generated on OURCE_DATE_EPOCH for elastix by doxygen 1.8.13 elastix logo