#include <kdtree_single_index.h>

Inheritance diagram for rtflann::KDTreeSingleIndex< Distance >:

Classes
struct	Interval
struct	Node
Public Types
typedef NNIndex< Distance >	BaseClass
typedef Distance::ResultType	DistanceType
typedef Distance::ElementType	ElementType
typedef bool	needs_kdtree_distance
Public Member Functions
void	addPoints (const Matrix< ElementType > &points, float rebuild_threshold=2)
	Incrementally add points to the index.
BaseClass *	clone () const
void	findNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const
flann_algorithm_t	getType () const
	KDTreeSingleIndex (const IndexParams &params=KDTreeSingleIndexParams(), Distance d=Distance())
	KDTreeSingleIndex (const Matrix< ElementType > &inputData, const IndexParams &params=KDTreeSingleIndexParams(), Distance d=Distance())
	KDTreeSingleIndex (const KDTreeSingleIndex &other)
void	loadIndex (FILE *stream)
KDTreeSingleIndex &	operator= (KDTreeSingleIndex other)
void	saveIndex (FILE *stream)
template<typename Archive >
void	serialize (Archive &ar)
int	usedMemory () const
virtual	~KDTreeSingleIndex ()
Protected Member Functions
void	buildIndexImpl ()
Private Types
typedef std::vector< Interval >	BoundingBox
typedef BranchSt *	Branch
typedef BranchStruct< NodePtr, DistanceType >	BranchSt
typedef Node *	NodePtr
Private Member Functions
void	computeBoundingBox (BoundingBox &bbox)
DistanceType	computeInitialDistances (const ElementType *vec, std::vector< DistanceType > &dists) const
void	computeMinMax (int *ind, int count, int dim, ElementType &min_elem, ElementType &max_elem)
void	copyTree (NodePtr &dst, const NodePtr &src)
NodePtr	divideTree (int left, int right, BoundingBox &bbox)
void	freeIndex ()
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)
template<bool with_removed>
void	searchLevel (ResultSet< DistanceType > &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, std::vector< DistanceType > &dists, const float epsError) const
void	swap (KDTreeSingleIndex &other)
Private Attributes
Matrix< ElementType >	data_
int	leaf_max_size_
PooledAllocator	pool_
bool	reorder_
BoundingBox	root_bbox_
NodePtr	root_node_
std::vector< int >	vind_

Detailed Description

template<typename Distance>
class rtflann::KDTreeSingleIndex< Distance >

Single kd-tree index

Contains the k-d trees and other information for indexing a set of points for nearest-neighbor matching.

Definition at line 69 of file kdtree_single_index.h.

Member Typedef Documentation

template<typename Distance >

typedef NNIndex<Distance> rtflann::KDTreeSingleIndex< Distance >::BaseClass

Definition at line 75 of file kdtree_single_index.h.

template<typename Distance >

typedef std::vector<Interval> rtflann::KDTreeSingleIndex< Distance >::BoundingBox [private]

Definition at line 334 of file kdtree_single_index.h.

template<typename Distance >

typedef BranchSt* rtflann::KDTreeSingleIndex< Distance >::Branch [private]

Definition at line 337 of file kdtree_single_index.h.

template<typename Distance >

typedef BranchStruct<NodePtr, DistanceType> rtflann::KDTreeSingleIndex< Distance >::BranchSt [private]

Definition at line 336 of file kdtree_single_index.h.

template<typename Distance >

typedef Distance::ResultType rtflann::KDTreeSingleIndex< Distance >::DistanceType

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 73 of file kdtree_single_index.h.

template<typename Distance >

typedef Distance::ElementType rtflann::KDTreeSingleIndex< Distance >::ElementType

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 72 of file kdtree_single_index.h.

template<typename Distance >

typedef bool rtflann::KDTreeSingleIndex< Distance >::needs_kdtree_distance

Definition at line 77 of file kdtree_single_index.h.

template<typename Distance >

typedef Node* rtflann::KDTreeSingleIndex< Distance >::NodePtr [private]

Definition at line 317 of file kdtree_single_index.h.

Constructor & Destructor Documentation

