#include <nanoflann.hpp>

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

Public Types
using	Base
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
using	distance_vector_t = typename Base::distance_vector_t
Public Types inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< 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
	KDTreeSingleIndexAdaptor (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > &)=delete
template<class... Args>
	KDTreeSingleIndexAdaptor (const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params, Args &&... args)
	KDTreeSingleIndexAdaptor (const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params={})
void	buildIndex ()
void	init_vind ()
bool	contains (const BoundingBox &bbox, IndexType idx) const
void	saveIndex (std::ostream &stream) const
void	loadIndex (std::istream &stream)
Query methods
template<typename RESULTSET>
bool	findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
template<typename RESULTSET>
NANOFLANN_NODISCARD Size	findWithinBox (RESULTSET &result, const BoundingBox &bbox) const
NANOFLANN_NODISCARD Size	knnSearch (const ElementType query_point, const Size num_closest, IndexType out_indices, DistanceType *out_distances) const
NANOFLANN_NODISCARD Size	radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
template<class SEARCH_CALLBACK>
NANOFLANN_NODISCARD Size	radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
NANOFLANN_NODISCARD Size	rknnSearch (const ElementType query_point, const Size num_closest, IndexType out_indices, DistanceType *out_distances, const DistanceType &radius) const
Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
void	freeIndex (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj)
NANOFLANN_NODISCARD Size	size (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const noexcept
NANOFLANN_NODISCARD Size	veclen (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const noexcept
ElementType	dataset_get (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, IndexType element, Dimension component) const
	Helper accessor to the dataset points:
NANOFLANN_NODISCARD Size	usedMemory (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
void	computeMinMax (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) const
NANOFLANN_NODISCARD bool	isActive (IndexType) const
void	computeBoundingBox (BoundingBox &bbox)
bool	searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const DistanceType epsError) const
bool	makeNode (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, NodePtr node, const Offset left, const Offset right, BoundingBox &bbox, Offset &idx, Dimension &cutfeat, DistanceType &cutval)
void	finalizeSplitNode (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, NodePtr node, const Dimension cutfeat, const BoundingBox &left_bbox, const BoundingBox &right_bbox, BoundingBox &bbox)
NodePtr	divideTree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox)
NodePtr	divideTreeConcurrent (KDTreeSingleIndexAdaptor< 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 KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
void	planeSplit (const KDTreeSingleIndexAdaptor< 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 KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const ElementType *vec, distance_vector_t &dists) const
void	saveIndex (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream) const
void	loadIndex (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream)

Public Attributes
const DatasetAdaptor &	dataset_
const KDTreeSingleIndexAdaptorParams	indexParams
Distance	distance_
Public Attributes inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< 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< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
static void	save_tree (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream, const NodeConstPtr tree)
static void	load_tree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream, NodePtr &tree)
Static Public Attributes inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
static constexpr uint32_t	SAVE_MAGIC

Detailed Description

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
class nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_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;
  }

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

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.

Member Typedef Documentation

◆ Base

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

using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::Base

Initial value:

 typename nanoflann::KDTreeBaseClass<
        nanoflann::KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>, Distance,
        DatasetAdaptor, DIM, index_t>

◆ BoundingBox

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

using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::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 index_t = uint32_t>

using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::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

◆ KDTreeSingleIndexAdaptor() [1/2]

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

nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::KDTreeSingleIndexAdaptor ( const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > & )

explicitdelete

Deleted copy constructor

◆ KDTreeSingleIndexAdaptor() [2/2]

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

template<class... Args>

nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::KDTreeSingleIndexAdaptor	(	const Dimension	dimensionality,
		const DatasetAdaptor &	inputData,
		const KDTreeSingleIndexAdaptorParams &	params,
		Args &&...	args )

inlineexplicit

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.

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

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.

Member Function Documentation

◆ buildIndex()

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

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::buildIndex ( )

inline

Builds the index

◆ findNeighbors()

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

template<typename RESULTSET>

bool nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::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.

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

Template Parameters

RESULTSET Should be any ResultSet<DistanceType>

Returns: True if the requested neighbors could be found.

See also: knnSearch, radiusSearch

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

◆ findWithinBox()

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

template<typename RESULTSET>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::findWithinBox	(	RESULTSET &	result,
		const BoundingBox &	bbox ) const

inline

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

Template Parameters

RESULTSET Should be any ResultSet<DistanceType>

Returns: Number of points found within the bounding box.

See also: findNeighbors, knnSearch, radiusSearch

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

◆ init_vind()

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

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::init_vind ( )

inline

Make sure the auxiliary list vind has the same size as the current dataset, and re-generate if size has changed.

◆ knnSearch()

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

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::knnSearch	(	const ElementType *	query_point,
		const Size	num_closest,
		IndexType *	out_indices,
		DistanceType *	out_distances ) const

inline

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

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 is 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 index_t = uint32_t>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::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

◆ radiusSearch()

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

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::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 index_t = uint32_t>

template<class SEARCH_CALLBACK>

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::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

◆ rknnSearch()

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

NANOFLANN_NODISCARD Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::rknnSearch	(	const ElementType *	query_point,
		const Size	num_closest,
		IndexType *	out_indices,
		DistanceType *	out_distances,
		const DistanceType &	radius ) const

inline

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

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

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.

◆ saveIndex()

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

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::saveIndex ( 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

Member Data Documentation

◆ dataset_

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

const DatasetAdaptor& nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::dataset_

The data source used by this index

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

include/nanoflann.hpp

Public Types

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base

◆ BoundingBox

◆ distance_vector_t

Constructor & Destructor Documentation

◆ KDTreeSingleIndexAdaptor() [1/2]

◆ KDTreeSingleIndexAdaptor() [2/2]

Member Function Documentation

◆ buildIndex()

◆ findNeighbors()

◆ findWithinBox()

◆ init_vind()

◆ knnSearch()

◆ loadIndex()

◆ radiusSearch()

◆ radiusSearchCustomCallback()

◆ rknnSearch()

◆ saveIndex()

Member Data Documentation

◆ dataset_