KiCad PCB EDA Suite
CONNECTIONS Class Reference

#include <connect.h>

Inheritance diagram for CONNECTIONS:
TRACKS_CLEANER

Public Member Functions

 CONNECTIONS (BOARD *aBrd)
 
 ~CONNECTIONS ()
 
void BuildPadsList (int aNetcode=-1)
 Function BuildPadsList Fills m_sortedPads with all pads that be connected to tracks pads are sorted by X then Y coordinates to allow fast binary search in list. More...
 
std::vector< D_PAD * > & GetPadsList ()
 Function GetPadsList. More...
 
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 track): Connections to pads and to tracks are recalculated If a track is deleted, the other pointers to pads do not change. More...
 
void BuildTracksCandidatesList (TRACK *aBegin, TRACK *aEnd=NULL)
 Function BuildTracksCandidatesList Fills m_Candidates with all connecting points (track ends or via location) with tracks from aBegin to aEnd. More...
 
void BuildPadsCandidatesList ()
 Function BuildPadsCandidatesList Populates m_candidates with all pads connecting points (pads position) m_sortedPads is expected to be populated by the pad candidates list. More...
 
int SearchConnectedTracks (const TRACK *aTrack)
 function SearchConnectedTracks Populates .m_connected with tracks/vias connected to aTrack m_candidates is expected to be populated by the track candidates ends list More...
 
void GetConnectedTracks (TRACK *aTrack)
 Function GetConnectedTracks Copy m_Connected that contains the list of tracks connected calculated by SearchConnectedTracks in aTrack->m_TracksConnected. More...
 
void SearchConnectionsPadsToIntersectingPads ()
 function SearchConnectionsPadsToIntersectingPads Explores the list of pads and adds to m_PadsConnected member of each pad pads connected to Here, connections are due to intersecting pads, not tracks m_sortedPads must be initialized More...
 
void SearchTracksConnectedToPads (bool add_to_padlist=true, bool add_to_tracklist=true)
 function SearchTracksConnectedToPads Explores the list of pads. More...
 
void CollectItemsNearTo (std::vector< CONNECTED_POINT * > &aList, const wxPoint &aPosition, int aDistMax)
 function CollectItemsNearTo Used by SearchTracksConnectedToPads Fills aList with pads near to aPosition near means aPosition to pad position <= aDistMax More...
 
void Propagate_SubNets ()
 Function Propagate_SubNets Test a list of tracks, to create or propagate a sub netcode to pads and segments connected together. More...
 

Private Member Functions

int searchEntryPointInCandidatesList (const wxPoint &aPoint)
 function searchEntryPointInCandidatesList Search an item in m_Connected connected to aPoint note m_Connected containts usually more than one candidate and searchEntryPointInCandidatesList returns an index to one of these candidates Others are neightbor of the indexed item. More...
 
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 connected to tracks from m_firstTrack to m_lastTrack and their connected pads. More...
 
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, 2 cluster (or subnets) are merged into only one. More...
 

Private Attributes

std::vector< TRACK * > m_connected
 
std::vector< CONNECTED_POINTm_candidates
 
BOARDm_brd
 
const TRACKm_firstTrack
 
const TRACKm_lastTrack
 
std::vector< D_PAD * > m_sortedPads
 

Detailed Description

Definition at line 91 of file connect.h.

Constructor & Destructor Documentation

CONNECTIONS::CONNECTIONS ( BOARD aBrd)

Definition at line 49 of file connect.cpp.

References m_brd, m_firstTrack, and m_lastTrack.

50 {
51  m_brd = aBrd;
52  m_firstTrack = NULL;
53  m_lastTrack = NULL;
54 }
BOARD * m_brd
Definition: connect.h:98
const TRACK * m_lastTrack
Definition: connect.h:100
const TRACK * m_firstTrack
Definition: connect.h:99
CONNECTIONS::~CONNECTIONS ( )
inline

Definition at line 105 of file connect.h.

105 {};

Member Function Documentation

void CONNECTIONS::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 track): Connections to pads and to tracks are recalculated If a track is deleted, the other pointers to pads do not change.

When a new track is added in track list, its pointers to pads are already initialized Builds the subnets inside a net (tracks from aFirstTrack to aFirstTrack). subnets are clusters of pads and tracks that are connected together. When all tracks are created relative to the net, there is only a cluster when not tracks there are a cluster per pad

Parameters
aFirstTrack= first track of the given net
aLastTrack= last track of the given net
aNetcode= the netcode of the given net

