queso-0.57.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
kd_util.cpp File Reference

Go to the source code of this file.

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 dim, ANNorthRect::hi, and ANNorthRect::lo.

55 {
56  ANNcoord length = bnd_box.hi[0] - bnd_box.lo[0];
57  ANNcoord min_length = length; // min side length
58  ANNcoord max_length = length; // max side length
59  for (int d = 0; d < dim; d++) {
60  length = bnd_box.hi[d] - bnd_box.lo[d];
61  if (length < min_length) min_length = length;
62  if (length > max_length) max_length = length;
63  }
64  return max_length/min_length;
65 }
ANNpoint hi
Definition: ANNx.h:94
double ANNcoord
Definition: ANN.h:158
ANNpoint lo
Definition: ANNx.h:93
int dim
Definition: ann_test.cpp:472
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().

432 {
433  annAssignRect(dim, inner_box, bnd_box); // copy bounding box to inner
434 
435  for (int i = 0; i < n_bnds; i++) {
436  bnds[i].project(inner_box.lo); // project each endpoint
437  bnds[i].project(inner_box.hi);
438  }
439 }
ANNpoint hi
Definition: ANNx.h:94
void project(ANNpoint &q)
Definition: ANNx.h:162
ANNpoint lo
Definition: ANNx.h:93
int dim
Definition: ann_test.cpp:472
void annAssignRect(int dim, ANNorthRect &dest, const ANNorthRect &source)
Definition: ANN.cpp:148
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().

390 {
391  int i;
392  n_bnds = 0; // count number of bounds
393  for (i = 0; i < dim; i++) {
394  if (inner_box.lo[i] > bnd_box.lo[i]) // low bound is inside
395  n_bnds++;
396  if (inner_box.hi[i] < bnd_box.hi[i]) // high bound is inside
397  n_bnds++;
398  }
399 
400  bnds = new ANNorthHalfSpace[n_bnds]; // allocate appropriate size
401 
402  int j = 0;
403  for (i = 0; i < dim; i++) { // fill the array
404  if (inner_box.lo[i] > bnd_box.lo[i]) {
405  bnds[j].cd = i;
406  bnds[j].cv = inner_box.lo[i];
407  bnds[j].sd = +1;
408  j++;
409  }
410  if (inner_box.hi[i] < bnd_box.hi[i]) {
411  bnds[j].cd = i;
412  bnds[j].cv = inner_box.hi[i];
413  bnds[j].sd = -1;
414  j++;
415  }
416  }
417 }
ANNpoint hi
Definition: ANNx.h:94
ANNcoord cv
Definition: ANNx.h:135
ANNpoint lo
Definition: ANNx.h:93
int dim
Definition: ann_test.cpp:472
ANNdist annBoxDistance ( const ANNpoint  q,
const ANNpoint  lo,
const ANNpoint  hi,
int  dim 
)

Definition at line 124 of file kd_util.cpp.

References dim.

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

129 {
130  register ANNdist dist = 0.0; // sum of squared distances
131  register ANNdist t;
132 
133  for (register int d = 0; d < dim; d++) {
134  if (q[d] < lo[d]) { // q is left of box
135  t = ANNdist(lo[d]) - ANNdist(q[d]);
136  dist = ANN_SUM(dist, ANN_POW(t));
137  }
138  else if (q[d] > hi[d]) { // q is right of box
139  t = ANNdist(q[d]) - ANNdist(hi[d]);
140  dist = ANN_SUM(dist, ANN_POW(t));
141  }
142  }
143  ANN_FLOP(4*dim) // increment floating op count
144 
145  return dist;
146 }
double ANNdist
Definition: ANN.h:159
int dim
Definition: ann_test.cpp:472
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().

Referenced by rbd_tree().

