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=========================================================================*/
67#ifndef vtkIncrementalOctreePointLocator_h
68#define vtkIncrementalOctreePointLocator_h
69
70#include "vtkCommonDataModelModule.h" // For export macro
72
73class vtkPoints;
74class vtkIdList;
75class vtkIntArray;
76class vtkPolyData;
77class vtkCellArray;
79
80class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
81{
82public:
84 void PrintSelf(ostream& os, vtkIndent indent) override;
85
87
89
99 vtkSetClampMacro(MaxPointsPerLeaf, int, 16, 256);
100 vtkGetMacro(MaxPointsPerLeaf, int);
102
104
107 vtkSetMacro(BuildCubicOctree, vtkTypeBool);
108 vtkGetMacro(BuildCubicOctree, vtkTypeBool);
109 vtkBooleanMacro(BuildCubicOctree, vtkTypeBool);
111
113
117 vtkGetObjectMacro(LocatorPoints, vtkPoints);
119
123 void Initialize() override { this->FreeSearchStructure(); }
124
128 void FreeSearchStructure() override;
129
133 void GetBounds(double* bounds) override;
134
138 double* GetBounds() override
139 {
140 this->GetBounds(this->Bounds);
141 return this->Bounds;
142 }
143
151 vtkGetMacro(NumberOfNodes, int);
152
160 vtkIdType FindClosestInsertedPoint(const double x[3]) override;
161
163
175 void GenerateRepresentation(int level, vtkPolyData* polysData) override;
176 void GenerateRepresentation(int level, vtkPolyData* polysData,
177 bool (*UserGetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
179
180 // -------------------------------------------------------------------------
181 // ---------------------------- Point Location ----------------------------
182 // -------------------------------------------------------------------------
183
188 void BuildLocator() override;
189
195 vtkIdType FindClosestPoint(const double x[3]) override;
196
203 virtual vtkIdType FindClosestPoint(double x, double y, double z);
204
211 virtual vtkIdType FindClosestPoint(const double x[3], double* miniDist2);
212
219 virtual vtkIdType FindClosestPoint(double x, double y, double z, double* miniDist2);
220
229 vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
230
239 vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double& dist2);
240
247 void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
248
255 void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList* result);
256
263 void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
264
265 // -------------------------------------------------------------------------
266 // ---------------------------- Point Insertion ----------------------------
267 // -------------------------------------------------------------------------
268
278 int InitPointInsertion(vtkPoints* points, const double bounds[6]) override;
279
290 int InitPointInsertion(vtkPoints* points, const double bounds[6], vtkIdType estSize) override;
291
297 vtkIdType IsInsertedPoint(const double x[3]) override;
298
304 vtkIdType IsInsertedPoint(double x, double y, double z) override;
305
314 int InsertUniquePoint(const double point[3], vtkIdType& pntId) override;
315
324 void InsertPoint(vtkIdType ptId, const double x[3]) override;
325
334 vtkIdType InsertNextPoint(const double x[3]) override;
335
345 void InsertPointWithoutChecking(const double point[3], vtkIdType& pntId, int insert);
346
347 vtkIncrementalOctreeNode* GetRoot() const { return OctreeRootNode; }
348
354
355protected:
358
359private:
360 vtkTypeBool BuildCubicOctree;
361 int MaxPointsPerLeaf;
362 double InsertTolerance2;
363 double OctreeMaxDimSize;
364 double FudgeFactor;
365 vtkPoints* LocatorPoints;
366 vtkIncrementalOctreeNode* OctreeRootNode;
367 int NumberOfNodes;
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#endif
virtual double * GetBounds()
Provide an accessor to the bounds.
object to represent cell connectivity
Definition: vtkCellArray.h:290
list of point or cell ids
Definition: vtkIdList.h:140
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.
vtkIncrementalOctreeNode * GetRoot() const
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.
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.
double * GetBounds() override
Get the spatial bounding box of the octree.
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.
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 ...
static vtkIncrementalOctreePointLocator * New()
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:113
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:149
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
represent and manipulate 3D points
Definition: vtkPoints.h:143
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:195
int vtkTypeBool
Definition: vtkABI.h:69
int vtkIdType
Definition: vtkType.h:332