VTK  9.3.1
vtkPointLocator.h
Go to the documentation of this file.
1 // SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
2 // SPDX-License-Identifier: BSD-3-Clause
37 #ifndef vtkPointLocator_h
38 #define vtkPointLocator_h
39 
40 #include "vtkCommonDataModelModule.h" // For export macro
42 
43 VTK_ABI_NAMESPACE_BEGIN
44 class vtkCellArray;
45 class vtkIdList;
46 class vtkNeighborPoints;
47 class vtkPoints;
48 
49 class VTKCOMMONDATAMODEL_EXPORT vtkPointLocator : public vtkIncrementalPointLocator
50 {
51 public:
56  static vtkPointLocator* New();
57 
59 
63  void PrintSelf(ostream& os, vtkIndent indent) override;
65 
67 
70  vtkSetVector3Macro(Divisions, int);
71  vtkGetVectorMacro(Divisions, int, 3);
73 
75 
78  vtkSetClampMacro(NumberOfPointsPerBucket, int, 1, VTK_INT_MAX);
79  vtkGetMacro(NumberOfPointsPerBucket, int);
81 
82  // Re-use any superclass signatures that we don't override.
84 
91  vtkIdType FindClosestPoint(const double x[3]) override;
92 
94 
101  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
103  double radius, const double x[3], double inputDataLength, double& dist2);
105 
112  int InitPointInsertion(vtkPoints* newPts, const double bounds[6]) override;
113 
120  int InitPointInsertion(vtkPoints* newPts, const double bounds[6], vtkIdType estNumPts) override;
121 
131  void InsertPoint(vtkIdType ptId, const double x[3]) override;
132 
143  vtkIdType InsertNextPoint(const double x[3]) override;
144 
146 
151  vtkIdType IsInsertedPoint(double x, double y, double z) override
152  {
153  double xyz[3];
154  xyz[0] = x;
155  xyz[1] = y;
156  xyz[2] = z;
157  return this->IsInsertedPoint(xyz);
158  };
159  vtkIdType IsInsertedPoint(const double x[3]) override;
161 
171  int InsertUniquePoint(const double x[3], vtkIdType& ptId) override;
172 
180  vtkIdType FindClosestInsertedPoint(const double x[3]) override;
181 
190  void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
191 
193 
200  virtual void FindDistributedPoints(int N, const double x[3], vtkIdList* result, int M);
201  virtual void FindDistributedPoints(int N, double x, double y, double z, vtkIdList* result, int M);
203 
210  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
211 
218  virtual vtkIdList* GetPointsInBucket(const double x[3], int ijk[3]);
219 
221 
224  vtkGetObjectMacro(Points, vtkPoints);
226 
228 
232  void Initialize() override;
233  void FreeSearchStructure() override;
234  void BuildLocator() override;
235  void ForceBuildLocator() override;
236  void GenerateRepresentation(int level, vtkPolyData* pd) override;
238 
239 protected:
240  vtkPointLocator();
241  ~vtkPointLocator() override;
242 
243  void BuildLocatorInternal() override;
244 
245  // place points in appropriate buckets
246  void GetBucketNeighbors(
247  vtkNeighborPoints* buckets, const int ijk[3], const int ndivs[3], int level);
248  void GetOverlappingBuckets(
249  vtkNeighborPoints* buckets, const double x[3], const int ijk[3], double dist, int level);
250  void GetOverlappingBuckets(vtkNeighborPoints* buckets, const double x[3], double dist,
251  int prevMinLevel[3], int prevMaxLevel[3]);
252  void GenerateFace(int face, int i, int j, int k, vtkPoints* pts, vtkCellArray* polys);
253  double Distance2ToBucket(const double x[3], const int nei[3]);
254  double Distance2ToBounds(const double x[3], const double bounds[6]);
255 
256  vtkPoints* Points; // Used for merging points
257  int Divisions[3]; // Number of sub-divisions in x-y-z directions
258  int NumberOfPointsPerBucket; // Used with previous boolean to control subdivide
259  vtkIdList** HashTable; // lists of point ids in buckets
260  double H[3]; // width of each bucket in x-y-z directions
261 
265 
266  // These are inlined methods and data members for performance reasons
267  double HX, HY, HZ;
268  double FX, FY, FZ, BX, BY, BZ;
269  vtkIdType XD, YD, ZD, SliceSize;
270 
271  void GetBucketIndices(const double* x, int ijk[3]) const
272  {
273  // Compute point index. Make sure it lies within range of locator.
274  vtkIdType tmp0 = static_cast<vtkIdType>(((x[0] - this->BX) * this->FX));
275  vtkIdType tmp1 = static_cast<vtkIdType>(((x[1] - this->BY) * this->FY));
276  vtkIdType tmp2 = static_cast<vtkIdType>(((x[2] - this->BZ) * this->FZ));
277 
278  ijk[0] = tmp0 < 0 ? 0 : (tmp0 >= this->XD ? this->XD - 1 : tmp0);
279  ijk[1] = tmp1 < 0 ? 0 : (tmp1 >= this->YD ? this->YD - 1 : tmp1);
280  ijk[2] = tmp2 < 0 ? 0 : (tmp2 >= this->ZD ? this->ZD - 1 : tmp2);
281  }
282 
283  vtkIdType GetBucketIndex(const double* x) const
284  {
285  int ijk[3];
286  this->GetBucketIndices(x, ijk);
287  return ijk[0] + ijk[1] * this->XD + ijk[2] * this->SliceSize;
288  }
289 
290  void ComputePerformanceFactors();
291 
292 private:
293  vtkPointLocator(const vtkPointLocator&) = delete;
294  void operator=(const vtkPointLocator&) = delete;
295 };
296 
297 VTK_ABI_NAMESPACE_END
298 #endif
vtkIdType GetBucketIndex(const double *x) const
vtkIdType IsInsertedPoint(double x, double y, double z) override
Determine whether point given by x[3] has been inserted into points list.
void GetBucketIndices(const double *x, int ijk[3]) const
virtual void BuildLocator()=0
Build the locator from the input dataset.
virtual vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double &dist2)=0
Given a position x and a radius r, return the id of the point closest to the point in that radius...
quickly locate points in 3-space
virtual int InsertUniquePoint(const double x[3], vtkIdType &ptId)=0
Insert a point unless there has been a duplicate in the search structure.
vtkIdType InsertionPointId
virtual vtkIdType IsInsertedPoint(double x, double y, double z)=0
Determine whether or not a given point has been inserted.
#define VTK_INT_MAX
Definition: vtkType.h:144
vtkIdList ** HashTable
Abstract class in support of both point location and point insertion.
int vtkIdType
Definition: vtkType.h:315
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
virtual int InitPointInsertion(vtkPoints *newPts, const double bounds[6])=0
Initialize the point insertion process.
a simple class to control print indentation
Definition: vtkIndent.h:28
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:192
list of point or cell ids
Definition: vtkIdList.h:22
vtkPoints * Points
virtual void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result)=0
Find all points within a specified radius R of position x.
virtual void FindClosestNPoints(int N, const double x[3], vtkIdList *result)=0
Find the closest N points to a position.
void PrintSelf(ostream &os, vtkIndent indent) override
Standard type and print methods.
object to represent cell connectivity
Definition: vtkCellArray.h:175
virtual vtkIdType InsertNextPoint(const double x[3])=0
Insert a given point and return the point index.
virtual vtkIdType FindClosestInsertedPoint(const double x[3])=0
Given a point x assumed to be covered by the search structure, return the index of the closest point ...
virtual vtkIdType FindClosestPoint(const double x[3])=0
Given a position x, return the id of the point closest to it.
virtual void Initialize()
Initialize locator.
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on...
virtual void InsertPoint(vtkIdType ptId, const double x[3])=0
Insert a given point with a specified point index ptId.
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
represent and manipulate 3D points
Definition: vtkPoints.h:28
virtual void ForceBuildLocator()
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
Definition: vtkLocator.h:156