VTK  9.3.0
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:
241  ~vtkPointLocator() override;
242 
243  void BuildLocatorInternal() override;
244 
245  // place points in appropriate buckets
247  vtkNeighborPoints* buckets, const int ijk[3], const int ndivs[3], int level);
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 
291 
292 private:
293  vtkPointLocator(const vtkPointLocator&) = delete;
294  void operator=(const vtkPointLocator&) = delete;
295 };
296 
297 VTK_ABI_NAMESPACE_END
298 #endif
virtual vtkIdType FindClosestPoint(const double x[3])=0
Given a position x, return the id of the point closest to it.
object to represent cell connectivity
Definition: vtkCellArray.h:176
list of point or cell ids
Definition: vtkIdList.h:23
Abstract class in support of both point location and point insertion.
virtual vtkIdType IsInsertedPoint(double x, double y, double z)=0
Determine whether or not a given point has been inserted.
a simple class to control print indentation
Definition: vtkIndent.h:29
quickly locate points in 3-space
void InsertPoint(vtkIdType ptId, const double x[3]) override
Incrementally insert a point into search structure with a particular index value.
int InitPointInsertion(vtkPoints *newPts, const double bounds[6]) override
Initialize the point insertion process.
vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double &dist2) override
Given a position x and a radius r, return the id of the point closest to the point in that radius.
vtkIdType IsInsertedPoint(double x, double y, double z) override
Determine whether point given by x[3] has been inserted into points list.
void BuildLocator() override
See vtkLocator interface documentation.
void FindClosestNPoints(int N, const double x[3], vtkIdList *result) override
Find the closest N points to a position.
virtual void FindDistributedPoints(int N, double x, double y, double z, vtkIdList *result, int M)
Find the closest points to a position such that each octant of space around the position contains at ...
static vtkPointLocator * New()
Construct with automatic computation of divisions, averaging 25 points per bucket.
void GetBucketIndices(const double *x, int ijk[3]) const
void GetBucketNeighbors(vtkNeighborPoints *buckets, const int ijk[3], const int ndivs[3], int level)
virtual void FindDistributedPoints(int N, const double x[3], vtkIdList *result, int M)
Find the closest points to a position such that each octant of space around the position contains at ...
void FreeSearchStructure() override
See vtkLocator interface documentation.
vtkIdList ** HashTable
virtual vtkIdList * GetPointsInBucket(const double x[3], int ijk[3])
Given a position x, return the list of points in the bucket that contains the point.
void BuildLocatorInternal() override
This function is not pure virtual to maintain backwards compatibility.
void ForceBuildLocator() override
See vtkLocator interface documentation.
void Initialize() override
See vtkLocator interface documentation.
vtkIdType FindClosestPoint(const double x[3]) override
Given a position x, return the id of the point closest to it.
double Distance2ToBucket(const double x[3], const int nei[3])
void PrintSelf(ostream &os, vtkIndent indent) override
Standard methods for type management and printing.
virtual vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double inputDataLength, double &dist2)
Given a position x and a radius r, return the id of the point closest to the point in that radius.
void ComputePerformanceFactors()
vtkIdType IsInsertedPoint(const double x[3]) override
Determine whether point given by x[3] has been inserted into points list.
~vtkPointLocator() override
void GenerateRepresentation(int level, vtkPolyData *pd) override
See vtkLocator interface documentation.
void GenerateFace(int face, int i, int j, int k, vtkPoints *pts, vtkCellArray *polys)
vtkIdType InsertionPointId
void GetOverlappingBuckets(vtkNeighborPoints *buckets, const double x[3], double dist, int prevMinLevel[3], int prevMaxLevel[3])
void GetOverlappingBuckets(vtkNeighborPoints *buckets, const double x[3], const int ijk[3], double dist, int level)
vtkPoints * Points
vtkIdType GetBucketIndex(const double *x) const
vtkIdType InsertNextPoint(const double x[3]) override
Incrementally insert a point into search structure.
int InsertUniquePoint(const double x[3], vtkIdType &ptId) override
Determine whether point given by x[3] has been inserted into points list.
void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result) override
Find all points within a specified radius R of position x.
double Distance2ToBounds(const double x[3], const double bounds[6])
int InitPointInsertion(vtkPoints *newPts, const double bounds[6], vtkIdType estNumPts) override
Initialize the point insertion process.
vtkIdType FindClosestInsertedPoint(const double x[3]) override
Given a position x, return the id of the point closest to it.
represent and manipulate 3D points
Definition: vtkPoints.h:29
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:80
@ level
Definition: vtkX3D.h:395
@ radius
Definition: vtkX3D.h:252
int vtkIdType
Definition: vtkType.h:315
#define VTK_INT_MAX
Definition: vtkType.h:144