queso-0.53.0
Functions | Variables
kd_split.cpp File Reference
#include "kd_tree.h"
#include "kd_util.h"
#include "kd_split.h"
Include dependency graph for kd_split.cpp:

Go to the source code of this file.

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

252 {
253  int d;
254  ANNcoord max_length = bnds.hi[0] - bnds.lo[0];
255  cut_dim = 0;
256  for (d = 1; d < dim; d++) { // find length of longest box side
257  ANNcoord length = bnds.hi[d] - bnds.lo[d];
258  if (length > max_length) {
259  max_length = length;
260  cut_dim = d;
261  }
262  }
263 
264  ANNcoord max_spread = 0; // find legal cut with max spread
265  cut_dim = 0;
266  for (d = 0; d < dim; d++) {
267  ANNcoord length = bnds.hi[d] - bnds.lo[d];
268  // is this side midpoint splitable
269  // without violating aspect ratio?
270  if (((double) max_length)*2.0/((double) length) <= FS_ASPECT_RATIO) {
271  // compute spread along this dim
272  ANNcoord spr = annSpread(pa, pidx, n, d);
273  if (spr > max_spread) { // best spread so far
274  max_spread = spr;
275  cut_dim = d; // this is dimension to cut
276  }
277  }
278  }
279 
280  max_length = 0; // find longest side other than cut_dim
281  for (d = 0; d < dim; d++) {
282  ANNcoord length = bnds.hi[d] - bnds.lo[d];
283  if (d != cut_dim && length > max_length)
284  max_length = length;
285  }
286  // consider most extreme splits
287  ANNcoord small_piece = max_length / FS_ASPECT_RATIO;
288  ANNcoord lo_cut = bnds.lo[cut_dim] + small_piece;// lowest legal cut
289  ANNcoord hi_cut = bnds.hi[cut_dim] - small_piece;// highest legal cut
290 
291  int br1, br2;
292  // is median below lo_cut ?
293  if (annSplitBalance(pa, pidx, n, cut_dim, lo_cut) >= 0) {
294  cut_val = lo_cut; // cut at lo_cut
295  annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
296  n_lo = br1;
297  }
298  // is median above hi_cut?
299  else if (annSplitBalance(pa, pidx, n, cut_dim, hi_cut) <= 0) {
300  cut_val = hi_cut; // cut at hi_cut
301  annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
302  n_lo = br2;
303  }
304  else { // median cut preserves asp ratio
305  n_lo = n/2; // split about median
306  annMedianSplit(pa, pidx, n, cut_dim, cut_val, n_lo);
307  }
308 }
int annSplitBalance(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord cv)
Definition: kd_util.cpp:360
double ANNcoord
Definition: ANN.h:158
ANNcoord annSpread(ANNpointArray pa, ANNidxArray pidx, int n, int d)
Definition: kd_util.cpp:154
void annMedianSplit(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord &cv, int n_lo)
Definition: kd_util.cpp:230
ANNpoint lo
Definition: ANNx.h:93
void annPlaneSplit(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord cv, int &br1, int &br2)
Definition: kd_util.cpp:291
int dim
Definition: ann2fig.cpp:81
ANNpoint hi
Definition: ANNx.h:94
const double FS_ASPECT_RATIO
Definition: kd_split.cpp:35
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().

53 {
54  // find dimension of maximum spread
55  cut_dim = annMaxSpread(pa, pidx, n, dim);
56  n_lo = n/2; // median rank
57  // split about median
58  annMedianSplit(pa, pidx, n, cut_dim, cut_val, n_lo);
59 }
void annMedianSplit(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord &cv, int n_lo)
Definition: kd_util.cpp:230
int annMaxSpread(ANNpointArray pa, ANNidxArray pidx, int n, int dim)
Definition: kd_util.cpp:187
int dim
Definition: ann2fig.cpp:81
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().

