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) override;
83 
84  static vtkKdTree *New();
85 
87 
90  vtkBooleanMacro(Timing, vtkTypeBool);
91  vtkSetMacro(Timing, vtkTypeBool);
92  vtkGetMacro(Timing, vtkTypeBool);
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) 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() 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, vtkTypeBool);
323  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
324  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
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() override;
412 
428  double **convexRegionBounds);
429 
437  int ViewOrderAllRegionsInDirection(const double directionOfProjection[3],
438  vtkIntArray *orderedList);
439 
448  const double directionOfProjection[3],
449  vtkIntArray *orderedList);
450 
458  int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3],
459  vtkIntArray *orderedList);
460 
469  const double directionOfProjection[3],
470  vtkIntArray *orderedList);
471 
473 
488  void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays);
490 
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 
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 
569 
574  void FreeSearchStructure() override;
575 
581  void GenerateRepresentation(int level, vtkPolyData *pd) override;
582 
587  void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd);
588 
590 
596  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
597  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
598  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
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 
632 
639  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
640 
641 protected:
642 
644  ~vtkKdTree() override;
645 
648 
650 
651  int ProcessUserDefinedCuts(double *bounds);
652 
653  void SetCuts(vtkBSPCuts *cuts, int userDefined);
654 
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; // nullptr 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 SetInputDataInfo(int i,
854  int dims[3], double origin[3], double spacing[3]);
856  int dims[3], double origin[3], double spacing[3]);
858 
859  static void __printTree(vtkKdNode *kd, int depth, int verbose);
860 
861  static int MidValue(int dim, float *c1, int nvals, double &coord);
862 
863  static int Select(int dim, float *c1, int *ids, int nvals, double &coord);
864  static float FindMaxLeftHalf(int dim, float *c1, int K);
865  static void _Select(int dim, float *X, int *ids, int L, int R, int K);
866 
867  static int ComputeLevel(vtkKdNode *kd);
868  static int SelfOrder(int id, vtkKdNode *kd);
869  static int findRegion(vtkKdNode *node, float x, float y, float z);
870  static int findRegion(vtkKdNode *node, double x, double y, double z);
871 
873  vtkKdNode *kd);
874 
875  static void AddNewRegions(vtkKdNode *kd, float *c1,
876  int midpt, int dim, double coord);
877 
878  void NewPartitioningRequest(int req);
879 
882 
884  double CellBoundsCache[6]; // to optimize IntersectsCell()
885 
887 
888  struct _cellList CellList;
889 
890  // Region Ids, by data set by cell id - this list is large (one
891  // int per cell) but accelerates creation of cell lists
892 
894 
895  int MinCells;
896  int NumberOfRegions; // number of leaf nodes
897 
899  double FudgeFactor; // a very small distance, relative to the dataset's size
900 
901  // These instance variables are used by the special locator created
902  // to find duplicate points. (BuildLocatorFromPoints)
903 
908 
909  float MaxWidth;
910 
911  // These Last* values are here to save state so we can
912  // determine later if k-d tree must be rebuilt.
913 
917  unsigned long *LastDataSetObserverTags;
920  double *LastBounds;
923 
925  double Progress;
926 
927  vtkKdTree(const vtkKdTree&) = delete;
928  void operator=(const vtkKdTree&) = delete;
929 };
930 #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::PrintTiming
virtual void PrintTiming(ostream &os, vtkIndent indent)
Print timing of k-d tree build.
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:899
vtkKdTree::_generateRepresentationWholeSpace
void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
vtkKdTree::LocatorIds
int * LocatorIds
Definition: vtkKdTree.h:906
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::FindPointsWithinRadius
void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result)
Find all points within a specified radius R of position x.
vtkKdTree::GetRegionContainingCell
int GetRegionContainingCell(vtkDataSet *set, vtkIdType cellID)
Get the id of the region containing the cell centroid.
vtkIdType
int vtkIdType
Definition: vtkType.h:347
vtkKdTree::FindPoint
vtkIdType FindPoint(double *x)
Find the Id of the point that was previously supplied to BuildLocatorFromPoints().
vtkKdTree::BuildMapForDuplicatePoints
vtkIdTypeArray * BuildMapForDuplicatePoints(float tolerance)
This call returns a mapping from the original point IDs supplied to BuildLocatorFromPoints to a subse...
vtkKdTree::_SetNewBounds
static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim)
vtkKdTree::InvalidateGeometry
virtual void InvalidateGeometry()
Forget about the last geometry used.
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::ViewOrderAllRegionsInDirection
int ViewOrderAllRegionsInDirection(const double directionOfProjection[3], vtkIntArray *orderedList)
Given a direction of projection (typically obtained with vtkCamera::GetDirectionOfProjection()),...
vtkKdTree::FoundId
static int FoundId(vtkIntArray *idArray, int id)
vtkKdTree::ViewOrderAllRegionsFromPosition
int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3], vtkIntArray *orderedList)
Given a camera position (typically obtained with vtkCamera::GetPosition()), this method,...
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:919
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:921
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:893
vtkKdTree::findRegion
static int findRegion(vtkKdNode *node, float x, float y, float z)
vtkKdTree::GenerateRepresentation
void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd)
Generate a polygonal representation of a list of regions.
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:920
vtkKdTree::FindClosestPoint
vtkIdType FindClosestPoint(double x, double y, double z, double &dist2)
vtkKdTree::RemoveDataSet
virtual void RemoveDataSet(int index)
Remove the given data set.
vtkKdTree::FindPoint
vtkIdType FindPoint(double x, double y, double z)
vtkKdTree::DivideTest
int DivideTest(int numberOfPoints, int level)
Prior to dividing a region at level "level", of size "numberOfPoints", apply the tests implied by Min...
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::FreeSearchStructure
void FreeSearchStructure() override
Delete the k-d tree data structure.
vtkKdTree::New
static vtkKdTree * New()
vtkKdTree::vtkKdTree
vtkKdTree()
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
vtkKdTree::GenerateRepresentation
void GenerateRepresentation(int level, vtkPolyData *pd) override
Create a polydata representation of the boundaries of the k-d tree regions.
vtkKdTree::FindPointsInArea
void FindPointsInArea(double *area, vtkIdTypeArray *ids, bool clearArray=true)
Fill ids with points found in area.
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:881
vtkKdTree::Top
vtkKdNode * Top
Definition: vtkKdTree.h:679
vtkKdTree::SetInputDataInfo
void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3])
vtkKdTree::BuildLocatorFromPoints
void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays)
vtkKdTree::FindClosestPointWithinRadius
vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double &dist2)
Given a position x and a radius r, return the id of the point closest to the point in that radius.
vtkKdTree::CreateCellLists
void CreateCellLists(int *regionReqList, int listSize)
vtkKdTree::InitializeCellLists
void InitializeCellLists()
vtkKdTree::ProcessUserDefinedCuts
int ProcessUserDefinedCuts(double *bounds)
vtkKdTree::GetRegionContainingCell
int GetRegionContainingCell(int set, vtkIdType cellID)
vtkKdTree::vtkKdTree
vtkKdTree(const vtkKdTree &)=delete
vtkKdTree::GetCellList
vtkIdList * GetCellList(int regionID)
Get the cell list for a region.
vtkKdTree::LocatorPoints
float * LocatorPoints
Definition: vtkKdTree.h:905
vtkKdTree::_FindClosestPointInRegion
int _FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
vtkKdTree::_cellList::boundaryCells
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:800
vtkKdTree::Timing
vtkTypeBool Timing
Definition: vtkKdTree.h:898
vtkKdTree::DoMedianFind
void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3)
vtkKdTree::BSPCalculator
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:646
vtkCell
abstract class to specify cell behavior
Definition: vtkCell.h:60
vtkKdTree::SelfOrder
static int SelfOrder(int id, vtkKdNode *kd)
vtkKdTree::CopyTree
static vtkKdNode * CopyTree(vtkKdNode *kd)
Create a copy of the binary tree representation of the k-d tree spatial partitioning provided.
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:917
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:895
vtkKdTree::NumberOfRegions
int NumberOfRegions
Definition: vtkKdTree.h:896
vtkKdTree::GenerateRepresentationUsingDataBounds
vtkTypeBool GenerateRepresentationUsingDataBounds
Definition: vtkKdTree.h:886
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::UpdateBuildTime
void UpdateBuildTime()
Save enough state so NewGeometry() can work, and update the BuildTime time stamp.
vtkKdTree::BuildLocatorFromPoints
void BuildLocatorFromPoints(vtkPoints *ptArray)
vtkKdTree::Progress
double Progress
Definition: vtkKdTree.h:925
vtkKdTree::_cellList
Definition: vtkKdTree.h:795
vtkKdTree::~vtkKdTree
~vtkKdTree() override
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::BuildLocatorFromPoints
void BuildLocatorFromPoints(vtkPointSet *pointset)
This is a special purpose locator that builds a k-d tree to find duplicate and near-by points.
vtkKdTree::FindClosestNPoints
void FindClosestNPoints(int N, const double x[3], vtkIdList *result)
Find the closest N points to a position.
vtkKdTree::LastInputDataSets
vtkDataSet ** LastInputDataSets
Definition: vtkKdTree.h:916
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::LocatorRegionLocation
int * LocatorRegionLocation
Definition: vtkKdTree.h:907
vtkKdTree::LastNumDataSets
int LastNumDataSets
Definition: vtkKdTree.h:914
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:909
vtkKdTree::NewGeometry
virtual int NewGeometry(vtkDataSet **sets, int numDataSets)
Return 1 if the geometry of these data sets differs for the geometry of the last data sets used to bu...
vtkKdTree::LastDataSetType
int * LastDataSetType
Definition: vtkKdTree.h:918
vtkKdTree::UpdateSubOperationProgress
void UpdateSubOperationProgress(double amount)
vtkTimerLog
Timer support and logging.
Definition: vtkTimerLog.h:92
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:922
vtkKdTree::GetDataSetsNumberOfCells
int GetDataSetsNumberOfCells(int set1, int set2)
Returns the total number of cells in data set 1 through data set 2.
vtkKdTree::IncludeRegionBoundaryCells
vtkTypeBool IncludeRegionBoundaryCells
Definition: vtkKdTree.h:883
vtkKdTree::FindPointsWithinRadius
void FindPointsWithinRadius(vtkKdNode *node, double R2, const double x[3], vtkIdList *ids)
vtkKdTree::SetCuts
void SetCuts(vtkBSPCuts *cuts, int userDefined)
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:904
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::FindClosestPointInRegion
vtkIdType FindClosestPointInRegion(int regionId, double *x, double &dist2)
Find the Id of the point in the given region which is closest to the given point.
vtkKdTree::MinimalNumberOfConvexSubRegions
int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList, double **convexRegionBounds)
Given a list of region IDs, determine the decomposition of these regions into the minimal number of c...
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:880
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:924
vtkKdTree::ComputeCellCenters
float * ComputeCellCenters(int set)
vtkKdTree::FindClosestPointInRegion
vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
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:915
vtkKdTree::RegionList
vtkKdNode ** RegionList
Definition: vtkKdTree.h:680
vtkKdTree::ViewOrderRegionsFromPosition
int ViewOrderRegionsFromPosition(vtkIntArray *regionIds, const double directionOfProjection[3], vtkIntArray *orderedList)
Given a camera position and a list of k-d tree region IDs, this method, creates a list of the k-d tre...
vtkKdTree::operator=
void operator=(const vtkKdTree &)=delete
vtkKdTree::NewGeometry
virtual int NewGeometry()
Return 1 if the geometry of the input data sets has changed since the last time the k-d tree was buil...
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::SetCalculator
void SetCalculator(vtkKdNode *kd)
vtkKdTree::GetPointsInRegion
vtkIdTypeArray * GetPointsInRegion(int regionId)
Get a list of the original IDs of all points in a region.
vtkKdTree::_printTree
void _printTree(int verbose)
vtkKdTree::GetNumberOfDataSets
int GetNumberOfDataSets()
Get the number of data sets included in spatial partitioning.
vtkKdTree::FindClosestPoint
vtkIdType FindClosestPoint(double *x, double &dist2)
Find the Id of the point that was previously supplied to BuildLocatorFromPoints() which is closest to...
vtkKdTree::CreateCellLists
void CreateCellLists()
vtkTypeBool
int vtkTypeBool
Definition: vtkABI.h:69
vtkKdTree::ViewOrderRegionsInDirection
int ViewOrderRegionsInDirection(vtkIntArray *regionIds, const double directionOfProjection[3], vtkIntArray *orderedList)
Given a direction of projection and a list of k-d tree region IDs, this method, creates a list of the...
vtkKdTree::ZeroNumberOfPoints
static void ZeroNumberOfPoints(vtkKdNode *kd)
vtkKdTree::ComputeCellCenters
float * ComputeCellCenters(vtkDataSet *set)
vtkKdTree::GenerateRepresentationWholeSpace
void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd)
vtkKdTree::UserDefinedCuts
int UserDefinedCuts
Definition: vtkKdTree.h:647
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)