KiCad PCB EDA Suite
connect.cpp
Go to the documentation of this file.
1 
6 /*
7  * This program source code file is part of KiCad, a free EDA CAD application.
8  *
9  * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
10  * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
11  * Copyright (C) 1992-2015 KiCad Developers, see AUTHORS.txt for contributors.
12  *
13  * This program is free software; you can redistribute it and/or
14  * modify it under the terms of the GNU General Public License
15  * as published by the Free Software Foundation; either version 2
16  * of the License, or (at your option) any later version.
17  *
18  * This program is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with this program; if not, you may find one here:
25  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
26  * or you may search the http://www.gnu.org website for the version 2 license,
27  * or you may write to the Free Software Foundation, Inc.,
28  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
29  */
30 
31 #include <fctsys.h>
32 #include <common.h>
33 #include <macros.h>
34 #include <wxBasePcbFrame.h>
35 #include <view/view.h>
36 
37 #include <pcbnew.h>
38 
39 // Helper classes to handle connection points
40 #include <connect.h>
41 
43 extern void Merge_SubNets_Connected_By_CopperAreas( BOARD* aPcb, int aNetcode );
44 
45 // Local functions
46 static void RebuildTrackChain( BOARD* pcb );
47 
48 
50 {
51  m_brd = aBrd;
52  m_firstTrack = NULL;
53  m_lastTrack = NULL;
54 }
55 
56 
57 /* Fills m_sortedPads with all pads that be connected to tracks
58  * pads are sorted by X coordinate ( and Y coordinates for same X value )
59  * aNetcode = net code to filter pads or < 0 to put all pads in list
60  */
61 void CONNECTIONS::BuildPadsList( int aNetcode )
62 {
63  // Creates sorted pad list if not exists
64  m_sortedPads.clear();
65  m_brd->GetSortedPadListByXthenYCoord( m_sortedPads, aNetcode < 0 ? -1 : aNetcode );
66 }
67 
68 /* Explores the list of pads and adds to m_PadsConnected member
69  * of each pad pads connected to
70  * Here, connections are due to intersecting pads, not tracks
71  */
73 {
74  std::vector<CONNECTED_POINT*> candidates;
75 
77 
78  for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
79  {
80  D_PAD* pad = m_sortedPads[ii];
81 
82  pad->m_PadsConnected.clear();
83  candidates.clear();
84 
85  CollectItemsNearTo( candidates, pad->ShapePos(), pad->GetBoundingRadius() );
86 
87  // add pads to pad.m_PadsConnected, if they are connected
88  for( unsigned jj = 0; jj < candidates.size(); jj++ )
89  {
90  CONNECTED_POINT* item = candidates[jj];
91 
92  D_PAD* candidate_pad = item->GetPad();
93 
94  if( pad == candidate_pad )
95  continue;
96 
97  if( !( pad->GetLayerSet() & candidate_pad->GetLayerSet() ).any() )
98  continue;
99 
100  if( pad->HitTest( item->GetPoint() ) )
101  {
102  pad->m_PadsConnected.push_back( candidate_pad );
103  }
104  }
105  }
106 }
107 
108 /* Explores the list of pads
109  * Adds to m_PadsConnected member of each track the pad(s) connected to
110  * Adds to m_TracksConnected member of each pad the track(s) connected to
111  * D_PAD::m_TracksConnected is cleared before adding items
112  * TRACK::m_PadsConnected is not cleared
113  */
114 void CONNECTIONS::SearchTracksConnectedToPads( bool add_to_padlist, bool add_to_tracklist)
115 {
116  std::vector<CONNECTED_POINT*> candidates;
117 
118  for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
119  {
120  D_PAD * pad = m_sortedPads[ii];
121  pad->m_TracksConnected.clear();
122  candidates.clear();
123 
124  CollectItemsNearTo( candidates, pad->GetPosition(), pad->GetBoundingRadius() );
125 
126  // add this pad to track.m_PadsConnected, if it is connected
127  for( unsigned jj = 0; jj < candidates.size(); jj++ )
128  {
129  CONNECTED_POINT* cp_item = candidates[jj];
130 
131  if( !( pad->GetLayerSet() & cp_item->GetTrack()->GetLayerSet() ).any() )
132  continue;
133 
134  if( pad->HitTest( cp_item->GetPoint() ) )
135  {
136  if( add_to_padlist )
137  cp_item->GetTrack()->m_PadsConnected.push_back( pad );
138 
139  if( add_to_tracklist )
140  pad->m_TracksConnected.push_back( cp_item->GetTrack() );
141  }
142  }
143  }
144 }
145 
146 void CONNECTIONS::CollectItemsNearTo( std::vector<CONNECTED_POINT*>& aList,
147  const wxPoint& aPosition, int aDistMax )
148 {
149  /* Search items in m_Candidates that position is <= aDistMax from aPosition
150  * (Rectilinear distance)
151  * m_Candidates is sorted by X then Y values, so a fast binary search is used
152  * to locate the "best" entry point in list
153  * The best entry is a pad having its m_Pos.x == (or near) aPosition.x
154  * All candidates are near this candidate in list
155  * So from this entry point, a linear search is made to find all candidates
156  */
157  int idxmax = m_candidates.size()-1;
158 
159  int delta = m_candidates.size();
160 
161  int idx = 0; // Starting index is the beginning of list
162  while( delta )
163  {
164  // Calculate half size of remaining interval to test.
165  // Ensure the computed value is not truncated (too small)
166  if( (delta & 1) && ( delta > 1 ) )
167  delta++;
168  delta /= 2;
169 
170  CONNECTED_POINT& item = m_candidates[idx];
171 
172  int dist = item.GetPoint().x - aPosition.x;
173  if( abs(dist) <= aDistMax )
174  {
175  break; // A good entry point is found. The list can be scanned from this point.
176  }
177 
178  else if( item.GetPoint().x < aPosition.x ) // We should search after this item
179  {
180  idx += delta;
181  if( idx > idxmax )
182  idx = idxmax;
183  }
184  else // We should search before this item
185  {
186  idx -= delta;
187  if( idx < 0 )
188  idx = 0;
189  }
190  }
191 
192  /* Now explore the candidate list from the "best" entry point found
193  * (candidate "near" aPosition.x)
194  * We explore the list until abs(candidate->m_Point.x - aPosition.x) > aDistMax
195  * because the list is sorted by X position (and for a given X pos, by Y pos)
196  * Currently a linear search is made because the number of candidates
197  * having the right X position is usually small
198  */
199  // search next candidates in list
200  wxPoint diff;
201  for( int ii = idx; ii <= idxmax; ii++ )
202  {
203  CONNECTED_POINT* item = &m_candidates[ii];
204  diff = item->GetPoint() - aPosition;
205  if( abs(diff.x) > aDistMax )
206  break; // Exit: the distance is to long, we cannot find other candidates
207  if( abs(diff.y) > aDistMax )
208  continue; // the y distance is to long, but we can find other candidates
209  // We have here a good candidate: add it
210  aList.push_back( item );
211  }
212  // search previous candidates in list
213  for( int ii = idx-1; ii >=0; ii-- )
214  {
215  CONNECTED_POINT * item = &m_candidates[ii];
216  diff = item->GetPoint() - aPosition;
217  if( abs(diff.x) > aDistMax )
218  break;
219  if( abs(diff.y) > aDistMax )
220  continue;
221  // We have here a good candidate:add it
222  aList.push_back( item );
223  }
224 }
225 
226 
228 {
229  m_candidates.clear();
230  m_candidates.reserve( m_sortedPads.size() );
231 
232  for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
233  {
234  D_PAD * pad = m_sortedPads[ii];
235  CONNECTED_POINT candidate( pad, pad->GetPosition() );
236  m_candidates.push_back( candidate );
237  }
238 }
239 
240 /* sort function used to sort .m_Connected by X the Y values
241  * items are sorted by X coordinate value,
242  * and for same X value, by Y coordinate value.
243  */
245  const CONNECTED_POINT & aTst )
246 {
247  if( aRef.GetPoint().x == aTst.GetPoint().x )
248  return aRef.GetPoint().y < aTst.GetPoint().y;
249  return aRef.GetPoint().x < aTst.GetPoint().x;
250 }
251 
253 {
254  m_candidates.clear();
255  m_firstTrack = m_lastTrack = aBegin;
256 
257  unsigned ii = 0;
258 
259  // Count candidates ( i.e. end points )
260  for( const TRACK* track = aBegin; track; track = track->Next() )
261  {
262  if( track->Type() == PCB_VIA_T )
263  ii++;
264  else
265  ii += 2;
266 
267  m_lastTrack = track;
268 
269  if( track == aEnd )
270  break;
271  }
272 
273  // Build candidate list
274  m_candidates.reserve( ii );
275  for( TRACK* track = aBegin; track; track = track->Next() )
276  {
277  CONNECTED_POINT candidate( track, track->GetStart() );
278 
279  m_candidates.push_back( candidate );
280  if( track->Type() != PCB_VIA_T )
281  {
282  CONNECTED_POINT candidate2( track, track->GetEnd());
283  m_candidates.push_back( candidate2 );
284  }
285 
286  if( track == aEnd )
287  break;
288  }
289 
290  // Sort list by increasing X coordinate,
291  // and for increasing Y coordinate when items have the same X coordinate
292  // So candidates to the same location are consecutive in list.
294 }
295 
296 
297 /* Populates .m_connected with tracks/vias connected to aTrack
298  * param aTrack = track or via to use as reference
299  * For calculation time reason, an exhaustive search cannot be made
300  * and a proximity search is made:
301  * Only tracks with one end near one end of aTrack are collected.
302  * near means dist <= aTrack width / 2
303  * because with this constraint we can make a fast search in track list
304  * m_candidates is expected to be populated by the track candidates ends list
305  */
307 {
308  int count = 0;
309  m_connected.clear();
310 
311  LSET layerMask = aTrack->GetLayerSet();
312 
313  // Search for connections to starting point:
314 #define USE_EXTENDED_SEARCH
315 
316 #ifdef USE_EXTENDED_SEARCH
317  int dist_max = aTrack->GetWidth() / 2;
318  static std::vector<CONNECTED_POINT*> tracks_candidates;
319 #endif
320 
321  wxPoint position = aTrack->GetStart();
322 
323  for( int kk = 0; kk < 2; kk++ )
324  {
325 #ifndef USE_EXTENDED_SEARCH
326  int idx = searchEntryPointInCandidatesList( position );
327 
328  if( idx >= 0 )
329  {
330  // search after:
331  for( unsigned ii = idx; ii < m_candidates.size(); ii ++ )
332  {
333  if( m_candidates[ii].GetTrack() == aTrack )
334  continue;
335 
336  if( m_candidates[ii].GetPoint() != position )
337  break;
338 
339  if( ( m_candidates[ii].GetTrack()->GetLayerSet() & layerMask ).any() )
340  m_connected.push_back( m_candidates[ii].GetTrack() );
341  }
342 
343  // search before:
344  for( int ii = idx-1; ii >= 0; ii -- )
345  {
346  if( m_candidates[ii].GetTrack() == aTrack )
347  continue;
348 
349  if( m_candidates[ii].GetPoint() != position )
350  break;
351 
352  if( ( m_candidates[ii].GetTrack()->GetLayerSet() & layerMask ).any() )
353  m_connected.push_back( m_candidates[ii].GetTrack() );
354  }
355  }
356 #else
357 
358  tracks_candidates.clear();
359 
360  CollectItemsNearTo( tracks_candidates, position, dist_max );
361 
362  for( unsigned ii = 0; ii < tracks_candidates.size(); ii++ )
363  {
364  TRACK* ctrack = tracks_candidates[ii]->GetTrack();
365 
366  if( !( ctrack->GetLayerSet() & layerMask ).any() )
367  continue;
368 
369  if( ctrack == aTrack )
370  continue;
371 
372  // We have a good candidate: calculate the actual distance
373  // between ends, which should be <= dist max.
374  wxPoint delta = tracks_candidates[ii]->GetPoint() - position;
375 
376  int dist = KiROUND( EuclideanNorm( delta ) );
377 
378  if( dist > dist_max )
379  continue;
380 
381  m_connected.push_back( ctrack );
382  }
383 #endif
384 
385  // Search for connections to ending point:
386  if( aTrack->Type() == PCB_VIA_T )
387  break;
388 
389  position = aTrack->GetEnd();
390  }
391 
392  return count;
393 }
394 
395 
397 {
398  // Search the aPoint coordinates in m_Candidates
399  // m_Candidates is sorted by X then Y values, and a fast binary search is used
400  int idxmax = m_candidates.size()-1;
401 
402  int delta = m_candidates.size();
403 
404  int idx = 0; // Starting index is the beginning of list
405 
406  while( delta )
407  {
408  // Calculate half size of remaining interval to test.
409  // Ensure the computed value is not truncated (too small)
410  if( ( delta & 1 ) && ( delta > 1 ) )
411  delta++;
412 
413  delta /= 2;
414 
415  CONNECTED_POINT& candidate = m_candidates[idx];
416 
417  if( candidate.GetPoint() == aPoint ) // candidate found
418  {
419  return idx;
420  }
421 
422  // Not found: test the middle of the remaining sub list
423  if( candidate.GetPoint().x == aPoint.x ) // Must search considering Y coordinate
424  {
425  if(candidate.GetPoint().y < aPoint.y) // Must search after this item
426  {
427  idx += delta;
428  if( idx > idxmax )
429  idx = idxmax;
430  }
431  else // Must search before this item
432  {
433  idx -= delta;
434  if( idx < 0 )
435  idx = 0;
436  }
437  }
438  else if( candidate.GetPoint().x < aPoint.x ) // Must search after this item
439  {
440  idx += delta;
441  if( idx > idxmax )
442  idx = idxmax;
443  }
444  else // Must search before this item
445  {
446  idx -= delta;
447  if( idx < 0 )
448  idx = 0;
449  }
450  }
451 
452  return -1;
453 }
454 
455 /* Used after a track change (delete a track ou add a track)
456  * Connections to pads are recalculated
457  * Note also aFirstTrack (and aLastTrack ) can be NULL
458  */
459 void CONNECTIONS::Build_CurrNet_SubNets_Connections( TRACK* aFirstTrack, TRACK* aLastTrack, int aNetcode )
460 {
461  m_firstTrack = aFirstTrack; // The first track used to build m_Candidates
462  m_lastTrack = aLastTrack; // The last track used to build m_Candidates
463 
464  // Pads subnets are expected already cleared, because this function
465  // does not know the full list of pads
466  BuildTracksCandidatesList( aFirstTrack, aLastTrack );
467  TRACK* curr_track;
468  for( curr_track = aFirstTrack; curr_track != NULL; curr_track = curr_track->Next() )
469  {
470  // Clear track subnet id (Pads subnets are cleared outside this function)
471  curr_track->SetSubNet( 0 );
472  curr_track->m_TracksConnected.clear();
473  curr_track->m_PadsConnected.clear();
474 
475  // Update connections between tracks:
476  SearchConnectedTracks( curr_track );
477  curr_track->m_TracksConnected = m_connected;
478 
479  if( curr_track == aLastTrack )
480  break;
481  }
482 
483  // Update connections between tracks and pads
484  BuildPadsList( aNetcode );
486 
487  // Update connections between intersecting pads (no tracks)
489 
490  // Creates sub nets (clusters) for the current net:
492 }
493 
494 
500 int CONNECTIONS::Merge_PadsSubNets( int aOldSubNet, int aNewSubNet )
501 {
502  int change_count = 0;
503 
504  if( aOldSubNet == aNewSubNet )
505  return 0;
506 
507  if( (aOldSubNet > 0) && (aOldSubNet < aNewSubNet) )
508  std::swap( aOldSubNet, aNewSubNet );
509 
510  // Examine connections between intersecting pads
511  for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
512  {
513  D_PAD * curr_pad = m_sortedPads[ii];
514  if( curr_pad->GetSubNet() != aOldSubNet )
515  continue;
516 
517  change_count++;
518  curr_pad->SetSubNet( aNewSubNet );
519  }
520 
521  return change_count;
522 }
523 
524 /*
525  * Change a subnet value to a new value, for tracks and pads which are connected to.
526  * The result is merging 2 clusters (or subnets) into only one cluster.
527  * Note: the resulting sub net value is the smallest between aOldSubNet et aNewSubNet
528  */
529 int CONNECTIONS::Merge_SubNets( int aOldSubNet, int aNewSubNet )
530 {
531  TRACK* curr_track;
532  int change_count = 0;
533 
534  if( aOldSubNet == aNewSubNet )
535  return 0;
536 
537  if( (aOldSubNet > 0) && (aOldSubNet < aNewSubNet) )
538  std::swap( aOldSubNet, aNewSubNet );
539 
540  curr_track = (TRACK*)m_firstTrack;
541 
542  for( ; curr_track != NULL; curr_track = curr_track->Next() )
543  {
544  if( curr_track->GetSubNet() != aOldSubNet )
545  {
546  if( curr_track == m_lastTrack )
547  break;
548 
549  continue;
550  }
551 
552  change_count++;
553  curr_track->SetSubNet( aNewSubNet );
554 
555  for( unsigned ii = 0; ii < curr_track->m_PadsConnected.size(); ii++ )
556  {
557  D_PAD * pad = curr_track->m_PadsConnected[ii];
558  if( pad->GetSubNet() == aOldSubNet )
559  {
560  pad->SetSubNet( curr_track->GetSubNet() );
561  }
562  }
563 
564  if( curr_track == m_lastTrack )
565  break;
566  }
567 
568  return change_count;
569 }
570 
571 
572 /* Test a list of track segments, to create or propagate a sub netcode to pads and
573  * segments connected together.
574  * The track list must be sorted by nets, and all segments
575  * from m_firstTrack to m_lastTrack have the same net
576  * When 2 items are connected (a track to a pad, or a track to an other track),
577  * they are grouped in a cluster.
578  * The .m_Subnet member is the cluster identifier (subnet id)
579  * For a given net, if all tracks are created, there is only one cluster.
580  * but if not all tracks are created, there are more than one cluster,
581  * and some ratsnests will be left active.
582  * A ratsnest is active when it "connect" 2 items having different subnet id
583  */
585 {
586  int sub_netcode = 1;
587 
588  TRACK* curr_track = (TRACK*)m_firstTrack;
589  if( curr_track )
590  curr_track->SetSubNet( sub_netcode );
591 
592  // Examine connections between tracks and pads
593  for( ; curr_track != NULL; curr_track = curr_track->Next() )
594  {
595  // First: handling connections to pads
596  for( unsigned ii = 0; ii < curr_track->m_PadsConnected.size(); ii++ )
597  {
598  D_PAD * pad = curr_track->m_PadsConnected[ii];
599 
600  if( curr_track->GetSubNet() ) // the track segment is already a cluster member
601  {
602  if( pad->GetSubNet() > 0 )
603  {
604  // The pad is already a cluster member, so we can merge the 2 clusters
605  Merge_SubNets( pad->GetSubNet(), curr_track->GetSubNet() );
606  }
607  else
608  {
609  /* The pad is not yet attached to a cluster , so we can add this pad to
610  * the cluster */
611  pad->SetSubNet( curr_track->GetSubNet() );
612  }
613  }
614  else // the track segment is not attached to a cluster
615  {
616  if( pad->GetSubNet() > 0 )
617  {
618  // it is connected to a pad in a cluster, merge this track
619  curr_track->SetSubNet( pad->GetSubNet() );
620  }
621  else
622  {
623  /* it is connected to a pad not in a cluster, so we must create a new
624  * cluster (only with the 2 items: the track and the pad) */
625  sub_netcode++;
626  curr_track->SetSubNet( sub_netcode );
627  pad->SetSubNet( curr_track->GetSubNet() );
628  }
629  }
630  }
631 
632  // Test connections between segments
633  for( unsigned ii = 0; ii < curr_track->m_TracksConnected.size(); ii++ )
634  {
635  BOARD_CONNECTED_ITEM* track = curr_track->m_TracksConnected[ii];
636 
637  if( curr_track->GetSubNet() ) // The current track is already a cluster member
638  {
639  // The other track is already a cluster member, so we can merge the 2 clusters
640  if( track->GetSubNet() )
641  {
642  Merge_SubNets( track->GetSubNet(), curr_track->GetSubNet() );
643  }
644  else
645  {
646  // The other track is not yet attached to a cluster , so we can add this
647  // other track to the cluster
648  track->SetSubNet( curr_track->GetSubNet() );
649  }
650  }
651  else // the current track segment is not yet attached to a cluster
652  {
653  if( track->GetSubNet() )
654  {
655  // The other track is already a cluster member, so we can add
656  // the current segment to the cluster
657  curr_track->SetSubNet( track->GetSubNet() );
658  }
659  else
660  {
661  // it is connected to an other segment not in a cluster, so we must
662  // create a new cluster (only with the 2 track segments)
663  sub_netcode++;
664  curr_track->SetSubNet( sub_netcode );
665  track->SetSubNet( curr_track->GetSubNet() );
666  }
667  }
668  }
669 
670  if( curr_track == m_lastTrack )
671  break;
672  }
673 
674  // Examine connections between intersecting pads, and propagate
675  // sub_netcodes to intersecting pads
676  for( unsigned ii = 0; ii < m_sortedPads.size(); ii++ )
677  {
678  D_PAD* curr_pad = m_sortedPads[ii];
679 
680  for( unsigned jj = 0; jj < curr_pad->m_PadsConnected.size(); jj++ )
681  {
682  D_PAD* pad = curr_pad->m_PadsConnected[jj];
683 
684  if( curr_pad->GetSubNet() ) // the current pad is already attached to a cluster
685  {
686  if( pad->GetSubNet() > 0 )
687  {
688  // The pad is already a cluster member, so we can merge the 2 clusters
689  // Store the initial subnets, which will be modified by Merge_PadsSubNets
690  int subnet1 = pad->GetSubNet();
691  int subnet2 = curr_pad->GetSubNet();
692 
693  // merge subnets of pads only, even those not connected by tracks
694  Merge_PadsSubNets( subnet1, subnet2 );
695 
696  // merge subnets of tracks (and pads, which are already merged)
697  Merge_SubNets( subnet1, subnet2 );
698  }
699  else
700  {
701  // The pad is not yet attached to a cluster,
702  // so we can add this pad to the cluster
703  pad->SetSubNet( curr_pad->GetSubNet() );
704  }
705  }
706  else // the current pad is not attached to a cluster
707  {
708  if( pad->GetSubNet() > 0 )
709  {
710  // the connected pad is in a cluster,
711  // so we can add the current pad to the cluster
712  curr_pad->SetSubNet( pad->GetSubNet() );
713  }
714  else
715  {
716  // the connected pad is not in a cluster,
717  // so we must create a new cluster, with the 2 pads.
718  sub_netcode++;
719  curr_pad->SetSubNet( sub_netcode );
720  pad->SetSubNet( curr_pad->GetSubNet() );
721  }
722  }
723  }
724  }
725 }
726 
727 /*
728  * Test all connections of the board,
729  * and update subnet variable of pads and tracks
730  * TestForActiveLinksInRatsnest must be called after this function
731  * to update active/inactive ratsnest items status
732  */
734 {
735  // Clear the cluster identifier for all pads
736  for( unsigned i = 0; i< m_Pcb->GetPadCount(); ++i )
737  {
738  D_PAD* pad = m_Pcb->GetPad(i);
739 
740  pad->SetZoneSubNet( 0 );
741  pad->SetSubNet( 0 );
742  }
743 
745 
746  // Test existing connections net by net
747  // note some nets can have no tracks, and pads intersecting
748  // so Build_CurrNet_SubNets_Connections must be called for each net
749  CONNECTIONS connections( m_Pcb );
750 
751  int last_net_tested = 0;
752  int current_net_code = 0;
753 
754  for( TRACK* track = m_Pcb->m_Track; track; )
755  {
756  // At this point, track is the first track of a given net
757  current_net_code = track->GetNetCode();
758 
759  // Get last track of the current net
760  TRACK* lastTrack = track->GetEndNetCode( current_net_code );
761 
762  if( current_net_code > 0 ) // do not spend time if net code = 0 ( dummy net )
763  {
764  // Test all previous nets having no tracks
765  for( int net = last_net_tested+1; net < current_net_code; net++ )
766  connections.Build_CurrNet_SubNets_Connections( NULL, NULL, net );
767 
768  connections.Build_CurrNet_SubNets_Connections( track, lastTrack, current_net_code );
769  last_net_tested = current_net_code;
770  }
771 
772  track = lastTrack->Next(); // this is now the first track of the next net
773  }
774 
775  // Test last nets without tracks, if any
776  int netsCount = m_Pcb->GetNetCount();
777  for( int net = last_net_tested+1; net < netsCount; net++ )
778  connections.Build_CurrNet_SubNets_Connections( NULL, NULL, net );
779 
781 
782  return;
783 }
784 
785 
786 void PCB_BASE_FRAME::TestNetConnection( wxDC* aDC, int aNetCode )
787 {
788  // Skip dummy net -1, and "not connected" net 0 (grouping all not connected pads)
789  if( aNetCode <= 0 )
790  return;
791 
793  Compile_Ratsnest( aDC, true );
794 
795  // Clear the cluster identifier (subnet) of pads for this net
796  // Pads are grouped by netcode (and in netname alphabetic order)
797  for( unsigned i = 0; i < m_Pcb->GetPadCount(); ++i )
798  {
799  D_PAD* pad = m_Pcb->GetPad(i);
800 
801  if( m_Pcb->GetPad(i)->GetNetCode() == aNetCode )
802  pad->SetSubNet( 0 );
803  }
804 
806 
807  // Search for the first and the last segment relative to the given net code
808  if( m_Pcb->m_Track )
809  {
810  CONNECTIONS connections( m_Pcb );
811 
812  TRACK* lastTrack = NULL;
813  TRACK* firstTrack = m_Pcb->m_Track.GetFirst()->GetStartNetCode( aNetCode );
814 
815  if( firstTrack )
816  lastTrack = firstTrack->GetEndNetCode( aNetCode );
817 
818  if( firstTrack && lastTrack ) // i.e. if there are segments
819  {
820  connections.Build_CurrNet_SubNets_Connections( firstTrack, lastTrack, aNetCode );
821  }
822  }
823 
825 
826  // rebuild the active ratsnest for this net
827  DrawGeneralRatsnest( aDC, aNetCode );
828  TestForActiveLinksInRatsnest( aNetCode );
829  DrawGeneralRatsnest( aDC, aNetCode );
830 
831  // Display results
832  wxString msg;
833  int net_notconnected_count = 0;
834  NETINFO_ITEM* net = m_Pcb->FindNet( aNetCode );
835 
836  if( net ) // Should not occur, but ...
837  {
838  for( unsigned ii = net->m_RatsnestStartIdx; ii < net->m_RatsnestEndIdx; ii++ )
839  {
840  if( m_Pcb->m_FullRatsnest[ii].IsActive() )
841  net_notconnected_count++;
842  }
843 
844  msg.Printf( wxT( "links %d nc %d net %d: not conn %d" ),
846  net_notconnected_count );
847  }
848  else
849  msg.Printf( wxT( "net not found: netcode %d" ), aNetCode );
850 
851  SetStatusText( msg );
852 
853  return;
854 }
855 
856 
857 /* search connections between tracks and pads and propagate pad net codes to the track
858  * segments.
859  * Pads netcodes are assumed to be up to date.
860  */
862 {
863  // Build the net info list
865 
866  // Reset variables and flags used in computation
867  for( TRACK* t = m_Pcb->m_Track; t; t = t->Next() )
868  {
869  t->m_TracksConnected.clear();
870  t->m_PadsConnected.clear();
871  t->start = NULL;
872  t->end = NULL;
873  t->SetState( BUSY | IN_EDIT | BEGIN_ONPAD | END_ONPAD, false );
874  t->SetZoneSubNet( 0 );
875  t->SetNetCode( NETINFO_LIST::UNCONNECTED );
876  }
877 
878  // If no pad, reset pointers and netcode, and do nothing else
879  if( m_Pcb->GetPadCount() == 0 )
880  return;
881 
882  CONNECTIONS connections( m_Pcb );
883  connections.BuildPadsList();
885 
886  // First pass: build connections between track segments and pads.
887  connections.SearchTracksConnectedToPads();
888 
889  // For tracks connected to at least one pad,
890  // set the track net code to the pad netcode
891  for( TRACK* t = m_Pcb->m_Track; t; t = t->Next() )
892  {
893  if( t->m_PadsConnected.size() )
894  t->SetNetCode( t->m_PadsConnected[0]->GetNetCode() );
895  }
896 
897  // Pass 2: build connections between track ends
898  for( TRACK* t = m_Pcb->m_Track; t; t = t->Next() )
899  {
900  connections.SearchConnectedTracks( t );
901  connections.GetConnectedTracks( t );
902  }
903 
904  // Propagate net codes from a segment to other connected segments
905  bool new_pass_request = true; // set to true if a track has its netcode changed from 0
906  // to a known netcode to re-evaluate netcodes
907  // of connected items
908  while( new_pass_request )
909  {
910  new_pass_request = false;
911 
912  for( TRACK* t = m_Pcb->m_Track; t; t = t->Next() )
913  {
914  int netcode = t->GetNetCode();
915 
916  if( netcode == 0 )
917  {
918  // try to find a connected item having a netcode
919  for( unsigned kk = 0; kk < t->m_TracksConnected.size(); kk++ )
920  {
921  int altnetcode = t->m_TracksConnected[kk]->GetNetCode();
922  if( altnetcode )
923  {
924  new_pass_request = true;
925  netcode = altnetcode;
926  t->SetNetCode(netcode);
927  break;
928  }
929  }
930  }
931 
932  if( netcode ) // this track has a netcode
933  {
934  // propagate this netcode to connected tracks having no netcode
935  for( unsigned kk = 0; kk < t->m_TracksConnected.size(); kk++ )
936  {
937  int altnetcode = t->m_TracksConnected[kk]->GetNetCode();
938  if( altnetcode == 0 )
939  {
940  t->m_TracksConnected[kk]->SetNetCode(netcode);
941  new_pass_request = true;
942  }
943  }
944  }
945  }
946  }
947 
948  if( IsGalCanvasActive() )
949  {
951  for( TRACK* track = m_Pcb->m_Track; track; track = track->Next() )
952  GetGalCanvas()->GetView()->Update( track );
953  }
954 
955  // Sort the track list by net codes:
957 }
958 
959 
960 
961 /*
962  * Function SortTracksByNetCode used in RebuildTrackChain()
963  * to sort track segments by net code.
964  */
965 static bool SortTracksByNetCode( const TRACK* const & ref, const TRACK* const & compare )
966 {
967  // For items having the same Net, keep the order in list
968  if( ref->GetNetCode() == compare->GetNetCode())
969  return ref->m_Param < compare->m_Param;
970 
971  return ref->GetNetCode() < compare->GetNetCode();
972 }
973 
981 static void RebuildTrackChain( BOARD* pcb )
982 {
983  if( pcb->m_Track == NULL )
984  return;
985 
986  int item_count = pcb->m_Track.GetCount();
987 
988  std::vector<TRACK*> trackList;
989  trackList.reserve( item_count );
990 
991  // Put track list in a temporary list to sort tracks by netcode
992  // We try to keep the initial order of track segments in list, when possible
993  // so we use m_Param (a member variable used for temporary storage)
994  // to temporary keep trace of the order of segments
995  // The sort function uses this variable to sort items that
996  // have the same net code.
997  // Without this, during sorting, the initial order is sometimes lost
998  // by the sort algorithm
999  for( int ii = 0; ii < item_count; ++ii )
1000  {
1001  pcb->m_Track->m_Param = ii;
1002  trackList.push_back( pcb->m_Track.PopFront() );
1003  }
1004 
1005  // the list is empty now
1006  wxASSERT( pcb->m_Track == NULL && pcb->m_Track.GetCount()==0 );
1007 
1008  sort( trackList.begin(), trackList.end(), SortTracksByNetCode );
1009 
1010  // add them back to the list
1011  for( int i = 0; i < item_count; ++i )
1012  pcb->m_Track.PushBack( trackList[i] );
1013 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:104
KICAD_T Type() const
Function Type()
Definition: base_struct.h:198
void BuildListOfNets()
Definition: class_board.h:764
TRACK * GetTrack(TRACK *aStartTrace, TRACK *aEndTrace, ENDPOINT_T aEndPoint, bool aSameNetOnly, bool aSequential)
Function GetTrack returns the trace segment connected to the segment at aEndPoint from aStartTrace to...
TRACK * GetTrack(TRACK *aStartTrace, const TRACK *aEndTrace, const wxPoint &aPosition, LSET aLayerMask)
Function GetTrack is a helper function to locate a trace segment having an end point at aPosition on ...
Definition: class_track.cpp:68
static bool sortConnectedPointByXthenYCoordinates(const CONNECTED_POINT &aRef, const CONNECTED_POINT &aTst)
Definition: connect.cpp:244
#define IN_EDIT
Item currently edited.
Definition: base_struct.h:111
void TestForActiveLinksInRatsnest(int aNetCode)
Function TestForActiveLinksInRatsnest Explores the full rats nest list (which must exist) to determin...
Definition: ratsnest.cpp:469
bool HitTest(const wxPoint &aPosition) const override
Function HitTest tests if aPosition is contained within or on the bounding area of an item...
Definition: class_pad.cpp:752
#define END_ONPAD
Pcbnew: flag set for track segment ending on a pad.
Definition: base_struct.h:133
unsigned GetUnconnectedNetCount() const
Function GetUnconnectedNetCount.
Definition: class_board.h:727
static int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:107
void TestNetConnection(wxDC *aDC, int aNetCode)
Function TestNetConnection tests the connections relative to aNetCode.
Definition: connect.cpp:786
void GetConnectedTracks(TRACK *aTrack)
Function GetConnectedTracks Copy m_Connected that contains the list of tracks connected calculated by...
Definition: connect.h:170
void BuildPadsCandidatesList()
Function BuildPadsCandidatesList Populates m_candidates with all pads connecting points (pads positio...
Definition: connect.cpp:227
helper classes to find track to track and track to pad connections.
void Build_CurrNet_SubNets_Connections(TRACK *aFirstTrack, TRACK *aLastTrack, int aNetcode)
Function Build_CurrNet_SubNets_Connections should be called after a track change (delete or add a tra...
Definition: connect.cpp:459
void GetSortedPadListByXthenYCoord(std::vector< D_PAD * > &aVector, int aNetCode=-1)
Function GetSortedPadListByXthenYCoord first empties then fills the vector with all pads and sorts th...
int Merge_PadsSubNets(int aOldSubNet, int aNewSubNet)
Function Merge_PadsSubNets Change a subnet value to a new value, in m_sortedPads pad list After that...
Definition: connect.cpp:500
static const int dist[10][10]
Definition: dist.cpp:57
void Merge_SubNets_Connected_By_CopperAreas(BOARD *aPcb)
Function Merge_SubNets_Connected_By_CopperAreas(BOARD* aPcb) Calls Merge_SubNets_Connected_By_CopperA...
BOARD * GetBoard() const
CONNECTIONS(BOARD *aBrd)
Definition: connect.cpp:49
#define BUSY
Pcbnew: flag indicating that the structure has.
Definition: base_struct.h:134
KIGFX::VIEW * GetView() const
Function GetView() Returns a pointer to the VIEW instance used in the panel.
#define BEGIN_ONPAD
Pcbnew: flag set for track segment starting on a pad.
Definition: base_struct.h:132
BOARD * m_brd
Definition: connect.h:98
#define abs(a)
Definition: auxiliary.h:84
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
static const int delta[8][2]
Definition: solve.cpp:112
const wxPoint & GetEnd() const
Definition: class_track.h:118
const TRACK * m_lastTrack
Definition: connect.h:100
void Propagate_SubNets()
Function Propagate_SubNets Test a list of tracks, to create or propagate a sub netcode to pads and se...
Definition: connect.cpp:584
void BuildPadsList(int aNetcode=-1)
Function BuildPadsList Fills m_sortedPads with all pads that be connected to tracks pads are sorted b...
Definition: connect.cpp:61
double m_Param
Definition: class_track.h:92
std::vector< D_PAD * > m_sortedPads
Definition: connect.h:101
This file contains miscellaneous commonly used macros and functions.
void PushBack(T *aNewElement)
Function PushBack puts aNewElement at the end of the list sequence.
Definition: dlist.h:250
std::vector< RATSNEST_ITEM > m_FullRatsnest
Ratsnest list for the BOARD.
Definition: class_board.h:248
void TestConnections()
Function TestConnections tests the connections relative to all nets.
Definition: connect.cpp:733
const wxPoint & GetPoint() const
Definition: connect.h:87
unsigned m_RatsnestStartIdx
Class LSET is a set of PCB_LAYER_IDs.
unsigned GetRatsnestsCount() const
Function GetNumRatsnests.
Definition: class_board.h:704
void BuildTracksCandidatesList(TRACK *aBegin, TRACK *aEnd=NULL)
Function BuildTracksCandidatesList Fills m_Candidates with all connecting points (track ends or via l...
Definition: connect.cpp:252
Classes used in Pcbnew, CvPcb and GerbView.
TRACK * GetTrack() const
Function GetTrack.
Definition: connect.h:72
int SearchConnectedTracks(const TRACK *aTrack)
function SearchConnectedTracks Populates .m_connected with tracks/vias connected to aTrack m_candidat...
Definition: connect.cpp:306
int GetBoundingRadius() const
Function GetBoundingRadius returns the radius of a minimum sized circle which fully encloses this pad...
Definition: class_pad.h:428
const wxPoint & GetStart() const
Definition: class_track.h:121
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
void RecalculateAllTracksNetcode()
Function RecalculateAllTracksNetcode search connections between tracks and pads and propagate pad net...
Definition: connect.cpp:861
LSET GetLayerSet() const override
Function GetLayerSet returns a "layer mask", which is a bitmap of all layers on which the TRACK segme...
Definition: class_pad.h:235
void DrawGeneralRatsnest(wxDC *aDC, int aNetcode=0)
function Displays the general ratsnest Only ratsnest with the status bit CH_VISIBLE is set are displa...
Definition: ratsnest.cpp:300
T * GetFirst() const
Function GetFirst returns the first T* in the list without removing it, or NULL if the list is empty...
Definition: dlist.h:163
virtual LSET GetLayerSet() const
Function GetLayerSet returns a "layer mask", which is a bitmap of all layers on which the TRACK segme...
void SearchConnectionsPadsToIntersectingPads()
function SearchConnectionsPadsToIntersectingPads Explores the list of pads and adds to m_PadsConnecte...
Definition: connect.cpp:72
TRACK * GetEndNetCode(int NetCode)
bool IsGalCanvasActive() const
Function IsGalCanvasActive is used to check which canvas (GAL-based or standard) is currently in use...
Definition: draw_frame.h:795
void SearchTracksConnectedToPads(bool add_to_padlist=true, bool add_to_tracklist=true)
function SearchTracksConnectedToPads Explores the list of pads.
Definition: connect.cpp:114
int Merge_SubNets(int aOldSubNet, int aNewSubNet)
Function Merge_SubNets Change a subnet old value to a new value, for tracks and pads which are connec...
Definition: connect.cpp:529
void Test_Connections_To_Copper_Areas(int aNetcode=-1)
Function Test_Connection_To_Copper_Areas init .m_ZoneSubnet parameter in tracks and pads according to...
std::vector< CONNECTED_POINT > m_candidates
Definition: connect.h:96
D_PAD * GetPad(unsigned aIndex) const
Function GetPad.
Definition: class_board.h:750
std::vector< D_PAD * > m_PadsConnected
void Update(VIEW_ITEM *aItem)
Function Update() For dynamic VIEWs, informs the associated VIEW that the graphical representation of...
Definition: view.cpp:1379
unsigned GetPadCount() const
Function GetPadCount.
Definition: class_board.h:741
void SetSubNet(int aSubNetCode)
void Compile_Ratsnest(wxDC *aDC, bool aDisplayStatus)
Function Compile_Ratsnest Create the entire board ratsnest.
Definition: ratsnest.cpp:165
int GetNetCode() const
Function GetNetCode.
Class NETINFO_ITEM handles the data for a net.
TRACK * Next() const
Definition: class_track.h:98
void SetZoneSubNet(int aSubNetCode)
TRACK * GetStartNetCode(int NetCode)
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:166
int GetWidth() const
Definition: class_track.h:115
int GetSubNet() const
Function GetSubNet.
void CollectItemsNearTo(std::vector< CONNECTED_POINT * > &aList, const wxPoint &aPosition, int aDistMax)
function CollectItemsNearTo Used by SearchTracksConnectedToPads Fills aList with pads near to aPositi...
Definition: connect.cpp:146
const TRACK * m_firstTrack
Definition: connect.h:99
NETINFO_ITEM * FindNet(int aNetcode) const
Function FindNet searches for a net with the given netcode.
The common library.
wxPoint ShapePos() const
Definition: class_pad.cpp:418
static bool SortTracksByNetCode(const TRACK *const &ref, const TRACK *const &compare)
Definition: connect.cpp:965
unsigned GetCount() const
Function GetCount returns the number of elements in the list.
Definition: dlist.h:126
std::vector< TRACK * > m_TracksConnected
EDA_DRAW_PANEL_GAL * GetGalCanvas() const
Function GetGalCanvas returns a pointer to GAL-based canvas of given EDA draw frame.
Definition: draw_frame.h:803
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:108
DLIST< TRACK > m_Track
Definition: class_board.h:244
static const int UNCONNECTED
Constant that holds the "unconnected net" number (typically 0) all items "connected" to this net are ...
int searchEntryPointInCandidatesList(const wxPoint &aPoint)
function searchEntryPointInCandidatesList Search an item in m_Connected connected to aPoint note m_Co...
Definition: connect.cpp:396
D_PAD * GetPad() const
Function GetPad.
Definition: connect.h:82
T * PopFront()
Definition: dlist.h:221
unsigned GetNetCount() const
Function GetNetCount.
Definition: class_board.h:814
std::vector< TRACK * > m_connected
Definition: connect.h:94
static void RebuildTrackChain(BOARD *pcb)
Helper function RebuildTrackChain rebuilds the track segment linked list in order to have a chain sor...
Definition: connect.cpp:981
int m_Status_Pcb
Flags used in ratsnest calculation and update.
Definition: class_board.h:240