VTK  9.3.0
vtkKdTree.h
Go to the documentation of this file.
1 // SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
2 // SPDX-FileCopyrightText: Copyright (c) Sandia Corporation
3 // SPDX-License-Identifier: BSD-3-Clause
4 
56 #ifndef vtkKdTree_h
57 #define vtkKdTree_h
58 
59 #include "vtkCommonDataModelModule.h" // For export macro
60 #include "vtkLocator.h"
61 
62 VTK_ABI_NAMESPACE_BEGIN
63 class vtkTimerLog;
64 class vtkIdList;
65 class vtkIdTypeArray;
66 class vtkIntArray;
67 class vtkPointSet;
68 class vtkPoints;
69 class vtkCellArray;
70 class vtkCell;
71 class vtkKdNode;
72 class vtkBSPCuts;
75 
76 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
77 {
78 public:
79  vtkTypeMacro(vtkKdTree, vtkLocator);
80  void PrintSelf(ostream& os, vtkIndent indent) override;
81 
82  static vtkKdTree* New();
83 
85 
88  vtkBooleanMacro(Timing, vtkTypeBool);
89  vtkSetMacro(Timing, vtkTypeBool);
90  vtkGetMacro(Timing, vtkTypeBool);
92 
94 
97  vtkSetMacro(MinCells, int);
98  vtkGetMacro(MinCells, int);
100 
108  vtkGetMacro(NumberOfRegionsOrLess, int);
109  vtkSetMacro(NumberOfRegionsOrLess, int);
110 
118  vtkGetMacro(NumberOfRegionsOrMore, int);
119  vtkSetMacro(NumberOfRegionsOrMore, int);
120 
128  vtkGetMacro(FudgeFactor, double);
129  vtkSetMacro(FudgeFactor, double);
130 
136  vtkGetObjectMacro(Cuts, vtkBSPCuts);
137 
144  void SetCuts(vtkBSPCuts* cuts);
145 
150 
155 
160 
165 
170 
175 
180 
195  void SetDataSet(vtkDataSet* set) override;
196 
201  virtual void AddDataSet(vtkDataSet* set);
202 
204 
207  virtual void RemoveDataSet(int index);
208  virtual void RemoveDataSet(vtkDataSet* set);
209  virtual void RemoveAllDataSets();
211 
216 
227 
232  vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
233 
235 
238  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
240 
246 
251  void GetBounds(double* bounds);
252 
261  void SetNewBounds(double* bounds);
262 
264 
267  vtkGetMacro(NumberOfRegions, int);
269 
273  void GetRegionBounds(int regionID, double bounds[6]);
274 
278  void GetRegionDataBounds(int regionID, double bounds[6]);
279 
281 
284  void PrintTree();
287 
291  void PrintRegion(int id);
292 
305  void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
306  void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
307  void CreateCellLists(int* regionReqList, int listSize);
309 
311 
318  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
319  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
320  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
322 
327 
332  vtkIdList* GetCellList(int regionID);
333 
345 
347 
368  vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
370  vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
372  vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
374 
376 
383  int GetRegionContainingCell(int set, vtkIdType cellID);
386 
396 
400  int GetRegionContainingPoint(double x, double y, double z);
401 
407  void BuildLocator() override;
408 
412  void ForceBuildLocator() 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 
641  void BuildLocatorInternal() override;
642 
645 
647 
648  int ProcessUserDefinedCuts(double* bounds);
649 
650  void SetCuts(vtkBSPCuts* cuts, int userDefined);
651 
658 
666  int DivideTest(int numberOfPoints, int level);
667 
668  enum
669  {
670  XDIM = 0, // don't change these values
671  YDIM = 1,
672  ZDIM = 2
673  };
674 
676 
678  vtkKdNode** RegionList; // indexed by region ID
679 
681 
682  static void DeleteAllDescendants(vtkKdNode* nd);
683 
685  virtual int SelectCutDirection(vtkKdNode* kd);
686  void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
687 
693  void GetRegionsAtLevel(int level, vtkKdNode** nodes);
694 
700  static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
701 
707 
713  int GetDataSetsNumberOfCells(int set1, int set2);
714 
721  void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
722  void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
723 
734  float* ComputeCellCenters(int set);
736 
738 
744  void UpdateProgress(double amount);
745 
747 
750  vtkSetClampMacro(Progress, double, 0.0, 1.0);
751  vtkGetMacro(Progress, double);
753 
754  // So that each suboperation can report progress
755  // in [0,1], yet we will be able to report a global
756  // progress. Sub-operations must use UpdateSubOperationProgress()
757  // for this to work.
760 
761  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
762  // Actual progress is given by
763  // (this->ProgressOffset + this->ProgressScale* amount).
764  void UpdateSubOperationProgress(double amount);
765 
766  static void SetNewBounds_(vtkKdNode* kd, double* b, int* fixDim);
767  static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
768  static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
770  static void ZeroNumberOfPoints(vtkKdNode* kd);
771 
772  // Recursive helper for public FindPointsWithinRadius
773  void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
774 
775  // Recursive helper for public FindPointsWithinRadius
777 
778  // Recursive helper for public FindPointsInArea
779  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
780 
781  // Recursive helper for public FindPointsInArea
783 
784  int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
785 
786  void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
787 
789 
790  struct cellList_
791  {
792  vtkDataSet* dataSet; // cell lists for which data set
793  int* regionIds; // nullptr if listing all regions
794  int nRegions;
798  };
799 
801  vtkIdList* GetList(int regionId, vtkIdList** which);
802 
803  void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
804 
807  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
808 
811  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
812 
813  void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
814 
815  void printTree_(int verbose);
816 
818  int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
819 
820  int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
821 
822  int FindClosestPointInRegion_(int regionId, double x, double y, double z, double& dist2);
823 
825  double x, double y, double z, double radius, int skipRegion, double& dist2);
826 
828  vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
829 
831  vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
832 
834  vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
835 
837  vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
838 
839  static int ConvexSubRegions_(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
840  static int FoundId(vtkIntArray* idArray, int id);
841 
842  void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
843  int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
845 
846  static void printTree_P(vtkKdNode* kd, int depth, int verbose);
847 
848  static int MidValue(int dim, float* c1, int nvals, double& coord);
849 
850  static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
851  static float FindMaxLeftHalf(int dim, float* c1, int K);
852  static void Select_(int dim, float* X, int* ids, int L, int R, int K);
853 
854  static int ComputeLevel(vtkKdNode* kd);
855  static int SelfOrder(int id, vtkKdNode* kd);
856  static int findRegion(vtkKdNode* node, float x, float y, float z);
857  static int findRegion(vtkKdNode* node, double x, double y, double z);
858 
859  static vtkKdNode** GetRegionsAtLevel_(int level, vtkKdNode** nodes, vtkKdNode* kd);
860 
861  static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
862 
863  void NewPartitioningRequest(int req);
864 
867 
869  double CellBoundsCache[6]; // to optimize IntersectsCell()
870 
871  vtkTypeBool GenerateRepresentationUsingDataBounds;
872 
873  struct cellList_ CellList;
874 
875  // Region Ids, by data set by cell id - this list is large (one
876  // int per cell) but accelerates creation of cell lists
877 
879 
880  int MinCells;
881  int NumberOfRegions; // number of leaf nodes
882 
884  double FudgeFactor; // a very small distance, relative to the dataset's size
885 
886  // These instance variables are used by the special locator created
887  // to find duplicate points. (BuildLocatorFromPoints)
888 
893 
894  float MaxWidth;
895 
896  // These Last* values are here to save state so we can
897  // determine later if k-d tree must be rebuilt.
898 
902  unsigned long* LastDataSetObserverTags;
905  double* LastBounds;
908 
910  double Progress;
911 
912  vtkKdTree(const vtkKdTree&) = delete;
913  void operator=(const vtkKdTree&) = delete;
914 };
915 VTK_ABI_NAMESPACE_END
916 #endif
This class represents an axis-aligned Binary Spatial Partitioning of a 3D space.
Definition: vtkBSPCuts.h:31
Perform calculations (mostly intersection calculations) on regions of a 3D binary spatial partitionin...
object to represent cell connectivity
Definition: vtkCellArray.h:185
abstract class to specify cell behavior
Definition: vtkCell.h:59
maintain an unordered list of dataset objects
abstract class to specify dataset behavior
Definition: vtkDataSet.h:62
list of point or cell ids
Definition: vtkIdList.h:32
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:38
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:44
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
Definition: vtkKdNode.h:32
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:77
void SelfRegister(vtkKdNode *kd)
void NewPartitioningRequest(int req)
void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3])
virtual void RemoveAllDataSets()
Remove the given data set.
static vtkKdNode * CopyTree(vtkKdNode *kd)
Create a copy of the binary tree representation of the k-d tree spatial partitioning provided.
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:903
vtkTypeBool Timing
Definition: vtkKdTree.h:883
int DivideRegion(vtkKdNode *kd, float *c1, int *ids, int nlevels)
static void CopyKdNode(vtkKdNode *to, vtkKdNode *from)
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:737
void CreateCellLists(int *regionReqList, int listSize)
int ValidDirections
Definition: vtkKdTree.h:675
vtkIdType FindPoint(double x, double y, double z)
Find the Id of the point that was previously supplied to BuildLocatorFromPoints().
int NumberOfRegions
Definition: vtkKdTree.h:881
int GetRegionContainingCell(vtkIdType cellID)
Get the id of the region containing the cell centroid.
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:868
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)
For a list of regions, get two cell lists.
int LastDataCacheSize
Definition: vtkKdTree.h:900
float MaxWidth
Definition: vtkKdTree.h:894
vtkIdType GetCellLists(vtkIntArray *regions, int set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
For a list of regions, get two cell lists.
void BuildRegionList()
void OmitNoPartitioning()
Partition along all three axes - this is the default.
void BuildLocatorInternal() override
This function is not pure virtual to maintain backwards compatibility.
int GetNumberOfCells()
Returns the total number of cells in all the data sets.
void GenerateRepresentationDataBounds(int level, vtkPolyData *pd)
void printTree_(int verbose)
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:865
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:901
static int ViewOrderRegionsInDirection_P(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double dir[3], int nextId)
void ComputeCellCenter(vtkCell *cell, double *center, double *weights)
double * LastInputDataInfo
Definition: vtkKdTree.h:904
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:909
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:643
void SetCuts(vtkBSPCuts *cuts, int userDefined)
vtkKdNode ** RegionList
Definition: vtkKdTree.h:678
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:899
static float FindMaxLeftHalf(int dim, float *c1, int K)
int * LocatorRegionLocation
Definition: vtkKdTree.h:892
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)
Remove the given data 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:906
void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
void ClearLastBuildCache()
static int ViewOrderRegionsFromPosition_P(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double pos[3], int nextId)
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:889
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
double * LastBounds
Definition: vtkKdTree.h:905
int GetNumberOfDataSets()
Get the number of data sets included in spatial partitioning.
static int ComputeLevel(vtkKdNode *kd)
int GetRegionContainingCell(int set, vtkIdType cellID)
Get the id of the region containing the cell centroid.
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:866
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 FoundId(vtkIntArray *idArray, int id)
double ProgressScale
Definition: vtkKdTree.h:751
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:891
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:759
void ComputeCellCenter(vtkDataSet *set, int cellId, double *center)
void BuildLocatorFromPoints(vtkPoints **ptArray, int numPtArrays)
This is a special purpose locator that builds a k-d tree to find duplicate and near-by points.
static void Select_(int dim, float *X, int *ids, int L, int R, int K)
void operator=(const vtkKdTree &)=delete
void BuildLocator() override
Create the k-d tree decomposition of the cells of the data set or data sets.
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:686
static vtkKdNode ** GetRegionsAtLevel_(int level, vtkKdNode **nodes, vtkKdNode *kd)
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()
Print out nodes of kd tree.
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:910
int ViewOrderRegionsInDirection_(vtkIntArray *IdsOfInterest, const double dop[3], vtkIntArray *orderedList)
static int MidValue(int dim, float *c1, int nvals, double &coord)
int UserDefinedCuts
Definition: vtkKdTree.h:644
virtual int SelectCutDirection(vtkKdNode *kd)
~vtkKdTree() override
vtkIdType FindClosestPoint(double x, double y, double z, double &dist2)
Find the Id of the point that was previously supplied to BuildLocatorFromPoints() which is closest to...
vtkDataSet * GetDataSet() override
Return the 0'th data set.
Definition: vtkKdTree.h:232
int MinCells
Definition: vtkKdTree.h:880
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:884
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)
static void printTree_P(vtkKdNode *kd, int depth, int verbose)
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,...
int ViewOrderRegionsFromPosition_(vtkIntArray *IdsOfInterest, const double pos[3], vtkIntArray *orderedList)
vtkTimerLog * TimerLog
Definition: vtkKdTree.h:680
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:902
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:878
int ViewOrderAllRegionsInDirection(const double directionOfProjection[3], vtkIntArray *orderedList)
Given a direction of projection (typically obtained with vtkCamera::GetDirectionOfProjection()),...
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.
static void SetNewBounds_(vtkKdNode *kd, double *b, int *fixDim)
vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
Find the Id of the point in the given region which is closest to the given point.
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.
static int ConvexSubRegions_(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes)
void OmitXYPartitioning()
Omit partitions along the X and Y axes, yielding slabs along Z.
void BuildLocatorFromPoints(vtkPoints *ptArray)
This is a special purpose locator that builds a k-d tree to find duplicate and near-by points.
void GenerateRepresentationWholeSpace(int level, vtkPolyData *pd)
int SearchRegionForDuplicate(float *point, int *pointsSoFar, int len, float tolerance2)
static void DeleteAllDescendants(vtkKdNode *nd)
void ForceBuildLocator() override
Build the locator from the input dataset (even if UseExistingSearchStructure is on).
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)
For a list of regions, get two cell lists.
vtkIdType * LastNumCells
Definition: vtkKdTree.h:907
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:677
int FindClosestPointInRegion_(int regionId, double x, double y, double z, double &dist2)
int GetDataSetIndex(vtkDataSet *set)
Return the index of the given data set.
float * LocatorPoints
Definition: vtkKdTree.h:890
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:68
concrete class for storing a set of points
Definition: vtkPointSet.h:68
represent and manipulate 3D points
Definition: vtkPoints.h:38
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:89
Timer support and logging.
Definition: vtkTimerLog.h:94
@ point
Definition: vtkX3D.h:236
@ level
Definition: vtkX3D.h:395
@ dir
Definition: vtkX3D.h:324
@ center
Definition: vtkX3D.h:230
@ spacing
Definition: vtkX3D.h:481
@ radius
Definition: vtkX3D.h:252
@ index
Definition: vtkX3D.h:246
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:796
vtkIdList ** cells
Definition: vtkKdTree.h:795
vtkIdList * emptyList
Definition: vtkKdTree.h:797
vtkDataSet * dataSet
Definition: vtkKdTree.h:792
int vtkTypeBool
Definition: vtkABI.h:64
int vtkIdType
Definition: vtkType.h:315