KiCad PCB EDA Suite
hetriang.cpp
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1998, 2000-2007, 2010, 2011, 2012, 2013 SINTEF ICT,
3  * Applied Mathematics, Norway.
4  * Copyright (C) 2013 CERN
5  * @author Maciej Suminski <maciej.suminski@cern.ch>
6  *
7  * Contact information: E-mail: tor.dokken@sintef.no
8  * SINTEF ICT, Department of Applied Mathematics,
9  * P.O. Box 124 Blindern,
10  * 0314 Oslo, Norway.
11  *
12  * This file is part of TTL.
13  *
14  * TTL is free software: you can redistribute it and/or modify
15  * it under the terms of the GNU Affero General Public License as
16  * published by the Free Software Foundation, either version 3 of the
17  * License, or (at your option) any later version.
18  *
19  * TTL is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU Affero General Public License for more details.
23  *
24  * You should have received a copy of the GNU Affero General Public
25  * License along with TTL. If not, see
26  * <http://www.gnu.org/licenses/>.
27  *
28  * In accordance with Section 7(b) of the GNU Affero General Public
29  * License, a covered work must retain the producer line in every data
30  * file that is created or manipulated using TTL.
31  *
32  * Other Usage
33  * You can be released from the requirements of the license by purchasing
34  * a commercial license. Buying such a license is mandatory as soon as you
35  * develop commercial activities involving the TTL library without
36  * disclosing the source code of your own applications.
37  *
38  * This file may be used in accordance with the terms contained in a
39  * written agreement between you and SINTEF ICT.
40  */
41 
42 #include <ttl/halfedge/hetriang.h>
43 #include <ttl/halfedge/hetraits.h>
44 #include <ttl/ttl.h>
45 #include <algorithm>
46 #include <fstream>
47 #include <limits>
49 #include <memory>
50 
51 using namespace hed;
52 
53 #ifdef TTL_USE_NODE_ID
54  int NODE::id_count = 0;
55 #endif
56 
57 
58 
59 //#define DEBUG_HE
60 #ifdef DEBUG_HE
61 #include <iostream>
62 static void errorAndExit( char* aMessage )
63 {
64  cout << "\n!!! ERROR: "<< aMessage << " !!!\n" << endl;
65  exit( -1 );
66 }
67 #endif
68 
69 
71 {
72  EDGE_PTR edge = aEdge;
73 
74  // Code: 3EF (assumes triangle)
75  if( !edge->IsLeadingEdge() )
76  {
77  edge = edge->GetNextEdgeInFace();
78 
79  if( !edge->IsLeadingEdge() )
80  edge = edge->GetNextEdgeInFace();
81  }
82 
83  if( !edge->IsLeadingEdge() )
84  {
85  return EDGE_PTR();
86  }
87 
88  return edge;
89 }
90 
91 
92 static void getLimits( NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast,
93  int& aXmin, int& aYmin, int& aXmax, int& aYmax)
94 {
95  aXmin = aYmin = std::numeric_limits<int>::min();
96  aXmax = aYmax = std::numeric_limits<int>::max();
97 
98  NODES_CONTAINER::iterator it;
99 
100  for( it = aFirst; it != aLast; ++it )
101  {
102  aXmin = std::min( aXmin, ( *it )->GetX() );
103  aYmin = std::min( aYmin, ( *it )->GetY() );
104  aXmax = std::max( aXmax, ( *it )->GetX() );
105  aYmax = std::max( aYmax, ( *it )->GetY() );
106  }
107 }
108 
109 
110 EDGE_PTR TRIANGULATION::InitTwoEnclosingTriangles( NODES_CONTAINER::iterator aFirst,
111  NODES_CONTAINER::iterator aLast)
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 }
164 
165 
167 {
168  m_helper = new ttl::TRIANGULATION_HELPER( *this );
169 }
170 
171 
173 {
174  m_helper = 0; // make coverity and static analysers quiet.
175  // Triangulation: Copy constructor not present
176  assert( false );
177 }
178 
179 
181 {
182  cleanAll();
183  delete m_helper;
184 }
185 
186 
187 void TRIANGULATION::CreateDelaunay( NODES_CONTAINER::iterator aFirst,
188  NODES_CONTAINER::iterator aLast )
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 }
213 
214 
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 }
234 
235 
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 }
286 
287 
289 {
290  // Return an arbitrary CCW dart
291  return DART( *m_leadingEdges.begin() );
292 }
293 
294 
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 }
319 
320 
322 {
323  for( EDGE_PTR& edge : m_leadingEdges )
324  edge->SetNextEdgeInFace( EDGE_PTR() );
325 }
326 
327 
329 {
330  SwapEdge( aDart.GetEdge() );
331 }
332 
333 
334 void TRIANGULATION::splitTriangle( DART& aDart, const NODE_PTR& aPoint )
335 {
336  EDGE_PTR edge = SplitTriangle( aDart.GetEdge(), aPoint );
337  aDart.Init( edge );
338 }
339 
340 
342 {
343  ReverseSplitTriangle( aDart.GetEdge() );
344 }
345 
346 
348 {
349  RemoveTriangle( aDart.GetEdge() );
350 }
351 
352 
353 #ifdef TTL_USE_NODE_FLAG
354 void TRIANGULATION::FlagNodes( bool aFlag ) const
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 }
368 
369 
370 std::list<NODE_PTR>* TRIANGULATION::GetNodes() const
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 }
394 #endif
395 
396 
397 void TRIANGULATION::GetEdges( std::list<EDGE_PTR>& aEdges, bool aSkipBoundaryEdges ) const
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 }
421 
422 
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 }
502 
503 
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 }
552 
553 
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 }
596 
597 
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 }
633 
634 
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 }
659 
660 
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 }
678 
679 
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 }
697 
698 
699 void TRIANGULATION::PrintEdges( std::ofstream& aOutput ) const
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 }
static int id_count
TTL_USE_NODE_ID must be defined.
Definition: hetriang.h:99
DART CreateDart()
Creates an arbitrary CCW dart.
Definition: hetriang.cpp:288
void removeBoundaryTriangle(DART &aDart)
Removes a triangle with an edge at the boundary of the triangulation in the actual data structure...
Definition: hetriang.cpp:347
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
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
Class BOARD_CONNECTED_ITEM.
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:287
void OptimizeDelaunay()
Swaps edges until the triangulation is Delaunay (constrained edges are not swapped) ...
Definition: hetriang.cpp:598
void splitTriangle(DART &aDart, const NODE_PTR &aPoint)
Splits the triangle associated with dart in the actual data structure into three new triangles joinin...
Definition: hetriang.cpp:334
void swapEdge(DART &aDart)
Swaps the edge associated with dart in the actual data structure.
Definition: hetriang.cpp:328
std::list< NODE_PTR > * GetNodes() const
Returns a list of nodes. This function requires TTL_USE_NODE_FLAG to be defined.
Definition: hetriang.cpp:370
EDGE_PTR GetInteriorNode() const
Returns an arbitrary interior node (as the source node of the returned edge)
Definition: hetriang.cpp:635
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
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
EDGE_PTR GetBoundaryEdge() const
Returns an arbitrary boundary edge.
Definition: hetriang.cpp:680
void PrintEdges(std::ofstream &aOutput) const
Print edges for plotting with, e.g., gnuplot.
Definition: hetriang.cpp:699
TRIANGULATION()
Default constructor.
Definition: hetriang.cpp:166
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:289
bool CheckDelaunay() const
Checks if the triangulation is Delaunay.
Definition: hetriang.cpp:554
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:295
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
void ReverseSplitTriangle(EDGE_PTR &aEdge)
The reverse operation of removeTriangle.
Definition: hetriang.cpp:236
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
void Init(const EDGE_PTR &aEdge, bool aDir=true)
Definition: hedart.h:156
static void getLimits(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast, int &aXmin, int &aYmin, int &aXmax, int &aYmax)
Definition: hetriang.cpp:92
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:388
static EDGE_PTR getLeadingEdgeInTriangle(const EDGE_PTR &aEdge)
Definition: hetriang.cpp:70
void reverseSplitTriangle(DART &aDart)
The reverse operation of TTLtraits::splitTriangle.
Definition: hetriang.cpp:341
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:73
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
The half-edge data structure.
Definition: hedart.h:45
void CreateDelaunay(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates a Delaunay triangulation from a set of points.
Definition: hetriang.cpp:187
EDGE_PTR & GetEdge()
Definition: hedart.h:188
#define max(a, b)
Definition: auxiliary.h:86
void FlagNodes(bool aFlag) const
Sets flag in all the nodes.
Definition: hetriang.cpp:354
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
void RemoveTriangle(EDGE_PTR &aEdge)
Removes the boundary triangle associated with edge.
Definition: hetriang.cpp:215
Triangulation class for the half-edge data structure with adaption to TTL.
Definition: hetriang.h:281
EDGE_PTR GetBoundaryEdgeInTriangle(const EDGE_PTR &aEdge) const
Definition: hetriang.cpp:661
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
~TRIANGULATION()
Destructor.
Definition: hetriang.cpp:180
#define min(a, b)
Definition: auxiliary.h:85
EDGE_PTR InitTwoEnclosingTriangles(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates an initial Delaunay triangulation from two enclosing triangles.
Definition: hetriang.cpp:110