#include <kd_tree.h>
Public Member Functions | |
| ANNkd_leaf (int n, ANNidxArray b) | |
| ~ANNkd_leaf () | |
| 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 91 of file kd_tree.h.
| ANNkd_leaf::ANNkd_leaf | ( | int | n, |
| ANNidxArray | b | ||
| ) | [inline] |
| ANNkd_leaf::~ANNkd_leaf | ( | ) | [inline] |
| void ANNkd_leaf::ann_FR_search | ( | ANNdist | ) | [virtual] |
Implements ANNkd_node.
Definition at line 148 of file kd_fix_rad_search.cpp.
References ANN_ALLOW_SELF_MATCH, ANN_COORD, ANN_FLOP, ANN_LEAF, ANN_POW, ANN_PTS, ANN_SUM, ANNkdFRDim, ANNkdFRPts, ANNkdFRPtsInRange, ANNkdFRPtsVisited, ANNkdFRQ, ANNkdFRSqRad, QuadProgPP::dist(), ANNmin_k::insert(), and QuadProgPP::t().
{
register ANNdist dist; // distance to data point
register ANNcoord* pp; // data coordinate pointer
register ANNcoord* qq; // query coordinate pointer
register ANNcoord t;
register int d;
for (int i = 0; i < n_pts; i++) { // check points in bucket
pp = ANNkdFRPts[bkt[i]]; // first coord of next data point
qq = ANNkdFRQ; // first coord of query point
dist = 0;
for(d = 0; d < ANNkdFRDim; d++) {
ANN_COORD(1) // one more coordinate hit
ANN_FLOP(5) // increment floating ops
t = *(qq++) - *(pp++); // compute length and adv coordinate
// exceeds dist to k-th smallest?
if( (dist = ANN_SUM(dist, ANN_POW(t))) > ANNkdFRSqRad) {
break;
}
}
if (d >= ANNkdFRDim && // among the k best?
(ANN_ALLOW_SELF_MATCH || dist!=0)) { // and no self-match problem
// add it to the list
ANNkdFRPointMK->insert(dist, bkt[i]);
ANNkdFRPtsInRange++; // increment point count
}
}
ANN_LEAF(1) // one more leaf node visited
ANN_PTS(n_pts) // increment points visited
ANNkdFRPtsVisited += n_pts; // increment number of points visited
}
| void ANNkd_leaf::ann_pri_search | ( | ANNdist | ) | [virtual] |
Implements ANNkd_node.
Definition at line 180 of file kd_pr_search.cpp.
References ANN_ALLOW_SELF_MATCH, ANN_COORD, ANN_FLOP, ANN_LEAF, ANN_POW, ANN_PTS, ANN_SUM, ANNprDim, ANNprPts, ANNprQ, ANNptsVisited, QuadProgPP::dist(), ANNmin_k::insert(), ANNmin_k::max_key(), and QuadProgPP::t().
{
register ANNdist dist; // distance to data point
register ANNcoord* pp; // data coordinate pointer
register ANNcoord* qq; // query coordinate pointer
register ANNdist min_dist; // distance to k-th closest point
register ANNcoord t;
register int d;
min_dist = ANNprPointMK->max_key(); // k-th smallest distance so far
for (int i = 0; i < n_pts; i++) { // check points in bucket
pp = ANNprPts[bkt[i]]; // first coord of next data point
qq = ANNprQ; // first coord of query point
dist = 0;
for(d = 0; d < ANNprDim; d++) {
ANN_COORD(1) // one more coordinate hit
ANN_FLOP(4) // increment floating ops
t = *(qq++) - *(pp++); // compute length and adv coordinate
// exceeds dist to k-th smallest?
if( (dist = ANN_SUM(dist, ANN_POW(t))) > min_dist) {
break;
}
}
if (d >= ANNprDim && // among the k best?
(ANN_ALLOW_SELF_MATCH || dist!=0)) { // and no self-match problem
// add it to the list
ANNprPointMK->insert(dist, bkt[i]);
min_dist = ANNprPointMK->max_key();
}
}
ANN_LEAF(1) // one more leaf node visited
ANN_PTS(n_pts) // increment points visited
ANNptsVisited += n_pts; // increment number of points visited
}
| void ANNkd_leaf::ann_search | ( | ANNdist | ) | [virtual] |
Implements ANNkd_node.
Definition at line 172 of file kd_search.cpp.
References ANN_ALLOW_SELF_MATCH, ANN_COORD, ANN_FLOP, ANN_LEAF, ANN_POW, ANN_PTS, ANN_SUM, ANNkdDim, ANNkdPts, ANNkdQ, ANNptsVisited, QuadProgPP::dist(), ANNmin_k::insert(), ANNmin_k::max_key(), and QuadProgPP::t().
{
register ANNdist dist; // distance to data point
register ANNcoord* pp; // data coordinate pointer
register ANNcoord* qq; // query coordinate pointer
register ANNdist min_dist; // distance to k-th closest point
register ANNcoord t;
register int d;
min_dist = ANNkdPointMK->max_key(); // k-th smallest distance so far
for (int i = 0; i < n_pts; i++) { // check points in bucket
pp = ANNkdPts[bkt[i]]; // first coord of next data point
qq = ANNkdQ; // first coord of query point
dist = 0;
for(d = 0; d < ANNkdDim; d++) {
ANN_COORD(1) // one more coordinate hit
ANN_FLOP(4) // increment floating ops
t = *(qq++) - *(pp++); // compute length and adv coordinate
// exceeds dist to k-th smallest?
if( (dist = ANN_SUM(dist, ANN_POW(t))) > min_dist) {
break;
}
}
if (d >= ANNkdDim && // among the k best?
(ANN_ALLOW_SELF_MATCH || dist!=0)) { // and no self-match problem
// add it to the list
ANNkdPointMK->insert(dist, bkt[i]);
min_dist = ANNkdPointMK->max_key();
}
}
ANN_LEAF(1) // one more leaf node visited
ANN_PTS(n_pts) // increment points visited
ANNptsVisited += n_pts; // increment number of points visited
}
| void ANNkd_leaf::dump | ( | ostream & | out ) | [virtual] |
Implements ANNkd_node.
Definition at line 146 of file kd_dump.cpp.
References KD_TRIVIAL.
{
if (this == KD_TRIVIAL) { // canonical trivial leaf node
out << "leaf 0\n"; // leaf no points
}
else{
out << "leaf " << n_pts;
for (int j = 0; j < n_pts; j++) {
out << " " << bkt[j];
}
out << "\n";
}
}
| void ANNkd_leaf::getStats | ( | int | dim, |
| ANNkdStats & | st, | ||
| ANNorthRect & | bnd_box | ||
| ) | [virtual] |
Implements ANNkd_node.
Definition at line 147 of file kd_tree.cpp.
References annAspectRatio(), ANNkdStats::n_lf, ANNkdStats::n_tl, ANNkdStats::reset(), and ANNkdStats::sum_ar.
{
st.reset();
st.n_lf = 1; // count this leaf
if (this == KD_TRIVIAL) st.n_tl = 1; // count trivial leaf
double ar = annAspectRatio(dim, bnd_box); // aspect ratio of leaf
// incr sum (ignore outliers)
st.sum_ar += float(ar < ANN_AR_TOOBIG ? ar : ANN_AR_TOOBIG);
}
| void ANNkd_leaf::print | ( | int | level, |
| ostream & | out | ||
| ) | [virtual] |
Implements ANNkd_node.
Definition at line 82 of file kd_tree.cpp.
{
out << " ";
for (int i = 0; i < level; i++) // print indentation
out << "..";
if (this == KD_TRIVIAL) { // canonical trivial leaf node
out << "Leaf (trivial)\n";
}
else{
out << "Leaf n=" << n_pts << " <";
for (int j = 0; j < n_pts; j++) {
out << bkt[j];
if (j < n_pts-1) out << ",";
}
out << ">\n";
}
}
1.7.2