kd_tree.cpp File Reference

#include "kd_tree.h"
#include "kd_split.h"
#include "kd_util.h"
#include <ANN/ANNperf.h>

Go to the source code of this file.

Defines
#define	MAX(a, b)   ((a) > (b) ? (a) : (b))
Functions
void	annClose ()
ANNkd_ptr	rkd_tree (ANNpointArray pa, ANNidxArray pidx, int n, int dim, int bsp, ANNorthRect &bnd_box, ANNkd_splitter splitter)
Variables
static int	IDX_TRIVIAL [] = {0}
ANNkd_leaf *	KD_TRIVIAL = NULL
const double	ANN_AR_TOOBIG = 1000

---

Define Documentation

#define MAX	(		a,
			b
	)		((a) > (b) ? (a) : (b))

Definition at line 131 of file kd_tree.cpp.

Referenced by ANNkdStats::merge().

---

Function Documentation

void annClose

(

)

Definition at line 221 of file kd_tree.cpp.

References KD_TRIVIAL.

{
        if (KD_TRIVIAL != NULL) {
                delete KD_TRIVIAL;
                KD_TRIVIAL = NULL;
        }
}

ANNkd_ptr rkd_tree	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim,
		int	bsp,
		ANNorthRect &	bnd_box,
		ANNkd_splitter	splitter
	)

Definition at line 314 of file kd_tree.cpp.

References KD_TRIVIAL, and rkd_tree().

Referenced by ANNkd_tree::ANNkd_tree(), and rkd_tree().

{
        if (n <= bsp) {                                         // n small, make a leaf node
                if (n == 0)                                             // empty leaf node
                        return KD_TRIVIAL;                      // return (canonical) empty leaf
                else                                                    // construct the node and return
                        return new ANNkd_leaf(n, pidx); 
        }
        else {                                                          // n large, make a splitting node
                int cd;                                                 // cutting dimension
                ANNcoord cv;                                    // cutting value
                int n_lo;                                               // number on low side of cut
                ANNkd_node *lo, *hi;                    // low and high children

                                                                                // invoke splitting procedure
                (*splitter)(pa, pidx, bnd_box, n, dim, cd, cv, n_lo);

                ANNcoord lv = bnd_box.lo[cd];   // save bounds for cutting dimension
                ANNcoord hv = bnd_box.hi[cd];

                bnd_box.hi[cd] = cv;                    // modify bounds for left subtree
                lo = rkd_tree(                                  // build left subtree
                                pa, pidx, n_lo,                 // ...from pidx[0..n_lo-1]
                                dim, bsp, bnd_box, splitter);
                bnd_box.hi[cd] = hv;                    // restore bounds

                bnd_box.lo[cd] = cv;                    // modify bounds for right subtree
                hi = rkd_tree(                                  // build right subtree
                                pa, pidx + n_lo, n-n_lo,// ...from pidx[n_lo..n-1]
                                dim, bsp, bnd_box, splitter);
                bnd_box.lo[cd] = lv;                    // restore bounds

                                                                                // create the splitting node
                ANNkd_split *ptr = new ANNkd_split(cd, cv, lv, hv, lo, hi);

                return ptr;                                             // return pointer to this node
        }
} 

---

Variable Documentation

const double ANN_AR_TOOBIG = 1000

Definition at line 145 of file kd_tree.cpp.

int IDX_TRIVIAL[] = {0} [static]

Definition at line 49 of file kd_tree.cpp.

Referenced by ANNkd_tree::SkeletonTree().

ANNkd_leaf* KD_TRIVIAL = NULL

Definition at line 50 of file kd_tree.cpp.

Referenced by ANNkd_split::ann_pri_search(), ANNbd_shrink::ann_pri_search(), annClose(), annReadTree(), ANNkd_leaf::dump(), rbd_tree(), rkd_tree(), ANNbd_shrink::~ANNbd_shrink(), and ANNkd_split::~ANNkd_split().