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 *)
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 34 of file BeachLine.h.

Constructor & Destructor Documentation

voronoi2d::BSTNode::BSTNode ( )

inline

Constructor.

Definition at line 39 of file BeachLine.h.

Referenced by 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 52 of file BeachLine.h.

      : 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 22 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();
  }

Member Function Documentation

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

inline

Definition at line 79 of file BeachLine.h.

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 72 of file BeachLine.h.

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

{ return m_depth; }

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

inline

Definition at line 73 of file BeachLine.h.

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 82 of file BeachLine.h.

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 81 of file BeachLine.h.

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

{ return m_halfEdge; }

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

inline

Definition at line 75 of file BeachLine.h.

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 74 of file BeachLine.h.

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 77 of file BeachLine.h.

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 76 of file BeachLine.h.

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 78 of file BeachLine.h.

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.

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

inline

Definition at line 92 of file BeachLine.h.

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 97 of file BeachLine.h.

References geo::operator<().

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 39 of file BeachLine.cxx.

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

Referenced by BSTNode().

  {
    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 95 of file BeachLine.h.

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

{ m_face = face; }

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

inline

Definition at line 94 of file BeachLine.h.

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 88 of file BeachLine.h.

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 87 of file BeachLine.h.

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 90 of file BeachLine.h.

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

{ m_predecessor = node; }

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

inline

Definition at line 89 of file BeachLine.h.

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 91 of file BeachLine.h.

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

{ m_successor = node; }

Member Data Documentation

BSTNode* voronoi2d::BSTNode::m_associated

private

Definition at line 113 of file BeachLine.h.

Referenced by BSTNode().

int voronoi2d::BSTNode::m_depth

private

Definition at line 106 of file BeachLine.h.

Referenced by BSTNode(), and setDepth().

IEvent* voronoi2d::BSTNode::m_event

private

Definition at line 107 of file BeachLine.h.

Referenced by BSTNode().

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

private

Definition at line 115 of file BeachLine.h.

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

private

Definition at line 114 of file BeachLine.h.

BSTNode* voronoi2d::BSTNode::m_leftChild

private

Definition at line 109 of file BeachLine.h.

Referenced by BSTNode(), and setDepth().

BSTNode* voronoi2d::BSTNode::m_parent

private

Definition at line 108 of file BeachLine.h.

Referenced by BSTNode(), and setDepth().

BSTNode* voronoi2d::BSTNode::m_predecessor

private

Definition at line 111 of file BeachLine.h.

Referenced by BSTNode().

BSTNode* voronoi2d::BSTNode::m_rightChild

private

Definition at line 110 of file BeachLine.h.

Referenced by BSTNode(), and setDepth().

BSTNode* voronoi2d::BSTNode::m_successor

private

Definition at line 112 of file BeachLine.h.

Referenced by BSTNode().

---

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

• larreco/v09_25_00/source/larreco/RecoAlg/Cluster3DAlgs/Voronoi/BeachLine.h
• larreco/v09_25_00/source/larreco/RecoAlg/Cluster3DAlgs/Voronoi/BeachLine.cxx