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<VECTOR2I> m_prevNodes;
165  std::vector<std::pair<int, int> > m_prevEdges;
166 
167  std::list<hed::EDGE_PTR> hedTriangulation( std::vector<hed::NODE_PTR>& aNodes )
168  {
169  hed::TRIANGULATION triangulator;
170  triangulator.CreateDelaunay( aNodes.begin(), aNodes.end() );
171  std::list<hed::EDGE_PTR> edges;
172  triangulator.GetEdges( edges );
173 
174  return edges;
175  }
176 
177 
178  std::list<hed::EDGE_PTR> computeTriangulation( std::vector<hed::NODE_PTR>& aNodes )
179  {
180  #if 0
181  bool refresh = false;
182  // we assume aNodes are sorted
183  VECTOR2I prevDelta;
184 
185  if ( aNodes.size() == m_prevNodes.size() )
186  {
187  for ( int i = 0; i < aNodes.size(); i++ )
188  {
189  const auto& a = aNodes[i];
190  const auto& b = m_prevNodes[i];
191 
192  const auto delta = a->Pos() - b;
193 
194  if ( i > 0 && delta != prevDelta )
195  {
196  refresh = true;
197  break;
198  }
199 
200  prevDelta = delta;
201  }
202  }
203 
204  if( refresh )
205  {
206  m_prevNodes.resize( aNodes.size() );
207 
208  for ( int i = 0; i < aNodes.size(); i++ )
209  {
210  m_prevNodes[i] = aNodes[i]->Pos();
211  }
212 
213  printf("need triang refresh\n");
214  auto edges = hedTriangulation( aNodes );
215 
216  m_prevEdges.resize( edges.size() );
217 
218  int i = 0;
219  for ( auto e : edges )
220  {
221  m_prevEdges[i].first = e->GetSourceNode()->Id();
222  m_prevEdges[i].second = e->GetTargetNode()->Id();
223  }
224 
225  }
226 
227 
228  #endif
229  return hedTriangulation( aNodes );
230  }
231 
232 public:
233 
234  void Clear()
235  {
236  m_allNodes.clear();
237  }
238 
239  void AddNode( CN_ANCHOR_PTR aNode )
240  {
241  m_allNodes.push_back( aNode );
242  }
243 
244  const std::list<CN_EDGE> Triangulate()
245  {
246  std::list<CN_EDGE> mstEdges;
247  std::list<hed::EDGE_PTR> triangEdges;
248  std::vector<hed::NODE_PTR> triNodes;
249 
250  using ANCHOR_LIST = std::vector<CN_ANCHOR_PTR>;
251  std::vector<ANCHOR_LIST> anchorChains;
252 
253  triNodes.reserve( m_allNodes.size() );
254  anchorChains.reserve( m_allNodes.size() );
255 
256  std::sort( m_allNodes.begin(), m_allNodes.end(),
257  [] ( const CN_ANCHOR_PTR& aNode1, const CN_ANCHOR_PTR& aNode2 )
258  {
259  if( aNode1->Pos().y < aNode2->Pos().y )
260  return true;
261  else if( aNode1->Pos().y == aNode2->Pos().y )
262  {
263  return aNode1->Pos().x < aNode2->Pos().x;
264  }
265 
266  return false;
267  }
268  );
269 
270  CN_ANCHOR_PTR prev, last;
271  int id = 0;
272 
273  for( auto n : m_allNodes )
274  {
275  anchorChains.push_back( ANCHOR_LIST() );
276  }
277 
278  for( auto n : m_allNodes )
279  {
280  if( !prev || prev->Pos() != n->Pos() )
281  {
282  auto tn = std::make_shared<hed::NODE> ( n->Pos().x, n->Pos().y );
283  tn->SetId( id );
284  triNodes.push_back( tn );
285  }
286 
287  id++;
288  prev = n;
289  }
290 
291  int prevId = 0;
292 
293  for( auto n : triNodes )
294  {
295  for( int i = prevId; i < n->Id(); i++ )
296  anchorChains[prevId].push_back( m_allNodes[ i ] );
297 
298  prevId = n->Id();
299  }
300 
301  for( int i = prevId; i < id; i++ )
302  anchorChains[prevId].push_back( m_allNodes[ i ] );
303 
304  if( triNodes.size() == 1 )
305  {
306  return mstEdges;
307  }
308  else if( triNodes.size() == 2 )
309  {
310  auto src = m_allNodes[ triNodes[0]->Id() ];
311  auto dst = m_allNodes[ triNodes[1]->Id() ];
312  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
313  }
314  else
315  {
316  hed::TRIANGULATION triangulator;
317  triangulator.CreateDelaunay( triNodes.begin(), triNodes.end() );
318 // std::list<hed::EDGE_PTR> edges;
319  triangulator.GetEdges( triangEdges );
320 
321  for( auto e : triangEdges )
322  {
323  auto src = m_allNodes[ e->GetSourceNode()->Id() ];
324  auto dst = m_allNodes[ e->GetTargetNode()->Id() ];
325 
326  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
327  }
328  }
329 
330  for( unsigned int i = 0; i < anchorChains.size(); i++ )
331  {
332  auto& chain = anchorChains[i];
333 
334  if( chain.size() < 2 )
335  continue;
336 
337  std::sort( chain.begin(), chain.end(),
338  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) {
339  return a->GetCluster().get() < b->GetCluster().get();
340  } );
341 
342  for( unsigned int j = 1; j < chain.size(); j++ )
343  {
344  const auto& prevNode = chain[j - 1];
345  const auto& curNode = chain[j];
346  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
347  mstEdges.push_back( CN_EDGE ( prevNode, curNode, weight ) );
348  }
349  }
350 
351  return mstEdges;
352  }
353 };
354 
355 
356 RN_NET::RN_NET() : m_dirty( true )
357 {
358  m_triangulator.reset( new TRIANGULATOR_STATE );
359 }
360 
361 
363 {
364  // Special cases do not need complicated algorithms (actually, it does not work well with
365  // the Delaunay triangulator)
366  //printf("compute nodes : %d\n", m_nodes.size() );
367  if( m_nodes.size() <= 2 )
368  {
369  m_rnEdges.clear();
370 
371  // Check if the only possible connection exists
372  if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
373  {
374  auto last = ++m_nodes.begin();
375 
376  // There can be only one possible connection, but it is missing
377  CN_EDGE edge (*m_nodes.begin(), *last );
378  edge.GetSourceNode()->SetTag( 0 );
379  edge.GetTargetNode()->SetTag( 1 );
380 
381  m_rnEdges.push_back( edge );
382  }
383  else
384  {
385  // Set tags to m_nodes as connected
386  for( auto node : m_nodes )
387  node->SetTag( 0 );
388  }
389 
390  return;
391  }
392 
393 
394  m_triangulator->Clear();
395 
396  for( auto n : m_nodes )
397  {
398  m_triangulator->AddNode( n );
399  }
400 
401  #ifdef PROFILE
402  PROF_COUNTER cnt("triangulate");
403  #endif
404  auto triangEdges = m_triangulator->Triangulate();
405  #ifdef PROFILE
406  cnt.Show();
407  #endif
408 
409  for( const auto& e : m_boardEdges )
410  triangEdges.push_back( e );
411 
412 // Get the minimal spanning tree
413 #ifdef PROFILE
414  PROF_COUNTER cnt2("mst");
415 #endif
416  m_rnEdges = kruskalMST( triangEdges, m_nodes );
417 #ifdef PROFILE
418  cnt2.Show();
419 #endif
420 }
421 
422 
423 
425 {
426  compute();
427 
428  m_dirty = false;
429 }
430 
431 
433 {
434  m_rnEdges.clear();
435  m_boardEdges.clear();
436  m_nodes.clear();
437 
438  m_dirty = true;
439 }
440 
441 
443 {
444  CN_ANCHOR_PTR firstAnchor;
445 
446  for( auto item : *aCluster )
447  {
448  bool isZone = dynamic_cast<CN_ZONE*>(item) != nullptr;
449  auto& anchors = item->Anchors();
450  unsigned int nAnchors = isZone ? 1 : anchors.size();
451 
452  if( nAnchors > anchors.size() )
453  nAnchors = anchors.size();
454 
455  //printf("item %p anchors : %d\n", item, anchors.size() );
456  //printf("add item %p anchors : %d net : %d\n", item, item->Anchors().size(), item->Parent()->GetNetCode() );
457 
458  for( unsigned int i = 0; i < nAnchors; i++ )
459  {
460  // printf("add anchor %p\n", anchors[i].get() );
461 
462  anchors[i]->SetCluster( aCluster );
463  m_nodes.push_back(anchors[i]);
464 
465  if( firstAnchor )
466  {
467  if( firstAnchor != anchors[i] )
468  {
469  m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
470  }
471  }
472  else
473  {
474  firstAnchor = anchors[i];
475  }
476  }
477  }
478 }
479 
480 
481 bool RN_NET::NearestBicoloredPair( const RN_NET& aOtherNet, CN_ANCHOR_PTR& aNode1,
482  CN_ANCHOR_PTR& aNode2 ) const
483 {
484  bool rv = false;
485 
487 
488  for( auto nodeA : m_nodes )
489  {
490  for( auto nodeB : aOtherNet.m_nodes )
491  {
492  if( !nodeA->GetNoLine() )
493  {
494  auto squaredDist = (nodeA->Pos() - nodeB->Pos() ).SquaredEuclideanNorm();
495 
496  if( squaredDist < distMax )
497  {
498  rv = true;
499  distMax = squaredDist;
500  aNode1 = nodeA;
501  aNode2 = nodeB;
502  }
503  }
504  }
505  }
506 
507  return rv;
508 }
509 
510 
511 void RN_NET::SetVisible( bool aEnabled )
512 {
513  for( auto& edge : m_rnEdges )
514  edge.SetVisible( aEnabled );
515 }
std::vector< CN_ANCHOR_PTR > m_allNodes
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:77
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
std::list< hed::EDGE_PTR > computeTriangulation(std::vector< hed::NODE_PTR > &aNodes)
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
static const int delta[8][2]
Definition: solve.cpp:112
std::vector< CN_ANCHOR_PTR > m_nodes
Vector of nodes
void AddNode(CN_ANCHOR_PTR aNode)
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
RN_NET()
Default constructor.
std::list< hed::EDGE_PTR > hedTriangulation(std::vector< hed::NODE_PTR > &aNodes)
void Clear()
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
std::vector< VECTOR2I > m_prevNodes
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
std::vector< std::pair< int, int > > m_prevEdges