#include <nanoflann.hpp>

Inherited by nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >, nanoflann::KDTreeSingleIndexAdaptor< nanoflann::L2_Simple_Adaptor< double, PointCloud >, PointCloud, 2 >, and nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >.

Data Structures
struct	Interval

struct	Node

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)

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

Definition at line 1010 of file nanoflann.hpp.

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"

Definition at line 1082 of file nanoflann.hpp.

◆ Dimension

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 >::Dimension = int32_t

Definition at line 1033 of file nanoflann.hpp.

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

Definition at line 1086 of file nanoflann.hpp.

◆ DistanceType

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 >::DistanceType = typename Distance::DistanceType

Definition at line 1023 of file nanoflann.hpp.

◆ ElementType

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 >::ElementType = typename Distance::ElementType

Definition at line 1022 of file nanoflann.hpp.

◆ IndexType

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 >::IndexType = index_t

Definition at line 1024 of file nanoflann.hpp.

◆ NodeConstPtr

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 >::NodeConstPtr = const Node*

Definition at line 1061 of file nanoflann.hpp.

◆ NodePtr

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 >::NodePtr = Node*

Definition at line 1060 of file nanoflann.hpp.

◆ Offset

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 >::Offset = typename decltype(vAcc_)::size_type

Definition at line 1031 of file nanoflann.hpp.

◆ Size

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 >::Size = typename decltype(vAcc_)::size_type

Definition at line 1032 of file nanoflann.hpp.

Member Function Documentation

◆ computeInitialDistances()

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

DistanceType nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::computeInitialDistances	(	const Derived &	obj,
		const ElementType *	vec,
		distance_vector_t &	dists ) const

inline

Definition at line 1429 of file nanoflann.hpp.

◆ 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

Definition at line 1127 of file nanoflann.hpp.

Referenced by middleSplit_().

◆ dataset_get()

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

ElementType nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::dataset_get	(	const Derived &	obj,
		IndexType	element,
		Dimension	component ) const

inline

Helper accessor to the dataset points:

Definition at line 1107 of file nanoflann.hpp.

Referenced by nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >::computeBoundingBox(), nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::computeBoundingBox(), computeMinMax(), divideTree(), divideTreeConcurrent(), and planeSplit().

◆ 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

Definition at line 1149 of file nanoflann.hpp.

Referenced by nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >::buildIndex(), nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::buildIndex(), and divideTree().

◆ 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

Definition at line 1224 of file nanoflann.hpp.

Referenced by nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >::buildIndex(), nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::buildIndex(), and divideTreeConcurrent().

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

Definition at line 1015 of file nanoflann.hpp.

Referenced by nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >::buildIndex(), and nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::buildIndex().

◆ load_tree()

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

static void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::load_tree	(	Derived &	obj,
		std::istream &	stream,
		NodePtr &	tree )

inlinestatic

Definition at line 1462 of file nanoflann.hpp.

Referenced by load_tree(), and loadIndex().

◆ 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

Definition at line 1490 of file nanoflann.hpp.

◆ middleSplit_()

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 >::middleSplit_	(	const Derived &	obj,
		const Offset	ind,
		const Size	count,
		Offset &	index,
		Dimension &	cutfeat,
		DistanceType &	cutval,
		const BoundingBox &	bbox )

inline

Definition at line 1320 of file nanoflann.hpp.

Referenced by divideTree(), and divideTreeConcurrent().

◆ 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

Definition at line 1382 of file nanoflann.hpp.

Referenced by middleSplit_().

◆ save_tree()

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

static void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::save_tree	(	const Derived &	obj,
		std::ostream &	stream,
		const NodeConstPtr	tree )

inlinestatic

Definition at line 1454 of file nanoflann.hpp.

Referenced by save_tree(), and saveIndex().

◆ 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

Definition at line 1475 of file nanoflann.hpp.

◆ 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

Definition at line 1101 of file nanoflann.hpp.

Referenced by nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >::init_vind().

◆ 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

Definition at line 1117 of file nanoflann.hpp.

◆ 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

Definition at line 1104 of file nanoflann.hpp.

Field Documentation

◆ dim_

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

Dimension nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::dim_ = 0

Dimensionality of each data point.

Definition at line 1078 of file nanoflann.hpp.

◆ leaf_max_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 >::leaf_max_size_ = 0

Definition at line 1070 of file nanoflann.hpp.

◆ n_thread_build_

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 >::n_thread_build_ = 1

Number of thread for concurrent tree build.

Definition at line 1073 of file nanoflann.hpp.

Referenced by divideTreeConcurrent().

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

Definition at line 1098 of file nanoflann.hpp.

◆ 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

Definition at line 1089 of file nanoflann.hpp.

◆ root_node_

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 >::root_node_ = nullptr

Definition at line 1068 of file nanoflann.hpp.

◆ 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_ = 0

Number of current points in the dataset.

Definition at line 1075 of file nanoflann.hpp.

◆ size_at_index_build_

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_at_index_build_ = 0

Number of points in the dataset when the index was built.

Definition at line 1077 of file nanoflann.hpp.

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

Definition at line 1029 of file nanoflann.hpp.

Referenced by computeMinMax(), and planeSplit().

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

nanoflann.hpp

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Data Fields

Detailed Description

Member Typedef Documentation

◆ BoundingBox

◆ Dimension

◆ distance_vector_t

◆ DistanceType

◆ ElementType

◆ IndexType

◆ NodeConstPtr

◆ NodePtr

◆ Offset

◆ Size

Member Function Documentation

◆ computeInitialDistances()

◆ computeMinMax()

◆ dataset_get()

◆ divideTree()

◆ divideTreeConcurrent()

◆ freeIndex()

◆ load_tree()

◆ loadIndex()

◆ middleSplit_()

◆ planeSplit()

◆ save_tree()

◆ saveIndex()

◆ size()

◆ usedMemory()

◆ veclen()

Field Documentation

◆ dim_

◆ leaf_max_size_

◆ n_thread_build_

◆ pool_

◆ root_bbox_

◆ root_node_

◆ size_

◆ size_at_index_build_

◆ vAcc_