ANNkd_leaf Class Reference

#include <kd_tree.h>

Inheritance diagram for ANNkd_leaf:

Collaboration diagram for ANNkd_leaf:

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)
Public Member Functions inherited from ANNkd_node
virtual	~ANNkd_node ()

Private Attributes
int	n_pts
ANNidxArray	bkt

Detailed Description

Definition at line 91 of file kd_tree.h.

Constructor & Destructor Documentation

ANNkd_leaf::ANNkd_leaf ( int  n, ANNidxArray  b  )

inline

Definition at line 96 of file kd_tree.h.

References n_pts.

                {
                        n_pts           = n;                    // number of points in bucket
                        bkt                     = b;                    // the bucket
                }

ANNkd_leaf::~ANNkd_leaf ( )

inline

Definition at line 104 of file kd_tree.h.

{ }                                     // destructor (none)

Member Function Documentation

void ANNkd_leaf::ann_FR_search ( ANNdist  box_dist )

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, bkt, ANNmin_k::insert(), and n_pts.

{
        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  box_dist )

virtual

Implements ANNkd_node.

Definition at line 181 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, bkt, ANNmin_k::insert(), ANNmin_k::max_key(), and n_pts.

{
        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  box_dist )

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, bkt, ANNmin_k::insert(), ANNmin_k::max_key(), and n_pts.

{
        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 144 of file kd_dump.cpp.

References KD_TRIVIAL, and n_pts.

{
        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 ANN_AR_TOOBIG, 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.

References bkt, and n_pts.

{

        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";
        }
}

Member Data Documentation

ANNidxArray ANNkd_leaf::bkt

private

Definition at line 94 of file kd_tree.h.

Referenced by ann_FR_search(), ann_pri_search(), ann_search(), and print().

int ANNkd_leaf::n_pts

private

Definition at line 93 of file kd_tree.h.

Referenced by ann_FR_search(), ann_pri_search(), ann_search(), and print().

---

The documentation for this class was generated from the following files:

• src/contrib/ANN/src/kd_tree.h
• src/contrib/ANN/src/kd_dump.cpp
• src/contrib/ANN/src/kd_fix_rad_search.cpp
• src/contrib/ANN/src/kd_pr_search.cpp
• src/contrib/ANN/src/kd_search.cpp
• src/contrib/ANN/src/kd_tree.cpp