VTK  9.2.6
vtkIncrementalOctreePointLocator.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkIncrementalOctreePointLocator.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 =========================================================================*/
51 #ifndef vtkIncrementalOctreePointLocator_h
52 #define vtkIncrementalOctreePointLocator_h
53 
54 #include "vtkCommonDataModelModule.h" // For export macro
56 
57 class vtkPoints;
58 class vtkIdList;
59 class vtkIntArray;
60 class vtkPolyData;
61 class vtkCellArray;
63 
64 class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
65 {
66 public:
68  void PrintSelf(ostream& os, vtkIndent indent) override;
69 
71 
73 
83  vtkSetMacro(MaxPointsPerLeaf, int);
84  vtkGetMacro(MaxPointsPerLeaf, int);
86 
88 
91  vtkSetMacro(BuildCubicOctree, vtkTypeBool);
92  vtkGetMacro(BuildCubicOctree, vtkTypeBool);
93  vtkBooleanMacro(BuildCubicOctree, vtkTypeBool);
95 
97 
101  vtkGetObjectMacro(LocatorPoints, vtkPoints);
103 
107  void Initialize() override { this->FreeSearchStructure(); }
108 
112  void FreeSearchStructure() override;
113 
117  void GetBounds(double* bounds) override;
118 
122  double* GetBounds() override
123  {
124  this->GetBounds(this->Bounds);
125  return this->Bounds;
126  }
127 
131  int GetNumberOfPoints();
135  vtkGetMacro(NumberOfNodes, int);
136 
144  vtkIdType FindClosestInsertedPoint(const double x[3]) override;
145 
147 
159  void GenerateRepresentation(int level, vtkPolyData* polysData) override;
160  void GenerateRepresentation(int level, vtkPolyData* polysData,
161  bool (*UserGetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
163 
164  // -------------------------------------------------------------------------
165  // ---------------------------- Point Location ----------------------------
166  // -------------------------------------------------------------------------
167 
173  void BuildLocator() override;
174 
178  void ForceBuildLocator() override;
179 
185  vtkIdType FindClosestPoint(const double x[3]) override;
186 
193  virtual vtkIdType FindClosestPoint(double x, double y, double z);
194 
201  virtual vtkIdType FindClosestPoint(const double x[3], double* miniDist2);
202 
209  virtual vtkIdType FindClosestPoint(double x, double y, double z, double* miniDist2);
210 
219  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
220 
229  vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double& dist2);
230 
237  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
238 
245  void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList* result);
246 
253  void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
254 
255  // -------------------------------------------------------------------------
256  // ---------------------------- Point Insertion ----------------------------
257  // -------------------------------------------------------------------------
258 
268  int InitPointInsertion(vtkPoints* points, const double bounds[6]) override;
269 
280  int InitPointInsertion(vtkPoints* points, const double bounds[6], vtkIdType estSize) override;
281 
287  vtkIdType IsInsertedPoint(const double x[3]) override;
288 
294  vtkIdType IsInsertedPoint(double x, double y, double z) override;
295 
304  int InsertUniquePoint(const double point[3], vtkIdType& pntId) override;
305 
314  void InsertPoint(vtkIdType ptId, const double x[3]) override;
315 
324  vtkIdType InsertNextPoint(const double x[3]) override;
325 
335  void InsertPointWithoutChecking(const double point[3], vtkIdType& pntId, int insert);
336 
337  vtkIncrementalOctreeNode* GetRoot() const { return OctreeRootNode; }
338 
343  int GetNumberOfLevels();
344 
345 protected:
348 
349 private:
350  vtkTypeBool BuildCubicOctree;
351  int MaxPointsPerLeaf;
352  double InsertTolerance2;
353  double OctreeMaxDimSize;
354  double FudgeFactor;
355  vtkPoints* LocatorPoints;
356  vtkIncrementalOctreeNode* OctreeRootNode;
357  int NumberOfNodes;
358 
359  void BuildLocatorInternal() override;
360 
364  static void DeleteAllDescendants(vtkIncrementalOctreeNode* node);
365 
370  static void AddPolys(vtkIncrementalOctreeNode* node, vtkPoints* points, vtkCellArray* polygs,
371  vtkIntArray* nodeIndexes, vtkIdType& cellIndex,
372  bool (*GetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
373 
378  vtkIncrementalOctreeNode* GetLeafContainer(vtkIncrementalOctreeNode* node, const double pnt[3]);
379 
387  vtkIdType FindClosestPointInLeafNode(
388  vtkIncrementalOctreeNode* leafNode, const double point[3], double* dist2);
389 
402  vtkIdType FindClosestPointInSphere(const double point[3], double radius2,
403  vtkIncrementalOctreeNode* maskNode, double* minDist2, const double* refDist2);
404 
405  // -------------------------------------------------------------------------
406  // ---------------------------- Point Location ----------------------------
407  // -------------------------------------------------------------------------
408 
419  vtkIdType FindClosestPointInSphereWithoutTolerance(
420  const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2);
421 
427  void FindPointsWithinSquaredRadius(
428  vtkIncrementalOctreeNode* node, double radius2, const double point[3], vtkIdList* idList);
429 
430  // -------------------------------------------------------------------------
431  // ---------------------------- Point Insertion ----------------------------
432  // -------------------------------------------------------------------------
433 
445  vtkIdType FindClosestPointInSphereWithTolerance(
446  const double point[3], double radius2, vtkIncrementalOctreeNode* maskNode, double* minDist2);
447 
457  vtkIdType IsInsertedPoint(const double x[3], vtkIncrementalOctreeNode** leafContainer);
458 
467  vtkIdType IsInsertedPointForZeroTolerance(
468  const double x[3], vtkIncrementalOctreeNode** leafContainer);
469 
479  vtkIdType IsInsertedPointForNonZeroTolerance(
480  const double x[3], vtkIncrementalOctreeNode** leafContainer);
481 
489  vtkIdType FindDuplicatePointInLeafNode(vtkIncrementalOctreeNode* leafNode, const double point[3]);
490 
498  vtkIdType FindDuplicateFloatTypePointInVisitedLeafNode(
499  vtkIncrementalOctreeNode* leafNode, const double point[3]);
500 
508  vtkIdType FindDuplicateDoubleTypePointInVisitedLeafNode(
509  vtkIncrementalOctreeNode* leafNode, const double point[3]);
510 
512  void operator=(const vtkIncrementalOctreePointLocator&) = delete;
513 };
514 #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:332
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:90
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
int vtkTypeBool
Definition: vtkABI.h:69
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:45
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:39
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition: vtkLocator.h:203
list of point or cell ids
Definition: vtkIdList.h:33
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:186
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:39
virtual void ForceBuildLocator()
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
Definition: vtkLocator.h:167
Incremental octree in support of both point location and point insertion.