Classes | Public Types | Public Member Functions | Protected Member Functions | Private Types | Private Member Functions | Private Attributes
rtflann::KDTreeSingleIndex< Distance > Class Template Reference

#include <kdtree_single_index.h>

Inheritance diagram for rtflann::KDTreeSingleIndex< Distance >:
Inheritance graph
[legend]

List of all members.

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.
BaseClassclone () 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)
KDTreeSingleIndexoperator= (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< IntervalBoundingBox
typedef BranchStBranch
typedef BranchStruct< NodePtr,
DistanceType
BranchSt
typedef NodeNodePtr

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< ElementTypedata_
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:
pointsMatrix 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]

Performs an exact search in the tree starting from a node.

Definition at line 593 of file kdtree_single_index.h.

template<typename Distance >
template<typename Archive >
void rtflann::KDTreeSingleIndex< Distance >::serialize ( Archive &  ar) [inline]

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 157 of file kdtree_single_index.h.

template<typename Distance >
void rtflann::KDTreeSingleIndex< Distance >::swap ( KDTreeSingleIndex< Distance > &  other) [inline, private]

Definition at line 645 of file kdtree_single_index.h.

template<typename Distance >
int rtflann::KDTreeSingleIndex< Distance >::usedMemory ( ) const [inline, virtual]

Computes the inde memory usage Returns: memory used by the index

Implements rtflann::IndexBase.

Definition at line 206 of file kdtree_single_index.h.


Member Data Documentation

template<typename Distance >
Matrix<ElementType> rtflann::KDTreeSingleIndex< Distance >::data_ [private]

Definition at line 671 of file kdtree_single_index.h.

template<typename Distance >
int rtflann::KDTreeSingleIndex< Distance >::leaf_max_size_ [private]

Definition at line 661 of file kdtree_single_index.h.

template<typename Distance >
PooledAllocator rtflann::KDTreeSingleIndex< Distance >::pool_ [private]

Pooled memory allocator.

Using a pooled memory allocator is more efficient than allocating memory directly when there is a large number small of memory allocations.

Definition at line 690 of file kdtree_single_index.h.

template<typename Distance >
bool rtflann::KDTreeSingleIndex< Distance >::reorder_ [private]

Definition at line 664 of file kdtree_single_index.h.

template<typename Distance >
BoundingBox rtflann::KDTreeSingleIndex< Distance >::root_bbox_ [private]

Root bounding box

Definition at line 681 of file kdtree_single_index.h.

template<typename Distance >
NodePtr rtflann::KDTreeSingleIndex< Distance >::root_node_ [private]

Array of k-d trees used to find neighbours.

Definition at line 676 of file kdtree_single_index.h.

template<typename Distance >
std::vector<int> rtflann::KDTreeSingleIndex< Distance >::vind_ [private]

Array of indices to vectors in the dataset.

Definition at line 669 of file kdtree_single_index.h.


The documentation for this class was generated from the following file:


rtabmap
Author(s): Mathieu Labbe
autogenerated on Sat Jul 23 2016 11:44:32