#include <ANN.h>

Inheritance diagram for ANNkd_tree:

Collaboration diagram for ANNkd_tree:

Public Member Functions
	ANNkd_tree (int n=0, int dd=0, int bs=1)

	ANNkd_tree (ANNpointArray pa, int n, int dd, int bs=1, ANNsplitRule split=ANN_KD_SUGGEST)

	ANNkd_tree (std::istream &in)

	~ANNkd_tree ()

void	annkSearch (ANNpoint q, int k, ANNidxArray nn_idx, ANNdistArray dd, double eps=0.0)

void	annkPriSearch (ANNpoint q, int k, ANNidxArray nn_idx, ANNdistArray dd, double eps=0.0)

int	annkFRSearch (ANNpoint q, ANNdist sqRad, int k, ANNidxArray nn_idx=NULL, ANNdistArray dd=NULL, double eps=0.0)

int	theDim ()

int	nPoints ()

ANNpointArray	thePoints ()

virtual void	Print (ANNbool with_pts, std::ostream &out)

virtual void	Dump (ANNbool with_pts, std::ostream &out)

virtual void	getStats (ANNkdStats &st)

Public Member Functions inherited from ANNpointSet
virtual	~ANNpointSet ()

Protected Member Functions
void	SkeletonTree (int n, int dd, int bs, ANNpointArray pa=NULL, ANNidxArray pi=NULL)

Protected Attributes
int	dim

int	n_pts

int	bkt_size

ANNpointArray	pts

ANNidxArray	pidx

ANNkd_ptr	root

ANNpoint	bnd_box_lo

ANNpoint	bnd_box_hi

Detailed Description

Definition at line 705 of file ANN.h.

Constructor & Destructor Documentation

ANNkd_tree::ANNkd_tree	(	int	n = `0`,
		int	dd = `0`,
		int	bs = `1`
	)

Definition at line 273 of file kd_tree.cpp.

References SkeletonTree().

277 { SkeletonTree(n, dd, bs); } // construct skeleton tree

ANNkd_tree::SkeletonTree

void SkeletonTree(int n, int dd, int bs, ANNpointArray pa=NULL, ANNidxArray pi=NULL)

Definition: kd_tree.cpp:244

ANNkd_tree::ANNkd_tree	(	ANNpointArray	pa,
		int	n,
		int	dd,
		int	bs = `1`,
		ANNsplitRule	split = `ANN_KD_SUGGEST`
	)

Definition at line 368 of file kd_tree.cpp.

References ANN_KD_FAIR, ANN_KD_MIDPT, ANN_KD_SL_FAIR, ANN_KD_SL_MIDPT, ANN_KD_STD, ANN_KD_SUGGEST, ANNabort, annCopyPt(), annEnclRect(), annError(), bnd_box_hi, bnd_box_lo, fair_split(), ANNorthRect::hi, kd_split(), ANNorthRect::lo, midpt_split(), pidx, pts, rkd_tree(), root, SkeletonTree(), sl_fair_split(), and sl_midpt_split().

 {
         SkeletonTree(n, dd, bs);                        // set up the basic stuff
         pts = pa;                                                       // where the points are
         if (n == 0) return;                                     // no points--no sweat
 
         ANNorthRect bnd_box(dd);                        // bounding box for points
         annEnclRect(pa, pidx, n, dd, bnd_box);// construct bounding rectangle
                                                                                 // copy to tree structure
         bnd_box_lo = annCopyPt(dd, bnd_box.lo);
         bnd_box_hi = annCopyPt(dd, bnd_box.hi);
 
         switch (split) {                                        // build by rule
         case ANN_KD_STD:                                        // standard kd-splitting rule
                 root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, kd_split);
                 break;
         case ANN_KD_MIDPT:                                      // midpoint split
                 root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, midpt_split);
                 break;
         case ANN_KD_FAIR:                                       // fair split
                 root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, fair_split);
                 break;
         case ANN_KD_SUGGEST:                            // best (in our opinion)
         case ANN_KD_SL_MIDPT:                           // sliding midpoint split
                 root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, sl_midpt_split);
                 break;
         case ANN_KD_SL_FAIR:                            // sliding fair split
                 root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, sl_fair_split);
                 break;
         default:
                 annError("Illegal splitting method", ANNabort);
         }
 }

