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