Definition at line 459 of file connect.cpp.

References BuildPadsList(), BuildTracksCandidatesList(), m_connected, m_firstTrack, m_lastTrack, BOARD_CONNECTED_ITEM::m_PadsConnected, BOARD_CONNECTED_ITEM::m_TracksConnected, TRACK::Next(), Propagate_SubNets(), SearchConnectedTracks(), SearchConnectionsPadsToIntersectingPads(), SearchTracksConnectedToPads(), and BOARD_CONNECTED_ITEM::SetSubNet().

Referenced by PCB_BASE_FRAME::TestConnections(), and PCB_BASE_FRAME::TestNetConnection().

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 }
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
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
int SearchConnectedTracks(const TRACK *aTrack)
function SearchConnectedTracks Populates .m_connected with tracks/vias connected to aTrack m_candidat...
Definition: connect.cpp:306
void SearchConnectionsPadsToIntersectingPads()
function SearchConnectionsPadsToIntersectingPads Explores the list of pads and adds to m_PadsConnecte...
Definition: connect.cpp:72
void SearchTracksConnectedToPads(bool add_to_padlist=true, bool add_to_tracklist=true)
function SearchTracksConnectedToPads Explores the list of pads.
Definition: connect.cpp:114
std::vector< D_PAD * > m_PadsConnected
void SetSubNet(int aSubNetCode)
TRACK * Next() const
Definition: class_track.h:98
const TRACK * m_firstTrack
Definition: connect.h:99
std::vector< TRACK * > m_TracksConnected
std::vector< TRACK * > m_connected
Definition: connect.h:94
void CONNECTIONS::BuildPadsCandidatesList ( )

Function BuildPadsCandidatesList Populates m_candidates with all pads connecting points (pads position) m_sortedPads is expected to be populated by the pad candidates list.

Definition at line 227 of file connect.cpp.

References D_PAD::GetPosition(), m_candidates, and m_sortedPads.

Referenced by SearchConnectionsPadsToIntersectingPads().

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 }
std::vector< D_PAD * > m_sortedPads
Definition: connect.h:101
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
std::vector< CONNECTED_POINT > m_candidates
Definition: connect.h:96
void CONNECTIONS::BuildPadsList ( int  aNetcode = -1)

Function BuildPadsList Fills m_sortedPads with all pads that be connected to tracks pads are sorted by X then Y coordinates to allow fast binary search in list.

Parameters
aNetcode= net code to use to filter pads if aNetcode < 0, all pads will be put in list (default)

Definition at line 61 of file connect.cpp.

References BOARD::GetSortedPadListByXthenYCoord(), m_brd, and m_sortedPads.

Referenced by Build_CurrNet_SubNets_Connections(), PCB_BASE_FRAME::RecalculateAllTracksNetcode(), and TRACKS_CLEANER::TRACKS_CLEANER().

62 {
63  // Creates sorted pad list if not exists
64  m_sortedPads.clear();
65  m_brd->GetSortedPadListByXthenYCoord( m_sortedPads, aNetcode < 0 ? -1 : aNetcode );
66 }
void GetSortedPadListByXthenYCoord(std::vector< D_PAD * > &aVector, int aNetCode=-1)
Function GetSortedPadListByXthenYCoord first empties then fills the vector with all pads and sorts th...
BOARD * m_brd
Definition: connect.h:98
std::vector< D_PAD * > m_sortedPads
Definition: connect.h:101
void CONNECTIONS::BuildTracksCandidatesList ( TRACK aBegin,
TRACK aEnd = NULL 
)

Function BuildTracksCandidatesList Fills m_Candidates with all connecting points (track ends or via location) with tracks from aBegin to aEnd.

Parameters
aBegin= first track to store in list (should not be NULL)
aEnd= last track to store in list if aEnd == NULL, uses all tracks from aBegin

Definition at line 252 of file connect.cpp.

References m_candidates, m_firstTrack, m_lastTrack, TRACK::Next(), PCB_VIA_T, and sortConnectedPointByXthenYCoordinates().

