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>
48 #include <memory>
49 
50 using namespace hed;
51 
52 #ifdef TTL_USE_NODE_ID
53  int NODE::id_count = 0;
54 #endif
55 
56 
57 
58 //#define DEBUG_HE
59 #ifdef DEBUG_HE
60 #include <iostream>
61 static void errorAndExit( char* aMessage )
62 {
63  cout << "\n!!! ERROR: "<< aMessage << " !!!\n" << endl;
64  exit( -1 );
65 }
66 #endif
67 
68 
70 {
71  EDGE_PTR edge = aEdge;
72 
73  // Code: 3EF (assumes triangle)
74  if( !edge->IsLeadingEdge() )
75  {
76  edge = edge->GetNextEdgeInFace();
77 
78  if( !edge->IsLeadingEdge() )
79  edge = edge->GetNextEdgeInFace();
80  }
81 
82  if( !edge->IsLeadingEdge() )
83  {
84  return EDGE_PTR();
85  }
86 
87  return edge;
88 }
89 
90 
91 static void getLimits( NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast,
92  int& aXmin, int& aYmin, int& aXmax, int& aYmax)
93 {
94  aXmin = aYmin = std::numeric_limits<int>::min();
95  aXmax = aYmax = std::numeric_limits<int>::max();
96 
97  NODES_CONTAINER::iterator it;
98 
99  for( it = aFirst; it != aLast; ++it )
100  {
101  aXmin = std::min( aXmin, ( *it )->GetX() );
102  aYmin = std::min( aYmin, ( *it )->GetY() );
103  aXmax = std::max( aXmax, ( *it )->GetX() );
104  aYmax = std::max( aYmax, ( *it )->GetY() );
105  }
106 }
107 
108 
109 EDGE_PTR TRIANGULATION::InitTwoEnclosingTriangles( NODES_CONTAINER::iterator aFirst,
110  NODES_CONTAINER::iterator aLast)
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 }
163 
164 
166 {
167  m_helper = new ttl::TRIANGULATION_HELPER( *this );
168 }
169 
170 
172 {
173  m_helper = 0; // make coverity and static analysers quiet.
174  // Triangulation: Copy constructor not present
175  assert( false );
176 }
177 
178 
180 {
181  cleanAll();
182  delete m_helper;
183 }
184 
185 
186 void TRIANGULATION::CreateDelaunay( NODES_CONTAINER::iterator aFirst,
187  NODES_CONTAINER::iterator aLast )
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 }
212 
213 
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 }
233 
234 
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 }
285 
286 
288 {
289  // Return an arbitrary CCW dart
290  return DART( *m_leadingEdges.begin() );
291 }
292 
293 
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 }
318 
319 
321 {
322  for( EDGE_PTR& edge : m_leadingEdges )
323  edge->SetNextEdgeInFace( EDGE_PTR() );
324 }
325 
326 
328 {
329  SwapEdge( aDart.GetEdge() );
330 }
331 
332 
333 void TRIANGULATION::splitTriangle( DART& aDart, const NODE_PTR& aPoint )
334 {
335  EDGE_PTR edge = SplitTriangle( aDart.GetEdge(), aPoint );
336  aDart.Init( edge );
337 }
338 
339 
341 {
342  ReverseSplitTriangle( aDart.GetEdge() );
343 }
344 
345 
347 {
348  RemoveTriangle( aDart.GetEdge() );
349 }
350 
351 
352 #ifdef TTL_USE_NODE_FLAG
353 void TRIANGULATION::FlagNodes( bool aFlag ) const
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 }
367 
368 
369 std::list<NODE_PTR>* TRIANGULATION::GetNodes() const
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 }
393 #endif
394 
395 
396 void TRIANGULATION::GetEdges( std::list<EDGE_PTR>& aEdges, bool aSkipBoundaryEdges ) const
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 }
420 
421 
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 }
501 
502 
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 }
551 
552 
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 }
595 
596 
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 }
632 
633 
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 }
658 
659 
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 }
677 
678 
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 }
696 
697 
698 void TRIANGULATION::PrintEdges( std::ofstream& aOutput ) const
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 }
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:287
void removeBoundaryTriangle(DART &aDart)
Removes a triangle with an edge at the boundary of the triangulation in the actual data structure.
Definition: hetriang.cpp:346
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:597
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:333
void swapEdge(DART &aDart)
Swaps the edge associated with dart in the actual data structure.
Definition: hetriang.cpp:327
EDGE_PTR GetBoundaryEdgeInTriangle(const EDGE_PTR &aEdge) const
Definition: hetriang.cpp:660
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
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
EDGE_PTR GetInteriorNode() const
Returns an arbitrary interior node (as the source node of the returned edge)
Definition: hetriang.cpp:634
TRIANGULATION()
Default constructor.
Definition: hetriang.cpp:165
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:289
bool CheckDelaunay() const
Checks if the triangulation is Delaunay.
Definition: hetriang.cpp:553
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 removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:294
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
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:235
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:91
void FlagNodes(bool aFlag) const
Sets flag in all the nodes.
Definition: hetriang.cpp:353
static EDGE_PTR getLeadingEdgeInTriangle(const EDGE_PTR &aEdge)
Definition: hetriang.cpp:69
EDGE_PTR GetBoundaryEdge() const
Returns an arbitrary boundary edge.
Definition: hetriang.cpp:679
void reverseSplitTriangle(DART &aDart)
The reverse operation of TTLtraits::splitTriangle.
Definition: hetriang.cpp:340
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:422
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:186
EDGE_PTR & GetEdge()
Definition: hedart.h:188
#define max(a, b)
Definition: auxiliary.h:86
size_t i
Definition: json11.cpp:597
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:214
Triangulation class for the half-edge data structure with adaption to TTL.
Definition: hetriang.h:281
void PrintEdges(std::ofstream &aOutput) const
Print edges for plotting with, e.g., gnuplot.
Definition: hetriang.cpp:698
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:285
~TRIANGULATION()
Destructor.
Definition: hetriang.cpp:179
#define min(a, b)
Definition: auxiliary.h:85
std::list< NODE_PTR > * GetNodes() const
Returns a list of nodes. This function requires TTL_USE_NODE_FLAG to be defined.
Definition: hetriang.cpp:369
EDGE_PTR InitTwoEnclosingTriangles(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates an initial Delaunay triangulation from two enclosing triangles.
Definition: hetriang.cpp:109