LArSoft  v06_85_00
Liquid Argon Software toolkit - http://larsoft.org/
BeachLine.h
Go to the documentation of this file.
1 
9 #ifndef BeachLine_h
10 #define BeachLine_h
11 
14 
15 // std includes
16 #include <vector>
17 #include <list>
18 #include <algorithm>
19 //------------------------------------------------------------------------------------------------------------------------------------------
20 
21 namespace voronoi2d
22 {
32 class BSTNode
33 {
34 public:
38  BSTNode() :
39  m_depth(0),
40  m_event(NULL),
41  m_parent(NULL),
42  m_leftChild(NULL),
43  m_rightChild(NULL),
44  m_predecessor(NULL),
45  m_successor(NULL),
46  m_associated(NULL),
47  m_halfEdge(NULL),
48  m_face(NULL)
49  {}
50 
52  m_depth(0),
53  m_event(event),
54  m_parent(NULL),
55  m_leftChild(NULL),
56  m_rightChild(NULL),
57  m_predecessor(NULL),
58  m_successor(NULL),
59  m_associated(NULL),
60  m_halfEdge(NULL),
61  m_face(NULL)
62  {
63  if (m_event) m_event->setBSTNode(this);
64  }
65 
67 
71  ~BSTNode() {}
72 
76  int getDepth() const {return m_depth;}
77  IEvent* getEvent() const {return m_event;}
78  BSTNode* getParent() const {return m_parent;}
79  BSTNode* getLeftChild() const {return m_leftChild;}
80  BSTNode* getRightChild() const {return m_rightChild;}
82  BSTNode* getSuccessor() const {return m_successor;}
83  BSTNode* getAssociated() const {return m_associated;}
84 
86  dcel2d::Face* getFace() const {return m_face;}
87 
91  void setParent(BSTNode* node) {m_parent = node;}
92  void setLeftChild(BSTNode* node) {m_leftChild = node;}
93  void setRightChild(BSTNode* node) {m_rightChild = node;}
94  void setPredecessor(BSTNode* node) {m_predecessor = node;}
95  void setSuccessor(BSTNode* node) {m_successor = node;}
96  void setAssociated(BSTNode* node) {m_associated = node;}
97 
98  void setHalfEdge(dcel2d::HalfEdge* half) {m_halfEdge = half;}
99  void setFace(dcel2d::Face* face) {m_face = face;}
100 
101  void setDepth(int depth) {m_depth = depth;}
102  void setDepth();
103 
107  bool operator<(const BSTNode&) const;
108 
109 private:
110  int m_depth; // Keep track of depth of nodes to this one
111  IEvent* m_event; // Pointer to the event object
112  BSTNode* m_parent; // Tree traversal - parent node
113  BSTNode* m_leftChild; // Tree traversal - left child node
114  BSTNode* m_rightChild; // Tree traversal - right child node
115  BSTNode* m_predecessor; // Beachline traversal - predecessor
116  BSTNode* m_successor; // Beachline traversal - successor
117  BSTNode* m_associated; // This allows handling of circle events
118  dcel2d::HalfEdge* m_halfEdge; // If a breakpoint then we associate halfedges
119  dcel2d::Face* m_face; // If a leaf then we associated faces
120 };
121 
122 using BSTNodeList = std::list<BSTNode>;
123 
130 {
131 public:
132  BeachLine() : m_root(NULL) {m_nodeVec.clear();}
133 
134  bool isEmpty() const {return m_root == NULL;}
135  void setEmpty() {m_root = NULL;}
136  const BSTNode* getTopNode() const {return m_root;}
137  BSTNode* findBestLeaf(const IEvent* event) const {return findBestLeaf(event, m_root);}
138  BSTNode* insertNewLeaf(IEvent*);
139  BSTNode* removeLeaf(BSTNode*);
140  int getHeight() const {return getTreeDepth(m_root);}
141  int countNodes() const;
142  int countLeaves() const;
143  int traverseBeach() const;
144 
145 private:
146  BSTNode* insertNewLeaf(IEvent*, BSTNode*);
147 
148  BSTNode* findBestLeaf(const IEvent*, BSTNode*) const;
149 
150  void countNodes(const BSTNode*, int&) const;
151  void countLeaves(const BSTNode*, int&) const;
152 
153  int traverseBeachLeft(BSTNode*) const;
154  int traverseBeachRight(BSTNode*) const;
155 
156  void checkBeachLine(double) const;
157 
161  int getTreeDepth(const BSTNode*) const;
162 
166  void rebalance(BSTNode*);
167  BSTNode* rotateWithLeftChild(BSTNode*);
168  BSTNode* rotateWithRightChild(BSTNode*);
169 
170  BSTNode* m_root; // the root of all evil, er, the top node
171  BSTNodeList m_nodeVec; // Use this to keep track of the nodes
172 
174 };
175 
176 } // namespace lar_cluster3d
177 #endif
This defines the actual beach line. The idea is to implement this as a self balancing binary search t...
Definition: BeachLine.h:129
IEvent * m_event
Definition: BeachLine.h:111
EventUtilities m_utilities
Definition: BeachLine.h:173
void setRightChild(BSTNode *node)
Definition: BeachLine.h:93
void setSuccessor(BSTNode *node)
Definition: BeachLine.h:95
BSTNode * m_associated
Definition: BeachLine.h:117
bool operator<(const BSTNode &) const
Provide override definition for ordering.
Provides some basic functions operating in IEvent class objects.
BSTNode class definiton specifically for use in constructing Voronoi diagrams. We are trying to follo...
Definition: BeachLine.h:32
void setDepth(int depth)
Definition: BeachLine.h:101
BSTNode * getParent() const
Definition: BeachLine.h:78
std::list< BSTNode > BSTNodeList
Definition: BeachLine.h:122
int getHeight() const
Definition: BeachLine.h:140
Internal class definitions to facilitate construction of diagram.
BSTNode * findBestLeaf(const IEvent *event) const
Definition: BeachLine.h:137
BSTNode * getAssociated() const
Definition: BeachLine.h:83
dcel2d::Face * m_face
Definition: BeachLine.h:119
BSTNode * m_successor
Definition: BeachLine.h:116
BSTNode * m_predecessor
Definition: BeachLine.h:115
void setLeftChild(BSTNode *node)
Definition: BeachLine.h:92
void setParent(BSTNode *node)
Allow setting of the points.
Definition: BeachLine.h:91
BSTNode * getRightChild() const
Definition: BeachLine.h:80
BSTNodeList m_nodeVec
Definition: BeachLine.h:171
BSTNode * m_parent
Definition: BeachLine.h:112
virtual void setBSTNode(BSTNode *)=0
void setAssociated(BSTNode *node)
Definition: BeachLine.h:96
const BSTNode * getTopNode() const
Definition: BeachLine.h:136
BSTNode()
Constructor.
Definition: BeachLine.h:38
int getDepth() const
recover the data members
Definition: BeachLine.h:76
BSTNode(IEvent *event)
Definition: BeachLine.h:51
~BSTNode()
Virtual Destructor.
Definition: BeachLine.h:71
BSTNode * getPredecessor() const
Definition: BeachLine.h:81
BSTNode * m_leftChild
Definition: BeachLine.h:113
dcel2d::Face * getFace() const
Definition: BeachLine.h:86
bool isEmpty() const
Definition: BeachLine.h:134
void setFace(dcel2d::Face *face)
Definition: BeachLine.h:99
dcel2d::HalfEdge * getHalfEdge() const
Definition: BeachLine.h:85
void setPredecessor(BSTNode *node)
Definition: BeachLine.h:94
IEvent * getEvent() const
Definition: BeachLine.h:77
dcel2d::HalfEdge * m_halfEdge
Definition: BeachLine.h:118
BSTNode * getSuccessor() const
Definition: BeachLine.h:82
BSTNode * m_rightChild
Definition: BeachLine.h:114
BSTNode * getLeftChild() const
Definition: BeachLine.h:79
Event finding and building.
void setHalfEdge(dcel2d::HalfEdge *half)
Definition: BeachLine.h:98