VTK  9.3.20240318
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
58 #ifndef vtkIncrementalOctreePointLocator_h
59 #define vtkIncrementalOctreePointLocator_h
60 
61 #include "vtkCommonDataModelModule.h" // For export macro
63 
64 VTK_ABI_NAMESPACE_BEGIN
65 class vtkPoints;
66 class vtkIdList;
67 class vtkIntArray;
68 class vtkPolyData;
69 class vtkCellArray;
71 
72 class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
73 {
74 public:
76  void PrintSelf(ostream& os, vtkIndent indent) override;
77 
79 
81 
91  vtkSetMacro(MaxPointsPerLeaf, int);
92  vtkGetMacro(MaxPointsPerLeaf, int);
94 
96 
99  vtkSetMacro(BuildCubicOctree, vtkTypeBool);
100  vtkGetMacro(BuildCubicOctree, vtkTypeBool);
101  vtkBooleanMacro(BuildCubicOctree, vtkTypeBool);
103 
105 
109  vtkGetObjectMacro(LocatorPoints, vtkPoints);
111 
115  void Initialize() override { this->FreeSearchStructure(); }
116 
120  void FreeSearchStructure() override;
121 
125  void GetBounds(double* bounds) override;
126 
130  double* GetBounds() override
131  {
132  this->GetBounds(this->Bounds);
133  return this->Bounds;
134  }
135 
143  vtkGetMacro(NumberOfNodes, int);
144 
152  vtkIdType FindClosestInsertedPoint(const double x[3]) override;
153 
155 
167  void GenerateRepresentation(int level, vtkPolyData* polysData) override;
169  bool (*UserGetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
171 
172  // -------------------------------------------------------------------------
173  // ---------------------------- Point Location ----------------------------
174  // -------------------------------------------------------------------------
175 
181  void BuildLocator() override;
182 
186  void ForceBuildLocator() override;
187 
193  vtkIdType FindClosestPoint(const double x[3]) override;
194 
201  virtual vtkIdType FindClosestPoint(double x, double y, double z);
202 
209  virtual vtkIdType FindClosestPoint(const double x[3], double* miniDist2);
210 
217  virtual vtkIdType FindClosestPoint(double x, double y, double z, double* miniDist2);
218 
227  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
228 
237  vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double& dist2);
238 
245  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
246 
253  void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList* result);
254 
261  void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
262 
263  // -------------------------------------------------------------------------
264  // ---------------------------- Point Insertion ----------------------------
265  // -------------------------------------------------------------------------
266 
276  int InitPointInsertion(vtkPoints* points, const double bounds[6]) override;
277 
288  int InitPointInsertion(vtkPoints* points, const double bounds[6], vtkIdType estSize) override;
289 
295  vtkIdType IsInsertedPoint(const double x[3]) override;
296 
302  vtkIdType IsInsertedPoint(double x, double y, double z) override;
303 
312  int InsertUniquePoint(const double point[3], vtkIdType& pntId) override;
313 
322  void InsertPoint(vtkIdType ptId, const double x[3]) override;
323 
332  vtkIdType InsertNextPoint(const double x[3]) override;
333 
343  void InsertPointWithoutChecking(const double point[3], vtkIdType& pntId, int insert);
344 
345  vtkIncrementalOctreeNode* GetRoot() const { return OctreeRootNode; }
346 
352 
353 protected:
356 
357 private:
358  vtkTypeBool BuildCubicOctree;
359  int MaxPointsPerLeaf;
360  double InsertTolerance2;
361  double OctreeMaxDimSize;
362  double FudgeFactor;
363  vtkPoints* LocatorPoints;
364  vtkIncrementalOctreeNode* OctreeRootNode;
365  int NumberOfNodes;
366 
367  void BuildLocatorInternal() override;
368 
372  static void DeleteAllDescendants(vtkIncrementalOctreeNode* node);
373 
378  static void AddPolys(vtkIncrementalOctreeNode* node, vtkPoints* points, vtkCellArray* polygs,
379  vtkIntArray* nodeIndexes, vtkIdType& cellIndex,
380  bool (*GetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
381 
386  vtkIncrementalOctreeNode* GetLeafContainer(vtkIncrementalOctreeNode* node, const double pnt[3]);
387 
395  vtkIdType FindClosestPointInLeafNode(
396  vtkIncrementalOctreeNode* leafNode, const double point[3], double* dist2);
397 
410  vtkIdType FindClosestPointInSphere(const double point[3], double radius2,
411  vtkIncrementalOctreeNode* maskNode, double* minDist2, const double* refDist2);
412 
413  // -------------------------------------------------------------------------
414  // ---------------------------- Point Location ----------------------------
415  // -------------------------------------------------------------------------
416 
427  vtkIdType FindClosestPointInSphereWithoutTolerance(
428  const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2);
429 
435  void FindPointsWithinSquaredRadius(
436  vtkIncrementalOctreeNode* node, double radius2, const double point[3], vtkIdList* idList);
437 
438  // -------------------------------------------------------------------------
439  // ---------------------------- Point Insertion ----------------------------
440  // -------------------------------------------------------------------------
441 
453  vtkIdType FindClosestPointInSphereWithTolerance(
454  const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2);
455 
465  vtkIdType IsInsertedPoint(const double x[3], vtkIncrementalOctreeNode** leafContainer);
466 
475  vtkIdType IsInsertedPointForZeroTolerance(
476  const double x[3], vtkIncrementalOctreeNode** leafContainer);
477 
487  vtkIdType IsInsertedPointForNonZeroTolerance(
488  const double x[3], vtkIncrementalOctreeNode** leafContainer);
489 
497  vtkIdType FindDuplicatePointInLeafNode(vtkIncrementalOctreeNode* leafNode, const double point[3]);
498 
506  vtkIdType FindDuplicateFloatTypePointInVisitedLeafNode(
507  vtkIncrementalOctreeNode* leafNode, const double point[3]);
508 
516  vtkIdType FindDuplicateDoubleTypePointInVisitedLeafNode(
517  vtkIncrementalOctreeNode* leafNode, const double point[3]);
518 
520  void operator=(const vtkIncrementalOctreePointLocator&) = delete;
521 };
522 VTK_ABI_NAMESPACE_END
523 #endif
virtual double * GetBounds()
Provide an accessor to the bounds.
object to represent cell connectivity
Definition: vtkCellArray.h:285
list of point or cell ids
Definition: vtkIdList.h:132
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:108
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:144
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:211
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
represent and manipulate 3D points
Definition: vtkPoints.h:138
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:180
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