 |
ROOT 6.10/09 Reference Guide |
| |
ROOT 6.10/09 Reference Guide |
Class implementing a kd-tree.
Contents:
In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbour searches). kd-trees are a special case of BSP trees.
A kd-tree uses only splitting planes that are perpendicular to one of the coordinate system axes. This differs from BSP trees, in which arbitrary splitting planes can be used. In addition, in the typical definition every node of a kd-tree, from the root to the leaves, stores a point. This differs from BSP trees, in which leaves are typically the only nodes that contain points (or other geometric primitives). As a consequence, each splitting plane must go through one of the points in the kd-tree. kd-trees are a variant that store data only in leaf nodes.
Since there are many possible ways to choose axis-aligned splitting planes, there are many different ways to construct kd-trees. The canonical method of kd-tree construction has the following constraints:
As one moves down the tree, one cycles through the axes used to select the splitting planes. (For example, the root would have an x-aligned plane, the root's children would both have y-aligned planes, the root's grandchildren would all have z-aligned planes, and so on.) At each step, the point selected to create the splitting plane is the median of the points being put into the kd-tree, with respect to their coordinates in the axis being used. (Note the assumption that we feed the entire set of points into the algorithm up-front.)
This method leads to a balanced kd-tree, in which each leaf node is about the same distance from the root. However, balanced trees are not necessarily optimal for all applications. The following pseudo-code illustrates this canonical construction procedure (NOTE, that the procedure used by the TKDTree class is a bit different, the following pseudo-code is given as a simple illustration of the concept):
Our construction method is optimized to save memory, and differs a bit from the constraints above. In particular, the division axis is chosen as the one with the biggest spread, and the point to create the splitting plane is chosen so, that one of the two subtrees contains exactly 2^k terminal nodes and is a perfectly balanced binary tree, and, while at the same time, trying to keep the number of terminal nodes in the 2 subtrees as close as possible. The following section gives more details about our implementation.
The interface of the TKDTree, that allows to set input data, has been developped to simplify using it together with TTree::Draw() functions. That's why the data has to be provided column-wise. For example:
By default, the kd-tree doesn't own the data and doesn't delete it with itself. If you want the data to be deleted together with the kd-tree, call TKDTree::SetOwner(kTRUE). Most functions of the kd-tree don't require the original data to be present after the tree has been built. Check the functions documentation for more details.
Nodes of the tree are indexed top to bottom, left to right. The root node has index 0. Functions TKDTree::GetLeft(Index inode), TKDTree::GetRight(Index inode) and TKDTree::GetParent(Index inode) allow to find the children and the parent of a given node. For a given node, one can find the indexes of the original points, contained in this node, by calling the GetNodePointsIndexes(Index inode) function. Additionally, for terminal nodes, there is a function GetPointsIndexes(Index inode) that returns a pointer to the relevant part of the index array. To find the number of point in the node (not only terminal), call TKDTree::GetNpointsNode(Index inode).
TKDtree is optimized to minimize memory consumption. Nodes of the TKDTree do not store pointers to the left and right children or to the parent node, but instead there are several 1-d arrays of size fNNodes with information about the nodes. The order of the nodes information in the arrays is described below. It's important to understand it, if one's class needs to store some kind of additional information on the per node basis, for example, the fit function parameters.
As noted above, the construction of the kd-tree involves choosing the axis and the point on that axis to divide the remaining points approximately in half. The exact algorithm for choosing the division point is described in the next section. The sequence of divisions is recorded in the following arrays:
Given the index of a node in those arrays, it's easy to find the indices, corresponding to children nodes or the parent node: Suppose, the parent node is stored under the index inode. Then:
index = inode*2+1index = (inode+1)*2Suppose, that the child node is stored under the index inode. Then:
index = inode/2Number of division nodes and number of terminals : fNNodes = (fNPoints/fBucketSize)
The nodes are filled always from left side to the right side: Let inode be the index of a node, and irow - the index of a row The TKDTree looks the following way: Ideal case:
Non ideal case:
As described above, the kd-tree is built by repeatingly dividing the given set of points into 2 smaller sets. The cut is made on the axis with the biggest spread, and the value on the axis, on which the cut is performed, is chosen based on the following formula: Suppose, we want to divide n nodes into 2 groups, left and right. Then the left and right will have the following number of nodes:
For example, let n_nodes=67. Then, the closest 2^k=64, 2^k-1=32, 2^k-2=16. Left node gets 32+3=35 sub-nodes, and the right node gets 32 sub-nodes
The division process continues until all the nodes contain not more than a predefined number of points.
Some kd-tree based algorithms need to know the boundaries of each node. This information can be computed by calling the TKDTree::MakeBoundaries() function. It fills the following arrays:
fRange : array containing the boundaries of the domain: | 1st dimension (min + max) | 2nd dimension (min + max) | ... fBoundaries : nodes boundaries | 1st node {1st dim * 2 elements | 2nd dim * 2 elements | ...} | 2nd node {...} | ...The nodes are arranged in the order described in section 3a.
Public Member Functions | |
| TKDTree () | |
| Default constructor. Nothing is built. More... | |
| TKDTree (Index npoints, Index ndim, UInt_t bsize) | |
| TKDTree (Index npoints, Index ndim, UInt_t bsize, Value **data) | |
| Create a kd-tree from the provided data array. More... | |
| ~TKDTree () | |
| Destructor By default, the original data is not owned by kd-tree and is not deleted with it. More... | |
| void | Build () |
| Build the kd-tree. More... | |
| Double_t | Distance (const Value *point, Index ind, Int_t type=2) const |
| Find the distance between point of the first argument and the point at index value ind Type argument specifies the metric: type=2 - L2 metric, type=1 - L1 metric. More... | |
| void | DistanceToNode (const Value *point, Index inode, Value &min, Value &max, Int_t type=2) |
| Find the minimal and maximal distance from a given point to a given node. More... | |
| void | FindBNodeA (Value *point, Value *delta, Int_t &inode) |
| find the smallest node covering the full range - start More... | |
| void | FindInRange (Value *point, Value range, std::vector< Index > &res) |
| Find all points in the sphere of a given radius "range" around the given point 1st argument - the point 2nd argument - radius of the shere 3rd argument - a vector, in which the results will be returned. More... | |
| void | FindNearestNeighbors (const Value *point, Int_t k, Index *ind, Value *dist) |
| Find kNN nearest neighbors to the point in the first argument Returns 1 on success, 0 on failure Arrays ind and dist are provided by the user and are assumed to be at least kNN elements long. More... | |
| Index | FindNode (const Value *point) const |
| returns the index of the terminal node to which point belongs (index in the fAxis, fValue, etc arrays) returns -1 in case of failure More... | |
| void | FindPoint (Value *point, Index &index, Int_t &iter) |
| find the index of point works only if we keep fData pointers More... | |
| Value * | GetBoundaries () |
| Get the boundaries. More... | |
| Value * | GetBoundariesExact () |
| Get the boundaries. More... | |
| Value * | GetBoundary (const Int_t node) |
| Get a boundary. More... | |
| Value * | GetBoundaryExact (const Int_t node) |
| Get a boundary. More... | |
| Index | GetBucketSize () |
| Int_t | GetCrossNode () |
| smallest terminal row More... | |
| Index * | GetIndPoints () |
| offset in fIndPoints More... | |
| Int_t | GetLeft (Int_t inode) const |
| Index | GetNDim () |
| Int_t | GetNNodes () const |
| UChar_t | GetNodeAxis (Int_t id) const |
| void | GetNodePointsIndexes (Int_t node, Int_t &first1, Int_t &last1, Int_t &first2, Int_t &last2) const |
| Return the indices of points in that node Indices are returned as the first and last value of the part of indices array, that belong to this node Sometimes points are in 2 intervals, then the first and last value for the second one are returned in third and fourth parameter, otherwise first2 is set to 0 and last2 is set to -1 To iterate over all the points of the node #inode, one can do, for example: Index *indices = kdtree->GetPointsIndexes(); Int_t first1, last1, first2, last2; kdtree->GetPointsIndexes(inode, first1, last1, first2, last2); for (Int_t ipoint=first1; ipoint<=last1; ipoint++){ point = indices[ipoint]; //do something with point; } for (Int_t ipoint=first2; ipoint<=last2; ipoint++){ point = indices[ipoint]; //do something with point; }. More... | |
| Value | GetNodeValue (Int_t id) const |
| Index | GetNPoints () |
| Index | GetNPointsNode (Int_t node) const |
| Get number of points in this node for all the terminal nodes except last, the size is fBucketSize for the last node it's fOffsetfBucketSize, or if fOffsetfBucketSize==0, it's also fBucketSize. More... | |
| Int_t | GetOffset () |
| cross node More... | |
| Int_t | GetParent (Int_t inode) const |
| Index * | GetPointsIndexes (Int_t node) const |
| return the indices of the points in that terminal node for all the nodes except last, the size is fBucketSize for the last node it's fOffsetfBucketSize More... | |
| Int_t | GetRight (Int_t inode) const |
| Int_t | GetRowT0 () |
| Int_t | GetTotalNodes () const |
| Int_t | IsOwner () |
| Bool_t | IsTerminal (Index inode) const |
| Value | KOrdStat (Index ntotal, Value *a, Index k, Index *index) const |
| copy of the TMath::KOrdStat because I need an Index work array More... | |
| void | MakeBoundaries (Value *range=0x0) |
| Build boundaries for each node. More... | |
| void | MakeBoundariesExact () |
| Build boundaries for each node. More... | |
| void | SetData (Index npoints, Index ndim, UInt_t bsize, Value **data) |
| Set the data array. See the constructor function comments for details. More... | |
| Int_t | SetData (Index idim, Value *data) |
| Set the coordinate #ndim of all points (the column #ndim of the data matrix) After setting all the data columns, proceed by calling Build() function Note, that calling this function after Build() is not possible Note also, that no checks on the array sizes is performed anywhere. More... | |
| void | SetOwner (Int_t owner) |
| void | Spread (Index ntotal, Value *a, Index *index, Value &min, Value &max) const |
| Calculate spread of the array a. More... | |
 Public Member Functions inherited from TObject | |