ANNkd_tree::ANNkd_tree ( std::istream & in )

ANNkd_tree::~ANNkd_tree ( )

Definition at line 209 of file kd_tree.cpp.

References annDeallocPt(), bnd_box_hi, bnd_box_lo, pidx, and root.

 {
         if (root != NULL) delete root;
         if (pidx != NULL) delete [] pidx;
         if (bnd_box_lo != NULL) annDeallocPt(bnd_box_lo);
         if (bnd_box_hi != NULL) annDeallocPt(bnd_box_hi);
 }

Member Function Documentation

int ANNkd_tree::annkFRSearch	(	ANNpoint	q,
		ANNdist	sqRad,
		int	k,
		ANNidxArray	nn_idx = `NULL`,
		ANNdistArray	dd = `NULL`,
		double	eps = `0.0`
	)

virtual

Implements ANNpointSet.

Definition at line 58 of file kd_fix_rad_search.cpp.

References ANN_FLOP, ANNkd_node::ann_FR_search(), ANN_POW, annBoxDistance(), ANNkdFRDim, ANNkdFRMaxErr, ANNkdFRPointMK, ANNkdFRPts, ANNkdFRPtsInRange, ANNkdFRPtsVisited, ANNkdFRQ, ANNkdFRSqRad, bnd_box_hi, bnd_box_lo, dim, ANNmin_k::ith_smallest_info(), ANNmin_k::ith_smallest_key(), k, pts, and root.

Referenced by main().

 {
         ANNkdFRDim = dim;                                       // copy arguments to static equivs
         ANNkdFRQ = q;
         ANNkdFRSqRad = sqRad;
         ANNkdFRPts = pts;
         ANNkdFRPtsVisited = 0;                          // initialize count of points visited
         ANNkdFRPtsInRange = 0;                          // ...and points in the range
 
         ANNkdFRMaxErr = ANN_POW(1.0 + eps);
         ANN_FLOP(2)                                                     // increment floating op count
 
         ANNkdFRPointMK = new ANNmin_k(k);       // create set for closest k points
                                                                                 // search starting at the root
         root->ann_FR_search(annBoxDistance(q, bnd_box_lo, bnd_box_hi, dim));
 
         for (int i = 0; i < k; i++) {           // extract the k-th closest points
                 if (dd != NULL)
                         dd[i] = ANNkdFRPointMK->ith_smallest_key(i);
                 if (nn_idx != NULL)
                         nn_idx[i] = ANNkdFRPointMK->ith_smallest_info(i);
         }
 
         delete ANNkdFRPointMK;                          // deallocate closest point set
         return ANNkdFRPtsInRange;                       // return final point count
 }

void ANNkd_tree::annkPriSearch	(	ANNpoint	q,
		int	k,
		ANNidxArray	nn_idx,
		ANNdistArray	dd,
		double	eps = `0.0`
	)

Definition at line 87 of file kd_pr_search.cpp.

References ANN_FLOP, ANN_POW, annBoxDistance(), ANNmaxPtsVisited, ANNprBoxPQ, ANNprDim, ANNprMaxErr, ANNprPointMK, ANNprPts, ANNprQ, ANNptsVisited, bnd_box_hi, bnd_box_lo, dim, ANNpr_queue::extr_min(), ANNpr_queue::insert(), ANNmin_k::ith_smallest_info(), ANNmin_k::ith_smallest_key(), k, ANNmin_k::max_key(), n_pts, ANNpr_queue::non_empty(), pts, and root.

