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
39 #ifndef vtkIncrementalOctreePointLocator_h
40 #define vtkIncrementalOctreePointLocator_h
41 
42 #include "vtkCommonDataModelModule.h" // For export macro
44 
45 VTK_ABI_NAMESPACE_BEGIN
46 class vtkPoints;
47 class vtkIdList;
48 class vtkIntArray;
49 class vtkPolyData;
50 class vtkCellArray;
52 
53 class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
54 {
55 public:
57  void PrintSelf(ostream& os, vtkIndent indent) override;
58 
60 
62 
72  vtkSetMacro(MaxPointsPerLeaf, int);
73  vtkGetMacro(MaxPointsPerLeaf, int);
75 
77 
80  vtkSetMacro(BuildCubicOctree, vtkTypeBool);
81  vtkGetMacro(BuildCubicOctree, vtkTypeBool);
82  vtkBooleanMacro(BuildCubicOctree, vtkTypeBool);
84 
86 
90  vtkGetObjectMacro(LocatorPoints, vtkPoints);
92 
96  void Initialize() override { this->FreeSearchStructure(); }
97 
101  void FreeSearchStructure() override;
102 
106  void GetBounds(double* bounds) override;
107 
111  double* GetBounds() override
112  {
113  this->GetBounds(this->Bounds);
114  return this->Bounds;
115  }
116 
124  vtkGetMacro(NumberOfNodes, int);
125 
133  vtkIdType FindClosestInsertedPoint(const double x[3]) override;
134 
136 
148  void GenerateRepresentation(int level, vtkPolyData* polysData) override;
150  bool (*UserGetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
152 
153  // -------------------------------------------------------------------------
154  // ---------------------------- Point Location ----------------------------
155  // -------------------------------------------------------------------------
156 
162  void BuildLocator() override;
163 
167  void ForceBuildLocator() override;
168 
174  vtkIdType FindClosestPoint(const double x[3]) override;
175 
182  virtual vtkIdType FindClosestPoint(double x, double y, double z);
183 
190  virtual vtkIdType FindClosestPoint(const double x[3], double* miniDist2);
191 
198  virtual vtkIdType FindClosestPoint(double x, double y, double z, double* miniDist2);
199 
208  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
209 
218  vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double& dist2);
219 
226  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
227 
234  void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList* result);
235 
242  void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
243 
244  // -------------------------------------------------------------------------
245  // ---------------------------- Point Insertion ----------------------------
246  // -------------------------------------------------------------------------
247 
257  int InitPointInsertion(vtkPoints* points, const double bounds[6]) override;
258 
269  int InitPointInsertion(vtkPoints* points, const double bounds[6], vtkIdType estSize) override;
270 
276  vtkIdType IsInsertedPoint(const double x[3]) override;
277 
283  vtkIdType IsInsertedPoint(double x, double y, double z) override;
284 
293  int InsertUniquePoint(const double point[3], vtkIdType& pntId) override;
294 
303  void InsertPoint(vtkIdType ptId, const double x[3]) override;
304 
313  vtkIdType InsertNextPoint(const double x[3]) override;
314 
324  void InsertPointWithoutChecking(const double point[3], vtkIdType& pntId, int insert);
325 
326  vtkIncrementalOctreeNode* GetRoot() const { return OctreeRootNode; }
327 
333 
334 protected:
337 
338 private:
339  vtkTypeBool BuildCubicOctree;
340  int MaxPointsPerLeaf;
341  double InsertTolerance2;
342  double OctreeMaxDimSize;
343  double FudgeFactor;
344  vtkPoints* LocatorPoints;
345  vtkIncrementalOctreeNode* OctreeRootNode;
346  int NumberOfNodes;
347 
348  void BuildLocatorInternal() override;
349 
353  static void DeleteAllDescendants(vtkIncrementalOctreeNode* node);
354 
359  static void AddPolys(vtkIncrementalOctreeNode* node, vtkPoints* points, vtkCellArray* polygs,
360  vtkIntArray* nodeIndexes, vtkIdType& cellIndex,
361  bool (*GetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
362 
367  vtkIncrementalOctreeNode* GetLeafContainer(vtkIncrementalOctreeNode* node, const double pnt[3]);
368 
376  vtkIdType FindClosestPointInLeafNode(
377  vtkIncrementalOctreeNode* leafNode, const double point[3], double* dist2);
378 
391  vtkIdType FindClosestPointInSphere(const double point[3], double radius2,
392  vtkIncrementalOctreeNode* maskNode, double* minDist2, const double* refDist2);
393 
394  // -------------------------------------------------------------------------
395  // ---------------------------- Point Location ----------------------------
396  // -------------------------------------------------------------------------
397 
408  vtkIdType FindClosestPointInSphereWithoutTolerance(
409  const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2);
410 
416  void FindPointsWithinSquaredRadius(
417  vtkIncrementalOctreeNode* node, double radius2, const double point[3], vtkIdList* idList);
418 
419  // -------------------------------------------------------------------------
420  // ---------------------------- Point Insertion ----------------------------
421  // -------------------------------------------------------------------------
422 
434  vtkIdType FindClosestPointInSphereWithTolerance(
435  const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2);
436 
446  vtkIdType IsInsertedPoint(const double x[3], vtkIncrementalOctreeNode** leafContainer);
447 
456  vtkIdType IsInsertedPointForZeroTolerance(
457  const double x[3], vtkIncrementalOctreeNode** leafContainer);
458 
468  vtkIdType IsInsertedPointForNonZeroTolerance(
469  const double x[3], vtkIncrementalOctreeNode** leafContainer);
470 
478  vtkIdType FindDuplicatePointInLeafNode(vtkIncrementalOctreeNode* leafNode, const double point[3]);
479 
487  vtkIdType FindDuplicateFloatTypePointInVisitedLeafNode(
488  vtkIncrementalOctreeNode* leafNode, const double point[3]);
489 
497  vtkIdType FindDuplicateDoubleTypePointInVisitedLeafNode(
498  vtkIncrementalOctreeNode* leafNode, const double point[3]);
499 
501  void operator=(const vtkIncrementalOctreePointLocator&) = delete;
502 };
503 VTK_ABI_NAMESPACE_END
504 #endif
virtual double * GetBounds()
Provide an accessor to the bounds.
object to represent cell connectivity
Definition: vtkCellArray.h:176
list of point or cell ids
Definition: vtkIdList.h:23
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:29
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:35
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:192
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
represent and manipulate 3D points
Definition: vtkPoints.h:29
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:80
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