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.reserve( 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( auto n : m_allNodes )
234  {
235  anchorChains.push_back( ANCHOR_LIST() );
236  }
237 
238  for( auto n : m_allNodes )
239  {
240  if( !prev || prev->Pos() != n->Pos() )
241  {
242  auto tn = std::make_shared<hed::NODE> ( n->Pos().x, n->Pos().y );
243 
244  tn->SetId( id );
245  triNodes.push_back( tn );
246  }
247 
248  id++;
249  prev = n;
250  }
251 
252  int prevId = 0;
253 
254  for( auto n : triNodes )
255  {
256  for( int i = prevId; i < n->Id(); i++ )
257  anchorChains[prevId].push_back( m_allNodes[ i ] );
258 
259  prevId = n->Id();
260  }
261 
262  for( int i = prevId; i < id; i++ )
263  anchorChains[prevId].push_back( m_allNodes[ i ] );
264 
265  if( triNodes.size() == 1 )
266  {
267  return mstEdges;
268  }
269  else if( areNodesColinear( triNodes ) )
270  {
271  // special case: all nodes are on the same line - there's no
272  // triangulation for such set. In this case, we sort along any coordinate
273  // and chain the nodes together.
274  for(int i = 0; i < (int)triNodes.size() - 1; i++ )
275  {
276  auto src = m_allNodes[ triNodes[i]->Id() ];
277  auto dst = m_allNodes[ triNodes[i + 1]->Id() ];
278  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
279  }
280  }
281  else
282  {
283  hed::TRIANGULATION triangulator;
284  triangulator.CreateDelaunay( triNodes.begin(), triNodes.end() );
285  triangulator.GetEdges( triangEdges );
286 
287  for( auto e : triangEdges )
288  {
289  auto src = m_allNodes[ e->GetSourceNode()->Id() ];
290  auto dst = m_allNodes[ e->GetTargetNode()->Id() ];
291 
292  mstEdges.emplace_back( src, dst, getDistance( src, dst ) );
293  }
294  }
295 
296  for( unsigned int i = 0; i < anchorChains.size(); i++ )
297  {
298  auto& chain = anchorChains[i];
299 
300  if( chain.size() < 2 )
301  continue;
302 
303  std::sort( chain.begin(), chain.end(),
304  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) {
305  return a->GetCluster().get() < b->GetCluster().get();
306  } );
307 
308  for( unsigned int j = 1; j < chain.size(); j++ )
309  {
310  const auto& prevNode = chain[j - 1];
311  const auto& curNode = chain[j];
312  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
313  mstEdges.push_back( CN_EDGE ( prevNode, curNode, weight ) );
314  }
315  }
316 
317  return mstEdges;
318  }
319 };
320 
321 
322 RN_NET::RN_NET() : m_dirty( true )
323 {
324  m_triangulator.reset( new TRIANGULATOR_STATE );
325 }
326 
327 
329 {
330  // Special cases do not need complicated algorithms (actually, it does not work well with
331  // the Delaunay triangulator)
332  if( m_nodes.size() <= 2 )
333  {
334  m_rnEdges.clear();
335 
336  // Check if the only possible connection exists
337  if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
338  {
339  auto last = ++m_nodes.begin();
340 
341  // There can be only one possible connection, but it is missing
342  CN_EDGE edge (*m_nodes.begin(), *last );
343  edge.GetSourceNode()->SetTag( 0 );
344  edge.GetTargetNode()->SetTag( 1 );
345 
346  m_rnEdges.push_back( edge );
347  }
348  else
349  {
350  // Set tags to m_nodes as connected
351  for( auto node : m_nodes )
352  node->SetTag( 0 );
353  }
354 
355  return;
356  }
357 
358 
359  m_triangulator->Clear();
360 
361  for( auto n : m_nodes )
362  {
363  m_triangulator->AddNode( n );
364  }
365 
366  #ifdef PROFILE
367  PROF_COUNTER cnt("triangulate");
368  #endif
369  auto triangEdges = m_triangulator->Triangulate();
370  #ifdef PROFILE
371  cnt.Show();
372  #endif
373 
374  for( const auto& e : m_boardEdges )
375  triangEdges.push_back( e );
376 
377 // Get the minimal spanning tree
378 #ifdef PROFILE
379  PROF_COUNTER cnt2("mst");
380 #endif
381  m_rnEdges = kruskalMST( triangEdges, m_nodes );
382 #ifdef PROFILE
383  cnt2.Show();
384 #endif
385 }
386 
387 
388 
390 {
391  compute();
392 
393  m_dirty = false;
394 }
395 
396 
398 {
399  m_rnEdges.clear();
400  m_boardEdges.clear();
401  m_nodes.clear();
402 
403  m_dirty = true;
404 }
405 
406 
408 {
409  CN_ANCHOR_PTR firstAnchor;
410 
411  for( auto item : *aCluster )
412  {
413  bool isZone = dynamic_cast<CN_ZONE*>(item) != nullptr;
414  auto& anchors = item->Anchors();
415  unsigned int nAnchors = isZone ? 1 : anchors.size();
416 
417  if( nAnchors > anchors.size() )
418  nAnchors = anchors.size();
419 
420  for( unsigned int i = 0; i < nAnchors; i++ )
421  {
422  anchors[i]->SetCluster( aCluster );
423  m_nodes.push_back(anchors[i]);
424 
425  if( firstAnchor )
426  {
427  if( firstAnchor != anchors[i] )
428  {
429  m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
430  }
431  }
432  else
433  {
434  firstAnchor = anchors[i];
435  }
436  }
437  }
438 }
439 
440 
441 bool RN_NET::NearestBicoloredPair( const RN_NET& aOtherNet, CN_ANCHOR_PTR& aNode1,
442  CN_ANCHOR_PTR& aNode2 ) const
443 {
444  bool rv = false;
445 
447 
448  for( auto nodeA : m_nodes )
449  {
450  for( auto nodeB : aOtherNet.m_nodes )
451  {
452  if( !nodeA->GetNoLine() )
453  {
454  auto squaredDist = (nodeA->Pos() - nodeB->Pos() ).SquaredEuclideanNorm();
455 
456  if( squaredDist < distMax )
457  {
458  rv = true;
459  distMax = squaredDist;
460  aNode1 = nodeA;
461  aNode2 = nodeB;
462  }
463  }
464  }
465  }
466 
467  return rv;
468 }
469 
470 
471 void RN_NET::SetVisible( bool aEnabled )
472 {
473  for( auto& edge : m_rnEdges )
474  edge.SetVisible( aEnabled );
475 }
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)
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
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
Class RN_NET Describes ratsnest for a single net.
Definition: ratsnest_data.h:59
CN_ANCHOR_PTR GetSourceNode() const
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
bool areNodesColinear(const std::vector< hed::NODE_PTR > &aNodes) const