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...
 
std::list< EDGE_PTR > * GetEdges (bool aSkipBoundaryEdges=false) const
 Returns a list of half-edges (one half-edge for each arc) 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 384 of file hetriang.h.

Constructor & Destructor Documentation

TRIANGULATION::TRIANGULATION ( )

Default constructor.

Definition at line 174 of file hetriang.cpp.

References m_helper.

175 {
176  m_helper = new ttl::TRIANGULATION_HELPER( *this );
177 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:390
TRIANGULATION::TRIANGULATION ( const TRIANGULATION aTriangulation)

Copy constructor.

Definition at line 180 of file hetriang.cpp.

References m_helper.

181 {
182  m_helper = 0; // make coverity and static analysers quiet.
183  // Triangulation: Copy constructor not present
184  assert( false );
185 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:390
TRIANGULATION::~TRIANGULATION ( )

Destructor.

Definition at line 188 of file hetriang.cpp.

References cleanAll(), and m_helper.

189 {
190  cleanAll();
191  delete m_helper;
192 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:390

Member Function Documentation

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

Definition at line 392 of file hetriang.h.

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

393  {
394  aEdge->SetAsLeadingEdge();
395  m_leadingEdges.push_front( aEdge );
396  }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:388
bool TRIANGULATION::CheckDelaunay ( ) const

Checks if the triangulation is Delaunay.

Definition at line 563 of file hetriang.cpp.

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

564 {
565  // ???? outputs !!!!
566  // ofstream os("qweND.dat");
567  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
568 
569  std::list<EDGE_PTR>::const_iterator it;
570  bool ok = true;
571  int noNotDelaunay = 0;
572 
573  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
574  {
575  EDGE_PTR edge = *it;
576 
577  for( int i = 0; i < 3; ++i )
578  {
579  EDGE_PTR twinedge = edge->GetTwinEdge();
580 
581  // only one of the half-edges
582  if( !twinedge || (size_t) edge.get() > (size_t) twinedge.get() )
583  {
584  DART dart( edge );
585  if( m_helper->SwapTestDelaunay<TTLtraits>( dart ) )
586  {
587  noNotDelaunay++;
588 
589  //printEdge(dart,os); os << "\n";
590  ok = false;
591  //cout << "............. not Delaunay .... " << endl;
592  }
593  }
594 
595  edge = edge->GetNextEdgeInFace();
596  }
597  }
598 
599 #ifdef DEBUG_HE
600  cout << "!!! Triangulation is NOT Delaunay: " << noNotDelaunay << " edges\n" << endl;
601 #endif
602 
603  return ok;
604 }
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:390
Traits class (static struct) for the half-edge data structure.
Definition: hetraits.h:62
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:491
void TRIANGULATION::cleanAll ( )
protected

Definition at line 329 of file hetriang.cpp.

References m_leadingEdges.

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

330 {
331  for( EDGE_PTR& edge : m_leadingEdges )
332  edge->SetNextEdgeInFace( EDGE_PTR() );
333 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:388
DART TRIANGULATION::CreateDart ( )

Creates an arbitrary CCW dart.

Definition at line 296 of file hetriang.cpp.

References m_leadingEdges.

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

Creates a Delaunay triangulation from a set of points.

Definition at line 195 of file hetriang.cpp.

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

Referenced by RN_NET::compute().

197 {
198  cleanAll();
199 
200  EDGE_PTR bedge = InitTwoEnclosingTriangles( aFirst, aLast );
201  DART dc( bedge );
202 
203  DART d_iter = dc;
204 
205  NODES_CONTAINER::iterator it;
206  for( it = aFirst; it != aLast; ++it )
207  {
208  m_helper->InsertNode<TTLtraits>( d_iter, *it );
209  }
210 
211  // In general (e.g. for the triangle based data structure), the initial dart
212  // may have been changed.
213  // It is the users responsibility to get a valid boundary dart here.
214  // The half-edge data structure preserves the initial dart.
215  // (A dart at the boundary can also be found by trying to locate a
216  // triangle "outside" the triangulation.)
217 
218  // Assumes rectangular domain
220 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:390
Traits class (static struct) for the half-edge data structure.
Definition: hetraits.h:62
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
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:118
EDGE_PTR TRIANGULATION::GetBoundaryEdge ( ) const

Returns an arbitrary boundary edge.

Definition at line 690 of file hetriang.cpp.

References GetBoundaryEdgeInTriangle(), and GetLeadingEdges().

691 {
692  // Get an arbitrary (CCW) boundary edge
693  // If the triangulation is closed, NULL is returned
694  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
695  std::list<EDGE_PTR>::const_iterator it;
696  EDGE_PTR edge;
697 
698  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
699  {
700  edge = GetBoundaryEdgeInTriangle( *it );
701 
702  if( edge )
703  return edge;
704  }
705  return EDGE_PTR();
706 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:491
EDGE_PTR GetBoundaryEdgeInTriangle(const EDGE_PTR &aEdge) const
Definition: hetriang.cpp:671
EDGE_PTR TRIANGULATION::GetBoundaryEdgeInTriangle ( const EDGE_PTR aEdge) const

Definition at line 671 of file hetriang.cpp.

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

Referenced by GetBoundaryEdge().

672 {
673  EDGE_PTR edge = aEdge;
674 
675  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
676  return edge;
677 
678  edge = edge->GetNextEdgeInFace();
679  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
680  return edge;
681 
682  edge = edge->GetNextEdgeInFace();
683  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
684  return edge;
685 
686  return EDGE_PTR();
687 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:390
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:73
std::list< EDGE_PTR > * TRIANGULATION::GetEdges ( bool  aSkipBoundaryEdges = false) const

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

Definition at line 405 of file hetriang.cpp.

References m_leadingEdges.

Referenced by OptimizeDelaunay().

406 {
407  // collect all arcs (one half edge for each arc)
408  // (boundary edges are also collected).
409  std::list<EDGE_PTR>::const_iterator it;
410  std::list<EDGE_PTR>* elist = new std::list<EDGE_PTR>;
411 
412  for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
413  {
414  EDGE_PTR edge = *it;
415  for( int i = 0; i < 3; ++i )
416  {
417  EDGE_PTR twinedge = edge->GetTwinEdge();
418  // only one of the half-edges
419 
420  if( ( !twinedge && !aSkipBoundaryEdges )
421  || ( twinedge && ( (size_t) edge.get() > (size_t) twinedge.get() ) ) )
422  elist->push_front( edge );
423 
424  edge = edge->GetNextEdgeInFace();
425  }
426  }
427 
428  return elist;
429 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:388
EDGE_PTR TRIANGULATION::GetInteriorNode ( ) const

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

Definition at line 645 of file hetriang.cpp.

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

646 {
647  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
648  std::list<EDGE_PTR>::const_iterator it;
649 
650  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
651  {
652  EDGE_PTR edge = *it;
653 
654  // multiple checks, but only until found
655  for( int i = 0; i < 3; ++i )
656  {
657  if( edge->GetTwinEdge() )
658  {
659  if( !m_helper->IsBoundaryNode( DART( edge ) ) )
660  return edge;
661  }
662 
663  edge = edge->GetNextEdgeInFace();
664  }
665  }
666 
667  return EDGE_PTR(); // no boundary nodes
668 }
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:390
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:73
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:491
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 491 of file hetriang.h.

References m_leadingEdges.

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

492  {
493  return m_leadingEdges;
494  }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:388
EDGE_PTR TRIANGULATION::InitTwoEnclosingTriangles ( NODES_CONTAINER::iterator  aFirst,
NODES_CONTAINER::iterator  aLast 
)

Creates an initial Delaunay triangulation from two enclosing triangles.

Definition at line 118 of file hetriang.cpp.

References addLeadingEdge(), and getLimits().

Referenced by CreateDelaunay().

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

Returns the number of triangles.

Definition at line 497 of file hetriang.h.

498  {
499  return (int) m_leadingEdges.size();
500  }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:388
void TRIANGULATION::OptimizeDelaunay ( )

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

Definition at line 607 of file hetriang.cpp.

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

608 {
609  // This function is also present in ttl where it is implemented
610  // generically.
611  // The implementation below is tailored for the half-edge data structure,
612  // and is thus more efficient
613 
614  // Collect all interior edges (one half edge for each arc)
615  bool skip_boundary_edges = true;
616  std::list<EDGE_PTR>* elist = GetEdges( skip_boundary_edges );
617 
618  // Assumes that elist has only one half-edge for each arc.
619  bool cycling_check = true;
620  bool optimal = false;
621  std::list<EDGE_PTR>::const_iterator it;
622 
623  while( !optimal )
624  {
625  optimal = true;
626 
627  for( it = elist->begin(); it != elist->end(); ++it )
628  {
629  EDGE_PTR edge = *it;
630 
631  DART dart( edge );
632  // Constrained edges should not be swapped
633  if( m_helper->SwapTestDelaunay<TTLtraits>( dart, cycling_check ) )
634  {
635  optimal = false;
636  SwapEdge( edge );
637  }
638  }
639  }
640 
641  delete elist;
642 }
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:390
void SwapEdge(EDGE_PTR &aDiagonal)
Swaps the edge associated with diagonal.
Definition: hetriang.cpp:513
Traits class (static struct) for the half-edge data structure.
Definition: hetraits.h:62
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
std::list< EDGE_PTR > * GetEdges(bool aSkipBoundaryEdges=false) const
Returns a list of half-edges (one half-edge for each arc)
Definition: hetriang.cpp:405
void TRIANGULATION::PrintEdges ( std::ofstream &  aOutput) const

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

Definition at line 709 of file hetriang.cpp.

References GetLeadingEdges().

710 {
711  // Print source node and target node for each edge face by face,
712  // but only one of the half-edges.
713  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
714  std::list<EDGE_PTR>::const_iterator it;
715 
716  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
717  {
718  EDGE_PTR edge = *it;
719 
720  for( int i = 0; i < 3; ++i )
721  {
722  EDGE_PTR twinedge = edge->GetTwinEdge();
723 
724  // Print only one edge (the highest value of the pointer)
725  if( !twinedge || (size_t) edge.get() > (size_t) twinedge.get() )
726  {
727  // Print source node and target node
728  NODE_PTR node = edge->GetSourceNode();
729  aOutput << node->GetX() << " " << node->GetY() << std::endl;
730  node = edge->GetTargetNode();
731  aOutput << node->GetX() << " " << node->GetY() << std::endl;
732  aOutput << '\n'; // blank line
733  }
734 
735  edge = edge->GetNextEdgeInFace();
736  }
737  }
738 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:491
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:71
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 355 of file hetriang.cpp.

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

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

356 {
357  RemoveTriangle( aDart.GetEdge() );
358 }
EDGE_PTR & GetEdge()
Definition: hedart.h:181
void RemoveTriangle(EDGE_PTR &aEdge)
Removes the boundary triangle associated with edge.
Definition: hetriang.cpp:223
bool TRIANGULATION::removeLeadingEdgeFromList ( EDGE_PTR aLeadingEdge)
protected

Definition at line 303 of file hetriang.cpp.

References m_leadingEdges.

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

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

Removes the boundary triangle associated with edge.

Definition at line 223 of file hetriang.cpp.

References getLeadingEdgeInTriangle(), and removeLeadingEdgeFromList().

Referenced by removeBoundaryTriangle().

224 {
225  EDGE_PTR e1 = getLeadingEdgeInTriangle( aEdge );
226 
227 #ifdef DEBUG_HE
228  if( !e1 )
229  errorAndExit( "Triangulation::removeTriangle: could not find leading aEdge" );
230 #endif
231 
233  // cout << "No leading edges = " << leadingEdges_.size() << endl;
234  // Remove the triangle
235  EDGE_PTR e2( e1->GetNextEdgeInFace() );
236  EDGE_PTR e3( e2->GetNextEdgeInFace() );
237 
238  e1->Clear();
239  e2->Clear();
240  e3->Clear();
241 }
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:303
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
static EDGE_PTR getLeadingEdgeInTriangle(const EDGE_PTR &aEdge)
Definition: hetriang.cpp:78
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 349 of file hetriang.cpp.

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

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

350 {
351  ReverseSplitTriangle( aDart.GetEdge() );
352 }
void ReverseSplitTriangle(EDGE_PTR &aEdge)
The reverse operation of removeTriangle.
Definition: hetriang.cpp:244
EDGE_PTR & GetEdge()
Definition: hedart.h:181
void TRIANGULATION::ReverseSplitTriangle ( EDGE_PTR aEdge)

The reverse operation of removeTriangle.

Definition at line 244 of file hetriang.cpp.

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

Referenced by reverseSplitTriangle().

245 {
246  // Reverse operation of splitTriangle
247  EDGE_PTR e1( aEdge->GetNextEdgeInFace() );
249 #ifdef DEBUG_HE
250  if (!le)
251  errorAndExit("Triangulation::removeTriangle: could not find leading edge");
252 #endif
254 
255  EDGE_PTR e2( e1->GetNextEdgeInFace()->GetTwinEdge()->GetNextEdgeInFace() );
256  le = getLeadingEdgeInTriangle( e2 );
257 #ifdef DEBUG_HE
258  if (!le)
259  errorAndExit("Triangulation::removeTriangle: could not find leading edge");
260 #endif
262 
263  EDGE_PTR e3( aEdge->GetTwinEdge()->GetNextEdgeInFace()->GetNextEdgeInFace() );
264  le = getLeadingEdgeInTriangle( e3 );
265 #ifdef DEBUG_HE
266  if (!le)
267  errorAndExit("Triangulation::removeTriangle: could not find leading edge");
268 #endif
270 
271  // The three triangles at the node have now been removed
272  // from the triangulation, but the arcs have not been deleted.
273  // Next delete the 6 half edges radiating from the node
274  // The node is maintained by handle and need not be deleted explicitly
275  EDGE_PTR estar = aEdge;
276  EDGE_PTR enext = estar->GetTwinEdge()->GetNextEdgeInFace();
277  estar->GetTwinEdge()->Clear();
278  estar->Clear();
279 
280  estar = enext;
281  enext = estar->GetTwinEdge()->GetNextEdgeInFace();
282  estar->GetTwinEdge()->Clear();
283  estar->Clear();
284 
285  enext->GetTwinEdge()->Clear();
286  enext->Clear();
287 
288  // Create the new triangle
289  e1->SetNextEdgeInFace( e2 );
290  e2->SetNextEdgeInFace( e3 );
291  e3->SetNextEdgeInFace( e1 );
292  addLeadingEdge( e1 );
293 }
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:392
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:303
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
static EDGE_PTR getLeadingEdgeInTriangle(const EDGE_PTR &aEdge)
Definition: hetriang.cpp:78
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 342 of file hetriang.cpp.

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

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

343 {
344  EDGE_PTR edge = SplitTriangle( aDart.GetEdge(), aPoint );
345  aDart.Init( edge );
346 }
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
void Init(const EDGE_PTR &aEdge, bool aDir=true)
Definition: hedart.h:150
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:432
EDGE_PTR & GetEdge()
Definition: hedart.h:181
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 432 of file hetriang.cpp.

References addLeadingEdge(), and removeLeadingEdgeFromList().

Referenced by splitTriangle().

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

337 {
338  SwapEdge( aDart.GetEdge() );
339 }
void SwapEdge(EDGE_PTR &aDiagonal)
Swaps the edge associated with diagonal.
Definition: hetriang.cpp:513
EDGE_PTR & GetEdge()
Definition: hedart.h:181
void TRIANGULATION::SwapEdge ( EDGE_PTR aDiagonal)

Swaps the edge associated with diagonal.

Definition at line 513 of file hetriang.cpp.

References addLeadingEdge(), and removeLeadingEdgeFromList().

Referenced by OptimizeDelaunay(), and swapEdge().

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

Friends And Related Function Documentation

friend class ttl::TRIANGULATION_HELPER
friend

Definition at line 530 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 388 of file hetriang.h.

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


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