#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 *	InsertMap (const double &x, const double &y, const double &z, void *data)

G4KDNode *	InsertMap (const double pos, void data)

void	Build ()

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

Constructor & Destructor Documentation

G4KDTree::G4KDTree ( int dim = 3 )

Definition at line 170 of file G4KDTree.cc.

References fRoot.

                          : fKDMap(new G4KDMap(k))
 {
     fDim = k;
     fRoot = 0;
     fDestr = 0;
     fRect = 0;
     fNbNodes = 0;
 }

G4KDTree::~G4KDTree ( )

virtual

Definition at line 179 of file G4KDTree.cc.

References __Clear_Rec(), and fRoot.

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

Member Function Documentation

void G4KDTree::__Clear_Rec ( G4KDNode * node )

protected

Definition at line 206 of file G4KDTree.cc.

References G4KDNode::GetData(), G4KDNode::GetLeft(), G4KDNode::GetRight(), and G4KDNode::SetData().

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

 {
     if(!node) return;
 
     if(node->GetLeft())  __Clear_Rec(node->GetLeft());
     if(node->GetRight()) __Clear_Rec(node->GetRight());
 
     if(fDestr)
     {
         if(node->GetData())
         {
             fDestr(node->GetData());
             node->SetData(0);
         }
     }
     delete node;
 }

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

References DBL_MAX, G4KDNode::GetAxis(), GetData(), G4KDNode::GetLeft(), G4KDNode::GetPosition(), G4KDNode::GetRight(), G4KDTreeResult::Insert(), and sqr().

Referenced by NearestInRange().

 {
     if(!node) return 0;
 
     double dist_sq(DBL_MAX), dx(DBL_MAX);
     int ret(-1), added_res(0);
 
     if(node-> GetData() && node != source_node)
     {
         bool do_break = false ;
         dist_sq = 0;
         for(int i=0; i<fDim; i++)
         {
             dist_sq += sqr(node->GetPosition()[i] - pos[i]);
             if(dist_sq > range_sq)
             {
                 do_break = true;
                 break;
             }
         }
         if(!do_break && dist_sq <= range_sq)
         {
             list.Insert(dist_sq, node);
             added_res = 1;
         }
     }
 
     dx = pos[node->GetAxis()] - node->GetPosition()[node->GetAxis()];
 
     ret = __NearestInRange(dx <= 0.0 ? node->GetLeft() : node->GetRight(), pos, range_sq, range, list, ordered, source_node);
     if(ret >= 0 && fabs(dx) <= range)
     {
         added_res += ret;
         ret = __NearestInRange(dx <= 0.0 ? node->GetRight() : node->GetLeft(), pos, range_sq, range, list, ordered, source_node);
     }
 
     if(ret == -1)
     {
         return -1;
     }
     added_res += ret;
 
     return added_res;
 }

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

References HyperRect::CompareDistSqr(), G4KDNode::GetAxis(), G4KDNode::GetData(), G4KDNode::GetLeft(), HyperRect::GetMax(), HyperRect::GetMin(), G4KDNode::GetPosition(), G4KDNode::GetRight(), and sqr().

