#include <kd_tree.h>
Public Member Functions | |
| ANNkd_split (int cd, ANNcoord cv, ANNcoord lv, ANNcoord hv, ANNkd_ptr lc=NULL, ANNkd_ptr hc=NULL) | |
| ~ANNkd_split () | |
| virtual void | getStats (int dim, ANNkdStats &st, ANNorthRect &bnd_box) |
| virtual void | print (int level, ostream &out) |
| virtual void | dump (ostream &out) |
| virtual void | ann_search (ANNdist) |
| virtual void | ann_pri_search (ANNdist) |
| virtual void | ann_FR_search (ANNdist) |
Definition at line 142 of file kd_tree.h.
| ANNkd_split::ANNkd_split | ( | int | cd, |
| ANNcoord | cv, | ||
| ANNcoord | lv, | ||
| ANNcoord | hv, | ||
| ANNkd_ptr | lc = NULL, |
||
| ANNkd_ptr | hc = NULL |
||
| ) | [inline] |
| ANNkd_split::~ANNkd_split | ( | ) | [inline] |
Definition at line 164 of file kd_tree.h.
References ANN_HI, ANN_LO, and KD_TRIVIAL.
{
if (child[ANN_LO]!= NULL && child[ANN_LO]!= KD_TRIVIAL)
delete child[ANN_LO];
if (child[ANN_HI]!= NULL && child[ANN_HI]!= KD_TRIVIAL)
delete child[ANN_HI];
}
| void ANNkd_split::ann_FR_search | ( | ANNdist | box_dist ) | [virtual] |
Implements ANNkd_node.
Definition at line 100 of file kd_fix_rad_search.cpp.
References ANN_DIFF, ANN_FLOP, ANNkd_node::ann_FR_search(), ANN_HI, ANN_LO, ANN_POW, ANN_SPL, ANN_SUM, ANNkdFRMaxErr, ANNkdFRPtsVisited, ANNkdFRQ, ANNkdFRSqRad, and ANNmaxPtsVisited.
{
// check dist calc term condition
if (ANNmaxPtsVisited != 0 && ANNkdFRPtsVisited > ANNmaxPtsVisited) return;
// distance to cutting plane
ANNcoord cut_diff = ANNkdFRQ[cut_dim] - cut_val;
if (cut_diff < 0) { // left of cutting plane
child[ANN_LO]->ann_FR_search(box_dist);// visit closer child first
ANNcoord box_diff = cd_bnds[ANN_LO] - ANNkdFRQ[cut_dim];
if (box_diff < 0) // within bounds - ignore
box_diff = 0;
// distance to further box
box_dist = (ANNdist) ANN_SUM(box_dist,
ANN_DIFF(ANN_POW(box_diff), ANN_POW(cut_diff)));
// visit further child if in range
if (box_dist * ANNkdFRMaxErr <= ANNkdFRSqRad)
child[ANN_HI]->ann_FR_search(box_dist);
}
else { // right of cutting plane
child[ANN_HI]->ann_FR_search(box_dist);// visit closer child first
ANNcoord box_diff = ANNkdFRQ[cut_dim] - cd_bnds[ANN_HI];
if (box_diff < 0) // within bounds - ignore
box_diff = 0;
// distance to further box
box_dist = (ANNdist) ANN_SUM(box_dist,
ANN_DIFF(ANN_POW(box_diff), ANN_POW(cut_diff)));
// visit further child if close enough
if (box_dist * ANNkdFRMaxErr <= ANNkdFRSqRad)
child[ANN_LO]->ann_FR_search(box_dist);
}
ANN_FLOP(13) // increment floating ops
ANN_SPL(1) // one more splitting node visited
}
| void ANNkd_split::ann_pri_search | ( | ANNdist | box_dist ) | [virtual] |
Implements ANNkd_node.
Definition at line 138 of file kd_pr_search.cpp.
References ANN_DIFF, ANN_FLOP, ANN_HI, ANN_LO, ANN_POW, ANNkd_node::ann_pri_search(), ANN_SPL, ANN_SUM, ANNprQ, ANNpr_queue::insert(), and KD_TRIVIAL.
{
ANNdist new_dist; // distance to child visited later
// distance to cutting plane
ANNcoord cut_diff = ANNprQ[cut_dim] - cut_val;
if (cut_diff < 0) { // left of cutting plane
ANNcoord box_diff = cd_bnds[ANN_LO] - ANNprQ[cut_dim];
if (box_diff < 0) // within bounds - ignore
box_diff = 0;
// distance to further box
new_dist = (ANNdist) ANN_SUM(box_dist,
ANN_DIFF(ANN_POW(box_diff), ANN_POW(cut_diff)));
if (child[ANN_HI] != KD_TRIVIAL)// enqueue if not trivial
ANNprBoxPQ->insert(new_dist, child[ANN_HI]);
// continue with closer child
child[ANN_LO]->ann_pri_search(box_dist);
}
else { // right of cutting plane
ANNcoord box_diff = ANNprQ[cut_dim] - cd_bnds[ANN_HI];
if (box_diff < 0) // within bounds - ignore
box_diff = 0;
// distance to further box
new_dist = (ANNdist) ANN_SUM(box_dist,
ANN_DIFF(ANN_POW(box_diff), ANN_POW(cut_diff)));
if (child[ANN_LO] != KD_TRIVIAL)// enqueue if not trivial
ANNprBoxPQ->insert(new_dist, child[ANN_LO]);
// continue with closer child
child[ANN_HI]->ann_pri_search(box_dist);
}
ANN_SPL(1) // one more splitting node visited
ANN_FLOP(8) // increment floating ops
}
| void ANNkd_split::ann_search | ( | ANNdist | box_dist ) | [virtual] |
Implements ANNkd_node.
Definition at line 124 of file kd_search.cpp.
References ANN_DIFF, ANN_FLOP, ANN_HI, ANN_LO, ANN_POW, ANNkd_node::ann_search(), ANN_SPL, ANN_SUM, ANNkdQ, ANNmaxPtsVisited, and ANNptsVisited.
{
// check dist calc term condition
if (ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited) return;
// distance to cutting plane
ANNcoord cut_diff = ANNkdQ[cut_dim] - cut_val;
if (cut_diff < 0) { // left of cutting plane
child[ANN_LO]->ann_search(box_dist);// visit closer child first
ANNcoord box_diff = cd_bnds[ANN_LO] - ANNkdQ[cut_dim];
if (box_diff < 0) // within bounds - ignore
box_diff = 0;
// distance to further box
box_dist = (ANNdist) ANN_SUM(box_dist,
ANN_DIFF(ANN_POW(box_diff), ANN_POW(cut_diff)));
// visit further child if close enough
if (box_dist * ANNkdMaxErr < ANNkdPointMK->max_key())
child[ANN_HI]->ann_search(box_dist);
}
else { // right of cutting plane
child[ANN_HI]->ann_search(box_dist);// visit closer child first
ANNcoord box_diff = ANNkdQ[cut_dim] - cd_bnds[ANN_HI];
if (box_diff < 0) // within bounds - ignore
box_diff = 0;
// distance to further box
box_dist = (ANNdist) ANN_SUM(box_dist,
ANN_DIFF(ANN_POW(box_diff), ANN_POW(cut_diff)));
// visit further child if close enough
if (box_dist * ANNkdMaxErr < ANNkdPointMK->max_key())
child[ANN_LO]->ann_search(box_dist);
}
ANN_FLOP(10) // increment floating ops
ANN_SPL(1) // one more splitting node visited
}
| void ANNkd_split::dump | ( | ostream & | out ) | [virtual] |
Implements ANNkd_node.
Definition at line 136 of file kd_dump.cpp.
| void ANNkd_split::getStats | ( | int | dim, |
| ANNkdStats & | st, | ||
| ANNorthRect & | bnd_box | ||
| ) | [virtual] |
Implements ANNkd_node.
Definition at line 160 of file kd_tree.cpp.
References ANN_HI, ANN_LO, ANNkdStats::depth, ANNkd_node::getStats(), ANNorthRect::hi, ANNorthRect::lo, ANNkdStats::merge(), ANNkdStats::n_spl, and ANNkdStats::reset().
{
ANNkdStats ch_stats; // stats for children
// get stats for low child
ANNcoord hv = bnd_box.hi[cut_dim]; // save box bounds
bnd_box.hi[cut_dim] = cut_val; // upper bound for low child
ch_stats.reset(); // reset
child[ANN_LO]->getStats(dim, ch_stats, bnd_box);
st.merge(ch_stats); // merge them
bnd_box.hi[cut_dim] = hv; // restore bound
// get stats for high child
ANNcoord lv = bnd_box.lo[cut_dim]; // save box bounds
bnd_box.lo[cut_dim] = cut_val; // lower bound for high child
ch_stats.reset(); // reset
child[ANN_HI]->getStats(dim, ch_stats, bnd_box);
st.merge(ch_stats); // merge them
bnd_box.lo[cut_dim] = lv; // restore bound
st.depth++; // increment depth
st.n_spl++; // increment number of splits
}
| void ANNkd_split::print | ( | int | level, |
| ostream & | out | ||
| ) | [virtual] |
Implements ANNkd_node.
Definition at line 67 of file kd_tree.cpp.
References ANN_HI, ANN_LO, and ANNkd_node::print().
{
child[ANN_HI]->print(level+1, out); // print high child
out << " ";
for (int i = 0; i < level; i++) // print indentation
out << "..";
out << "Split cd=" << cut_dim << " cv=" << cut_val;
out << " lbnd=" << cd_bnds[ANN_LO];
out << " hbnd=" << cd_bnds[ANN_HI];
out << "\n";
child[ANN_LO]->print(level+1, out); // print low child
}
1.7.2