VTK  9.1.0
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
121#ifndef vtkKdTree_h
122#define vtkKdTree_h
123
124#include "vtkCommonDataModelModule.h" // For export macro
125#include "vtkLocator.h"
126
127class vtkTimerLog;
128class vtkIdList;
129class vtkIdTypeArray;
130class vtkIntArray;
131class vtkPointSet;
132class vtkPoints;
133class vtkCellArray;
134class vtkCell;
135class vtkKdNode;
136class vtkBSPCuts;
139
140class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
141{
142public:
143 vtkTypeMacro(vtkKdTree, vtkLocator);
144 void PrintSelf(ostream& os, vtkIndent indent) override;
145
146 static vtkKdTree* New();
147
149
152 vtkBooleanMacro(Timing, vtkTypeBool);
153 vtkSetMacro(Timing, vtkTypeBool);
154 vtkGetMacro(Timing, vtkTypeBool);
156
158
161 vtkSetMacro(MinCells, int);
162 vtkGetMacro(MinCells, int);
164
172 vtkGetMacro(NumberOfRegionsOrLess, int);
173 vtkSetMacro(NumberOfRegionsOrLess, int);
174
182 vtkGetMacro(NumberOfRegionsOrMore, int);
183 vtkSetMacro(NumberOfRegionsOrMore, int);
184
192 vtkGetMacro(FudgeFactor, double);
193 vtkSetMacro(FudgeFactor, double);
194
200 vtkGetObjectMacro(Cuts, vtkBSPCuts);
201
208 void SetCuts(vtkBSPCuts* cuts);
209
214
219
224
229
234
239
244
259 void SetDataSet(vtkDataSet* set) override;
260
265 virtual void AddDataSet(vtkDataSet* set);
266
268
271 virtual void RemoveDataSet(int index);
272 virtual void RemoveDataSet(vtkDataSet* set);
273 virtual void RemoveAllDataSets();
275
280
291
296 vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
297
299
302 vtkGetObjectMacro(DataSets, vtkDataSetCollection);
304
310
315 void GetBounds(double* bounds);
316
325 void SetNewBounds(double* bounds);
326
328
331 vtkGetMacro(NumberOfRegions, int);
333
337 void GetRegionBounds(int regionID, double bounds[6]);
338
342 void GetRegionDataBounds(int regionID, double bounds[6]);
343
345
348 void PrintTree();
351
355 void PrintRegion(int id);
356
369 void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
370 void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
371 void CreateCellLists(int* regionReqList, int listSize);
373
375
382 vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
383 vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
384 vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
386
391
396 vtkIdList* GetCellList(int regionID);
397
409
411
432 vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
434 vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
436 vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
438
440
447 int GetRegionContainingCell(int set, vtkIdType cellID);
450
460
464 int GetRegionContainingPoint(double x, double y, double z);
465
471 void BuildLocator() override;
472
487 int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
488
497 const double directionOfProjection[3], vtkIntArray* orderedList);
498
507 vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
508
517 const double directionOfProjection[3], vtkIntArray* orderedList);
518
527 vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
528
530
545 void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
547
563
565
571 vtkIdType FindPoint(double x, double y, double z);
573
575
580 vtkIdType FindClosestPoint(double* x, double& dist2);
581 vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
583
589 vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
590
592
597 vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
598 vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
600
607 void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
608
617 void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
618
624
629 void FreeSearchStructure() override;
630
636 void GenerateRepresentation(int level, vtkPolyData* pd) override;
637
642 void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
643
645
651 vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
652 vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
653 vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
655
659 virtual void PrintTiming(ostream& os, vtkIndent indent);
660
665 virtual int NewGeometry();
666
672 virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
673
679 virtual void InvalidateGeometry();
680
687
694 void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
695
696protected:
698 ~vtkKdTree() override;
699
702
704
705 int ProcessUserDefinedCuts(double* bounds);
706
707 void SetCuts(vtkBSPCuts* cuts, int userDefined);
708
715
723 int DivideTest(int numberOfPoints, int level);
724
725 enum
726 {
727 XDIM = 0, // don't change these values
728 YDIM = 1,
729 ZDIM = 2
730 };
731
733
735 vtkKdNode** RegionList; // indexed by region ID
736
738
740
743 void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
744
750 void GetRegionsAtLevel(int level, vtkKdNode** nodes);
751
757 static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
758
764
770 int GetDataSetsNumberOfCells(int set1, int set2);
771
778 void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
779 void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
780
791 float* ComputeCellCenters(int set);
793
795
801 void UpdateProgress(double amount);
802
804
807 vtkSetClampMacro(Progress, double, 0.0, 1.0);
808 vtkGetMacro(Progress, double);
810
811protected:
812 // So that each suboperation can report progress
813 // in [0,1], yet we will be able to report a global
814 // progress. Sub-operations must use UpdateSubOperationProgress()
815 // for this to work.
818
819 // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
820 // Actual progress is given by
821 // (this->ProgressOffset + this->ProgressScale* amount).
822 void UpdateSubOperationProgress(double amount);
823
824 static void _SetNewBounds(vtkKdNode* kd, double* b, int* fixDim);
825 static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
826 static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
829
830 // Recursive helper for public FindPointsWithinRadius
831 void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
832
833 // Recursive helper for public FindPointsWithinRadius
835
836 // Recursive helper for public FindPointsInArea
837 void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
838
839 // Recursive helper for public FindPointsInArea
841
842 int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
843
844 void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
845
847
849 {
850 vtkDataSet* dataSet; // cell lists for which data set
851 int* regionIds; // nullptr if listing all regions
856 };
857
859 vtkIdList* GetList(int regionId, vtkIdList** which);
860
861 void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
862
865 vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
866
869 vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
870
871 void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
872
873 void _printTree(int verbose);
874
876 int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
877
878 int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
879
880 int _FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
881
883 double x, double y, double z, double radius, int skipRegion, double& dist2);
884
886 vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
887
889 vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
890
892 vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
893
895 vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
896
897 static int __ConvexSubRegions(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
898 static int FoundId(vtkIntArray* idArray, int id);
899
900 void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
901 int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
903
904 static void __printTree(vtkKdNode* kd, int depth, int verbose);
905
906 static int MidValue(int dim, float* c1, int nvals, double& coord);
907
908 static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
909 static float FindMaxLeftHalf(int dim, float* c1, int K);
910 static void _Select(int dim, float* X, int* ids, int L, int R, int K);
911
912 static int ComputeLevel(vtkKdNode* kd);
913 static int SelfOrder(int id, vtkKdNode* kd);
914 static int findRegion(vtkKdNode* node, float x, float y, float z);
915 static int findRegion(vtkKdNode* node, double x, double y, double z);
916
917 static vtkKdNode** _GetRegionsAtLevel(int level, vtkKdNode** nodes, vtkKdNode* kd);
918
919 static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
920
922
925
927 double CellBoundsCache[6]; // to optimize IntersectsCell()
928
930
931 struct _cellList CellList;
932
933 // Region Ids, by data set by cell id - this list is large (one
934 // int per cell) but accelerates creation of cell lists
935
937
939 int NumberOfRegions; // number of leaf nodes
940
942 double FudgeFactor; // a very small distance, relative to the dataset's size
943
944 // These instance variables are used by the special locator created
945 // to find duplicate points. (BuildLocatorFromPoints)
946
951
952 float MaxWidth;
953
954 // These Last* values are here to save state so we can
955 // determine later if k-d tree must be rebuilt.
956
963 double* LastBounds;
966
968 double Progress;
969
970 vtkKdTree(const vtkKdTree&) = delete;
971 void operator=(const vtkKdTree&) = delete;
972};
973#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:290
abstract class to specify cell behavior
Definition: vtkCell.h:147
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:140
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition: vtkIndent.h:113
dynamic, self-adjusting array of int
Definition: vtkIntArray.h:149
This class represents a single spatial region in an 3D axis aligned binary spatial partitioning.
Definition: vtkKdNode.h:43
a Kd-tree spatial decomposition of a set of points
Definition: vtkKdTree.h:141
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.
static void __printTree(vtkKdNode *kd, int depth, int verbose)
int * LastDataSetType
Definition: vtkKdTree.h:961
vtkTypeBool Timing
Definition: vtkKdTree.h:941
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)
static void _SetNewBounds(vtkKdNode *kd, double *b, int *fixDim)
int MinimalNumberOfConvexSubRegions(vtkIntArray *regionIdList, double **convexRegionBounds)
Given a list of region IDs, determine the decomposition of these regions into the minimal number of c...
vtkDataSetCollection * DataSets
Definition: vtkKdTree.h:794
static vtkKdNode ** _GetRegionsAtLevel(int level, vtkKdNode **nodes, vtkKdNode *kd)
void CreateCellLists(int *regionReqList, int listSize)
int ValidDirections
Definition: vtkKdTree.h:732
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:939
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:926
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:958
float MaxWidth
Definition: vtkKdTree.h:952
vtkIdType GetCellLists(vtkIntArray *regions, int set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
For a list of regions, get two cell lists.
void BuildRegionList()
int _ViewOrderRegionsInDirection(vtkIntArray *IdsOfInterest, const double dop[3], vtkIntArray *orderedList)
void OmitNoPartitioning()
Partition along all three axes - this is the default.
void _printTree(int verbose)
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 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:923
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
void UpdateSubOperationProgress(double amount)
void CreateCellLists()
vtkDataSet ** LastInputDataSets
Definition: vtkKdTree.h:959
void ComputeCellCenter(vtkCell *cell, double *center, double *weights)
double * LastInputDataInfo
Definition: vtkKdTree.h:962
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:967
vtkBSPIntersections * BSPCalculator
Definition: vtkKdTree.h:700
void SetCuts(vtkBSPCuts *cuts, int userDefined)
vtkKdNode ** RegionList
Definition: vtkKdTree.h:735
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:957
static float FindMaxLeftHalf(int dim, float *c1, int K)
int * LocatorRegionLocation
Definition: vtkKdTree.h:950
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:964
void _generateRepresentationWholeSpace(vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
void ClearLastBuildCache()
vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double &dist2)
Given a position x and a radius r, return the id of the point closest to the point in that radius.
void OmitYPartitioning()
Omit partitions along the Y axis, yielding shafts in the Y direction.
void GetBounds(double *bounds)
Get the spatial bounds of the entire k-d tree space.
int NumberOfLocatorPoints
Definition: vtkKdTree.h:947
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
static void _Select(int dim, float *X, int *ids, int L, int R, int K)
float * ComputeCellCenters(vtkDataSet *set)
double * LastBounds
Definition: vtkKdTree.h:963
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:296
int NumberOfRegionsOrMore
Definition: vtkKdTree.h:924
void SetNewBounds(double *bounds)
There are certain applications where you want the bounds of the k-d tree space to be at least as larg...
int ProcessUserDefinedCuts(double *bounds)
static void AddNewRegions(vtkKdNode *kd, float *c1, int midpt, int dim, double coord)
static int __ViewOrderRegionsInDirection(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double dir[3], int nextId)
static int FoundId(vtkIntArray *idArray, int id)
double ProgressScale
Definition: vtkKdTree.h:816
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:949
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:817
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.
void operator=(const vtkKdTree &)=delete
void BuildLocator() override
Create the k-d tree decomposition of the cells of the data set or data sets.
int _ViewOrderRegionsFromPosition(vtkIntArray *IdsOfInterest, const double pos[3], vtkIntArray *orderedList)
void SetActualLevel()
Definition: vtkKdTree.h:743
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:968
static int MidValue(int dim, float *c1, int nvals, double &coord)
int UserDefinedCuts
Definition: vtkKdTree.h:701
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:929
static int __ViewOrderRegionsFromPosition(vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double pos[3], int nextId)
int MinCells
Definition: vtkKdTree.h:938
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:942
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)
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,...
vtkTimerLog * TimerLog
Definition: vtkKdTree.h:737
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:960
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:936
int ViewOrderAllRegionsInDirection(const double directionOfProjection[3], vtkIntArray *orderedList)
Given a direction of projection (typically obtained with vtkCamera::GetDirectionOfProjection()),...
static int __ConvexSubRegions(int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes)
int _FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
void DoMedianFind(vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3)
void PrintRegion(int id)
Print out leaf node data for given id.
vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double &dist2)
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.
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 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:965
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:734
int GetDataSetIndex(vtkDataSet *set)
Return the index of the given data set.
float * LocatorPoints
Definition: vtkKdTree.h:948
abstract base class for objects that accelerate spatial searches
Definition: vtkLocator.h:89
concrete class for storing a set of points
Definition: vtkPointSet.h:106
represent and manipulate 3D points
Definition: vtkPoints.h:143
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition: vtkPolyData.h:195
Timer support and logging.
Definition: vtkTimerLog.h:199
vtkIdList ** boundaryCells
Definition: vtkKdTree.h:854
vtkIdList * emptyList
Definition: vtkKdTree.h:855
vtkIdList ** cells
Definition: vtkKdTree.h:853
vtkDataSet * dataSet
Definition: vtkKdTree.h:850
int vtkTypeBool
Definition: vtkABI.h:69
int vtkIdType
Definition: vtkType.h:332