nanoflann
C++ header-only ANN library
Public Types | Public Member Functions | Public Attributes | List of all members
nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType > Class Template Reference

#include <nanoflann.hpp>

Inheritance diagram for nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >:
nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >

Public Types

using BaseClassRef = typename nanoflann::KDTreeBaseClass< nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >, Distance, DatasetAdaptor, DIM, AccessorType >
 
using ElementType = typename BaseClassRef::ElementType
 
using DistanceType = typename BaseClassRef::DistanceType
 
using Offset = typename BaseClassRef::Offset
 
using Size = typename BaseClassRef::Size
 
using Dimension = typename BaseClassRef::Dimension
 
using Node = typename BaseClassRef::Node
 
using NodePtr = Node *
 
using Interval = typename BaseClassRef::Interval
 
using BoundingBox = typename BaseClassRef::BoundingBox
 
using distance_vector_t = typename BaseClassRef::distance_vector_t
 
- Public Types inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
using ElementType = typename Distance::ElementType
 
using DistanceType = typename Distance::DistanceType
 
using Offset = typename decltype(vAcc)::size_type
 
using Size = typename decltype(vAcc)::size_type
 
using Dimension = int32_t
 
using NodePtr = Node *
 
using BoundingBox = typename array_or_vector_selector< DIM, Interval >::container_t
 
using distance_vector_t = typename array_or_vector_selector< DIM, DistanceType >::container_t
 

Public Member Functions

 KDTreeSingleIndexDynamicAdaptor_ (const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex_, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
 
 KDTreeSingleIndexDynamicAdaptor_ (const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
 
KDTreeSingleIndexDynamicAdaptor_ operator= (const KDTreeSingleIndexDynamicAdaptor_ &rhs)
 
void buildIndex ()
 
void computeBoundingBox (BoundingBox &bbox)
 
template<class RESULTSET >
void searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const
 
void saveIndex (std::ostream &stream)
 
void loadIndex (std::istream &stream)
 
Query methods
template<typename RESULTSET >
bool findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
 
Size knnSearch (const ElementType *query_point, const Size num_closest, AccessorType *out_indices, DistanceType *out_distances_sq, const int=10) const
 
Size radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< std::pair< AccessorType, DistanceType > > &IndicesDists, const SearchParams &searchParams) const
 
template<class SEARCH_CALLBACK >
Size radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParams &searchParams=SearchParams()) const
 
- Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
void freeIndex (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj)
 
