KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_node.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2019 CERN
5 * Copyright (C) 2016-2023 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <[email protected]>
8 *
9 * This program is free software: you can redistribute it and/or modify it
10 * under the terms of the GNU General Public License as published by the
11 * Free Software Foundation, either version 3 of the License, or (at your
12 * option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program. If not, see <http://www.gnu.org/licenses/>.
21 */
22
23#include <vector>
24#include <cassert>
25#include <utility>
26
27#include <math/vector2d.h>
28
29#include <geometry/seg.h>
31#include <zone.h>
32
33#include <wx/log.h>
34
35#include "pns_arc.h"
36#include "pns_item.h"
37#include "pns_itemset.h"
38#include "pns_line.h"
39#include "pns_node.h"
40#include "pns_via.h"
41#include "pns_solid.h"
42#include "pns_joint.h"
43#include "pns_index.h"
44#include "pns_debug_decorator.h"
45#include "pns_router.h"
46#include "pns_utils.h"
47
48
49namespace PNS {
50
51#ifdef DEBUG
52static std::unordered_set<const NODE*> allocNodes;
53#endif
54
56{
57 m_depth = 0;
58 m_root = this;
59 m_parent = nullptr;
60 m_maxClearance = 800000; // fixme: depends on how thick traces are.
61 m_ruleResolver = nullptr;
62 m_index = new INDEX;
63
64#ifdef DEBUG
65 allocNodes.insert( this );
66#endif
67}
68
69
71{
72 if( !m_children.empty() )
73 {
74 wxLogTrace( wxT( "PNS" ), wxT( "attempting to free a node that has kids." ) );
75 assert( false );
76 }
77
78#ifdef DEBUG
79 if( allocNodes.find( this ) == allocNodes.end() )
80 {
81 wxLogTrace( wxT( "PNS" ), wxT( "attempting to free an already-free'd node." ) );
82 assert( false );
83 }
84
85 allocNodes.erase( this );
86#endif
87
88 m_joints.clear();
89
90 std::vector<const ITEM*> toDelete;
91
92 toDelete.reserve( m_index->Size() );
93
94 for( ITEM* item : *m_index )
95 {
96 if( item->BelongsTo( this ) && item->OfKind( ITEM::HOLE_T ) )
97 toDelete.push_back( item );
98 }
99
100 for( const ITEM* item : toDelete )
101 {
102 wxLogTrace( wxT( "PNS" ), wxT( "del item %p type %s" ), item, item->KindStr().c_str() );
103 delete item;
104 }
105
106 if( m_ruleResolver )
107 {
109 }
110
112 unlinkParent();
113
114 delete m_index;
115}
116
117
118int NODE::GetClearance( const ITEM* aA, const ITEM* aB, bool aUseClearanceEpsilon ) const
119{
120 if( !m_ruleResolver )
121 return 100000;
122
123 if( aA->IsVirtual() || aB->IsVirtual() )
124 return 0;
125
126 int cl = m_ruleResolver->Clearance( aA, aB, aUseClearanceEpsilon );
127
128 return cl;
129}
130
131
133{
134 NODE* child = new NODE;
135
136 m_children.insert( child );
137
138 child->m_depth = m_depth + 1;
139 child->m_parent = this;
141 child->m_root = isRoot() ? this : m_root;
143
144 // Immediate offspring of the root branch needs not copy anything. For the rest, deep-copy
145 // joints, overridden item maps and pointers to stored items.
146 if( !isRoot() )
147 {
148 JOINT_MAP::iterator j;
149
150 for( ITEM* item : *m_index )
151 child->m_index->Add( item );
152
153 child->m_joints = m_joints;
154 child->m_override = m_override;
155 }
156
157#if 0
158 wxLogTrace( wxT( "PNS" ), wxT( "%d items, %d joints, %d overrides" ),
159 child->m_index->Size(),
160 (int) child->m_joints.size(),
161 (int) child->m_override.size() );
162#endif
163
164 return child;
165}
166
167
169{
170 if( isRoot() )
171 return;
172
173 m_parent->m_children.erase( this );
174}
175
176
178 m_item( aItem ),
179 m_node( nullptr ),
180 m_override( nullptr )
181{
182}
183
184
185void OBSTACLE_VISITOR::SetWorld( const NODE* aNode, const NODE* aOverride )
186{
187 m_node = aNode;
188 m_override = aOverride;
189}
190
191
192bool OBSTACLE_VISITOR::visit( ITEM* aCandidate )
193{
194 // check if there is a more recent branch with a newer (possibly modified) version of this
195 // item.
196 if( m_override && m_override->Overrides( aCandidate ) )
197 return true;
198
199 return false;
200}
201
202
203// function object that visits potential obstacles and performs the actual collision refining
205{
207
209 OBSTACLE_VISITOR( aItem ),
210 m_ctx( aCtx )
211 {
212 }
213
215 {
216 }
217
218 bool operator()( ITEM* aCandidate ) override
219 {
220 if( !aCandidate->OfKind( m_ctx->options.m_kindMask ) )
221 return true;
222
223 // Collisions with self aren't a thing; don't spend time on them.
224 if( m_item == aCandidate )
225 return true;
226
227 if( visit( aCandidate ) )
228 return true;
229
230 if( !aCandidate->Collide( m_item, m_node, m_ctx ) )
231 return true;
232
234 return false;
235
236 return true;
237 };
238};
239
240
241int NODE::QueryColliding( const ITEM* aItem, NODE::OBSTACLES& aObstacles,
242 const COLLISION_SEARCH_OPTIONS& aOpts ) const
243{
244 COLLISION_SEARCH_CONTEXT ctx( aObstacles, aOpts );
245
247 if( aItem->IsVirtual() )
248 return 0;
249
250 DEFAULT_OBSTACLE_VISITOR visitor( &ctx, aItem );
251
252#ifdef DEBUG
253 assert( allocNodes.find( this ) != allocNodes.end() );
254#endif
255
256 visitor.SetWorld( this, nullptr );
257
258 // first, look for colliding items in the local index
259 m_index->Query( aItem, m_maxClearance, visitor );
260
261 // if we haven't found enough items, look in the root branch as well.
262 if( !isRoot() && ( ctx.obstacles.size() < aOpts.m_limitCount || aOpts.m_limitCount < 0 ) )
263 {
264 visitor.SetWorld( m_root, this );
265 m_root->m_index->Query( aItem, m_maxClearance, visitor );
266 }
267
268 return aObstacles.size();
269}
270
271
273 const COLLISION_SEARCH_OPTIONS& aOpts )
274{
275 const int clearanceEpsilon = GetRuleResolver()->ClearanceEpsilon();
276 OBSTACLES obstacleList;
277 std::vector<SEGMENT> tmpSegs;
278
279 tmpSegs.reserve( aLine->CLine().SegmentCount() );
280
281
282 for( int i = 0; i < aLine->CLine().SegmentCount(); i++ )
283 {
284 // Note: Clearances between tmpSegs.back() and other items are cached,
285 // which means they'll be the same for all segments in the line.
286 // Disabling the cache will lead to slowness.
287
288 tmpSegs.emplace_back( *aLine, aLine->CLine().CSegment( i ) );
289 QueryColliding( &tmpSegs.back(), obstacleList, aOpts );
290 }
291
292 if( aLine->EndsWithVia() )
293 QueryColliding( &aLine->Via(), obstacleList, aOpts );
294
295 if( obstacleList.empty() )
296 return OPT_OBSTACLE();
297
298 OBSTACLE nearest;
299 nearest.m_head = nullptr;
300 nearest.m_item = nullptr;
301 nearest.m_distFirst = INT_MAX;
302 nearest.m_maxFanoutWidth = 0;
303
304 auto updateNearest =
305 [&]( const SHAPE_LINE_CHAIN::INTERSECTION& pt, const OBSTACLE& obstacle )
306 {
307 int dist = aLine->CLine().PathLength( pt.p, pt.index_their );
308
309 if( dist < nearest.m_distFirst )
310 {
311 nearest = obstacle;
312 nearest.m_distFirst = dist;
313 nearest.m_ipFirst = pt.p;
314 }
315 };
316
317 SHAPE_LINE_CHAIN obstacleHull;
319 std::vector<SHAPE_LINE_CHAIN::INTERSECTION> intersectingPts;
320 int layer = aLine->Layer();
321
322 for( const OBSTACLE& obstacle : obstacleList )
323 {
324 if( aOpts.m_restrictedSet && aOpts.m_restrictedSet->count( obstacle.m_item ) == 0 )
325 continue;
326
327 int clearance =
328 GetClearance( obstacle.m_item, aLine, aOpts.m_useClearanceEpsilon ) + aLine->Width() / 2;
329
330 obstacleHull = obstacle.m_item->Hull( clearance, 0, layer );
331 //debugDecorator->AddLine( obstacleHull, 2, 40000, "obstacle-hull-test" );
332 //debugDecorator->AddLine( aLine->CLine(), 5, 40000, "obstacle-test-line" );
333
334 intersectingPts.clear();
335 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
336
337 for( const auto& ip : intersectingPts )
338 {
339 //debugDecorator->AddPoint( ip.p, ip.valid?3:6, 100000, (const char *) wxString::Format("obstacle-isect-point-%d" ).c_str() );
340 if( ip.valid )
341 updateNearest( ip, obstacle );
342 }
343
344 if( aLine->EndsWithVia() )
345 {
346 const VIA& via = aLine->Via();
347 int viaClearance = GetClearance( obstacle.m_item, &via, aOpts.m_useClearanceEpsilon )
348 + via.Diameter() / 2;
349
350 obstacleHull = obstacle.m_item->Hull( viaClearance, 0, layer );
351 //debugDecorator->AddLine( obstacleHull, 3 );
352
353 intersectingPts.clear();
354 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
355
356 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
357 updateNearest( ip, obstacle );
358 }
359 }
360
361 if( nearest.m_distFirst == INT_MAX )
362 nearest = (*obstacleList.begin());
363
364 return nearest;
365}
366
367
369{
370 for( const ITEM* item : aSet.CItems() )
371 {
372 OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
373
374 if( obs )
375 return obs;
376 }
377
378 return OPT_OBSTACLE();
379}
380
381
382NODE::OPT_OBSTACLE NODE::CheckColliding( const ITEM* aItemA, int aKindMask )
383{
384 OBSTACLES obs;
386
387 opts.m_kindMask = aKindMask;
388 opts.m_limitCount = 1;
389
390 if( aItemA->Kind() == ITEM::LINE_T )
391 {
392 int n = 0;
393 const LINE* line = static_cast<const LINE*>( aItemA );
394 const SHAPE_LINE_CHAIN& l = line->CLine();
395
396 for( int i = 0; i < l.SegmentCount(); i++ )
397 {
398 // Note: Clearances between &s and other items are cached,
399 // which means they'll be the same for all segments in the line.
400 // Disabling the cache will lead to slowness.
401
402 const SEGMENT s( *line, l.CSegment( i ) );
403 n += QueryColliding( &s, obs, opts );
404
405 if( n )
406 return OPT_OBSTACLE( *obs.begin() );
407 }
408
409 if( line->EndsWithVia() )
410 {
411 n += QueryColliding( &line->Via(), obs, opts );
412
413 if( n )
414 return OPT_OBSTACLE( *obs.begin() );
415 }
416 }
417 else if( QueryColliding( aItemA, obs, opts ) > 0 )
418 {
419 return OPT_OBSTACLE( *obs.begin() );
420 }
421
422 return OPT_OBSTACLE();
423}
424
425
427{
430
431 HIT_VISITOR( ITEM_SET& aTab, const VECTOR2I& aPoint ) :
432 OBSTACLE_VISITOR( nullptr ),
433 m_items( aTab ),
434 m_point( aPoint )
435 {}
436
437 virtual ~HIT_VISITOR()
438 {
439 }
440
441 bool operator()( ITEM* aItem ) override
442 {
443 SHAPE_CIRCLE cp( m_point, 0 );
444
445 int cl = 0;
446
447 if( aItem->Shape()->Collide( &cp, cl ) )
448 m_items.Add( aItem );
449
450 return true;
451 }
452};
453
454
455const ITEM_SET NODE::HitTest( const VECTOR2I& aPoint ) const
456{
457 ITEM_SET items;
458
459 // fixme: we treat a point as an infinitely small circle - this is inefficient.
460 SHAPE_CIRCLE s( aPoint, 0 );
461 HIT_VISITOR visitor( items, aPoint );
462 visitor.SetWorld( this, nullptr );
463
464 m_index->Query( &s, m_maxClearance, visitor );
465
466 if( !isRoot() ) // fixme: could be made cleaner
467 {
468 ITEM_SET items_root;
469 visitor.SetWorld( m_root, nullptr );
470 HIT_VISITOR visitor_root( items_root, aPoint );
471 m_root->m_index->Query( &s, m_maxClearance, visitor_root );
472
473 for( ITEM* item : items_root.Items() )
474 {
475 if( !Overrides( item ) )
476 items.Add( item );
477 }
478 }
479
480 return items;
481}
482
483
484void NODE::addSolid( SOLID* aSolid )
485{
486 if( aSolid->HasHole() && aSolid->Hole()->BelongsTo( aSolid ) )
487 addHole( aSolid->Hole() );
488
489 if( aSolid->IsRoutable() )
490 linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
491
492 aSolid->SetOwner( this );
493 m_index->Add( aSolid );
494}
495
496
497void NODE::Add( std::unique_ptr< SOLID >&& aSolid )
498{
499 aSolid->SetOwner( this );
500 addSolid( aSolid.release() );
501}
502
503
504void NODE::addVia( VIA* aVia )
505{
506 if( aVia->HasHole() && aVia->Hole()->BelongsTo( aVia ) )
507 addHole( aVia->Hole() );
508
509 linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
510 aVia->SetOwner( this );
511
512 m_index->Add( aVia );
513}
514
515
516void NODE::addHole( HOLE* aHole )
517{
518 // do we need holes in the connection graph?
519 //linkJoint( aHole->Pos(), aHole->Layers(), aHole->Net(), aHole );
520
521 aHole->SetOwner( this );
522 m_index->Add( aHole );
523}
524
525
526void NODE::Add( std::unique_ptr< VIA >&& aVia )
527{
528 addVia( aVia.release() );
529}
530
531
532void NODE::add( ITEM* aItem, bool aAllowRedundant )
533{
534 switch( aItem->Kind() )
535 {
536 case ITEM::ARC_T:
537 addArc( static_cast<ARC*>( aItem ) );
538 break;
539 case ITEM::SEGMENT_T:
540 addSegment( static_cast<SEGMENT*>( aItem ) );
541 break;
542 case ITEM::VIA_T:
543 addVia( static_cast<VIA*>( aItem ) );
544 break;
545 case ITEM::SOLID_T:
546 addSolid( static_cast<SOLID*>( aItem ) );
547 break;
548 case ITEM::HOLE_T:
549 // added by parent VIA_T or SOLID_T (pad)
550 break;
551 default:
552 assert( false );
553 }
554}
555
556
557void NODE::Add( LINE& aLine, bool aAllowRedundant )
558{
559 assert( !aLine.IsLinked() );
560
561 SHAPE_LINE_CHAIN& l = aLine.Line();
562
563 for( size_t i = 0; i < l.ArcCount(); i++ )
564 {
565 auto s = l.Arc( i );
566 ARC* rarc;
567
568 if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(),
569 aLine.Net() ) ) )
570 {
571 aLine.Link( rarc );
572 }
573 else
574 {
575 auto newarc = std::make_unique< ARC >( aLine, s );
576 aLine.Link( newarc.get() );
577 Add( std::move( newarc ), true );
578 }
579 }
580
581 for( int i = 0; i < l.SegmentCount(); i++ )
582 {
583 if( l.IsArcSegment( i ) )
584 continue;
585
586 SEG s = l.CSegment( i );
587
588 if( s.A != s.B )
589 {
590 SEGMENT* rseg;
591
592 if( !aAllowRedundant && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(),
593 aLine.Net() ) ) )
594 {
595 // another line could be referencing this segment too :(
596 aLine.Link( rseg );
597 }
598 else
599 {
600 std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
601 aLine.Link( newseg.get() );
602 Add( std::move( newseg ), true );
603 }
604 }
605 }
606}
607
608
610{
611 aSeg->SetOwner( this );
612
613 linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
614 linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
615
616 m_index->Add( aSeg );
617}
618
619
620bool NODE::Add( std::unique_ptr< SEGMENT >&& aSegment, bool aAllowRedundant )
621{
622 if( aSegment->Seg().A == aSegment->Seg().B )
623 {
624 wxLogTrace( wxT( "PNS" ),
625 wxT( "attempting to add a segment with same end coordinates, ignoring." ) );
626 return false;
627 }
628
629 if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
630 return false;
631
632 addSegment( aSegment.release() );
633
634 return true;
635}
636
637
638void NODE::addArc( ARC* aArc )
639{
640 aArc->SetOwner( this );
641
642 linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
643 linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
644
645 m_index->Add( aArc );
646}
647
648
649bool NODE::Add( std::unique_ptr< ARC >&& aArc, bool aAllowRedundant )
650{
651 const SHAPE_ARC& arc = aArc->CArc();
652
653 if( !aAllowRedundant && findRedundantArc( arc.GetP0(), arc.GetP1(), aArc->Layers(),
654 aArc->Net() ) )
655 {
656 return false;
657 }
658
659 addArc( aArc.release() );
660 return true;
661}
662
663
664void NODE::AddEdgeExclusion( std::unique_ptr<SHAPE> aShape )
665{
666 m_edgeExclusions.push_back( std::move( aShape ) );
667}
668
669
670bool NODE::QueryEdgeExclusions( const VECTOR2I& aPos ) const
671{
672 for( const std::unique_ptr<SHAPE>& edgeExclusion : m_edgeExclusions )
673 {
674 if( edgeExclusion->Collide( aPos ) )
675 return true;
676 }
677
678 return false;
679}
680
681
682void NODE::doRemove( ITEM* aItem )
683{
684 // case 1: removing an item that is stored in the root node from any branch:
685 // mark it as overridden, but do not remove
686 if( aItem->BelongsTo( m_root ) && !isRoot() )
687 {
688 m_override.insert( aItem );
689
690 if( aItem->HasHole() )
691 m_override.insert( aItem->Hole() );
692 }
693
694 // case 2: the item belongs to this branch or a parent, non-root branch,
695 // or the root itself and we are the root: remove from the index
696 else if( !aItem->BelongsTo( m_root ) || isRoot() )
697 {
698 m_index->Remove( aItem );
699
700 if( aItem->HasHole() )
701 m_index->Remove( aItem->Hole() );
702 }
703
704 // the item belongs to this particular branch: un-reference it
705 if( aItem->BelongsTo( this ) )
706 {
707 aItem->SetOwner( nullptr );
708
709 m_root->m_garbageItems.insert( aItem );
710
711 HOLE *hole = aItem->Hole();
712
713 if( hole )
714 {
715 m_index->Remove( hole ); // hole is not directly owned by NODE but by the parent SOLID/VIA.
716 hole->SetOwner( hole->ParentPadVia() );
717 }
718 }
719}
720
721
723{
724 unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
725 unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
726}
727
728
730{
731 unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
732 unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
733}
734
735
736void NODE::rebuildJoint( const JOINT* aJoint, const ITEM* aItem )
737{
738 // We have to split a single joint (associated with a via or a pad, binding together multiple
739 // layers) into multiple independent joints. As I'm a lazy bastard, I simply delete the
740 // via/solid and all its links and re-insert them.
741
742 std::vector<ITEM*> links( aJoint->LinkList() );
743 JOINT::HASH_TAG tag;
744 int net = aItem->Net();
745
746 tag.net = net;
747 tag.pos = aJoint->Pos();
748
749 bool split;
750
751 do
752 {
753 split = false;
754 auto range = m_joints.equal_range( tag );
755
756 if( range.first == m_joints.end() )
757 break;
758
759 // find and remove all joints containing the via to be removed
760
761 for( auto f = range.first; f != range.second; ++f )
762 {
763 if( aItem->LayersOverlap( &f->second ) )
764 {
765 m_joints.erase( f );
766 split = true;
767 break;
768 }
769 }
770 } while( split );
771
772 // and re-link them, using the former via's link list
773 for( ITEM* link : links )
774 {
775 if( link != aItem )
776 linkJoint( tag.pos, link->Layers(), net, link );
777 }
778}
779
780
782{
783 const JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
784 assert( jt );
785 rebuildJoint( jt, aVia );
786}
787
788
790{
791 if( !aSolid->IsRoutable() )
792 return;
793
794 // fixme: redundant code
795 const JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
796 assert( jt );
797 rebuildJoint( jt, aSolid );
798}
799
800
801void NODE::Replace( ITEM* aOldItem, std::unique_ptr< ITEM >&& aNewItem )
802{
803 Remove( aOldItem );
804 add( aNewItem.release() );
805}
806
807
808void NODE::Replace( LINE& aOldLine, LINE& aNewLine )
809{
810 Remove( aOldLine );
811 Add( aNewLine );
812}
813
814
815void NODE::Remove( SOLID* aSolid )
816{
817 removeSolidIndex( aSolid );
818 doRemove( aSolid );
819}
820
821
822void NODE::Remove( VIA* aVia )
823{
824 removeViaIndex( aVia );
825 doRemove( aVia );
826}
827
828
829void NODE::Remove( SEGMENT* aSegment )
830{
831 removeSegmentIndex( aSegment );
832 doRemove( aSegment );
833}
834
835
836void NODE::Remove( ARC* aArc )
837{
838 removeArcIndex( aArc );
839 doRemove( aArc );
840}
841
842
843void NODE::Remove( ITEM* aItem )
844{
845 switch( aItem->Kind() )
846 {
847 case ITEM::ARC_T:
848 Remove( static_cast<ARC*>( aItem ) );
849 break;
850
851 case ITEM::SOLID_T:
852 {
853 SOLID* solid = static_cast<SOLID*>( aItem );
854
855 if( solid->HasHole() )
856 Remove( solid->Hole() );
857
858 Remove( static_cast<SOLID*>( aItem ) );
859 break;
860 }
861
862 case ITEM::SEGMENT_T:
863 Remove( static_cast<SEGMENT*>( aItem ) );
864 break;
865
866 case ITEM::LINE_T:
867 {
868 LINE* l = static_cast<LINE*>( aItem );
869
870 for ( LINKED_ITEM* s : l->Links() )
871 Remove( s );
872
873 break;
874 }
875
876 case ITEM::VIA_T:
877 {
878 VIA* via = static_cast<VIA*>( aItem );
879
880 if( via->HasHole() )
881 Remove( via->Hole() );
882
883 Remove( static_cast<VIA*>( aItem ) );
884 break;
885 }
886
887 default:
888 break;
889 }
890}
891
892
893void NODE::Remove( LINE& aLine )
894{
895 // LINE does not have a separate remover, as LINEs are never truly a member of the tree
896 std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
897
898 for( LINKED_ITEM* li : segRefs )
899 {
900 if( li->OfKind( ITEM::SEGMENT_T ) )
901 Remove( static_cast<SEGMENT*>( li ) );
902 else if( li->OfKind( ITEM::ARC_T ) )
903 Remove( static_cast<ARC*>( li ) );
904 }
905
906 aLine.SetOwner( nullptr );
907 aLine.ClearLinks();
908}
909
910
911void NODE::followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
912 VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
913 bool& aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments )
914{
915 bool prevReversed = false;
916
917 const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
918
919 for( int count = 0 ; ; ++count )
920 {
921 const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
922 const JOINT* jt = FindJoint( p, aCurrent );
923
924 assert( jt );
925
926 aCorners[aPos] = jt->Pos();
927 aSegments[aPos] = aCurrent;
928 aArcReversed[aPos] = false;
929
930 if( aCurrent->Kind() == ITEM::ARC_T )
931 {
932 if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) )
933 || ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
934 aArcReversed[aPos] = true;
935 }
936
937 aPos += ( aScanDirection ? 1 : -1 );
938
939 if( count && guard == p )
940 {
941 if( aPos >= 0 && aPos < aLimit )
942 aSegments[aPos] = nullptr;
943
944 aGuardHit = true;
945 break;
946 }
947
948 bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
949
950 if( locked || !jt->IsLineCorner( aFollowLockedSegments ) || aPos < 0 || aPos == aLimit )
951 break;
952
953 aCurrent = jt->NextSegment( aCurrent, aFollowLockedSegments );
954
955 prevReversed = ( aCurrent && jt->Pos() == aCurrent->Anchor( aScanDirection ) );
956 }
957}
958
959
960const LINE NODE::AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex,
961 bool aStopAtLockedJoints, bool aFollowLockedSegments )
962{
963 const int MaxVerts = 1024 * 16;
964
965 std::array<VECTOR2I, MaxVerts + 1> corners;
966 std::array<LINKED_ITEM*, MaxVerts + 1> segs;
967 std::array<bool, MaxVerts + 1> arcReversed;
968
969 LINE pl;
970 bool guardHit = false;
971
972 int i_start = MaxVerts / 2;
973 int i_end = i_start + 1;
974
975 pl.SetWidth( aSeg->Width() );
976 pl.SetLayers( aSeg->Layers() );
977 pl.SetNet( aSeg->Net() );
978 pl.SetOwner( this );
979
980 followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
981 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
982
983 if( !guardHit )
984 {
985 followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
986 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
987 }
988
989 int n = 0;
990
991 LINKED_ITEM* prev_seg = nullptr;
992 bool originSet = false;
993
994 SHAPE_LINE_CHAIN& line = pl.Line();
995
996 for( int i = i_start + 1; i < i_end; i++ )
997 {
998 const VECTOR2I& p = corners[i];
999 LINKED_ITEM* li = segs[i];
1000
1001 if( !li || li->Kind() != ITEM::ARC_T )
1002 line.Append( p );
1003
1004 if( li && prev_seg != li )
1005 {
1006 if( li->Kind() == ITEM::ARC_T )
1007 {
1008 const ARC* arc = static_cast<const ARC*>( li );
1009 const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape() );
1010
1011 int nSegs = line.PointCount();
1012 VECTOR2I last = nSegs ? line.CPoint( -1 ) : VECTOR2I();
1013 ssize_t lastShape = nSegs ? line.ArcIndex( static_cast<ssize_t>( nSegs ) - 1 ) : -1;
1014
1015 line.Append( arcReversed[i] ? sa->Reversed() : *sa );
1016 }
1017
1018 pl.Link( li );
1019
1020 // latter condition to avoid loops
1021 if( li == aSeg && aOriginSegmentIndex && !originSet )
1022 {
1023 wxASSERT( n < line.SegmentCount() ||
1024 ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
1025 *aOriginSegmentIndex = line.PointCount() - 1;
1026 originSet = true;
1027 }
1028 }
1029
1030 prev_seg = li;
1031 }
1032
1033 // Remove duplicate verts, but do NOT remove colinear segments here!
1034 pl.Line().Simplify( false );
1035
1036 // TODO: maintain actual segment index under simplification system
1037 if( aOriginSegmentIndex && *aOriginSegmentIndex >= pl.SegmentCount() )
1038 *aOriginSegmentIndex = pl.SegmentCount() - 1;
1039
1040 assert( pl.SegmentCount() != 0 );
1041
1042 return pl;
1043}
1044
1045
1046void NODE::FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB )
1047{
1048 aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
1049 aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
1050}
1051
1052
1053int NODE::FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines )
1054{
1055 for( ITEM* item : aA.LinkList() )
1056 {
1057 if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
1058 {
1059 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1060 LINE line = AssembleLine( li );
1061
1062 if( !line.Layers().Overlaps( aB.Layers() ) )
1063 continue;
1064
1065 JOINT j_start, j_end;
1066
1067 FindLineEnds( line, j_start, j_end );
1068
1069 int id_start = line.CLine().Find( aA.Pos() );
1070 int id_end = line.CLine().Find( aB.Pos() );
1071
1072 if( id_end < id_start )
1073 std::swap( id_end, id_start );
1074
1075 if( id_start >= 0 && id_end >= 0 )
1076 {
1077 line.ClipVertexRange( id_start, id_end );
1078 aLines.push_back( line );
1079 }
1080 }
1081 }
1082
1083 return 0;
1084}
1085
1086
1088{
1089 const SEGMENT* locked_seg = nullptr;
1090 std::vector<VVIA*> vvias;
1091
1092 for( auto& jointPair : m_joints )
1093 {
1094 JOINT joint = jointPair.second;
1095
1096 if( joint.Layers().IsMultilayer() )
1097 continue;
1098
1099 int n_seg = 0, n_solid = 0, n_vias = 0;
1100 int prev_w = -1;
1101 int max_w = -1;
1102 bool is_width_change = false;
1103 bool is_locked = false;
1104
1105 for( const ITEM* item : joint.LinkList() )
1106 {
1107 if( item->OfKind( ITEM::VIA_T ) )
1108 {
1109 n_vias++;
1110 }
1111 else if( item->OfKind( ITEM::SOLID_T ) )
1112 {
1113 n_solid++;
1114 }
1115 else if( const auto t = dyn_cast<const PNS::SEGMENT*>( item ) )
1116 {
1117 int w = t->Width();
1118
1119 if( prev_w >= 0 && w != prev_w )
1120 {
1121 is_width_change = true;
1122 }
1123
1124 max_w = std::max( w, max_w );
1125 prev_w = w;
1126
1127 is_locked = t->IsLocked();
1128 locked_seg = t;
1129 }
1130 }
1131
1132 if( ( is_width_change || n_seg >= 3 || is_locked ) && n_solid == 0 && n_vias == 0 )
1133 {
1134 // fixme: the hull margin here is an ugly temporary workaround. The real fix
1135 // is to use octagons for via force propagation.
1136 vvias.push_back( new VVIA( joint.Pos(), joint.Layers().Start(),
1137 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1138 }
1139
1140 if( is_locked )
1141 {
1142 const VECTOR2I& secondPos = ( locked_seg->Seg().A == joint.Pos() ) ?
1143 locked_seg->Seg().B :
1144 locked_seg->Seg().A;
1145
1146 vvias.push_back( new VVIA( secondPos, joint.Layers().Start(),
1147 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1148 }
1149 }
1150
1151 for( auto vvia : vvias )
1152 {
1153 Add( ItemCast<VIA>( std::move( std::unique_ptr<VVIA>( vvia ) ) ) );
1154 }
1155}
1156
1157
1158const JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, int aNet ) const
1159{
1160 JOINT::HASH_TAG tag;
1161
1162 tag.net = aNet;
1163 tag.pos = aPos;
1164
1165 JOINT_MAP::const_iterator f = m_joints.find( tag ), end = m_joints.end();
1166
1167 if( f == end && !isRoot() )
1168 {
1169 end = m_root->m_joints.end();
1170 f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1171 }
1172
1173 if( f == end )
1174 return nullptr;
1175
1176 while( f != end )
1177 {
1178 if( f->second.Layers().Overlaps( aLayer ) )
1179 return &f->second;
1180
1181 ++f;
1182 }
1183
1184 return nullptr;
1185}
1186
1187
1188void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
1189{
1190 JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1191 jt.Lock( aLock );
1192}
1193
1194
1195JOINT& NODE::touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet )
1196{
1197 JOINT::HASH_TAG tag;
1198
1199 tag.pos = aPos;
1200 tag.net = aNet;
1201
1202 // try to find the joint in this node.
1203 JOINT_MAP::iterator f = m_joints.find( tag );
1204
1205 std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1206
1207 // not found and we are not root? find in the root and copy results here.
1208 if( f == m_joints.end() && !isRoot() )
1209 {
1210 range = m_root->m_joints.equal_range( tag );
1211
1212 for( f = range.first; f != range.second; ++f )
1213 m_joints.insert( *f );
1214 }
1215
1216 // now insert and combine overlapping joints
1217 JOINT jt( aPos, aLayers, aNet );
1218
1219 bool merged;
1220
1221 do
1222 {
1223 merged = false;
1224 range = m_joints.equal_range( tag );
1225
1226 if( range.first == m_joints.end() )
1227 break;
1228
1229 for( f = range.first; f != range.second; ++f )
1230 {
1231 if( aLayers.Overlaps( f->second.Layers() ) )
1232 {
1233 jt.Merge( f->second );
1234 m_joints.erase( f );
1235 merged = true;
1236 break;
1237 }
1238 }
1239 } while( merged );
1240
1241 return m_joints.insert( TagJointPair( tag, jt ) )->second;
1242}
1243
1244
1245void JOINT::Dump() const
1246{
1247 wxLogTrace( wxT( "PNS" ), wxT( "joint layers %d-%d, net %d, pos %s, links: %d" ),
1248 m_layers.Start(),
1249 m_layers.End(),
1250 m_tag.net,
1251 m_tag.pos.Format().c_str(),
1252 LinkCount() );
1253}
1254
1255
1256void NODE::linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere )
1257{
1258 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1259
1260 jt.Link( aWhere );
1261}
1262
1263
1264void NODE::unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, int aNet, ITEM* aWhere )
1265{
1266 // fixme: remove dangling joints
1267 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1268
1269 jt.Unlink( aWhere );
1270}
1271
1272
1273void NODE::Dump( bool aLong )
1274{
1275#if 0
1276 std::unordered_set<SEGMENT*> all_segs;
1278
1279 for( i = m_items.begin(); i != m_items.end(); i++ )
1280 {
1281 if( (*i)->GetKind() == ITEM::SEGMENT_T )
1282 all_segs.insert( static_cast<SEGMENT*>( *i ) );
1283 }
1284
1285 if( !isRoot() )
1286 {
1287 for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1288 {
1289 if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1290 all_segs.insert( static_cast<SEGMENT*>(*i) );
1291 }
1292 }
1293
1294 JOINT_MAP::iterator j;
1295
1296 if( aLong )
1297 {
1298 for( j = m_joints.begin(); j != m_joints.end(); ++j )
1299 {
1300 wxLogTrace( wxT( "PNS" ), wxT( "joint : %s, links : %d\n" ),
1301 j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1302 JOINT::LINKED_ITEMS::const_iterator k;
1303
1304 for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1305 {
1306 const ITEM* m_item = *k;
1307
1308 switch( m_item->GetKind() )
1309 {
1310 case ITEM::SEGMENT_T:
1311 {
1312 const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1313 wxLogTrace( wxT( "PNS" ), wxT( " -> seg %s %s\n" ),
1314 seg->GetSeg().A.Format().c_str(),
1315 seg->GetSeg().B.Format().c_str() );
1316 break;
1317 }
1318
1319 default:
1320 break;
1321 }
1322 }
1323 }
1324 }
1325
1326 int lines_count = 0;
1327
1328 while( !all_segs.empty() )
1329 {
1330 SEGMENT* s = *all_segs.begin();
1331 LINE* l = AssembleLine( s );
1332
1333 LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1334
1335 if( aLong )
1336 {
1337 wxLogTrace( wxT( "PNS" ), wxT( "Line: %s, net %d " ),
1338 l->GetLine().Format().c_str(), l->GetNet() );
1339 }
1340
1341 for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1342 {
1343 wxLogTrace( wxT( "PNS" ), wxT( "%s " ), (*j)->GetSeg().A.Format().c_str() );
1344
1345 if( j + 1 == seg_refs->end() )
1346 wxLogTrace( wxT( "PNS" ), wxT( "%s\n" ), (*j)->GetSeg().B.Format().c_str() );
1347
1348 all_segs.erase( *j );
1349 }
1350
1351 lines_count++;
1352 }
1353
1354 wxLogTrace( wxT( "PNS" ), wxT( "Local joints: %d, lines : %d \n" ),
1355 m_joints.size(), lines_count );
1356#endif
1357}
1358
1359
1361{
1362 if( isRoot() )
1363 return;
1364
1365 if( m_override.size() )
1366 aRemoved.reserve( m_override.size() );
1367
1368 if( m_index->Size() )
1369 aAdded.reserve( m_index->Size() );
1370
1371 for( ITEM* item : m_override )
1372 aRemoved.push_back( item );
1373
1374 for( ITEM* item : *m_index )
1375 aAdded.push_back( item );
1376}
1377
1378
1380{
1381 // copy the kids as the NODE destructor erases the item from the parent node.
1382 std::set<NODE*> kids = m_children;
1383
1384 for( NODE* node : kids )
1385 {
1386 node->releaseChildren();
1387 delete node;
1388 }
1389}
1390
1391
1393{
1394 if( !isRoot() )
1395 return;
1396
1397 std::vector<const ITEM*> cacheCheckItems;
1398 cacheCheckItems.reserve( m_garbageItems.size() );
1399
1400 for( ITEM* item : m_garbageItems )
1401 {
1402 if( !item->BelongsTo( this ) )
1403 delete item;
1404 }
1405
1406 m_garbageItems.clear();
1407
1408 if( m_ruleResolver )
1409 {
1410 m_ruleResolver->ClearCacheForItems( cacheCheckItems );
1411 }
1412}
1413
1414
1415void NODE::Commit( NODE* aNode )
1416{
1417 if( aNode->isRoot() )
1418 return;
1419
1420 for( ITEM* item : aNode->m_override )
1421 Remove( item );
1422
1423 for( ITEM* item : *aNode->m_index )
1424 {
1425 item->SetRank( -1 );
1426 item->Unmark();
1427 add( item );
1428 }
1429
1432}
1433
1434
1436{
1438}
1439
1440
1441void NODE::AllItemsInNet( int aNet, std::set<ITEM*>& aItems, int aKindMask )
1442{
1444
1445 if( l_cur )
1446 {
1447 for( ITEM* item : *l_cur )
1448 {
1449 if( item->OfKind( aKindMask ) && item->IsRoutable() )
1450 aItems.insert( item );
1451 }
1452 }
1453
1454 if( !isRoot() )
1455 {
1457
1458 if( l_root )
1459 {
1460 for( ITEM* item : *l_root )
1461 {
1462 if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1463 aItems.insert( item );
1464 }
1465 }
1466 }
1467}
1468
1469
1470void NODE::ClearRanks( int aMarkerMask )
1471{
1472 for( ITEM* item : *m_index )
1473 {
1474 item->SetRank( -1 );
1475 item->Mark( item->Marker() & ~aMarkerMask );
1476 }
1477}
1478
1479
1480void NODE::RemoveByMarker( int aMarker )
1481{
1482 std::vector<ITEM*> garbage;
1483
1484 for( ITEM* item : *m_index )
1485 {
1486 if( item->Marker() & aMarker )
1487 garbage.emplace_back( item );
1488 }
1489
1490 for( ITEM* item : garbage )
1491 Remove( item );
1492}
1493
1494
1496 int aNet )
1497{
1498 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1499
1500 if( !jtStart )
1501 return nullptr;
1502
1503 for( ITEM* item : jtStart->LinkList() )
1504 {
1505 if( item->OfKind( ITEM::SEGMENT_T ) )
1506 {
1507 SEGMENT* seg2 = (SEGMENT*)item;
1508
1509 const VECTOR2I a2( seg2->Seg().A );
1510 const VECTOR2I b2( seg2->Seg().B );
1511
1512 if( seg2->Layers().Start() == lr.Start()
1513 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1514 {
1515 return seg2;
1516 }
1517 }
1518 }
1519
1520 return nullptr;
1521}
1522
1523
1525{
1526 return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1527}
1528
1529
1531 int aNet )
1532{
1533 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1534
1535 if( !jtStart )
1536 return nullptr;
1537
1538 for( ITEM* item : jtStart->LinkList() )
1539 {
1540 if( item->OfKind( ITEM::ARC_T ) )
1541 {
1542 ARC* seg2 = static_cast<ARC*>( item );
1543
1544 const VECTOR2I a2( seg2->Anchor( 0 ) );
1545 const VECTOR2I b2( seg2->Anchor( 1 ) );
1546
1547 if( seg2->Layers().Start() == lr.Start()
1548 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1549 {
1550 return seg2;
1551 }
1552 }
1553 }
1554
1555 return nullptr;
1556}
1557
1558
1560{
1561 return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1562}
1563
1564
1565int NODE::QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints, LAYER_RANGE aLayerMask,
1566 int aKindMask )
1567{
1568 int n = 0;
1569
1570 aJoints.clear();
1571
1572 for( JOINT_MAP::value_type& j : m_joints )
1573 {
1574 if( !j.second.Layers().Overlaps( aLayerMask ) )
1575 continue;
1576
1577 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1578 {
1579 aJoints.push_back( &j.second );
1580 n++;
1581 }
1582 }
1583
1584 if( isRoot() )
1585 return n;
1586
1587 for( JOINT_MAP::value_type& j : m_root->m_joints )
1588 {
1589 if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1590 {
1591 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1592 {
1593 aJoints.push_back( &j.second );
1594 n++;
1595 }
1596 }
1597 }
1598
1599 return n;
1600}
1601
1602
1604{
1605 if( aParent->IsConnected() )
1606 {
1607 const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1609
1610 if( l_cur )
1611 {
1612 for( ITEM* item : *l_cur )
1613 {
1614 if( item->Parent() == aParent )
1615 return item;
1616 }
1617 }
1618 }
1619
1620 return nullptr;
1621}
1622
1623std::vector<ITEM*> NODE::FindItemsByZone( const ZONE* aParent )
1624{
1625 std::vector<ITEM*> ret;
1626
1627 for( ITEM* item : *m_index )
1628 {
1629 if( item->Parent() == aParent )
1630 ret.push_back( item );
1631 }
1632
1633 return ret;
1634}
1635}
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:71
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:128
bool Contains(const Vec &aPoint) const
Definition: box2.h:141
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
int Start() const
Definition: pns_layerset.h:82
bool IsMultilayer() const
Definition: pns_layerset.h:77
int End() const
Definition: pns_layerset.h:87
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
virtual VECTOR2I Anchor(int n) const override
Definition: pns_arc.h:99
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_arc.h:77
ITEM * ParentPadVia() const override
Definition: pns_hole.h:72
INDEX.
Definition: pns_index.h:46
void Remove(ITEM *aItem)
Removes an item from the spatial index.
Definition: pns_index.cpp:46
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
int Size() const
Returns number of items stored in the index.
Definition: pns_index.h:115
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor) const
Searches items in the index that are in proximity of aItem.
Definition: pns_index.h:141
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Returns list of all items in a given net.
Definition: pns_index.cpp:71
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
std::vector< ITEM * > & Items()
Definition: pns_itemset.h:87
const std::vector< ITEM * > & CItems() const
Definition: pns_itemset.h:88
Base class for PNS router board items.
Definition: pns_item.h:91
void SetLayers(const LAYER_RANGE &aLayers)
Definition: pns_item.h:192
virtual const std::string Format() const
Definition: pns_item.cpp:269
virtual void Unmark(int aMarker=-1) const
Definition: pns_item.h:226
void SetNet(int aNet)
Definition: pns_item.h:188
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:162
virtual void SetRank(int aRank)
Definition: pns_item.h:229
LAYER_RANGE m_layers
Definition: pns_item.h:277
virtual int Layer() const
Definition: pns_item.h:195
virtual int Net() const
Definition: pns_item.h:189
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:220
@ SOLID_T
Definition: pns_item.h:98
@ LINE_T
Definition: pns_item.h:99
@ SEGMENT_T
Definition: pns_item.h:101
const LAYER_RANGE & Layers() const
Definition: pns_item.h:191
bool OfKind(int aKindMask) const
Definition: pns_item.h:170
bool IsVirtual() const
Definition: pns_item.h:255
bool IsRoutable() const
Definition: pns_item.h:248
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:232
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:200
virtual HOLE * Hole() const
Definition: pns_item.h:264
bool Collide(const ITEM *aHead, const NODE *aNode, COLLISION_SEARCH_CONTEXT *aCtx=nullptr) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:237
virtual bool HasHole() const
Definition: pns_item.h:263
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:43
const std::vector< ITEM * > & LinkList() const
Definition: pns_joint.h:239
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:254
LINKED_ITEM * NextSegment(ITEM *aCurrent, bool aAllowLockedSegs=false) const
Definition: pns_joint.h:203
bool IsLineCorner(bool aAllowLockedSegs=false) const
Checks if a joint connects two segments of the same net, layer, and width.
Definition: pns_joint.h:101
void Lock(bool aLock=true)
Definition: pns_joint.h:288
void Link(ITEM *aItem)
Unlink a given board item from the joint (upon its removal from a NODE)
Definition: pns_joint.h:185
int Net() const override
Definition: pns_joint.h:234
void Dump() const
Definition: pns_node.cpp:1245
HASH_TAG m_tag
< hash tag for unordered_multimap
Definition: pns_joint.h:300
bool IsLocked() const
Definition: pns_joint.h:293
void Merge(const JOINT &aJoint)
Definition: pns_joint.h:266
bool Unlink(ITEM *aItem)
For trivial joints, return the segment adjacent to (aCurrent).
Definition: pns_joint.h:195
const VECTOR2I & Pos() const
Definition: pns_joint.h:229
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:144
void ClipVertexRange(int aStart, int aEnd)
Return the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:1100
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:136
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:135
VIA & Via()
Definition: pns_line.h:193
int SegmentCount() const
Definition: pns_line.h:138
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:148
bool EndsWithVia() const
Definition: pns_line.h:188
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:155
virtual int Width() const
Keep the router "world" - i.e.
Definition: pns_node.h:198
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:132
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1256
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1480
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:519
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
Definition: pns_node.cpp:1053
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:209
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:118
void followLine(LINKED_ITEM *aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool *aArcReversed, bool &aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments)
Definition: pns_node.cpp:911
void addSolid(SOLID *aSeg)
Definition: pns_node.cpp:484
bool Overrides(ITEM *aItem) const
Definition: pns_node.h:447
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:722
void rebuildJoint(const JOINT *aJoint, const ITEM *aItem)
Definition: pns_node.cpp:736
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1360
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:609
std::vector< std::unique_ptr< SHAPE > > m_edgeExclusions
Definition: pns_node.h:531
void releaseChildren()
Definition: pns_node.cpp:1379
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:513
void addVia(VIA *aVia)
Definition: pns_node.cpp:504
bool QueryEdgeExclusions(const VECTOR2I &aPos) const
Definition: pns_node.cpp:670
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1441
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:682
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:382
void addHole(HOLE *aHole)
Definition: pns_node.cpp:516
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:208
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:533
void Dump(bool aLong=false)
Definition: pns_node.cpp:1273
void releaseGarbage()
Definition: pns_node.cpp:1392
void addArc(ARC *aVia)
Definition: pns_node.cpp:638
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1046
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:236
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1565
void FixupVirtualVias()
Definition: pns_node.cpp:1087
std::set< OBSTACLE > OBSTACLES
Definition: pns_node.h:210
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:527
std::vector< ITEM * > FindItemsByZone(const ZONE *aParent)
Definition: pns_node.cpp:1623
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:522
OPT_OBSTACLE NearestObstacle(const LINE *aLine, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS())
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:272
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1188
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1530
void removeArcIndex(ARC *aVia)
Definition: pns_node.cpp:729
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
Touch a joint and links it to an m_item.
Definition: pns_node.cpp:1195
void AddEdgeExclusion(std::unique_ptr< SHAPE > aShape)
Definition: pns_node.cpp:664
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS()) const
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:241
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:525
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1264
bool isRoot() const
Definition: pns_node.h:493
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:781
void add(ITEM *aItem, bool aAllowRedundant=false)
Definition: pns_node.cpp:532
void KillChildren()
Definition: pns_node.cpp:1435
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:789
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:528
bool Add(std::unique_ptr< SEGMENT > &&aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:620
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet) const
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1158
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:520
ITEM * FindItemByParent(const BOARD_ITEM *aParent)
Definition: pns_node.cpp:1603
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:515
NODE * m_parent
node this node was branched from
Definition: pns_node.h:518
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1470
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > &&aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:801
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
void unlinkParent()
Definition: pns_node.cpp:168
void Commit(NODE *aNode)
Apply the changes from a given branch (aNode) to the root branch.
Definition: pns_node.cpp:1415
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:526
~NODE()
Return the expected clearance between items a and b.
Definition: pns_node.cpp:70
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:960
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1495
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition: pns_node.cpp:455
OBSTACLE_VISITOR(const ITEM *aItem)
Definition: pns_node.cpp:177
const NODE * m_node
node we are searching in (either root or a branch)
Definition: pns_node.h:184
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:182
bool visit(ITEM *aCandidate)
Definition: pns_node.cpp:192
void SetWorld(const NODE *aNode, const NODE *aOverride=nullptr)
Definition: pns_node.cpp:185
const NODE * m_override
node that overrides root entries
Definition: pns_node.h:185
void SetOwner(const ITEM_OWNER *aOwner)
Set the node that owns this item.
Definition: pns_item.h:70
bool BelongsTo(const ITEM_OWNER *aNode) const
Definition: pns_item.h:75
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
virtual void ClearCacheForItems(std::vector< const PNS::ITEM * > &aItems)
Definition: pns_node.h:158
virtual int ClearanceEpsilon() const
Definition: pns_node.h:161
virtual int Clearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true)=0
virtual const std::string Format() const override
Definition: pns_line.cpp:1286
const SEG & Seg() const
Definition: pns_segment.h:84
virtual bool HasHole() const override
Definition: pns_solid.h:122
virtual HOLE * Hole() const override
Definition: pns_solid.h:123
const VECTOR2I & Pos() const
Definition: pns_solid.h:88
const VECTOR2I & Pos() const
Definition: pns_via.h:111
virtual HOLE * Hole() const override
Definition: pns_via.h:185
virtual bool HasHole() const override
Definition: pns_via.h:184
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
SHAPE_ARC Reversed() const
Definition: shape_arc.cpp:587
const VECTOR2I & GetP1() const
Definition: shape_arc.h:113
const VECTOR2I & GetP0() const
Definition: shape_arc.h:112
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_ARC & Arc(size_t aArc) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int PointCount() const
Return the number of points (vertices) in this line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
int PathLength(const VECTOR2I &aP, int aIndex=-1) const
Compute the walk path length from the beginning of the line chain and the point aP belonging to our l...
size_t ArcCount() const
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:179
const std::string Format() const
Return the vector formatted as a string.
Definition: vector2d.h:378
Handle a list of polygons defining a copper zone.
Definition: zone.h:72
Push and Shove diff pair dimensions (gap) settings dialog.
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
Definition: pns_utils.cpp:384
#define PNS_HULL_MARGIN
Definition: pns_line.h:44
static std::vector< std::string > split(const std::string &aStr, const std::string &aDelim)
Split the input string into a vector of output strings.
Definition: string_utils.h:297
const COLLISION_SEARCH_OPTIONS options
Definition: pns_node.h:131
std::set< OBSTACLE > & obstacles
Definition: pns_node.h:130
std::set< ITEM * > * m_restrictedSet
Definition: pns_node.h:118
bool operator()(ITEM *aItem) override
Definition: pns_node.cpp:441
const VECTOR2I & m_point
Definition: pns_node.cpp:429
HIT_VISITOR(ITEM_SET &aTab, const VECTOR2I &aPoint)
Definition: pns_node.cpp:431
virtual ~HIT_VISITOR()
Definition: pns_node.cpp:437
ITEM_SET & m_items
Definition: pns_node.cpp:428
< Joints are hashed by their position, layers and net.
Definition: pns_joint.h:48
bool operator()(ITEM *aCandidate) override
Definition: pns_node.cpp:218
COLLISION_SEARCH_CONTEXT * m_ctx
Definition: pns_node.cpp:206
DEFAULT_OBSTACLE_VISITOR(COLLISION_SEARCH_CONTEXT *aCtx, const ITEM *aItem)
Definition: pns_node.cpp:208
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:84
int m_distFirst
... and the distance thereof
Definition: pns_node.h:90
int m_maxFanoutWidth
worst case (largest) width of the tracks connected to the item
Definition: pns_node.h:91
ITEM * m_head
Line we search collisions against.
Definition: pns_node.h:85
VECTOR2I m_ipFirst
First intersection between m_head and m_hull.
Definition: pns_node.h:87
ITEM * m_item
Item found to be colliding with m_head.
Definition: pns_node.h:86
Represent an intersection between two line segments.
VECTOR2I p
Point of intersection between our and their.
int index_their
index of the intersecting corner/segment in the 'their' (Intersect() method parameter) line.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588