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
43VTK_ABI_NAMESPACE_BEGIN
44class vtkCellArray;
45class vtkIdList;
46class vtkNeighborPoints;
47class vtkPoints;
48
49class VTKCOMMONDATAMODEL_EXPORT vtkPointLocator : public vtkIncrementalPointLocator
50{
51public:
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
239protected:
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
292private:
293 vtkPointLocator(const vtkPointLocator&) = delete;
294 void operator=(const vtkPointLocator&) = delete;
295};
296
297VTK_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
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 ...
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.
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
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)
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
int vtkIdType
Definition vtkType.h:315
#define VTK_INT_MAX
Definition vtkType.h:144