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

#include <KDTree.h>

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

Detailed Description

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

Definition at line 41 of file KDTree.h.

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 111 of file KDTree.h.

template<class KE, class VTYPE>

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

Definition at line 110 of file KDTree.h.

template<class KE, class VTYPE>

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

Definition at line 108 of file KDTree.h.

template<class KE, class VTYPE>

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

Definition at line 109 of file KDTree.h.

template<class KE, class VTYPE>

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

Definition at line 106 of file KDTree.h.

template<class KE, class VTYPE>

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

Definition at line 107 of file KDTree.h.

template<class KE, class VTYPE>

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

Definition at line 112 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().

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.

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 celeste::max().

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 lfeat::bounded_set< _Key, _Compare >::getSet().

template<class KE , class VTYPE >

void KDTreeSpace::KDTree< KE, VTYPE >::init ( const ItemPtrVector_t &  iElemsPtrList )

private

Definition at line 98 of file KDTreeImpl.h.

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, lfeat::bounded_set< _Key, _Compare >::begin(), KDTreeSpace::HyperRectangle< KE, TYPE >::calcSqDistance(), KDTreeSpace::HyperRectangle< KE, TYPE >::hasHyperSphereIntersect(), lfeat::bounded_set< _Key, _Compare >::insert(), celeste::max(), KDTreeSpace::KDTree< KE, VTYPE >::recurseNearestNeighboursBBF(), lfeat::bounded_set< _Key, _Compare >::size(), and KDTreeSpace::HyperRectangle< KE, TYPE >::split().

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

Member Data Documentation

template<class KE, class VTYPE>

int KDTreeSpace::KDTree< KE, VTYPE >::_dims

private

Definition at line 139 of file KDTree.h.

template<class KE, class VTYPE>

KDTree<KE, VTYPE>* KDTreeSpace::KDTree< KE, VTYPE >::_leftKD

private

Definition at line 146 of file KDTree.h.

template<class KE, class VTYPE>

const KE* KDTreeSpace::KDTree< KE, VTYPE >::_pivot

private

Definition at line 142 of file KDTree.h.

template<class KE, class VTYPE>

KDTree<KE, VTYPE>* KDTreeSpace::KDTree< KE, VTYPE >::_rightKD

private

Definition at line 147 of file KDTree.h.

template<class KE, class VTYPE>

int KDTreeSpace::KDTree< KE, VTYPE >::_splitDim

private

Definition at line 143 of file KDTree.h.

---

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

• hugin_cpfind/cpfind/KDTree.h
• hugin_cpfind/cpfind/KDTreeImpl.h