Method FindClosestNPoints

Common/DataModel/vtkKdTree.cxx:2511–2675

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

//------------------------------------------------------------------------------
void vtkKdTree::FindClosestNPoints(int N, const double x[3], vtkIdList* result)
{
  result->Reset();
  if (N <= 0)
  {
    return;
  }
  if (!this->LocatorPoints)
  {
    vtkErrorMacro(<< "vtkKdTree::FindClosestNPoints - must build locator first");
    return;
  }

  int numTotalPoints = this->Top->GetNumberOfPoints();
  if (numTotalPoints < N)
  {
    vtkWarningMacro("Number of requested points is greater than total number of points in KdTree");
    N = numTotalPoints;
  }
  result->SetNumberOfIds(N);

  // now we want to go about finding a region that contains at least N points
  // but not many more -- hopefully the region contains X as well but we
  // can't depend on that
  vtkKdNode* node = this->Top;
  vtkKdNode* startingNode = nullptr;
  if (!node->ContainsPoint(x[0], x[1], x[2], 0))
  {
    // point is not in the region
    int numPoints = node->GetNumberOfPoints();
    vtkKdNode* prevNode = node;
    while (node->GetLeft() && numPoints > N)
    {
      prevNode = node;
      double leftDist2 = node->GetLeft()->GetDistance2ToBoundary(x[0], x[1], x[2], 1);
      double rightDist2 = node->GetRight()->GetDistance2ToBoundary(x[0], x[1], x[2], 1);
      if (leftDist2 < rightDist2)
      {
        node = node->GetLeft();
      }
      else
      {
        node = node->GetRight();
      }
      numPoints = node->GetNumberOfPoints();
    }
    if (numPoints < N)
    {
      startingNode = prevNode;
    }
    else
    {
      startingNode = node;
    }
  }
  else
  {
    int numPoints = node->GetNumberOfPoints();