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