VTK  9.1.0
vtkPointLocator.h
Go to the documentation of this file.
1/*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkPointLocator.h
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14=========================================================================*/
39#ifndef vtkPointLocator_h
40#define vtkPointLocator_h
41
42#include "vtkCommonDataModelModule.h" // For export macro
44
45class vtkCellArray;
46class vtkIdList;
47class vtkNeighborPoints;
48class vtkPoints;
49
50class VTKCOMMONDATAMODEL_EXPORT vtkPointLocator : public vtkIncrementalPointLocator
51{
52public:
58
60
64 void PrintSelf(ostream& os, vtkIndent indent) override;
66
68
71 vtkSetVector3Macro(Divisions, int);
72 vtkGetVectorMacro(Divisions, int, 3);
74
76
79 vtkSetClampMacro(NumberOfPointsPerBucket, int, 1, VTK_INT_MAX);
80 vtkGetMacro(NumberOfPointsPerBucket, int);
82
83 // Re-use any superclass signatures that we don't override.
85
92 vtkIdType FindClosestPoint(const double x[3]) override;
93
95
102 vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
104 double radius, const double x[3], double inputDataLength, double& dist2);
106
113 int InitPointInsertion(vtkPoints* newPts, const double bounds[6]) override;
114
121 int InitPointInsertion(vtkPoints* newPts, const double bounds[6], vtkIdType estNumPts) override;
122
132 void InsertPoint(vtkIdType ptId, const double x[3]) override;
133
144 vtkIdType InsertNextPoint(const double x[3]) override;
145
147
152 vtkIdType IsInsertedPoint(double x, double y, double z) override
153 {
154 double xyz[3];
155 xyz[0] = x;
156 xyz[1] = y;
157 xyz[2] = z;
158 return this->IsInsertedPoint(xyz);
159 };
160 vtkIdType IsInsertedPoint(const double x[3]) override;
162
172 int InsertUniquePoint(const double x[3], vtkIdType& ptId) override;
173
181 vtkIdType FindClosestInsertedPoint(const double x[3]) override;
182
191 void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
192
194
201 virtual void FindDistributedPoints(int N, const double x[3], vtkIdList* result, int M);
202 virtual void FindDistributedPoints(int N, double x, double y, double z, vtkIdList* result, int M);
204
211 void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
212
219 virtual vtkIdList* GetPointsInBucket(const double x[3], int ijk[3]);
220
222
225 vtkGetObjectMacro(Points, vtkPoints);
227
229
233 void Initialize() override;
234 void FreeSearchStructure() override;
235 void BuildLocator() override;
236 void GenerateRepresentation(int level, vtkPolyData* pd) override;
238
239protected:
242
243 // place points in appropriate buckets
245 vtkNeighborPoints* buckets, const int ijk[3], const int ndivs[3], int level);
247 vtkNeighborPoints* buckets, const double x[3], const int ijk[3], double dist, int level);
248 void GetOverlappingBuckets(vtkNeighborPoints* buckets, const double x[3], double dist,
249 int prevMinLevel[3], int prevMaxLevel[3]);
250 void GenerateFace(int face, int i, int j, int k, vtkPoints* pts, vtkCellArray* polys);
251 double Distance2ToBucket(const double x[3], const int nei[3]);
252 double Distance2ToBounds(const double x[3], const double bounds[6]);
253
254 vtkPoints* Points; // Used for merging points
255 int Divisions[3]; // Number of sub-divisions in x-y-z directions
256 int NumberOfPointsPerBucket; // Used with previous boolean to control subdivide
257 vtkIdList** HashTable; // lists of point ids in buckets
258 double H[3]; // width of each bucket in x-y-z directions
259
263
264 // These are inlined methods and data members for performance reasons
265 double HX, HY, HZ;
266 double FX, FY, FZ, BX, BY, BZ;
267 vtkIdType XD, YD, ZD, SliceSize;
268
269 void GetBucketIndices(const double* x, int ijk[3]) const
270 {
271 // Compute point index. Make sure it lies within range of locator.
272 vtkIdType tmp0 = static_cast<vtkIdType>(((x[0] - this->BX) * this->FX));
273 vtkIdType tmp1 = static_cast<vtkIdType>(((x[1] - this->BY) * this->FY));
274 vtkIdType tmp2 = static_cast<vtkIdType>(((x[2] - this->BZ) * this->FZ));
275
276 ijk[0] = tmp0 < 0 ? 0 : (tmp0 >= this->XD ? this->XD - 1 : tmp0);
277 ijk[1] = tmp1 < 0 ? 0 : (tmp1 >= this->YD ? this->YD - 1 : tmp1);
278 ijk[2] = tmp2 < 0 ? 0 : (tmp2 >= this->ZD ? this->ZD - 1 : tmp2);
279 }
280
281 vtkIdType GetBucketIndex(const double* x) const
282 {
283 int ijk[3];
284 this->GetBucketIndices(x, ijk);
285 return ijk[0] + ijk[1] * this->XD + ijk[2] * this->SliceSize;
286 }
287
289
290private:
291 vtkPointLocator(const vtkPointLocator&) = delete;
292 void operator=(const vtkPointLocator&) = delete;
293};
294
295#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:181
list of point or cell ids
Definition: vtkIdList.h:31
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:34
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 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:34
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
@ level
Definition: vtkX3D.h:401
@ radius
Definition: vtkX3D.h:258
int vtkIdType
Definition: vtkType.h:332
#define VTK_INT_MAX
Definition: vtkType.h:155