VTK  9.1.0
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 =========================================================================*/
48 #ifndef vtkIncrementalOctreePointLocator_h
49 #define vtkIncrementalOctreePointLocator_h
50 
51 #include "vtkCommonDataModelModule.h" // For export macro
53 
54 class vtkPoints;
55 class vtkIdList;
56 class vtkIntArray;
57 class vtkPolyData;
58 class vtkCellArray;
60 
61 class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
62 {
63 public:
65  void PrintSelf(ostream& os, vtkIndent indent) override;
66 
68 
70 
80  vtkSetClampMacro(MaxPointsPerLeaf, int, 16, 256);
81  vtkGetMacro(MaxPointsPerLeaf, int);
83 
85 
88  vtkSetMacro(BuildCubicOctree, vtkTypeBool);
89  vtkGetMacro(BuildCubicOctree, vtkTypeBool);
90  vtkBooleanMacro(BuildCubicOctree, vtkTypeBool);
92 
94 
98  vtkGetObjectMacro(LocatorPoints, vtkPoints);
100 
104  void Initialize() override { this->FreeSearchStructure(); }
105 
109  void FreeSearchStructure() override;
110 
114  void GetBounds(double* bounds) override;
115 
119  double* GetBounds() override
120  {
121  this->GetBounds(this->Bounds);
122  return this->Bounds;
123  }
124 
132  vtkGetMacro(NumberOfNodes, int);
133 
141  vtkIdType FindClosestInsertedPoint(const double x[3]) override;
142 
144 
156  void GenerateRepresentation(int level, vtkPolyData* polysData) override;
158  bool (*UserGetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
160 
161  // -------------------------------------------------------------------------
162  // ---------------------------- Point Location ----------------------------
163  // -------------------------------------------------------------------------
164 
169  void BuildLocator() override;
170 
176  vtkIdType FindClosestPoint(const double x[3]) override;
177 
184  virtual vtkIdType FindClosestPoint(double x, double y, double z);
185 
192  virtual vtkIdType FindClosestPoint(const double x[3], double* miniDist2);
193 
200  virtual vtkIdType FindClosestPoint(double x, double y, double z, double* miniDist2);
201 
210  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
211 
220  vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double& dist2);
221 
228  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
229 
236  void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList* result);
237 
244  void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
245 
246  // -------------------------------------------------------------------------
247  // ---------------------------- Point Insertion ----------------------------
248  // -------------------------------------------------------------------------
249 
259  int InitPointInsertion(vtkPoints* points, const double bounds[6]) override;
260 
271  int InitPointInsertion(vtkPoints* points, const double bounds[6], vtkIdType estSize) override;
272 
278  vtkIdType IsInsertedPoint(const double x[3]) override;
279 
285  vtkIdType IsInsertedPoint(double x, double y, double z) override;
286 
295  int InsertUniquePoint(const double point[3], vtkIdType& pntId) override;
296 
305  void InsertPoint(vtkIdType ptId, const double x[3]) override;
306 
315  vtkIdType InsertNextPoint(const double x[3]) override;
316 
326  void InsertPointWithoutChecking(const double point[3], vtkIdType& pntId, int insert);
327 
328  vtkIncrementalOctreeNode* GetRoot() const { return OctreeRootNode; }
329 
335 
336 protected:
339 
340 private:
341  vtkTypeBool BuildCubicOctree;
342  int MaxPointsPerLeaf;
343  double InsertTolerance2;
344  double OctreeMaxDimSize;
345  double FudgeFactor;
346  vtkPoints* LocatorPoints;
347  vtkIncrementalOctreeNode* OctreeRootNode;
348  int NumberOfNodes;
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 #endif
virtual double * GetBounds()
Provide an accessor to the bounds.
object to represent cell connectivity
Definition: vtkCellArray.h:181
list of point or cell ids
Definition: vtkIdList.h:31
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)
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.
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:34
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:40
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
represent and manipulate 3D points
Definition: vtkPoints.h:34
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
void GetBounds(T a, double bds[6])
@ point
Definition: vtkX3D.h:242
@ points
Definition: vtkX3D.h:452
@ level
Definition: vtkX3D.h:401
@ radius
Definition: vtkX3D.h:258
@ data
Definition: vtkX3D.h:321
int vtkTypeBool
Definition: vtkABI.h:69
int vtkIdType
Definition: vtkType.h:332