Size size (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
 
Size veclen (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj)
 
ElementType dataset_get (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, uint32_t element, Dimension component) const
 Helper accessor to the dataset points:
 
Size usedMemory (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj)
 
void computeMinMax (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem)
 
NodePtr divideTree (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox)
 
void middleSplit_ (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, Offset ind, Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
 
void planeSplit (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, Offset ind, const Size count, Dimension cutfeat, DistanceType &cutval, Offset &lim1, Offset &lim2)
 
DistanceType computeInitialDistances (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, const ElementType *vec, distance_vector_t &dists) const
 
void save_tree (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream, NodePtr tree)
 
void load_tree (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream, NodePtr &tree)
 
void saveIndex_ (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream)
 
void loadIndex_ (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream)
 

Public Attributes

const DatasetAdaptor & dataset
 The source of our data. More...
 
KDTreeSingleIndexAdaptorParams index_params
 
std::vector< int > & treeIndex
 
Distance distance
 
- Public Attributes inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
std::vector< uint32_t > vAcc
 
NodePtr root_node
 
Size m_leaf_max_size
 
Size m_size
 Number of current points in the dataset.
 
Size m_size_at_index_build
 
Dimension dim
 Dimensionality of each data point.
 
BoundingBox root_bbox
 
PooledAllocator pool
 

Detailed Description

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename AccessorType = uint32_t>
class nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >

kd-tree dynamic 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 poins
inline size_t kdtree_get_point_count() const { ... }
// Must return the dim'th component of the idx'th point in the class:
inline T kdtree_get_pt(const size_t idx, const size_t 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
DatasetAdaptorThe user-provided adaptor (see comments above).
DistanceThe distance metric to use: nanoflann::metric_L1, nanoflann::metric_L2, nanoflann::metric_L2_Simple, etc.
DIMDimensionality of data points (e.g. 3 for 3D points)
AccessorTypeWill be typically size_t or int

Member Typedef Documentation

◆ BoundingBox

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
using nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::BoundingBox = typename BaseClassRef::BoundingBox

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

◆ distance_vector_t

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
using nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::distance_vector_t = typename BaseClassRef::distance_vector_t

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

Constructor & Destructor Documentation

◆ KDTreeSingleIndexDynamicAdaptor_() [1/2]

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::KDTreeSingleIndexDynamicAdaptor_ ( const Dimension  dimensionality,
const DatasetAdaptor &  inputData,
std::vector< int > &  treeIndex_,
const KDTreeSingleIndexAdaptorParams params = KDTreeSingleIndexAdaptorParams() 
)
inline

KDTree constructor

Refer to docs in README.md or online in https://github.com/jlblancoc/nanoflann

The KD-Tree point dimension (the length of each point in the datase, e.g. 3 for 3D points) is determined by means of:

  • The DIM template parameter if >0 (highest priority)
  • Otherwise, the dimensionality parameter of this constructor.
Parameters
inputDataDataset with the input features. Its lifetime must be equal or longer than that of the instance of this class.
paramsBasically, the maximum leaf node size

◆ KDTreeSingleIndexDynamicAdaptor_() [2/2]

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::KDTreeSingleIndexDynamicAdaptor_ ( const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType > &  rhs)
default

Explicitly default the copy constructor

Member Function Documentation

◆ buildIndex()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::buildIndex ( )
inline

Builds the index

◆ findNeighbors()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
template<typename RESULTSET >
bool nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::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>
Returns
True if the requested neighbors could be found.
See also
knnSearch, radiusSearch

◆ knnSearch()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
Size nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::knnSearch ( const ElementType *  query_point,
const Size  num_closest,
AccessorType *  out_indices,
DistanceType *  out_distances_sq,
const int  = 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.
Returns
Number N of valid points in the result set. Only the first N entries in out_indices and out_distances_sq will be valid. Return may be less than num_closest only if the number of elements in the tree is less than num_closest.

◆ loadIndex()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::loadIndex ( std::istream &  stream)
inline

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

◆ operator=()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
KDTreeSingleIndexDynamicAdaptor_ nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::operator= ( const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType > &  rhs)
inline

Assignment operator definiton

◆ radiusSearch()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
Size nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::radiusSearch ( const ElementType *  query_point,
const DistanceType &  radius,
std::vector< std::pair< AccessorType, 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, radiusSearchCustomCallback
Returns
The number of points within the given radius (i.e. indices.size() or dists.size() )

◆ radiusSearchCustomCallback()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
template<class SEARCH_CALLBACK >
Size nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::radiusSearchCustomCallback ( const ElementType *  query_point,
SEARCH_CALLBACK &  resultSet,
const SearchParams searchParams = SearchParams() 
) const
inline

Just like radiusSearch() but with a custom callback class for each point found in the radius of the query. See the source of RadiusResultSet<> as a start point for your own classes.

See also
radiusSearch

◆ saveIndex()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::saveIndex ( std::ostream &  stream)
inline

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

◆ searchLevel()

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
template<class RESULTSET >
void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::searchLevel ( RESULTSET &  result_set,
const ElementType *  vec,
const NodePtr  node,
DistanceType  mindistsq,
distance_vector_t dists,
const float  epsError 
) const
inline

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

Template Parameters
RESULTSETShould be any ResultSet<DistanceType>

Member Data Documentation

◆ dataset

template<typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
const DatasetAdaptor& nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, AccessorType >::dataset

The source of our data.

The dataset used by this index


The documentation for this class was generated from the following file: