kd_tree.h File Reference

#include <ANN/ANNx.h>

Include dependency graph for kd_tree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	ANNkd_node
class	ANNkd_leaf
class	ANNkd_split

Typedefs
typedef void(*	ANNkd_splitter )(ANNpointArray pa, ANNidxArray pidx, const ANNorthRect &bnds, int n, int dim, int &cut_dim, ANNcoord &cut_val, int &n_lo)

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

Variables
ANNkd_leaf *	KD_TRIVIAL

Typedef Documentation

typedef void(* ANNkd_splitter)(ANNpointArray pa,ANNidxArray pidx,const ANNorthRect &bnds,int n,int dim,int &cut_dim,ANNcoord &cut_val,int &n_lo)

Definition at line 72 of file kd_tree.h.

Function Documentation

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, 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

ANNkd_leaf* KD_TRIVIAL

Definition at line 50 of file kd_tree.cpp.

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