Detailed Description

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;
   }

#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

typedef std::vector<Interval> nanoflann::KDTreeSingleIndexAdaptor::BoundingBox [private]

Definition at line 639 of file nanoflann.hpp.

typedef BranchSt* nanoflann::KDTreeSingleIndexAdaptor::Branch [private]

Definition at line 666 of file nanoflann.hpp.

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

Definition at line 665 of file nanoflann.hpp.

typedef Distance::ResultType nanoflann::KDTreeSingleIndexAdaptor::DistanceType [private]

Definition at line 582 of file nanoflann.hpp.

typedef Distance::ElementType nanoflann::KDTreeSingleIndexAdaptor::ElementType [private]

Definition at line 581 of file nanoflann.hpp.

typedef Node* nanoflann::KDTreeSingleIndexAdaptor::NodePtr [private]

Definition at line 631 of file nanoflann.hpp.

Constructor & Destructor Documentation

nanoflann::KDTreeSingleIndexAdaptor::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.

nanoflann::KDTreeSingleIndexAdaptor::~KDTreeSingleIndexAdaptor ( ) [inline]

Standard destructor.

Definition at line 711 of file nanoflann.hpp.

Member Function Documentation

void nanoflann::KDTreeSingleIndexAdaptor::buildIndex ( ) [inline]

Builds the index.

Definition at line 718 of file nanoflann.hpp.

void nanoflann::KDTreeSingleIndexAdaptor::computeBoundingBox ( BoundingBox & bbox ) [inline, private]

Definition at line 845 of file nanoflann.hpp.

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

Definition at line 1064 of file nanoflann.hpp.

References mrpt::math::distance().

void nanoflann::KDTreeSingleIndexAdaptor::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::count.

ElementType nanoflann::KDTreeSingleIndexAdaptor::dataset_get	(	size_t	idx,
		int	component
	)		const `[inline, private]`

Helper accessor to the dataset points:

Definition at line 815 of file nanoflann.hpp.

NodePtr nanoflann::KDTreeSingleIndexAdaptor::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::Node::child1, nanoflann::KDTreeSingleIndexAdaptor::Node::child2, nanoflann::KDTreeSingleIndexAdaptor::Node::lr, and nanoflann::KDTreeSingleIndexAdaptor::Node::sub.

template<typename RESULTSET >

void nanoflann::KDTreeSingleIndexAdaptor::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::SearchParams::eps, and nanoflann::KNNResultSet::dists.

void nanoflann::KDTreeSingleIndexAdaptor::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::init().

void nanoflann::KDTreeSingleIndexAdaptor::load_tree	(	FILE *	stream,
		NodePtr &	tree
	)		`[inline, private]`

Definition at line 832 of file nanoflann.hpp.

References nanoflann::load_value(), nanoflann::KDTreeSingleIndexAdaptor::Node::child1, and nanoflann::KDTreeSingleIndexAdaptor::Node::child2.

void nanoflann::KDTreeSingleIndexAdaptor::loadIndex ( FILE * stream ) [inline, private]

Definition at line 1147 of file nanoflann.hpp.

References nanoflann::load_value().

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

Definition at line 939 of file nanoflann.hpp.

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

Definition at line 984 of file nanoflann.hpp.

void nanoflann::KDTreeSingleIndexAdaptor::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.

size_t nanoflann::KDTreeSingleIndexAdaptor::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::SearchParams::sorted.

void nanoflann::KDTreeSingleIndexAdaptor::save_tree	(	FILE *	stream,
		NodePtr	tree
	)		`[inline, private]`

Definition at line 820 of file nanoflann.hpp.

References nanoflann::save_value(), nanoflann::KDTreeSingleIndexAdaptor::Node::child1, and nanoflann::KDTreeSingleIndexAdaptor::Node::child2.

void nanoflann::KDTreeSingleIndexAdaptor::saveIndex ( FILE * stream ) [inline, private]

Definition at line 1137 of file nanoflann.hpp.

References nanoflann::save_value().

template<class RESULTSET >

void nanoflann::KDTreeSingleIndexAdaptor::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]`