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>
29 #include <macros.h>
31 
33 {
34  if( !m_valid )
35  return 0;
36 
37  switch( m_parent->Type() )
38  {
39  case PCB_PAD_T:
40  return 5; // center, north, south, east and west
41  case PCB_TRACE_T:
42  case PCB_ARC_T:
43  return 2; // start and end
44  default:
45  return 1;
46  }
47 }
48 
49 
50 const VECTOR2I CN_ITEM::GetAnchor( int n ) const
51 {
52  VECTOR2I pt0;
53 
54  if( !m_valid )
55  return pt0;
56 
57  switch( m_parent->Type() )
58  {
59  case PCB_PAD_T:
60  {
61  PAD* pad = static_cast<PAD*>( m_parent );
62 
63  if( n == 0 )
64  return VECTOR2I( pad->GetPosition() );
65 
66  // ShapePos() is the geometric center (not anchor) for the pad
67  pt0 = pad->ShapePos();
68  VECTOR2I pt1 = pt0;
69 
70  switch( pad->GetShape() )
71  {
73  // Because the trap delta is applied as +1/2 at one end and -1/2 at the other,
74  // the midpoint is actually unchanged. Therefore all the cardinal points are
75  // the same as for a rectangle.
77 
78  case PAD_SHAPE::RECT:
79  case PAD_SHAPE::CIRCLE:
80  case PAD_SHAPE::OVAL:
83  switch( n )
84  {
85  case 1: pt1.y -= pad->GetSize().y / 2; break; // North
86  case 2: pt1.y += pad->GetSize().y / 2; break; // South
87  case 3: pt1.x -= pad->GetSize().x / 2; break; // East
88  case 4: pt1.x += pad->GetSize().x / 2; break; // West
89  default: break; // Wicked witch
90  }
91 
92  if( pad->GetOrientation() )
93  RotatePoint( pt1, pad->ShapePos(), pad->GetOrientation() );
94 
95  // Thermal spokes on circular pads form an 'X' instead of a '+'
96  if( pad->GetShape() == PAD_SHAPE::CIRCLE )
97  RotatePoint( pt1, pad->ShapePos(), 450 );
98 
99  return pt1;
100 
101  case PAD_SHAPE::CUSTOM:
102  {
103  switch( n )
104  {
105  case 1: pt1.y = INT_MIN / 2; break; // North
106  case 2: pt1.y = INT_MAX / 2; break; // South
107  case 3: pt1.x = INT_MIN / 2; break; // East
108  case 4: pt1.x = INT_MAX / 2; break; // West
109  default: break; // Wicked witch
110  }
111 
112  if( pad->GetOrientation() )
113  RotatePoint( pt1, pad->ShapePos(), pad->GetOrientation() );
114 
115  const std::shared_ptr<SHAPE_POLY_SET>& padPolySet = pad->GetEffectivePolygon();
116  const SHAPE_LINE_CHAIN& padOutline = padPolySet->COutline( 0 );
117  SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
118 
119  padOutline.Intersect( SEG( pt0, pt1 ), intersections );
120 
121  if( intersections.empty() )
122  {
123  // There should always be at least some copper outside the hole and/or
124  // shapePos center
125  assert( false );
126  return pt0;
127  }
128 
129  return intersections[ intersections.size() - 1 ].p;
130  }
131  }
132 
133  break;
134  }
135  case PCB_TRACE_T:
136  case PCB_ARC_T:
137  if( n == 0 )
138  return static_cast<const TRACK*>( m_parent )->GetStart();
139  else
140  return static_cast<const TRACK*>( m_parent )->GetEnd();
141 
142  case PCB_VIA_T:
143  return static_cast<const VIA*>( m_parent )->GetStart();
144 
145  default:
146  assert( false );
147  break;
148  }
149 
150  return pt0;
151 }
152 
153 
155 {
156  wxLogDebug(" valid: %d, connected: \n", !!Valid());
157 
158  for( auto i : m_connected )
159  {
160  TRACK* t = static_cast<TRACK*>( i->Parent() );
161  wxLogDebug( " - %p %d\n", t, t->Type() );
162  }
163 }
164 
165 
167 {
168  if( !Valid() )
169  return 0;
170 
171  const ZONE* zone = static_cast<const ZONE*>( Parent() );
173 
174  return outline.PointCount() ? 1 : 0;
175 }
176 
177 
178 const VECTOR2I CN_ZONE_LAYER::GetAnchor( int n ) const
179 {
180  if( !Valid() )
181  return VECTOR2I();
182 
183  const ZONE* zone = static_cast<const ZONE*>( Parent() );
185 
186  return outline.CPoint( 0 );
187 }
188 
189 
191 {
192  for( auto it = m_connected.begin(); it != m_connected.end(); )
193  {
194  if( !(*it)->Valid() )
195  it = m_connected.erase( it );
196  else
197  ++it;
198  }
199 }
200 
201 
203  {
204  if( !pad->IsOnCopperLayer() )
205  return nullptr;
206 
207  auto item = new CN_ITEM( pad, false, 1 );
208  item->AddAnchor( pad->ShapePos() );
209  item->SetLayers( LAYER_RANGE( F_Cu, B_Cu ) );
210 
211  switch( pad->GetAttribute() )
212  {
213  case PAD_ATTRIB::SMD:
214  case PAD_ATTRIB::NPTH:
215  case PAD_ATTRIB::CONN:
216  {
217  LSET lmsk = pad->GetLayerSet();
218 
219  for( int i = 0; i <= MAX_CU_LAYERS; i++ )
220  {
221  if( lmsk[i] )
222  {
223  item->SetLayer( i );
224  break;
225  }
226  }
227  break;
228  }
229  default:
230  break;
231  }
232 
233  addItemtoTree( item );
234  m_items.push_back( item );
235  SetDirty();
236  return item;
237 }
238 
240 {
241  auto item = new CN_ITEM( track, true );
242  m_items.push_back( item );
243  item->AddAnchor( track->GetStart() );
244  item->AddAnchor( track->GetEnd() );
245  item->SetLayer( track->GetLayer() );
246  addItemtoTree( item );
247  SetDirty();
248  return item;
249 }
250 
252 {
253  auto item = new CN_ITEM( aArc, true );
254  m_items.push_back( item );
255  item->AddAnchor( aArc->GetStart() );
256  item->AddAnchor( aArc->GetEnd() );
257  item->SetLayer( aArc->GetLayer() );
258  addItemtoTree( item );
259  SetDirty();
260  return item;
261 }
262 
264  {
265  auto item = new CN_ITEM( via, !via->GetIsFree(), 1 );
266 
267  m_items.push_back( item );
268  item->AddAnchor( via->GetStart() );
269 
270  item->SetLayers( LAYER_RANGE( via->TopLayer(), via->BottomLayer() ) );
271  addItemtoTree( item );
272  SetDirty();
273  return item;
274  }
275 
276  const std::vector<CN_ITEM*> CN_LIST::Add( ZONE* zone, PCB_LAYER_ID aLayer )
277  {
278  const auto& polys = zone->GetFilledPolysList( aLayer );
279 
280  std::vector<CN_ITEM*> rv;
281 
282  for( int j = 0; j < polys.OutlineCount(); j++ )
283  {
284  CN_ZONE_LAYER* zitem = new CN_ZONE_LAYER( zone, aLayer, false, j );
285  const auto& outline = zone->GetFilledPolysList( aLayer ).COutline( j );
286 
287  for( int k = 0; k < outline.PointCount(); k++ )
288  zitem->AddAnchor( outline.CPoint( k ) );
289 
290  m_items.push_back( zitem );
291  zitem->SetLayer( aLayer );
292  addItemtoTree( zitem );
293  rv.push_back( zitem );
294  SetDirty();
295  }
296 
297  return rv;
298  }
299 
300 
301 void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
302 {
303  if( !m_hasInvalid )
304  return;
305 
306  auto lastItem = std::remove_if(m_items.begin(), m_items.end(), [&aGarbage] ( CN_ITEM* item )
307  {
308  if( !item->Valid() )
309  {
310  aGarbage.push_back ( item );
311  return true;
312  }
313 
314  return false;
315  } );
316 
317  m_items.resize( lastItem - m_items.begin() );
318 
319  for( auto item : m_items )
320  item->RemoveInvalidRefs();
321 
322  for( auto item : aGarbage )
323  m_index.Remove( item );
324 
325  m_hasInvalid = false;
326 }
327 
328 
330 {
331  assert( m_item->Valid() );
332  return m_item->Parent();
333 }
334 
335 
336 bool CN_ANCHOR::Valid() const
337 {
338  if( !m_item )
339  return false;
340 
341  return m_item->Valid();
342 }
343 
344 
346 {
347  int accuracy = 0;
348 
349  if( !m_cluster )
350  return true;
351 
352  // the minimal number of items connected to item_ref
353  // at this anchor point to decide the anchor is *not* dangling
354  size_t minimal_count = 1;
355  size_t connected_count = m_item->ConnectedItems().size();
356 
357  // a via can be removed if connected to only one other item.
358  if( Parent()->Type() == PCB_VIA_T )
359  return connected_count < 2;
360 
361  if( m_item->AnchorCount() == 1 )
362  return connected_count < minimal_count;
363 
364  if( Parent()->Type() == PCB_TRACE_T || Parent()->Type() == PCB_ARC_T )
365  accuracy = ( static_cast<const TRACK*>( Parent() )->GetWidth() + 1 )/ 2;
366 
367  // Items with multiple anchors have usually items connected to each anchor.
368  // We want only the item count of this anchor point
369  connected_count = 0;
370  for( auto item : m_item->ConnectedItems() )
371  {
372  if( item->Parent()->Type() == PCB_ZONE_T )
373  {
374  ZONE* zone = static_cast<ZONE*>( item->Parent() );
375 
376  if( zone->HitTestFilledArea( static_cast<PCB_LAYER_ID>( item->Layer() ),
377  wxPoint( Pos() ), accuracy ) )
378  connected_count++;
379  }
380  else if( item->Parent()->HitTest( wxPoint( Pos() ), accuracy ) )
381  connected_count++;
382  }
383 
384  return connected_count < minimal_count;
385 }
386 
387 
389 {
390  if( !m_cluster )
391  return 0;
392 
393  int connected_count = 0;
394 
395  for( CN_ITEM* item : m_item->ConnectedItems() )
396  {
397  if( item->Parent()->Type() == PCB_ZONE_T )
398  {
399  ZONE* zone = static_cast<ZONE*>( item->Parent() );
400 
401  if( zone->HitTestFilledArea( static_cast<PCB_LAYER_ID>( item->Layer() ),
402  (wxPoint) Pos() ) )
403  connected_count++;
404  }
405  else if( item->Parent()->HitTest( (wxPoint) Pos() ) )
406  connected_count++;
407  }
408 
409  return connected_count;
410 }
411 
412 
414 {
415  m_items.reserve( 64 );
416  m_originPad = nullptr;
417  m_originNet = -1;
418  m_conflicting = false;
419 }
420 
421 
423 {
424 }
425 
426 
428 {
429  if( !m_originPad || !m_originPad->Valid() )
430  return "<none>";
431  else
432  return m_originPad->Parent()->GetNetname();
433 }
434 
435 
436 bool CN_CLUSTER::Contains( const CN_ITEM* aItem )
437 {
438  return alg::contains( m_items, aItem );
439 }
440 
441 
443 {
444  return std::find_if( m_items.begin(), m_items.end(),
445  [ &aItem ] ( const CN_ITEM* item )
446  {
447  return item->Valid() && item->Parent() == aItem;
448  } ) != m_items.end();
449 }
450 
451 
453 {
454  for( auto item : m_items )
455  {
456  wxLogTrace( "CN", " - item : %p bitem : %p type : %d inet %s\n",
457  item,
458  item->Parent(),
459  item->Parent()->Type(),
460  (const char*) item->Parent()->GetNetname().c_str() );
461  wxLogTrace( "CN", "- item : %p bitem : %p type : %d inet %s\n",
462  item,
463  item->Parent(),
464  item->Parent()->Type(),
465  (const char*) item->Parent()->GetNetname().c_str() );
466  item->Dump();
467  }
468 }
469 
470 
472 {
473  m_items.push_back( item );
474 
475  int netCode = item->Net();
476 
477  if( netCode <= 0 )
478  return;
479 
480  if( m_originNet <= 0 )
481  {
482  m_originNet = netCode;
483  }
484 
485  if( item->Parent()->Type() == PCB_PAD_T )
486  {
487  if( m_netRanks.count( netCode ) )
488  {
489  m_netRanks[netCode]++;
490 
491  if( m_netRanks.count( m_originNet ) && m_netRanks[netCode] > m_netRanks[m_originNet] )
492  {
493  m_originPad = item;
494  m_originNet = netCode;
495  }
496  }
497  else
498  {
499  m_netRanks[netCode] = 1;
500 
501  if( !m_originPad )
502  {
503  m_originPad = item;
504  m_originNet = netCode;
505  }
506  }
507 
508  if( m_originPad && item->Net() != m_originNet )
509  {
510  m_conflicting = true;
511  }
512  }
513 }
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)
Like smd, does not appear on the solder paste layer (default)
Smd pad, appears on the solder paste layer (default)
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
Definition: zone.h:632
BOARD_CONNECTED_ITEM * Parent() const
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:228
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
Test if the given wxPoint is within the bounds of a filled area of this zone.
Definition: zone.cpp:504
int Net() const
allow parallel connection threads
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
This file contains miscellaneous commonly used macros and functions.
virtual int AnchorCount() const
const VECTOR2I & CPoint(int aIndex) const
Function Point()
std::unordered_map< int, int > m_netRanks
std::vector< CN_ITEM * > m_items
like PAD_PTH, but not plated
PCB_LAYER_ID
A quick note on layer IDs:
LSET is a set of PCB_LAYER_IDs.
virtual int AnchorCount() const override
Handle a list of polygons defining a copper zone.
Definition: zone.h:57
class ZONE, a copper pour area
Definition: typeinfo.h:105
void Add(CN_ITEM *item)
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)
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 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
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:163