All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Private Member Functions | Private Attributes | List of all members
lar_content::KDTreeLinkerAlgo< typename, int > 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, unsigned int>
class lar_content::KDTreeLinkerAlgo< typename, int >

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 }
lar_content::KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
The initial element list.
Definition: KDTreeLinkerAlgoT.h:155
lar_content::KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
The closest neighbour.
Definition: KDTreeLinkerAlgoT.h:154
lar_content::KDTreeLinkerAlgo::nodePoolSize_
int nodePoolSize_
The node pool size.
Definition: KDTreeLinkerAlgoT.h:151
lar_content::KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
Definition: KDTreeLinkerAlgoT.h:149
lar_content::KDTreeLinkerAlgo::nodePoolPos_
int nodePoolPos_
The node pool position.
Definition: KDTreeLinkerAlgoT.h:152
lar_content::KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Node pool allows us to do just 1 call to new for each tree building.
Definition: KDTreeLinkerAlgoT.h:150
template<typename DATA , unsigned DIM>
lar_content::KDTreeLinkerAlgo< DATA, DIM >::~KDTreeLinkerAlgo ( )
inline

Destructor calls clear.

Definition at line 175 of file KDTreeLinkerAlgoT.h.

176 {
177  this->clear();
178 }
lar_content::KDTreeLinkerAlgo::clear
void clear()
Clear all allocated structures.
Definition: KDTreeLinkerAlgoT.h:486

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.

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 }
lar_content::KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
The closest neighbour.
Definition: KDTreeLinkerAlgoT.h:154
lar_content::KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNodeT< DATA, DIM > *current)
Add all elements of an subtree to the closest elements. Used during the recSearch().
Definition: KDTreeLinkerAlgoT.h:421
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.

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 }
lar_content::KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
The initial element list.
Definition: KDTreeLinkerAlgoT.h:155
lar_content::KDTreeLinkerAlgo::nodePoolSize_
int nodePoolSize_
The node pool size.
Definition: KDTreeLinkerAlgoT.h:151
lar_content::KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
Definition: KDTreeLinkerAlgoT.h:149
lar_content::KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Node pool allows us to do just 1 call to new for each tree building.
Definition: KDTreeLinkerAlgoT.h:150
lar_content::KDTreeLinkerAlgo::recBuild
KDTreeNodeT< DATA, DIM > * recBuild(int low, int high, int depth, const KDTreeBoxT< DIM > &region)
Recursive kdtree builder. Is called by build()
Definition: KDTreeLinkerAlgoT.h:509
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.

487 {
488  if (root_)
489  this->clearTree();
490 }
lar_content::KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
Definition: KDTreeLinkerAlgoT.h:149
lar_content::KDTreeLinkerAlgo::clearTree
void clearTree()
Frees the KDTree.
Definition: KDTreeLinkerAlgoT.h:458
template<typename DATA , unsigned DIM>
void lar_content::KDTreeLinkerAlgo< DATA, DIM >::clearTree ( )
inlineprivate

Frees the KDTree.

Definition at line 458 of file KDTreeLinkerAlgoT.h.

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

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 }
lar_content::KDTreeNodeInfoT::dims
std::array< float, DIM > dims
Definition: KDTreeLinkerToolsT.h:84
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.

