Loading...
Searching...
No Matches
nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType > Class Template Reference
nanoflann C++ library for KD-trees » KD-tree classes and adaptors

`#include <nanoflann.hpp>`

Inheritance diagram for nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >:

## Public Types

using | Base
using | ElementType = typename Base::ElementType
using | DistanceType = typename Base::DistanceType
using | Offset = typename Base::Offset
using | Size = typename Base::Size
using | Dimension = typename Base::Dimension
using | Node = typename Base::Node
using | NodePtr = Node*
using | Interval = typename Base::Interval
using | BoundingBox = typename Base::BoundingBox
using | distance_vector_t = typename Base::distance_vector_t
Public Types inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
using | ElementType
using | DistanceType
using | IndexType
using | Offset
using | Size
using | Dimension
using | NodePtr
using | NodeConstPtr
using | BoundingBox
using | distance_vector_t

## Public Member Functions

| KDTreeSingleIndexDynamicAdaptor_ (const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
| KDTreeSingleIndexDynamicAdaptor_ (const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
KDTreeSingleIndexDynamicAdaptor_ | operator= (const KDTreeSingleIndexDynamicAdaptor_ &rhs)
void | buildIndex ()
void | computeBoundingBox (BoundingBox &bbox)
template<class RESULTSET>
void | searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
void | saveIndex (std::ostream &stream)
void | loadIndex (std::istream &stream)
Query methods
template<typename RESULTSET>
bool | findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Size | knnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Size | radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
template<class SEARCH_CALLBACK>
Size | radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
void | freeIndex (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj)
Size | size (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
Size | veclen (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
ElementType | dataset_get (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, IndexType element, Dimension component) const
| Helper accessor to the dataset points:
Size | usedMemory (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
void | computeMinMax (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) const
NodePtr | divideTree (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox)
NodePtr | divideTreeConcurrent (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
void | middleSplit_ (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
void | planeSplit (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
DistanceType | computeInitialDistances (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, const ElementType *vec, distance_vector_t &dists) const
void | saveIndex (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream) const
void | loadIndex (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream)

## Public Attributes

const DatasetAdaptor & | dataset_
| The source of our data.
KDTreeSingleIndexAdaptorParams | index_params_
std::vector< int > & | treeIndex_
Distance | distance_
Public Attributes inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
std::vector< IndexType > | vAcc_
NodePtr | root_node_
Size | leaf_max_size_
Size | n_thread_build_
| Number of thread for concurrent tree build.
Size | size_
| Number of current points in the dataset.
Size | size_at_index_build_
| Number of points in the dataset when the index was built.
Dimension | dim_
| Dimensionality of each data point.
BoundingBox | root_bbox_
PooledAllocator | pool_

## Additional Inherited Members

Static Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
static void | save_tree (const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream, const NodeConstPtr tree)
static void | load_tree (KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream, NodePtr &tree)

## Detailed Description

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>
class nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >

kd-tree dynamic index

Contains the k-d trees and other information for indexing a set of points for nearest-neighbor matching.

The class "DatasetAdaptor" must provide the following interface (can be non-virtual, inlined methods):

// Must return the number of data poins
size_t kdtree_get_point_count() const { ... }
// Must return the dim'th component of the idx'th point in the class:
T kdtree_get_pt(const size_t idx, const size_t dim) const { ... }
// Optional bounding-box computation: return false to default to a standard
bbox computation loop.
// Return true if the BBOX was already computed by the class and returned
in "bb" so it can be avoided to redo it again.
// Look at bb.size() to find out the expected dimensionality (e.g. 2 or 3
for point clouds) template <class BBOX> bool kdtree_get_bbox(BBOX &bb) const
{
bb[0].low = ...; bb[0].high = ...; // 0th dimension limits
bb[1].low = ...; bb[1].high = ...; // 1st dimension limits
...
return true;
}

Template Parameters

  DatasetAdaptor | The user-provided adaptor (see comments above).
  Distance | The distance metric to use: nanoflann::metric_L1, nanoflann::metric_L2, nanoflann::metric_L2_Simple, etc.
  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

## Base

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

using nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::Base

Initial value:
typename nanoflann::KDTreeBaseClass<
nanoflann::KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM, IndexType>,
Distance, DatasetAdaptor, DIM, IndexType>
nanoflann::KDTreeBaseClass
Definition nanoflann.hpp:1037
nanoflann::KDTreeSingleIndexDynamicAdaptor_
Definition nanoflann.hpp:2133

## BoundingBox

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

using nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::BoundingBox = typename Base::BoundingBox

Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM"

## distance_vector_t

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

using nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::distance_vector_t = typename Base::distance_vector_t

Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM"

## Constructor & Destructor Documentation

## KDTreeSingleIndexDynamicAdaptor_() [1/2]

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

nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexDynamicAdaptor_ | ( | const Dimension | dimensionality,
|  | const DatasetAdaptor & | inputData,
|  | std::vector< int > & | treeIndex,
|  | const KDTreeSingleIndexAdaptorParams & | params = KDTreeSingleIndexAdaptorParams() )

inline

KDTree constructor

Refer to docs in README.md or online in https://github.com/jlblancoc/nanoflann

The KD-Tree point dimension (the length of each point in the datase, e.g. 3 for 3D points) is determined by means of:

- The DIM template parameter if >0 (highest priority)
- Otherwise, the dimensionality parameter of this constructor.

Parameters

  inputData | Dataset with the input features. Its lifetime must be equal or longer than that of the instance of this class.
  params | Basically, the maximum leaf node size

## KDTreeSingleIndexDynamicAdaptor_() [2/2]

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

nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexDynamicAdaptor_ | ( | const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType > & | rhs | ) |

default

Explicitly default the copy constructor

## Member Function Documentation

## buildIndex()

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

void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::buildIndex | ( |  | ) |

inline

Builds the index

## findNeighbors()

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

bool nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::findNeighbors | ( | RESULTSET & | result,
|  | const ElementType * | vec,
|  | const SearchParameters & | searchParams = {} ) const

inline

Find set of nearest neighbors to vec[0:dim-1]. Their indices are stored inside the result object. This is the core search function, all others are wrappers around this one.

Parameters

  result | The result object in which the indices of the nearest-neighbors are stored.
  vec | The vector of the query point for which to search the nearest neighbors.
  searchParams | Optional parameters for the search.

Template Parameters

  RESULTSET | Should be any ResultSet<DistanceType>

Returns
  True if the requested neighbors could be found.

See also
  knnSearch(), radiusSearch(), radiusSearchCustomCallback()

Note
  If L2 norms are used, all returned distances are actually squared distances.

## knnSearch()

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

Size nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::knnSearch | ( | const ElementType * | query_point,
|  | const Size | num_closest,
|  | IndexType * | out_indices,
|  | DistanceType * | out_distances,
|  | const SearchParameters & | searchParams = {} ) const

inline

Find the "num_closest" nearest neighbors to the query_point[0:dim-1]. Their indices are stored inside the result object.

See also
  radiusSearch, findNeighbors

Returns
  Number N of valid points in the result set.

Note
  If L2 norms are used, all returned distances are actually squared distances.
  Only the first N entries in out_indices and out_distances will be valid. Return may be less than num_closest only if the number of elements in the tree is less than num_closest.

## loadIndex()

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

void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::loadIndex | ( | 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

## operator=()

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

KDTreeSingleIndexDynamicAdaptor_ nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::operator= | ( | const KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType > & | rhs | ) |

inline

Assignment operator definiton

## radiusSearch()

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

Size nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::radiusSearch | ( | const ElementType * | query_point,
|  | const DistanceType & | radius,
|  | std::vector< ResultItem< IndexType, DistanceType > > & | IndicesDists,
|  | const SearchParameters & | searchParams = {} ) const

inline

Find all the neighbors to query_point[0:dim-1] within a maximum radius. The output is given as a vector of pairs, of which the first element is a point index and the second the corresponding distance. Previous contents of IndicesDists are cleared.

If searchParams.sorted==true, the output list is sorted by ascending distances.

For a better performance, it is advisable to do a .reserve() on the vector if you have any wild guess about the number of expected matches.

See also
  knnSearch, findNeighbors, radiusSearchCustomCallback

Returns
  The number of points within the given radius (i.e. indices.size() or dists.size() )

Note
  If L2 norms are used, search radius and all returned distances are actually squared distances.

## radiusSearchCustomCallback()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>
template<class SEARCH_CALLBACK>

Size nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::radiusSearchCustomCallback | ( | const ElementType * | query_point,
|  | SEARCH_CALLBACK & | resultSet,
|  | const SearchParameters & | searchParams = {} ) const

inline

Just like radiusSearch() but with a custom callback class for each point found in the radius of the query. See the source of RadiusResultSet<> as a start point for your own classes.

See also
  radiusSearch

## saveIndex()

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

void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::saveIndex | ( | std::ostream & | stream | ) |

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

## searchLevel()

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

void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::searchLevel | ( | RESULTSET & | result_set,
|  | const ElementType * | vec,
|  | const NodePtr | node,
|  | DistanceType | mindist,
|  | distance_vector_t & | dists,
|  | const float | epsError ) const

inline

Performs an exact search in the tree starting from a node.

Template Parameters

  RESULTSET | Should be any ResultSet<DistanceType>

## Member Data Documentation

## dataset_

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

const DatasetAdaptor& nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::dataset_

The source of our data.

The dataset used by this index

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

- include/nanoflann.hpp