| ANN.h | | ANN.h | |
|---|
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // File: ANN.h | | // File: ANN.h | |
| // Programmer: Sunil Arya and David Mount | | // Programmer: Sunil Arya and David Mount | |
|
| // Last modified: 03/19/05 (Release 1.0) | | // Last modified: 05/03/05 (Release 1.1) | |
| // Description: Basic include file for approximate nearest | | // Description: Basic include file for approximate nearest | |
| // neighbor searching. | | // neighbor searching. | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and | | // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and | |
| // David Mount. All Rights Reserved. | | // David Mount. All Rights Reserved. | |
| // | | // | |
|
| // This software and related documentation is part of the | | // This software and related documentation is part of the Approximate | |
| // Approximate Nearest Neighbor Library (ANN). | | // Nearest Neighbor Library (ANN). This software is provided under | |
| // | | // the provisions of the Lesser GNU Public License (LGPL). See the | |
| // Permission to use, copy, and distribute this software and its | | // file ../ReadMe.txt for further information. | |
| // documentation is hereby granted free of charge, provided that | | | |
| // (1) it is not a component of a commercial product, and | | | |
| // (2) this notice appears in all copies of the software and | | | |
| // related documentation. | | | |
| // | | // | |
|
| // The University of Maryland (U.M.) and the authors make no representation | | // The University of Maryland (U.M.) and the authors make no | |
| s | | // representations about the suitability or fitness of this software for | |
| // about the suitability or fitness of this software for any purpose. It i | | // any purpose. It is provided "as is" without express or implied | |
| s | | // warranty. | |
| // provided "as is" without express or implied warranty. | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
|
| // History: | | // History: | |
| // Revision 0.1 03/04/98 | | // Revision 0.1 03/04/98 | |
| // Initial release | | // Initial release | |
| // Revision 1.0 04/01/05 | | // Revision 1.0 04/01/05 | |
| // Added copyright and revision information | | // Added copyright and revision information | |
| // Added ANNcoordPrec for coordinate precision. | | // Added ANNcoordPrec for coordinate precision. | |
| // Added methods theDim, nPoints, maxPoints, thePoints | | // Added methods theDim, nPoints, maxPoints, thePoints to ANNpo | |
| to ANNpointSet. | | intSet. | |
| // Cleaned up C++ structure for modern compilers | | // Cleaned up C++ structure for modern compilers | |
| | | // Revision 1.1 05/03/05 | |
| | | // Added fixed-radius k-NN searching | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // ANN - approximate nearest neighbor searching | | // ANN - approximate nearest neighbor searching | |
| // ANN is a library for approximate nearest neighbor searching, | | // ANN is a library for approximate nearest neighbor searching, | |
| // based on the use of standard and priority search in kd-trees | | // based on the use of standard and priority search in kd-trees | |
| // and balanced box-decomposition (bbd) trees. Here are some | | // and balanced box-decomposition (bbd) trees. Here are some | |
| // references to the main algorithmic techniques used here: | | // references to the main algorithmic techniques used here: | |
| // | | // | |
| // kd-trees: | | // kd-trees: | |
| | | | |
| skipping to change at line 118 | | skipping to change at line 117 | |
|---|
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| #ifdef ANN_NO_LIMITS_H // limits.h unavaila
ble | | #ifdef ANN_NO_LIMITS_H // limits.h unavaila
ble | |
| #include <cvalues> // replacement for l
imits.h | | #include <cvalues> // replacement for l
imits.h | |
| const double ANN_DBL_MAX = MAXDOUBLE; // insert maximum double | | const double ANN_DBL_MAX = MAXDOUBLE; // insert maximum double | |
| #else | | #else | |
| #include <climits> | | #include <climits> | |
| #include <cfloat> | | #include <cfloat> | |
| const double ANN_DBL_MAX = DBL_MAX; | | const double ANN_DBL_MAX = DBL_MAX; | |
| #endif | | #endif | |
| | | | |
|
| #define ANNversion "1.0" // ANN version and i
nformation | | #define ANNversion "1.1.1" // ANN version and i
nformation | |
| #define ANNversionCmt "" | | #define ANNversionCmt "" | |
| #define ANNcopyright "David M. Mount and Sunil Arya" | | #define ANNcopyright "David M. Mount and Sunil Arya" | |
|
| #define ANNlatestRev "Mar 1, 2005" | | #define ANNlatestRev "Aug 4, 2006" | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // ANNbool | | // ANNbool | |
| // This is a simple boolean type. Although ANSI C++ is supposed | | // This is a simple boolean type. Although ANSI C++ is supposed | |
| // to support the type bool, some compilers do not have it. | | // to support the type bool, some compilers do not have it. | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| enum ANNbool {ANNfalse = 0, ANNtrue = 1}; // ANN boolean type (non ANSI C++
) | | enum ANNbool {ANNfalse = 0, ANNtrue = 1}; // ANN boolean type (non ANSI C++
) | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| skipping to change at line 165 | | skipping to change at line 164 | |
|---|
| typedef double ANNcoord; // coordinate data t
ype | | typedef double ANNcoord; // coordinate data t
ype | |
| typedef double ANNdist; // distance data typ
e | | typedef double ANNdist; // distance data typ
e | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // ANNidx | | // ANNidx | |
| // ANNidx is a point index. When the data structure is built,
the | | // ANNidx is a point index. When the data structure is built,
the | |
| // points are given as an array. Nearest neighbor results are | | // points are given as an array. Nearest neighbor results are | |
| // returned as an integer index into this array. To make it | | // returned as an integer index into this array. To make it | |
| // clearer when this is happening, we define the integer type | | // clearer when this is happening, we define the integer type | |
| // ANNidx. Indexing starts from 0. | | // ANNidx. Indexing starts from 0. | |
|
| | | // | |
| | | // For fixed-radius near neighbor searching, it is possible tha | |
| | | t | |
| | | // there are not k nearest neighbors within the search radius. | |
| | | To | |
| | | // indicate this, the algorithm returns ANN_NULL_IDX as its res | |
| | | ult. | |
| | | // It should be distinguishable from any valid array index. | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| typedef int ANNidx; // point ind
ex | | typedef int ANNidx; // point ind
ex | |
|
| | | const ANNidx ANN_NULL_IDX = -1; // a NULL point index | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // Infinite distance: | | // Infinite distance: | |
| // The code assumes that there is an "infinite distance" which
it | | // The code assumes that there is an "infinite distance" which
it | |
| // uses to initialize distances before performing nearest neigh
bor | | // uses to initialize distances before performing nearest neigh
bor | |
| // searches. It should be as larger or larger than any legitim
ate | | // searches. It should be as larger or larger than any legitim
ate | |
| // nearest neighbor distance. | | // nearest neighbor distance. | |
| // | | // | |
| // On most systems, these should be found in the standard inclu
de | | // On most systems, these should be found in the standard inclu
de | |
| // file <limits.h> or possibly <float.h>. If you do not have t
hese | | // file <limits.h> or possibly <float.h>. If you do not have t
hese | |
| | | | |
| skipping to change at line 366 | | skipping to change at line 371 | |
|---|
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // Array types | | // Array types | |
| // The following array types are of basic interest. A point is | | // The following array types are of basic interest. A point is | |
| // just a dimensionless array of coordinates, a point array is
a | | // just a dimensionless array of coordinates, a point array is
a | |
| // dimensionless array of points. A distance array is a | | // dimensionless array of points. A distance array is a | |
| // dimensionless array of distances and an index array is a | | // dimensionless array of distances and an index array is a | |
| // dimensionless array of point indices. The latter two are us
ed | | // dimensionless array of point indices. The latter two are us
ed | |
| // when returning the results of k-nearest neighbor queries. | | // when returning the results of k-nearest neighbor queries. | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
|
| typedef ANNcoord *ANNpoint; // a point | | typedef ANNcoord* ANNpoint; // a point | |
| typedef ANNpoint *ANNpointArray; // an array of points | | typedef ANNpoint* ANNpointArray; // an array of points | |
| typedef ANNdist *ANNdistArray; // an array of distances | | typedef ANNdist* ANNdistArray; // an array of distances | |
| typedef ANNidx *ANNidxArray; // an array of point indices | | typedef ANNidx* ANNidxArray; // an array of point indices | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // Basic point and array utilities: | | // Basic point and array utilities: | |
| // The following procedures are useful supplements to ANN's nea
rest | | // The following procedures are useful supplements to ANN's nea
rest | |
| // neighbor capabilities. | | // neighbor capabilities. | |
| // | | // | |
| // annDist(): | | // annDist(): | |
| // Computes the (squared) distance between a pair of po
ints. | | // Computes the (squared) distance between a pair of po
ints. | |
| // Note that this routine is not used internally by ANN
for | | // Note that this routine is not used internally by ANN
for | |
| // computing distance calculations. For reasons of eff
iciency | | // computing distance calculations. For reasons of eff
iciency | |
| | | | |
| skipping to change at line 432 | | skipping to change at line 437 | |
|---|
| ANNpoint &p); // deallocate 1 point | | ANNpoint &p); // deallocate 1 point | |
| | | | |
| DLL_API void annDeallocPts( | | DLL_API void annDeallocPts( | |
| ANNpointArray &pa); // point array | | ANNpointArray &pa); // point array | |
| | | | |
| DLL_API ANNpoint annCopyPt( | | DLL_API ANNpoint annCopyPt( | |
| int dim, // dimension | | int dim, // dimension | |
| ANNpoint source); // point to copy | | ANNpoint source); // point to copy | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
|
| // Overall structure: | | //Overall structure: ANN supports a number of different data structures | |
| // ANN supports a number of different data structures for | | //for approximate and exact nearest neighbor searching. These are: | |
| // approximate and exact nearest neighbor searching. These are | | | |
| : | | | |
| // | | // | |
| // ANNbruteForce A simple brute-force search structure. | | // ANNbruteForce A simple brute-force search structure. | |
|
| // ANNkd_tree A kd-tree tree search structure. | | // ANNkd_tree A kd-tree tree search structure. AN | |
| // ANNbd_tree A bd-tree tree search structure (a k | | Nbd_tree | |
| d-tree | | // A bd-tree tree search structure (a kd-tree with shrink | |
| // with shrink capabilities). | | // capabilities). | |
| // | | // | |
| // At a minimum, each of these data structures support k-neares
t | | // At a minimum, each of these data structures support k-neares
t | |
|
| // neighbor queries. The nearest neighbor query (annkSearch) | | // neighbor queries. The nearest neighbor query, annkSearch, | |
| // returns an integer identifier and the distance to the neares
t | | // returns an integer identifier and the distance to the neares
t | |
|
| // neighbor(s). | | // neighbor(s) and annRangeSearch returns the nearest points th | |
| | | at | |
| | | // lie within a given query ball. | |
| // | | // | |
| // Each structure is built by invoking the appropriate construc
tor | | // Each structure is built by invoking the appropriate construc
tor | |
| // and passing it (at a minimum) the array of points, the total | | // and passing it (at a minimum) the array of points, the total | |
| // number of points and the dimension of the space. Each struc
ture | | // number of points and the dimension of the space. Each struc
ture | |
| // is also assumed to support a destructor and member functions | | // is also assumed to support a destructor and member functions | |
| // that return basic information about the point set. | | // that return basic information about the point set. | |
| // | | // | |
| // Note that the array of points is not copied by the data | | // Note that the array of points is not copied by the data | |
| // structure (for reasons of space efficiency), and it is assum
ed | | // structure (for reasons of space efficiency), and it is assum
ed | |
| // to be constant throughout the lifetime of the search structu
re. | | // to be constant throughout the lifetime of the search structu
re. | |
| // | | // | |
| // The search algorithm, annkSearch, is given the query point (
q), | | // The search algorithm, annkSearch, is given the query point (
q), | |
| // and the desired number of nearest neighbors to report (k), a
nd | | // and the desired number of nearest neighbors to report (k), a
nd | |
| // the error bound (eps) (whose default value is 0, implying ex
act | | // the error bound (eps) (whose default value is 0, implying ex
act | |
| // nearest neighbors). It returns two arrays which are assumed
to | | // nearest neighbors). It returns two arrays which are assumed
to | |
| // contain at least k elements: one (nn_idx) contains the indic
es | | // contain at least k elements: one (nn_idx) contains the indic
es | |
| // (within the point array) of the nearest neighbors and the ot
her | | // (within the point array) of the nearest neighbors and the ot
her | |
| // (dd) contains the squared distances to these nearest neighbo
rs. | | // (dd) contains the squared distances to these nearest neighbo
rs. | |
| // | | // | |
|
| | | // The search algorithm, annkFRSearch, is a fixed-radius kNN | |
| | | // search. In addition to a query point, it is given a (square | |
| | | d) | |
| | | // radius bound. (This is done for consistency, because the se | |
| | | arch | |
| | | // returns distances as squared quantities.) It does two things | |
| | | . | |
| | | // First, it computes the k nearest neighbors within the radius | |
| | | // bound, and second, it returns the total number of points lyi | |
| | | ng | |
| | | // within the radius bound. It is permitted to set k = 0, in wh | |
| | | ich | |
| | | // case it effectively answers a range counting query. If the | |
| | | // error bound epsilon is positive, then the search is approxim | |
| | | ate | |
| | | // in the sense that it is free to ignore any point that lies | |
| | | // outside a ball of radius r/(1+epsilon), where r is the given | |
| | | // (unsquared) radius bound. | |
| | | // | |
| // The generic object from which all the search structures are | | // The generic object from which all the search structures are | |
| // dervied is given below. It is a virtual object, and is usel
ess | | // dervied is given below. It is a virtual object, and is usel
ess | |
| // by itself. | | // by itself. | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| class DLL_API ANNpointSet { | | class DLL_API ANNpointSet { | |
| public: | | public: | |
| virtual ~ANNpointSet() {} // virtual distructo
r | | virtual ~ANNpointSet() {} // virtual distructo
r | |
| | | | |
| virtual void annkSearch( // approx k near nei
ghbor search | | virtual void annkSearch( // approx k near nei
ghbor search | |
| ANNpoint q, // q
uery point | | ANNpoint q, // q
uery point | |
| int k,
// number of near neighbors to return | | int k,
// number of near neighbors to return | |
|
| ANNidxArray nn_idx, // nearest n | | ANNidxArray nn_idx, // nearest n | |
| eighbor array (returned) | | eighbor array (modified) | |
| ANNdistArray dd, // dist to n | | ANNdistArray dd, // dist to n | |
| ear neighbors (returned) | | ear neighbors (modified) | |
| | | double eps=0.0 // error bou | |
| | | nd | |
| | | ) = 0; // p | |
| | | ure virtual (defined elsewhere) | |
| | | | |
| | | virtual int annkFRSearch( // approx fixed-radi | |
| | | us kNN search | |
| | | ANNpoint q, // q | |
| | | uery point | |
| | | ANNdist sqRad, // squared r | |
| | | adius | |
| | | int k = 0, // n | |
| | | umber of near neighbors to return | |
| | | ANNidxArray nn_idx = NULL, // nearest neighbor | |
| | | array (modified) | |
| | | ANNdistArray dd = NULL, // dist to near neig | |
| | | hbors (modified) | |
| double eps=0.0 // error bou
nd | | double eps=0.0 // error bou
nd | |
| ) = 0; // p
ure virtual (defined elsewhere) | | ) = 0; // p
ure virtual (defined elsewhere) | |
| | | | |
| virtual int theDim() = 0; // return dimension
of space | | virtual int theDim() = 0; // return dimension
of space | |
| virtual int nPoints() = 0; // return number of
points | | virtual int nPoints() = 0; // return number of
points | |
|
// return pointer to points | |
// return pointer to points | |
| virtual ANNpointArray thePoints() = 0; | | virtual ANNpointArray thePoints() = 0; | |
| }; | | }; | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| skipping to change at line 522 | | skipping to change at line 549 | |
|---|
| ANNbruteForce( // construct
or from point array | | ANNbruteForce( // construct
or from point array | |
| ANNpointArray pa, // point arr
ay | | ANNpointArray pa, // point arr
ay | |
| int n,
// number of points | | int n,
// number of points | |
| int dd); // d
imension | | int dd); // d
imension | |
| | | | |
| ~ANNbruteForce(); // destructo
r | | ~ANNbruteForce(); // destructo
r | |
| | | | |
| void annkSearch( // approx k
near neighbor search | | void annkSearch( // approx k
near neighbor search | |
| ANNpoint q, // q
uery point | | ANNpoint q, // q
uery point | |
| int k,
// number of near neighbors to return | | int k,
// number of near neighbors to return | |
|
| ANNidxArray nn_idx, // nearest n | | ANNidxArray nn_idx, // nearest n | |
| eighbor array (returned) | | eighbor array (modified) | |
| ANNdistArray dd, // dist to n | | ANNdistArray dd, // dist to n | |
| ear neighbors (returned) | | ear neighbors (modified) | |
| | | double eps=0.0); // error bou | |
| | | nd | |
| | | | |
| | | int annkFRSearch( // approx fi | |
| | | xed-radius kNN search | |
| | | ANNpoint q, // q | |
| | | uery point | |
| | | ANNdist sqRad, // squared r | |
| | | adius | |
| | | int k = 0, // n | |
| | | umber of near neighbors to return | |
| | | ANNidxArray nn_idx = NULL, // nearest neighbor | |
| | | array (modified) | |
| | | ANNdistArray dd = NULL, // dist to near neig | |
| | | hbors (modified) | |
| double eps=0.0); // error bou
nd | | double eps=0.0); // error bou
nd | |
| | | | |
| int theDim() // return di
mension of space | | int theDim() // return di
mension of space | |
| { return dim; } | | { return dim; } | |
| | | | |
| int nPoints() // return nu
mber of points | | int nPoints() // return nu
mber of points | |
| { return n_pts; } | | { return n_pts; } | |
| | | | |
| ANNpointArray thePoints() // return pointer to
points | | ANNpointArray thePoints() // return pointer to
points | |
| { return pts; } | | { return pts; } | |
| | | | |
| skipping to change at line 664 | | skipping to change at line 699 | |
|---|
| // splitRule Splitting method use
d | | // splitRule Splitting method use
d | |
| // | | // | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // Some types and objects used by kd-tree functions | | // Some types and objects used by kd-tree functions | |
| // See src/kd_tree.h and src/kd_tree.cpp for definitions | | // See src/kd_tree.h and src/kd_tree.cpp for definitions | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| class ANNkdStats; // stats on kd-tree | | class ANNkdStats; // stats on kd-tree | |
| class ANNkd_node; // generic node in a kd-tree | | class ANNkd_node; // generic node in a kd-tree | |
|
| typedef ANNkd_node *ANNkd_ptr; // pointer to a kd-tree node | | typedef ANNkd_node* ANNkd_ptr; // pointer to a kd-tree node | |
| | | | |
| class DLL_API ANNkd_tree: public ANNpointSet { | | class DLL_API ANNkd_tree: public ANNpointSet { | |
| protected: | | protected: | |
|
| int dim; // dimension of spac | | int dim; // d | |
| e | | imension of space | |
| int n_pts; // number of points | | int n_pts; // n | |
| in tree | | umber of points in tree | |
| int bkt_size; // bucket size | | int bkt_size; // b | |
| ANNpointArray pts; // the points | | ucket size | |
| ANNidxArray pidx; // point indices (to pts arr | | ANNpointArray pts; // the points | |
| ay) | | ANNidxArray pidx; // point ind | |
| ANNkd_ptr root; // root of kd-tree | | ices (to pts array) | |
| ANNpoint bnd_box_lo; // bounding box low point | | ANNkd_ptr root; // root of k | |
| ANNpoint bnd_box_hi; // bounding box high point | | d-tree | |
| | | ANNpoint bnd_box_lo; // bounding | |
| | | box low point | |
| | | ANNpoint bnd_box_hi; // bounding | |
| | | box high point | |
| | | | |
|
| void SkeletonTree( // construct skeleto | | void SkeletonTree( // construct | |
| n tree | | skeleton tree | |
| int n, // n | | int n, | |
| umber of points | | // number of points | |
| int dd, // d | | int dd, | |
| imension | | // dimension | |
| int bs, // b | | int bs, | |
| ucket size | | // bucket size | |
| ANNpointArray pa = NULL, // point array (optional) | | ANNpointArray pa = NULL, // point array (opti | |
| ANNidxArray pi = NULL); // point indices (optional) | | onal) | |
| | | ANNidxArray pi = NULL); // point indices (op | |
| | | tional) | |
| | | | |
| public: | | public: | |
|
| ANNkd_tree( // build ske | | ANNkd_tree( // b | |
| leton tree | | uild skeleton tree | |
| int n = 0, // number of | | int n = 0, // n | |
| points | | umber of points | |
| int dd = 0, // dimension | | int dd = 0, // d | |
| int bs = 1); // bucket si | | imension | |
| ze | | int bs = 1); // b | |
| | | ucket size | |
| | | | |
|
| ANNkd_tree( // build fro | | ANNkd_tree( // b | |
| m point array | | uild from point array | |
| ANNpointArray pa, // point array | | ANNpointArray pa, // point arr | |
| int n, // n | | ay | |
| umber of points | | int n, | |
| int dd, // d | | // number of points | |
| imension | | int dd, | |
| int bs = 1, // bucket si | | // dimension | |
| ze | | int bs = 1, // b | |
| | | ucket size | |
| ANNsplitRule split = ANN_KD_SUGGEST); // splitting
method | | ANNsplitRule split = ANN_KD_SUGGEST); // splitting
method | |
| | | | |
|
| ANNkd_tree( // build fro | | ANNkd_tree( // b | |
| m dump file | | uild from dump file | |
| std::istream &in); // input stream for dump fil | | std::istream& in); // input stream for | |
| e | | dump file | |
| | | | |
|
| ~ANNkd_tree(); // tree destructor | | ~ANNkd_tree(); // tree dest
ructor | |
| | | | |
|
| void annkSearch( // approx k near nei | | void annkSearch( // approx k | |
| ghbor search | | near neighbor search | |
| ANNpoint q, // query poi | | ANNpoint q, // q | |
| nt | | uery point | |
| int k, // n | | int k, | |
| umber of near neighbors to return | | // number of near neighbors to return | |
| ANNidxArray nn_idx, // nearest neighbor | | ANNidxArray nn_idx, // nearest n | |
| array (returned) | | eighbor array (modified) | |
| ANNdistArray dd, // dist to near neig | | ANNdistArray dd, // dist to n | |
| hbors (returned) | | ear neighbors (modified) | |
| double eps=0.0); // error bound | | double eps=0.0); // error bou | |
| | | nd | |
| | | | |
|
| void annkPriSearch( // priority k near neighbor | | void annkPriSearch( // priority k near n | |
| search | | eighbor search | |
| ANNpoint q, // query poi | | ANNpoint q, // q | |
| nt | | uery point | |
| int k, // n | | int k, | |
| umber of near neighbors to return | | // number of near neighbors to return | |
| ANNidxArray nn_idx, // nearest neighbor | | ANNidxArray nn_idx, // nearest n | |
| array (returned) | | eighbor array (modified) | |
| ANNdistArray dd, // dist to near neig | | ANNdistArray dd, // dist to n | |
| hbors (returned) | | ear neighbors (modified) | |
| double eps=0.0); // error bound | | double eps=0.0); // error bou | |
| | | nd | |
| | | | |
|
| int theDim() // return dimension | | int annkFRSearch( // approx fi | |
| of space | | xed-radius kNN search | |
| | | ANNpoint q, // t | |
| | | he query point | |
| | | ANNdist sqRad, // squared r | |
| | | adius of query ball | |
| | | int k, | |
| | | // number of neighbors to return | |
| | | ANNidxArray nn_idx = NULL, // nearest neighbor | |
| | | array (modified) | |
| | | ANNdistArray dd = NULL, // dist to near neig | |
| | | hbors (modified) | |
| | | double eps=0.0); // error bou | |
| | | nd | |
| | | | |
| | | int theDim() // return di | |
| | | mension of space | |
| { return dim; } | | { return dim; } | |
| | | | |
|
| int nPoints() // return number of
points | | int nPoints() // return nu
mber of points | |
| { return n_pts; } | | { return n_pts; } | |
| | | | |
|
| ANNpointArray thePoints() // return pointer to points | | ANNpointArray thePoints() // return pointer to
points | |
| { return pts; } | | { return pts; } | |
| | | | |
|
| virtual void Print( // print the tree (f | | virtual void Print( // print the | |
| or debugging) | | tree (for debugging) | |
| ANNbool with_pts, // print points as w | | ANNbool with_pts, // print poi | |
| ell? | | nts as well? | |
| std::ostream &out); // output stream | | std::ostream& out); // output stream | |
| | | | |
|
| virtual void Dump( // dump entire tree | | virtual void Dump( // dump enti | |
| ANNbool with_pts, // print points as w | | re tree | |
| ell? | | ANNbool with_pts, // print poi | |
| std::ostream &out); // output stream | | nts as well? | |
| | | std::ostream& out); // output stream | |
| | | | |
|
| virtual void getStats( // compute tree statistics | | virtual void getStats( // compute tree stat | |
| ANNkdStats &st); // the statistics (r | | istics | |
| eturned) | | ANNkdStats& st); // the stati | |
| | | stics (modified) | |
| }; | | }; | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // Box decomposition tree (bd-tree) | | // Box decomposition tree (bd-tree) | |
| // The bd-tree is inherited from a kd-tree. The main differenc
e | | // The bd-tree is inherited from a kd-tree. The main differenc
e | |
| // in the bd-tree and the kd-tree is a new type of internal nod
e | | // in the bd-tree and the kd-tree is a new type of internal nod
e | |
| // called a shrinking node (in the kd-tree there is only one ty
pe | | // called a shrinking node (in the kd-tree there is only one ty
pe | |
| // of internal node, a splitting node). The shrinking node | | // of internal node, a splitting node). The shrinking node | |
| // makes it possible to generate balanced trees in which the | | // makes it possible to generate balanced trees in which the | |
| // cells have bounded aspect ratio, by allowing the decompositi
on | | // cells have bounded aspect ratio, by allowing the decompositi
on | |
| // to zoom in on regions of dense point concentration. Althoug
h | | // to zoom in on regions of dense point concentration. Althoug
h | |
| // this is a nice idea in theory, few point distributions are s
o | | // this is a nice idea in theory, few point distributions are s
o | |
| // densely clustered that this is really needed. | | // densely clustered that this is really needed. | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| class DLL_API ANNbd_tree: public ANNkd_tree { | | class DLL_API ANNbd_tree: public ANNkd_tree { | |
| public: | | public: | |
|
| ANNbd_tree( // build ske | | ANNbd_tree( // b | |
| leton tree | | uild skeleton tree | |
| int n, // n | | int n, | |
| umber of points | | // number of points | |
| int dd, // d | | int dd, | |
| imension | | // dimension | |
| int bs = 1) // bucket si | | int bs = 1) // b | |
| ze | | ucket size | |
| : ANNkd_tree(n, dd, bs) {} // build base kd-tree | | : ANNkd_tree(n, dd, bs) {} // build base kd-tre | |
| | | e | |
| | | | |
|
| ANNbd_tree( // build fro | | ANNbd_tree( // b | |
| m point array | | uild from point array | |
| ANNpointArray pa, // point array | | ANNpointArray pa, // point arr | |
| int n, // n | | ay | |
| umber of points | | int n, | |
| int dd, // d | | // number of points | |
| imension | | int dd, | |
| int bs = 1, // bucket si | | // dimension | |
| ze | | int bs = 1, // b | |
| | | ucket size | |
| ANNsplitRule split = ANN_KD_SUGGEST, // splitting
rule | | ANNsplitRule split = ANN_KD_SUGGEST, // splitting
rule | |
| ANNshrinkRule shrink = ANN_BD_SUGGEST); // shrinking
rule | | ANNshrinkRule shrink = ANN_BD_SUGGEST); // shrinking
rule | |
| | | | |
|
| ANNbd_tree( // build fro | | ANNbd_tree( // b | |
| m dump file | | uild from dump file | |
| std::istream &in); // input str | | std::istream& in); // input stream for | |
| eam for dump file | | dump file | |
| }; | | }; | |
| | | | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| // Other functions | | // Other functions | |
| // annMaxPtsVisit Sets a limit on the maximum number of points | | // annMaxPtsVisit Sets a limit on the maximum number of points | |
| // to visit in the search. | | // to visit in the search. | |
| // annClose Can be called when all use of ANN is finishe
d. | | // annClose Can be called when all use of ANN is finishe
d. | |
| // It clears up a minor memory
leak. | | // It clears up a minor memory
leak. | |
| //---------------------------------------------------------------------- | | //---------------------------------------------------------------------- | |
| | | | |
| | | | |
| End of changes. 34 change blocks. |
|---|
| 150 lines changed or deleted | | 236 lines changed or added | |
|---|
|