KiCad PCB EDA Suite
ratsnest.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) 2007-2014 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 1992-2012 KiCad Developers, see AUTHORS.txt for contributors.
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 
30 #include <fctsys.h>
31 #include <gr_basic.h>
32 #include <common.h>
33 #include <class_drawpanel.h>
34 #include <colors_selection.h>
35 #include <wxBasePcbFrame.h>
36 #include <macros.h>
37 
38 #include <class_board.h>
39 #include <class_module.h>
40 #include <class_track.h>
41 
42 #include <pcbnew.h>
43 
44 #include <minimun_spanning_tree.h>
45 
52 {
53  friend class MIN_SPAN_TREE;
54 public:
55  std::vector <D_PAD*>* m_PadsList; // list of pads:
56  /* these pads are the parents of nodes of the tree.
57  * Each node position is the corresponding pad position.
58  * This pad list is used to evaluate the weight of an edge in tree.
59  * -> edge = link between 2 nodes = links between 2 pads.
60  * -> weight of a link = rectilinear distance between the 2 pads
61  */
62 
63 public:
65  {
66  m_PadsList = NULL;
67  }
68 
69  void MSP_Init( std::vector <D_PAD*>* aPadsList )
70  {
71  m_PadsList = aPadsList;
72  MIN_SPAN_TREE::MSP_Init( (int) m_PadsList->size() );
73  }
74 
81  void AddTreeToRatsnest( std::vector<RATSNEST_ITEM>* aRatsnestList );
82 
91  int GetWeight( int aItem1, int aItem2 ) override;
92 };
93 
94 
95 void MIN_SPAN_TREE_PADS::AddTreeToRatsnest( std::vector<RATSNEST_ITEM>* aRatsnestList )
96 {
97  std::vector<D_PAD*>& padsBuffer = *m_PadsList;
98 
99  if( padsBuffer.empty() )
100  return;
101 
102  int netcode = padsBuffer[0]->GetNetCode();
103 
104  // Note: to get edges in minimum spanning tree,
105  // the index value 0 is not used: it is just
106  // the entry point of the minimum spanning tree.
107  // The first edge (i.e. rastnest) starts at index 1
108  for( int ii = 1; ii < m_Size; ii++ )
109  {
110  // Create the new ratsnest
111  RATSNEST_ITEM net;
112 
113  net.SetNet( netcode );
114  net.m_Status = CH_ACTIF | CH_VISIBLE;
115  net.m_Length = GetDist(ii);
116  net.m_PadStart = padsBuffer[ii];
117  net.m_PadEnd = padsBuffer[ GetWhoTo(ii) ];
118 
119  aRatsnestList->push_back( net );
120  }
121 }
122 
123 /* Function GetWeight
124  * calculates the weight between 2 items
125  * Here it calculate the rectilinear distance between 2 pads (2 items)
126  * NOTE: The weight between a node and itself should be <=0
127  * aItem1 and aItem2 are the 2 items
128  * return the rectilinear distance
129  */
130 int MIN_SPAN_TREE_PADS::GetWeight( int aItem1, int aItem2 )
131 {
132  // NOTE: The distance (weight) between a node and itself should be 0
133  // so we add 1 to other distances to be sure we never have 0
134  // in cases other than a node and itself
135 
136  D_PAD* pad1 = (*m_PadsList)[aItem1];
137  D_PAD* pad2 = (*m_PadsList)[aItem2];
138 
139  if( pad1 == pad2 )
140  return 0;
141 
142  int weight = abs( pad2->GetPosition().x - pad1->GetPosition().x ) +
143  abs( pad2->GetPosition().y - pad1->GetPosition().y );
144  return weight + 1;
145 }
146 
147 
148 /* Note about the ratsnest computation:
149  * Building the general ratsnest:
150  * For each net, the ratsnest is the set of lines connecting pads,
151  * using the shorter distance
152  * Therefore this problem is well known in graph therory, and sloved
153  * using the "minimum spanning tree".
154  * We use here an algorithm to build the minimum spanning tree known as Prim's algorithm
155  */
156 
165 void PCB_BASE_FRAME::Compile_Ratsnest( wxDC* aDC, bool aDisplayStatus )
166 {
167  wxString msg;
168 
169  GetBoard()->m_Status_Pcb = 0; // we want a full ratsnest computation, from the scratch
170  ClearMsgPanel();
171 
172  // Rebuild the full pads and net info list
174 
175  if( aDisplayStatus )
176  {
177  msg.Printf( wxT( " %d" ), m_Pcb->GetPadCount() );
178  AppendMsgPanel( wxT( "Pads" ), msg, RED );
179  msg.Printf( wxT( " %d" ), m_Pcb->GetNetCount() );
180  AppendMsgPanel( wxT( "Nets" ), msg, CYAN );
181  }
182 
183  /* Compute the full ratsnest
184  * which can be see like all the possible links or logical connections.
185  * some of them are active (no track connected) and others are inactive
186  * (when tracks connect pads)
187  * This full ratsnest is not modified by track editing.
188  * It changes only when a netlist is read, or footprints are modified
189  */
191 
192  // Compute the pad connections due to the existing tracks (physical connections)
193  TestConnections();
194 
195  /* Compute the active ratsnest, i.e. the unconnected links
196  */
198 
199  // Redraw the active ratsnest ( if enabled )
200  if( GetBoard()->IsElementVisible( LAYER_RATSNEST ) && aDC )
201  DrawGeneralRatsnest( aDC, 0 );
202 
203  if( aDisplayStatus )
204  SetMsgPanel( m_Pcb );
205 }
206 
207 
208 /* Sort function used by QSORT
209  * Sort pads by net code
210  */
211 static bool sortByNetcode( const D_PAD* const & ref, const D_PAD* const & item )
212 {
213  return ref->GetNetCode() < item->GetNetCode();
214 }
215 
216 
232 {
233  D_PAD* pad;
234  int noconn;
235 
237 
238  m_Pcb->m_FullRatsnest.clear();
239 
240  if( m_Pcb->GetPadCount() == 0 )
241  return;
242 
243  // Created pad list and the net_codes if needed
244  if( (m_Pcb->m_Status_Pcb & NET_CODES_OK) == 0 )
246 
247  for( unsigned ii = 0; ii<m_Pcb->GetPadCount(); ++ii )
248  {
249  pad = m_Pcb->GetPad( ii );
250  pad->SetSubRatsnest( 0 );
251  }
252 
253  if( m_Pcb->GetNodesCount() == 0 )
254  return; // No useful connections.
255 
256  // Ratsnest computation
257  unsigned current_net_code = 1; // First net code is analyzed.
258  // (net_code = 0 -> no connect)
259  noconn = 0;
260  MIN_SPAN_TREE_PADS min_spanning_tree;
261 
262  for( ; current_net_code < m_Pcb->GetNetCount(); current_net_code++ )
263  {
264  NETINFO_ITEM* net = m_Pcb->FindNet( current_net_code );
265 
266  if( !net ) // Should not occur
267  {
268  UTF8 msg = StrPrintf( "%s: error, net %d not found", __func__, current_net_code );
269  wxMessageBox( msg ); // BTW, it does happen.
270  return;
271  }
272 
274 
275  min_spanning_tree.MSP_Init( &net->m_PadInNetList );
276  min_spanning_tree.BuildTree();
277  min_spanning_tree.AddTreeToRatsnest( &m_Pcb->m_FullRatsnest );
279  }
280 
281  m_Pcb->SetUnconnectedNetCount( noconn );
283 
284  // Update the ratsnest display option (visible/invisible) flag
285  for( unsigned ii = 0; ii < m_Pcb->GetRatsnestsCount(); ii++ )
286  {
287  if( !GetBoard()->IsElementVisible( LAYER_RATSNEST ) ) // Clear VISIBLE flag
288  m_Pcb->m_FullRatsnest[ii].m_Status &= ~CH_VISIBLE;
289  }
290 }
291 
292 
300 void PCB_BASE_FRAME::DrawGeneralRatsnest( wxDC* aDC, int aNetcode )
301 {
302  if( ( m_Pcb->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK ) == 0 )
303  return;
304 
306  return;
307 
308  if( aDC == NULL )
309  return;
310 
311  const int state = CH_VISIBLE | CH_ACTIF;
312 
313  for( unsigned ii = 0; ii < m_Pcb->GetRatsnestsCount(); ii++ )
314  {
315  RATSNEST_ITEM& item = m_Pcb->m_FullRatsnest[ii];
316 
317  if( ( item.m_Status & state ) != state )
318  continue;
319 
320  if( ( aNetcode <= 0 ) || ( aNetcode == item.GetNet() ) )
321  {
322  item.Draw( m_canvas, aDC, GR_XOR, wxPoint( 0, 0 ) );
323  }
324  }
325 }
326 
327 
340  std::vector<RATSNEST_ITEM>& aRatsnestBuffer )
341 {
342  int subratsnest_id, min_id;
343  RATSNEST_ITEM* link, * best_link;
344 
345  // Search a link from a block to an other block
346  best_link = NULL;
347 
348  for( unsigned ii = aNetinfo->m_RatsnestStartIdx; ii < aNetinfo->m_RatsnestEndIdx; ii++ )
349  {
350  link = &aRatsnestBuffer[ii];
351 
352  // If this link joints 2 pads inside the same block, do nothing
353  // (these pads are already connected)
354  if( link->m_PadStart->GetSubRatsnest() == link->m_PadEnd->GetSubRatsnest() )
355  continue;
356 
357  // This link joints 2 pads of different blocks: this is a candidate,
358  // but we want to select the shorter link, so use it only if it is shorter
359  // than the previous candidate:
360  if( best_link == NULL ) // no candidate
361  best_link = link;
362  else if( best_link->m_Length > link->m_Length ) // It is a better candidate.
363  best_link = link;
364  }
365 
366  if( best_link == NULL )
367  return 1;
368 
369  /* At this point we have found a link between 2 different blocks (subratsnest)
370  * we must set its status to ACTIVE and merge the 2 blocks
371  */
372  best_link->m_Status |= CH_ACTIF;
373  subratsnest_id = best_link->m_PadStart->GetSubRatsnest();
374  min_id = best_link->m_PadEnd->GetSubRatsnest();
375 
376  if( min_id > subratsnest_id )
377  std::swap( min_id, subratsnest_id );
378 
379  // Merge the 2 blocks in one sub ratsnest:
380  for( unsigned ii = 0; ii < aNetinfo->m_PadInNetList.size(); ii++ )
381  {
382  if( aNetinfo->m_PadInNetList[ii]->GetSubRatsnest() == subratsnest_id )
383  {
384  aNetinfo->m_PadInNetList[ii]->SetSubRatsnest( min_id );
385  }
386  }
387 
388  return subratsnest_id;
389 }
390 
391 
410 static void tst_links_between_pads( int & aCurrSubRatsnestId,
411  RATSNEST_ITEM* aFirstItem,
412  RATSNEST_ITEM* aLastItem )
413 {
414  for( RATSNEST_ITEM* item = aFirstItem; item < aLastItem; item++ )
415  {
416  D_PAD* pad_start = item->m_PadStart;
417  D_PAD* pad_end = item->m_PadEnd;
418 
419  /* Update the current SubRatsnest if the 2 pads are not connected :
420  * a new cluster is created and the link activated
421  */
422  if( (pad_start->GetSubRatsnest() == 0) && (pad_end->GetSubRatsnest() == 0) )
423  {
424  aCurrSubRatsnestId++;
425  pad_start->SetSubRatsnest( aCurrSubRatsnestId );
426  pad_end->SetSubRatsnest( aCurrSubRatsnestId );
427  item->m_Status |= CH_ACTIF;
428  }
429 
430  /* If a pad is already connected to a subratsnest: activate the link
431  * the pad other is merged in the existing subratsnest
432  */
433  else if( pad_start->GetSubRatsnest() == 0 )
434  {
435  pad_start->SetSubRatsnest( pad_end->GetSubRatsnest() );
436  item->m_Status |= CH_ACTIF;
437  }
438  else if( pad_end->GetSubRatsnest() == 0 )
439  {
440  pad_end->SetSubRatsnest( pad_start->GetSubRatsnest() );
441  item->m_Status |= CH_ACTIF;
442  }
443  }
444 }
445 
446 /* function TestForActiveLinksInRatsnest
447  * determine the active links inside the full ratsnest
448  *
449  * I used an algorithm inspired by the "Lee algorithm".
450  * The idea is all pads must be connected by a physical track or a logical track
451  * a physical track is the existing track on copper layers.
452  * a logical track is the link that must be activated (visible) if
453  * no track found between 2 pads.
454  * The algorithm explore the existing full ratnest
455  * This is a 2 steps algorithm (executed for each net).
456  * - First:
457  * Initialise for each pad the subratsnest id to its subnet value
458  * explore the full ratnest (relative to the net) and active a link each time at least one pad of
459  * the given link is not connected to an other pad by a track ( subratsnest = 0)
460  * If the 2 pads linked have both the subratsnest id = 0, a new subratsnest value is created
461  * - Second:
462  * explore the full ratnest (relative to the net) and find a link that links
463  * 2 pads having different subratsnest values
464  * Active the link and merge the 2 subratsnest value.
465  *
466  * This is usually fast because the ratsnest is not built here: it is just explored
467  * to see what link must be activated
468  */
470 {
471  RATSNEST_ITEM* rats;
472  D_PAD* pad;
473  NETINFO_ITEM* net;
474 
475  if( m_Pcb->GetPadCount() == 0 )
476  return;
477 
480 
481  for( int net_code = 1; net_code < (int) m_Pcb->GetNetCount(); net_code++ )
482  {
483  net = m_Pcb->FindNet( net_code );
484 
485  wxCHECK_RET( net != NULL,
486  wxString::Format( wxT( "Net code %d not found!" ), net_code ) );
487 
488  if( aNetCode && (net_code != aNetCode) )
489  continue;
490 
491  // Create subratsnests id from subnets created by existing tracks:
492  int subratsnest = 0;
493  for( unsigned ip = 0; ip < net->m_PadInNetList.size(); ip++ )
494  {
495  pad = net->m_PadInNetList[ip];
496  int subnet = pad->GetSubNet();
497  pad->SetSubRatsnest( subnet );
498  subratsnest = std::max( subratsnest, subnet );
499  }
500 
501  for( unsigned ii = net->m_RatsnestStartIdx; ii < net->m_RatsnestEndIdx; ii++ )
502  {
503  m_Pcb->m_FullRatsnest[ii].m_Status &= ~CH_ACTIF;
504  }
505 
506  // First pass - activate links for not connected pads
507  rats = &m_Pcb->m_FullRatsnest[0];
508  tst_links_between_pads( subratsnest,
509  rats + net->m_RatsnestStartIdx,
510  rats + net->m_RatsnestEndIdx );
511 
512  // Second pass activate links between blocks (Iteration)
513  while( subratsnest > 1 )
514  {
515  subratsnest = tst_links_between_blocks( net, m_Pcb->m_FullRatsnest );
516  }
517  }
518 
520 
521  unsigned cnt = 0;
522 
523  for( unsigned ii = 0; ii < m_Pcb->GetRatsnestsCount(); ii++ )
524  {
525  if( m_Pcb->m_FullRatsnest[ii].IsActive() )
526  cnt++;
527  }
528 
530 }
531 
532 
534 {
535  // for local ratsnest calculation when moving a footprint:
536  // list of pads to use for this local ratsnets:
537  // this is the list of connected pads of the current module,
538  // and all pads connected to these pads:
539  static std::vector <D_PAD*> localPadList;
540  static unsigned pads_module_count; // node count (node = pad with a net
541  // code) for the footprint being moved
542  static unsigned internalRatsCount; // number of internal links (links
543  // between pads of the module)
544  D_PAD* pad_ref;
545  D_PAD* pad_externe;
546  int current_net_code;
547  int distance;
548  wxPoint pad_pos; // True pad position according to the
549  // current footprint position
550 
551  if( (GetBoard()->m_Status_Pcb & LISTE_PAD_OK) == 0 )
552  {
553  GetBoard()->m_Status_Pcb = 0;
555  }
556 
557  /* Compute the "local" ratsnest if needed (when this footprint starts move)
558  * and the list of external pads to consider, i.e pads in others
559  * footprints which are "connected" to
560  * a pad in the current footprint
561  */
563  {
564  // Compute the "internal" ratsnest, i.e the links between the current
565  // footprint pads
566  localPadList.clear();
567  m_Pcb->m_LocalRatsnest.clear();
568 
569  // collect active pads of the module:
570  for( pad_ref = aModule->Pads(); pad_ref; pad_ref = pad_ref->Next() )
571  {
572  if( pad_ref->GetNetCode() == NETINFO_LIST::UNCONNECTED )
573  continue;
574 
575  if( !( pad_ref->GetLayerSet() & LSET::AllCuMask() ).any() )
576  // pad not a copper layer (happens when building complex shapes)
577  continue;
578 
579  localPadList.push_back( pad_ref );
580  pad_ref->SetSubRatsnest( 0 );
581  pad_ref->SetSubNet( 0 );
582  }
583 
584  pads_module_count = localPadList.size();
585 
586  if( pads_module_count == 0 )
587  return; // no connection!
588 
589  sort( localPadList.begin(), localPadList.end(), sortByNetcode );
590 
591  // Build the list of pads linked to the current footprint pads
592  current_net_code = 0;
593 
594  for( unsigned ii = 0; ii < pads_module_count; ii++ )
595  {
596  pad_ref = localPadList[ii];
597 
598  if( pad_ref->GetNetCode() == current_net_code )
599  continue;
600 
601  // A new net was found, load all pads of others modules members of this net:
602  NETINFO_ITEM* net = pad_ref->GetNet();
603 
604  if( net == NULL ) //Should not occur
605  {
606  wxMessageBox( wxT( "build_ratsnest_module() error: net not found" ) );
607  return;
608  }
609 
610  for( unsigned jj = 0; jj < net->m_PadInNetList.size(); jj++ )
611  {
612  pad_externe = net->m_PadInNetList[jj];
613 
614  if( pad_externe->GetParent() == aModule )
615  continue;
616 
617  pad_externe->SetSubRatsnest( 0 );
618  pad_externe->SetSubNet( 0 );
619 
620  localPadList.push_back( pad_externe );
621  }
622  }
623 
624  // Sort the pad list by net_code
625  sort( localPadList.begin() + pads_module_count, localPadList.end(),
626  sortByNetcode );
627 
628  /* Compute the internal rats nest:
629  * this is the same as general ratsnest, but considers only the current
630  * footprint pads it is therefore not time consuming, and it is made only
631  * once
632  */
633  current_net_code = localPadList[0]->GetNetCode();
634 
635  MIN_SPAN_TREE_PADS min_spanning_tree;
636  std::vector<D_PAD*> padsBuffer; // contains pads of only one net
637 
638  for( unsigned ii = 0; ii < pads_module_count; ii++ )
639  {
640  // Search the end of pad list relative to the current net
641  unsigned jj = ii + 1;
642 
643  for( ; jj <= pads_module_count; jj++ )
644  {
645  if( jj >= pads_module_count )
646  break;
647 
648  if( localPadList[jj]->GetNetCode() != current_net_code )
649  break;
650  }
651 
652  for( unsigned kk = ii; kk < jj; kk++ )
653  padsBuffer.push_back( localPadList[kk] );
654 
655  min_spanning_tree.MSP_Init( &padsBuffer );
656  min_spanning_tree.BuildTree();
657  min_spanning_tree.AddTreeToRatsnest( &m_Pcb->m_LocalRatsnest );
658  padsBuffer.clear();
659 
660  ii = jj;
661 
662  if( ii < localPadList.size() )
663  current_net_code = localPadList[ii]->GetNetCode();
664  }
665 
666  internalRatsCount = m_Pcb->m_LocalRatsnest.size();
667 
668  // set the flag LOCAL_RATSNEST_ITEM of the ratsnest status:
669  for( unsigned ii = 0; ii < m_Pcb->m_LocalRatsnest.size(); ii++ )
670  m_Pcb->m_LocalRatsnest[ii].m_Status = LOCAL_RATSNEST_ITEM;
671 
673  } // End of internal ratsnest build
674 
675  /* This section computes the "external" ratsnest: it is done when the
676  * footprint position changes
677  *
678  * This section search:
679  * for each current module pad the nearest neighbor external pad (of
680  * course for the same net code).
681  * For each current footprint cluster of pad (pads having the same net
682  * code),
683  * we search the smaller rats nest.
684  * so, for each net, only one rats nest item is created
685  */
686  RATSNEST_ITEM local_rats;
687 
688  local_rats.m_Length = INT_MAX;
689  local_rats.m_Status = 0;
690  bool addRats = false;
691 
692  // Erase external ratsnest items:
693  if( internalRatsCount < m_Pcb->m_LocalRatsnest.size() )
694  m_Pcb->m_LocalRatsnest.erase( m_Pcb->m_LocalRatsnest.begin() + internalRatsCount,
695  m_Pcb->m_LocalRatsnest.end() );
696 
697  current_net_code = localPadList[0]->GetNetCode();
698 
699  for( unsigned ii = 0; ii < pads_module_count; ii++ )
700  {
701  pad_ref = localPadList[ii];
702 
703  if( pad_ref->GetNetCode() != current_net_code )
704  {
705  // if needed, creates a new ratsnest for the old net
706  if( addRats )
707  {
708  m_Pcb->m_LocalRatsnest.push_back( local_rats );
709  }
710 
711  addRats = false;
712  current_net_code = pad_ref->GetNetCode();
713  local_rats.m_Length = INT_MAX;
714  }
715 
716  pad_pos = pad_ref->GetPosition() - g_Offset_Module;
717 
718  // Search the nearest external pad of this current pad
719  for( unsigned jj = pads_module_count; jj < localPadList.size(); jj++ )
720  {
721  pad_externe = localPadList[jj];
722 
723  // we search pads having the same net code
724  if( pad_externe->GetNetCode() < pad_ref->GetNetCode() )
725  continue;
726 
727  if( pad_externe->GetNetCode() > pad_ref->GetNetCode() ) // pads are sorted by net code
728  break;
729 
730  distance = abs( pad_externe->GetPosition().x - pad_pos.x ) +
731  abs( pad_externe->GetPosition().y - pad_pos.y );
732 
733  if( distance < local_rats.m_Length )
734  {
735  local_rats.m_PadStart = pad_ref;
736  local_rats.m_PadEnd = pad_externe;
737  local_rats.SetNet( pad_ref->GetNetCode() );
738  local_rats.m_Length = distance;
739  local_rats.m_Status = 0;
740 
741  addRats = true;
742  }
743  }
744  }
745 
746  if( addRats ) // Ensure the last created rats nest item is stored in buffer
747  m_Pcb->m_LocalRatsnest.push_back( local_rats );
748 }
749 
750 
752 {
753  if( DC == NULL )
754  return;
755 
756  if( ( m_Pcb->m_Status_Pcb & RATSNEST_ITEM_LOCAL_OK ) == 0 )
757  return;
758 
760 
761  for( unsigned ii = 0; ii < m_Pcb->m_LocalRatsnest.size(); ii++ )
762  {
763  RATSNEST_ITEM* rats = &m_Pcb->m_LocalRatsnest[ii];
764 
765  if( rats->m_Status & LOCAL_RATSNEST_ITEM )
766  {
768  rats->Draw( m_canvas, DC, GR_XOR, g_Offset_Module );
769  }
770  else
771  {
773 
774  wxPoint tmp = rats->m_PadStart->GetPosition();
775 
776  rats->m_PadStart->SetPosition( tmp - g_Offset_Module );
777  rats->Draw( m_canvas, DC, GR_XOR, wxPoint( 0, 0 ) );
778 
779  rats->m_PadStart->SetPosition( tmp );
780  }
781  }
782 
784 }
785 
786 
787 /*
788  * PCB_BASE_FRAME::BuildAirWiresTargetsList and
789  * PCB_BASE_FRAME::TraceAirWiresToTargets
790  * are 2 function to show the near connecting points when
791  * a new track is created, by displaying g_MaxLinksShowed airwires
792  * between the on grid mouse cursor and these connecting points
793  * during the creation of a track
794  */
795 
796 /* Buffer to store pads coordinates when creating a track.
797  * these pads are members of the net
798  * and when the mouse is moved, the g_MaxLinksShowed links to neighbors are
799  * drawn
800  */
801 static std::vector <wxPoint> s_TargetsLocations;
802 static wxPoint s_CursorPos; // Coordinate of the moving point (mouse cursor and
803  // end of current track segment)
804 
805 /* Used by BuildAirWiresTargetsList(): sort function by link length
806  * (rectilinear distance between s_CursorPos and item pos)
807  */
808 static bool sort_by_distance( const wxPoint& ref, const wxPoint& compare )
809 {
810  wxPoint deltaref = ref - s_CursorPos; // relative coordinate of ref
811  wxPoint deltacmp = compare - s_CursorPos; // relative coordinate of compare
812 
813  // rectilinear distance between ref and s_CursorPos:
814  int lengthref = abs( deltaref.x ) + abs( deltaref.y );
815 
816  // rectilinear distance between compare and s_CursorPos:
817  int lengthcmp = abs( deltacmp.x ) + abs( deltacmp.y );
818 
819  return lengthref < lengthcmp;
820 }
821 
822 static bool sort_by_point( const wxPoint& ref, const wxPoint& compare )
823 {
824  if( ref.x == compare.x )
825  return ref.y < compare.y;
826 
827  return ref.x < compare.x;
828 }
829 
830 /* Function BuildAirWiresTargetsList
831  * Build a list of candidates that can be a coonection point
832  * when a track is started.
833  * This functions prepares data to show airwires to nearest connecting points (pads)
834  * from the current new track to candidates during track creation
835  */
837  const wxPoint& aPosition, bool aInit )
838 {
839  if( ( ( m_Pcb->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK ) == 0 )
840  || ( ( m_Pcb->m_Status_Pcb & LISTE_PAD_OK ) == 0 )
841  || ( ( m_Pcb->m_Status_Pcb & NET_CODES_OK ) == 0 ) )
842  {
843  s_TargetsLocations.clear();
844  return;
845  }
846 
847  s_CursorPos = aPosition; // needed for sort_by_distance
848 
849  if( aInit )
850  {
851  s_TargetsLocations.clear();
852 
853  if( aItemRef == NULL )
854  return;
855 
856  int net_code = aItemRef->GetNetCode();
857  int subnet = aItemRef->GetSubNet();
858 
859  if( net_code <= 0 )
860  return;
861 
862  NETINFO_ITEM* net = m_Pcb->FindNet( net_code );
863 
864  if( net == NULL ) // Should not occur
865  {
866  wxMessageBox( wxT( "BuildAirWiresTargetsList() error: net not found" ) );
867  return;
868  }
869 
870  // Create a list of pads candidates ( pads not already connected to the
871  // current track ):
872  for( unsigned ii = 0; ii < net->m_PadInNetList.size(); ii++ )
873  {
874  D_PAD* pad = net->m_PadInNetList[ii];
875 
876  if( pad == aItemRef )
877  continue;
878 
879  if( !pad->GetSubNet() || (pad->GetSubNet() != subnet) )
880  s_TargetsLocations.push_back( pad->GetPosition() );
881  }
882 
883  // Create a list of tracks ends candidates, not already connected to the
884  // current track:
885  for( TRACK* track = m_Pcb->m_Track; track; track = track->Next() )
886  {
887  if( track->GetNetCode() < net_code )
888  continue;
889  if( track->GetNetCode() > net_code )
890  break;
891 
892  if( !track->GetSubNet() || (track->GetSubNet() != subnet) )
893  {
894  if( aPosition != track->GetStart() )
895  s_TargetsLocations.push_back( track->GetStart() );
896  if( aPosition != track->GetEnd() && track->GetStart() != track->GetEnd() )
897  s_TargetsLocations.push_back( track->GetEnd() );
898  }
899  }
900 
901  // Remove duplicate targets, using the C++ unique algorithm
902  sort( s_TargetsLocations.begin(), s_TargetsLocations.end(), sort_by_point );
903  std::vector< wxPoint >::iterator it = unique( s_TargetsLocations.begin(), s_TargetsLocations.end() );
904 
905  // Using the C++ unique algorithm only moves the duplicate entries to the end of
906  // of the array. This removes the duplicate entries from the array.
907  s_TargetsLocations.resize( it - s_TargetsLocations.begin() );
908  } // end if Init
909 
910  // in all cases, sort by distances:
912 }
913 
914 
916 {
917  if( aDC == NULL )
918  return;
919 
920  if( s_TargetsLocations.size() == 0 )
921  return;
922 
923  GRSetDrawMode( aDC, GR_XOR );
925 
926  for( int ii = 0; ii < (int) s_TargetsLocations.size(); ii++ )
927  {
928  if( ii >= displ_opts->m_MaxLinksShowed )
929  break;
930 
932  }
933 }
std::vector< RATSNEST_ITEM > m_LocalRatsnest
Ratsnest list relative to a given footprint (used while moving a footprint).
Definition: class_board.h:251
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Function AllCuMask returns a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:639
Class UTF8 is an 8 bit std::string that is assuredly encoded in UTF8, and supplies special conversion...
Definition: utf8.h:53
void TraceAirWiresToTargets(wxDC *aDC)
Function TraceAirWiresToTargets This functions shows airwires to nearest connecting points (pads) fro...
Definition: ratsnest.cpp:915
static wxPoint s_CursorPos
Definition: ratsnest.cpp:802
void BuildListOfNets()
Definition: class_board.h:764
wxPoint g_Offset_Module
Definition: pcbnew.cpp:83
bool IsElementVisible(GAL_LAYER_ID LAYER_aPCB) const
Function IsElementVisible tests whether a given element category is visible.
int GetDist(int aIdx)
void SetItemColor(int aItemIdx, COLOR4D aColor)
Function SetItemColor sets the color for an item which is one of the item indices given in enum PCB_L...
void TestForActiveLinksInRatsnest(int aNetCode)
Function TestForActiveLinksInRatsnest Explores the full rats nest list (which must exist) to determin...
Definition: ratsnest.cpp:469
void GRSetDrawMode(wxDC *DC, GR_DRAWMODE draw_mode)
Definition: gr_basic.cpp:290
void TraceModuleRatsNest(wxDC *aDC)
Function TraceModuleRatsNest display the rats nest of a moving footprint, computed by build_ratsnest_...
Definition: ratsnest.cpp:751
void MSP_Init(int aNodesCount)
void SetUnconnectedNetCount(unsigned aCount)
Function SetUnconnectedNetCount sets the number of unconnected nets in the current rats nest to aCoun...
Definition: class_board.h:735
void GRLine(EDA_RECT *ClipBox, wxDC *DC, int x1, int y1, int x2, int y2, int width, COLOR4D Color)
Definition: gr_basic.cpp:352
Class BOARD to handle a board.
MODULE * GetParent() const
Definition: class_pad.h:108
BOARD * GetBoard() const
void SetPosition(const wxPoint &aPos) override
Definition: class_pad.h:169
void SetSubRatsnest(int aSubRatsnest)
Definition: class_pad.h:475
The class MIN_SPAN_TREE calculates the rectilinear minimum spanning tree of a set of points (pads usu...
D_PADS m_PadInNetList
List of pads connected to this net.
#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...
void SetNet(int aNetCode)
Definition: class_netinfo.h:90
Functions relatives to tracks, vias and segments used to fill zones.
void * GetDisplayOptions() override
Function GetDisplayOptions returns the display options current in use Display options are relative to...
class MIN_SPAN_TREE_PADS (derived from MIN_SPAN_TREE) specializes the base class to calculate a minim...
Definition: ratsnest.cpp:51
This file contains miscellaneous commonly used macros and functions.
int StrPrintf(std::string *result, const char *format,...)
Function StrPrintf is like sprintf() but the output is appended to a std::string instead of to a char...
Definition: richio.cpp:75
COLOR4D GetItemColor(int aItemIdx) const
Function GetItemColor.
#define CH_ACTIF
Definition: class_netinfo.h:60
std::vector< RATSNEST_ITEM > m_FullRatsnest
Ratsnest list for the BOARD.
Definition: class_board.h:248
D_PAD * m_PadEnd
Definition: class_netinfo.h:76
static bool sortByNetcode(const D_PAD *const &ref, const D_PAD *const &item)
Definition: ratsnest.cpp:211
void TestConnections()
Function TestConnections tests the connections relative to all nets.
Definition: connect.cpp:733
static bool sort_by_distance(const wxPoint &ref, const wxPoint &compare)
Definition: ratsnest.cpp:808
unsigned m_RatsnestStartIdx
unsigned GetRatsnestsCount() const
Function GetNumRatsnests.
Definition: class_board.h:704
#define LOCAL_RATSNEST_ITEM
Definition: class_netinfo.h:61
Classes used in Pcbnew, CvPcb and GerbView.
void Draw(EDA_DRAW_PANEL *panel, wxDC *DC, GR_DRAWMODE aDrawMode, const wxPoint &offset)
Function Draw.
void SetMsgPanel(const std::vector< MSG_PANEL_ITEM > &aList)
Function SetMsgPanel clears the message panel and populates it with the contents of aList...
Definition: draw_frame.cpp:754
int GetSubRatsnest() const
Function GetSubRatsnest.
Definition: class_pad.h:474
void build_ratsnest_module(MODULE *aModule)
Function build_ratsnest_module Build a ratsnest relative to one footprint.
Definition: ratsnest.cpp:533
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
Definition: colors.h:59
void AddTreeToRatsnest(std::vector< RATSNEST_ITEM > *aRatsnestList)
Function AddTreeToRatsnest Adds the current minimum spanning tree as ratsnest items to the main ratsn...
Definition: ratsnest.cpp:95
static int tst_links_between_blocks(NETINFO_ITEM *aNetinfo, std::vector< RATSNEST_ITEM > &aRatsnestBuffer)
Function used by TestForActiveLinksInRatsnest Function testing the ratsnest between 2 blocks ( of the...
Definition: ratsnest.cpp:339
D_PAD * Next() const
Definition: class_pad.h:106
void BuildAirWiresTargetsList(BOARD_CONNECTED_ITEM *aItemRef, const wxPoint &aPosition, bool aInit)
Function BuildAirWiresTargetsList Build a list of candidates that can be a coonection point when a tr...
Definition: ratsnest.cpp:836
#define CH_VISIBLE
Definition: class_netinfo.h:57
EDA_RECT * GetClipBox()
Definition: colors.h:60
int GetNet() const
Function GetNet.
Definition: class_netinfo.h:85
D_PAD * GetPad(unsigned aIndex) const
Function GetPad.
Definition: class_board.h:750
COLORS_DESIGN_SETTINGS g_ColorsSettings
Definition: pcbnew.cpp:68
unsigned GetPadCount() const
Function GetPadCount.
Definition: class_board.h:741
void SetSubNet(int aSubNetCode)
int GetWhoTo(int aIdx)
void Compile_Ratsnest(wxDC *aDC, bool aDisplayStatus)
Function Compile_Ratsnest Create the entire board ratsnest.
Definition: ratsnest.cpp:165
Class DISPLAY_OPTIONS handles display options like enable/disable some optional drawings.
Definition: pcbstruct.h:62
D_PAD * m_PadStart
Definition: class_netinfo.h:75
int GetNetCode() const
Function GetNetCode.
EDA_DRAW_PANEL * m_canvas
The area to draw on.
Definition: draw_frame.h:92
void AppendMsgPanel(const wxString &textUpper, const wxString &textLower, COLOR4D color, int pad=6)
Append a message to the message panel.
Definition: draw_frame.cpp:734
static std::vector< wxPoint > s_TargetsLocations
Definition: ratsnest.cpp:801
Class NETINFO_ITEM handles the data for a net.
TRACK * Next() const
Definition: class_track.h:98
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, CPTREE &aTree)
Function Format outputs a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:205
#define max(a, b)
Definition: auxiliary.h:86
unsigned GetNodesCount() const
Function GetNodesCount.
int GetSubNet() const
Function GetSubNet.
NETINFO_ITEM * FindNet(int aNetcode) const
Function FindNet searches for a net with the given netcode.
The common library.
void Build_Board_Ratsnest()
Function Build_Board_Ratsnest.
Definition: ratsnest.cpp:231
static void tst_links_between_pads(int &aCurrSubRatsnestId, RATSNEST_ITEM *aFirstItem, RATSNEST_ITEM *aLastItem)
Function used by TestForActiveLinksInRatsnest_general The general ratsnest list must exists because t...
Definition: ratsnest.cpp:410
int m_MaxLinksShowed
Definition: pcbstruct.h:86
DLIST< D_PAD > & Pads()
Definition: class_module.h:134
Class RATSNEST_ITEM describes a ratsnest line: a straight line connecting 2 pads. ...
Definition: class_netinfo.h:68
DLIST< TRACK > m_Track
Definition: class_board.h:244
Module description (excepted pads)
static bool sort_by_point(const wxPoint &ref, const wxPoint &compare)
Definition: ratsnest.cpp:822
void MSP_Init(std::vector< D_PAD * > *aPadsList)
Definition: ratsnest.cpp:69
Definition: colors.h:68
static const int UNCONNECTED
Constant that holds the "unconnected net" number (typically 0) all items "connected" to this net are ...
void ClearMsgPanel(void)
Clear all messages from the message panel.
Definition: draw_frame.cpp:745
std::vector< D_PAD * > * m_PadsList
Definition: ratsnest.cpp:55
NETINFO_ITEM * GetNet() const
Function GetNet Returns NET_INFO object for a given item.
unsigned m_RatsnestEndIdx
unsigned GetNetCount() const
Function GetNetCount.
Definition: class_board.h:814
int m_Status_Pcb
Flags used in ratsnest calculation and update.
Definition: class_board.h:240
Class COLOR4D is the color representation with 4 components: red, green, blue, alpha.
Definition: color4d.h:39
int GetWeight(int aItem1, int aItem2) override
Function GetWeight calculates the weight between 2 items NOTE: The weight between a node and itself s...
Definition: ratsnest.cpp:130