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

#include <nanoflann.hpp>

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

Classes

struct  Interval
 
struct  Node
 

Public Types

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

void freeIndex (Derived &obj)
 
Size size (const Derived &obj) const
 
Size veclen (const Derived &obj)
 
ElementType dataset_get (const Derived &obj, AccessorType element, Dimension component) const
 Helper accessor to the dataset points:
 
Size usedMemory (Derived &obj)
 
void computeMinMax (const Derived &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem)
 
NodePtr divideTree (Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
 
void middleSplit_ (Derived &obj, Offset ind, Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
 
void planeSplit (Derived &obj, Offset ind, const Size count, Dimension cutfeat, DistanceType &cutval, Offset &lim1, Offset &lim2)
 
DistanceType computeInitialDistances (const Derived &obj, const ElementType *vec, distance_vector_t &dists) const
 
void save_tree (Derived &obj, std::ostream &stream, NodePtr tree)
 
void load_tree (Derived &obj, std::istream &stream, NodePtr &tree)
 
void saveIndex_ (Derived &obj, std::ostream &stream)
 
void loadIndex_ (Derived &obj, std::istream &stream)
 

Public Attributes

std::vector< AccessorType > 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<class Derived, typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename AccessorType = uint32_t>
class nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >

kd-tree base-class

Contains the member functions common to the classes KDTreeSingleIndexAdaptor and KDTreeSingleIndexDynamicAdaptor_.

Template Parameters
DerivedThe name of the class which inherits this class.
DatasetAdaptorThe user-provided adaptor (see comments above).
DistanceThe distance metric to use, these are all classes derived from nanoflann::Metric
DIMDimensionality of data points (e.g. 3 for 3D points)
AccessorTypeWill be typically size_t or int

Member Typedef Documentation

◆ BoundingBox

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::BoundingBox = typename array_or_vector_selector<DIM, Interval>::container_t

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

◆ distance_vector_t

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::distance_vector_t = typename array_or_vector_selector<DIM, DistanceType>::container_t

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

Member Function Documentation

◆ divideTree()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
NodePtr nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::divideTree ( Derived &  obj,
const Offset  left,
const Offset  right,
BoundingBox bbox 
)
inline

Create a tree node that subdivides the list of vecs from vind[first] to vind[last]. The routine is called recursively on each sublist.

Parameters
leftindex of the first vector
rightindex of the last vector

◆ freeIndex()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::freeIndex ( Derived &  obj)
inline

Frees the previously-built index. Automatically called within buildIndex().

◆ loadIndex_()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::loadIndex_ ( Derived &  obj,
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

◆ planeSplit()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::planeSplit ( Derived &  obj,
Offset  ind,
const Size  count,
Dimension  cutfeat,
DistanceType &  cutval,
Offset &  lim1,
Offset &  lim2 
)
inline

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

◆ saveIndex_()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::saveIndex_ ( Derived &  obj,
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

◆ size()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::size ( const Derived &  obj) const
inline

Returns number of points in dataset

◆ usedMemory()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::usedMemory ( Derived &  obj)
inline

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

◆ veclen()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::veclen ( const Derived &  obj)
inline

Returns the length of each point in the dataset

Member Data Documentation

◆ m_size_at_index_build

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::m_size_at_index_build

Number of points in the dataset when the index was built

◆ pool

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
PooledAllocator nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::pool

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.

◆ root_bbox

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
BoundingBox nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::root_bbox

The KD-tree used to find neighbours

◆ vAcc

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename AccessorType = uint32_t>
std::vector<AccessorType> nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, AccessorType >::vAcc

Array of indices to vectors in the dataset.


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