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  * Copyright (C) 2019-2020 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Maciej Suminski <maciej.suminski@cern.ch>
8  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
33 #ifdef PROFILE
34 #include <profile.h>
35 #endif
36 
37 #include <ratsnest/ratsnest_data.h>
38 #include <functional>
39 using namespace std::placeholders;
40 
41 #include <algorithm>
42 #include <cassert>
43 #include <limits>
44 
45 #include <delaunator.hpp>
46 
48 {
49 
50 public:
51  disjoint_set( size_t size )
52  {
53  m_data.resize( size );
54  m_depth.resize( size, 0 );
55 
56  for( size_t i = 0; i < size; i++ )
57  m_data[i] = i;
58  }
59 
60  int find( int aVal )
61  {
62  int root = aVal;
63 
64  while( m_data[root] != root )
65  root = m_data[root];
66 
67  // Compress the path
68  while( m_data[aVal] != aVal )
69  {
70  auto& tmp = m_data[aVal];
71  aVal = tmp;
72  tmp = root;
73  }
74 
75  return root;
76  }
77 
78 
79  bool unite( int aVal1, int aVal2 )
80  {
81  aVal1 = find( aVal1 );
82  aVal2 = find( aVal2 );
83 
84  if( aVal1 != aVal2 )
85  {
86  if( m_depth[aVal1] < m_depth[aVal2] )
87  {
88  m_data[aVal1] = aVal2;
89  }
90  else
91  {
92  m_data[aVal2] = aVal1;
93 
94  if( m_depth[aVal1] == m_depth[aVal2] )
95  m_depth[aVal1]++;
96  }
97 
98  return true;
99  }
100 
101  return false;
102  }
103 
104 private:
105  std::vector<int> m_data;
106  std::vector<int> m_depth;
107 };
108 
109 void RN_NET::kruskalMST( const std::vector<CN_EDGE> &aEdges )
110 {
111  disjoint_set dset( m_nodes.size() );
112 
113  m_rnEdges.clear();
114 
115  int i = 0;
116 
117  for( auto& node : m_nodes )
118  node->SetTag( i++ );
119 
120  for( auto& tmp : aEdges )
121  {
122  int u = tmp.GetSourceNode()->GetTag();
123  int v = tmp.GetTargetNode()->GetTag();
124 
125  if( dset.unite( u, v ) )
126  {
127  if( tmp.GetWeight() > 0 )
128  m_rnEdges.push_back( tmp );
129  }
130  }
131 }
132 
133 
135 {
136 private:
137  std::multiset<CN_ANCHOR_PTR, CN_PTR_CMP> m_allNodes;
138 
139 
140  // Checks if all nodes in aNodes lie on a single line. Requires the nodes to
141  // have unique coordinates!
142  bool areNodesColinear( const std::vector<CN_ANCHOR_PTR>& aNodes ) const
143  {
144  if ( aNodes.size() <= 2 )
145  return true;
146 
147  const VECTOR2I p0( aNodes[0]->Pos() );
148  const VECTOR2I v0( aNodes[1]->Pos() - p0 );
149 
150  for( unsigned i = 2; i < aNodes.size(); i++ )
151  {
152  const VECTOR2I v1 = aNodes[i]->Pos() - p0;
153 
154  if( v0.Cross( v1 ) != 0 )
155  return false;
156  }
157 
158  return true;
159  }
160 
161 public:
162 
163  void Clear()
164  {
165  m_allNodes.clear();
166  }
167 
168  void AddNode( CN_ANCHOR_PTR aNode )
169  {
170  m_allNodes.insert( aNode );
171  }
172 
173  void Triangulate( std::vector<CN_EDGE>& mstEdges)
174  {
175  std::vector<double> node_pts;
176 
177  using ANCHOR_LIST = std::vector<CN_ANCHOR_PTR>;
178 
179  ANCHOR_LIST anchors;
180  std::vector<ANCHOR_LIST> anchorChains( m_allNodes.size() );
181 
182  node_pts.reserve( 2 * m_allNodes.size() );
183  anchors.reserve( m_allNodes.size() );
184 
185  CN_ANCHOR_PTR prev = nullptr;
186 
187  for( const auto& n : m_allNodes )
188  {
189  if( !prev || prev->Pos() != n->Pos() )
190  {
191  node_pts.push_back( n->Pos().x );
192  node_pts.push_back( n->Pos().y );
193  anchors.push_back( n );
194  prev = n;
195  }
196 
197  anchorChains[anchors.size() - 1].push_back( n );
198  }
199 
200  if( anchors.size() < 2 )
201  {
202  return;
203  }
204  else if( areNodesColinear( anchors ) )
205  {
206  // special case: all nodes are on the same line - there's no
207  // triangulation for such set. In this case, we sort along any coordinate
208  // and chain the nodes together.
209  for( size_t i = 0; i < anchors.size() - 1; i++ )
210  {
211  auto src = anchors[i];
212  auto dst = anchors[i + 1];
213  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
214  }
215  }
216  else
217  {
218  delaunator::Delaunator delaunator( node_pts );
219  auto& triangles = delaunator.triangles;
220 
221  for( size_t i = 0; i < triangles.size(); i += 3 )
222  {
223  auto src = anchors[triangles[i]];
224  auto dst = anchors[triangles[i + 1]];
225  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
226 
227  src = anchors[triangles[i + 1]];
228  dst = anchors[triangles[i + 2]];
229  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
230 
231  src = anchors[triangles[i + 2]];
232  dst = anchors[triangles[i]];
233  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
234  }
235 
236  for( size_t i = 0; i < delaunator.halfedges.size(); i++ )
237  {
238  if( delaunator.halfedges[i] == delaunator::INVALID_INDEX )
239  continue;
240 
241  auto src = anchors[triangles[i]];
242  auto dst = anchors[triangles[delaunator.halfedges[i]]];
243  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
244  }
245  }
246 
247  for( size_t i = 0; i < anchorChains.size(); i++ )
248  {
249  auto& chain = anchorChains[i];
250 
251  if( chain.size() < 2 )
252  continue;
253 
254  std::sort( chain.begin(), chain.end(),
255  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) {
256  return a->GetCluster().get() < b->GetCluster().get();
257  } );
258 
259  for( unsigned int j = 1; j < chain.size(); j++ )
260  {
261  const auto& prevNode = chain[j - 1];
262  const auto& curNode = chain[j];
263  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
264  mstEdges.emplace_back( prevNode, curNode, weight );
265  }
266  }
267  }
268 };
269 
270 
271 RN_NET::RN_NET() : m_dirty( true )
272 {
273  m_triangulator.reset( new TRIANGULATOR_STATE );
274 }
275 
276 
278 {
279  // Special cases do not need complicated algorithms (actually, it does not work well with
280  // the Delaunay triangulator)
281  if( m_nodes.size() <= 2 )
282  {
283  m_rnEdges.clear();
284 
285  // Check if the only possible connection exists
286  if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
287  {
288  auto last = ++m_nodes.begin();
289 
290  // There can be only one possible connection, but it is missing
291  CN_EDGE edge ( *m_nodes.begin(), *last );
292  edge.GetSourceNode()->SetTag( 0 );
293  edge.GetTargetNode()->SetTag( 1 );
294 
295  m_rnEdges.push_back( edge );
296  }
297  else
298  {
299  // Set tags to m_nodes as connected
300  for( const auto& node : m_nodes )
301  node->SetTag( 0 );
302  }
303 
304  return;
305  }
306 
307 
308  m_triangulator->Clear();
309 
310  for( const auto& n : m_nodes )
311  {
312  m_triangulator->AddNode( n );
313  }
314 
315  std::vector<CN_EDGE> triangEdges;
316  triangEdges.reserve( m_nodes.size() + m_boardEdges.size() );
317 
318  #ifdef PROFILE
319  PROF_COUNTER cnt("triangulate");
320  #endif
321  m_triangulator->Triangulate( triangEdges );
322  #ifdef PROFILE
323  cnt.Show();
324  #endif
325 
326  for( const auto& e : m_boardEdges )
327  triangEdges.emplace_back( e );
328 
329  std::sort( triangEdges.begin(), triangEdges.end() );
330 
331 // Get the minimal spanning tree
332 #ifdef PROFILE
333  PROF_COUNTER cnt2("mst");
334 #endif
335  kruskalMST( triangEdges );
336 #ifdef PROFILE
337  cnt2.Show();
338 #endif
339 }
340 
341 
342 
344 {
345  compute();
346 
347  m_dirty = false;
348 }
349 
350 
352 {
353  m_rnEdges.clear();
354  m_boardEdges.clear();
355  m_nodes.clear();
356 
357  m_dirty = true;
358 }
359 
360 
362 {
363  CN_ANCHOR_PTR firstAnchor;
364 
365  for( auto item : *aCluster )
366  {
367  bool isZone = dynamic_cast<CN_ZONE*>(item) != nullptr;
368  auto& anchors = item->Anchors();
369  unsigned int nAnchors = isZone ? 1 : anchors.size();
370 
371  if( nAnchors > anchors.size() )
372  nAnchors = anchors.size();
373 
374  for( unsigned int i = 0; i < nAnchors; i++ )
375  {
376  anchors[i]->SetCluster( aCluster );
377  m_nodes.insert( anchors[i] );
378 
379  if( firstAnchor )
380  {
381  if( firstAnchor != anchors[i] )
382  {
383  m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
384  }
385  }
386  else
387  {
388  firstAnchor = anchors[i];
389  }
390  }
391  }
392 }
393 
394 
395 bool RN_NET::NearestBicoloredPair( const RN_NET& aOtherNet, CN_ANCHOR_PTR& aNode1,
396  CN_ANCHOR_PTR& aNode2 ) const
397 {
398  bool rv = false;
399 
401 
402  auto verify = [&]( auto& aTestNode1, auto& aTestNode2 )
403  {
404  auto squaredDist = ( aTestNode1->Pos() - aTestNode2->Pos() ).SquaredEuclideanNorm();
405 
406  if( squaredDist < distMax )
407  {
408  rv = true;
409  distMax = squaredDist;
410  aNode1 = aTestNode1;
411  aNode2 = aTestNode2;
412  }
413  };
414 
418  for( const auto& nodeA : aOtherNet.m_nodes )
419  {
420  if( nodeA->GetNoLine() )
421  continue;
422 
426  auto fwd_it = m_nodes.lower_bound( nodeA );
427  auto rev_it = std::make_reverse_iterator( fwd_it );
428 
429  for( ; fwd_it != m_nodes.end(); ++fwd_it )
430  {
431  auto nodeB = *fwd_it;
432 
433  if( nodeB->GetNoLine() )
434  continue;
435 
436  VECTOR2I::extended_type distX = nodeA->Pos().x - nodeB->Pos().x;
437 
440  if( distX * distX > distMax )
441  break;
442 
443  verify( nodeA, nodeB );
444  }
445 
447  if( rev_it != m_nodes.rend() )
448  ++rev_it;
449 
450  for( ; rev_it != m_nodes.rend(); ++rev_it )
451  {
452  auto nodeB = *rev_it;
453 
454  if( nodeB->GetNoLine() )
455  continue;
456 
457  VECTOR2I::extended_type distX = nodeA->Pos().x - nodeB->Pos().x;
458 
459  if( distX * distX > distMax )
460  break;
461 
462  verify( nodeA, nodeB );
463  }
464  }
465 
466  return rv;
467 }
468 
469 
470 void RN_NET::SetVisible( bool aEnabled )
471 {
472  for( auto& edge : m_rnEdges )
473  edge.SetVisible( aEnabled );
474 }
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:77
extended_type Cross(const VECTOR2< T > &aVector) const
Function Cross() computes cross product of self with aVector.
Definition: vector2d.h:484
void Update()
Function Update() Recomputes ratsnest for a net.
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_allNodes
std::vector< int > m_depth
bool m_dirty
Flag indicating necessity of recalculation of ratsnest for a net.
Class that computes missing connections on a PCB.
bool areNodesColinear(const std::vector< CN_ANCHOR_PTR > &aNodes) const
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
void AddNode(CN_ANCHOR_PTR aNode)
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
RN_NET()
Default constructor.
void Clear()
disjoint_set(size_t size)
void kruskalMST(const std::vector< CN_EDGE > &aEdges)
Compute the minimum spanning tree using Kruskal's algorithm
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
bool unite(int aVal1, int aVal2)
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
int find(int aVal)
constexpr std::size_t INVALID_INDEX
Definition: delauney.h:20
RN_NET Describes ratsnest for a single net.
Definition: ratsnest_data.h:61
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
Definition: profile.h:99
std::vector< int > m_data
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of nodes
CN_ANCHOR_PTR GetSourceNode() const
void Triangulate(std::vector< CN_EDGE > &mstEdges)