/usr/include/vtk-5.8/vtkIncrementalOctreePointLocator.h is in libvtk5-dev 5.8.0-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 | /*=========================================================================
Program: Visualization Toolkit
Module: vtkIncrementalOctreePointLocator.h
Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
All rights reserved.
See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
This software is distributed WITHOUT ANY WARRANTY; without even
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the above copyright notice for more information.
=========================================================================*/
// .NAME vtkIncrementalOctreePointLocator - Incremental octree in support
// of both point location and point insertion.
//
// .SECTION Description
// As opposed to the uniform bin-based search structure (adopted in class
// vtkPointLocator) with a fixed spatial resolution, an octree mechanism
// employs a hierarchy of tree-like sub-division of the 3D data domain. Thus
// it enables data-aware multi-resolution and accordingly accelerated point
// location as well as insertion, particularly when handling a radically
// imbalanced layout of points as not uncommon in datasets defined on
// adaptive meshes. Compared to a static point locator supporting pure
// location functionalities through some search structure established from
// a fixed set of points, an incremental point locator allows for, in addition,
// point insertion capabilities, with the search structure maintaining a
// dynamically increasing number of points.
// Class vtkIncrementalOctreePointLocator is an octree-based accelerated
// implementation of the functionalities of the uniform bin-based incremental
// point locator vtkPointLocator. For point location, an octree is built by
// accessing a vtkDataSet, specifically a vtkPointSet. For point insertion,
// an empty octree is inited and then incrementally populated as points are
// inserted. Three increasingly complex point insertion modes, i.e., direct
// check-free insertion, zero tolerance insertion, and non-zero tolerance
// insertion, are supported. In fact, the octree used in the point location
// mode is actually constructed via direct check-free point insertion. This
// class also provides a polygonal representation of the octree boundary.
//
// .SECTION See Also
// vtkAbstractPointLocator, vtkIncrementalPointLocator, vtkPointLocator,
// vtkMergePoints
#ifndef __vtkIncrementalOctreePointLocator_h
#define __vtkIncrementalOctreePointLocator_h
#include "vtkIncrementalPointLocator.h"
class vtkPoints;
class vtkIdList;
class vtkPolyData;
class vtkCellArray;
class vtkIncrementalOctreeNode;
class VTK_FILTERING_EXPORT vtkIncrementalOctreePointLocator : public vtkIncrementalPointLocator
{
public:
vtkTypeMacro( vtkIncrementalOctreePointLocator, vtkIncrementalPointLocator );
void PrintSelf( ostream & os, vtkIndent indent );
static vtkIncrementalOctreePointLocator * New();
// Description:
// Set/Get the maximum number of points that a leaf node may maintain.
// Note that the actual number of points maintained by a leaf node might
// exceed this threshold if there is a large number (equal to or greater
// than the threshold) of exactly duplicate points (with zero distance)
// to be inserted (e.g., to construct an octree for subsequent point
// location) in extreme cases. Respecting this threshold in such scenarios
// would cause endless node sub-division. Thus this threshold is broken, but
// only in case of such situations.
vtkSetClampMacro( MaxPointsPerLeaf, int, 16, 256 );
vtkGetMacro( MaxPointsPerLeaf, int );
// Description:
// Set/Get whether the search octree is built as a cubic shape or not.
vtkSetMacro( BuildCubicOctree, int );
vtkGetMacro( BuildCubicOctree, int );
vtkBooleanMacro( BuildCubicOctree, int );
// Description:
// Get access to the vtkPoints object in which point coordinates are stored
// for either point location or point insertion.
vtkGetObjectMacro( LocatorPoints, vtkPoints );
// Description:
// Delete the octree search structure.
virtual void Initialize() { this->FreeSearchStructure(); }
// Description:
// Delete the octree search structure.
virtual void FreeSearchStructure();
// Description:
// Get the spatial bounding box of the octree.
virtual void GetBounds( double * bounds );
// Description:
// Get the spatial bounding box of the octree.
virtual double * GetBounds()
{ this->GetBounds( this->Bounds ); return this->Bounds; }
// Description:
// Get the number of points maintained by the octree.
int GetNumberOfPoints();
// Description:
// Given a point x assumed to be covered by the octree, return the index of
// the closest in-octree point regardless of the associated minimum squared
// distance relative to the squared insertion-tolerance distance. This method
// is used when performing incremental point insertion. Note -1 indicates that
// no point is found. InitPointInsertion() should have been called in advance.
virtual vtkIdType FindClosestInsertedPoint( const double x[3] );
// Description:
// Create a polygonal representation of the octree boundary (from the root
// node to a specified level).
virtual void GenerateRepresentation( int nodeLevel, vtkPolyData * polysData );
// -------------------------------------------------------------------------
// ---------------------------- Point Location ----------------------------
// -------------------------------------------------------------------------
// Description:
// Load points from a dataset to construct an octree for point location.
// This function resorts to InitPointInsertion() to fulfill some of the work.
virtual void BuildLocator();
// Description:
// Given a point x, return the id of the closest point. BuildLocator() should
// have been called prior to this function. This method is thread safe if
// BuildLocator() is directly or indirectly called from a single thread first.
virtual vtkIdType FindClosestPoint( const double x[3] );
// Description:
// Given a point (x, y, z), return the id of the closest point. Note that
// BuildLocator() should have been called prior to this function. This method
// is thread safe if BuildLocator() is directly or indirectly called from a
// single thread first.
virtual vtkIdType FindClosestPoint( double x, double y, double z );
// Description:
// Given a point x, return the id of the closest point and the associated
// minimum squared distance (via miniDist2). Note BuildLocator() should have
// been called prior to this function. This method is thread safe if
// BuildLocator() is directly or indirectly called from a single thread first.
virtual vtkIdType FindClosestPoint( const double x[3], double * miniDist2 );
// Description:
// Given a point (x, y, z), return the id of the closest point and the
// associated minimum squared distance (via miniDist2). BuildLocator() should
// have been called prior to this function. This method is thread safe if
// BuildLocator() is directly or indirectly called from a single thread first.
virtual vtkIdType FindClosestPoint( double x, double y, double z, double * miniDist2 );
// Description:
// Given a point x and a radius, return the id of the closest point within
// the radius and the associated minimum squared distance (via dist2, this
// returned distance is valid only if the point id is not -1). Note that
// BuildLocator() should have been called prior to this function. This method
// is thread safe if BuildLocator() is directly or indirectly called from a
// single thread first.
virtual vtkIdType FindClosestPointWithinRadius
( double radius, const double x[3], double & dist2 );
// Description:
// Given a point x and a squared radius radius2, return the id of the closest
// point within the radius and the associated minimum squared distance (via
// dist2, note this returned distance is valid only if the point id is not
// -1). BuildLocator() should have been called prior to this function.This
// method is thread safe if BuildLocator() is directly or indirectly called
// from a single thread first.
vtkIdType FindClosestPointWithinSquaredRadius
( double radius2, const double x[3], double & dist2 );
// Description:
// Find all points within a radius R relative to a given point x. The returned
// point ids (stored in result) are not sorted in any way. BuildLocator() should
// have been called prior to this function. This method is thread safe if
// BuildLocator() is directly or indirectly called from a single thread first.
virtual void FindPointsWithinRadius
( double R, const double x[3], vtkIdList * result );
// Description:
// Find all points within a squared radius R2 relative to a given point x. The
// returned point ids (stored in result) are not sorted in any way. BuildLocator()
// should have been called prior to this function. This method is thread safe if
// BuildLocator() is directly or indirectly called from a single thread first.
void FindPointsWithinSquaredRadius
( double R2, const double x[3], vtkIdList * result );
// Description:
// Find the closest N points to a given point. The returned point ids (via
// result) are sorted from closest to farthest. BuildLocator() should have
// been called prior to this function. This method is thread safe if
// BuildLocator() is directly or indirectly called from a single thread first.
virtual void FindClosestNPoints
( int N, const double x[3], vtkIdList * result );
// -------------------------------------------------------------------------
// ---------------------------- Point Insertion ----------------------------
// -------------------------------------------------------------------------
// Description:
// Initialize the point insertion process. points is an object, storing 3D
// point coordinates, to which incremental point insertion put coordinates.
// It is created and provided by an external VTK class. Argument bounds
// represents the spatial bounding box, into which the points fall. In fact,
// an adjusted version of the bounding box is used to build the octree to
// make sure no any point (to be inserted) falls outside the octree. This
// function is not thread safe.
virtual int InitPointInsertion( vtkPoints * points, const double bounds[6] );
// Description:
// Initialize the point insertion process. points is an object, storing 3D
// point coordinates, to which incremental point insertion put coordinates.
// It is created and provided by an external VTK class. Argument bounds
// represents the spatial bounding box, into which the points fall. In fact,
// an adjusted version of the bounding box is used to build the octree to
// make sure no any point (to be inserted) falls outside the octree. Argument
// estSize specifies the initial estimated size of the vtkPoints object. This
// function is not thread safe.
virtual int InitPointInsertion( vtkPoints * points, const double bounds[6],
vtkIdType estSize );
// Description:
// Determine whether or not a given point has been inserted into the octree.
// Return the id of the already inserted point if true, otherwise return -1.
// InitPointInsertion() should have been called in advance.
virtual vtkIdType IsInsertedPoint( const double x[3] );
// Description:
// Determine whether or not a given point has been inserted into the octree.
// Return the id of the already inserted point if true, otherwise return -1.
// InitPointInsertion() should have been called in advance.
virtual vtkIdType IsInsertedPoint( double x, double y, double z );
// Description:
// Insert a point to the octree unless there has been a duplciate point.
// Whether the point is actually inserted (return 1) or not (return 0 upon a
// rejection by an existing duplicate), the index of the point (either new
// or the duplicate) is returned via pntId. Note that InitPointInsertion()
// should have been called prior to this function. vtkPoints::InsertNextPoint()
// is invoked. This method is not thread safe.
virtual int InsertUniquePoint( const double point[3], vtkIdType & pntId );
// Description:
// Insert a given point into the octree with a specified point index ptId.
// InitPointInsertion() should have been called prior to this function. In
// addition, IsInsertedPoint() should have been called in advance to ensure
// that the given point has not been inserted unless point duplication is
// allowed (Note that in this case, this function involves a repeated leaf
// container location). vtkPoints::InsertPoint() is invoked.
virtual void InsertPoint( vtkIdType ptId, const double x[3] );
// Description:
// Insert a given point into the octree and return the point index. Note that
// InitPointInsertion() should have been called prior to this function. In
// addition, IsInsertedPoint() should have been called in advance to ensure
// that the given point has not been inserted unless point duplication is
// allowed (in this case, this function invovles a repeated leaf container
// location). vtkPoints::InsertNextPoint() is invoked.
virtual vtkIdType InsertNextPoint( const double x[3] );
// Description:
// "Insert" a point to the octree without any checking. Argument insert means
// whether vtkPoints::InsertNextPoint() upon 1 is called or the point itself
// is not inserted to the vtkPoints at all but instead only the point index is
// inserted to a vtkIdList upon 0. For case 0, the point index needs to be
// specified via pntId. For case 1, the actual point index is returned via
// pntId. InitPointInsertion() should have been called.
void InsertPointWithoutChecking
( const double point[3], vtkIdType & pntId, int insert );
//BTX
protected:
vtkIncrementalOctreePointLocator();
virtual ~vtkIncrementalOctreePointLocator();
private:
int BuildCubicOctree;
int MaxPointsPerLeaf;
double InsertTolerance2;
double OctreeMaxDimSize;
double FudgeFactor;
vtkPoints * LocatorPoints;
vtkIncrementalOctreeNode * OctreeRootNode;
// Description:
// Delete all descendants of a node.
static void DeleteAllDescendants( vtkIncrementalOctreeNode * node );
// Description:
// Add the polygonal representation of a given node to the allocated vtkPoints
// and vtkCellArray objects.
static void AddPolys( vtkIncrementalOctreeNode * node,
vtkPoints * points, vtkCellArray * polygs );
// Description:
// Given a point and a reference node, find the leaf containing the point.
// Note the point is assumed to be inside or under the reference node.
vtkIncrementalOctreeNode * GetLeafContainer( vtkIncrementalOctreeNode * node,
const double pnt[3] );
// Description:
// Given a point (under check, either inside or outside the octree) and a leaf
// node (not necessarily the container of this point), find the closest point
// (possibly a duplicate of the point under check) within the node and return
// the point index as well as the associated minimum squared distance (via dist2).
// InitPointInsertion() or BuildLocator() should have been called.
vtkIdType FindClosestPointInLeafNode( vtkIncrementalOctreeNode * leafNode,
const double point[3], double * dist2 );
// Description:
// This function may not be directly called. Please use the follwing two ones:
// FindClosestPointInSphereWithTolerance() for point insertion and
// FindClosestPointInSphereWithoutTolerance() for point location. Arguments
// refDist2 and the initialization of minDist2 determine which version is used.
// Given a point (under check) and an already-checked node (possibly NULL),
// find the closest point across a set of neighboring nodes within a specified
// squared radius to the given point --- to perform an extended within-radius
// inter-node search. The leaf (mask) node itself is excluded from the search
// scope. Returned are the point index and the associated minimum squared
// distance. InitPointInsertion() or BuildLocator() should have been called.
vtkIdType FindClosestPointInSphere
( const double point[3], double radius2, vtkIncrementalOctreeNode * maskNode,
double * minDist2, const double * refDist2 );
// -------------------------------------------------------------------------
// ---------------------------- Point Location ----------------------------
// -------------------------------------------------------------------------
// Description:
// This function is intended for point location, excluding point insertion.
// Given a point (under check, covered or uncovered by the octree) and an
// already-checked leaf node (maskNode, possibly NULL), find the closest point
// across a set of neighboring nodes within a specified squared radius to the
// given point --- to perform an extended within-radius inter-node search. The
// leaf (mask) node itself is excluded from the search scope. Returned are the
// point index and the associated minimum squared distance (via minDist2). Note
// that BuildLocator() should have been called.
vtkIdType FindClosestPointInSphereWithoutTolerance( const double point[3],
double radius2, vtkIncrementalOctreeNode * maskNode, double * minDist2 );
// Description:
// Find all points, inside a given node, within a squared radius relative to
// a given point. Returned are the associated un-sorted point indices (idList).
// Note that BuildLocator() should have been called prior to this function.
void FindPointsWithinSquaredRadius( vtkIncrementalOctreeNode * node,
double radius2, const double point[3], vtkIdList * idList );
// -------------------------------------------------------------------------
// ---------------------------- Point Insertion ----------------------------
// -------------------------------------------------------------------------
// Description:
// This function is intended for point insertion, excluding point location.
// Given a point (under check for insertion, must be covered by the octree)
// and an already-checked node (maskNode, the container leaf node, possibly
// NULL if no any node has been checked), find the closest point across a set
// of neighbor nodes within a specified squared radius radius2 to the given
// point --- to perform an extended within-radius inter-node search. The leaf
// (mask) node itself is excluded from the search scope. Returned are the point
// index and the associated minimum squared distance (via minDist2). Note that
// InitPointInsertion() should have been called.
vtkIdType FindClosestPointInSphereWithTolerance( const double point[3],
double radius2, vtkIncrementalOctreeNode * maskNode, double * minDist2 );
// Description:
// Determine whether or not a given point has been inserted into the octree.
// Return the id of the already inserted point if true, otherwise return -1.
// Argument leafContainer is useful for access only if -1 is returned. This
// returned parameter indicates the leaf node that contains the given point.
// This function resorts to IsInsertedPointForZeroTolerance() for zero
// tolerance insertion or IsInsertedPointForNonZeroTolerance() for non-zero
// tolerance insertion. InitPointInsertion() should have been called.
vtkIdType IsInsertedPoint( const double x[3],
vtkIncrementalOctreeNode ** leafContainer );
// Description:
// Determine whether or not a given point has been inserted into the octree.
// Return the id of the already inserted point if true, otherwise return -1.
// Argument leafContainer is useful for access only if -1 is returned. This
// returned parameter indicates the leaf node that contains the given point.
// This variant is invoked by IsInsertedPoint(x, vtkIncrementalOctreeNode **)
// for zero tolerance insertion. InitPointInsertion() should have been called.
vtkIdType IsInsertedPointForZeroTolerance
( const double x[3], vtkIncrementalOctreeNode ** leafContainer );
// Description:
// Determine whether or not a given point has been inserted into the octree.
// Return the id of the already inserted point if true, otherwise return -1.
// Argument leafContainer is useful for access only if -1 is returned. This
// returned parameter indicates the leaf node that contains the given point.
// This variant is invoked by IsInsertedPoint(x, vtkIncrementalOctreeNode **)
// for non-zero tolerance insertion. InitPointInsertion() should have been
// called in advance.
vtkIdType IsInsertedPointForNonZeroTolerance
( const double x[3], vtkIncrementalOctreeNode ** leafContainer );
// Description:
// Given a point (under check for zero tolerance insertion) and a leaf node,
// find its duplicate, if any, in the node and return the point index (-1 if
// no duplicate is found). Note that the leaf node, already with at least one
// point, is the container of the point under check. InitPointInsertion()
// should have been called.
vtkIdType FindDuplicatePointInLeafNode( vtkIncrementalOctreeNode * leafNode,
const double point[3] );
// Description:
// Given a point (under check for zero tolerance insertion) and a leaf node,
// find its duplicate, if any, in the node and return the point index (-1 if
// no duplicate is found). Note that the leaf node, already with at least one
// point, is the container of the point under check. This function is invoked
// for type VTK_FLOAT. InitPointInsertion() should have been called.
vtkIdType FindDuplicateFloatTypePointInVisitedLeafNode
( vtkIncrementalOctreeNode * leafNode, const double point[3] );
// Description:
// Given a point (under check for zero tolerance insertion) and a leaf node,
// find its duplicate, if any, in the node and return the point index (-1 if
// no duplicate is found). Note that the leaf node, already with at least one
// point, is the container of the point under check. This function is invoked
// for type VTK_DOUBLE. InitPointInsertion() should have been called.
vtkIdType FindDuplicateDoubleTypePointInVisitedLeafNode
( vtkIncrementalOctreeNode * leafNode, const double point[3] );
vtkIncrementalOctreePointLocator
( const vtkIncrementalOctreePointLocator & ); // Not implemented
void operator = ( const vtkIncrementalOctreePointLocator & );// Not implemented
//ETX
};
#endif
|