VTK
vtkOctreePointLocator.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkOctreePointLocator.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 =========================================================================*/
15 /*----------------------------------------------------------------------------
16  Copyright (c) Sandia Corporation
17  See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
18 ----------------------------------------------------------------------------*/
19 
39 #ifndef __vtkOctreePointLocator_h
40 #define __vtkOctreePointLocator_h
41 
42 #include "vtkAbstractPointLocator.h"
43 
44 class vtkCellArray;
45 class vtkIdTypeArray;
47 class vtkPoints;
48 class vtkPolyData;
49 
50 class VTK_FILTERING_EXPORT vtkOctreePointLocator : public vtkAbstractPointLocator
51 {
52 public:
53  vtkTypeMacro(vtkOctreePointLocator, vtkAbstractPointLocator);
54  void PrintSelf(ostream& os, vtkIndent indent);
55 
56  static vtkOctreePointLocator *New();
57 
59 
60  vtkSetMacro(MaximumPointsPerRegion, int);
61  vtkGetMacro(MaximumPointsPerRegion, int);
63 
65 
66  vtkSetMacro(CreateCubicOctants, int);
67  vtkGetMacro(CreateCubicOctants, int);
69 
71 
75  vtkGetMacro(FudgeFactor, double);
76  vtkSetMacro(FudgeFactor, double);
78 
80 
82  virtual double *GetBounds();
83  virtual void GetBounds(double *bounds);
85 
87 
88  vtkGetMacro(NumberOfLeafNodes, int);
90 
92  void GetRegionBounds(int regionID, double bounds[6]);
93 
95  void GetRegionDataBounds(int leafNodeID, double bounds[6]);
96 
98  int GetRegionContainingPoint(double x, double y, double z);
99 
103  virtual void BuildLocator();
104 
106 
108  virtual vtkIdType FindClosestPoint(const double x[3]);
109  vtkIdType FindClosestPoint(double x, double y, double z, double &dist2);
111 
113 
116  virtual vtkIdType FindClosestPointWithinRadius(
117  double radius, const double x[3], double& dist2);
119 
121 
124  vtkIdType FindClosestPointInRegion(int regionId, double *x, double &dist2);
125  vtkIdType FindClosestPointInRegion(int regionId, double x, double y,
126  double z, double &dist2);
128 
130 
132  virtual void FindPointsWithinRadius(
133  double radius, const double x[3], vtkIdList *result);
135 
142  void FindClosestNPoints(int N, const double x[3], vtkIdList *result);
143 
145  vtkIdTypeArray *GetPointsInRegion(int leafNodeId);
146 
148  virtual void FreeSearchStructure();
149 
152  void GenerateRepresentation(int level, vtkPolyData *pd);
153 
158  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
159 
160 protected:
161 
164 
166  vtkOctreePointLocatorNode **LeafNodeList; // indexed by region/node ID
167 
168  void BuildLeafNodeList(vtkOctreePointLocatorNode* node, int & index);
169 
171 
173  int FindRegion(vtkOctreePointLocatorNode* node, float x, float y, float z);
174  int FindRegion(vtkOctreePointLocatorNode* node, double x, double y, double z);
176 
177  static void SetDataBoundsToSpatialBounds(vtkOctreePointLocatorNode *node);
178 
179  static void DeleteAllDescendants(vtkOctreePointLocatorNode* octant);
180 
181 //BTX
183 
186  void FindPointsWithinRadius(vtkOctreePointLocatorNode* node, double radiusSquared,
187  const double x[3], vtkIdList* ids);
189 
190  // Recursive helper for public FindPointsWithinRadius
191  void AddAllPointsInRegion(vtkOctreePointLocatorNode* node, vtkIdList* ids);
192 
193  // Recursive helper for public FindPointsInArea
194  void FindPointsInArea(vtkOctreePointLocatorNode* node, double* area, vtkIdTypeArray* ids);
195 
196  // Recursive helper for public FindPointsInArea
197  void AddAllPointsInRegion(vtkOctreePointLocatorNode* node, vtkIdTypeArray* ids);
198 
199  void DivideRegion(vtkOctreePointLocatorNode *node, int* ordering, int level);
200 
201  int DivideTest(int size, int level);
202 
203 //ETX
204 
205  void AddPolys(vtkOctreePointLocatorNode *node, vtkPoints *pts, vtkCellArray *polys);
206 
208 
210  int _FindClosestPointInRegion(int leafNodeId, double x, double y,
211  double z, double &dist2);
213 
215 
220  int FindClosestPointInSphere(double x, double y, double z, double radius,
221  int skipRegion, double &dist2);
223 
225 
230 
231  double FudgeFactor; // a very small distance, relative to the dataset's size
235 
236  float MaxWidth;
237 
244 
245  vtkOctreePointLocator(const vtkOctreePointLocator&); // Not implemented
246  void operator=(const vtkOctreePointLocator&); // Not implemented
247 };
248 #endif
a octree spatial decomposition of a set of points
#define VTK_FILTERING_EXPORT
dynamic, self-adjusting array of vtkIdType
int vtkIdType
Definition: vtkType.h:255
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:81
vtkOctreePointLocatorNode ** LeafNodeList
a simple class to control print indentation
Definition: vtkIndent.h:37
list of point or cell ids
Definition: vtkIdList.h:34
object to represent cell connectivity
Definition: vtkCellArray.h:48
Octree node that has 8 children each of equal size.
vtkOctreePointLocatorNode * Top
represent and manipulate 3D points
Definition: vtkPoints.h:38