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
59#ifndef vtkKdTree_h
60#define vtkKdTree_h
61
62#include "vtkCommonDataModelModule.h" // For export macro
63#include "vtkLocator.h"
64
65class vtkTimerLog;
66class vtkIdList;
67class vtkIdTypeArray;
68class vtkIntArray;
69class vtkPointSet;
70class vtkPoints;
71class vtkCellArray;
72class vtkCell;
73class vtkKdNode;
74class vtkBSPCuts;
77
78class VTKCOMMONDATAMODEL_EXPORT vtkKdTree : public vtkLocator
79{
80public:
81 vtkTypeMacro(vtkKdTree, vtkLocator);
82 void PrintSelf(ostream& os, vtkIndent indent) override;
83
84 static vtkKdTree* New();
85
87
90 vtkBooleanMacro(Timing, vtkTypeBool);
91 vtkSetMacro(Timing, vtkTypeBool);
92 vtkGetMacro(Timing, vtkTypeBool);
94
96
99 vtkSetMacro(MinCells, int);
100 vtkGetMacro(MinCells, int);
102
110 vtkGetMacro(NumberOfRegionsOrLess, int);
111 vtkSetMacro(NumberOfRegionsOrLess, int);
112
120 vtkGetMacro(NumberOfRegionsOrMore, int);
121 vtkSetMacro(NumberOfRegionsOrMore, int);
122
130 vtkGetMacro(FudgeFactor, double);
131 vtkSetMacro(FudgeFactor, double);
132
138 vtkGetObjectMacro(Cuts, vtkBSPCuts);
139
146 void SetCuts(vtkBSPCuts* cuts);
147
152
157
162
167
172
177
182
197 void SetDataSet(vtkDataSet* set) override;
198
203 virtual void AddDataSet(vtkDataSet* set);
204
206
209 virtual void RemoveDataSet(int index);
210 virtual void RemoveDataSet(vtkDataSet* set);
211 virtual void RemoveAllDataSets();
213
218
229
234 vtkDataSet* GetDataSet() override { return this->GetDataSet(0); }
235
237
240 vtkGetObjectMacro(DataSets, vtkDataSetCollection);
242
248
253 void GetBounds(double* bounds);
254
263 void SetNewBounds(double* bounds);
264
266
269 vtkGetMacro(NumberOfRegions, int);
271
275 void GetRegionBounds(int regionID, double bounds[6]);
276
280 void GetRegionDataBounds(int regionID, double bounds[6]);
281
283
286 void PrintTree();
289
293 void PrintRegion(int id);
294
307 void CreateCellLists(int dataSetIndex, int* regionReqList, int reqListSize);
308 void CreateCellLists(vtkDataSet* set, int* regionReqList, int reqListSize);
309 void CreateCellLists(int* regionReqList, int listSize);
311
313
320 vtkSetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
321 vtkGetMacro(IncludeRegionBoundaryCells, vtkTypeBool);
322 vtkBooleanMacro(IncludeRegionBoundaryCells, vtkTypeBool);
324
329
334 vtkIdList* GetCellList(int regionID);
335
347
349
370 vtkIntArray* regions, int set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
372 vtkIntArray* regions, vtkDataSet* set, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
374 vtkIntArray* regions, vtkIdList* inRegionCells, vtkIdList* onBoundaryCells);
376
378
385 int GetRegionContainingCell(int set, vtkIdType cellID);
388
398
402 int GetRegionContainingPoint(double x, double y, double z);
403
409 void BuildLocator() override;
410
414 void ForceBuildLocator() override;
415
430 int MinimalNumberOfConvexSubRegions(vtkIntArray* regionIdList, double** convexRegionBounds);
431
440 const double directionOfProjection[3], vtkIntArray* orderedList);
441
450 vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
451
460 const double directionOfProjection[3], vtkIntArray* orderedList);
461
470 vtkIntArray* regionIds, const double directionOfProjection[3], vtkIntArray* orderedList);
471
473
488 void BuildLocatorFromPoints(vtkPoints** ptArray, int numPtArrays);
490
506
508
514 vtkIdType FindPoint(double x, double y, double z);
516
518
523 vtkIdType FindClosestPoint(double* x, double& dist2);
524 vtkIdType FindClosestPoint(double x, double y, double z, double& dist2);
526
532 vtkIdType FindClosestPointWithinRadius(double radius, const double x[3], double& dist2);
533
535
540 vtkIdType FindClosestPointInRegion(int regionId, double* x, double& dist2);
541 vtkIdType FindClosestPointInRegion(int regionId, double x, double y, double z, double& dist2);
543
550 void FindPointsWithinRadius(double R, const double x[3], vtkIdList* result);
551
560 void FindClosestNPoints(int N, const double x[3], vtkIdList* result);
561
567
572 void FreeSearchStructure() override;
573
579 void GenerateRepresentation(int level, vtkPolyData* pd) override;
580
585 void GenerateRepresentation(int* regionList, int len, vtkPolyData* pd);
586
588
594 vtkBooleanMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
595 vtkSetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
596 vtkGetMacro(GenerateRepresentationUsingDataBounds, vtkTypeBool);
598
602 virtual void PrintTiming(ostream& os, vtkIndent indent);
603
608 virtual int NewGeometry();
609
615 virtual int NewGeometry(vtkDataSet** sets, int numDataSets);
616
622 virtual void InvalidateGeometry();
623
630
637 void FindPointsInArea(double* area, vtkIdTypeArray* ids, bool clearArray = true);
638
639protected:
641 ~vtkKdTree() override;
642
643 void BuildLocatorInternal() override;
644
647
649
650 int ProcessUserDefinedCuts(double* bounds);
651
652 void SetCuts(vtkBSPCuts* cuts, int userDefined);
653
660
668 int DivideTest(int numberOfPoints, int level);
669
670 enum
671 {
672 XDIM = 0, // don't change these values
673 YDIM = 1,
674 ZDIM = 2
675 };
676
678
680 vtkKdNode** RegionList; // indexed by region ID
681
683
685
688 void SetActualLevel() { this->Level = vtkKdTree::ComputeLevel(this->Top); }
689
695 void GetRegionsAtLevel(int level, vtkKdNode** nodes);
696
702 static void GetLeafNodeIds(vtkKdNode* node, vtkIntArray* ids);
703
709
715 int GetDataSetsNumberOfCells(int set1, int set2);
716
723 void ComputeCellCenter(vtkDataSet* set, int cellId, float* center);
724 void ComputeCellCenter(vtkDataSet* set, int cellId, double* center);
725
736 float* ComputeCellCenters(int set);
738
740
746 void UpdateProgress(double amount);
747
749
752 vtkSetClampMacro(Progress, double, 0.0, 1.0);
753 vtkGetMacro(Progress, double);
755
756protected:
757 // So that each suboperation can report progress
758 // in [0,1], yet we will be able to report a global
759 // progress. Sub-operations must use UpdateSubOperationProgress()
760 // for this to work.
763
764 // Update progress for a sub-operation. \c amount goes from 0.0 to 1.0.
765 // Actual progress is given by
766 // (this->ProgressOffset + this->ProgressScale* amount).
767 void UpdateSubOperationProgress(double amount);
768
769 static void SetNewBounds_(vtkKdNode* kd, double* b, int* fixDim);
770 static void CopyChildNodes(vtkKdNode* to, vtkKdNode* from);
771 static void CopyKdNode(vtkKdNode* to, vtkKdNode* from);
774
775 // Recursive helper for public FindPointsWithinRadius
776 void FindPointsWithinRadius(vtkKdNode* node, double R2, const double x[3], vtkIdList* ids);
777
778 // Recursive helper for public FindPointsWithinRadius
780
781 // Recursive helper for public FindPointsInArea
782 void FindPointsInArea(vtkKdNode* node, double* area, vtkIdTypeArray* ids);
783
784 // Recursive helper for public FindPointsInArea
786
787 int DivideRegion(vtkKdNode* kd, float* c1, int* ids, int nlevels);
788
789 void DoMedianFind(vtkKdNode* kd, float* c1, int* ids, int d1, int d2, int d3);
790
792
794 {
795 vtkDataSet* dataSet; // cell lists for which data set
796 int* regionIds; // nullptr if listing all regions
801 };
802
804 vtkIdList* GetList(int regionId, vtkIdList** which);
805
806 void ComputeCellCenter(vtkCell* cell, double* center, double* weights);
807
810 vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
811
814 vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys, int level);
815
816 void AddPolys(vtkKdNode* kd, vtkPoints* pts, vtkCellArray* polys);
817
818 void printTree_(int verbose);
819
821 int regionId, float* point, int** pointsSoFar, int* len, float tolerance, float tolerance2);
822
823 int SearchRegionForDuplicate(float* point, int* pointsSoFar, int len, float tolerance2);
824
825 int FindClosestPointInRegion_(int regionId, double x, double y, double z, double& dist2);
826
828 double x, double y, double z, double radius, int skipRegion, double& dist2);
829
831 vtkIntArray* IdsOfInterest, const double dop[3], vtkIntArray* orderedList);
832
834 vtkIntArray* IdsOfInterest, const double dir[3], int nextId);
835
837 vtkIntArray* IdsOfInterest, const double pos[3], vtkIntArray* orderedList);
838
840 vtkIntArray* IdsOfInterest, const double pos[3], int nextId);
841
842 static int ConvexSubRegions_(int* ids, int len, vtkKdNode* tree, vtkKdNode** nodes);
843 static int FoundId(vtkIntArray* idArray, int id);
844
845 void SetInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
846 int CheckInputDataInfo(int i, int dims[3], double origin[3], double spacing[3]);
848
849 static void printTree_P(vtkKdNode* kd, int depth, int verbose);
850
851 static int MidValue(int dim, float* c1, int nvals, double& coord);
852
853 static int Select(int dim, float* c1, int* ids, int nvals, double& coord);
854 static float FindMaxLeftHalf(int dim, float* c1, int K);
855 static void Select_(int dim, float* X, int* ids, int L, int R, int K);
856
857 static int ComputeLevel(vtkKdNode* kd);
858 static int SelfOrder(int id, vtkKdNode* kd);
859 static int findRegion(vtkKdNode* node, float x, float y, float z);
860 static int findRegion(vtkKdNode* node, double x, double y, double z);
861
862 static vtkKdNode** GetRegionsAtLevel_(int level, vtkKdNode** nodes, vtkKdNode* kd);
863
864 static void AddNewRegions(vtkKdNode* kd, float* c1, int midpt, int dim, double coord);
865
867
870
872 double CellBoundsCache[6]; // to optimize IntersectsCell()
873
875
876 struct cellList_ CellList;
877
878 // Region Ids, by data set by cell id - this list is large (one
879 // int per cell) but accelerates creation of cell lists
880
882
884 int NumberOfRegions; // number of leaf nodes
885
887 double FudgeFactor; // a very small distance, relative to the dataset's size
888
889 // These instance variables are used by the special locator created
890 // to find duplicate points. (BuildLocatorFromPoints)
891
896
897 float MaxWidth;
898
899 // These Last* values are here to save state so we can
900 // determine later if k-d tree must be rebuilt.
901
908 double* LastBounds;
911
913 double Progress;
914
915 vtkKdTree(const vtkKdTree&) = delete;
916 void operator=(const vtkKdTree&) = delete;
917};
918#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
abstract class to specify cell behavior
Definition vtkCell.h:58
maintain an unordered list of dataset objects
abstract class to specify dataset behavior
Definition vtkDataSet.h:57
list of point or cell ids
Definition vtkIdList.h:31
dynamic, self-adjusting array of vtkIdType
a simple class to control print indentation
Definition vtkIndent.h:34
dynamic, self-adjusting array of int
Definition vtkIntArray.h:40
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:79
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:906
vtkTypeBool Timing
Definition vtkKdTree.h:886
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:739
void CreateCellLists(int *regionReqList, int listSize)
int ValidDirections
Definition vtkKdTree.h:677
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:884
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:871
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:903
float MaxWidth
Definition vtkKdTree.h:897
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:868
static int Select(int dim, float *c1, int *ids, int nvals, double &coord)
void UpdateSubOperationProgress(double amount)
void CreateCellLists()
vtkDataSet ** LastInputDataSets
Definition vtkKdTree.h:904
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:907
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:912
vtkBSPIntersections * BSPCalculator
Definition vtkKdTree.h:645
void SetCuts(vtkBSPCuts *cuts, int userDefined)
vtkKdNode ** RegionList
Definition vtkKdTree.h:680
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:902
static float FindMaxLeftHalf(int dim, float *c1, int K)
int * LocatorRegionLocation
Definition vtkKdTree.h:895
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:909
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:892
static void SetDataBoundsToSpatialBounds(vtkKdNode *kd)
static void CopyChildNodes(vtkKdNode *to, vtkKdNode *from)
float * ComputeCellCenters(vtkDataSet *set)
double * LastBounds
Definition vtkKdTree.h:908
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:234
int NumberOfRegionsOrMore
Definition vtkKdTree.h:869
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:761
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:894
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:762
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:688
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:913
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:646
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:874
int MinCells
Definition vtkKdTree.h:883
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:887
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:682
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:905
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:881
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:910
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:679
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:893
abstract base class for objects that accelerate spatial searches
Definition vtkLocator.h:70
concrete class for storing a set of points
Definition vtkPointSet.h:67
represent and manipulate 3D points
Definition vtkPoints.h:34
concrete dataset represents vertices, lines, polygons, and triangle strips
Definition vtkPolyData.h:85
Timer support and logging.
Definition vtkTimerLog.h:90
vtkIdList ** boundaryCells
Definition vtkKdTree.h:799
vtkIdList ** cells
Definition vtkKdTree.h:798
vtkIdList * emptyList
Definition vtkKdTree.h:800
vtkDataSet * dataSet
Definition vtkKdTree.h:795
int vtkTypeBool
Definition vtkABI.h:69
int vtkIdType
Definition vtkType.h:332