VTK  9.3.20240329
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 
96 #ifndef vtkKdTree_h
97 #define vtkKdTree_h
98 
99 #include "vtkCommonDataModelModule.h" // For export macro
100 #include "vtkLocator.h"
101 
102 VTK_ABI_NAMESPACE_BEGIN
103 class vtkTimerLog;
104 class vtkIdList;
105 class vtkIdTypeArray;
106 class vtkIntArray;
107 class vtkPointSet;
108 class vtkPoints;
109 class vtkCellArray;
110 class vtkCell;
111 class vtkKdNode;
112 class vtkBSPCuts;
113 class vtkBSPIntersections;
115 
116 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
117 {
118 public:
119  vtkTypeMacro(vtkKdTree, vtkLocator);
120  void PrintSelf(ostream& os, vtkIndent indent) override;
121 
122  static vtkKdTree* New();
123 
125 
128  vtkBooleanMacro(Timing, vtkTypeBool);
129  vtkSetMacro(Timing, vtkTypeBool);
130  vtkGetMacro(Timing, vtkTypeBool);
132 
134 
137  vtkSetMacro(MinCells, int);
138  vtkGetMacro(MinCells, int);
140 
148  vtkGetMacro(NumberOfRegionsOrLess, int);
149  vtkSetMacro(NumberOfRegionsOrLess, int);
150 
158  vtkGetMacro(NumberOfRegionsOrMore, int);
159  vtkSetMacro(NumberOfRegionsOrMore, int);
160 
168  vtkGetMacro(FudgeFactor, double);
169  vtkSetMacro(FudgeFactor, double);
170 
176  vtkGetObjectMacro(Cuts, vtkBSPCuts);
177 
184  void SetCuts(vtkBSPCuts* cuts);
185 
190 
195 
200 
205 
210 
215 
220 
235  void SetDataSet(vtkDataSet* set) override;
236 
241  virtual void AddDataSet(vtkDataSet* set);
242 
244 
247  virtual void RemoveDataSet(int index);
248  virtual void RemoveDataSet(vtkDataSet* set);
249  virtual void RemoveAllDataSets();
251 
256 
267 
272  vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
273 
275 
278  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
280 
286 
291  void GetBounds(double* bounds);
292 
301  void SetNewBounds(double* bounds);
302 
304 
307  vtkGetMacro(NumberOfRegions, int);
309 
313  void GetRegionBounds(int regionID, double bounds[6]);
314 
318  void GetRegionDataBounds(int regionID, double bounds[6]);
319 
321 
324  void PrintTree();
327 
331  void PrintRegion(int id);
332 
345  void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
346  void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
347  void CreateCellLists(int* regionReqList, int listSize);
349 
351 
358  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
359  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
360  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
362 
367 
372  vtkIdList* GetCellList(int regionID);
373 
385 
387 
408  vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
410  vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
412  vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
414 
416 
423  int GetRegionContainingCell(int set, vtkIdType cellID);
426 
436 
440  int GetRegionContainingPoint(double x, double y, double z);
441 
447  void BuildLocator() override;
448 
452  void ForceBuildLocator() override;
453 
468  int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
469 
478  const double directionOfProjection[3], vtkIntArray* orderedList);
479 
488  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
489 
498  const double directionOfProjection[3], vtkIntArray* orderedList);
499 
508  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
509 
511 
526  void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
528 
544 
546 
551  vtkIdType FindPoint(double* x);
552  vtkIdType FindPoint(double x, double y, double z);
554 
556 
561  vtkIdType FindClosestPoint(double* x, double& dist2);
562  vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
564 
570  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
571 
573 
578  vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
579  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
581 
588  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
589 
598  void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
599 
605 
610  void FreeSearchStructure() override;
611 
617  void GenerateRepresentation(int level, vtkPolyData* pd) override;
618 
623  void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
624 
626 
632  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
633  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
634  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
636 
640  virtual void PrintTiming(ostream& os, vtkIndent indent);
641 
646  virtual int NewGeometry();
647 
653  virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
654 
660  virtual void InvalidateGeometry();
661 
668 
675  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
676 
677 protected:
679  ~vtkKdTree() override;
680 
681  void BuildLocatorInternal() override;
682 
685 
687 
688  int ProcessUserDefinedCuts(double* bounds);
689 
690  void SetCuts(vtkBSPCuts* cuts, int userDefined);
691 
698 
706  int DivideTest(int numberOfPoints, int level);
707 
708  enum
709  {
710  XDIM = 0, // don't change these values
711  YDIM = 1,
712  ZDIM = 2
713  };
714 
716 
718  vtkKdNode** RegionList; // indexed by region ID
719 
721 
722  static void DeleteAllDescendants(vtkKdNode* nd);
723 
725  virtual int SelectCutDirection(vtkKdNode* kd);
726  void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
727 
733  void GetRegionsAtLevel(int level, vtkKdNode** nodes);
734 
740  static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
741 
747 
753  int GetDataSetsNumberOfCells(int set1, int set2);
754 
761  void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
762  void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
763 
774  float* ComputeCellCenters(int set);
776 
778 
784  void UpdateProgress(double amount);
785 
787 
790  vtkSetClampMacro(Progress, double, 0.0, 1.0);
791  vtkGetMacro(Progress, double);
793 
794  // So that each suboperation can report progress
795  // in [0,1], yet we will be able to report a global
796  // progress. Sub-operations must use UpdateSubOperationProgress()
797  // for this to work.
800 
801  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
802  // Actual progress is given by
803  // (this->ProgressOffset + this->ProgressScale* amount).
804  void UpdateSubOperationProgress(double amount);
805 
806  static void SetNewBounds_(vtkKdNode* kd, double* b, int* fixDim);
807  static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
808  static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
810  static void ZeroNumberOfPoints(vtkKdNode* kd);
811 
812  // Recursive helper for public FindPointsWithinRadius
813  void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
814 
815  // Recursive helper for public FindPointsWithinRadius
817 
818  // Recursive helper for public FindPointsInArea
819  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
820 
821  // Recursive helper for public FindPointsInArea
823 
824  int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
825 
826  void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
827 
829 
830  struct cellList_
831  {
832  vtkDataSet* dataSet; // cell lists for which data set
833  int* regionIds; // nullptr if listing all regions
834  int nRegions;
838  };
839 
841  vtkIdList* GetList(int regionId, vtkIdList** which);
842 
843  void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
844 
847  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
848 
851  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
852 
853  void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
854 
855  void printTree_(int verbose);
856 
858  int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
859 
860  int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
861 
862  int FindClosestPointInRegion_(int regionId, double x, double y, double z, double& dist2);
863 
865  double x, double y, double z, double radius, int skipRegion, double& dist2);
866 
868  vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
869 
871  vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
872 
874  vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
875 
877  vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
878 
879  static int ConvexSubRegions_(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
880  static int FoundId(vtkIntArray* idArray, int id);
881 
882  void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
883  int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
885 
886  static void printTree_P(vtkKdNode* kd, int depth, int verbose);
887 
888  static int MidValue(int dim, float* c1, int nvals, double& coord);
889 
890  static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
891  static float FindMaxLeftHalf(int dim, float* c1, int K);
892  static void Select_(int dim, float* X, int* ids, int L, int R, int K);
893 
894  static int ComputeLevel(vtkKdNode* kd);
895  static int SelfOrder(int id, vtkKdNode* kd);
896  static int findRegion(vtkKdNode* node, float x, float y, float z);
897  static int findRegion(vtkKdNode* node, double x, double y, double z);
898 
899  static vtkKdNode** GetRegionsAtLevel_(int level, vtkKdNode** nodes, vtkKdNode* kd);
900 
901  static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
902 
903  void NewPartitioningRequest(int req);
904 
907 
909  double CellBoundsCache[6]; // to optimize IntersectsCell()
910 
911  vtkTypeBool GenerateRepresentationUsingDataBounds;
912 
913  struct cellList_ CellList;
914 
915  // Region Ids, by data set by cell id - this list is large (one
916  // int per cell) but accelerates creation of cell lists
917 
919 
920  int MinCells;
921  int NumberOfRegions; // number of leaf nodes
922 
924  double FudgeFactor; // a very small distance, relative to the dataset's size
925 
926  // These instance variables are used by the special locator created
927  // to find duplicate points. (BuildLocatorFromPoints)
928 
933 
934  float MaxWidth;
935 
936  // These Last* values are here to save state so we can
937  // determine later if k-d tree must be rebuilt.
938 
942  unsigned long* LastDataSetObserverTags;
945  double* LastBounds;
948 
950  double Progress;
951 
952  vtkKdTree(const vtkKdTree&) = delete;
953  void operator=(const vtkKdTree&) = delete;
954 };
955 VTK_ABI_NAMESPACE_END
956 #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:286
abstract class to specify cell behavior
Definition: vtkCell.h:130
maintain an unordered list of dataset objects
abstract class to specify dataset behavior
Definition: vtkDataSet.h:166
list of point or cell ids
Definition: vtkIdList.h:133
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:108
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:144
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:117
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:943
vtkTypeBool Timing
Definition: vtkKdTree.h:923
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:777
void CreateCellLists(int *regionReqList, int listSize)
int ValidDirections
Definition: vtkKdTree.h:715
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:921
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:908
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:940
float MaxWidth
Definition: vtkKdTree.h:934
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:905
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:941
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:944
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:949
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:683
void SetCuts(vtkBSPCuts *cuts, int userDefined)
vtkKdNode ** RegionList
Definition: vtkKdTree.h:718
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:939
static float FindMaxLeftHalf(int dim, float *c1, int K)
int * LocatorRegionLocation
Definition: vtkKdTree.h:932
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:946
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:929
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
double * LastBounds
Definition: vtkKdTree.h:945
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:906
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:791
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:931
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:799
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:726
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:950
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:684
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:272
int MinCells
Definition: vtkKdTree.h:920
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:924
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:720
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:942
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:918
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:947
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:717
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:930
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:78
concrete class for storing a set of points
Definition: vtkPointSet.h:98
represent and manipulate 3D points
Definition: vtkPoints.h:139
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:181
Timer support and logging.
Definition: vtkTimerLog.h:174
@ 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:836
vtkIdList ** cells
Definition: vtkKdTree.h:835
vtkIdList * emptyList
Definition: vtkKdTree.h:837
vtkDataSet * dataSet
Definition: vtkKdTree.h:832
int vtkTypeBool
Definition: vtkABI.h:64
int vtkIdType
Definition: vtkType.h:315