#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)
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 711 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().

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

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(), pts, and root.

{
        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, ANNkd_node::ann_pri_search(), 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(), ANNmin_k::max_key(), n_pts, ANNpr_queue::non_empty(), pts, and root.

{
                                                                                // 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
  void* pVoid_Np = NULL;

        while (ANNprBoxPQ->non_empty() &&
                (!(ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited))) {
                ANNprBoxPQ->extr_min(box_dist, pVoid_Np); // extract closest box from queue
    ANNkd_ptr np = (ANNkd_ptr)pVoid_Np;        // next box from prior queue

                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(), n_pts, pts, and root.

Referenced by ipMITKSegmentationGetCutPoints(), and ipMITKSegmentationGetDistGradient().

{

        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
}

virtual void ANNkd_tree::Dump	(	ANNbool	with_pts,
		std::ostream &	out
	)		`[virtual]`

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.

{
        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 ( ) [inline, virtual]

Implements ANNpointSet.

Definition at line 772 of file ANN.h.

                { return n_pts; }

virtual void ANNkd_tree::Print	(	ANNbool	with_pts,
		std::ostream &	out
	)		`[virtual]`

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
}