voronoi2d::BSTNode Class Reference

BSTNode class definiton specifically for use in constructing Voronoi diagrams. We are trying to follow the prescription described in "Computational Geometry" by Mark de Berg, et al. More...

#include "BeachLine.h"

Public Member Functions
	BSTNode ()
	Constructor. More...
	BSTNode (IEvent *event)
	BSTNode (IEvent *, BSTNode *, BSTNode *, BSTNode *)
	~BSTNode ()
	Virtual Destructor. More...
int	getDepth () const
	recover the data members More...
IEvent *	getEvent () const
BSTNode *	getParent () const
BSTNode *	getLeftChild () const
BSTNode *	getRightChild () const
BSTNode *	getPredecessor () const
BSTNode *	getSuccessor () const
BSTNode *	getAssociated () const
dcel2d::HalfEdge *	getHalfEdge () const
dcel2d::Face *	getFace () const
void	setParent (BSTNode *node)
	Allow setting of the points. More...
void	setLeftChild (BSTNode *node)
void	setRightChild (BSTNode *node)
void	setPredecessor (BSTNode *node)
void	setSuccessor (BSTNode *node)
void	setAssociated (BSTNode *node)
void	setHalfEdge (dcel2d::HalfEdge *half)
void	setFace (dcel2d::Face *face)
void	setDepth (int depth)
void	setDepth ()
bool	operator< (const BSTNode &) const
	Provide override definition for ordering. More...

Private Attributes
int	m_depth
IEvent *	m_event
BSTNode *	m_parent
BSTNode *	m_leftChild
BSTNode *	m_rightChild
BSTNode *	m_predecessor
BSTNode *	m_successor
BSTNode *	m_associated
dcel2d::HalfEdge *	m_halfEdge
dcel2d::Face *	m_face

Detailed Description

BSTNode class definiton specifically for use in constructing Voronoi diagrams. We are trying to follow the prescription described in "Computational Geometry" by Mark de Berg, et al.

Note that in this implementation the internal nodes of the tree will describe the breakpoints in the beach line and the leaves of the tree will describe the arcs (site points).

Definition at line 32 of file BeachLine.h.

Constructor & Destructor Documentation

voronoi2d::BSTNode::BSTNode ( )

inline

Constructor.

Definition at line 38 of file BeachLine.h.

Referenced by BSTNode(), and voronoi2d::BeachLine::insertNewLeaf().

              :
        m_depth(0),
        m_event(NULL),
        m_parent(NULL),
        m_leftChild(NULL),
        m_rightChild(NULL),
        m_predecessor(NULL),
        m_successor(NULL),
        m_associated(NULL),
        m_halfEdge(NULL),
        m_face(NULL)
    {}

voronoi2d::BSTNode::BSTNode ( IEvent *  event )

inline

Definition at line 51 of file BeachLine.h.

References BSTNode(), m_event, and voronoi2d::IEvent::setBSTNode().

                           :
        m_depth(0),
        m_event(event),
        m_parent(NULL),
        m_leftChild(NULL),
        m_rightChild(NULL),
        m_predecessor(NULL),
        m_successor(NULL),
        m_associated(NULL),
        m_halfEdge(NULL),
        m_face(NULL)
    {
        if (m_event) m_event->setBSTNode(this);
    }

voronoi2d::BSTNode::BSTNode	(	IEvent *	event,
		BSTNode *	parent,
		BSTNode *	leftChild,
		BSTNode *	rightChild
	)

Definition at line 24 of file BeachLine.cxx.

References m_associated, m_depth, m_event, m_leftChild, m_parent, m_predecessor, m_rightChild, m_successor, voronoi2d::IEvent::setBSTNode(), and setDepth().

{
    m_depth       = 0;
    m_event       = event;
    m_parent      = parent;
    m_leftChild   = leftChild;
    m_rightChild  = rightChild;
    m_predecessor = NULL;
    m_successor   = NULL;
    m_associated  = NULL;
    
    m_event->setBSTNode(this);
    
    // Reset depth
    setDepth();
}

voronoi2d::BSTNode::~BSTNode ( )

inline

