Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap > Struct Template Reference

KDTree, unbalanced, points in leaves, stack, implicit bounds, ANN_KD_SL_MIDPT, optimised implementation. More...

#include <nabo_private.h>

Inheritance diagram for Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap >:

List of all members.

Classes
struct	BucketEntry
	entry in a bucket More...
struct	Node
	search node More...
Public Types
typedef NearestNeighbourSearch < T >::Vector	Vector
	an Eigen vector of type T, to hold the coordinates of a point
typedef NearestNeighbourSearch < T >::Matrix	Matrix
	a column-major Eigen matrix in which each column is a point; this matrix has dim rows
typedef NearestNeighbourSearch < T >::Index	Index
	an index to a Vector or a Matrix, for refering to data points
typedef NearestNeighbourSearch < T >::IndexVector	IndexVector
	a vector of indices to data points
typedef NearestNeighbourSearch < T >::IndexMatrix	IndexMatrix
	a matrix of indices to data points
Protected Types
typedef std::vector< Index >	BuildPoints
	indices of points during kd-tree construction
typedef BuildPoints::iterator	BuildPointsIt
	iterator to indices of points during kd-tree construction
typedef BuildPoints::const_iterator	BuildPointsCstIt
	const-iterator to indices of points during kd-tree construction
typedef std::vector< Node >	Nodes
	dense vector of search nodes, provides better memory performances than many small objects
typedef std::vector< BucketEntry >	Buckets
	bucket data
Protected Member Functions
uint32_t	createDimChildBucketSize (const uint32_t dim, const uint32_t childIndex) const
	create the compound index containing the dimension and the index of the child or the bucket size
uint32_t	getDim (const uint32_t dimChildBucketSize) const
	get the dimension out of the compound index
uint32_t	getChildBucketSize (const uint32_t dimChildBucketSize) const
	get the child index or the bucket size out of the coumpount index
Protected Attributes
const unsigned	bucketSize
	size of bucket
const uint32_t	dimBitCount
	number of bits required to store dimension index + number of dimensions
const uint32_t	dimMask
	mask to access dim
Nodes	nodes
	search nodes
Buckets	buckets
	buckets
