Main Page | Directories | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

vtkKdTree Class Reference

#include <vtkKdTree.h>

Inheritance diagram for vtkKdTree:

Inheritance graph
[legend]
Collaboration diagram for vtkKdTree:

Collaboration graph
[legend]
List of all members.

Detailed Description

a Kd-tree spatial decomposition of a data set

Creates a k-d tree decomposition of one data set or the combined result of multiple datasets. Decomposition is based off of the data set cell centers.

Responds to region intersection queries, indicating whether a k-d tree spatial region intersects:

an axis aligned box a sphere an arbitrary vtkCell a view frustrum defined by an axis-aligned rectangle in the view plane an arbitrary region expressed as vtkPlanes

Can depth sort all regions or any subset of regions with respect to a vtkCamera.

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.

If there is no specification of minimum number of cells per region or maximum number of levels in the tree, the tree is built to a maximum of 20 levels or until less than 100 cells would be in each 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. You can't create cell lists from this locator, but you perform all the other queries on the tree structure if you wish, and you can get a list of the points in any spatial region.

See also:
vtkLocator vtkCellLocator vtkPKdTree
Created by:
  • Law, Charles
CVS contributions (if > 5%):
  • Law, Charles (78%)
  • Fisk, Lee Ann (13%)
  • Malaterre, Mathieu (6%)
CVS logs (CVSweb):
  • .h (/Parallel/vtkKdTree.h)
  • .cxx (/Parallel/vtkKdTree.cxx)

Definition at line 96 of file vtkKdTree.h.

Public Types

typedef vtkLocator Superclass

Public Member Functions

virtual const char * GetClassName ()
virtual int IsA (const char *type)
void PrintSelf (ostream &os, vtkIndent indent)
virtual double GetFudgeFactor ()
virtual void SetFudgeFactor (double)
void OmitXPartitioning ()
void OmitYPartitioning ()
void OmitZPartitioning ()
void OmitXYPartitioning ()
void OmitYZPartitioning ()
void OmitZXPartitioning ()
void OmitNoPartitioning ()
void SetDataSet (vtkDataSet *set)
void SetNthDataSet (int index, vtkDataSet *set)
void RemoveDataSet (int index)
void RemoveDataSet (vtkDataSet *set)
void AddDataSet (vtkDataSet *set)
int GetNumberOfDataSets ()
vtkDataSetGetDataSet (int n)
vtkDataSetGetDataSet ()
int GetDataSet (vtkDataSet *set)
int GetNumberOfRegions ()
void PrintRegion (int id)
void CreateCellLists (int DataSet, int *regionReqList, int reqListSize)
void CreateCellLists (vtkDataSet *set, int *regionReqList, int reqListSize)
void CreateCellLists (int *regionReqList, int listSize)
void CreateCellLists ()
void DeleteCellLists ()
vtkIdListGetCellList (int regionID)
vtkIdListGetBoundaryCellList (int regionID)
int * AllGetRegionContainingCell ()
int DepthOrderAllRegions (vtkCamera *camera, vtkIntArray *orderedList)
void BuildLocator ()
vtkIdTypeArrayBuildMapForDuplicatePoints (float tolerance)
vtkIdTypeArrayGetPointsInRegion (int regionId)
void FreeSearchStructure ()
void GenerateRepresentation (int level, vtkPolyData *pd)
void GenerateRepresentation (int *regionList, int len, vtkPolyData *pd)
virtual void PrintTiming (ostream &os, vtkIndent indent)
int NewGeometry ()
int NewGeometry (vtkDataSet **sets, int numDataSets)
virtual void TimingOn ()
virtual void TimingOff ()
virtual void SetTiming (int)
virtual int GetTiming ()
virtual void SetMinCells (int)
virtual int GetMinCells ()
void GetBounds (float *bounds)
void GetBounds (double *bounds)
void GetRegionBounds (int regionID, float bounds[6])
void GetRegionBounds (int regionID, double bounds[6])
void GetRegionDataBounds (int regionID, float bounds[6])
void GetRegionDataBounds (int regionID, double bounds[6])
void PrintTree ()
void PrintVerboseTree ()
virtual void SetIncludeRegionBoundaryCells (int)
virtual int GetIncludeRegionBoundaryCells ()
virtual void IncludeRegionBoundaryCellsOn ()
virtual void IncludeRegionBoundaryCellsOff ()
vtkIdType GetCellLists (vtkIntArray *regions, int set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
vtkIdType GetCellLists (vtkIntArray *regions, vtkDataSet *set, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
vtkIdType GetCellLists (vtkIntArray *regions, vtkIdList *inRegionCells, vtkIdList *onBoundaryCells)
int GetRegionContainingCell (vtkDataSet *set, vtkIdType cellID)
int GetRegionContainingCell (int set, vtkIdType cellID)
int GetRegionContainingCell (vtkIdType cellID)
int GetRegionContainingPoint (float x, float y, float z)
int GetRegionContainingPoint (double x, double y, double z)
int DepthOrderRegions (vtkIntArray *regionIds, vtkCamera *camera, vtkIntArray *orderedList)
int IntersectsBox (int regionId, float *x)
int IntersectsBox (int regionId, double *x)
int IntersectsBox (int regionId, float xmin, float xmax, float ymin, float ymax, float zmin, float zmax)
int IntersectsBox (int regionId, double xmin, double xmax, double ymin, double ymax, double zmin, double zmax)
int IntersectsBox (int *ids, int len, float *x)
int IntersectsBox (int *ids, int len, double *x)
int IntersectsBox (int *ids, int len, float x0, float x1, float y0, float y1, float z0, float z1)
int IntersectsBox (int *ids, int len, double x0, double x1, double y0, double y1, double z0, double z1)
int IntersectsSphere2 (int regionId, float x, float y, float z, float rSquared)
int IntersectsSphere2 (int regionId, double x, double y, double z, double rSquared)
int IntersectsSphere2 (int *ids, int len, float x, float y, float z, float rSquared)
int IntersectsSphere2 (int *ids, int len, double x, double y, double z, double rSquared)
int IntersectsRegion (int regionId, vtkPlanes *planes)
int IntersectsRegion (int regionId, vtkPlanes *planes, int nvertices, float *vertices)
int IntersectsRegion (int regionId, vtkPlanes *planes, int nvertices, double *vertices)
int IntersectsRegion (int *ids, int len, vtkPlanes *planes)
int IntersectsRegion (int *ids, int len, vtkPlanes *planes, int nvertices, float *vertices)
int IntersectsRegion (int *ids, int len, vtkPlanes *planes, int nvertices, double *vertices)
int IntersectsCell (int regionId, vtkCell *cell, int cellRegion=-1)
int IntersectsCell (int regionId, int cellId, int cellRegion=-1)
int IntersectsCell (int regionId, vtkDataSet *Set, int cellId, int cellRegion=-1)
int IntersectsCell (int *ids, int len, vtkCell *cell, int cellRegion=-1)
int IntersectsCell (int *ids, int len, int cellId, int cellRegion=-1)
int IntersectsCell (int *ids, int len, vtkDataSet *set, int cellId, int cellRegion=-1)
int IntersectsFrustum (int regionId, vtkRenderer *ren, float x0, float x1, float y0, float y1)
int IntersectsFrustum (int regionId, vtkRenderer *ren, double x0, double x1, double y0, double y1)
int IntersectsFrustum (int *ids, int len, vtkRenderer *ren, float x0, float x1, float y0, float y1)
int IntersectsFrustum (int *ids, int len, vtkRenderer *ren, double x0, double x1, double y0, double y1)
int MinimalNumberOfConvexSubRegions (vtkIntArray *regionIdList, double **convexRegionBounds)
virtual void ComputeIntersectionsUsingDataBoundsOn ()
virtual void ComputeIntersectionsUsingDataBoundsOff ()
virtual void SetComputeIntersectionsUsingDataBounds (int)
virtual int GetComputeIntersectionsUsingDataBounds ()
void BuildLocatorFromPoints (vtkPoints *ptArray)
void BuildLocatorFromPoints (vtkPoints **ptArray, int numPtArrays)
vtkIdType FindPoint (float *x)
vtkIdType FindPoint (double *x)
vtkIdType FindPoint (float x, float y, float z)
vtkIdType FindPoint (double x, double y, double z)
vtkIdType FindClosestPoint (float *x, float &dist2)
vtkIdType FindClosestPoint (double *x, double &dist2)
vtkIdType FindClosestPoint (float x, float y, float z, float &dist2)
vtkIdType FindClosestPoint (double x, double y, double z, double &dist2)
vtkIdType FindClosestPointInRegion (int regionId, float *x, float &dist2)
vtkIdType FindClosestPointInRegion (int regionId, float x, float y, float z, float &dist2)
virtual void GenerateRepresentationUsingDataBoundsOn ()
virtual void GenerateRepresentationUsingDataBoundsOff ()
virtual void SetGenerateRepresentationUsingDataBounds (int)
virtual int GetGenerateRepresentationUsingDataBounds ()

Static Public Member Functions

int IsTypeOf (const char *type)
vtkKdTreeSafeDownCast (vtkObject *o)
vtkKdTreeNew ()
void SetCellBounds (vtkCell *cell, double *bounds)

Protected Types

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

Protected Member Functions

 vtkKdTree ()
 ~vtkKdTree ()
void UpdateBuildTime ()
void BuildRegionList ()
virtual int SelectCutDirection (vtkKdNode *kd)
void SetActualLevel ()
void GetRegionsAtLevel (int level, vtkKdNode **nodes)
int GetNumberOfCells ()
int GetDataSetsNumberOfCells (int set1, int set2)
void ComputeCellCenter (vtkDataSet *set, int cellId, float *center)
void ComputeCellCenter (vtkDataSet *set, int cellId, double *center)
float * ComputeCellCenters ()
float * ComputeCellCenters (int set)
float * ComputeCellCenters (vtkDataSet *set)

Static Protected Member Functions

void DeleteNodes (vtkKdNode *nd)
void GetLeafNodeIds (vtkKdNode *node, vtkIntArray *ids)

Protected Attributes

int ValidDirections
vtkKdNodeTop
vtkKdNode ** RegionList
vtkTimerLogTimerLog


Member Typedef Documentation

typedef vtkLocator vtkKdTree::Superclass
 

Reimplemented from vtkLocator.

Reimplemented in vtkPKdTree.

Definition at line 99 of file vtkKdTree.h.


Member Enumeration Documentation

anonymous enum [protected]
 

Enumeration values:
XDIM 
YDIM 
ZDIM 

Definition at line 558 of file vtkKdTree.h.


Constructor & Destructor Documentation

vtkKdTree::vtkKdTree  )  [protected]
 

vtkKdTree::~vtkKdTree  )  [protected]
 


Member Function Documentation

virtual const char* vtkKdTree::GetClassName  )  [virtual]
 

Reimplemented from vtkLocator.

Reimplemented in vtkPKdTree.

int vtkKdTree::IsTypeOf const char *  type  )  [static]
 

Return 1 if this class type is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeRevisionMacro found in vtkSetGet.h.

Reimplemented from vtkLocator.

Reimplemented in vtkPKdTree.

virtual int vtkKdTree::IsA const char *  type  )  [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 vtkTypeRevisionMacro found in vtkSetGet.h.

Reimplemented from vtkLocator.

Reimplemented in vtkPKdTree.

vtkKdTree* vtkKdTree::SafeDownCast vtkObject o  )  [static]
 

Reimplemented from vtkLocator.

Reimplemented in vtkPKdTree.

void vtkKdTree::PrintSelf ostream &  os,
vtkIndent  indent
[virtual]
 

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 vtkLocator.

Reimplemented in vtkPKdTree.

vtkKdTree* vtkKdTree::New  )  [static]
 

Create an object with Debug turned off, modified time initialized to zero, and reference counting on.

Reimplemented from vtkObject.

Reimplemented in vtkPKdTree.

virtual void vtkKdTree::TimingOn  )  [virtual]
 

Turn on timing of the k-d tree build

