KiCad PCB EDA Suite
connectivity_items.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) 2016-2018 CERN
5  * Copyright (C) 2019 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, you may find one here:
21  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22  * or you may search the http://www.gnu.org website for the version 2 license,
23  * or you may write to the Free Software Foundation, Inc.,
24  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25  */
26 
28 
30 {
31  if( !m_valid )
32  return 0;
33 
34  switch( m_parent->Type() )
35  {
36  case PCB_PAD_T:
37  return 5; // center, north, south, east and west
38  case PCB_TRACE_T:
39  case PCB_ARC_T:
40  return 2; // start and end
41  default:
42  return 1;
43  }
44 }
45 
46 
47 const VECTOR2I CN_ITEM::GetAnchor( int n ) const
48 {
49  VECTOR2I pt0;
50 
51  if( !m_valid )
52  return pt0;
53 
54  switch( m_parent->Type() )
55  {
56  case PCB_PAD_T:
57  {
58  D_PAD* pad = (D_PAD*) m_parent;
59 
60  if( n == 0 )
61  return VECTOR2I( pad->GetPosition() );
62 
63  // ShapePos() is the geometric center (not anchor) for the pad
64  pt0 = pad->ShapePos();
65  VECTOR2I pt1 = pt0;
66 
67  switch( pad->GetShape() )
68  {
70  // Because the trap delta is applied as +1/2 at one end and -1/2 at the other,
71  // the midpoint is actually unchanged. Therefore all the cardinal points are
72  // the same as for a rectangle.
74 
75  case PAD_SHAPE_RECT:
76  case PAD_SHAPE_CIRCLE:
77  case PAD_SHAPE_OVAL:
80  switch( n )
81  {
82  case 1: pt1.y -= pad->GetSize().y / 2; break; // North
83  case 2: pt1.y += pad->GetSize().y / 2; break; // South
84  case 3: pt1.x -= pad->GetSize().x / 2; break; // East
85  case 4: pt1.x += pad->GetSize().x / 2; break; // West
86  default: break; // Wicked witch
87  }
88 
89  if( pad->GetOrientation() )
90  RotatePoint( pt1, pad->ShapePos(), pad->GetOrientation() );
91 
92  // Thermal spokes on circular pads form an 'X' instead of a '+'
93  if( pad->GetShape() == PAD_SHAPE_CIRCLE )
94  RotatePoint( pt1, pad->ShapePos(), 450 );
95 
96  return pt1;
97 
98  case PAD_SHAPE_CUSTOM:
99  {
100  switch( n )
101  {
102  case 1: pt1.y = INT_MIN / 2; break; // North
103  case 2: pt1.y = INT_MAX / 2; break; // South
104  case 3: pt1.x = INT_MIN / 2; break; // East
105  case 4: pt1.x = INT_MAX / 2; break; // West
106  default: break; // Wicked witch
107  }
108 
109  if( pad->GetOrientation() )
110  RotatePoint( pt1, pad->ShapePos(), pad->GetOrientation() );
111 
112  const std::shared_ptr<SHAPE_POLY_SET>& padPolySet = pad->GetEffectivePolygon();
113  const SHAPE_LINE_CHAIN& padOutline = padPolySet->COutline( 0 );
114  SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
115 
116  padOutline.Intersect( SEG( pt0, pt1 ), intersections );
117 
118  if( intersections.empty() )
119  {
120  // There should always be at least some copper outside the hole and/or
121  // shapePos center
122  assert( false );
123  return pt0;
124  }
125 
126  return intersections[ intersections.size() - 1 ].p;
127  }
128  }
129 
130  break;
131  }
132  case PCB_TRACE_T:
133  case PCB_ARC_T:
134  if( n == 0 )
135  return static_cast<const TRACK*>( m_parent )->GetStart();
136  else
137  return static_cast<const TRACK*>( m_parent )->GetEnd();
138 
139  case PCB_VIA_T:
140  return static_cast<const VIA*>( m_parent )->GetStart();
141 
142  default:
143  assert( false );
144  break;
145  }
146 
147  return pt0;
148 }
149 
150 
152 {
153  wxLogDebug(" valid: %d, connected: \n", !!Valid());
154 
155  for( auto i : m_connected )
156  {
157  TRACK* t = static_cast<TRACK*>( i->Parent() );
158  wxLogDebug( " - %p %d\n", t, t->Type() );
159  }
160 }
161 
162 
164 {
165  if( !Valid() )
166  return 0;
167 
168  const auto zone = static_cast<const ZONE_CONTAINER*>( Parent() );
169  const auto& outline = zone->GetFilledPolysList( m_layer ).COutline( m_subpolyIndex );
170 
171  return outline.PointCount() ? 1 : 0;
172 }
173 
174 
175 const VECTOR2I CN_ZONE_LAYER::GetAnchor( int n ) const
176 {
177  if( !Valid() )
178  return VECTOR2I();
179 
180  const auto zone = static_cast<const ZONE_CONTAINER*>( Parent() );
181  const auto& outline = zone->GetFilledPolysList( m_layer ).COutline( m_subpolyIndex );
182 
183  return outline.CPoint( 0 );
184 }
185 
186 
188 {
189  for( auto it = m_connected.begin(); it != m_connected.end(); )
190  {
191  if( !(*it)->Valid() )
192  it = m_connected.erase( it );
193  else
194  ++it;
195  }
196 }
197 
198 
200  {
201  if( !pad->IsOnCopperLayer() )
202  return nullptr;
203 
204  auto item = new CN_ITEM( pad, false, 1 );
205  item->AddAnchor( pad->ShapePos() );
206  item->SetLayers( LAYER_RANGE( F_Cu, B_Cu ) );
207 
208  switch( pad->GetAttribute() )
209  {
210  case PAD_ATTRIB_SMD:
211  case PAD_ATTRIB_NPTH:
212  case PAD_ATTRIB_CONN:
213  {
214  LSET lmsk = pad->GetLayerSet();
215 
216  for( int i = 0; i <= MAX_CU_LAYERS; i++ )
217  {
218  if( lmsk[i] )
219  {
220  item->SetLayer( i );
221  break;
222  }
223  }
224  break;
225  }
226  default:
227  break;
228  }
229 
230  addItemtoTree( item );
231  m_items.push_back( item );
232  SetDirty();
233  return item;
234 }
235 
237 {
238  auto item = new CN_ITEM( track, true );
239  m_items.push_back( item );
240  item->AddAnchor( track->GetStart() );
241  item->AddAnchor( track->GetEnd() );
242  item->SetLayer( track->GetLayer() );
243  addItemtoTree( item );
244  SetDirty();
245  return item;
246 }
247 
249 {
250  auto item = new CN_ITEM( aArc, true );
251  m_items.push_back( item );
252  item->AddAnchor( aArc->GetStart() );
253  item->AddAnchor( aArc->GetEnd() );
254  item->SetLayer( aArc->GetLayer() );
255  addItemtoTree( item );
256  SetDirty();
257  return item;
258 }
259 
261  {
262  auto item = new CN_ITEM( via, true, 1 );
263 
264  m_items.push_back( item );
265  item->AddAnchor( via->GetStart() );
266 
267  item->SetLayers( LAYER_RANGE( via->TopLayer(), via->BottomLayer() ) );
268  addItemtoTree( item );
269  SetDirty();
270  return item;
271  }
272 
273  const std::vector<CN_ITEM*> CN_LIST::Add( ZONE_CONTAINER* zone, PCB_LAYER_ID aLayer )
274  {
275  const auto& polys = zone->GetFilledPolysList( aLayer );
276 
277  std::vector<CN_ITEM*> rv;
278 
279  for( int j = 0; j < polys.OutlineCount(); j++ )
280  {
281  CN_ZONE_LAYER* zitem = new CN_ZONE_LAYER( zone, aLayer, false, j );
282  const auto& outline = zone->GetFilledPolysList( aLayer ).COutline( j );
283 
284  for( int k = 0; k < outline.PointCount(); k++ )
285  zitem->AddAnchor( outline.CPoint( k ) );
286 
287  m_items.push_back( zitem );
288  zitem->SetLayer( aLayer );
289  addItemtoTree( zitem );
290  rv.push_back( zitem );
291  SetDirty();
292  }
293 
294  return rv;
295  }
296 
297 
298 void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
299 {
300  if( !m_hasInvalid )
301  return;
302 
303  auto lastItem = std::remove_if(m_items.begin(), m_items.end(), [&aGarbage] ( CN_ITEM* item )
304  {
305  if( !item->Valid() )
306  {
307  aGarbage.push_back ( item );
308  return true;
309  }
310 
311  return false;
312  } );
313 
314  m_items.resize( lastItem - m_items.begin() );
315 
316  for( auto item : m_items )
317  item->RemoveInvalidRefs();
318 
319  for( auto item : aGarbage )
320  m_index.Remove( item );
321 
322  m_hasInvalid = false;
323 }
324 
325 
327 {
328  assert( m_item->Valid() );
329  return m_item->Parent();
330 }
331 
332 
333 bool CN_ANCHOR::Valid() const
334 {
335  if( !m_item )
336  return false;
337 
338  return m_item->Valid();
339 }
340 
341 
343 {
344  int accuracy = 0;
345 
346  if( !m_cluster )
347  return true;
348 
349  // the minimal number of items connected to item_ref
350  // at this anchor point to decide the anchor is *not* dangling
351  size_t minimal_count = 1;
352  size_t connected_count = m_item->ConnectedItems().size();
353 
354  // a via can be removed if connected to only one other item.
355  if( Parent()->Type() == PCB_VIA_T )
356  return connected_count < 2;
357 
358  if( m_item->AnchorCount() == 1 )
359  return connected_count < minimal_count;
360 
361  if( Parent()->Type() == PCB_TRACE_T || Parent()->Type() == PCB_ARC_T )
362  accuracy = ( static_cast<const TRACK*>( Parent() )->GetWidth() + 1 )/ 2;
363 
364  // Items with multiple anchors have usually items connected to each anchor.
365  // We want only the item count of this anchor point
366  connected_count = 0;
367  for( auto item : m_item->ConnectedItems() )
368  {
369  if( item->Parent()->Type() == PCB_ZONE_AREA_T )
370  {
371  ZONE_CONTAINER* zone = static_cast<ZONE_CONTAINER*>( item->Parent() );
372 
373  if( zone->HitTestFilledArea( static_cast<PCB_LAYER_ID>( item->Layer() ),
374  wxPoint( Pos() ), accuracy ) )
375  connected_count++;
376  }
377  else if( item->Parent()->HitTest( wxPoint( Pos() ), accuracy ) )
378  connected_count++;
379  }
380 
381  return connected_count < minimal_count;
382 }
383 
384 
386 {
387  if( !m_cluster )
388  return 0;
389 
390  int connected_count = 0;
391 
392  for( auto item : m_item->ConnectedItems() )
393  {
394  if( item->Parent()->Type() == PCB_ZONE_AREA_T )
395  {
396  ZONE_CONTAINER* zone = static_cast<ZONE_CONTAINER*>( item->Parent() );
397 
398  if( zone->HitTestFilledArea( static_cast<PCB_LAYER_ID>( item->Layer() ),
399  wxPoint( Pos().x, Pos().y ) ) )
400  connected_count++;
401  }
402  else if( item->Parent()->HitTest( wxPoint( Pos().x, Pos().y ) ) )
403  connected_count++;
404  }
405 
406  return connected_count;
407 }
408 
409 
411 {
412  m_items.reserve( 64 );
413  m_originPad = nullptr;
414  m_originNet = -1;
415  m_conflicting = false;
416 }
417 
418 
420 {
421 }
422 
423 
425 {
426  if( !m_originPad || !m_originPad->Valid() )
427  return "<none>";
428  else
429  return m_originPad->Parent()->GetNetname();
430 }
431 
432 
433 bool CN_CLUSTER::Contains( const CN_ITEM* aItem )
434 {
435  return alg::contains( m_items, aItem );
436 }
437 
438 
440 {
441  return std::find_if( m_items.begin(), m_items.end(), [ &aItem ] ( const CN_ITEM* item )
442  { return item->Valid() && item->Parent() == aItem; } ) != m_items.end();
443 }
444 
445 
447 {
448  for( auto item : m_items )
449  {
450  wxLogTrace( "CN", " - item : %p bitem : %p type : %d inet %s\n", item, item->Parent(),
451  item->Parent()->Type(), (const char*) item->Parent()->GetNetname().c_str() );
452  wxLogTrace( "CN", "- item : %p bitem : %p type : %d inet %s\n", item, item->Parent(),
453  item->Parent()->Type(), (const char*) item->Parent()->GetNetname().c_str() );
454  item->Dump();
455  }
456 }
457 
458 
460 {
461  m_items.push_back( item );
462 
463  if( item->Net() <= 0 )
464  return;
465 
466  if( m_originNet <= 0 )
467  {
468  m_originNet = item->Net();
469  }
470 
471  if( item->Parent()->Type() == PCB_PAD_T )
472  {
473  if( !m_originPad )
474  {
475  m_originPad = item;
476  m_originNet = item->Net();
477  }
478 
479  if( m_originPad && item->Net() != m_originNet )
480  {
481  m_conflicting = true;
482  }
483  }
484 }
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
const CONNECTED_ITEMS & ConnectedItems() const
bool Contains(const CN_ITEM *aItem)
std::vector< CN_ITEM * > m_items
ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:61
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
BOARD_CONNECTED_ITEM * m_parent
wxPoint GetPosition() const override
Definition: class_pad.h:172
std::shared_ptr< CN_CLUSTER > m_cluster
Cluster to which the anchor belongs.
const wxPoint & GetStart() const
Definition: class_track.h:116
void addItemtoTree(CN_ITEM *item)
bool m_valid
valid flag, used to identify garbage items (we use lazy removal)
CN_ITEM * Add(D_PAD *pad)
Smd pad, appears on the solder paste layer (default)
Definition: pad_shapes.h:81
class ZONE_CONTAINER, a zone area
Definition: typeinfo.h:106
const SHAPE_POLY_SET & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Function GetFilledPolysList returns a reference to the list of filled polygons.
Definition: class_zone.h:629
class ARC, an arc track segment on a copper layer
Definition: typeinfo.h:98
wxString GetNetname() const
Function GetNetname.
class D_PAD, a pad in a footprint
Definition: typeinfo.h:90
#define KI_FALLTHROUGH
The KI_FALLTHROUGH macro is to be used when switch statement cases should purposely fallthrough from ...
Definition: macros.h:89
BOARD_CONNECTED_ITEM * Parent() const
const std::shared_ptr< SHAPE_POLY_SET > & GetEffectivePolygon(PCB_LAYER_ID=UNDEFINED_LAYER) const
Definition: class_pad.cpp:253
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:208
like PAD_PTH, but not plated mechanical use only, no connection allowed
Definition: pad_shapes.h:85
bool IsDangling() const
has meaning only for tracks and vias.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
void SetDirty(bool aDirty=true)
int ConnectedItemsCount() const
has meaning only for tracks and vias.
int Net() const
PAD_ATTR_T GetAttribute() const
Definition: class_pad.h:352
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:96
virtual int AnchorCount() const
std::vector< CN_ITEM * > m_items
PCB_LAYER_ID
A quick note on layer IDs:
LSET is a set of PCB_LAYER_IDs.
virtual int AnchorCount() const override
bool IsOnCopperLayer() const override
Definition: class_pad.h:216
LSET GetLayerSet() const override
Function GetLayerSet returns a std::bitset of all layers on which the item physically resides.
Definition: class_pad.h:349
void Add(CN_ITEM *item)
bool contains(_Container __container, _Value __value)
Returns true if the container contains the given value.
Definition: kicad_algo.h:81
Like smd, does not appear on the solder paste layer (default) note also has a special attribute in Ge...
Definition: pad_shapes.h:82
PCB_LAYER_ID m_layer
bool Valid() const
virtual const VECTOR2I GetAnchor(int n) const
Definition: seg.h:39
wxString OriginNetName() const
void AddAnchor(const VECTOR2I &aPos)
CN_ITEM * m_item
Item owning the anchor.
SHAPE_LINE_CHAIN.
void SetLayer(int aLayer)
Function SetLayer()
CN_ITEM * m_originPad
double GetOrientation() const
Function GetOrientation returns the rotation angle of the pad in a variety of units (the basic call r...
Definition: class_pad.h:338
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
wxPoint ShapePos() const
Definition: class_pad.cpp:610
BOARD_CONNECTED_ITEM * Parent() const
virtual const VECTOR2I GetAnchor(int n) const override
bool HitTestFilledArea(PCB_LAYER_ID aLayer, const wxPoint &aRefPos, int aAccuracy=0) const
Function HitTestFilledArea tests if the given wxPoint is within the bounds of a filled area of this z...
Definition: class_zone.cpp:481
PCB_LAYER_ID TopLayer() const
const wxPoint & GetEnd() const
Definition: class_track.h:113
void Remove(T aItem)
Function Remove() Removes an item from the tree.
const VECTOR2I & Pos() const
CONNECTED_ITEMS m_connected
list of items physically connected (touching)
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:97
PAD_SHAPE_T GetShape() const
Definition: class_pad.h:164
const wxSize & GetSize() const
Definition: class_pad.h:231
PCB_LAYER_ID BottomLayer() const
virtual PCB_LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
LAYER_RANGE.
Definition: pns_layerset.h:32
void RemoveInvalidRefs()
bool Valid() const
CN_RTREE< CN_ITEM * > m_index
KICAD_T Type() const
Function Type()
Definition: eda_item.h:181