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  break;
151  }
152 
153  return pt0;
154 }
155 
156 
158 {
159  wxLogDebug(" valid: %d, connected: \n", !!Valid());
160 
161  for( CN_ITEM* i : m_connected )
162  {
163  PCB_TRACK* t = static_cast<PCB_TRACK*>( i->Parent() );
164  wxLogDebug( " - %p %d\n", t, t->Type() );
165  }
166 }
167 
168 
170 {
171  if( !Valid() )
172  return 0;
173 
174  const ZONE* zone = static_cast<const ZONE*>( Parent() );
176 
177  return outline.PointCount() ? 1 : 0;
178 }
179 
180 
181 const VECTOR2I CN_ZONE_LAYER::GetAnchor( int n ) const
182 {
183  if( !Valid() )
184  return VECTOR2I();
185 
186  const ZONE* zone = static_cast<const ZONE*>( Parent() );
188 
189  return outline.CPoint( 0 );
190 }
191 
192 
194 {
195  for( auto it = m_connected.begin(); it != m_connected.end(); )
196  {
197  if( !(*it)->Valid() )
198  it = m_connected.erase( it );
199  else
200  ++it;
201  }
202 }
203 
204 
206  {
207  if( !pad->IsOnCopperLayer() )
208  return nullptr;
209 
210  auto item = new CN_ITEM( pad, false, 1 );
211  item->AddAnchor( pad->ShapePos() );
212  item->SetLayers( LAYER_RANGE( F_Cu, B_Cu ) );
213 
214  switch( pad->GetAttribute() )
215  {
216  case PAD_ATTRIB::SMD:
217  case PAD_ATTRIB::NPTH:
218  case PAD_ATTRIB::CONN:
219  {
220  LSET lmsk = pad->GetLayerSet();
221 
222  for( int i = 0; i <= MAX_CU_LAYERS; i++ )
223  {
224  if( lmsk[i] )
225  {
226  item->SetLayer( i );
227  break;
228  }
229  }
230  break;
231  }
232  default:
233  break;
234  }
235 
236  addItemtoTree( item );
237  m_items.push_back( item );
238  SetDirty();
239  return item;
240 }
241 
243 {
244  auto item = new CN_ITEM( track, true );
245  m_items.push_back( item );
246  item->AddAnchor( track->GetStart() );
247  item->AddAnchor( track->GetEnd() );
248  item->SetLayer( track->GetLayer() );
249  addItemtoTree( item );
250  SetDirty();
251  return item;
252 }
253 
255 {
256  auto item = new CN_ITEM( aArc, true );
257  m_items.push_back( item );
258  item->AddAnchor( aArc->GetStart() );
259  item->AddAnchor( aArc->GetEnd() );
260  item->SetLayer( aArc->GetLayer() );
261  addItemtoTree( item );
262  SetDirty();
263  return item;
264 }
265 
267  {
268  auto item = new CN_ITEM( via, !via->GetIsFree(), 1 );
269 
270  m_items.push_back( item );
271  item->AddAnchor( via->GetStart() );
272 
273  item->SetLayers( LAYER_RANGE( via->TopLayer(), via->BottomLayer() ) );
274  addItemtoTree( item );
275  SetDirty();
276  return item;
277  }
278 
279  const std::vector<CN_ITEM*> CN_LIST::Add( ZONE* zone, PCB_LAYER_ID aLayer )
280  {
281  const auto& polys = zone->GetFilledPolysList( aLayer );
282 
283  std::vector<CN_ITEM*> rv;
284 
285  for( int j = 0; j < polys.OutlineCount(); j++ )
286  {
287  CN_ZONE_LAYER* zitem = new CN_ZONE_LAYER( zone, aLayer, false, j );
288  const auto& outline = zone->GetFilledPolysList( aLayer ).COutline( j );
289 
290  for( int k = 0; k < outline.PointCount(); k++ )
291  zitem->AddAnchor( outline.CPoint( k ) );
292 
293  m_items.push_back( zitem );
294  zitem->SetLayer( aLayer );
295  addItemtoTree( zitem );
296  rv.push_back( zitem );
297  SetDirty();
298  }
299 
300  return rv;
301  }
302 
303 
304 void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
305 {
306  if( !m_hasInvalid )
307  return;
308 
309  auto lastItem = std::remove_if(m_items.begin(), m_items.end(), [&aGarbage] ( CN_ITEM* item )
310  {
311  if( !item->Valid() )
312  {
313  aGarbage.push_back ( item );
314  return true;
315  }
316 
317  return false;
318  } );
319 
320  m_items.resize( lastItem - m_items.begin() );
321 
322  for( auto item : m_items )
323  item->RemoveInvalidRefs();
324 
325  for( auto item : aGarbage )
326  m_index.Remove( item );
327 
328  m_hasInvalid = false;
329 }
330 
331 
333 {
334  assert( m_item->Valid() );
335  return m_item->Parent();
336 }
337 
338 
339 bool CN_ANCHOR::Valid() const
340 {
341  if( !m_item )
342  return false;
343 
344  return m_item->Valid();
345 }
346 
347 
349 {
350  int accuracy = 0;
351 
352  if( !m_cluster )
353  return true;
354 
355  // the minimal number of items connected to item_ref
356  // at this anchor point to decide the anchor is *not* dangling
357  size_t minimal_count = 1;
358  size_t connected_count = m_item->ConnectedItems().size();
359 
360  // a via can be removed if connected to only one other item.
361  if( Parent()->Type() == PCB_VIA_T )
362  return connected_count < 2;
363 
364  if( m_item->AnchorCount() == 1 )
365  return connected_count < minimal_count;
366 
367  if( Parent()->Type() == PCB_TRACE_T || Parent()->Type() == PCB_ARC_T )
368  accuracy = ( static_cast<const PCB_TRACK*>( Parent() )->GetWidth() + 1 ) / 2;
369 
370  // Items with multiple anchors have usually items connected to each anchor.
371  // We want only the item count of this anchor point
372  connected_count = 0;
373  for( auto 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( static_cast<PCB_LAYER_ID>( item->Layer() ),
380  wxPoint( Pos() ), accuracy ) )
381  connected_count++;
382  }
383  else if( item->Parent()->HitTest( wxPoint( Pos() ), accuracy ) )
384  connected_count++;
385  }
386 
387  return connected_count < minimal_count;
388 }
389 
390 
392 {
393  if( !m_cluster )
394  return 0;
395 
396  int connected_count = 0;
397 
398  for( CN_ITEM* item : m_item->ConnectedItems() )
399  {
400  if( item->Parent()->Type() == PCB_ZONE_T )
401  {
402  ZONE* zone = static_cast<ZONE*>( item->Parent() );
403 
404  if( zone->HitTestFilledArea( static_cast<PCB_LAYER_ID>( item->Layer() ),
405  (wxPoint) Pos() ) )
406  connected_count++;
407  }
408  else if( item->Parent()->HitTest( (wxPoint) Pos() ) )
409  connected_count++;
410  }
411 
412  return connected_count;
413 }
414 
415 
417 {
418  m_items.reserve( 64 );
419  m_originPad = nullptr;
420  m_originNet = -1;
421  m_conflicting = false;
422 }
423 
424 
426 {
427 }
428 
429 
431 {
432  if( !m_originPad || !m_originPad->Valid() )
433  return "<none>";
434  else
435  return m_originPad->Parent()->GetNetname();
436 }
437 
438 
439 bool CN_CLUSTER::Contains( const CN_ITEM* aItem )
440 {
441  return alg::contains( m_items, aItem );
442 }
443 
444 
446 {
447  return std::find_if( m_items.begin(), m_items.end(),
448  [ &aItem ] ( const CN_ITEM* item )
449  {
450  return item->Valid() && item->Parent() == aItem;
451  } ) != m_items.end();
452 }
453 
454 
456 {
457  for( auto item : m_items )
458  {
459  wxLogTrace( "CN", " - item : %p bitem : %p type : %d inet %s\n",
460  item,
461  item->Parent(),
462  item->Parent()->Type(),
463  (const char*) item->Parent()->GetNetname().c_str() );
464  wxLogTrace( "CN", "- item : %p bitem : %p type : %d inet %s\n",
465  item,
466  item->Parent(),
467  item->Parent()->Type(),
468  (const char*) item->Parent()->GetNetname().c_str() );
469  item->Dump();
470  }
471 }
472 
473 
475 {
476  m_items.push_back( item );
477 
478  int netCode = item->Net();
479 
480  if( netCode <= 0 )
481  return;
482 
483  if( m_originNet <= 0 )
484  {
485  m_originNet = netCode;
486  }
487 
488  if( item->Parent()->Type() == PCB_PAD_T )
489  {
490  if( m_netRanks.count( netCode ) )
491  {
492  m_netRanks[netCode]++;
493 
494  if( m_netRanks.count( m_originNet ) && m_netRanks[netCode] > m_netRanks[m_originNet] )
495  {
496  m_originPad = item;
497  m_originNet = netCode;
498  }
499  }
500  else
501  {
502  m_netRanks[netCode] = 1;
503 
504  if( !m_originPad )
505  {
506  m_originPad = item;
507  m_originNet = netCode;
508  }
509  }
510 
511  if( m_originPad && item->Net() != m_originNet )
512  {
513  m_conflicting = true;
514  }
515  }
516 }
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:636
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:506
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
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:98
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).
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
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:171
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