Method Select

Common/DataModel/vtkKdTree.cxx:1410–1459

------------------------------------------------------------------------------

//------------------------------------------------------------------------------
int vtkKdTree::Select(int dim, float* c1, int* ids, int nvals, double& coord)
{
  int left = 0;
  int mid = nvals / 2;
  int right = nvals - 1;

  vtkKdTree::Select_(dim, c1, ids, left, right, mid);

  // We need to be careful in the case where the "mid"
  // value is repeated several times in the array.  We
  // want to roll the dividing index (mid) back to the
  // first occurrence in the array, so that there is no
  // ambiguity about which spatial region a given point
  // belongs in.
  //
  // The array has been rearranged (in Select_) like this:
  //
  // All values c1[n], left <= n < mid, satisfy c1[n] <= c1[mid]
  // All values c1[n], mid < n <= right, satisfy c1[n] >= c1[mid]
  //
  // In addition, by careful construction, there is a J <= mid
  // such that
  //
  // All values c1[n], n < J, satisfy c1[n] < c1[mid] STRICTLY
  // All values c1[n], J <= n <= mid, satisfy c1[n] = c1[mid]
  // All values c1[n], mid < n <= right , satisfy c1[n] >= c1[mid]
  //
  // We need to roll back the "mid" value to the "J".  This
  // means our spatial regions are less balanced, but there
  // is no ambiguity regarding which region a point belongs in.

  int midValIndex = mid * 3 + dim;

  while ((mid > left) && (c1[midValIndex - 3] == c1[midValIndex]))
  {
    mid--;
    midValIndex -= 3;
  }

  if (mid == left)
  {
    return mid; // failed to divide region
  }

  float leftMax = vtkKdTree::FindMaxLeftHalf(dim, c1, mid);

  coord = (static_cast<double>(c1[midValIndex]) + static_cast<double>(leftMax)) / 2.0;

  return mid;
}

//------------------------------------------------------------------------------
float vtkKdTree::FindMaxLeftHalf(int dim, float* c1, int K)