Template Class KDTreeBaseClass

Defined in File nanoflann.hpp

Nested Relationships

Nested Types

Inheritance Relationships

Derived Types

public nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType > (Template Class KDTreeSingleIndexAdaptor)
public nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType > (Template Class KDTreeSingleIndexDynamicAdaptor_)
public nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType > (Template Class KDTreeSingleIndexIncrementalAdaptor)

Class Documentation

template<class Derived, typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = 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*)

Subclassed by nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >, nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >, nanoflann::KDTreeSingleIndexIncrementalAdaptor< Distance, DatasetAdaptor, DIM, IndexType >

Public Types

using ElementType = typename Distance::ElementType

using DistanceType = typename Distance::DistanceType

using IndexType = index_t 

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 NANOFLANN_NODISCARD Size size (const Derived &obj) const noexcept: Returns number of points in dataset

inline NANOFLANN_NODISCARD Size veclen (const Derived &obj) const noexcept: Returns the length of each point in the dataset. For a fixed-size tree (DIM > 0) this is a compile-time constant; under C++17 the if constexpr lets the compiler drop the runtime read of dim_ entirely. The C++11 path keeps the equivalent ternary.

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

inline NANOFLANN_NODISCARD Size usedMemory (const Derived &obj) const: Computes the index 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) const: Compute the minimum and maximum element values in the specified dimension

inline NANOFLANN_NODISCARD bool isActive (IndexType) const: Returns true if the point at index idx should be visited during search. The static adaptor always returns true; the dynamic adaptor overrides this to skip tombstoned (removed) points.

inline void computeBoundingBox(BoundingBox &bbox): Computes the bounding box of the points currently in the index. Uses size_ (set by buildIndex before this is called) so the result is correct for both the static and dynamic adaptors.

template<class RESULTSET> inline bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const DistanceType epsError) const

Performs an exact search in the tree starting from a node. Uses the CRTP-dispatched isActive() hook to skip removed points (no-op in the static adaptor, checks treeIndex_ in the dynamic adaptor).

Template Parameters:: RESULTSET – Should be any ResultSet<DistanceType>
Returns:: true if the search should be continued, false if the results are sufficient

inline bool makeNode(Derived &obj, NodePtr node, const Offset left, const Offset right, BoundingBox &bbox, Offset &idx, Dimension &cutfeat, DistanceType &cutval)

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
bbox – bounding box used as input for splitting and output for parent node Initialize a freshly-allocated node while building the tree: either turn it into a leaf node (computing the leaf bounding-box) or compute the split plane for an interior node. Shared by the sequential and concurrent builders, which differ only in how they recurse.

Returns:

true if the node became a leaf (no further recursion needed), false if it is an interior node and idx / cutfeat / cutval describe the split plane.

inline void finalizeSplitNode(Derived &obj, NodePtr node, const Dimension cutfeat, const BoundingBox &left_bbox, const BoundingBox &right_bbox, BoundingBox &bbox): After both children of an interior node have been built, record the split planes and expand bbox to the union of the children bounding-boxes. Shared by the sequential and concurrent builders.

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

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
bbox – bounding box used as input for splitting and output for parent node
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 stream.

The set of data points is NOT stored; when reloading, the index object must be constructed with the same dataset. See: examples/saveload_example.cpp