VTK
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 vtkPolyData;
57 class vtkCellArray;
59 
60 class VTKCOMMONDATAMODEL_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
61 {
62 public:
63 
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  { this->GetBounds( this->Bounds ); return this->Bounds; }
121 
125  int GetNumberOfPoints();
126 
134  vtkIdType FindClosestInsertedPoint( const double x[3] ) override;
135 
140  void GenerateRepresentation( int nodeLevel, vtkPolyData * polysData ) override;
141 
142  // -------------------------------------------------------------------------
143  // ---------------------------- Point Location ----------------------------
144  // -------------------------------------------------------------------------
145 
150  void BuildLocator() override;
151 
157  vtkIdType FindClosestPoint( const double x[3] ) override;
158 
165  virtual vtkIdType FindClosestPoint( double x, double y, double z );
166 
173  virtual vtkIdType FindClosestPoint( const double x[3], double * miniDist2 );
174 
181  virtual vtkIdType FindClosestPoint( double x, double y, double z, double * miniDist2 );
182 
192  ( double radius, const double x[3], double & dist2 ) override;
193 
202  vtkIdType FindClosestPointWithinSquaredRadius
203  ( double radius2, const double x[3], double & dist2 );
204 
212  ( double R, const double x[3], vtkIdList * result ) override;
213 
220  void FindPointsWithinSquaredRadius
221  ( double R2, const double x[3], vtkIdList * result );
222 
229  void FindClosestNPoints
230  ( int N, const double x[3], vtkIdList * result ) override;
231 
232  // -------------------------------------------------------------------------
233  // ---------------------------- Point Insertion ----------------------------
234  // -------------------------------------------------------------------------
235 
246  ( vtkPoints * points, const double bounds[6] ) override;
247 
258  int InitPointInsertion( vtkPoints * points, const double bounds[6],
259  vtkIdType estSize ) override;
260 
266  vtkIdType IsInsertedPoint( const double x[3] ) override;
267 
273  vtkIdType IsInsertedPoint( double x, double y, double z ) override;
274 
283  int InsertUniquePoint( const double point[3], vtkIdType & pntId ) override;
284 
293  void InsertPoint( vtkIdType ptId, const double x[3] ) override;
294 
303  vtkIdType InsertNextPoint( const double x[3] ) override;
304 
313  void InsertPointWithoutChecking
314  ( const double point[3], vtkIdType & pntId, int insert );
315 
316 protected:
317 
320 
321 private:
322 
323  vtkTypeBool BuildCubicOctree;
324  int MaxPointsPerLeaf;
325  double InsertTolerance2;
326  double OctreeMaxDimSize;
327  double FudgeFactor;
328  vtkPoints * LocatorPoints;
329  vtkIncrementalOctreeNode * OctreeRootNode;
330 
334  static void DeleteAllDescendants( vtkIncrementalOctreeNode * node );
335 
340  static void AddPolys( vtkIncrementalOctreeNode * node,
341  vtkPoints * points, vtkCellArray * polygs );
342 
347  vtkIncrementalOctreeNode * GetLeafContainer( vtkIncrementalOctreeNode * node,
348  const double pnt[3] );
349 
357  vtkIdType FindClosestPointInLeafNode( vtkIncrementalOctreeNode * leafNode,
358  const double point[3], double * dist2 );
359 
372  vtkIdType FindClosestPointInSphere
373  ( const double point[3], double radius2, vtkIncrementalOctreeNode * maskNode,
374  double * minDist2, const double * refDist2 );
375 
376 
377  // -------------------------------------------------------------------------
378  // ---------------------------- Point Location ----------------------------
379  // -------------------------------------------------------------------------
380 
391  vtkIdType FindClosestPointInSphereWithoutTolerance( const double point[3],
392  double radius2, vtkIncrementalOctreeNode * maskNode, double * minDist2 );
393 
399  void FindPointsWithinSquaredRadius( vtkIncrementalOctreeNode * node,
400  double radius2, const double point[3], vtkIdList * idList );
401 
402  // -------------------------------------------------------------------------
403  // ---------------------------- Point Insertion ----------------------------
404  // -------------------------------------------------------------------------
405 
417  vtkIdType FindClosestPointInSphereWithTolerance( const double point[3],
418  double radius2, vtkIncrementalOctreeNode * maskNode, double * minDist2 );
419 
429  vtkIdType IsInsertedPoint( const double x[3],
430  vtkIncrementalOctreeNode ** leafContainer );
431 
440  vtkIdType IsInsertedPointForZeroTolerance
441  ( const double x[3], vtkIncrementalOctreeNode ** leafContainer );
442 
452  vtkIdType IsInsertedPointForNonZeroTolerance
453  ( const double x[3], vtkIncrementalOctreeNode ** leafContainer );
454 
462  vtkIdType FindDuplicatePointInLeafNode( vtkIncrementalOctreeNode * leafNode,
463  const double point[3] );
464 
472  vtkIdType FindDuplicateFloatTypePointInVisitedLeafNode
473  ( vtkIncrementalOctreeNode * leafNode, const double point[3] );
474 
482  vtkIdType FindDuplicateDoubleTypePointInVisitedLeafNode
483  ( vtkIncrementalOctreeNode * leafNode, const double point[3] );
484 
486  ( const vtkIncrementalOctreePointLocator & ) = delete;
487  void operator = ( const vtkIncrementalOctreePointLocator & ) = delete;
488 
489 };
490 #endif
virtual void BuildLocator()=0
Build the locator from the input dataset.
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 duplciate 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:345
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:79
virtual void FreeSearchStructure()=0
Free the memory required for the spatial data structure.
int vtkTypeBool
Definition: vtkABI.h:69
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:33
list of point or cell ids
Definition: vtkIdList.h:30
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:44
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.
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:33
Incremental octree in support of both point location and point insertion.