Classes struct BranchStruct This record represents a branch point when finding neighbors in the tree. More...
struct Interval struct Node Public Types typedef Distance::ElementType ElementType typedef Distance::DistanceType DistanceType Public Member Functions KDTreeSingleIndexAdaptor (const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params= KDTreeSingleIndexAdaptorParams ())  KDTree constructor.
void init () ~KDTreeSingleIndexAdaptor ()  Standard destructor.
void freeIndex ()  Frees the previously-built index.
void buildIndex ()  Builds the index.
size_t size () const  Returns size of index.
size_t veclen () const  Returns the length of an index feature.
size_t usedMemory () const  Computes the inde memory usage Returns: memory used by the index.
void saveIndex (FILE *stream)  Stores the index in a binary file.
void loadIndex (FILE *stream)  Loads a previous index from a binary file.
template<typename RESULTSET > void findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const  Find set of nearest neighbors to vec[0:dim-1].
void knnSearch (const ElementType *query_point, const size_t num_closest, IndexType *out_indices, DistanceType *out_distances_sq, const int=10) const  Find the "num_closest" nearest neighbors to the query_point [0:dim-1].
size_t radiusSearch (const ElementType *query_point, const DistanceType radius, std::vector< std::pair< IndexType, DistanceType > > &IndicesDists, const SearchParams &searchParams) const  Find all the neighbors to query_point [0:dim-1] within a maximum radius.
size_t radiusSearch (const ElementType *query_point, const DistanceType radius, std::list< IndexType > &IndicesDists, const SearchParams &searchParams) const Public Attributes Distance distance Protected Types typedef Node * NodePtr typedef array_or_vector_selector < DIM, Interval >::container_t BoundingBox Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM".
typedef array_or_vector_selector < DIM, DistanceType >::container_t distance_vector_t Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM".
typedef BranchStruct < NodePtr , DistanceType > BranchSt typedef BranchSt * Branch Protected Attributes std::vector< IndexType > vind Array of indices to vectors in the dataset.
size_t m_leaf_max_size const DatasetAdaptor & dataset The dataset used by this index.
const KDTreeSingleIndexAdaptorParams index_params size_t m_size int dim Dimensionality of each data point.
NodePtr root_node Array of k-d trees used to find neighbours.
BoundingBox root_bbox PooledAllocator pool Pooled memory allocator.

Detailed Description

typedef Distance::DistanceType nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::DistanceType template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t> typedef Distance::ElementType nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::ElementType nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexAdaptor const int dimensionality ,

KDTree constructor.

Params: inputData = dataset with the input features params = parameters passed to the kdtree algorithm (see http://code.google.com/p/nanoflann/ for help choosing the parameters)

Definition at line 983 of file nanoflann.hpp .

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t> template<typename RESULTSET > void nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::findNeighbors RESULTSET & result ,

Find set of nearest neighbors to vec[0:dim-1].

Their indices are stored inside the result object.

Params: result = the result object in which the indices of the nearest-neighbors are stored vec = the vector for which to search the nearest neighbors

Template Parameters

RESULTSETShould be any ResultSet<DistanceType>

See also

knnSearch , radiusSearch

Definition at line 1073 of file nanoflann.hpp .

1074 {

1075 assert(vec);

1076 if (! root_node )

1077 throw std::runtime_error(

1078 "[nanoflann] findNeighbors() called before building the index or no data points." );

1079 float epsError = 1 + searchParams.eps;

1081 distance_vector_t dists; // fixed or variable-sized container (depending on DIM)

1082 dists.assign((DIM > 0 ? DIM : dim ), 0); // Fill it with zeros.

1083 DistanceType distsq = computeInitialDistances(vec, dists);

1084 searchLevel(result, vec, root_node , distsq, dists, epsError); // "count_leaf" parameter removed since was neither used nor returned to the user.

1085 }

nanoflann::KDTreeSingleIndexAdaptor::distance_vector_t

array_or_vector_selector< DIM, DistanceType >::container_t distance_vector_t

Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM".

Definition nanoflann.hpp:931

References nanoflann::CArray< T, N >::assign() , and nanoflann::SearchParams::eps .

Here is the call graph for this function:

void nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::freeIndex

Automatically called within buildIndex() .

Definition at line 1018 of file nanoflann.hpp .

1018 {

1019 pool . free_all ();

1020 root_node = NULL;

1021 }

nanoflann::KDTreeSingleIndexAdaptor::pool

PooledAllocator pool

Pooled memory allocator.

Definition nanoflann.hpp:970

nanoflann::PooledAllocator::free_all

void free_all()

Frees all allocated memory chunks.

Definition nanoflann.hpp:570

void nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::init

Definition at line 1004 of file nanoflann.hpp .

1004 {

1005 m_size = dataset .kdtree_get_point_count();

1007 // Create a permutable array of indices to the input vectors.

1008 init_vind();

1009 }

Here is the caller graph for this function:

void nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::knnSearch const ElementType * query_point ,

Find the "num_closest" nearest neighbors to the query_point [0:dim-1].

Their indices are stored inside the result object.

See also

radiusSearch , findNeighbors

Note

nChecks_IGNORED is ignored but kept for compatibility with the original FLANN interface.

Definition at line 1093 of file nanoflann.hpp .

1096 {

1097 nanoflann::KNNResultSet<DistanceType, IndexType> resultSet(num_closest);

1098 resultSet.init(out_indices, out_distances_sq);

1099 this-> findNeighbors (resultSet, query_point, nanoflann::SearchParams ());

1100 }

nanoflann::KDTreeSingleIndexAdaptor::findNeighbors

void findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const

Find set of nearest neighbors to vec[0:dim-1].

Definition nanoflann.hpp:1073

nanoflann::KNNResultSet

Definition nanoflann.hpp:64

nanoflann::SearchParams

Search options for KDTreeSingleIndexAdaptor::findNeighbors()

Definition nanoflann.hpp:484

References nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::init() .

Here is the call graph for this function:

void nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::loadIndex FILE * stream )

