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