Referenced by Build_CurrNet_SubNets_Connections(), TRACKS_CLEANER::buildTrackConnectionInfo(), DRAG_LIST::fillList(), PCB_BASE_FRAME::RecalculateAllTracksNetcode(), and TRACKS_CLEANER::removeBadTrackSegments().

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 }
static bool sortConnectedPointByXthenYCoordinates(const CONNECTED_POINT &aRef, const CONNECTED_POINT &aTst)
Definition: connect.cpp:244
const TRACK * m_lastTrack
Definition: connect.h:100
std::vector< CONNECTED_POINT > m_candidates
Definition: connect.h:96
TRACK * Next() const
Definition: class_track.h:98
const TRACK * m_firstTrack
Definition: connect.h:99
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:108
void CONNECTIONS::CollectItemsNearTo ( std::vector< CONNECTED_POINT * > &  aList,
const wxPoint aPosition,
int  aDistMax 
)

function CollectItemsNearTo Used by SearchTracksConnectedToPads Fills aList with pads near to aPosition near means aPosition to pad position <= aDistMax

Parameters
aList= list to fill
aPosition= aPosition to use as reference
aDistMax= dist max from aPosition to a candidate to select it

Definition at line 146 of file connect.cpp.

References abs, delta, dist, CONNECTED_POINT::GetPoint(), m_candidates, wxPoint::x, and wxPoint::y.

Referenced by SearchConnectedTracks(), SearchConnectionsPadsToIntersectingPads(), and SearchTracksConnectedToPads().

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 }
static const int dist[10][10]
Definition: dist.cpp:57
#define abs(a)
Definition: auxiliary.h:84
static const int delta[8][2]
Definition: solve.cpp:112
const wxPoint & GetPoint() const
Definition: connect.h:87
std::vector< CONNECTED_POINT > m_candidates
Definition: connect.h:96
void CONNECTIONS::GetConnectedTracks ( TRACK aTrack)
inline

Function GetConnectedTracks Copy m_Connected that contains the list of tracks connected calculated by SearchConnectedTracks in aTrack->m_TracksConnected.

Parameters
aTrack= track or via to fill with connected tracks

Definition at line 170 of file connect.h.

References m_connected, and BOARD_CONNECTED_ITEM::m_TracksConnected.

Referenced by PCB_BASE_FRAME::RecalculateAllTracksNetcode(), and TRACKS_CLEANER::removeBadTrackSegments().

171  {
172  aTrack->m_TracksConnected = m_connected;
173  }
std::vector< TRACK * > m_TracksConnected
std::vector< TRACK * > m_connected
Definition: connect.h:94
std::vector<D_PAD*>& CONNECTIONS::GetPadsList ( )
inline

Function GetPadsList.

Returns
the pads list used in connections calculations

Definition at line 120 of file connect.h.

References m_sortedPads.

Referenced by DRAG_LIST::BuildDragListe(), and DRAG_LIST::fillList().

120 { return m_sortedPads; }
std::vector< D_PAD * > m_sortedPads
Definition: connect.h:101
int CONNECTIONS::Merge_PadsSubNets ( int  aOldSubNet,
int  aNewSubNet 
)
private

Function Merge_PadsSubNets Change a subnet value to a new value, in m_sortedPads pad list After that, 2 cluster (or subnets) are merged into only one.

Change a subnet value to a new value, in m_sortedPads pad list After that, 2 cluster (or subnets) are merged into only one.

Note: the resulting subnet value is the smallest between aOldSubNet et aNewSubNet

Returns
modification count
Parameters
aOldSubNet= subnet value to modify
aNewSubNet= new subnet value for each item which have old_val as subnet value

Note: the resulting subnet value is the smallest between aOldSubNet et aNewSubNet

Definition at line 500 of file connect.cpp.

References BOARD_CONNECTED_ITEM::GetSubNet(), m_sortedPads, and BOARD_CONNECTED_ITEM::SetSubNet().

Referenced by Propagate_SubNets().

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 }
std::vector< D_PAD * > m_sortedPads
Definition: connect.h:101
void SetSubNet(int aSubNetCode)
int GetSubNet() const
Function GetSubNet.
int CONNECTIONS::Merge_SubNets ( int  aOldSubNet,
int  aNewSubNet 
)
private

Function Merge_SubNets Change a subnet old value to a new value, for tracks and pads which are connected to tracks from m_firstTrack to m_lastTrack and their connected pads.

and modify the subnet parameter (change the old value to the new value). After that, 2 cluster (or subnets) are merged into only one. Note: the resulting sub net value is the smallest between aOldSubNet and aNewSubNet

Returns
modification count
Parameters
aOldSubNet= subnet value to modify
aNewSubNet= new subnet value for each item which have old_val as subnet value

Definition at line 529 of file connect.cpp.