339 {
340  int l = 0;
341  int r = n-1;
342  for(;;) { // partition pa[0..n-1] about box
343  while (l < n && box.inside(dim, PP(l))) l++;
344  while (r >= 0 && !box.inside(dim, PP(r))) r--;
345  if (l > r) break;
346  PASWAP(l,r);
347  l++; r--;
348  }
349  n_in = l; // now: pa[0..n_in-1] inside and rest outside
350 }
int dim
Definition: ann_test.cpp:472
ANNbool inside(int dim, ANNpoint p)
Definition: ANN.cpp:157
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.

98 {
99  int d;
100  // compute smallest enclosing rect
101  annEnclRect(pa, pidx, n, dim, bnds);
102 
103  ANNcoord max_len = 0; // max length of any side
104  for (d = 0; d < dim; d++) { // determine max side length
105  ANNcoord len = bnds.hi[d] - bnds.lo[d];
106  if (len > max_len) { // update max_len if longest
107  max_len = len;
108  }
109  }
110  for (d = 0; d < dim; d++) { // grow sides to match max
111  ANNcoord len = bnds.hi[d] - bnds.lo[d];
112  ANNcoord half_diff = (max_len - len) / 2;
113  bnds.lo[d] -= half_diff;
114  bnds.hi[d] += half_diff;
115  }
116 }
void annEnclRect(ANNpointArray pa, ANNidxArray pidx, int n, int dim, ANNorthRect &bnds)
Definition: kd_util.cpp:73
ANNpoint hi
Definition: ANNx.h:94
double ANNcoord
Definition: ANN.h:158
ANNpoint lo
Definition: ANNx.h:93
int dim
Definition: ann_test.cpp:472
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, and ANNorthRect::lo.

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

79 {
80  for (int d = 0; d < dim; d++) { // find smallest enclosing rectangle
81  ANNcoord lo_bnd = PA(0,d); // lower bound on dimension d
82  ANNcoord hi_bnd = PA(0,d); // upper bound on dimension d
83  for (int i = 0; i < n; i++) {
84  if (PA(i,d) < lo_bnd) lo_bnd = PA(i,d);
85  else if (PA(i,d) > hi_bnd) hi_bnd = PA(i,d);
86  }
87  bnds.lo[d] = lo_bnd;
88  bnds.hi[d] = hi_bnd;
89  }
90 }
ANNpoint hi
Definition: ANNx.h:94
double ANNcoord
Definition: ANN.h:158
ANNpoint lo
Definition: ANNx.h:93
int dim
Definition: ann_test.cpp:472
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().

192 {
193  int max_dim = 0; // dimension of max spread
194  ANNcoord max_spr = 0; // amount of max spread
195 
196  if (n == 0) return max_dim; // no points, who cares?
197 
198  for (int d = 0; d < dim; d++) { // compute spread along each dim
199  ANNcoord spr = annSpread(pa, pidx, n, d);
200  if (spr > max_spr) { // bigger than current max
201  max_spr = spr;
202  max_dim = d;
203  }
204  }
205  return max_dim;
206 }
ANNcoord annSpread(ANNpointArray pa, ANNidxArray pidx, int n, int d)
Definition: kd_util.cpp:154
double ANNcoord
Definition: ANN.h:158
int dim
Definition: ann_test.cpp:472
int max_dim
Definition: ann_test.cpp:477
void annMedianSplit ( ANNpointArray  pa,
ANNidxArray  pidx,
int  n,
int  d,
ANNcoord cv,
int  n_lo 
)

Definition at line 230 of file kd_util.cpp.

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

