#include "kd_tree.h"
#include "kd_util.h"
#include "kd_split.h"

Include dependency graph for kd_split.cpp:

Functions
void	kd_split (ANNpointArray pa, ANNidxArray pidx, const ANNorthRect &bnds, int n, int dim, int &cut_dim, ANNcoord &cut_val, int &n_lo)

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

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

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

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

Variables
const double	ERR = 0.001

const double	FS_ASPECT_RATIO = 3.0

Function Documentation

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

Definition at line 243 of file kd_split.cpp.

References annMedianSplit(), annPlaneSplit(), annSplitBalance(), annSpread(), dim, FS_ASPECT_RATIO, ANNorthRect::hi, and ANNorthRect::lo.

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

 {
         int d;
         ANNcoord max_length = bnds.hi[0] - bnds.lo[0];
         cut_dim = 0;
         for (d = 1; d < dim; d++) {                     // find length of longest box side
                 ANNcoord length = bnds.hi[d] - bnds.lo[d];
                 if (length > max_length) {
                         max_length = length;
                         cut_dim = d;
                 }
         }
 
         ANNcoord max_spread = 0;                        // find legal cut with max spread
         cut_dim = 0;
         for (d = 0; d < dim; d++) {
                 ANNcoord length = bnds.hi[d] - bnds.lo[d];
                                                                                 // is this side midpoint splitable
                                                                                 // without violating aspect ratio?
                 if (((double) max_length)*2.0/((double) length) <= FS_ASPECT_RATIO) {
                                                                                 // compute spread along this dim
                         ANNcoord spr = annSpread(pa, pidx, n, d);
                         if (spr > max_spread) {         // best spread so far
                                 max_spread = spr;
                                 cut_dim = d;                    // this is dimension to cut
                         }
                 }
         }
 
         max_length = 0;                                         // find longest side other than cut_dim
         for (d = 0; d < dim; d++) {
                 ANNcoord length = bnds.hi[d] - bnds.lo[d];
                 if (d != cut_dim && length > max_length)
                         max_length = length;
         }
                                                                                 // consider most extreme splits
         ANNcoord small_piece = max_length / FS_ASPECT_RATIO;
         ANNcoord lo_cut = bnds.lo[cut_dim] + small_piece;// lowest legal cut
         ANNcoord hi_cut = bnds.hi[cut_dim] - small_piece;// highest legal cut
 
         int br1, br2;
                                                                                 // is median below lo_cut ?
         if (annSplitBalance(pa, pidx, n, cut_dim, lo_cut) >= 0) {
                 cut_val = lo_cut;                               // cut at lo_cut
                 annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
                 n_lo = br1;
         }
                                                                                 // is median above hi_cut?
         else if (annSplitBalance(pa, pidx, n, cut_dim, hi_cut) <= 0) {
                 cut_val = hi_cut;                               // cut at hi_cut
                 annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
                 n_lo = br2;
         }
         else {                                                          // median cut preserves asp ratio
                 n_lo = n/2;                                             // split about median
                 annMedianSplit(pa, pidx, n, cut_dim, cut_val, n_lo);
         }
 }

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

Definition at line 44 of file kd_split.cpp.

References annMaxSpread(), and annMedianSplit().

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

 {
                                                                                 // find dimension of maximum spread
         cut_dim = annMaxSpread(pa, pidx, n, dim);
         n_lo = n/2;                                                     // median rank
                                                                                 // split about median
         annMedianSplit(pa, pidx, n, cut_dim, cut_val, n_lo);
 }

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

Definition at line 76 of file kd_split.cpp.

References annPlaneSplit(), annSpread(), dim, ERR, ANNorthRect::hi, and ANNorthRect::lo.

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

 {
         int d;
 
         ANNcoord max_length = bnds.hi[0] - bnds.lo[0];
         for (d = 1; d < dim; d++) {                     // find length of longest box side
                 ANNcoord length = bnds.hi[d] - bnds.lo[d];
                 if (length > max_length) {
                         max_length = length;
                 }
         }
         ANNcoord max_spread = -1;                       // find long side with most spread
         for (d = 0; d < dim; d++) {
                                                                                 // is it among longest?
                 if (double(bnds.hi[d] - bnds.lo[d]) >= (1-ERR)*max_length) {
                                                                                 // compute its spread
                         ANNcoord spr = annSpread(pa, pidx, n, d);
                         if (spr > max_spread) {         // is it max so far?
                                 max_spread = spr;
                                 cut_dim = d;
                         }
                 }
         }
                                                                                 // split along cut_dim at midpoint
         cut_val = (bnds.lo[cut_dim] + bnds.hi[cut_dim]) / 2;
                                                                                 // permute points accordingly
         int br1, br2;
         annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
         //------------------------------------------------------------------
         //      On return:              pa[0..br1-1] < cut_val
         //                                      pa[br1..br2-1] == cut_val
         //                                      pa[br2..n-1] > cut_val
         //
         //      We can set n_lo to any value in the range [br1..br2].
         //      We choose split so that points are most evenly divided.
         //------------------------------------------------------------------
         if (br1 > n/2) n_lo = br1;
         else if (br2 < n/2) n_lo = br2;
         else n_lo = n/2;
 }

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

Definition at line 346 of file kd_split.cpp.

