Class that implements the KDTree partition of 2D space and a closest point search algorithm. More...

#include <KDTreeLinkerAlgoT.h>

Public Member Functions
	KDTreeLinkerAlgo ()
	Default constructor.

	~KDTreeLinkerAlgo ()
	Destructor calls clear.

void	build (std::vector< KDTreeNodeInfoT< DATA, DIM > > &eltList, const KDTreeBoxT< DIM > &region)
	Build the KD tree from the "eltList" in the space define by "region". More...

void	search (const KDTreeBoxT< DIM > &searchBox, std::vector< KDTreeNodeInfoT< DATA, DIM > > &resRecHitList)
	Search in the KDTree for all points that would be contained in the given searchbox The founded points are stored in resRecHitList. More...

void	findNearestNeighbour (const KDTreeNodeInfoT< DATA, DIM > &point, const KDTreeNodeInfoT< DATA, DIM > *&result, float &distance)
	findNearestNeighbour More...

bool	empty ()
	Whether the tree is empty. More...

int	size ()
	Return the number of nodes + leaves in the tree (nElements should be (size() +1) / 2) More...

void	clear ()
	Clear all allocated structures.

Private Member Functions
KDTreeNodeT< DATA, DIM > *	getNextNode ()
	Get the next node from the node pool. More...

int	medianSearch (int low, int high, int treeDepth)
	Fast median search with Wirth algorithm in eltList between low and high indexes. More...

KDTreeNodeT< DATA, DIM > *	recBuild (int low, int high, int depth, const KDTreeBoxT< DIM > &region)
	Recursive kdtree builder. Is called by build() More...

void	recSearch (const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
	Recursive kdtree search. Is called by search() More...

void	recNearestNeighbour (unsigned depth, const KDTreeNodeT< DATA, DIM > current, const KDTreeNodeInfoT< DATA, DIM > &point, const KDTreeNodeT< DATA, DIM > &best_match, float &best_dist)
	Recursive nearest neighbour search. Is called by findNearestNeighbour() More...

void	addSubtree (const KDTreeNodeT< DATA, DIM > *current)
	Add all elements of an subtree to the closest elements. Used during the recSearch(). More...

float	dist2 (const KDTreeNodeInfoT< DATA, DIM > &a, const KDTreeNodeInfoT< DATA, DIM > &b) const
	dist2 More...

void	clearTree ()
	Frees the KDTree.

Private Attributes
KDTreeNodeT< DATA, DIM > *	root_
	The KDTree root.

KDTreeNodeT< DATA, DIM > *	nodePool_
	Node pool allows us to do just 1 call to new for each tree building.

int	nodePoolSize_
	The node pool size.

int	nodePoolPos_
	The node pool position.

std::vector< KDTreeNodeInfoT < DATA, DIM > > *	closestNeighbour
	The closest neighbour.

std::vector< KDTreeNodeInfoT < DATA, DIM > > *	initialEltList
	The initial element list.

Detailed Description

template<typename, unsigned int>
class april_content::KDTreeLinkerAlgo< typename, int >

Class that implements the KDTree partition of 2D space and a closest point search algorithm.

Member Function Documentation

template<typename DATA , unsigned DIM>

void april_content::KDTreeLinkerAlgo< DATA, DIM >::addSubtree ( const KDTreeNodeT< DATA, DIM > * current )

inlineprivate

Add all elements of an subtree to the closest elements. Used during the recSearch().

Parameters

current

template<typename DATA , unsigned DIM>

void april_content::KDTreeLinkerAlgo< DATA, DIM >::build	(	std::vector< KDTreeNodeInfoT< DATA, DIM > > &	eltList,
		const KDTreeBoxT< DIM > &	region
	)

inline

Build the KD tree from the "eltList" in the space define by "region".

Parameters

eltList
region

template<typename DATA , unsigned DIM>

float april_content::KDTreeLinkerAlgo< DATA, DIM >::dist2	(	const KDTreeNodeInfoT< DATA, DIM > &	a,
		const KDTreeNodeInfoT< DATA, DIM > &	b
	)		const

inlineprivate

dist2

Parameters

a
b

Returns: dist2

template<typename DATA , unsigned DIM>

bool april_content::KDTreeLinkerAlgo< DATA, DIM >::empty ( )

inline

Whether the tree is empty.

Returns: boolean

template<typename DATA , unsigned DIM>

void april_content::KDTreeLinkerAlgo< DATA, DIM >::findNearestNeighbour	(	const KDTreeNodeInfoT< DATA, DIM > &	point,
		const KDTreeNodeInfoT< DATA, DIM > *&	result,
		float &	distance
	)

inline

findNearestNeighbour

Parameters

point
result
distance

template<typename DATA , unsigned DIM>

KDTreeNodeT< DATA, DIM > * april_content::KDTreeLinkerAlgo< DATA, DIM >::getNextNode ( )

inlineprivate

Get the next node from the node pool.

Returns: the next node from the node pool

template<typename , unsigned int>

int april_content::KDTreeLinkerAlgo< DATA, DIM >::medianSearch	(	int	low,
		int	high,
		int	treeDepth
	)

inlineprivate

Fast median search with Wirth algorithm in eltList between low and high indexes.

Parameters

low
high
treeDepth

template<typename , unsigned int>

KDTreeNodeT< DATA, DIM > * april_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild	(	int	low,
		int	high,
		int	depth,
		const KDTreeBoxT< DIM > &	region
	)

inlineprivate

Recursive kdtree builder. Is called by build()

Parameters

low
high
depth
region

template<typename , unsigned int>

void april_content::KDTreeLinkerAlgo< DATA, DIM >::recNearestNeighbour	(	unsigned	depth,
		const KDTreeNodeT< DATA, DIM > *	current,
		const KDTreeNodeInfoT< DATA, DIM > &	point,
		const KDTreeNodeT< DATA, DIM > *&	best_match,
		float &	best_dist
	)

inlineprivate

Recursive nearest neighbour search. Is called by findNearestNeighbour()

Parameters

depth
current
point
best_match
best_dist

template<typename DATA , unsigned DIM>

void april_content::KDTreeLinkerAlgo< DATA, DIM >::recSearch	(	const KDTreeNodeT< DATA, DIM > *	current,
		const KDTreeBoxT< DIM > &	trackBox
	)

inlineprivate

Recursive kdtree search. Is called by search()

Parameters

current
trackBox

template<typename DATA , unsigned DIM>

void april_content::KDTreeLinkerAlgo< DATA, DIM >::search	(	const KDTreeBoxT< DIM > &	searchBox,
		std::vector< KDTreeNodeInfoT< DATA, DIM > > &	resRecHitList
	)

inline

Search in the KDTree for all points that would be contained in the given searchbox The founded points are stored in resRecHitList.

Parameters

searchBox
resRecHitList

template<typename DATA , unsigned DIM>

int april_content::KDTreeLinkerAlgo< DATA, DIM >::size ( )

inline

Return the number of nodes + leaves in the tree (nElements should be (size() +1) / 2)

Returns: the number of nodes + leaves in the tree

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

APRILContent/include/APRILTrackClusterAssociation/TrackClusterAssociationAlgorithm.h
APRILContent/include/APRILUtility/KDTreeLinkerAlgoT.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename, unsigned int> class april_content::KDTreeLinkerAlgo< typename, int >

Member Function Documentation

template<typename, unsigned int>
class april_content::KDTreeLinkerAlgo< typename, int >