VTK  9.3.0
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
45VTK_ABI_NAMESPACE_BEGIN
46class vtkPoints;
47class vtkIdList;
48class vtkIntArray;
49class vtkPolyData;
50class vtkCellArray;
52
53class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
54{
55public:
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
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
333
334protected:
337
338private:
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};
503VTK_ABI_NAMESPACE_END
504#endif
virtual double * GetBounds()
Provide an accessor to the bounds.
object to represent cell connectivity
list of point or cell ids
Definition vtkIdList.h:23
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:29
dynamic, self-adjusting array of int
Definition vtkIntArray.h:35
virtual void BuildLocatorInternal()
This function is not pure virtual to maintain backwards compatibility.
Definition vtkLocator.h:192
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
represent and manipulate 3D points
Definition vtkPoints.h:29
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition vtkPolyData.h:80
int vtkTypeBool
Definition vtkABI.h:64
int vtkIdType
Definition vtkType.h:315