Logo ROOT   6.18/05
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();
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);
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
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
int Int_t
Definition: RtypesCore.h:41
unsigned char UChar_t
Definition: RtypesCore.h:34
unsigned int UInt_t
Definition: RtypesCore.h:42
bool Bool_t
Definition: RtypesCore.h:59
double Double_t
Definition: RtypesCore.h:55
#define ClassDef(name, id)
Definition: Rtypes.h:326
XFontStruct * id
Definition: TGX11.cxx:108
int type
Definition: TGX11.cxx:120
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:708
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
Int_t GetCrossNode()
smallest terminal row
Definition: TKDTree.h:45
Int_t fCrossNode
smallest terminal row - first row that contains terminal nodes
Definition: TKDTree.h:94
Index GetBucketSize()
Definition: TKDTree.h:48
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
Index GetNDim()
Definition: TKDTree.h:40
Index * GetIndPoints()
offset in fIndPoints
Definition: TKDTree.h:47
Index * fIndPoints
nodes boundaries
Definition: TKDTree.h:92
Value * fValue
Definition: TKDTree.h:85
Value * GetBoundaryExact(const Int_t node)
Get a boundary.
Definition: TKDTree.cxx:1221
Int_t IsOwner()
Definition: TKDTree.h:57
void MakeBoundaries(Value *range=0x0)
Build boundaries for each node.
Definition: TKDTree.cxx:1039
void FindBNodeA(Value *point, Value *delta, Int_t &inode)
find the smallest node covering the full range - start
Definition: TKDTree.cxx:1178
Value * fRange
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:764
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:677
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 ** fData
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:985
Int_t fOffset
cross node - node that begins the last row (with terminal nodes only)
Definition: TKDTree.h:95
Value GetNodeValue(Int_t id) const
Definition: TKDTree.h:32
Value * GetBoundariesExact()
Get the boundaries.
Definition: TKDTree.cxx:1201
UChar_t * fAxis
Definition: TKDTree.h:84
Int_t fDataOwner
Definition: TKDTree.h:77
~TKDTree()
Destructor By default, the original data is not owned by kd-tree and is not deleted with it.
Definition: TKDTree.cxx:373
Index fNDim
Definition: TKDTree.h:80
void MakeBoundariesExact()
Build boundaries for each node.
Definition: TKDTree.cxx:1119
void CookBoundaries(const Int_t node, Bool_t left)
define index of this terminal node
Definition: TKDTree.cxx:1074
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
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:615
Index fBucketSize
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:817
void Spread(Index ntotal, Value *a, Index *index, Value &min, Value &max) const
Calculate spread of the array a.
Definition: TKDTree.cxx:968
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:640
Int_t GetNNodes() const
Definition: TKDTree.h:33
TKDTree()
Default constructor. Nothing is built.
Definition: TKDTree.cxx:270
Int_t fRowT0
array of points indexes
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:754
Value * fBoundaries
data points
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:900
Value * GetBoundaries()
Get the boundaries.
Definition: TKDTree.cxx:1190
Index fNDimm
Definition: TKDTree.h:81
Value * GetBoundary(const Int_t node)
Get a boundary.
Definition: TKDTree.cxx:1211
TKDTree< Index, Value > & operator=(const TKDTree< Index, Value > &)
Int_t fTotalNodes
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:548
Index fNPoints
Definition: TKDTree.h:82
Int_t GetRowT0()
Definition: TKDTree.h:44
Mother of all ROOT objects.
Definition: TObject.h:37
double dist(Rotation3D const &r1, Rotation3D const &r2)
Definition: 3DDistances.cxx:48
RooCmdArg Index(RooCategory &icat)
const char * Value
Definition: TXMLSetup.cxx:72
auto * a
Definition: textangle.C:12