Virtual Destructor.

Definition at line 71 of file BeachLine.h.

{}

Member Function Documentation

BSTNode* voronoi2d::BSTNode::getAssociated ( ) const

inline

Definition at line 83 of file BeachLine.h.

References m_associated.

Referenced by voronoi2d::BeachLine::checkBeachLine(), voronoi2d::VoronoiDiagram::handleCircleEvents(), voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::VoronoiDiagram::makeLeftCircleEvent(), voronoi2d::VoronoiDiagram::makeRightCircleEvent(), voronoi2d::BeachLine::removeLeaf(), and voronoi2d::VoronoiDiagram::terminateInfiniteEdges().

{return m_associated;}

int voronoi2d::BSTNode::getDepth ( ) const

inline

recover the data members

Definition at line 76 of file BeachLine.h.

References m_depth.

Referenced by voronoi2d::BeachLine::rebalance(), and setDepth().

{return m_depth;}

IEvent* voronoi2d::BSTNode::getEvent ( ) const

inline

Definition at line 77 of file BeachLine.h.

References m_event.

Referenced by voronoi2d::BeachLine::checkBeachLine(), voronoi2d::BeachLine::findBestLeaf(), voronoi2d::VoronoiDiagram::getConvexHull(), voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::VoronoiDiagram::makeCircleEvent(), voronoi2d::VoronoiDiagram::makeLeftCircleEvent(), voronoi2d::VoronoiDiagram::makeRightCircleEvent(), voronoi2d::BeachLine::removeLeaf(), and voronoi2d::VoronoiDiagram::terminateInfiniteEdges().

{return m_event;}

dcel2d::Face* voronoi2d::BSTNode::getFace ( ) const

inline

Definition at line 86 of file BeachLine.h.

References m_face.

Referenced by voronoi2d::VoronoiDiagram::getConvexHull(), voronoi2d::VoronoiDiagram::handleCircleEvents(), voronoi2d::VoronoiDiagram::handleSiteEvents(), and voronoi2d::VoronoiDiagram::terminateInfiniteEdges().

{return m_face;}

dcel2d::HalfEdge* voronoi2d::BSTNode::getHalfEdge ( ) const

inline

Definition at line 85 of file BeachLine.h.

References m_halfEdge.

Referenced by voronoi2d::VoronoiDiagram::handleCircleEvents(), and voronoi2d::VoronoiDiagram::terminateInfiniteEdges().

{return m_halfEdge;}

BSTNode* voronoi2d::BSTNode::getLeftChild ( ) const

inline

Definition at line 79 of file BeachLine.h.

References m_leftChild.

