KiCad PCB EDA Suite
zones_polygons_test_connections.cpp
Go to the documentation of this file.
1 
5 /*
6  * This program source code file is part of KiCad, a free EDA CAD application.
7  *
8  * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
9  * Copyright (C) 1992-2012 KiCad Developers, see AUTHORS.txt for contributors.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, you may find one here:
23  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
24  * or you may search the http://www.gnu.org website for the version 2 license,
25  * or you may write to the Free Software Foundation, Inc.,
26  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
27  */
28 
29 #include <algorithm> // sort
30 
31 #include <fctsys.h>
32 #include <common.h>
33 #include <macros.h>
34 
35 #include <class_board.h>
36 #include <class_module.h>
37 #include <class_track.h>
38 #include <class_zone.h>
39 
40 #include <pcbnew.h>
41 #include <zones.h>
43 
44 static bool CmpZoneSubnetValue( const BOARD_CONNECTED_ITEM* a, const BOARD_CONNECTED_ITEM* b );
45 
46 void Merge_SubNets_Connected_By_CopperAreas( BOARD* aPcb, int aNetcode );
47 
48 // This helper function sort a list of zones by netcode,
49 // and for a given netcode by zone size
50 // zone size = size of the m_FilledPolysList buffer
51 bool sort_areas( const ZONE_CONTAINER* ref, const ZONE_CONTAINER* tst )
52 {
53  if( ref->GetNetCode() == tst->GetNetCode() )
54  return ref->GetFilledPolysList().TotalVertices() <
56  else
57  return ref->GetNetCode() < tst->GetNetCode();
58 }
59 
66 {
67  // list of pads and tracks candidates on this layer and on this net.
68  // It is static to avoid multiple memory realloc.
69  static std::vector <BOARD_CONNECTED_ITEM*> candidates;
70 
71  // clear .m_ZoneSubnet parameter for pads
72  for( MODULE* module = m_Modules; module; module = module->Next() )
73  {
74  for( D_PAD* pad = module->Pads(); pad; pad = pad->Next() )
75  if( aNetcode < 0 || aNetcode == pad->GetNetCode() )
76  pad->SetZoneSubNet( 0 );
77  }
78 
79  // clear .m_ZoneSubnet parameter for tracks and vias
80  for( TRACK* track = m_Track; track; track = track->Next() )
81  {
82  if( aNetcode < 0 || aNetcode == track->GetNetCode() )
83  track->SetZoneSubNet( 0 );
84  }
85 
86  // examine all zones, net by net:
87  int subnet = 0;
88 
89  // Build zones candidates list
90  std::vector<ZONE_CONTAINER*> zones_candidates;
91 
92  zones_candidates.reserve( GetAreaCount() );
93 
94  for( int index = 0; index < GetAreaCount(); index++ )
95  {
96  ZONE_CONTAINER* zone = GetArea( index );
97 
98  if( !zone->IsOnCopperLayer() )
99  continue;
100 
101  if( aNetcode >= 0 && aNetcode != zone->GetNetCode() )
102  continue;
103 
104  if( zone->GetFilledPolysList().IsEmpty() )
105  continue;
106 
107  zones_candidates.push_back( zone );
108  }
109 
110  // sort them by netcode then vertices count.
111  // For a given net, examine the smaller zones first slightly speed up calculation
112  // (25% faster)
113  // this is only noticeable with very large boards and depends on board zones topology
114  // This is due to the fact some items are connected by small zones ares,
115  // before examining large zones areas and these items are not tested after a connection is found
116  sort( zones_candidates.begin(), zones_candidates.end(), sort_areas );
117 
118  int oldnetcode = -1;
119  for( unsigned idx = 0; idx < zones_candidates.size(); idx++ )
120  {
121  ZONE_CONTAINER* zone = zones_candidates[idx];
122 
123  int netcode = zone->GetNetCode();
124 
125  // Build a list of candidates connected to the net:
126  // At this point, layers are not considered, because areas on different layers can
127  // be connected by a via or a pad.
128  // (because zones are sorted by netcode, there is made only once per net)
129  NETINFO_ITEM* net = FindNet( netcode );
130 
131  wxASSERT( net );
132  if( net == NULL )
133  continue;
134 
135  if( oldnetcode != netcode )
136  {
137  oldnetcode = netcode;
138  candidates.clear();
139 
140  // Build the list of pads candidates connected to the net:
141  candidates.reserve( net->m_PadInNetList.size() );
142 
143  for( unsigned ii = 0; ii < net->m_PadInNetList.size(); ii++ )
144  candidates.push_back( net->m_PadInNetList[ii] );
145 
146  // If we have any tracks...
147  if( m_Track.GetCount() > 0 )
148  {
149  // Build the list of track candidates connected to the net:
150  TRACK* track = m_Track.GetFirst()->GetStartNetCode( netcode );
151 
152  for( ; track; track = track->Next() )
153  {
154  if( track->GetNetCode() != netcode )
155  break;
156 
157  candidates.push_back( track );
158  }
159  }
160  }
161 
162  // test if a candidate is inside a filled area of this zone
163  const SHAPE_POLY_SET& polysList = zone->GetFilledPolysList();
164 
165  for( int outline = 0; outline < polysList.OutlineCount(); outline++ )
166  {
167  subnet++;
168 
169  for( unsigned ic = 0; ic < candidates.size(); ic++ )
170  {
171  // test if this area is connected to a board item:
172  BOARD_CONNECTED_ITEM* item = candidates[ic];
173 
174  if( item->GetZoneSubNet() == subnet ) // Already merged
175  continue;
176 
177  if( !item->IsOnLayer( zone->GetLayer() ) )
178  continue;
179 
180  wxPoint pos1, pos2;
181 
182  if( item->Type() == PCB_PAD_T )
183  {
184  // For pads we use the shape position instead of
185  // the pad position, because the zones are connected
186  // to the center of the shape, not the pad position
187  // (this is important for pads with thermal relief)
188  pos1 = pos2 = ( (D_PAD*) item )->ShapePos();
189  }
190  else if( item->Type() == PCB_VIA_T )
191  {
192  const VIA *via = static_cast<const VIA*>( item );
193  pos1 = via->GetStart();
194  pos2 = pos1;
195  }
196  else if( item->Type() == PCB_TRACE_T )
197  {
198  const TRACK *trk = static_cast<const TRACK*>( item );
199  pos1 = trk->GetStart();
200  pos2 = trk->GetEnd();
201  }
202  else
203  {
204  continue;
205  }
206 
207  bool connected = false;
208 
209  if( polysList.Contains( VECTOR2I( pos1.x, pos1.y ), outline ) )
210  connected = true;
211 
212  if( !connected && ( pos1 != pos2 ) )
213  {
214  if( polysList.Contains( VECTOR2I( pos2.x, pos2.y ), outline ) )
215  connected = true;
216  }
217 
218  if( connected )
219  {
220  // Set ZoneSubnet to the current subnet value.
221  // If the previous subnet is not 0, merge all items with old subnet
222  // to the new one
223  int old_subnet = item->GetZoneSubNet();
224  item->SetZoneSubNet( subnet );
225 
226  // Merge previous subnet with the current
227  if( (old_subnet > 0) && (old_subnet != subnet) )
228  {
229  for( unsigned jj = 0; jj < candidates.size(); jj++ )
230  {
231  BOARD_CONNECTED_ITEM* item_to_merge = candidates[jj];
232 
233  if( old_subnet == item_to_merge->GetZoneSubNet() )
234  {
235  item_to_merge->SetZoneSubNet( subnet );
236  }
237  }
238  } // End if ( old_subnet > 0 )
239  } // End if( connected )
240  }
241  }
242  } // End read all zones candidates
243 }
244 
245 
253 {
254  for( int index = 0; index < aPcb->GetAreaCount(); index++ )
255  {
256  ZONE_CONTAINER* zone = aPcb->GetArea( index );
257 
258  if ( ! zone->IsOnCopperLayer() )
259  continue;
260 
261  if ( zone->GetNetCode() <= 0 )
262  continue;
263 
265  }
266 }
267 
268 
282 {
283  // Ensure a zone with the given netcode exists: examine all zones:
284  bool found = false;
285 
286  for( int index = 0; index < aPcb->GetAreaCount(); index++ )
287  {
288  ZONE_CONTAINER* zone = aPcb->GetArea( index );
289 
290  if( aNetcode == zone->GetNetCode() )
291  {
292  found = true;
293  break;
294  }
295  }
296 
297  if( !found ) // No zone with this netcode, therefore no connection by zone
298  return;
299 
300  // list of pads and tracks candidates to test:
301  // It is static to avoid multiple memory realloc.
302  static std::vector <BOARD_CONNECTED_ITEM*> Candidates;
303  Candidates.clear();
304 
305  // Build the list of pads candidates connected to the net:
306  NETINFO_ITEM* net = aPcb->FindNet( aNetcode );
307  wxASSERT( net );
308  Candidates.reserve( net->m_PadInNetList.size() );
309  for( unsigned ii = 0; ii < net->m_PadInNetList.size(); ii++ )
310  Candidates.push_back( net->m_PadInNetList[ii] );
311 
312  // Build the list of track candidates connected to the net:
313  TRACK* track;
314 
315  if( aPcb->m_Track.GetCount() > 0 )
316  {
317  track = aPcb->m_Track.GetFirst()->GetStartNetCode( aNetcode );
318 
319  for( ; track; track = track->Next() )
320  {
321  if( track->GetNetCode() != aNetcode )
322  break;
323 
324  Candidates.push_back( track );
325  }
326  }
327 
328  if( Candidates.size() == 0 )
329  return;
330 
331  int next_subnet_free_number = 0;
332  for( unsigned ii = 0; ii < Candidates.size(); ii++ )
333  {
334  int subnet = Candidates[ii]->GetSubNet();
335  next_subnet_free_number = std::max( next_subnet_free_number, subnet );
336  }
337 
338  next_subnet_free_number++; // This is a subnet we can use with not connected items
339  // by tracks, but connected by zone.
340 
341  // Sort by zone_subnet:
342  sort( Candidates.begin(), Candidates.end(), CmpZoneSubnetValue );
343 
344  // Some items can be not connected, but they can be connected to a filled area:
345  // give them a subnet common to these items connected only by the area,
346  // and not already used.
347  // a value like next_subnet_free_number+zone_subnet is right
348  for( unsigned jj = 0; jj < Candidates.size(); jj++ )
349  {
350  BOARD_CONNECTED_ITEM* item = Candidates[jj];
351  if ( item->GetSubNet() == 0 && (item->GetZoneSubNet() > 0) )
352  {
353  item->SetSubNet( next_subnet_free_number + item->GetZoneSubNet() );
354  }
355  }
356 
357  // Now, for each zone subnet, we search for 2 items with different subnets.
358  // if found, the 2 subnet are merged in the whole candidate list.
359  int old_subnet = 0;
360  int old_zone_subnet = 0;
361  for( unsigned ii = 0; ii < Candidates.size(); ii++ )
362  {
363  BOARD_CONNECTED_ITEM* item = Candidates[ii];
364  int zone_subnet = item->GetZoneSubNet();
365 
366  if( zone_subnet == 0 ) // Not connected by a filled area, skip it
367  continue;
368 
369  int subnet = item->GetSubNet();
370 
371  if( zone_subnet != old_zone_subnet ) // a new zone subnet is found
372  {
373  old_subnet = subnet;
374  old_zone_subnet = zone_subnet;
375  continue;
376  }
377 
378  // 2 successive items already from the same cluster: nothing to do
379  if( subnet == old_subnet )
380  continue;
381 
382  // Here we have 2 items connected by the same area have 2 differents subnets: merge subnets
383  if( (subnet > old_subnet) || ( subnet <= 0) )
384  std::swap( subnet, old_subnet );
385 
386  for( unsigned jj = 0; jj < Candidates.size(); jj++ )
387  {
388  BOARD_CONNECTED_ITEM * item_to_merge = Candidates[jj];
389 
390  if( item_to_merge->GetSubNet() == old_subnet )
391  item_to_merge->SetSubNet( subnet );
392  }
393 
394  old_subnet = subnet;
395  }
396 }
397 
398 
399 /* Compare function used for sorting candidates by increasing zone subnet
400  */
402 {
403  int asubnet, bsubnet;
404 
405  asubnet = a->GetZoneSubNet();
406  bsubnet = b->GetZoneSubNet();
407 
408  return asubnet < bsubnet;
409 }
KICAD_T Type() const
Function Type()
Definition: base_struct.h:198
Class ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:78
Class BOARD to handle a board.
MODULE * Next() const
Definition: class_module.h:99
int TotalVertices() const
Returns total number of vertices stored in the set.
Classes to handle copper zones.
class D_PAD, a pad in a footprint
Definition: typeinfo.h:102
int OutlineCount() const
Returns the number of outlines in the set
LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
D_PADS m_PadInNetList
List of pads connected to this net.
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
const wxPoint & GetEnd() const
Definition: class_track.h:117
Functions relatives to tracks, vias and segments used to fill zones.
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:107
static bool CmpZoneSubnetValue(const BOARD_CONNECTED_ITEM *a, const BOARD_CONNECTED_ITEM *b)
This file contains miscellaneous commonly used macros and functions.
virtual bool IsOnLayer(LAYER_ID aLayer) const
Function IsOnLayer tests to see if this object is on the given layer.
Class SHAPE_POLY_SET.
void Merge_SubNets_Connected_By_CopperAreas(BOARD *aPcb, int aNetcode)
Function Merge_SubNets_Connected_By_CopperAreas(BOARD* aPcb, int aNetcode) Used after connections by ...
const wxPoint & GetStart() const
Definition: class_track.h:120
int GetZoneSubNet() const
Function GetZoneSubNet.
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
D_PAD * Next() const
Definition: class_pad.h:106
bool sort_areas(const ZONE_CONTAINER *ref, const ZONE_CONTAINER *tst)
int GetAreaCount() const
Function GetAreaCount.
Definition: class_board.h:1051
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...
const SHAPE_POLY_SET & GetFilledPolysList() const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: class_zone.h:587
void SetSubNet(int aSubNetCode)
int GetNetCode() const
Function GetNetCode.
Class NETINFO_ITEM handles the data for a net.
bool IsOnCopperLayer() const
Function IsOnCopperLayer.
Definition: class_zone.h:179
TRACK * Next() const
Definition: class_track.h:97
ZONE_CONTAINER * GetArea(int index) const
Function GetArea returns the Area (Zone Container) at a given index.
Definition: class_board.h:1022
void SetZoneSubNet(int aSubNetCode)
TRACK * GetStartNetCode(int NetCode)
#define max(a, b)
Definition: auxiliary.h:86
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:166
DLIST< MODULE > m_Modules
Definition: class_board.h:243
int GetSubNet() const
Function GetSubNet.
NETINFO_ITEM * FindNet(int aNetcode) const
Function FindNet searches for a net with the given netcode.
The common library.
unsigned GetCount() const
Function GetCount returns the number of elements in the list.
Definition: dlist.h:126
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
Module description (excepted pads)
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1) const
Returns true if a given subpolygon contains the point aP.