References annMedianSplit(), annMinMax(), annPlaneSplit(), annSplitBalance(), annSpread(), dim, FS_ASPECT_RATIO, ANNorthRect::hi, and ANNorthRect::lo.

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

 {
         int d;
         ANNcoord min, max;                                      // min/max coordinates
         int br1, br2;                                           // split break points
 
         ANNcoord max_length = bnds.hi[0] - bnds.lo[0];
         cut_dim = 0;
         for (d = 1; d < dim; d++) {                     // find length of longest box side
                 ANNcoord length = bnds.hi[d] - bnds.lo[d];
                 if (length      > max_length) {
                         max_length = length;
                         cut_dim = d;
                 }
         }
 
         ANNcoord max_spread = 0;                        // find legal cut with max spread
         cut_dim = 0;
         for (d = 0; d < dim; d++) {
                 ANNcoord length = bnds.hi[d] - bnds.lo[d];
                                                                                 // is this side midpoint splitable
                                                                                 // without violating aspect ratio?
                 if (((double) max_length)*2.0/((double) length) <= FS_ASPECT_RATIO) {
                                                                                 // compute spread along this dim
                         ANNcoord spr = annSpread(pa, pidx, n, d);
                         if (spr > max_spread) {         // best spread so far
                                 max_spread = spr;
                                 cut_dim = d;                    // this is dimension to cut
                         }
                 }
         }
 
         max_length = 0;                                         // find longest side other than cut_dim
         for (d = 0; d < dim; d++) {
                 ANNcoord length = bnds.hi[d] - bnds.lo[d];
                 if (d != cut_dim && length > max_length)
                         max_length = length;
         }
                                                                                 // consider most extreme splits
         ANNcoord small_piece = max_length / FS_ASPECT_RATIO;
         ANNcoord lo_cut = bnds.lo[cut_dim] + small_piece;// lowest legal cut
         ANNcoord hi_cut = bnds.hi[cut_dim] - small_piece;// highest legal cut
                                                                                 // find min and max along cut_dim
         annMinMax(pa, pidx, n, cut_dim, min, max);
                                                                                 // is median below lo_cut?
         if (annSplitBalance(pa, pidx, n, cut_dim, lo_cut) >= 0) {
                 if (max > lo_cut) {                             // are any points above lo_cut?
                         cut_val = lo_cut;                       // cut at lo_cut
                         annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
                         n_lo = br1;                                     // balance if there are ties
                 }
                 else {                                                  // all points below lo_cut
                         cut_val = max;                          // cut at max value
                         annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
                         n_lo = n-1;
                 }
         }
                                                                                 // is median above hi_cut?
         else if (annSplitBalance(pa, pidx, n, cut_dim, hi_cut) <= 0) {
                 if (min < hi_cut) {                             // are any points below hi_cut?
                         cut_val = hi_cut;                       // cut at hi_cut
                         annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
                         n_lo = br2;                                     // balance if there are ties
                 }
                 else {                                                  // all points above hi_cut
                         cut_val = min;                          // cut at min value
                         annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
                         n_lo = 1;
                 }
         }
         else {                                                          // median cut is good enough
                 n_lo = n/2;                                             // split about median
                 annMedianSplit(pa, pidx, n, cut_dim, cut_val, n_lo);
         }
 }

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

Definition at line 146 of file kd_split.cpp.

References annMinMax(), annPlaneSplit(), annSpread(), dim, ERR, ANNorthRect::hi, and ANNorthRect::lo.

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

 {
         int d;
 
         ANNcoord max_length = bnds.hi[0] - bnds.lo[0];
         for (d = 1; d < dim; d++) {                     // find length of longest box side
                 ANNcoord length = bnds.hi[d] - bnds.lo[d];
                 if (length > max_length) {
                         max_length = length;
                 }
         }
         ANNcoord max_spread = -1;                       // find long side with most spread
         for (d = 0; d < dim; d++) {
                                                                                 // is it among longest?
                 if ((bnds.hi[d] - bnds.lo[d]) >= (1-ERR)*max_length) {
                                                                                 // compute its spread
                         ANNcoord spr = annSpread(pa, pidx, n, d);
                         if (spr > max_spread) {         // is it max so far?
                                 max_spread = spr;
                                 cut_dim = d;
                         }
                 }
         }
                                                                                 // ideal split at midpoint
         ANNcoord ideal_cut_val = (bnds.lo[cut_dim] + bnds.hi[cut_dim])/2;
 
         ANNcoord min, max;
         annMinMax(pa, pidx, n, cut_dim, min, max);      // find min/max coordinates
 
         if (ideal_cut_val < min)                        // slide to min or max as needed
                 cut_val = min;
         else if (ideal_cut_val > max)
                 cut_val = max;
         else
                 cut_val = ideal_cut_val;
 
                                                                                 // permute points accordingly
         int br1, br2;
         annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
         //------------------------------------------------------------------
         //      On return:              pa[0..br1-1] < cut_val
         //                                      pa[br1..br2-1] == cut_val
         //                                      pa[br2..n-1] > cut_val
         //
         //      We can set n_lo to any value in the range [br1..br2] to satisfy
         //      the exit conditions of the procedure.
         //
         //      if ideal_cut_val < min (implying br2 >= 1),
         //                      then we select n_lo = 1 (so there is one point on left) and
         //      if ideal_cut_val > max (implying br1 <= n-1),
         //                      then we select n_lo = n-1 (so there is one point on right).
         //      Otherwise, we select n_lo as close to n/2 as possible within
         //                      [br1..br2].
         //------------------------------------------------------------------
         if (ideal_cut_val < min) n_lo = 1;
         else if (ideal_cut_val > max) n_lo = n-1;
         else if (br1 > n/2) n_lo = br1;
         else if (br2 < n/2) n_lo = br2;
         else n_lo = n/2;
 }

Variable Documentation

const double ERR = 0.001

Definition at line 34 of file kd_split.cpp.

Referenced by doValidation(), midpt_split(), and sl_midpt_split().

const double FS_ASPECT_RATIO = 3.0

Definition at line 35 of file kd_split.cpp.

Referenced by fair_split(), and sl_fair_split().

Functions

Variables

Function Documentation

Variable Documentation