KDTreeSpace::KDTree< KE, VTYPE > Class Template Reference

#include <KDTree.h>

List of all members.

Public Types

typedef std::vector< KE > ItemVector_t
typedef std::vector< KE
>::const_iterator 
ItemVectorIt_t
typedef std::vector< const
KE * > 
ItemPtrVector_t
typedef std::vector< const
KE * >::const_iterator 
ItemPtrVectorIt_t
typedef std::set< BestMatch<
KE >, std::greater< BestMatch<
KE > > > 
BestMatchSet_t
typedef lfeat::bounded_set<
BestMatch< KE >, std::greater<
BestMatch< KE > > > 
BestMatchLimitedSet_t
typedef std::list< QueueEntry<
KE, VTYPE > > 
QueueEntryList_t

Public Member Functions

 KDTree (const ItemVector_t &iElemsList, int iDimensions)
 KDTree (const ItemPtrVector_t &iElemsPtrList, int iDimensions)
 ~KDTree ()
BestMatchSet_t getNearestNeighboursBBF (const KE &iTarget, int iNbBestMatches, int iNbSearchSteps)
double calcSqDist (const KE *i1, const KE *i2)

Private Member Functions

void init (const ItemPtrVector_t &iElemsPtrList)
ItemPtrVectorIt_t choosePivot (const ItemPtrVector_t &iElemsPtrList)
void recurseNearestNeighboursBBF (const KE &iTarget, HyperRectangle< KE, VTYPE > &iHR, BestMatchLimitedSet_t &ioBestMatches, QueueEntryList_t &ioSearchQueue, int &ioRemainingUnqueues)

Private Attributes

int _dims
const KE * _pivot
int _splitDim
KDTree< KE, VTYPE > * _leftKD
KDTree< KE, VTYPE > * _rightKD

template<class KE, class VTYPE>
class KDTreeSpace::KDTree< KE, VTYPE >


Member Typedef Documentation

template<class KE, class VTYPE>
typedef lfeat::bounded_set<BestMatch<KE>, std::greater<BestMatch<KE> > > KDTreeSpace::KDTree< KE, VTYPE >::BestMatchLimitedSet_t
 

Definition at line 110 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::getNearestNeighboursBBF(), and KDTreeSpace::KDTree< KE, VTYPE >::recurseNearestNeighboursBBF().

template<class KE, class VTYPE>
typedef std::set<BestMatch<KE>, std::greater<BestMatch<KE> > > KDTreeSpace::KDTree< KE, VTYPE >::BestMatchSet_t
 

Definition at line 109 of file KDTree.h.

template<class KE, class VTYPE>
typedef std::vector<const KE*> KDTreeSpace::KDTree< KE, VTYPE >::ItemPtrVector_t
 

Definition at line 107 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::init(), and KDTreeSpace::KDTree< KE, VTYPE >::KDTree().

template<class KE, class VTYPE>
typedef std::vector<const KE*>::const_iterator KDTreeSpace::KDTree< KE, VTYPE >::ItemPtrVectorIt_t
 

Definition at line 108 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::choosePivot(), and KDTreeSpace::KDTree< KE, VTYPE >::init().

template<class KE, class VTYPE>
typedef std::vector<KE> KDTreeSpace::KDTree< KE, VTYPE >::ItemVector_t
 

Definition at line 105 of file KDTree.h.

template<class KE, class VTYPE>
typedef std::vector<KE>::const_iterator KDTreeSpace::KDTree< KE, VTYPE >::ItemVectorIt_t
 

Definition at line 106 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::KDTree().

template<class KE, class VTYPE>
typedef std::list<QueueEntry<KE, VTYPE> > KDTreeSpace::KDTree< KE, VTYPE >::QueueEntryList_t
 

Definition at line 111 of file KDTree.h.


Constructor & Destructor Documentation

template<class KE, class VTYPE>
KDTreeSpace::KDTree< KE, VTYPE >::KDTree const ItemVector_t iElemsList,
int  iDimensions
 

Definition at line 38 of file KDTreeImpl.h.

References KDTreeSpace::KDTree< KE, VTYPE >::init(), KDTreeSpace::KDTree< KE, VTYPE >::ItemPtrVector_t, and KDTreeSpace::KDTree< KE, VTYPE >::ItemVectorIt_t.

template<class KE, class VTYPE>
KDTreeSpace::KDTree< KE, VTYPE >::KDTree const ItemPtrVector_t iElemsPtrList,
int  iDimensions
 

Definition at line 68 of file KDTreeImpl.h.

References KDTreeSpace::KDTree< KE, VTYPE >::init().

template<class KE, class VTYPE>
KDTreeSpace::KDTree< KE, VTYPE >::~KDTree  ) 
 

Definition at line 83 of file KDTreeImpl.h.


Member Function Documentation

template<class KE, class VTYPE>
double KDTreeSpace::KDTree< KE, VTYPE >::calcSqDist const KE *  i1,
const KE *  i2
 

Definition at line 227 of file KDTreeImpl.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::recurseNearestNeighboursBBF().

