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() [1/2]

TRIANGULATION::TRIANGULATION ( )

Default constructor.

Definition at line 165 of file hetriang.cpp.

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

References m_helper.

◆ TRIANGULATION() [2/2]

TRIANGULATION::TRIANGULATION ( const TRIANGULATION aTriangulation)

Copy constructor.

Definition at line 171 of file hetriang.cpp.

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

References m_helper.

◆ ~TRIANGULATION()

TRIANGULATION::~TRIANGULATION ( )

Destructor.

Definition at line 179 of file hetriang.cpp.

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

References cleanAll(), and m_helper.

Member Function Documentation

◆ addLeadingEdge()

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

Definition at line 289 of file hetriang.h.

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

References m_leadingEdges.

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

◆ CheckDelaunay()

bool TRIANGULATION::CheckDelaunay ( ) const

Checks if the triangulation is Delaunay.

Definition at line 553 of file hetriang.cpp.

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

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

◆ cleanAll()

void TRIANGULATION::cleanAll ( )
protected

Definition at line 320 of file hetriang.cpp.

321 {
322  for( EDGE_PTR& edge : m_leadingEdges )
323  edge->SetNextEdgeInFace( EDGE_PTR() );
324 }
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

References m_leadingEdges.

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

◆ CreateDart()

DART TRIANGULATION::CreateDart ( )

Creates an arbitrary CCW dart.

Definition at line 287 of file hetriang.cpp.

288 {
289  // Return an arbitrary CCW dart
290  return DART( *m_leadingEdges.begin() );
291 }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285

References m_leadingEdges.

◆ CreateDelaunay()

void TRIANGULATION::CreateDelaunay ( NODES_CONTAINER::iterator  aFirst,
NODES_CONTAINER::iterator  aLast 
)

Creates a Delaunay triangulation from a set of points.

Definition at line 186 of file hetriang.cpp.

