KiCad PCB EDA Suite
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
connectivity_data.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KICAD, a free EDA CAD application.
3 *
4 * Copyright (C) 2017 CERN
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7 *
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version 2
11 * of the License, or (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, you may find one here:
20 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21 * or you may search the http://www.gnu.org website for the version 2 license,
22 * or you may write to the Free Software Foundation, Inc.,
23 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24 */
25
26#ifdef PROFILE
27#include <core/profile.h>
28#endif
29
30#include <algorithm>
31#include <future>
32#include <initializer_list>
33
42#include <progress_reporter.h>
43#include <thread_pool.h>
44#include <trigo.h>
45#include <drc/drc_rtree.h>
46
48 m_skipRatsnestUpdate( false )
49{
50 m_connAlgo.reset( new CN_CONNECTIVITY_ALGO( this ) );
51 m_progressReporter = nullptr;
52 m_fromToCache.reset( new FROM_TO_CACHE );
53}
54
55
56CONNECTIVITY_DATA::CONNECTIVITY_DATA( std::shared_ptr<CONNECTIVITY_DATA> aGlobalConnectivity,
57 const std::vector<BOARD_ITEM*>& aLocalItems,
58 bool aSkipRatsnestUpdate ) :
59 m_skipRatsnestUpdate( aSkipRatsnestUpdate )
60{
61 Build( aGlobalConnectivity, aLocalItems );
62 m_progressReporter = nullptr;
63 m_fromToCache.reset( new FROM_TO_CACHE );
64}
65
66
68{
69 for( RN_NET* net : m_nets )
70 delete net;
71
72 m_nets.clear();
73}
74
75
77{
78 m_connAlgo->Add( aItem );
79 return true;
80}
81
82
84{
85 m_connAlgo->Remove( aItem );
86 return true;
87}
88
89
91{
92 m_connAlgo->Remove( aItem );
93 m_connAlgo->Add( aItem );
94 return true;
95}
96
97
99{
100 aBoard->CacheTriangulation( aReporter );
101
102 std::unique_lock<KISPINLOCK> lock( m_lock, std::try_to_lock );
103
104 if( !lock )
105 return false;
106
107 if( aReporter )
108 {
109 aReporter->Report( _( "Updating nets..." ) );
110 aReporter->KeepRefreshing( false );
111 }
112
113 for( auto net : m_nets )
114 if ( net )
115 delete net;
116
117 m_nets.clear();
118
119 m_connAlgo.reset( new CN_CONNECTIVITY_ALGO( this ) );
120 m_connAlgo->Build( aBoard, aReporter );
121
123
124 RefreshNetcodeMap( aBoard );
125
126 if( aReporter )
127 {
128 aReporter->SetCurrentProgress( 0.75 );
129 aReporter->KeepRefreshing( false );
130 }
131
133
134 if( aReporter )
135 {
136 aReporter->SetCurrentProgress( 1.0 );
137 aReporter->KeepRefreshing( false );
138 }
139
140 return true;
141}
142
143
145{
146 m_netcodeMap.clear();
147
148 for( NETINFO_ITEM* net : aBoard->GetNetInfo() )
149 m_netcodeMap[net->GetNetCode()] = net->GetNetname();
150}
151
152
153void CONNECTIVITY_DATA::Build( std::shared_ptr<CONNECTIVITY_DATA>& aGlobalConnectivity,
154 const std::vector<BOARD_ITEM*>& aLocalItems )
155{
156 std::unique_lock<KISPINLOCK> lock( m_lock, std::try_to_lock );
157
158 if( !lock )
159 return;
160
161 m_connAlgo.reset( new CN_CONNECTIVITY_ALGO( this ) );
162 m_connAlgo->LocalBuild( aGlobalConnectivity, aLocalItems );
163
165}
166
167
169{
170 m_connAlgo->ForEachAnchor( [&aDelta]( CN_ANCHOR& anchor )
171 {
172 anchor.Move( aDelta );
173 } );
174}
175
176
178{
179#ifdef PROFILE
180 PROF_TIMER rnUpdate( "update-ratsnest" );
181#endif
182
183 std::vector<RN_NET*> dirty_nets;
184
185 // Start with net 1 as net 0 is reserved for not-connected
186 // Nets without nodes are also ignored
187 std::copy_if( m_nets.begin() + 1, m_nets.end(), std::back_inserter( dirty_nets ),
188 [] ( RN_NET* aNet )
189 {
190 return aNet->IsDirty() && aNet->GetNodeCount() > 0;
191 } );
192
194
195 tp.push_loop( dirty_nets.size(),
196 [&]( const int a, const int b )
197 {
198 for( int ii = a; ii < b; ++ii )
199 dirty_nets[ii]->UpdateNet();
200 } );
201 tp.wait_for_tasks();
202
203 tp.push_loop( dirty_nets.size(),
204 [&]( const int a, const int b )
205 {
206 for( int ii = a; ii < b; ++ii )
207 dirty_nets[ii]->OptimizeRNEdges();
208 } );
209 tp.wait_for_tasks();
210
211#ifdef PROFILE
212 rnUpdate.Show();
213#endif
214}
215
216
217void CONNECTIVITY_DATA::addRatsnestCluster( const std::shared_ptr<CN_CLUSTER>& aCluster )
218{
219 RN_NET* rnNet = m_nets[ aCluster->OriginNet() ];
220
221 rnNet->AddCluster( aCluster );
222}
223
224
226{
227
228 // We can take over the lock here if called in the same thread
229 // This is to prevent redraw during a RecalculateRatsnets process
230 std::unique_lock<KISPINLOCK> lock( m_lock );
231
233
234}
235
237{
238 m_connAlgo->PropagateNets( aCommit );
239
240 int lastNet = m_connAlgo->NetCount();
241
242 if( lastNet >= (int) m_nets.size() )
243 {
244 unsigned int prevSize = m_nets.size();
245 m_nets.resize( lastNet + 1 );
246
247 for( unsigned int i = prevSize; i < m_nets.size(); i++ )
248 m_nets[i] = new RN_NET;
249 }
250 else
251 {
252 for( size_t ii = lastNet; ii < m_nets.size(); ++ii )
253 m_nets[ii]->Clear();
254 }
255
256 const std::vector<std::shared_ptr<CN_CLUSTER>>& clusters = m_connAlgo->GetClusters();
257
258 for( int net = 0; net < lastNet; net++ )
259 {
260 if( m_connAlgo->IsNetDirty( net ) )
261 {
262 m_nets[net]->Clear();
263 }
264 }
265
266 for( const std::shared_ptr<CN_CLUSTER>& c : clusters )
267 {
268 int net = c->OriginNet();
269
270 // Don't add intentionally-kept zone islands to the ratsnest
271 if( c->IsOrphaned() && c->Size() == 1 )
272 {
273 if( dynamic_cast<CN_ZONE_LAYER*>( *c->begin() ) )
274 continue;
275 }
276
277 if( m_connAlgo->IsNetDirty( net ) )
279 }
280
281 m_connAlgo->ClearDirtyFlags();
282
285}
286
287
288void CONNECTIVITY_DATA::BlockRatsnestItems( const std::vector<BOARD_ITEM*>& aItems )
289{
290 std::vector<BOARD_CONNECTED_ITEM*> citems;
291
292 for( BOARD_ITEM* item : aItems )
293 {
294 if( item->Type() == PCB_FOOTPRINT_T )
295 {
296 for( PAD* pad : static_cast<FOOTPRINT*>(item)->Pads() )
297 citems.push_back( pad );
298 }
299 else
300 {
301 if( BOARD_CONNECTED_ITEM* citem = dynamic_cast<BOARD_CONNECTED_ITEM*>( item ) )
302 citems.push_back( citem );
303 }
304 }
305
306 for( const BOARD_CONNECTED_ITEM* item : citems )
307 {
308 if ( m_connAlgo->ItemExists( item ) )
309 {
310 CN_CONNECTIVITY_ALGO::ITEM_MAP_ENTRY& entry = m_connAlgo->ItemEntry( item );
311
312 for( CN_ITEM* cnItem : entry.GetItems() )
313 {
314 for( const std::shared_ptr<CN_ANCHOR>& anchor : cnItem->Anchors() )
315 anchor->SetNoLine( true );
316 }
317 }
318 }
319}
320
321
323{
324 return m_connAlgo->NetCount();
325}
326
327
328void CONNECTIVITY_DATA::FillIsolatedIslandsMap( std::map<ZONE*, std::map<PCB_LAYER_ID, ISOLATED_ISLANDS>>& aMap,
329 bool aConnectivityAlreadyRebuilt )
330{
331 m_connAlgo->FillIsolatedIslandsMap( aMap, aConnectivityAlreadyRebuilt );
332}
333
334
335void CONNECTIVITY_DATA::ComputeLocalRatsnest( const std::vector<BOARD_ITEM*>& aItems,
336 const CONNECTIVITY_DATA* aDynamicData,
337 VECTOR2I aInternalOffset )
338{
339 if( !aDynamicData )
340 return;
341
342 m_dynamicRatsnest.clear();
343 std::mutex dynamic_ratsnest_mutex;
344
345 // This gets connections between the stationary board and the
346 // moving selection
347
348 auto update_lambda = [&]( int nc )
349 {
350 RN_NET* dynamicNet = aDynamicData->m_nets[nc];
351 RN_NET* staticNet = m_nets[nc];
352
356 if( dynamicNet->GetNodeCount() != 0
357 && dynamicNet->GetNodeCount() != staticNet->GetNodeCount() )
358 {
359 VECTOR2I pos1, pos2;
360
361 if( staticNet->NearestBicoloredPair( dynamicNet, pos1, pos2 ) )
362 {
364 l.a = pos1;
365 l.b = pos2;
366 l.netCode = nc;
367
368 std::lock_guard<std::mutex> lock( dynamic_ratsnest_mutex );
369 m_dynamicRatsnest.push_back( l );
370 }
371 }
372 };
373
375 size_t num_nets = std::min( m_nets.size(), aDynamicData->m_nets.size() );
376
377 tp.push_loop( 1, num_nets,
378 [&]( const int a, const int b)
379 {
380 for( int ii = a; ii < b; ++ii )
381 update_lambda( ii );
382 });
383 tp.wait_for_tasks();
384
385 // This gets the ratsnest for internal connections in the moving set
386 const std::vector<CN_EDGE>& edges = GetRatsnestForItems( aItems );
387
388 for( const CN_EDGE& edge : edges )
389 {
390 const std::shared_ptr<const CN_ANCHOR>& nodeA = edge.GetSourceNode();
391 const std::shared_ptr<const CN_ANCHOR>& nodeB = edge.GetTargetNode();
392
393 if( !nodeA || nodeA->Dirty() || !nodeB || nodeB->Dirty() )
394 continue;
395
397
398 // Use the parents' positions
399 l.a = nodeA->Parent()->GetPosition() + aInternalOffset;
400 l.b = nodeB->Parent()->GetPosition() + aInternalOffset;
401 l.netCode = 0;
402 m_dynamicRatsnest.push_back( l );
403 }
404}
405
406
408{
409 m_connAlgo->ForEachAnchor( []( CN_ANCHOR& anchor )
410 {
411 anchor.SetNoLine( false );
412 } );
414}
415
416
418{
419 m_dynamicRatsnest.clear();
420}
421
422
424{
425 m_connAlgo->PropagateNets( aCommit );
426}
427
428
430 const std::initializer_list<KICAD_T>& aTypes ) const
431{
432 CN_CONNECTIVITY_ALGO::ITEM_MAP_ENTRY &entry = m_connAlgo->ItemEntry( aItem );
433
434 auto matchType =
435 [&]( KICAD_T aItemType )
436 {
437 if( aTypes.size() == 0 )
438 return true;
439
440 return alg::contains( aTypes, aItemType);
441 };
442
443 for( CN_ITEM* citem : entry.GetItems() )
444 {
445 for( CN_ITEM* connected : citem->ConnectedItems() )
446 {
447 CN_ZONE_LAYER* zoneLayer = dynamic_cast<CN_ZONE_LAYER*>( connected );
448
449 // lyIdx is compatible with StartLayer() and EndLayer() notation in CN_ITEM
450 // items, where B_Cu is set to INT_MAX (std::numeric_limits<int>::max())
451 int lyIdx = aLayer;
452
453 if( aLayer == B_Cu )
454 lyIdx = std::numeric_limits<int>::max();
455
456 if( connected->Valid()
457 && connected->StartLayer() <= lyIdx && connected->EndLayer() >= lyIdx
458 && matchType( connected->Parent()->Type() )
459 && connected->Net() == aItem->GetNetCode() )
460 {
461 if( aItem->Type() == PCB_PAD_T && zoneLayer )
462 {
463 const PAD* pad = static_cast<const PAD*>( aItem );
464 ZONE* zone = static_cast<ZONE*>( zoneLayer->Parent() );
465 int islandIdx = zoneLayer->SubpolyIndex();
466
467 if( zone->IsFilled() )
468 {
469 PCB_LAYER_ID pcbLayer = ToLAYER_ID( aLayer );
470 const SHAPE_POLY_SET* zoneFill = zone->GetFill( pcbLayer );
471 const SHAPE_LINE_CHAIN& padHull =
472 pad->GetEffectivePolygon( pcbLayer, ERROR_INSIDE )->Outline( 0 );
473
474 for( const VECTOR2I& pt : zoneFill->COutline( islandIdx ).CPoints() )
475 {
476 // If the entire island is inside the pad's flashing then the pad
477 // won't actually connect to anything else, so only return true if
478 // part of the island is *outside* the pad's flashing.
479
480 if( !padHull.PointInside( pt ) )
481 return true;
482 }
483 }
484
485 continue;
486 }
487 else if( aItem->Type() == PCB_VIA_T && zoneLayer )
488 {
489 const PCB_VIA* via = static_cast<const PCB_VIA*>( aItem );
490 ZONE* zone = static_cast<ZONE*>( zoneLayer->Parent() );
491 int islandIdx = zoneLayer->SubpolyIndex();
492
493 if( zone->IsFilled() )
494 {
495 PCB_LAYER_ID lyr = ToLAYER_ID( aLayer );
496 const SHAPE_POLY_SET* zoneFill = zone->GetFill( lyr );
497 SHAPE_CIRCLE viaHull( via->GetCenter(), via->GetWidth( lyr ) / 2 );
498
499 for( const VECTOR2I& pt : zoneFill->COutline( islandIdx ).CPoints() )
500 {
501 // If the entire island is inside the via's flashing then the via
502 // won't actually connect to anything else, so only return true if
503 // part of the island is *outside* the via's flashing.
504
505 if( !viaHull.SHAPE::Collide( pt ) )
506 return true;
507 }
508 }
509
510 continue;
511 }
512
513 return true;
514 }
515 }
516 }
517
518 return false;
519}
520
521
522unsigned int CONNECTIVITY_DATA::GetUnconnectedCount( bool aVisibleOnly ) const
523{
524 unsigned int unconnected = 0;
525
526 for( RN_NET* net : m_nets )
527 {
528 if( !net )
529 continue;
530
531 for( const CN_EDGE& edge : net->GetEdges() )
532 {
533 if( edge.IsVisible() || !aVisibleOnly )
534 ++unconnected;
535 }
536 }
537
538 return unconnected;
539}
540
541
543{
544 for( RN_NET* net : m_nets )
545 net->Clear();
546}
547
548
549const std::vector<BOARD_CONNECTED_ITEM*>
551{
554
555 std::vector<BOARD_CONNECTED_ITEM*> rv;
556
557 auto clusters = m_connAlgo->SearchClusters( ( aFlags & IGNORE_NETS ) ? CSM_PROPAGATE
558 : CSM_CONNECTIVITY_CHECK,
559 ( aFlags & EXCLUDE_ZONES ),
560 ( aFlags & IGNORE_NETS ) ? -1
561 : aItem->GetNetCode() );
562
563 for( const std::shared_ptr<CN_CLUSTER>& cl : clusters )
564 {
565 if( cl->Contains( aItem ) )
566 {
567 for( const CN_ITEM* item : *cl )
568 {
569 if( item->Valid() )
570 rv.push_back( item->Parent() );
571 }
572 }
573 }
574
575 return rv;
576}
577
578
579const std::vector<BOARD_CONNECTED_ITEM*>
580CONNECTIVITY_DATA::GetNetItems( int aNetCode, const std::vector<KICAD_T>& aTypes ) const
581{
582 std::vector<BOARD_CONNECTED_ITEM*> items;
583 items.reserve( 32 );
584
585 std::bitset<MAX_STRUCT_TYPE_ID> type_bits;
586
587 for( KICAD_T scanType : aTypes )
588 {
589 wxASSERT( scanType < MAX_STRUCT_TYPE_ID );
590 type_bits.set( scanType );
591 }
592
593 m_connAlgo->ForEachItem(
594 [&]( CN_ITEM& aItem )
595 {
596 if( aItem.Valid() && ( aItem.Net() == aNetCode ) && type_bits[aItem.Parent()->Type()] )
597 items.push_back( aItem.Parent() );
598 } );
599
600 std::sort( items.begin(), items.end() );
601 items.erase( std::unique( items.begin(), items.end() ), items.end() );
602 return items;
603}
604
605
606const std::vector<PCB_TRACK*>
608{
609 CN_CONNECTIVITY_ALGO::ITEM_MAP_ENTRY& entry = m_connAlgo->ItemEntry( aItem );
610
611 std::set<PCB_TRACK*> tracks;
612 std::vector<PCB_TRACK*> rv;
613
614 for( CN_ITEM* citem : entry.GetItems() )
615 {
616 for( CN_ITEM* connected : citem->ConnectedItems() )
617 {
618 if( connected->Valid() &&
619 ( connected->Parent()->Type() == PCB_TRACE_T ||
620 connected->Parent()->Type() == PCB_VIA_T ||
621 connected->Parent()->Type() == PCB_ARC_T ) )
622 {
623 tracks.insert( static_cast<PCB_TRACK*> ( connected->Parent() ) );
624 }
625 }
626 }
627
628 std::copy( tracks.begin(), tracks.end(), std::back_inserter( rv ) );
629 return rv;
630}
631
632
634 std::set<PAD*>* pads ) const
635{
636 for( CN_ITEM* citem : m_connAlgo->ItemEntry( aItem ).GetItems() )
637 {
638 for( CN_ITEM* connected : citem->ConnectedItems() )
639 {
640 if( connected->Valid() && connected->Parent()->Type() == PCB_PAD_T )
641 pads->insert( static_cast<PAD*> ( connected->Parent() ) );
642 }
643 }
644}
645
646
647const std::vector<PAD*> CONNECTIVITY_DATA::GetConnectedPads( const BOARD_CONNECTED_ITEM* aItem )
648const
649{
650 std::set<PAD*> pads;
651 std::vector<PAD*> rv;
652
653 GetConnectedPads( aItem, &pads );
654
655 std::copy( pads.begin(), pads.end(), std::back_inserter( rv ) );
656 return rv;
657}
658
659
661 std::vector<PAD*>* pads,
662 std::vector<PCB_VIA*>* vias )
663{
664 for( CN_ITEM* citem : m_connAlgo->ItemEntry( aItem ).GetItems() )
665 {
666 for( CN_ITEM* connected : citem->ConnectedItems() )
667 {
668 if( connected->Valid() )
669 {
670 BOARD_CONNECTED_ITEM* parent = connected->Parent();
671
672 if( parent->Type() == PCB_PAD_T )
673 pads->push_back( static_cast<PAD*>( parent ) );
674 else if( parent->Type() == PCB_VIA_T )
675 vias->push_back( static_cast<PCB_VIA*>( parent ) );
676 }
677 }
678 }
679}
680
681
682unsigned int CONNECTIVITY_DATA::GetNodeCount( int aNet ) const
683{
684 int sum = 0;
685
686 if( aNet < 0 ) // Node count for all nets
687 {
688 for( const RN_NET* net : m_nets )
689 sum += net->GetNodeCount();
690 }
691 else if( aNet < (int) m_nets.size() )
692 {
693 sum = m_nets[aNet]->GetNodeCount();
694 }
695
696 return sum;
697}
698
699
700unsigned int CONNECTIVITY_DATA::GetPadCount( int aNet ) const
701{
702 int n = 0;
703
704 for( CN_ITEM* pad : m_connAlgo->ItemList() )
705 {
706 if( !pad->Valid() || pad->Parent()->Type() != PCB_PAD_T)
707 continue;
708
709 PAD* dpad = static_cast<PAD*>( pad->Parent() );
710
711 if( aNet < 0 || aNet == dpad->GetNetCode() )
712 n++;
713 }
714
715 return n;
716}
717
718
719void CONNECTIVITY_DATA::RunOnUnconnectedEdges( std::function<bool( CN_EDGE& )> aFunc )
720{
721 for( RN_NET* rnNet : m_nets )
722 {
723 if( rnNet )
724 {
725 for( CN_EDGE& edge : rnNet->GetEdges() )
726 {
727 if( !aFunc( edge ) )
728 return;
729 }
730 }
731 }
732}
733
734
735static int getMinDist( BOARD_CONNECTED_ITEM* aItem, const VECTOR2I& aPoint )
736{
737 switch( aItem->Type() )
738 {
739 case PCB_TRACE_T:
740 case PCB_ARC_T:
741 {
742 PCB_TRACK* track = static_cast<PCB_TRACK*>( aItem );
743
744 return std::min( track->GetStart().Distance(aPoint ),
745 track->GetEnd().Distance( aPoint ) );
746 }
747
748 default:
749 return aItem->GetPosition().Distance( aPoint );
750 }
751}
752
753
754bool CONNECTIVITY_DATA::TestTrackEndpointDangling( PCB_TRACK* aTrack, bool aIgnoreTracksInPads,
755 VECTOR2I* aPos ) const
756{
757 const std::list<CN_ITEM*>& items = GetConnectivityAlgo()->ItemEntry( aTrack ).GetItems();
758
759 // Not in the connectivity system. This is a bug!
760 if( items.empty() )
761 {
762 wxFAIL_MSG( wxT( "track not in connectivity system" ) );
763 return false;
764 }
765
766 CN_ITEM* citem = items.front();
767
768 if( !citem->Valid() )
769 return false;
770
771 if( aTrack->Type() == PCB_TRACE_T || aTrack->Type() == PCB_ARC_T )
772 {
773 // Test if a segment is connected on each end.
774 //
775 // NB: be wary of short segments which can be connected to the *same* other item on
776 // each end. If that's their only connection then they're still dangling.
777
778 PCB_LAYER_ID layer = aTrack->GetLayer();
779 int accuracy = KiROUND( aTrack->GetWidth() / 2 );
780 int start_count = 0;
781 int end_count = 0;
782
783 for( CN_ITEM* connected : citem->ConnectedItems() )
784 {
785 BOARD_CONNECTED_ITEM* item = connected->Parent();
786 ZONE* zone = dynamic_cast<ZONE*>( item );
787 DRC_RTREE* rtree = nullptr;
788 bool hitStart = false;
789 bool hitEnd = false;
790
791 if( item->GetFlags() & IS_DELETED )
792 continue;
793
794 if( zone )
795 rtree = zone->GetBoard()->m_CopperZoneRTreeCache[ zone ].get();
796
797 if( rtree )
798 {
799 SHAPE_CIRCLE start( aTrack->GetStart(), accuracy );
800 SHAPE_CIRCLE end( aTrack->GetEnd(), accuracy );
801
802 hitStart = rtree->QueryColliding( start.BBox(), &start, layer );
803 hitEnd = rtree->QueryColliding( end.BBox(), &end, layer );
804 }
805 else
806 {
807 std::shared_ptr<SHAPE> shape = item->GetEffectiveShape( layer );
808
809 hitStart = shape->Collide( aTrack->GetStart(), accuracy );
810 hitEnd = shape->Collide( aTrack->GetEnd(), accuracy );
811 }
812
813 if( hitStart && hitEnd )
814 {
815 if( zone )
816 {
817 // Both start and end in a zone: track may be redundant, but it's not dangling
818 return false;
819 }
820 else if( item->Type() == PCB_PAD_T || item->Type() == PCB_VIA_T )
821 {
822 // Both start and end are under a pad: see what the caller wants us to do
823 if( aIgnoreTracksInPads )
824 return false;
825 }
826
827 if( getMinDist( item, aTrack->GetStart() ) < getMinDist( item, aTrack->GetEnd() ) )
828 start_count++;
829 else
830 end_count++;
831 }
832 else if( hitStart )
833 {
834 start_count++;
835 }
836 else if( hitEnd )
837 {
838 end_count++;
839 }
840
841 if( start_count > 0 && end_count > 0 )
842 return false;
843 }
844
845 if( aPos )
846 *aPos = (start_count == 0 ) ? aTrack->GetStart() : aTrack->GetEnd();
847
848 return true;
849 }
850 else if( aTrack->Type() == PCB_VIA_T )
851 {
852 // Test if a via is only connected on one layer
853
854 const std::vector<CN_ITEM*>& connected = citem->ConnectedItems();
855
856 if( connected.empty() )
857 {
858 // No connections AND no-net is not an error
859 if( aTrack->GetNetCode() <= 0 )
860 return false;
861
862 if( aPos )
863 *aPos = aTrack->GetPosition();
864
865 return true;
866 }
867
868 // Here, we check if the via is connected only to items on a single layer
869 int first_layer = UNDEFINED_LAYER;
870
871 for( CN_ITEM* item : connected )
872 {
873 if( item->Parent()->GetFlags() & IS_DELETED )
874 continue;
875
876 if( first_layer == UNDEFINED_LAYER )
877 first_layer = item->Layer();
878 else if( item->Layer() != first_layer )
879 return false;
880 }
881
882 if( aPos )
883 *aPos = aTrack->GetPosition();
884
885 return true;
886 }
887 else
888 {
889 wxFAIL_MSG( wxT( "CONNECTIVITY_DATA::TestTrackEndpointDangling: unknown track type" ) );
890 }
891
892 return false;
893}
894
895
896const std::vector<BOARD_CONNECTED_ITEM*>
898 const VECTOR2I& aAnchor,
899 const std::vector<KICAD_T>& aTypes,
900 const int& aMaxError ) const
901{
902 CN_CONNECTIVITY_ALGO::ITEM_MAP_ENTRY& entry = m_connAlgo->ItemEntry( aItem );
903 std::vector<BOARD_CONNECTED_ITEM*> rv;
904 SEG::ecoord maxError_sq = (SEG::ecoord) aMaxError * aMaxError;
905
906 for( CN_ITEM* cnItem : entry.GetItems() )
907 {
908 for( CN_ITEM* connected : cnItem->ConnectedItems() )
909 {
910 for( const std::shared_ptr<CN_ANCHOR>& anchor : connected->Anchors() )
911 {
912 if( ( anchor->Pos() - aAnchor ).SquaredEuclideanNorm() <= maxError_sq )
913 {
914 for( KICAD_T type : aTypes )
915 {
916 if( connected->Valid() && connected->Parent()->Type() == type )
917 {
918 rv.push_back( connected->Parent() );
919 break;
920 }
921 }
922
923 break;
924 }
925 }
926 }
927 }
928
929 return rv;
930}
931
932
934{
935 if ( aNet < 0 || aNet >= (int) m_nets.size() )
936 return nullptr;
937
938 return m_nets[ aNet ];
939}
940
941
943{
944 if ( aItem->Type() == PCB_FOOTPRINT_T)
945 {
946 for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
947 m_connAlgo->MarkNetAsDirty( pad->GetNetCode() );
948 }
949
950 if (aItem->IsConnected() )
951 m_connAlgo->MarkNetAsDirty( static_cast<BOARD_CONNECTED_ITEM*>( aItem )->GetNetCode() );
952}
953
954
956{
957 m_connAlgo->RemoveInvalidRefs();
958
959 for( RN_NET* rnNet : m_nets )
960 rnNet->RemoveInvalidRefs();
961}
962
963
965{
966 m_progressReporter = aReporter;
967 m_connAlgo->SetProgressReporter( m_progressReporter );
968}
969
970
971const std::vector<CN_EDGE>
972CONNECTIVITY_DATA::GetRatsnestForItems( const std::vector<BOARD_ITEM*>& aItems )
973{
974 std::set<int> nets;
975 std::vector<CN_EDGE> edges;
976 std::set<BOARD_CONNECTED_ITEM*> item_set;
977
978 for( BOARD_ITEM* item : aItems )
979 {
980 if( item->Type() == PCB_FOOTPRINT_T )
981 {
982 FOOTPRINT* footprint = static_cast<FOOTPRINT*>( item );
983
984 for( PAD* pad : footprint->Pads() )
985 {
986 nets.insert( pad->GetNetCode() );
987 item_set.insert( pad );
988 }
989 }
990 else if( item->IsConnected() )
991 {
992 BOARD_CONNECTED_ITEM* conn_item = static_cast<BOARD_CONNECTED_ITEM*>( item );
993
994 item_set.insert( conn_item );
995 nets.insert( conn_item->GetNetCode() );
996 }
997 }
998
999 for( int netcode : nets )
1000 {
1001 RN_NET* net = GetRatsnestForNet( netcode );
1002
1003 if( !net )
1004 continue;
1005
1006 for( const CN_EDGE& edge : net->GetEdges() )
1007 {
1008 std::shared_ptr<const CN_ANCHOR> srcNode = edge.GetSourceNode();
1009 std::shared_ptr<const CN_ANCHOR> dstNode = edge.GetTargetNode();
1010
1011 if( !srcNode || srcNode->Dirty() || !dstNode || dstNode->Dirty() )
1012 continue;
1013
1014 BOARD_CONNECTED_ITEM* srcParent = srcNode->Parent();
1015 BOARD_CONNECTED_ITEM* dstParent = dstNode->Parent();
1016
1017 bool srcFound = ( item_set.find( srcParent ) != item_set.end() );
1018 bool dstFound = ( item_set.find( dstParent ) != item_set.end() );
1019
1020 if ( srcFound && dstFound )
1021 edges.push_back( edge );
1022 }
1023 }
1024
1025 return edges;
1026}
1027
1028
1029const std::vector<CN_EDGE> CONNECTIVITY_DATA::GetRatsnestForPad( const PAD* aPad )
1030{
1031 std::vector<CN_EDGE> edges;
1032 RN_NET* net = GetRatsnestForNet( aPad->GetNetCode() );
1033
1034 if( !net )
1035 return edges;
1036
1037 for( const CN_EDGE& edge : net->GetEdges() )
1038 {
1039 if( !edge.GetSourceNode() || edge.GetSourceNode()->Dirty() )
1040 continue;
1041
1042 if( !edge.GetTargetNode() || edge.GetTargetNode()->Dirty() )
1043 continue;
1044
1045 if( edge.GetSourceNode()->Parent() == aPad || edge.GetTargetNode()->Parent() == aPad )
1046 edges.push_back( edge );
1047 }
1048
1049 return edges;
1050}
1051
1052
1053const std::vector<CN_EDGE> CONNECTIVITY_DATA::GetRatsnestForComponent( FOOTPRINT* aComponent,
1054 bool aSkipInternalConnections )
1055{
1056 std::set<int> nets;
1057 std::set<const PAD*> pads;
1058 std::vector<CN_EDGE> edges;
1059
1060 for( PAD* pad : aComponent->Pads() )
1061 {
1062 nets.insert( pad->GetNetCode() );
1063 pads.insert( pad );
1064 }
1065
1066 for( int netcode : nets )
1067 {
1068 RN_NET* net = GetRatsnestForNet( netcode );
1069
1070 if( !net )
1071 continue;
1072
1073 for( const CN_EDGE& edge : net->GetEdges() )
1074 {
1075 const std::shared_ptr<const CN_ANCHOR>& srcNode = edge.GetSourceNode();
1076 const std::shared_ptr<const CN_ANCHOR>& dstNode = edge.GetTargetNode();
1077
1078 if( !srcNode || srcNode->Dirty() || !dstNode || dstNode->Dirty() )
1079 continue;
1080
1081 const PAD* srcParent = static_cast<const PAD*>( srcNode->Parent() );
1082 const PAD* dstParent = static_cast<const PAD*>( dstNode->Parent() );
1083
1084 bool srcFound = ( pads.find(srcParent) != pads.end() );
1085 bool dstFound = ( pads.find(dstParent) != pads.end() );
1086
1087 if ( srcFound && dstFound && !aSkipInternalConnections )
1088 edges.push_back( edge );
1089 else if ( srcFound || dstFound )
1090 edges.push_back( edge );
1091 }
1092 }
1093
1094 return edges;
1095}
1096
1097
1099{
1100 if( std::shared_ptr<NET_SETTINGS> netSettings = m_netSettings.lock() )
1101 return netSettings.get();
1102 else
1103 return nullptr;
1104}
@ ERROR_INSIDE
Definition: approximation.h:34
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
Definition: box2.h:990
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
std::shared_ptr< NET_SETTINGS > m_NetSettings
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:78
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:235
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:137
virtual std::shared_ptr< SHAPE > GetEffectiveShape(PCB_LAYER_ID aLayer=UNDEFINED_LAYER, FLASHING aFlash=FLASHING::DEFAULT) const
Some pad shapes can be complex (rounded/chamfered rectangle), even without considering custom shapes.
Definition: board_item.cpp:285
virtual const BOARD * GetBoard() const
Return the BOARD in which this BOARD_ITEM resides, or NULL if none.
Definition: board_item.cpp:54
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:297
const NETINFO_LIST & GetNetInfo() const
Definition: board.h:897
std::unordered_map< ZONE *, std::unique_ptr< DRC_RTREE > > m_CopperZoneRTreeCache
Definition: board.h:1341
BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Definition: board.cpp:946
void CacheTriangulation(PROGRESS_REPORTER *aReporter=nullptr, const std::vector< ZONE * > &aZones={})
Definition: board.cpp:990
CN_ANCHOR represents a physical location that can be connected: a pad or a track/arc/via endpoint.
const std::list< CN_ITEM * > & GetItems() const
CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc.
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
const std::vector< CN_ITEM * > & ConnectedItems() const
int Net() const
bool Valid() const
BOARD_CONNECTED_ITEM * Parent() const
int SubpolyIndex() const
void FillIsolatedIslandsMap(std::map< ZONE *, std::map< PCB_LAYER_ID, ISOLATED_ISLANDS > > &aMap, bool aConnectivityAlreadyRebuilt=false)
Fill the isolate islands list for each layer of each zone.
void RecalculateRatsnest(BOARD_COMMIT *aCommit=nullptr)
Function RecalculateRatsnest() Updates the ratsnest for the board.
void ClearLocalRatsnest()
Function ClearLocalRatsnest() Erases the temporary, selection-based ratsnest (i.e.
PROGRESS_REPORTER * m_progressReporter
unsigned int GetPadCount(int aNet=-1) const
void MarkItemNetAsDirty(BOARD_ITEM *aItem)
std::weak_ptr< NET_SETTINGS > m_netSettings
Used to get netclass data when drawing ratsnests.
const std::vector< BOARD_CONNECTED_ITEM * > GetConnectedItems(const BOARD_CONNECTED_ITEM *aItem, int aFlags=0) const
void PropagateNets(BOARD_COMMIT *aCommit=nullptr)
Propagates the net codes from the source pads to the tracks/vias.
void RunOnUnconnectedEdges(std::function< bool(CN_EDGE &)> aFunc)
std::vector< RN_DYNAMIC_LINE > m_dynamicRatsnest
bool m_skipRatsnestUpdate
Used to suppress ratsnest calculations on dynamic ratsnests.
const std::vector< CN_EDGE > GetRatsnestForPad(const PAD *aPad)
RN_NET * GetRatsnestForNet(int aNet)
Function GetRatsnestForNet() Returns the ratsnest, expressed as a set of graph edges for a given net.
const std::vector< BOARD_CONNECTED_ITEM * > GetConnectedItemsAtAnchor(const BOARD_CONNECTED_ITEM *aItem, const VECTOR2I &aAnchor, const std::vector< KICAD_T > &aTypes, const int &aMaxError=0) const
Function GetConnectedItemsAtAnchor() Returns a list of items connected to a source item aItem at posi...
void ClearRatsnest()
Function Clear() Erases the connectivity database.
bool Remove(BOARD_ITEM *aItem)
Function Remove() Removes an item from the connectivity data.
void GetConnectedPadsAndVias(const BOARD_CONNECTED_ITEM *aItem, std::vector< PAD * > *pads, std::vector< PCB_VIA * > *vias)
const NET_SETTINGS * GetNetSettings() const
void ComputeLocalRatsnest(const std::vector< BOARD_ITEM * > &aItems, const CONNECTIVITY_DATA *aDynamicData, VECTOR2I aInternalOffset={ 0, 0 })
Function ComputeLocalRatsnest() Calculates the temporary (usually selection-based) ratsnest for the s...
bool TestTrackEndpointDangling(PCB_TRACK *aTrack, bool aIgnoreTracksInPads, VECTOR2I *aPos=nullptr) const
unsigned int GetNodeCount(int aNet=-1) const
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
void BlockRatsnestItems(const std::vector< BOARD_ITEM * > &aItems)
bool IsConnectedOnLayer(const BOARD_CONNECTED_ITEM *aItem, int aLayer, const std::initializer_list< KICAD_T > &aTypes={}) const
const std::vector< PCB_TRACK * > GetConnectedTracks(const BOARD_CONNECTED_ITEM *aItem) const
const std::vector< CN_EDGE > GetRatsnestForComponent(FOOTPRINT *aComponent, bool aSkipInternalConnections=false)
const std::vector< BOARD_CONNECTED_ITEM * > GetNetItems(int aNetCode, const std::vector< KICAD_T > &aTypes) const
Function GetNetItems() Returns the list of items that belong to a certain net.
bool Add(BOARD_ITEM *aItem)
Function Add() Adds an item to the connectivity data.
std::shared_ptr< CN_CONNECTIVITY_ALGO > m_connAlgo
bool Build(BOARD *aBoard, PROGRESS_REPORTER *aReporter=nullptr)
Function Build() Builds the connectivity database for the board aBoard.
std::shared_ptr< FROM_TO_CACHE > m_fromToCache
const std::vector< PAD * > GetConnectedPads(const BOARD_CONNECTED_ITEM *aItem) const
unsigned int GetUnconnectedCount(bool aVisibileOnly) const
std::map< int, wxString > m_netcodeMap
Used to map netcode to net name.
void internalRecalculateRatsnest(BOARD_COMMIT *aCommit=nullptr)
Updates the ratsnest for the board without locking the connectivity mutex.
void RefreshNetcodeMap(BOARD *aBoard)
Refresh the map of netcodes to net names.
void HideLocalRatsnest()
Hides the temporary, selection-based ratsnest lines.
const std::vector< CN_EDGE > GetRatsnestForItems(const std::vector< BOARD_ITEM * > &aItems)
void addRatsnestCluster(const std::shared_ptr< CN_CLUSTER > &aCluster)
std::vector< RN_NET * > m_nets
bool Update(BOARD_ITEM *aItem)
Function Update() Updates the connectivity data for an item.
void Move(const VECTOR2I &aDelta)
Moves the connectivity list anchors.
int GetNetCount() const
Function GetNetCount() Returns the total number of nets in the connectivity database.
std::shared_ptr< CN_CONNECTIVITY_ALGO > GetConnectivityAlgo() const
Implement an R-tree for fast spatial and layer indexing of connectable items.
Definition: drc_rtree.h:48
int QueryColliding(BOARD_ITEM *aRefItem, PCB_LAYER_ID aRefLayer, PCB_LAYER_ID aTargetLayer, std::function< bool(BOARD_ITEM *)> aFilter=nullptr, std::function< bool(BOARD_ITEM *)> aVisitor=nullptr, int aClearance=0) const
This is a fast test which essentially does bounding-box overlap given a worst-case clearance.
Definition: drc_rtree.h:214
virtual VECTOR2I GetPosition() const
Definition: eda_item.h:248
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:107
EDA_ITEM_FLAGS GetFlags() const
Definition: eda_item.h:134
std::deque< PAD * > & Pads()
Definition: footprint.h:211
Handle the data for a net.
Definition: netinfo.h:56
NET_SETTINGS stores various net-related settings in a project context.
Definition: net_settings.h:39
Definition: pad.h:54
const VECTOR2I & GetStart() const
Definition: pcb_track.h:152
VECTOR2I GetPosition() const override
Definition: pcb_track.h:142
const VECTOR2I & GetEnd() const
Definition: pcb_track.h:149
virtual int GetWidth() const
Definition: pcb_track.h:146
A small class to help profiling.
Definition: profile.h:49
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
Definition: profile.h:105
A progress reporter interface for use in multi-threaded environments.
virtual bool KeepRefreshing(bool aWait=false)=0
Update the UI (if any).
virtual void Report(const wxString &aMessage)=0
Display aMessage in the progress bar dialog.
virtual void SetCurrentProgress(double aProgress)=0
Set the progress value to aProgress (0..1).
Describe ratsnest for a single net.
Definition: ratsnest_data.h:63
unsigned int GetNodeCount() const
Definition: ratsnest_data.h:94
const std::vector< CN_EDGE > & GetEdges() const
Definition: ratsnest_data.h:96
bool NearestBicoloredPair(RN_NET *aOtherNet, VECTOR2I &aPos1, VECTOR2I &aPos2) const
void AddCluster(std::shared_ptr< CN_CLUSTER > aCluster)
VECTOR2I::extended_type ecoord
Definition: seg.h:44
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_circle.h:70
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const std::vector< VECTOR2I > & CPoints() const
Represent a set of closed polygons.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
double Distance(const VECTOR2< extended_type > &aVector) const
Compute the distance between two vectors.
Definition: vector2d.h:561
Handle a list of polygons defining a copper zone.
Definition: zone.h:74
bool IsFilled() const
Definition: zone.h:292
SHAPE_POLY_SET * GetFill(PCB_LAYER_ID aLayer)
Definition: zone.h:654
static int getMinDist(BOARD_CONNECTED_ITEM *aItem, const VECTOR2I &aPoint)
#define EXCLUDE_ZONES
#define IGNORE_NETS
Function GetConnectedItems() Returns a list of items connected to a source item aItem.
#define _(s)
#define IS_DELETED
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:60
@ B_Cu
Definition: layer_ids.h:65
@ UNDEFINED_LAYER
Definition: layer_ids.h:61
PCB_LAYER_ID ToLAYER_ID(int aLayer)
Definition: lset.cpp:723
bool contains(const _Container &__container, _Value __value)
Returns true if the container contains the given value.
Definition: kicad_algo.h:100
Class that computes missing connections on a PCB.
VECTOR2I end
const int accuracy
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
Definition: thread_pool.cpp:30
static thread_pool * tp
Definition: thread_pool.cpp:28
BS::thread_pool thread_pool
Definition: thread_pool.h:31
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:78
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:97
@ MAX_STRUCT_TYPE_ID
Definition: typeinfo.h:237
@ PCB_FOOTPRINT_T
class FOOTPRINT, a footprint
Definition: typeinfo.h:86
@ 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