85 {
86  int d;
87 
88  ANNcoord max_length = bnds.hi[0] - bnds.lo[0];
89  for (d = 1; d < dim; d++) { // find length of longest box side
90  ANNcoord length = bnds.hi[d] - bnds.lo[d];
91  if (length > max_length) {
92  max_length = length;
93  }
94  }
95  ANNcoord max_spread = -1; // find long side with most spread
96  for (d = 0; d < dim; d++) {
97  // is it among longest?
98  if (double(bnds.hi[d] - bnds.lo[d]) >= (1-ERR)*max_length) {
99  // compute its spread
100  ANNcoord spr = annSpread(pa, pidx, n, d);
101  if (spr > max_spread) { // is it max so far?
102  max_spread = spr;
103  cut_dim = d;
104  }
105  }
106  }
107  // split along cut_dim at midpoint
108  cut_val = (bnds.lo[cut_dim] + bnds.hi[cut_dim]) / 2;
109  // permute points accordingly
110  int br1, br2;
111  annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
112  //------------------------------------------------------------------
113  // On return: pa[0..br1-1] < cut_val
114  // pa[br1..br2-1] == cut_val
115  // pa[br2..n-1] > cut_val
116  //
117  // We can set n_lo to any value in the range [br1..br2].
118  // We choose split so that points are most evenly divided.
119  //------------------------------------------------------------------
120  if (br1 > n/2) n_lo = br1;
121  else if (br2 < n/2) n_lo = br2;
122  else n_lo = n/2;
123 }
double ANNcoord
Definition: ANN.h:158
ANNcoord annSpread(ANNpointArray pa, ANNidxArray pidx, int n, int d)
Definition: kd_util.cpp:154
ANNpoint lo
Definition: ANNx.h:93
void annPlaneSplit(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord cv, int &br1, int &br2)
Definition: kd_util.cpp:291
int dim
Definition: ann2fig.cpp:81
ANNpoint hi
Definition: ANNx.h:94
const double ERR
Definition: kd_split.cpp:34
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().

355 {
356  int d;
357  ANNcoord min, max; // min/max coordinates
358  int br1, br2; // split break points
359 
360  ANNcoord max_length = bnds.hi[0] - bnds.lo[0];
361  cut_dim = 0;
362  for (d = 1; d < dim; d++) { // find length of longest box side
363  ANNcoord length = bnds.hi[d] - bnds.lo[d];
364  if (length > max_length) {
365  max_length = length;
366  cut_dim = d;
367  }
368  }
369 
370  ANNcoord max_spread = 0; // find legal cut with max spread
371  cut_dim = 0;
372  for (d = 0; d < dim; d++) {
373  ANNcoord length = bnds.hi[d] - bnds.lo[d];
374  // is this side midpoint splitable
375  // without violating aspect ratio?
376  if (((double) max_length)*2.0/((double) length) <= FS_ASPECT_RATIO) {
377  // compute spread along this dim
378  ANNcoord spr = annSpread(pa, pidx, n, d);
379  if (spr > max_spread) { // best spread so far
380  max_spread = spr;
381  cut_dim = d; // this is dimension to cut
382  }
383  }
384  }
385 
386  max_length = 0; // find longest side other than cut_dim
387  for (d = 0; d < dim; d++) {
388  ANNcoord length = bnds.hi[d] - bnds.lo[d];
389  if (d != cut_dim && length > max_length)
390  max_length = length;
391  }
392  // consider most extreme splits
393  ANNcoord small_piece = max_length / FS_ASPECT_RATIO;
394  ANNcoord lo_cut = bnds.lo[cut_dim] + small_piece;// lowest legal cut
395  ANNcoord hi_cut = bnds.hi[cut_dim] - small_piece;// highest legal cut
396  // find min and max along cut_dim
397  annMinMax(pa, pidx, n, cut_dim, min, max);
398  // is median below lo_cut?
399  if (annSplitBalance(pa, pidx, n, cut_dim, lo_cut) >= 0) {
400  if (max > lo_cut) { // are any points above lo_cut?
401  cut_val = lo_cut; // cut at lo_cut
402  annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
403  n_lo = br1; // balance if there are ties
404  }
405  else { // all points below lo_cut
406  cut_val = max; // cut at max value
407  annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
408  n_lo = n-1;
409  }
410  }
411  // is median above hi_cut?
412  else if (annSplitBalance(pa, pidx, n, cut_dim, hi_cut) <= 0) {
413  if (min < hi_cut) { // are any points below hi_cut?
414  cut_val = hi_cut; // cut at hi_cut
415  annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
416  n_lo = br2; // balance if there are ties
417  }
418  else { // all points above hi_cut
419  cut_val = min; // cut at min value
420  annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
421  n_lo = 1;
422  }
423  }
424  else { // median cut is good enough
425  n_lo = n/2; // split about median
426  annMedianSplit(pa, pidx, n, cut_dim, cut_val, n_lo);
427  }
428 }
void annMinMax(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord &min, ANNcoord &max)
Definition: kd_util.cpp:170
int annSplitBalance(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord cv)
Definition: kd_util.cpp:360
double ANNcoord
Definition: ANN.h:158
ANNcoord annSpread(ANNpointArray pa, ANNidxArray pidx, int n, int d)
Definition: kd_util.cpp:154
void annMedianSplit(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord &cv, int n_lo)
Definition: kd_util.cpp:230
ANNpoint lo
Definition: ANNx.h:93
void annPlaneSplit(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord cv, int &br1, int &br2)
Definition: kd_util.cpp:291
int dim
Definition: ann2fig.cpp:81
ANNpoint hi
Definition: ANNx.h:94
const double FS_ASPECT_RATIO
Definition: kd_split.cpp:35
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().

