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-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 for( auto it = m_connected.begin(); it != m_connected.end(); /* increment in loop */ )
115 {
116 if( !(*it)->Valid() )
117 it = m_connected.erase( it );
118 else
119 ++it;
120 }
121}
122
123
125 {
126 if( !pad->IsOnCopperLayer() )
127 return nullptr;
128
129 auto item = new CN_ITEM( pad, false, 1 );
130 item->AddAnchor( pad->ShapePos() );
131 item->SetLayers( LAYER_RANGE( F_Cu, B_Cu ) );
132
133 switch( pad->GetAttribute() )
134 {
135 case PAD_ATTRIB::SMD:
136 case PAD_ATTRIB::NPTH:
137 case PAD_ATTRIB::CONN:
138 {
139 LSET lmsk = pad->GetLayerSet();
140
141 for( int i = 0; i <= MAX_CU_LAYERS; i++ )
142 {
143 if( lmsk[i] )
144 {
145 item->SetLayer( i );
146 break;
147 }
148 }
149 break;
150 }
151 default:
152 break;
153 }
154
155 addItemtoTree( item );
156 m_items.push_back( item );
157 SetDirty();
158 return item;
159}
160
161
163{
164 CN_ITEM* item = new CN_ITEM( track, true );
165 m_items.push_back( item );
166 item->AddAnchor( track->GetStart() );
167 item->AddAnchor( track->GetEnd() );
168 item->SetLayer( track->GetLayer() );
169 addItemtoTree( item );
170 SetDirty();
171 return item;
172}
173
174
176{
177 CN_ITEM* item = new CN_ITEM( aArc, true );
178 m_items.push_back( item );
179 item->AddAnchor( aArc->GetStart() );
180 item->AddAnchor( aArc->GetEnd() );
181 item->SetLayer( aArc->GetLayer() );
182 addItemtoTree( item );
183 SetDirty();
184 return item;
185}
186
187
189{
190 CN_ITEM* item = new CN_ITEM( via, !via->GetIsFree(), 1 );
191
192 m_items.push_back( item );
193 item->AddAnchor( via->GetStart() );
194
195 item->SetLayers( LAYER_RANGE( via->TopLayer(), via->BottomLayer() ) );
196 addItemtoTree( item );
197 SetDirty();
198 return item;
199}
200
201
202const std::vector<CN_ITEM*> CN_LIST::Add( ZONE* zone, PCB_LAYER_ID aLayer )
203{
204 const std::shared_ptr<SHAPE_POLY_SET>& polys = zone->GetFilledPolysList( aLayer );
205
206 std::vector<CN_ITEM*> rv;
207
208 for( int j = 0; j < polys->OutlineCount(); j++ )
209 {
210 CN_ZONE_LAYER* zitem = new CN_ZONE_LAYER( zone, aLayer, j );
211
212 zitem->BuildRTree();
213
214 for( VECTOR2I pt : zone->GetFilledPolysList( aLayer )->COutline( j ).CPoints() )
215 zitem->AddAnchor( pt );
216
217 rv.push_back( Add( zitem ) );
218 }
219
220 return rv;
221}
222
223
225{
226 m_items.push_back( zitem );
227 addItemtoTree( zitem );
228 SetDirty();
229 return zitem;
230}
231
232
233void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
234{
235 if( !m_hasInvalid )
236 return;
237
238 auto lastItem = std::remove_if( m_items.begin(), m_items.end(),
239 [&aGarbage]( CN_ITEM* item )
240 {
241 if( !item->Valid() )
242 {
243 aGarbage.push_back ( item );
244 return true;
245 }
246
247 return false;
248 } );
249
250 m_items.resize( lastItem - m_items.begin() );
251
252 for( CN_ITEM* item : m_items )
253 item->RemoveInvalidRefs();
254
255 for( CN_ITEM* item : aGarbage )
256 m_index.Remove( item );
257
258 m_hasInvalid = false;
259}
260
261
263{
264 assert( m_item->Valid() );
265 return m_item->Parent();
266}
267
268
270{
271 if( !m_item )
272 return false;
273
274 return m_item->Valid();
275}
276
277
279{
280 int accuracy = 0;
281
282 if( !m_cluster )
283 return true;
284
285 // the minimal number of items connected to item_ref
286 // at this anchor point to decide the anchor is *not* dangling
287 size_t minimal_count = 1;
288 size_t connected_count = m_item->ConnectedItems().size();
289
290 // a via can be removed if connected to only one other item.
291 if( Parent()->Type() == PCB_VIA_T )
292 return connected_count < 2;
293
294 if( m_item->AnchorCount() == 1 )
295 return connected_count < minimal_count;
296
297 if( Parent()->Type() == PCB_TRACE_T || Parent()->Type() == PCB_ARC_T )
298 accuracy = KiROUND( static_cast<const PCB_TRACK*>( Parent() )->GetWidth() / 2 );
299
300 // Items with multiple anchors have usually items connected to each anchor.
301 // We want only the item count of this anchor point
302 connected_count = 0;
303
304 for( CN_ITEM* item : m_item->ConnectedItems() )
305 {
306 if( item->Parent()->Type() == PCB_ZONE_T )
307 {
308 ZONE* zone = static_cast<ZONE*>( item->Parent() );
309
310 if( zone->HitTestFilledArea( ToLAYER_ID( item->Layer() ), Pos(), accuracy ) )
311 connected_count++;
312 }
313 else if( item->Parent()->HitTest( Pos(), accuracy ) )
314 {
315 connected_count++;
316 }
317 }
318
319 return connected_count < minimal_count;
320}
321
322
324{
325 if( !m_cluster )
326 return 0;
327
328 int connected_count = 0;
329
330 for( CN_ITEM* item : m_item->ConnectedItems() )
331 {
332 if( item->Parent()->Type() == PCB_ZONE_T )
333 {
334 ZONE* zone = static_cast<ZONE*>( item->Parent() );
335
336 if( zone->HitTestFilledArea( ToLAYER_ID( item->Layer() ), Pos() ) )
337 connected_count++;
338 }
339 else if( item->Parent()->HitTest( Pos() ) )
340 {
341 connected_count++;
342 }
343 }
344
345 return connected_count;
346}
347
348
350{
351 m_items.reserve( 64 );
352 m_originPad = nullptr;
353 m_originNet = -1;
354 m_conflicting = false;
355}
356
357
359{
360}
361
362
364{
365 if( !m_originPad || !m_originPad->Valid() )
366 return "<none>";
367 else
368 return m_originPad->Parent()->GetNetname();
369}
370
371
372bool CN_CLUSTER::Contains( const CN_ITEM* aItem )
373{
374 return alg::contains( m_items, aItem );
375}
376
377
379{
380 return std::find_if( m_items.begin(), m_items.end(),
381 [&aItem]( const CN_ITEM* item )
382 {
383 return item->Valid() && item->Parent() == aItem;
384 } ) != m_items.end();
385}
386
387
389{
390 for( CN_ITEM* item : m_items )
391 {
392 wxLogTrace( wxT( "CN" ), wxT( " - item : %p bitem : %p type : %d inet %s\n" ),
393 item,
394 item->Parent(),
395 item->Parent()->Type(),
396 (const char*) item->Parent()->GetNetname().c_str() );
397 wxLogTrace( wxT( "CN" ), wxT( "- item : %p bitem : %p type : %d inet %s\n" ),
398 item,
399 item->Parent(),
400 item->Parent()->Type(),
401 (const char*) item->Parent()->GetNetname().c_str() );
402 item->Dump();
403 }
404}
405
406
408{
409 m_items.push_back( item );
410
411 int netCode = item->Net();
412
413 if( netCode <= 0 )
414 return;
415
416 if( m_originNet <= 0 )
417 m_originNet = netCode;
418
419 if( item->Parent()->Type() == PCB_PAD_T )
420 {
421 if( m_netRanks.count( netCode ) )
422 {
423 m_netRanks[netCode]++;
424
425 if( m_netRanks.count( m_originNet ) && m_netRanks[netCode] > m_netRanks[m_originNet] )
426 {
427 m_originPad = item;
428 m_originNet = netCode;
429 }
430 }
431 else
432 {
433 m_netRanks[netCode] = 1;
434
435 if( !m_originPad )
436 {
437 m_originPad = item;
438 m_originNet = netCode;
439 }
440 }
441
442 if( m_originPad && item->Net() != m_originNet )
443 m_conflicting = true;
444 }
445}
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:169
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
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
allow parallel connection threads
BOARD_CONNECTED_ITEM * m_parent
bool Valid() const
virtual const VECTOR2I GetAnchor(int n) const
void AddAnchor(const VECTOR2I &aPos)
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)
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:111
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:530
Definition: pad.h:58
const VECTOR2I & GetStart() const
Definition: pcb_track.h:111
const VECTOR2I & GetEnd() const
Definition: pcb_track.h:108
Handle a list of polygons defining a copper zone.
Definition: zone.h:57
const std::shared_ptr< SHAPE_POLY_SET > & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition: zone.h:596
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:437
#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:926
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
@ NPTH
like PAD_PTH, but not plated
@ SMD
Smd pad, appears on the solder paste layer (default)
@ CONN
Like smd, does not appear on the solder paste layer (default)
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:102
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition: typeinfo.h:112
@ 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:103
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:101
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:80
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618