References BOARD_CONNECTED_ITEM::GetSubNet(), m_firstTrack, m_lastTrack, BOARD_CONNECTED_ITEM::m_PadsConnected, TRACK::Next(), and BOARD_CONNECTED_ITEM::SetSubNet().

Referenced by Propagate_SubNets().

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 }
const TRACK * m_lastTrack
Definition: connect.h:100
std::vector< D_PAD * > m_PadsConnected
void SetSubNet(int aSubNetCode)
TRACK * Next() const
Definition: class_track.h:98
int GetSubNet() const
Function GetSubNet.
const TRACK * m_firstTrack
Definition: connect.h:99
void CONNECTIONS::Propagate_SubNets ( )

Function Propagate_SubNets Test a list of tracks, to create or propagate a sub netcode to pads and segments connected together.

The track list must be sorted by nets, and all segments from m_firstTrack to m_lastTrack have the same net. When 2 items are connected (a track to a pad, or a track to an other track), they are grouped in a cluster. For pads, this is the .m_physical_connexion member which is a cluster identifier For tracks, this is the .m_Subnet member which is a cluster identifier For a given net, if all tracks are created, there is only one cluster. but if not all tracks are created, there are more than one cluster, and some ratsnests will be left active.

Definition at line 584 of file connect.cpp.

References BOARD_CONNECTED_ITEM::GetSubNet(), m_firstTrack, m_lastTrack, BOARD_CONNECTED_ITEM::m_PadsConnected, m_sortedPads, BOARD_CONNECTED_ITEM::m_TracksConnected, Merge_PadsSubNets(), Merge_SubNets(), TRACK::Next(), and BOARD_CONNECTED_ITEM::SetSubNet().

Referenced by Build_CurrNet_SubNets_Connections().

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 }
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
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
const TRACK * m_lastTrack
Definition: connect.h:100
std::vector< D_PAD * > m_sortedPads
Definition: connect.h:101
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
std::vector< D_PAD * > m_PadsConnected
void SetSubNet(int aSubNetCode)
TRACK * Next() const
Definition: class_track.h:98
int GetSubNet() const
Function GetSubNet.
const TRACK * m_firstTrack
Definition: connect.h:99
std::vector< TRACK * > m_TracksConnected
int CONNECTIONS::SearchConnectedTracks ( const TRACK aTrack)

function SearchConnectedTracks Populates .m_connected with tracks/vias connected to aTrack m_candidates is expected to be populated by the track candidates ends list

Parameters
aTrack= track or via to use as reference

Definition at line 306 of file connect.cpp.

References CollectItemsNearTo(), delta, dist, EuclideanNorm(), TRACK::GetEnd(), BOARD_ITEM::GetLayerSet(), TRACK::GetStart(), GetTrack(), TRACK::GetTrack(), TRACK::GetWidth(), KiROUND(), m_candidates, m_connected, PCB_VIA_T, searchEntryPointInCandidatesList(), and EDA_ITEM::Type().

Referenced by Build_CurrNet_SubNets_Connections(), PCB_BASE_FRAME::RecalculateAllTracksNetcode(), and TRACKS_CLEANER::removeBadTrackSegments().

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 }
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
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 int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:107
static const int dist[10][10]
Definition: dist.cpp:57
static const int delta[8][2]
Definition: solve.cpp:112
const wxPoint & GetEnd() const
Definition: class_track.h:118
Class LSET is a set of PCB_LAYER_IDs.
const wxPoint & GetStart() const
Definition: class_track.h:121
virtual LSET GetLayerSet() const
Function GetLayerSet returns a "layer mask", which is a bitmap of all layers on which the TRACK segme...
std::vector< CONNECTED_POINT > m_candidates
Definition: connect.h:96
int GetWidth() const
Definition: class_track.h:115
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
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:108
int searchEntryPointInCandidatesList(const wxPoint &aPoint)
function searchEntryPointInCandidatesList Search an item in m_Connected connected to aPoint note m_Co...
Definition: connect.cpp:396
std::vector< TRACK * > m_connected
Definition: connect.h:94
void CONNECTIONS::SearchConnectionsPadsToIntersectingPads ( )

function SearchConnectionsPadsToIntersectingPads Explores the list of pads and adds to m_PadsConnected member of each pad pads connected to Here, connections are due to intersecting pads, not tracks m_sortedPads must be initialized

Definition at line 72 of file connect.cpp.

