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

Include dependency graph for kd_util.cpp:

Macros
#define	PA(i, d) (pa[pidx[(i)]][(d)])

#define	PP(i) (pa[pidx[(i)]])

#define	PASWAP(a, b) { int tmp = pidx[a]; pidx[a] = pidx[b]; pidx[b] = tmp; }

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)

Macro Definition Documentation

#define PA	(	i,
		d
	)	(pa[pidx[(i)]][(d)])

Definition at line 42 of file kd_util.cpp.

Referenced by annEnclRect(), annMedianSplit(), annMinMax(), annPlaneSplit(), annSplitBalance(), and annSpread().

#define PASWAP	(	a,
		b
	)	{ int tmp = pidx[a]; pidx[a] = pidx[b]; pidx[b] = tmp; }

Definition at line 228 of file kd_util.cpp.

Referenced by annBoxSplit(), annMedianSplit(), and annPlaneSplit().

#define PP ( i ) (pa[pidx[(i)]])

Definition at line 44 of file kd_util.cpp.

Referenced by annBoxSplit().

Function Documentation

double annAspectRatio	(	int	dim,
		const ANNorthRect &	bnd_box
	)

Definition at line 52 of file kd_util.cpp.

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

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(), dim, 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 dim, 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(), dim, and max_dim.

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 k, 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 = (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 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
 }

Macros

Functions

Macro Definition Documentation

Function Documentation