#include "kd_tree.h"

Functions
double	annAspectRatio (int dim, const ANNorthRect &bnd_box)
void	annEnclRect (ANNpointArray pa, ANNidxArray pidx, int n, int dim, ANNorthRect &bnds)
void	annEnclCube (ANNpointArray pa, ANNidxArray pidx, int n, int dim, ANNorthRect &bnds)
ANNdist	annBoxDistance (const ANNpoint q, const ANNpoint lo, const ANNpoint hi, int dim)
ANNcoord	annSpread (ANNpointArray pa, ANNidxArray pidx, int n, int d)
void	annMinMax (ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord &min, ANNcoord &max)
int	annMaxSpread (ANNpointArray pa, ANNidxArray pidx, int n, int dim)
void	annMedianSplit (ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord &cv, int n_lo)
void	annPlaneSplit (ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord cv, int &br1, int &br2)
void	annBoxSplit (ANNpointArray pa, ANNidxArray pidx, int n, int dim, ANNorthRect &box, int &n_in)
int	annSplitBalance (ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord cv)
void	annBox2Bnds (const ANNorthRect &inner_box, const ANNorthRect &bnd_box, int dim, int &n_bnds, ANNorthHSArray &bnds)
void	annBnds2Box (const ANNorthRect &bnd_box, int dim, int n_bnds, ANNorthHSArray bnds, ANNorthRect &inner_box)

Function Documentation

double annAspectRatio	(	int	dim,
		const ANNorthRect &	bnd_box
	)

Definition at line 52 of file kd_util.cpp.

References ANNorthRect::hi, and ANNorthRect::lo.

Referenced by ANNkd_leaf::getStats().

{
        ANNcoord length = bnd_box.hi[0] - bnd_box.lo[0];
        ANNcoord min_length = length;                           // min side length
        ANNcoord max_length = length;                           // max side length
        for (int d = 0; d < dim; d++) {
                length = bnd_box.hi[d] - bnd_box.lo[d];
                if (length < min_length) min_length = length;
                if (length > max_length) max_length = length;
        }
        return max_length/min_length;
}

void annBnds2Box	(	const ANNorthRect &	bnd_box,
		int	dim,
		int	n_bnds,
		ANNorthHSArray	bnds,
		ANNorthRect &	inner_box
	)

Definition at line 426 of file kd_util.cpp.

References annAssignRect(), ANNorthRect::hi, ANNorthRect::lo, and ANNorthHalfSpace::project().

Referenced by ANNbd_shrink::getStats().

{
        annAssignRect(dim, inner_box, bnd_box);         // copy bounding box to inner

        for (int i = 0; i < n_bnds; i++) {
                bnds[i].project(inner_box.lo);                  // project each endpoint
                bnds[i].project(inner_box.hi);
        }
}

void annBox2Bnds	(	const ANNorthRect &	inner_box,
		const ANNorthRect &	bnd_box,
		int	dim,
		int &	n_bnds,
		ANNorthHSArray &	bnds
	)

Definition at line 384 of file kd_util.cpp.

References ANNorthHalfSpace::cd, ANNorthHalfSpace::cv, ANNorthRect::hi, ANNorthRect::lo, and ANNorthHalfSpace::sd.

Referenced by rbd_tree().

{
        int i;
        n_bnds = 0;                                                                     // count number of bounds
        for (i = 0; i < dim; i++) {
                if (inner_box.lo[i] > bnd_box.lo[i])    // low bound is inside
                                n_bnds++;
                if (inner_box.hi[i] < bnd_box.hi[i])    // high bound is inside
                                n_bnds++;
        }

        bnds = new ANNorthHalfSpace[n_bnds];            // allocate appropriate size

        int j = 0;
        for (i = 0; i < dim; i++) {                                     // fill the array
                if (inner_box.lo[i] > bnd_box.lo[i]) {
                                bnds[j].cd = i;
                                bnds[j].cv = inner_box.lo[i];
                                bnds[j].sd = +1;
                                j++;
                }
                if (inner_box.hi[i] < bnd_box.hi[i]) {
                                bnds[j].cd = i;
                                bnds[j].cv = inner_box.hi[i];
                                bnds[j].sd = -1;
                                j++;
                }
        }
}

ANNdist annBoxDistance	(	const ANNpoint	q,
		const ANNpoint	lo,
		const ANNpoint	hi,
		int	dim
	)

Definition at line 124 of file kd_util.cpp.

References ANN_FLOP, ANN_POW, ANN_SUM, QuadProgPP::dist(), and QuadProgPP::t().

Referenced by ANNkd_tree::annkFRSearch(), ANNkd_tree::annkPriSearch(), and ANNkd_tree::annkSearch().

{
        register ANNdist dist = 0.0;            // sum of squared distances
        register ANNdist t;

        for (register int d = 0; d < dim; d++) {
                if (q[d] < lo[d]) {                             // q is left of box
                        t = ANNdist(lo[d]) - ANNdist(q[d]);
                        dist = ANN_SUM(dist, ANN_POW(t));
                }
                else if (q[d] > hi[d]) {                // q is right of box
                        t = ANNdist(q[d]) - ANNdist(hi[d]);
                        dist = ANN_SUM(dist, ANN_POW(t));
                }
        }
        ANN_FLOP(4*dim)                                         // increment floating op count

        return dist;
}

void annBoxSplit	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim,
		ANNorthRect &	box,
		int &	n_in
	)

Definition at line 332 of file kd_util.cpp.

References ANNorthRect::inside(), PASWAP, and PP.

Referenced by rbd_tree().

{
        int l = 0;
        int r = n-1;
        for(;;) {                                                       // partition pa[0..n-1] about box
                while (l < n && box.inside(dim, PP(l))) l++;
                while (r >= 0 && !box.inside(dim, PP(r))) r--;
                if (l > r) break;
                PASWAP(l,r);
                l++; r--;
        }
        n_in = l;                                       // now: pa[0..n_in-1] inside and rest outside
}

void annEnclCube	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim,
		ANNorthRect &	bnds
	)

Definition at line 92 of file kd_util.cpp.

References annEnclRect(), ANNorthRect::hi, and ANNorthRect::lo.

{
        int d;
                                                                                // compute smallest enclosing rect
        annEnclRect(pa, pidx, n, dim, bnds);

        ANNcoord max_len = 0;                           // max length of any side
        for (d = 0; d < dim; d++) {                     // determine max side length
                ANNcoord len = bnds.hi[d] - bnds.lo[d];
                if (len > max_len) {                    // update max_len if longest
                        max_len = len;
                }
        }
        for (d = 0; d < dim; d++) {                     // grow sides to match max
                ANNcoord len = bnds.hi[d] - bnds.lo[d];
                ANNcoord half_diff = (max_len - len) / 2;
                bnds.lo[d] -= half_diff;
                bnds.hi[d] += half_diff;
        }
}

void annEnclRect	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim,
		ANNorthRect &	bnds
	)

Definition at line 73 of file kd_util.cpp.

References ANNorthRect::hi, ANNorthRect::lo, and PA.

Referenced by ANNbd_tree::ANNbd_tree(), annEnclCube(), ANNkd_tree::ANNkd_tree(), and trySimpleShrink().

{
        for (int d = 0; d < dim; d++) {         // find smallest enclosing rectangle
                ANNcoord lo_bnd = PA(0,d);              // lower bound on dimension d
                ANNcoord hi_bnd = PA(0,d);              // upper bound on dimension d
                for (int i = 0; i < n; i++) {
                        if (PA(i,d) < lo_bnd) lo_bnd = PA(i,d);
                        else if (PA(i,d) > hi_bnd) hi_bnd = PA(i,d);
                }
                bnds.lo[d] = lo_bnd;
                bnds.hi[d] = hi_bnd;
        }
}

int annMaxSpread	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	dim
	)

Definition at line 187 of file kd_util.cpp.

References annSpread().

Referenced by kd_split().

{
        int max_dim = 0;                                        // dimension of max spread
        ANNcoord max_spr = 0;                           // amount of max spread

        if (n == 0) return max_dim;                     // no points, who cares?

        for (int d = 0; d < dim; d++) {         // compute spread along each dim
                ANNcoord spr = annSpread(pa, pidx, n, d);
                if (spr > max_spr) {                    // bigger than current max
                        max_spr = spr;
                        max_dim = d;
                }
        }
        return max_dim;
}

void annMedianSplit	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	d,
		ANNcoord &	cv,
		int	n_lo
	)

Definition at line 230 of file kd_util.cpp.

References PA, and PASWAP.

Referenced by fair_split(), kd_split(), and sl_fair_split().

{
        int l = 0;                                                      // left end of current subarray
        int r = n-1;                                            // right end of current subarray
        while (l < r) {
                register int i = (r+l)/2;               // select middle as pivot
                register int k;

                if (PA(i,d) > PA(r,d))                  // make sure last > pivot
                        PASWAP(i,r)
                PASWAP(l,i);                                    // move pivot to first position

                ANNcoord c = PA(l,d);                   // pivot value
                i = l;
                k = r;
                for(;;) {                                               // pivot about c
                        while (PA(++i,d) < c) ;
                        while (PA(--k,d) > c) ;
                        if (i < k) PASWAP(i,k) else break;
                }
                PASWAP(l,k);                                    // pivot winds up in location k

                if (k > n_lo)      r = k-1;             // recurse on proper subarray
                else if (k < n_lo) l = k+1;
                else break;                                             // got the median exactly
        }
        if (n_lo > 0) {                                         // search for next smaller item
                ANNcoord c = PA(0,d);                   // candidate for max
                int k = 0;                                              // candidate's index
                for (int i = 1; i < n_lo; i++) {
                        if (PA(i,d) > c) {
                                c = PA(i,d);
                                k = i;
                        }
                }
                PASWAP(n_lo-1, k);                              // max among pa[0..n_lo-1] to pa[n_lo-1]
        }
                                                                                // cut value is midpoint value
        cv = (ANNcoord)((PA(n_lo-1,d) + PA(n_lo,d))/2.0);
}

void annMinMax	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	d,
		ANNcoord &	min,
		ANNcoord &	max
	)

Definition at line 170 of file kd_util.cpp.

References PA.

Referenced by sl_fair_split(), and sl_midpt_split().

{
        min = PA(0,d);                                          // compute max and min coords
        max = PA(0,d);
        for (int i = 1; i < n; i++) {
                ANNcoord c = PA(i,d);
                if (c < min) min = c;
                else if (c > max) max = c;
        }
}

void annPlaneSplit	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	d,
		ANNcoord	cv,
		int &	br1,
		int &	br2
	)

Definition at line 291 of file kd_util.cpp.

References PA, and PASWAP.

Referenced by fair_split(), midpt_split(), sl_fair_split(), and sl_midpt_split().

{
        int l = 0;
        int r = n-1;
        for(;;) {                                                       // partition pa[0..n-1] about cv
                while (l < n && PA(l,d) < cv) l++;
                while (r >= 0 && PA(r,d) >= cv) r--;
                if (l > r) break;
                PASWAP(l,r);
                l++; r--;
        }
        br1 = l;                                        // now: pa[0..br1-1] < cv <= pa[br1..n-1]
        r = n-1;
        for(;;) {                                                       // partition pa[br1..n-1] about cv
                while (l < n && PA(l,d) <= cv) l++;
                while (r >= br1 && PA(r,d) > cv) r--;
                if (l > r) break;
                PASWAP(l,r);
                l++; r--;
        }
        br2 = l;                                        // now: pa[br1..br2-1] == cv < pa[br2..n-1]
}

int annSplitBalance	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	d,
		ANNcoord	cv
	)

Definition at line 360 of file kd_util.cpp.

References PA.

Referenced by fair_split(), and sl_fair_split().

{
        int n_lo = 0;
        for(int i = 0; i < n; i++) {            // count number less than cv
                if (PA(i,d) < cv) n_lo++;
        }
        return n_lo - n/2;
}

ANNcoord annSpread	(	ANNpointArray	pa,
		ANNidxArray	pidx,
		int	n,
		int	d
	)

Definition at line 154 of file kd_util.cpp.

References QuadProgPP::max(), min, and PA.

Referenced by annMaxSpread(), fair_split(), midpt_split(), sl_fair_split(), and sl_midpt_split().

{
        ANNcoord min = PA(0,d);                         // compute max and min coords
        ANNcoord max = PA(0,d);
        for (int i = 1; i < n; i++) {
                ANNcoord c = PA(i,d);
                if (c < min) min = c;
                else if (c > max) max = c;
        }
        return (max - min);                                     // total spread is difference
}

kd_util.h File Reference

Functions

Function Documentation