#include <vtkKdTree.h>
Inheritance diagram for vtkKdTree:
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.
Definition at line 71 of file vtkKdTree.h.
| virtual void | TimingOn () |
| virtual void | TimingOff () |
| virtual void | SetTiming (int) |
| virtual int | GetTiming () |
| static vtkKdTree * | New () |
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 int | GetNumberOfRegionsOrLess () |
| virtual void | SetNumberOfRegionsOrLess (int) |
| virtual int | GetNumberOfRegionsOrMore () |
| virtual void | SetNumberOfRegionsOrMore (int) |
| virtual double | GetFudgeFactor () |
| virtual void | SetFudgeFactor (double) |
| virtual vtkBSPCuts * | GetCuts () |
| void | SetCuts (vtkBSPCuts *cuts) |
| 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 () |
| vtkDataSet * | GetDataSet (int n) |
| vtkDataSet * | GetDataSet () |
| int | GetDataSet (vtkDataSet *set) |
| void | GetBounds (double *bounds) |
| void | GetRegionBounds (int regionID, double bounds[6]) |
| 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 | DeleteCellLists () |
| vtkIdList * | GetCellList (int regionID) |
| int * | AllGetRegionContainingCell () |
| int | GetRegionContainingPoint (double x, double y, double z) |
| void | BuildLocator () |
| int | MinimalNumberOfConvexSubRegions (vtkIntArray *regionIdList, double **convexRegionBounds) |
| int | DepthOrderAllRegions (double *dop, vtkIntArray *orderedList) |
| vtkIdTypeArray * | GetPointsInRegion (int regionId) |
| void | FreeSearchStructure () |
| void | GenerateRepresentation (int level, vtkPolyData *pd) |
| virtual void | PrintTiming (ostream &os, vtkIndent indent) |
| int | NewGeometry () |
| int | NewGeometry (vtkDataSet **sets, int numDataSets) |
| virtual void | SetMinCells (int) |
| virtual int | GetMinCells () |
| void | SetNewBounds (double *bounds) |
| virtual int | GetNumberOfRegions () |
| void | GetRegionDataBounds (int regionID, double bounds[6]) |
| void | PrintTree () |
| void | PrintVerboseTree () |
| void | CreateCellLists () |
| virtual void | SetIncludeRegionBoundaryCells (int) |
| virtual int | GetIncludeRegionBoundaryCells () |
| virtual void | IncludeRegionBoundaryCellsOn () |
| virtual void | IncludeRegionBoundaryCellsOff () |
| vtkIdList * | GetBoundaryCellList (int regionID) |
| 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 | DepthOrderRegions (vtkIntArray *regionIds, double *dop, vtkIntArray *orderedList) |
| void | BuildLocatorFromPoints (vtkPoints *ptArray) |
| void | BuildLocatorFromPoints (vtkPoints **ptArray, int numPtArrays) |
| vtkIdTypeArray * | BuildMapForDuplicatePoints (float tolerance) |
| vtkIdType | FindPoint (double *x) |
| vtkIdType | FindPoint (double x, double y, double z) |
| vtkIdType | FindClosestPoint (double *x, double &dist2) |
| vtkIdType | FindClosestPoint (double x, double y, double z, double &dist2) |
| vtkIdType | FindClosestPointInRegion (int regionId, double *x, double &dist2) |
| vtkIdType | FindClosestPointInRegion (int regionId, double x, double y, double z, double &dist2) |
| void | GenerateRepresentation (int *regionList, int len, vtkPolyData *pd) |
| virtual void | GenerateRepresentationUsingDataBoundsOn () |
| virtual void | GenerateRepresentationUsingDataBoundsOff () |
| virtual void | SetGenerateRepresentationUsingDataBounds (int) |
| virtual int | GetGenerateRepresentationUsingDataBounds () |
Static Public Member Functions | |
| static int | IsTypeOf (const char *type) |
| static vtkKdTree * | SafeDownCast (vtkObject *o) |
| static vtkKdNode * | CopyTree (vtkKdNode *kd) |
Protected Types | |
| enum | { XDIM = 0, YDIM = 1, ZDIM = 2 } |
Protected Member Functions | |
| vtkKdTree () | |
| ~vtkKdTree () | |
| void | SetCalculator (vtkKdNode *kd) |
| int | ProcessUserDefinedCuts (double *bounds) |
| void | SetCuts (vtkBSPCuts *cuts, int userDefined) |
| void | UpdateBuildTime () |
| int | DivideTest (int numberOfPoints, int level) |
| 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) |
| virtual void | ReportReferences (vtkGarbageCollector *) |
Static Protected Member Functions | |
| static void | DeleteAllDescendants (vtkKdNode *nd) |
| static void | GetLeafNodeIds (vtkKdNode *node, vtkIntArray *ids) |
Protected Attributes | |
| vtkBSPIntersections * | BSPCalculator |
| int | UserDefinedCuts |
| int | ValidDirections |
| vtkKdNode * | Top |
| vtkKdNode ** | RegionList |
| vtkTimerLog * | TimerLog |
|
|
Reimplemented from vtkLocator. Reimplemented in vtkPKdTree. Definition at line 74 of file vtkKdTree.h. |
|
|
Definition at line 442 of file vtkKdTree.h. |
|
|
|
|
|
|
|
|
Reimplemented from vtkLocator. Reimplemented in vtkPKdTree. |
|
|
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. |
|
|
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. |
|
|
Reimplemented from vtkLocator. Reimplemented in vtkPKdTree. |
|
||||||||||||
|
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. |
|
|
Turn on timing of the k-d tree build Reimplemented from vtkObject. Reimplemented in vtkPKdTree. |
|
|
Turn on timing of the k-d tree build |
|
|
Turn on timing of the k-d tree build |
|
|
Turn on timing of the k-d tree build |
|
|
Turn on timing of the k-d tree build |
|
|
Minimum number of cells per spatial region. Default is 100. |
|
|
Minimum number of cells per spatial region. Default is 100. |
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
Get a vtkBSPCuts object, a general object representing an axis- aligned spatial partitioning. Used by vtkBSPIntersections. |
|
|
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. |
|
|
Omit partitions along the X axis, yielding shafts in the X direction |
|
|
Omit partitions along the Y axis, yielding shafts in the Y direction |
|
|
Omit partitions along the Z axis, yielding shafts in the Z direction |
|
|
Omit partitions along the X and Y axes, yielding slabs along Z |
|
|
Omit partitions along the Y and Z axes, yielding slabs along X |
|
|
Omit partitions along the Z and X axes, yielding slabs along Y |
|
|
Partition along all three axes - this is the default |
|
|
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. |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Get the number of data sets included in spatial paritioning Definition at line 160 of file vtkKdTree.h. |
|
|
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.) |
|
|
Reimplemented from vtkLocator. Definition at line 167 of file vtkKdTree.h. References vtkLocator::GetDataSet(). |
|
|
Get handle for one of the data sets included in spatial paritioning. Handles can change after RemoveDataSet. |
|
|
Get the spatial bounds of the entire k-d tree space. Sets bounds array to xmin, xmax, ymin, ymax, zmin, zmax. |
|
|
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. |
|
|
The number of leaf nodes of the tree, the spatial regions |
|
||||||||||||
|
Get the spatial bounds of k-d tree region |
|
||||||||||||
|
Get the bounds of the data within the k-d tree region |
|
|
Print out nodes of kd tree |
|
|
Get the bounds of the data within the k-d tree region |
|
|
Print out leaf node data for given id |
|
||||||||||||||||
|
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. |
|
||||||||||||||||
|
|
|
||||||||||||
|
|
|
|
|
|
|
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. |
|
|
|
|
|
|
|
|
|
|
|
Free the memory used by the cell lists. |
|
|
Get the cell list for a region. This returns a pointer to vtkKdTree's memory, so don't free it. |
|
|
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. |
|
||||||||||||||||||||
|
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. |
|
||||||||||||||||||||
|
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. |
|
||||||||||||||||
|
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. |
|
||||||||||||
|
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. |
|
||||||||||||
|
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. |
|
|
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. |
|
|
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. |
|
||||||||||||||||
|
Get the id of the region containing the specified location. |
|
|
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. |
|
||||||||||||
|
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. |
|
||||||||||||
|
Given a direction of projection (typically obtained with vtkCamera::GetDirectionOfProjection()), this function creates a list of the k-d tree region IDs in order from front to back with respect to the that direction. 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.) |
|
||||||||||||||||
|
Given a direction of projection, 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. |
|
|
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. |
|
||||||||||||
|
Given a direction of projection, 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. |
|
|
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. |
|
|
Find the Id of the point that was previously supplied to BuildLocatorFromPoints(). Returns -1 if the point was not in the original array. |
|
||||||||||||||||
|
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. |
|
||||||||||||
|
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. |
|
||||||||||||||||||||
|
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. |
|
||||||||||||||||
|
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. |
|
||||||||||||||||||||||||
|
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. |
|
|
Get a list of the original IDs of all points in a region. You must have called BuildLocatorFromPoints before calling this. |
|
|
Delete the k-d tree data structure. Also delete any cell lists that were computed with CreateCellLists(). Implements vtkLocator. |
|
||||||||||||
|
Create a polydata representation of the boundaries of the k-d tree regions. If level equals GetLevel(), the leaf nodes are represented. Implements vtkLocator. |
|
||||||||||||||||
|
Generate a polygonal representation of a list of regions. Only leaf nodes have region IDs, so these will be leaf nodes. |
|
|
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. |
|
|
Generate a polygonal representation of a list of regions. Only leaf nodes have region IDs, so these will be leaf nodes. |
|
|
Generate a polygonal representation of a list of regions. Only leaf nodes have region IDs, so these will be leaf nodes. |
|
|
Generate a polygonal representation of a list of regions. Only leaf nodes have region IDs, so these will be leaf nodes. |
|
||||||||||||
|
Print timing of k-d tree build Reimplemented in vtkPKdTree. |
|
|
Return 1 if the geometry of the input data sets has changed since the last time the k-d tree was built. |
|
||||||||||||
|
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. |
|
|
Create a copy of the binary tree representation of the k-d tree spatial partitioning provided. |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
Save enough state so NewGeometry() can work, and update the BuildTime time stamp. |
|
||||||||||||
|
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. |
|
|
|
|
|
|
|
|
|
|
|
Definition at line 460 of file vtkKdTree.h. |
|
||||||||||||
|
Get back a list of the nodes at a specified level, nodes must be preallocated to hold 2^^(level) node structures. |
|
||||||||||||
|
Adds to the vtkIntArray the list of region IDs of all leaf nodes in the given node. |
|
|
Returns the total number of cells in all the data sets |
|
||||||||||||
|
Returns the total number of cells in data set 1 through data set 2. |
|
||||||||||||||||
|
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. |
|
||||||||||||||||
|
|
|
|
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. |
|
|
|
|
|
|
|
|
Reimplemented from vtkLocator. |
|
|
Definition at line 420 of file vtkKdTree.h. |
|
|
Definition at line 421 of file vtkKdTree.h. |
|
|
Definition at line 449 of file vtkKdTree.h. |
|
|
Definition at line 451 of file vtkKdTree.h. |
|
|
Definition at line 452 of file vtkKdTree.h. |
|
|
Definition at line 454 of file vtkKdTree.h. |
1.4.3-20050530