KiCad PCB EDA Suite
hetriang.h
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 #ifndef _HE_TRIANG_H_
43 #define _HE_TRIANG_H_
44 
45 #define TTL_USE_NODE_ID // Each node gets it's own unique id
46 #define TTL_USE_NODE_FLAG // Each node gets a flag (can be set to true or false)
47 
48 #include <list>
49 #include <unordered_set>
50 #include <vector>
51 #include <iostream>
52 #include <fstream>
53 #include <ttl/ttl_util.h>
54 #include <memory>
56 #include <math/vector2d.h>
57 
59 class CN_CLUSTER;
60 
61 namespace ttl
62 {
64 };
65 
69 namespace hed
70 {
71 // Helper typedefs
72 class NODE;
73 class EDGE;
74 typedef std::shared_ptr<NODE> NODE_PTR;
75 typedef std::shared_ptr<EDGE> EDGE_PTR;
76 typedef std::weak_ptr<EDGE> EDGE_WEAK_PTR;
77 typedef std::vector<NODE_PTR> NODES_CONTAINER;
78 
89 class NODE
90 {
91 protected:
92 #ifdef TTL_USE_NODE_FLAG
93  bool m_flag;
95 #endif
96 
97 #ifdef TTL_USE_NODE_ID
98  static int id_count;
100 
102  int m_id;
103 #endif
104 
106  const int m_x, m_y;
107 
108 public:
110  NODE( int aX = 0, int aY = 0, std::shared_ptr<CN_CLUSTER> aCluster = nullptr ) :
111 #ifdef TTL_USE_NODE_FLAG
112  m_flag( false ),
113 #endif
114 #ifdef TTL_USE_NODE_ID
115  m_id( id_count++ ),
116 #endif
117  m_x( aX ), m_y( aY )
118  {
119  }
120 
122  ~NODE() {
123 
124  }
125 
126  const VECTOR2D Pos() const { return VECTOR2D( m_x, m_y ); }
127 
129  inline int GetX() const
130  {
131  return m_x;
132  }
133 
135  inline int GetY() const
136  {
137  return m_y;
138  }
139 
140  inline VECTOR2I GetPos() const
141  {
142  return VECTOR2I( m_x, m_y );
143  }
144 
145 #ifdef TTL_USE_NODE_ID
146 
148  inline void SetId( int aId )
149  {
150  m_id = aId;
151  }
152 
153  inline int Id() const
154  {
155  return m_id;
156  }
157 #endif
158 
159 #ifdef TTL_USE_NODE_FLAG
160  inline void SetFlag( bool aFlag )
162  {
163  m_flag = aFlag;
164  }
165 
167  inline const bool& GetFlag() const
168  {
169  return m_flag;
170  }
171 #endif
172 };
173 
174 
179 class EDGE
180 {
181 public:
183  EDGE() : m_isLeadingEdge( false )
184  {
185  }
186 
188  virtual ~EDGE()
189  {
190 
191  }
192 
194  inline void SetSourceNode( const NODE_PTR& aNode )
195  {
196  m_sourceNode = aNode;
197  }
198 
200  inline void SetNextEdgeInFace( const EDGE_PTR& aEdge )
201  {
202  m_nextEdgeInFace = aEdge;
203  }
204 
206  inline void SetTwinEdge( const EDGE_PTR& aEdge )
207  {
208  m_twinEdge = aEdge;
209  }
210 
212  inline void SetAsLeadingEdge( bool aLeading = true )
213  {
214  m_isLeadingEdge = aLeading;
215  }
216 
218  inline bool IsLeadingEdge() const
219  {
220  return m_isLeadingEdge;
221  }
222 
224  inline EDGE_PTR GetTwinEdge() const
225  {
226  if( m_twinEdge.expired() )
227  return nullptr;
228 
229  return m_twinEdge.lock();
230  }
231 
232  inline void ClearTwinEdge()
233  {
234  m_twinEdge.reset();
235  }
236 
238  inline const EDGE_PTR& GetNextEdgeInFace() const
239  {
240  assert ( m_nextEdgeInFace );
241  return m_nextEdgeInFace;
242  }
243 
245  inline const NODE_PTR& GetSourceNode() const
246  {
247  return m_sourceNode;
248  }
249 
251  virtual const NODE_PTR& GetTargetNode() const
252  {
253  return m_nextEdgeInFace->GetSourceNode();
254  }
255 
256  void Clear()
257  {
258  m_sourceNode.reset();
259  m_nextEdgeInFace.reset();
260 
261  if( !m_twinEdge.expired() )
262  {
263  m_twinEdge.lock()->ClearTwinEdge();
264  m_twinEdge.reset();
265  }
266  }
267 
268 protected:
269  NODE_PTR m_sourceNode;
270  EDGE_WEAK_PTR m_twinEdge;
273 };
274 
275 class DART; // Forward declaration (class in this namespace)
276 
282 {
283 protected:
285  std::list<EDGE_PTR> m_leadingEdges;
286 
288 
289  void addLeadingEdge( EDGE_PTR& aEdge )
290  {
291  aEdge->SetAsLeadingEdge();
292  m_leadingEdges.push_front( aEdge );
293  }
294 
295  bool removeLeadingEdgeFromList( EDGE_PTR& aLeadingEdge );
296 
297  void cleanAll();
298 
317  void swapEdge( DART& aDart );
318 
330  void splitTriangle( DART& aDart, const NODE_PTR& aPoint );
331 
341  void reverseSplitTriangle( DART& aDart );
342 
347  void removeBoundaryTriangle( DART& aDart );
348 
349 public:
351  TRIANGULATION();
352 
354  TRIANGULATION( const TRIANGULATION& aTriangulation );
355 
357  ~TRIANGULATION();
358 
360  void CreateDelaunay( NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast );
361 
363  // When using rectangular boundary - loop through all points and expand.
364  // (Called from createDelaunay(...) when starting)
365  EDGE_PTR InitTwoEnclosingTriangles( NODES_CONTAINER::iterator aFirst,
366  NODES_CONTAINER::iterator aLast );
367 
368  // These two functions are required by TTL for Delaunay triangulation
369 
371  void SwapEdge( EDGE_PTR& aDiagonal );
372 
374  EDGE_PTR SplitTriangle( EDGE_PTR& aEdge, const NODE_PTR& aPoint );
375 
376  // Functions required by TTL for removing nodes in a Delaunay triangulation
377 
379  void RemoveTriangle( EDGE_PTR& aEdge ); // boundary triangle required
380 
382  void ReverseSplitTriangle( EDGE_PTR& aEdge );
383 
385  DART CreateDart();
386 
388  const std::list<EDGE_PTR>& GetLeadingEdges() const
389  {
390  return m_leadingEdges;
391  }
392 
394  int NoTriangles() const
395  {
396  return (int) m_leadingEdges.size();
397  }
398 
400  void GetEdges( std::list<EDGE_PTR>& aEdges, bool aSkipBoundaryEdges = false ) const;
401 
402 #ifdef TTL_USE_NODE_FLAG
403  void FlagNodes( bool aFlag ) const;
405 
407  std::list<NODE_PTR>* GetNodes() const;
408 #endif
409 
411  void OptimizeDelaunay();
412 
414  bool CheckDelaunay() const;
415 
417  EDGE_PTR GetInteriorNode() const;
418 
419  EDGE_PTR GetBoundaryEdgeInTriangle( const EDGE_PTR& aEdge ) const;
420 
422  EDGE_PTR GetBoundaryEdge() const;
423 
425  void PrintEdges( std::ofstream& aOutput ) const;
426 
428 };
429 }; // End of hed namespace
430 
431 #endif
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
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
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
void SetId(int aId)
Returns the id (TTL_USE_NODE_ID must be defined)
Definition: hetriang.h:148
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
int NoTriangles() const
Returns the number of triangles.
Definition: hetriang.h:394
int GetX() const
Returns the x-coordinate.
Definition: hetriang.h:129
~NODE()
Destructor.
Definition: hetriang.h:122
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
const NODE_PTR & GetSourceNode() const
Retuns the source node.
Definition: hetriang.h:245
void ClearTwinEdge()
Definition: hetriang.h:232
int GetY() const
Returns the y-coordinate.
Definition: hetriang.h:135
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
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590
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:166
bool m_flag
TTL_USE_NODE_FLAG must be defined.
Definition: hetriang.h:94
const VECTOR2D Pos() const
Definition: hetriang.h:126
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:289
virtual ~EDGE()
Destructor.
Definition: hetriang.h:188
NODE(int aX=0, int aY=0, std::shared_ptr< CN_CLUSTER > aCluster=nullptr)
Constructor.
Definition: hetriang.h:110
bool CheckDelaunay() const
Checks if the triangulation is Delaunay.
Definition: hetriang.cpp:554
Edge class in the in the half-edge data structure.
Definition: hetriang.h:179
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:295
void ReverseSplitTriangle(EDGE_PTR &aEdge)
The reverse operation of removeTriangle.
Definition: hetriang.cpp:236
std::vector< NODE_PTR > NODES_CONTAINER
Definition: hetriang.h:77
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:75
#define TTL_USE_NODE_FLAG
Definition: hetriang.h:46
VECTOR2< double > VECTOR2D
Definition: vector2d.h:589
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:388
#define TTL_USE_NODE_ID
Definition: hetriang.h:45
EDGE_WEAK_PTR m_twinEdge
Definition: hetriang.h:270
Main interface to TTL.
Definition: hetriang.h:61
const bool & GetFlag() const
Returns the flag (TTL_USE_NODE_FLAG must be defined)
Definition: hetriang.h:167
void reverseSplitTriangle(DART &aDart)
The reverse operation of TTLtraits::splitTriangle.
Definition: hetriang.cpp:341
void SetAsLeadingEdge(bool aLeading=true)
Sets the edge as a leading edge.
Definition: hetriang.h:212
bool IsLeadingEdge() const
Checks if an edge is a leading edge.
Definition: hetriang.h:218
EDGE_PTR GetTwinEdge() const
Returns the twin edge.
Definition: hetriang.h:224
int Id() const
Definition: hetriang.h:153
VECTOR2I GetPos() const
Definition: hetriang.h:140
void SetSourceNode(const NODE_PTR &aNode)
Sets the source node.
Definition: hetriang.h:194
void SetFlag(bool aFlag)
Sets the flag (TTL_USE_NODE_FLAG must be defined)
Definition: hetriang.h:161
void Clear()
Definition: hetriang.h:256
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:73
void SetTwinEdge(const EDGE_PTR &aEdge)
Sets the twin edge.
Definition: hetriang.h:206
int m_id
A unique id for each node (TTL_USE_NODE_ID must be defined)
Definition: hetriang.h:102
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()
Constructor.
Definition: hetriang.h:183
Board layer functions and definitions.
virtual const NODE_PTR & GetTargetNode() const
Returns the target node.
Definition: hetriang.h:251
void SetNextEdgeInFace(const EDGE_PTR &aEdge)
Sets the next edge in face.
Definition: hetriang.h:200
const int m_y
Definition: hetriang.h:106
bool m_isLeadingEdge
Definition: hetriang.h:272
const EDGE_PTR & GetNextEdgeInFace() const
Returns the next edge in face.
Definition: hetriang.h:238
void FlagNodes(bool aFlag) const
Sets flag in all the nodes.
Definition: hetriang.cpp:354
Node class for data structures (Inherits from HandleId)
Definition: hetriang.h:89
const int m_x
Node coordinates.
Definition: hetriang.h:106
NODE_PTR m_sourceNode
Definition: hetriang.h:269
EDGE_PTR m_nextEdgeInFace
Definition: hetriang.h:271
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
std::weak_ptr< EDGE > EDGE_WEAK_PTR
Definition: hetriang.h:76
EDGE_PTR InitTwoEnclosingTriangles(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates an initial Delaunay triangulation from two enclosing triangles.
Definition: hetriang.cpp:110