Referenced by voronoi2d::BeachLine::checkBeachLine(), voronoi2d::BeachLine::countLeaves(), voronoi2d::BeachLine::countNodes(), voronoi2d::BeachLine::findBestLeaf(), voronoi2d::VoronoiDiagram::getConvexHull(), voronoi2d::BeachLine::getTreeDepth(), voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::BeachLine::rebalance(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::BeachLine::rotateWithLeftChild(), voronoi2d::BeachLine::rotateWithRightChild(), voronoi2d::VoronoiDiagram::terminateInfiniteEdges(), voronoi2d::BeachLine::traverseBeach(), voronoi2d::BeachLine::traverseBeachLeft(), and voronoi2d::BeachLine::traverseBeachRight().

{return m_leftChild;}

BSTNode* voronoi2d::BSTNode::getParent ( ) const

inline

Definition at line 78 of file BeachLine.h.

References m_parent.

Referenced by voronoi2d::BeachLine::checkBeachLine(), voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::BeachLine::rebalance(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::BeachLine::rotateWithLeftChild(), and voronoi2d::BeachLine::rotateWithRightChild().

{return m_parent;}

BSTNode* voronoi2d::BSTNode::getPredecessor ( ) const

inline

Definition at line 81 of file BeachLine.h.

References m_predecessor.

Referenced by voronoi2d::BeachLine::checkBeachLine(), voronoi2d::BeachLine::findBestLeaf(), voronoi2d::VoronoiDiagram::getConvexHull(), voronoi2d::VoronoiDiagram::handleCircleEvents(), voronoi2d::VoronoiDiagram::handleSiteEvents(), voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::VoronoiDiagram::makeLeftCircleEvent(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::VoronoiDiagram::terminateInfiniteEdges(), voronoi2d::BeachLine::traverseBeach(), and voronoi2d::BeachLine::traverseBeachLeft().

{return m_predecessor;}

BSTNode* voronoi2d::BSTNode::getRightChild ( ) const

inline

Definition at line 80 of file BeachLine.h.

References m_rightChild.

Referenced by voronoi2d::BeachLine::checkBeachLine(), voronoi2d::BeachLine::countLeaves(), voronoi2d::BeachLine::countNodes(), voronoi2d::BeachLine::findBestLeaf(), voronoi2d::VoronoiDiagram::getConvexHull(), voronoi2d::BeachLine::getTreeDepth(), voronoi2d::BeachLine::rebalance(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::BeachLine::rotateWithLeftChild(), voronoi2d::BeachLine::rotateWithRightChild(), voronoi2d::VoronoiDiagram::terminateInfiniteEdges(), voronoi2d::BeachLine::traverseBeach(), voronoi2d::BeachLine::traverseBeachLeft(), and voronoi2d::BeachLine::traverseBeachRight().

{return m_rightChild;}

BSTNode* voronoi2d::BSTNode::getSuccessor ( ) const

inline

Definition at line 82 of file BeachLine.h.

References m_successor.

Referenced by voronoi2d::BeachLine::checkBeachLine(), voronoi2d::BeachLine::findBestLeaf(), voronoi2d::VoronoiDiagram::handleCircleEvents(), voronoi2d::VoronoiDiagram::handleSiteEvents(), voronoi2d::VoronoiDiagram::makeRightCircleEvent(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::VoronoiDiagram::terminateInfiniteEdges(), voronoi2d::BeachLine::traverseBeach(), and voronoi2d::BeachLine::traverseBeachRight().

{return m_successor;}

bool voronoi2d::BSTNode::operator<

(

const BSTNode &

)

const

Provide override definition for ordering.

Referenced by setDepth().

void voronoi2d::BSTNode::setAssociated ( BSTNode *  node )

inline

Definition at line 96 of file BeachLine.h.

References m_associated.

Referenced by voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::VoronoiDiagram::makeLeftCircleEvent(), voronoi2d::VoronoiDiagram::makeRightCircleEvent(), and voronoi2d::BeachLine::removeLeaf().

{m_associated  = node;}

void voronoi2d::BSTNode::setDepth ( int  depth )

inline

Definition at line 101 of file BeachLine.h.

References m_depth, operator<(), and setDepth().

Referenced by voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::BeachLine::rotateWithLeftChild(), voronoi2d::BeachLine::rotateWithRightChild(), and setDepth().

{m_depth       = depth;}

void voronoi2d::BSTNode::setDepth

(

)

Definition at line 41 of file BeachLine.cxx.

References getDepth(), m_depth, m_leftChild, m_parent, m_rightChild, max, and setDepth().

Referenced by BSTNode(), and setDepth().

{
    if (m_leftChild && m_rightChild)
    {
        int maxDepth = std::max(m_leftChild->getDepth(),m_rightChild->getDepth());
        
        m_depth = maxDepth + 1;
    }
    else m_depth = 0;

    // If we change depth at this level then need to ripple it up through the tree
    if (m_parent) m_parent->setDepth();
    
    return;
}

void voronoi2d::BSTNode::setFace ( dcel2d::Face *  face )

inline

Definition at line 99 of file BeachLine.h.

References m_face.

Referenced by voronoi2d::VoronoiDiagram::handleSiteEvents(), and voronoi2d::BeachLine::removeLeaf().

{m_face        = face;}

void voronoi2d::BSTNode::setHalfEdge ( dcel2d::HalfEdge *  half )

inline

Definition at line 98 of file BeachLine.h.

References m_halfEdge.

Referenced by voronoi2d::VoronoiDiagram::handleCircleEvents(), voronoi2d::VoronoiDiagram::handleSiteEvents(), and voronoi2d::BeachLine::removeLeaf().

{m_halfEdge    = half;}

void voronoi2d::BSTNode::setLeftChild ( BSTNode *  node )

inline

Definition at line 92 of file BeachLine.h.

References m_leftChild.

Referenced by voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::BeachLine::rotateWithLeftChild(), and voronoi2d::BeachLine::rotateWithRightChild().

{m_leftChild   = node;}

void voronoi2d::BSTNode::setParent ( BSTNode *  node )

inline

Allow setting of the points.

Definition at line 91 of file BeachLine.h.

References m_parent.

Referenced by voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::BeachLine::rotateWithLeftChild(), and voronoi2d::BeachLine::rotateWithRightChild().

{m_parent      = node;}

void voronoi2d::BSTNode::setPredecessor ( BSTNode *  node )

inline

Definition at line 94 of file BeachLine.h.

References m_predecessor.

Referenced by voronoi2d::BeachLine::insertNewLeaf(), and voronoi2d::BeachLine::removeLeaf().

{m_predecessor = node;}

void voronoi2d::BSTNode::setRightChild ( BSTNode *  node )

inline

Definition at line 93 of file BeachLine.h.

References m_rightChild.

Referenced by voronoi2d::BeachLine::insertNewLeaf(), voronoi2d::BeachLine::removeLeaf(), voronoi2d::BeachLine::rotateWithLeftChild(), and voronoi2d::BeachLine::rotateWithRightChild().

{m_rightChild  = node;}

void voronoi2d::BSTNode::setSuccessor ( BSTNode *  node )

inline

Definition at line 95 of file BeachLine.h.

References m_successor.

Referenced by voronoi2d::BeachLine::insertNewLeaf(), and voronoi2d::BeachLine::removeLeaf().

{m_successor   = node;}

Member Data Documentation

BSTNode* voronoi2d::BSTNode::m_associated

private

Definition at line 117 of file BeachLine.h.

Referenced by BSTNode(), getAssociated(), and setAssociated().

int voronoi2d::BSTNode::m_depth

private

Definition at line 110 of file BeachLine.h.

Referenced by BSTNode(), getDepth(), and setDepth().

IEvent* voronoi2d::BSTNode::m_event

private

Definition at line 111 of file BeachLine.h.

Referenced by BSTNode(), and getEvent().

dcel2d::Face* voronoi2d::BSTNode::m_face

private

Definition at line 119 of file BeachLine.h.

Referenced by getFace(), and setFace().

dcel2d::HalfEdge* voronoi2d::BSTNode::m_halfEdge

private

Definition at line 118 of file BeachLine.h.

Referenced by getHalfEdge(), and setHalfEdge().

BSTNode* voronoi2d::BSTNode::m_leftChild

private

Definition at line 113 of file BeachLine.h.

Referenced by BSTNode(), getLeftChild(), setDepth(), and setLeftChild().

BSTNode* voronoi2d::BSTNode::m_parent

private

Definition at line 112 of file BeachLine.h.

Referenced by BSTNode(), getParent(), setDepth(), and setParent().

BSTNode* voronoi2d::BSTNode::m_predecessor

private

Definition at line 115 of file BeachLine.h.

Referenced by BSTNode(), getPredecessor(), and setPredecessor().

BSTNode* voronoi2d::BSTNode::m_rightChild

private

Definition at line 114 of file BeachLine.h.

Referenced by BSTNode(), getRightChild(), setDepth(), and setRightChild().

BSTNode* voronoi2d::BSTNode::m_successor

private

Definition at line 116 of file BeachLine.h.

Referenced by BSTNode(), getSuccessor(), and setSuccessor().

---

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

• /cvmfs/larsoft.opensciencegrid.org/products/larreco/v07_10_02/source/larreco/RecoAlg/Cluster3DAlgs/Voronoi/BeachLine.h
• /cvmfs/larsoft.opensciencegrid.org/products/larreco/v07_10_02/source/larreco/RecoAlg/Cluster3DAlgs/Voronoi/BeachLine.cxx