188 {
189  cleanAll();
190 
191  EDGE_PTR bedge = InitTwoEnclosingTriangles( aFirst, aLast );
192  DART dc( bedge );
193 
194  DART d_iter = dc;
195 
196  NODES_CONTAINER::iterator it;
197  for( it = aFirst; it != aLast; ++it )
198  {
199  m_helper->InsertNode<TTLtraits>( d_iter, *it );
200  }
201 
202  // In general (e.g. for the triangle based data structure), the initial dart
203  // may have been changed.
204  // It is the users responsibility to get a valid boundary dart here.
205  // The half-edge data structure preserves the initial dart.
206  // (A dart at the boundary can also be found by trying to locate a
207  // triangle "outside" the triangulation.)
208 
209  // Assumes rectangular domain
211 }
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:292
void RemoveRectangularBoundary(DART_TYPE &aDart)
Removes the rectangular boundary of a triangulation as a final step of an incremental Delaunay triang...
Definition: ttl.h:382
EDGE_PTR InitTwoEnclosingTriangles(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates an initial Delaunay triangulation from two enclosing triangles.
Definition: hetriang.cpp:109

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

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

◆ FlagNodes()

void TRIANGULATION::FlagNodes ( bool  aFlag) const

Sets flag in all the nodes.

Definition at line 353 of file hetriang.cpp.

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

References i, and m_leadingEdges.

Referenced by GetNodes().

◆ GetBoundaryEdge()

EDGE_PTR TRIANGULATION::GetBoundaryEdge ( ) const

Returns an arbitrary boundary edge.

Definition at line 679 of file hetriang.cpp.

680 {
681  // Get an arbitrary (CCW) boundary edge
682  // If the triangulation is closed, NULL is returned
683  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
684  std::list<EDGE_PTR>::const_iterator it;
685  EDGE_PTR edge;
686 
687  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
688  {
689  edge = GetBoundaryEdgeInTriangle( *it );
690 
691  if( edge )
692  return edge;
693  }
694  return EDGE_PTR();
695 }
EDGE_PTR GetBoundaryEdgeInTriangle(const EDGE_PTR &aEdge) const
Definition: hetriang.cpp:660
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< EDGE > EDGE_PTR
Definition: hetriang.h:75

References GetBoundaryEdgeInTriangle(), and GetLeadingEdges().

◆ GetBoundaryEdgeInTriangle()

EDGE_PTR TRIANGULATION::GetBoundaryEdgeInTriangle ( const EDGE_PTR aEdge) const

Definition at line 660 of file hetriang.cpp.

661 {
662  EDGE_PTR edge = aEdge;
663 
664  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
665  return edge;
666 
667  edge = edge->GetNextEdgeInFace();
668  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
669  return edge;
670 
671  edge = edge->GetNextEdgeInFace();
672  if( m_helper->IsBoundaryEdge( DART( edge ) ) )
673  return edge;
674 
675  return EDGE_PTR();
676 }
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:904
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75

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

Referenced by GetBoundaryEdge().

◆ GetEdges()

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 396 of file hetriang.cpp.

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

References i, and m_leadingEdges.

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

◆ GetInteriorNode()

EDGE_PTR TRIANGULATION::GetInteriorNode ( ) const

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

Definition at line 634 of file hetriang.cpp.

635 {
636  const std::list<EDGE_PTR>& leadingEdges = GetLeadingEdges();
637  std::list<EDGE_PTR>::const_iterator it;
638 
639  for( it = leadingEdges.begin(); it != leadingEdges.end(); ++it )
640  {
641  EDGE_PTR edge = *it;
642 
643  // multiple checks, but only until found
644  for( int i = 0; i < 3; ++i )
645  {
646  if( edge->GetTwinEdge() )
647  {
648  if( !m_helper->IsBoundaryNode( DART( edge ) ) )
649  return edge;
650  }
651 
652  edge = edge->GetNextEdgeInFace();
653  }
654  }
655 
656  return EDGE_PTR(); // no boundary nodes
657 }
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:946
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< EDGE > EDGE_PTR
Definition: hetriang.h:75
size_t i
Definition: json11.cpp:649

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

◆ GetLeadingEdges()

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.

389  {
390  return m_leadingEdges;
391  }
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285

References m_leadingEdges.

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

◆ GetNodes()

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 369 of file hetriang.cpp.

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

References FlagNodes(), i, and m_leadingEdges.

◆ InitTwoEnclosingTriangles()

EDGE_PTR TRIANGULATION::InitTwoEnclosingTriangles ( NODES_CONTAINER::iterator  aFirst,
NODES_CONTAINER::iterator  aLast 
)

Creates an initial Delaunay triangulation from two enclosing triangles.

Definition at line 109 of file hetriang.cpp.

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

References addLeadingEdge(), and getLimits().

Referenced by CreateDelaunay().

◆ NoTriangles()

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

References m_leadingEdges.

◆ OptimizeDelaunay()

void TRIANGULATION::OptimizeDelaunay ( )

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

Definition at line 597 of file hetriang.cpp.

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

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

◆ PrintEdges()

void TRIANGULATION::PrintEdges ( std::ofstream &  aOutput) const

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

Definition at line 698 of file hetriang.cpp.

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

References GetLeadingEdges(), and i.

◆ removeBoundaryTriangle()

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 346 of file hetriang.cpp.

347 {
348  RemoveTriangle( aDart.GetEdge() );
349 }
EDGE_PTR & GetEdge()
Definition: hedart.h:188
void RemoveTriangle(EDGE_PTR &aEdge)
Removes the boundary triangle associated with edge.
Definition: hetriang.cpp:214

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

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

◆ removeLeadingEdgeFromList()

bool TRIANGULATION::removeLeadingEdgeFromList ( EDGE_PTR aLeadingEdge)
protected

Definition at line 294 of file hetriang.cpp.

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

References m_leadingEdges.

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

◆ RemoveTriangle()

void TRIANGULATION::RemoveTriangle ( EDGE_PTR aEdge)

Removes the boundary triangle associated with edge.

Definition at line 214 of file hetriang.cpp.

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

References getLeadingEdgeInTriangle(), and removeLeadingEdgeFromList().

Referenced by removeBoundaryTriangle().

◆ reverseSplitTriangle()

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 340 of file hetriang.cpp.

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

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

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

◆ ReverseSplitTriangle()

void TRIANGULATION::ReverseSplitTriangle ( EDGE_PTR aEdge)

The reverse operation of removeTriangle.

Definition at line 235 of file hetriang.cpp.

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

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

Referenced by reverseSplitTriangle().

◆ splitTriangle()

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 333 of file hetriang.cpp.

334 {
335  EDGE_PTR edge = SplitTriangle( aDart.GetEdge(), aPoint );
336  aDart.Init( edge );
337 }
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:422
EDGE_PTR & GetEdge()
Definition: hedart.h:188

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

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

◆ SplitTriangle()

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 422 of file hetriang.cpp.

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

References addLeadingEdge(), and removeLeadingEdgeFromList().

Referenced by splitTriangle().

◆ swapEdge()

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 327 of file hetriang.cpp.

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

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().

◆ SwapEdge()

void TRIANGULATION::SwapEdge ( EDGE_PTR aDiagonal)

Swaps the edge associated with diagonal.

Definition at line 503 of file hetriang.cpp.

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

References addLeadingEdge(), and removeLeadingEdgeFromList().

Referenced by OptimizeDelaunay(), and swapEdge().

Friends And Related Function Documentation

◆ ttl::TRIANGULATION_HELPER

friend class ttl::TRIANGULATION_HELPER
friend

Definition at line 427 of file hetriang.h.

Member Data Documentation

◆ m_helper

◆ m_leadingEdges

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 addLeadingEdge(), cleanAll(), CreateDart(), FlagNodes(), GetEdges(), GetLeadingEdges(), GetNodes(), NoTriangles(), and removeLeadingEdgeFromList().


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