VTK
Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Types | Protected Member Functions | Static Protected Member Functions | Protected Attributes | List of all members
vtkKdTree Class Reference

a Kd-tree spatial decomposition of a set of points More...

#include <vtkKdTree.h>

Inheritance diagram for vtkKdTree:
[legend]
Collaboration diagram for vtkKdTree:
[legend]

Classes

struct  _cellList
 

Public Types

typedef vtkLocator Superclass
 
- Public Types inherited from vtkLocator
typedef vtkObject Superclass
 Standard type and print methods. More...
 

Public Member Functions

virtual vtkTypeBool IsA (const char *type)
 Return 1 if this class is the same type of (or a subclass of) the named class. More...
 
vtkKdTreeNewInstance () const
 
void PrintSelf (ostream &os, vtkIndent indent) override
 Methods invoked by print to print information about the object including superclasses. More...
 
virtual void TimingOn ()
 Turn on timing of the k-d tree build. More...
 
virtual void TimingOff ()
 
virtual void SetTiming (vtkTypeBool)
 
virtual vtkTypeBool GetTiming ()
 
virtual void SetMinCells (int)
 Minimum number of cells per spatial region. More...
 
virtual int GetMinCells ()
 
virtual int GetNumberOfRegionsOrLess ()
 Set/Get the number of spatial regions you want to get close to without going over. More...
 
virtual void SetNumberOfRegionsOrLess (int)
 
virtual int GetNumberOfRegionsOrMore ()
 Set/Get the number of spatial regions you want to get close to while having at least this many regions. More...
 
virtual void SetNumberOfRegionsOrMore (int)
 
virtual double GetFudgeFactor ()
 Some algorithms on k-d trees require a value that is a very small distance relative to the diameter of the entire space divided by the k-d tree. More...
 
virtual void SetFudgeFactor (double)
 
virtual vtkBSPCutsGetCuts ()
 Get a vtkBSPCuts object, a general object representing an axis- aligned spatial partitioning. More...
 
void SetCuts (vtkBSPCuts *cuts)
 Normally the k-d tree is computed from the dataset(s) provided in SetDataSet. More...
 
void OmitXPartitioning ()
 Omit partitions along the X axis, yielding shafts in the X direction. More...
 
void OmitYPartitioning ()
 Omit partitions along the Y axis, yielding shafts in the Y direction. More...
 
void OmitZPartitioning ()
 Omit partitions along the Z axis, yielding shafts in the Z direction. More...
 
void OmitXYPartitioning ()
 Omit partitions along the X and Y axes, yielding slabs along Z. More...
 
void OmitYZPartitioning ()
 Omit partitions along the Y and Z axes, yielding slabs along X. More...
 
void OmitZXPartitioning ()
 Omit partitions along the Z and X axes, yielding slabs along Y. More...
 
void OmitNoPartitioning ()
 Partition along all three axes - this is the default. More...
 
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 sets. More...
 
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 sets. More...
 
virtual void RemoveDataSet (int index)
 Remove the given data set. More...
 
virtual void RemoveDataSet (vtkDataSet *set)
 
virtual void RemoveAllDataSets ()
 
int GetNumberOfDataSets ()
 Get the number of data sets included in spatial partitioning. More...
 
vtkDataSetGetDataSet (int n)
 Get the nth defined data set in the spatial partitioning. More...
 
vtkDataSetGetDataSet () override
 Return the 0'th data set. More...
 
virtual vtkDataSetCollectionGetDataSets ()
 Return a collection of all the data sets. More...
 
int GetDataSetIndex (vtkDataSet *set)
 Return the index of the given data set. More...
 
void GetBounds (double *bounds)
 Get the spatial bounds of the entire k-d tree space. More...
 
void SetNewBounds (double *bounds)
 There are certain applications where you want the bounds of the k-d tree space to be at least as large as a specified box. More...
 
virtual int GetNumberOfRegions ()
 The number of leaf nodes of the tree, the spatial regions. More...
 
void GetRegionBounds (int regionID, double bounds[6])
 Get the spatial bounds of k-d tree region. More...
 
void GetRegionDataBounds (int regionID, double bounds[6])
 Get the bounds of the data within the k-d tree region. More...
 
void PrintTree ()
 Print out nodes of kd tree. More...
 
void PrintVerboseTree ()
 
void PrintRegion (int id)
 Print out leaf node data for given id. More...
 
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 the region. More...
 
void CreateCellLists (vtkDataSet *set, int *regionReqList, int reqListSize)
 
void CreateCellLists (int *regionReqList, int listSize)
 
void CreateCellLists ()
 
virtual void SetIncludeRegionBoundaryCells (vtkTypeBool)
 If IncludeRegionBoundaryCells is ON, CreateCellLists() will also create a list of cells which intersect a given region, but are not assigned to the region. More...
 
virtual vtkTypeBool GetIncludeRegionBoundaryCells ()
 
virtual void IncludeRegionBoundaryCellsOn ()
 
virtual void IncludeRegionBoundaryCellsOff ()
 
void DeleteCellLists ()
 Free the memory used by the cell lists. More...
 
vtkIdListGetCellList (int regionID)
 Get the cell list for a region. More...
 
vtkIdListGetBoundaryCellList (int regionID)
 The cell list obtained with GetCellList is the list of all cells such that their centroid is contained in the spatial region. More...
 