virtual void vtkKdTree::TimingOff  )  [virtual]
 

Turn on timing of the k-d tree build

virtual void vtkKdTree::SetTiming int   )  [virtual]
 

Turn on timing of the k-d tree build

virtual int vtkKdTree::GetTiming  )  [virtual]
 

Turn on timing of the k-d tree build

virtual void vtkKdTree::SetMinCells int   )  [virtual]
 

Minimum number of cells per spatial region

virtual int vtkKdTree::GetMinCells  )  [virtual]
 

Minimum number of cells per spatial region

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 multipled by 10e-6.

virtual void vtkKdTree::SetFudgeFactor double   )  [virtual]
 

void vtkKdTree::OmitXPartitioning  ) 
 

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

void vtkKdTree::OmitYPartitioning  ) 
 

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

void vtkKdTree::OmitZPartitioning  ) 
 

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

void vtkKdTree::OmitXYPartitioning  ) 
 

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

void vtkKdTree::OmitYZPartitioning  ) 
 

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

void vtkKdTree::OmitZXPartitioning  ) 
 

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

void vtkKdTree::OmitNoPartitioning  ) 
 

Partition along all three axes - this is the default

void vtkKdTree::SetDataSet vtkDataSet set  )  [virtual]
 

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.

Reimplemented from vtkLocator.

void vtkKdTree::SetNthDataSet int  index,
vtkDataSet set
 

void vtkKdTree::RemoveDataSet int  index  ) 
 

void vtkKdTree::RemoveDataSet vtkDataSet set  ) 
 

void vtkKdTree::AddDataSet vtkDataSet set  ) 
 

int vtkKdTree::GetNumberOfDataSets  )  [inline]
 

Get the number of data sets included in spatial paritioning

Definition at line 160 of file vtkKdTree.h.

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.)

vtkDataSet* vtkKdTree::GetDataSet  )  [inline, virtual]
 

Build the locator from the points/cells defining this dataset.

Reimplemented from vtkLocator.

Definition at line 167 of file vtkKdTree.h.

References vtkLocator::GetDataSet().

int vtkKdTree::GetDataSet vtkDataSet set  ) 
 

Get handle for one of the data sets included in spatial paritioning. Handles can change after RemoveDataSet.

void vtkKdTree::GetBounds float *  bounds  ) 
 

Get the spatial bounds of the entire k-d tree space. Sets bounds array to xmin, xmax, ymin, ymax, zmin, zmax.

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.

int vtkKdTree::GetNumberOfRegions  )  [inline]
 

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

Definition at line 181 of file vtkKdTree.h.

void vtkKdTree::GetRegionBounds int  regionID,
float  bounds[6]
 

Get the spatial bounds of k-d tree region

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

Get the spatial bounds of k-d tree region

void vtkKdTree::GetRegionDataBounds int  regionID,
float  bounds[6]
 

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

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

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

void vtkKdTree::PrintTree  ) 
 

Print out nodes of kd tree

void vtkKdTree::PrintVerboseTree  ) 
 

Print out nodes of kd tree

void vtkKdTree::PrintRegion int  id  ) 
 

Print out leaf node data for given id

void vtkKdTree::CreateCellLists int  DataSet,
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.

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

void vtkKdTree::CreateCellLists int *  regionReqList,
int  listSize
 

void vtkKdTree::CreateCellLists  ) 
 

