VTK  9.0.1
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 
56 #ifndef vtkKdTree_h
57 #define vtkKdTree_h
58 
59 #include "vtkCommonDataModelModule.h" // For export macro
60 #include "vtkLocator.h"
61 
62 class vtkTimerLog;
63 class vtkIdList;
64 class vtkIdTypeArray;
65 class vtkIntArray;
66 class vtkPointSet;
67 class vtkPoints;
68 class vtkCellArray;
69 class vtkCell;
70 class vtkKdNode;
71 class vtkBSPCuts;
74 
75 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
76 {
77 public:
78  vtkTypeMacro(vtkKdTree, vtkLocator);
79  void PrintSelf(ostream& os, vtkIndent indent) override;
80 
81  static vtkKdTree* New();
82 
84 
87  vtkBooleanMacro(Timing, vtkTypeBool);
88  vtkSetMacro(Timing, vtkTypeBool);
89  vtkGetMacro(Timing, vtkTypeBool);
91 
93 
96  vtkSetMacro(MinCells, int);
97  vtkGetMacro(MinCells, int);
99 
107  vtkGetMacro(NumberOfRegionsOrLess, int);
108  vtkSetMacro(NumberOfRegionsOrLess, int);
109 
117  vtkGetMacro(NumberOfRegionsOrMore, int);
118  vtkSetMacro(NumberOfRegionsOrMore, int);
119 
127  vtkGetMacro(FudgeFactor, double);
128  vtkSetMacro(FudgeFactor, double);
129 
135  vtkGetObjectMacro(Cuts, vtkBSPCuts);
136 
143  void SetCuts(vtkBSPCuts* cuts);
144 
149 
154 
159 
164 
169 
174 
179 
194  void SetDataSet(vtkDataSet* set) override;
195 
200  virtual void AddDataSet(vtkDataSet* set);
201 
203 
206  virtual void RemoveDataSet(int index);
207  virtual void RemoveDataSet(vtkDataSet* set);
208  virtual void RemoveAllDataSets();
210 
215 
226 
231  vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
232 
234 
237  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
239 
245 
250  void GetBounds(double* bounds);
251 
260  void SetNewBounds(double* bounds);
261 
263 
266  vtkGetMacro(NumberOfRegions, int);
268 
272  void GetRegionBounds(int regionID, double bounds[6]);
273 
277  void GetRegionDataBounds(int regionID, double bounds[6]);
278 
280 
283  void PrintTree();
286 
290  void PrintRegion(int id);
291 
304  void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
305  void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
306  void CreateCellLists(int* regionReqList, int listSize);
308 
310 
317  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
318  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
319  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
321 
326 
331  vtkIdList* GetCellList(int regionID);
332 
344 
346 
367  vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
369  vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
371  vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
373 
375 
382  int GetRegionContainingCell(int set, vtkIdType cellID);
385 
395 
399  int GetRegionContainingPoint(double x, double y, double z);
400 
406  void BuildLocator() override;
407 
422  int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
423 
432  const double directionOfProjection[3], vtkIntArray* orderedList);
433 
442  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
443 
452  const double directionOfProjection[3], vtkIntArray* orderedList);
453 
462  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
463 
465 
480  void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
482 
498 
500 
505  vtkIdType FindPoint(double* x);
506  vtkIdType FindPoint(double x, double y, double z);
508 
510 
515  vtkIdType FindClosestPoint(double* x, double& dist2);
516  vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
518 
524  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
525 
527 
532  vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
533  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
535 
542  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
543 
552  void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
553 
559 
564  void FreeSearchStructure() override;
565 
571  void GenerateRepresentation(int level, vtkPolyData* pd) override;
572 
577  void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
578 
580 
586  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
587  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
588  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
590 
594  virtual void PrintTiming(ostream& os, vtkIndent indent);
595 
600  virtual int NewGeometry();
601 
607  virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
608 
614  virtual void InvalidateGeometry();
615 
622 
629  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
630 
631 protected:
633  ~vtkKdTree() override;
634 
637 
639 
640  int ProcessUserDefinedCuts(double* bounds);
641 
642  void SetCuts(vtkBSPCuts* cuts, int userDefined);
643 
650 
658  int DivideTest(int numberOfPoints, int level);
659 
660  enum
661  {
662  XDIM = 0, // don't change these values
663  YDIM = 1,
664  ZDIM = 2
665  };
666 
668 
670  vtkKdNode** RegionList; // indexed by region ID
671 
673 
674  static void DeleteAllDescendants(vtkKdNode* nd);
675 
677  virtual int SelectCutDirection(vtkKdNode* kd);
678  void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
679 
685  void GetRegionsAtLevel(int level, vtkKdNode** nodes);
686 
692  static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
693 
699 
705  int GetDataSetsNumberOfCells(int set1, int set2);
706 
713  void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
714  void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
715 
726  float* ComputeCellCenters(int set);
728 
730 
736  void UpdateProgress(double amount);
737 
739 
742  vtkSetClampMacro(Progress, double, 0.0, 1.0);
743  vtkGetMacro(Progress, double);
745 
746 protected:
747  // So that each suboperation can report progress
748  // in [0,1], yet we will be able to report a global
749  // progress. Sub-operations must use UpdateSubOperationProgress()
750  // for this to work.
753 
754  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
755  // Actual progress is given by
756  // (this->ProgressOffset + this->ProgressScale* amount).
757  void UpdateSubOperationProgress(double amount);
758 
759  static void _SetNewBounds(vtkKdNode* kd, double* b, int* fixDim);
760  static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
761  static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
763  static void ZeroNumberOfPoints(vtkKdNode* kd);
764 
765  // Recursive helper for public FindPointsWithinRadius
766  void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
767 
768  // Recursive helper for public FindPointsWithinRadius
770 
771  // Recursive helper for public FindPointsInArea
772  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
773 
774  // Recursive helper for public FindPointsInArea
776 
777  int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
778 
779  void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
780 
782 
783  struct _cellList
784  {
785  vtkDataSet* dataSet; // cell lists for which data set
786  int* regionIds; // nullptr if listing all regions
787  int nRegions;
791  };
792 
794  vtkIdList* GetList(int regionId, vtkIdList** which);
795 
796  void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
797 
800  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
801 
804  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
805 
806  void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
807 
808  void _printTree(int verbose);
809 
811  int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
812 
813  int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
814 
815  int _FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
816 
818  double x, double y, double z, double radius, int skipRegion, double& dist2);
819 
821  vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
822 
824  vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
825 
827  vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
828 
830  vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
831 
832  static int __ConvexSubRegions(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
833  static int FoundId(vtkIntArray* idArray, int id);
834 
835  void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
836  int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
838 
839  static void __printTree(vtkKdNode* kd, int depth, int verbose);
840 
841  static int MidValue(int dim, float* c1, int nvals, double& coord);
842 
843  static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
844  static float FindMaxLeftHalf(int dim, float* c1, int K);
845  static void _Select(int dim, float* X, int* ids, int L, int R, int K);
846 
847  static int ComputeLevel(vtkKdNode* kd);
848  static int SelfOrder(int id, vtkKdNode* kd);
849  static int findRegion(vtkKdNode* node, float x, float y, float z);
850  static int findRegion(vtkKdNode* node, double x, double y, double z);
851 
852  static vtkKdNode** _GetRegionsAtLevel(int level, vtkKdNode** nodes, vtkKdNode* kd);
853 
854  static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
855 
856  void NewPartitioningRequest(int req);
857 
860 
862  double CellBoundsCache[6]; // to optimize IntersectsCell()
863 
864  vtkTypeBool GenerateRepresentationUsingDataBounds;
865 
866  struct _cellList CellList;
867 
868  // Region Ids, by data set by cell id - this list is large (one
869  // int per cell) but accelerates creation of cell lists
870 
872 
873  int MinCells;
874  int NumberOfRegions; // number of leaf nodes
875 
877  double FudgeFactor; // a very small distance, relative to the dataset's size
878 
879  // These instance variables are used by the special locator created
880  // to find duplicate points. (BuildLocatorFromPoints)
881 
886 
887  float MaxWidth;
888 
889  // These Last* values are here to save state so we can
890  // determine later if k-d tree must be rebuilt.
891 
895  unsigned long* LastDataSetObserverTags;
898  double* LastBounds;
901 
903  double Progress;
904 
905  vtkKdTree(const vtkKdTree&) = delete;
906  void operator=(const vtkKdTree&) = delete;
907 };
908 #endif
This class represents an axis-aligned Binary Spatial Partitioning of a 3D space.
Definition: vtkBSPCuts.h:45
Perform calculations (mostly intersection calculations) on regions of a 3D binary spatial partitionin...
object to represent cell connectivity
Definition: vtkCellArray.h:180
abstract class to specify cell behavior
Definition: vtkCell.h:57
maintain an unordered list of dataset objects
abstract class to specify dataset behavior
Definition: vtkDataSet.h:57
list of point or cell ids
Definition: vtkIdList.h:31
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:34
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:40
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
Definition: vtkKdNode.h:43
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:76
void SelfRegister(vtkKdNode *kd)
void NewPartitioningRequest(int req)
void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3])
virtual void RemoveAllDataSets()
static vtkKdNode * CopyTree(vtkKdNode *kd)
Create a copy of the binary tree representation of the k-d tree spatial partitioning provided.
static void __printTree(vtkKdNode *kd, int depth, int verbose)
float * ComputeCellCenters()
Compute and return a pointer to a list of all cell centers, in order by data set by cell Id.
int * LastDataSetType
Definition: vtkKdTree.h:896
vtkTypeBool Timing
Definition: vtkKdTree.h:876
int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels)
static void CopyKdNode(vtkKdNode *to, vtkKdNode *from)
static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim)
int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList, double **convexRegionBounds)
Given a list of region IDs, determine the decomposition of these regions into the minimal number of c...
float * ComputeCellCenters(int set)
vtkDataSetCollection * DataSets
Definition: vtkKdTree.h:729
void CreateCellLists(int *regionReqList, int listSize)
int ValidDirections
Definition: vtkKdTree.h:667
vtkIdType FindPoint(double x, double y, double z)
int NumberOfRegions
Definition: vtkKdTree.h:874
int GetRegionContainingCell(vtkIdType cellID)
void GetRegionDataBounds(int regionID, double bounds[6])
Get the bounds of the data within the k-d tree region.
void InitializeCellLists()
virtual void InvalidateGeometry()
Forget about the last geometry used.
void OmitYZPartitioning()
Omit partitions along the Y and Z axes, yielding slabs along X.
vtkTypeBool IncludeRegionBoundaryCells
Definition: vtkKdTree.h:861
static int SelfOrder(int id, vtkKdNode *kd)
void OmitZXPartitioning()
Omit partitions along the Z and X axes, yielding slabs along Y.
vtkIdType GetCellLists(vtkIntArray *regions, vtkDataSet *set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
int LastDataCacheSize
Definition: vtkKdTree.h:893
float MaxWidth
Definition: vtkKdTree.h:887
vtkIdType GetCellLists(vtkIntArray *regions, int set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
For a list of regions, get two cell lists.
void BuildRegionList()
int _ViewOrderRegionsInDirection(vtkIntArray *IdsOfInterest, const double dop[3], vtkIntArray *orderedList)
void OmitNoPartitioning()
Partition along all three axes - this is the default.
static vtkKdNode ** _GetRegionsAtLevel(int level, vtkKdNode **nodes, vtkKdNode *kd)
void _printTree(int verbose)
int GetNumberOfCells()
Returns the total number of cells in all the data sets.
void GenerateRepresentationDataBounds(int level, vtkPolyData *pd)
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...
int NumberOfRegionsOrLess
Definition: vtkKdTree.h:858
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
void UpdateSubOperationProgress(double amount)
vtkIdTypeArray * BuildMapForDuplicatePoints(float tolerance)
This call returns a mapping from the original point IDs supplied to BuildLocatorFromPoints to a subse...
vtkIdTypeArray * GetPointsInRegion(int regionId)
Get a list of the original IDs of all points in a region.
void CreateCellLists()
vtkDataSet ** LastInputDataSets
Definition: vtkKdTree.h:894
void ComputeCellCenter(vtkCell *cell, double *center, double *weights)
double * LastInputDataInfo
Definition: vtkKdTree.h:897
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:902
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:635
void SetCuts(vtkBSPCuts *cuts, int userDefined)
vtkKdNode ** RegionList
Definition: vtkKdTree.h:670
int SearchNeighborsForDuplicate(int regionId, float *point, int **pointsSoFar, int *len, float tolerance, float tolerance2)
void GenerateRepresentation(int level, vtkPolyData *pd) override
Create a polydata representation of the boundaries of the k-d tree regions.
void AddAllPointsInRegion(vtkKdNode *node, vtkIdList *ids)
int LastNumDataSets
Definition: vtkKdTree.h:892
static float FindMaxLeftHalf(int dim, float *c1, int K)
int * LocatorRegionLocation
Definition: vtkKdTree.h:885
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...
vtkIdList * GetList(int regionId, vtkIdList **which)
void PrintTree()
Print out nodes of kd tree.
void FreeSearchStructure() override
Delete the k-d tree data structure.
virtual void RemoveDataSet(vtkDataSet *set)
int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3])
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...
static int findRegion(vtkKdNode *node, float x, float y, float z)
void DeleteCellLists()
Free the memory used by the cell lists.
vtkIdType * LastNumPoints
Definition: vtkKdTree.h:899
void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
void ClearLastBuildCache()
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.
void OmitYPartitioning()
Omit partitions along the Y axis, yielding shafts in the Y direction.
void GetBounds(double *bounds)
Get the spatial bounds of the entire k-d tree space.
int NumberOfLocatorPoints
Definition: vtkKdTree.h:882
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
static void _Select(int dim, float *X, int *ids, int L, int R, int K)
double * LastBounds
Definition: vtkKdTree.h:898
int GetNumberOfDataSets()
Get the number of data sets included in spatial partitioning.
static int ComputeLevel(vtkKdNode *kd)
int GetRegionContainingCell(int set, vtkIdType cellID)
static int findRegion(vtkKdNode *node, double x, double y, double z)
void UpdateProgress(double amount)
Modelled on vtkAlgorithm::UpdateProgress().
void FindPointsWithinRadius(double R, const double x[3], vtkIdList *result)
Find all points within a specified radius R of position x.
int NumberOfRegionsOrMore
Definition: vtkKdTree.h:859
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...
int ProcessUserDefinedCuts(double *bounds)
static void AddNewRegions(vtkKdNode *kd, float *c1, int midpt, int dim, double coord)
static int __ViewOrderRegionsInDirection(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double dir[3], int nextId)
static int FoundId(vtkIntArray *idArray, int id)
double ProgressScale
Definition: vtkKdTree.h:743
void OmitZPartitioning()
Omit partitions along the Z axis, yielding shafts in the Z direction.
void AddAllPointsInRegion(vtkKdNode *node, vtkIdTypeArray *ids)
void GenerateRepresentation(int *regionList, int len, vtkPolyData *pd)
Generate a polygonal representation of a list of regions.
int * LocatorIds
Definition: vtkKdTree.h:884
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...
void FindPointsWithinRadius(vtkKdNode *node, double R2, const double x[3], vtkIdList *ids)
double ProgressOffset
Definition: vtkKdTree.h:752
void ComputeCellCenter(vtkDataSet *set, int cellId, double *center)
void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays)
void operator=(const vtkKdTree &)=delete
void BuildLocator() override
Create the k-d tree decomposition of the cells of the data set or data sets.
int _ViewOrderRegionsFromPosition(vtkIntArray *IdsOfInterest, const double pos[3], vtkIntArray *orderedList)
vtkIdList * GetBoundaryCellList(int regionID)
The cell list obtained with GetCellList is the list of all cells such that their centroid is containe...
void SetActualLevel()
Definition: vtkKdTree.h:678
void _generateRepresentationDataBounds(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
void BuildLocatorFromPoints(vtkPointSet *pointset)
This is a special purpose locator that builds a k-d tree to find duplicate and near-by points.
void PrintVerboseTree()
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.
vtkIdType FindClosestPoint(double *x, double &dist2)
Find the Id of the point that was previously supplied to BuildLocatorFromPoints() which is closest to...
double Progress
Definition: vtkKdTree.h:903
static int MidValue(int dim, float *c1, int nvals, double &coord)
int UserDefinedCuts
Definition: vtkKdTree.h:636
virtual int SelectCutDirection(vtkKdNode *kd)
~vtkKdTree() override
vtkIdType FindClosestPoint(double x, double y, double z, double &dist2)
vtkDataSet * GetDataSet() override
Return the 0'th data set.
Definition: vtkKdTree.h:231
static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double pos[3], int nextId)
int MinCells
Definition: vtkKdTree.h:873
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...
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...
double FudgeFactor
Definition: vtkKdTree.h:877
int * AllGetRegionContainingCell()
Get a list (in order by data set by cell id) of the region IDs of the region containing the centroid ...
void ComputeCellCenter(vtkDataSet *set, int cellId, float *center)
Get or compute the center of one cell.
void CreateCellLists(vtkDataSet *set, int *regionReqList, int reqListSize)
virtual void PrintTiming(ostream &os, vtkIndent indent)
Print timing of k-d tree build.
void FindPointsInArea(vtkKdNode *node, double *area, vtkIdTypeArray *ids)
vtkDataSet * GetDataSet(int n)
Get the nth defined data set in the spatial partitioning.
void UpdateBuildTime()
Save enough state so NewGeometry() can work, and update the BuildTime time stamp.
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...
int FindClosestPointInSphere(double x, double y, double z, double radius, int skipRegion, double &dist2)
void PrintSelf(ostream &os, vtkIndent indent) override
Methods invoked by print to print information about the object including superclasses.
void SetCalculator(vtkKdNode *kd)
vtkIdList * GetCellList(int regionID)
Get the cell list for a region.
static vtkKdTree * New()
vtkKdTree(const vtkKdTree &)=delete
int GetRegionContainingCell(vtkDataSet *set, vtkIdType cellID)
Get the id of the region containing the cell centroid.
int ViewOrderAllRegionsFromPosition(const double directionOfProjection[3], vtkIntArray *orderedList)
Given a camera position (typically obtained with vtkCamera::GetPosition()), this method,...
vtkTimerLog * TimerLog
Definition: vtkKdTree.h:672
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...
unsigned long * LastDataSetObserverTags
Definition: vtkKdTree.h:895
void OmitXPartitioning()
Omit partitions along the X axis, yielding shafts in the X direction.
static void GetLeafNodeIds(vtkKdNode *node, vtkIntArray *ids)
Adds to the vtkIntArray the list of region IDs of all leaf nodes in the given node.
int * CellRegionList
Definition: vtkKdTree.h:871
int ViewOrderAllRegionsInDirection(const double directionOfProjection[3], vtkIntArray *orderedList)
Given a direction of projection (typically obtained with vtkCamera::GetDirectionOfProjection()),...
static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes)
int _FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3)
void PrintRegion(int id)
Print out leaf node data for given id.
vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
int DivideTest(int numberOfPoints, int level)
Prior to dividing a region at level "level", of size "numberOfPoints", apply the tests implied by Min...
float * ComputeCellCenters(vtkDataSet *set)
virtual void RemoveDataSet(int index)
Remove the given data set.
void OmitXYPartitioning()
Omit partitions along the X and Y axes, yielding slabs along Z.
void BuildLocatorFromPoints(vtkPoints *ptArray)
void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd)
int SearchRegionForDuplicate(float *point, int *pointsSoFar, int len, float tolerance2)
static void DeleteAllDescendants(vtkKdNode *nd)
void AddPolys(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys)
vtkIdType FindPoint(double *x)
Find the Id of the point that was previously supplied to BuildLocatorFromPoints().
vtkIdType GetCellLists(vtkIntArray *regions, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
vtkIdType * LastNumCells
Definition: vtkKdTree.h:900
void GetRegionBounds(int regionID, double bounds[6])
Get the spatial bounds of k-d tree region.
int GetRegionContainingPoint(double x, double y, double z)
Get the id of the region containing the specified location.
int GetDataSetsNumberOfCells(int set1, int set2)
Returns the total number of cells in data set 1 through data set 2.
void SetCuts(vtkBSPCuts *cuts)
Normally the k-d tree is computed from the dataset(s) provided in SetDataSet.
void FindPointsInArea(double *area, vtkIdTypeArray *ids, bool clearArray=true)
Fill ids with points found in area.
void FindClosestNPoints(int N, const double x[3], vtkIdList *result)
Find the closest N points to a position.
static void ZeroNumberOfPoints(vtkKdNode *kd)
vtkKdNode * Top
Definition: vtkKdTree.h:669
int GetDataSetIndex(vtkDataSet *set)
Return the index of the given data set.
float * LocatorPoints
Definition: vtkKdTree.h:883
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:70
abstract class for specifying dataset behavior
Definition: vtkPointSet.h:63
represent and manipulate 3D points
Definition: vtkPoints.h:34
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:85
Timer support and logging.
Definition: vtkTimerLog.h:91
@ point
Definition: vtkX3D.h:242
@ level
Definition: vtkX3D.h:401
@ dir
Definition: vtkX3D.h:330
@ center
Definition: vtkX3D.h:236
@ spacing
Definition: vtkX3D.h:487
@ radius
Definition: vtkX3D.h:258
@ index
Definition: vtkX3D.h:252
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:789
vtkIdList * emptyList
Definition: vtkKdTree.h:790
vtkIdList ** cells
Definition: vtkKdTree.h:788
vtkDataSet * dataSet
Definition: vtkKdTree.h:785
int vtkTypeBool
Definition: vtkABI.h:69
int vtkIdType
Definition: vtkType.h:338