Geant4 11.1.1
Toolkit for the simulation of the passage of particles through matter
Loading...
Searching...
No Matches
G4KDTree Class Reference

#include <G4KDTree.hh>

Classes

class  HyperRect
 

Public Member Functions

 G4KDTree (std::size_t dim=3)
 
 ~G4KDTree ()
 
void Clear ()
 
void Print (std::ostream &out=G4cout) const
 
void Build ()
 
void NoticeNodeDeactivation ()
 
std::size_t GetDim () const
 
G4int GetNbNodes () const
 
G4KDNode_BaseGetRoot ()
 
template<typename PointT >
G4KDNode_BaseInsertMap (PointT *pos)
 
template<typename PointT >
G4KDNode_BaseInsert (PointT *pos)
 
template<typename PointT >
G4KDNode_BaseInsert (const PointT &pos)
 
template<typename Position >
G4KDTreeResultHandle Nearest (const Position &pos)
 
G4KDTreeResultHandle Nearest (G4KDNode_Base *node)
 
template<typename Position >
G4KDTreeResultHandle NearestInRange (const Position &pos, const G4double &range)
 
G4KDTreeResultHandle NearestInRange (G4KDNode_Base *node, const G4double &range)
 
void * operator new (std::size_t)
 
void operator delete (void *)
 

Protected Member Functions

void __InsertMap (G4KDNode_Base *node)
 
void __Clear_Rec (G4KDNode_Base *node)
 
template<typename Position >
G4int __NearestInRange (G4KDNode_Base *node, const Position &pos, const G4double &range_sq, const G4double &range, G4KDTreeResult &list, G4int ordered, G4KDNode_Base *source_node=nullptr)
 
template<typename Position >
void __NearestToPosition (G4KDNode_Base *node, const Position &pos, G4KDNode_Base *&result, G4double *result_dist_sq, HyperRect *fRect)
 
template<typename Position >
void __NearestToNode (G4KDNode_Base *source_node, G4KDNode_Base *node, const Position &pos, std::vector< G4KDNode_Base * > &result, G4double *result_dist_sq, HyperRect *fRect, G4int &nbresult)
 

Static Protected Member Functions

static G4Allocator< G4KDTree > *& fgAllocator ()
 

Protected Attributes

HyperRectfRect = nullptr
 
G4KDNode_BasefRoot = nullptr
 
std::size_t fDim
 
G4int fNbNodes = 0
 
G4int fNbActiveNodes = 0
 
G4KDMapfKDMap
 

Friends

class G4KDNode_Base
 

Detailed Description

G4KDTree is used by the ITManager to locate the neareast neighbours. A kdtree sorts out node in such a way that it reduces the number of node check. The results of this search can be retrieved by G4KDTreeResultHandle.

Definition at line 70 of file G4KDTree.hh.

Constructor & Destructor Documentation

◆ G4KDTree()

G4KDTree::G4KDTree ( std::size_t  dim = 3)

Definition at line 53 of file G4KDTree.cc.

54 : fDim(k)
55 ,fKDMap(new G4KDMap(k))
56{}
std::size_t fDim
Definition: G4KDTree.hh:247
G4KDMap * fKDMap
Definition: G4KDTree.hh:250

◆ ~G4KDTree()

G4KDTree::~G4KDTree ( )

Definition at line 58 of file G4KDTree.cc.

59{
60 if(fRoot){
62 fRoot = nullptr;
63 }
64
65 if(fRect){
66 delete fRect;
67 fRect = nullptr;
68 }
69
70 if(fKDMap){
71 delete fKDMap;
72 fKDMap = nullptr;
73 }
74}
HyperRect * fRect
Definition: G4KDTree.hh:245
G4KDNode_Base * fRoot
Definition: G4KDTree.hh:246
void __Clear_Rec(G4KDNode_Base *node)
Definition: G4KDTree.cc:109

Member Function Documentation

◆ __Clear_Rec()

void G4KDTree::__Clear_Rec ( G4KDNode_Base node)
protected

Definition at line 109 of file G4KDTree.cc.

110{
111 if(!node)
112 {
113 return;
114 }
115
116 if(node->GetLeft())
117 {
118 __Clear_Rec(node->GetLeft());
119 }
120 if(node->GetRight())
121 {
122 __Clear_Rec(node->GetRight());
123 }
124
125 delete node;
126}
G4KDNode_Base * GetRight()
Definition: G4KDNode.hh:82
G4KDNode_Base * GetLeft()
Definition: G4KDNode.hh:81

Referenced by __Clear_Rec(), Clear(), and ~G4KDTree().

◆ __InsertMap()

void G4KDTree::__InsertMap ( G4KDNode_Base node)
protected

Definition at line 128 of file G4KDTree.cc.

128{ fKDMap->Insert(node); }
void Insert(G4KDNode_Base *pos)
Definition: G4KDMap.cc:90

◆ __NearestInRange()

template<typename Position >
G4int G4KDTree::__NearestInRange ( G4KDNode_Base node,
const Position &  pos,
const G4double range_sq,
const G4double range,
G4KDTreeResult list,
G4int  ordered,
G4KDNode_Base source_node = nullptr 
)
protected

Referenced by NearestInRange().

◆ __NearestToNode()

template<typename Position >
void G4KDTree::__NearestToNode ( G4KDNode_Base source_node,
G4KDNode_Base node,
const Position &  pos,
std::vector< G4KDNode_Base * > &  result,
G4double result_dist_sq,
HyperRect fRect,
G4int nbresult 
)
protected

Referenced by Nearest().

◆ __NearestToPosition()

template<typename Position >
void G4KDTree::__NearestToPosition ( G4KDNode_Base node,
const Position &  pos,
G4KDNode_Base *&  result,
G4double result_dist_sq,
HyperRect fRect 
)
protected

◆ Build()

void G4KDTree::Build ( )

Definition at line 130 of file G4KDTree.cc.

131{
132 size_t Nnodes = fKDMap->GetSize();
133
134 G4cout << "********************" << G4endl;
135 G4cout << "template<typename PointT> G4KDTree<PointT>::Build" << G4endl;
136 G4cout << "Map size = " << Nnodes << G4endl;
137
139
140 if(root == nullptr)
141 {
142 return;
143 }
144
145 fRoot = root;
147 fRect = new HyperRect(fDim);
149
150 Nnodes--;
151
152 G4KDNode_Base* parent = fRoot;
153
154 for(size_t n = 0; n < Nnodes; n += fDim)
155 {
156 for(size_t dim = 0; dim < fDim; dim++)
157 {
158 G4KDNode_Base* node = fKDMap->PopOutMiddle(dim);
159 if(node)
160 {
161 parent->Insert(node);
163 fRect->Extend(*node);
164 parent = node;
165 }
166 }
167 }
168}
#define G4endl
Definition: G4ios.hh:57
G4GLOB_DLL std::ostream G4cout
std::size_t GetSize()
Definition: G4KDMap.hh:112
G4KDNode_Base * PopOutMiddle(std::size_t dimension)
Definition: G4KDMap.cc:137
G4KDNode_Base * Insert(PointT *point)
void SetMinMax(const Position &min, const Position &max)
Definition: G4KDTree.hh:139
void Extend(const Position &pos)
Definition: G4KDTree.hh:168
G4int fNbActiveNodes
Definition: G4KDTree.hh:249

◆ Clear()

void G4KDTree::Clear ( )

Definition at line 96 of file G4KDTree.cc.

97{
99 fRoot = nullptr;
100 fNbNodes = 0;
101
102 if(fRect)
103 {
104 delete fRect;
105 fRect = nullptr;
106 }
107}
G4int fNbNodes
Definition: G4KDTree.hh:248

Referenced by NoticeNodeDeactivation().

◆ fgAllocator()

G4Allocator< G4KDTree > *& G4KDTree::fgAllocator ( )
staticprotected

Definition at line 45 of file G4KDTree.cc.

46{
47 G4ThreadLocalStatic G4Allocator<G4KDTree>* _instance = nullptr;
48 return _instance;
49}
#define G4ThreadLocalStatic
Definition: tls.hh:76

◆ GetDim()

std::size_t G4KDTree::GetDim ( ) const
inline

Definition at line 90 of file G4KDTree.hh.

90{ return fDim; }

Referenced by G4KDNode_Base::GetDim(), and G4KDNode_Base::Insert().

◆ GetNbNodes()

G4int G4KDTree::GetNbNodes ( ) const
inline

Definition at line 91 of file G4KDTree.hh.

91{ return fNbNodes; }

◆ GetRoot()

G4KDNode_Base * G4KDTree::GetRoot ( )
inline

Definition at line 92 of file G4KDTree.hh.

92{ return fRoot; }

◆ Insert() [1/2]

template<typename PointT >
G4KDNode_Base * G4KDTree::Insert ( const PointT &  pos)

◆ Insert() [2/2]

template<typename PointT >
G4KDNode_Base * G4KDTree::Insert ( PointT *  pos)

◆ InsertMap()

template<typename PointT >
G4KDNode_Base * G4KDTree::InsertMap ( PointT *  pos)

◆ Nearest() [1/2]

template<typename Position >
G4KDTreeResultHandle G4KDTree::Nearest ( const Position &  pos)

◆ Nearest() [2/2]

G4KDTreeResultHandle G4KDTree::Nearest ( G4KDNode_Base node)

Definition at line 170 of file G4KDTree.cc.

