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 
47 #ifndef vtkKdTree_h
48 #define vtkKdTree_h
49 
50 #include "vtkCommonDataModelModule.h" // For export macro
51 #include "vtkLocator.h"
52 
53 VTK_ABI_NAMESPACE_BEGIN
54 class vtkTimerLog;
55 class vtkIdList;
56 class vtkIdTypeArray;
57 class vtkIntArray;
58 class vtkPointSet;
59 class vtkPoints;
60 class vtkCellArray;
61 class vtkCell;
62 class vtkKdNode;
63 class vtkBSPCuts;
66 
67 class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
68 {
69 public:
70  vtkTypeMacro(vtkKdTree, vtkLocator);
71  void PrintSelf(ostream& os, vtkIndent indent) override;
72 
73  static vtkKdTree* New();
74 
76 
79  vtkBooleanMacro(Timing, vtkTypeBool);
80  vtkSetMacro(Timing, vtkTypeBool);
81  vtkGetMacro(Timing, vtkTypeBool);
83 
85 
88  vtkSetMacro(MinCells, int);
89  vtkGetMacro(MinCells, int);
91 
99  vtkGetMacro(NumberOfRegionsOrLess, int);
100  vtkSetMacro(NumberOfRegionsOrLess, int);
101 
109  vtkGetMacro(NumberOfRegionsOrMore, int);
110  vtkSetMacro(NumberOfRegionsOrMore, int);
111 
119  vtkGetMacro(FudgeFactor, double);
120  vtkSetMacro(FudgeFactor, double);
121 
127  vtkGetObjectMacro(Cuts, vtkBSPCuts);
128 
135  void SetCuts(vtkBSPCuts* cuts);
136 
141 
146 
151 
156 
161 
166 
171 
186  void SetDataSet(vtkDataSet* set) override;
187 
192  virtual void AddDataSet(vtkDataSet* set);
193 
195 
198  virtual void RemoveDataSet(int index);
199  virtual void RemoveDataSet(vtkDataSet* set);
200  virtual void RemoveAllDataSets();
202 
207 
218 
223  vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
224 
226 
229  vtkGetObjectMacro(DataSets, vtkDataSetCollection);
231 
237 
242  void GetBounds(double* bounds);
243 
252  void SetNewBounds(double* bounds);
253 
255 
258  vtkGetMacro(NumberOfRegions, int);
260 
264  void GetRegionBounds(int regionID, double bounds[6]);
265 
269  void GetRegionDataBounds(int regionID, double bounds[6]);
270 
272 
275  void PrintTree();
278 
282  void PrintRegion(int id);
283 
296  void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
297  void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
298  void CreateCellLists(int* regionReqList, int listSize);
300 
302 
309  vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
310  vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
311  vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
313 
318 
323  vtkIdList* GetCellList(int regionID);
324 
336 
338 
359  vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
361  vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
363  vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
365 
367 
374  int GetRegionContainingCell(int set, vtkIdType cellID);
377 
387 
391  int GetRegionContainingPoint(double x, double y, double z);
392 
398  void BuildLocator() override;
399 
403  void ForceBuildLocator() override;
404 
419  int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
420 
429  const double directionOfProjection[3], vtkIntArray* orderedList);
430 
439  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
440 
449  const double directionOfProjection[3], vtkIntArray* orderedList);
450 
459  vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
460 
462 
477  void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
479 
495 
497 
502  vtkIdType FindPoint(double* x);
503  vtkIdType FindPoint(double x, double y, double z);
505 
507 
512  vtkIdType FindClosestPoint(double* x, double& dist2);
513  vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
515 
521  vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
522 
524 
529  vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
530  vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
532 
539  void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
540 
549  void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
550 
556 
561  void FreeSearchStructure() override;
562 
568  void GenerateRepresentation(int level, vtkPolyData* pd) override;
569 
574  void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
575 
577 
583  vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
584  vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
585  vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
587 
591  virtual void PrintTiming(ostream& os, vtkIndent indent);
592 
597  virtual int NewGeometry();
598 
604  virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
605 
611  virtual void InvalidateGeometry();
612 
619 
626  void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
627 
628 protected:
630  ~vtkKdTree() override;
631 
632  void BuildLocatorInternal() override;
633 
636 
638 
639  int ProcessUserDefinedCuts(double* bounds);
640 
641  void SetCuts(vtkBSPCuts* cuts, int userDefined);
642 
649 
657  int DivideTest(int numberOfPoints, int level);
658 
659  enum
660  {
661  XDIM = 0, // don't change these values
662  YDIM = 1,
663  ZDIM = 2
664  };
665 
667 
669  vtkKdNode** RegionList; // indexed by region ID
670 
672 
673  static void DeleteAllDescendants(vtkKdNode* nd);
674 
676  virtual int SelectCutDirection(vtkKdNode* kd);
677  void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
678 
684  void GetRegionsAtLevel(int level, vtkKdNode** nodes);
685 
691  static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
692 
698 
704  int GetDataSetsNumberOfCells(int set1, int set2);
705 
712  void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
713  void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
714 
725  float* ComputeCellCenters(int set);
727 
729 
735  void UpdateProgress(double amount);
736 
738 
741  vtkSetClampMacro(Progress, double, 0.0, 1.0);
742  vtkGetMacro(Progress, double);
744 
745  // So that each suboperation can report progress
746  // in [0,1], yet we will be able to report a global
747  // progress. Sub-operations must use UpdateSubOperationProgress()
748  // for this to work.
751 
752  // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
753  // Actual progress is given by
754  // (this->ProgressOffset + this->ProgressScale* amount).
755  void UpdateSubOperationProgress(double amount);
756 
757  static void SetNewBounds_(vtkKdNode* kd, double* b, int* fixDim);
758  static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
759  static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
761  static void ZeroNumberOfPoints(vtkKdNode* kd);
762 
763  // Recursive helper for public FindPointsWithinRadius
764  void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
765 
766  // Recursive helper for public FindPointsWithinRadius
768 
769  // Recursive helper for public FindPointsInArea
770  void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
771 
772  // Recursive helper for public FindPointsInArea
774 
775  int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
776 
777  void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
778 
780 
781  struct cellList_
782  {
783  vtkDataSet* dataSet; // cell lists for which data set
784  int* regionIds; // nullptr if listing all regions
785  int nRegions;
789  };
790 
792  vtkIdList* GetList(int regionId, vtkIdList** which);
793 
794  void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
795 
798  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
799 
802  vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
803 
804  void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
805 
806  void printTree_(int verbose);
807 
809  int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
810 
811  int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
812 
813  int FindClosestPointInRegion_(int regionId, double x, double y, double z, double& dist2);
814 
816  double x, double y, double z, double radius, int skipRegion, double& dist2);
817 
819  vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
820 
822  vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
823 
825  vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
826 
828  vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
829 
830  static int ConvexSubRegions_(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
831  static int FoundId(vtkIntArray* idArray, int id);
832 
833  void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
834  int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
836 
837  static void printTree_P(vtkKdNode* kd, int depth, int verbose);
838 
839  static int MidValue(int dim, float* c1, int nvals, double& coord);
840 
841  static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
842  static float FindMaxLeftHalf(int dim, float* c1, int K);
843  static void Select_(int dim, float* X, int* ids, int L, int R, int K);
844 
845  static int ComputeLevel(vtkKdNode* kd);
846  static int SelfOrder(int id, vtkKdNode* kd);
847  static int findRegion(vtkKdNode* node, float x, float y, float z);
848  static int findRegion(vtkKdNode* node, double x, double y, double z);
849 
850  static vtkKdNode** GetRegionsAtLevel_(int level, vtkKdNode** nodes, vtkKdNode* kd);
851 
852  static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
853 
854  void NewPartitioningRequest(int req);
855 
858 
860  double CellBoundsCache[6]; // to optimize IntersectsCell()
861 
862  vtkTypeBool GenerateRepresentationUsingDataBounds;
863 
864  struct cellList_ CellList;
865 
866  // Region Ids, by data set by cell id - this list is large (one
867  // int per cell) but accelerates creation of cell lists
868 
870 
871  int MinCells;
872  int NumberOfRegions; // number of leaf nodes
873 
875  double FudgeFactor; // a very small distance, relative to the dataset's size
876 
877  // These instance variables are used by the special locator created
878  // to find duplicate points. (BuildLocatorFromPoints)
879 
884 
885  float MaxWidth;
886 
887  // These Last* values are here to save state so we can
888  // determine later if k-d tree must be rebuilt.
889 
893  unsigned long* LastDataSetObserverTags;
896  double* LastBounds;
899 
901  double Progress;
902 
903  vtkKdTree(const vtkKdTree&) = delete;
904  void operator=(const vtkKdTree&) = delete;
905 };
906 VTK_ABI_NAMESPACE_END
907 #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:176
abstract class to specify cell behavior
Definition: vtkCell.h:50
maintain an unordered list of dataset objects
abstract class to specify dataset behavior
Definition: vtkDataSet.h:53
list of point or cell ids
Definition: vtkIdList.h:23
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:29
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:35
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:68
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:894
vtkTypeBool Timing
Definition: vtkKdTree.h:874
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:728
void CreateCellLists(int *regionReqList, int listSize)
int ValidDirections
Definition: vtkKdTree.h:666
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:872
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:859
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:891
float MaxWidth
Definition: vtkKdTree.h:885
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:856
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:892
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:895
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:900
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:634
void SetCuts(vtkBSPCuts *cuts, int userDefined)
vtkKdNode ** RegionList
Definition: vtkKdTree.h:669
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:890
static float FindMaxLeftHalf(int dim, float *c1, int K)
int * LocatorRegionLocation
Definition: vtkKdTree.h:883
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:897
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:880
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
double * LastBounds
Definition: vtkKdTree.h:896
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:857
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:742
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:882
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:750
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:677
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:901
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:635
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:223
int MinCells
Definition: vtkKdTree.h:871
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:875
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:671
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:893
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:869
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:898
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:668
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:881
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:59
concrete class for storing a set of points
Definition: vtkPointSet.h:59
represent and manipulate 3D points
Definition: vtkPoints.h:29
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:80
Timer support and logging.
Definition: vtkTimerLog.h:85
@ 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:787
vtkIdList ** cells
Definition: vtkKdTree.h:786
vtkIdList * emptyList
Definition: vtkKdTree.h:788
vtkDataSet * dataSet
Definition: vtkKdTree.h:783
int vtkTypeBool
Definition: vtkABI.h:64
int vtkIdType
Definition: vtkType.h:315