VTK  9.0.2
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 
62 #ifndef vtkKdTree_h
63 #define vtkKdTree_h
64 
65 #include "vtkCommonDataModelModule.h" // For export macro
66 #include "vtkLocator.h"
67 
68 class vtkTimerLog;
69 class vtkIdList;
70 class vtkIdTypeArray;
71 class vtkIntArray;
72 class vtkPointSet;
73 class vtkPoints;
74 class vtkCellArray;
75 class vtkCell;
76 class vtkKdNode;
77 class vtkBSPCuts;
80 
81 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
82 {
83 public:
84  vtkTypeMacro(vtkKdTree, vtkLocator);
85  void PrintSelf(ostream& os, vtkIndent indent) override;
86 
87  static vtkKdTree* New();
88 
90 
93  vtkBooleanMacro(Timing, vtkTypeBool);
94  vtkSetMacro(Timing, vtkTypeBool);
95  vtkGetMacro(Timing, vtkTypeBool);
97 
99 
102  vtkSetMacro(MinCells, int);
103  vtkGetMacro(MinCells, int);
105 
113  vtkGetMacro(NumberOfRegionsOrLess, int);
114  vtkSetMacro(NumberOfRegionsOrLess, int);
115 
123  vtkGetMacro(NumberOfRegionsOrMore, int);
124  vtkSetMacro(NumberOfRegionsOrMore, int);
125 
133  vtkGetMacro(FudgeFactor, double);
134  vtkSetMacro(FudgeFactor, double);
135 
141  vtkGetObjectMacro(Cuts, vtkBSPCuts);
142 
149  void SetCuts(vtkBSPCuts* cuts);
150 
155 
160 
165 
170 
175 
180 
185 
200  void SetDataSet(vtkDataSet* set) override;
201 
206  virtual void AddDataSet(vtkDataSet* set);
207 
209 
212  virtual void RemoveDataSet(int index);
213  virtual void RemoveDataSet(vtkDataSet* set);
214  virtual void RemoveAllDataSets();
216 
221 
232 
237  vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
238 
240 
243  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
245 
251 
256  void GetBounds(double* bounds);
257 
266  void SetNewBounds(double* bounds);
267 
269 
272  vtkGetMacro(NumberOfRegions, int);
274 
278  void GetRegionBounds(int regionID, double bounds[6]);
279 
283  void GetRegionDataBounds(int regionID, double bounds[6]);
284 
286 
289  void PrintTree();
292 
296  void PrintRegion(int id);
297 
310  void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
311  void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
312  void CreateCellLists(int* regionReqList, int listSize);
314 
316 
323  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
324  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
325  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
327 
332 
337  vtkIdList* GetCellList(int regionID);
338 
350 
352 
373  vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
375  vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
377  vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
379 
381 
388  int GetRegionContainingCell(int set, vtkIdType cellID);
391 
401 
405  int GetRegionContainingPoint(double x, double y, double z);
406 
412  void BuildLocator() override;
413 
428  int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
429 
438  const double directionOfProjection[3], vtkIntArray* orderedList);
439 
448  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
449 
458  const double directionOfProjection[3], vtkIntArray* orderedList);
459 
468  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
469 
471 
486  void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
488 
504 
506 
511  vtkIdType FindPoint(double* x);
512  vtkIdType FindPoint(double x, double y, double z);
514 
516 
521  vtkIdType FindClosestPoint(double* x, double& dist2);
522  vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
524 
530  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
531 
533 
538  vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
539  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
541 
548  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
549 
558  void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
559 
565 
570  void FreeSearchStructure() override;
571 
577  void GenerateRepresentation(int level, vtkPolyData* pd) override;
578 
583  void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
584 
586 
592  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
593  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
594  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
596 
600  virtual void PrintTiming(ostream& os, vtkIndent indent);
601 
606  virtual int NewGeometry();
607 
613  virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
614 
620  virtual void InvalidateGeometry();
621 
628 
635  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
636 
637 protected:
639  ~vtkKdTree() override;
640 
643 
645 
646  int ProcessUserDefinedCuts(double* bounds);
647 
648  void SetCuts(vtkBSPCuts* cuts, int userDefined);
649 
656 
664  int DivideTest(int numberOfPoints, int level);
665 
666  enum
667  {
668  XDIM = 0, // don't change these values
669  YDIM = 1,
670  ZDIM = 2
671  };
672 
674 
676  vtkKdNode** RegionList; // indexed by region ID
677 
679 
680  static void DeleteAllDescendants(vtkKdNode* nd);
681 
683  virtual int SelectCutDirection(vtkKdNode* kd);
684  void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
685 
691  void GetRegionsAtLevel(int level, vtkKdNode** nodes);
692 
698  static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
699 
705 
711  int GetDataSetsNumberOfCells(int set1, int set2);
712 
719  void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
720  void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
721 
732  float* ComputeCellCenters(int set);
734 
736 
742  void UpdateProgress(double amount);
743 
745 
748  vtkSetClampMacro(Progress, double, 0.0, 1.0);
749  vtkGetMacro(Progress, double);
751 
752 protected:
753  // So that each suboperation can report progress
754  // in [0,1], yet we will be able to report a global
755  // progress. Sub-operations must use UpdateSubOperationProgress()
756  // for this to work.
759 
760  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
761  // Actual progress is given by
762  // (this->ProgressOffset + this->ProgressScale* amount).
763  void UpdateSubOperationProgress(double amount);
764 
765  static void _SetNewBounds(vtkKdNode* kd, double* b, int* fixDim);
766  static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
767  static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
769  static void ZeroNumberOfPoints(vtkKdNode* kd);
770 
771  // Recursive helper for public FindPointsWithinRadius
772  void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
773 
774  // Recursive helper for public FindPointsWithinRadius
776 
777  // Recursive helper for public FindPointsInArea
778  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
779 
780  // Recursive helper for public FindPointsInArea
782 
783  int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
784 
785  void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
786 
788 
789  struct _cellList
790  {
791  vtkDataSet* dataSet; // cell lists for which data set
792  int* regionIds; // nullptr if listing all regions
793  int nRegions;
797  };
798 
800  vtkIdList* GetList(int regionId, vtkIdList** which);
801 
802  void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
803 
806  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
807 
810  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
811 
812  void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
813 
814  void _printTree(int verbose);
815 
817  int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
818 
819  int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
820 
821  int _FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
822 
824  double x, double y, double z, double radius, int skipRegion, double& dist2);
825 
827  vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
828 
830  vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
831 
833  vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
834 
836  vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
837 
838  static int __ConvexSubRegions(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
839  static int FoundId(vtkIntArray* idArray, int id);
840 
841  void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
842  int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
844 
845  static void __printTree(vtkKdNode* kd, int depth, int verbose);
846 
847  static int MidValue(int dim, float* c1, int nvals, double& coord);
848 
849  static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
850  static float FindMaxLeftHalf(int dim, float* c1, int K);
851  static void _Select(int dim, float* X, int* ids, int L, int R, int K);
852 
853  static int ComputeLevel(vtkKdNode* kd);
854  static int SelfOrder(int id, vtkKdNode* kd);
855  static int findRegion(vtkKdNode* node, float x, float y, float z);
856  static int findRegion(vtkKdNode* node, double x, double y, double z);
857 
858  static vtkKdNode** _GetRegionsAtLevel(int level, vtkKdNode** nodes, vtkKdNode* kd);
859 
860  static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
861 
862  void NewPartitioningRequest(int req);
863 
866 
868  double CellBoundsCache[6]; // to optimize IntersectsCell()
869 
870  vtkTypeBool GenerateRepresentationUsingDataBounds;
871 
872  struct _cellList CellList;
873 
874  // Region Ids, by data set by cell id - this list is large (one
875  // int per cell) but accelerates creation of cell lists
876 
878 
879  int MinCells;
880  int NumberOfRegions; // number of leaf nodes
881 
883  double FudgeFactor; // a very small distance, relative to the dataset's size
884 
885  // These instance variables are used by the special locator created
886  // to find duplicate points. (BuildLocatorFromPoints)
887 
892 
893  float MaxWidth;
894 
895  // These Last* values are here to save state so we can
896  // determine later if k-d tree must be rebuilt.
897 
901  unsigned long* LastDataSetObserverTags;
904  double* LastBounds;
907 
909  double Progress;
910 
911  vtkKdTree(const vtkKdTree&) = delete;
912  void operator=(const vtkKdTree&) = delete;
913 };
914 #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:82
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:902
vtkTypeBool Timing
Definition: vtkKdTree.h:882
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:735
void CreateCellLists(int *regionReqList, int listSize)
int ValidDirections
Definition: vtkKdTree.h:673
vtkIdType FindPoint(double x, double y, double z)
int NumberOfRegions
Definition: vtkKdTree.h:880
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:867
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:899
float MaxWidth
Definition: vtkKdTree.h:893
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:864
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:900
void ComputeCellCenter(vtkCell *cell, double *center, double *weights)
double * LastInputDataInfo
Definition: vtkKdTree.h:903
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:908
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:641
void SetCuts(vtkBSPCuts *cuts, int userDefined)
vtkKdNode ** RegionList
Definition: vtkKdTree.h:676
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:898
static float FindMaxLeftHalf(int dim, float *c1, int K)
int * LocatorRegionLocation
Definition: vtkKdTree.h:891
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:905
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:888
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:904
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:865
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:749
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:890
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:758
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:684
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:909
static int MidValue(int dim, float *c1, int nvals, double &coord)
int UserDefinedCuts
Definition: vtkKdTree.h:642
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:237
static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double pos[3], int nextId)
int MinCells
Definition: vtkKdTree.h:879
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:883
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:678
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:901
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:877
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:906
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:675
int GetDataSetIndex(vtkDataSet *set)
Return the index of the given data set.
float * LocatorPoints
Definition: vtkKdTree.h:889
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:795
vtkIdList * emptyList
Definition: vtkKdTree.h:796
vtkIdList ** cells
Definition: vtkKdTree.h:794
vtkDataSet * dataSet
Definition: vtkKdTree.h:791
int vtkTypeBool
Definition: vtkABI.h:69
int vtkIdType
Definition: vtkType.h:338