template<class KE, class VTYPE>
std::vector< const KE * >::const_iterator KDTreeSpace::KDTree< KE, VTYPE >::choosePivot const ItemPtrVector_t iElemsPtrList  )  [private]
 

Definition at line 163 of file KDTreeImpl.h.

References KDTreeSpace::KDTree< KE, VTYPE >::_dims, KDTreeSpace::KDTree< KE, VTYPE >::_splitDim, KDTreeSpace::KDTree< KE, VTYPE >::ItemPtrVectorIt_t, and celeste::max().

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::init().

template<class KE, class VTYPE>
std::set< BestMatch< KE >, std::greater< BestMatch< KE > > > KDTreeSpace::KDTree< KE, VTYPE >::getNearestNeighboursBBF const KE &  iTarget,
int  iNbBestMatches,
int  iNbSearchSteps
 

Definition at line 240 of file KDTreeImpl.h.

References KDTreeSpace::KDTree< KE, VTYPE >::_dims, KDTreeSpace::KDTree< KE, VTYPE >::BestMatchLimitedSet_t, lfeat::bounded_set< _Key, _Compare >::getSet(), and KDTreeSpace::KDTree< KE, VTYPE >::recurseNearestNeighboursBBF().

template<class KE, class VTYPE>
void KDTreeSpace::KDTree< KE, VTYPE >::init const ItemPtrVector_t iElemsPtrList  )  [private]
 

Definition at line 98 of file KDTreeImpl.h.

References KDTreeSpace::KDTree< KE, VTYPE >::_leftKD, KDTreeSpace::KDTree< KE, VTYPE >::_pivot, KDTreeSpace::KDTree< KE, VTYPE >::_rightKD, KDTreeSpace::KDTree< KE, VTYPE >::_splitDim, KDTreeSpace::KDTree< KE, VTYPE >::choosePivot(), KDTreeSpace::KDTree< KE, VTYPE >::ItemPtrVector_t, and KDTreeSpace::KDTree< KE, VTYPE >::ItemPtrVectorIt_t.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::KDTree().

template<class KE, class VTYPE>
void KDTreeSpace::KDTree< KE, VTYPE >::recurseNearestNeighboursBBF const KE &  iTarget,
HyperRectangle< KE, VTYPE > &  iHR,
BestMatchLimitedSet_t ioBestMatches,
QueueEntryList_t ioSearchQueue,
int &  ioRemainingUnqueues
[private]
 

Definition at line 258 of file KDTreeImpl.h.

References KDTreeSpace::QueueEntry< KE, VTYPE >::_HR, KDTreeSpace::QueueEntry< KE, VTYPE >::_kdTree, KDTreeSpace::KDTree< KE, VTYPE >::_pivot, KDTreeSpace::KDTree< KE, VTYPE >::_splitDim, lfeat::bounded_set< _Key, _Compare >::begin(), KDTreeSpace::KDTree< KE, VTYPE >::BestMatchLimitedSet_t, KDTreeSpace::KDTree< KE, VTYPE >::calcSqDist(), lfeat::bounded_set< _Key, _Compare >::end(), KDTreeSpace::HyperRectangle< KE, TYPE >::hasHyperSphereIntersect(), lfeat::bounded_set< _Key, _Compare >::insert(), celeste::max(), lfeat::bounded_set< _Key, _Compare >::size(), and KDTreeSpace::HyperRectangle< KE, TYPE >::split().

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::getNearestNeighboursBBF().


Member Data Documentation

template<class KE, class VTYPE>
int KDTreeSpace::KDTree< KE, VTYPE >::_dims [private]
 

Definition at line 138 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::choosePivot(), and KDTreeSpace::KDTree< KE, VTYPE >::getNearestNeighboursBBF().

template<class KE, class VTYPE>
KDTree<KE, VTYPE>* KDTreeSpace::KDTree< KE, VTYPE >::_leftKD [private]
 

Definition at line 145 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::init().

template<class KE, class VTYPE>
const KE* KDTreeSpace::KDTree< KE, VTYPE >::_pivot [private]
 

Definition at line 141 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::init(), and KDTreeSpace::KDTree< KE, VTYPE >::recurseNearestNeighboursBBF().

template<class KE, class VTYPE>
KDTree<KE, VTYPE>* KDTreeSpace::KDTree< KE, VTYPE >::_rightKD [private]
 

Definition at line 146 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::init().

template<class KE, class VTYPE>
int KDTreeSpace::KDTree< KE, VTYPE >::_splitDim [private]
 

Definition at line 142 of file KDTree.h.

Referenced by KDTreeSpace::KDTree< KE, VTYPE >::choosePivot(), KDTreeSpace::KDTree< KE, VTYPE >::init(), and KDTreeSpace::KDTree< KE, VTYPE >::recurseNearestNeighboursBBF().


The documentation for this class was generated from the following files:
Generated on Mon Sep 1 01:25:53 2014 for Hugintrunk by  doxygen 1.3.9.1