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

(

int

dim = 3

)

Definition at line 169 of file G4KDTree.cc.

References fRoot.

{
    fDim = k;
    fRoot = 0;
    fDestr = 0;
    fRect = 0;
    fNbNodes = 0;
}

G4KDTree::~G4KDTree

(

)

[virtual]

Definition at line 178 of file G4KDTree.cc.

References __Clear_Rec(), and fRoot.

{
    if(fRoot) __Clear_Rec(fRoot);
    fRoot = 0;

    if (fRect)
    {
        delete fRect;
        fRect = 0;
    }
}

---

Member Function Documentation

void G4KDTree::__Clear_Rec

(

G4KDNode *

node

)

[protected]

Definition at line 203 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 261 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 420 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 308 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::Clear

(

)

Definition at line 190 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 136 of file G4KDTree.hh.

References HyperRect::fDim.

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

{
    return fDim ;
}

int G4KDTree::GetNbNodes

(

)

[inline]

Definition at line 80 of file G4KDTree.hh.

{ return fNbNodes;  }

G4KDNode* G4KDTree::GetRoot

(

)

[inline]

Definition at line 81 of file G4KDTree.hh.

References fRoot.

{ return fRoot ;    }

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

Definition at line 251 of file G4KDTree.cc.

References Insert().

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

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

Definition at line 221 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;
}

G4KDTreeResultHandle G4KDTree::Nearest

(

G4KDNode *

node

)

Definition at line 508 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::Nearest	(	const double &	x,
		const double &	y,
		const double &	z
	)

Definition at line 552 of file G4KDTree.cc.

References Nearest().

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

G4KDTreeResultHandle G4KDTree::Nearest

(

const double *

pos

)

Definition at line 386 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::NearestInRange	(	G4KDNode *	node,
		const double &	range
	)

Definition at line 590 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;
}

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

Definition at line 578 of file G4KDTree.cc.

References NearestInRange().

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

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

Definition at line 561 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;
}

void G4KDTree::SetDataDestructor

(

void(*)(void *)

fDestr

)

[inline]

Definition at line 141 of file G4KDTree.hh.

{
    fDestr = fct;
}

---

Friends And Related Function Documentation

friend class G4KDNode [friend]

Definition at line 62 of file G4KDTree.hh.

Referenced by Insert().

---

Field Documentation

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:

• G4KDTree.hh
• G4KDTree.cc

---