KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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-2022 KiCad Developers, see AUTHORS.txt for contributors.
7 *
8 * @author Tomasz Wlostowski <[email protected]>
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_TRACE_T:
43 case PCB_ARC_T:
44 return 2; // start and end
45
46 case PCB_SHAPE_T:
47 return m_anchors.size();
48
49 default:
50 return 1;
51 }
52}
53
54
55const VECTOR2I CN_ITEM::GetAnchor( int n ) const
56{
57 if( !m_valid )
58 return VECTOR2I();
59
60 switch( m_parent->Type() )
61 {
62 case PCB_PAD_T:
63 return static_cast<PAD*>( m_parent )->GetPosition();
64
65 case PCB_TRACE_T:
66 case PCB_ARC_T:
67 if( n == 0 )
68 return static_cast<const PCB_TRACK*>( m_parent )->GetStart();
69 else
70 return static_cast<const PCB_TRACK*>( m_parent )->GetEnd();
71
72 case PCB_VIA_T:
73 return static_cast<const PCB_VIA*>( m_parent )->GetStart();
74
75 case PCB_SHAPE_T:
76 return ( n < static_cast<int>( m_anchors.size() ) ) ? m_anchors[n]->Pos() : VECTOR2I();
77
78 default:
80 return VECTOR2I();
81 }
82}
83
84
86{
87 wxLogDebug(" valid: %d, connected: \n", !!Valid());
88
89 for( CN_ITEM* i : m_connected )
90 {
91 PCB_TRACK* t = static_cast<PCB_TRACK*>( i->Parent() );
92 wxLogDebug( wxT( " - %p %d\n" ), t, t->Type() );
93 }
94}
95
96
98{
99 if( !Valid() )
100 return 0;
101
102 const ZONE* zone = static_cast<const ZONE*>( Parent() );
103
104 return zone->GetFilledPolysList( m_layer )->COutline( m_subpolyIndex ).PointCount() ? 1 : 0;
105}
106
107
109{
110 if( !Valid() )
111 return VECTOR2I();
112
113 const ZONE* zone = static_cast<const ZONE*>( Parent() );
114
115 return zone->GetFilledPolysList( m_layer )->COutline( m_subpolyIndex ).CPoint( 0 );
116}
117
118
120{
121 int count = 0;
122
123 for( CN_ITEM* item : ConnectedItems() )
124 {
125 if( item->Valid() )
126 count++;
127
128 if( count > 1 )
129 break;
130 }
131
132 return count == 1;
133}
134
135
137{
138 for( auto it = m_connected.begin(); it != m_connected.end(); /* increment in loop */ )
139 {
140 if( !(*it)->Valid() )
141 it = m_connected.erase( it );
142 else
143 ++it;
144 }
145}
146
147
149 {
150 if( !pad->IsOnCopperLayer() )
151 return nullptr;
152
153 auto item = new CN_ITEM( pad, false, 1 );
154 item->AddAnchor( pad->ShapePos() );
155 item->SetLayers( LAYER_RANGE( F_Cu, B_Cu ) );
156
157 switch( pad->GetAttribute() )
158 {
159 case PAD_ATTRIB::SMD:
160 case PAD_ATTRIB::NPTH:
161 case PAD_ATTRIB::CONN:
162 {
163 LSET lmsk = pad->GetLayerSet();
164
165 for( int i = 0; i <= MAX_CU_LAYERS; i++ )
166 {
167 if( lmsk[i] )
168 {
169 item->SetLayer( i );
170 break;
171 }
172 }
173 break;
174 }
175 default:
176 break;
177 }
178
179 addItemtoTree( item );
180 m_items.push_back( item );
181 SetDirty();
182 return item;
183}
184
185
187{
188 CN_ITEM* item = new CN_ITEM( track, true );
189 m_items.push_back( item );
190 item->AddAnchor( track->GetStart() );
191 item->AddAnchor( track->GetEnd() );
192 item->SetLayer( track->GetLayer() );
193 addItemtoTree( item );
194 SetDirty();
195 return item;
196}
197
198
200{
201 CN_ITEM* item = new CN_ITEM( aArc, true );
202 m_items.push_back( item );
203 item->AddAnchor( aArc->GetStart() );
204 item->AddAnchor( aArc->GetEnd() );
205 item->SetLayer( aArc->GetLayer() );
206 addItemtoTree( item );
207 SetDirty();
208 return item;
209}
210
211
213{
214 CN_ITEM* item = new CN_ITEM( via, !via->GetIsFree(), 1 );
215
216 m_items.push_back( item );
217 item->AddAnchor( via->GetStart() );
218
219 item->SetLayers( LAYER_RANGE( via->TopLayer(), via->BottomLayer() ) );
220 addItemtoTree( item );
221 SetDirty();
222 return item;
223}
224
225
226const std::vector<CN_ITEM*> CN_LIST::Add( ZONE* zone, PCB_LAYER_ID aLayer )
227{
228 const std::shared_ptr<SHAPE_POLY_SET>& polys = zone->GetFilledPolysList( aLayer );
229
230 std::vector<CN_ITEM*> rv;
231
232 for( int j = 0; j < polys->OutlineCount(); j++ )
233 {
234 CN_ZONE_LAYER* zitem = new CN_ZONE_LAYER( zone, aLayer, j );
235
236 zitem->BuildRTree();
237
238 for( const VECTOR2I& pt : zone->GetFilledPolysList( aLayer )->COutline( j ).CPoints() )
239 zitem->AddAnchor( pt );
240
241 rv.push_back( Add( zitem ) );
242 }
243
244 return rv;
245}
246
247
249{
250 m_items.push_back( zitem );
251 addItemtoTree( zitem );
252 SetDirty();
253 return zitem;
254}
255
256
258{
259 CN_ITEM* item = new CN_ITEM( shape, true );
260 m_items.push_back( item );
261
262 for( const VECTOR2I& point : shape->GetConnectionPoints() )
263 item->AddAnchor( point );
264
265 item->SetLayer( shape->GetLayer() );
266 addItemtoTree( item );
267 SetDirty();
268 return item;
269}
270
271
272void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
273{
274 if( !m_hasInvalid )
275 return;
276
277 auto lastItem = std::remove_if( m_items.begin(), m_items.end(),
278 [&aGarbage]( CN_ITEM* item )
279 {
280 if( !item->Valid() )
281 {
282 aGarbage.push_back ( item );
283 return true;
284 }
285
286 return false;
287 } );
288
289 m_items.resize( lastItem - m_items.begin() );
290
291 for( CN_ITEM* item : aGarbage )
292 m_index.Remove( item );
293
294 m_hasInvalid = false;
295}
296
297
299{
300 assert( m_item->Valid() );
301 return m_item->Parent();
302}
303
304
306{
307 if( !m_item )
308 return false;
309
310 return m_item->Valid();
311}
312
313
315{
316 return !Valid() || m_item->Dirty();
317}
318
319
321{
322 int accuracy = 0;
323
324 if( !m_cluster )
325 return true;
326
327 // the minimal number of items connected to item_ref
328 // at this anchor point to decide the anchor is *not* dangling
329 size_t minimal_count = 1;
330 size_t connected_count = m_item->ConnectedItems().size();
331
332 // a via can be removed if connected to only one other item.
333 if( Parent()->Type() == PCB_VIA_T )
334 return connected_count < 2;
335
336 if( m_item->AnchorCount() == 1 )
337 return connected_count < minimal_count;
338
339 if( Parent()->Type() == PCB_TRACE_T || Parent()->Type() == PCB_ARC_T )
340 {
341 accuracy = KiROUND( static_cast<const PCB_TRACK*>( Parent() )->GetWidth() / 2 );
342 }
343 else if( Parent()->Type() == PCB_SHAPE_T )
344 {
345 auto shape = static_cast<const PCB_SHAPE*>( Parent() );
346
347 if( !shape->IsFilled() )
348 accuracy = KiROUND( shape->GetWidth() / 2 );
349 }
350
351 // Items with multiple anchors have usually items connected to each anchor.
352 // We want only the item count of this anchor point
353 connected_count = 0;
354
355 for( CN_ITEM* item : m_item->ConnectedItems() )
356 {
357 if( item->Parent()->Type() == PCB_ZONE_T )
358 {
359 ZONE* zone = static_cast<ZONE*>( item->Parent() );
360
361 if( zone->HitTestFilledArea( ToLAYER_ID( item->Layer() ), Pos(), accuracy ) )
362 connected_count++;
363 }
364 else if( item->Parent()->HitTest( Pos(), accuracy ) )
365 {
366 connected_count++;
367 }
368 }
369
370 return connected_count < minimal_count;
371}
372
373
375{
376 if( !m_cluster )
377 return 0;
378
379 int connected_count = 0;
380
381 for( CN_ITEM* item : m_item->ConnectedItems() )
382 {
383 if( item->Parent()->Type() == PCB_ZONE_T )
384 {
385 ZONE* zone = static_cast<ZONE*>( item->Parent() );
386
387 if( zone->HitTestFilledArea( ToLAYER_ID( item->Layer() ), Pos() ) )
388 connected_count++;
389 }
390 else if( item->Parent()->HitTest( Pos() ) )
391 {
392 connected_count++;
393 }
394 }
395
396 return connected_count;
397}
398
399
401{
402 m_items.reserve( 64 );
403 m_originPad = nullptr;
404 m_originNet = -1;
405 m_conflicting = false;
406}
407
408
410{
411}
412
413
415{
416 if( !m_originPad || !m_originPad->Valid() )
417 return "<none>";
418 else
419 return m_originPad->Parent()->GetNetname();
420}
421
422
423bool CN_CLUSTER::Contains( const CN_ITEM* aItem )
424{
425 return alg::contains( m_items, aItem );
426}
427
428
430{
431 return std::find_if( m_items.begin(), m_items.end(),
432 [&aItem]( const CN_ITEM* item )
433 {
434 return item->Valid() && item->Parent() == aItem;
435 } ) != m_items.end();
436}
437
438
440{
441 for( CN_ITEM* item : m_items )
442 {
443 wxLogTrace( wxT( "CN" ), wxT( " - item : %p bitem : %p type : %d inet %s\n" ),
444 item,
445 item->Parent(),
446 item->Parent()->Type(),
447 (const char*) item->Parent()->GetNetname().c_str() );
448 wxLogTrace( wxT( "CN" ), wxT( "- item : %p bitem : %p type : %d inet %s\n" ),
449 item,
450 item->Parent(),
451 item->Parent()->Type(),
452 (const char*) item->Parent()->GetNetname().c_str() );
453 item->Dump();
454 }
455}
456
457
459{
460 m_items.push_back( item );
461
462 int netCode = item->Net();
463
464 if( netCode <= 0 )
465 return;
466
467 if( m_originNet <= 0 )
468 {
469 m_originNet = netCode;
471 }
472
473 if( item->Parent()->Type() == PCB_PAD_T && !static_cast<PAD*>( item->Parent() )->IsFreePad() )
474 {
475 int rank;
476 auto it = m_netRanks.find( netCode );
477
478 if( it == m_netRanks.end() )
479 {
480 m_netRanks[netCode] = 1;
481 rank = 1;
482 }
483 else
484 {
485 it->second++;
486 rank = it->second;
487 }
488
489 if( !m_originPad || rank > m_netRanks[m_originNet] )
490 {
491 m_originPad = item;
492 m_originNet = netCode;
493 }
494
495 if( m_originPad && item->Net() != m_originNet )
496 m_conflicting = true;
497 }
498}
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:226
CN_ITEM * m_item
Pad or track/arc/via owning the anchor.
bool Valid() const
int ConnectedItemsCount() const
std::shared_ptr< CN_CLUSTER > m_cluster
Cluster to which the anchor belongs.
const VECTOR2I & Pos() const
bool Dirty() const
BOARD_CONNECTED_ITEM * Parent() const
bool IsDangling() const
The anchor point is dangling if the parent is a track and this anchor point is not connected to anoth...
std::vector< CN_ITEM * > m_items
bool Contains(const CN_ITEM *aItem)
void Add(CN_ITEM *item)
CN_ITEM * m_originPad
wxString OriginNetName() const
std::unordered_map< int, int > m_netRanks
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
void SetLayers(const LAYER_RANGE &aLayers)
Set the layers spanned by the item to aLayers.
virtual int AnchorCount() const
void RemoveInvalidRefs()
std::vector< CN_ITEM * > m_connected
list of physically touching items
const std::vector< CN_ITEM * > & ConnectedItems() const
int Net() const
BOARD_CONNECTED_ITEM * m_parent
bool Valid() const
std::shared_ptr< CN_ANCHOR > AddAnchor(const VECTOR2I &aPos)
virtual const VECTOR2I GetAnchor(int n) const
void SetLayer(int aLayer)
Set the layers spanned by the item to a single layer aLayer.
std::vector< std::shared_ptr< CN_ANCHOR > > m_anchors
bool m_valid
used to identify garbage items (we use lazy removal)
bool Dirty() const
BOARD_CONNECTED_ITEM * Parent() const
CN_ITEM * Add(PAD *pad)
void SetDirty(bool aDirty=true)
std::vector< CN_ITEM * > m_items
void addItemtoTree(CN_ITEM *item)
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
virtual int AnchorCount() const override
virtual const VECTOR2I GetAnchor(int n) const override
PCB_LAYER_ID m_layer
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:97
virtual wxString GetClass() const =0
Return the class name.
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
LSET is a set of PCB_LAYER_IDs.
Definition: layer_ids.h:573
Definition: pad.h:59
bool IsFreePad() const
Definition: pad.cpp:183
std::vector< VECTOR2I > GetConnectionPoints() const
Definition: pcb_shape.cpp:106
PCB_LAYER_ID GetLayer() const override
Return the primary layer this item is on.
Definition: pcb_shape.h:67
const VECTOR2I & GetStart() const
Definition: pcb_track.h:113
const VECTOR2I & GetEnd() const
Definition: pcb_track.h:110
Handle a list of polygons defining a copper zone.
Definition: zone.h:72
const std::shared_ptr< SHAPE_POLY_SET > & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition: zone.h:615
bool HitTestFilledArea(PCB_LAYER_ID aLayer, const VECTOR2I &aRefPos, int aAccuracy=0) const
Test if the given VECTOR2I is within the bounds of a filled area of this zone.
Definition: zone.cpp:495
#define MAX_CU_LAYERS
Definition: layer_ids.h:141
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:60
@ B_Cu
Definition: layer_ids.h:96
@ F_Cu
Definition: layer_ids.h:65
PCB_LAYER_ID ToLAYER_ID(int aLayer)
Definition: lset.cpp:1022
This file contains miscellaneous commonly used macros and functions.
#define UNIMPLEMENTED_FOR(type)
Definition: macros.h:96
bool contains(const _Container &__container, _Value __value)
Returns true if the container contains the given value.
Definition: kicad_algo.h:100
@ PCB_SHAPE_T
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:88
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:97
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition: typeinfo.h:107
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87
@ PCB_ARC_T
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:98
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:96
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:85
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588