Loads a previous index from a binary file.

IMPORTANT NOTE: The set of data points is NOT stored in the file, so the index object must be constructed associated to the same source of data points used while building the index. See the example: examples/saveload_example.cpp

See also

loadIndex

Definition at line 1507 of file nanoflann.hpp .

1507 {

1508 load_value (stream, m_size );

1509 load_value (stream, dim );

1510 load_value (stream, root_bbox );

1511 load_value (stream, m_leaf_max_size );

1512 load_value (stream, vind );

1513 load_tree(stream, root_node );

1514 }

nanoflann::KDTreeSingleIndexAdaptor::vind

std::vector< IndexType > vind

Array of indices to vectors in the dataset.

Definition nanoflann.hpp:882

nanoflann::load_value

void load_value(FILE *stream, T &value, size_t count=1)

Definition nanoflann.hpp:275

References nanoflann::load_value() .

Here is the call graph for this function:

size_t nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::radiusSearch const ElementType * query_point ,

Definition at line 1127 of file nanoflann.hpp .

1129 {

1130 RadiusResultList<DistanceType, IndexType> resultList(radius, IndicesDists);

1131 this-> findNeighbors (resultList, query_point, searchParams);

1133 if (searchParams.sorted)

1134 IndicesDists.sort();

1136 return resultList.size();

1137 }

References nanoflann::RadiusResultList< DistanceType, IndexType >::size() , and nanoflann::SearchParams::sorted .

Here is the call graph for this function:

size_t nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::radiusSearch const ElementType * query_point ,

Find all the neighbors to query_point [0:dim-1] within a maximum radius.

The output is given as a vector of pairs, of which the first element is a point index and the second the corresponding distance. Previous contents of IndicesDists are cleared.

If searchParams.sorted==true, the output list is sorted by ascending distances.

For a better performance, it is advisable to do a .reserve() on the vector if you have any wild guess about the number of expected matches.

See also

knnSearch , findNeighbors

Returns

The number of points within the given radius (i.e. indices.size() or dists.size() )

Definition at line 1114 of file nanoflann.hpp .

1117 {

1118 RadiusResultSet<DistanceType, IndexType> resultSet(radius, IndicesDists);

1119 this-> findNeighbors (resultSet, query_point, searchParams);

1121 if (searchParams.sorted)

1122 std::sort(IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());

1124 return resultSet.size();

1125 }

References nanoflann::RadiusResultSet< DistanceType, IndexType >::size() , and nanoflann::SearchParams::sorted .

Here is the call graph for this function:

void nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::saveIndex FILE * stream )

Stores the index in a binary file.

IMPORTANT NOTE: The set of data points is NOT stored in the file, so when loading the index object it must be constructed associated to the same source of data points used while building it. See the example: examples/saveload_example.cpp

See also

loadIndex

Definition at line 1494 of file nanoflann.hpp .

1494 {

1495 save_value (stream, m_size );

1496 save_value (stream, dim );

1497 save_value (stream, root_bbox );

1498 save_value (stream, m_leaf_max_size );

1499 save_value (stream, vind );

1500 save_tree(stream, root_node );

1501 }

nanoflann::save_value

void save_value(FILE *stream, const T &value, size_t count=1)

Definition nanoflann.hpp:263

References nanoflann::save_value() .

Here is the call graph for this function:

size_t nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::size const size_t nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::usedMemory const

Computes the inde memory usage Returns: memory used by the index.

Definition at line 1053 of file nanoflann.hpp .

1053 {

1054 return pool . usedMemory + pool . wastedMemory

1055 + dataset .kdtree_get_point_count() * sizeof (IndexType); // pool memory and vind array memory

1056 }

nanoflann::PooledAllocator::usedMemory

size_t usedMemory

Definition nanoflann.hpp:551

nanoflann::PooledAllocator::wastedMemory

size_t wastedMemory

Definition nanoflann.hpp:552

size_t nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::veclen const

Definition at line 1045 of file nanoflann.hpp .

1045 {

1046 return static_cast< size_t > (DIM > 0 ? DIM : dim );

1047 }

Member Data Documentation

◆ dataset

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

Distance nanoflann::KDTreeSingleIndexAdaptor < Distance, DatasetAdaptor, DIM, IndexType >::distance

Pooled memory allocator.

Using a pooled memory allocator is more efficient than allocating memory directly when there is a large number small of memory allocations.

Definition at line 970 of file nanoflann.hpp .