std::pair< T, T >	getBounds (const BuildPointsIt first, const BuildPointsIt last, const unsigned dim)
	return the bounds of points from [first..last[ on dimension dim
unsigned	buildNodes (const BuildPointsIt first, const BuildPointsIt last, const Vector minValues, const Vector maxValues)
	construct nodes for points [first..last[ inside the hyperrectangle [minValues..maxValues]
unsigned long	onePointKnn (const Matrix &query, IndexMatrix &indices, Matrix &dists2, int i, Heap &heap, std::vector< T > &off, const T maxError, const T maxRadius2, const bool allowSelfMatch, const bool collectStatistics, const bool sortResults) const
	search one point, call recurseKnn with the correct template parameters
template<bool allowSelfMatch, bool collectStatistics>
unsigned long	recurseKnn (const T *query, const unsigned n, T rd, Heap &heap, std::vector< T > &off, const T maxError, const T maxRadius2) const
	recursive search, strongly inspired by ANN and [Arya & Mount, Algorithms for fast vector quantization, 1993]
	KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt (const Matrix &cloud, const Index dim, const unsigned creationOptionFlags, const Parameters &additionalParameters)
	constructor, calls NearestNeighbourSearch<T>(cloud)
virtual unsigned long	knn (const Matrix &query, IndexMatrix &indices, Matrix &dists2, const Index k, const T epsilon, const unsigned optionFlags, const T maxRadius) const
	Find the k nearest neighbours for each point of query.
virtual unsigned long	knn (const Matrix &query, IndexMatrix &indices, Matrix &dists2, const Vector &maxRadii, const Index k=1, const T epsilon=0, const unsigned optionFlags=0) const
	Find the k nearest neighbours for each point of query.

---

Detailed Description

template<typename T, typename Heap>
struct Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap >

KDTree, unbalanced, points in leaves, stack, implicit bounds, ANN_KD_SL_MIDPT, optimised implementation.

---

Member Function Documentation

template<typename T , typename Heap >

unsigned long Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap >::knn	(	const Matrix &	query,
		IndexMatrix &	indices,
		Matrix &	dists2,
		const Index	k,
		const T	epsilon,
		const unsigned	optionFlags,
		const T	maxRadius
	)		const [virtual]

Find the k nearest neighbours for each point of query.

If the search finds less than k points, the empty entries in dists2 will be filled with infinity and the indices with 0.

Parameters:

query	query points
indices	indices of nearest neighbours, must be of size k x query.cols()
dists2	squared distances to nearest neighbours, must be of size k x query.cols()
k	number of nearest neighbour requested
epsilon	maximal percentage of error for approximate search, 0 for exact search
optionFlags	search options, a bitwise OR of elements of SearchOptionFlags
maxRadius	maximum radius in which to search, can be used to prune search, is not affected by epsilon

Returns:

if creationOptionFlags contains TOUCH_STATISTICS, return the number of point touched, otherwise return 0

Implements Nabo::NearestNeighbourSearch< T >.

template<typename T , typename Heap >

unsigned long Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap >::knn	(	const Matrix &	query,
		IndexMatrix &	indices,
		Matrix &	dists2,
		const Vector &	maxRadii,
		const Index	k = 1,
		const T	epsilon = 0,
		const unsigned	optionFlags = 0
	)		const [virtual]

Find the k nearest neighbours for each point of query.

If the search finds less than k points, the empty entries in dists2 will be filled with infinity and the indices with 0.

Parameters:

query	query points
indices	indices of nearest neighbours, must be of size k x query.cols()
dists2	squared distances to nearest neighbours, must be of size k x query.cols()
maxRadii	vector of maximum radii in which to search, used to prune search, is not affected by epsilon
k	number of nearest neighbour requested
epsilon	maximal percentage of error for approximate search, 0 for exact search
optionFlags	search options, a bitwise OR of elements of SearchOptionFlags

Returns:

if creationOptionFlags contains TOUCH_STATISTICS, return the number of point touched, otherwise return 0

Implements Nabo::NearestNeighbourSearch< T >.

template<typename T , typename Heap >

unsigned long Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap >::onePointKnn	(	const Matrix &	query,
		IndexMatrix &	indices,
		Matrix &	dists2,
		int	i,
		Heap &	heap,
		std::vector< T > &	off,
		const T	maxError,
		const T	maxRadius2,
		const bool	allowSelfMatch,
		const bool	collectStatistics,
		const bool	sortResults
	)		const [protected]

search one point, call recurseKnn with the correct template parameters

Parameters:

query	pointer to query coordinates
indices	indices of nearest neighbours, must be of size k x query.cols()
dists2	squared distances to nearest neighbours, must be of size k x query.cols()
i	index of point to search
heap	reference to heap
off	reference to array of offsets
maxError	error factor (1 + epsilon)
maxRadius2	square of maximum radius
allowSelfMatch	whether to allow self match
collectStatistics	whether to collect statistics
sortResults	wether to sort results

template<typename T , typename Heap >

template<bool allowSelfMatch, bool collectStatistics>

unsigned long Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap >::recurseKnn	(	const T *	query,
		const unsigned	n,
		T	rd,
		Heap &	heap,
		std::vector< T > &	off,
		const T	maxError,
		const T	maxRadius2
	)		const [protected]

recursive search, strongly inspired by ANN and [Arya & Mount, Algorithms for fast vector quantization, 1993]

Parameters:

query	pointer to query coordinates
n	index of node to visit
rd	squared dist to this rect
heap	reference to heap
off	reference to array of offsets
maxError	error factor (1 + epsilon)
maxRadius2	square of maximum radius

---

The documentation for this struct was generated from the following files:

• nabo_private.h
• kdtree_cpu.cpp