| TObject () | |
| TObject constructor. More... | |
| TObject (const TObject &object) | |
| TObject copy ctor. More... | |
| virtual | ~TObject () |
| TObject destructor. More... | |
| void | AbstractMethod (const char *method) const |
| Use this method to implement an "abstract" method that you don't want to leave purely abstract. More... | |
| virtual void | AppendPad (Option_t *option="") |
| Append graphics object to current pad. More... | |
| virtual void | Browse (TBrowser *b) |
| Browse object. May be overridden for another default action. More... | |
| virtual const char * | ClassName () const |
| Returns name of class to which the object belongs. More... | |
| virtual void | Clear (Option_t *="") |
| virtual TObject * | Clone (const char *newname="") const |
| Make a clone of an object using the Streamer facility. More... | |
| virtual Int_t | Compare (const TObject *obj) const |
| Compare abstract method. More... | |
| virtual void | Copy (TObject &object) const |
| Copy this to obj. More... | |
| virtual void | Delete (Option_t *option="") |
| Delete this object. More... | |
| virtual Int_t | DistancetoPrimitive (Int_t px, Int_t py) |
| Computes distance from point (px,py) to the object. More... | |
| virtual void | Draw (Option_t *option="") |
| Default Draw method for all objects. More... | |
| virtual void | DrawClass () const |
| Draw class inheritance tree of the class to which this object belongs. More... | |
| virtual TObject * | DrawClone (Option_t *option="") const |
Draw a clone of this object in the current selected pad for instance with: gROOT->SetSelectedPad(gPad). More... | |
| virtual void | Dump () const |
| Dump contents of object on stdout. More... | |
| virtual void | Error (const char *method, const char *msgfmt,...) const |
| Issue error message. More... | |
| virtual void | Execute (const char *method, const char *params, Int_t *error=0) |
| Execute method on this object with the given parameter string, e.g. More... | |
| virtual void | Execute (TMethod *method, TObjArray *params, Int_t *error=0) |
| Execute method on this object with parameters stored in the TObjArray. More... | |
| virtual void | ExecuteEvent (Int_t event, Int_t px, Int_t py) |
| Execute action corresponding to an event at (px,py). More... | |
| virtual void | Fatal (const char *method, const char *msgfmt,...) const |
| Issue fatal error message. More... | |
| virtual TObject * | FindObject (const char *name) const |
| Must be redefined in derived classes. More... | |
| virtual TObject * | FindObject (const TObject *obj) const |
| Must be redefined in derived classes. More... | |
| virtual Option_t * | GetDrawOption () const |
| Get option used by the graphics system to draw this object. More... | |
| virtual const char * | GetIconName () const |
| Returns mime type name of object. More... | |
| virtual const char * | GetName () const |
| Returns name of object. More... | |
| virtual char * | GetObjectInfo (Int_t px, Int_t py) const |
| Returns string containing info about the object at position (px,py). More... | |
| virtual Option_t * | GetOption () const |
| virtual const char * | GetTitle () const |
| Returns title of object. More... | |
| virtual UInt_t | GetUniqueID () const |
| Return the unique object id. More... | |
| virtual Bool_t | HandleTimer (TTimer *timer) |
| Execute action in response of a timer timing out. More... | |
| virtual ULong_t | Hash () const |
| Return hash value for this object. More... | |
| virtual void | Info (const char *method, const char *msgfmt,...) const |
| Issue info message. More... | |
| virtual Bool_t | InheritsFrom (const char *classname) const |
| Returns kTRUE if object inherits from class "classname". More... | |
| virtual Bool_t | InheritsFrom (const TClass *cl) const |
| Returns kTRUE if object inherits from TClass cl. More... | |
| virtual void | Inspect () const |
| Dump contents of this object in a graphics canvas. More... | |
| void | InvertBit (UInt_t f) |
| virtual Bool_t | IsEqual (const TObject *obj) const |
| Default equal comparison (objects are equal if they have the same address in memory). More... | |
| virtual Bool_t | IsFolder () const |
| Returns kTRUE in case object contains browsable objects (like containers or lists of other objects). More... | |
| Bool_t | IsOnHeap () const |
| virtual Bool_t | IsSortable () const |
| Bool_t | IsZombie () const |
| virtual void | ls (Option_t *option="") const |
| The ls function lists the contents of a class on stdout. More... | |
| void | MayNotUse (const char *method) const |
| Use this method to signal that a method (defined in a base class) may not be called in a derived class (in principle against good design since a child class should not provide less functionality than its parent, however, sometimes it is necessary). More... | |
| virtual Bool_t | Notify () |
| This method must be overridden to handle object notification. More... | |
| void | Obsolete (const char *method, const char *asOfVers, const char *removedFromVers) const |
| Use this method to declare a method obsolete. More... | |
| void | operator delete (void *ptr) |
| Operator delete. More... | |
| void | operator delete[] (void *ptr) |
| Operator delete []. More... | |
| void * | operator new (size_t sz) |
| void * | operator new (size_t sz, void *vp) |
| void * | operator new[] (size_t sz) |
| void * | operator new[] (size_t sz, void *vp) |
| TObject & | operator= (const TObject &rhs) |
| TObject assignment operator. More... | |
| virtual void | Paint (Option_t *option="") |
| This method must be overridden if a class wants to paint itself. More... | |
| virtual void | Pop () |
| Pop on object drawn in a pad to the top of the display list. More... | |
| virtual void | Print (Option_t *option="") const |
| This method must be overridden when a class wants to print itself. More... | |
| virtual Int_t | Read (const char *name) |
| Read contents of object with specified name from the current directory. More... | |
| virtual void | RecursiveRemove (TObject *obj) |
| Recursively remove this object from a list. More... | |
| void | ResetBit (UInt_t f) |
| virtual void | SaveAs (const char *filename="", Option_t *option="") const |
| Save this object in the file specified by filename. More... | |
| virtual void | SavePrimitive (std::ostream &out, Option_t *option="") |
| Save a primitive as a C++ statement(s) on output stream "out". More... | |
| void | SetBit (UInt_t f, Bool_t set) |
| Set or unset the user status bits as specified in f. More... | |
| void | SetBit (UInt_t f) |
| virtual void | SetDrawOption (Option_t *option="") |
| Set drawing option for object. More... | |
| virtual void | SetUniqueID (UInt_t uid) |
| Set the unique object id. More... | |
| virtual void | SysError (const char *method, const char *msgfmt,...) const |
| Issue system error message. More... | |
| Bool_t | TestBit (UInt_t f) const |
| Int_t | TestBits (UInt_t f) const |
| virtual void | UseCurrentStyle () |
| Set current style settings in this object This function is called when either TCanvas::UseCurrentStyle or TROOT::ForceStyle have been invoked. More... | |
| virtual void | Warning (const char *method, const char *msgfmt,...) const |
| Issue warning message. More... | |
| virtual Int_t | Write (const char *name=0, Int_t option=0, Int_t bufsize=0) |
| Write this object to the current directory. More... | |
| virtual Int_t | Write (const char *name=0, Int_t option=0, Int_t bufsize=0) const |
| Write this object to the current directory. More... | |
Protected Attributes | |
| UChar_t * | fAxis |
| Value * | fBoundaries |
| data points More... | |
| Index | fBucketSize |
| Int_t | fCrossNode |
| smallest terminal row - first row that contains terminal nodes More... | |
| Value ** | fData |
| Int_t | fDataOwner |
| Index * | fIndPoints |
| nodes boundaries More... | |
| Index | fNDim |
| Index | fNDimm |
| Int_t | fNNodes |
| 0 - not owner, 2 - owner of the pointer array, 1 - owner of the whole 2-d array More... | |
| Index | fNPoints |
| Int_t | fOffset |
| cross node - node that begins the last row (with terminal nodes only) More... | |
| Value * | fRange |
| Int_t | fRowT0 |
| array of points indexes More... | |
| Int_t | fTotalNodes |
| Value * | fValue |
Private Member Functions | |
| TKDTree (const TKDTree &) | |
| void | CookBoundaries (const Int_t node, Bool_t left) |
| define index of this terminal node More... | |
| TKDTree< Index, Value > & | operator= (const TKDTree< Index, Value > &) |
| void | UpdateNearestNeighbors (Index inode, const Value *point, Int_t kNN, Index *ind, Value *dist) |
| Update the nearest neighbors values by examining the node inode. More... | |
| void | UpdateRange (Index inode, Value *point, Value range, std::vector< Index > &res) |
| Internal recursive function with the implementation of range searches. More... | |
Additional Inherited Members | |
| Public Types inherited from TObject | |
| enum | { kIsOnHeap = 0x01000000, kNotDeleted = 0x02000000, kZombie = 0x04000000, kBitMask = 0x00ffffff } |
| enum | { kSingleKey = BIT(0), kOverwrite = BIT(1), kWriteDelete = BIT(2) } |
| enum | EStatusBits { kCanDelete = BIT(0), kMustCleanup = BIT(3), kObjInCanvas = BIT(3), kIsReferenced = BIT(4), kHasUUID = BIT(5), kCannotPick = BIT(6), kNoContextMenu = BIT(8), kInvalidObject = BIT(13) } |
| Static Public Member Functions inherited from TObject | |
| static Long_t | GetDtorOnly () |
| Return destructor only flag. More... | |
| static Bool_t | GetObjectStat () |
| Get status of object stat flag. More... | |
| static void | SetDtorOnly (void *obj) |
| Set destructor only flag. More... | |
| static void | SetObjectStat (Bool_t stat) |
| Turn on/off tracking of objects in the TObjectTable. More... | |
| Protected Member Functions inherited from TObject | |
| virtual void | DoError (int level, const char *location, const char *fmt, va_list va) const |
| Interface to ErrorHandler (protected). More... | |
| void | MakeZombie () |
#include <TKDTree.h>
Default constructor. Nothing is built.
Definition at line 270 of file TKDTree.cxx.
| TKDTree< Index, Value >::TKDTree | ( | Index | npoints, |
| Index | ndim, | ||
| UInt_t | bsize | ||
| ) |
Definition at line 292 of file TKDTree.cxx.
| TKDTree< Index, Value >::TKDTree | ( | Index | npoints, |
| Index | ndim, | ||
| UInt_t | bsize, | ||
| Value ** | data | ||
| ) |
Create a kd-tree from the provided data array.
This function only sets the data, call Build() to build the tree!!! Parameteres:
The data should be placed columnwise (like in a TTree). The columnwise orientation is chosen to simplify the usage together with TTree::GetV1() like functions. An example of filling such an array for a 2d case: Double_t **data = new Double_t*[2]; data[0] = new Double_t[npoints]; data[1] = new Double_t[npoints]; for (Int_t i=0; i<npoints; i++){ data[0][i]=gRandom->Uniform(-1, 1); //fill the x-coordinate data[1][i]=gRandom->Uniform(-1, 1); //fill the y-coordinate }
By default, the kd-tree doesn't own the data. If you want the kd-tree to delete the data array, call kdtree->SetOwner(kTRUE).
Definition at line 344 of file TKDTree.cxx.
Destructor By default, the original data is not owned by kd-tree and is not deleted with it.
If you want to delete the data along with the kd-tree, call SetOwner(kTRUE).
Definition at line 373 of file TKDTree.cxx.
|
private |
Build the kd-tree.
The tree is divided recursively. See class description, section 4b for the details of the division alogrithm
Definition at line 411 of file TKDTree.cxx.
|
private |
define index of this terminal node
Definition at line 1074 of file TKDTree.cxx.
| Double_t TKDTree< Index, Value >::Distance | ( | const Value * | point, |
| Index | ind, | ||
| Int_t | type = 2 |
||
| ) | const |
Find the distance between point of the first argument and the point at index value ind Type argument specifies the metric: type=2 - L2 metric, type=1 - L1 metric.
Definition at line 615 of file TKDTree.cxx.
| void TKDTree< Index, Value >::DistanceToNode | ( | const Value * | point, |
| Index | inode, | ||
| Value & | min, | ||
| Value & | max, | ||
| Int_t | type = 2 |
||
| ) |
Find the minimal and maximal distance from a given point to a given node.
Type argument specifies the metric: type=2 - L2 metric, type=1 - L1 metric If the point is inside the node, both min and max are set to 0.
Definition at line 640 of file TKDTree.cxx.
| void TKDTree< Index, Value >::FindBNodeA | ( | Value * | point, |
| Value * | delta, | ||
| Int_t & | inode | ||
| ) |
find the smallest node covering the full range - start
Definition at line 1178 of file TKDTree.cxx.
| void TKDTree< Index, Value >::FindInRange | ( | Value * | point, |
| Value | range, | ||
| std::vector< Index > & | res | ||
| ) |
Find all points in the sphere of a given radius "range" around the given point 1st argument - the point 2nd argument - radius of the shere 3rd argument - a vector, in which the results will be returned.
Definition at line 754 of file TKDTree.cxx.
| void TKDTree< Index, Value >::FindNearestNeighbors | ( | const Value * | point, |
| Int_t | k, | ||
| Index * | ind, | ||
| Value * | dist | ||
| ) |
Find kNN nearest neighbors to the point in the first argument Returns 1 on success, 0 on failure Arrays ind and dist are provided by the user and are assumed to be at least kNN elements long.
Definition at line 548 of file TKDTree.cxx.
| Index TKDTree< Index, Value >::FindNode | ( | const Value * | point | ) | const |
returns the index of the terminal node to which point belongs (index in the fAxis, fValue, etc arrays) returns -1 in case of failure
Definition at line 677 of file TKDTree.cxx.
| void TKDTree< Index, Value >::FindPoint | ( | Value * | point, |
| Index & | index, | ||
| Int_t & | iter | ||
| ) |
find the index of point works only if we keep fData pointers
Definition at line 708 of file TKDTree.cxx.
| Value * TKDTree< Index, Value >::GetBoundaries | ( | ) |
Get the boundaries.
Definition at line 1190 of file TKDTree.cxx.
| Value * TKDTree< Index, Value >::GetBoundariesExact | ( | ) |
Get the boundaries.
Definition at line 1201 of file TKDTree.cxx.
| Value * TKDTree< Index, Value >::GetBoundary | ( | const Int_t | node | ) |
Get a boundary.
Definition at line 1211 of file TKDTree.cxx.
| Value * TKDTree< Index, Value >::GetBoundaryExact | ( | const Int_t | node | ) |
Get a boundary.
Definition at line 1221 of file TKDTree.cxx.
|
inline |
|
inline |
|
inline |
| void TKDTree< Index, Value >::GetNodePointsIndexes | ( | Int_t | node, |
| Int_t & | first1, | ||
| Int_t & | last1, | ||
| Int_t & | first2, | ||
| Int_t & | last2 | ||
| ) | const |
Return the indices of points in that node Indices are returned as the first and last value of the part of indices array, that belong to this node Sometimes points are in 2 intervals, then the first and last value for the second one are returned in third and fourth parameter, otherwise first2 is set to 0 and last2 is set to -1 To iterate over all the points of the node #inode, one can do, for example: Index *indices = kdtree->GetPointsIndexes(); Int_t first1, last1, first2, last2; kdtree->GetPointsIndexes(inode, first1, last1, first2, last2); for (Int_t ipoint=first1; ipoint<=last1; ipoint++){ point = indices[ipoint]; //do something with point; } for (Int_t ipoint=first2; ipoint<=last2; ipoint++){ point = indices[ipoint]; //do something with point; }.
Definition at line 846 of file TKDTree.cxx.
|
inline |
| Index TKDTree< Index, Value >::GetNPointsNode | ( | Int_t | node | ) | const |
Get number of points in this node for all the terminal nodes except last, the size is fBucketSize for the last node it's fOffsetfBucketSize, or if fOffsetfBucketSize==0, it's also fBucketSize.
Definition at line 900 of file TKDTree.cxx.
| Index * TKDTree< Index, Value >::GetPointsIndexes | ( | Int_t | node | ) | const |
return the indices of the points in that terminal node for all the nodes except last, the size is fBucketSize for the last node it's fOffsetfBucketSize
Definition at line 817 of file TKDTree.cxx.
| Value TKDTree< Index, Value >::KOrdStat | ( | Index | ntotal, |
| Value * | a, | ||
| Index | k, | ||
| Index * | index | ||
| ) | const |
copy of the TMath::KOrdStat because I need an Index work array
Definition at line 985 of file TKDTree.cxx.
| void TKDTree< Index, Value >::MakeBoundaries | ( | Value * | range = 0x0 | ) |
Build boundaries for each node.
Note, that the boundaries here are built based on the splitting planes of the kd-tree, and don't necessarily pass through the points of the original dataset. For the latter functionality see function MakeBoundariesExact() Boundaries can be retrieved by calling GetBoundary(inode) function that would return an array of boundaries for the specified node, or GetBoundaries() function that would return the complete array.
Definition at line 1039 of file TKDTree.cxx.
Build boundaries for each node.
Unlike MakeBoundaries() function the boundaries built here always pass through a point of the original dataset So, for example, for a terminal node with just one point minimum and maximum for each dimension are the same. Boundaries can be retrieved by calling GetBoundaryExact(inode) function that would return an array of boundaries for the specified node, or GetBoundaries() function that would return the complete array.
Definition at line 1119 of file TKDTree.cxx.
|
private |
| void TKDTree< Index, Value >::SetData | ( | Index | npoints, |
| Index | ndim, | ||
| UInt_t | bsize, | ||
| Value ** | data | ||
| ) |
Set the data array. See the constructor function comments for details.
Definition at line 923 of file TKDTree.cxx.
| Int_t TKDTree< Index, Value >::SetData | ( | Index | idim, |
| Value * | data | ||
| ) |
Set the coordinate #ndim of all points (the column #ndim of the data matrix) After setting all the data columns, proceed by calling Build() function Note, that calling this function after Build() is not possible Note also, that no checks on the array sizes is performed anywhere.
Definition at line 948 of file TKDTree.cxx.
| void TKDTree< Index, Value >::Spread | ( | Index | ntotal, |
| Value * | a, | ||
| Index * | index, | ||
| Value & | min, | ||
| Value & | max | ||
| ) | const |
Calculate spread of the array a.
Definition at line 968 of file TKDTree.cxx.
|
private |
Update the nearest neighbors values by examining the node inode.
Definition at line 568 of file TKDTree.cxx.
|
private |
Internal recursive function with the implementation of range searches.
Definition at line 764 of file TKDTree.cxx.
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
ROOT 6.10/09 - Reference Guide Generated on Thu May 31 2018 12:14:56 using Doxygen 1.8.13.