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-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Maciej Suminski <[email protected]>
8  * @author Tomasz Wlostowski <[email protected]>
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 
110 void RN_NET::kruskalMST( const std::vector<CN_EDGE> &aEdges )
111 {
112  disjoint_set dset( m_nodes.size() );
113 
114  m_rnEdges.clear();
115 
116  int i = 0;
117 
118  for( const CN_ANCHOR_PTR& node : m_nodes )
119  node->SetTag( i++ );
120 
121  for( const CN_EDGE& tmp : aEdges )
122  {
123  int u = tmp.GetSourceNode()->GetTag();
124  int v = tmp.GetTargetNode()->GetTag();
125 
126  if( dset.unite( u, v ) )
127  {
128  if( tmp.GetWeight() > 0 )
129  m_rnEdges.push_back( tmp );
130  }
131  }
132 }
133 
134 
136 {
137 private:
138  std::multiset<CN_ANCHOR_PTR, CN_PTR_CMP> m_allNodes;
139 
140 
141  // Checks if all nodes in aNodes lie on a single line. Requires the nodes to
142  // have unique coordinates!
143  bool areNodesColinear( const std::vector<CN_ANCHOR_PTR>& aNodes ) const
144  {
145  if ( aNodes.size() <= 2 )
146  return true;
147 
148  const VECTOR2I p0( aNodes[0]->Pos() );
149  const VECTOR2I v0( aNodes[1]->Pos() - p0 );
150 
151  for( unsigned i = 2; i < aNodes.size(); i++ )
152  {
153  const VECTOR2I v1 = aNodes[i]->Pos() - p0;
154 
155  if( v0.Cross( v1 ) != 0 )
156  return false;
157  }
158 
159  return true;
160  }
161 
162 public:
163 
164  void Clear()
165  {
166  m_allNodes.clear();
167  }
168 
169  void AddNode( CN_ANCHOR_PTR aNode )
170  {
171  m_allNodes.insert( aNode );
172  }
173 
174  void Triangulate( std::vector<CN_EDGE>& mstEdges)
175  {
176  std::vector<double> node_pts;
177  std::vector<CN_ANCHOR_PTR> anchors;
178  std::vector< std::vector<CN_ANCHOR_PTR> > anchorChains( m_allNodes.size() );
179 
180  node_pts.reserve( 2 * m_allNodes.size() );
181  anchors.reserve( m_allNodes.size() );
182 
183  CN_ANCHOR_PTR prev = nullptr;
184 
185  for( const CN_ANCHOR_PTR& n : m_allNodes )
186  {
187  if( !prev || prev->Pos() != n->Pos() )
188  {
189  node_pts.push_back( n->Pos().x );
190  node_pts.push_back( n->Pos().y );
191  anchors.push_back( n );
192  prev = n;
193  }
194 
195  anchorChains[anchors.size() - 1].push_back( n );
196  }
197 
198  if( anchors.size() < 2 )
199  {
200  return;
201  }
202  else if( areNodesColinear( anchors ) )
203  {
204  // special case: all nodes are on the same line - there's no
205  // triangulation for such set. In this case, we sort along any coordinate
206  // and chain the nodes together.
207  for( size_t i = 0; i < anchors.size() - 1; i++ )
208  {
209  const CN_ANCHOR_PTR& src = anchors[i];
210  const CN_ANCHOR_PTR& dst = anchors[i + 1];
211  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
212  }
213  }
214  else
215  {
216  delaunator::Delaunator delaunator( node_pts );
217  auto& triangles = delaunator.triangles;
218 
219  for( size_t i = 0; i < triangles.size(); i += 3 )
220  {
221  CN_ANCHOR_PTR& src = anchors[triangles[i]];
222  CN_ANCHOR_PTR& dst = anchors[triangles[i + 1]];
223  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
224 
225  src = anchors[triangles[i + 1]];
226  dst = anchors[triangles[i + 2]];
227  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
228 
229  src = anchors[triangles[i + 2]];
230  dst = anchors[triangles[i]];
231  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
232  }
233 
234  for( size_t i = 0; i < delaunator.halfedges.size(); i++ )
235  {
236  if( delaunator.halfedges[i] == delaunator::INVALID_INDEX )
237  continue;
238 
239  const CN_ANCHOR_PTR& src = anchors[triangles[i]];
240  const CN_ANCHOR_PTR& dst = anchors[triangles[delaunator.halfedges[i]]];
241  mstEdges.emplace_back( src, dst, src->Dist( *dst ) );
242  }
243  }
244 
245  for( size_t i = 0; i < anchorChains.size(); i++ )
246  {
247  std::vector<CN_ANCHOR_PTR>& chain = anchorChains[i];
248 
249  if( chain.size() < 2 )
250  continue;
251 
252  std::sort( chain.begin(), chain.end(),
253  [] ( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b )
254  {
255  return a->GetCluster().get() < b->GetCluster().get();
256  } );
257 
258  for( unsigned int j = 1; j < chain.size(); j++ )
259  {
260  const CN_ANCHOR_PTR& prevNode = chain[j - 1];
261  const CN_ANCHOR_PTR& curNode = chain[j];
262  int weight = prevNode->GetCluster() != curNode->GetCluster() ? 1 : 0;
263  mstEdges.emplace_back( prevNode, curNode, weight );
264  }
265  }
266  }
267 };
268 
269 
270 RN_NET::RN_NET() : m_dirty( true )
271 {
272  m_triangulator.reset( new TRIANGULATOR_STATE );
273 }
274 
275 
277 {
278  // Special cases do not need complicated algorithms (actually, it does not work well with
279  // the Delaunay triangulator)
280  if( m_nodes.size() <= 2 )
281  {
282  m_rnEdges.clear();
283 
284  // Check if the only possible connection exists
285  if( m_boardEdges.size() == 0 && m_nodes.size() == 2 )
286  {
287  auto last = ++m_nodes.begin();
288 
289  // There can be only one possible connection, but it is missing
290  CN_EDGE edge ( *m_nodes.begin(), *last );
291  edge.GetSourceNode()->SetTag( 0 );
292  edge.GetTargetNode()->SetTag( 1 );
293 
294  m_rnEdges.push_back( edge );
295  }
296  else
297  {
298  // Set tags to m_nodes as connected
299  for( const CN_ANCHOR_PTR& node : m_nodes )
300  node->SetTag( 0 );
301  }
302 
303  return;
304  }
305 
306 
307  m_triangulator->Clear();
308 
309  for( const CN_ANCHOR_PTR& n : m_nodes )
310  m_triangulator->AddNode( n );
311 
312  std::vector<CN_EDGE> triangEdges;
313  triangEdges.reserve( m_nodes.size() + m_boardEdges.size() );
314 
315 #ifdef PROFILE
316  PROF_COUNTER cnt("triangulate");
317 #endif
318  m_triangulator->Triangulate( triangEdges );
319 #ifdef PROFILE
320  cnt.Show();
321 #endif
322 
323  for( const CN_EDGE& e : m_boardEdges )
324  triangEdges.emplace_back( e );
325 
326  std::sort( triangEdges.begin(), triangEdges.end() );
327 
328 // Get the minimal spanning tree
329 #ifdef PROFILE
330  PROF_COUNTER cnt2("mst");
331 #endif
332  kruskalMST( triangEdges );
333 #ifdef PROFILE
334  cnt2.Show();
335 #endif
336 }
337 
338 
339 
341 {
342  compute();
343 
344  m_dirty = false;
345 }
346 
347 
349 {
350  m_rnEdges.clear();
351  m_boardEdges.clear();
352  m_nodes.clear();
353 
354  m_dirty = true;
355 }
356 
357 
359 {
360  CN_ANCHOR_PTR firstAnchor;
361 
362  for( CN_ITEM* item : *aCluster )
363  {
364  bool isZone = dynamic_cast<CN_ZONE_LAYER*>( item );
365  std::vector<CN_ANCHOR_PTR>& anchors = item->Anchors();
366  unsigned int nAnchors = isZone ? 1 : anchors.size();
367 
368  if( nAnchors > anchors.size() )
369  nAnchors = anchors.size();
370 
371  for( unsigned int i = 0; i < nAnchors; i++ )
372  {
373  anchors[i]->SetCluster( aCluster );
374  m_nodes.insert( anchors[i] );
375 
376  if( firstAnchor )
377  {
378  if( firstAnchor != anchors[i] )
379  m_boardEdges.emplace_back( firstAnchor, anchors[i], 0 );
380  }
381  else
382  {
383  firstAnchor = anchors[i];
384  }
385  }
386  }
387 }
388 
389 
390 bool RN_NET::NearestBicoloredPair( const RN_NET& aOtherNet, CN_ANCHOR_PTR& aNode1,
391  CN_ANCHOR_PTR& aNode2 ) const
392 {
393  bool rv = false;
394 
395  SEG::ecoord distMax_sq = VECTOR2I::ECOORD_MAX;
396 
397  auto verify =
398  [&]( const std::shared_ptr<CN_ANCHOR>& aTestNode1,
399  const std::shared_ptr<CN_ANCHOR>& aTestNode2 )
400  {
401  VECTOR2I diff = aTestNode1->Pos() - aTestNode2->Pos();
402  SEG::ecoord dist_sq = diff.SquaredEuclideanNorm();
403 
404  if( dist_sq < distMax_sq )
405  {
406  rv = true;
407  distMax_sq = dist_sq;
408  aNode1 = aTestNode1;
409  aNode2 = aTestNode2;
410  }
411  };
412 
416  for( const std::shared_ptr<CN_ANCHOR>& nodeA : aOtherNet.m_nodes )
417  {
418  if( nodeA->GetNoLine() )
419  continue;
420 
424  auto fwd_it = m_nodes.lower_bound( nodeA );
425  auto rev_it = std::make_reverse_iterator( fwd_it );
426 
427  for( ; fwd_it != m_nodes.end(); ++fwd_it )
428  {
429  const std::shared_ptr<CN_ANCHOR>& nodeB = *fwd_it;
430 
431  if( nodeB->GetNoLine() )
432  continue;
433 
434  SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
435 
438  if( distX_sq > distMax_sq )
439  break;
440 
441  verify( nodeA, nodeB );
442  }
443 
445  for( ; rev_it != m_nodes.rend(); ++rev_it )
446  {
447  const std::shared_ptr<CN_ANCHOR>& nodeB = *rev_it;
448 
449  if( nodeB->GetNoLine() )
450  continue;
451 
452  SEG::ecoord distX_sq = SEG::Square( nodeA->Pos().x - nodeB->Pos().x );
453 
454  if( distX_sq > distMax_sq )
455  break;
456 
457  verify( nodeA, nodeB );
458  }
459  }
460 
461  return rv;
462 }
463 
464 
465 void RN_NET::SetVisible( bool aEnabled )
466 {
467  for( CN_EDGE& edge : m_rnEdges )
468  edge.SetVisible( aEnabled );
469 }
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:513
void Update()
Recompute ratsnest for a net.
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_allNodes
std::vector< int > m_depth
bool m_dirty
Class that computes missing connections on a PCB.
VECTOR2I::extended_type ecoord
Definition: seg.h:43
bool areNodesColinear(const std::vector< CN_ANCHOR_PTR > &aNodes) const
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:300
std::vector< CN_EDGE > m_rnEdges
Flag indicating necessity of recalculation of ratsnest for a net.
void compute()
< Recompute ratsnest from scratch.
static SEG::ecoord Square(int a)
Definition: seg.h:122
A thread-safe event counter.
Definition: profile.h:225
void AddNode(CN_ANCHOR_PTR aNode)
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
void Clear()
disjoint_set(size_t size)
void kruskalMST(const std::vector< CN_EDGE > &aEdges)
Vector of nodes.
void SetVisible(bool aEnabled)
Set 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
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
std::vector< CN_EDGE > m_boardEdges
Vector of edges that makes ratsnest for a given net.
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
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)
Describe ratsnest for a single net.
Definition: ratsnest_data.h:61
void Show(std::ostream &aStream=std::cerr)
Definition: profile.h:249
std::vector< int > m_data
std::multiset< CN_ANCHOR_PTR, CN_PTR_CMP > m_nodes
Vector of edges that make pre-defined connections.
CN_ANCHOR_PTR GetSourceNode() const
void Triangulate(std::vector< CN_EDGE > &mstEdges)