171{
172 if(!fRect)
173 {
174 return nullptr;
175 }
176
177 std::vector<G4KDNode_Base*> result;
178 G4double dist_sq = DBL_MAX;
179
180 /* Duplicate the bounding hyperrectangle, we will work on the copy */
181 auto newrect = new HyperRect(*fRect);
182
183 /* Search for the nearest neighbour recursively */
184 G4int nbresult = 0;
185
186 __NearestToNode(node, fRoot, *node, result, &dist_sq, newrect, nbresult);
187
188 /* Free the copy of the hyperrect */
189 delete newrect;
190
191 /* Store the result */
192 if(!result.empty())
193 {
194 G4KDTreeResultHandle rset(new G4KDTreeResult(this));
195 G4int j = 0;
196 while(j < nbresult)
197 {
198 rset->Insert(dist_sq, result[j]);
199 j++;
200 }
201 rset->Rewind();
202
203 return rset;
204 }
205 else
206 {
207 return nullptr;
208 }
209}
double G4double
Definition: G4Types.hh:83
int G4int
Definition: G4Types.hh:85
void __NearestToNode(G4KDNode_Base *source_node, G4KDNode_Base *node, const Position &pos, std::vector< G4KDNode_Base * > &result, G4double *result_dist_sq, HyperRect *fRect, G4int &nbresult)
#define DBL_MAX
Definition: templates.hh:62

◆ NearestInRange() [1/2]

template<typename Position >
G4KDTreeResultHandle G4KDTree::NearestInRange ( const Position &  pos,
const G4double range 
)

◆ NearestInRange() [2/2]

G4KDTreeResultHandle G4KDTree::NearestInRange ( G4KDNode_Base node,
const G4double range 
)

Definition at line 211 of file G4KDTree.cc.

213{
214 if(!node)
215 {
216 return nullptr;
217 }
218 G4int ret(-1);
219
220 auto* rset = new G4KDTreeResult(this);
221
222 const G4double range_sq = sqr(range);
223
224 if((ret = __NearestInRange(fRoot, *node, range_sq, range, *rset, 0, node)) ==
225 -1)
226 {
227 delete rset;
228 return nullptr;
229 }
230 rset->Sort();
231 rset->Rewind();
232 return rset;
233}
G4int __NearestInRange(G4KDNode_Base *node, const Position &pos, const G4double &range_sq, const G4double &range, G4KDTreeResult &list, G4int ordered, G4KDNode_Base *source_node=nullptr)
T sqr(const T &x)
Definition: templates.hh:128

◆ NoticeNodeDeactivation()

void G4KDTree::NoticeNodeDeactivation ( )
inline

Definition at line 81 of file G4KDTree.hh.

82 {
84 if(fNbActiveNodes <= 0)
85 {
86 Clear();
87 }
88 }
void Clear()
Definition: G4KDTree.cc:96

Referenced by G4KDNode_Base::InactiveNode().

◆ operator delete()

void G4KDTree::operator delete ( void *  aNode)

Definition at line 84 of file G4KDTree.cc.

85{
86 fgAllocator()->FreeSingle((G4KDTree*) aNode);
87}
static G4Allocator< G4KDTree > *& fgAllocator()
Definition: G4KDTree.cc:45

◆ operator new()

void * G4KDTree::operator new ( std::size_t  )

Definition at line 76 of file G4KDTree.cc.

77{
78 if(!fgAllocator()){
80 }
81 return (void*) fgAllocator()->MallocSingle();
82}

◆ Print()

void G4KDTree::Print ( std::ostream &  out = G4cout) const

Definition at line 89 of file G4KDTree.cc.

90{
91 if(fRoot){
92 fRoot->Print(out);
93 }
94}
void Print(std::ostream &out, G4int level=0) const
Definition: G4KDNode.cc:177

Friends And Related Function Documentation

◆ G4KDNode_Base

friend class G4KDNode_Base
friend

Definition at line 72 of file G4KDTree.hh.

Member Data Documentation

◆ fDim

std::size_t G4KDTree::fDim
protected

Definition at line 247 of file G4KDTree.hh.

Referenced by Build(), G4KDNode_Base::G4KDNode_Base(), and GetDim().

◆ fKDMap

G4KDMap* G4KDTree::fKDMap
protected

Definition at line 250 of file G4KDTree.hh.

Referenced by __InsertMap(), Build(), and ~G4KDTree().

◆ fNbActiveNodes

G4int G4KDTree::fNbActiveNodes = 0
protected

Definition at line 249 of file G4KDTree.hh.

Referenced by Build(), and NoticeNodeDeactivation().

◆ fNbNodes

G4int G4KDTree::fNbNodes = 0
protected

Definition at line 248 of file G4KDTree.hh.

Referenced by Clear(), and GetNbNodes().

◆ fRect

HyperRect* G4KDTree::fRect = nullptr
protected

Definition at line 245 of file G4KDTree.hh.

Referenced by Build(), Clear(), Nearest(), and ~G4KDTree().

◆ fRoot

G4KDNode_Base* G4KDTree::fRoot = nullptr
protected

Definition at line 246 of file G4KDTree.hh.

Referenced by Build(), Clear(), GetRoot(), Nearest(), NearestInRange(), Print(), and ~G4KDTree().


The documentation for this class was generated from the following files: