CMS 3D CMS Logo
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Pages
List of all members | Public Member Functions | Private Member Functions | Private Attributes
KDTreeLinkerAlgo< DATA > Class Template Reference

#include <KDTreeLinkerAlgo.h>

Public Member Functions

void build (std::vector< KDTreeNodeInfo > &eltList, const KDTreeBox &region)
 
void build (std::vector< KDTreeNodeInfo< DATA > > &eltList, const KDTreeBox &region)
 
void clear ()
 
void clear ()
 
bool empty ()
 
 KDTreeLinkerAlgo ()
 
 KDTreeLinkerAlgo ()
 
void search (const KDTreeBox &searchBox, std::vector< KDTreeNodeInfo > &resRecHitList)
 
void search (const KDTreeBox &searchBox, std::vector< KDTreeNodeInfo< DATA > > &resRecHitList)
 
int size ()
 
 ~KDTreeLinkerAlgo ()
 
 ~KDTreeLinkerAlgo ()
 

Private Member Functions

void addSubtree (const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)
 
void addSubtree (const KDTreeNode< DATA > *current)
 
void clearTree ()
 
void clearTree ()
 
KDTreeNode * getNextNode ()
 
KDTreeNode< DATA > * getNextNode ()
 
int medianSearch (std::vector< KDTreeNodeInfo > &eltList, int low, int high, int treeDepth)
 
int medianSearch (int low, int high, int treeDepth)
 
KDTreeNode * recBuild (std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox &region)
 
KDTreeNode< DATA > * recBuild (int low, int hight, int depth, const KDTreeBox &region)
 
void recSearch (const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
 
void recSearch (const KDTreeNode< DATA > *current, const KDTreeBox &trackBox)
 
void swap (KDTreeNodeInfo &e1, KDTreeNodeInfo &e2)
 

Private Attributes

std::vector< KDTreeNodeInfo
< DATA > > * 		closestNeighbour
 
std::vector< KDTreeNodeInfo
< DATA > > * 		initialEltList
 
KDTreeNode * nodePool_
 
KDTreeNode< DATA > * nodePool_
 
int nodePoolPos_
 
int nodePoolSize_
 
KDTreeNode * root_
 
KDTreeNode< DATA > * root_
 

Detailed Description

template<typename DATA>
class KDTreeLinkerAlgo< DATA >

Definition at line 10 of file KDTreeLinkerAlgo.h.

Constructor & Destructor Documentation

template<typename DATA >
KDTreeLinkerAlgo< DATA >::KDTreeLinkerAlgo ( )

Definition at line 3 of file KDTreeLinkerAlgo.cc.

4  : root_ (0),
5  nodePool_(0),
6  nodePoolSize_(-1),
7  nodePoolPos_(-1)
8 {
9 }
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
template<typename DATA >
KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo ( )

Definition at line 11 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA >::clear().

12 {
13  clear();
14 }
template<typename DATA>
KDTreeLinkerAlgo< DATA >::KDTreeLinkerAlgo ( )
template<typename DATA>
KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo ( )

Member Function Documentation

template<typename DATA>
void KDTreeLinkerAlgo< DATA >::addSubtree ( const KDTreeNode *  current,
std::vector< KDTreeNodeInfo > &  recHits 
)
private

Definition at line 209 of file KDTreeLinkerAlgo.cc.

References KDTreeNode< DATA >::left, KDTreeNode< DATA >::rh, and KDTreeNode< DATA >::right.

Referenced by KDTreeLinkerAlgo< DATA >::recSearch().

211 {
212  // By construction, current can't be null
213  assert(current != 0);
214 
215  if ((current->left == 0) && (current->right == 0)) // leaf
216  recHits.push_back(current->rh);
217  else { // node
218  addSubtree(current->left, recHits);
219  addSubtree(current->right, recHits);
220  }
221 }
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:209
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeNode::rh
KDTreeNodeInfo rh
Definition: KDTreeLinkerTools.h:67
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
template<typename DATA >
void KDTreeLinkerAlgo< DATA >::addSubtree ( const KDTreeNode< DATA > *  current)
private

Definition at line 224 of file KDTreeLinkerAlgo.h.

References KDTreeNode< DATA >::info, KDTreeNode< DATA >::left, and KDTreeNode< DATA >::right.

225 {
226  // By construction, current can't be null
227  // assert(current != 0);
228 
229  if ((current->left == 0) && (current->right == 0)) // leaf
230  closestNeighbour->push_back(current->info);
231  else { // node
232  addSubtree(current->left);
233  addSubtree(current->right);
234  }
235 }
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:209
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfo< DATA > > * closestNeighbour
Definition: KDTreeLinkerAlgo.h:51
KDTreeNode::info
KDTreeNodeInfo< DATA > info
Definition: KDTreeLinkerTools.h:54
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
template<typename DATA >
void KDTreeLinkerAlgo< DATA >::build ( std::vector< KDTreeNodeInfo > &  eltList,
const KDTreeBox &  region 
)

Definition at line 17 of file KDTreeLinkerAlgo.cc.

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

Referenced by KDTreeLinkerTrackEcal::buildTree(), KDTreeLinkerTrackHcal::buildTree(), KDTreeLinkerPSEcal::buildTree(), PixelTripletLargeTipGenerator::hitTriplets(), and PixelTripletHLTGenerator::hitTriplets().

19 {
20  if (eltList.size()) {
21  nodePoolSize_ = eltList.size() * 2 - 1;
22  nodePool_ = new KDTreeNode[nodePoolSize_];
23 
24  // Here we build the KDTree
25  root_ = recBuild(eltList, 0, eltList.size(), 0, region);
26  }
27 }
KDTreeLinkerAlgo::recBuild
KDTreeNode * recBuild(std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox &region)
Definition: KDTreeLinkerAlgo.cc:31
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
template<typename DATA>
void KDTreeLinkerAlgo< DATA >::build ( std::vector< KDTreeNodeInfo< DATA > > &  eltList,
const KDTreeBox &  region 
)
template<typename DATA >
void KDTreeLinkerAlgo< DATA >::clear ( void  )

Definition at line 235 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA >::clearTree(), and KDTreeLinkerAlgo< DATA >::root_.

Referenced by KDTreeLinkerPSEcal::clear(), KDTreeLinkerTrackHcal::clear(), KDTreeLinkerTrackEcal::clear(), and KDTreeLinkerAlgo< DATA >::~KDTreeLinkerAlgo().

236 {
237  if (root_)
238  clearTree();
239 }
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
template<typename DATA>
void KDTreeLinkerAlgo< DATA >::clear ( )
template<typename DATA >
void KDTreeLinkerAlgo< DATA >::clearTree ( )
private

Definition at line 225 of file KDTreeLinkerAlgo.cc.

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

Referenced by KDTreeLinkerAlgo< DATA >::clear().

226 {
227  delete[] nodePool_;
228  nodePool_ = 0;
229  root_ = 0;
230  nodePoolSize_ = -1;
231  nodePoolPos_ = -1;
232 }
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
template<typename DATA>
void KDTreeLinkerAlgo< DATA >::clearTree ( )
private
template<typename DATA>
bool KDTreeLinkerAlgo< DATA >::empty ( void  )
inline

Definition at line 31 of file KDTreeLinkerAlgo.h.

References KDTreeLinkerAlgo< DATA >::nodePoolPos_.

31 {return nodePoolPos_ == -1;}
template<typename DATA >
KDTreeNode< DATA > * KDTreeLinkerAlgo< DATA >::getNextNode ( )
private

Definition at line 243 of file KDTreeLinkerAlgo.cc.

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

Referenced by KDTreeLinkerAlgo< DATA >::recBuild().

244 {
245  ++nodePoolPos_;
246 
247  // The tree size is exactly 2 * nbrElts - 1 and this is the total allocated memory.
248  // If we have used more than that....there is a big problem.
249  assert(nodePoolPos_ < nodePoolSize_);
250 
251  return &(nodePool_[nodePoolPos_]);
252 }
KDTreeLinkerAlgo::nodePool_
KDTreeNode * nodePool_
Definition: KDTreeLinkerAlgo.h:35
template<typename DATA>
KDTreeNode<DATA>* KDTreeLinkerAlgo< DATA >::getNextNode ( )
private
template<typename DATA>
int KDTreeLinkerAlgo< DATA >::medianSearch ( std::vector< KDTreeNodeInfo > &  eltList,
int  low,
int  high,
int  treeDepth 
)
private

Definition at line 90 of file KDTreeLinkerAlgo.cc.

References KDTreeNodeInfo< DATA >::dim1, KDTreeNodeInfo< DATA >::dim2, i, j, prof2calltree::l, m, and KDTreeLinkerAlgo< DATA >::swap().

Referenced by KDTreeLinkerAlgo< DATA >::recBuild().

94 {
95  //We should have at least 1 element to calculate the median...
96  assert(low < high);
97 
98  int nbrElts = high - low;
99  int median = (nbrElts & 1) ? nbrElts / 2
100  : nbrElts / 2 - 1;
101  median += low;
102 
103  int l = low;
104  int m = high - 1;
105 
106  while (l < m) {
107  KDTreeNodeInfo elt = eltList[median];
108  int i = l;
109  int j = m;
110 
111  do {
112 
113  // The even depth is associated to dim1 dimension
114  // The odd one to dim2 dimension
115  if (treeDepth & 1) {
116  while (eltList[i].dim2 < elt.dim2) i++;
117  while (eltList[j].dim2 > elt.dim2) j--;
118  } else {
119  while (eltList[i].dim1 < elt.dim1) i++;
120  while (eltList[j].dim1 > elt.dim1) j--;
121  }
122 
123  if (i <= j){
124  swap(eltList[i], eltList[j]);
125  i++;
126  j--;
127  }
128  } while (i <= j);
129  if (j < median) l = i;
130  if (i > median) m = j;
131  }
132 
133  return median;
134 }
i
int i
Definition: DBlmapReader.cc:9
j
int j
Definition: DBlmapReader.cc:9
KDTreeLinkerAlgo::swap
void swap(KDTreeNodeInfo &e1, KDTreeNodeInfo &e2)
Definition: KDTreeLinkerAlgo.cc:137
template<typename DATA >
int KDTreeLinkerAlgo< DATA >::medianSearch ( int  low,
int  high,
int  treeDepth 
)
private

Definition at line 106 of file KDTreeLinkerAlgo.h.

References KDTreeNodeInfo< DATA >::dim1, KDTreeNodeInfo< DATA >::dim2, i, j, prof2calltree::l, m, and std::swap().

109 {
110  //We should have at least 1 element to calculate the median...
111  //assert(low < high);
112 
113  int nbrElts = high - low;
114  int median = (nbrElts & 1) ? nbrElts / 2
115  : nbrElts / 2 - 1;
116  median += low;
117 
118  int l = low;
119  int m = high - 1;
120 
121  while (l < m) {
122  KDTreeNodeInfo<DATA> elt = (*initialEltList)[median];
123  int i = l;
124  int j = m;
125 
126  do {
127  // The even depth is associated to dim1 dimension
128  // The odd one to dim2 dimension
129  if (treeDepth & 1) {
130  while ((*initialEltList)[i].dim2 < elt.dim2) i++;
131  while ((*initialEltList)[j].dim2 > elt.dim2) j--;
132  } else {
133  while ((*initialEltList)[i].dim1 < elt.dim1) i++;
134  while ((*initialEltList)[j].dim1 > elt.dim1) j--;
135  }
136 
137  if (i <= j){
138  std::swap((*initialEltList)[i], (*initialEltList)[j]);
139  i++;
140  j--;
141  }
142  } while (i <= j);
143  if (j < median) l = i;
144  if (i > median) m = j;
145  }
146 
147  return median;
148 }
i
int i
Definition: DBlmapReader.cc:9
KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfo< DATA > > * initialEltList
Definition: KDTreeLinkerAlgo.h:52
std::swap
void swap(edm::DataFrameContainer &lhs, edm::DataFrameContainer &rhs)
Definition: DataFrameContainer.h:223
j
int j
Definition: DBlmapReader.cc:9
template<typename DATA>
KDTreeNode * KDTreeLinkerAlgo< DATA >::recBuild ( std::vector< KDTreeNodeInfo > &  eltList,
int  low,
int  hight,
int  depth,
const KDTreeBox &  region 
)
private

Definition at line 31 of file KDTreeLinkerAlgo.cc.

References KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeLinkerAlgo< DATA >::getNextNode(), python.Node::leaf, KDTreeNode< DATA >::left, KDTreeLinkerAlgo< DATA >::medianSearch(), python.Node::node, KDTreeNode< DATA >::right, and KDTreeNode< DATA >::setAttributs().

Referenced by KDTreeLinkerAlgo< DATA >::build().

36 {
37  int portionSize = high - low;
38 
39  // By construction, portionSize > 0 can't happend.
40  assert(portionSize > 0);
41 
42  if (portionSize == 1) { // Leaf case
43 
44  KDTreeNode *leaf = getNextNode();
45  leaf->setAttributs(region, eltList[low]);
46  return leaf;
47 
48  } else { // Node case
49 
50  // The even depth is associated to dim1 dimension
51  // The odd one to dim2 dimension
52  int medianId = medianSearch(eltList, low, high, depth);
53 
54  // We create the node
55  KDTreeNode *node = getNextNode();
56  node->setAttributs(region);
57 
58 
59  // Here we split into 2 halfplanes the current plane
60  KDTreeBox leftRegion = region;
61  KDTreeBox rightRegion = region;
62  if (depth & 1) {
63 
64  double medianVal = eltList[medianId].dim2;
65  leftRegion.dim2max = medianVal;
66  rightRegion.dim2min = medianVal;
67 
68  } else {
69 
70  double medianVal = eltList[medianId].dim1;
71  leftRegion.dim1max = medianVal;
72  rightRegion.dim1min = medianVal;
73 
74  }
75 
76  ++depth;
77  ++medianId;
78 
79  // We recursively build the son nodes
80  node->left = recBuild(eltList, low, medianId, depth, leftRegion);
81  node->right = recBuild(eltList, medianId, high, depth, rightRegion);
82 
83  return node;
84  }
85 }
KDTreeNode::setAttributs
void setAttributs(const KDTreeBox &regionBox, const KDTreeNodeInfo &rhinfo)
Definition: KDTreeLinkerTools.h:80
KDTreeLinkerAlgo::medianSearch
int medianSearch(std::vector< KDTreeNodeInfo > &eltList, int low, int high, int treeDepth)
Definition: KDTreeLinkerAlgo.cc:90
KDTreeLinkerAlgo::getNextNode
KDTreeNode * getNextNode()
Definition: KDTreeLinkerAlgo.cc:243
python.Node.node
tuple node
Definition: Node.py:50
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
python.Node.leaf
tuple leaf
Definition: Node.py:62
KDTreeLinkerAlgo::recBuild
KDTreeNode * recBuild(std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox &region)
Definition: KDTreeLinkerAlgo.cc:31
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
template<typename DATA >
KDTreeNode< DATA > * KDTreeLinkerAlgo< DATA >::recBuild ( int  low,
int  hight,
int  depth,
const KDTreeBox &  region 
)
private

Definition at line 292 of file KDTreeLinkerAlgo.h.

References KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, python.Node::leaf, KDTreeNode< DATA >::left, python.Node::node, KDTreeNode< DATA >::right, and KDTreeNode< DATA >::setAttributs().

296 {
297  int portionSize = high - low;
298 
299  // By construction, portionSize > 0 can't happend.
300  // assert(portionSize > 0);
301 
302  if (portionSize == 1) { // Leaf case
303 
304  KDTreeNode<DATA> *leaf = getNextNode();
305  leaf->setAttributs(region, (*initialEltList)[low]);
306  return leaf;
307 
308  } else { // Node case
309 
310  // The even depth is associated to dim1 dimension
311  // The odd one to dim2 dimension
312  int medianId = medianSearch(low, high, depth);
313 
314  // We create the node
315  KDTreeNode<DATA> *node = getNextNode();
316  node->setAttributs(region);
317 
318 
319  // Here we split into 2 halfplanes the current plane
320  KDTreeBox leftRegion = region;
321  KDTreeBox rightRegion = region;
322  if (depth & 1) {
323 
324  auto medianVal = (*initialEltList)[medianId].dim2;
325  leftRegion.dim2max = medianVal;
326  rightRegion.dim2min = medianVal;
327 
328  } else {
329 
330  auto medianVal = (*initialEltList)[medianId].dim1;
331  leftRegion.dim1max = medianVal;
332  rightRegion.dim1min = medianVal;
333 
334  }
335 
336  ++depth;
337  ++medianId;
338 
339  // We recursively build the son nodes
340  node->left = recBuild(low, medianId, depth, leftRegion);
341  node->right = recBuild(medianId, high, depth, rightRegion);
342 
343  return node;
344  }
345 }
KDTreeNode::setAttributs
void setAttributs(const KDTreeBox &regionBox, const KDTreeNodeInfo &rhinfo)
Definition: KDTreeLinkerTools.h:80
KDTreeLinkerAlgo::medianSearch
int medianSearch(std::vector< KDTreeNodeInfo > &eltList, int low, int high, int treeDepth)
Definition: KDTreeLinkerAlgo.cc:90
KDTreeLinkerAlgo::getNextNode
KDTreeNode * getNextNode()
Definition: KDTreeLinkerAlgo.cc:243
KDTreeLinkerAlgo::initialEltList
std::vector< KDTreeNodeInfo< DATA > > * initialEltList
Definition: KDTreeLinkerAlgo.h:52
python.Node.node
tuple node
Definition: Node.py:50
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
python.Node.leaf
tuple leaf
Definition: Node.py:62
KDTreeLinkerAlgo::recBuild
KDTreeNode * recBuild(std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox &region)
Definition: KDTreeLinkerAlgo.cc:31
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
template<typename DATA>
void KDTreeLinkerAlgo< DATA >::recSearch ( const KDTreeNode *  current,
const KDTreeBox &  trackBox,
std::vector< KDTreeNodeInfo > &  recHits 
)
private

Definition at line 154 of file KDTreeLinkerAlgo.cc.

References KDTreeLinkerAlgo< DATA >::addSubtree(), KDTreeNodeInfo< DATA >::dim1, KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeNodeInfo< DATA >::dim2, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeNode< DATA >::left, KDTreeNode< DATA >::region, KDTreeNode< DATA >::rh, and KDTreeNode< DATA >::right.

Referenced by KDTreeLinkerAlgo< DATA >::search().

157 {
158  // By construction, current can't be null
159  assert(current != 0);
160 
161  // By Construction, a node can't have just 1 son.
162  assert (!(((current->left == 0) && (current->right != 0)) ||
163  ((current->left != 0) && (current->right == 0))));
164 
165  if ((current->left == 0) && (current->right == 0)) {//leaf case
166 
167  // If point inside the rectangle/area
168  if ((current->rh.dim1 >= trackBox.dim1min) && (current->rh.dim1 <= trackBox.dim1max) &&
169  (current->rh.dim2 >= trackBox.dim2min) && (current->rh.dim2 <= trackBox.dim2max))
170  recHits.push_back(current->rh);
171 
172  } else {
173 
174  //if region( v->left ) is fully contained in the rectangle
175  if ((current->left->region.dim1min >= trackBox.dim1min) &&
176  (current->left->region.dim1max <= trackBox.dim1max) &&
177  (current->left->region.dim2min >= trackBox.dim2min) &&
178  (current->left->region.dim2max <= trackBox.dim2max))
179  addSubtree(current->left, recHits);
180 
181  else { //if region( v->left ) intersects the rectangle
182 
183  if (!((current->left->region.dim1min >= trackBox.dim1max) ||
184  (current->left->region.dim1max <= trackBox.dim1min) ||
185  (current->left->region.dim2min >= trackBox.dim2max) ||
186  (current->left->region.dim2max <= trackBox.dim2min)))
187  recSearch(current->left, trackBox, recHits);
188  }
189 
190  //if region( v->right ) is fully contained in the rectangle
191  if ((current->right->region.dim1min >= trackBox.dim1min) &&
192  (current->right->region.dim1max <= trackBox.dim1max) &&
193  (current->right->region.dim2min >= trackBox.dim2min) &&
194  (current->right->region.dim2max <= trackBox.dim2max))
195  addSubtree(current->right, recHits);
196 
197  else { //if region( v->right ) intersects the rectangle
198 
199  if (!((current->right->region.dim1min >= trackBox.dim1max) ||
200  (current->right->region.dim1max <= trackBox.dim1min) ||
201  (current->right->region.dim2min >= trackBox.dim2max) ||
202  (current->right->region.dim2max <= trackBox.dim2min)))
203  recSearch(current->right, trackBox, recHits);
204  }
205  }
206 }
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:154
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:209
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeNode::rh
KDTreeNodeInfo rh
Definition: KDTreeLinkerTools.h:67
KDTreeNode::region
KDTreeBox region
Definition: KDTreeLinkerTools.h:73
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
template<typename DATA >
void KDTreeLinkerAlgo< DATA >::recSearch ( const KDTreeNode< DATA > *  current,
const KDTreeBox &  trackBox 
)
private

Definition at line 167 of file KDTreeLinkerAlgo.h.

References KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeNode< DATA >::info, KDTreeNode< DATA >::left, KDTreeNode< DATA >::region, and KDTreeNode< DATA >::right.

169 {
170  /*
171  // By construction, current can't be null
172  assert(current != 0);
173 
174  // By Construction, a node can't have just 1 son.
175  assert (!(((current->left == 0) && (current->right != 0)) ||
176  ((current->left != 0) && (current->right == 0))));
177  */
178 
179  if ((current->left == 0) && (current->right == 0)) {//leaf case
180 
181  // If point inside the rectangle/area
182  if ((current->info.dim1 >= trackBox.dim1min) && (current->info.dim1 <= trackBox.dim1max) &&
183  (current->info.dim2 >= trackBox.dim2min) && (current->info.dim2 <= trackBox.dim2max))
184  closestNeighbour->push_back(current->info);
185 
186  } else {
187 
188  //if region( v->left ) is fully contained in the rectangle
189  if ((current->left->region.dim1min >= trackBox.dim1min) &&
190  (current->left->region.dim1max <= trackBox.dim1max) &&
191  (current->left->region.dim2min >= trackBox.dim2min) &&
192  (current->left->region.dim2max <= trackBox.dim2max))
193  addSubtree(current->left);
194 
195  else { //if region( v->left ) intersects the rectangle
196 
197  if (!((current->left->region.dim1min >= trackBox.dim1max) ||
198  (current->left->region.dim1max <= trackBox.dim1min) ||
199  (current->left->region.dim2min >= trackBox.dim2max) ||
200  (current->left->region.dim2max <= trackBox.dim2min)))
201  recSearch(current->left, trackBox);
202  }
203 
204  //if region( v->right ) is fully contained in the rectangle
205  if ((current->right->region.dim1min >= trackBox.dim1min) &&
206  (current->right->region.dim1max <= trackBox.dim1max) &&
207  (current->right->region.dim2min >= trackBox.dim2min) &&
208  (current->right->region.dim2max <= trackBox.dim2max))
209  addSubtree(current->right);
210 
211  else { //if region( v->right ) intersects the rectangle
212 
213  if (!((current->right->region.dim1min >= trackBox.dim1max) ||
214  (current->right->region.dim1max <= trackBox.dim1min) ||
215  (current->right->region.dim2min >= trackBox.dim2max) ||
216  (current->right->region.dim2max <= trackBox.dim2min)))
217  recSearch(current->right, trackBox);
218  }
219  }
220 }
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:154
KDTreeLinkerAlgo::addSubtree
void addSubtree(const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:209
KDTreeNode::left
KDTreeNode * left
Definition: KDTreeLinkerTools.h:70
KDTreeLinkerAlgo::closestNeighbour
std::vector< KDTreeNodeInfo< DATA > > * closestNeighbour
Definition: KDTreeLinkerAlgo.h:51
KDTreeNode::info
KDTreeNodeInfo< DATA > info
Definition: KDTreeLinkerTools.h:54
KDTreeNode::region
KDTreeBox region
Definition: KDTreeLinkerTools.h:73
KDTreeNode::right
KDTreeNode * right
Definition: KDTreeLinkerTools.h:70
template<typename DATA >
void KDTreeLinkerAlgo< DATA >::search ( const KDTreeBox &  searchBox,
std::vector< KDTreeNodeInfo > &  resRecHitList 
)

Definition at line 146 of file KDTreeLinkerAlgo.cc.

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

Referenced by PixelTripletLargeTipGenerator::hitTriplets(), PixelTripletHLTGenerator::hitTriplets(), KDTreeLinkerPSEcal::searchLinks(), KDTreeLinkerTrackHcal::searchLinks(), and KDTreeLinkerTrackEcal::searchLinks().

148 {
149  if (root_)
150  recSearch(root_, trackBox, recHits);
151 }
KDTreeLinkerAlgo::recSearch
void recSearch(const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits)
Definition: KDTreeLinkerAlgo.cc:154
KDTreeLinkerAlgo::root_
KDTreeNode * root_
Definition: KDTreeLinkerAlgo.h:32
template<typename DATA>
void KDTreeLinkerAlgo< DATA >::search ( const KDTreeBox &  searchBox,
std::vector< KDTreeNodeInfo< DATA > > &  resRecHitList 
)
template<typename DATA>
int KDTreeLinkerAlgo< DATA >::size ( void  )
inline

Definition at line 35 of file KDTreeLinkerAlgo.h.

References KDTreeLinkerAlgo< DATA >::nodePoolPos_.

35 { return nodePoolPos_ + 1;}
template<typename DATA>
void KDTreeLinkerAlgo< DATA >::swap ( KDTreeNodeInfo &  e1,
KDTreeNodeInfo &  e2 
)
private

Definition at line 137 of file KDTreeLinkerAlgo.cc.

References reco::e1, reco::e2, and tmp.

Referenced by KDTreeLinkerAlgo< DATA >::medianSearch().

139 {
140  KDTreeNodeInfo tmp = e1;
141  e1 = e2;
142  e2 = tmp;
143 }
reco::e1
Float e1
Definition: deltaR.h:22
reco::e2
Float e2
Definition: deltaR.h:23
tmp
std::vector< std::vector< double > > tmp
Definition: MVATrainer.cc:100

Member Data Documentation

template<typename DATA>
std::vector<KDTreeNodeInfo<DATA> >* KDTreeLinkerAlgo< DATA >::closestNeighbour
private

Definition at line 51 of file KDTreeLinkerAlgo.h.

template<typename DATA>
std::vector<KDTreeNodeInfo<DATA> >* KDTreeLinkerAlgo< DATA >::initialEltList
private

Definition at line 52 of file KDTreeLinkerAlgo.h.

template<typename DATA>
KDTreeNode* KDTreeLinkerAlgo< DATA >::nodePool_
private

Definition at line 35 of file KDTreeLinkerAlgo.h.

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

template<typename DATA>
KDTreeNode<DATA>* KDTreeLinkerAlgo< DATA >::nodePool_
private

Definition at line 45 of file KDTreeLinkerAlgo.h.

template<typename DATA>
int KDTreeLinkerAlgo< DATA >::nodePoolPos_
private

Definition at line 37 of file KDTreeLinkerAlgo.h.

Referenced by KDTreeLinkerAlgo< DATA >::clearTree(), KDTreeLinkerAlgo< DATA >::empty(), KDTreeLinkerAlgo< DATA >::getNextNode(), and KDTreeLinkerAlgo< DATA >::size().

template<typename DATA>
int KDTreeLinkerAlgo< DATA >::nodePoolSize_
private

Definition at line 36 of file KDTreeLinkerAlgo.h.

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

template<typename DATA>
KDTreeNode* KDTreeLinkerAlgo< DATA >::root_
private

Definition at line 32 of file KDTreeLinkerAlgo.h.

Referenced by KDTreeLinkerAlgo< DATA >::build(), KDTreeLinkerAlgo< DATA >::clear(), KDTreeLinkerAlgo< DATA >::clearTree(), and KDTreeLinkerAlgo< DATA >::search().

template<typename DATA>
KDTreeNode<DATA>* KDTreeLinkerAlgo< DATA >::root_
private

Definition at line 42 of file KDTreeLinkerAlgo.h.

Generated for CMSSW Reference Manual by doxygen 1.8.5