471 {
472  return (nodePoolPos_ == -1);
473 }
lar_content::KDTreeLinkerAlgo::nodePoolPos_
int nodePoolPos_
The node pool position.
Definition: KDTreeLinkerAlgoT.h:152
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.

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 }
lar_content::KDTreeLinkerAlgo::root_
KDTreeNodeT< DATA, DIM > * root_
The KDTree root.
Definition: KDTreeLinkerAlgoT.h:149
lar_content::KDTreeLinkerAlgo::recNearestNeighbour
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()
Definition: KDTreeLinkerAlgoT.h:359
icarus::distance
double distance(geo::Point_t const &point, CathodeDesc_t const &cathode)
Returns the distance of a point from the cathode.
Definition: CathodeCrossingUtils.cxx:35
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.

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 }
lar_content::KDTreeLinkerAlgo::nodePoolPos_
int nodePoolPos_
The node pool position.
Definition: KDTreeLinkerAlgoT.h:152
lar_content::KDTreeLinkerAlgo::nodePool_
KDTreeNodeT< DATA, DIM > * nodePool_
Node pool allows us to do just 1 call to new for each tree building.
Definition: KDTreeLinkerAlgoT.h:150
template<typename , unsigned int>
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.

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  {
231  std::swap((*initialEltList)[i], (*initialEltList)[j]);
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 }
lar_content::KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
The initial element list.
Definition: KDTreeLinkerAlgoT.h:155
gen_crt_frags.m
tuple m
now if test mode generate materials, CRT shell, world, gdml header else just generate CRT shell for u...
Definition: gen_crt_frags.py:1347
low
standard_dbscan3dalg useful for diagnostics hits not in a line will not be clustered on on only for track like only for track like on on the smaller the less shower like tracks low
Definition: clusteralgorithms.fcl:253
template<typename , unsigned int>
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.

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 }
lar_content::KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfoT< DATA, DIM > > * initialEltList
The initial element list.
Definition: KDTreeLinkerAlgoT.h:155
low
standard_dbscan3dalg useful for diagnostics hits not in a line will not be clustered on on only for track like only for track like on on the smaller the less shower like tracks low
Definition: clusteralgorithms.fcl:253
lar_content::KDTreeLinkerAlgo::getNextNode
KDTreeNodeT< DATA, DIM > * getNextNode()
Get the next node from the node pool.
Definition: KDTreeLinkerAlgoT.h:495
lar_content::KDTreeLinkerAlgo::recBuild
KDTreeNodeT< DATA, DIM > * recBuild(int low, int high, int depth, const KDTreeBoxT< DIM > &region)
Recursive kdtree builder. Is called by build()
Definition: KDTreeLinkerAlgoT.h:509
lar_content::KDTreeLinkerAlgo::medianSearch
int medianSearch(int low, int high, int treeDepth)
Fast median search with Wirth algorithm in eltList between low and high indexes.
Definition: KDTreeLinkerAlgoT.h:202
template<typename , unsigned int>
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.

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 }
lar_content::KDTreeLinkerAlgo::recNearestNeighbour
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()
Definition: KDTreeLinkerAlgoT.h:359
lar_content::KDTreeLinkerAlgo::dist2
float dist2(const KDTreeNodeInfoT< DATA, DIM > &a, const KDTreeNodeInfoT< DATA, DIM > &b) const
dist2
Definition: KDTreeLinkerAlgoT.h:442
lar_content::KDTreeNodeInfoT::dims
std::array< float, DIM > dims
Definition: KDTreeLinkerToolsT.h:84
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.

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 }
lar_content::KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfoT< DATA, DIM > > * closestNeighbour
The closest neighbour.
Definition: KDTreeLinkerAlgoT.h:154
lar_content::KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNodeT< DATA, DIM > *current)
Add all elements of an subtree to the closest elements. Used during the recSearch().
Definition: KDTreeLinkerAlgoT.h:421
lar_content::KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNodeT< DATA, DIM > *current, const KDTreeBoxT< DIM > &trackBox)
Recursive kdtree search. Is called by search()
Definition: KDTreeLinkerAlgoT.h:262
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.

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

479 {
480  return (nodePoolPos_ + 1);
481 }
lar_content::KDTreeLinkerAlgo::nodePoolPos_
int nodePoolPos_
The node pool position.
Definition: KDTreeLinkerAlgoT.h:152

Member Data Documentation

template<typename , unsigned int>
std::vector<KDTreeNodeInfoT<DATA, DIM> >* lar_content::KDTreeLinkerAlgo< typename, int >::closestNeighbour
private

The closest neighbour.

Definition at line 154 of file KDTreeLinkerAlgoT.h.

template<typename , unsigned int>
std::vector<KDTreeNodeInfoT<DATA, DIM> >* lar_content::KDTreeLinkerAlgo< typename, int >::initialEltList
private

The initial element list.

Definition at line 155 of file KDTreeLinkerAlgoT.h.

template<typename , unsigned int>
KDTreeNodeT<DATA, DIM>* lar_content::KDTreeLinkerAlgo< typename, int >::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 , unsigned int>
int lar_content::KDTreeLinkerAlgo< typename, int >::nodePoolPos_
private

The node pool position.

Definition at line 152 of file KDTreeLinkerAlgoT.h.

template<typename , unsigned int>
int lar_content::KDTreeLinkerAlgo< typename, int >::nodePoolSize_
private

The node pool size.

Definition at line 151 of file KDTreeLinkerAlgoT.h.

template<typename , unsigned int>
KDTreeNodeT<DATA, DIM>* lar_content::KDTreeLinkerAlgo< typename, int >::root_
private

The KDTree root.

Definition at line 149 of file KDTreeLinkerAlgoT.h.

The documentation for this class was generated from the following files:
Generated by   doxygen 1.8.5