155 {
156  int d;
157 
158  ANNcoord max_length = bnds.hi[0] - bnds.lo[0];
159  for (d = 1; d < dim; d++) { // find length of longest box side
160  ANNcoord length = bnds.hi[d] - bnds.lo[d];
161  if (length > max_length) {
162  max_length = length;
163  }
164  }
165  ANNcoord max_spread = -1; // find long side with most spread
166  for (d = 0; d < dim; d++) {
167  // is it among longest?
168  if ((bnds.hi[d] - bnds.lo[d]) >= (1-ERR)*max_length) {
169  // compute its spread
170  ANNcoord spr = annSpread(pa, pidx, n, d);
171  if (spr > max_spread) { // is it max so far?
172  max_spread = spr;
173  cut_dim = d;
174  }
175  }
176  }
177  // ideal split at midpoint
178  ANNcoord ideal_cut_val = (bnds.lo[cut_dim] + bnds.hi[cut_dim])/2;
179 
180  ANNcoord min, max;
181  annMinMax(pa, pidx, n, cut_dim, min, max); // find min/max coordinates
182 
183  if (ideal_cut_val < min) // slide to min or max as needed
184  cut_val = min;
185  else if (ideal_cut_val > max)
186  cut_val = max;
187  else
188  cut_val = ideal_cut_val;
189 
190  // permute points accordingly
191  int br1, br2;
192  annPlaneSplit(pa, pidx, n, cut_dim, cut_val, br1, br2);
193  //------------------------------------------------------------------
194  // On return: pa[0..br1-1] < cut_val
195  // pa[br1..br2-1] == cut_val
196  // pa[br2..n-1] > cut_val
197  //
198  // We can set n_lo to any value in the range [br1..br2] to satisfy
199  // the exit conditions of the procedure.
200  //
201  // if ideal_cut_val < min (implying br2 >= 1),
202  // then we select n_lo = 1 (so there is one point on left) and
203  // if ideal_cut_val > max (implying br1 <= n-1),
204  // then we select n_lo = n-1 (so there is one point on right).
205  // Otherwise, we select n_lo as close to n/2 as possible within
206  // [br1..br2].
207  //------------------------------------------------------------------
208  if (ideal_cut_val < min) n_lo = 1;
209  else if (ideal_cut_val > max) n_lo = n-1;
210  else if (br1 > n/2) n_lo = br1;
211  else if (br2 < n/2) n_lo = br2;
212  else n_lo = n/2;
213 }
void annMinMax(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord &min, ANNcoord &max)
Definition: kd_util.cpp:170
double ANNcoord
Definition: ANN.h:158
ANNcoord annSpread(ANNpointArray pa, ANNidxArray pidx, int n, int d)
Definition: kd_util.cpp:154
ANNpoint lo
Definition: ANNx.h:93
void annPlaneSplit(ANNpointArray pa, ANNidxArray pidx, int n, int d, ANNcoord cv, int &br1, int &br2)
Definition: kd_util.cpp:291
int dim
Definition: ann2fig.cpp:81
ANNpoint hi
Definition: ANNx.h:94
const double ERR
Definition: kd_split.cpp:34

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


Generated on Thu Jun 11 2015 13:52:33 for queso-0.53.0 by  doxygen 1.8.5