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
46 #ifndef vtkPointLocator_h
47 #define vtkPointLocator_h
48 
49 #include "vtkCommonDataModelModule.h" // For export macro
51 
52 VTK_ABI_NAMESPACE_BEGIN
53 class vtkCellArray;
54 class vtkIdList;
55 class vtkNeighborPoints;
56 class vtkPoints;
57 
58 class VTKCOMMONDATAMODEL_EXPORT vtkPointLocator : public vtkIncrementalPointLocator
59 {
60 public:
65  static vtkPointLocator* New();
66 
68 
72  void PrintSelf(ostream& os, vtkIndent indent) override;
74 
76 
79  vtkSetVector3Macro(Divisions, int);
80  vtkGetVectorMacro(Divisions, int, 3);
82 
84 
87  vtkSetClampMacro(NumberOfPointsPerBucket, int, 1, VTK_INT_MAX);
88  vtkGetMacro(NumberOfPointsPerBucket, int);
90 
91  // Re-use any superclass signatures that we don't override.
93 
100  vtkIdType FindClosestPoint(const double x[3]) override;
101 
103 
110  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
112  double radius, const double x[3], double inputDataLength, double& dist2);
114 
121  int InitPointInsertion(vtkPoints* newPts, const double bounds[6]) override;
122 
129  int InitPointInsertion(vtkPoints* newPts, const double bounds[6], vtkIdType estNumPts) override;
130 
140  void InsertPoint(vtkIdType ptId, const double x[3]) override;
141 
152  vtkIdType InsertNextPoint(const double x[3]) override;
153 
155 
160  vtkIdType IsInsertedPoint(double x, double y, double z) override
161  {
162  double xyz[3];
163  xyz[0] = x;
164  xyz[1] = y;
165  xyz[2] = z;
166  return this->IsInsertedPoint(xyz);
167  };
168  vtkIdType IsInsertedPoint(const double x[3]) override;
170 
180  int InsertUniquePoint(const double x[3], vtkIdType& ptId) override;
181 
189  vtkIdType FindClosestInsertedPoint(const double x[3]) override;
190 
199  void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
200 
202 
209  virtual void FindDistributedPoints(int N, const double x[3], vtkIdList* result, int M);
210  virtual void FindDistributedPoints(int N, double x, double y, double z, vtkIdList* result, int M);
212 
219  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
220 
227  virtual vtkIdList* GetPointsInBucket(const double x[3], int ijk[3]);
228 
230 
233  vtkGetObjectMacro(Points, vtkPoints);
235 
237 
241  void Initialize() override;
242  void FreeSearchStructure() override;
243  void BuildLocator() override;
244  void ForceBuildLocator() override;
245  void GenerateRepresentation(int level, vtkPolyData* pd) override;
247 
248 protected:
250  ~vtkPointLocator() override;
251 
252  void BuildLocatorInternal() override;
253 
254  // place points in appropriate buckets
256  vtkNeighborPoints* buckets, const int ijk[3], const int ndivs[3], int level);
258  vtkNeighborPoints* buckets, const double x[3], const int ijk[3], double dist, int level);
259  void GetOverlappingBuckets(vtkNeighborPoints* buckets, const double x[3], double dist,
260  int prevMinLevel[3], int prevMaxLevel[3]);
261  void GenerateFace(int face, int i, int j, int k, vtkPoints* pts, vtkCellArray* polys);
262  double Distance2ToBucket(const double x[3], const int nei[3]);
263  double Distance2ToBounds(const double x[3], const double bounds[6]);
264 
265  vtkPoints* Points; // Used for merging points
266  int Divisions[3]; // Number of sub-divisions in x-y-z directions
267  int NumberOfPointsPerBucket; // Used with previous boolean to control subdivide
268  vtkIdList** HashTable; // lists of point ids in buckets
269  double H[3]; // width of each bucket in x-y-z directions
270 
274 
275  // These are inlined methods and data members for performance reasons
276  double HX, HY, HZ;
277  double FX, FY, FZ, BX, BY, BZ;
278  vtkIdType XD, YD, ZD, SliceSize;
279 
280  void GetBucketIndices(const double* x, int ijk[3]) const
281  {
282  // Compute point index. Make sure it lies within range of locator.
283  vtkIdType tmp0 = static_cast<vtkIdType>(((x[0] - this->BX) * this->FX));
284  vtkIdType tmp1 = static_cast<vtkIdType>(((x[1] - this->BY) * this->FY));
285  vtkIdType tmp2 = static_cast<vtkIdType>(((x[2] - this->BZ) * this->FZ));
286 
287  ijk[0] = tmp0 < 0 ? 0 : (tmp0 >= this->XD ? this->XD - 1 : tmp0);
288  ijk[1] = tmp1 < 0 ? 0 : (tmp1 >= this->YD ? this->YD - 1 : tmp1);
289  ijk[2] = tmp2 < 0 ? 0 : (tmp2 >= this->ZD ? this->ZD - 1 : tmp2);
290  }
291 
292  vtkIdType GetBucketIndex(const double* x) const
293  {
294  int ijk[3];
295  this->GetBucketIndices(x, ijk);
296  return ijk[0] + ijk[1] * this->XD + ijk[2] * this->SliceSize;
297  }
298 
300 
301 private:
302  vtkPointLocator(const vtkPointLocator&) = delete;
303  void operator=(const vtkPointLocator&) = delete;
304 };
305 
306 VTK_ABI_NAMESPACE_END
307 #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:185
list of point or cell ids
Definition: vtkIdList.h:32
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:38
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:38
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:89
@ level
Definition: vtkX3D.h:395
@ radius
Definition: vtkX3D.h:252
int vtkIdType
Definition: vtkType.h:315
#define VTK_INT_MAX
Definition: vtkType.h:144