Geant4 9.6.0
Toolkit for the simulation of the passage of particles through matter
Loading...
Searching...
No Matches
Public Member Functions | Protected Member Functions | Protected Attributes | Friends | List of all members
G4KDTree Class Reference

#include <G4KDTree.hh>

Public Member Functions

 G4KDTree (int dim=3)
 
virtual ~G4KDTree ()
 
void Clear ()
 
int GetDim ()
 
void SetDataDestructor (void(*fDestr)(void *))
 
int GetNbNodes ()
 
G4KDNode * GetRoot ()
 
G4KDNode * Insert (const double *pos, void *data)
 
G4KDNode * Insert (const double &x, const double &y, const double &z, void *data)
 
G4KDTreeResultHandle Nearest (const double *pos)
 
G4KDTreeResultHandle Nearest (const double &x, const double &y, const double &z)
 
G4KDTreeResultHandle Nearest (G4KDNode *node)
 
G4KDTreeResultHandle NearestInRange (const double *pos, const double &range)
 
G4KDTreeResultHandle NearestInRange (const double &x, const double &y, const double &z, const double &range)
 
G4KDTreeResultHandle NearestInRange (G4KDNode *node, const double &range)
 

Protected Member Functions

void __Clear_Rec (G4KDNode *node)
 
int __NearestInRange (G4KDNode *node, const double *pos, const double &range_sq, const double &range, G4KDTreeResult &list, int ordered, G4KDNode *source_node=0)
 
void __NearestToPosition (G4KDNode *node, const double *pos, G4KDNode *&result, double *result_dist_sq, struct HyperRect *fRect)
 
void __NearestToNode (G4KDNode *source_node, G4KDNode *node, const double *pos, std::vector< G4KDNode * > &result, double *result_dist_sq, struct HyperRect *fRect, int &nbresult)
 

Protected Attributes

G4KDNode * fRoot
 

Friends

class G4KDNode
 

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 60 of file G4KDTree.hh.

Constructor & Destructor Documentation

◆ G4KDTree()

G4KDTree::G4KDTree ( int  dim = 3)

Definition at line 169 of file G4KDTree.cc.

170{
171 fDim = k;
172 fRoot = 0;
173 fDestr = 0;
174 fRect = 0;
175 fNbNodes = 0;
176}
G4KDTree::fRoot
G4KDNode * fRoot
Definition: G4KDTree.hh:69

◆ ~G4KDTree()

G4KDTree::~G4KDTree ( )
virtual

Definition at line 178 of file G4KDTree.cc.

179{
180 if(fRoot) __Clear_Rec(fRoot);
181 fRoot = 0;
182
183 if (fRect)
184 {
185 delete fRect;
186 fRect = 0;
187 }
188}
G4KDTree::__Clear_Rec
void __Clear_Rec(G4KDNode *node)
Definition: G4KDTree.cc:203

Member Function Documentation

◆ __Clear_Rec()

void G4KDTree::__Clear_Rec ( G4KDNode *  node)
protected

Definition at line 203 of file G4KDTree.cc.

204{
205 if(!node) return;
206
207 if(node->GetLeft()) __Clear_Rec(node->GetLeft());
208 if(node->GetRight()) __Clear_Rec(node->GetRight());
209
210 if(fDestr)
211 {
212 if(node->GetData())
213 {
214 fDestr(node->GetData());
215 node->SetData(0);
216 }
217 }
218 delete node;
219}
G4KDNode::GetLeft
G4KDNode * GetLeft()
Definition: G4KDNode.hh:137
G4KDNode::SetData
void SetData(void *)
Definition: G4KDNode.hh:122
G4KDNode::GetRight
G4KDNode * GetRight()
Definition: G4KDNode.hh:142
G4KDNode::GetData
void * GetData()
Definition: G4KDNode.hh:117

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

◆ __NearestInRange()

int G4KDTree::__NearestInRange ( G4KDNode *  node,
const double *  pos,
const double &  range_sq,
const double &  range,
G4KDTreeResult &  list,
int  ordered,
G4KDNode *  source_node = 0 
)
protected

Definition at line 261 of file G4KDTree.cc.

