KiCad PCB EDA Suite
connectivity_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) 2017 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 #ifdef PROFILE
25 #include <profile.h>
26 #endif
27 
28 #include <connectivity_data.h>
29 #include <connectivity_algo.h>
30 #include <ratsnest_data.h>
31 
32 #ifdef USE_OPENMP
33 #include <omp.h>
34 #endif /* USE_OPENMP */
35 
37 {
38  m_connAlgo.reset( new CN_CONNECTIVITY_ALGO );
39  m_progressReporter = nullptr;
40 }
41 
42 
44 {
45  Clear();
46 }
47 
48 
50 {
51  m_connAlgo->Add( aItem );
52  return true;
53 }
54 
55 
57 {
58  m_connAlgo->Remove( aItem );
59  return true;
60 }
61 
62 
64 {
65  m_connAlgo->Remove( aItem );
66  m_connAlgo->Add( aItem );
67  return true;
68 }
69 
70 
72 {
73  m_connAlgo.reset( new CN_CONNECTIVITY_ALGO );
74  m_connAlgo->Build( aBoard );
76 }
77 
78 
79 void CONNECTIVITY_DATA::Build( const std::vector<BOARD_ITEM*>& aItems )
80 {
81  m_connAlgo.reset( new CN_CONNECTIVITY_ALGO );
82  m_connAlgo->Build( aItems );
83 
85 }
86 
87 
89 {
90  int lastNet = m_connAlgo->NetCount();
91 
92  #ifdef PROFILE
93  PROF_COUNTER rnUpdate( "update-ratsnest" );
94  #endif
95 
96  int nDirty = 0;
97 
98  int i;
99 
100  #ifdef USE_OPENMP
101  #pragma omp parallel shared(lastNet) private(i)
102  {
103  #pragma omp for schedule(guided, 1)
104  #else /* USE_OPENMP */
105  {
106  #endif
107 
108  // Start with net number 1, as 0 stands for not connected
109  for( i = 1; i < lastNet; ++i )
110  {
111  if( m_nets[i]->IsDirty() )
112  {
113  m_nets[i]->Update();
114  nDirty++;
115  }
116  }
117  } /* end of parallel section */
118 
119  #ifdef PROFILE
120  rnUpdate.Show();
121  #endif /* PROFILE */
122 }
123 
124 
125 void CONNECTIVITY_DATA::addRatsnestCluster( const std::shared_ptr<CN_CLUSTER>& aCluster )
126 {
127  auto rnNet = m_nets[ aCluster->OriginNet() ];
128 
129  rnNet->AddCluster( aCluster );
130 }
131 
132 
134 {
135  m_connAlgo->PropagateNets();
136 
137  int lastNet = m_connAlgo->NetCount();
138 
139  if( lastNet >= (int) m_nets.size() )
140  {
141  unsigned int prevSize = m_nets.size();
142  m_nets.resize( lastNet + 1 );
143 
144  for( unsigned int i = prevSize; i < m_nets.size(); i++ )
145  m_nets[i] = new RN_NET;
146  }
147 
148  auto clusters = m_connAlgo->GetClusters();
149 
150  int dirtyNets = 0;
151 
152  for( int net = 0; net < lastNet; net++ )
153  {
154  if( m_connAlgo->IsNetDirty( net ) )
155  {
156  m_nets[net]->Clear();
157  dirtyNets++;
158  }
159  }
160 
161  for( auto c : clusters )
162  {
163  int net = c->OriginNet();
164 
165  if( m_connAlgo->IsNetDirty( net ) )
166  {
167  addRatsnestCluster( c );
168  }
169  }
170 
171  m_connAlgo->ClearDirtyFlags();
172 
173  updateRatsnest();
174 }
175 
176 
177 void CONNECTIVITY_DATA::BlockRatsnestItems( const std::vector<BOARD_ITEM*>& aItems )
178 {
179  std::vector<BOARD_CONNECTED_ITEM*> citems;
180 
181  for( auto item : aItems )
182  {
183  if( item->Type() == PCB_MODULE_T )
184  {
185  for( auto pad : static_cast<MODULE*>(item)->Pads() )
186  citems.push_back( pad );
187  }
188  else
189  {
190  citems.push_back( static_cast<BOARD_CONNECTED_ITEM*>(item) );
191  }
192  }
193 
194  for( auto item : citems )
195  {
196  if ( m_connAlgo->ItemExists( item ) )
197  {
198  auto& entry = m_connAlgo->ItemEntry( item );
199 
200  for( auto cnItem : entry.GetItems() )
201  {
202  for( auto anchor : cnItem->Anchors() )
203  anchor->SetNoLine( true );
204  }
205  }
206  }
207 }
208 
209 
211 {
212  return m_connAlgo->NetCount();
213 }
214 
215 
217  std::vector<int>& aIslands )
218 {
219  m_connAlgo->FindIsolatedCopperIslands( aZone, aIslands );
220 }
221 
222 void CONNECTIVITY_DATA::FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones )
223 {
224  m_connAlgo->FindIsolatedCopperIslands( aZones );
225 }
226 
227 void CONNECTIVITY_DATA::ComputeDynamicRatsnest( const std::vector<BOARD_ITEM*>& aItems )
228 {
230  m_dynamicConnectivity->Build( aItems );
231 
232  m_dynamicRatsnest.clear();
233 
234  BlockRatsnestItems( aItems );
235 
236  for( unsigned int nc = 1; nc < m_dynamicConnectivity->m_nets.size(); nc++ )
237  {
238  auto dynNet = m_dynamicConnectivity->m_nets[nc];
239 
240  if( dynNet->GetNodeCount() != 0 )
241  {
242  auto ourNet = m_nets[nc];
243  CN_ANCHOR_PTR nodeA, nodeB;
244 
245  if( ourNet->NearestBicoloredPair( *dynNet, nodeA, nodeB ) )
246  {
247  RN_DYNAMIC_LINE l;
248  l.a = nodeA->Pos();
249  l.b = nodeB->Pos();
250  l.netCode = nc;
251 
252  m_dynamicRatsnest.push_back( l );
253  }
254  }
255  }
256 
257  for( auto net : m_dynamicConnectivity->m_nets )
258  {
259  if( !net )
260  continue;
261 
262  const auto& edges = net->GetUnconnected();
263 
264  if( edges.empty() )
265  continue;
266 
267  for( const auto& edge : edges )
268  {
269  const auto& nodeA = edge.GetSourceNode();
270  const auto& nodeB = edge.GetTargetNode();
271  RN_DYNAMIC_LINE l;
272 
273  l.a = nodeA->Pos();
274  l.b = nodeB->Pos();
275  l.netCode = 0;
276  m_dynamicRatsnest.push_back( l );
277  }
278  }
279 }
280 
281 
283 {
284  m_connAlgo->ForEachAnchor( [] ( CN_ANCHOR& anchor ) { anchor.SetNoLine( false ); } );
286 }
287 
288 
290 {
291  m_dynamicConnectivity.reset();
292  m_dynamicRatsnest.clear();
293 }
294 
295 
297 {
298  m_connAlgo->PropagateNets();
299 }
300 
301 
303 {
304  unsigned int unconnected = 0;
305 
306  for( auto net : m_nets )
307  {
308  if( !net )
309  continue;
310 
311  const auto& edges = net->GetUnconnected();
312 
313  if( edges.empty() )
314  continue;
315 
316  unconnected += edges.size();
317  }
318 
319  return unconnected;
320 }
321 
322 
324 {
325  for( auto net : m_nets )
326  delete net;
327 
328  m_nets.clear();
329 }
330 
331 
332 const std::vector<BOARD_CONNECTED_ITEM*> CONNECTIVITY_DATA::GetConnectedItems(
333  const BOARD_CONNECTED_ITEM* aItem,
334  const KICAD_T aTypes[] ) const
335 {
336  std::vector<BOARD_CONNECTED_ITEM*> rv;
337  const auto clusters = m_connAlgo->SearchClusters( CN_CONNECTIVITY_ALGO::CSM_CONNECTIVITY_CHECK,
338  aTypes, aItem->GetNetCode() );
339 
340  for( auto cl : clusters )
341  {
342  if( cl->Contains( aItem ) )
343  {
344  for( const auto item : *cl )
345  {
346  if( item->Valid() )
347  rv.push_back( item->Parent() );
348  }
349  }
350  }
351 
352  return rv;
353 }
354 
355 
356 const std::vector<BOARD_CONNECTED_ITEM*> CONNECTIVITY_DATA::GetNetItems( int aNetCode,
357  const KICAD_T aTypes[] ) const
358 {
359  std::set<BOARD_CONNECTED_ITEM*> items;
360  std::vector<BOARD_CONNECTED_ITEM*> rv;
361 
362  m_connAlgo->ForEachItem( [&items, aNetCode, &aTypes] ( CN_ITEM& aItem )
363  {
364  if( aItem.Valid() && ( aItem.Net() == aNetCode ) )
365  {
366  KICAD_T itemType = aItem.Parent()->Type();
367 
368  for( int i = 0; aTypes[i] > 0; ++i )
369  {
370  wxASSERT( aTypes[i] < MAX_STRUCT_TYPE_ID );
371 
372  if( itemType == aTypes[i] )
373  {
374  items.insert( aItem.Parent() );
375  break;
376  }
377  }
378  }
379  } );
380 
381  std::copy( items.begin(), items.end(), std::back_inserter( rv ) );
382 
383  return rv;
384 }
385 
386 
387 bool CONNECTIVITY_DATA::CheckConnectivity( std::vector<CN_DISJOINT_NET_ENTRY>& aReport )
388 {
390 
391  for( auto net : m_nets )
392  {
393  if( net )
394  {
395  for( const auto& edge : net->GetEdges() )
396  {
398  ent.net = edge.GetSourceNode()->Parent()->GetNetCode();
399  ent.a = edge.GetSourceNode()->Parent();
400  ent.b = edge.GetTargetNode()->Parent();
401  ent.anchorA = edge.GetSourceNode()->Pos();
402  ent.anchorB = edge.GetTargetNode()->Pos();
403  aReport.push_back( ent );
404  }
405  }
406  }
407 
408  return aReport.empty();
409 }
410 
411 
412 const std::vector<TRACK*> CONNECTIVITY_DATA::GetConnectedTracks( const BOARD_CONNECTED_ITEM* aItem )
413 const
414 {
415  auto& entry = m_connAlgo->ItemEntry( aItem );
416 
417  std::set<TRACK*> tracks;
418  std::vector<TRACK*> rv;
419 
420  for( auto citem : entry.GetItems() )
421  {
422  for( auto connected : citem->ConnectedItems() )
423  {
424  if( connected->Valid() && ( connected->Parent()->Type() == PCB_TRACE_T || connected->Parent()->Type() == PCB_VIA_T ) )
425  tracks.insert( static_cast<TRACK*> ( connected->Parent() ) );
426  }
427  }
428 
429  std::copy( tracks.begin(), tracks.end(), std::back_inserter( rv ) );
430  return rv;
431 }
432 
433 
434 const std::vector<D_PAD*> CONNECTIVITY_DATA::GetConnectedPads( const BOARD_CONNECTED_ITEM* aItem )
435 const
436 {
437  auto& entry = m_connAlgo->ItemEntry( aItem );
438 
439  std::set<D_PAD*> pads;
440  std::vector<D_PAD*> rv;
441 
442  for( auto citem : entry.GetItems() )
443  {
444  for( auto connected : citem->ConnectedItems() )
445  {
446  if( connected->Valid() && connected->Parent()->Type() == PCB_PAD_T )
447  pads.insert( static_cast<D_PAD*> ( connected->Parent() ) );
448  }
449  }
450 
451  std::copy( pads.begin(), pads.end(), std::back_inserter( rv ) );
452  return rv;
453 }
454 
455 
456 unsigned int CONNECTIVITY_DATA::GetNodeCount( int aNet ) const
457 {
458  int sum = 0;
459 
460  if( aNet < 0 ) // Node count for all nets
461  {
462  for( const auto& net : m_nets )
463  sum += net->GetNodeCount();
464  }
465  else if( aNet < (int) m_nets.size() )
466  {
467  sum = m_nets[aNet]->GetNodeCount();
468  }
469 
470  return sum;
471 }
472 
473 
474 unsigned int CONNECTIVITY_DATA::GetPadCount( int aNet ) const
475 {
476  int n = 0;
477 
478  for( auto pad : m_connAlgo->PadList() )
479  {
480  if( !pad->Valid() )
481  continue;
482 
483  auto dpad = static_cast<D_PAD*>( pad->Parent() );
484 
485  if( aNet < 0 || aNet == dpad->GetNetCode() )
486  {
487  n++;
488  }
489  }
490 
491  return n;
492 }
493 
494 
496  const BOARD_CONNECTED_ITEM* aRef,
497  const VECTOR2I& aPos,
498  int aNet )
499 {
500  CN_CLUSTER_PTR refCluster;
501  int refNet = -1;
502 
503  if( aRef )
504  refNet = aRef->GetNetCode();
505 
506  if( aNet >= 0 )
507  refNet = aNet;
508 
509  if( aRef )
510  {
511  for( auto cl : m_connAlgo->GetClusters() )
512  {
513  if( cl->Contains( aRef ) )
514  {
515  refCluster = cl;
516  break;
517  }
518  }
519  }
520 
521  std::set <VECTOR2I> anchors;
522 
523  for( auto cl : m_connAlgo->GetClusters() )
524  {
525  if( cl != refCluster )
526  {
527  for( auto item : *cl )
528  {
529  if( item->Valid() && item->Parent()->GetNetCode() == refNet
530  && item->Parent()->Type() != PCB_ZONE_AREA_T )
531  {
532  for( auto anchor : item->Anchors() )
533  {
534  anchors.insert( anchor->Pos() );
535  }
536  }
537  }
538  }
539  }
540 
541 
542  std::vector<VECTOR2I> rv;
543 
544  std::copy( anchors.begin(), anchors.end(), std::back_inserter( rv ) );
545  std::sort( rv.begin(), rv.end(), [aPos] ( const VECTOR2I& a, const VECTOR2I& b )
546  {
547  auto da = (a - aPos).EuclideanNorm();
548  auto db = (b - aPos).EuclideanNorm();
549 
550  return da < db;
551  } );
552 
553  return rv;
554 }
555 
556 
557 void CONNECTIVITY_DATA::GetUnconnectedEdges( std::vector<CN_EDGE>& aEdges) const
558 {
559  for( auto rnNet : m_nets )
560  {
561  if( rnNet )
562  {
563  for( auto edge : rnNet->GetEdges() )
564  {
565  aEdges.push_back( edge );
566  }
567  }
568  }
569 }
570 
571 
572 const std::vector<BOARD_CONNECTED_ITEM*> CONNECTIVITY_DATA::GetConnectedItems(
573  const BOARD_CONNECTED_ITEM* aItem, const VECTOR2I& aAnchor, KICAD_T aTypes[] )
574 {
575  auto& entry = m_connAlgo->ItemEntry( aItem );
576  std::vector<BOARD_CONNECTED_ITEM* > rv;
577 
578  for( auto cnItem : entry.GetItems() )
579  {
580  for( auto anchor : cnItem->Anchors() )
581  {
582  if( anchor->Pos() == aAnchor )
583  {
584  for( int i = 0; aTypes[i] > 0; i++ )
585  {
586  if( cnItem->Valid() && cnItem->Parent()->Type() == aTypes[i] )
587  {
588  rv.push_back( cnItem->Parent() );
589  break;
590  }
591  }
592  }
593  }
594  }
595 
596  return rv;
597 }
598 
599 
601 {
602  if ( aNet < 0 || aNet >= (int) m_nets.size() )
603  {
604  return nullptr;
605  }
606 
607  return m_nets[ aNet ];
608 }
609 
610 
612 {
613  if (aItem->Type() == PCB_MODULE_T)
614  {
615  for ( auto pad : static_cast<MODULE*>( aItem )->Pads() )
616  {
617  m_connAlgo->MarkNetAsDirty( pad->GetNetCode() );
618  }
619  }
620  if (aItem->IsConnected() )
621  {
622  m_connAlgo->MarkNetAsDirty( static_cast<BOARD_CONNECTED_ITEM*>( aItem )->GetNetCode() );
623  }
624 }
625 
627 {
628  m_progressReporter = aReporter;
629  m_connAlgo->SetProgressReporter( m_progressReporter );
630 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:112
KICAD_T Type() const
Function Type()
Definition: base_struct.h:209
void Clear()
Function Clear() Erases the connectivity database.
Class ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:60
const std::vector< D_PAD * > GetConnectedPads(const BOARD_CONNECTED_ITEM *aItem) const
Class BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class...
A progress reporter for use in multi-threaded environments.
std::shared_ptr< CN_CONNECTIVITY_ALGO > m_connAlgo
Class that computes missing connections on a PCB.
PROGRESS_REPORTER * m_progressReporter
class ZONE_CONTAINER, a zone area
Definition: typeinfo.h:102
bool Update(BOARD_ITEM *aItem)
Function Update() Updates the connectivity data for an item.
const std::vector< BOARD_CONNECTED_ITEM * > GetConnectedItems(const BOARD_CONNECTED_ITEM *aItem, const VECTOR2I &aAnchor, KICAD_T aTypes[])
void ComputeDynamicRatsnest(const std::vector< BOARD_ITEM * > &aItems)
Function ComputeDynamicRatsnest() Calculates the temporary dynamic ratsnest (i.e. ...
unsigned int GetNodeCount(int aNet=-1) const
class D_PAD, a pad in a footprint
Definition: typeinfo.h:90
void Show()
Print the elapsed time (in ms) to STDERR.
Definition: profile.h:93
void RecalculateRatsnest()
Function RecalculateRatsnest() Updates the ratsnest for the board.
void FindIsolatedCopperIslands(ZONE_CONTAINER *aZone, std::vector< int > &aIslands)
Function FindIsolatedCopperIslands() Searches for copper islands in zone aZone that are not connected...
The class PROF_COUNTER is a small class to help profiling.
Definition: profile.h:45
const std::vector< TRACK * > GetConnectedTracks(const BOARD_CONNECTED_ITEM *aItem) const
BOARD_CONNECTED_ITEM * b
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
std::vector< RN_DYNAMIC_LINE > m_dynamicRatsnest
VECTOR2I anchorB
KICAD_T
Enum KICAD_T is the set of class identification values, stored in EDA_ITEM::m_StructType.
Definition: typeinfo.h:78
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
class MODULE, a footprint
Definition: typeinfo.h:89
VECTOR2I anchorA
bool Valid() const
const std::vector< VECTOR2I > NearestUnconnectedTargets(const BOARD_CONNECTED_ITEM *aRef, const VECTOR2I &aPos, int aMaxCount=-1)
void PropagateNets()
Function PropagateNets() Propagates the net codes from the source pads to the tracks/vias.
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
unsigned int GetUnconnectedCount() const
Function GetUnconnectedCount() Returns the number of remaining edges in the ratsnest.
int GetNetCount() const
Function GetNetCount() Returns the total number of nets in the connectivity database.
int Net() const
void ClearDynamicRatsnest()
Function ClearDynamicRatsnest() Erases the temporary dynamic ratsnest (i.e.
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
bool Remove(BOARD_ITEM *aItem)
Function Remove() Removes an item from the connectivity data.
void MarkItemNetAsDirty(BOARD_ITEM *aItem)
std::unique_ptr< CONNECTIVITY_DATA > m_dynamicConnectivity
std::vector< RN_NET * > m_nets
bool Add(BOARD_ITEM *aItem)
Function Add() Adds an item to the connectivity data.
int GetNetCode() const
Function GetNetCode.
void BlockRatsnestItems(const std::vector< BOARD_ITEM * > &aItems)
RN_NET * GetRatsnestForNet(int aNet)
Function GetRatsnestForNet() Returns the ratsnest, expressed as a set of graph edges for a given net...
BOARD_CONNECTED_ITEM * a
BOARD_CONNECTED_ITEM * Parent() const
bool CheckConnectivity(std::vector< CN_DISJOINT_NET_ENTRY > &aReport)
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:169
virtual bool IsConnected() const
Function IsConnected() Returns information if the object is derived from BOARD_CONNECTED_ITEM.
size_t i
Definition: json11.cpp:597
int net
void GetUnconnectedEdges(std::vector< CN_EDGE > &aEdges) const
void SetNoLine(bool aEnable)
Decides whether this node can be a ratsnest line target.
unsigned int GetPadCount(int aNet=-1) const
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96
Class RN_NET Describes ratsnest for a single net.
Definition: ratsnest_data.h:59
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
void Build(BOARD *aBoard)
Function Build() Builds the connectivity database for the board aBoard.
void HideDynamicRatsnest()
Hides the temporary dynamic ratsnest lines.
void addRatsnestCluster(const std::shared_ptr< CN_CLUSTER > &aCluster)
const std::vector< BOARD_CONNECTED_ITEM * > GetNetItems(int aNetCode, const KICAD_T aTypes[]) const
Function GetNetItems() Returns the list of items that belong to a certain net.