Logo ROOT   6.13/01
Reference Guide
TKDTree.h
Go to the documentation of this file.
1 #ifndef ROOT_TKDTree
2 #define ROOT_TKDTree
3 
4 #include "TObject.h"
5 
6 #include "TMath.h"
7 #include <vector>
8 
9 template <typename Index, typename Value> class TKDTree : public TObject
10 {
11 public:
12 
13  TKDTree();
14  TKDTree(Index npoints, Index ndim, UInt_t bsize);
15  TKDTree(Index npoints, Index ndim, UInt_t bsize, Value **data);
16  ~TKDTree();
17 
18  void Build(); // build the tree
19 
20  Double_t Distance(const Value *point, Index ind, Int_t type=2) const;
21  void DistanceToNode(const Value *point, Index inode, Value &min, Value &max, Int_t type=2);
22 
23  // Get indexes of left and right daughter nodes
24  Int_t GetLeft(Int_t inode) const {return inode*2+1;}
25  Int_t GetRight(Int_t inode) const {return (inode+1)*2;}
26  Int_t GetParent(Int_t inode) const {return (inode-1)/2;}
27  //
28  // Other getters
29  Index* GetPointsIndexes(Int_t node) const;
30  void GetNodePointsIndexes(Int_t node, Int_t &first1, Int_t &last1, Int_t &first2, Int_t &last2) const;
31  UChar_t GetNodeAxis(Int_t id) const {return (id < 0 || id >= fNNodes) ? 0 : fAxis[id];}
32  Value GetNodeValue(Int_t id) const {return (id < 0 || id >= fNNodes) ? 0 : fValue[id];}
33  Int_t GetNNodes() const {return fNNodes;}
34  Int_t GetTotalNodes() const {return fTotalNodes;}
35  Value* GetBoundaries();
36  Value* GetBoundariesExact();
37  Value* GetBoundary(const Int_t node);
38  Value* GetBoundaryExact(const Int_t node);
39  Index GetNPoints() { return fNPoints; }
40  Index GetNDim() { return fNDim; }
41  Index GetNPointsNode(Int_t node) const;
42 
43  //Getters for internal variables.
44  Int_t GetRowT0() {return fRowT0;} //! smallest terminal row
45  Int_t GetCrossNode() {return fCrossNode;} //! cross node
46  Int_t GetOffset() {return fOffset;} //! offset in fIndPoints
47  Index* GetIndPoints() {return fIndPoints;}
48  Index GetBucketSize() {return fBucketSize;}
49 
50  void FindNearestNeighbors(const Value *point, Int_t k, Index *ind, Value *dist);
51  Index FindNode(const Value * point) const;
52  void FindPoint(Value * point, Index &index, Int_t &iter);
53  void FindInRange(Value *point, Value range, std::vector<Index> &res);
54  void FindBNodeA(Value * point, Value * delta, Int_t &inode);
55 
56  Bool_t IsTerminal(Index inode) const {return (inode>=fNNodes);}
57  Int_t IsOwner() { return fDataOwner; }
58  Value KOrdStat(Index ntotal, Value *a, Index k, Index *index) const;
59 
60 
61  void MakeBoundaries(Value *range = 0x0);
62  void MakeBoundariesExact();
63  void SetData(Index npoints, Index ndim, UInt_t bsize, Value **data);
64  Int_t SetData(Index idim, Value *data);
65  void SetOwner(Int_t owner) { fDataOwner = owner; }
66  void Spread(Index ntotal, Value *a, Index *index, Value &min, Value &max) const;
67 
68  private:
69  TKDTree(const TKDTree &); // not implemented
70  TKDTree<Index, Value>& operator=(const TKDTree<Index, Value>&); // not implemented
71  void CookBoundaries(const Int_t node, Bool_t left);
72 
73  void UpdateNearestNeighbors(Index inode, const Value *point, Int_t kNN, Index *ind, Value *dist);
74  void UpdateRange(Index inode, Value *point, Value range, std::vector<Index> &res);
75 
76  protected:
77  Int_t fDataOwner; //! 0 - not owner, 2 - owner of the pointer array, 1 - owner of the whole 2-d array
78  Int_t fNNodes; // size of node array
79  Int_t fTotalNodes; // total number of nodes (fNNodes + terminal nodes)
80  Index fNDim; // number of dimensions
81  Index fNDimm; // dummy 2*fNDim
82  Index fNPoints; // number of multidimensional points
83  Index fBucketSize; // size of the terminal nodes
84  UChar_t *fAxis; //[fNNodes] nodes cutting axis
85  Value *fValue; //[fNNodes] nodes cutting value
86  //
87  Value *fRange; //[fNDimm] range of data for each dimension
88  Value **fData; //! data points
89  Value *fBoundaries;//! nodes boundaries
90 
91 
92  Index *fIndPoints; //! array of points indexes
93  Int_t fRowT0; //! smallest terminal row - first row that contains terminal nodes
94  Int_t fCrossNode; //! cross node - node that begins the last row (with terminal nodes only)
95  Int_t fOffset; //! offset in fIndPoints - if there are 2 rows, that contain terminal nodes
96  // fOffset returns the index in the fIndPoints array of the first point
97  // that belongs to the first node on the second row.
98 
99 
100  ClassDef(TKDTree, 1) // KD tree
101 };
102 
103 
106 
107 // Test functions:
109 
110 #endif
111 
double dist(Rotation3D const &r1, Rotation3D const &r2)
Definition: 3DDistances.cxx:48
void Spread(Index ntotal, Value *a, Index *index, Value &min, Value &max) const
Calculate spread of the array a.
Definition: TKDTree.cxx:968
Int_t GetParent(Int_t inode) const
Definition: TKDTree.h:26
Int_t fOffset
cross node - node that begins the last row (with terminal nodes only)
Definition: TKDTree.h:95
void SetData(Index npoints, Index ndim, UInt_t bsize, Value **data)
Set the data array. See the constructor function comments for details.
Definition: TKDTree.cxx:923
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
Definition: TKDTree.cxx:677
Int_t fDataOwner
Definition: TKDTree.h:77
Int_t GetRowT0()
Definition: TKDTree.h:44
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&#39;s fOffsetfBucketSize
Definition: TKDTree.cxx:817
TKDTree< Int_t, Float_t > TKDTreeIF
Definition: TKDTree.h:105
Index GetNPoints()
Definition: TKDTree.h:39
Bool_t IsTerminal(Index inode) const
Definition: TKDTree.h:56
Int_t fTotalNodes
Definition: TKDTree.h:79
void FindBNodeA(Value *point, Value *delta, Int_t &inode)
find the smallest node covering the full range - start
Definition: TKDTree.cxx:1178
Index GetNDim()
Definition: TKDTree.h:40
Index fNPoints
Definition: TKDTree.h:82
Int_t GetOffset()
cross node
Definition: TKDTree.h:46
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 poi...
Definition: TKDTree.cxx:754
Index fBucketSize
Definition: TKDTree.h:83
void MakeBoundariesExact()
Build boundaries for each node.
Definition: TKDTree.cxx:1119
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...
Definition: TKDTree.cxx:900
void SetOwner(Int_t owner)
Definition: TKDTree.h:65
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 ...
Definition: TKDTree.cxx:615
Value * fRange
Definition: TKDTree.h:87
Int_t GetCrossNode()
smallest terminal row
Definition: TKDTree.h:45
void Build()
Build the kd-tree.
Definition: TKDTree.cxx:411
Index fNDim
Definition: TKDTree.h:80
Int_t GetRight(Int_t inode) const
Definition: TKDTree.h:25
void FindPoint(Value *point, Index &index, Int_t &iter)
find the index of point works only if we keep fData pointers
Definition: TKDTree.cxx:708
Index GetBucketSize()
Definition: TKDTree.h:48
TKDTree()
Default constructor. Nothing is built.
Definition: TKDTree.cxx:270
Index * fIndPoints
nodes boundaries
Definition: TKDTree.h:92
Class implementing a kd-tree.
Definition: TKDTree.h:9
UChar_t * fAxis
Definition: TKDTree.h:84
Int_t IsOwner()
Definition: TKDTree.h:57
Int_t GetNNodes() const
Definition: TKDTree.h:33
void UpdateNearestNeighbors(Index inode, const Value *point, Int_t kNN, Index *ind, Value *dist)
Update the nearest neighbors values by examining the node inode.
Definition: TKDTree.cxx:568
Int_t fRowT0
array of points indexes
Definition: TKDTree.h:93
~TKDTree()
Destructor By default, the original data is not owned by kd-tree and is not deleted with it...
Definition: TKDTree.cxx:373
Value KOrdStat(Index ntotal, Value *a, Index k, Index *index) const
copy of the TMath::KOrdStat because I need an Index work array
Definition: TKDTree.cxx:985
TKDTree< Index, Value > & operator=(const TKDTree< Index, Value > &)
Int_t GetLeft(Int_t inode) const
Definition: TKDTree.h:24
TKDTreeIF * TKDTreeTestBuild()
Index * GetIndPoints()
offset in fIndPoints
Definition: TKDTree.h:47
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 par...
Definition: TKDTree.cxx:846
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.
Definition: TKDTree.cxx:548
void CookBoundaries(const Int_t node, Bool_t left)
define index of this terminal node
Definition: TKDTree.cxx:1074
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.
Definition: TKDTree.cxx:640
TKDTree< Int_t, Double_t > TKDTreeID
Definition: TKDTree.h:104
Value * fValue
Definition: TKDTree.h:85
void MakeBoundaries(Value *range=0x0)
Build boundaries for each node.
Definition: TKDTree.cxx:1039
Value * GetBoundariesExact()
Get the boundaries.
Definition: TKDTree.cxx:1201
Int_t fCrossNode
smallest terminal row - first row that contains terminal nodes
Definition: TKDTree.h:94
Index fNDimm
Definition: TKDTree.h:81
Value ** fData
Definition: TKDTree.h:88
Value GetNodeValue(Int_t id) const
Definition: TKDTree.h:32
void UpdateRange(Index inode, Value *point, Value range, std::vector< Index > &res)
Internal recursive function with the implementation of range searches.
Definition: TKDTree.cxx:764
Int_t fNNodes
0 - not owner, 2 - owner of the pointer array, 1 - owner of the whole 2-d array
Definition: TKDTree.h:78
Value * GetBoundaries()
Get the boundaries.
Definition: TKDTree.cxx:1190
UChar_t GetNodeAxis(Int_t id) const
Definition: TKDTree.h:31
Int_t GetTotalNodes() const
Definition: TKDTree.h:34
Value * GetBoundaryExact(const Int_t node)
Get a boundary.
Definition: TKDTree.cxx:1221
Value * fBoundaries
data points
Definition: TKDTree.h:89
Value * GetBoundary(const Int_t node)
Get a boundary.
Definition: TKDTree.cxx:1211