263{
264 if(!node) return 0;
265
266 double dist_sq(DBL_MAX), dx(DBL_MAX);
267 int ret(-1), added_res(0);
268
269 if(node-> GetData() && node != source_node)
270 {
271 bool do_break = false ;
272 dist_sq = 0;
273 for(int i=0; i<fDim; i++)
274 {
275 dist_sq += sqr(node->GetPosition()[i] - pos[i]);
276 if(dist_sq > range_sq)
277 {
278 do_break = true;
279 break;
280 }
281 }
282 if(!do_break && dist_sq <= range_sq)
283 {
284 list.Insert(dist_sq, node);
285 added_res = 1;
286 }
287 }
288
289 dx = pos[node->GetAxis()] - node->GetPosition()[node->GetAxis()];
290
291 ret = __NearestInRange(dx <= 0.0 ? node->GetLeft() : node->GetRight(), pos, range_sq, range, list, ordered, source_node);
292 if(ret >= 0 && fabs(dx) <= range)
293 {
294 added_res += ret;
295 ret = __NearestInRange(dx <= 0.0 ? node->GetRight() : node->GetLeft(), pos, range_sq, range, list, ordered, source_node);
296 }
297
298 if(ret == -1)
299 {
300 return -1;
301 }
302 added_res += ret;
303
304 return added_res;
305}
GetData
void * GetData(G4KDNode *)
Definition: G4KDNode.cc:45
G4KDNode::GetPosition
const double * GetPosition()
Definition: G4KDNode.hh:127
G4KDNode::GetAxis
int GetAxis()
Definition: G4KDNode.hh:112
G4KDTreeResult::Insert
void Insert(double, G4KDNode *)
Definition: G4KDTreeResult.cc:90
G4KDTree::__NearestInRange
int __NearestInRange(G4KDNode *node, const double *pos, const double &range_sq, const double &range, G4KDTreeResult &list, int ordered, G4KDNode *source_node=0)
Definition: G4KDTree.cc:261
sqr
T sqr(const T &x)
Definition: templates.hh:145
DBL_MAX
#define DBL_MAX
Definition: templates.hh:83

Referenced by __NearestInRange(), and NearestInRange().

◆ __NearestToNode()

void G4KDTree::__NearestToNode ( G4KDNode *  source_node,
G4KDNode *  node,
const double *  pos,
std::vector< G4KDNode * > &  result,
double *  result_dist_sq,
struct HyperRect *  fRect,
int &  nbresult 
)
protected

Definition at line 420 of file G4KDTree.cc.

423{
424 int dir = node->GetAxis();
425 double dummy, dist_sq;
426 G4KDNode *nearer_subtree (0), *farther_subtree (0);
427 double *nearer_hyperrect_coord (0), *farther_hyperrect_coord (0);
428
429 /* Decide whether to go left or right in the tree */
430 dummy = pos[dir] - node->GetPosition()[dir];
431 if (dummy <= 0)
432 {
433 nearer_subtree = node->GetLeft();
434 farther_subtree = node->GetRight();
435 nearer_hyperrect_coord = rect->GetMax() + dir;
436 farther_hyperrect_coord = rect->GetMin() + dir;
437 }
438 else
439 {
440 nearer_subtree = node->GetRight();
441 farther_subtree = node->GetLeft();
442 nearer_hyperrect_coord = rect->GetMin() + dir;
443 farther_hyperrect_coord = rect->GetMax() + dir;
444 }
445
446 if (nearer_subtree)
447 {
448 /* Slice the hyperrect to get the hyperrect of the nearer subtree */
449 dummy = *nearer_hyperrect_coord;
450 *nearer_hyperrect_coord = node->GetPosition()[dir];
451 /* Recurse down into nearer subtree */
452 __NearestToNode(source_node, nearer_subtree, pos, result, result_dist_sq, rect, nbresult);
453 /* Undo the slice */
454 *nearer_hyperrect_coord = dummy;
455 }
456
457 /* Check the distance of the point at the current node, compare it
458 * with our best so far */
459 if(node->GetData() && node != source_node)
460 {
461 dist_sq = 0;
462 bool do_break = false;
463 for(int i=0; i < fDim; i++)
464 {
465 dist_sq += sqr(node->GetPosition()[i] - pos[i]);
466 if(dist_sq > *result_dist_sq)
467 {
468 do_break = true;
469 break ;
470 }
471 }
472 if(!do_break)
473 {
474 if (dist_sq < *result_dist_sq)
475 {
476 result.clear();
477 nbresult = 1 ;
478 result.push_back(node);
479 *result_dist_sq = dist_sq;
480 }
481 else if(dist_sq == *result_dist_sq)
482 {
483 result.push_back(node);
484 nbresult++;
485 }
486 }
487 }
488
489 if (farther_subtree)
490 {
491 /* Get the hyperrect of the farther subtree */
492 dummy = *farther_hyperrect_coord;
493 *farther_hyperrect_coord = node->GetPosition()[dir];
494 /* Check if we have to recurse down by calculating the closest
495 * point of the hyperrect and see if it's closer than our
496 * minimum distance in result_dist_sq. */
497 // if (hyperrect_dist_sq(rect, pos) < *result_dist_sq)
498 if (rect->CompareDistSqr(pos,result_dist_sq))
499 {
500 /* Recurse down into farther subtree */
501 __NearestToNode(source_node, farther_subtree, pos, result, result_dist_sq, rect, nbresult);
502 }
503 /* Undo the slice on the hyperrect */
504 *farther_hyperrect_coord = dummy;
505 }
506}
G4KDTree::__NearestToNode
void __NearestToNode(G4KDNode *source_node, G4KDNode *node, const double *pos, std::vector< G4KDNode * > &result, double *result_dist_sq, struct HyperRect *fRect, int &nbresult)
Definition: G4KDTree.cc:420