Referenced by Nearest().

 {
     int dir = node->GetAxis();
     double dummy, dist_sq;
     G4KDNode *nearer_subtree (0), *farther_subtree (0);
     double *nearer_hyperrect_coord (0), *farther_hyperrect_coord (0);
 
     /* Decide whether to go left or right in the tree */
     dummy = pos[dir] - node->GetPosition()[dir];
     if (dummy <= 0)
     {
         nearer_subtree = node->GetLeft();
         farther_subtree = node->GetRight();
         nearer_hyperrect_coord = rect->GetMax() + dir;
         farther_hyperrect_coord = rect->GetMin() + dir;
     }
     else
     {
         nearer_subtree = node->GetRight();
         farther_subtree = node->GetLeft();
         nearer_hyperrect_coord = rect->GetMin() + dir;
         farther_hyperrect_coord = rect->GetMax() + dir;
     }
 
     if (nearer_subtree)
     {
         /* Slice the hyperrect to get the hyperrect of the nearer subtree */
         dummy = *nearer_hyperrect_coord;
         *nearer_hyperrect_coord = node->GetPosition()[dir];
         /* Recurse down into nearer subtree */
         __NearestToNode(source_node, nearer_subtree, pos, result, result_dist_sq, rect, nbresult);
         /* Undo the slice */
         *nearer_hyperrect_coord = dummy;
     }
 
     /* Check the distance of the point at the current node, compare it
      * with our best so far */
     if(node->GetData() && node != source_node)
     {
         dist_sq = 0;
         bool do_break = false;
         for(int i=0; i < fDim; i++)
         {
             dist_sq += sqr(node->GetPosition()[i] - pos[i]);
             if(dist_sq > *result_dist_sq)
             {
                 do_break = true;
                 break ;
             }
         }
         if(!do_break)
         {
             if (dist_sq < *result_dist_sq)
             {
                 result.clear();
                 nbresult = 1 ;
                 result.push_back(node);
                 *result_dist_sq = dist_sq;
             }
             else if(dist_sq == *result_dist_sq)
             {
                 result.push_back(node);
                 nbresult++;
             }
         }
     }
 
     if (farther_subtree)
     {
         /* Get the hyperrect of the farther subtree */
         dummy = *farther_hyperrect_coord;
         *farther_hyperrect_coord = node->GetPosition()[dir];
         /* Check if we have to recurse down by calculating the closest
          * point of the hyperrect and see if it's closer than our
          * minimum distance in result_dist_sq. */
         //        if (hyperrect_dist_sq(rect, pos) < *result_dist_sq)
         if (rect->CompareDistSqr(pos,result_dist_sq))
         {
             /* Recurse down into farther subtree */
             __NearestToNode(source_node, farther_subtree, pos, result, result_dist_sq, rect, nbresult);
         }
         /* Undo the slice on the hyperrect */
         *farther_hyperrect_coord = dummy;
     }
 }

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

protected

Definition at line 350 of file G4KDTree.cc.

References HyperRect::CompareDistSqr(), G4KDNode::GetAxis(), G4KDNode::GetData(), G4KDNode::GetLeft(), HyperRect::GetMax(), HyperRect::GetMin(), G4KDNode::GetPosition(), G4KDNode::GetRight(), and sqr().

Referenced by Nearest().

 {
     int dir = node->GetAxis();
     int i;
     double dummy(0.), dist_sq(-1.);
     G4KDNode *nearer_subtree(0), *farther_subtree (0);
     double *nearer_hyperrect_coord(0),*farther_hyperrect_coord(0);
 
     /* Decide whether to go left or right in the tree */
     dummy = pos[dir] - node->GetPosition()[dir];
     if (dummy <= 0)
     {
         nearer_subtree = node->GetLeft();
         farther_subtree = node->GetRight();
 
         nearer_hyperrect_coord = rect->GetMax() + dir;
         farther_hyperrect_coord = rect->GetMin() + dir;
     }
     else
     {
         nearer_subtree = node->GetRight();
         farther_subtree = node->GetLeft();
         nearer_hyperrect_coord = rect->GetMin() + dir;
         farther_hyperrect_coord = rect->GetMax() + dir;
     }
 
     if (nearer_subtree)
     {
         /* Slice the hyperrect to get the hyperrect of the nearer subtree */
         dummy = *nearer_hyperrect_coord;
         *nearer_hyperrect_coord = node->GetPosition()[dir];
         /* Recurse down into nearer subtree */
         __NearestToPosition(nearer_subtree, pos, result, result_dist_sq, rect);
         /* Undo the slice */
         *nearer_hyperrect_coord = dummy;
     }
 
     /* Check the distance of the point at the current node, compare it
      * with our best so far */
     if(node->GetData())
     {
         dist_sq = 0;
         bool do_break = false ;
         for(i=0; i < fDim; i++)
         {
             dist_sq += sqr(node->GetPosition()[i] - pos[i]);
             if(dist_sq > *result_dist_sq)
             {
                 do_break = true;
                 break ;
             }
         }
         if (!do_break && dist_sq < *result_dist_sq)
         {
             result = node;
             *result_dist_sq = dist_sq;
         }
     }
 
     if (farther_subtree)
     {
         /* Get the hyperrect of the farther subtree */
         dummy = *farther_hyperrect_coord;
         *farther_hyperrect_coord = node->GetPosition()[dir];
         /* Check if we have to recurse down by calculating the closest
          * point of the hyperrect and see if it's closer than our
          * minimum distance in result_dist_sq. */
         if (rect->CompareDistSqr(pos,result_dist_sq))
         {
             /* Recurse down into farther subtree */
             __NearestToPosition(farther_subtree, pos, result, result_dist_sq, rect);
         }
         /* Undo the slice on the hyperrect */
         *farther_hyperrect_coord = dummy;
     }
 }