vtkIdType GetCellLists (vtkIntArray *regions, int set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
 For a list of regions, get two cell lists. More...
 
vtkIdType GetCellLists (vtkIntArray *regions, vtkDataSet *set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
 
vtkIdType GetCellLists (vtkIntArray *regions, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
 
int GetRegionContainingCell (vtkDataSet *set, vtkIdType cellID)
 Get the id of the region containing the cell centroid. More...
 
int GetRegionContainingCell (int set, vtkIdType cellID)
 
int GetRegionContainingCell (vtkIdType cellID)
 
int * AllGetRegionContainingCell ()
 Get a list (in order by data set by cell id) of the region IDs of the region containing the centroid for each cell. More...
 
int GetRegionContainingPoint (double x, double y, double z)
 Get the id of the region containing the specified location. More...
 
void BuildLocator () override
 Create the k-d tree decomposition of the cells of the data set or data sets. More...
 
int MinimalNumberOfConvexSubRegions (vtkIntArray *regionIdList, double **convexRegionBounds)
 Given a list of region IDs, determine the decomposition of these regions into the minimal number of convex subregions. More...
 
int ViewOrderAllRegionsInDirection (const double directionOfProjection[3], vtkIntArray *orderedList)
 Given a direction of projection (typically obtained with vtkCamera::GetDirectionOfProjection()), this method, creates a list of the k-d tree region IDs in order from front to back with respect to that direction. More...
 
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 k-d tree region IDs in order from front to back with respect to that direction. More...
 
int ViewOrderAllRegionsFromPosition (const double directionOfProjection[3], vtkIntArray *orderedList)
 Given a camera position (typically obtained with vtkCamera::GetPosition()), this method, creates a list of the k-d tree region IDs in order from front to back with respect to that direction. More...
 
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 tree region IDs in order from front to back with respect to that direction. More...
 
void BuildLocatorFromPoints (vtkPointSet *pointset)
 This is a special purpose locator that builds a k-d tree to find duplicate and near-by points. More...
 
void BuildLocatorFromPoints (vtkPoints *ptArray)
 
void BuildLocatorFromPoints (vtkPoints **ptArray, int numPtArrays)
 
vtkIdTypeArrayBuildMapForDuplicatePoints (float tolerance)
 This call returns a mapping from the original point IDs supplied to BuildLocatorFromPoints to a subset of those IDs that is unique within the specified tolerance. More...
 
vtkIdType FindPoint (double *x)
 Find the Id of the point that was previously supplied to BuildLocatorFromPoints(). More...
 
vtkIdType FindPoint (double x, double y, double z)
 
vtkIdType FindClosestPoint (double *x, double &dist2)
 Find the Id of the point that was previously supplied to BuildLocatorFromPoints() which is closest to the given point. More...
 
vtkIdType FindClosestPoint (double x, double y, double z, double &dist2)
 
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. More...
 
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. More...
 
vtkIdType FindClosestPointInRegion (int regionId, double x, double y, double z, double &dist2)
 
void FindPointsWithinRadius (double R, const double x[3], vtkIdList *result)
 Find all points within a specified radius R of position x. More...
 
void FindClosestNPoints (int N, const double x[3], vtkIdList *result)
 Find the closest N points to a position. More...
 
vtkIdTypeArrayGetPointsInRegion (int regionId)
 Get a list of the original IDs of all points in a region. More...
 
void FreeSearchStructure () override
 Delete the k-d tree data structure. More...
 
void GenerateRepresentation (int level, vtkPolyData *pd) override
 Create a polydata representation of the boundaries of the k-d tree regions. More...
 
void GenerateRepresentation (int *regionList, int len, vtkPolyData *pd)
 Generate a polygonal representation of a list of regions. More...
 
virtual void GenerateRepresentationUsingDataBoundsOn ()
 The polydata representation of the k-d tree shows the boundaries of the k-d tree decomposition spatial regions. More...
 
virtual void GenerateRepresentationUsingDataBoundsOff ()
 
virtual void SetGenerateRepresentationUsingDataBounds (vtkTypeBool)
 
virtual vtkTypeBool GetGenerateRepresentationUsingDataBounds ()
 
virtual void PrintTiming (ostream &os, vtkIndent indent)
 Print timing of k-d tree build. More...
 
virtual int NewGeometry ()
 Return 1 if the geometry of the input data sets has changed since the last time the k-d tree was built. More...
 
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 build the k-d tree. More...
 
virtual void InvalidateGeometry ()
 Forget about the last geometry used. More...
 
void FindPointsInArea (double *area, vtkIdTypeArray *ids, bool clearArray=true)
 Fill ids with points found in area. More...
 
- Public Member Functions inherited from vtkLocator
vtkLocatorNewInstance () const
 
void PrintSelf (ostream &os, vtkIndent indent) override
 Methods invoked by print to print information about the object including superclasses. More...
 
virtual void SetMaxLevel (int)
 Set the maximum allowable level for the tree. More...
 
virtual int GetMaxLevel ()
 
virtual int GetLevel ()
 Get the level of the locator (determined automatically if Automatic is true). More...
 
virtual void SetAutomatic (vtkTypeBool)
 Boolean controls whether locator depth/resolution of locator is computed automatically from average number of entities in bucket. More...
 
virtual vtkTypeBool GetAutomatic ()
 
virtual void AutomaticOn ()
 
virtual void AutomaticOff ()
 
virtual void SetTolerance (double)
 Specify absolute tolerance (in world coordinates) for performing geometric operations. More...
 
virtual double GetTolerance ()
 
virtual void Update ()
 Cause the locator to rebuild itself if it or its input dataset has changed. More...
 
virtual void Initialize ()
 Initialize locator. More...
 
virtual vtkMTimeType GetBuildTime ()
 Return the time of the last data structure build. More...
 
void Register (vtkObjectBase *o) override
 Handle the PointSet <-> Locator loop. More...
 
void UnRegister (vtkObjectBase *o) override
 Decrease the reference count (release by another object). More...
 
- Public Member Functions inherited from vtkObject
 vtkBaseTypeMacro (vtkObject, vtkObjectBase)
 
virtual void DebugOn ()
 Turn debugging output on. More...
 
virtual void DebugOff ()
 Turn debugging output off. More...
 
bool GetDebug ()
 Get the value of the debug flag. More...
 
void SetDebug (bool debugFlag)
 Set the value of the debug flag. More...
 
virtual void Modified ()
 Update the modification time for this object. More...
 
virtual vtkMTimeType GetMTime ()
 Return this object's modified time. More...
 
unsigned long AddObserver (unsigned long event, vtkCommand *, float priority=0.0f)
 Allow people to add/remove/invoke observers (callbacks) to any VTK object. More...
 
unsigned long AddObserver (const char *event, vtkCommand *, float priority=0.0f)
 
vtkCommandGetCommand (unsigned long tag)
 
void RemoveObserver (vtkCommand *)
 
void RemoveObservers (unsigned long event, vtkCommand *)
 
void RemoveObservers (const char *event, vtkCommand *)
 
vtkTypeBool HasObserver (unsigned long event, vtkCommand *)
 
vtkTypeBool HasObserver (const char *event, vtkCommand *)
 
void RemoveObserver (unsigned long tag)
 
void RemoveObservers (unsigned long event)
 
void RemoveObservers (const char *event)
 
void RemoveAllObservers ()
 
vtkTypeBool HasObserver (unsigned long event)
 
vtkTypeBool HasObserver (const char *event)
 
template<class U , class T >
unsigned long AddObserver (unsigned long event, U observer, void(T::*callback)(), float priority=0.0f)
 Overloads to AddObserver that allow developers to add class member functions as callbacks for events. More...
 
template<class U , class T >
unsigned long AddObserver (unsigned long event, U observer, void(T::*callback)(vtkObject *, unsigned long, void *), float priority=0.0f)
 
template<class U , class T >
unsigned long AddObserver (unsigned long event, U observer, bool(T::*callback)(vtkObject *, unsigned long, void *), float priority=0.0f)
 Allow user to set the AbortFlagOn() with the return value of the callback method. More...
 
int InvokeEvent (unsigned long event, void *callData)
 This method invokes an event and return whether the event was aborted or not. More...
 
int InvokeEvent (const char *event, void *callData)
 
int InvokeEvent (unsigned long event)
 
int InvokeEvent (const char *event)
 
- Public Member Functions inherited from vtkObjectBase
const char * GetClassName () const
 Return the class name as a string. More...
 
virtual void Delete ()
 Delete a VTK object. More...
 
virtual void FastDelete ()
 Delete a reference to this object. More...
 
void InitializeObjectBase ()
 
void Print (ostream &os)
 Print an object to an ostream. More...
 
virtual void PrintHeader (ostream &os, vtkIndent indent)
 
virtual void PrintTrailer (ostream &os, vtkIndent indent)
 
int GetReferenceCount ()
 Return the current reference count of this object. More...
 
void SetReferenceCount (int)
 Sets the reference count. More...
 
void PrintRevisions (ostream &)
 Legacy. More...
 

Static Public Member Functions

static vtkTypeBool IsTypeOf (const char *type)
 
static vtkKdTreeSafeDownCast (vtkObjectBase *o)
 
static vtkKdTreeNew ()
 
static vtkKdNodeCopyTree (vtkKdNode *kd)
 Create a copy of the binary tree representation of the k-d tree spatial partitioning provided. More...
 
- Static Public Member Functions inherited from vtkLocator
static vtkTypeBool IsTypeOf (const char *type)
 
static vtkLocatorSafeDownCast (vtkObjectBase *o)
 
- Static Public Member Functions inherited from vtkObject
static vtkObjectNew ()
 Create an object with Debug turned off, modified time initialized to zero, and reference counting on. More...
 
static void BreakOnError ()
 This method is called when vtkErrorMacro executes. More...
 
static void SetGlobalWarningDisplay (int val)
 This is a global flag that controls whether any debug, warning or error messages are displayed. More...
 
static void GlobalWarningDisplayOn ()
 
static void GlobalWarningDisplayOff ()
 
static int GetGlobalWarningDisplay ()
 
- Static Public Member Functions inherited from vtkObjectBase
static vtkTypeBool IsTypeOf (const char *name)
 Return 1 if this class type is the same type of (or a subclass of) the named class. More...
 
static vtkObjectBaseNew ()
 Create an object with Debug turned off, modified time initialized to zero, and reference counting on. More...
 

Protected Types

enum  { XDIM = 0, YDIM = 1, ZDIM = 2 }
 

Protected Member Functions

virtual vtkObjectBaseNewInstanceInternal () const
 
 vtkKdTree ()
 
 ~vtkKdTree () override
 
void SetCalculator (vtkKdNode *kd)
 
int ProcessUserDefinedCuts (double *bounds)
 
void SetCuts (vtkBSPCuts *cuts, int userDefined)
 
void UpdateBuildTime ()
 Save enough state so NewGeometry() can work, and update the BuildTime time stamp. More...
 
int DivideTest (int numberOfPoints, int level)
 Prior to dividing a region at level "level", of size "numberOfPoints", apply the tests implied by MinCells, NumberOfRegionsOrMore and NumberOfRegionsOrLess. More...
 
void BuildRegionList ()
 
virtual int SelectCutDirection (vtkKdNode *kd)
 
void SetActualLevel ()
 
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 structures. More...
 
int GetNumberOfCells ()
 Returns the total number of cells in all the data sets. More...
 
int GetDataSetsNumberOfCells (int set1, int set2)
 Returns the total number of cells in data set 1 through data set 2. More...
 
void ComputeCellCenter (vtkDataSet *set, int cellId, float *center)
 Get or compute the center of one cell. More...
 
void ComputeCellCenter (vtkDataSet *set, int cellId, double *center)
 
float * ComputeCellCenters ()
 Compute and return a pointer to a list of all cell centers, in order by data set by cell Id. More...
 
float * ComputeCellCenters (int set)
 
float * ComputeCellCenters (vtkDataSet *set)
 
void UpdateProgress (double amount)
 Modelled on vtkAlgorithm::UpdateProgress(). More...
 
virtual void SetProgress (double)
 Set/Get the execution progress of a process object. More...
 
virtual double GetProgress ()
 
void UpdateSubOperationProgress (double amount)
 
void FindPointsWithinRadius (vtkKdNode *node, double R2, const double x[3], vtkIdList *ids)
 
void AddAllPointsInRegion (vtkKdNode *node, vtkIdList *ids)
 
void FindPointsInArea (vtkKdNode *node, double *area, vtkIdTypeArray *ids)
 
void AddAllPointsInRegion (vtkKdNode *node, vtkIdTypeArray *ids)
 
int DivideRegion (vtkKdNode *kd, float *c1, int *ids, int nlevels)
 
void DoMedianFind (vtkKdNode *kd, float *c1, int *ids, int d1, int d2, int d3)
 
void SelfRegister (vtkKdNode *kd)
 
void InitializeCellLists ()
 
vtkIdListGetList (int regionId, vtkIdList **which)
 
void ComputeCellCenter (vtkCell *cell, double *center, double *weights)
 
void GenerateRepresentationDataBounds (int level, vtkPolyData *pd)
 
void _generateRepresentationDataBounds (vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
 
void GenerateRepresentationWholeSpace (int level, vtkPolyData *pd)
 
void _generateRepresentationWholeSpace (vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys, int level)
 
void AddPolys (vtkKdNode *kd, vtkPoints *pts, vtkCellArray *polys)
 
void _printTree (int verbose)
 
int SearchNeighborsForDuplicate (int regionId, float *point, int **pointsSoFar, int *len, float tolerance, float tolerance2)
 
int SearchRegionForDuplicate (float *point, int *pointsSoFar, int len, float tolerance2)
 
int _FindClosestPointInRegion (int regionId, double x, double y, double z, double &dist2)
 
int FindClosestPointInSphere (double x, double y, double z, double radius, int skipRegion, double &dist2)
 
int _ViewOrderRegionsInDirection (vtkIntArray *IdsOfInterest, const double dop[3], vtkIntArray *orderedList)
 
int _ViewOrderRegionsFromPosition (vtkIntArray *IdsOfInterest, const double pos[3], vtkIntArray *orderedList)
 
void SetInputDataInfo (int i, int dims[3], double origin[3], double spacing[3])
 
int CheckInputDataInfo (int i, int dims[3], double origin[3], double spacing[3])
 
void ClearLastBuildCache ()
 
void NewPartitioningRequest (int req)
 
 vtkKdTree (const vtkKdTree &)=delete
 
void operator= (const vtkKdTree &)=delete
 
- Protected Member Functions inherited from vtkLocator
 vtkLocator ()
 
 ~vtkLocator () override
 
void ReportReferences (vtkGarbageCollector *) override
 
- Protected Member Functions inherited from vtkObject
 vtkObject ()
 
 ~vtkObject () override
 
void RegisterInternal (vtkObjectBase *, vtkTypeBool check) override
 
void UnRegisterInternal (vtkObjectBase *, vtkTypeBool check) override
 
void InternalGrabFocus (vtkCommand *mouseEvents, vtkCommand *keypressEvents=nullptr)
 These methods allow a command to exclusively grab all events. More...
 
void InternalReleaseFocus ()
 
- Protected Member Functions inherited from vtkObjectBase
 vtkObjectBase ()
 
virtual ~vtkObjectBase ()
 
virtual void CollectRevisions (ostream &)
 
 vtkObjectBase (const vtkObjectBase &)
 
void operator= (const vtkObjectBase &)
 

Static Protected Member Functions

static void DeleteAllDescendants (vtkKdNode *nd)
 
static void GetLeafNodeIds (vtkKdNode *node, vtkIntArray *ids)
 Adds to the vtkIntArray the list of region IDs of all leaf nodes in the given node. More...
 
static void _SetNewBounds (vtkKdNode *kd, double *b, int *fixDim)
 
static void CopyChildNodes (vtkKdNode *to, vtkKdNode *from)
 
static void CopyKdNode (vtkKdNode *to, vtkKdNode *from)
 
static void SetDataBoundsToSpatialBounds (vtkKdNode *kd)
 
static void ZeroNumberOfPoints (vtkKdNode *kd)
 
static int __ViewOrderRegionsInDirection (vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double dir[3], int nextId)
 
static int __ViewOrderRegionsFromPosition (vtkKdNode *node, vtkIntArray *list, vtkIntArray *IdsOfInterest, const double pos[3], int nextId)
 
static int __ConvexSubRegions (int *ids, int len, vtkKdNode *tree, vtkKdNode **nodes)
 
static int FoundId (vtkIntArray *idArray, int id)
 
static void __printTree (vtkKdNode *kd, int depth, int verbose)
 
static int MidValue (int dim, float *c1, int nvals, double &coord)
 
static int Select (int dim, float *c1, int *ids, int nvals, double &coord)
 
static float FindMaxLeftHalf (int dim, float *c1, int K)
 
static void _Select (int dim, float *X, int *ids, int L, int R, int K)
 
static int ComputeLevel (vtkKdNode *kd)
 
static int SelfOrder (int id, vtkKdNode *kd)
 
static int findRegion (vtkKdNode *node, float x, float y, float z)
 
static int findRegion (vtkKdNode *node, double x, double y, double z)
 
static vtkKdNode ** _GetRegionsAtLevel (int level, vtkKdNode **nodes, vtkKdNode *kd)
 
static void AddNewRegions (vtkKdNode *kd, float *c1, int midpt, int dim, double coord)
 

Protected Attributes

vtkBSPIntersectionsBSPCalculator
 
int UserDefinedCuts
 
int ValidDirections
 
vtkKdNodeTop
 
vtkKdNode ** RegionList
 
vtkTimerLogTimerLog
 
vtkDataSetCollectionDataSets
 
double ProgressScale
 
double ProgressOffset
 
int NumberOfRegionsOrLess
 
int NumberOfRegionsOrMore
 
vtkTypeBool IncludeRegionBoundaryCells
 
double CellBoundsCache [6]
 
vtkTypeBool GenerateRepresentationUsingDataBounds
 
struct _cellList CellList
 
int * CellRegionList
 
int MinCells
 
int NumberOfRegions
 
vtkTypeBool Timing
 
double FudgeFactor
 
int NumberOfLocatorPoints
 
float * LocatorPoints
 
int * LocatorIds
 
int * LocatorRegionLocation
 
float MaxWidth
 
int LastNumDataSets
 
int LastDataCacheSize
 
vtkDataSet ** LastInputDataSets
 
unsigned long * LastDataSetObserverTags
 
int * LastDataSetType
 
double * LastInputDataInfo
 
double * LastBounds
 
vtkIdTypeLastNumPoints
 
vtkIdTypeLastNumCells
 
vtkBSPCutsCuts
 
double Progress
 
- Protected Attributes inherited from vtkLocator
vtkDataSetDataSet
 
vtkTypeBool Automatic
 
double Tolerance
 
int MaxLevel
 
int Level
 
vtkTimeStamp BuildTime
 
- Protected Attributes inherited from vtkObject
bool Debug
 
vtkTimeStamp MTime
 
vtkSubjectHelper * SubjectHelper
 
- Protected Attributes inherited from vtkObjectBase
std::atomic< int32_t > ReferenceCount
 
vtkWeakPointerBase ** WeakPointers
 

Detailed Description

a Kd-tree spatial decomposition of a set of points

Given one or more vtkDataSets, create a load balancing
k-d tree decomposition of the points at the center of the cells.
Or, create a k-d tree point locator from a list of points.

This class can also generate a PolyData representation of
the boundaries of the spatial regions in the decomposition.

It can sort the regions with respect to a viewing direction,
and it can decompose a list of regions into subsets, each
of which represent a convex spatial region (since many algorithms
require a convex region).

If the points were derived from cells, vtkKdTree
can create a list of cell Ids for each region for each data set.
Two lists are available - all cells with centroid in the region,
and all cells that intersect the region but whose centroid lies
in another region.

For the purpose of removing duplicate points quickly from large
data sets, or for finding nearby points, we added another mode for
building the locator.  BuildLocatorFromPoints will build a k-d tree
from one or more vtkPoints objects.  This can be followed by
BuildMapForDuplicatePoints which returns a mapping from the original
ids to a subset of the ids that is unique within a supplied
tolerance, or you can use FindPoint and FindClosestPoint to
locate points in the original set that the tree was built from.
See also
vtkLocator vtkCellLocator vtkPKdTree

Definition at line 75 of file vtkKdTree.h.

Member Typedef Documentation

◆ Superclass

Definition at line 78 of file vtkKdTree.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum
protected
Enumerator
XDIM 
YDIM 
ZDIM 

Definition at line 660 of file vtkKdTree.h.

Constructor & Destructor Documentation

◆ vtkKdTree() [1/2]

vtkKdTree::vtkKdTree ( )
protected

◆ ~vtkKdTree()

vtkKdTree::~vtkKdTree ( )
overrideprotected

◆ vtkKdTree() [2/2]

vtkKdTree::vtkKdTree ( const vtkKdTree )
protecteddelete

Member Function Documentation

◆ IsTypeOf()

static vtkTypeBool vtkKdTree::IsTypeOf ( const char *  type)
static

◆ IsA()

virtual vtkTypeBool vtkKdTree::IsA ( const char *  name)
virtual

Return 1 if this class is the same type of (or a subclass of) the named class.

Returns 0 otherwise. This method works in combination with vtkTypeMacro found in vtkSetGet.h.

Reimplemented from vtkLocator.

Reimplemented in vtkPKdTree.

◆ SafeDownCast()

static vtkKdTree* vtkKdTree::SafeDownCast ( vtkObjectBase o)
static

◆ NewInstanceInternal()

virtual vtkObjectBase* vtkKdTree::NewInstanceInternal ( ) const
protectedvirtual

Reimplemented from vtkLocator.

Reimplemented in vtkPKdTree.

◆ NewInstance()

vtkKdTree* vtkKdTree::NewInstance ( ) const

◆ PrintSelf()

void vtkKdTree::PrintSelf ( ostream &  os,
vtkIndent  indent 
)
overridevirtual

Methods invoked by print to print information about the object including superclasses.

Typically not called by the user (use Print() instead) but used in the hierarchical print process to combine the output of several classes.

Reimplemented from vtkObject.

Reimplemented in vtkPKdTree.

◆ New()

static vtkKdTree* vtkKdTree::New ( )
static

◆ TimingOn()

virtual void vtkKdTree::TimingOn ( )
virtual

Turn on timing of the k-d tree build.

◆ TimingOff()

virtual void vtkKdTree::TimingOff ( )
virtual

◆ SetTiming()

virtual void vtkKdTree::SetTiming ( vtkTypeBool  )
virtual

◆ GetTiming()

virtual vtkTypeBool vtkKdTree::GetTiming ( )
virtual

◆ SetMinCells()

virtual void vtkKdTree::SetMinCells ( int  )
virtual

Minimum number of cells per spatial region.

Default is 100.

◆ GetMinCells()

virtual int vtkKdTree::GetMinCells ( )
virtual

◆ GetNumberOfRegionsOrLess()

virtual int vtkKdTree::GetNumberOfRegionsOrLess ( )
virtual

Set/Get the number of spatial regions you want to get close to without going over.

(The number of spatial regions is normally a power of two.) Call this before BuildLocator(). Default is unset (0).

◆ SetNumberOfRegionsOrLess()

virtual void vtkKdTree::SetNumberOfRegionsOrLess ( int  )
virtual

◆ GetNumberOfRegionsOrMore()

virtual int vtkKdTree::GetNumberOfRegionsOrMore ( )
virtual

Set/Get the number of spatial regions you want to get close to while having at least this many regions.

(The number of spatial regions is normally a power of two.) Default is unset (0).

◆ SetNumberOfRegionsOrMore()

virtual void vtkKdTree::SetNumberOfRegionsOrMore ( int  )
virtual

◆ GetFudgeFactor()

virtual double vtkKdTree::GetFudgeFactor ( )
virtual

Some algorithms on k-d trees require a value that is a very small distance relative to the diameter of the entire space divided by the k-d tree.

This factor is the maximum axis-aligned width of the space multiplied by 10e-6.

◆ SetFudgeFactor()

virtual void vtkKdTree::SetFudgeFactor ( double  )
virtual

◆ GetCuts()

virtual vtkBSPCuts* vtkKdTree::GetCuts ( )
virtual

Get a vtkBSPCuts object, a general object representing an axis- aligned spatial partitioning.

Used by vtkBSPIntersections.

◆ SetCuts() [1/2]

void vtkKdTree::SetCuts ( vtkBSPCuts cuts)

Normally the k-d tree is computed from the dataset(s) provided in SetDataSet.

Alternatively, you can provide the cuts that will be applied by calling SetCuts.

◆ OmitXPartitioning()

void vtkKdTree::OmitXPartitioning ( )

Omit partitions along the X axis, yielding shafts in the X direction.

◆ OmitYPartitioning()

void vtkKdTree::OmitYPartitioning ( )

Omit partitions along the Y axis, yielding shafts in the Y direction.

◆ OmitZPartitioning()

void vtkKdTree::OmitZPartitioning ( )

Omit partitions along the Z axis, yielding shafts in the Z direction.

◆ OmitXYPartitioning()

void vtkKdTree::OmitXYPartitioning ( )

Omit partitions along the X and Y axes, yielding slabs along Z.

◆ OmitYZPartitioning()

void vtkKdTree::OmitYZPartitioning ( )

Omit partitions along the Y and Z axes, yielding slabs along X.

◆ OmitZXPartitioning()

void vtkKdTree::OmitZXPartitioning ( )

Omit partitions along the Z and X axes, yielding slabs along Y.

◆ OmitNoPartitioning()

void vtkKdTree::OmitNoPartitioning ( )

Partition along all three axes - this is the default.

◆ SetDataSet()

void vtkKdTree::SetDataSet ( vtkDataSet set)
overridevirtual

This class can compute a spatial decomposition based on the cells in a list of one or more input data sets.

SetDataSet sets the first data set in the list to the named set. SetNthDataSet sets the data set at index N to the data set named. RemoveData set takes either the data set itself or an index and removes that data set from the list of data sets. AddDataSet adds a data set to the list of data sets. Clear out all data sets and replace with single data set. For backward compatibility with superclass.

Reimplemented from vtkLocator.

◆ AddDataSet()

virtual void vtkKdTree::AddDataSet ( vtkDataSet set)
virtual

This class can compute a spatial decomposition based on the cells in a list of one or more input data sets.

Add them one at a time with this method.

◆ RemoveDataSet() [1/2]

virtual void vtkKdTree::RemoveDataSet ( int  index)
virtual

Remove the given data set.

◆ RemoveDataSet() [2/2]

virtual void vtkKdTree::RemoveDataSet ( vtkDataSet set)
virtual

◆ RemoveAllDataSets()

virtual void vtkKdTree::RemoveAllDataSets ( )
virtual

◆ GetNumberOfDataSets()

int vtkKdTree::GetNumberOfDataSets ( )

Get the number of data sets included in spatial partitioning.

◆ GetDataSet() [1/2]

vtkDataSet* vtkKdTree::GetDataSet ( int  n)

Get the nth defined data set in the spatial partitioning.

(If you used SetNthDataSet to define 0,1 and 3 and ask for data set 2, you get 3.) Return the n'th data set.

◆ GetDataSet() [2/2]

vtkDataSet* vtkKdTree::GetDataSet ( )
inlineoverridevirtual

Return the 0'th data set.

For compatibility with the superclass' interface.

Reimplemented from vtkLocator.

Definition at line 231 of file vtkKdTree.h.

◆ GetDataSets()

virtual vtkDataSetCollection* vtkKdTree::GetDataSets ( )
virtual

Return a collection of all the data sets.

◆ GetDataSetIndex()

int vtkKdTree::GetDataSetIndex ( vtkDataSet set)

Return the index of the given data set.

Returns -1 if that data set does not exist.

◆ GetBounds()

void vtkKdTree::GetBounds ( double *  bounds)

Get the spatial bounds of the entire k-d tree space.

Sets bounds array to xmin, xmax, ymin, ymax, zmin, zmax.

◆ SetNewBounds()

void vtkKdTree::SetNewBounds ( double *  bounds)

There are certain applications where you want the bounds of the k-d tree space to be at least as large as a specified box.

If the k-d tree has been built, you can expand it's bounds with this method. If the bounds supplied are smaller than those computed, they will be ignored.

◆ GetNumberOfRegions()

virtual int vtkKdTree::GetNumberOfRegions ( )
virtual

The number of leaf nodes of the tree, the spatial regions.

◆ GetRegionBounds()

void vtkKdTree::GetRegionBounds ( int  regionID,
double  bounds[6] 
)

Get the spatial bounds of k-d tree region.

◆ GetRegionDataBounds()

void vtkKdTree::GetRegionDataBounds ( int  regionID,
double  bounds[6] 
)

Get the bounds of the data within the k-d tree region.

◆ PrintTree()

void vtkKdTree::PrintTree ( )

Print out nodes of kd tree.

◆ PrintVerboseTree()

void vtkKdTree::PrintVerboseTree ( )

◆ PrintRegion()

void vtkKdTree::PrintRegion ( int  id)

Print out leaf node data for given id.

◆ CreateCellLists() [1/4]

void vtkKdTree::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 the region.

These lists are obtained with GetCellList(). If no DataSet is specified, the cell list is created for DataSet 0. If no list of requested regions is provided, the cell lists for all regions are created.

When CreateCellLists is called again, the lists created on the previous call are deleted.

◆ CreateCellLists() [2/4]

void vtkKdTree::CreateCellLists ( vtkDataSet set,
int *  regionReqList,
int  reqListSize 
)

◆ CreateCellLists() [3/4]

void vtkKdTree::CreateCellLists ( int *  regionReqList,
int  listSize 
)

◆ CreateCellLists() [4/4]

void vtkKdTree::CreateCellLists ( )

◆ SetIncludeRegionBoundaryCells()

virtual void vtkKdTree::SetIncludeRegionBoundaryCells ( vtkTypeBool  )
virtual

If IncludeRegionBoundaryCells is ON, CreateCellLists() will also create a list of cells which intersect a given region, but are not assigned to the region.

These lists are obtained with GetBoundaryCellList(). Default is OFF.

◆ GetIncludeRegionBoundaryCells()

virtual vtkTypeBool vtkKdTree::GetIncludeRegionBoundaryCells ( )
virtual

◆ IncludeRegionBoundaryCellsOn()

virtual void vtkKdTree::IncludeRegionBoundaryCellsOn ( )
virtual

◆ IncludeRegionBoundaryCellsOff()

virtual void vtkKdTree::IncludeRegionBoundaryCellsOff ( )
virtual

◆ DeleteCellLists()

void vtkKdTree::DeleteCellLists ( )

Free the memory used by the cell lists.

◆ GetCellList()

vtkIdList* vtkKdTree::GetCellList ( int  regionID)

Get the cell list for a region.

This returns a pointer to vtkKdTree's memory, so don't free it.

◆ GetBoundaryCellList()

vtkIdList* vtkKdTree::GetBoundaryCellList ( int  regionID)

The cell list obtained with GetCellList is the list of all cells such that their centroid is contained in the spatial region.

It may also be desirable to get a list of all cells intersecting a spatial region, but with centroid in some other region. This is that list. This list is computed in CreateCellLists() if and only if IncludeRegionBoundaryCells is ON. This returns a pointer to KdTree's memory, so don't free it.

◆ GetCellLists() [1/3]

vtkIdType vtkKdTree::GetCellLists ( vtkIntArray regions,
int  set,
vtkIdList inRegionCells,
vtkIdList onBoundaryCells 
)

For a list of regions, get two cell lists.

The first lists the IDs all cells whose centroids lie in one of the regions. The second lists the IDs of all cells that intersect the regions, but whose centroid lies in a region not on the list.

The total number of cell IDs written to both lists is returned. Either list pointer passed in can be nullptr, and it will be ignored. If there are multiple data sets, you must specify which data set you wish cell IDs for.

The caller should delete these two lists when done. This method uses the cell lists created in CreateCellLists(). If the cell list for any of the requested regions does not exist, then this method will call CreateCellLists() to create cell lists for every region of the k-d tree. You must remember to DeleteCellLists() when done with all calls to this method, as cell lists can require a great deal of memory.

◆ GetCellLists() [2/3]

vtkIdType vtkKdTree::GetCellLists ( vtkIntArray regions,
vtkDataSet set,
vtkIdList inRegionCells,
vtkIdList onBoundaryCells 
)

◆ GetCellLists() [3/3]

vtkIdType vtkKdTree::GetCellLists ( vtkIntArray regions,
vtkIdList inRegionCells,
vtkIdList onBoundaryCells 
)

◆ GetRegionContainingCell() [1/3]

int vtkKdTree::GetRegionContainingCell ( vtkDataSet set,
vtkIdType  cellID 
)

Get the id of the region containing the cell centroid.

If no DataSet is specified, assume DataSet 0. If you need the region ID for every cell, use AllGetRegionContainingCell instead. It is more efficient.

◆ GetRegionContainingCell() [2/3]

int vtkKdTree::GetRegionContainingCell ( int  set,
vtkIdType  cellID 
)

◆ GetRegionContainingCell() [3/3]

int vtkKdTree::GetRegionContainingCell ( vtkIdType  cellID)

◆ AllGetRegionContainingCell()

int* vtkKdTree::AllGetRegionContainingCell ( )

Get a list (in order by data set by cell id) of the region IDs of the region containing the centroid for each cell.

This is faster than calling GetRegionContainingCell for each cell in the DataSet. vtkKdTree uses this list, so don't delete it.

◆ GetRegionContainingPoint()

int vtkKdTree::GetRegionContainingPoint ( double  x,
double  y,
double  z 
)

Get the id of the region containing the specified location.

◆ BuildLocator()

void vtkKdTree::BuildLocator ( )
overridevirtual

Create the k-d tree decomposition of the cells of the data set or data sets.

Cells are assigned to k-d tree spatial regions based on the location of their centroids.

Implements vtkLocator.

Reimplemented in vtkPKdTree.

◆ MinimalNumberOfConvexSubRegions()

int vtkKdTree::MinimalNumberOfConvexSubRegions ( vtkIntArray regionIdList,
double **  convexRegionBounds 
)

Given a list of region IDs, determine the decomposition of these regions into the minimal number of convex subregions.

Due to the way the k-d tree is constructed, those convex subregions will be axis-aligned boxes. Return the minimal number of such convex regions that compose the original region list. This call will set convexRegionBounds to point to a list of the bounds of these regions. Caller should free this. There will be six values for each convex subregion (xmin, xmax, ymin, ymax, zmin, zmax). If the regions in the regionIdList form a box already, a "1" is returned and the second argument contains the bounds of the box.

◆ ViewOrderAllRegionsInDirection()

int vtkKdTree::ViewOrderAllRegionsInDirection ( const double  directionOfProjection[3],
vtkIntArray orderedList 
)

Given a direction of projection (typically obtained with vtkCamera::GetDirectionOfProjection()), this method, creates a list of the k-d tree region IDs in order from front to back with respect to that direction.

The number of ordered regions is returned. Use this method to view order regions for cameras that use parallel projection.

◆ ViewOrderRegionsInDirection()

int vtkKdTree::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 k-d tree region IDs in order from front to back with respect to that direction.

The number of ordered regions is returned. Use this method to view order regions for cameras that use parallel projection.

◆ ViewOrderAllRegionsFromPosition()

int vtkKdTree::ViewOrderAllRegionsFromPosition ( const double  directionOfProjection[3],
vtkIntArray orderedList 
)

Given a camera position (typically obtained with vtkCamera::GetPosition()), this method, creates a list of the k-d tree region IDs in order from front to back with respect to that direction.

The number of ordered regions is returned. Use this method to view order regions for cameras that use perspective projection.

◆ ViewOrderRegionsFromPosition()

int vtkKdTree::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 tree region IDs in order from front to back with respect to that direction.

The number of ordered regions is returned. Use this method to view order regions for cameras that use perspective projection.

◆ BuildLocatorFromPoints() [1/3]

void vtkKdTree::BuildLocatorFromPoints ( vtkPointSet pointset)

This is a special purpose locator that builds a k-d tree to find duplicate and near-by points.

It builds the tree from one or more vtkPoints objects instead of from the cells of a vtkDataSet. This build would normally be followed by BuildMapForDuplicatePoints, FindPoint, or FindClosestPoint. Since this will build a normal k-d tree, all the region intersection queries will still work, as will most other calls except those that have "Cell" in the name.

This method works most efficiently when the point arrays are float arrays.

◆ BuildLocatorFromPoints() [2/3]

void vtkKdTree::BuildLocatorFromPoints ( vtkPoints ptArray)

◆ BuildLocatorFromPoints() [3/3]

void vtkKdTree::BuildLocatorFromPoints ( vtkPoints **  ptArray,
int  numPtArrays 
)

◆ BuildMapForDuplicatePoints()

vtkIdTypeArray* vtkKdTree::BuildMapForDuplicatePoints ( float  tolerance)

This call returns a mapping from the original point IDs supplied to BuildLocatorFromPoints to a subset of those IDs that is unique within the specified tolerance.

If points 2, 5, and 12 are the same, then IdMap[2] = IdMap[5] = IdMap[12] = 2 (or 5 or 12).

"original point IDs" - For point IDs we start at 0 for the first point in the first vtkPoints object, and increase by 1 for subsequent points and subsequent vtkPoints objects.

You must have called BuildLocatorFromPoints() before calling this. You are responsible for deleting the returned array.

◆ FindPoint() [1/2]

vtkIdType vtkKdTree::FindPoint ( double *  x)

Find the Id of the point that was previously supplied to BuildLocatorFromPoints().

Returns -1 if the point was not in the original array.

◆ FindPoint() [2/2]

vtkIdType vtkKdTree::FindPoint ( double  x,
double  y,
double  z 
)

◆ FindClosestPoint() [1/2]

vtkIdType vtkKdTree::FindClosestPoint ( double *  x,
double &  dist2 
)

Find the Id of the point that was previously supplied to BuildLocatorFromPoints() which is closest to the given point.

Set the square of the distance between the two points.

◆ FindClosestPoint() [2/2]

vtkIdType vtkKdTree::FindClosestPoint ( double  x,
double  y,
double  z,
double &  dist2 
)

◆ FindClosestPointWithinRadius()

vtkIdType vtkKdTree::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.

dist2 returns the squared distance to the point.

◆ FindClosestPointInRegion() [1/2]

vtkIdType vtkKdTree::FindClosestPointInRegion ( int  regionId,
double *  x,
double &  dist2 
)

Find the Id of the point in the given region which is closest to the given point.

Return the ID of the point, and set the square of the distance of between the points.

◆ FindClosestPointInRegion() [2/2]

vtkIdType vtkKdTree::FindClosestPointInRegion ( int  regionId,
double  x,
double  y,
double  z,
double &  dist2 
)

◆ FindPointsWithinRadius() [1/2]

void vtkKdTree::FindPointsWithinRadius ( double  R,
const double  x[3],
vtkIdList result 
)

Find all points within a specified radius R of position x.

The result is not sorted in any specific manner. These methods are thread safe if BuildLocator() is directly or indirectly called from a single thread first.

◆ FindClosestNPoints()

void vtkKdTree::FindClosestNPoints ( int  N,
const double  x[3],
vtkIdList result 
)

Find the closest N points to a position.

This returns the closest N points to a position. A faster method could be created that returned N close points to a position, but necessarily the exact N closest. The returned points are sorted from closest to farthest. These methods are thread safe if BuildLocator() is directly or indirectly called from a single thread first.

◆ GetPointsInRegion()

vtkIdTypeArray* vtkKdTree::GetPointsInRegion ( int  regionId)

Get a list of the original IDs of all points in a region.

You must have called BuildLocatorFromPoints before calling this.

◆ FreeSearchStructure()

void vtkKdTree::FreeSearchStructure ( )
overridevirtual

Delete the k-d tree data structure.

Also delete any cell lists that were computed with CreateCellLists().

Implements vtkLocator.

◆ GenerateRepresentation() [1/2]

void vtkKdTree::GenerateRepresentation ( int  level,
vtkPolyData pd 
)
overridevirtual

Create a polydata representation of the boundaries of the k-d tree regions.

If level equals GetLevel(), the leaf nodes are represented.

Implements vtkLocator.

◆ GenerateRepresentation() [2/2]

void vtkKdTree::GenerateRepresentation ( int *  regionList,
int  len,
vtkPolyData pd 
)

Generate a polygonal representation of a list of regions.

Only leaf nodes have region IDs, so these will be leaf nodes.

◆ GenerateRepresentationUsingDataBoundsOn()

virtual void vtkKdTree::GenerateRepresentationUsingDataBoundsOn ( )
virtual

The polydata representation of the k-d tree shows the boundaries of the k-d tree decomposition spatial regions.

The data inside the regions may not occupy the entire space. To draw just the bounds of the data in the regions, set this variable ON.

◆ GenerateRepresentationUsingDataBoundsOff()

virtual void vtkKdTree::GenerateRepresentationUsingDataBoundsOff ( )
virtual

◆ SetGenerateRepresentationUsingDataBounds()

virtual void vtkKdTree::SetGenerateRepresentationUsingDataBounds ( vtkTypeBool  )
virtual

◆ GetGenerateRepresentationUsingDataBounds()

virtual vtkTypeBool vtkKdTree::GetGenerateRepresentationUsingDataBounds ( )
virtual

◆ PrintTiming()

virtual void vtkKdTree::PrintTiming ( ostream &  os,
vtkIndent  indent 
)
virtual

Print timing of k-d tree build.

Reimplemented in vtkPKdTree.

◆ NewGeometry() [1/2]

virtual int vtkKdTree::NewGeometry ( )
virtual

Return 1 if the geometry of the input data sets has changed since the last time the k-d tree was built.

◆ NewGeometry() [2/2]

virtual int vtkKdTree::NewGeometry ( vtkDataSet **  sets,
int  numDataSets 
)
virtual

Return 1 if the geometry of these data sets differs for the geometry of the last data sets used to build the k-d tree.

◆ InvalidateGeometry()

virtual void vtkKdTree::InvalidateGeometry ( )
virtual

Forget about the last geometry used.

The next call to NewGeometry will return 1. A new k-d tree will be built the next time BuildLocator is called.

◆ CopyTree()

static vtkKdNode* vtkKdTree::CopyTree ( vtkKdNode kd)
static

Create a copy of the binary tree representation of the k-d tree spatial partitioning provided.

◆ FindPointsInArea() [1/2]

void vtkKdTree::FindPointsInArea ( double *  area,
vtkIdTypeArray ids,
bool  clearArray = true 
)

Fill ids with points found in area.

The area is a 6-tuple containing (xmin, xmax, ymin, ymax, zmin, zmax). This method will clear the array by default. To append ids to an array, set clearArray to false.

◆ SetCalculator()

void vtkKdTree::SetCalculator ( vtkKdNode kd)
protected

◆ ProcessUserDefinedCuts()

int vtkKdTree::ProcessUserDefinedCuts ( double *  bounds)
protected

◆ SetCuts() [2/2]

void vtkKdTree::SetCuts ( vtkBSPCuts cuts,
int  userDefined 
)
protected

◆ UpdateBuildTime()

void vtkKdTree::UpdateBuildTime ( )
protected

Save enough state so NewGeometry() can work, and update the BuildTime time stamp.

◆ DivideTest()

int vtkKdTree::DivideTest ( int  numberOfPoints,
int  level 
)
protected

Prior to dividing a region at level "level", of size "numberOfPoints", apply the tests implied by MinCells, NumberOfRegionsOrMore and NumberOfRegionsOrLess.

Return 1 if it's OK to divide the region, 0 if you should not.

◆ DeleteAllDescendants()

static void vtkKdTree::DeleteAllDescendants ( vtkKdNode nd)
staticprotected

◆ BuildRegionList()

void vtkKdTree::BuildRegionList ( )
protected

◆ SelectCutDirection()

virtual int vtkKdTree::SelectCutDirection ( vtkKdNode kd)
protectedvirtual

◆ SetActualLevel()

void vtkKdTree::SetActualLevel ( )
inlineprotected

Definition at line 678 of file vtkKdTree.h.

◆ GetRegionsAtLevel()

void vtkKdTree::GetRegionsAtLevel ( int  level,
vtkKdNode **  nodes 
)
protected

Get back a list of the nodes at a specified level, nodes must be preallocated to hold 2^^(level) node structures.

◆ GetLeafNodeIds()

static void vtkKdTree::GetLeafNodeIds ( vtkKdNode node,
vtkIntArray ids 
)
staticprotected

Adds to the vtkIntArray the list of region IDs of all leaf nodes in the given node.

◆ GetNumberOfCells()

int vtkKdTree::GetNumberOfCells ( )
protected

Returns the total number of cells in all the data sets.

◆ GetDataSetsNumberOfCells()

int vtkKdTree::GetDataSetsNumberOfCells ( int  set1,
int  set2 
)
protected

Returns the total number of cells in data set 1 through data set 2.

◆ ComputeCellCenter() [1/3]

void vtkKdTree::ComputeCellCenter ( vtkDataSet set,
int  cellId,
float *  center 
)
protected

Get or compute the center of one cell.

If the DataSet is nullptr, the first DataSet is used. This is the point used in determining to which spatial region the cell is assigned.

◆ ComputeCellCenter() [2/3]

void vtkKdTree::ComputeCellCenter ( vtkDataSet set,
int  cellId,
double *  center 
)
protected

◆ ComputeCellCenters() [1/3]

float* vtkKdTree::ComputeCellCenters ( )
protected

Compute and return a pointer to a list of all cell centers, in order by data set by cell Id.

If a DataSet is specified cell centers for cells of that data only are returned. If no DataSet is specified, the cell centers of cells in all DataSets are returned. The caller should free the list of cell centers when done.

◆ ComputeCellCenters() [2/3]

float* vtkKdTree::ComputeCellCenters ( int  set)
protected

◆ ComputeCellCenters() [3/3]

float* vtkKdTree::ComputeCellCenters ( vtkDataSet set)
protected

◆ UpdateProgress()

void vtkKdTree::UpdateProgress ( double  amount)
protected

Modelled on vtkAlgorithm::UpdateProgress().

Update the progress when building the locator. Fires vtkCommand::ProgressEvent.

◆ SetProgress()

virtual void vtkKdTree::SetProgress ( double  )
protectedvirtual

Set/Get the execution progress of a process object.

◆ GetProgress()

virtual double vtkKdTree::GetProgress ( )
protectedvirtual

◆ UpdateSubOperationProgress()

void vtkKdTree::UpdateSubOperationProgress ( double  amount)
protected

◆ _SetNewBounds()

static void vtkKdTree::_SetNewBounds ( vtkKdNode kd,
double *  b,
int *  fixDim 
)
staticprotected

◆ CopyChildNodes()

static void vtkKdTree::CopyChildNodes ( vtkKdNode to,
vtkKdNode from 
)
staticprotected

◆ CopyKdNode()

static void vtkKdTree::CopyKdNode ( vtkKdNode to,
vtkKdNode from 
)
staticprotected

◆ SetDataBoundsToSpatialBounds()

static void vtkKdTree::SetDataBoundsToSpatialBounds ( vtkKdNode kd)
staticprotected

◆ ZeroNumberOfPoints()

static void vtkKdTree::ZeroNumberOfPoints ( vtkKdNode kd)
staticprotected

◆ FindPointsWithinRadius() [2/2]

void vtkKdTree::FindPointsWithinRadius ( vtkKdNode node,
double  R2,
const double  x[3],
vtkIdList ids 
)
protected

◆ AddAllPointsInRegion() [1/2]

void vtkKdTree::AddAllPointsInRegion ( vtkKdNode node,
vtkIdList ids 
)
protected

◆ FindPointsInArea() [2/2]

void vtkKdTree::FindPointsInArea ( vtkKdNode node,
double *  area,
vtkIdTypeArray ids 
)
protected

◆ AddAllPointsInRegion() [2/2]

void vtkKdTree::AddAllPointsInRegion ( vtkKdNode node,
vtkIdTypeArray ids 
)
protected

◆ DivideRegion()

int vtkKdTree::DivideRegion ( vtkKdNode kd,
float *  c1,
int *  ids,
int  nlevels 
)
protected

◆ DoMedianFind()

void vtkKdTree::DoMedianFind ( vtkKdNode kd,
float *  c1,
int *  ids,
int  d1,
int  d2,
int  d3 
)
protected

◆ SelfRegister()

void vtkKdTree::SelfRegister ( vtkKdNode kd)
protected

◆ InitializeCellLists()

void vtkKdTree::InitializeCellLists ( )
protected

◆ GetList()

vtkIdList* vtkKdTree::GetList ( int  regionId,
vtkIdList **  which 
)
protected

◆ ComputeCellCenter() [3/3]

void vtkKdTree::ComputeCellCenter ( vtkCell cell,
double *  center,
double *  weights 
)
protected

◆ GenerateRepresentationDataBounds()

void vtkKdTree::GenerateRepresentationDataBounds ( int  level,
vtkPolyData pd 
)
protected

◆ _generateRepresentationDataBounds()

void vtkKdTree::_generateRepresentationDataBounds ( vtkKdNode kd,
vtkPoints pts,
vtkCellArray polys,
int  level 
)
protected

◆ GenerateRepresentationWholeSpace()

void vtkKdTree::GenerateRepresentationWholeSpace ( int  level,
vtkPolyData pd 
)
protected

◆ _generateRepresentationWholeSpace()

void vtkKdTree::_generateRepresentationWholeSpace ( vtkKdNode kd,
vtkPoints pts,
vtkCellArray polys,
int  level 
)
protected

◆ AddPolys()

void vtkKdTree::AddPolys ( vtkKdNode kd,
vtkPoints pts,
vtkCellArray polys 
)
protected

◆ _printTree()

void vtkKdTree::_printTree ( int  verbose)
protected

◆ SearchNeighborsForDuplicate()

int vtkKdTree::SearchNeighborsForDuplicate ( int  regionId,
float *  point,
int **  pointsSoFar,
int *  len,
float  tolerance,
float  tolerance2 
)
protected

◆ SearchRegionForDuplicate()

int vtkKdTree::SearchRegionForDuplicate ( float *  point,
int *  pointsSoFar,
int  len,
float  tolerance2 
)
protected

◆ _FindClosestPointInRegion()

int vtkKdTree::_FindClosestPointInRegion ( int  regionId,
double  x,
double  y,
double  z,
double &  dist2 
)
protected

◆ FindClosestPointInSphere()

int vtkKdTree::FindClosestPointInSphere ( double  x,
double  y,
double  z,
double  radius,
int  skipRegion,
double &  dist2 
)
protected

◆ _ViewOrderRegionsInDirection()

int vtkKdTree::_ViewOrderRegionsInDirection ( vtkIntArray IdsOfInterest,
const double  dop[3],
vtkIntArray orderedList 
)
protected

◆ __ViewOrderRegionsInDirection()

static int vtkKdTree::__ViewOrderRegionsInDirection ( vtkKdNode node,
vtkIntArray list,
vtkIntArray IdsOfInterest,
const double  dir[3],
int  nextId 
)
staticprotected

◆ _ViewOrderRegionsFromPosition()

int vtkKdTree::_ViewOrderRegionsFromPosition ( vtkIntArray IdsOfInterest,
const double  pos[3],
vtkIntArray orderedList 
)
protected

◆ __ViewOrderRegionsFromPosition()

static int vtkKdTree::__ViewOrderRegionsFromPosition ( vtkKdNode node,
vtkIntArray list,
vtkIntArray IdsOfInterest,
const double  pos[3],
int  nextId 
)
staticprotected

◆ __ConvexSubRegions()

static int vtkKdTree::__ConvexSubRegions ( int *  ids,
int  len,
vtkKdNode tree,
vtkKdNode **  nodes 
)
staticprotected

◆ FoundId()

static int vtkKdTree::FoundId ( vtkIntArray idArray,
int  id 
)
staticprotected

◆ SetInputDataInfo()

void vtkKdTree::SetInputDataInfo ( int  i,
int  dims[3],
double  origin[3],
double  spacing[3] 
)
protected

◆ CheckInputDataInfo()

int vtkKdTree::CheckInputDataInfo ( int  i,
int  dims[3],
double  origin[3],
double  spacing[3] 
)
protected

◆ ClearLastBuildCache()

void vtkKdTree::ClearLastBuildCache ( )
protected

◆ __printTree()

static void vtkKdTree::__printTree ( vtkKdNode kd,
int  depth,
int  verbose 
)
staticprotected

◆ MidValue()

static int vtkKdTree::MidValue ( int  dim,
float *  c1,
int  nvals,
double &  coord 
)
staticprotected

◆ Select()

static int vtkKdTree::Select ( int  dim,
float *  c1,
int *  ids,
int  nvals,
double &  coord 
)
staticprotected

◆ FindMaxLeftHalf()

static float vtkKdTree::FindMaxLeftHalf ( int  dim,
float *  c1,
int  K 
)
staticprotected

◆ _Select()

static void vtkKdTree::_Select ( int  dim,
float *  X,
int *  ids,
int  L,
int  R,
int  K 
)
staticprotected

◆ ComputeLevel()

static int vtkKdTree::ComputeLevel ( vtkKdNode kd)
staticprotected

◆ SelfOrder()

static int vtkKdTree::SelfOrder ( int  id,
vtkKdNode kd 
)
staticprotected

◆ findRegion() [1/2]

static int vtkKdTree::findRegion ( vtkKdNode node,
float  x,
float  y,
float  z 
)
staticprotected

◆ findRegion() [2/2]

static int vtkKdTree::findRegion ( vtkKdNode node,
double  x,
double  y,
double  z 
)
staticprotected

◆ _GetRegionsAtLevel()

static vtkKdNode** vtkKdTree::_GetRegionsAtLevel ( int  level,
vtkKdNode **  nodes,
vtkKdNode kd 
)
staticprotected

◆ AddNewRegions()

static void vtkKdTree::AddNewRegions ( vtkKdNode kd,
float *  c1,
int  midpt,
int  dim,
double  coord 
)
staticprotected

◆ NewPartitioningRequest()

void vtkKdTree::NewPartitioningRequest ( int  req)
protected

◆ operator=()

void vtkKdTree::operator= ( const vtkKdTree )
protecteddelete

Member Data Documentation

◆ BSPCalculator

vtkBSPIntersections* vtkKdTree::BSPCalculator
protected

Definition at line 635 of file vtkKdTree.h.

◆ UserDefinedCuts

int vtkKdTree::UserDefinedCuts
protected

Definition at line 636 of file vtkKdTree.h.

◆ ValidDirections

int vtkKdTree::ValidDirections
protected

Definition at line 667 of file vtkKdTree.h.

◆ Top

vtkKdNode* vtkKdTree::Top
protected

Definition at line 669 of file vtkKdTree.h.

◆ RegionList

vtkKdNode** vtkKdTree::RegionList
protected

Definition at line 670 of file vtkKdTree.h.

◆ TimerLog

vtkTimerLog* vtkKdTree::TimerLog
protected

Definition at line 672 of file vtkKdTree.h.

◆ DataSets

vtkDataSetCollection* vtkKdTree::DataSets
protected

Definition at line 729 of file vtkKdTree.h.

◆ ProgressScale

double vtkKdTree::ProgressScale
protected

Definition at line 743 of file vtkKdTree.h.

◆ ProgressOffset

double vtkKdTree::ProgressOffset
protected

Definition at line 752 of file vtkKdTree.h.

◆ NumberOfRegionsOrLess

int vtkKdTree::NumberOfRegionsOrLess
protected

Definition at line 858 of file vtkKdTree.h.

◆ NumberOfRegionsOrMore

int vtkKdTree::NumberOfRegionsOrMore
protected

Definition at line 859 of file vtkKdTree.h.

◆ IncludeRegionBoundaryCells

vtkTypeBool vtkKdTree::IncludeRegionBoundaryCells
protected

Definition at line 861 of file vtkKdTree.h.

◆ CellBoundsCache

double vtkKdTree::CellBoundsCache[6]
protected

Definition at line 862 of file vtkKdTree.h.

◆ GenerateRepresentationUsingDataBounds

vtkTypeBool vtkKdTree::GenerateRepresentationUsingDataBounds
protected

Definition at line 864 of file vtkKdTree.h.

◆ CellList

struct _cellList vtkKdTree::CellList
protected

Definition at line 866 of file vtkKdTree.h.

◆ CellRegionList

int* vtkKdTree::CellRegionList
protected

Definition at line 871 of file vtkKdTree.h.

◆ MinCells

int vtkKdTree::MinCells
protected

Definition at line 873 of file vtkKdTree.h.

◆ NumberOfRegions

int vtkKdTree::NumberOfRegions
protected

Definition at line 874 of file vtkKdTree.h.

◆ Timing

vtkTypeBool vtkKdTree::Timing
protected

Definition at line 876 of file vtkKdTree.h.

◆ FudgeFactor

double vtkKdTree::FudgeFactor
protected

Definition at line 877 of file vtkKdTree.h.

◆ NumberOfLocatorPoints

int vtkKdTree::NumberOfLocatorPoints
protected

Definition at line 882 of file vtkKdTree.h.

◆ LocatorPoints

float* vtkKdTree::LocatorPoints
protected

Definition at line 883 of file vtkKdTree.h.

◆ LocatorIds

int* vtkKdTree::LocatorIds
protected

Definition at line 884 of file vtkKdTree.h.

◆ LocatorRegionLocation

int* vtkKdTree::LocatorRegionLocation
protected

Definition at line 885 of file vtkKdTree.h.

◆ MaxWidth

float vtkKdTree::MaxWidth
protected

Definition at line 887 of file vtkKdTree.h.

◆ LastNumDataSets

int vtkKdTree::LastNumDataSets
protected

Definition at line 892 of file vtkKdTree.h.

◆ LastDataCacheSize

int vtkKdTree::LastDataCacheSize
protected

Definition at line 893 of file vtkKdTree.h.

◆ LastInputDataSets

vtkDataSet** vtkKdTree::LastInputDataSets
protected

Definition at line 894 of file vtkKdTree.h.

◆ LastDataSetObserverTags

unsigned long* vtkKdTree::LastDataSetObserverTags
protected

Definition at line 895 of file vtkKdTree.h.

◆ LastDataSetType

int* vtkKdTree::LastDataSetType
protected

Definition at line 896 of file vtkKdTree.h.

◆ LastInputDataInfo

double* vtkKdTree::LastInputDataInfo
protected

Definition at line 897 of file vtkKdTree.h.

◆ LastBounds

double* vtkKdTree::LastBounds
protected

Definition at line 898 of file vtkKdTree.h.

◆ LastNumPoints

vtkIdType* vtkKdTree::LastNumPoints
protected

Definition at line 899 of file vtkKdTree.h.

◆ LastNumCells

vtkIdType* vtkKdTree::LastNumCells
protected

Definition at line 900 of file vtkKdTree.h.

◆ Cuts

vtkBSPCuts* vtkKdTree::Cuts
protected

Definition at line 902 of file vtkKdTree.h.

◆ Progress

double vtkKdTree::Progress
protected

Definition at line 903 of file vtkKdTree.h.


The documentation for this class was generated from the following file: