Loading...
Searching...
No Matches
nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t > Class Template Reference
nanoflann C++ library for KD-trees

`#include <nanoflann.hpp>`

Inheritance diagram for nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >:

## Classes

struct | Node
struct | Interval

## 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)
NANOFLANN_NODISCARD Size | size (const Derived &obj) const noexcept
NANOFLANN_NODISCARD Size | veclen (const Derived &obj) const noexcept
ElementType | dataset_get (const Derived &obj, IndexType element, Dimension component) const
| Helper accessor to the dataset points:
NANOFLANN_NODISCARD Size | usedMemory (const Derived &obj) const
void | computeMinMax (const Derived &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) const
NANOFLANN_NODISCARD bool | isActive (IndexType) const
void | computeBoundingBox (BoundingBox &bbox)
template<class RESULTSET>
bool | searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const DistanceType epsError) const
bool | makeNode (Derived &obj, NodePtr node, const Offset left, const Offset right, BoundingBox &bbox, Offset &idx, Dimension &cutfeat, DistanceType &cutval)
void | finalizeSplitNode (Derived &obj, NodePtr node, const Dimension cutfeat, const BoundingBox &left_bbox, const BoundingBox &right_bbox, BoundingBox &bbox)
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_

## Static Public Attributes

static constexpr uint32_t | SAVE_MAGIC = 0x4E464C4E

## 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

  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*)

## 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

## computeBoundingBox()

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 >::computeBoundingBox | ( | BoundingBox & | bbox | ) |

inline

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.

## computeMinMax()

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 >::computeMinMax | ( | const Derived & | obj,
|  | Offset | ind,
|  | Size | count,
|  | Dimension | element,
|  | ElementType & | min_elem,
|  | ElementType & | max_elem ) const

inline

Compute the minimum and maximum element values in the specified dimension

## 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

  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

## finalizeSplitNode()

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 >::finalizeSplitNode | ( | Derived & | obj,
|  | NodePtr | node,
|  | const Dimension | cutfeat,
|  | const BoundingBox & | left_bbox,
|  | const BoundingBox & | right_bbox,
|  | BoundingBox & | bbox )

inline

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.

## 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().

## isActive()

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

NANOFLANN_NODISCARD bool nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::isActive | ( | IndexType |  | ) | const

inline

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.

## 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 an index previously saved with saveIndex() from a binary stream.

The index object must be constructed associated to the same dataset that was used when building the saved index. See: examples/saveload_example.cpp

Exceptions

  std::runtime_error | if the stream does not start with the expected magic number (wrong file or corrupt data), if the nanoflann version in the file differs from the current library version, if the saved type sizes (size_t, IndexType, ElementType, DistanceType) do not match the current template instantiation, or if a read error occurs.

Note
  See saveIndex() for portability limitations.

See also
  saveIndex

## makeNode()

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

bool nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::makeNode | ( | Derived & | obj,
|  | NodePtr | node,
|  | const Offset | left,
|  | const Offset | right,
|  | BoundingBox & | bbox,
|  | Offset & | idx,
|  | Dimension & | cutfeat,
|  | DistanceType & | cutval )

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

  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.

## 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 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

Note
  Portability limitations (by design – fixing them would require a breaking format change):
  - Files are NOT portable across different endianness (e.g. x86 little-endian vs. big-endian SPARC/PowerPC). No byte-swapping is performed.
  - Files are NOT portable across 32-bit vs. 64-bit platforms (sizeof(size_t) differs).
  - Files are NOT portable across different nanoflann versions; loadIndex() throws if the version in the file does not match the library.
  - Files are NOT portable across different template instantiations (e.g. float vs. double IndexType/ElementType); loadIndex() throws on mismatch.

See also
  loadIndex

## searchLevel()

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

bool nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::searchLevel | ( | RESULTSET & | result_set,
|  | const ElementType * | vec,
|  | const NodePtr | node,
|  | DistanceType | mindist,
|  | distance_vector_t & | dists,
|  | const DistanceType | epsError ) const

inline

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

## size()

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

NANOFLANN_NODISCARD Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::size | ( | const Derived & | obj | ) | const

inline noexcept

Returns number of points in dataset

## usedMemory()

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

NANOFLANN_NODISCARD Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::usedMemory | ( | const Derived & | obj | ) | const

inline

Computes the index 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>

NANOFLANN_NODISCARD Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::veclen | ( | const Derived & | obj | ) | const

inline 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.

## 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 neighbors

## SAVE_MAGIC

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

uint32_t nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::SAVE_MAGIC = 0x4E464C4E

static constexpr

Magic number written at the start of every saveIndex() stream. Spells 'NFLN' in ASCII.

## 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:

- include/nanoflann.hpp