kd_tree.cpp File Reference

Go to the source code of this file.

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

Function Documentation

void annClose

(

)

Definition at line 221 of file kd_tree.cpp.

References KD_TRIVIAL.

Referenced by QUESO::distANN_XY(), and main().

{
        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 dim, and KD_TRIVIAL.

Referenced by ANNkd_tree::ANNkd_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 annClose(), annReadTree(), rbd_tree(), rkd_tree(), and ANNkd_tree::SkeletonTree().