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