#include <nanoflann.hpp>

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

Collaboration diagram for nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >:

Classes
struct	Interval

struct	Node

Public Types
using	ElementType = typename Distance::ElementType

using	DistanceType = typename Distance::DistanceType

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)

ElementType	dataset_get (const Derived &obj, IndexType element, Dimension component) const
	Helper accessor to the dataset points:

Size	usedMemory (Derived &obj)

void	computeMinMax (const Derived &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem)

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)

Public Attributes
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 IndexType = uint32_t>
class nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >

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

Member Typedef Documentation

◆ BoundingBox

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

using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::BoundingBox = typename array_or_vector<DIM, Interval>::type

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

◆ Dimension

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

using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::Dimension = int32_t

◆ distance_vector_t

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

using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::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"

◆ DistanceType

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

using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::DistanceType = typename Distance::DistanceType

◆ ElementType

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

using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::ElementType = typename Distance::ElementType

◆ NodeConstPtr

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

using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::NodeConstPtr = const Node*

◆ NodePtr

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

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

◆ Offset

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

using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::Offset = typename decltype(vAcc_)::size_type

◆ Size

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

using nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::Size = typename decltype(vAcc_)::size_type

Member Function Documentation

◆ computeInitialDistances()

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

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

inline

◆ computeMinMax()

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

void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::computeMinMax	(	const Derived &	obj,
		Offset	ind,
		Size	count,
		Dimension	element,
		ElementType &	min_elem,
		ElementType &	max_elem
	)

inline

◆ dataset_get()

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

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

inline

Helper accessor to the dataset points:

◆ divideTree()

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

NodePtr nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::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

◆ divideTreeConcurrent()

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

NodePtr nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::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
thread_count	count of std::async threads
mutex	mutex for mempool allocation

◆ freeIndex()

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

void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::freeIndex ( Derived & obj )

inline

Frees the previously-built index. Automatically called within buildIndex().

◆ load_tree()

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

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

inlinestatic

Here is the call graph for this function:

◆ loadIndex()

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

void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::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

Here is the call graph for this function:

◆ middleSplit_()

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

void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::middleSplit_	(	const Derived &	obj,
		const Offset	ind,
		const Size	count,
		Offset &	index,
		Dimension &	cutfeat,
		DistanceType &	cutval,
		const BoundingBox &	bbox
	)

inline

◆ planeSplit()

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

void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::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

◆ save_tree()

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

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

inlinestatic

Here is the call graph for this function:

◆ saveIndex()

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

void nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::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

Here is the call graph for this function:

◆ size()

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

Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::size ( const Derived & obj ) const

inline

Returns number of points in dataset

◆ usedMemory()

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

Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::usedMemory ( Derived & obj )

inline

Computes the inde memory usage Returns: memory used by the index

◆ veclen()

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

Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::veclen ( const Derived & obj )

inline

Returns the length of each point in the dataset

Member Data Documentation

◆ dim_

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

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

Dimensionality of each data point.

◆ leaf_max_size_

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

Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::leaf_max_size_ = 0

◆ n_thread_build_

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

Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::n_thread_build_ = 1

Number of thread for concurrent tree build.

◆ pool_

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

PooledAllocator nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::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.

◆ root_bbox_

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

BoundingBox nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::root_bbox_

The KD-tree used to find neighbours

◆ root_node_

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

NodePtr nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::root_node_ = nullptr

◆ size_

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

Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::size_ = 0

Number of current points in the dataset.

◆ size_at_index_build_

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

Size nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::size_at_index_build_ = 0

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

◆ vAcc_

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

std::vector<IndexType> nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, IndexType >::vAcc_

Array of indices to vectors in the dataset_.

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

src/lib/patchGeneration/nanoflann.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ BoundingBox

◆ Dimension

◆ distance_vector_t

◆ DistanceType

◆ ElementType

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

Member Data Documentation

◆ dim_

◆ leaf_max_size_

◆ n_thread_build_

◆ pool_

◆ root_bbox_

◆ root_node_

◆ size_

◆ size_at_index_build_

◆ vAcc_