Classes | Public Types | Protected Types | Protected Member Functions | Protected Attributes
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType > 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, CloudType >:
Inheritance graph
[legend]

List of all members.

Classes

struct  BucketEntry
 entry in a bucket More...
struct  Node
 search node More...

Public Types

typedef NearestNeighbourSearch
< T, CloudType >::Index 
Index
 an index to a Vector or a Matrix, for refering to data points
typedef NearestNeighbourSearch
< T, CloudType >::IndexMatrix 
IndexMatrix
 a matrix of indices to data points
typedef NearestNeighbourSearch
< T, CloudType >::IndexVector 
IndexVector
 a vector of indices to data points
typedef NearestNeighbourSearch
< T, CloudType >::Matrix 
Matrix
 a column-major Eigen matrix in which each column is a point; this matrix has dim rows
typedef NearestNeighbourSearch
< T, CloudType >::Vector 
Vector
 an Eigen vector of type T, to hold the coordinates of a point

Protected Types

typedef std::vector< BucketEntryBuckets
 bucket data
typedef std::vector< IndexBuildPoints
 indices of points during kd-tree construction
typedef BuildPoints::const_iterator BuildPointsCstIt
 const-iterator to indices of points during kd-tree construction
typedef BuildPoints::iterator BuildPointsIt
 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

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 getChildBucketSize (const uint32_t dimChildBucketSize) const
 get the child index or the bucket size out of the coumpount index
uint32_t getDim (const uint32_t dimChildBucketSize) const
 get the dimension out of the compound index

Protected Attributes

Buckets buckets
 buckets
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
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 CloudType &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
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

Detailed Description

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
struct Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >

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

Definition at line 94 of file nabo_private.h.


Member Typedef Documentation

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef std::vector<BucketEntry> Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::Buckets [protected]

bucket data

Definition at line 171 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef std::vector<Index> Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::BuildPoints [protected]

indices of points during kd-tree construction

Definition at line 111 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef BuildPoints::const_iterator Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::BuildPointsCstIt [protected]

const-iterator to indices of points during kd-tree construction

Definition at line 115 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef BuildPoints::iterator Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::BuildPointsIt [protected]

iterator to indices of points during kd-tree construction

Definition at line 113 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef NearestNeighbourSearch<T, CloudType>::Index Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::Index

an index to a Vector or a Matrix, for refering to data points

Reimplemented from Nabo::NearestNeighbourSearch< T, CloudType >.

Definition at line 98 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef NearestNeighbourSearch<T, CloudType>::IndexMatrix Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::IndexMatrix

a matrix of indices to data points

Reimplemented from Nabo::NearestNeighbourSearch< T, CloudType >.

Definition at line 100 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef NearestNeighbourSearch<T, CloudType>::IndexVector Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::IndexVector

a vector of indices to data points

Reimplemented from Nabo::NearestNeighbourSearch< T, CloudType >.

Definition at line 99 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef NearestNeighbourSearch<T, CloudType>::Matrix Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::Matrix

a column-major Eigen matrix in which each column is a point; this matrix has dim rows

Reimplemented from Nabo::NearestNeighbourSearch< T, CloudType >.

Definition at line 97 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef std::vector<Node> Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::Nodes [protected]

dense vector of search nodes, provides better memory performances than many small objects

Definition at line 155 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
typedef NearestNeighbourSearch<T, CloudType>::Vector Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::Vector

an Eigen vector of type T, to hold the coordinates of a point

Reimplemented from Nabo::NearestNeighbourSearch< T, CloudType >.

Definition at line 96 of file nabo_private.h.


Constructor & Destructor Documentation

template<typename T , typename Heap , typename CloudType >
Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt ( const CloudType cloud,
const Index  dim,
const unsigned  creationOptionFlags,
const Parameters additionalParameters 
)

constructor, calls NearestNeighbourSearch<T>(cloud)

Definition at line 228 of file nabo/kdtree_cpu.cpp.


Member Function Documentation

template<typename T , typename Heap , typename CloudType >
unsigned Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::buildNodes ( const BuildPointsIt  first,
const BuildPointsIt  last,
const Vector  minValues,
const Vector  maxValues 
) [protected]

construct nodes for points [first..last[ inside the hyperrectangle [minValues..maxValues]

Definition at line 110 of file nabo/kdtree_cpu.cpp.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
uint32_t Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::createDimChildBucketSize ( const uint32_t  dim,
const uint32_t  childIndex 
) const [inline, protected]

create the compound index containing the dimension and the index of the child or the bucket size

Definition at line 126 of file nabo_private.h.

template<typename T , typename Heap , typename CloudType >
pair< T, T > Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::getBounds ( const BuildPointsIt  first,
const BuildPointsIt  last,
const unsigned  dim 
) [protected]

return the bounds of points from [first..last[ on dimension dim

Definition at line 94 of file nabo/kdtree_cpu.cpp.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
uint32_t Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::getChildBucketSize ( const uint32_t  dimChildBucketSize) const [inline, protected]

get the child index or the bucket size out of the coumpount index

Definition at line 132 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
uint32_t Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::getDim ( const uint32_t  dimChildBucketSize) const [inline, protected]

get the dimension out of the compound index

Definition at line 129 of file nabo_private.h.

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

Definition at line 275 of file nabo/kdtree_cpu.cpp.

template<typename T , typename Heap , typename CloudType >
unsigned long Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::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]

Definition at line 307 of file nabo/kdtree_cpu.cpp.

template<typename T , typename Heap , typename CloudType >
unsigned long Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::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:
querypointer to query coordinates
indicesindices of nearest neighbours, must be of size k x query.cols()
dists2squared distances to nearest neighbours, must be of size k x query.cols()
iindex of point to search
heapreference to heap
offreference to array of offsets
maxErrorerror factor (1 + epsilon)
maxRadius2square of maximum radius
allowSelfMatchwhether to allow self match
collectStatisticswhether to collect statistics
sortResultswether to sort results

Definition at line 339 of file nabo/kdtree_cpu.cpp.

template<typename T , typename Heap , typename CloudType >
template<bool allowSelfMatch, bool collectStatistics>
unsigned long Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::recurseKnn ( const T *  query,
const unsigned  n,
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:
querypointer to query coordinates
nindex of node to visit
rdsquared dist to this rect
heapreference to heap
offreference to array of offsets
maxErrorerror factor (1 + epsilon)
maxRadius2square of maximum radius

Definition at line 368 of file nabo/kdtree_cpu.cpp.


Member Data Documentation

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
Buckets Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::buckets [protected]

buckets

Definition at line 177 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
const unsigned Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::bucketSize [protected]

size of bucket

Definition at line 118 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
const uint32_t Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::dimBitCount [protected]

number of bits required to store dimension index + number of dimensions

Definition at line 121 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
const uint32_t Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::dimMask [protected]

mask to access dim

Definition at line 123 of file nabo_private.h.

template<typename T, typename Heap, typename CloudType = Eigen::Matrix<T, Eigen::Dynamic, Eigen::Dynamic>>
Nodes Nabo::KDTreeUnbalancedPtInLeavesImplicitBoundsStackOpt< T, Heap, CloudType >::nodes [protected]

search nodes

Definition at line 174 of file nabo_private.h.


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


libnabo
Author(s): Stéphane Magnenat
autogenerated on Sun Feb 10 2019 03:52:20