Method Select

Filters/Parallel/vtkPKdTree.cxx:964–1044

  }
}
int vtkPKdTree::Select(int dim, int L, int R)
{
  int K = ((R + L) / 2) + 1;

  this->_select(L, R, K, dim);

  if (K == L)
    return K;

  // The global array is now re-ordered, partitioned around X[K].
  // (In particular, for all i, i<K, X[i] <= X[K] and for all i,
  // i > K, X[i] >= X[K].)
  // However the value at X[K] may occur more than once, and by
  // construction of the reordered array, there is a J <= K such that
  // for all i < J, X[i] < X[K] and for all J <= i < K X[i] = X[K].
  //
  // We want to roll K back to this value J, so that all points are
  // unambiguously assigned to one region or the other.

  int hasK = this->WhoHas(K);
  int hasKrank = this->SubGroup->getLocalRank(hasK);

  int hasKleft = this->WhoHas(K - 1);
  int hasKleftrank = this->SubGroup->getLocalRank(hasKleft);

  float Kval;
  float Kleftval;
  float* pt;

  if (hasK == this->MyId)
  {
    pt = this->GetLocalVal(K) + dim;
    Kval = *pt;
  }

  this->SubGroup->Broadcast(&Kval, 1, hasKrank);

  if (hasKleft == this->MyId)
  {
    pt = this->GetLocalVal(K - 1) + dim;
    Kleftval = *pt;
  }

  this->SubGroup->Broadcast(&Kleftval, 1, hasKleftrank);

  if (Kleftval != Kval)
    return K;

  int firstKval = this->TotalNumCells; // greater than any valid index

  if ((this->MyId <= hasKleft) && (this->NumCells[this->MyId] > 0))
  {
    int start = this->EndVal[this->MyId];
    start = std::min(start, K - 1);

    pt = this->GetLocalVal(start) + dim;

    if (*pt == Kval)