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 
58 
59 namespace ttl
60 {
62 };
63 
67 namespace hed
68 {
69 // Helper typedefs
70 class NODE;
71 class EDGE;
72 typedef std::shared_ptr<NODE> NODE_PTR;
73 typedef std::shared_ptr<EDGE> EDGE_PTR;
74 typedef std::weak_ptr<EDGE> EDGE_WEAK_PTR;
75 typedef std::vector<NODE_PTR> NODES_CONTAINER;
76 
87 class NODE
88 {
89 protected:
90 #ifdef TTL_USE_NODE_FLAG
91  bool m_flag;
93 #endif
94 
95 #ifdef TTL_USE_NODE_ID
96  static int id_count;
98 
100  int m_id;
101 #endif
102 
104  const int m_x, m_y;
105 
107  int m_tag;
108 
110  bool m_noline;
111 
113  std::unordered_set<const BOARD_CONNECTED_ITEM*> m_parents;
114 
117 
119  void updateLayers();
120 
121 public:
123  NODE( int aX = 0, int aY = 0 ) :
124 #ifdef TTL_USE_NODE_FLAG
125  m_flag( false ),
126 #endif
127 #ifdef TTL_USE_NODE_ID
128  m_id( id_count++ ),
129 #endif
130  m_x( aX ), m_y( aY ), m_tag( -1 ), m_noline( false )
131  {
132  m_layers.reset();
133  }
134 
136  ~NODE() {}
137 
139  inline int GetX() const
140  {
141  return m_x;
142  }
143 
145  inline int GetY() const
146  {
147  return m_y;
148  }
149 
151  inline int GetTag() const
152  {
153  return m_tag;
154  }
155 
157  inline void SetTag( int aTag )
158  {
159  m_tag = aTag;
160  }
161 
163  inline void SetNoLine( bool aEnable )
164  {
165  m_noline = aEnable;
166  }
167 
169  inline const bool& GetNoLine() const
170  {
171  return m_noline;
172  }
173 
174 #ifdef TTL_USE_NODE_ID
175  inline int Id() const
177  {
178  return m_id;
179  }
180 #endif
181 
182 #ifdef TTL_USE_NODE_FLAG
183  inline void SetFlag( bool aFlag )
185  {
186  m_flag = aFlag;
187  }
188 
190  inline const bool& GetFlag() const
191  {
192  return m_flag;
193  }
194 #endif
195 
196  inline unsigned int GetRefCount() const
197  {
198  return m_parents.size();
199  }
200 
201  inline void AddParent( const BOARD_CONNECTED_ITEM* aParent )
202  {
203  m_parents.insert( aParent );
204  m_layers.reset(); // mark as needs updating
205  }
206 
207  inline void RemoveParent( const BOARD_CONNECTED_ITEM* aParent )
208  {
209  auto it = m_parents.find( aParent );
210 
211  if( it != m_parents.end() )
212  {
213  m_parents.erase( it );
214  m_layers.reset(); // mark as needs updating
215  }
216  }
217 
218  const LSET& GetLayers()
219  {
220  if( m_layers.none() )
221  updateLayers();
222 
223  return m_layers;
224  }
225 
226  // Tag used for unconnected items.
227  static const int TAG_UNCONNECTED = -1;
228 };
229 
230 
235 class EDGE
236 {
237 public:
239  EDGE() : m_weight( 0 ), m_isLeadingEdge( false )
240  {
241  }
242 
244  virtual ~EDGE()
245  {
246  }
247 
249  inline int GetTag() const
250  {
251  int tag = GetSourceNode()->GetTag();
252  if( tag >= 0 )
253  return tag;
254 
255  return GetTargetNode()->GetTag();
256  }
257 
259  inline void SetSourceNode( const NODE_PTR& aNode )
260  {
261  m_sourceNode = aNode;
262  }
263 
265  inline void SetNextEdgeInFace( const EDGE_PTR& aEdge )
266  {
267  m_nextEdgeInFace = aEdge;
268  }
269 
271  inline void SetTwinEdge( const EDGE_PTR& aEdge )
272  {
273  m_twinEdge = aEdge;
274  }
275 
277  inline void SetAsLeadingEdge( bool aLeading = true )
278  {
279  m_isLeadingEdge = aLeading;
280  }
281 
283  inline bool IsLeadingEdge() const
284  {
285  return m_isLeadingEdge;
286  }
287 
289  inline EDGE_PTR GetTwinEdge() const
290  {
291  return m_twinEdge.lock();
292  }
293 
294  inline void ClearTwinEdge()
295  {
296  m_twinEdge.reset();
297  }
298 
300  inline const EDGE_PTR& GetNextEdgeInFace() const
301  {
302  return m_nextEdgeInFace;
303  }
304 
306  inline const NODE_PTR& GetSourceNode() const
307  {
308  return m_sourceNode;
309  }
310 
312  virtual const NODE_PTR& GetTargetNode() const
313  {
314  return m_nextEdgeInFace->GetSourceNode();
315  }
316 
317  inline void SetWeight( unsigned int weight )
318  {
319  m_weight = weight;
320  }
321 
322  inline unsigned int GetWeight() const
323  {
324  return m_weight;
325  }
326 
327  void Clear()
328  {
329  m_sourceNode.reset();
330  m_nextEdgeInFace.reset();
331 
332  if( !m_twinEdge.expired() )
333  {
334  m_twinEdge.lock()->ClearTwinEdge();
335  m_twinEdge.reset();
336  }
337  }
338 
339 protected:
340  NODE_PTR m_sourceNode;
341  EDGE_WEAK_PTR m_twinEdge;
343  unsigned int m_weight;
345 };
346 
347 
352 class EDGE_MST : public EDGE
353 {
354 private:
355  NODE_PTR m_target;
356 
357 public:
358  EDGE_MST( const NODE_PTR& aSource, const NODE_PTR& aTarget, unsigned int aWeight = 0 ) :
359  m_target( aTarget )
360  {
361  m_sourceNode = aSource;
362  m_weight = aWeight;
363  }
364 
366  virtual const NODE_PTR& GetTargetNode() const override
367  {
368  return m_target;
369  }
370 
371 private:
372  EDGE_MST( const EDGE& aEdge )
373  {
374  assert( false );
375  }
376 };
377 
378 class DART; // Forward declaration (class in this namespace)
379 
385 {
386 protected:
388  std::list<EDGE_PTR> m_leadingEdges;
389 
391 
392  void addLeadingEdge( EDGE_PTR& aEdge )
393  {
394  aEdge->SetAsLeadingEdge();
395  m_leadingEdges.push_front( aEdge );
396  }
397 
398  bool removeLeadingEdgeFromList( EDGE_PTR& aLeadingEdge );
399 
400  void cleanAll();
401 
420  void swapEdge( DART& aDart );
421 
433  void splitTriangle( DART& aDart, const NODE_PTR& aPoint );
434 
444  void reverseSplitTriangle( DART& aDart );
445 
450  void removeBoundaryTriangle( DART& aDart );
451 
452 public:
454  TRIANGULATION();
455 
457  TRIANGULATION( const TRIANGULATION& aTriangulation );
458 
460  ~TRIANGULATION();
461 
463  void CreateDelaunay( NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast );
464 
466  // When using rectangular boundary - loop through all points and expand.
467  // (Called from createDelaunay(...) when starting)
468  EDGE_PTR InitTwoEnclosingTriangles( NODES_CONTAINER::iterator aFirst,
469  NODES_CONTAINER::iterator aLast );
470 
471  // These two functions are required by TTL for Delaunay triangulation
472 
474  void SwapEdge( EDGE_PTR& aDiagonal );
475 
477  EDGE_PTR SplitTriangle( EDGE_PTR& aEdge, const NODE_PTR& aPoint );
478 
479  // Functions required by TTL for removing nodes in a Delaunay triangulation
480 
482  void RemoveTriangle( EDGE_PTR& aEdge ); // boundary triangle required
483 
485  void ReverseSplitTriangle( EDGE_PTR& aEdge );
486 
488  DART CreateDart();
489 
491  const std::list<EDGE_PTR>& GetLeadingEdges() const
492  {
493  return m_leadingEdges;
494  }
495 
497  int NoTriangles() const
498  {
499  return (int) m_leadingEdges.size();
500  }
501 
503  std::list<EDGE_PTR>* GetEdges( bool aSkipBoundaryEdges = false ) const;
504 
505 #ifdef TTL_USE_NODE_FLAG
506  void FlagNodes( bool aFlag ) const;
508 
510  std::list<NODE_PTR>* GetNodes() const;
511 #endif
512 
514  void OptimizeDelaunay();
515 
517  bool CheckDelaunay() const;
518 
520  EDGE_PTR GetInteriorNode() const;
521 
522  EDGE_PTR GetBoundaryEdgeInTriangle( const EDGE_PTR& aEdge ) const;
523 
525  EDGE_PTR GetBoundaryEdge() const;
526 
528  void PrintEdges( std::ofstream& aOutput ) const;
529 
531 };
532 }; // End of hed namespace
533 
534 #endif
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
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
int NoTriangles() const
Returns the number of triangles.
Definition: hetriang.h:497
int GetX() const
Returns the x-coordinate.
Definition: hetriang.h:139
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
int m_tag
Tag for quick connection resolution.
Definition: hetriang.h:107
~NODE()
Destructor.
Definition: hetriang.h:136
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
const NODE_PTR & GetSourceNode() const
Retuns the source node.
Definition: hetriang.h:306
void ClearTwinEdge()
Definition: hetriang.h:294
void SetNoLine(bool aEnable)
Decides whether this node can be a ratsnest line target.
Definition: hetriang.h:163
int GetY() const
Returns the y-coordinate.
Definition: hetriang.h:145
EDGE_PTR GetBoundaryEdge() const
Returns an arbitrary boundary edge.
Definition: hetriang.cpp:690
int GetTag() const
Returns tag, common identifier for connected nodes.
Definition: hetriang.h:249
const LSET & GetLayers()
Definition: hetriang.h:218
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
EDGE_MST(const EDGE &aEdge)
Definition: hetriang.h:372
unsigned int m_weight
Definition: hetriang.h:343
void addLeadingEdge(EDGE_PTR &aEdge)
Definition: hetriang.h:392
virtual ~EDGE()
Destructor.
Definition: hetriang.h:244
bool CheckDelaunay() const
Checks if the triangulation is Delaunay.
Definition: hetriang.cpp:563
Edge class in the in the half-edge data structure.
Definition: hetriang.h:235
bool removeLeadingEdgeFromList(EDGE_PTR &aLeadingEdge)
Definition: hetriang.cpp:303
Class LSET is a set of LAYER_IDs.
void ReverseSplitTriangle(EDGE_PTR &aEdge)
The reverse operation of removeTriangle.
Definition: hetriang.cpp:244
std::vector< NODE_PTR > NODES_CONTAINER
Definition: hetriang.h:75
std::shared_ptr< EDGE > EDGE_PTR
Definition: hetriang.h:73
void AddParent(const BOARD_CONNECTED_ITEM *aParent)
Definition: hetriang.h:201
const std::list< EDGE_PTR > & GetLeadingEdges() const
Returns a list of "triangles" (one leading half-edge for each triangle)
Definition: hetriang.h:491
EDGE_WEAK_PTR m_twinEdge
Definition: hetriang.h:341
unsigned int GetRefCount() const
Definition: hetriang.h:196
NODE_PTR m_target
Definition: hetriang.h:355
Main interface to TTL.
Definition: hetriang.h:59
Specialization of EDGE class to be used for Minimum Spanning Tree algorithm.
Definition: hetriang.h:352
void reverseSplitTriangle(DART &aDart)
The reverse operation of TTLtraits::splitTriangle.
Definition: hetriang.cpp:349
int GetTag() const
Returns tag, common identifier for connected nodes.
Definition: hetriang.h:151
void SetAsLeadingEdge(bool aLeading=true)
Sets the edge as a leading edge.
Definition: hetriang.h:277
bool IsLeadingEdge() const
Checks if an edge is a leading edge.
Definition: hetriang.h:283
EDGE_PTR GetTwinEdge() const
Returns the twin edge.
Definition: hetriang.h:289
void SetSourceNode(const NODE_PTR &aNode)
Sets the source node.
Definition: hetriang.h:259
void Clear()
Definition: hetriang.h:327
unsigned int GetWeight() const
Definition: hetriang.h:322
std::shared_ptr< NODE > NODE_PTR
Definition: hetriang.h:71
virtual const NODE_PTR & GetTargetNode() const override
Definition: hetriang.h:366
void SetTwinEdge(const EDGE_PTR &aEdge)
Sets the twin edge.
Definition: hetriang.h:271
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
void SetWeight(unsigned int weight)
Definition: hetriang.h:317
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()
Constructor.
Definition: hetriang.h:239
void SetTag(int aTag)
Sets tag, common identifier for connected nodes.
Definition: hetriang.h:157
static const int TAG_UNCONNECTED
Definition: hetriang.h:227
Board layer functions and definitions.
virtual const NODE_PTR & GetTargetNode() const
Returns the target node.
Definition: hetriang.h:312
void SetNextEdgeInFace(const EDGE_PTR &aEdge)
Sets the next edge in face.
Definition: hetriang.h:265
EDGE_MST(const NODE_PTR &aSource, const NODE_PTR &aTarget, unsigned int aWeight=0)
Definition: hetriang.h:358
const int m_y
Definition: hetriang.h:104
NODE(int aX=0, int aY=0)
Constructor.
Definition: hetriang.h:123
bool m_isLeadingEdge
Definition: hetriang.h:344
const EDGE_PTR & GetNextEdgeInFace() const
Returns the next edge in face.
Definition: hetriang.h:300
const bool & GetNoLine() const
Returns true if this node can be a target for ratsnest lines.
Definition: hetriang.h:169
Node class for data structures (Inherits from HandleId)
Definition: hetriang.h:87
const int m_x
Node coordinates.
Definition: hetriang.h:104
bool m_noline
Whether it the node can be a target for ratsnest lines.
Definition: hetriang.h:110
NODE_PTR m_sourceNode
Definition: hetriang.h:340
EDGE_PTR m_nextEdgeInFace
Definition: hetriang.h:342
void RemoveTriangle(EDGE_PTR &aEdge)
Removes the boundary triangle associated with edge.
Definition: hetriang.cpp:223
void RemoveParent(const BOARD_CONNECTED_ITEM *aParent)
Definition: hetriang.h:207
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
std::weak_ptr< EDGE > EDGE_WEAK_PTR
Definition: hetriang.h:74
EDGE_PTR InitTwoEnclosingTriangles(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates an initial Delaunay triangulation from two enclosing triangles.
Definition: hetriang.cpp:118