Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap > Struct Template Reference
[private implementation]

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 >:
Nabo::NearestNeighbourSearch< T >

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< IndexBuildPoints
 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< NodeNodes
 dense vector of search nodes, provides better memory performances than many small objects
typedef std::vector< BucketEntryBuckets
 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 Vector maxRadii,
const Index  k = 1,
const T  epsilon = 0,
const unsigned  optionFlags = 0 
) const [inline, 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 >::knn ( const Matrix query,
IndexMatrix indices,
Matrix dists2,
const Index  k,
const T  epsilon,
const unsigned  optionFlags,
const T  maxRadius 
) const [inline, 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 >::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 [inline, 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,
rd,
Heap &  heap,
std::vector< T > &  off,
const T  maxError,
const T  maxRadius2 
) const [inline, 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:
Generated on Fri May 3 12:48:10 2013 for libnabo by  doxygen 1.6.3