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 default:
46 return 1;
47 }
48}
49
50
51const VECTOR2I CN_ITEM::GetAnchor( int n ) const
52{
53 if( !m_valid )
54 return VECTOR2I();
55
56 switch( m_parent->Type() )
57 {
58 case PCB_PAD_T:
59 return static_cast<PAD*>( m_parent )->GetPosition();
60
61 case PCB_TRACE_T:
62 case PCB_ARC_T:
63 if( n == 0 )
64 return static_cast<const PCB_TRACK*>( m_parent )->GetStart();
65 else
66 return static_cast<const PCB_TRACK*>( m_parent )->GetEnd();
67
68 case PCB_VIA_T:
69 return static_cast<const PCB_VIA*>( m_parent )->GetStart();
70
71 default:
73 return VECTOR2I();
74 }
75}
76
77
79{
80 wxLogDebug(" valid: %d, connected: \n", !!Valid());
81
82 for( CN_ITEM* i : m_connected )
83 {
84 PCB_TRACK* t = static_cast<PCB_TRACK*>( i->Parent() );
85 wxLogDebug( wxT( " - %p %d\n" ), t, t->Type() );
86 }
87}
88
89
91{
92 if( !Valid() )
93 return 0;
94
95 const ZONE* zone = static_cast<const ZONE*>( Parent() );
96
97 return zone->GetFilledPolysList( m_layer )->COutline( m_subpolyIndex ).PointCount() ? 1 : 0;
98}
99
100
102{
103 if( !Valid() )
104 return VECTOR2I();
105
106 const ZONE* zone = static_cast<const ZONE*>( Parent() );
107
108 return zone->GetFilledPolysList( m_layer )->COutline( m_subpolyIndex ).CPoint( 0 );
109}
110
111
113{
114 int count = 0;
115
116 for( CN_ITEM* item : ConnectedItems() )
117 {
118 if( item->Valid() )
119 count++;
120
121 if( count > 1 )
122 break;
123 }
124
125 return count == 1;
126}
127
128
130{
131 for( auto it = m_connected.begin(); it != m_connected.end(); /* increment in loop */ )
132 {
133 if( !(*it)->Valid() )
134 it = m_connected.erase( it );
135 else
136 ++it;
137 }
138}
139
140
142 {
143 if( !pad->IsOnCopperLayer() )
144 return nullptr;
145
146 auto item = new CN_ITEM( pad, false, 1 );
147 item->AddAnchor( pad->ShapePos() );
148 item->SetLayers( LAYER_RANGE( F_Cu, B_Cu ) );
149
150 switch( pad->GetAttribute() )
151 {
152 case PAD_ATTRIB::SMD:
153 case PAD_ATTRIB::NPTH:
154 case PAD_ATTRIB::CONN:
155 {
156 LSET lmsk = pad->GetLayerSet();
157
158 for( int i = 0; i <= MAX_CU_LAYERS; i++ )
159 {
160 if( lmsk[i] )
161 {
162 item->SetLayer( i );
163 break;
164 }
165 }
166 break;
167 }
168 default:
169 break;
170 }
171
172 addItemtoTree( item );
173 m_items.push_back( item );
174 SetDirty();
175 return item;
176}
177
178
180{
181 CN_ITEM* item = new CN_ITEM( track, true );
182 m_items.push_back( item );
183 item->AddAnchor( track->GetStart() );
184 item->AddAnchor( track->GetEnd() );
185 item->SetLayer( track->GetLayer() );
186 addItemtoTree( item );
187 SetDirty();
188 return item;
189}
190
191
193{
194 CN_ITEM* item = new CN_ITEM( aArc, true );
195 m_items.push_back( item );
196 item->AddAnchor( aArc->GetStart() );
197 item->AddAnchor( aArc->GetEnd() );
198 item->SetLayer( aArc->GetLayer() );
199 addItemtoTree( item );
200 SetDirty();
201 return item;
202}
203
204
206{
207 CN_ITEM* item = new CN_ITEM( via, !via->GetIsFree(), 1 );
208
209 m_items.push_back( item );
210 item->AddAnchor( via->GetStart() );
211
212 item->SetLayers( LAYER_RANGE( via->TopLayer(), via->BottomLayer() ) );
213 addItemtoTree( item );
214 SetDirty();
215 return item;
216}
217
218
219const std::vector<CN_ITEM*> CN_LIST::Add( ZONE* zone, PCB_LAYER_ID aLayer )
220{
221 const std::shared_ptr<SHAPE_POLY_SET>& polys = zone->GetFilledPolysList( aLayer );
222
223 std::vector<CN_ITEM*> rv;
224
225 for( int j = 0; j < polys->OutlineCount(); j++ )
226 {
227 CN_ZONE_LAYER* zitem = new CN_ZONE_LAYER( zone, aLayer, j );
228
229 zitem->BuildRTree();
230
231 for( const VECTOR2I& pt : zone->GetFilledPolysList( aLayer )->COutline( j ).CPoints() )
232 zitem->AddAnchor( pt );
233
234 rv.push_back( Add( zitem ) );
235 }
236
237 return rv;
238}
239
240
242{
243 m_items.push_back( zitem );
244 addItemtoTree( zitem );
245 SetDirty();
246 return zitem;
247}
248
249
250void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
251{
252 if( !m_hasInvalid )
253 return;
254
255 auto lastItem = std::remove_if( m_items.begin(), m_items.end(),
256 [&aGarbage]( CN_ITEM* item )
257 {
258 if( !item->Valid() )
259 {
260 aGarbage.push_back ( item );
261 return true;
262 }
263
264 return false;
265 } );
266
267 m_items.resize( lastItem - m_items.begin() );
268
269 for( CN_ITEM* item : m_items )
270 item->RemoveInvalidRefs();
271
272 for( CN_ITEM* item : aGarbage )
273 m_index.Remove( item );
274
275 m_hasInvalid = false;
276}
277
278
280{
281 assert( m_item->Valid() );
282 return m_item->Parent();
283}
284
285
287{
288 if( !m_item )
289 return false;
290
291 return m_item->Valid();
292}
293
294
296{
297 return !Valid() || m_item->Dirty();
298}
299
300
302{
303 int accuracy = 0;
304
305 if( !m_cluster )
306 return true;
307
308 // the minimal number of items connected to item_ref
309 // at this anchor point to decide the anchor is *not* dangling
310 size_t minimal_count = 1;
311 size_t connected_count = m_item->ConnectedItems().size();
312
313 // a via can be removed if connected to only one other item.
314 if( Parent()->Type() == PCB_VIA_T )
315 return connected_count < 2;
316
317 if( m_item->AnchorCount() == 1 )
318 return connected_count < minimal_count;
319
320 if( Parent()->Type() == PCB_TRACE_T || Parent()->Type() == PCB_ARC_T )
321 accuracy = KiROUND( static_cast<const PCB_TRACK*>( Parent() )->GetWidth() / 2 );
322
323 // Items with multiple anchors have usually items connected to each anchor.
324 // We want only the item count of this anchor point
325 connected_count = 0;
326
327 for( CN_ITEM* item : m_item->ConnectedItems() )
328 {
329 if( item->Parent()->Type() == PCB_ZONE_T )
330 {
331 ZONE* zone = static_cast<ZONE*>( item->Parent() );
332
333 if( zone->HitTestFilledArea( ToLAYER_ID( item->Layer() ), Pos(), accuracy ) )
334 connected_count++;
335 }
336 else if( item->Parent()->HitTest( Pos(), accuracy ) )
337 {
338 connected_count++;
339 }
340 }
341
342 return connected_count < minimal_count;
343}
344
345
347{
348 if( !m_cluster )
349 return 0;
350
351 int connected_count = 0;
352
353 for( CN_ITEM* item : m_item->ConnectedItems() )
354 {
355 if( item->Parent()->Type() == PCB_ZONE_T )
356 {
357 ZONE* zone = static_cast<ZONE*>( item->Parent() );
358
359 if( zone->HitTestFilledArea( ToLAYER_ID( item->Layer() ), Pos() ) )
360 connected_count++;
361 }
362 else if( item->Parent()->HitTest( Pos() ) )
363 {
364 connected_count++;
365 }
366 }
367
368 return connected_count;
369}
370
371
373{
374 m_items.reserve( 64 );
375 m_originPad = nullptr;
376 m_originNet = -1;
377 m_conflicting = false;
378}
379
380
382{
383}
384
385
387{
388 if( !m_originPad || !m_originPad->Valid() )
389 return "<none>";
390 else
391 return m_originPad->Parent()->GetNetname();
392}
393
394
395bool CN_CLUSTER::Contains( const CN_ITEM* aItem )
396{
397 return alg::contains( m_items, aItem );
398}
399
400
402{
403 return std::find_if( m_items.begin(), m_items.end(),
404 [&aItem]( const CN_ITEM* item )
405 {
406 return item->Valid() && item->Parent() == aItem;
407 } ) != m_items.end();
408}
409
410
412{
413 for( CN_ITEM* item : m_items )
414 {
415 wxLogTrace( wxT( "CN" ), wxT( " - item : %p bitem : %p type : %d inet %s\n" ),
416 item,
417 item->Parent(),
418 item->Parent()->Type(),
419 (const char*) item->Parent()->GetNetname().c_str() );
420 wxLogTrace( wxT( "CN" ), wxT( "- item : %p bitem : %p type : %d inet %s\n" ),
421 item,
422 item->Parent(),
423 item->Parent()->Type(),
424 (const char*) item->Parent()->GetNetname().c_str() );
425 item->Dump();
426 }
427}
428
429
431{
432 m_items.push_back( item );
433
434 int netCode = item->Net();
435
436 if( netCode <= 0 )
437 return;
438
439 if( m_originNet <= 0 )
440 {
441 m_originNet = netCode;
443 }
444
445 if( item->Parent()->Type() == PCB_PAD_T && !static_cast<PAD*>( item->Parent() )->IsFreePad() )
446 {
447 int rank;
448 auto it = m_netRanks.find( netCode );
449
450 if( it == m_netRanks.end() )
451 {
452 m_netRanks[netCode] = 1;
453 rank = 1;
454 }
455 else
456 {
457 it->second++;
458 rank = it->second;
459 }
460
461 if( !m_originPad || rank > m_netRanks[m_originNet] )
462 {
463 m_originPad = item;
464 m_originNet = netCode;
465 }
466
467 if( m_originPad && item->Net() != m_originNet )
468 m_conflicting = true;
469 }
470}
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:196
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.
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:536
Definition: pad.h:59
bool IsFreePad() const
Definition: pad.cpp:188
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:510
#define MAX_CU_LAYERS
Definition: layer_ids.h:140
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:59
@ B_Cu
Definition: layer_ids.h:95
@ F_Cu
Definition: layer_ids.h:64
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:120
bool contains(const _Container &__container, _Value __value)
Returns true if the container contains the given value.
Definition: kicad_algo.h:99
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:93
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition: typeinfo.h:103
@ 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:94
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:92
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