VTK  9.3.0
vtkIncrementalOctreePointLocator.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
48 #ifndef vtkIncrementalOctreePointLocator_h
49 #define vtkIncrementalOctreePointLocator_h
50 
51 #include "vtkCommonDataModelModule.h" // For export macro
53 
54 VTK_ABI_NAMESPACE_BEGIN
55 class vtkPoints;
56 class vtkIdList;
57 class vtkIntArray;
58 class vtkPolyData;
59 class vtkCellArray;
61 
62 class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
63 {
64 public:
66  void PrintSelf(ostream& os, vtkIndent indent) override;
67 
69 
71 
81  vtkSetMacro(MaxPointsPerLeaf, int);
82  vtkGetMacro(MaxPointsPerLeaf, int);
84 
86 
89  vtkSetMacro(BuildCubicOctree, vtkTypeBool);
90  vtkGetMacro(BuildCubicOctree, vtkTypeBool);
91  vtkBooleanMacro(BuildCubicOctree, vtkTypeBool);
93 
95 
99  vtkGetObjectMacro(LocatorPoints, vtkPoints);
101 
105  void Initialize() override { this->FreeSearchStructure(); }
106 
110  void FreeSearchStructure() override;
111 
115  void GetBounds(double* bounds) override;
116 
120  double* GetBounds() override
121  {
122  this->GetBounds(this->Bounds);
123  return this->Bounds;
124  }
125 
133  vtkGetMacro(NumberOfNodes, int);
134 
142  vtkIdType FindClosestInsertedPoint(const double x[3]) override;
143 
145 
157  void GenerateRepresentation(int level, vtkPolyData* polysData) override;
159  bool (*UserGetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
161 
162  // -------------------------------------------------------------------------
163  // ---------------------------- Point Location ----------------------------
164  // -------------------------------------------------------------------------
165 
171  void BuildLocator() override;
172 
176  void ForceBuildLocator() override;
177 
183  vtkIdType FindClosestPoint(const double x[3]) override;
184 
191  virtual vtkIdType FindClosestPoint(double x, double y, double z);
192 
199  virtual vtkIdType FindClosestPoint(const double x[3], double* miniDist2);
200 
207  virtual vtkIdType FindClosestPoint(double x, double y, double z, double* miniDist2);
208 
217  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
218 
227  vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double& dist2);
228 
235  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
236 
243  void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList* result);
244 
251  void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
252 
253  // -------------------------------------------------------------------------
254  // ---------------------------- Point Insertion ----------------------------
255  // -------------------------------------------------------------------------
256 
266  int InitPointInsertion(vtkPoints* points, const double bounds[6]) override;
267 
278  int InitPointInsertion(vtkPoints* points, const double bounds[6], vtkIdType estSize) override;
279 
285  vtkIdType IsInsertedPoint(const double x[3]) override;
286 
292  vtkIdType IsInsertedPoint(double x, double y, double z) override;
293 
302  int InsertUniquePoint(const double point[3], vtkIdType& pntId) override;
303 
312  void InsertPoint(vtkIdType ptId, const double x[3]) override;
313 
322  vtkIdType InsertNextPoint(const double x[3]) override;
323 
333  void InsertPointWithoutChecking(const double point[3], vtkIdType& pntId, int insert);
334 
335  vtkIncrementalOctreeNode* GetRoot() const { return OctreeRootNode; }
336 
342 
343 protected:
346 
347 private:
348  vtkTypeBool BuildCubicOctree;
349  int MaxPointsPerLeaf;
350  double InsertTolerance2;
351  double OctreeMaxDimSize;
352  double FudgeFactor;
353  vtkPoints* LocatorPoints;
354  vtkIncrementalOctreeNode* OctreeRootNode;
355  int NumberOfNodes;
356 
357  void BuildLocatorInternal() override;
358 
362  static void DeleteAllDescendants(vtkIncrementalOctreeNode* node);
363 
368  static void AddPolys(vtkIncrementalOctreeNode* node, vtkPoints* points, vtkCellArray* polygs,
369  vtkIntArray* nodeIndexes, vtkIdType& cellIndex,
370  bool (*GetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
371 
376  vtkIncrementalOctreeNode* GetLeafContainer(vtkIncrementalOctreeNode* node, const double pnt[3]);
377 
385  vtkIdType FindClosestPointInLeafNode(
386  vtkIncrementalOctreeNode* leafNode, const double point[3], double* dist2);
387 
400  vtkIdType FindClosestPointInSphere(const double point[3], double radius2,
401  vtkIncrementalOctreeNode* maskNode, double* minDist2, const double* refDist2);
402 
403  // -------------------------------------------------------------------------
404  // ---------------------------- Point Location ----------------------------
405  // -------------------------------------------------------------------------
406 
417  vtkIdType FindClosestPointInSphereWithoutTolerance(
418  const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2);
419 
425  void FindPointsWithinSquaredRadius(
426  vtkIncrementalOctreeNode* node, double radius2, const double point[3], vtkIdList* idList);
427 
428  // -------------------------------------------------------------------------
429  // ---------------------------- Point Insertion ----------------------------
430  // -------------------------------------------------------------------------
431 
443  vtkIdType FindClosestPointInSphereWithTolerance(
444  const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2);
445 
455  vtkIdType IsInsertedPoint(const double x[3], vtkIncrementalOctreeNode** leafContainer);
456 
465  vtkIdType IsInsertedPointForZeroTolerance(
466  const double x[3], vtkIncrementalOctreeNode** leafContainer);
467 
477  vtkIdType IsInsertedPointForNonZeroTolerance(
478  const double x[3], vtkIncrementalOctreeNode** leafContainer);
479 
487  vtkIdType FindDuplicatePointInLeafNode(vtkIncrementalOctreeNode* leafNode, const double point[3]);
488 
496  vtkIdType FindDuplicateFloatTypePointInVisitedLeafNode(
497  vtkIncrementalOctreeNode* leafNode, const double point[3]);
498 
506  vtkIdType FindDuplicateDoubleTypePointInVisitedLeafNode(
507  vtkIncrementalOctreeNode* leafNode, const double point[3]);
508 
510  void operator=(const vtkIncrementalOctreePointLocator&) = delete;
511 };
512 VTK_ABI_NAMESPACE_END
513 #endif
virtual double * GetBounds()
Provide an accessor to the bounds.
object to represent cell connectivity
Definition: vtkCellArray.h:185
list of point or cell ids
Definition: vtkIdList.h:32
Octree node constituting incremental octree (in support of both point location and point insertion)
Incremental octree in support of both point location and point insertion.
void GenerateRepresentation(int level, vtkPolyData *polysData, bool(*UserGetBounds)(void *data, vtkIncrementalOctreeNode *node, double *bounds), void *data)
Create a polygonal representation of the octree 'level': for each node on the specified level we gene...
vtkIdType IsInsertedPoint(const double x[3]) override
Determine whether or not a given point has been inserted into the octree.
vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double &dist2) override
Given a point x and a radius, return the id of the closest point within the radius and the associated...
virtual vtkIdType FindClosestPoint(const double x[3], double *miniDist2)
Given a point x, return the id of the closest point and the associated minimum squared distance (via ...
int InitPointInsertion(vtkPoints *points, const double bounds[6]) override
Initialize the point insertion process.
void InsertPoint(vtkIdType ptId, const double x[3]) override
Insert a given point into the octree with a specified point index ptId.
void FindClosestNPoints(int N, const double x[3], vtkIdList *result) override
Find the closest N points to a given point.
double * GetBounds() override
Get the spatial bounding box of the octree.
void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList *result)
Find all points within a squared radius R2 relative to a given point x.
int InsertUniquePoint(const double point[3], vtkIdType &pntId) override
Insert a point to the octree unless there has been a duplicate point.
void Initialize() override
Delete the octree search structure.
void GetBounds(double *bounds) override
Get the spatial bounding box of the octree.
void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result) override
Find all points within a radius R relative to a given point x.
void InsertPointWithoutChecking(const double point[3], vtkIdType &pntId, int insert)
"Insert" a point to the octree without any checking.
vtkIncrementalOctreeNode * GetRoot() const
vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double &dist2)
Given a point x and a squared radius radius2, return the id of the closest point within the radius an...
virtual vtkIdType FindClosestPoint(double x, double y, double z)
Given a point (x, y, z), return the id of the closest point.
static vtkIncrementalOctreePointLocator * New()
vtkIdType InsertNextPoint(const double x[3]) override
Insert a given point into the octree and return the point index.
void PrintSelf(ostream &os, vtkIndent indent) override
Standard type and print methods.
void ForceBuildLocator() override
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
int GetNumberOfPoints()
Get the number of points maintained by the octree.
vtkIdType FindClosestPoint(const double x[3]) override
Given a point x, return the id of the closest point.
void GenerateRepresentation(int level, vtkPolyData *polysData) override
Create a polygonal representation of the octree 'level': for each node on the specified level we gene...
vtkIdType IsInsertedPoint(double x, double y, double z) override
Determine whether or not a given point has been inserted into the octree.
void FreeSearchStructure() override
Delete the octree search structure.
virtual vtkIdType FindClosestPoint(double x, double y, double z, double *miniDist2)
Given a point (x, y, z), return the id of the closest point and the associated minimum squared distan...
int GetNumberOfLevels()
Returns the maximum level of the tree.
vtkIdType FindClosestInsertedPoint(const double x[3]) override
Given a point x assumed to be covered by the octree, return the index of the closest in-octree point ...
int InitPointInsertion(vtkPoints *points, const double bounds[6], vtkIdType estSize) override
Initialize the point insertion process.
void BuildLocator() override
Load points from a dataset to construct an octree for point location.
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
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:44
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:201
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
represent and manipulate 3D points
Definition: vtkPoints.h:38
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:89
void GetBounds(T a, double bds[6])
@ point
Definition: vtkX3D.h:236
@ points
Definition: vtkX3D.h:446
@ level
Definition: vtkX3D.h:395
@ radius
Definition: vtkX3D.h:252
@ data
Definition: vtkX3D.h:315
int vtkTypeBool
Definition: vtkABI.h:64
int vtkIdType
Definition: vtkType.h:315