virtual void vtkKdTree::SetIncludeRegionBoundaryCells int   )  [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.

virtual int vtkKdTree::GetIncludeRegionBoundaryCells  )  [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.

virtual void vtkKdTree::IncludeRegionBoundaryCellsOn  )  [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.

virtual void vtkKdTree::IncludeRegionBoundaryCellsOff  )  [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.

void vtkKdTree::DeleteCellLists  ) 
 

Free the memory used by the cell lists.

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.

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.

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 NULL, 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.

vtkIdType vtkKdTree::GetCellLists vtkIntArray regions,
vtkDataSet 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 NULL, 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.

vtkIdType vtkKdTree::GetCellLists vtkIntArray regions,
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 NULL, 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.

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.

int vtkKdTree::GetRegionContainingCell int  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.

int vtkKdTree::GetRegionContainingCell 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.

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.

int vtkKdTree::GetRegionContainingPoint float  x,
float  y,
float  z
 

Get the id of the region containing the specified location.

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

Get the id of the region containing the specified location.

int vtkKdTree::DepthOrderAllRegions vtkCamera camera,
vtkIntArray orderedList
 

Given a vtkCamera, this function creates a list of the k-d tree region IDs in order from front to back with respect to the camera's direction of projection. The number of regions in the ordered list is returned. (This is not actually sorting the regions on their distance from the view plane, but there is no region on the list which blocks a region that appears earlier on the list.)

int vtkKdTree::DepthOrderRegions vtkIntArray regionIds,
vtkCamera camera,
vtkIntArray orderedList
 

Given a vtkCamera, and a list of k-d tree region IDs, this function creates an ordered list of those IDs in front to back order with respect to the camera's direction of projection. The number of regions in the ordered list is returned.

int vtkKdTree::IntersectsBox int  regionId,
float *  x
 

Determine whether a region of the spatial decomposition intersects an axis aligned box.

int vtkKdTree::IntersectsBox int  regionId,
double *  x
 

Determine whether a region of the spatial decomposition intersects an axis aligned box.

int vtkKdTree::IntersectsBox int  regionId,
float  xmin,
float  xmax,
float  ymin,
float  ymax,
float  zmin,
float  zmax
 

Determine whether a region of the spatial decomposition intersects an axis aligned box.

int vtkKdTree::IntersectsBox int  regionId,
double  xmin,
double  xmax,
double  ymin,
double  ymax,
double  zmin,
double  zmax
 

Determine whether a region of the spatial decomposition intersects an axis aligned box.

int vtkKdTree::IntersectsBox int *  ids,
int  len,
float *  x
 

Compute a list of the Ids of all regions that intersect the specified axis aligned box. Returns: the number of ids in the list.

int vtkKdTree::IntersectsBox int *  ids,
int  len,
double *  x
 

Compute a list of the Ids of all regions that intersect the specified axis aligned box. Returns: the number of ids in the list.

int vtkKdTree::IntersectsBox int *  ids,
int  len,
float  x0,
float  x1,
float  y0,
float  y1,
float  z0,
float  z1
 

Compute a list of the Ids of all regions that intersect the specified axis aligned box. Returns: the number of ids in the list.

int vtkKdTree::IntersectsBox int *  ids,
int  len,
double  x0,
double  x1,
double  y0,
double  y1,
double  z0,
double  z1
 

Compute a list of the Ids of all regions that intersect the specified axis aligned box. Returns: the number of ids in the list.

int vtkKdTree::IntersectsSphere2 int  regionId,
float  x,
float  y,
float  z,
float  rSquared
 

Determine whether a region of the spatial decomposition intersects a sphere, given the center of the sphere and the square of it's radius.

int vtkKdTree::IntersectsSphere2 int  regionId,
double  x,
double  y,
double  z,
double  rSquared
 

Determine whether a region of the spatial decomposition intersects a sphere, given the center of the sphere and the square of it's radius.

int vtkKdTree::IntersectsSphere2 int *  ids,
int  len,
float  x,
float  y,
float  z,
float  rSquared
 