Referenced by main().

 {
                                                                                 // max tolerable squared error
         ANNprMaxErr = ANN_POW(1.0 + eps);
         ANN_FLOP(2)                                                     // increment floating ops
 
         ANNprDim = dim;                                         // copy arguments to static equivs
         ANNprQ = q;
         ANNprPts = pts;
         ANNptsVisited = 0;                                      // initialize count of points visited
 
         ANNprPointMK = new ANNmin_k(k);         // create set for closest k points
 
                                                                                 // distance to root box
         ANNdist box_dist = annBoxDistance(q,
                                 bnd_box_lo, bnd_box_hi, dim);
 
         ANNprBoxPQ = new ANNpr_queue(n_pts);// create priority queue for boxes
         ANNprBoxPQ->insert(box_dist, root); // insert root in priority queue
 
         while (ANNprBoxPQ->non_empty() &&
                 (!(ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited))) {
                 ANNkd_ptr np;                                   // next box from prior queue
 
                                                                                 // extract closest box from queue
                 ANNprBoxPQ->extr_min(box_dist, (void *&) np);
 
                 ANN_FLOP(2)                                             // increment floating ops
                 if (box_dist*ANNprMaxErr >= ANNprPointMK->max_key())
                         break;
 
                 np->ann_pri_search(box_dist);   // search this subtree.
         }
 
         for (int i = 0; i < k; i++) {           // extract the k-th closest points
                 dd[i] = ANNprPointMK->ith_smallest_key(i);
                 nn_idx[i] = ANNprPointMK->ith_smallest_info(i);
         }
 
         delete ANNprPointMK;                            // deallocate closest point set
         delete ANNprBoxPQ;                                      // deallocate priority queue
 }

void ANNkd_tree::annkSearch	(	ANNpoint	q,
		int	k,
		ANNidxArray	nn_idx,
		ANNdistArray	dd,
		double	eps = `0.0`
	)

virtual

Implements ANNpointSet.

Definition at line 89 of file kd_search.cpp.

References ANN_FLOP, ANN_POW, ANNkd_node::ann_search(), ANNabort, annBoxDistance(), annError(), ANNkdDim, ANNkdMaxErr, ANNkdPointMK, ANNkdPts, ANNkdQ, ANNptsVisited, bnd_box_hi, bnd_box_lo, dim, ANNmin_k::ith_smallest_info(), ANNmin_k::ith_smallest_key(), k, n_pts, pts, and root.

Referenced by main().

 {
 
         ANNkdDim = dim;                                         // copy arguments to static equivs
         ANNkdQ = q;
         ANNkdPts = pts;
         ANNptsVisited = 0;                                      // initialize count of points visited
 
         if (k > n_pts) {                                        // too many near neighbors?
                 annError("Requesting more near neighbors than data points", ANNabort);
         }
 
         ANNkdMaxErr = ANN_POW(1.0 + eps);
         ANN_FLOP(2)                                                     // increment floating op count
 
         ANNkdPointMK = new ANNmin_k(k);         // create set for closest k points
                                                                                 // search starting at the root
         root->ann_search(annBoxDistance(q, bnd_box_lo, bnd_box_hi, dim));
 
         for (int i = 0; i < k; i++) {           // extract the k-th closest points
                 dd[i] = ANNkdPointMK->ith_smallest_key(i);
                 nn_idx[i] = ANNkdPointMK->ith_smallest_info(i);
         }
         delete ANNkdPointMK;                            // deallocate closest point set
 }

void ANNkd_tree::Dump	(	ANNbool	with_pts,
		std::ostream &	out
	)

virtual

Definition at line 102 of file kd_dump.cpp.

References ANNcoordPrec, annPrintPt(), ANNversion, dim, n_pts, and pts.

