KiCad PCB EDA Suite
hed::TRIANGULATION Class Reference

Triangulation class for the half-edge data structure with adaption to TTL. More...

#include <hetriang.h>

Public Member Functions

 TRIANGULATION ()
 Default constructor. More...
 
 TRIANGULATION (const TRIANGULATION &aTriangulation)
 Copy constructor. More...
 
 ~TRIANGULATION ()
 Destructor. More...
 
void CreateDelaunay (NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
 Creates a Delaunay triangulation from a set of points. More...
 
EDGE_PTR InitTwoEnclosingTriangles (NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
 Creates an initial Delaunay triangulation from two enclosing triangles. More...
 
void SwapEdge (EDGE_PTR &aDiagonal)
 Swaps the edge associated with diagonal. More...
 
EDGE_PTR SplitTriangle (EDGE_PTR &aEdge, const NODE_PTR &aPoint)
 Splits the triangle associated with edge into three new triangles joining at point. More...
 
void RemoveTriangle (EDGE_PTR &aEdge)
 Removes the boundary triangle associated with edge. More...
 
void ReverseSplitTriangle (EDGE_PTR &aEdge)
 The reverse operation of removeTriangle. More...
 
DART CreateDart ()
 Creates an arbitrary CCW dart. More...
 
const std::list< EDGE_PTR > & GetLeadingEdges () const
 Returns a list of "triangles" (one leading half-edge for each triangle) More...
 
int NoTriangles () const
 Returns the number of triangles. More...
 
void GetEdges (std::list< EDGE_PTR > &aEdges, bool aSkipBoundaryEdges=false) const
 Returns a list of half-edges (one half-edge for each arc) More...
 
void FlagNodes (bool aFlag) const
 Sets flag in all the nodes. More...
 
std::list< NODE_PTR > * GetNodes () const
 Returns a list of nodes. This function requires TTL_USE_NODE_FLAG to be defined. More...
 
void OptimizeDelaunay ()
 Swaps edges until the triangulation is Delaunay (constrained edges are not swapped) More...
 
bool CheckDelaunay () const
 Checks if the triangulation is Delaunay. More...
 
EDGE_PTR GetInteriorNode () const
 Returns an arbitrary interior node (as the source node of the returned edge) More...
 
EDGE_PTR GetBoundaryEdgeInTriangle (const EDGE_PTR &aEdge) const
 
EDGE_PTR GetBoundaryEdge () const
 Returns an arbitrary boundary edge. More...
 
void PrintEdges (std::ofstream &aOutput) const
 Print edges for plotting with, e.g., gnuplot. More...
 

Protected Member Functions

void addLeadingEdge (EDGE_PTR &aEdge)
 
bool removeLeadingEdgeFromList (EDGE_PTR &aLeadingEdge)
 
void cleanAll ()
 
void swapEdge (DART &aDart)
 Swaps the edge associated with dart in the actual data structure. More...
 
void splitTriangle (DART &aDart, const NODE_PTR &aPoint)
 Splits the triangle associated with dart in the actual data structure into three new triangles joining at point. More...
 
void reverseSplitTriangle (DART &aDart)
 The reverse operation of TTLtraits::splitTriangle. More...
 
void removeBoundaryTriangle (DART &aDart)
 Removes a triangle with an edge at the boundary of the triangulation in the actual data structure. More...
 

Protected Attributes

std::list< EDGE_PTRm_leadingEdges
 One half-edge for each arc. More...
 
ttl::TRIANGULATION_HELPERm_helper
 

Friends

class ttl::TRIANGULATION_HELPER
 

Detailed Description

Triangulation class for the half-edge data structure with adaption to TTL.

Definition at line 281 of file hetriang.h.

Constructor & Destructor Documentation

TRIANGULATION::TRIANGULATION ( )

Default constructor.

Definition at line 166 of file hetriang.cpp.

References m_helper.

167 {
168  m_helper = new ttl::TRIANGULATION_HELPER( *this );
169 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287
TRIANGULATION::TRIANGULATION ( const TRIANGULATION aTriangulation)

Copy constructor.

Definition at line 172 of file hetriang.cpp.

References m_helper.

173 {
174  m_helper = 0; // make coverity and static analysers quiet.
175  // Triangulation: Copy constructor not present
176  assert( false );
177 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287
TRIANGULATION::~TRIANGULATION ( )

Destructor.

Definition at line 180 of file hetriang.cpp.

References cleanAll(), and m_helper.

181 {
182  cleanAll();
183  delete m_helper;
184 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287

Member Function Documentation

void hed::TRIANGULATION::addLeadingEdge ( EDGE_PTR aEdge)
inlineprotected

Definition at line 289 of file hetriang.h.

Referenced by InitTwoEnclosingTriangles(), ReverseSplitTriangle(), SplitTriangle(), and SwapEdge().

290  {
291  aEdge->SetAsLeadingEdge();
292  m_leadingEdges.push_front( aEdge );
293  }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
bool TRIANGULATION::CheckDelaunay ( ) const

Checks if the triangulation is Delaunay.

Definition at line 554 of file hetriang.cpp.

References GetLeadingEdges(), m_helper, and ttl::TRIANGULATION_HELPER::SwapTestDelaunay().

555 {
556  // ???? outputs !!!!
557  // ofstream os("qweND.dat");
558  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
559 
560  std::list<EDGE_PTR>::const_iterator it;
561  bool ok = true;
562  int noNotDelaunay = 0;
563 
564  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
565  {
566  EDGE_PTR edge = *it;
567 
568  for( int i = 0; i < 3; ++i )
569  {
570  EDGE_PTR twinedge = edge->GetTwinEdge();
571 
572  // only one of the half-edges
573  if( !twinedge || (size_t) edge.get() > (size_t) twinedge.get() )
574  {
575  DART dart( edge );
576  if( m_helper->SwapTestDelaunay<TTLtraits>( dart ) )
577  {
578  noNotDelaunay++;
579 
580  //printEdge(dart,os); os << "\n";
581  ok = false;
582  //cout << "............. not Delaunay .... " << endl;
583  }
584  }
585 
586  edge = edge->GetNextEdgeInFace();
587  }
588  }
589 
590 #ifdef DEBUG_HE
591  cout << "!!! Triangulation is NOT Delaunay: " << noNotDelaunay << " edges\n" << endl;
592 #endif
593 
594  return ok;
595 }
bool SwapTestDelaunay(const DART_TYPE &aDart, bool aCyclingCheck=false) const
Checks if the edge associated with dart should be swapped according to the Delaunay criterion...
Definition: ttl.h:1488
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287
Traits class (static struct) for the half-edge data structure.
Definition: hetraits.h:62
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:388
void TRIANGULATION::cleanAll ( )
protected

Definition at line 321 of file hetriang.cpp.

References m_leadingEdges.

Referenced by CreateDelaunay(), and ~TRIANGULATION().

322 {
323  for( EDGE_PTR& edge : m_leadingEdges )
324  edge->SetNextEdgeInFace( EDGE_PTR() );
325 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
DART TRIANGULATION::CreateDart ( )

Creates an arbitrary CCW dart.

Definition at line 288 of file hetriang.cpp.

References m_leadingEdges.

289 {
290  // Return an arbitrary CCW dart
291  return DART( *m_leadingEdges.begin() );
292 }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
void TRIANGULATION::CreateDelaunay ( NODES_CONTAINER::iterator  aFirst,
NODES_CONTAINER::iterator  aLast 
)

Creates a Delaunay triangulation from a set of points.

Definition at line 187 of file hetriang.cpp.

References cleanAll(), InitTwoEnclosingTriangles(), ttl::TRIANGULATION_HELPER::InsertNode(), m_helper, and ttl::TRIANGULATION_HELPER::RemoveRectangularBoundary().

Referenced by RN_NET::TRIANGULATOR_STATE::Triangulate().

189 {
190  cleanAll();
191 
192  EDGE_PTR bedge = InitTwoEnclosingTriangles( aFirst, aLast );
193  DART dc( bedge );
194 
195  DART d_iter = dc;
196 
197  NODES_CONTAINER::iterator it;
198  for( it = aFirst; it != aLast; ++it )
199  {
200  m_helper->InsertNode<TTLtraits>( d_iter, *it );
201  }
202 
203  // In general (e.g. for the triangle based data structure), the initial dart
204  // may have been changed.
205  // It is the users responsibility to get a valid boundary dart here.
206  // The half-edge data structure preserves the initial dart.
207  // (A dart at the boundary can also be found by trying to locate a
208  // triangle "outside" the triangulation.)
209 
210  // Assumes rectangular domain
212 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287
Traits class (static struct) for the half-edge data structure.
Definition: hetraits.h:62
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
bool InsertNode(DART_TYPE &aDart, POINT_TYPE &aPoint)
Inserts a new node in an existing Delaunay triangulation and swaps edges to obtain a new Delaunay tri...
Definition: ttl.h:289
void RemoveRectangularBoundary(DART_TYPE &aDart)
Removes the rectangular boundary of a triangulation as a final step of an incremental Delaunay triang...
Definition: ttl.h:379
EDGE_PTR InitTwoEnclosingTriangles(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates an initial Delaunay triangulation from two enclosing triangles.
Definition: hetriang.cpp:110
void TRIANGULATION::FlagNodes ( bool  aFlag) const

Sets flag in all the nodes.

Definition at line 354 of file hetriang.cpp.

References m_leadingEdges.

Referenced by GetNodes().

355 {
356  std::list<EDGE_PTR>::const_iterator it;
357  for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
358  {
359  EDGE_PTR edge = *it;
360 
361  for( int i = 0; i < 3; ++i )
362  {
363  edge->GetSourceNode()->SetFlag( aFlag );
364  edge = edge->GetNextEdgeInFace();
365  }
366  }
367 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
EDGE_PTR TRIANGULATION::GetBoundaryEdge ( ) const

Returns an arbitrary boundary edge.

Definition at line 680 of file hetriang.cpp.

References GetBoundaryEdgeInTriangle(), and GetLeadingEdges().

681 {
682  // Get an arbitrary (CCW) boundary edge
683  // If the triangulation is closed, NULL is returned
684  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
685  std::list<EDGE_PTR>::const_iterator it;
686  EDGE_PTR edge;
687 
688  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
689  {
690  edge = GetBoundaryEdgeInTriangle( *it );
691 
692  if( edge )
693  return edge;
694  }
695  return EDGE_PTR();
696 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:388
EDGE_PTR GetBoundaryEdgeInTriangle(const EDGE_PTR &aEdge) const
Definition: hetriang.cpp:661
EDGE_PTR TRIANGULATION::GetBoundaryEdgeInTriangle ( const EDGE_PTR aEdge) const

Definition at line 661 of file hetriang.cpp.

References ttl::TRIANGULATION_HELPER::IsBoundaryEdge(), and m_helper.

Referenced by GetBoundaryEdge().

662 {
663  EDGE_PTR edge = aEdge;
664 
665  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
666  return edge;
667 
668  edge = edge->GetNextEdgeInFace();
669  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
670  return edge;
671 
672  edge = edge->GetNextEdgeInFace();
673  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
674  return edge;
675 
676  return EDGE_PTR();
677 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287
static bool IsBoundaryEdge(const DART_TYPE &aDart)
Checks if the edge associated with dart is at the boundary of the m_triangulation.
Definition: ttl.h:901
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
void TRIANGULATION::GetEdges ( std::list< EDGE_PTR > &  aEdges,
bool  aSkipBoundaryEdges = false 
) const

Returns a list of half-edges (one half-edge for each arc)

Definition at line 397 of file hetriang.cpp.

References m_leadingEdges.

Referenced by OptimizeDelaunay(), and RN_NET::TRIANGULATOR_STATE::Triangulate().

398 {
399  // collect all arcs (one half edge for each arc)
400  // (boundary edges are also collected).
401  std::list<EDGE_PTR>::const_iterator it;
402 
403  for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
404  {
405  EDGE_PTR edge = *it;
406  for( int i = 0; i < 3; ++i )
407  {
408  EDGE_PTR twinedge = edge->GetTwinEdge();
409  // only one of the half-edges
410 
411  if( ( !twinedge && !aSkipBoundaryEdges )
412  || ( twinedge && ( (size_t) edge.get() > (size_t) twinedge.get() ) ) )
413  {
414  aEdges.push_front( edge );
415  }
416 
417  edge = edge->GetNextEdgeInFace();
418  }
419  }
420 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
EDGE_PTR TRIANGULATION::GetInteriorNode ( ) const

Returns an arbitrary interior node (as the source node of the returned edge)

Definition at line 635 of file hetriang.cpp.

References GetLeadingEdges(), ttl::TRIANGULATION_HELPER::IsBoundaryNode(), and m_helper.

636 {
637  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
638  std::list<EDGE_PTR>::const_iterator it;
639 
640  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
641  {
642  EDGE_PTR edge = *it;
643 
644  // multiple checks, but only until found
645  for( int i = 0; i < 3; ++i )
646  {
647  if( edge->GetTwinEdge() )
648  {
649  if( !m_helper->IsBoundaryNode( DART( edge ) ) )
650  return edge;
651  }
652 
653  edge = edge->GetNextEdgeInFace();
654  }
655  }
656 
657  return EDGE_PTR(); // no boundary nodes
658 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287
static bool IsBoundaryNode(const DART_TYPE &aDart)
Checks if the node associated with dart is at the boundary of the m_triangulation.
Definition: ttl.h:943
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:388
const std::list<EDGE_PTR>& hed::TRIANGULATION::GetLeadingEdges ( ) const
inline

Returns a list of "triangles" (one leading half-edge for each triangle)

Definition at line 388 of file hetriang.h.

References m_leadingEdges.

Referenced by CheckDelaunay(), GetBoundaryEdge(), GetInteriorNode(), and PrintEdges().

389  {
390  return m_leadingEdges;
391  }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
std::list< NODE_PTR > * TRIANGULATION::GetNodes ( ) const

Returns a list of nodes. This function requires TTL_USE_NODE_FLAG to be defined.

See also
Node.

Definition at line 370 of file hetriang.cpp.

References FlagNodes(), and m_leadingEdges.

371 {
372  FlagNodes( false );
373  std::list<NODE_PTR>* nodeList = new std::list<NODE_PTR>;
374  std::list<EDGE_PTR>::const_iterator it;
375 
376  for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
377  {
378  EDGE_PTR edge = *it;
379 
380  for( int i = 0; i < 3; ++i )
381  {
382  const NODE_PTR& node = edge->GetSourceNode();
383 
384  if( node->GetFlag() == false )
385  {
386  nodeList->push_back( node );
387  node->SetFlag( true );
388  }
389  edge = edge->GetNextEdgeInFace();
390  }
391  }
392  return nodeList;
393 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:73
void FlagNodes(bool aFlag) const
Sets flag in all the nodes.
Definition: hetriang.cpp:354
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
EDGE_PTR TRIANGULATION::InitTwoEnclosingTriangles ( NODES_CONTAINER::iterator  aFirst,
NODES_CONTAINER::iterator  aLast 
)

Creates an initial Delaunay triangulation from two enclosing triangles.

Definition at line 110 of file hetriang.cpp.

References addLeadingEdge(), and getLimits().

Referenced by CreateDelaunay().

112 {
113  int xmin, ymin, xmax, ymax;
114  getLimits( aFirst, aLast, xmin, ymin, xmax, ymax );
115 
116  // Add 10% of range:
117  double fac = 10.0;
118  double dx = ( xmax - xmin ) / fac;
119  double dy = ( ymax - ymin ) / fac;
120 
121  NODE_PTR n1 = std::make_shared<NODE>( xmin - dx, ymin - dy );
122  NODE_PTR n2 = std::make_shared<NODE>( xmax + dx, ymin - dy );
123  NODE_PTR n3 = std::make_shared<NODE>( xmax + dx, ymax + dy );
124  NODE_PTR n4 = std::make_shared<NODE>( xmin - dx, ymax + dy );
125 
126  // diagonal
127  EDGE_PTR e1d = std::make_shared<EDGE>();
128  EDGE_PTR e2d = std::make_shared<EDGE>();
129 
130  // lower triangle
131  EDGE_PTR e11 = std::make_shared<EDGE>();
132  EDGE_PTR e12 = std::make_shared<EDGE>();
133 
134  // upper triangle
135  EDGE_PTR e21 = std::make_shared<EDGE>();
136  EDGE_PTR e22 = std::make_shared<EDGE>();
137 
138  // lower triangle
139  e1d->SetSourceNode( n3 );
140  e1d->SetNextEdgeInFace( e11 );
141  e1d->SetTwinEdge( e2d );
142  addLeadingEdge( e1d );
143 
144  e11->SetSourceNode( n1 );
145  e11->SetNextEdgeInFace( e12 );
146 
147  e12->SetSourceNode( n2 );
148  e12->SetNextEdgeInFace( e1d );
149 
150  // upper triangle
151  e2d->SetSourceNode( n1 );
152  e2d->SetNextEdgeInFace( e21 );
153  e2d->SetTwinEdge( e1d );
154  addLeadingEdge( e2d );
155 
156  e21->SetSourceNode( n3 );
157  e21->SetNextEdgeInFace( e22 );
158 
159  e22->SetSourceNode( n4 );
160  e22->SetNextEdgeInFace( e2d );
161 
162  return e11;
163 }
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:289
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
static void getLimits(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast, int &aXmin, int &aYmin, int &aXmax, int &aYmax)
Definition: hetriang.cpp:92
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:73
int hed::TRIANGULATION::NoTriangles ( ) const
inline

Returns the number of triangles.

Definition at line 394 of file hetriang.h.

395  {
396  return (int) m_leadingEdges.size();
397  }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
void TRIANGULATION::OptimizeDelaunay ( )

Swaps edges until the triangulation is Delaunay (constrained edges are not swapped)

Definition at line 598 of file hetriang.cpp.

References GetEdges(), m_helper, SwapEdge(), and ttl::TRIANGULATION_HELPER::SwapTestDelaunay().

599 {
600  // This function is also present in ttl where it is implemented
601  // generically.
602  // The implementation below is tailored for the half-edge data structure,
603  // and is thus more efficient
604 
605  // Collect all interior edges (one half edge for each arc)
606  bool skip_boundary_edges = true;
607  std::list<EDGE_PTR> elist;
608  GetEdges( elist, skip_boundary_edges );
609 
610  // Assumes that elist has only one half-edge for each arc.
611  bool cycling_check = true;
612  bool optimal = false;
613  std::list<EDGE_PTR>::const_iterator it;
614 
615  while( !optimal )
616  {
617  optimal = true;
618 
619  for( it = elist.begin(); it != elist.end(); ++it )
620  {
621  EDGE_PTR edge = *it;
622 
623  DART dart( edge );
624  // Constrained edges should not be swapped
625  if( m_helper->SwapTestDelaunay<TTLtraits>( dart, cycling_check ) )
626  {
627  optimal = false;
628  SwapEdge( edge );
629  }
630  }
631  }
632 }
bool SwapTestDelaunay(const DART_TYPE &aDart, bool aCyclingCheck=false) const
Checks if the edge associated with dart should be swapped according to the Delaunay criterion...
Definition: ttl.h:1488
void GetEdges(std::list< EDGE_PTR > &aEdges, bool aSkipBoundaryEdges=false) const
Returns a list of half-edges (one half-edge for each arc)
Definition: hetriang.cpp:397
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287
void SwapEdge(EDGE_PTR &aDiagonal)
Swaps the edge associated with diagonal.
Definition: hetriang.cpp:504
Traits class (static struct) for the half-edge data structure.
Definition: hetraits.h:62
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
void TRIANGULATION::PrintEdges ( std::ofstream &  aOutput) const

Print edges for plotting with, e.g., gnuplot.

Definition at line 699 of file hetriang.cpp.

References GetLeadingEdges().

700 {
701  // Print source node and target node for each edge face by face,
702  // but only one of the half-edges.
703  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
704  std::list<EDGE_PTR>::const_iterator it;
705 
706  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
707  {
708  EDGE_PTR edge = *it;
709 
710  for( int i = 0; i < 3; ++i )
711  {
712  EDGE_PTR twinedge = edge->GetTwinEdge();
713 
714  // Print only one edge (the highest value of the pointer)
715  if( !twinedge || (size_t) edge.get() > (size_t) twinedge.get() )
716  {
717  // Print source node and target node
718  NODE_PTR node = edge->GetSourceNode();
719  aOutput << node->GetX() << " " << node->GetY() << std::endl;
720  node = edge->GetTargetNode();
721  aOutput << node->GetX() << " " << node->GetY() << std::endl;
722  aOutput << '\n'; // blank line
723  }
724 
725  edge = edge->GetNextEdgeInFace();
726  }
727  }
728 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:388
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:73
void TRIANGULATION::removeBoundaryTriangle ( DART aDart)
protected

Removes a triangle with an edge at the boundary of the triangulation in the actual data structure.

Definition at line 347 of file hetriang.cpp.

References hed::DART::GetEdge(), and RemoveTriangle().

Referenced by ttl::TRIANGULATION_HELPER::RemoveBoundaryNode().

348 {
349  RemoveTriangle( aDart.GetEdge() );
350 }
EDGE_PTR & GetEdge()
Definition: hedart.h:188
void RemoveTriangle(EDGE_PTR &aEdge)
Removes the boundary triangle associated with edge.
Definition: hetriang.cpp:215
bool TRIANGULATION::removeLeadingEdgeFromList ( EDGE_PTR aLeadingEdge)
protected

Definition at line 295 of file hetriang.cpp.

References m_leadingEdges.

Referenced by RemoveTriangle(), ReverseSplitTriangle(), SplitTriangle(), and SwapEdge().

296 {
297  // Remove the edge from the list of leading edges,
298  // but don't delete it.
299  // Also set flag for leading edge to false.
300  // Must search from start of list. Since edges are added to the
301  // start of the list during triangulation, this operation will
302  // normally be fast (when used in the triangulation algorithm)
303  std::list<EDGE_PTR>::iterator it;
304  for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
305  {
306  EDGE_PTR edge = *it;
307 
308  if( edge == aLeadingEdge )
309  {
310  edge->SetAsLeadingEdge( false );
311  it = m_leadingEdges.erase( it );
312 
313  return true;
314  }
315  }
316 
317  return false;
318 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
void TRIANGULATION::RemoveTriangle ( EDGE_PTR aEdge)

Removes the boundary triangle associated with edge.

Definition at line 215 of file hetriang.cpp.

References getLeadingEdgeInTriangle(), and removeLeadingEdgeFromList().

Referenced by removeBoundaryTriangle().

216 {
217  EDGE_PTR e1 = getLeadingEdgeInTriangle( aEdge );
218 
219 #ifdef DEBUG_HE
220  if( !e1 )
221  errorAndExit( "Triangulation::removeTriangle: could not find leading aEdge" );
222 #endif
223 
225  // cout << "No leading edges = " << leadingEdges_.size() << endl;
226  // Remove the triangle
227  EDGE_PTR e2( e1->GetNextEdgeInFace() );
228  EDGE_PTR e3( e2->GetNextEdgeInFace() );
229 
230  e1->Clear();
231  e2->Clear();
232  e3->Clear();
233 }
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:295
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
static EDGE_PTR getLeadingEdgeInTriangle(const EDGE_PTR &aEdge)
Definition: hetriang.cpp:70
void TRIANGULATION::reverseSplitTriangle ( DART aDart)
protected

The reverse operation of TTLtraits::splitTriangle.

This function is only required for functions that involve removal of interior nodes; see for example TrinagulationHelper::RemoveInteriorNode.

reverse_splitTriangle.gif

Definition at line 341 of file hetriang.cpp.

References hed::DART::GetEdge(), and ReverseSplitTriangle().

Referenced by ttl::TRIANGULATION_HELPER::RemoveInteriorNode().

342 {
343  ReverseSplitTriangle( aDart.GetEdge() );
344 }
void ReverseSplitTriangle(EDGE_PTR &aEdge)
The reverse operation of removeTriangle.
Definition: hetriang.cpp:236
EDGE_PTR & GetEdge()
Definition: hedart.h:188
void TRIANGULATION::ReverseSplitTriangle ( EDGE_PTR aEdge)

The reverse operation of removeTriangle.

Definition at line 236 of file hetriang.cpp.

References addLeadingEdge(), getLeadingEdgeInTriangle(), and removeLeadingEdgeFromList().

Referenced by reverseSplitTriangle().

237 {
238  // Reverse operation of splitTriangle
239  EDGE_PTR e1( aEdge->GetNextEdgeInFace() );
241 #ifdef DEBUG_HE
242  if (!le)
243  errorAndExit("Triangulation::removeTriangle: could not find leading edge");
244 #endif
246 
247  EDGE_PTR e2( e1->GetNextEdgeInFace()->GetTwinEdge()->GetNextEdgeInFace() );
248  le = getLeadingEdgeInTriangle( e2 );
249 #ifdef DEBUG_HE
250  if (!le)
251  errorAndExit("Triangulation::removeTriangle: could not find leading edge");
252 #endif
254 
255  EDGE_PTR e3( aEdge->GetTwinEdge()->GetNextEdgeInFace()->GetNextEdgeInFace() );
256  le = getLeadingEdgeInTriangle( e3 );
257 #ifdef DEBUG_HE
258  if (!le)
259  errorAndExit("Triangulation::removeTriangle: could not find leading edge");
260 #endif
262 
263  // The three triangles at the node have now been removed
264  // from the triangulation, but the arcs have not been deleted.
265  // Next delete the 6 half edges radiating from the node
266  // The node is maintained by handle and need not be deleted explicitly
267  EDGE_PTR estar = aEdge;
268  EDGE_PTR enext = estar->GetTwinEdge()->GetNextEdgeInFace();
269  estar->GetTwinEdge()->Clear();
270  estar->Clear();
271 
272  estar = enext;
273  enext = estar->GetTwinEdge()->GetNextEdgeInFace();
274  estar->GetTwinEdge()->Clear();
275  estar->Clear();
276 
277  enext->GetTwinEdge()->Clear();
278  enext->Clear();
279 
280  // Create the new triangle
281  e1->SetNextEdgeInFace( e2 );
282  e2->SetNextEdgeInFace( e3 );
283  e3->SetNextEdgeInFace( e1 );
284  addLeadingEdge( e1 );
285 }
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:289
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:295
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
static EDGE_PTR getLeadingEdgeInTriangle(const EDGE_PTR &aEdge)
Definition: hetriang.cpp:70
void TRIANGULATION::splitTriangle ( DART aDart,
const NODE_PTR aPoint 
)
protected

Splits the triangle associated with dart in the actual data structure into three new triangles joining at point.

splitTriangle.gif
Parameters
aDartOutput: A CCW dart incident with the new node; see the figure.

Definition at line 334 of file hetriang.cpp.

References hed::DART::GetEdge(), hed::DART::Init(), and SplitTriangle().

Referenced by ttl::TRIANGULATION_HELPER::InsertNode().

335 {
336  EDGE_PTR edge = SplitTriangle( aDart.GetEdge(), aPoint );
337  aDart.Init( edge );
338 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
void Init(const EDGE_PTR &aEdge, bool aDir=true)
Definition: hedart.h:156
EDGE_PTR SplitTriangle(EDGE_PTR &aEdge, const NODE_PTR &aPoint)
Splits the triangle associated with edge into three new triangles joining at point.
Definition: hetriang.cpp:423
EDGE_PTR & GetEdge()
Definition: hedart.h:188
EDGE_PTR TRIANGULATION::SplitTriangle ( EDGE_PTR aEdge,
const NODE_PTR aPoint 
)

Splits the triangle associated with edge into three new triangles joining at point.

Definition at line 423 of file hetriang.cpp.

References addLeadingEdge(), and removeLeadingEdgeFromList().

Referenced by splitTriangle().

424 {
425  // Add a node by just splitting a triangle into three triangles
426  // Assumes the half aEdge is located in the triangle
427  // Returns a half aEdge with source node as the new node
428 
429  // e#_n are new edges
430  // e# are existing edges
431  // e#_n and e##_n are new twin edges
432  // e##_n are edges incident to the new node
433 
434  // Add the node to the structure
435  //NODE_PTR new_node(new Node(x,y,z));
436 
437  NODE_PTR n1( aEdge->GetSourceNode() );
438  EDGE_PTR e1( aEdge );
439 
440  EDGE_PTR e2( aEdge->GetNextEdgeInFace() );
441  NODE_PTR n2( e2->GetSourceNode() );
442 
443  EDGE_PTR e3( e2->GetNextEdgeInFace() );
444  NODE_PTR n3( e3->GetSourceNode() );
445 
446  EDGE_PTR e1_n = std::make_shared<EDGE>();
447  EDGE_PTR e11_n = std::make_shared<EDGE>();
448  EDGE_PTR e2_n = std::make_shared<EDGE>();
449  EDGE_PTR e22_n = std::make_shared<EDGE>();
450  EDGE_PTR e3_n = std::make_shared<EDGE>();
451  EDGE_PTR e33_n = std::make_shared<EDGE>();
452 
453  e1_n->SetSourceNode( n1 );
454  e11_n->SetSourceNode( aPoint );
455  e2_n->SetSourceNode( n2 );
456  e22_n->SetSourceNode( aPoint );
457  e3_n->SetSourceNode( n3 );
458  e33_n->SetSourceNode( aPoint );
459 
460  e1_n->SetTwinEdge( e11_n );
461  e11_n->SetTwinEdge( e1_n );
462  e2_n->SetTwinEdge( e22_n );
463  e22_n->SetTwinEdge( e2_n );
464  e3_n->SetTwinEdge( e33_n );
465  e33_n->SetTwinEdge( e3_n );
466 
467  e1_n->SetNextEdgeInFace( e33_n );
468  e2_n->SetNextEdgeInFace( e11_n );
469  e3_n->SetNextEdgeInFace( e22_n );
470 
471  e11_n->SetNextEdgeInFace( e1 );
472  e22_n->SetNextEdgeInFace( e2 );
473  e33_n->SetNextEdgeInFace( e3 );
474 
475  // and update old's next aEdge
476  e1->SetNextEdgeInFace( e2_n );
477  e2->SetNextEdgeInFace( e3_n );
478  e3->SetNextEdgeInFace( e1_n );
479 
480  // add the three new leading edges,
481  // Must remove the old leading aEdge from the list.
482  // Use the field telling if an aEdge is a leading aEdge
483  // NOTE: Must search in the list!!!
484 
485  if( e1->IsLeadingEdge() )
487  else if( e2->IsLeadingEdge() )
489  else if( e3->IsLeadingEdge() )
491  else
492  assert( false ); // one of the edges should be leading
493 
494  addLeadingEdge( e1_n );
495  addLeadingEdge( e2_n );
496  addLeadingEdge( e3_n );
497 
498  // Return a half aEdge incident to the new node (with the new node as source node)
499 
500  return e11_n;
501 }
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:289
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:295
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:73
void TRIANGULATION::swapEdge ( DART aDart)
protected

Swaps the edge associated with dart in the actual data structure.

swapEdge.gif
Parameters
aDartSome of the functions require a dart as output. If this is required by the actual function, the dart should be delivered back in a position as seen if it was glued to the edge when swapping (rotating) the edge CCW; see the figure.
Note
  • If the edge is constrained, or if it should not be swapped for some other reason, this function need not do the actual swap of the edge.
  • Some functions in TTL require that swapEdge is implemented such that darts outside the quadrilateral are not affected by the swap.

Definition at line 328 of file hetriang.cpp.

References hed::DART::GetEdge(), and SwapEdge().

Referenced by ttl::TRIANGULATION_HELPER::RecSwapDelaunay(), ttl::TRIANGULATION_HELPER::SwapEdgeInList(), ttl::TRIANGULATION_HELPER::SwapEdgesAwayFromBoundaryNode(), and ttl::TRIANGULATION_HELPER::SwapEdgesAwayFromInteriorNode().

329 {
330  SwapEdge( aDart.GetEdge() );
331 }
void SwapEdge(EDGE_PTR &aDiagonal)
Swaps the edge associated with diagonal.
Definition: hetriang.cpp:504
EDGE_PTR & GetEdge()
Definition: hedart.h:188
void TRIANGULATION::SwapEdge ( EDGE_PTR aDiagonal)

Swaps the edge associated with diagonal.

Definition at line 504 of file hetriang.cpp.

References addLeadingEdge(), and removeLeadingEdgeFromList().

Referenced by OptimizeDelaunay(), and swapEdge().

505 {
506  // Note that diagonal is both input and output and it is always
507  // kept in counterclockwise direction (this is not required by all
508  // functions in TriangulationHelper now)
509 
510  // Swap by rotating counterclockwise
511  // Use the same objects - no deletion or new objects
512  EDGE_PTR eL( aDiagonal );
513  EDGE_PTR eR( eL->GetTwinEdge() );
514  EDGE_PTR eL_1( eL->GetNextEdgeInFace() );
515  EDGE_PTR eL_2( eL_1->GetNextEdgeInFace() );
516  EDGE_PTR eR_1( eR->GetNextEdgeInFace() );
517  EDGE_PTR eR_2( eR_1->GetNextEdgeInFace() );
518 
519  // avoid node to be dereferenced to zero and deleted
520  NODE_PTR nR( eR_2->GetSourceNode() );
521  NODE_PTR nL( eL_2->GetSourceNode() );
522 
523  eL->SetSourceNode( nR );
524  eR->SetSourceNode( nL );
525 
526  // and now 6 1-sewings
527  eL->SetNextEdgeInFace( eL_2 );
528  eL_2->SetNextEdgeInFace( eR_1 );
529  eR_1->SetNextEdgeInFace( eL );
530 
531  eR->SetNextEdgeInFace( eR_2 );
532  eR_2->SetNextEdgeInFace( eL_1 );
533  eL_1->SetNextEdgeInFace( eR );
534 
535  if( eL->IsLeadingEdge() )
537  else if( eL_1->IsLeadingEdge() )
539  else if( eL_2->IsLeadingEdge() )
541 
542  if( eR->IsLeadingEdge() )
544  else if( eR_1->IsLeadingEdge() )
546  else if( eR_2->IsLeadingEdge() )
548 
549  addLeadingEdge( eL );
550  addLeadingEdge( eR );
551 }
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:289
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:295
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:73

Friends And Related Function Documentation

friend class ttl::TRIANGULATION_HELPER
friend

Definition at line 427 of file hetriang.h.

Member Data Documentation

std::list<EDGE_PTR> hed::TRIANGULATION::m_leadingEdges
protected

One half-edge for each arc.

Definition at line 285 of file hetriang.h.

Referenced by cleanAll(), CreateDart(), FlagNodes(), GetEdges(), GetLeadingEdges(), GetNodes(), and removeLeadingEdgeFromList().


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