#include <nanoflann.hpp>

Inherits nanoflann::KDTreeBaseClass< KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >.

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)

Data Fields
const DatasetAdaptor &	dataset_
	The source of our data.

KDTreeSingleIndexAdaptorParams	index_params_

std::vector< int > &	treeIndex_

Distance	distance_

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

Definition at line 2022 of file nanoflann.hpp.

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>

Definition at line 2040 of file nanoflann.hpp.

◆ 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"

Definition at line 2058 of file nanoflann.hpp.

◆ Dimension

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

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

Definition at line 2050 of file nanoflann.hpp.

◆ 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"

Definition at line 2062 of file nanoflann.hpp.

◆ DistanceType

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

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

Definition at line 2046 of file nanoflann.hpp.

◆ ElementType

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

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

Definition at line 2045 of file nanoflann.hpp.

◆ Interval

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

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

Definition at line 2055 of file nanoflann.hpp.

◆ Node

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

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

Definition at line 2052 of file nanoflann.hpp.

◆ NodePtr

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

using nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::NodePtr = Node*

Definition at line 2053 of file nanoflann.hpp.

◆ Offset

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

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

Definition at line 2048 of file nanoflann.hpp.

◆ Size

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

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

Definition at line 2049 of file nanoflann.hpp.

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

Definition at line 2079 of file nanoflann.hpp.

◆ 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

Definition at line 2130 of file nanoflann.hpp.

◆ computeBoundingBox()

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

void nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::computeBoundingBox ( BoundingBox & bbox )

inline

Definition at line 2273 of file nanoflann.hpp.

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

Definition at line 2180 of file nanoflann.hpp.

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

Definition at line 2214 of file nanoflann.hpp.

◆ 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

Definition at line 2394 of file nanoflann.hpp.

Referenced by 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

Definition at line 2111 of file nanoflann.hpp.

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

Definition at line 2244 of file nanoflann.hpp.

◆ 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

Definition at line 2262 of file nanoflann.hpp.

◆ 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

Definition at line 2387 of file nanoflann.hpp.

Referenced by saveIndex().

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

Definition at line 2312 of file nanoflann.hpp.

Field 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

Definition at line 2032 of file nanoflann.hpp.

◆ distance_

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

Distance nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::distance_

Definition at line 2038 of file nanoflann.hpp.

◆ index_params_

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

KDTreeSingleIndexAdaptorParams nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::index_params_

Definition at line 2034 of file nanoflann.hpp.

Referenced by operator=().

◆ treeIndex_

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

std::vector<int>& nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::treeIndex_

Definition at line 2036 of file nanoflann.hpp.

Referenced by operator=().

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

nanoflann.hpp

Public Types

Public Member Functions

Data Fields

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base

◆ BoundingBox

◆ Dimension

◆ distance_vector_t

◆ DistanceType

◆ ElementType

◆ Interval

◆ Node

◆ NodePtr

◆ Offset

◆ Size

Constructor & Destructor Documentation

◆ KDTreeSingleIndexDynamicAdaptor_() [1/2]

◆ KDTreeSingleIndexDynamicAdaptor_() [2/2]

Member Function Documentation

◆ buildIndex()

◆ computeBoundingBox()

◆ findNeighbors()

◆ knnSearch()

◆ loadIndex()

◆ operator=()

◆ radiusSearch()

◆ radiusSearchCustomCallback()

◆ saveIndex()

◆ searchLevel()

Field Documentation

◆ dataset_

◆ distance_

◆ index_params_

◆ treeIndex_