Referenced by main().

 {
         out << "#ANN " << ANNversion << "\n";
         out.precision(ANNcoordPrec);            // use full precision in dumping
         if (with_pts) {                                         // print point coordinates
                 out << "points " << dim << " " << n_pts << "\n";
                 for (int i = 0; i < n_pts; i++) {
                         out << i << " ";
                         annPrintPt(pts[i], dim, out);
                         out << "\n";
                 }
         }
         out << "tree "                                          // print tree elements
                 << dim << " "
                 << n_pts << " "
                 << bkt_size << "\n";
 
         annPrintPt(bnd_box_lo, dim, out);       // print lower bound
         out << "\n";
         annPrintPt(bnd_box_hi, dim, out);       // print upper bound
         out << "\n";
 
         if (root == NULL)                                       // empty tree?
                 out << "null\n";
         else {
                 root->dump(out);                                // invoke printing at root
         }
         out.precision(0);                                       // restore default precision
 }

void ANNkd_tree::getStats ( ANNkdStats & st )

virtual

Definition at line 191 of file kd_tree.cpp.

References ANNkdStats::avg_ar, bkt_size, bnd_box_hi, bnd_box_lo, dim, ANNkd_node::getStats(), ANNkdStats::n_lf, n_pts, ANNkdStats::reset(), root, and ANNkdStats::sum_ar.

Referenced by treeStats().

 {
         st.reset(dim, n_pts, bkt_size);                         // reset stats
                                                                                                 // create bounding box
         ANNorthRect bnd_box(dim, bnd_box_lo, bnd_box_hi);
         if (root != NULL) {                                                     // if nonempty tree
                 root->getStats(dim, st, bnd_box);               // get statistics
                 st.avg_ar = st.sum_ar / st.n_lf;                // average leaf asp ratio
         }
 }

int ANNkd_tree::nPoints ( )

inlinevirtual

Implements ANNpointSet.

Definition at line 766 of file ANN.h.

References n_pts.

Referenced by main().

767 { return n_pts; }

ANNkd_tree::n_pts

int n_pts

Definition: ANN.h:708

void ANNkd_tree::Print	(	ANNbool	with_pts,
		std::ostream &	out
	)

virtual

Definition at line 104 of file kd_tree.cpp.

References annPrintPt(), ANNversion, dim, n_pts, ANNkd_node::print(), pts, and root.

Referenced by main().

 {
         out << "ANN Version " << ANNversion << "\n";
         if (with_pts) {                                         // print point coordinates
                 out << "    Points:\n";
                 for (int i = 0; i < n_pts; i++) {
                         out << "\t" << i << ": ";
                         annPrintPt(pts[i], dim, out);
                         out << "\n";
                 }
         }
         if (root == NULL)                                       // empty tree?
                 out << "    Null tree.\n";
         else {
                 root->print(0, out);                    // invoke printing at root
         }
 }

void ANNkd_tree::SkeletonTree	(	int	n,
		int	dd,
		int	bs,
		ANNpointArray	pa = `NULL`,
		ANNidxArray	pi = `NULL`
	)

protected

Definition at line 244 of file kd_tree.cpp.

References bkt_size, bnd_box_hi, bnd_box_lo, dim, IDX_TRIVIAL, n_pts, pidx, pts, and root.

Referenced by ANNkd_tree().

 {
         dim = dd;                                                       // initialize basic elements
         n_pts = n;
         bkt_size = bs;
         pts = pa;                                                       // initialize points array
 
         root = NULL;                                            // no associated tree yet
 
         if (pi == NULL) {                                       // point indices provided?
                 pidx = new ANNidx[n];                   // no, allocate space for point indices
                 for (int i = 0; i < n; i++) {
                         pidx[i] = i;                            // initially identity
                 }
         }
         else {
                 pidx = pi;                                              // yes, use them
         }
 
         bnd_box_lo = bnd_box_hi = NULL;         // bounding box is nonexistent
         if (KD_TRIVIAL == NULL)                         // no trivial leaf node yet?
                 KD_TRIVIAL = new ANNkd_leaf(0, IDX_TRIVIAL);    // allocate it
 }