template<typename Distance >

rtflann::KDTreeSingleIndex< Distance >::KDTreeSingleIndex	(	const IndexParams &	params = `KDTreeSingleIndexParams()`,
		Distance	d = `Distance()`
	)		`[inline]`

KDTree constructor

Params: params = parameters passed to the kdtree algorithm

Definition at line 85 of file kdtree_single_index.h.

template<typename Distance >

rtflann::KDTreeSingleIndex< Distance >::KDTreeSingleIndex	(	const Matrix< ElementType > &	inputData,
		const IndexParams &	params = `KDTreeSingleIndexParams()`,
		Distance	d = `Distance()`
	)		`[inline]`

KDTree constructor

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

Definition at line 99 of file kdtree_single_index.h.

template<typename Distance >

rtflann::KDTreeSingleIndex< Distance >::KDTreeSingleIndex ( const KDTreeSingleIndex< Distance > & other ) [inline]

Definition at line 109 of file kdtree_single_index.h.

template<typename Distance >

virtual rtflann::KDTreeSingleIndex< Distance >::~KDTreeSingleIndex ( ) [inline, virtual]

Standard destructor

Definition at line 131 of file kdtree_single_index.h.

Member Function Documentation

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::addPoints	(	const Matrix< ElementType > &	points,
		float	rebuild_threshold = `2`
	)		`[inline, virtual]`

Incrementally add points to the index.

Parameters:

points	Matrix with points to be added
rebuild_threshold

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 143 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::buildIndexImpl ( ) [inline, protected, virtual]

Builds the index

Implements rtflann::NNIndex< Distance >.

Definition at line 239 of file kdtree_single_index.h.

template<typename Distance >

BaseClass* rtflann::KDTreeSingleIndex< Distance >::clone ( ) const [inline, virtual]

Implements rtflann::NNIndex< Distance >.

Definition at line 136 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::computeBoundingBox ( BoundingBox & bbox ) [inline, private]

Definition at line 363 of file kdtree_single_index.h.

template<typename Distance >

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

Definition at line 571 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::computeMinMax	(	int *	ind,
		int	count,
		int	dim,
		ElementType &	min_elem,
		ElementType &	max_elem
	)		`[inline, private]`

Definition at line 438 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::copyTree	(	NodePtr &	dst,
		const NodePtr &	src
	)		`[inline, private]`

Definition at line 351 of file kdtree_single_index.h.

template<typename Distance >

NodePtr rtflann::KDTreeSingleIndex< Distance >::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 388 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::findNeighbors	(	ResultSet< DistanceType > &	result,
		const ElementType *	vec,
		const SearchParams &	searchParams
	)		const `[inline, virtual]`

Find set of nearest neighbors to vec. 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)

Implements rtflann::NNIndex< Distance >.

Definition at line 220 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::freeIndex ( ) [inline, private, virtual]

Implements rtflann::NNIndex< Distance >.

Definition at line 341 of file kdtree_single_index.h.

template<typename Distance >

flann_algorithm_t rtflann::KDTreeSingleIndex< Distance >::getType ( ) const [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 150 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::loadIndex ( FILE * stream ) [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 195 of file kdtree_single_index.h.

template<typename Distance >

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

Definition at line 449 of file kdtree_single_index.h.

template<typename Distance >

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

Definition at line 496 of file kdtree_single_index.h.

template<typename Distance >

KDTreeSingleIndex& rtflann::KDTreeSingleIndex< Distance >::operator= ( KDTreeSingleIndex< Distance > other ) [inline]

Definition at line 122 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::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 549 of file kdtree_single_index.h.

template<typename Distance >

void rtflann::KDTreeSingleIndex< Distance >::saveIndex ( FILE * stream ) [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 188 of file kdtree_single_index.h.

template<typename Distance >

template<bool with_removed>

void rtflann::KDTreeSingleIndex< Distance >::searchLevel	(	ResultSet< DistanceType > &	result_set,
		const ElementType *	vec,
		const NodePtr	node,
		DistanceType	mindistsq,
		std::vector< DistanceType > &	dists,
		const float	epsError
	)		const `[inline, private]`