nanoflann
C++ header-only ANN library
Loading...
Searching...
No Matches
nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t > Class Template Reference

#include <nanoflann.hpp>

Classes

struct  Interval
 
struct  Node
 

Public Types

using ElementType = typename Distance::ElementType
 
using DistanceType = typename Distance::DistanceType
 
using IndexType = index_t
 
using Offset = typename decltype(vAcc_)::size_type
 
using Size = typename decltype(vAcc_)::size_type
 
using Dimension = int32_t
 
using NodePtr = Node*
 
using NodeConstPtr = const Node*
 
using BoundingBox = typename array_or_vector<DIM, Interval>::type
 
using distance_vector_t = typename array_or_vector<DIM, DistanceType>::type
 

Public Member Functions

void freeIndex (Derived &obj)
 
Size size (const Derived &obj) const
 
Size veclen (const Derived &obj)
 
ElementType dataset_get (const Derived &obj, IndexType 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)
 
NodePtr divideTreeConcurrent (Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
 
void middleSplit_ (const Derived &obj, const Offset ind, const Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
 
void planeSplit (const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
 
DistanceType computeInitialDistances (const Derived &obj, const ElementType *vec, distance_vector_t &dists) const
 
void saveIndex (const Derived &obj, std::ostream &stream) const
 
void loadIndex (Derived &obj, std::istream &stream)
 

Static Public Member Functions

static void save_tree (const Derived &obj, std::ostream &stream, const NodeConstPtr tree)
 
static void load_tree (Derived &obj, std::istream &stream, NodePtr &tree)
 

Public Attributes

std::vector< IndexType > vAcc_
 
NodePtr root_node_ = nullptr
 
Size leaf_max_size_ = 0
 
Size n_thread_build_ = 1
 Number of thread for concurrent tree build.
 
Size size_ = 0
 Number of current points in the dataset.
 
Size size_at_index_build_ = 0
 Number of points in the dataset when the index was built.
 
Dimension dim_ = 0
 Dimensionality of each data point.
 
BoundingBox root_bbox_
 
PooledAllocator pool_
 

Detailed Description

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

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, which must be ensured to have a lifetime equal or longer than the instance of this class.
DistanceThe distance metric to use, these are all classes derived from nanoflann::Metric
DIMDimensionality of data points (e.g. 3 for 3D points)
IndexTypeType of the arguments with which the data can be accessed (e.g. float, double, int64_t, T*)

Member Typedef Documentation

◆ BoundingBox

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::BoundingBox = typename array_or_vector<DIM, Interval>::type

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 index_t = uint32_t>
using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::distance_vector_t = typename array_or_vector<DIM, DistanceType>::type

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 index_t = uint32_t>
NodePtr nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::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

◆ divideTreeConcurrent()

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename index_t = uint32_t>
NodePtr nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::divideTreeConcurrent ( Derived & obj,
const Offset left,
const Offset right,
BoundingBox & bbox,
std::atomic< unsigned int > & thread_count,
std::mutex & mutex )
inline

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

Parameters
leftindex of the first vector
rightindex of the last vector
thread_countcount of std::async threads
mutexmutex for mempool allocation

◆ freeIndex()

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

Subdivide the list of points by a plane perpendicular on the axis 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 index_t = uint32_t>
void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::saveIndex ( const Derived & obj,
std::ostream & stream ) const
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 index_t = uint32_t>
Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::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 index_t = uint32_t>
Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::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 index_t = uint32_t>
Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::veclen ( const Derived & obj)
inline

Returns the length of each point in the dataset

Member Data Documentation

◆ pool_

template<class Derived , typename Distance , class DatasetAdaptor , int32_t DIM = -1, typename index_t = uint32_t>
PooledAllocator nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::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 index_t = uint32_t>
BoundingBox nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::root_bbox_

The KD-tree used to find neighbours

◆ vAcc_

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

Array of indices to vectors in the dataset_.


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