Referenced by __NearestToNode(), and Nearest().

◆ __NearestToPosition()

void G4KDTree::__NearestToPosition ( G4KDNode *  node,
const double *  pos,
G4KDNode *&  result,
double *  result_dist_sq,
struct HyperRect *  fRect 
)
protected

Definition at line 308 of file G4KDTree.cc.

310{
311 int dir = node->GetAxis();
312 int i;
313 double dummy(0.), dist_sq(-1.);
314 G4KDNode *nearer_subtree(0), *farther_subtree (0);
315 double *nearer_hyperrect_coord(0),*farther_hyperrect_coord(0);
316
317 /* Decide whether to go left or right in the tree */
318 dummy = pos[dir] - node->GetPosition()[dir];
319 if (dummy <= 0)
320 {
321 nearer_subtree = node->GetLeft();
322 farther_subtree = node->GetRight();
323
324 nearer_hyperrect_coord = rect->GetMax() + dir;
325 farther_hyperrect_coord = rect->GetMin() + dir;
326 }
327 else
328 {
329 nearer_subtree = node->GetRight();
330 farther_subtree = node->GetLeft();
331 nearer_hyperrect_coord = rect->GetMin() + dir;
332 farther_hyperrect_coord = rect->GetMax() + dir;
333 }
334
335 if (nearer_subtree)
336 {
337 /* Slice the hyperrect to get the hyperrect of the nearer subtree */
338 dummy = *nearer_hyperrect_coord;
339 *nearer_hyperrect_coord = node->GetPosition()[dir];
340 /* Recurse down into nearer subtree */
341 __NearestToPosition(nearer_subtree, pos, result, result_dist_sq, rect);
342 /* Undo the slice */
343 *nearer_hyperrect_coord = dummy;
344 }
345
346 /* Check the distance of the point at the current node, compare it
347 * with our best so far */
348 if(node->GetData())
349 {
350 dist_sq = 0;
351 bool do_break = false ;
352 for(i=0; i < fDim; i++)
353 {
354 dist_sq += sqr(node->GetPosition()[i] - pos[i]);
355 if(dist_sq > *result_dist_sq)
356 {
357 do_break = true;
358 break ;
359 }
360 }
361 if (!do_break && dist_sq < *result_dist_sq)
362 {
363 result = node;
364 *result_dist_sq = dist_sq;
365 }
366 }
367
368 if (farther_subtree)
369 {
370 /* Get the hyperrect of the farther subtree */
371 dummy = *farther_hyperrect_coord;
372 *farther_hyperrect_coord = node->GetPosition()[dir];
373 /* Check if we have to recurse down by calculating the closest
374 * point of the hyperrect and see if it's closer than our
375 * minimum distance in result_dist_sq. */
376 if (rect->CompareDistSqr(pos,result_dist_sq))
377 {
378 /* Recurse down into farther subtree */
379 __NearestToPosition(farther_subtree, pos, result, result_dist_sq, rect);
380 }
381 /* Undo the slice on the hyperrect */
382 *farther_hyperrect_coord = dummy;
383 }
384}
G4KDTree::__NearestToPosition
void __NearestToPosition(G4KDNode *node, const double *pos, G4KDNode *&result, double *result_dist_sq, struct HyperRect *fRect)
Definition: G4KDTree.cc:308

