Logo ROOT  
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
9template <typename Index, typename Value> class TKDTree : public TObject
10{
11public:
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() override;
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;}
37 Value* GetBoundary(const Int_t node);
38 Value* GetBoundaryExact(const Int_t node);
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
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);
63 void SetData(Index npoints, Index ndim, UInt_t bsize, 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
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
101};
102
103
106
107// Test functions:
109
110#endif
111
int Int_t
Definition: RtypesCore.h:45
unsigned char UChar_t
Definition: RtypesCore.h:38
unsigned int UInt_t
Definition: RtypesCore.h:46
#define ClassDefOverride(name, id)
Definition: Rtypes.h:339
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void data
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t index
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize id
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t Int_t Int_t Window_t TString Int_t GCValues_t GetPrimarySelectionOwner GetDisplay GetScreen GetColormap GetNativeEvent const char const char dpyName wid window const char font_name cursor keysym reg const char only_if_exist regb h Point_t winding char text const char depth char const char Int_t count const char ColorStruct_t color const char Pixmap_t Pixmap_t PictureAttributes_t attr const char char ret_data h unsigned char height h Atom_t Int_t ULong_t ULong_t unsigned char prop_list Atom_t Atom_t Atom_t Time_t type
TKDTree< Int_t, Double_t > TKDTreeID
Definition: TKDTree.h:104
TKDTreeIF * TKDTreeTestBuild()
TKDTree< Int_t, Float_t > TKDTreeIF
Definition: TKDTree.h:105
Class implementing a kd-tree.
Definition: TKDTree.h:10
Int_t GetLeft(Int_t inode) const
Definition: TKDTree.h:24
UChar_t GetNodeAxis(Int_t id) const
Definition: TKDTree.h:31
Int_t GetOffset()
cross node
Definition: TKDTree.h:46
Int_t GetTotalNodes() const
Definition: TKDTree.h:34
void FindPoint(Value *point, Index &index, Int_t &iter)
find the index of point works only if we keep fData pointers
Definition: TKDTree.cxx:703
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:918
Int_t GetCrossNode()
smallest terminal row
Definition: TKDTree.h:45
Int_t fCrossNode
! cross node - node that begins the last row (with terminal nodes only)
Definition: TKDTree.h:94
Index GetBucketSize()
Definition: TKDTree.h:48
~TKDTree() override
Destructor By default, the original data is not owned by kd-tree and is not deleted with it.
Definition: TKDTree.cxx:373
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:841
Index GetNDim()
Definition: TKDTree.h:40
Index * GetIndPoints()
offset in fIndPoints
Definition: TKDTree.h:47
Index * fIndPoints
! array of points indexes
Definition: TKDTree.h:92
Value * fValue
[fNNodes] nodes cutting value
Definition: TKDTree.h:85
Value * GetBoundaryExact(const Int_t node)
Get a boundary.
Definition: TKDTree.cxx:1216
Int_t IsOwner()
Definition: TKDTree.h:57
void MakeBoundaries(Value *range=0x0)
Build boundaries for each node.
Definition: TKDTree.cxx:1034
void FindBNodeA(Value *point, Value *delta, Int_t &inode)
find the smallest node covering the full range - start
Definition: TKDTree.cxx:1173
Value * fRange
[fNDimm] range of data for each dimension
Definition: TKDTree.h:87
void UpdateRange(Index inode, Value *point, Value range, std::vector< Index > &res)
Internal recursive function with the implementation of range searches.
Definition: TKDTree.cxx:759
TKDTree(const TKDTree &)
Index FindNode(const Value *point) const
returns the index of the terminal node to which point belongs (index in the fAxis,...
Definition: TKDTree.cxx:672
Int_t fNNodes
size of node array
Definition: TKDTree.h:78
Value ** fData
! data points
Definition: TKDTree.h:88
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:980
Int_t fOffset
! offset in fIndPoints - if there are 2 rows, that contain terminal nodes fOffset returns the index i...
Definition: TKDTree.h:95
Value GetNodeValue(Int_t id) const
Definition: TKDTree.h:32
Value * GetBoundariesExact()
Get the boundaries.
Definition: TKDTree.cxx:1196
UChar_t * fAxis
[fNNodes] nodes cutting axis
Definition: TKDTree.h:84
Int_t fDataOwner
! 0 - not owner, 2 - owner of the pointer array, 1 - owner of the whole 2-d array
Definition: TKDTree.h:77
Index fNDim
number of dimensions
Definition: TKDTree.h:80
void MakeBoundariesExact()
Build boundaries for each node.
Definition: TKDTree.cxx:1114
void CookBoundaries(const Int_t node, Bool_t left)
define index of this terminal node
Definition: TKDTree.cxx:1069
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:563
Index GetNPoints()
Definition: TKDTree.h:39
Int_t GetRight(Int_t inode) const
Definition: TKDTree.h:25
Int_t GetParent(Int_t inode) const
Definition: TKDTree.h:26
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:610
Index fBucketSize
size of the terminal nodes
Definition: TKDTree.h:83
Index * GetPointsIndexes(Int_t node) const
return the indices of the points in that terminal node for all the nodes except last,...
Definition: TKDTree.cxx:812
void Spread(Index ntotal, Value *a, Index *index, Value &min, Value &max) const
Calculate spread of the array a.
Definition: TKDTree.cxx:963
void Build()
Build the kd-tree.
Definition: TKDTree.cxx:411
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:635
Int_t GetNNodes() const
Definition: TKDTree.h:33
TKDTree()
Default constructor. Nothing is built.
Definition: TKDTree.cxx:270
Int_t fRowT0
! smallest terminal row - first row that contains terminal nodes
Definition: TKDTree.h:93
void SetOwner(Int_t owner)
Definition: TKDTree.h:65
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:749
Value * fBoundaries
! nodes boundaries
Definition: TKDTree.h:89
Bool_t IsTerminal(Index inode) const
Definition: TKDTree.h:56
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:895
Value * GetBoundaries()
Get the boundaries.
Definition: TKDTree.cxx:1185
Index fNDimm
dummy 2*fNDim
Definition: TKDTree.h:81
Value * GetBoundary(const Int_t node)
Get a boundary.
Definition: TKDTree.cxx:1206
TKDTree< Index, Value > & operator=(const TKDTree< Index, Value > &)
Int_t fTotalNodes
total number of nodes (fNNodes + terminal nodes)
Definition: TKDTree.h:79
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,...
Definition: TKDTree.cxx:543
Index fNPoints
number of multidimensional points
Definition: TKDTree.h:82
Int_t GetRowT0()
Definition: TKDTree.h:44
kNN::Event describes point in input variable vector-space, with additional functionality like distanc...
Mother of all ROOT objects.
Definition: TObject.h:37
RooCmdArg Index(RooCategory &icat)
double dist(Rotation3D const &r1, Rotation3D const &r2)
Definition: 3DDistances.cxx:48
TArc a
Definition: textangle.C:12