vtkPointLocator.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkPointLocator_h
#define vtkPointLocator_h

#include "vtkCommonDataModelModule.h" // For export macro
#include "vtkIncrementalPointLocator.h"
#include "vtkMathUtilities.h" // for SafeCastFromDouble

#include <algorithm> // for std::min/std::max

VTK_ABI_NAMESPACE_BEGIN
class vtkCellArray;
class vtkIdList;
class vtkNeighborPoints;
class vtkPoints;

class VTKCOMMONDATAMODEL_EXPORT vtkPointLocator : public vtkIncrementalPointLocator
{
public:
  static vtkPointLocator* New();


  vtkTypeMacro(vtkPointLocator, vtkIncrementalPointLocator);
  void PrintSelf(ostream& os, vtkIndent indent) override;


  vtkSetVector3Macro(Divisions, int);
  vtkGetVectorMacro(Divisions, int, 3);


  vtkSetClampMacro(NumberOfPointsPerBucket, int, 1, VTK_INT_MAX);
  vtkGetMacro(NumberOfPointsPerBucket, int);

  // Reuse any superclass signatures that we don't override.
  using vtkAbstractPointLocator::FindClosestPoint;

  vtkIdType FindClosestPoint(const double x[3]) override;


  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
  virtual vtkIdType FindClosestPointWithinRadius(
    double radius, const double x[3], double inputDataLength, double& dist2);

  int InitPointInsertion(vtkPoints* newPts, const double bounds[6]) override;

  int InitPointInsertion(vtkPoints* newPts, const double bounds[6], vtkIdType estNumPts) override;

  void InsertPoint(vtkIdType ptId, const double x[3]) override;

  vtkIdType InsertNextPoint(const double x[3]) override;


  vtkIdType IsInsertedPoint(double x, double y, double z) override
  {
    double xyz[3];
    xyz[0] = x;
    xyz[1] = y;
    xyz[2] = z;
    return this->IsInsertedPoint(xyz);
  }
  vtkIdType IsInsertedPoint(const double x[3]) override;

  int InsertUniquePoint(const double x[3], vtkIdType& ptId) override;

  vtkIdType FindClosestInsertedPoint(const double x[3]) override;

  void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;


  virtual void FindDistributedPoints(int N, const double x[3], vtkIdList* result, int M);
  virtual void FindDistributedPoints(int N, double x, double y, double z, vtkIdList* result, int M);

  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;

  virtual vtkIdList* GetPointsInBucket(const double x[3], int ijk[3]);


  vtkGetObjectMacro(Points, vtkPoints);


  void Initialize() override;
  void FreeSearchStructure() override;
  void BuildLocator() override;
  void ForceBuildLocator() override;
  void GenerateRepresentation(int level, vtkPolyData* pd) override;

protected:
  vtkPointLocator();
  ~vtkPointLocator() override;

  void BuildLocatorInternal() override;

  // place points in appropriate buckets
  void GetBucketNeighbors(
    vtkNeighborPoints* buckets, const int ijk[3], const int ndivs[3], int level);
  void GetOverlappingBuckets(
    vtkNeighborPoints* buckets, const double x[3], const int ijk[3], double dist, int level);
  void GetOverlappingBuckets(vtkNeighborPoints* buckets, const double x[3], double dist,
    int prevMinLevel[3], int prevMaxLevel[3]);
  void GenerateFace(int face, int i, int j, int k, vtkPoints* pts, vtkCellArray* polys);
  double Distance2ToBucket(const double x[3], const int nei[3]);
  double Distance2ToBounds(const double x[3], const double bounds[6]);

  vtkPoints* Points;           // Used for merging points
  int Divisions[3];            // Number of sub-divisions in x-y-z directions
  int NumberOfPointsPerBucket; // Used with previous boolean to control subdivide
  vtkIdList** HashTable;       // lists of point ids in buckets
  double H[3];                 // width of each bucket in x-y-z directions

  double InsertionTol2;
  vtkIdType InsertionPointId;
  double InsertionLevel;

  // These are inlined methods and data members for performance reasons
  double HX, HY, HZ;
  double FX, FY, FZ, BX, BY, BZ;
  vtkIdType XD, YD, ZD, SliceSize;

  void GetBucketIndices(const double* x, int ijk[3]) const
  {
    // Compute point index. SafeCastFromDouble clamps to the integer type limits
    // (mapping NaN to 0) so casting a coordinate far outside the locator bounds
    // (e.g. VTK_DOUBLE_MAX) is not undefined behavior. Make sure it then lies
    // within the range of the locator.
    vtkIdType tmp0 = vtkMathUtilities::SafeCastFromDouble<vtkIdType>((x[0] - this->BX) * this->FX);
    vtkIdType tmp1 = vtkMathUtilities::SafeCastFromDouble<vtkIdType>((x[1] - this->BY) * this->FY);
    vtkIdType tmp2 = vtkMathUtilities::SafeCastFromDouble<vtkIdType>((x[2] - this->BZ) * this->FZ);

    ijk[0] = std::min(std::max<vtkIdType>(tmp0, 0), this->XD - 1);
    ijk[1] = std::min(std::max<vtkIdType>(tmp1, 0), this->YD - 1);
    ijk[2] = std::min(std::max<vtkIdType>(tmp2, 0), this->ZD - 1);
  }

  vtkIdType GetBucketIndex(const double* x) const
  {
    int ijk[3];
    this->GetBucketIndices(x, ijk);
    return ijk[0] + ijk[1] * this->XD + ijk[2] * this->SliceSize;
  }

  void ComputePerformanceFactors();

private:
  vtkPointLocator(const vtkPointLocator&) = delete;
  void operator=(const vtkPointLocator&) = delete;
};

VTK_ABI_NAMESPACE_END
#endif