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

#include <PreProcessingAlgorithm.h>

Public Member Functions
	KDTreeLinkerAlgo ()
	Default constructor. More...

	~KDTreeLinkerAlgo ()
	Destructor calls clear. More...

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

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

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

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

int	nodePoolSize_
	The node pool size. More...

int	nodePoolPos_
	The node pool position. More...

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

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

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 17 of file PreProcessingAlgorithm.h.

Constructor & Destructor Documentation

template<typename DATA , unsigned DIM>

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

inline

Default constructor.

Definition at line 162 of file KDTreeLinkerAlgoT.h.

                                                      :
     root_(nullptr),
     nodePool_(nullptr),
     nodePoolSize_(-1),
     nodePoolPos_(-1),
     closestNeighbour(nullptr),
     initialEltList(nullptr)
 {
 }

template<typename DATA , unsigned DIM>

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

inline

Destructor calls clear.

Definition at line 175 of file KDTreeLinkerAlgoT.h.

 {
     this->clear();
 }

Member Function Documentation

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.

 {
     // By construction, current can't be null
     //assert(current != 0);
 
     if ((current->left == nullptr) && (current->right == nullptr))
     {
         // Leaf case
         closestNeighbour->push_back(current->info);
     }
     else
     {
         // Node case
         this->addSubtree(current->left);
         this->addSubtree(current->right);
     }
 }

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.

 {
     if (eltList.size())
     {
         initialEltList = &eltList;
         const size_t mysize = initialEltList->size();
 
         nodePoolSize_ = mysize * 2 - 1;
         nodePool_ = new KDTreeNodeT<DATA, DIM>[nodePoolSize_];
 
         // Here we build the KDTree
         root_ = this->recBuild(0, mysize, 0, region);
         initialEltList = nullptr;
     }
 }

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.

 {
     if (root_)
         this->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.

 {
     delete[] nodePool_;
     nodePool_ = nullptr;
     root_ = nullptr;
     nodePoolSize_ = -1;
     nodePoolPos_ = -1;
 }

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.

 {
     double d = 0.;
 
     for (unsigned i = 0; i < DIM; ++i)
     {
         const double diff = a.dims[i] - b.dims[i];
         d += diff * diff;
     }
 
     return (float)d;
 }

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.

 {
     return (nodePoolPos_ == -1);
 }

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.

 {
     if (nullptr != result || distance != std::numeric_limits<float>::max())
     {
         result = nullptr;
         distance = std::numeric_limits<float>::max();
     }
 
     if (root_)
     {
         const KDTreeNodeT<DATA, DIM> *best_match = nullptr;
         this->recNearestNeighbour(0, root_, point, best_match, distance);
 
         if (distance != std::numeric_limits<float>::max())
         {
             result = &(best_match->info);
             distance = std::sqrt(distance);
         }
     }
 }

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.

 {
     ++nodePoolPos_;
 
     // The tree size is exactly 2 * nbrElts - 1 and this is the total allocated memory.
     // If we have used more than that....there is a big problem.
     //assert(nodePoolPos_ < nodePoolSize_);
 
     return &(nodePool_[nodePoolPos_]);
 }

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.

 {
     // We should have at least 1 element to calculate the median...
     //assert(low < high);
 
     const int nbrElts = high - low;
     int median = nbrElts / 2 - (1 - 1 * (nbrElts & 1));
     median += low;
 
     int l = low;
     int m = high - 1;
 
     while (l < m)
     {
         KDTreeNodeInfoT<DATA, DIM> elt = (*initialEltList)[median];
         int i = l;
         int j = m;
 
         do
         {
             // The even depth is associated to dim1 dimension, the odd one to dim2 dimension
             const unsigned thedim = treeDepth % DIM;
             while ((*initialEltList)[i].dims[thedim] < elt.dims[thedim])
                 ++i;
             while ((*initialEltList)[j].dims[thedim] > elt.dims[thedim])
                 --j;
 
             if (i <= j)
             {
                 std::swap((*initialEltList)[i], (*initialEltList)[j]);
                 i++;
                 j--;
             }
         } while (i <= j);
 
         if (j < median)
             l = i;
         if (i > median)
             m = j;
     }
 
     return median;
 }

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.

 {
     const int portionSize = high - low;
 
     // By construction, portionSize > 0 can't happen.
     //assert(portionSize > 0);
 
     if (portionSize == 1)
     {
         // Leaf case
         KDTreeNodeT<DATA, DIM> *leaf = this->getNextNode();
         leaf->setAttributs(region, (*initialEltList)[low]);
         return leaf;
     }
     else
     {
         // The even depth is associated to dim1 dimension, the odd one to dim2 dimension
         int medianId = this->medianSearch(low, high, depth);
 
         // We create the node
         KDTreeNodeT<DATA, DIM> *node = this->getNextNode();
         node->setAttributs(region);
         node->info = (*initialEltList)[medianId];
 
         // Here we split into 2 halfplanes the current plane
         KDTreeBoxT<DIM> leftRegion = region;
         KDTreeBoxT<DIM> rightRegion = region;
 
         const unsigned thedim = depth % DIM;
         auto medianVal = (*initialEltList)[medianId].dims[thedim];
         leftRegion.dimmax[thedim] = medianVal;
         rightRegion.dimmin[thedim] = medianVal;
 
         ++depth;
         ++medianId;
 
         // We recursively build the son nodes
         node->left = this->recBuild(low, medianId, depth, leftRegion);
         node->right = this->recBuild(medianId, high, depth, rightRegion);
         return node;
     }
 }

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.

 {
     const unsigned int current_dim = depth % DIM;
 
     if (current->left == nullptr && current->right == nullptr)
     {
         best_match = current;
         best_dist = this->dist2(point, best_match->info);
         return;
     }
     else
     {
         const float dist_to_axis = point.dims[current_dim] - current->info.dims[current_dim];
 
         if (dist_to_axis < 0.f)
         {
             this->recNearestNeighbour(depth + 1, current->left, point, best_match, best_dist);
         }
         else
         {
             this->recNearestNeighbour(depth + 1, current->right, point, best_match, best_dist);
         }
 
         // If we're here we're returned so best_dist is filled. Compare to this node and see if it's a better match. If it is, update result
         const float dist_current = this->dist2(point, current->info);
 
         if (dist_current < best_dist)
         {
             best_dist = dist_current;
             best_match = current;
         }
 
         // Now we see if the radius to best crosses the splitting axis
         if (best_dist > dist_to_axis * dist_to_axis)
         {
             // if it does we traverse the other side of the axis to check for a new best
             const KDTreeNodeT<DATA, DIM> *check_best = best_match;
             float check_dist = best_dist;
 
             if (dist_to_axis < 0.f)
             {
                 this->recNearestNeighbour(depth + 1, current->right, point, check_best, check_dist);
             }
             else
             {
                 this->recNearestNeighbour(depth + 1, current->left, point, check_best, check_dist);
             }
 
             if (check_dist < best_dist)
             {
                 best_dist = check_dist;
                 best_match = check_best;
             }
         }
         return;
     }
 }

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.

 {
     // By construction, current can't be null
     //assert(current != 0);
     // By Construction, a node can't have just 1 son.
     //assert (!(((current->left == 0) && (current->right != 0)) || ((current->left != 0) && (current->right == 0))));
 
     if ((current->left == nullptr) && (current->right == nullptr))
     {
         // Leaf case
         // If point inside the rectangle/area
         bool isInside = true;
 
         for (unsigned i = 0; i < DIM; ++i)
         {
             const auto thedim = current->info.dims[i];
             isInside = isInside && thedim >= trackBox.dimmin[i] && thedim <= trackBox.dimmax[i];
         }
 
         if (isInside)
             closestNeighbour->push_back(current->info);
     }
     else
     {
         // Node case
         // If region( v->left ) is fully contained in the rectangle
         bool isFullyContained = true;
         bool hasIntersection = true;
 
         for (unsigned i = 0; i < DIM; ++i)
         {
             const auto regionmin = current->left->region.dimmin[i];
             const auto regionmax = current->left->region.dimmax[i];
             isFullyContained = isFullyContained && (regionmin >= trackBox.dimmin[i] && regionmax <= trackBox.dimmax[i]);
             hasIntersection = hasIntersection && (regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
         }
 
         if (isFullyContained)
         {
             this->addSubtree(current->left);
         }
         else if (hasIntersection)
         {
             this->recSearch(current->left, trackBox);
         }
 
         //if region( v->right ) is fully contained in the rectangle
         isFullyContained = true;
         hasIntersection = true;
 
         for (unsigned i = 0; i < DIM; ++i)
         {
             const auto regionmin = current->right->region.dimmin[i];
             const auto regionmax = current->right->region.dimmax[i];
             isFullyContained = isFullyContained && (regionmin >= trackBox.dimmin[i] && regionmax <= trackBox.dimmax[i]);
             hasIntersection = hasIntersection && (regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
         }
 
         if (isFullyContained)
         {
             this->addSubtree(current->right);
         }
         else if (hasIntersection)
         {
             this->recSearch(current->right, trackBox);
         }
     }
 }

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.

 {
     if (root_)
     {
         closestNeighbour = &recHits;
         this->recSearch(root_, trackBox);
         closestNeighbour = nullptr;
     }
 }

template<typename DATA , unsigned DIM>

int lar_content::KDTreeLinkerAlgo< DATA, DIM >::size ( void )

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.

 {
     return (nodePoolPos_ + 1);
 }

Member Data Documentation

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.

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.

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.

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.

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.

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:

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

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename DATA, unsigned DIM = 2> class lar_content::KDTreeLinkerAlgo< DATA, DIM >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename DATA, unsigned DIM = 2>
class lar_content::KDTreeLinkerAlgo< DATA, DIM >