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)
Size | size (const Derived &obj) const
Size | veclen (const Derived &obj) const
ElementType | dataset_get (const Derived &obj, IndexType element, Dimension component) const
| Helper accessor to the dataset points:
Size | usedMemory (const Derived &obj) const
void | computeMinMax (const Derived &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) const
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

  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

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

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

  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

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

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

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

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:

- include/nanoflann.hpp