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 : m_items )
292 item->RemoveInvalidRefs();
293
294 for( CN_ITEM* item : aGarbage )
295 m_index.Remove( item );
296
297 m_hasInvalid = false;
298}
299
300
302{
303 assert( m_item->Valid() );
304 return m_item->Parent();
305}
306
307
309{
310 if( !m_item )
311 return false;
312
313 return m_item->Valid();
314}
315
316
318{
319 return !Valid() || m_item->Dirty();
320}
321
322
324{
325 int accuracy = 0;
326
327 if( !m_cluster )
328 return true;
329
330 // the minimal number of items connected to item_ref
331 // at this anchor point to decide the anchor is *not* dangling
332 size_t minimal_count = 1;
333 size_t connected_count = m_item->ConnectedItems().size();
334
335 // a via can be removed if connected to only one other item.
336 if( Parent()->Type() == PCB_VIA_T )
337 return connected_count < 2;
338
339 if( m_item->AnchorCount() == 1 )
340 return connected_count < minimal_count;
341
342 if( Parent()->Type() == PCB_TRACE_T || Parent()->Type() == PCB_ARC_T )
343 {
344 accuracy = KiROUND( static_cast<const PCB_TRACK*>( Parent() )->GetWidth() / 2 );
345 }
346 else if( Parent()->Type() == PCB_SHAPE_T )
347 {
348 auto shape = static_cast<const PCB_SHAPE*>( Parent() );
349
350 if( !shape->IsFilled() )
351 accuracy = KiROUND( shape->GetWidth() / 2 );
352 }
353
354 // Items with multiple anchors have usually items connected to each anchor.
355 // We want only the item count of this anchor point
356 connected_count = 0;
357
358 for( CN_ITEM* item : m_item->ConnectedItems() )
359 {
360 if( item->Parent()->Type() == PCB_ZONE_T )
361 {
362 ZONE* zone = static_cast<ZONE*>( item->Parent() );
363
364 if( zone->HitTestFilledArea( ToLAYER_ID( item->Layer() ), Pos(), accuracy ) )
365 connected_count++;
366 }
367 else if( item->Parent()->HitTest( Pos(), accuracy ) )
368 {
369 connected_count++;
370 }
371 }
372
373 return connected_count < minimal_count;
374}
375
376
378{
379 if( !m_cluster )
380 return 0;
381
382 int connected_count = 0;
383
384 for( CN_ITEM* item : m_item->ConnectedItems() )
385 {
386 if( item->Parent()->Type() == PCB_ZONE_T )
387 {
388 ZONE* zone = static_cast<ZONE*>( item->Parent() );
389
390 if( zone->HitTestFilledArea( ToLAYER_ID( item->Layer() ), Pos() ) )
391 connected_count++;
392 }
393 else if( item->Parent()->HitTest( Pos() ) )
394 {
395 connected_count++;
396 }
397 }
398
399 return connected_count;
400}
401
402
404{
405 m_items.reserve( 64 );
406 m_originPad = nullptr;
407 m_originNet = -1;
408 m_conflicting = false;
409}
410
411
413{
414}
415
416
418{
419 if( !m_originPad || !m_originPad->Valid() )
420 return "<none>";
421 else
422 return m_originPad->Parent()->GetNetname();
423}
424
425
426bool CN_CLUSTER::Contains( const CN_ITEM* aItem )
427{
428 return alg::contains( m_items, aItem );
429}
430
431
433{
434 return std::find_if( m_items.begin(), m_items.end(),
435 [&aItem]( const CN_ITEM* item )
436 {
437 return item->Valid() && item->Parent() == aItem;
438 } ) != m_items.end();
439}
440
441
443{
444 for( CN_ITEM* item : m_items )
445 {
446 wxLogTrace( wxT( "CN" ), wxT( " - item : %p bitem : %p type : %d inet %s\n" ),
447 item,
448 item->Parent(),
449 item->Parent()->Type(),
450 (const char*) item->Parent()->GetNetname().c_str() );
451 wxLogTrace( wxT( "CN" ), wxT( "- item : %p bitem : %p type : %d inet %s\n" ),
452 item,
453 item->Parent(),
454 item->Parent()->Type(),
455 (const char*) item->Parent()->GetNetname().c_str() );
456 item->Dump();
457 }
458}
459
460
462{
463 m_items.push_back( item );
464
465 int netCode = item->Net();
466
467 if( netCode <= 0 )
468 return;
469
470 if( m_originNet <= 0 )
471 {
472 m_originNet = netCode;
474 }
475
476 if( item->Parent()->Type() == PCB_PAD_T && !static_cast<PAD*>( item->Parent() )->IsFreePad() )
477 {
478 int rank;
479 auto it = m_netRanks.find( netCode );
480
481 if( it == m_netRanks.end() )
482 {
483 m_netRanks[netCode] = 1;
484 rank = 1;
485 }
486 else
487 {
488 it->second++;
489 rank = it->second;
490 }
491
492 if( !m_originPad || rank > m_netRanks[m_originNet] )
493 {
494 m_originPad = item;
495 m_originNet = netCode;
496 }
497
498 if( m_originPad && item->Net() != m_originNet )
499 m_conflicting = true;
500 }
501}
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:204
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:552
Definition: pad.h:58
bool IsFreePad() const
Definition: pad.cpp:187
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:513
#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:932
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:99
@ 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:94
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition: typeinfo.h:104
@ 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:95
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:93
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