VTK
vtkKdTree.h
Go to the documentation of this file.
1 /*=========================================================================
2 
3  Program: Visualization Toolkit
4  Module: vtkKdTree.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 
59 #ifndef vtkKdTree_h
60 #define vtkKdTree_h
61 
62 #include "vtkCommonDataModelModule.h" // For export macro
63 #include "vtkLocator.h"
64 
65 class vtkTimerLog;
66 class vtkIdList;
67 class vtkIdTypeArray;
68 class vtkIntArray;
69 class vtkPointSet;
70 class vtkPoints;
71 class vtkCellArray;
72 class vtkCell;
73 class vtkKdNode;
74 class vtkBSPCuts;
77 
78 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
79 {
80 public:
81  vtkTypeMacro(vtkKdTree, vtkLocator);
82  void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;
83 
84  static vtkKdTree *New();
85 
87 
90  vtkBooleanMacro(Timing, int);
91  vtkSetMacro(Timing, int);
92  vtkGetMacro(Timing, int);
94 
96 
99  vtkSetMacro(MinCells, int);
100  vtkGetMacro(MinCells, int);
102 
110  vtkGetMacro(NumberOfRegionsOrLess, int);
111  vtkSetMacro(NumberOfRegionsOrLess, int);
112 
120  vtkGetMacro(NumberOfRegionsOrMore, int);
121  vtkSetMacro(NumberOfRegionsOrMore, int);
122 
130  vtkGetMacro(FudgeFactor, double);
131  vtkSetMacro(FudgeFactor, double);
132 
138  vtkGetObjectMacro(Cuts, vtkBSPCuts);
139 
146  void SetCuts(vtkBSPCuts *cuts);
147 
152 
157 
162 
167 
172 
177 
182 
197  void SetDataSet(vtkDataSet *set) VTK_OVERRIDE;
198 
203  virtual void AddDataSet(vtkDataSet *set);
204 
206 
209  virtual void RemoveDataSet(int index);
210  virtual void RemoveDataSet(vtkDataSet *set);
211  virtual void RemoveAllDataSets();
213 
218 
229 
234  vtkDataSet *GetDataSet() VTK_OVERRIDE { return this->GetDataSet(0); }
235 
237 
240  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
242 
248 
253  void GetBounds(double *bounds);
254 
263  void SetNewBounds(double *bounds);
264 
266 
269  vtkGetMacro(NumberOfRegions, int);
271 
275  void GetRegionBounds(int regionID, double bounds[6]);
276 
280  void GetRegionDataBounds(int regionID, double bounds[6]);
281 
283 
286  void PrintTree();
289 
293  void PrintRegion(int id);
294 
307  void CreateCellLists(int dataSetIndex, int *regionReqList,
308  int reqListSize);
309  void CreateCellLists(vtkDataSet *set, int *regionReqList,
310  int reqListSize);
311  void CreateCellLists(int *regionReqList, int listSize);
313 
315 
322  vtkSetMacro(IncludeRegionBoundaryCells, int);
323  vtkGetMacro(IncludeRegionBoundaryCells, int);
324  vtkBooleanMacro(IncludeRegionBoundaryCells, int);
326 
331 
336  vtkIdList *GetCellList(int regionID);
337 
349 
351 
371  vtkIdType GetCellLists(vtkIntArray *regions, int set,
372  vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
374  vtkIdList *inRegionCells, vtkIdList *onBoundaryCells);
375  vtkIdType GetCellLists(vtkIntArray *regions, vtkIdList *inRegionCells,
376  vtkIdList *onBoundaryCells);
378 
380 
387  int GetRegionContainingCell(int set, vtkIdType cellID);
390 
400 
404  int GetRegionContainingPoint(double x, double y, double z);
405 
411  void BuildLocator() VTK_OVERRIDE;
412 
427  int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList,
428  double **convexRegionBounds);
429 
437  int ViewOrderAllRegionsInDirection(const double directionOfProjection[3],
438  vtkIntArray *orderedList);
439 
447  int ViewOrderRegionsInDirection(vtkIntArray *regionIds,
448  const double directionOfProjection[3],
449  vtkIntArray *orderedList);
450 
458  int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3],
459  vtkIntArray *orderedList);
460 
468  int ViewOrderRegionsFromPosition(vtkIntArray *regionIds,
469  const double directionOfProjection[3],
470  vtkIntArray *orderedList);
471 
473 
486  void BuildLocatorFromPoints(vtkPointSet *pointset);
487  void BuildLocatorFromPoints(vtkPoints *ptArray);
488  void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays);
490 
505  vtkIdTypeArray *BuildMapForDuplicatePoints(float tolerance);
506 
508 
513  vtkIdType FindPoint(double *x);
514  vtkIdType FindPoint(double x, double y, double z);
516 
518 
523  vtkIdType FindClosestPoint(double *x, double &dist2);
524  vtkIdType FindClosestPoint(double x, double y, double z, double &dist2);
526 
532  vtkIdType FindClosestPointWithinRadius(
533  double radius, const double x[3], double& dist2);
534 
536 
541  vtkIdType FindClosestPointInRegion(int regionId, double *x, double &dist2);
542  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z,
543  double &dist2);
545 
552  void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result);
553 
562  void FindClosestNPoints(int N, const double x[3], vtkIdList *result);
563 
568  vtkIdTypeArray *GetPointsInRegion(int regionId);
569 
574  void FreeSearchStructure() VTK_OVERRIDE;
575 
581  void GenerateRepresentation(int level, vtkPolyData *pd) VTK_OVERRIDE;
582 
587  void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd);
588 
590 
596  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, int);
597  vtkSetMacro(GenerateRepresentationUsingDataBounds, int);
598  vtkGetMacro(GenerateRepresentationUsingDataBounds, int);
600 
604  virtual void PrintTiming(ostream& os, vtkIndent indent);
605 
610  virtual int NewGeometry();
611 
617  virtual int NewGeometry(vtkDataSet **sets, int numDataSets);
618 
624  virtual void InvalidateGeometry();
625 
631  static vtkKdNode *CopyTree(vtkKdNode *kd);
632 
639  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
640 
641 protected:
642 
644  ~vtkKdTree() VTK_OVERRIDE;
645 
646  vtkBSPIntersections *BSPCalculator;
647  int UserDefinedCuts;
648 
649  void SetCalculator(vtkKdNode *kd);
650 
651  int ProcessUserDefinedCuts(double *bounds);
652 
653  void SetCuts(vtkBSPCuts *cuts, int userDefined);
654 
660  void UpdateBuildTime();
661 
669  int DivideTest(int numberOfPoints, int level);
670 
671  enum {
672  XDIM = 0, // don't change these values
673  YDIM = 1,
674  ZDIM = 2
675  };
676 
678 
680  vtkKdNode **RegionList; // indexed by region ID
681 
683 
684  static void DeleteAllDescendants(vtkKdNode *nd);
685 
687  virtual int SelectCutDirection(vtkKdNode *kd);
688  void SetActualLevel(){this->Level = vtkKdTree::ComputeLevel(this->Top);}
689 
695  void GetRegionsAtLevel(int level, vtkKdNode **nodes);
696 
702  static void GetLeafNodeIds(vtkKdNode *node, vtkIntArray *ids);
703 
704 
710 
716  int GetDataSetsNumberOfCells(int set1, int set2);
717 
724  void ComputeCellCenter(vtkDataSet *set, int cellId, float *center);
725  void ComputeCellCenter(vtkDataSet *set, int cellId, double *center);
726 
737  float *ComputeCellCenters(int set);
739 
741 
747  void UpdateProgress(double amount);
748 
750 
753  vtkSetClampMacro(Progress,double,0.0,1.0);
754  vtkGetMacro(Progress,double);
756 
757 protected:
758  // So that each suboperation can report progress
759  // in [0,1], yet we will be able to report a global
760  // progress. Sub-operations must use UpdateSubOperationProgress()
761  // for this to work.
764 
765  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
766  // Actual progress is given by
767  // (this->ProgressOffset + this->ProgressScale* amount).
768  void UpdateSubOperationProgress(double amount);
769 
770  static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim);
771  static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from);
772  static void CopyKdNode(vtkKdNode *to, vtkKdNode *from);
774  static void ZeroNumberOfPoints(vtkKdNode *kd);
775 
776  // Recursive helper for public FindPointsWithinRadius
777  void FindPointsWithinRadius(vtkKdNode* node, double R2,
778  const double x[3], vtkIdList* ids);
779 
780  // Recursive helper for public FindPointsWithinRadius
782 
783  // Recursive helper for public FindPointsInArea
784  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
785 
786  // Recursive helper for public FindPointsInArea
788 
789  int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels);
790 
791  void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3);
792 
794 
795  struct _cellList{
796  vtkDataSet *dataSet; // cell lists for which data set
797  int *regionIds; // NULL if listing all regions
798  int nRegions;
802  };
803 
805  vtkIdList *GetList(int regionId, vtkIdList **which);
806 
807  void ComputeCellCenter(vtkCell* cell, double *center, double *weights);
808 
811  vtkCellArray *polys, int level);
812 
815  vtkCellArray *polys, int level);
816 
817  void AddPolys(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys);
818 
819  void _printTree(int verbose);
820 
821  int SearchNeighborsForDuplicate(int regionId, float *point,
822  int **pointsSoFar, int *len,
823  float tolerance, float tolerance2);
824 
825  int SearchRegionForDuplicate(float *point, int *pointsSoFar,
826  int len, float tolerance2);
827 
828  int _FindClosestPointInRegion(int regionId,
829  double x, double y, double z, double &dist2);
830 
831  int FindClosestPointInSphere(double x, double y, double z, double radius,
832  int skipRegion, double &dist2);
833 
835  const double dop[3],
836  vtkIntArray *orderedList);
837 
839  vtkIntArray *IdsOfInterest,
840  const double dir[3], int nextId);
841 
843  const double pos[3],
844  vtkIntArray *orderedList);
845 
847  vtkIntArray *IdsOfInterest,
848  const double pos[3], int nextId);
849 
850  static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes);
851  static int FoundId(vtkIntArray *idArray, int id);
852 
853  void NewParitioningRequest(int req);
854  void SetInputDataInfo(int i,
855  int dims[3], double origin[3], double spacing[3]);
857  int dims[3], double origin[3], double spacing[3]);
859 
860  static void __printTree(vtkKdNode *kd, int depth, int verbose);
861 
862  static int MidValue(int dim, float *c1, int nvals, double &coord);
863 
864  static int Select(int dim, float *c1, int *ids, int nvals, double &coord);
865  static float FindMaxLeftHalf(int dim, float *c1, int K);
866  static void _Select(int dim, float *X, int *ids, int L, int R, int K);
867 
868  static int ComputeLevel(vtkKdNode *kd);
869  static int SelfOrder(int id, vtkKdNode *kd);
870  static int findRegion(vtkKdNode *node, float x, float y, float z);
871  static int findRegion(vtkKdNode *node, double x, double y, double z);
872 
874  vtkKdNode *kd);
875 
876  static void AddNewRegions(vtkKdNode *kd, float *c1,
877  int midpt, int dim, double coord);
878 
879  void NewPartitioningRequest(int req);
880 
883 
885  double CellBoundsCache[6]; // to optimize IntersectsCell()
886 
888 
889  struct _cellList CellList;
890 
891  // Region Ids, by data set by cell id - this list is large (one
892  // int per cell) but accelerates creation of cell lists
893 
895 
896  int MinCells;
897  int NumberOfRegions; // number of leaf nodes
898 
899  int Timing;
900  double FudgeFactor; // a very small distance, relative to the dataset's size
901 
902  // These instance variables are used by the special locator created
903  // to find duplicate points. (BuildLocatorFromPoints)
904 
909 
910  float MaxWidth;
911 
912  // These Last* values are here to save state so we can
913  // determine later if k-d tree must be rebuilt.
914 
918  unsigned long *LastDataSetObserverTags;
921  double *LastBounds;
924 
926  double Progress;
927 
928  vtkKdTree(const vtkKdTree&) VTK_DELETE_FUNCTION;
929  void operator=(const vtkKdTree&) VTK_DELETE_FUNCTION;
930 };
931 #endif
vtkKdTree::CopyChildNodes
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
vtkPoints
represent and manipulate 3D points
Definition: vtkPoints.h:40
vtkKdTree::GetBounds
void GetBounds(double *bounds)
Get the spatial bounds of the entire k-d tree space.
vtkKdTree::CreateCellLists
void CreateCellLists(vtkDataSet *set, int *regionReqList, int reqListSize)
vtkKdTree::TimerLog
vtkTimerLog * TimerLog
Definition: vtkKdTree.h:682
vtkKdNode
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
Definition: vtkKdNode.h:46
vtkKdTree::GetList
vtkIdList * GetList(int regionId, vtkIdList **which)
vtkKdTree::OmitYPartitioning
void OmitYPartitioning()
Omit partitions along the Y axis, yielding shafts in the Y direction.
vtkKdTree::GetCellLists
vtkIdType GetCellLists(vtkIntArray *regions, int set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
For a list of regions, get two cell lists.
vtkKdTree::AddPolys
void AddPolys(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys)
vtkKdTree::GetNumberOfCells
int GetNumberOfCells()
Returns the total number of cells in all the data sets.
vtkKdTree::RemoveAllDataSets
virtual void RemoveAllDataSets()
vtkKdTree::OmitZXPartitioning
void OmitZXPartitioning()
Omit partitions along the Z and X axes, yielding slabs along Y.
vtkKdTree::OmitXPartitioning
void OmitXPartitioning()
Omit partitions along the X axis, yielding shafts in the X direction.
vtkKdTree::_cellList::nRegions
int nRegions
Definition: vtkKdTree.h:798
vtkKdTree::NewPartitioningRequest
void NewPartitioningRequest(int req)
vtkKdTree::FudgeFactor
double FudgeFactor
Definition: vtkKdTree.h:900
vtkKdTree::_generateRepresentationWholeSpace
void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
vtkKdTree::IncludeRegionBoundaryCells
int IncludeRegionBoundaryCells
Definition: vtkKdTree.h:884
vtkKdTree::LocatorIds
int * LocatorIds
Definition: vtkKdTree.h:907
vtkKdTree::GetDataSetIndex
int GetDataSetIndex(vtkDataSet *set)
Return the index of the given data set.
vtkKdTree::AddDataSet
virtual void AddDataSet(vtkDataSet *set)
This class can compute a spatial decomposition based on the cells in a list of one or more input data...
vtkKdTree::_cellList::emptyList
vtkIdList * emptyList
Definition: vtkKdTree.h:801
vtkKdTree::ComputeCellCenter
void ComputeCellCenter(vtkDataSet *set, int cellId, float *center)
Get or compute the center of one cell.
vtkKdTree::PrintSelf
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
vtkKdTree::GetRegionContainingCell
int GetRegionContainingCell(vtkDataSet *set, vtkIdType cellID)
Get the id of the region containing the cell centroid.
vtkIdType
int vtkIdType
Definition: vtkType.h:287
vtkKdTree::_SetNewBounds
static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim)
vtkKdTree::_cellList::dataSet
vtkDataSet * dataSet
Definition: vtkKdTree.h:796
vtkKdTree::SetDataSet
void SetDataSet(vtkDataSet *set) override
This class can compute a spatial decomposition based on the cells in a list of one or more input data...
vtkKdTree::SetActualLevel
void SetActualLevel()
Definition: vtkKdTree.h:688
vtkKdTree::_cellList::cells
vtkIdList ** cells
Definition: vtkKdTree.h:799
vtkKdTree::FindPointsInArea
void FindPointsInArea(vtkKdNode *node, double *area, vtkIdTypeArray *ids)
vtkLocator.h
vtkKdTree::FoundId
static int FoundId(vtkIntArray *idArray, int id)
vtkKdTree::__printTree
static void __printTree(vtkKdNode *kd, int depth, int verbose)
vtkX3D::dir
@ dir
Definition: vtkX3D.h:324
vtkKdTree::AddNewRegions
static void AddNewRegions(vtkKdNode *kd, float *c1, int midpt, int dim, double coord)
vtkKdTree::FindClosestPointInSphere
int FindClosestPointInSphere(double x, double y, double z, double radius, int skipRegion, double &dist2)
vtkKdTree::LastInputDataInfo
double * LastInputDataInfo
Definition: vtkKdTree.h:920
vtkKdTree::PrintTree
void PrintTree()
Print out nodes of kd tree.
vtkKdTree::Select
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
vtkKdTree::LastNumPoints
vtkIdType * LastNumPoints
Definition: vtkKdTree.h:922
vtkX3D::center
@ center
Definition: vtkX3D.h:230
vtkKdTree::SearchNeighborsForDuplicate
int SearchNeighborsForDuplicate(int regionId, float *point, int **pointsSoFar, int *len, float tolerance, float tolerance2)
vtkKdTree::CellRegionList
int * CellRegionList
Definition: vtkKdTree.h:894
vtkKdTree::findRegion
static int findRegion(vtkKdNode *node, float x, float y, float z)
vtkKdTree::__ViewOrderRegionsFromPosition
static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double pos[3], int nextId)
vtkKdTree::GetDataSet
vtkDataSet * GetDataSet(int n)
Get the nth defined data set in the spatial partitioning.
vtkKdTree::LastBounds
double * LastBounds
Definition: vtkKdTree.h:921
vtkKdTree::RemoveDataSet
virtual void RemoveDataSet(int index)
Remove the given data set.
vtkKdTree::ProgressOffset
double ProgressOffset
Definition: vtkKdTree.h:763
vtkKdTree::ClearLastBuildCache
void ClearLastBuildCache()
vtkKdTree::_ViewOrderRegionsFromPosition
int _ViewOrderRegionsFromPosition(vtkIntArray *IdsOfInterest, const double pos[3], vtkIntArray *orderedList)
vtkKdTree::GetRegionsAtLevel
void GetRegionsAtLevel(int level, vtkKdNode **nodes)
Get back a list of the nodes at a specified level, nodes must be preallocated to hold 2^^(level) node...
vtkKdTree::ComputeCellCenter
void ComputeCellCenter(vtkCell *cell, double *center, double *weights)
vtkKdTree::_cellList::regionIds
int * regionIds
Definition: vtkKdTree.h:797
vtkKdTree::New
static vtkKdTree * New()
vtkKdTree::AllGetRegionContainingCell
int * AllGetRegionContainingCell()
Get a list (in order by data set by cell id) of the region IDs of the region containing the centroid ...
vtkKdTree::_GetRegionsAtLevel
static vtkKdNode ** _GetRegionsAtLevel(int level, vtkKdNode **nodes, vtkKdNode *kd)
vtkKdTree::GetRegionDataBounds
void GetRegionDataBounds(int regionID, double bounds[6])
Get the bounds of the data within the k-d tree region.
vtkLocator
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:70
vtkX3D::level
@ level
Definition: vtkX3D.h:395
vtkKdTree::CreateCellLists
void CreateCellLists(int dataSetIndex, int *regionReqList, int reqListSize)
Create a list for each of the requested regions, listing the IDs of all cells whose centroid falls in...
vtkKdTree::GetCellLists
vtkIdType GetCellLists(vtkIntArray *regions, vtkDataSet *set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
vtkKdTree::BuildLocator
void BuildLocator() override
Create the k-d tree decomposition of the cells of the data set or data sets.
vtkX3D::point
@ point
Definition: vtkX3D.h:236
vtkBSPIntersections
Perform calculations (mostly intersection calculations) on regions of a 3D binary spatial partitionin...
Definition: vtkBSPIntersections.h:46
vtkKdTree::SelectCutDirection
virtual int SelectCutDirection(vtkKdNode *kd)
vtkKdTree::ComputeCellCenters
float * ComputeCellCenters()
Compute and return a pointer to a list of all cell centers, in order by data set by cell Id.
vtkKdTree::FindMaxLeftHalf
static float FindMaxLeftHalf(int dim, float *c1, int K)
vtkKdTree::NumberOfRegionsOrMore
int NumberOfRegionsOrMore
Definition: vtkKdTree.h:882
vtkKdTree::Top
vtkKdNode * Top
Definition: vtkKdTree.h:679
vtkKdTree::SetInputDataInfo
void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3])
vtkKdTree::CreateCellLists
void CreateCellLists(int *regionReqList, int listSize)
vtkKdTree::InitializeCellLists
void InitializeCellLists()
vtkKdTree::GetRegionContainingCell
int GetRegionContainingCell(int set, vtkIdType cellID)
vtkKdTree::GetCellList
vtkIdList * GetCellList(int regionID)
Get the cell list for a region.
vtkKdTree::LocatorPoints
float * LocatorPoints
Definition: vtkKdTree.h:906
vtkKdTree::_FindClosestPointInRegion
int _FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
vtkKdTree::_cellList::boundaryCells
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:800
vtkKdTree::DoMedianFind
void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3)
vtkKdTree::NewParitioningRequest
void NewParitioningRequest(int req)
vtkCell
abstract class to specify cell behavior
Definition: vtkCell.h:60
vtkKdTree::SelfOrder
static int SelfOrder(int id, vtkKdNode *kd)
vtkKdTree::ValidDirections
int ValidDirections
Definition: vtkKdTree.h:677
vtkIndent
a simple class to control print indentation
Definition: vtkIndent.h:40
vtkKdTree::ComputeLevel
static int ComputeLevel(vtkKdNode *kd)
vtkCellArray
object to represent cell connectivity
Definition: vtkCellArray.h:51
vtkKdTree::SelfRegister
void SelfRegister(vtkKdNode *kd)
vtkIntArray
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:46
vtkKdTree::LastDataSetObserverTags
unsigned long * LastDataSetObserverTags
Definition: vtkKdTree.h:918
vtkKdTree::operator=
void operator=(const vtkKdTree &) VTK_DELETE_FUNCTION
vtkKdTree::SetDataBoundsToSpatialBounds
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
vtkKdTree::DivideRegion
int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels)
vtkKdTree::UpdateProgress
void UpdateProgress(double amount)
Modelled on vtkAlgorithm::UpdateProgress().
vtkKdTree::MinCells
int MinCells
Definition: vtkKdTree.h:896
vtkKdTree::NumberOfRegions
int NumberOfRegions
Definition: vtkKdTree.h:897
vtkBSPCuts
This class represents an axis-aligned Binary Spatial Partitioning of a 3D space.
Definition: vtkBSPCuts.h:45
vtkIdList
list of point or cell ids
Definition: vtkIdList.h:37
vtkKdTree::Progress
double Progress
Definition: vtkKdTree.h:926
vtkKdTree::_cellList
Definition: vtkKdTree.h:795
vtkKdTree::OmitXYPartitioning
void OmitXYPartitioning()
Omit partitions along the X and Y axes, yielding slabs along Z.
vtkKdTree::GetDataSet
vtkDataSet * GetDataSet() override
Return the 0'th data set.
Definition: vtkKdTree.h:234
vtkKdTree::SearchRegionForDuplicate
int SearchRegionForDuplicate(float *point, int *pointsSoFar, int len, float tolerance2)
vtkKdTree::GenerateRepresentationDataBounds
void GenerateRepresentationDataBounds(int level, vtkPolyData *pd)
vtkKdTree::LastInputDataSets
vtkDataSet ** LastInputDataSets
Definition: vtkKdTree.h:917
vtkKdTree::GenerateRepresentationUsingDataBounds
int GenerateRepresentationUsingDataBounds
Definition: vtkKdTree.h:887
vtkKdTree::OmitZPartitioning
void OmitZPartitioning()
Omit partitions along the Z axis, yielding shafts in the Z direction.
vtkKdTree::CopyKdNode
static void CopyKdNode(vtkKdNode *to, vtkKdNode *from)
vtkKdTree::vtkKdTree
vtkKdTree(const vtkKdTree &) VTK_DELETE_FUNCTION
vtkKdTree::LocatorRegionLocation
int * LocatorRegionLocation
Definition: vtkKdTree.h:908
vtkKdTree::LastNumDataSets
int LastNumDataSets
Definition: vtkKdTree.h:915
vtkKdTree::GetBoundaryCellList
vtkIdList * GetBoundaryCellList(int regionID)
The cell list obtained with GetCellList is the list of all cells such that their centroid is containe...
vtkKdTree::OmitNoPartitioning
void OmitNoPartitioning()
Partition along all three axes - this is the default.
vtkKdTree::RemoveDataSet
virtual void RemoveDataSet(vtkDataSet *set)
vtkKdTree::ProgressScale
double ProgressScale
Definition: vtkKdTree.h:754
vtkKdTree::GetCellLists
vtkIdType GetCellLists(vtkIntArray *regions, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
vtkKdTree::DataSets
vtkDataSetCollection * DataSets
Definition: vtkKdTree.h:740
vtkKdTree::SetCuts
void SetCuts(vtkBSPCuts *cuts)
Normally the k-d tree is computed from the dataset(s) provided in SetDataSet.
vtkX3D::spacing
@ spacing
Definition: vtkX3D.h:481
vtkDataSet
abstract class to specify dataset behavior
Definition: vtkDataSet.h:63
vtkKdTree::MaxWidth
float MaxWidth
Definition: vtkKdTree.h:910
vtkBooleanMacro
vtkBooleanMacro(IgnoreDriverBugs, bool)
Updates the extensions string.
vtkKdTree::LastDataSetType
int * LastDataSetType
Definition: vtkKdTree.h:919
vtkSetMacro
vtkSetMacro(IgnoreDriverBugs, bool)
Updates the extensions string.
vtkKdTree::UpdateSubOperationProgress
void UpdateSubOperationProgress(double amount)
vtkTimerLog
Timer support and logging.
Definition: vtkTimerLog.h:81
vtkKdTree::PrintRegion
void PrintRegion(int id)
Print out leaf node data for given id.
vtkIdTypeArray
dynamic, self-adjusting array of vtkIdType
Definition: vtkIdTypeArray.h:42
vtkKdTree::LastNumCells
vtkIdType * LastNumCells
Definition: vtkKdTree.h:923
vtkKdTree::GetDataSetsNumberOfCells
int GetDataSetsNumberOfCells(int set1, int set2)
Returns the total number of cells in data set 1 through data set 2.
vtkKdTree::FindPointsWithinRadius
void FindPointsWithinRadius(vtkKdNode *node, double R2, const double x[3], vtkIdList *ids)
vtkKdTree::_generateRepresentationDataBounds
void _generateRepresentationDataBounds(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
vtkPointSet
abstract class for specifying dataset behavior
Definition: vtkPointSet.h:43
vtkKdTree::NumberOfLocatorPoints
int NumberOfLocatorPoints
Definition: vtkKdTree.h:905
vtkKdTree::BuildRegionList
void BuildRegionList()
vtkKdTree::SetNewBounds
void SetNewBounds(double *bounds)
There are certain applications where you want the bounds of the k-d tree space to be at least as larg...
vtkKdTree::AddAllPointsInRegion
void AddAllPointsInRegion(vtkKdNode *node, vtkIdList *ids)
vtkPolyData
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:86
vtkKdTree::_Select
static void _Select(int dim, float *X, int *ids, int L, int R, int K)
vtkKdTree::AddAllPointsInRegion
void AddAllPointsInRegion(vtkKdNode *node, vtkIdTypeArray *ids)
vtkKdTree::PrintVerboseTree
void PrintVerboseTree()
vtkKdTree::GetRegionBounds
void GetRegionBounds(int regionID, double bounds[6])
Get the spatial bounds of k-d tree region.
vtkKdTree::ComputeCellCenter
void ComputeCellCenter(vtkDataSet *set, int cellId, double *center)
vtkKdTree
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:79
vtkKdTree::NumberOfRegionsOrLess
int NumberOfRegionsOrLess
Definition: vtkKdTree.h:881
vtkKdTree::GetRegionContainingPoint
int GetRegionContainingPoint(double x, double y, double z)
Get the id of the region containing the specified location.
vtkDataSetCollection
maintain an unordered list of dataset objects
Definition: vtkDataSetCollection.h:32
vtkKdTree::_ViewOrderRegionsInDirection
int _ViewOrderRegionsInDirection(vtkIntArray *IdsOfInterest, const double dop[3], vtkIntArray *orderedList)
vtkKdTree::__ViewOrderRegionsInDirection
static int __ViewOrderRegionsInDirection(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double dir[3], int nextId)
vtkKdTree::__ConvexSubRegions
static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes)
vtkKdTree::Cuts
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:925
vtkKdTree::ComputeCellCenters
float * ComputeCellCenters(int set)
vtkKdTree::DeleteCellLists
void DeleteCellLists()
Free the memory used by the cell lists.
vtkKdTree::findRegion
static int findRegion(vtkKdNode *node, double x, double y, double z)
vtkKdTree::GetRegionContainingCell
int GetRegionContainingCell(vtkIdType cellID)
vtkKdTree::LastDataCacheSize
int LastDataCacheSize
Definition: vtkKdTree.h:916
vtkKdTree::RegionList
vtkKdNode ** RegionList
Definition: vtkKdTree.h:680
vtkX3D::radius
@ radius
Definition: vtkX3D.h:252
vtkKdTree::OmitYZPartitioning
void OmitYZPartitioning()
Omit partitions along the Y and Z axes, yielding slabs along X.
vtkX3D::index
@ index
Definition: vtkX3D.h:246
vtkKdTree::CheckInputDataInfo
int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3])
vtkKdTree::_printTree
void _printTree(int verbose)
vtkKdTree::GetNumberOfDataSets
int GetNumberOfDataSets()
Get the number of data sets included in spatial paritioning.
vtkKdTree::Timing
int Timing
Definition: vtkKdTree.h:899
vtkKdTree::CreateCellLists
void CreateCellLists()
vtkKdTree::ZeroNumberOfPoints
static void ZeroNumberOfPoints(vtkKdNode *kd)
vtkKdTree::ComputeCellCenters
float * ComputeCellCenters(vtkDataSet *set)
vtkKdTree::GenerateRepresentationWholeSpace
void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd)
vtkKdTree::GetLeafNodeIds
static void GetLeafNodeIds(vtkKdNode *node, vtkIntArray *ids)
Adds to the vtkIntArray the list of region IDs of all leaf nodes in the given node.
vtkKdTree::MidValue
static int MidValue(int dim, float *c1, int nvals, double &coord)
vtkKdTree::DeleteAllDescendants
static void DeleteAllDescendants(vtkKdNode *nd)