LArSoft  v09_90_00
Liquid Argon Software toolkit - https://larsoft.org/
lar_content::KDTreeLinkerAlgo< DATA, DIM > Class Template Reference

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.

162  :
163  root_(nullptr),
164  nodePool_(nullptr),
165  nodePoolSize_(-1),
166  nodePoolPos_(-1),
167  closestNeighbour(nullptr),
168  initialEltList(nullptr)
169 {
170 }
int nodePoolPos_
The node pool position.
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
The initial element list.
int nodePoolSize_
The node pool size.
KDTreeNodeT< DATA, DIM > * nodePool_
Node pool allows us to do just 1 call to new for each tree building.
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
The closest neighbour.
template<typename DATA , unsigned DIM>
lar_content::KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo ( )
inline

Destructor calls clear.

Definition at line 175 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::clear().

176 {
177  this->clear();
178 }
void clear()
Clear all allocated structures.

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.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeNodeT< DATA, DIM >::left, and lar_content::KDTreeNodeT< DATA, DIM >::right.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::recSearch().

422 {
423  // By construction, current can't be null
424  //assert(current != 0);
425 
426  if ((current->left == nullptr) && (current->right == nullptr))
427  {
428  // Leaf case
429  closestNeighbour->push_back(current->info);
430  }
431  else
432  {
433  // Node case
434  this->addSubtree(current->left);
435  this->addSubtree(current->right);
436  }
437 }
void addSubtree(const KDTreeNodeT< DATA, DIM > *current)
Add all elements of an subtree to the closest elements. Used during the recSearch().
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
The closest neighbour.
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.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList, lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePool_, lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_, lar_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::EventSlicingTool::AssignRemainingHitsToSlices(), lar_content::DeltaRayMatchingContainers::BuildKDTree(), lar_content::IsolatedClusterMopUpAlgorithm::GetCaloHitToClusterMap(), lar_content::PreProcessingAlgorithm::GetFilteredCaloHitList(), lar_content::TransverseAssociationAlgorithm::GetNearbyClusterMap(), lar_content::VertexSelectionBaseAlgorithm::InitializeKDTrees(), lar_content::DeltaRayMatchingAlgorithm::InitializeNearbyClusterMap(), lar_content::TrainedVertexSelectionAlgorithm::PopulateKdTree(), and lar_content::CrossedTrackSplittingAlgorithm::PreparationStep().

184 {
185  if (eltList.size())
186  {
187  initialEltList = &eltList;
188  const size_t mysize = initialEltList->size();
189 
190  nodePoolSize_ = mysize * 2 - 1;
191  nodePool_ = new KDTreeNodeT<DATA, DIM>[nodePoolSize_];
192 
193  // Here we build the KDTree
194  root_ = this->recBuild(0, mysize, 0, region);
195  initialEltList = nullptr;
196  }
197 }
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
The initial element list.
int nodePoolSize_
The node pool size.
KDTreeNodeT< DATA, DIM > * nodePool_
Node pool allows us to do just 1 call to new for each tree building.
KDTreeNodeT< DATA, DIM > * recBuild(int low, int high, int depth, const KDTreeBoxT< DIM > &region)
Recursive kdtree builder. Is called by build()
template<typename DATA , unsigned DIM>
void lar_content::KDTreeLinkerAlgo< DATA, DIM >::clear ( )
inline
template<typename DATA , unsigned DIM>
void lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree ( )
inlineprivate

Frees the KDTree.

Definition at line 458 of file KDTreeLinkerAlgoT.h.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePool_, lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_, lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_, and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::clear().

459 {
460  delete[] nodePool_;
461  nodePool_ = nullptr;
462  root_ = nullptr;
463  nodePoolSize_ = -1;
464  nodePoolPos_ = -1;
465 }
int nodePoolPos_
The node pool position.
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
int nodePoolSize_
The node pool size.
KDTreeNodeT< DATA, DIM > * nodePool_
Node pool allows us to do just 1 call to new for each tree building.
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.

References d, and lar_content::KDTreeNodeInfoT< DATA, DIM >::dims.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::recNearestNeighbour().

443 {
444  double d = 0.;
445 
446  for (unsigned i = 0; i < DIM; ++i)
447  {
448  const double diff = a.dims[i] - b.dims[i];
449  d += diff * diff;
450  }
451 
452  return (float)d;
453 }
Float_t d
Definition: plot.C:235
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.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

