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 PROFILE
32 #include <profile.h>
33 #endif
34 
35 #include <ratsnest_data.h>
36 #include <functional>
37 using namespace std::placeholders;
38 
39 #include <cassert>
40 #include <algorithm>
41 #include <limits>
42 
43 static uint64_t getDistance( const CN_ANCHOR_PTR& aNode1, const CN_ANCHOR_PTR& aNode2 )
44 {
45  double dx = ( aNode1->Pos().x - aNode2->Pos().x );
46  double dy = ( aNode1->Pos().y - aNode2->Pos().y );
47 
48  return sqrt( dx * dx + dy * dy );
49 }
50 
51 
52 static bool sortWeight( const CN_EDGE& aEdge1, const CN_EDGE& aEdge2 )
53 {
54  return aEdge1.GetWeight() < aEdge2.GetWeight();
55 }
56 
57 
58 static const std::vector<CN_EDGE> kruskalMST( std::list<CN_EDGE>& aEdges,
59  std::vector<CN_ANCHOR_PTR>& aNodes )
60 {
61  unsigned int nodeNumber = aNodes.size();
62  unsigned int mstExpectedSize = nodeNumber - 1;
63  unsigned int mstSize = 0;
64  bool ratsnestLines = false;
65 
66  // The output
67  std::vector<CN_EDGE> mst;
68 
69  // Set tags for marking cycles
70  std::unordered_map<CN_ANCHOR_PTR, int> tags;
71  unsigned int tag = 0;
72 
73  for( auto& node : aNodes )
74  {
75  node->SetTag( tag );
76  tags[node] = tag++;
77  }
78 
79  // Lists of nodes connected together (subtrees) to detect cycles in the graph
80  std::vector<std::list<int> > cycles( nodeNumber );
81 
82  for( unsigned int i = 0; i < nodeNumber; ++i )
83  cycles[i].push_back( i );
84 
85  // Kruskal algorithm requires edges to be sorted by their weight
86  aEdges.sort( sortWeight );
87 
88  while( mstSize < mstExpectedSize && !aEdges.empty() )
89  {
90  //printf("mstSize %d %d\n", mstSize, mstExpectedSize);
91  auto& dt = aEdges.front();
92 
93  int srcTag = tags[dt.GetSourceNode()];
94  int trgTag = tags[dt.GetTargetNode()];
95 
96  // Check if by adding this edge we are going to join two different forests
97  if( srcTag != trgTag )
98  {
99  // Because edges are sorted by their weight, first we always process connected
100  // items (weight == 0). Once we stumble upon an edge with non-zero weight,
101  // it means that the rest of the lines are ratsnest.
102  if( !ratsnestLines && dt.GetWeight() != 0 )
103  ratsnestLines = true;
104 
105  // Update tags
106  if( ratsnestLines )
107  {
108  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
109  {
110  tags[aNodes[*it]] = srcTag;
111  }
112 
113  // Do a copy of edge, but make it RN_EDGE_MST. In contrary to RN_EDGE,
114  // RN_EDGE_MST saves both source and target node and does not require any other
115  // edges to exist for getting source/target nodes
116  CN_EDGE newEdge ( dt.GetSourceNode(), dt.GetTargetNode(), dt.GetWeight() );
117 
118  assert( newEdge.GetSourceNode()->GetTag() != newEdge.GetTargetNode()->GetTag() );
119  assert( newEdge.GetWeight() > 0 );
120 
121  mst.push_back( newEdge );
122  ++mstSize;
123  }
124  else
125  {
126  // for( it = cycles[trgTag].begin(), itEnd = cycles[trgTag].end(); it != itEnd; ++it )
127  // for( auto it : cycles[trgTag] )
128  for( auto it = cycles[trgTag].begin(); it != cycles[trgTag].end(); ++it )
129  {
130  tags[aNodes[*it]] = srcTag;
131  aNodes[*it]->SetTag( srcTag );
132  }
133 
134  // Processing a connection, decrease the expected size of the ratsnest MST
135  --mstExpectedSize;
136  }
137 
138  // Move nodes that were marked with old tag to the list marked with the new tag
139  cycles[srcTag].splice( cycles[srcTag].end(), cycles[trgTag] );
140  }
141 
142  // Remove the edge that was just processed
143  aEdges.erase( aEdges.begin() );
144  }
145 
146  // Probably we have discarded some of edges, so reduce the size
147  mst.resize( mstSize );
148 
149  return mst;
150 }
151 
152 
154 {
155 private:
156  std::vector<CN_ANCHOR_PTR> m_allNodes;
157 
158  std::list<hed::EDGE_PTR> hedTriangulation( std::vector<hed::NODE_PTR>& aNodes )
159  {
160  hed::TRIANGULATION triangulator;
161  triangulator.CreateDelaunay( aNodes.begin(), aNodes.end() );
162  std::list<hed::EDGE_PTR> edges;
163  triangulator.GetEdges( edges );
164 
165  return edges;
166  }
167 
168 
169  // Checks if all nodes in aNodes lie on a single line. Requires the nodes to
170  // have unique coordinates!
171  bool areNodesColinear( const std::vector<hed::NODE_PTR>& aNodes ) const
172  {
173  if ( aNodes.size() <= 2 )
174  return true;
175 
176  const auto p0 = aNodes[0]->Pos();
177  const auto v0 = aNodes[1]->Pos() - p0;
178 
179  for( unsigned i = 2; i < aNodes.size(); i++ )
180  {
181  const auto v1 = aNodes[i]->Pos() - p0;
182 
183  if( v0.Cross( v1 ) != 0 )
184  {
185  return false;
186  }
187  }
188 
189  return true;
190  }
191 
192 public:
193 
194  void Clear()
195  {
196  m_allNodes.clear();
197  }
198 
199  void AddNode( CN_ANCHOR_PTR aNode )
200  {
201  m_allNodes.push_back( aNode );
202  }
203 
204  const std::list<CN_EDGE> Triangulate()
205  {
206  std::list<CN_EDGE> mstEdges;
207  std::list<hed::EDGE_PTR> triangEdges;
208  std::vector<hed::NODE_PTR> triNodes;
209 
210  using ANCHOR_LIST = std::vector<CN_ANCHOR_PTR>;
211  std::vector<ANCHOR_LIST> anchorChains;
212 
213  triNodes.reserve( m_allNodes.size() );
214  anchorChains.resize( m_allNodes.size() );
215 
216  std::sort( m_allNodes.begin(), m_allNodes.end(),
217  [] ( const CN_ANCHOR_PTR& aNode1, const CN_ANCHOR_PTR& aNode2 )
218  {
219  if( aNode1->Pos().y < aNode2->Pos().y )
220  return true;
221  else if( aNode1->Pos().y == aNode2->Pos().y )
222  {
223  return aNode1->Pos().x < aNode2->Pos().x;
224  }
225 
226  return false;
227  }
228  );
229 
230  CN_ANCHOR_PTR prev, last;
231  int id = 0;
232 
233  for( const auto& n : m_allNodes )
234  {
235  if( !prev || prev->Pos() != n->Pos() )
236  {
237  auto tn = std::make_shared<hed::NODE> ( n->Pos().x, n->Pos().y );
238 
239  tn->SetId( id );
240  triNodes.push_back( tn );
241  }
242 
243  id++;
244  prev = n;
245  }
246 
247  int prevId = 0;
248 
249  for( const auto& n : triNodes )
250  {
251  for( int i = prevId; i < n->Id(); i++ )
252  anchorChains[prevId].push_back( m_allNodes[ i ] );
253 
254  prevId = n->Id();
255  }
256 
257  for( int i = prevId; i < id; i++ )
258  anchorChains[prevId].push_back( m_allNodes[ i ] );
259 
260  if( triNodes.size() == 1 )
261  {
262  return mstEdges;
263  }
264  else if( areNodesColinear( triNodes ) )
265  {
266  // special case: all nodes are on the same line - there's no
267  // triangulation for such set. In this case, we sort along any coordinate
268  // and chain the nodes together.
269  for(int i = 0; i < (int)triNodes.size() - 1; i++ )
270  {
271  auto src = m_allNodes[ triNodes[i]->Id() ];
272  auto dst = m_allNodes[ triNodes[i + 1]->Id() ];
273  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
274  }
275  }
276  else
277  {
278  hed::TRIANGULATION triangulator;
279  triangulator.CreateDelaunay( triNodes.begin(), triNodes.end() );
280  triangulator.GetEdges( triangEdges );
281 
282  for( const auto& e : triangEdges )
283  {
284  auto src = m_allNodes[ e->GetSourceNode()->Id() ];
285  auto dst = m_allNodes[ e->GetTargetNode()->Id() ];
286 
287  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
288  }
289  }
290 
291  for( unsigned int i = 0; i < anchorChains.size(); i++ )
292  {
293  auto& chain = anchorChains[i];
294 
295  if( chain.size() < 2 )
296  continue;
297 
298  std::sort( chain.begin(), chain.end(),
299  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) {
300  return a->GetCluster().get() < b->GetCluster().get();
301  } );
302 
303  for( unsigned int j = 1; j < chain.size(); j++ )
304  {
305  const auto& prevNode = chain[j - 1];
306  const auto& curNode = chain[j];
307  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
308  mstEdges.emplace_back( prevNode, curNode, weight );
309  }
310  }
311 
312  return mstEdges;
313  }
314 };
315 
316 
317 RN_NET::RN_NET() : m_dirty( true )
318 {
319  m_triangulator.reset( new TRIANGULATOR_STATE );
320 }
321 
322 
324 {
325  // Special cases do not need complicated algorithms (actually, it does not work well with
326  // the Delaunay triangulator)
327  if( m_nodes.size() <= 2 )
328  {
329  m_rnEdges.clear();
330 
331  // Check if the only possible connection exists
332  if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
333  {
334  auto last = ++m_nodes.begin();
335 
336  // There can be only one possible connection, but it is missing
337  CN_EDGE edge (*m_nodes.begin(), *last );
338  edge.GetSourceNode()->SetTag( 0 );
339  edge.GetTargetNode()->SetTag( 1 );
340 
341  m_rnEdges.push_back( edge );
342  }
343  else
344  {
345  // Set tags to m_nodes as connected
346  for( const auto& node : m_nodes )
347  node->SetTag( 0 );
348  }
349 
350  return;
351  }
352 
353 
354  m_triangulator->Clear();
355 
356  for( const auto& n : m_nodes )
357  {
358  m_triangulator->AddNode( n );
359  }
360 
361  #ifdef PROFILE
362  PROF_COUNTER cnt("triangulate");
363  #endif
364  auto triangEdges = m_triangulator->Triangulate();
365  #ifdef PROFILE
366  cnt.Show();
367  #endif
368 
369  for( const auto& e : m_boardEdges )
370  triangEdges.push_back( e );
371 
372 // Get the minimal spanning tree
373 #ifdef PROFILE
374  PROF_COUNTER cnt2("mst");
375 #endif
376  m_rnEdges = kruskalMST( triangEdges, m_nodes );
377 #ifdef PROFILE
378  cnt2.Show();
379 #endif
380 }
381 
382 
383 
385 {
386  compute();
387 
388  m_dirty = false;
389 }
390 
391 
393 {
394  m_rnEdges.clear();
395  m_boardEdges.clear();
396  m_nodes.clear();
397 
398  m_dirty = true;
399 }
400 
401 
403 {
404  CN_ANCHOR_PTR firstAnchor;
405 
406  for( auto item : *aCluster )
407  {
408  bool isZone = dynamic_cast<CN_ZONE*>(item) != nullptr;
409  auto& anchors = item->Anchors();
410  unsigned int nAnchors = isZone ? 1 : anchors.size();
411 
412  if( nAnchors > anchors.size() )
413  nAnchors = anchors.size();
414 
415  for( unsigned int i = 0; i < nAnchors; i++ )
416  {
417  anchors[i]->SetCluster( aCluster );
418  m_nodes.push_back(anchors[i]);
419 
420  if( firstAnchor )
421  {
422  if( firstAnchor != anchors[i] )
423  {
424  m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
425  }
426  }
427  else
428  {
429  firstAnchor = anchors[i];
430  }
431  }
432  }
433 }
434 
435 
436 bool RN_NET::NearestBicoloredPair( const RN_NET& aOtherNet, CN_ANCHOR_PTR& aNode1,
437  CN_ANCHOR_PTR& aNode2 ) const
438 {
439  bool rv = false;
440 
442 
443  for( const auto& nodeA : m_nodes )
444  {
445  for( const auto& nodeB : aOtherNet.m_nodes )
446  {
447  if( !nodeA->GetNoLine() )
448  {
449  auto squaredDist = (nodeA->Pos() - nodeB->Pos() ).SquaredEuclideanNorm();
450 
451  if( squaredDist < distMax )
452  {
453  rv = true;
454  distMax = squaredDist;
455  aNode1 = nodeA;
456  aNode2 = nodeB;
457  }
458  }
459  }
460  }
461 
462  return rv;
463 }
464 
465 
466 void RN_NET::SetVisible( bool aEnabled )
467 {
468  for( auto& edge : m_rnEdges )
469  edge.SetVisible( aEnabled );
470 }
std::vector< CN_ANCHOR_PTR > m_allNodes
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:77
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)
int GetWeight() const
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.
The class PROF_COUNTER is a small class to help profiling.
Definition: profile.h:44
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)
void SetVisible(bool aEnabled)
Function SetVisible() Sets state of the visibility flag.
bool NearestBicoloredPair(const RN_NET &aOtherNet, CN_ANCHOR_PTR &aNode1, CN_ANCHOR_PTR &aNode2) const
void AddCluster(std::shared_ptr< CN_CLUSTER > aCluster)
std::shared_ptr< TRIANGULATOR_STATE > m_triangulator
std::vector< CN_EDGE > m_boardEdges
Vector of edges that make pre-defined connections
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
RN_NET Describes ratsnest for a single net.
Definition: ratsnest_data.h:59
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
Definition: profile.h:99
static uint64_t getDistance(const CN_ANCHOR_PTR &aNode1, const CN_ANCHOR_PTR &aNode2)
bool areNodesColinear(const std::vector< hed::NODE_PTR > &aNodes) const
CN_ANCHOR_PTR GetSourceNode() const