VTK  9.2.6
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
68class vtkTimerLog;
69class vtkIdList;
70class vtkIdTypeArray;
71class vtkIntArray;
72class vtkPointSet;
73class vtkPoints;
74class vtkCellArray;
75class vtkCell;
76class vtkKdNode;
77class vtkBSPCuts;
80
81class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
82{
83public:
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
417 void ForceBuildLocator() override;
418
433 int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
434
443 const double directionOfProjection[3], vtkIntArray* orderedList);
444
453 vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
454
463 const double directionOfProjection[3], vtkIntArray* orderedList);
464
473 vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
474
476
491 void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
493
509
511
517 vtkIdType FindPoint(double x, double y, double z);
519
521
526 vtkIdType FindClosestPoint(double* x, double& dist2);
527 vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
529
535 vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
536
538
543 vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
544 vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
546
553 void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
554
563 void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
564
570
575 void FreeSearchStructure() override;
576
582 void GenerateRepresentation(int level, vtkPolyData* pd) override;
583
588 void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
589
591
597 vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
598 vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
599 vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
601
605 virtual void PrintTiming(ostream& os, vtkIndent indent);
606
611 virtual int NewGeometry();
612
618 virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
619
625 virtual void InvalidateGeometry();
626
633
640 void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
641
642protected:
644 ~vtkKdTree() override;
645
646 void BuildLocatorInternal() override;
647
650
652
653 int ProcessUserDefinedCuts(double* bounds);
654
655 void SetCuts(vtkBSPCuts* cuts, int userDefined);
656
663
671 int DivideTest(int numberOfPoints, int level);
672
673 enum
674 {
675 XDIM = 0, // don't change these values
676 YDIM = 1,
677 ZDIM = 2
678 };
679
681
683 vtkKdNode** RegionList; // indexed by region ID
684
686
688
691 void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
692
698 void GetRegionsAtLevel(int level, vtkKdNode** nodes);
699
705 static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
706
712
718 int GetDataSetsNumberOfCells(int set1, int set2);
719
726 void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
727 void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
728
739 float* ComputeCellCenters(int set);
741
743
749 void UpdateProgress(double amount);
750
752
755 vtkSetClampMacro(Progress, double, 0.0, 1.0);
756 vtkGetMacro(Progress, double);
758
759protected:
760 // So that each suboperation can report progress
761 // in [0,1], yet we will be able to report a global
762 // progress. Sub-operations must use UpdateSubOperationProgress()
763 // for this to work.
766
767 // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
768 // Actual progress is given by
769 // (this->ProgressOffset + this->ProgressScale* amount).
770 void UpdateSubOperationProgress(double amount);
771
772 static void SetNewBounds_(vtkKdNode* kd, double* b, int* fixDim);
773 static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
774 static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
777
778 // Recursive helper for public FindPointsWithinRadius
779 void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
780
781 // Recursive helper for public FindPointsWithinRadius
783
784 // Recursive helper for public FindPointsInArea
785 void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
786
787 // Recursive helper for public FindPointsInArea
789
790 int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
791
792 void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
793
795
797 {
798 vtkDataSet* dataSet; // cell lists for which data set
799 int* regionIds; // nullptr if listing all regions
804 };
805
807 vtkIdList* GetList(int regionId, vtkIdList** which);
808
809 void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
810
813 vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
814
817 vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
818
819 void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
820
821 void printTree_(int verbose);
822
824 int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
825
826 int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
827
828 int FindClosestPointInRegion_(int regionId, double x, double y, double z, double& dist2);
829
831 double x, double y, double z, double radius, int skipRegion, double& dist2);
832
834 vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
835
837 vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
838
840 vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
841
843 vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
844
845 static int ConvexSubRegions_(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
846 static int FoundId(vtkIntArray* idArray, int id);
847
848 void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
849 int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
851
852 static void printTree_P(vtkKdNode* kd, int depth, int verbose);
853
854 static int MidValue(int dim, float* c1, int nvals, double& coord);
855
856 static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
857 static float FindMaxLeftHalf(int dim, float* c1, int K);
858 static void Select_(int dim, float* X, int* ids, int L, int R, int K);
859
860 static int ComputeLevel(vtkKdNode* kd);
861 static int SelfOrder(int id, vtkKdNode* kd);
862 static int findRegion(vtkKdNode* node, float x, float y, float z);
863 static int findRegion(vtkKdNode* node, double x, double y, double z);
864
865 static vtkKdNode** GetRegionsAtLevel_(int level, vtkKdNode** nodes, vtkKdNode* kd);
866
867 static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
868
870
873
875 double CellBoundsCache[6]; // to optimize IntersectsCell()
876
878
879 struct cellList_ CellList;
880
881 // Region Ids, by data set by cell id - this list is large (one
882 // int per cell) but accelerates creation of cell lists
883
885
887 int NumberOfRegions; // number of leaf nodes
888
890 double FudgeFactor; // a very small distance, relative to the dataset's size
891
892 // These instance variables are used by the special locator created
893 // to find duplicate points. (BuildLocatorFromPoints)
894
899
900 float MaxWidth;
901
902 // These Last* values are here to save state so we can
903 // determine later if k-d tree must be rebuilt.
904
911 double* LastBounds;
914
916 double Progress;
917
918 vtkKdTree(const vtkKdTree&) = delete;
919 void operator=(const vtkKdTree&) = delete;
920};
921#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:187
abstract class to specify cell behavior
Definition: vtkCell.h:61
maintain an unordered list of dataset objects
abstract class to specify dataset behavior
Definition: vtkDataSet.h:63
list of point or cell ids
Definition: vtkIdList.h:34
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:40
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:46
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
Definition: vtkKdNode.h:46
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:82
void SelfRegister(vtkKdNode *kd)
vtkIdList * GetBoundaryCellList(int regionID)
The cell list obtained with GetCellList is the list of all cells such that their centroid is containe...
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.
int * LastDataSetType
Definition: vtkKdTree.h:909
vtkTypeBool Timing
Definition: vtkKdTree.h:889
vtkIdTypeArray * GetPointsInRegion(int regionId)
Get a list of the original IDs of all points in a region.
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...
vtkDataSetCollection * DataSets
Definition: vtkKdTree.h:742
void CreateCellLists(int *regionReqList, int listSize)
int ValidDirections
Definition: vtkKdTree.h:680
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:887
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:874
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:906
float MaxWidth
Definition: vtkKdTree.h:900
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)
vtkDataSet * GetDataSet(int n)
Get the nth defined data set in the spatial partitioning.
float * ComputeCellCenters(int set)
vtkIdTypeArray * BuildMapForDuplicatePoints(float tolerance)
This call returns a mapping from the original point IDs supplied to BuildLocatorFromPoints to a subse...
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:871
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
void UpdateSubOperationProgress(double amount)
void CreateCellLists()
vtkDataSet ** LastInputDataSets
Definition: vtkKdTree.h:907
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:910
static vtkKdNode * CopyTree(vtkKdNode *kd)
Create a copy of the binary tree representation of the k-d tree spatial partitioning provided.
vtkBSPCuts * Cuts
Definition: vtkKdTree.h:915
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:648
void SetCuts(vtkBSPCuts *cuts, int userDefined)
vtkKdNode ** RegionList
Definition: vtkKdTree.h:683
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:905
static float FindMaxLeftHalf(int dim, float *c1, int K)
int * LocatorRegionLocation
Definition: vtkKdTree.h:898
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...
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:912
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:895
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
float * ComputeCellCenters(vtkDataSet *set)
double * LastBounds
Definition: vtkKdTree.h:911
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 vtkKdTree * New()
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.
vtkDataSet * GetDataSet() override
Return the 0'th data set.
Definition: vtkKdTree.h:237
int NumberOfRegionsOrMore
Definition: vtkKdTree.h:872
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:764
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:897
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:765
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)
static vtkKdNode ** GetRegionsAtLevel_(int level, vtkKdNode **nodes, vtkKdNode *kd)
void operator=(const vtkKdTree &)=delete
void BuildLocator() override
Create the k-d tree decomposition of the cells of the data set or data sets.
void SetActualLevel()
Definition: vtkKdTree.h:691
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:916
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:649
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...
vtkTypeBool GenerateRepresentationUsingDataBounds
Definition: vtkKdTree.h:877
int MinCells
Definition: vtkKdTree.h:886
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:890
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)
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)
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:685
vtkIdList * GetCellList(int regionID)
Get the cell list for a region.
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:908
void OmitXPartitioning()
Omit partitions along the X axis, yielding shafts in the X direction.
int * AllGetRegionContainingCell()
Get a list (in order by data set by cell id) of the region IDs of the region containing the centroid ...
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:884
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...
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)
vtkIdList * GetList(int regionId, vtkIdList **which)
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:913
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)
float * ComputeCellCenters()
Compute and return a pointer to a list of all cell centers, in order by data set by cell Id.
vtkKdNode * Top
Definition: vtkKdTree.h:682
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:896
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:70
concrete class for storing a set of points
Definition: vtkPointSet.h:70
represent and manipulate 3D points
Definition: vtkPoints.h:40
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:91
Timer support and logging.
Definition: vtkTimerLog.h:96
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:802
vtkIdList ** cells
Definition: vtkKdTree.h:801
vtkIdList * emptyList
Definition: vtkKdTree.h:803
vtkDataSet * dataSet
Definition: vtkKdTree.h:798
int vtkTypeBool
Definition: vtkABI.h:69
int vtkIdType
Definition: vtkType.h:332