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


Generated on 1641078589 for elastix by doxygen 1.9.1 elastix logo