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 
59 {
60  assert( m_layers.none() );
61 
62  for( const BOARD_CONNECTED_ITEM* item : m_parents )
63  m_layers |= item->GetLayerSet();
64 }
65 
66 
67 //#define DEBUG_HE
68 #ifdef DEBUG_HE
69 #include <iostream>
70 static void errorAndExit( char* aMessage )
71 {
72  cout << "\n!!! ERROR: "<< aMessage << " !!!\n" << endl;
73  exit( -1 );
74 }
75 #endif
76 
77 
79 {
80  EDGE_PTR edge = aEdge;
81 
82  // Code: 3EF (assumes triangle)
83  if( !edge->IsLeadingEdge() )
84  {
85  edge = edge->GetNextEdgeInFace();
86 
87  if( !edge->IsLeadingEdge() )
88  edge = edge->GetNextEdgeInFace();
89  }
90 
91  if( !edge->IsLeadingEdge() )
92  {
93  return EDGE_PTR();
94  }
95 
96  return edge;
97 }
98 
99 
100 static void getLimits( NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast,
101  int& aXmin, int& aYmin, int& aXmax, int& aYmax)
102 {
103  aXmin = aYmin = std::numeric_limits<int>::min();
104  aXmax = aYmax = std::numeric_limits<int>::max();
105 
106  NODES_CONTAINER::iterator it;
107 
108  for( it = aFirst; it != aLast; ++it )
109  {
110  aXmin = std::min( aXmin, ( *it )->GetX() );
111  aYmin = std::min( aYmin, ( *it )->GetY() );
112  aXmax = std::max( aXmax, ( *it )->GetX() );
113  aYmax = std::max( aYmax, ( *it )->GetY() );
114  }
115 }
116 
117 
118 EDGE_PTR TRIANGULATION::InitTwoEnclosingTriangles( NODES_CONTAINER::iterator aFirst,
119  NODES_CONTAINER::iterator aLast)
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 }
172 
173 
175 {
176  m_helper = new ttl::TRIANGULATION_HELPER( *this );
177 }
178 
179 
181 {
182  m_helper = 0; // make coverity and static analysers quiet.
183  // Triangulation: Copy constructor not present
184  assert( false );
185 }
186 
187 
189 {
190  cleanAll();
191  delete m_helper;
192 }
193 
194 
195 void TRIANGULATION::CreateDelaunay( NODES_CONTAINER::iterator aFirst,
196  NODES_CONTAINER::iterator aLast )
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 }
221 
222 
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 }
242 
243 
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 }
294 
295 
297 {
298  // Return an arbitrary CCW dart
299  return DART( *m_leadingEdges.begin() );
300 }
301 
302 
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 }
327 
328 
330 {
331  for( EDGE_PTR& edge : m_leadingEdges )
332  edge->SetNextEdgeInFace( EDGE_PTR() );
333 }
334 
335 
337 {
338  SwapEdge( aDart.GetEdge() );
339 }
340 
341 
342 void TRIANGULATION::splitTriangle( DART& aDart, const NODE_PTR& aPoint )
343 {
344  EDGE_PTR edge = SplitTriangle( aDart.GetEdge(), aPoint );
345  aDart.Init( edge );
346 }
347 
348 
350 {
351  ReverseSplitTriangle( aDart.GetEdge() );
352 }
353 
354 
356 {
357  RemoveTriangle( aDart.GetEdge() );
358 }
359 
360 
361 #ifdef TTL_USE_NODE_FLAG
362 void TRIANGULATION::FlagNodes( bool aFlag ) const
363 {
364  std::list<EDGE_PTR>::const_iterator it;
365  for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
366  {
367  EDGE_PTR edge = *it;
368 
369  for( int i = 0; i < 3; ++i )
370  {
371  edge->GetSourceNode()->SetFlag( aFlag );
372  edge = edge->GetNextEdgeInFace();
373  }
374  }
375 }
376 
377 
378 std::list<NODE_PTR>* TRIANGULATION::GetNodes() const
379 {
380  FlagNodes( false );
381  std::list<NODE_PTR>* nodeList = new std::list<NODE_PTR>;
382  std::list<EDGE_PTR>::const_iterator it;
383 
384  for( it = m_leadingEdges.begin(); it != m_leadingEdges.end(); ++it )
385  {
386  EDGE_PTR edge = *it;
387 
388  for( int i = 0; i < 3; ++i )
389  {
390  const NODE_PTR& node = edge->GetSourceNode();
391 
392  if( node->GetFlag() == false )
393  {
394  nodeList->push_back( node );
395  node->SetFlag( true );
396  }
397  edge = edge->GetNextEdgeInFace();
398  }
399  }
400  return nodeList;
401 }
402 #endif
403 
404 
405 std::list<EDGE_PTR>* TRIANGULATION::GetEdges( bool aSkipBoundaryEdges ) const
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 }
430 
431 
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 }
511 
512 
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 }
561 
562 
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 }
605 
606 
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 }
643 
644 
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 }
669 
670 
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 }
688 
689 
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 }
707 
708 
709 void TRIANGULATION::PrintEdges( std::ofstream& aOutput ) const
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 }
DART CreateDart()
Creates an arbitrary CCW dart.
Definition: hetriang.cpp:296
void removeBoundaryTriangle(DART &aDart)
Removes a triangle with an edge at the boundary of the triangulation in the actual data structure...
Definition: hetriang.cpp:355
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
Class BOARD_CONNECTED_ITEM.
ttl::TRIANGULATION_HELPER * m_helper
Definition: hetriang.h:390
void OptimizeDelaunay()
Swaps edges until the triangulation is Delaunay (constrained edges are not swapped) ...
Definition: hetriang.cpp:607
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:342
void swapEdge(DART &aDart)
Swaps the edge associated with dart in the actual data structure.
Definition: hetriang.cpp:336
std::unordered_set< const BOARD_CONNECTED_ITEM * > m_parents
List of board items that share this node.
Definition: hetriang.h:113
void updateLayers()
Recomputes the layers used by this node.
Definition: hetriang.cpp:58
EDGE_PTR GetInteriorNode() const
Returns an arbitrary interior node (as the source node of the returned edge)
Definition: hetriang.cpp:645
LSET m_layers
Layers that are occupied by this node.
Definition: hetriang.h:116
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
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
EDGE_PTR GetBoundaryEdge() const
Returns an arbitrary boundary edge.
Definition: hetriang.cpp:690
void PrintEdges(std::ofstream &aOutput) const
Print edges for plotting with, e.g., gnuplot.
Definition: hetriang.cpp:709
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
TRIANGULATION()
Default constructor.
Definition: hetriang.cpp:174
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:392
bool CheckDelaunay() const
Checks if the triangulation is Delaunay.
Definition: hetriang.cpp:563
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:303
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
void ReverseSplitTriangle(EDGE_PTR &aEdge)
The reverse operation of removeTriangle.
Definition: hetriang.cpp:244
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
void Init(const EDGE_PTR &aEdge, bool aDir=true)
Definition: hedart.h:150
static void getLimits(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast, int &aXmin, int &aYmin, int &aXmax, int &aYmax)
Definition: hetriang.cpp:100
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:491
static EDGE_PTR getLeadingEdgeInTriangle(const EDGE_PTR &aEdge)
Definition: hetriang.cpp:78
void reverseSplitTriangle(DART &aDart)
The reverse operation of TTLtraits::splitTriangle.
Definition: hetriang.cpp:349
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:71
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
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
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:195
EDGE_PTR & GetEdge()
Definition: hedart.h:181
#define max(a, b)
Definition: auxiliary.h:86
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
void RemoveTriangle(EDGE_PTR &aEdge)
Removes the boundary triangle associated with edge.
Definition: hetriang.cpp:223
Triangulation class for the half-edge data structure with adaption to TTL.
Definition: hetriang.h:384
EDGE_PTR GetBoundaryEdgeInTriangle(const EDGE_PTR &aEdge) const
Definition: hetriang.cpp:671
std::list< EDGE_PTR > m_leadingEdges
One half-edge for each arc.
Definition: hetriang.h:388
~TRIANGULATION()
Destructor.
Definition: hetriang.cpp:188
#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:118