Method FindNPointsInAnnulus

Common/DataModel/vtkStaticPointLocator2D.cxx:862–957

// of the circles.
template <typename TIds>
double BucketList2D<TIds>::FindNPointsInAnnulus(int N, const double x[3],
  vtkDist2TupleArray& results, double minR2, bool sort, vtkDoubleArray* circles)
{
  // Clear out any previous results
  results.clear();

  // Find the bucket the point is in. This is the center of the request
  // footprint.
  int center[2];
  this->GetBucketIndices(x, center);

  // Traverse and gather points in the bucket/bins contained in the annulus
  // request. We hold the information in the results vector.
  double minR = sqrt(minR2);
  double maxR = 0, maxR2 = 0;

  // Determine absolue limits of iteration (based on possible number of points).
  vtkIdType numPts = this->DataSet->GetNumberOfPoints();
  N = (numPts < N ? numPts : N);

  // Gather N points if possible and determine maxR2. Make sure all points
  // within maxR2 have been found. We use a annulus iterator to grow a
  // "rectangular" annulus from the center bin. Skip over bins inside the
  // inner radius minR2. The bin index is updated during iteration,  binIdx<0
  // is returned when the iteration is exhausted.
  vtkIdType binIdx;
  int currentLevel = (minR <= 0 ? 0 : static_cast<int>(std::floor(minR / (2.0 * this->BinRadius))));
  AnnulusIterator<TIds> aiter(
    this->DataSet, this, this->Divisions, this->BinRadius, circles, x, center);

  // Loop across levels, gathering points as we go. This will determine the maxR2. It also
  // carves out some inner levels (based on current level) that do not have to be revisited.
  while (static_cast<int>(results.size()) < N && currentLevel < this->MaxLevel)
  {
    int i, j;
    binIdx = aiter.Initialize(currentLevel, i, j);
    // Basically iterating over a "rectangular" footprint defined from
    // the current level.
    while (binIdx >= 0)
    {
      maxR2 = aiter.GatherPoints(i, j, binIdx, currentLevel, N, minR2, maxR2, results);
      binIdx = aiter.NextBin(i, j);
    }
    ++currentLevel;
  }
  // Reset the level to the last successfully processed
  int level = currentLevel - 1;

  // We have determined maxR2 and ~N points in the request annulus
  // (minR2 < p_d2 <= maxR2). Now gather any other remaining points
  // within the request. It's typical that the number of points
  // returned is >N.
  maxR = sqrt(maxR2);

  // Determine the range of indices in each direction based on radius maxR.
  // This block of bins is processed to gather any additional points with
  // radius <=maxR2.
  double xMin[2], xMax[2];