Referenced by lar_content::VertexSelectionBaseAlgorithm::FilterVertexList(), and lar_content::VertexSelectionBaseAlgorithm::InitializeKDTrees().

471 {
472  return (nodePoolPos_ == -1);
473 }
int nodePoolPos_
The node pool position.
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.

References lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeLinkerAlgo< DATA, DIM >::recNearestNeighbour(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::IsolatedClusterMopUpAlgorithm::GetCaloHitToClusterMap(), and lar_content::EventSlicingTool::MatchClusterToSlice().

336 {
337  if (nullptr != result || distance != std::numeric_limits<float>::max())
338  {
339  result = nullptr;
340  distance = std::numeric_limits<float>::max();
341  }
342 
343  if (root_)
344  {
345  const KDTreeNodeT<DATA, DIM> *best_match = nullptr;
346  this->recNearestNeighbour(0, root_, point, best_match, distance);
347 
348  if (distance != std::numeric_limits<float>::max())
349  {
350  result = &(best_match->info);
351  distance = std::sqrt(distance);
352  }
353  }
354 }
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
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()
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.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePool_, and lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild().

496 {
497  ++nodePoolPos_;
498 
499  // The tree size is exactly 2 * nbrElts - 1 and this is the total allocated memory.
500  // If we have used more than that....there is a big problem.
501  //assert(nodePoolPos_ < nodePoolSize_);
502 
503  return &(nodePool_[nodePoolPos_]);
504 }
int nodePoolPos_
The node pool position.
KDTreeNodeT< DATA, DIM > * nodePool_
Node pool allows us to do just 1 call to new for each tree building.
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.

References lar_content::KDTreeNodeInfoT< DATA, DIM >::dims, and lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::recBuild().

203 {
204  // We should have at least 1 element to calculate the median...
205  //assert(low < high);
206 
207  const int nbrElts = high - low;
208  int median = nbrElts / 2 - (1 - 1 * (nbrElts & 1));
209  median += low;
210 
211  int l = low;
212  int m = high - 1;
213 
214  while (l < m)
215  {
216  KDTreeNodeInfoT<DATA, DIM> elt = (*initialEltList)[median];
217  int i = l;
218  int j = m;
219 
220  do
221  {
222  // The even depth is associated to dim1 dimension, the odd one to dim2 dimension
223  const unsigned thedim = treeDepth % DIM;
224  while ((*initialEltList)[i].dims[thedim] < elt.dims[thedim])
225  ++i;
226  while ((*initialEltList)[j].dims[thedim] > elt.dims[thedim])
227  --j;
228 
229  if (i <= j)
230  {
232  i++;
233  j--;
234  }
235  } while (i <= j);
236 
237  if (j < median)
238  l = i;
239  if (i > median)
240  m = j;
241  }
242 
243  return median;
244 }
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
The initial element list.
void swap(lar::deep_const_fwd_iterator_nested< CITER, INNERCONTEXTRACT > &a, lar::deep_const_fwd_iterator_nested< CITER, INNERCONTEXTRACT > &b)
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.

References lar_content::KDTreeBoxT< DIM >::dimmax, lar_content::KDTreeBoxT< DIM >::dimmin, lar_content::KDTreeLinkerAlgo< DATA, DIM >::getNextNode(), lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList, lar_content::KDTreeNodeT< DATA, DIM >::left, lar_content::KDTreeLinkerAlgo< DATA, DIM >::medianSearch(), lar_content::KDTreeNodeT< DATA, DIM >::right, and lar_content::KDTreeNodeT< DATA, DIM >::setAttributs().

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::build().

510 {
511  const int portionSize = high - low;
512 
513  // By construction, portionSize > 0 can't happen.
514  //assert(portionSize > 0);
515 
516  if (portionSize == 1)
517  {
518  // Leaf case
519  KDTreeNodeT<DATA, DIM> *leaf = this->getNextNode();
520  leaf->setAttributs(region, (*initialEltList)[low]);
521  return leaf;
522  }
523  else
524  {
525  // The even depth is associated to dim1 dimension, the odd one to dim2 dimension
526  int medianId = this->medianSearch(low, high, depth);
527 
528  // We create the node
529  KDTreeNodeT<DATA, DIM> *node = this->getNextNode();
530  node->setAttributs(region);
531  node->info = (*initialEltList)[medianId];
532 
533  // Here we split into 2 halfplanes the current plane
534  KDTreeBoxT<DIM> leftRegion = region;
535  KDTreeBoxT<DIM> rightRegion = region;
536 
537  const unsigned thedim = depth % DIM;
538  auto medianVal = (*initialEltList)[medianId].dims[thedim];
539  leftRegion.dimmax[thedim] = medianVal;
540  rightRegion.dimmin[thedim] = medianVal;
541 
542  ++depth;
543  ++medianId;
544 
545  // We recursively build the son nodes
546  node->left = this->recBuild(low, medianId, depth, leftRegion);
547  node->right = this->recBuild(medianId, high, depth, rightRegion);
548  return node;
549  }
550 }
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
The initial element list.
KDTreeNodeT< DATA, DIM > * getNextNode()
Get the next node from the node pool.
KDTreeNodeT< DATA, DIM > * recBuild(int low, int high, int depth, const KDTreeBoxT< DIM > &region)
Recursive kdtree builder. Is called by build()
int medianSearch(int low, int high, int treeDepth)
Fast median search with Wirth algorithm in eltList between low and high indexes.
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.

References lar_content::KDTreeNodeInfoT< DATA, DIM >::dims, lar_content::KDTreeLinkerAlgo< DATA, DIM >::dist2(), f, lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeNodeT< DATA, DIM >::left, and lar_content::KDTreeNodeT< DATA, DIM >::right.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::findNearestNeighbour().

361 {
362  const unsigned int current_dim = depth % DIM;
363 
364  if (current->left == nullptr && current->right == nullptr)
365  {
366  best_match = current;
367  best_dist = this->dist2(point, best_match->info);
368  return;
369  }
370  else
371  {
372  const float dist_to_axis = point.dims[current_dim] - current->info.dims[current_dim];
373 
374  if (dist_to_axis < 0.f)
375  {
376  this->recNearestNeighbour(depth + 1, current->left, point, best_match, best_dist);
377  }
378  else
379  {
380  this->recNearestNeighbour(depth + 1, current->right, point, best_match, best_dist);
381  }
382 
383  // 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
384  const float dist_current = this->dist2(point, current->info);
385 
386  if (dist_current < best_dist)
387  {
388  best_dist = dist_current;
389  best_match = current;
390  }
391 
392  // Now we see if the radius to best crosses the splitting axis
393  if (best_dist > dist_to_axis * dist_to_axis)
394  {
395  // if it does we traverse the other side of the axis to check for a new best
396  const KDTreeNodeT<DATA, DIM> *check_best = best_match;
397  float check_dist = best_dist;
398 
399  if (dist_to_axis < 0.f)
400  {
401  this->recNearestNeighbour(depth + 1, current->right, point, check_best, check_dist);
402  }
403  else
404  {
405  this->recNearestNeighbour(depth + 1, current->left, point, check_best, check_dist);
406  }
407 
408  if (check_dist < best_dist)
409  {
410  best_dist = check_dist;
411  best_match = check_best;
412  }
413  }
414  return;
415  }
416 }
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()
TFile f
Definition: plotHisto.C:6
float dist2(const KDTreeNodeInfoT< DATA, DIM > &a, const KDTreeNodeInfoT< DATA, DIM > &b) const
dist2
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.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::addSubtree(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, lar_content::KDTreeBoxT< DIM >::dimmax, lar_content::KDTreeBoxT< DIM >::dimmin, lar_content::KDTreeNodeT< DATA, DIM >::info, lar_content::KDTreeNodeT< DATA, DIM >::left, and lar_content::KDTreeNodeT< DATA, DIM >::right.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::search().

263 {
264  // By construction, current can't be null
265  //assert(current != 0);
266  // By Construction, a node can't have just 1 son.
267  //assert (!(((current->left == 0) && (current->right != 0)) || ((current->left != 0) && (current->right == 0))));
268 
269  if ((current->left == nullptr) && (current->right == nullptr))
270  {
271  // Leaf case
272  // If point inside the rectangle/area
273  bool isInside = true;
274 
275  for (unsigned i = 0; i < DIM; ++i)
276  {
277  const auto thedim = current->info.dims[i];
278  isInside = isInside && thedim >= trackBox.dimmin[i] && thedim <= trackBox.dimmax[i];
279  }
280 
281  if (isInside)
282  closestNeighbour->push_back(current->info);
283  }
284  else
285  {
286  // Node case
287  // If region( v->left ) is fully contained in the rectangle
288  bool isFullyContained = true;
289  bool hasIntersection = true;
290 
291  for (unsigned i = 0; i < DIM; ++i)
292  {
293  const auto regionmin = current->left->region.dimmin[i];
294  const auto regionmax = current->left->region.dimmax[i];
295  isFullyContained = isFullyContained && (regionmin >= trackBox.dimmin[i] && regionmax <= trackBox.dimmax[i]);
296  hasIntersection = hasIntersection && (regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
297  }
298 
299  if (isFullyContained)
300  {
301  this->addSubtree(current->left);
302  }
303  else if (hasIntersection)
304  {
305  this->recSearch(current->left, trackBox);
306  }
307 
308  //if region( v->right ) is fully contained in the rectangle
309  isFullyContained = true;
310  hasIntersection = true;
311 
312  for (unsigned i = 0; i < DIM; ++i)
313  {
314  const auto regionmin = current->right->region.dimmin[i];
315  const auto regionmax = current->right->region.dimmax[i];
316  isFullyContained = isFullyContained && (regionmin >= trackBox.dimmin[i] && regionmax <= trackBox.dimmax[i]);
317  hasIntersection = hasIntersection && (regionmin < trackBox.dimmax[i] && regionmax > trackBox.dimmin[i]);
318  }
319 
320  if (isFullyContained)
321  {
322  this->addSubtree(current->right);
323  }
324  else if (hasIntersection)
325  {
326  this->recSearch(current->right, trackBox);
327  }
328  }
329 }
void addSubtree(const KDTreeNodeT< DATA, DIM > *current)
Add all elements of an subtree to the closest elements. Used during the recSearch().
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
The closest neighbour.
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Recursive kdtree search. Is called by 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.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour, lar_content::KDTreeLinkerAlgo< DATA, DIM >::recSearch(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::root_.

Referenced by lar_content::DeltaRayMatchingContainers::AddToClusterProximityMap(), lar_content::RPhiFeatureTool::FillKernelEstimate(), lar_content::PreProcessingAlgorithm::GetFilteredCaloHitList(), lar_content::TransverseAssociationAlgorithm::GetNearbyClusterMap(), lar_content::TrainedVertexSelectionAlgorithm::IncrementSharedAxisValues(), lar_content::DeltaRayMatchingAlgorithm::InitializeNearbyClusterMap(), lar_content::VertexSelectionBaseAlgorithm::IsVertexOnHit(), lar_content::TrainedVertexSelectionAlgorithm::PopulateKdTree(), lar_content::CrossedTrackSplittingAlgorithm::PreparationStep(), and lar_content::VertexSelectionBaseAlgorithm::VertexHitEnergy().

250 {
251  if (root_)
252  {
253  closestNeighbour = &recHits;
254  this->recSearch(root_, trackBox);
255  closestNeighbour = nullptr;
256  }
257 }
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
The closest neighbour.
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Recursive kdtree search. Is called by search()
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.

References lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolPos_.

479 {
480  return (nodePoolPos_ + 1);
481 }
int nodePoolPos_
The node pool position.

Member Data Documentation

template<typename DATA, unsigned DIM = 2>
std::vector<KDTreeNodeInfoT<DATA, DIM> >* lar_content::KDTreeLinkerAlgo< DATA, DIM >::closestNeighbour
private
template<typename DATA, unsigned DIM = 2>
std::vector<KDTreeNodeInfoT<DATA, DIM> >* lar_content::KDTreeLinkerAlgo< DATA, DIM >::initialEltList
private
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.

Referenced by lar_content::KDTreeLinkerAlgo< DATA, DIM >::build(), lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree(), and lar_content::KDTreeLinkerAlgo< DATA, DIM >::getNextNode().

template<typename DATA, unsigned DIM = 2>
int lar_content::KDTreeLinkerAlgo< DATA, DIM >::nodePoolSize_
private

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