237 {
238  int l = 0; // left end of current subarray
239  int r = n-1; // right end of current subarray
240  while (l < r) {
241  register int i = (r+l)/2; // select middle as pivot
242  register int k;
243 
244  if (PA(i,d) > PA(r,d)) // make sure last > pivot
245  PASWAP(i,r)
246  PASWAP(l,i); // move pivot to first position
247 
248  ANNcoord c = PA(l,d); // pivot value
249  i = l;
250  k = r;
251  for(;;) { // pivot about c
252  while (PA(++i,d) < c) ;
253  while (PA(--k,d) > c) ;
254  if (i < k) PASWAP(i,k) else break;
255  }
256  PASWAP(l,k); // pivot winds up in location k
257 
258  if (k > n_lo) r = k-1; // recurse on proper subarray
259  else if (k < n_lo) l = k+1;
260  else break; // got the median exactly
261  }
262  if (n_lo > 0) { // search for next smaller item
263  ANNcoord c = PA(0,d); // candidate for max
264  int k = 0; // candidate's index
265  for (int i = 1; i < n_lo; i++) {
266  if (PA(i,d) > c) {
267  c = PA(i,d);
268  k = i;
269  }
270  }
271  PASWAP(n_lo-1, k); // max among pa[0..n_lo-1] to pa[n_lo-1]
272  }
273  // cut value is midpoint value
274  cv = (PA(n_lo-1,d) + PA(n_lo,d))/2.0;
275 }
double ANNcoord
Definition: ANN.h:158
McOptionsValues::McOptionsValues(#ifdef QUESO_USES_SEQUENCE_STATISTICAL_OPTIONS const SsOptionsValues *alternativePSsOptionsValues, const SsOptionsValues *alternativeQSsOptionsValues#endif if)(m_alternativeQSsOptionsValues=*alternativeQSsOptionsValues)
void annMinMax ( ANNpointArray  pa,
ANNidxArray  pidx,
int  n,
int  d,
ANNcoord min,
ANNcoord max 
)

Definition at line 170 of file kd_util.cpp.

Referenced by sl_fair_split(), and sl_midpt_split().

177 {
178  min = PA(0,d); // compute max and min coords
179  max = PA(0,d);
180  for (int i = 1; i < n; i++) {
181  ANNcoord c = PA(i,d);
182  if (c < min) min = c;
183  else if (c > max) max = c;
184  }
185 }
double ANNcoord
Definition: ANN.h:158
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.

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

299 {
300  int l = 0;
301  int r = n-1;
302  for(;;) { // partition pa[0..n-1] about cv
303  while (l < n && PA(l,d) < cv) l++;
304  while (r >= 0 && PA(r,d) >= cv) r--;
305  if (l > r) break;
306  PASWAP(l,r);
307  l++; r--;
308  }
309  br1 = l; // now: pa[0..br1-1] < cv <= pa[br1..n-1]
310  r = n-1;
311  for(;;) { // partition pa[br1..n-1] about cv
312  while (l < n && PA(l,d) <= cv) l++;
313  while (r >= br1 && PA(r,d) > cv) r--;
314  if (l > r) break;
315  PASWAP(l,r);
316  l++; r--;
317  }
318  br2 = l; // now: pa[br1..br2-1] == cv < pa[br2..n-1]
319 }
int annSplitBalance ( ANNpointArray  pa,
ANNidxArray  pidx,
int  n,
int  d,
ANNcoord  cv 
)

Definition at line 360 of file kd_util.cpp.

Referenced by fair_split(), and sl_fair_split().

366 {
367  int n_lo = 0;
368  for(int i = 0; i < n; i++) { // count number less than cv
369  if (PA(i,d) < cv) n_lo++;
370  }
371  return n_lo - n/2;
372 }
ANNcoord annSpread ( ANNpointArray  pa,
ANNidxArray  pidx,
int  n,
int  d 
)

Definition at line 154 of file kd_util.cpp.

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

159 {
160  ANNcoord min = PA(0,d); // compute max and min coords
161  ANNcoord max = PA(0,d);
162  for (int i = 1; i < n; i++) {
163  ANNcoord c = PA(i,d);
164  if (c < min) min = c;
165  else if (c > max) max = c;
166  }
167  return (max - min); // total spread is difference
168 }
double ANNcoord
Definition: ANN.h:158

Generated on Tue Jun 5 2018 19:48:56 for queso-0.57.1 by  doxygen 1.8.5