Referenced by __NearestToPosition(), and Nearest().

◆ Clear()

void G4KDTree::Clear ( )

Definition at line 190 of file G4KDTree.cc.

191{
192 __Clear_Rec(fRoot);
193 fRoot = 0;
194 fNbNodes = 0;
195
196 if (fRect)
197 {
198 delete fRect;
199 fRect = 0;
200 }
201}

◆ GetDim()

int G4KDTree::GetDim ( )
inline

Definition at line 136 of file G4KDTree.hh.

137{
138 return fDim ;
139}

Referenced by G4KDNode::GetDim(), and G4KDTreeResult::GetItem().

◆ GetNbNodes()

int G4KDTree::GetNbNodes ( )
inline

Definition at line 80 of file G4KDTree.hh.

80{ return fNbNodes; }

◆ GetRoot()

G4KDNode * G4KDTree::GetRoot ( )
inline

Definition at line 81 of file G4KDTree.hh.

81{ return fRoot ; }

◆ Insert() [1/2]

G4KDNode * G4KDTree::Insert ( const double &  x,
const double &  y,
const double &  z,
void *  data 
)

Definition at line 251 of file G4KDTree.cc.

252{
253 double buf[3];
254 buf[0] = x;
255 buf[1] = y;
256 buf[2] = z;
257 return Insert(buf, data);
258}
G4KDTree::Insert
G4KDNode * Insert(const double *pos, void *data)
Definition: G4KDTree.cc:221

◆ Insert() [2/2]

G4KDNode * G4KDTree::Insert ( const double *  pos,
void *  data 
)

Definition at line 221 of file G4KDTree.cc.

222{
223 G4KDNode* node = 0 ;
224 if(!fRoot)
225 {
226 fRoot = new G4KDNode(this,pos,data,0, 0);
227 node = fRoot;
228 fNbNodes = 0;
229 fNbNodes++;
230 }
231 else
232 {
233 if((node=fRoot->Insert(pos, data)))
234 {
235 fNbNodes++;
236 }
237 }
238
239 if (fRect == 0)
240 {
241 fRect = new HyperRect(fDim,pos,pos);
242 }
243 else
244 {
245 fRect->Extend(pos);
246 }
247
248 return node;
249}
G4KDNode::Insert
G4KDNode * Insert(const double *p, void *data)
Definition: G4KDNode.cc:156
G4KDTree::G4KDNode
friend class G4KDNode
Definition: G4KDTree.hh:62
HyperRect::Extend
void Extend(const double *pos)
Definition: G4KDTree.cc:112

Referenced by Insert().

◆ Nearest() [1/3]

G4KDTreeResultHandle G4KDTree::Nearest ( const double &  x,
const double &  y,
const double &  z 
)

Definition at line 552 of file G4KDTree.cc.

553{
554 double pos[3];
555 pos[0] = x;
556 pos[1] = y;
557 pos[2] = z;
558 return Nearest(pos);
559}
G4KDTree::Nearest
G4KDTreeResultHandle Nearest(const double *pos)
Definition: G4KDTree.cc:386

◆ Nearest() [2/3]

G4KDTreeResultHandle G4KDTree::Nearest ( const double *  pos)

Definition at line 386 of file G4KDTree.cc.

387{
388// G4cout << "Nearest(pos)" << G4endl ;
389
390 if (!fRect) return 0;
391
392 G4KDNode *result(0);
393 double dist_sq = DBL_MAX;
394
395 /* Duplicate the bounding hyperrectangle, we will work on the copy */
396 HyperRect *newrect = new HyperRect(*fRect);
397
398 /* Our first guesstimate is the root node */
399 /* Search for the nearest neighbour recursively */
400 __NearestToPosition(fRoot, pos, result, &dist_sq, newrect);
401
402 /* Free the copy of the hyperrect */
403 delete newrect;
404
405 /* Store the result */
406 if (result)
407 {
408 G4KDTreeResultHandle rset = new G4KDTreeResult(this);
409 rset->Insert(dist_sq, result);
410 rset -> Rewind();
411 return rset;
412 }
413 else
414 {
415 return 0;
416 }
417}

Referenced by Nearest().

◆ Nearest() [3/3]

G4KDTreeResultHandle G4KDTree::Nearest ( G4KDNode *  node)

Definition at line 508 of file G4KDTree.cc.

509{
510// G4cout << "Nearest(node)" << G4endl ;
511 if (!fRect)
512 {
513 G4cout << "Tree empty" << G4endl ;
514 return 0;
515 }
516
517 const double* pos = node->GetPosition();
518 std::vector<G4KDNode*> result;
519 double dist_sq = DBL_MAX;
520
521 /* Duplicate the bounding hyperrectangle, we will work on the copy */
522 HyperRect *newrect = new HyperRect(*fRect);
523
524 /* Search for the nearest neighbour recursively */
525 int nbresult = 0 ;
526
527 __NearestToNode(node, fRoot, pos, result, &dist_sq, newrect, nbresult);
528
529 /* Free the copy of the hyperrect */
530 delete newrect;
531
532 /* Store the result */
533 if (!result.empty())
534 {
535 G4KDTreeResultHandle rset(new G4KDTreeResult(this));
536 int j = 0 ;
537 while (j<nbresult)
538 {
539 rset->Insert(dist_sq, result[j]);
540 j++;
541 }
542 rset->Rewind();
543
544 return rset;
545 }
546 else
547 {
548 return 0;
549 }
550}
G4endl
#define G4endl
Definition: G4ios.hh:52
G4cout
G4DLLIMPORT std::ostream G4cout

◆ NearestInRange() [1/3]

G4KDTreeResultHandle G4KDTree::NearestInRange ( const double &  x,
const double &  y,
const double &  z,
const double &  range 
)

Definition at line 578 of file G4KDTree.cc.

582{
583 double buf[3];
584 buf[0] = x;
585 buf[1] = y;
586 buf[2] = z;
587 return NearestInRange(buf, range);
588}
G4KDTree::NearestInRange
G4KDTreeResultHandle NearestInRange(const double *pos, const double &range)
Definition: G4KDTree.cc:561

◆ NearestInRange() [2/3]

G4KDTreeResultHandle G4KDTree::NearestInRange ( const double *  pos,
const double &  range 
)

Definition at line 561 of file G4KDTree.cc.

562{
563 int ret(-1);
564
565 const double range_sq = sqr(range) ;
566
567 G4KDTreeResultHandle rset = new G4KDTreeResult(this);
568 if((ret = __NearestInRange(fRoot, pos, range_sq, range, *(rset()), 0)) == -1)
569 {
570 rset = 0;
571 return rset;
572 }
573 rset->Sort();
574 rset->Rewind();
575 return rset;
576}

Referenced by NearestInRange().

◆ NearestInRange() [3/3]

G4KDTreeResultHandle G4KDTree::NearestInRange ( G4KDNode *  node,
const double &  range 
)

Definition at line 590 of file G4KDTree.cc.

591{
592 if(!node) return 0 ;
593 int ret(-1);
594
595 G4KDTreeResult *rset = new G4KDTreeResult(this);
596
597 const double range_sq = sqr(range) ;
598
599 if((ret = __NearestInRange(fRoot, node->GetPosition(), range_sq, range, *rset, 0, node)) == -1)
600 {
601 delete rset;
602 return 0;
603 }
604 rset->Sort();
605 rset->Rewind();
606 return rset;
607}

◆ SetDataDestructor()

void G4KDTree::SetDataDestructor ( void(*)(void *)  fDestr)
inline

Definition at line 141 of file G4KDTree.hh.

142{
143 fDestr = fct;
144}

Friends And Related Function Documentation

◆ G4KDNode

friend class G4KDNode
friend

Definition at line 62 of file G4KDTree.hh.

Referenced by Insert().

Member Data Documentation

◆ fRoot

G4KDNode* G4KDTree::fRoot
protected

Definition at line 69 of file G4KDTree.hh.

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

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