#include <nanoflann.hpp>

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

Classes
struct	Node
struct	Interval

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)
NANOFLANN_NODISCARD Size	size (const Derived &obj) const noexcept
NANOFLANN_NODISCARD Size	veclen (const Derived &obj) const noexcept
ElementType	dataset_get (const Derived &obj, IndexType element, Dimension component) const
	Helper accessor to the dataset points:
NANOFLANN_NODISCARD Size	usedMemory (const Derived &obj) const
void	computeMinMax (const Derived &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) const
NANOFLANN_NODISCARD bool	isActive (IndexType) const
void	computeBoundingBox (BoundingBox &bbox)
template<class RESULTSET>
bool	searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const DistanceType epsError) const
bool	makeNode (Derived &obj, NodePtr node, const Offset left, const Offset right, BoundingBox &bbox, Offset &idx, Dimension &cutfeat, DistanceType &cutval)
void	finalizeSplitNode (Derived &obj, NodePtr node, const Dimension cutfeat, const BoundingBox &left_bbox, const BoundingBox &right_bbox, BoundingBox &bbox)
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_

Static Public Attributes
static constexpr uint32_t	SAVE_MAGIC = 0x4E464C4E

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

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"

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

Member Function Documentation

◆ computeBoundingBox()

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 >::computeBoundingBox ( BoundingBox & bbox )

inline

Computes the bounding box of the points currently in the index. Uses size_ (set by buildIndex before this is called) so the result is correct for both the static and dynamic adaptors.

◆ 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

◆ 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

◆ finalizeSplitNode()

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 >::finalizeSplitNode	(	Derived &	obj,
		NodePtr	node,
		const Dimension	cutfeat,
		const BoundingBox &	left_bbox,
		const BoundingBox &	right_bbox,
		BoundingBox &	bbox )

inline

After both children of an interior node have been built, record the split planes and expand bbox to the union of the children bounding-boxes. Shared by the sequential and concurrent builders.

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

◆ isActive()

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

NANOFLANN_NODISCARD bool nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::isActive ( IndexType ) const

inline

Returns true if the point at index idx should be visited during search. The static adaptor always returns true; the dynamic adaptor overrides this to skip tombstoned (removed) points.

◆ 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 an index previously saved with saveIndex() from a binary stream.

The index object must be constructed associated to the same dataset that was used when building the saved index. See: examples/saveload_example.cpp

Exceptions

std::runtime_error if the stream does not start with the expected magic number (wrong file or corrupt data), if the nanoflann version in the file differs from the current library version, if the saved type sizes (size_t, IndexType, ElementType, DistanceType) do not match the current template instantiation, or if a read error occurs.

Note: See saveIndex() for portability limitations.

See also: saveIndex

◆ makeNode()

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

bool nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::makeNode	(	Derived &	obj,
		NodePtr	node,
		const Offset	left,
		const Offset	right,
		BoundingBox &	bbox,
		Offset &	idx,
		Dimension &	cutfeat,
		DistanceType &	cutval )

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 Initialize a freshly-allocated node while building the tree: either turn it into a leaf node (computing the leaf bounding-box) or compute the split plane for an interior node. Shared by the sequential and concurrent builders, which differ only in how they recurse.

Returns: true if the node became a leaf (no further recursion needed), false if it is an interior node and idx / cutfeat / cutval describe the split plane.

◆ 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

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

The set of data points is NOT stored; when reloading, the index object must be constructed with the same dataset. See: examples/saveload_example.cpp

Note

Portability limitations (by design – fixing them would require a breaking format change):

Files are NOT portable across different endianness (e.g. x86 little-endian vs. big-endian SPARC/PowerPC). No byte-swapping is performed.
Files are NOT portable across 32-bit vs. 64-bit platforms (sizeof(size_t) differs).
Files are NOT portable across different nanoflann versions; loadIndex() throws if the version in the file does not match the library.
Files are NOT portable across different template instantiations (e.g. float vs. double IndexType/ElementType); loadIndex() throws on mismatch.

See also: loadIndex

◆ searchLevel()

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

template<class RESULTSET>

bool nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::searchLevel	(	RESULTSET &	result_set,
		const ElementType *	vec,
		const NodePtr	node,
		DistanceType	mindist,
		distance_vector_t &	dists,
		const DistanceType	epsError ) const

inline

Performs an exact search in the tree starting from a node. Uses the CRTP-dispatched isActive() hook to skip removed points (no-op in the static adaptor, checks treeIndex_ in the dynamic adaptor).

Template Parameters

RESULTSET Should be any ResultSet<DistanceType>

Returns: true if the search should be continued, false if the results are sufficient

◆ size()

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

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

inlinenoexcept

Returns number of points in dataset

◆ usedMemory()

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

NANOFLANN_NODISCARD 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

◆ veclen()

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

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

inlinenoexcept

Returns the length of each point in the dataset. For a fixed-size tree (DIM > 0) this is a compile-time constant; under C++17 the if constexpr lets the compiler drop the runtime read of dim_ entirely. The C++11 path keeps the equivalent ternary.

Member Data Documentation

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

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

◆ SAVE_MAGIC

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

uint32_t nanoflann::KDTreeBaseClass< Derived, Distance, DatasetAdaptor, DIM, index_t >::SAVE_MAGIC = 0x4E464C4E

staticconstexpr

Magic number written at the start of every saveIndex() stream. Spells 'NFLN' in ASCII.

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

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

include/nanoflann.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ BoundingBox

◆ distance_vector_t

Member Function Documentation

◆ computeBoundingBox()

◆ computeMinMax()

◆ divideTreeConcurrent()

◆ finalizeSplitNode()

◆ freeIndex()

◆ isActive()

◆ loadIndex()

◆ makeNode()

◆ planeSplit()

◆ saveIndex()

◆ searchLevel()

◆ size()

◆ usedMemory()

◆ veclen()

Member Data Documentation

◆ pool_

◆ root_bbox_

◆ SAVE_MAGIC

◆ vAcc_