Template Class KDTreeSingleIndexAdaptor

Defined in File nanoflann.hpp

Inheritance Relationships

Base Type

public nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t > (Template Class KDTreeBaseClass)

Class Documentation

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t> class KDTreeSingleIndexAdaptor : public nanoflann::KDTreeBaseClass<KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, -1, uint32_t>, Distance, DatasetAdaptor, -1, uint32_t>

kd-tree static 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 points
  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;
  }

Note

Threading guarantees:

Index build: passing n_thread_build > 1 in the params parallelizes the build using std::async (unless NANOFLANN_NO_THREADS is defined, in which case requesting more than one thread throws).
Queries (findNeighbors, knnSearch, radiusSearch, rknnSearch) are const and thread-safe for concurrent readers: multiple threads may query the same index simultaneously, as long as no thread is concurrently (re)building or modifying it.
The internal PooledAllocator is NOT thread-safe; building an index from multiple threads, or mixing queries with a concurrent build, is not supported.

Template Parameters:

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: nanoflann::metric_L1, nanoflann::metric_L2, nanoflann::metric_L2_Simple, etc.
DIM – Dimensionality of data points (e.g. 3 for 3D points)
IndexType – Will be typically size_t or int

Query methods

template<typename RESULTSET> inline bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams = {}) const

Find set of nearest neighbors to vec[0:dim-1]. Their indices are stored inside the result object.

Params: result = the result object in which the indices of the nearest-neighbors are stored vec = the vector for which to search the nearest neighbors

See also

knnSearch, radiusSearch

Note

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

Template Parameters:: RESULTSET – Should be any ResultSet<DistanceType>
Returns:: True if the requested neighbors could be found.

template<typename RESULTSET> inline NANOFLANN_NODISCARD Size findWithinBox (RESULTSET &result, const BoundingBox &bbox) const

Find all points contained within the specified bounding box. Their indices are stored inside the result object.

Params: result = the result object in which the indices of the points within the bounding box are stored bbox = the bounding box defining the search region

See also

findNeighbors, knnSearch, radiusSearch

Note

The search is inclusive - points on the boundary are included.

Template Parameters:: RESULTSET – Should be any ResultSet<DistanceType>
Returns:: Number of points found within the bounding box.

inline NANOFLANN_NODISCARD Size knnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const

Find the “num_closest” nearest neighbors to the query_point[0:dim-1]. Their indices and distances are stored in the provided pointers to array/vector.

See also

radiusSearch, findNeighbors

Note

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

Note

Only the first N entries in out_indices and out_distances will be valid. Return is less than num_closest only if the number of elements in the tree is less than num_closest.

Returns:: Number N of valid points in the result set.

inline NANOFLANN_NODISCARD Size radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const

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.

Note

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

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

template<class SEARCH_CALLBACK> inline NANOFLANN_NODISCARD Size radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const

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

inline NANOFLANN_NODISCARD Size rknnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const

Find the N closest neighbors to query_point[0:dim-1] that are also within the given maximum radius. Results are stored in the provided output arrays; previous contents are overwritten.

See also

radiusSearch, findNeighbors

Note

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

Note

Only the first N entries in out_indices and out_distances will be valid.

Returns:: Number of valid points written (at most num_closest). May be less if fewer than num_closest points lie within the radius.

Public Types

using Base = typename nanoflann::KDTreeBaseClass<nanoflann::KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>, Distance, DatasetAdaptor, DIM, index_t>

using Offset = typename Base::Offset

using Size = typename Base::Size

using Dimension = typename Base::Dimension

using ElementType = typename Base::ElementType

using DistanceType = typename Base::DistanceType

using IndexType = typename Base::IndexType

using Node = typename Base::Node

using NodePtr = Node*

using Interval = typename Base::Interval

using BoundingBox = typename Base::BoundingBox: Define “BoundingBox” as a fixed-size or variable-size container depending on “DIM”

using distance_vector_t = typename Base::distance_vector_t: Define “distance_vector_t” as a fixed-size or variable-size container depending on “DIM”

Public Functions

explicit KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>&) = delete: Deleted copy constructor

template<class ...Args> inline explicit KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params, Args&&... args)

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 dataset, 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.

Note that there is a variable number of optional additional parameters which will be forwarded to the metric class constructor. Refer to example examples/pointcloud_custom_metric.cpp for a use case.

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

inline explicit KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params = {})

inline void buildIndex(): Builds the index

inline void init_vind(): Make sure the auxiliary list vind has the same size as the current dataset, and re-generate if size has changed.

inline bool contains(const BoundingBox &bbox, IndexType idx) const

inline void saveIndex(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

See also

loadIndex

inline void loadIndex(std::istream &stream)

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

Public Members

const DatasetAdaptor &dataset_: The data source used by this index

const KDTreeSingleIndexAdaptorParams indexParams

Distance distance_