#include <kd_tree.h>

Inheritance diagram for ANNkd_split:

Collaboration diagram for ANNkd_split:

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)

Public Member Functions inherited from ANNkd_node
virtual	~ANNkd_node ()

Private Attributes
int	cut_dim

ANNcoord	cut_val

ANNcoord	cd_bnds [2]

ANNkd_ptr	child [2]

Detailed Description

Definition at line 142 of file kd_tree.h.

Constructor & Destructor Documentation

ANNkd_split::ANNkd_split	(	int	cd,
		ANNcoord	cv,
		ANNcoord	lv,
		ANNcoord	hv,
		ANNkd_ptr	lc = `NULL`,
		ANNkd_ptr	hc = `NULL`
	)

inline

Definition at line 150 of file kd_tree.h.

References ANN_HI, and ANN_LO.

                 {
                         cut_dim         = cd;                                   // cutting dimension
                         cut_val         = cv;                                   // cutting value
                         cd_bnds[ANN_LO] = lv;                           // lower bound for rectangle
                         cd_bnds[ANN_HI] = hv;                           // upper bound for rectangle
                         child[ANN_LO]   = lc;                           // left child
                         child[ANN_HI]   = hc;                           // right child
                 }

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

Member Function Documentation

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, ANNmaxPtsVisited, cd_bnds, child, cut_dim, and cut_val.

 {
                                                                                 // 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 139 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, cd_bnds, child, cut_dim, cut_val, 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, ANNptsVisited, cd_bnds, child, cut_dim, and cut_val.

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

References ANN_HI, and ANN_LO.

 {
         out << "split " << cut_dim << " " << cut_val << " ";
         out << cd_bnds[ANN_LO] << " " << cd_bnds[ANN_HI] << "\n";
 
         child[ANN_LO]->dump(out);                       // print low child
         child[ANN_HI]->dump(out);                       // print high child
 }

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, child, cut_dim, cut_val, 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, cd_bnds, child, cut_dim, cut_val, 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
 }