VTK  9.3.1
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 
120  int GetNumberOfPoints();
124  vtkGetMacro(NumberOfNodes, int);
125 
133  vtkIdType FindClosestInsertedPoint(const double x[3]) override;
134 
136 
148  void GenerateRepresentation(int level, vtkPolyData* polysData) override;
149  void GenerateRepresentation(int level, vtkPolyData* polysData,
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 
332  int GetNumberOfLevels();
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 void BuildLocator()=0
Build the locator from the input dataset.
void GetBounds(T a, double bds[6])
virtual vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double &dist2)=0
Given a position x and a radius r, return the id of the point closest to the point in that radius...
virtual int InsertUniquePoint(const double x[3], vtkIdType &ptId)=0
Insert a point unless there has been a duplicate in the search structure.
virtual vtkIdType IsInsertedPoint(double x, double y, double z)=0
Determine whether or not a given point has been inserted.
Abstract class in support of both point location and point insertion.
virtual double * GetBounds()
Provide an accessor to the bounds.
int vtkIdType
Definition: vtkType.h:315
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
int vtkTypeBool
Definition: vtkABI.h:64
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:34
virtual int InitPointInsertion(vtkPoints *newPts, const double bounds[6])=0
Initialize the point insertion process.
a simple class to control print indentation
Definition: vtkIndent.h:28
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:192
list of point or cell ids
Definition: vtkIdList.h:22
Octree node constituting incremental octree (in support of both point location and point insertion) ...
virtual void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result)=0
Find all points within a specified radius R of position x.
void Initialize() override
Delete the octree search structure.
virtual void FindClosestNPoints(int N, const double x[3], vtkIdList *result)=0
Find the closest N points to a position.
void PrintSelf(ostream &os, vtkIndent indent) override
Standard type and print methods.
object to represent cell connectivity
Definition: vtkCellArray.h:175
virtual vtkIdType InsertNextPoint(const double x[3])=0
Insert a given point and return the point index.
virtual vtkIdType FindClosestInsertedPoint(const double x[3])=0
Given a point x assumed to be covered by the search structure, return the index of the closest point ...
virtual vtkIdType FindClosestPoint(const double x[3])=0
Given a position x, return the id of the point closest to it.
vtkIncrementalOctreeNode * GetRoot() const
static vtkObject * New()
Create an object with Debug turned off, modified time initialized to zero, and reference counting on...
virtual void InsertPoint(vtkIdType ptId, const double x[3])=0
Insert a given point with a specified point index ptId.
double * GetBounds() override
Get the spatial bounding box of the octree.
virtual void GenerateRepresentation(int level, vtkPolyData *pd)=0
Method to build a representation at a particular level.
represent and manipulate 3D points
Definition: vtkPoints.h:28
virtual void ForceBuildLocator()
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
Definition: vtkLocator.h:156
Incremental octree in support of both point location and point insertion.