Detailed Description

template<typename Distance, class DatasetAdaptor, int DIM = -1>
class nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >

kd-tree 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
   inline size_t kdtree_get_point_count() const { ... }

   // Must return the Euclidean (L2) distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
   inline float kdtree_distance(const float *p1, const size_t idx_p2,size_t size) const { ... }

   // Must return the dim'th component of the idx'th point in the class:
   inline num_t kdtree_get_pt(const size_t idx, int 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;
   }

Definition at line 579 of file nanoflann.hpp.

#include <mrpt/otherlibs/nanoflann/nanoflann.hpp>

List of all members.

Classes
struct	BranchStruct
	This record represents a branch point when finding neighbors in the tree. More...
struct	Interval
struct	Node
Public Member Functions
	KDTreeSingleIndexAdaptor (const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
	KDTree constructor.
	~KDTreeSingleIndexAdaptor ()
	Standard destructor.
void	buildIndex ()
	Builds the index.
size_t	size () const
	Returns size of index.
size_t	veclen () const
	Returns the length of an index feature.
int	usedMemory () const
	Computes the inde memory usage Returns: memory used by the index.
Query methods
template<typename RESULTSET >
void	findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
	Find set of nearest neighbors to vec[0:dim-1].
void	knnSearch (const ElementType query_point, int num_closest, int out_indices, ElementType *out_distances_sq, const int nChecks=10) const
	Find the "num_closest" nearest neighbors to the query_point[0:dim-1].
size_t	radiusSearch (const ElementType *query_point, const DistanceType radius, std::vector< std::pair< int, DistanceType > > &IndicesDists, const SearchParams &searchParams) const
	Find all the neighbors to query_point[0:dim-1] within a maximum radius.
Public Attributes
Distance	distance
Private Types
typedef Distance::ElementType	ElementType
typedef Distance::ResultType	DistanceType
typedef Node *	NodePtr
typedef std::vector< Interval >	BoundingBox
typedef BranchStruct< NodePtr, DistanceType >	BranchSt
typedef BranchSt *	Branch
Private Member Functions
ElementType	dataset_get (size_t idx, int component) const
	Helper accessor to the dataset points:
void	save_tree (FILE *stream, NodePtr tree)
void	load_tree (FILE *stream, NodePtr &tree)
void	computeBoundingBox (BoundingBox &bbox)
NodePtr	divideTree (int left, int right, BoundingBox &bbox)
	Create a tree node that subdivides the list of vecs from vind[first] to vind[last].
void	computeMinMax (int *ind, int count, int element, ElementType &min_elem, ElementType &max_elem)
void	middleSplit (int *ind, int count, int &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
void	middleSplit_ (int *ind, int count, int &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
void	planeSplit (int *ind, int count, int cutfeat, DistanceType cutval, int &lim1, int &lim2)
	Subdivide the list of points by a plane perpendicular on axe corresponding to the 'cutfeat' dimension at 'cutval' position.
DistanceType	computeInitialDistances (const ElementType *vec, std::vector< DistanceType > &dists) const
template<class RESULTSET >
void	searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, std::vector< DistanceType > &dists, const float epsError, int &count_leaf) const
	Performs an exact search in the tree starting from a node.
void	saveIndex (FILE *stream)
void	loadIndex (FILE *stream)
Private Attributes
std::vector< int >	vind
	Array of indices to vectors in the dataset.
int	leaf_max_size_
const DatasetAdaptor &	dataset
	The dataset used by this index.
const KDTreeSingleIndexAdaptorParams	index_params
int	size_
int	dim
NodePtr	root_node
	Array of k-d trees used to find neighbours.
BoundingBox	root_bbox
PooledAllocator	pool
	Pooled memory allocator.

Member Typedef Documentation

template<typename Distance , class DatasetAdaptor , int DIM = -1>

typedef std::vector<Interval> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::BoundingBox [private]

Definition at line 639 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

typedef BranchSt* nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Branch [private]

Definition at line 666 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

typedef BranchStruct<NodePtr, DistanceType> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::BranchSt [private]

Definition at line 665 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

typedef Distance::ResultType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::DistanceType [private]

Definition at line 582 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

typedef Distance::ElementType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::ElementType [private]

Definition at line 581 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

typedef Node* nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::NodePtr [private]

Definition at line 631 of file nanoflann.hpp.

Constructor & Destructor Documentation

template<typename Distance , class DatasetAdaptor , int DIM = -1>

nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::KDTreeSingleIndexAdaptor	(	const int	dimensionality,
		const DatasetAdaptor &	inputData,
		const KDTreeSingleIndexAdaptorParams &	params = `KDTreeSingleIndexAdaptorParams()`
	)		`[inline]`

KDTree constructor.

Params: inputData = dataset with the input features params = parameters passed to the kdtree algorithm

Definition at line 690 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::~KDTreeSingleIndexAdaptor ( ) [inline]

Standard destructor.

Definition at line 711 of file nanoflann.hpp.

Member Function Documentation

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::buildIndex ( ) [inline]

Builds the index.

Definition at line 718 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::computeBoundingBox ( BoundingBox & bbox ) [inline, private]

Definition at line 845 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

DistanceType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::computeInitialDistances	(	const ElementType *	vec,
		std::vector< DistanceType > &	dists
	)		const `[inline, private]`

Definition at line 1064 of file nanoflann.hpp.

References mrpt::math::distance().

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::computeMinMax	(	int *	ind,
		int	count,
		int	element,
		ElementType &	min_elem,
		ElementType &	max_elem
	)		`[inline, private]`

Definition at line 928 of file nanoflann.hpp.

References nanoflann::KNNResultSet< DistanceType >::count.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

ElementType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::dataset_get	(	size_t	idx,
		int	component
	)		const `[inline, private]`

Helper accessor to the dataset points:

Definition at line 815 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

NodePtr nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::divideTree	(	int	left,
		int	right,
		BoundingBox &	bbox
	)		`[inline, private]`

Create a tree node that subdivides the list of vecs from vind[first] to vind[last].

The routine is called recursively on each sublist. Place a pointer to this new tree node in the location pTree.

Params: pTree = the new node to create first = index of the first vector last = index of the last vector

Definition at line 878 of file nanoflann.hpp.

References nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::child1, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::child2, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::lr, and nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::sub.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

template<typename RESULTSET >

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::findNeighbors	(	RESULTSET &	result,
		const ElementType *	vec,
		const SearchParams &	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 maxCheck = the maximum number of restarts (in a best-bin-first manner)

Template Parameters:

RESULTSET Should be any ResultSet<DistanceType>

See also:: knnSearch, radiusSearch

Definition at line 765 of file nanoflann.hpp.

References nanoflann::KNNResultSet< DistanceType >::dists, and nanoflann::SearchParams::eps.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::knnSearch	(	const ElementType *	query_point,
		int	num_closest,
		int *	out_indices,
		ElementType *	out_distances_sq,
		const int	nChecks = `10`
	)		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

Definition at line 780 of file nanoflann.hpp.

References nanoflann::KNNResultSet< DistanceType >::init().

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::load_tree	(	FILE *	stream,
		NodePtr &	tree
	)		`[inline, private]`

Definition at line 832 of file nanoflann.hpp.

References nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::child1, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::child2, and nanoflann::load_value().

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::loadIndex ( FILE * stream ) [inline, private]

Definition at line 1147 of file nanoflann.hpp.

References nanoflann::load_value().

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::middleSplit	(	int *	ind,
		int	count,
		int &	index,
		int &	cutfeat,
		DistanceType &	cutval,
		const BoundingBox &	bbox
	)		`[inline, private]`

Definition at line 939 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::middleSplit_	(	int *	ind,
		int	count,
		int &	index,
		int &	cutfeat,
		DistanceType &	cutval,
		const BoundingBox &	bbox
	)		`[inline, private]`

Definition at line 984 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::planeSplit	(	int *	ind,
		int	count,
		int	cutfeat,
		DistanceType	cutval,
		int &	lim1,
		int &	lim2
	)		`[inline, private]`

Subdivide the list of points by a plane perpendicular on axe 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 1035 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::radiusSearch	(	const ElementType *	query_point,
		const DistanceType	radius,
		std::vector< std::pair< int, DistanceType > > &	IndicesDists,
		const SearchParams &	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

Returns:: The number of points within the given radius (i.e. indices.size() or dists.size() )

Definition at line 799 of file nanoflann.hpp.

References nanoflann::RadiusResultSet< DistanceType >::size(), and nanoflann::SearchParams::sorted.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::save_tree	(	FILE *	stream,
		NodePtr	tree
	)		`[inline, private]`

Definition at line 820 of file nanoflann.hpp.

References nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::child1, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::child2, and nanoflann::save_value().

template<typename Distance , class DatasetAdaptor , int DIM = -1>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::saveIndex ( FILE * stream ) [inline, private]

Definition at line 1137 of file nanoflann.hpp.

References nanoflann::save_value().

template<typename Distance , class DatasetAdaptor , int DIM = -1>

template<class RESULTSET >

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::searchLevel	(	RESULTSET &	result_set,
		const ElementType *	vec,
		const NodePtr	node,
		DistanceType	mindistsq,
		std::vector< DistanceType > &	dists,
		const float	epsError,
		int &	count_leaf
	)		const `[inline, private]`

Performs an exact search in the tree starting from a node.

Template Parameters:

RESULTSET Should be any ResultSet<DistanceType>

Definition at line 1087 of file nanoflann.hpp.

References nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::child1, nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::child2, mrpt::math::distance(), nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::lr, and nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::Node::sub.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::size ( ) const [inline]

Returns size of index.

Definition at line 727 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

int nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::usedMemory ( ) const [inline]

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

Definition at line 744 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::veclen ( ) const [inline]

Returns the length of an index feature.

Definition at line 735 of file nanoflann.hpp.

Member Data Documentation

template<typename Distance , class DatasetAdaptor , int DIM = -1>

const DatasetAdaptor& nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::dataset [private]

The dataset used by this index.

The source of our data

Definition at line 595 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

int nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::dim [private]

Definition at line 600 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

Distance nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::distance

Definition at line 681 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

const KDTreeSingleIndexAdaptorParams nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::index_params [private]

Definition at line 597 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

int nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::leaf_max_size_ [private]

Definition at line 589 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

PooledAllocator nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::pool [private]

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 677 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

BoundingBox nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::root_bbox [private]

Definition at line 668 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

NodePtr nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::root_node [private]

Array of k-d trees used to find neighbours.

Definition at line 664 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

int nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::size_ [private]

Definition at line 599 of file nanoflann.hpp.

template<typename Distance , class DatasetAdaptor , int DIM = -1>

std::vector<int> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >::vind [private]

Array of indices to vectors in the dataset.

Definition at line 587 of file nanoflann.hpp.

Detailed Description

template<typename Distance, class DatasetAdaptor, int DIM = -1> class nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >

Classes

Public Member Functions

Public Attributes

Private Types

Private Member Functions

Private Attributes

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename Distance, class DatasetAdaptor, int DIM = -1>
class nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM >