Method FindClosestPointWithinRadius

Common/DataModel/vtkStaticCellLocator.cxx:1007–1125

// Return closest point (if any) AND the cell on which this closest point lies
template <typename T>
vtkIdType CellProcessor<T>::FindClosestPointWithinRadius(const double x[3], double radius,
  double closestPoint[3], vtkGenericCell* cell, vtkIdType& closestCellId, int& closestSubId,
  double& minDist2, int& inside)
{
  std::vector<bool> binHasBeenQueued(this->NumBins, false);
  std::vector<double> weights(this->MaxCellSize);
  double pcoords[3], point[3], bds[6], *bounds;
  double distance2ToCellBounds, dist2, binDist2;
  int subId, stat, ijk[3];
  vtkIdType retVal = 0;
  T numIds, j, cellId;

  using node = std::pair<double, vtkIdType>;
  std::priority_queue<node, std::vector<node>, std::greater<>> queue;

  // first get ijk containing point
  vtkIdType binId = this->Binner->GetBinIndex(x);
  queue.emplace(0.0, binId);
  binHasBeenQueued[binId] = true;

  // minimum squared distance to the closest point
  minDist2 = radius * radius;

  // Process the queue of candidate bins until the candidate bins are
  // further away than the current closest point.
  while (!queue.empty())
  {
    auto& top = queue.top();
    binId = top.second;
    binDist2 = top.first;

    // stop if bounding box is further away than current closest point
    if (binDist2 > minDist2)
    {
      break;
    }
    // perform pop after ensuring that the bin is within the bounds
    queue.pop();

    // compute distance to cells in bin, if any
    numIds = this->GetNumberOfIds(binId);
    if (numIds >= 1)
    {
      const CellFragments<T>* cellIds = this->GetIds(binId);

      for (j = 0; j < numIds; j++)
      {
        cellId = cellIds[j].CellId;

        // compute distance to cell bounding box
        bounds = this->CellBounds + 6 * cellId;
        distance2ToCellBounds = Distance2ToBounds(x, bounds);

        // compute distance to cell only if distance to bounding box smaller than minDist2
        if (distance2ToCellBounds < minDist2)
        {
          this->DataSet->GetCell(cellId, cell);