Template Class KDTreeBaseClass

Defined in File nanoflann.hpp

Nested Relationships

Nested Types

Class Documentation

template<class Derived, typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t> class KDTreeBaseClass

kd-tree base-class

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

Template Parameters:

Derived – The name of the class which inherits this class.
DatasetAdaptor – The user-provided adaptor, which must be ensured to have a lifetime equal or longer than the instance of this class.
Distance – The distance metric to use, these are all classes derived from nanoflann::Metric
DIM – Dimensionality of data points (e.g. 3 for 3D points)
IndexType – Type of the arguments with which the data can be accessed (e.g. float, double, int64_t, T*)

Public Types

using ElementType = typename Distance::ElementType

using DistanceType = typename Distance::DistanceType

Offset = typename decltype(vAcc_)::size_type

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: Define “BoundingBox” as a fixed-size or variable-size container depending on “DIM”

using 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”

Public Functions

inline void freeIndex(Derived &obj): Frees the previously-built index. Automatically called within buildIndex().

inline Size size(const Derived &obj) const: Returns number of points in dataset

inline Size veclen(const Derived &obj): Returns the length of each point in the dataset

inline ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const: Helper accessor to the dataset points:

inline Size usedMemory(Derived &obj): Computes the inde memory usage Returns: memory used by the index

inline void computeMinMax(const Derived &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem)

inline NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)

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:

left – index of the first vector
right – index of the last vector

inline NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic<unsigned int> &thread_count, std::mutex &mutex)

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:

left – index of the first vector
right – index of the last vector
thread_count – count of std::async threads
mutex – mutex for mempool allocation

inline void middleSplit_(const Derived &obj, const Offset ind, const Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox)

inline void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)

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

inline DistanceType computeInitialDistances(const Derived &obj, const ElementType *vec, distance_vector_t &dists) const

inline void saveIndex(const Derived &obj, std::ostream &stream) const

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