void G4KDTree::Build ( )

Definition at line 241 of file G4KDTree.cc.

References HyperRect::Extend(), fRoot, G4KDNode::GetPosition(), G4KDMap::GetSize(), G4KDNode::Insert(), n, and G4KDMap::PopOutMiddle().

 {
     int Nnodes = fKDMap->GetSize();
 
     G4KDNode* root = fKDMap->PopOutMiddle(0);
 
     fRoot = root;
     fRect = new HyperRect(fDim,fRoot->GetPosition(),fRoot->GetPosition());
 
     Nnodes--;
 
     for(int n = 0 ; n < Nnodes ; n = n+fDim)
     {
         for(int dim = 0 ; dim < fDim ; dim ++)
         {
             G4KDNode* node = fKDMap->PopOutMiddle(dim);
             fRoot->Insert(node);
             fRect->Extend(node->GetPosition());
         }
     }
 }

void G4KDTree::Clear ( )

Definition at line 193 of file G4KDTree.cc.

References __Clear_Rec(), and fRoot.

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

int G4KDTree::GetDim ( )

inline

Definition at line 143 of file G4KDTree.hh.

References HyperRect::fDim.

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

 {
     return fDim ;
 }

int G4KDTree::GetNbNodes ( )

inline

Definition at line 83 of file G4KDTree.hh.

83 { return fNbNodes; }

G4KDNode* G4KDTree::GetRoot ( )

inline

Definition at line 84 of file G4KDTree.hh.

References fRoot.

84 { return fRoot ; }

G4KDTree::fRoot

G4KDNode * fRoot

Definition: G4KDTree.hh:72

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

Definition at line 263 of file G4KDTree.cc.

References HyperRect::Extend(), fRoot, G4KDNode, and G4KDNode::Insert().

Referenced by Insert().

 {
     G4KDNode* node = 0 ;
     if(!fRoot)
     {
         fRoot =  new G4KDNode(this,pos,data,0, 0);
         node = fRoot;
         fNbNodes = 0;
         fNbNodes++;
     }
     else
     {
         if((node=fRoot->Insert(pos, data)))
         {
             fNbNodes++;
         }
     }
 
     if (fRect == 0)
     {
         fRect = new HyperRect(fDim,pos,pos);
     }
     else
     {
         fRect->Extend(pos);
     }
 
     return node;
 }

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

Definition at line 293 of file G4KDTree.cc.

References Insert(), test::x, and z.

 {
     double buf[3];
     buf[0] = x;
     buf[1] = y;
     buf[2] = z;
     return Insert(buf, data);
 }

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

Definition at line 224 of file G4KDTree.cc.

References test::x, and z.

 {
     double buf[3];
     buf[0] = x;
     buf[1] = y;
     buf[2] = z;
     return InsertMap(buf, data);
 }

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

Definition at line 233 of file G4KDTree.cc.

References G4KDNode, and G4KDMap::Insert().

 {
     G4KDNode* node = new G4KDNode(this,pos,data,0,-2) ;
     // -2 = valeur intentionnellement absurde
     fKDMap->Insert(node);
     return node;
 }

G4KDTreeResultHandle G4KDTree::Nearest ( const double * pos )

Definition at line 428 of file G4KDTree.cc.

References __NearestToPosition(), DBL_MAX, and fRoot.

