KiCad PCB EDA Suite
ratsnest_data.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KICAD, a free EDA CAD application.
3  *
4  * Copyright (C) 2013-2017 CERN
5  * @author Maciej Suminski <maciej.suminski@cern.ch>
6  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
31 #ifdef USE_OPENMP
32 #include <omp.h>
33 #endif /* USE_OPENMP */
34 
35 #ifdef PROFILE
36 #include <profile.h>
37 #endif
38 
39 #include <ratsnest_data.h>
40 #include <functional>
41 using namespace std::placeholders;
42 
43 #include <cassert>
44 #include <algorithm>
45 #include <limits>
46 
47 #include <connectivity_algo.h>
48 
49 static uint64_t getDistance( const CN_ANCHOR_PTR& aNode1, const CN_ANCHOR_PTR& aNode2 )
50 {
51  double dx = ( aNode1->Pos().x - aNode2->Pos().x );
52  double dy = ( aNode1->Pos().y - aNode2->Pos().y );
53 
54  return sqrt( dx * dx + dy * dy );
55 }
56 
57 
58 static bool sortWeight( const CN_EDGE& aEdge1, const CN_EDGE& aEdge2 )
59 {
60  return aEdge1.GetWeight() < aEdge2.GetWeight();
61 }
62 
63 
64 static const std::vector<CN_EDGE> kruskalMST( std::list<CN_EDGE>& aEdges,
65  std::vector<CN_ANCHOR_PTR>& aNodes )
66 {
67  unsigned int nodeNumber = aNodes.size();
68  unsigned int mstExpectedSize = nodeNumber - 1;
69  unsigned int mstSize = 0;
70  bool ratsnestLines = false;
71 
72  //printf("mst nodes : %d edges : %d\n", aNodes.size(), aEdges.size () );
73  // The output
74  std::vector<CN_EDGE> mst;
75 
76  // Set tags for marking cycles
77  std::unordered_map<CN_ANCHOR_PTR, int> tags;
78  unsigned int tag = 0;
79 
80  for( auto& node : aNodes )
81  {
82  node->SetTag( tag );
83  tags[node] = tag++;
84  }
85 
86  // Lists of nodes connected together (subtrees) to detect cycles in the graph
87  std::vector<std::list<int> > cycles( nodeNumber );
88 
89  for( unsigned int i = 0; i < nodeNumber; ++i )
90  cycles[i].push_back( i );
91 
92  // Kruskal algorithm requires edges to be sorted by their weight
93  aEdges.sort( sortWeight );
94 
95  while( mstSize < mstExpectedSize && !aEdges.empty() )
96  {
97  //printf("mstSize %d %d\n", mstSize, mstExpectedSize);
98  auto& dt = aEdges.front();
99 
100  int srcTag = tags[dt.GetSourceNode()];
101  int trgTag = tags[dt.GetTargetNode()];
102 
103  // Check if by adding this edge we are going to join two different forests
104  if( srcTag != trgTag )
105  {
106  // Because edges are sorted by their weight, first we always process connected
107  // items (weight == 0). Once we stumble upon an edge with non-zero weight,
108  // it means that the rest of the lines are ratsnest.
109  if( !ratsnestLines && dt.GetWeight() != 0 )
110  ratsnestLines = true;
111 
112  // Update tags
113  if( ratsnestLines )
114  {
115  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
116  {
117  tags[aNodes[*it]] = srcTag;
118  }
119 
120  // Do a copy of edge, but make it RN_EDGE_MST. In contrary to RN_EDGE,
121  // RN_EDGE_MST saves both source and target node and does not require any other
122  // edges to exist for getting source/target nodes
123  CN_EDGE newEdge ( dt.GetSourceNode(), dt.GetTargetNode(), dt.GetWeight() );
124 
125  assert( newEdge.GetSourceNode()->GetTag() != newEdge.GetTargetNode()->GetTag() );
126  assert( newEdge.GetWeight() > 0 );
127 
128  mst.push_back( newEdge );
129  ++mstSize;
130  }
131  else
132  {
133  // for( it = cycles[trgTag].begin(), itEnd = cycles[trgTag].end(); it != itEnd; ++it )
134  // for( auto it : cycles[trgTag] )
135  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
136  {
137  tags[aNodes[*it]] = srcTag;
138  aNodes[*it]->SetTag( srcTag );
139  }
140 
141  // Processing a connection, decrease the expected size of the ratsnest MST
142  --mstExpectedSize;
143  }
144 
145  // Move nodes that were marked with old tag to the list marked with the new tag
146  cycles[srcTag].splice( cycles[srcTag].end(), cycles[trgTag] );
147  }
148 
149  // Remove the edge that was just processed
150  aEdges.erase( aEdges.begin() );
151  }
152 
153  // Probably we have discarded some of edges, so reduce the size
154  mst.resize( mstSize );
155 
156  return mst;
157 }
158 
159 
161 {
162 private:
163  std::vector<CN_ANCHOR_PTR> m_allNodes;
164  std::vector<hed::NODE_PTR> m_triangulationNodes;
165 
166 public:
167 
168  void Clear()
169  {
170  m_allNodes.clear();
171  }
172 
173  void AddNode( CN_ANCHOR_PTR aNode )
174  {
175  m_allNodes.push_back( aNode );
176  }
177 
178  const std::list<CN_EDGE> Triangulate()
179  {
180  std::list<CN_EDGE> mstEdges;
181  std::list<hed::EDGE_PTR> triangEdges;
182  std::vector<hed::NODE_PTR> triNodes;
183 
184  using ANCHOR_LIST = std::vector<CN_ANCHOR_PTR>;
185  std::vector<ANCHOR_LIST> anchorChains;
186 
187  triNodes.reserve( m_allNodes.size() );
188  anchorChains.reserve( m_allNodes.size() );
189 
190  std::sort( m_allNodes.begin(), m_allNodes.end(),
191  [] ( const CN_ANCHOR_PTR& aNode1, const CN_ANCHOR_PTR& aNode2 )
192  {
193  if( aNode1->Pos().y < aNode2->Pos().y )
194  return true;
195  else if( aNode1->Pos().y == aNode2->Pos().y )
196  {
197  return aNode1->Pos().x < aNode2->Pos().x;
198  }
199 
200  return false;
201  }
202  );
203 
204  CN_ANCHOR_PTR prev, last;
205  int id = 0;
206 
207  for( auto n : m_allNodes )
208  {
209  anchorChains.push_back( ANCHOR_LIST() );
210  }
211 
212  for( auto n : m_allNodes )
213  {
214  if( !prev || prev->Pos() != n->Pos() )
215  {
216  auto tn = std::make_shared<hed::NODE> ( n->Pos().x, n->Pos().y );
217  tn->SetId( id );
218  triNodes.push_back( tn );
219  }
220 
221  id++;
222  prev = n;
223  }
224 
225  int prevId = 0;
226 
227  for( auto n : triNodes )
228  {
229  for( int i = prevId; i < n->Id(); i++ )
230  anchorChains[prevId].push_back( m_allNodes[ i ] );
231 
232  prevId = n->Id();
233  }
234 
235  for( int i = prevId; i < id; i++ )
236  anchorChains[prevId].push_back( m_allNodes[ i ] );
237 
238 
239  hed::TRIANGULATION triangulator;
240  triangulator.CreateDelaunay( triNodes.begin(), triNodes.end() );
241  triangulator.GetEdges( triangEdges );
242 
243  for( auto e : triangEdges )
244  {
245  auto src = m_allNodes[ e->GetSourceNode()->Id() ];
246  auto dst = m_allNodes[ e->GetTargetNode()->Id() ];
247 
248  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
249  }
250 
251  for( unsigned int i = 0; i < anchorChains.size(); i++ )
252  {
253  auto& chain = anchorChains[i];
254 
255  if( chain.size() < 2 )
256  continue;
257 
258  std::sort( chain.begin(), chain.end(),
259  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) {
260  return a->GetCluster().get() < b->GetCluster().get();
261  } );
262 
263  for( unsigned int j = 1; j < chain.size(); j++ )
264  {
265  const auto& prevNode = chain[j - 1];
266  const auto& curNode = chain[j];
267  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
268  mstEdges.push_back( CN_EDGE ( prevNode, curNode, weight ) );
269  }
270  }
271 
272  return mstEdges;
273  }
274 };
275 
276 
277 RN_NET::RN_NET() : m_dirty( true )
278 {
279  m_triangulator.reset( new TRIANGULATOR_STATE );
280 }
281 
282 
284 {
285  // Special cases do not need complicated algorithms (actually, it does not work well with
286  // the Delaunay triangulator)
287  //printf("compute nodes : %d\n", m_nodes.size() );
288  if( m_nodes.size() <= 2 )
289  {
290  m_rnEdges.clear();
291 
292  // Check if the only possible connection exists
293  if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
294  {
295  auto last = ++m_nodes.begin();
296 
297  // There can be only one possible connection, but it is missing
298  CN_EDGE edge (*m_nodes.begin(), *last );
299  edge.GetSourceNode()->SetTag( 0 );
300  edge.GetTargetNode()->SetTag( 1 );
301 
302  m_rnEdges.push_back( edge );
303  }
304  else
305  {
306  // Set tags to m_nodes as connected
307  for( auto node : m_nodes )
308  node->SetTag( 0 );
309  }
310 
311  return;
312  }
313 
314 
315  m_triangulator->Clear();
316 
317  for( auto n : m_nodes )
318  {
319  m_triangulator->AddNode( n );
320  }
321 
322  #ifdef PROFILE
323  PROF_COUNTER cnt("triangulate");
324  #endif
325  auto triangEdges = m_triangulator->Triangulate();
326  #ifdef PROFILE
327  cnt.Show();
328  #endif
329 
330  for( const auto& e : m_boardEdges )
331  triangEdges.push_back( e );
332 
333 // Get the minimal spanning tree
334 #ifdef PROFILE
335  PROF_COUNTER cnt2("mst");
336 #endif
337  m_rnEdges = kruskalMST( triangEdges, m_nodes );
338 #ifdef PROFILE
339  cnt2.Show();
340 #endif
341 }
342 
343 
344 
346 {
347  compute();
348 
349  m_dirty = false;
350 }
351 
352 
354 {
355  m_rnEdges.clear();
356  m_boardEdges.clear();
357  m_nodes.clear();
358 
359  m_dirty = true;
360 }
361 
362 
364 {
365  CN_ANCHOR_PTR firstAnchor;
366 
367  for( auto item : *aCluster )
368  {
369  bool isZone = dynamic_cast<CN_ZONE*>(item) != nullptr;
370  auto& anchors = item->Anchors();
371  unsigned int nAnchors = isZone ? 1 : anchors.size();
372 
373  if( nAnchors > anchors.size() )
374  nAnchors = anchors.size();
375 
376  //printf("item %p anchors : %d\n", item, anchors.size() );
377  //printf("add item %p anchors : %d net : %d\n", item, item->Anchors().size(), item->Parent()->GetNetCode() );
378 
379  for( unsigned int i = 0; i < nAnchors; i++ )
380  {
381  // printf("add anchor %p\n", anchors[i].get() );
382 
383  anchors[i]->SetCluster( aCluster );
384  m_nodes.push_back(anchors[i]);
385 
386  if( firstAnchor )
387  {
388  if( firstAnchor != anchors[i] )
389  {
390  m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
391  }
392  }
393  else
394  {
395  firstAnchor = anchors[i];
396  }
397  }
398  }
399 }
400 
401 
402 bool RN_NET::NearestBicoloredPair( const RN_NET& aOtherNet, CN_ANCHOR_PTR& aNode1,
403  CN_ANCHOR_PTR& aNode2 ) const
404 {
405  bool rv = false;
406 
408 
409  for( auto nodeA : m_nodes )
410  {
411  for( auto nodeB : aOtherNet.m_nodes )
412  {
413  if( !nodeA->GetNoLine() )
414  {
415  auto squaredDist = (nodeA->Pos() - nodeB->Pos() ).SquaredEuclideanNorm();
416 
417  if( squaredDist < distMax )
418  {
419  rv = true;
420  distMax = squaredDist;
421  aNode1 = nodeA;
422  aNode2 = nodeB;
423  }
424  }
425  }
426  }
427 
428  return rv;
429 }
430 
431 
432 void RN_NET::SetVisible( bool aEnabled )
433 {
434  for( auto& edge : m_rnEdges )
435  edge.SetVisible( aEnabled );
436 }
std::vector< CN_ANCHOR_PTR > m_allNodes
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:81
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
void Update()
Function Update() Recomputes ratsnest for a net.
const std::list< CN_EDGE > Triangulate()
static bool sortWeight(const CN_EDGE &aEdge1, const CN_EDGE &aEdge2)
bool m_dirty
Flag indicating necessity of recalculation of ratsnest for a net.
Class that computes missing connections on a PCB.
std::vector< CN_EDGE > m_rnEdges
Vector of edges that makes ratsnest for a given net.
void compute()
Recomputes ratsnest from scratch.
void Show()
Print the elapsed time (in ms) to STDERR.
Definition: profile.h:93
CN_ANCHORS & Anchors()
The class PROF_COUNTER is a small class to help profiling.
Definition: profile.h:45
std::vector< CN_ANCHOR_PTR > m_nodes
Vector of nodes
void AddNode(CN_ANCHOR_PTR aNode)
RN_NET()
Default constructor.
static const extended_type ECOORD_MAX
Definition: vector2d.h:59
void Clear()
std::vector< hed::NODE_PTR > m_triangulationNodes
static const std::vector< CN_EDGE > kruskalMST(std::list< CN_EDGE > &aEdges, std::vector< CN_ANCHOR_PTR > &aNodes)
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
void SetVisible(bool aEnabled)
Function SetVisible() Sets state of the visibility flag.
void AddCluster(std::shared_ptr< CN_CLUSTER > aCluster)
void CreateDelaunay(NODES_CONTAINER::iterator aFirst, NODES_CONTAINER::iterator aLast)
Creates a Delaunay triangulation from a set of points.
Definition: hetriang.cpp:187
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator
std::vector< CN_EDGE > m_boardEdges
Vector of edges that make pre-defined connections
bool NearestBicoloredPair(const RN_NET &aOtherNet, CN_ANCHOR_PTR &aNode1, CN_ANCHOR_PTR &aNode2) const
int GetWeight() const
Class RN_NET Describes ratsnest for a single net.
Definition: ratsnest_data.h:59
CN_ANCHOR_PTR GetSourceNode() const
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
static uint64_t getDistance(const CN_ANCHOR_PTR &aNode1, const CN_ANCHOR_PTR &aNode2)
Triangulation class for the half-edge data structure with adaption to TTL.
Definition: hetriang.h:281