Compute a list of the Ids of all regions that intersect the specified sphere. The sphere is given by it's center and the square of it's radius. Returns: the number of ids in the list.

int vtkKdTree::IntersectsSphere2 int *  ids,
int  len,
double  x,
double  y,
double  z,
double  rSquared
 

Compute a list of the Ids of all regions that intersect the specified sphere. The sphere is given by it's center and the square of it's radius. Returns: the number of ids in the list.

int vtkKdTree::IntersectsRegion int  regionId,
vtkPlanes planes
 

Determine whether a region of the spatial decomposition intersects the convex region "inside" a set of planes. Planes must be defined as vtkPlanes (i.e. outward pointing normals). If you can provide the vertices of the convex region (as 3-tuples) it will save an expensive calculation.

int vtkKdTree::IntersectsRegion int  regionId,
vtkPlanes planes,
int  nvertices,
float *  vertices
 

Determine whether a region of the spatial decomposition intersects the convex region "inside" a set of planes. Planes must be defined as vtkPlanes (i.e. outward pointing normals). If you can provide the vertices of the convex region (as 3-tuples) it will save an expensive calculation.

int vtkKdTree::IntersectsRegion int  regionId,
vtkPlanes planes,
int  nvertices,
double *  vertices
 

Determine whether a region of the spatial decomposition intersects the convex region "inside" a set of planes. Planes must be defined as vtkPlanes (i.e. outward pointing normals). If you can provide the vertices of the convex region (as 3-tuples) it will save an expensive calculation.

int vtkKdTree::IntersectsRegion int *  ids,
int  len,
vtkPlanes planes
 

Compute a list of the Ids of all regions that intersect the convex region "inside" a set of planes. Planes must be defined as vtkPlanes (i.e. outward pointing normals). If you can provide the vertices of the convex region (as 3-tuples) it will save an expensive calculation. Returns: the number of ids in the list.

int vtkKdTree::IntersectsRegion int *  ids,
int  len,
vtkPlanes planes,
int  nvertices,
float *  vertices
 

Compute a list of the Ids of all regions that intersect the convex region "inside" a set of planes. Planes must be defined as vtkPlanes (i.e. outward pointing normals). If you can provide the vertices of the convex region (as 3-tuples) it will save an expensive calculation. Returns: the number of ids in the list.

int vtkKdTree::IntersectsRegion int *  ids,
int  len,
vtkPlanes planes,
int  nvertices,
double *  vertices
 

Compute a list of the Ids of all regions that intersect the convex region "inside" a set of planes. Planes must be defined as vtkPlanes (i.e. outward pointing normals). If you can provide the vertices of the convex region (as 3-tuples) it will save an expensive calculation. Returns: the number of ids in the list.

int vtkKdTree::IntersectsCell int  regionId,
vtkCell cell,
int  cellRegion = -1
 

Determine whether a region of the spatial decomposition intersects the given cell. If a cell Id is given, and no data set is specified, data set 0 is assumed. If you already know the region that the cell centroid lies in, (perhaps from a previous call to AllGetRegionContainingCell), provide that as the last argument to make the computation quicker.

int vtkKdTree::IntersectsCell int  regionId,
int  cellId,
int  cellRegion = -1
 

Determine whether a region of the spatial decomposition intersects the given cell. If a cell Id is given, and no data set is specified, data set 0 is assumed. If you already know the region that the cell centroid lies in, (perhaps from a previous call to AllGetRegionContainingCell), provide that as the last argument to make the computation quicker.

int vtkKdTree::IntersectsCell int  regionId,
vtkDataSet Set,
int  cellId,
int  cellRegion = -1
 

Determine whether a region of the spatial decomposition intersects the given cell. If a cell Id is given, and no data set is specified, data set 0 is assumed. If you already know the region that the cell centroid lies in, (perhaps from a previous call to AllGetRegionContainingCell), provide that as the last argument to make the computation quicker.

