VTK  9.4.20241221
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
58#ifndef vtkIncrementalOctreePointLocator_h
59#define vtkIncrementalOctreePointLocator_h
60
61#include "vtkCommonDataModelModule.h" // For export macro
63
64VTK_ABI_NAMESPACE_BEGIN
65class vtkPoints;
66class vtkIdList;
67class vtkIntArray;
68class vtkPolyData;
69class vtkCellArray;
71
72class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
73{
74public:
76 void PrintSelf(ostream& os, vtkIndent indent) override;
77
79
81
91 vtkSetMacro(MaxPointsPerLeaf, int);
92 vtkGetMacro(MaxPointsPerLeaf, int);
94
96
99 vtkSetMacro(BuildCubicOctree, vtkTypeBool);
100 vtkGetMacro(BuildCubicOctree, vtkTypeBool);
101 vtkBooleanMacro(BuildCubicOctree, vtkTypeBool);
103
105
109 vtkGetObjectMacro(LocatorPoints, vtkPoints);
111
115 void Initialize() override { this->FreeSearchStructure(); }
116
120 void FreeSearchStructure() override;
121
125 void GetBounds(double* bounds) override;
126
130 double* GetBounds() override
131 {
132 this->GetBounds(this->Bounds);
133 return this->Bounds;
134 }
135
143 vtkGetMacro(NumberOfNodes, int);
144
152 vtkIdType FindClosestInsertedPoint(const double x[3]) override;
153
155
167 void GenerateRepresentation(int level, vtkPolyData* polysData) override;
168 void GenerateRepresentation(int level, vtkPolyData* polysData,
169 bool (*UserGetBounds)(void* data, vtkIncrementalOctreeNode* node, double* bounds), void* data);
171
172 // -------------------------------------------------------------------------
173 // ---------------------------- Point Location ----------------------------
174 // -------------------------------------------------------------------------
175
181 void BuildLocator() override;
182
186 void ForceBuildLocator() override;
187
193 vtkIdType FindClosestPoint(const double x[3]) override;
194
201 virtual vtkIdType FindClosestPoint(double x, double y, double z);
202
209 virtual vtkIdType FindClosestPoint(const double x[3], double* miniDist2);
210
217 virtual vtkIdType FindClosestPoint(double x, double y, double z, double* miniDist2);
218
227 vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2) override;
228
237 vtkIdType FindClosestPointWithinSquaredRadius(double radius2, const double x[3], double& dist2);
238
245 void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result) override;
246
253 void FindPointsWithinSquaredRadius(double R2, const double x[3], vtkIdList* result);
254
261 void FindClosestNPoints(int N, const double x[3], vtkIdList* result) override;
262
263 // -------------------------------------------------------------------------
264 // ---------------------------- Point Insertion ----------------------------
265 // -------------------------------------------------------------------------
266
276 int InitPointInsertion(vtkPoints* points, const double bounds[6]) override;
277
288 int InitPointInsertion(vtkPoints* points, const double bounds[6], vtkIdType estSize) override;
289
295 vtkIdType IsInsertedPoint(const double x[3]) override;
296
302 vtkIdType IsInsertedPoint(double x, double y, double z) override;
303
312 int InsertUniquePoint(const double point[3], vtkIdType& pntId) override;
313
322 void InsertPoint(vtkIdType ptId, const double x[3]) override;
323
332 vtkIdType InsertNextPoint(const double x[3]) override;
333
343 void InsertPointWithoutChecking(const double point[3], vtkIdType& pntId, int insert);
344
345 vtkIncrementalOctreeNode* GetRoot() const { return OctreeRootNode; }
346
352
353protected:
356
357private:
358 vtkTypeBool BuildCubicOctree;
359 int MaxPointsPerLeaf;
360 double InsertTolerance2;
361 double OctreeMaxDimSize;
362 double FudgeFactor;
363 vtkPoints* LocatorPoints;
364 vtkIncrementalOctreeNode* OctreeRootNode;
365 int NumberOfNodes;
366
367 void BuildLocatorInternal() override;
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};
522VTK_ABI_NAMESPACE_END
523#endif
virtual double * GetBounds()
Provide an accessor to the bounds.
object to represent cell connectivity
list of point or cell ids
Definition vtkIdList.h:133
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.
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.
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 ...
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:108
dynamic, self-adjusting array of int
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition vtkLocator.h:211
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
represent and manipulate 3D points
Definition vtkPoints.h:139
concrete dataset represents vertices, lines, polygons, and triangle strips
int vtkTypeBool
Definition vtkABI.h:64
int vtkIdType
Definition vtkType.h:315