Main MRPT website > C++ reference
MRPT logo

ANN.h

Go to the documentation of this file.
00001 //----------------------------------------------------------------------
00002 // File:                        ANN.h
00003 // Programmer:          Sunil Arya and David Mount
00004 // Last modified:       05/03/05 (Release 1.1)
00005 // Description:         Basic include file for approximate nearest
00006 //                                      neighbor searching.
00007 //----------------------------------------------------------------------
00008 // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
00009 // David Mount.  All Rights Reserved.
00010 //
00011 // This software and related documentation is part of the Approximate
00012 // Nearest Neighbor Library (ANN).  This software is provided under
00013 // the provisions of the Lesser GNU Public License (LGPL).  See the
00014 // file ../ReadMe.txt for further information.
00015 //
00016 // The University of Maryland (U.M.) and the authors make no
00017 // representations about the suitability or fitness of this software for
00018 // any purpose.  It is provided "as is" without express or implied
00019 // warranty.
00020 //----------------------------------------------------------------------
00021 // History:
00022 //      Revision 0.1  03/04/98
00023 //              Initial release
00024 //      Revision 1.0  04/01/05
00025 //              Added copyright and revision information
00026 //              Added ANNcoordPrec for coordinate precision.
00027 //              Added methods theDim, nPoints, maxPoints, thePoints to ANNpointSet.
00028 //              Cleaned up C++ structure for modern compilers
00029 //      Revision 1.1  05/03/05
00030 //              Added fixed-radius k-NN searching
00031 //----------------------------------------------------------------------
00032 
00033 //----------------------------------------------------------------------
00034 // ANN - approximate nearest neighbor searching
00035 //      ANN is a library for approximate nearest neighbor searching,
00036 //      based on the use of standard and priority search in kd-trees
00037 //      and balanced box-decomposition (bbd) trees. Here are some
00038 //      references to the main algorithmic techniques used here:
00039 //
00040 //              kd-trees:
00041 //                      Friedman, Bentley, and Finkel, ``An algorithm for finding
00042 //                              best matches in logarithmic expected time,'' ACM
00043 //                              Transactions on Mathematical Software, 3(3):209-226, 1977.
00044 //
00045 //              Priority search in kd-trees:
00046 //                      Arya and Mount, ``Algorithms for fast vector quantization,''
00047 //                              Proc. of DCC '93: Data Compression Conference, eds. J. A.
00048 //                              Storer and M. Cohn, IEEE Press, 1993, 381-390.
00049 //
00050 //              Approximate nearest neighbor search and bbd-trees:
00051 //                      Arya, Mount, Netanyahu, Silverman, and Wu, ``An optimal
00052 //                              algorithm for approximate nearest neighbor searching,''
00053 //                              5th Ann. ACM-SIAM Symposium on Discrete Algorithms,
00054 //                              1994, 573-582.
00055 //----------------------------------------------------------------------
00056 
00057 #ifndef ANN_H
00058 #define ANN_H
00059 
00060 // JLBC: Use DLL defines as those in the library ANN is embedded into: mrpt-base
00061 #include <mrpt/base/link_pragmas.h>
00062 #define DLL_API  BASE_IMPEXP
00063 
00064 //----------------------------------------------------------------------
00065 //  basic includes
00066 //----------------------------------------------------------------------
00067 
00068 #include <cstdlib>                      // I/O streams
00069 
00070 #include "math.h"                       // math includes
00071 #include <cmath>                        // math includes
00072 #include <iostream>                     // I/O streams
00073 #include <iostream>                     // I/O streams
00074 
00075 #include <cstring>                      // JLBC: For strcmp
00076 
00077 //----------------------------------------------------------------------
00078 // Limits
00079 // There are a number of places where we use the maximum double value as
00080 // default initializers (and others may be used, depending on the
00081 // data/distance representation). These can usually be found in limits.h
00082 // (as LONG_MAX, INT_MAX) or in float.h (as DBL_MAX, FLT_MAX).
00083 //
00084 // Not all systems have these files.  If you are using such a system,
00085 // you should set the preprocessor symbol ANN_NO_LIMITS_H when
00086 // compiling, and modify the statements below to generate the
00087 // appropriate value. For practical purposes, this does not need to be
00088 // the maximum double value. It is sufficient that it be at least as
00089 // large than the maximum squared distance between between any two
00090 // points.
00091 //----------------------------------------------------------------------
00092 #ifdef ANN_NO_LIMITS_H                                  // limits.h unavailable
00093   #include <cvalues>                                    // replacement for limits.h
00094   const double ANN_DBL_MAX = MAXDOUBLE; // insert maximum double
00095 #else
00096   #include <climits>
00097   #include <cfloat>
00098   const double ANN_DBL_MAX = DBL_MAX;
00099 #endif
00100 
00101 #define ANNversion              "1.1.1"                 // ANN version and information
00102 #define ANNversionCmt   ""
00103 #define ANNcopyright    "David M. Mount and Sunil Arya"
00104 #define ANNlatestRev    "Aug 4, 2006"
00105 
00106 //----------------------------------------------------------------------
00107 //      ANNbool
00108 //      This is a simple boolean type. Although ANSI C++ is supposed
00109 //      to support the type bool, some compilers do not have it.
00110 //----------------------------------------------------------------------
00111 
00112 enum ANNbool {ANNfalse = 0, ANNtrue = 1}; // ANN boolean type (non ANSI C++)
00113 
00114 //----------------------------------------------------------------------
00115 //      ANNcoord, ANNdist
00116 //              ANNcoord and ANNdist are the types used for representing
00117 //              point coordinates and distances.  They can be modified by the
00118 //              user, with some care.  It is assumed that they are both numeric
00119 //              types, and that ANNdist is generally of an equal or higher type
00120 //              from ANNcoord.  A variable of type ANNdist should be large
00121 //              enough to store the sum of squared components of a variable
00122 //              of type ANNcoord for the number of dimensions needed in the
00123 //              application.  For example, the following combinations are
00124 //              legal:
00125 //
00126 //              ANNcoord                ANNdist
00127 //              ---------               -------------------------------
00128 //              short                   short, int, long, float, double
00129 //              int                             int, long, float, double
00130 //              long                    long, float, double
00131 //              float                   float, double
00132 //              double                  double
00133 //
00134 //              It is the user's responsibility to make sure that overflow does
00135 //              not occur in distance calculation.
00136 //----------------------------------------------------------------------
00137 
00138 typedef float   ANNcoord;                               // coordinate data type
00139 typedef float   ANNdist;                                // distance data type
00140 
00141 //----------------------------------------------------------------------
00142 //      ANNidx
00143 //              ANNidx is a point index.  When the data structure is built, the
00144 //              points are given as an array.  Nearest neighbor results are
00145 //              returned as an integer index into this array.  To make it
00146 //              clearer when this is happening, we define the integer type
00147 //              ANNidx.  Indexing starts from 0.
00148 //
00149 //              For fixed-radius near neighbor searching, it is possible that
00150 //              there are not k nearest neighbors within the search radius.  To
00151 //              indicate this, the algorithm returns ANN_NULL_IDX as its result.
00152 //              It should be distinguishable from any valid array index.
00153 //----------------------------------------------------------------------
00154 
00155 typedef int             ANNidx;                                 // point index
00156 const ANNidx    ANN_NULL_IDX = -1;              // a NULL point index
00157 
00158 //----------------------------------------------------------------------
00159 //      Infinite distance:
00160 //              The code assumes that there is an "infinite distance" which it
00161 //              uses to initialize distances before performing nearest neighbor
00162 //              searches.  It should be as larger or larger than any legitimate
00163 //              nearest neighbor distance.
00164 //
00165 //              On most systems, these should be found in the standard include
00166 //              file <limits.h> or possibly <float.h>.  If you do not have these
00167 //              file, some suggested values are listed below, assuming 64-bit
00168 //              long, 32-bit int and 16-bit short.
00169 //
00170 //              ANNdist ANN_DIST_INF    Values (see <limits.h> or <float.h>)
00171 //              ------- ------------    ------------------------------------
00172 //              double  DBL_MAX                 1.79769313486231570e+308
00173 //              float   FLT_MAX                 3.40282346638528860e+38
00174 //              long    LONG_MAX                0x7fffffffffffffff
00175 //              int             INT_MAX                 0x7fffffff
00176 //              short   SHRT_MAX                0x7fff
00177 //----------------------------------------------------------------------
00178 
00179 const ANNdist   ANN_DIST_INF = FLT_MAX; //ANN_DBL_MAX;
00180 
00181 //----------------------------------------------------------------------
00182 //      Significant digits for tree dumps:
00183 //              When floating point coordinates are used, the routine that dumps
00184 //              a tree needs to know roughly how many significant digits there
00185 //              are in a ANNcoord, so it can output points to full precision.
00186 //              This is defined to be ANNcoordPrec.  On most systems these
00187 //              values can be found in the standard include files <limits.h> or
00188 //              <float.h>.  For integer types, the value is essentially ignored.
00189 //
00190 //              ANNcoord ANNcoordPrec   Values (see <limits.h> or <float.h>)
00191 //              -------- ------------   ------------------------------------
00192 //              double   DBL_DIG                15
00193 //              float    FLT_DIG                6
00194 //              long     doesn't matter 19
00195 //              int              doesn't matter 10
00196 //              short    doesn't matter 5
00197 //----------------------------------------------------------------------
00198 
00199 #ifdef DBL_DIG                                                  // number of sig. bits in ANNcoord
00200         const int        ANNcoordPrec   = DBL_DIG;
00201 #else
00202         const int        ANNcoordPrec   = 15;   // default precision
00203 #endif
00204 
00205 //----------------------------------------------------------------------
00206 // Self match?
00207 //      In some applications, the nearest neighbor of a point is not
00208 //      allowed to be the point itself. This occurs, for example, when
00209 //      computing all nearest neighbors in a set.  By setting the
00210 //      parameter ANN_ALLOW_SELF_MATCH to ANNfalse, the nearest neighbor
00211 //      is the closest point whose distance from the query point is
00212 //      strictly positive.
00213 //----------------------------------------------------------------------
00214 
00215 const ANNbool   ANN_ALLOW_SELF_MATCH    = ANNtrue;
00216 
00217 //----------------------------------------------------------------------
00218 //      Norms and metrics:
00219 //              ANN supports any Minkowski norm for defining distance.  In
00220 //              particular, for any p >= 1, the L_p Minkowski norm defines the
00221 //              length of a d-vector (v0, v1, ..., v(d-1)) to be
00222 //
00223 //                              (|v0|^p + |v1|^p + ... + |v(d-1)|^p)^(1/p),
00224 //
00225 //              (where ^ denotes exponentiation, and |.| denotes absolute
00226 //              value).  The distance between two points is defined to be the
00227 //              norm of the vector joining them.  Some common distance metrics
00228 //              include
00229 //
00230 //                              Euclidean metric                p = 2
00231 //                              Manhattan metric                p = 1
00232 //                              Max metric                              p = infinity
00233 //
00234 //              In the case of the max metric, the norm is computed by taking
00235 //              the maxima of the absolute values of the components.  ANN is
00236 //              highly "coordinate-based" and does not support general distances
00237 //              functions (e.g. those obeying just the triangle inequality).  It
00238 //              also does not support distance functions based on
00239 //              inner-products.
00240 //
00241 //              For the purpose of computing nearest neighbors, it is not
00242 //              necessary to compute the final power (1/p).  Thus the only
00243 //              component that is used by the program is |v(i)|^p.
00244 //
00245 //              ANN parameterizes the distance computation through the following
00246 //              macros.  (Macros are used rather than procedures for
00247 //              efficiency.) Recall that the distance between two points is
00248 //              given by the length of the vector joining them, and the length
00249 //              or norm of a vector v is given by formula:
00250 //
00251 //                              |v| = ROOT(POW(v0) # POW(v1) # ... # POW(v(d-1)))
00252 //
00253 //              where ROOT, POW are unary functions and # is an associative and
00254 //              commutative binary operator mapping the following types:
00255 //
00256 //                      **      POW:    ANNcoord                                --> ANNdist
00257 //                      **      #:              ANNdist x ANNdist               --> ANNdist
00258 //                      **      ROOT:   ANNdist (>0)                    --> double
00259 //
00260 //              For early termination in distance calculation (partial distance
00261 //              calculation) we assume that POW and # together are monotonically
00262 //              increasing on sequences of arguments, meaning that for all
00263 //              v0..vk and y:
00264 //
00265 //              POW(v0) #...# POW(vk) <= (POW(v0) #...# POW(vk)) # POW(y).
00266 //
00267 //      Incremental Distance Calculation:
00268 //              The program uses an optimized method of computing distances for
00269 //              kd-trees and bd-trees, called incremental distance calculation.
00270 //              It is used when distances are to be updated when only a single
00271 //              coordinate of a point has been changed.  In order to use this,
00272 //              we assume that there is an incremental update function DIFF(x,y)
00273 //              for #, such that if:
00274 //
00275 //                                      s = x0 # ... # xi # ... # xk
00276 //
00277 //              then if s' is equal to s but with xi replaced by y, that is,
00278 //
00279 //                                      s' = x0 # ... # y # ... # xk
00280 //
00281 //              then the length of s' can be computed by:
00282 //
00283 //                                      |s'| = |s| # DIFF(xi,y).
00284 //
00285 //              Thus, if # is + then DIFF(xi,y) is (yi-x).  For the L_infinity
00286 //              norm we make use of the fact that in the program this function
00287 //              is only invoked when y > xi, and hence DIFF(xi,y)=y.
00288 //
00289 //              Finally, for approximate nearest neighbor queries we assume
00290 //              that POW and ROOT are related such that
00291 //
00292 //                                      v*ROOT(x) = ROOT(POW(v)*x)
00293 //
00294 //              Here are the values for the various Minkowski norms:
00295 //
00296 //              L_p:    p even:                                                 p odd:
00297 //                              -------------------------               ------------------------
00298 //                              POW(v)                  = v^p                   POW(v)                  = |v|^p
00299 //                              ROOT(x)                 = x^(1/p)               ROOT(x)                 = x^(1/p)
00300 //                              #                               = +                             #                               = +
00301 //                              DIFF(x,y)               = y - x                 DIFF(x,y)               = y - x
00302 //
00303 //              L_inf:
00304 //                              POW(v)                  = |v|
00305 //                              ROOT(x)                 = x
00306 //                              #                               = max
00307 //                              DIFF(x,y)               = y
00308 //
00309 //              By default the Euclidean norm is assumed.  To change the norm,
00310 //              uncomment the appropriate set of macros below.
00311 //----------------------------------------------------------------------
00312 
00313 //----------------------------------------------------------------------
00314 //      Use the following for the Euclidean norm
00315 //----------------------------------------------------------------------
00316 #define ANN_POW(v)                      ((v)*(v))
00317 #define ANN_ROOT(x)                     sqrt(x)
00318 #define ANN_SUM(x,y)            ((x) + (y))
00319 #define ANN_DIFF(x,y)           ((y) - (x))
00320 
00321 //----------------------------------------------------------------------
00322 //      Use the following for the L_1 (Manhattan) norm
00323 //----------------------------------------------------------------------
00324 // #define ANN_POW(v)           fabs(v)
00325 // #define ANN_ROOT(x)          (x)
00326 // #define ANN_SUM(x,y)         ((x) + (y))
00327 // #define ANN_DIFF(x,y)        ((y) - (x))
00328 
00329 //----------------------------------------------------------------------
00330 //      Use the following for a general L_p norm
00331 //----------------------------------------------------------------------
00332 // #define ANN_POW(v)           pow(fabs(v),p)
00333 // #define ANN_ROOT(x)          pow(fabs(x),1/p)
00334 // #define ANN_SUM(x,y)         ((x) + (y))
00335 // #define ANN_DIFF(x,y)        ((y) - (x))
00336 
00337 //----------------------------------------------------------------------
00338 //      Use the following for the L_infinity (Max) norm
00339 //----------------------------------------------------------------------
00340 // #define ANN_POW(v)           fabs(v)
00341 // #define ANN_ROOT(x)          (x)
00342 // #define ANN_SUM(x,y)         ((x) > (y) ? (x) : (y))
00343 // #define ANN_DIFF(x,y)        (y)
00344 
00345 //----------------------------------------------------------------------
00346 //      Array types
00347 //              The following array types are of basic interest.  A point is
00348 //              just a dimensionless array of coordinates, a point array is a
00349 //              dimensionless array of points.  A distance array is a
00350 //              dimensionless array of distances and an index array is a
00351 //              dimensionless array of point indices.  The latter two are used
00352 //              when returning the results of k-nearest neighbor queries.
00353 //----------------------------------------------------------------------
00354 
00355 typedef ANNcoord* ANNpoint;                     // a point
00356 typedef ANNpoint* ANNpointArray;        // an array of points
00357 typedef ANNdist*  ANNdistArray;         // an array of distances
00358 typedef ANNidx*   ANNidxArray;          // an array of point indices
00359 
00360 //----------------------------------------------------------------------
00361 //      Basic point and array utilities:
00362 //              The following procedures are useful supplements to ANN's nearest
00363 //              neighbor capabilities.
00364 //
00365 //              annDist():
00366 //                      Computes the (squared) distance between a pair of points.
00367 //                      Note that this routine is not used internally by ANN for
00368 //                      computing distance calculations.  For reasons of efficiency
00369 //                      this is done using incremental distance calculation.  Thus,
00370 //                      this routine cannot be modified as a method of changing the
00371 //                      metric.
00372 //
00373 //              Because points (somewhat like strings in C) are stored as
00374 //              pointers.  Consequently, creating and destroying copies of
00375 //              points may require storage allocation.  These procedures do
00376 //              this.
00377 //
00378 //              annAllocPt() and annDeallocPt():
00379 //                              Allocate a deallocate storage for a single point, and
00380 //                              return a pointer to it.  The argument to AllocPt() is
00381 //                              used to initialize all components.
00382 //
00383 //              annAllocPts() and annDeallocPts():
00384 //                              Allocate and deallocate an array of points as well a
00385 //                              place to store their coordinates, and initializes the
00386 //                              points to point to their respective coordinates.  It
00387 //                              allocates point storage in a contiguous block large
00388 //                              enough to store all the points.  It performs no
00389 //                              initialization.
00390 //
00391 //              annCopyPt():
00392 //                              Creates a copy of a given point, allocating space for
00393 //                              the new point.  It returns a pointer to the newly
00394 //                              allocated copy.
00395 //----------------------------------------------------------------------
00396 
00397 DLL_API ANNdist annDist(
00398         int                             dim,            // dimension of space
00399         ANNpoint                p,                      // points
00400         ANNpoint                q);
00401 
00402 DLL_API ANNpoint annAllocPt(
00403         int                             dim,            // dimension
00404         ANNcoord                c = 0);         // coordinate value (all equal)
00405 
00406 DLL_API ANNpointArray annAllocPts(
00407         int                             n,                      // number of points
00408         int                             dim);           // dimension
00409 
00410 DLL_API void annDeallocPt(
00411         ANNpoint                &p);            // deallocate 1 point
00412 
00413 DLL_API void annDeallocPts(
00414         ANNpointArray   &pa);           // point array
00415 
00416 DLL_API ANNpoint annCopyPt(
00417         int                             dim,            // dimension
00418         ANNpoint                source);        // point to copy
00419 
00420 //----------------------------------------------------------------------
00421 //Overall structure: ANN supports a number of different data structures
00422 //for approximate and exact nearest neighbor searching.  These are:
00423 //
00424 //              ANNbruteForce   A simple brute-force search structure.
00425 //              ANNkd_tree              A kd-tree tree search structure.  ANNbd_tree
00426 //              A bd-tree tree search structure (a kd-tree with shrink
00427 //              capabilities).
00428 //
00429 //              At a minimum, each of these data structures support k-nearest
00430 //              neighbor queries.  The nearest neighbor query, annkSearch,
00431 //              returns an integer identifier and the distance to the nearest
00432 //              neighbor(s) and annRangeSearch returns the nearest points that
00433 //              lie within a given query ball.
00434 //
00435 //              Each structure is built by invoking the appropriate constructor
00436 //              and passing it (at a minimum) the array of points, the total
00437 //              number of points and the dimension of the space.  Each structure
00438 //              is also assumed to support a destructor and member functions
00439 //              that return basic information about the point set.
00440 //
00441 //              Note that the array of points is not copied by the data
00442 //              structure (for reasons of space efficiency), and it is assumed
00443 //              to be constant throughout the lifetime of the search structure.
00444 //
00445 //              The search algorithm, annkSearch, is given the query point (q),
00446 //              and the desired number of nearest neighbors to report (k), and
00447 //              the error bound (eps) (whose default value is 0, implying exact
00448 //              nearest neighbors).  It returns two arrays which are assumed to
00449 //              contain at least k elements: one (nn_idx) contains the indices
00450 //              (within the point array) of the nearest neighbors and the other
00451 //              (dd) contains the squared distances to these nearest neighbors.
00452 //
00453 //              The search algorithm, annkFRSearch, is a fixed-radius kNN
00454 //              search.  In addition to a query point, it is given a (squared)
00455 //              radius bound.  (This is done for consistency, because the search
00456 //              returns distances as squared quantities.) It does two things.
00457 //              First, it computes the k nearest neighbors within the radius
00458 //              bound, and second, it returns the total number of points lying
00459 //              within the radius bound. It is permitted to set k = 0, in which
00460 //              case it effectively answers a range counting query.  If the
00461 //              error bound epsilon is positive, then the search is approximate
00462 //              in the sense that it is free to ignore any point that lies
00463 //              outside a ball of radius r/(1+epsilon), where r is the given
00464 //              (unsquared) radius bound.
00465 //
00466 //              The generic object from which all the search structures are
00467 //              dervied is given below.  It is a virtual object, and is useless
00468 //              by itself.
00469 //----------------------------------------------------------------------
00470 
00471 class DLL_API ANNpointSet {
00472 public:
00473         virtual ~ANNpointSet() {}                       // virtual distructor
00474 
00475         virtual void annkSearch(                        // approx k near neighbor search
00476                 ANNpoint                q,                              // query point
00477                 int                             k,                              // number of near neighbors to return
00478                 ANNidxArray             nn_idx,                 // nearest neighbor array (modified)
00479                 ANNdistArray    dd,                             // dist to near neighbors (modified)
00480                 double                  eps=0.0                 // error bound
00481                 ) = 0;                                                  // pure virtual (defined elsewhere)
00482 
00483         virtual int annkFRSearch(                       // approx fixed-radius kNN search
00484                 ANNpoint                q,                              // query point
00485                 ANNdist                 sqRad,                  // squared radius
00486                 int                             k = 0,                  // number of near neighbors to return
00487                 ANNidxArray             nn_idx = NULL,  // nearest neighbor array (modified)
00488                 ANNdistArray    dd = NULL,              // dist to near neighbors (modified)
00489                 double                  eps=0.0                 // error bound
00490                 ) = 0;                                                  // pure virtual (defined elsewhere)
00491 
00492         virtual int theDim() = 0;                       // return dimension of space
00493         virtual int nPoints() = 0;                      // return number of points
00494                                                                                 // return pointer to points
00495         virtual ANNpointArray thePoints() = 0;
00496 };
00497 
00498 //----------------------------------------------------------------------
00499 //      Brute-force nearest neighbor search:
00500 //              The brute-force search structure is very simple but inefficient.
00501 //              It has been provided primarily for the sake of comparison with
00502 //              and validation of the more complex search structures.
00503 //
00504 //              Query processing is the same as described above, but the value
00505 //              of epsilon is ignored, since all distance calculations are
00506 //              performed exactly.
00507 //
00508 //              WARNING: This data structure is very slow, and should not be
00509 //              used unless the number of points is very small.
00510 //
00511 //              Internal information:
00512 //              ---------------------
00513 //              This data structure bascially consists of the array of points
00514 //              (each a pointer to an array of coordinates).  The search is
00515 //              performed by a simple linear scan of all the points.
00516 //----------------------------------------------------------------------
00517 
00518 class DLL_API ANNbruteForce: public ANNpointSet {
00519         int                             dim;                            // dimension
00520         int                             n_pts;                          // number of points
00521         ANNpointArray   pts;                            // point array
00522 public:
00523         ANNbruteForce(                                          // constructor from point array
00524                 ANNpointArray   pa,                             // point array
00525                 int                             n,                              // number of points
00526                 int                             dd);                    // dimension
00527 
00528         ANNbruteForce(const ANNbruteForce &o);
00529         ANNbruteForce & operator =(const ANNbruteForce &o);
00530 
00531 
00532         ~ANNbruteForce();                                       // destructor
00533 
00534         void annkSearch(                                        // approx k near neighbor search
00535                 ANNpoint                q,                              // query point
00536                 int                             k,                              // number of near neighbors to return
00537                 ANNidxArray             nn_idx,                 // nearest neighbor array (modified)
00538                 ANNdistArray    dd,                             // dist to near neighbors (modified)
00539                 double                  eps=0.0);               // error bound
00540 
00541         int annkFRSearch(                                       // approx fixed-radius kNN search
00542                 ANNpoint                q,                              // query point
00543                 ANNdist                 sqRad,                  // squared radius
00544                 int                             k = 0,                  // number of near neighbors to return
00545                 ANNidxArray             nn_idx = NULL,  // nearest neighbor array (modified)
00546                 ANNdistArray    dd = NULL,              // dist to near neighbors (modified)
00547                 double                  eps=0.0);               // error bound
00548 
00549         int theDim()                                            // return dimension of space
00550                 { return dim; }
00551 
00552         int nPoints()                                           // return number of points
00553                 { return n_pts; }
00554 
00555         ANNpointArray thePoints()                       // return pointer to points
00556                 {  return pts;  }
00557 };
00558 
00559 //----------------------------------------------------------------------
00560 // kd- and bd-tree splitting and shrinking rules
00561 //              kd-trees supports a collection of different splitting rules.
00562 //              In addition to the standard kd-tree splitting rule proposed
00563 //              by Friedman, Bentley, and Finkel, we have introduced a
00564 //              number of other splitting rules, which seem to perform
00565 //              as well or better (for the distributions we have tested).
00566 //
00567 //              The splitting methods given below allow the user to tailor
00568 //              the data structure to the particular data set.  They are
00569 //              are described in greater details in the kd_split.cc source
00570 //              file.  The method ANN_KD_SUGGEST is the method chosen (rather
00571 //              subjectively) by the implementors as the one giving the
00572 //              fastest performance, and is the default splitting method.
00573 //
00574 //              As with splitting rules, there are a number of different
00575 //              shrinking rules.  The shrinking rule ANN_BD_NONE does no
00576 //              shrinking (and hence produces a kd-tree tree).  The rule
00577 //              ANN_BD_SUGGEST uses the implementors favorite rule.
00578 //----------------------------------------------------------------------
00579 
00580 enum ANNsplitRule {
00581                 ANN_KD_STD                              = 0,    // the optimized kd-splitting rule
00582                 ANN_KD_MIDPT                    = 1,    // midpoint split
00583                 ANN_KD_FAIR                             = 2,    // fair split
00584                 ANN_KD_SL_MIDPT                 = 3,    // sliding midpoint splitting method
00585                 ANN_KD_SL_FAIR                  = 4,    // sliding fair split method
00586                 ANN_KD_SUGGEST                  = 5};   // the authors' suggestion for best
00587 const int ANN_N_SPLIT_RULES             = 6;    // number of split rules
00588 
00589 enum ANNshrinkRule {
00590                 ANN_BD_NONE                             = 0,    // no shrinking at all (just kd-tree)
00591                 ANN_BD_SIMPLE                   = 1,    // simple splitting
00592                 ANN_BD_CENTROID                 = 2,    // centroid splitting
00593                 ANN_BD_SUGGEST                  = 3};   // the authors' suggested choice
00594 const int ANN_N_SHRINK_RULES    = 4;    // number of shrink rules
00595 
00596 //----------------------------------------------------------------------
00597 //      kd-tree:
00598 //              The main search data structure supported by ANN is a kd-tree.
00599 //              The main constructor is given a set of points and a choice of
00600 //              splitting method to use in building the tree.
00601 //
00602 //              Construction:
00603 //              -------------
00604 //              The constructor is given the point array, number of points,
00605 //              dimension, bucket size (default = 1), and the splitting rule
00606 //              (default = ANN_KD_SUGGEST).  The point array is not copied, and
00607 //              is assumed to be kept constant throughout the lifetime of the
00608 //              search structure.  There is also a "load" constructor that
00609 //              builds a tree from a file description that was created by the
00610 //              Dump operation.
00611 //
00612 //              Search:
00613 //              -------
00614 //              There are two search methods:
00615 //
00616 //                      Standard search (annkSearch()):
00617 //                              Searches nodes in tree-traversal order, always visiting
00618 //                              the closer child first.
00619 //                      Priority search (annkPriSearch()):
00620 //                              Searches nodes in order of increasing distance of the
00621 //                              associated cell from the query point.  For many
00622 //                              distributions the standard search seems to work just
00623 //                              fine, but priority search is safer for worst-case
00624 //                              performance.
00625 //
00626 //              Printing:
00627 //              ---------
00628 //              There are two methods provided for printing the tree.  Print()
00629 //              is used to produce a "human-readable" display of the tree, with
00630 //              indenation, which is handy for debugging.  Dump() produces a
00631 //              format that is suitable reading by another program.  There is a
00632 //              "load" constructor, which constructs a tree which is assumed to
00633 //              have been saved by the Dump() procedure.
00634 //
00635 //              Performance and Structure Statistics:
00636 //              -------------------------------------
00637 //              The procedure getStats() collects statistics information on the
00638 //              tree (its size, height, etc.)  See ANNperf.h for information on
00639 //              the stats structure it returns.
00640 //
00641 //              Internal information:
00642 //              ---------------------
00643 //              The data structure consists of three major chunks of storage.
00644 //              The first (implicit) storage are the points themselves (pts),
00645 //              which have been provided by the users as an argument to the
00646 //              constructor, or are allocated dynamically if the tree is built
00647 //              using the load constructor).  These should not be changed during
00648 //              the lifetime of the search structure.  It is the user's
00649 //              responsibility to delete these after the tree is destroyed.
00650 //
00651 //              The second is the tree itself (which is dynamically allocated in
00652 //              the constructor) and is given as a pointer to its root node
00653 //              (root).  These nodes are automatically deallocated when the tree
00654 //              is deleted.  See the file src/kd_tree.h for further information
00655 //              on the structure of the tree nodes.
00656 //
00657 //              Each leaf of the tree does not contain a pointer directly to a
00658 //              point, but rather contains a pointer to a "bucket", which is an
00659 //              array consisting of point indices.  The third major chunk of
00660 //              storage is an array (pidx), which is a large array in which all
00661 //              these bucket subarrays reside.  (The reason for storing them
00662 //              separately is the buckets are typically small, but of varying
00663 //              sizes.  This was done to avoid fragmentation.)  This array is
00664 //              also deallocated when the tree is deleted.
00665 //
00666 //              In addition to this, the tree consists of a number of other
00667 //              pieces of information which are used in searching and for
00668 //              subsequent tree operations.  These consist of the following:
00669 //
00670 //              dim                                             Dimension of space
00671 //              n_pts                                   Number of points currently in the tree
00672 //              n_max                                   Maximum number of points that are allowed
00673 //                                                              in the tree
00674 //              bkt_size                                Maximum bucket size (no. of points per leaf)
00675 //              bnd_box_lo                              Bounding box low point
00676 //              bnd_box_hi                              Bounding box high point
00677 //              splitRule                               Splitting method used
00678 //
00679 //----------------------------------------------------------------------
00680 
00681 //----------------------------------------------------------------------
00682 // Some types and objects used by kd-tree functions
00683 // See src/kd_tree.h and src/kd_tree.cpp for definitions
00684 //----------------------------------------------------------------------
00685 class ANNkdStats;                               // stats on kd-tree
00686 class ANNkd_node;                               // generic node in a kd-tree
00687 typedef ANNkd_node*     ANNkd_ptr;      // pointer to a kd-tree node
00688 
00689 class DLL_API ANNkd_tree: public ANNpointSet {
00690 protected:
00691         int                             dim;                            // dimension of space
00692         int                             n_pts;                          // number of points in tree
00693         int                             bkt_size;                       // bucket size
00694         ANNpointArray   pts;                            // the points
00695         ANNidxArray             pidx;                           // point indices (to pts array)
00696         ANNkd_ptr               root;                           // root of kd-tree
00697         ANNpoint                bnd_box_lo;                     // bounding box low point
00698         ANNpoint                bnd_box_hi;                     // bounding box high point
00699 
00700         void SkeletonTree(                                      // construct skeleton tree
00701                 int                             n,                              // number of points
00702                 int                             dd,                             // dimension
00703                 int                             bs,                             // bucket size
00704                 ANNpointArray pa = NULL,                // point array (optional)
00705                 ANNidxArray pi = NULL);                 // point indices (optional)
00706 
00707 public:
00708         ANNkd_tree(                                                     // build skeleton tree
00709                 int                             n = 0,                  // number of points
00710                 int                             dd = 0,                 // dimension
00711                 int                             bs = 1);                // bucket size
00712 
00713         ANNkd_tree(                                                     // build from point array
00714                 ANNpointArray   pa,                             // point array
00715                 int                             n,                              // number of points
00716                 int                             dd,                             // dimension
00717                 int                             bs = 1,                 // bucket size
00718                 ANNsplitRule    split = ANN_KD_SUGGEST);        // splitting method
00719 
00720         ANNkd_tree(                                                     // build from dump file
00721                 std::istream&   in);                    // input stream for dump file
00722 
00723         ANNkd_tree(const ANNkd_tree&o);
00724         ANNkd_tree & operator = (const ANNkd_tree&o);
00725 
00726         ~ANNkd_tree();                                          // tree destructor
00727 
00728         void annkSearch(                                        // approx k near neighbor search
00729                 ANNpoint                q,                              // query point
00730                 int                             k,                              // number of near neighbors to return
00731                 ANNidxArray             nn_idx,                 // nearest neighbor array (modified)
00732                 ANNdistArray    dd,                             // dist to near neighbors (modified)
00733                 double                  eps=0.0);               // error bound
00734 
00735         void annkPriSearch(                             // priority k near neighbor search
00736                 ANNpoint                q,                              // query point
00737                 int                             k,                              // number of near neighbors to return
00738                 ANNidxArray             nn_idx,                 // nearest neighbor array (modified)
00739                 ANNdistArray    dd,                             // dist to near neighbors (modified)
00740                 double                  eps=0.0);               // error bound
00741 
00742         int annkFRSearch(                                       // approx fixed-radius kNN search
00743                 ANNpoint                q,                              // the query point
00744                 ANNdist                 sqRad,                  // squared radius of query ball
00745                 int                             k,                              // number of neighbors to return
00746                 ANNidxArray             nn_idx = NULL,  // nearest neighbor array (modified)
00747                 ANNdistArray    dd = NULL,              // dist to near neighbors (modified)
00748                 double                  eps=0.0);               // error bound
00749 
00750         int theDim()                                            // return dimension of space
00751                 { return dim; }
00752 
00753         int nPoints()                                           // return number of points
00754                 { return n_pts; }
00755 
00756         ANNpointArray thePoints()                       // return pointer to points
00757                 {  return pts;  }
00758 
00759         virtual void Print(                                     // print the tree (for debugging)
00760                 ANNbool                 with_pts,               // print points as well?
00761                 std::ostream&   out);                   // output stream
00762 
00763         virtual void Dump(                                      // dump entire tree
00764                 ANNbool                 with_pts,               // print points as well?
00765                 std::ostream&   out);                   // output stream
00766 
00767         virtual void getStats(                          // compute tree statistics
00768                 ANNkdStats&             st);                    // the statistics (modified)
00769 };
00770 
00771 //----------------------------------------------------------------------
00772 //      Box decomposition tree (bd-tree)
00773 //              The bd-tree is inherited from a kd-tree.  The main difference
00774 //              in the bd-tree and the kd-tree is a new type of internal node
00775 //              called a shrinking node (in the kd-tree there is only one type
00776 //              of internal node, a splitting node).  The shrinking node
00777 //              makes it possible to generate balanced trees in which the
00778 //              cells have bounded aspect ratio, by allowing the decomposition
00779 //              to zoom in on regions of dense point concentration.  Although
00780 //              this is a nice idea in theory, few point distributions are so
00781 //              densely clustered that this is really needed.
00782 //----------------------------------------------------------------------
00783 
00784 /*
00785 class DLL_API ANNbd_tree: public ANNkd_tree {
00786 public:
00787         ANNbd_tree(                                                     // build skeleton tree
00788                 int                             n,                              // number of points
00789                 int                             dd,                             // dimension
00790                 int                             bs = 1)                 // bucket size
00791                 : ANNkd_tree(n, dd, bs) {}              // build base kd-tree
00792 
00793         ANNbd_tree(                                                     // build from point array
00794                 ANNpointArray   pa,                             // point array
00795                 int                             n,                              // number of points
00796                 int                             dd,                             // dimension
00797                 int                             bs = 1,                 // bucket size
00798                 ANNsplitRule    split  = ANN_KD_SUGGEST,        // splitting rule
00799                 ANNshrinkRule   shrink = ANN_BD_SUGGEST);       // shrinking rule
00800 
00801         ANNbd_tree(                                                     // build from dump file
00802                 std::istream&   in);                    // input stream for dump file
00803 };
00804 */
00805 
00806 //----------------------------------------------------------------------
00807 //      Other functions
00808 //      annMaxPtsVisit          Sets a limit on the maximum number of points
00809 //                                              to visit in the search.
00810 //  annClose                    Can be called when all use of ANN is finished.
00811 //                                              It clears up a minor memory leak.
00812 //----------------------------------------------------------------------
00813 
00814 DLL_API void annMaxPtsVisit(    // max. pts to visit in search
00815         int                             maxPts);        // the limit
00816 
00817 DLL_API void annClose();                // called to end use of ANN
00818 
00819 #endif



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:16:28 UTC 2011