int vtkKdTree::IntersectsCell int *  ids,
int  len,
vtkCell cell,
int  cellRegion = -1
 

Compute a list of the Ids of all regions that intersect the given cell. If a cell Id is given, and no data set is specified, data set 0 is assumed. If you already know the region that the cell centroid lies in, provide that as the last argument to make the computation quicker. Returns the number of regions the cell intersects.

int vtkKdTree::IntersectsCell int *  ids,
int  len,
int  cellId,
int  cellRegion = -1
 

Compute a list of the Ids of all regions that intersect the given cell. If a cell Id is given, and no data set is specified, data set 0 is assumed. If you already know the region that the cell centroid lies in, provide that as the last argument to make the computation quicker. Returns the number of regions the cell intersects.

int vtkKdTree::IntersectsCell int *  ids,
int  len,
vtkDataSet set,
int  cellId,
int  cellRegion = -1
 

Compute a list of the Ids of all regions that intersect the given cell. If a cell Id is given, and no data set is specified, data set 0 is assumed. If you already know the region that the cell centroid lies in, provide that as the last argument to make the computation quicker. Returns the number of regions the cell intersects.

int vtkKdTree::IntersectsFrustum int  regionId,
vtkRenderer ren,
float  x0,
float  x1,
float  y0,
float  y1
 

Determine whether a region of the spatial decomposition intersects a region which is the view frustum obtained from an axis aligned rectangular viewport. Viewport coordinates range from -1 to +1 in x and y directions.

int vtkKdTree::IntersectsFrustum int  regionId,
vtkRenderer ren,
double  x0,
double  x1,
double  y0,
double  y1
 

Determine whether a region of the spatial decomposition intersects a region which is the view frustum obtained from an axis aligned rectangular viewport. Viewport coordinates range from -1 to +1 in x and y directions.

int vtkKdTree::IntersectsFrustum int *  ids,
int  len,
vtkRenderer ren,
float  x0,
float  x1,
float  y0,
float  y1
 

Compute a list of the Ids of all regions that intersect a region specified by the view frustum obtained from an axis aligned rectangular viewport. Returns: the number of ids in the list.

int vtkKdTree::IntersectsFrustum int *  ids,
int  len,
vtkRenderer ren,
double  x0,
double  x1,
double  y0,
double  y1
 

Compute a list of the Ids of all regions that intersect a region specified by the view frustum obtained from an axis aligned rectangular viewport. Returns: the number of ids in the list.

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.

virtual void vtkKdTree::ComputeIntersectionsUsingDataBoundsOn  )  [virtual]
 

When computing the intersection of k-d tree regions with other objects, we use the spatial bounds of the region. To use the tighter bound of the bounding box of the data within the region, set this variable ON.

virtual void vtkKdTree::ComputeIntersectionsUsingDataBoundsOff  )  [virtual]
 

When computing the intersection of k-d tree regions with other objects, we use the spatial bounds of the region. To use the tighter bound of the bounding box of the data within the region, set this variable ON.

virtual void vtkKdTree::SetComputeIntersectionsUsingDataBounds int   )  [virtual]
 

When computing the intersection of k-d tree regions with other objects, we use the spatial bounds of the region. To use the tighter bound of the bounding box of the data within the region, set this variable ON.

virtual int vtkKdTree::GetComputeIntersectionsUsingDataBounds  )  [virtual]
 

When computing the intersection of k-d tree regions with other objects, we use the spatial bounds of the region. To use the tighter bound of the bounding box of the data within the region, set this variable ON.

void vtkKdTree::BuildLocator  )  [virtual]
 

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.

void vtkKdTree::BuildLocatorFromPoints vtkPoints ptArray  ) 
 

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.

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

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.

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.

vtkIdType vtkKdTree::FindPoint float *  x  ) 
 

Find the Id of the point that was previously supplied to BuildLocatorFromPoints(). Returns -1 if the point was not in the original array.

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.