Referenced by Nearest().

 {
     //    G4cout << "Nearest(pos)" << G4endl ;
 
     if (!fRect) return 0;
 
     G4KDNode *result(0);
     double dist_sq = DBL_MAX;
 
     /* Duplicate the bounding hyperrectangle, we will work on the copy */
     HyperRect *newrect = new HyperRect(*fRect);
 
     /* Our first guesstimate is the root node */
     /* Search for the nearest neighbour recursively */
     __NearestToPosition(fRoot, pos, result, &dist_sq, newrect);
 
     /* Free the copy of the hyperrect */
     delete newrect;
 
     /* Store the result */
     if (result)
     {
         G4KDTreeResultHandle rset = new G4KDTreeResult(this);
         rset->Insert(dist_sq, result);
         rset -> Rewind();
         return rset;
     }
     else
     {
         return 0;
     }
 }

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

Definition at line 594 of file G4KDTree.cc.

References Nearest(), test::x, and z.

 {
     double pos[3];
     pos[0] = x;
     pos[1] = y;
     pos[2] = z;
     return Nearest(pos);
 }

G4KDTreeResultHandle G4KDTree::Nearest ( G4KDNode * node )

Definition at line 550 of file G4KDTree.cc.

References __NearestToNode(), DBL_MAX, fRoot, G4cout, G4endl, and G4KDNode::GetPosition().

 {
     //    G4cout << "Nearest(node)" << G4endl ;
     if (!fRect)
     {
         G4cout << "Tree empty" << G4endl ;
         return 0;
     }
 
     const double* pos = node->GetPosition();
     std::vector<G4KDNode*> result;
     double dist_sq = DBL_MAX;
 
     /* Duplicate the bounding hyperrectangle, we will work on the copy */
     HyperRect *newrect = new HyperRect(*fRect);
 
     /* Search for the nearest neighbour recursively */
     int nbresult = 0 ;
 
     __NearestToNode(node, fRoot, pos, result, &dist_sq, newrect, nbresult);
 
     /* Free the copy of the hyperrect */
     delete newrect;
 
     /* Store the result */
     if (!result.empty())
     {
         G4KDTreeResultHandle rset(new G4KDTreeResult(this));
         int j = 0 ;
         while (j<nbresult)
         {
             rset->Insert(dist_sq, result[j]);
             j++;
         }
         rset->Rewind();
 
         return rset;
     }
     else
     {
         return 0;
     }
 }

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

Definition at line 603 of file G4KDTree.cc.

References __NearestInRange(), fRoot, and sqr().

Referenced by NearestInRange().

 {
     int ret(-1);
 
     const double range_sq = sqr(range) ;
 
     G4KDTreeResultHandle rset = new G4KDTreeResult(this);
     if((ret = __NearestInRange(fRoot, pos, range_sq, range, *(rset()), 0)) == -1)
     {
         rset = 0;
         return rset;
     }
     rset->Sort();
     rset->Rewind();
     return rset;
 }

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

Definition at line 620 of file G4KDTree.cc.

References NearestInRange(), test::x, and z.

 {
     double buf[3];
     buf[0] = x;
     buf[1] = y;
     buf[2] = z;
     return NearestInRange(buf, range);
 }

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

Definition at line 632 of file G4KDTree.cc.

References __NearestInRange(), fRoot, G4KDNode::GetPosition(), and sqr().

 {
     if(!node) return 0 ;
     int ret(-1);
 
     G4KDTreeResult *rset = new G4KDTreeResult(this);
 
     const double range_sq = sqr(range) ;
 
     if((ret = __NearestInRange(fRoot, node->GetPosition(), range_sq, range, *rset, 0, node)) == -1)
     {
         delete rset;
         return 0;
     }
     rset->Sort();
     rset->Rewind();
     return rset;
 }

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

inline

Definition at line 148 of file G4KDTree.hh.

 {
     fDestr = fct;
 }

Friends And Related Function Documentation

friend class G4KDNode

friend

Definition at line 64 of file G4KDTree.hh.

Referenced by Insert(), and InsertMap().

Field Documentation

G4KDNode* G4KDTree::fRoot

protected

Definition at line 72 of file G4KDTree.hh.

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

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

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Field Documentation