Classes | Public Types | Public Member Functions | Public Attributes | Protected Types | Protected Attributes | Private Member Functions | List of all members
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > Class Template Reference

#include <nanoflann.hpp>

Classes

struct  BranchStruct
 
struct  Interval
 
struct  Node
 

Public Types

typedef Distance::DistanceType DistanceType
 
typedef Distance::ElementType ElementType
 

Public Member Functions

void buildIndex ()
 
 KDTreeSingleIndexAdaptor (const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
 
size_t size () const
 
size_t usedMemory () const
 
size_t veclen () const
 
 ~KDTreeSingleIndexAdaptor ()
 
Query methods
template<typename RESULTSET >
void findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
 
void knnSearch (const ElementType *query_point, const size_t num_closest, IndexType *out_indices, DistanceType *out_distances_sq, const int nChecks_IGNORED=10) const
 
size_t radiusSearch (const ElementType *query_point, const DistanceType radius, std::vector< std::pair< IndexType, DistanceType > > &IndicesDists, const SearchParams &searchParams) const
 

Public Attributes

Distance distance
 

Protected Types

typedef std::vector< IntervalBoundingBox
 
typedef BranchStBranch
 
typedef BranchStruct< NodePtr, DistanceTypeBranchSt
 
typedef NodeNodePtr
 

Protected Attributes

const DatasetAdaptor & dataset
 The source of our data. More...
 
int dim
 Dimensionality of each data point. More...
 
const KDTreeSingleIndexAdaptorParams index_params
 
size_t m_leaf_max_size
 
size_t m_size
 
PooledAllocator pool
 
BoundingBox root_bbox
 
NodePtr root_node
 
std::vector< IndexType > vind
 

Private Member Functions

void computeBoundingBox (BoundingBox &bbox)
 
DistanceType computeInitialDistances (const ElementType *vec, std::vector< DistanceType > &dists) const
 
void computeMinMax (IndexType *ind, IndexType count, int element, ElementType &min_elem, ElementType &max_elem)
 
ElementType dataset_get (size_t idx, int component) const
 Helper accessor to the dataset points: More...
 
NodePtr divideTree (const IndexType left, const IndexType right, BoundingBox &bbox)
 
void init_vind ()
 
void load_tree (FILE *stream, NodePtr &tree)
 
void loadIndex (FILE *stream)
 
void middleSplit (IndexType *ind, IndexType count, IndexType &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
 
void middleSplit_ (IndexType *ind, IndexType count, IndexType &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
 
void planeSplit (IndexType *ind, const IndexType count, int cutfeat, DistanceType cutval, IndexType &lim1, IndexType &lim2)
 
void save_tree (FILE *stream, NodePtr tree)
 
void saveIndex (FILE *stream)
 
template<class RESULTSET >
void searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, std::vector< DistanceType > &dists, const float epsError) const
 

Detailed Description

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

kd-tree index

Contains the k-d trees and other information for indexing a set of points for nearest-neighbor matching.

The class "DatasetAdaptor" must provide the following interface (can be non-virtual, inlined methods):

// Must return the number of data points
inline size_t kdtree_get_point_count() const { ... }
// Must return the Euclidean (L2) distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
inline DistanceType kdtree_distance(const T *p1, const size_t idx_p2,size_t size) const { ... }
// Must return the dim'th component of the idx'th point in the class:
inline T kdtree_get_pt(const size_t idx, int dim) const { ... }
// Optional bounding-box computation: return false to default to a standard bbox computation loop.
// Return true if the BBOX was already computed by the class and returned in "bb" so it can be avoided to redo it again.
// Look at bb.size() to find out the expected dimensionality (e.g. 2 or 3 for point clouds)
template <class BBOX>
bool kdtree_get_bbox(BBOX &bb) const
{
bb[0].low = ...; bb[0].high = ...; // 0th dimension limits
bb[1].low = ...; bb[1].high = ...; // 1st dimension limits
...
return true;
}
Template Parameters
IndexTypeWill be typically size_t or int

Definition at line 634 of file nanoflann.hpp.

Member Typedef Documentation

◆ BoundingBox

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
typedef std::vector<Interval> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::BoundingBox
protected

Definition at line 696 of file nanoflann.hpp.

◆ Branch

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
typedef BranchSt* nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Branch
protected

Definition at line 723 of file nanoflann.hpp.

◆ BranchSt

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
typedef BranchStruct<NodePtr, DistanceType> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::BranchSt
protected

Definition at line 722 of file nanoflann.hpp.

◆ DistanceType

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

Definition at line 638 of file nanoflann.hpp.

◆ ElementType

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

Definition at line 637 of file nanoflann.hpp.

◆ NodePtr

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
typedef Node* nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::NodePtr
protected

Definition at line 688 of file nanoflann.hpp.

Constructor & Destructor Documentation

◆ KDTreeSingleIndexAdaptor()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexAdaptor ( const int  dimensionality,
const DatasetAdaptor &  inputData,
const KDTreeSingleIndexAdaptorParams params = KDTreeSingleIndexAdaptorParams() 
)
inline

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 747 of file nanoflann.hpp.

◆ ~KDTreeSingleIndexAdaptor()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::~KDTreeSingleIndexAdaptor ( )
inline

Standard destructor

Definition at line 765 of file nanoflann.hpp.

Member Function Documentation

◆ buildIndex()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::buildIndex ( )
inline

Builds the index

Definition at line 772 of file nanoflann.hpp.

◆ computeBoundingBox()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::computeBoundingBox ( BoundingBox bbox)
inlineprivate

Definition at line 911 of file nanoflann.hpp.

◆ computeInitialDistances()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
DistanceType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::computeInitialDistances ( const ElementType vec,
std::vector< DistanceType > &  dists 
) const
inlineprivate

Definition at line 1130 of file nanoflann.hpp.

◆ computeMinMax()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::computeMinMax ( IndexType *  ind,
IndexType  count,
int  element,
ElementType min_elem,
ElementType max_elem 
)
inlineprivate

Definition at line 994 of file nanoflann.hpp.

◆ dataset_get()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
ElementType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dataset_get ( size_t  idx,
int  component 
) const
inlineprivate

Helper accessor to the dataset points:

Definition at line 881 of file nanoflann.hpp.

◆ divideTree()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
NodePtr nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::divideTree ( const IndexType  left,
const IndexType  right,
BoundingBox bbox 
)
inlineprivate

Create a tree node that subdivides the list of vecs from vind[first] to vind[last]. The routine is called recursively on each sublist. Place a pointer to this new tree node in the location pTree.

Params: pTree = the new node to create first = index of the first vector last = index of the last vector

Definition at line 944 of file nanoflann.hpp.

◆ findNeighbors()

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,
const ElementType vec,
const SearchParams searchParams 
) const
inline

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 819 of file nanoflann.hpp.

◆ init_vind()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::init_vind ( )
inlineprivate

Make sure the auxiliary list vind has the same size than the current dataset, and re-generate if size has changed.

Definition at line 869 of file nanoflann.hpp.

◆ knnSearch()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::knnSearch ( const ElementType query_point,
const size_t  num_closest,
IndexType *  out_indices,
DistanceType out_distances_sq,
const int  nChecks_IGNORED = 10 
) const
inline

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 835 of file nanoflann.hpp.

◆ load_tree()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::load_tree ( FILE *  stream,
NodePtr tree 
)
inlineprivate

Definition at line 898 of file nanoflann.hpp.

◆ loadIndex()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::loadIndex ( FILE *  stream)
inlineprivate

Definition at line 1214 of file nanoflann.hpp.

◆ middleSplit()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::middleSplit ( IndexType *  ind,
IndexType  count,
IndexType &  index,
int &  cutfeat,
DistanceType cutval,
const BoundingBox bbox 
)
inlineprivate

Definition at line 1005 of file nanoflann.hpp.

◆ middleSplit_()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::middleSplit_ ( IndexType *  ind,
IndexType  count,
IndexType &  index,
int &  cutfeat,
DistanceType cutval,
const BoundingBox bbox 
)
inlineprivate

Definition at line 1050 of file nanoflann.hpp.

◆ planeSplit()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::planeSplit ( IndexType *  ind,
const IndexType  count,
int  cutfeat,
DistanceType  cutval,
IndexType &  lim1,
IndexType &  lim2 
)
inlineprivate

Subdivide the list of points by a plane perpendicular on axe corresponding to the 'cutfeat' dimension at 'cutval' position.

On return: dataset[ind[0..lim1-1]][cutfeat]<cutval dataset[ind[lim1..lim2-1]][cutfeat]==cutval dataset[ind[lim2..count]][cutfeat]>cutval

Definition at line 1101 of file nanoflann.hpp.

◆ radiusSearch()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::radiusSearch ( const ElementType query_point,
const DistanceType  radius,
std::vector< std::pair< IndexType, DistanceType > > &  IndicesDists,
const SearchParams searchParams 
) const
inline

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 854 of file nanoflann.hpp.

◆ save_tree()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::save_tree ( FILE *  stream,
NodePtr  tree 
)
inlineprivate

Definition at line 886 of file nanoflann.hpp.

◆ saveIndex()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::saveIndex ( FILE *  stream)
inlineprivate

Definition at line 1204 of file nanoflann.hpp.

◆ searchLevel()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
template<class RESULTSET >
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::searchLevel ( RESULTSET &  result_set,
const ElementType vec,
const NodePtr  node,
DistanceType  mindistsq,
std::vector< DistanceType > &  dists,
const float  epsError 
) const
inlineprivate

Performs an exact search in the tree starting from a node.

Template Parameters
RESULTSETShould be any ResultSet<DistanceType>

Definition at line 1154 of file nanoflann.hpp.

◆ size()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::size ( ) const
inline

Returns size of index.

Definition at line 782 of file nanoflann.hpp.

◆ usedMemory()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::usedMemory ( ) const
inline

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

Definition at line 799 of file nanoflann.hpp.

◆ veclen()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::veclen ( ) const
inline

Returns the length of an index feature.

Definition at line 790 of file nanoflann.hpp.

Member Data Documentation

◆ dataset

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
const DatasetAdaptor& nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dataset
protected

The source of our data.

The dataset used by this index

Definition at line 652 of file nanoflann.hpp.

◆ dim

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
int nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dim
protected

Dimensionality of each data point.

Definition at line 657 of file nanoflann.hpp.

◆ distance

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
Distance nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::distance

Definition at line 738 of file nanoflann.hpp.

◆ index_params

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
const KDTreeSingleIndexAdaptorParams nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::index_params
protected

Definition at line 654 of file nanoflann.hpp.

◆ m_leaf_max_size

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::m_leaf_max_size
protected

Definition at line 646 of file nanoflann.hpp.

◆ m_size

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::m_size
protected

Definition at line 656 of file nanoflann.hpp.

◆ pool

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
PooledAllocator nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::pool
protected

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 734 of file nanoflann.hpp.

◆ root_bbox

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
BoundingBox nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::root_bbox
protected

Definition at line 725 of file nanoflann.hpp.

◆ root_node

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
NodePtr nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::root_node
protected

Array of k-d trees used to find neighbours.

Definition at line 721 of file nanoflann.hpp.

◆ vind

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>
std::vector<IndexType> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::vind
protected

Array of indices to vectors in the dataset.

Definition at line 644 of file nanoflann.hpp.


The documentation for this class was generated from the following file:
nanoflann::KDTreeSingleIndexAdaptor::DistanceType
Distance::DistanceType DistanceType
Definition: nanoflann.hpp:638
nanoflann::KDTreeSingleIndexAdaptor::size
size_t size() const
Definition: nanoflann.hpp:782
nanoflann::KDTreeSingleIndexAdaptor::dim
int dim
Dimensionality of each data point.
Definition: nanoflann.hpp:657


lvr2
Author(s): Thomas Wiemann , Sebastian Pütz , Alexander Mock , Lars Kiesow , Lukas Kalbertodt , Tristan Igelbrink , Johan M. von Behren , Dominik Feldschnieders , Alexander Löhr
autogenerated on Wed Mar 2 2022 00:37:28