vtkIdType vtkKdTree::FindPoint float  x,
float  y,
float  z
 

Find the Id of the point that was previously supplied to BuildLocatorFromPoints(). Returns -1 if the point was not in the original array.

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

Find the Id of the point that was previously supplied to BuildLocatorFromPoints(). Returns -1 if the point was not in the original array.

vtkIdType vtkKdTree::FindClosestPoint float *  x,
float &  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.

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.

vtkIdType vtkKdTree::FindClosestPoint float  x,
float  y,
float  z,
float &  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.

vtkIdType vtkKdTree::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 the given point. Set the square of the distance between the two points.

vtkIdType vtkKdTree::FindClosestPointInRegion int  regionId,
float *  x,
float &  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.

vtkIdType vtkKdTree::FindClosestPointInRegion int  regionId,
float  x,
float  y,
float  z,
float &  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.

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.

void vtkKdTree::FreeSearchStructure  )  [virtual]
 

Delete the k-d tree data structure. Also delete any cell lists that were computed with CreateCellLists().

Implements vtkLocator.

void vtkKdTree::GenerateRepresentation int  level,
vtkPolyData pd
[virtual]
 

Create a polydata representation of the boundaries of the k-d tree regions. If level equals GetLevel(), the leaf nodes are represented.

Implements vtkLocator.

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.

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.

virtual void vtkKdTree::GenerateRepresentationUsingDataBoundsOff  )  [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.

virtual void vtkKdTree::SetGenerateRepresentationUsingDataBounds int   )  [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.

virtual int vtkKdTree::GetGenerateRepresentationUsingDataBounds  )  [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.

virtual void vtkKdTree::PrintTiming ostream &  os,
vtkIndent  indent
[virtual]
 

Print timing of k-d tree build

Reimplemented in vtkPKdTree.

int vtkKdTree::NewGeometry  ) 
 

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

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

void vtkKdTree::SetCellBounds vtkCell cell,
double *  bounds
[inline, static]
 

Write six floats to the bounds array giving the bounds of the specified cell.

void vtkKdTree::UpdateBuildTime  )  [protected]
 

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

void vtkKdTree::DeleteNodes vtkKdNode nd  )  [static, protected]
 

void vtkKdTree::BuildRegionList  )  [protected]
 

virtual int vtkKdTree::SelectCutDirection vtkKdNode kd  )  [protected, virtual]
 

void vtkKdTree::SetActualLevel  )  [inline, protected]
 

Definition at line 578 of file vtkKdTree.h.

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.

void vtkKdTree::GetLeafNodeIds vtkKdNode node,
vtkIntArray ids
[static, protected]
 

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

int vtkKdTree::GetNumberOfCells  )  [protected]
 

Returns the total number of cells in all the data sets

int vtkKdTree::GetDataSetsNumberOfCells int  set1,
int  set2
[protected]
 

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

void vtkKdTree::ComputeCellCenter vtkDataSet set,
int  cellId,
float *  center
[protected]
 

Get or compute the center of one cell. If the DataSet is NULL, the first DataSet is used. This is the point used in determining to which spatial region the cell is assigned.

void vtkKdTree::ComputeCellCenter vtkDataSet set,
int  cellId,
double *  center
[protected]
 

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.

float* vtkKdTree::ComputeCellCenters int  set  )  [protected]
 

float* vtkKdTree::ComputeCellCenters vtkDataSet set  )  [protected]
 


Member Data Documentation

int vtkKdTree::ValidDirections [protected]
 

Definition at line 565 of file vtkKdTree.h.

vtkKdNode* vtkKdTree::Top [protected]
 

Definition at line 568 of file vtkKdTree.h.

vtkKdNode** vtkKdTree::RegionList [protected]
 

Definition at line 569 of file vtkKdTree.h.

vtkTimerLog* vtkKdTree::TimerLog [protected]
 

Definition at line 572 of file vtkKdTree.h.


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