References BuildPadsCandidatesList(), CollectItemsNearTo(), D_PAD::GetBoundingRadius(), D_PAD::GetLayerSet(), CONNECTED_POINT::GetPad(), CONNECTED_POINT::GetPoint(), D_PAD::HitTest(), BOARD_CONNECTED_ITEM::m_PadsConnected, m_sortedPads, and D_PAD::ShapePos().

Referenced by Build_CurrNet_SubNets_Connections().

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 }
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:700
void BuildPadsCandidatesList()
Function BuildPadsCandidatesList Populates m_candidates with all pads connecting points (pads positio...
Definition: connect.cpp:227
std::vector< D_PAD * > m_sortedPads
Definition: connect.h:101
const wxPoint & GetPoint() const
Definition: connect.h:87
int GetBoundingRadius() const
Function GetBoundingRadius returns the radius of a minimum sized circle which fully encloses this pad...
Definition: class_pad.h:428
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
std::vector< D_PAD * > m_PadsConnected
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
wxPoint ShapePos() const
Definition: class_pad.cpp:367
D_PAD * GetPad() const
Function GetPad.
Definition: connect.h:82
int CONNECTIONS::searchEntryPointInCandidatesList ( const wxPoint aPoint)
private

function searchEntryPointInCandidatesList Search an item in m_Connected connected to aPoint note m_Connected containts usually more than one candidate and searchEntryPointInCandidatesList returns an index to one of these candidates Others are neightbor of the indexed item.

Parameters
aPointis the reference coordinates
Returns
the index of item found or -1 if no candidate

Definition at line 396 of file connect.cpp.

References delta, CONNECTED_POINT::GetPoint(), m_candidates, wxPoint::x, and wxPoint::y.

Referenced by SearchConnectedTracks().

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 }
static const int delta[8][2]
Definition: solve.cpp:112
const wxPoint & GetPoint() const
Definition: connect.h:87
std::vector< CONNECTED_POINT > m_candidates
Definition: connect.h:96
void CONNECTIONS::SearchTracksConnectedToPads ( bool  add_to_padlist = true,
bool  add_to_tracklist = true 
)

function SearchTracksConnectedToPads Explores the list of pads.

if( add_to_padlist ) adds to m_PadsConnected member of each track the pad(s) connected to if add_to_tracklist adds to m_TracksConnected member of each pad the track(s) connected to D_PAD::m_TracksConnected is cleared before adding items TRACK::m_PadsConnected is not cleared

Parameters
add_to_padlist= true to fill m_PadsConnected member of each track
add_to_tracklist= true to fill m_TracksConnected member of each pad

Definition at line 114 of file connect.cpp.

References CollectItemsNearTo(), D_PAD::GetBoundingRadius(), BOARD_ITEM::GetLayerSet(), D_PAD::GetLayerSet(), CONNECTED_POINT::GetPoint(), D_PAD::GetPosition(), CONNECTED_POINT::GetTrack(), D_PAD::HitTest(), BOARD_CONNECTED_ITEM::m_PadsConnected, m_sortedPads, and BOARD_CONNECTED_ITEM::m_TracksConnected.

Referenced by Build_CurrNet_SubNets_Connections(), TRACKS_CLEANER::buildTrackConnectionInfo(), DRAG_LIST::fillList(), PCB_BASE_FRAME::RecalculateAllTracksNetcode(), and TRACKS_CLEANER::removeBadTrackSegments().

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 }
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:700
std::vector< D_PAD * > m_sortedPads
Definition: connect.h:101
const wxPoint & GetPoint() const
Definition: connect.h:87
TRACK * GetTrack() const
Function GetTrack.
Definition: connect.h:72
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 & GetPosition() const override
Definition: class_pad.h:170
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
virtual LSET GetLayerSet() const
Function GetLayerSet returns a "layer mask", which is a bitmap of all layers on which the TRACK segme...
std::vector< D_PAD * > m_PadsConnected
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
std::vector< TRACK * > m_TracksConnected

Member Data Documentation

BOARD* CONNECTIONS::m_brd
private

Definition at line 98 of file connect.h.

Referenced by BuildPadsList(), and CONNECTIONS().

std::vector<CONNECTED_POINT> CONNECTIONS::m_candidates
private
std::vector<TRACK*> CONNECTIONS::m_connected
private
const TRACK* CONNECTIONS::m_firstTrack
private
const TRACK* CONNECTIONS::m_lastTrack
private

The documentation for this class was generated from the following files: