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

#include "KDTreeLinkerAlgoT.h"

Collaboration diagram for lar_content::KDTreeLinkerAlgo< DATA, DIM >:

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".

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.

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

bool	empty ()
	Whether the tree is empty.

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

void	clear ()
	Clear all allocated structures.

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

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

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

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

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()

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

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

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 DATA, unsigned DIM = 2>
class lar_content::KDTreeLinkerAlgo< DATA, DIM >

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

Definition at line 22 of file KDTreeLinkerAlgoT.h.

Constructor & Destructor Documentation

◆ KDTreeLinkerAlgo()

template<typename DATA , unsigned DIM>

lar_content::KDTreeLinkerAlgo< DATA, DIM >::KDTreeLinkerAlgo ( )

inline

Default constructor.

Definition at line 162 of file KDTreeLinkerAlgoT.h.

◆ ~KDTreeLinkerAlgo()

template<typename DATA , unsigned DIM>

lar_content::KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo ( )

inline

Destructor calls clear.

Definition at line 175 of file KDTreeLinkerAlgoT.h.

Member Function Documentation

◆ addSubtree()

template<typename DATA , unsigned DIM>

void lar_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

Definition at line 421 of file KDTreeLinkerAlgoT.h.

◆ build()

template<typename DATA , unsigned DIM>

void lar_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

Definition at line 183 of file KDTreeLinkerAlgoT.h.

Here is the caller graph for this function:

◆ clear()

template<typename DATA , unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::clear ( )

inline

Clear all allocated structures.

Definition at line 486 of file KDTreeLinkerAlgoT.h.

Here is the caller graph for this function:

◆ clearTree()

template<typename DATA , unsigned DIM>

void lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree ( )

inlineprivate

Frees the KDTree.

Definition at line 458 of file KDTreeLinkerAlgoT.h.

◆ dist2()

template<typename DATA , unsigned DIM>

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

inlineprivate

dist2

Parameters

a
b

Returns: dist2

Definition at line 442 of file KDTreeLinkerAlgoT.h.

◆ empty()

template<typename DATA , unsigned DIM>

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

inline

Whether the tree is empty.

Returns: boolean

Definition at line 470 of file KDTreeLinkerAlgoT.h.

Here is the caller graph for this function:

◆ findNearestNeighbour()

template<typename DATA , unsigned DIM>

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

inline

findNearestNeighbour

Parameters

point
result
distance

Definition at line 334 of file KDTreeLinkerAlgoT.h.

Here is the caller graph for this function:

◆ getNextNode()

template<typename DATA , unsigned DIM>

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

inlineprivate

Get the next node from the node pool.

Returns: the next node from the node pool

Definition at line 495 of file KDTreeLinkerAlgoT.h.

◆ medianSearch()

template<typename DATA , unsigned DIM>

int lar_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

Definition at line 202 of file KDTreeLinkerAlgoT.h.

◆ recBuild()

template<typename DATA , unsigned DIM>

KDTreeNodeT< DATA, DIM > * lar_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

Definition at line 509 of file KDTreeLinkerAlgoT.h.

Here is the call graph for this function:

◆ recNearestNeighbour()

template<typename DATA , unsigned DIM = 2>

void lar_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

Definition at line 359 of file KDTreeLinkerAlgoT.h.

◆ recSearch()

template<typename DATA , unsigned DIM>

void lar_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

Definition at line 262 of file KDTreeLinkerAlgoT.h.

◆ search()

template<typename DATA , unsigned DIM>

void lar_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

Definition at line 249 of file KDTreeLinkerAlgoT.h.

Here is the caller graph for this function:

◆ size()

template<typename DATA , unsigned DIM>

int lar_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

Definition at line 478 of file KDTreeLinkerAlgoT.h.

Member Data Documentation

◆ closestNeighbour

template<typename DATA , unsigned DIM = 2>

std::vector<KDTreeNodeInfoT<DATA, DIM> >* lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour

private

The closest neighbour.

Definition at line 154 of file KDTreeLinkerAlgoT.h.

◆ initialEltList

template<typename DATA , unsigned DIM = 2>

std::vector<KDTreeNodeInfoT<DATA, DIM> >* lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList

private

The initial element list.

Definition at line 155 of file KDTreeLinkerAlgoT.h.

◆ nodePool_

template<typename DATA , unsigned DIM = 2>

KDTreeNodeT<DATA, DIM>* lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePool_

private

Node pool allows us to do just 1 call to new for each tree building.

Definition at line 150 of file KDTreeLinkerAlgoT.h.

◆ nodePoolPos_

template<typename DATA , unsigned DIM = 2>

int lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_

private

The node pool position.

Definition at line 152 of file KDTreeLinkerAlgoT.h.

◆ nodePoolSize_

template<typename DATA , unsigned DIM = 2>

int lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_

private

The node pool size.

Definition at line 151 of file KDTreeLinkerAlgoT.h.

◆ root_

template<typename DATA , unsigned DIM = 2>

KDTreeNodeT<DATA, DIM>* lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_

private

The KDTree root.

Definition at line 149 of file KDTreeLinkerAlgoT.h.

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

LArContent/larpandoracontent/LArControlFlow/PreProcessingAlgorithm.h
LArContent/larpandoracontent/LArUtility/KDTreeLinkerAlgoT.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ KDTreeLinkerAlgo()

◆ ~KDTreeLinkerAlgo()

Member Function Documentation

◆ addSubtree()

◆ build()

◆ clear()

◆ clearTree()

◆ dist2()

◆ empty()

◆ findNearestNeighbour()

◆ getNextNode()

◆ medianSearch()

◆ recBuild()

◆ recNearestNeighbour()

◆ recSearch()

◆ search()

◆ size()

Member Data Documentation

◆ closestNeighbour

◆ initialEltList

◆ nodePool_

◆ nodePoolPos_

◆ nodePoolSize_

◆ root_