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_Base *	GetRoot ()
template<typename PointT >
G4KDNode_Base *	InsertMap (PointT *pos)
template<typename PointT >
G4KDNode_Base *	Insert (PointT *pos)
template<typename PointT >
G4KDNode_Base *	Insert (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
HyperRect *	fRect = nullptr
G4KDNode_Base *	fRoot = nullptr
std::size_t	fDim
G4int	fNbNodes = 0
G4int	fNbActiveNodes = 0
G4KDMap *	fKDMap

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.

  : fDim(k)
  ,fKDMap(new G4KDMap(k))
{}

~G4KDTree()

G4KDTree::~G4KDTree

(

)

Definition at line 58 of file G4KDTree.cc.

{
  if(fRoot != nullptr){
    __Clear_Rec(fRoot);
    fRoot = nullptr;
  }
 
  if(fRect != nullptr){
    delete fRect;
    fRect = nullptr;
  }
 
  if(fKDMap != nullptr){
    delete fKDMap;
    fKDMap = nullptr;
  }
}

Member Function Documentation

__Clear_Rec()

void G4KDTree::__Clear_Rec ( G4KDNode_Base * node )

protected

Definition at line 109 of file G4KDTree.cc.

{
  if(node == nullptr)
  {
    return;
  }
 
  if(node->GetLeft() != nullptr)
  {
    __Clear_Rec(node->GetLeft());
  }
  if(node->GetRight() != nullptr)
  {
    __Clear_Rec(node->GetRight());
  }
 
  delete node;
}

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

__InsertMap()

void G4KDTree::__InsertMap ( G4KDNode_Base * node )

protected

Definition at line 128 of file G4KDTree.cc.

{ fKDMap->Insert(node); }

__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.

{
  size_t Nnodes = fKDMap->GetSize();
 
  G4cout << "********************" << G4endl;
  G4cout << "template<typename PointT> G4KDTree<PointT>::Build" << G4endl;
  G4cout << "Map size = " << Nnodes << G4endl;
 
  G4KDNode_Base* root = fKDMap->PopOutMiddle(0);
 
  if(root == nullptr)
  {
    return;
  }
 
  fRoot = root;
  fNbActiveNodes++;
  fRect = new HyperRect(fDim);
  fRect->SetMinMax(*fRoot, *fRoot);
 
  Nnodes--;
 
  G4KDNode_Base* parent = fRoot;
 
  for(size_t n = 0; n < Nnodes; n += fDim)
  {
    for(size_t dim = 0; dim < fDim; dim++)
    {
      G4KDNode_Base* node = fKDMap->PopOutMiddle(dim);
      if(node != nullptr)
      {
        parent->Insert(node);
        fNbActiveNodes++;
        fRect->Extend(*node);
        parent = node;
      }
    }
  }
}

Clear()

void G4KDTree::Clear

(

)

Definition at line 96 of file G4KDTree.cc.

{
  __Clear_Rec(fRoot);
  fRoot    = nullptr;
  fNbNodes = 0;
 
  if(fRect != nullptr)
  {
    delete fRect;
    fRect = nullptr;
  }
}

Referenced by NoticeNodeDeactivation().

fgAllocator()

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

staticprotected

Definition at line 45 of file G4KDTree.cc.

{
  G4ThreadLocalStatic G4Allocator<G4KDTree>* _instance = nullptr;
  return _instance;
}

GetDim()

std::size_t G4KDTree::GetDim ( ) const

inline

Definition at line 90 of file G4KDTree.hh.

{ 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.

{ return fNbNodes; }

GetRoot()

G4KDNode_Base * G4KDTree::GetRoot ( )

inline

Definition at line 92 of file G4KDTree.hh.

{ 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.

{
  if(fRect == nullptr)
  {
    return nullptr;
  }
 
  std::vector<G4KDNode_Base*> result;
  G4double dist_sq = DBL_MAX;
 
  /* Duplicate the bounding hyperrectangle, we will work on the copy */
  auto newrect = new HyperRect(*fRect);
 
  /* Search for the nearest neighbour recursively */
  G4int nbresult = 0;
 
  __NearestToNode(node, fRoot, *node, result, &dist_sq, newrect, nbresult);
 
  /* Free the copy of the hyperrect */
  delete newrect;
 
  /* Store the result */
  if(!result.empty())
  {
    G4KDTreeResultHandle rset(new G4KDTreeResult(this));
    G4int j = 0;
    while(j < nbresult)
    {
      rset->Insert(dist_sq, result[j]);
      j++;
    }
    rset->Rewind();
 
    return rset;
  }
  
  return nullptr;
}

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 209 of file G4KDTree.cc.

{
  if(node == nullptr)
  {
    return nullptr;
  }
  G4int ret(-1);
 
  auto* rset = new G4KDTreeResult(this);
 
  const G4double range_sq = sqr(range);
 
  if((ret = __NearestInRange(fRoot, *node, range_sq, range, *rset, 0, node)) ==
     -1)
  {
    delete rset;
    return nullptr;
  }
  rset->Sort();
  rset->Rewind();
  return rset;
}

NoticeNodeDeactivation()

void G4KDTree::NoticeNodeDeactivation ( )

inline

Definition at line 81 of file G4KDTree.hh.

  {
    fNbActiveNodes--;
    if(fNbActiveNodes <= 0)
    {
      Clear();
    }
  }

Referenced by G4KDNode_Base::InactiveNode().

operator delete()

void G4KDTree::operator delete

(

void *

aNode

)

Definition at line 84 of file G4KDTree.cc.

{
  fgAllocator()->FreeSingle((G4KDTree*) aNode);
}

operator new()

void * G4KDTree::operator new

(

std::size_t

)

Definition at line 76 of file G4KDTree.cc.

{
  if(fgAllocator() == nullptr){
    fgAllocator() = new G4Allocator<G4KDTree>;
  }
  return (void*) fgAllocator()->MallocSingle();
}

Print()

void G4KDTree::Print

(

std::ostream &

out = G4cout

)

const

Definition at line 89 of file G4KDTree.cc.

{
  if(fRoot != nullptr){
    fRoot->Print(out);
  }
}

Friends And Related Symbol 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:

• G4KDTree.hh
• G4KDTree.cc