|
|
|
#include <KDTreeLinkerAlgo.h>
Public Member Functions | |
| void | build (std::vector< KDTreeNodeInfo > &eltList, const KDTreeBox ®ion) |
| void | clear () |
| KDTreeLinkerAlgo () | |
| void | search (const KDTreeBox &searchBox, std::vector< KDTreeNodeInfo > &resRecHitList) |
| ~KDTreeLinkerAlgo () | |
Private Member Functions | |
| void | addSubtree (const KDTreeNode *current, std::vector< KDTreeNodeInfo > &recHits) |
| void | clearTree () |
| KDTreeNode * | getNextNode () |
| int | medianSearch (std::vector< KDTreeNodeInfo > &eltList, int low, int high, int treeDepth) |
| KDTreeNode * | recBuild (std::vector< KDTreeNodeInfo > &eltList, int low, int hight, int depth, const KDTreeBox ®ion) |
| void | recSearch (const KDTreeNode *current, const KDTreeBox &trackBox, std::vector< KDTreeNodeInfo > &recHits) |
| void | swap (KDTreeNodeInfo &e1, KDTreeNodeInfo &e2) |
Private Attributes | |
| KDTreeNode * | nodePool_ |
| int | nodePoolPos_ |
| int | nodePoolSize_ |
| KDTreeNode * | root_ |
Definition at line 10 of file KDTreeLinkerAlgo.h.
| KDTreeLinkerAlgo::KDTreeLinkerAlgo | ( | ) |
Definition at line 3 of file KDTreeLinkerAlgo.cc.
: root_ (0), nodePool_(0), nodePoolSize_(-1), nodePoolPos_(-1) { }
| KDTreeLinkerAlgo::~KDTreeLinkerAlgo | ( | ) |
| void KDTreeLinkerAlgo::addSubtree | ( | const KDTreeNode * | current, |
| std::vector< KDTreeNodeInfo > & | recHits | ||
| ) | [private] |
Definition at line 209 of file KDTreeLinkerAlgo.cc.
References KDTreeNode::left, KDTreeNode::rh, and KDTreeNode::right.
Referenced by recSearch().
{
// By construction, current can't be null
assert(current != 0);
if ((current->left == 0) && (current->right == 0)) // leaf
recHits.push_back(current->rh);
else { // node
addSubtree(current->left, recHits);
addSubtree(current->right, recHits);
}
}
| void KDTreeLinkerAlgo::build | ( | std::vector< KDTreeNodeInfo > & | eltList, |
| const KDTreeBox & | region | ||
| ) |
Definition at line 17 of file KDTreeLinkerAlgo.cc.
References nodePool_, nodePoolSize_, recBuild(), and root_.
Referenced by KDTreeLinkerTrackHcal::buildTree(), KDTreeLinkerPSEcal::buildTree(), and KDTreeLinkerTrackEcal::buildTree().
{
if (eltList.size()) {
nodePoolSize_ = eltList.size() * 2 - 1;
nodePool_ = new KDTreeNode[nodePoolSize_];
// Here we build the KDTree
root_ = recBuild(eltList, 0, eltList.size(), 0, region);
}
}
| void KDTreeLinkerAlgo::clear | ( | void | ) |
Definition at line 235 of file KDTreeLinkerAlgo.cc.
References clearTree(), and root_.
Referenced by KDTreeLinkerPSEcal::clear(), KDTreeLinkerTrackHcal::clear(), KDTreeLinkerTrackEcal::clear(), and ~KDTreeLinkerAlgo().
| void KDTreeLinkerAlgo::clearTree | ( | ) | [private] |
Definition at line 225 of file KDTreeLinkerAlgo.cc.
References nodePool_, nodePoolPos_, nodePoolSize_, and root_.
Referenced by clear().
{
delete[] nodePool_;
nodePool_ = 0;
root_ = 0;
nodePoolSize_ = -1;
nodePoolPos_ = -1;
}
| KDTreeNode * KDTreeLinkerAlgo::getNextNode | ( | ) | [private] |
Definition at line 243 of file KDTreeLinkerAlgo.cc.
References nodePool_, nodePoolPos_, and nodePoolSize_.
Referenced by recBuild().
{
++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_]);
}
| int KDTreeLinkerAlgo::medianSearch | ( | std::vector< KDTreeNodeInfo > & | eltList, |
| int | low, | ||
| int | high, | ||
| int | treeDepth | ||
| ) | [private] |
Definition at line 90 of file KDTreeLinkerAlgo.cc.
References KDTreeNodeInfo::dim1, KDTreeNodeInfo::dim2, i, j, prof2calltree::l, m, and swap().
Referenced by recBuild().
{
//We should have at least 1 element to calculate the median...
assert(low < high);
int nbrElts = high - low;
int median = (nbrElts & 1) ? nbrElts / 2
: nbrElts / 2 - 1;
median += low;
int l = low;
int m = high - 1;
while (l < m) {
KDTreeNodeInfo elt = eltList[median];
int i = l;
int j = m;
do {
// The even depth is associated to dim1 dimension
// The odd one to dim2 dimension
if (treeDepth & 1) {
while (eltList[i].dim2 < elt.dim2) i++;
while (eltList[j].dim2 > elt.dim2) j--;
} else {
while (eltList[i].dim1 < elt.dim1) i++;
while (eltList[j].dim1 > elt.dim1) j--;
}
if (i <= j){
swap(eltList[i], eltList[j]);
i++;
j--;
}
} while (i <= j);
if (j < median) l = i;
if (i > median) m = j;
}
return median;
}
| KDTreeNode * KDTreeLinkerAlgo::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, getNextNode(), python::Node::leaf, KDTreeNode::left, medianSearch(), python::Node::node, KDTreeNode::right, and KDTreeNode::setAttributs().
Referenced by build().
{
int portionSize = high - low;
// By construction, portionSize > 0 can't happend.
assert(portionSize > 0);
if (portionSize == 1) { // Leaf case
KDTreeNode *leaf = getNextNode();
leaf->setAttributs(region, eltList[low]);
return leaf;
} else { // Node case
// The even depth is associated to dim1 dimension
// The odd one to dim2 dimension
int medianId = medianSearch(eltList, low, high, depth);
// We create the node
KDTreeNode *node = getNextNode();
node->setAttributs(region);
// Here we split into 2 halfplanes the current plane
KDTreeBox leftRegion = region;
KDTreeBox rightRegion = region;
if (depth & 1) {
double medianVal = eltList[medianId].dim2;
leftRegion.dim2max = medianVal;
rightRegion.dim2min = medianVal;
} else {
double medianVal = eltList[medianId].dim1;
leftRegion.dim1max = medianVal;
rightRegion.dim1min = medianVal;
}
++depth;
++medianId;
// We recursively build the son nodes
node->left = recBuild(eltList, low, medianId, depth, leftRegion);
node->right = recBuild(eltList, medianId, high, depth, rightRegion);
return node;
}
}
| void KDTreeLinkerAlgo::recSearch | ( | const KDTreeNode * | current, |
| const KDTreeBox & | trackBox, | ||
| std::vector< KDTreeNodeInfo > & | recHits | ||
| ) | [private] |
Definition at line 154 of file KDTreeLinkerAlgo.cc.
References addSubtree(), KDTreeNodeInfo::dim1, KDTreeBox::dim1max, KDTreeBox::dim1min, KDTreeNodeInfo::dim2, KDTreeBox::dim2max, KDTreeBox::dim2min, KDTreeNode::left, KDTreeNode::region, KDTreeNode::rh, and KDTreeNode::right.
Referenced by search().
{
// 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 == 0) && (current->right == 0)) {//leaf case
// If point inside the rectangle/area
if ((current->rh.dim1 >= trackBox.dim1min) && (current->rh.dim1 <= trackBox.dim1max) &&
(current->rh.dim2 >= trackBox.dim2min) && (current->rh.dim2 <= trackBox.dim2max))
recHits.push_back(current->rh);
} else {
//if region( v->left ) is fully contained in the rectangle
if ((current->left->region.dim1min >= trackBox.dim1min) &&
(current->left->region.dim1max <= trackBox.dim1max) &&
(current->left->region.dim2min >= trackBox.dim2min) &&
(current->left->region.dim2max <= trackBox.dim2max))
addSubtree(current->left, recHits);
else { //if region( v->left ) intersects the rectangle
if (!((current->left->region.dim1min >= trackBox.dim1max) ||
(current->left->region.dim1max <= trackBox.dim1min) ||
(current->left->region.dim2min >= trackBox.dim2max) ||
(current->left->region.dim2max <= trackBox.dim2min)))
recSearch(current->left, trackBox, recHits);
}
//if region( v->right ) is fully contained in the rectangle
if ((current->right->region.dim1min >= trackBox.dim1min) &&
(current->right->region.dim1max <= trackBox.dim1max) &&
(current->right->region.dim2min >= trackBox.dim2min) &&
(current->right->region.dim2max <= trackBox.dim2max))
addSubtree(current->right, recHits);
else { //if region( v->right ) intersects the rectangle
if (!((current->right->region.dim1min >= trackBox.dim1max) ||
(current->right->region.dim1max <= trackBox.dim1min) ||
(current->right->region.dim2min >= trackBox.dim2max) ||
(current->right->region.dim2max <= trackBox.dim2min)))
recSearch(current->right, trackBox, recHits);
}
}
}
| void KDTreeLinkerAlgo::search | ( | const KDTreeBox & | searchBox, |
| std::vector< KDTreeNodeInfo > & | resRecHitList | ||
| ) |
Definition at line 146 of file KDTreeLinkerAlgo.cc.
References recSearch(), and root_.
Referenced by KDTreeLinkerTrackHcal::searchLinks(), KDTreeLinkerPSEcal::searchLinks(), and KDTreeLinkerTrackEcal::searchLinks().
| void KDTreeLinkerAlgo::swap | ( | KDTreeNodeInfo & | e1, |
| KDTreeNodeInfo & | e2 | ||
| ) | [private] |
Definition at line 137 of file KDTreeLinkerAlgo.cc.
References tmp.
Referenced by medianSearch().
{
KDTreeNodeInfo tmp = e1;
e1 = e2;
e2 = tmp;
}
KDTreeNode* KDTreeLinkerAlgo::nodePool_ [private] |
Definition at line 35 of file KDTreeLinkerAlgo.h.
Referenced by build(), clearTree(), and getNextNode().
int KDTreeLinkerAlgo::nodePoolPos_ [private] |
Definition at line 37 of file KDTreeLinkerAlgo.h.
Referenced by clearTree(), and getNextNode().
int KDTreeLinkerAlgo::nodePoolSize_ [private] |
Definition at line 36 of file KDTreeLinkerAlgo.h.
Referenced by build(), clearTree(), and getNextNode().
KDTreeNode* KDTreeLinkerAlgo::root_ [private] |
Definition at line 32 of file KDTreeLinkerAlgo.h.
Referenced by build(), clear(), clearTree(), and search().
1.7.3