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 if( !jt )
979 break;
980
981 aCorners[aPos] = jt->Pos();
982 aSegments[aPos] = aCurrent;
983 aArcReversed[aPos] = false;
984
985 if( aCurrent->Kind() == ITEM::ARC_T )
986 {
987 if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) )
988 || ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
989 {
990 aArcReversed[aPos] = true;
991 }
992 }
993
994 aPos += ( aScanDirection ? 1 : -1 );
995
996 if( count && guard == p )
997 {
998 if( aPos >= 0 && aPos < aLimit )
999 aSegments[aPos] = nullptr;
1000
1001 aGuardHit = true;
1002 break;
1003 }
1004
1005 bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
1006
1007 if( locked || !jt->IsLineCorner( aFollowLockedSegments ) || aPos < 0 || aPos == aLimit )
1008 break;
1009
1010 aCurrent = jt->NextSegment( aCurrent, aFollowLockedSegments );
1011
1012 prevReversed = ( aCurrent && jt->Pos() == aCurrent->Anchor( aScanDirection ) );
1013 }
1014}
1015
1016
1017const LINE NODE::AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex,
1018 bool aStopAtLockedJoints, bool aFollowLockedSegments )
1019{
1020 const int MaxVerts = 1024 * 16;
1021
1022 std::array<VECTOR2I, MaxVerts + 1> corners;
1023 std::array<LINKED_ITEM*, MaxVerts + 1> segs;
1024 std::array<bool, MaxVerts + 1> arcReversed;
1025
1026 LINE pl;
1027 bool guardHit = false;
1028
1029 int i_start = MaxVerts / 2;
1030 int i_end = i_start + 1;
1031
1032 pl.SetWidth( aSeg->Width() );
1033 pl.SetLayers( aSeg->Layers() );
1034 pl.SetNet( aSeg->Net() );
1035 pl.SetOwner( this );
1036
1037 followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1038 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1039
1040 if( !guardHit )
1041 {
1042 followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1043 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1044 }
1045
1046 int n = 0;
1047
1048 LINKED_ITEM* prev_seg = nullptr;
1049 bool originSet = false;
1050
1051 SHAPE_LINE_CHAIN& line = pl.Line();
1052
1053 for( int i = i_start + 1; i < i_end; i++ )
1054 {
1055 const VECTOR2I& p = corners[i];
1056 LINKED_ITEM* li = segs[i];
1057
1058 if( !li || li->Kind() != ITEM::ARC_T )
1059 line.Append( p );
1060
1061 if( li && prev_seg != li )
1062 {
1063 if( li->Kind() == ITEM::ARC_T )
1064 {
1065 const ARC* arc = static_cast<const ARC*>( li );
1066 const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape() );
1067
1068 int nSegs = line.PointCount();
1069 VECTOR2I last = nSegs ? line.CPoint( -1 ) : VECTOR2I();
1070 ssize_t lastShape = nSegs ? line.ArcIndex( static_cast<ssize_t>( nSegs ) - 1 ) : -1;
1071
1072 line.Append( arcReversed[i] ? sa->Reversed() : *sa );
1073 }
1074
1075 pl.Link( li );
1076
1077 // latter condition to avoid loops
1078 if( li == aSeg && aOriginSegmentIndex && !originSet )
1079 {
1080 wxASSERT( n < line.SegmentCount() ||
1081 ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
1082 *aOriginSegmentIndex = line.PointCount() - 1;
1083 originSet = true;
1084 }
1085 }
1086
1087 prev_seg = li;
1088 }
1089
1090 // Remove duplicate verts, but do NOT remove colinear segments here!
1092
1093 // TODO: maintain actual segment index under simplification system
1094 if( aOriginSegmentIndex && *aOriginSegmentIndex >= pl.SegmentCount() )
1095 *aOriginSegmentIndex = pl.SegmentCount() - 1;
1096
1097 wxASSERT_MSG( pl.SegmentCount() != 0, "assembled line should never be empty" );
1098
1099 return pl;
1100}
1101
1102
1103void NODE::FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB )
1104{
1105 aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
1106 aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
1107}
1108
1109
1110int NODE::FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines )
1111{
1112 for( ITEM* item : aA.LinkList() )
1113 {
1114 if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
1115 {
1116 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1117 LINE line = AssembleLine( li );
1118
1119 if( !line.Layers().Overlaps( aB.Layers() ) )
1120 continue;
1121
1122 JOINT j_start, j_end;
1123
1124 FindLineEnds( line, j_start, j_end );
1125
1126 int id_start = line.CLine().Find( aA.Pos() );
1127 int id_end = line.CLine().Find( aB.Pos() );
1128
1129 if( id_end < id_start )
1130 std::swap( id_end, id_start );
1131
1132 if( id_start >= 0 && id_end >= 0 )
1133 {
1134 line.ClipVertexRange( id_start, id_end );
1135 aLines.push_back( line );
1136 }
1137 }
1138 }
1139
1140 return 0;
1141}
1142
1143
1145{
1146 const SEGMENT* locked_seg = nullptr;
1147 std::vector<VVIA*> vvias;
1148
1149 for( auto& jointPair : m_joints )
1150 {
1151 JOINT joint = jointPair.second;
1152
1153 if( joint.Layers().IsMultilayer() )
1154 continue;
1155
1156 int n_seg = 0, n_solid = 0, n_vias = 0;
1157 int prev_w = -1;
1158 int max_w = -1;
1159 bool is_width_change = false;
1160 bool is_locked = false;
1161
1162 for( const ITEM* item : joint.LinkList() )
1163 {
1164 if( item->OfKind( ITEM::VIA_T ) )
1165 {
1166 n_vias++;
1167 }
1168 else if( item->OfKind( ITEM::SOLID_T ) )
1169 {
1170 n_solid++;
1171 }
1172 else if( const auto t = dyn_cast<const PNS::SEGMENT*>( item ) )
1173 {
1174 int w = t->Width();
1175
1176 if( prev_w >= 0 && w != prev_w )
1177 {
1178 is_width_change = true;
1179 }
1180
1181 max_w = std::max( w, max_w );
1182 prev_w = w;
1183
1184 is_locked = t->IsLocked();
1185 locked_seg = t;
1186 }
1187 }
1188
1189 if( ( is_width_change || n_seg >= 3 || is_locked ) && n_solid == 0 && n_vias == 0 )
1190 {
1191 // fixme: the hull margin here is an ugly temporary workaround. The real fix
1192 // is to use octagons for via force propagation.
1193 vvias.push_back( new VVIA( joint.Pos(), joint.Layers().Start(),
1194 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1195 }
1196
1197 if( is_locked )
1198 {
1199 const VECTOR2I& secondPos = ( locked_seg->Seg().A == joint.Pos() ) ?
1200 locked_seg->Seg().B :
1201 locked_seg->Seg().A;
1202
1203 vvias.push_back( new VVIA( secondPos, joint.Layers().Start(),
1204 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1205 }
1206 }
1207
1208 for( auto vvia : vvias )
1209 {
1210 Add( ItemCast<VIA>( std::move( std::unique_ptr<VVIA>( vvia ) ) ) );
1211 }
1212}
1213
1214
1215const JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, NET_HANDLE aNet ) const
1216{
1217 JOINT::HASH_TAG tag;
1218
1219 tag.net = aNet;
1220 tag.pos = aPos;
1221
1222 JOINT_MAP::const_iterator f = m_joints.find( tag ), end = m_joints.end();
1223
1224 if( f == end && !isRoot() )
1225 {
1226 end = m_root->m_joints.end();
1227 f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1228 }
1229
1230 if( f == end )
1231 return nullptr;
1232
1233 while( f != end )
1234 {
1235 if( f->second.Layers().Overlaps( aLayer ) )
1236 return &f->second;
1237
1238 ++f;
1239 }
1240
1241 return nullptr;
1242}
1243
1244
1245void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
1246{
1247 JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1248 jt.Lock( aLock );
1249}
1250
1251
1252JOINT& NODE::touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet )
1253{
1254 JOINT::HASH_TAG tag;
1255
1256 tag.pos = aPos;
1257 tag.net = aNet;
1258
1259 // try to find the joint in this node.
1260 JOINT_MAP::iterator f = m_joints.find( tag );
1261
1262 std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1263
1264 // not found and we are not root? find in the root and copy results here.
1265 if( f == m_joints.end() && !isRoot() )
1266 {
1267 range = m_root->m_joints.equal_range( tag );
1268
1269 for( f = range.first; f != range.second; ++f )
1270 m_joints.insert( *f );
1271 }
1272
1273 // now insert and combine overlapping joints
1274 JOINT jt( aPos, aLayers, aNet );
1275
1276 bool merged;
1277
1278 do
1279 {
1280 merged = false;
1281 range = m_joints.equal_range( tag );
1282
1283 if( range.first == m_joints.end() )
1284 break;
1285
1286 for( f = range.first; f != range.second; ++f )
1287 {
1288 if( aLayers.Overlaps( f->second.Layers() ) )
1289 {
1290 jt.Merge( f->second );
1291 m_joints.erase( f );
1292 merged = true;
1293 break;
1294 }
1295 }
1296 } while( merged );
1297
1298 return m_joints.insert( TagJointPair( tag, jt ) )->second;
1299}
1300
1301
1302void JOINT::Dump() const
1303{
1304 wxLogTrace( wxT( "PNS" ), wxT( "joint layers %d-%d, net %d, pos %s, links: %d" ),
1305 m_layers.Start(),
1306 m_layers.End(),
1307 m_tag.net,
1308 m_tag.pos.Format().c_str(),
1309 LinkCount() );
1310}
1311
1312
1313void NODE::linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet,
1314 ITEM* aWhere )
1315{
1316 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1317
1318 jt.Link( aWhere );
1319}
1320
1321
1322void NODE::unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet,
1323 ITEM* aWhere )
1324{
1325 // fixme: remove dangling joints
1326 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1327
1328 jt.Unlink( aWhere );
1329}
1330
1331
1332void NODE::Dump( bool aLong )
1333{
1334#if 0
1335 std::unordered_set<SEGMENT*> all_segs;
1337
1338 for( i = m_items.begin(); i != m_items.end(); i++ )
1339 {
1340 if( (*i)->GetKind() == ITEM::SEGMENT_T )
1341 all_segs.insert( static_cast<SEGMENT*>( *i ) );
1342 }
1343
1344 if( !isRoot() )
1345 {
1346 for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1347 {
1348 if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1349 all_segs.insert( static_cast<SEGMENT*>(*i) );
1350 }
1351 }
1352
1353 JOINT_MAP::iterator j;
1354
1355 if( aLong )
1356 {
1357 for( j = m_joints.begin(); j != m_joints.end(); ++j )
1358 {
1359 wxLogTrace( wxT( "PNS" ), wxT( "joint : %s, links : %d\n" ),
1360 j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1361 JOINT::LINKED_ITEMS::const_iterator k;
1362
1363 for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1364 {
1365 const ITEM* m_item = *k;
1366
1367 switch( m_item->GetKind() )
1368 {
1369 case ITEM::SEGMENT_T:
1370 {
1371 const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1372 wxLogTrace( wxT( "PNS" ), wxT( " -> seg %s %s\n" ),
1373 seg->GetSeg().A.Format().c_str(),
1374 seg->GetSeg().B.Format().c_str() );
1375 break;
1376 }
1377
1378 default:
1379 break;
1380 }
1381 }
1382 }
1383 }
1384
1385 int lines_count = 0;
1386
1387 while( !all_segs.empty() )
1388 {
1389 SEGMENT* s = *all_segs.begin();
1390 LINE* l = AssembleLine( s );
1391
1392 LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1393
1394 if( aLong )
1395 {
1396 wxLogTrace( wxT( "PNS" ), wxT( "Line: %s, net %d " ),
1397 l->GetLine().Format().c_str(), l->GetNet() );
1398 }
1399
1400 for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1401 {
1402 wxLogTrace( wxT( "PNS" ), wxT( "%s " ), (*j)->GetSeg().A.Format().c_str() );
1403
1404 if( j + 1 == seg_refs->end() )
1405 wxLogTrace( wxT( "PNS" ), wxT( "%s\n" ), (*j)->GetSeg().B.Format().c_str() );
1406
1407 all_segs.erase( *j );
1408 }
1409
1410 lines_count++;
1411 }
1412
1413 wxLogTrace( wxT( "PNS" ), wxT( "Local joints: %d, lines : %d \n" ),
1414 m_joints.size(), lines_count );
1415#endif
1416}
1417
1418
1420{
1421 if( isRoot() )
1422 return;
1423
1424 if( m_override.size() )
1425 aRemoved.reserve( m_override.size() );
1426
1427 if( m_index->Size() )
1428 aAdded.reserve( m_index->Size() );
1429
1430 for( ITEM* item : m_override )
1431 aRemoved.push_back( item );
1432
1433 for( ITEM* item : *m_index )
1434 aAdded.push_back( item );
1435}
1436
1437
1439{
1440 // copy the kids as the NODE destructor erases the item from the parent node.
1441 std::set<NODE*> kids = m_children;
1442
1443 for( NODE* node : kids )
1444 {
1445 node->releaseChildren();
1446 delete node;
1447 }
1448}
1449
1450
1452{
1453 if( !isRoot() )
1454 return;
1455
1456 std::vector<const ITEM*> cacheCheckItems;
1457 cacheCheckItems.reserve( m_garbageItems.size() );
1458
1459 for( ITEM* item : m_garbageItems )
1460 {
1461 if( !item->BelongsTo( this ) )
1462 delete item;
1463 }
1464
1465 m_garbageItems.clear();
1466
1467 if( m_ruleResolver )
1468 {
1469 m_ruleResolver->ClearCacheForItems( cacheCheckItems );
1470 }
1471}
1472
1473
1474void NODE::Commit( NODE* aNode )
1475{
1476 if( aNode->isRoot() )
1477 return;
1478
1479 for( ITEM* item : aNode->m_override )
1480 Remove( item );
1481
1482 for( ITEM* item : *aNode->m_index )
1483 {
1484 if( item->HasHole() )
1485 {
1486 item->Hole()->SetOwner( item );
1487 }
1488
1489 item->SetRank( -1 );
1490 item->Unmark();
1491 add( item );
1492 }
1493
1496}
1497
1498
1500{
1502}
1503
1504
1505void NODE::AllItemsInNet( NET_HANDLE aNet, std::set<ITEM*>& aItems, int aKindMask )
1506{
1508
1509 if( l_cur )
1510 {
1511 for( ITEM* item : *l_cur )
1512 {
1513 if( item->OfKind( aKindMask ) && item->IsRoutable() )
1514 aItems.insert( item );
1515 }
1516 }
1517
1518 if( !isRoot() )
1519 {
1521
1522 if( l_root )
1523 {
1524 for( ITEM* item : *l_root )
1525 {
1526 if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1527 aItems.insert( item );
1528 }
1529 }
1530 }
1531}
1532
1533
1534void NODE::ClearRanks( int aMarkerMask )
1535{
1536 for( ITEM* item : *m_index )
1537 {
1538 item->SetRank( -1 );
1539 item->Mark( item->Marker() & ~aMarkerMask );
1540 }
1541}
1542
1543
1544void NODE::RemoveByMarker( int aMarker )
1545{
1546 std::vector<ITEM*> garbage;
1547
1548 for( ITEM* item : *m_index )
1549 {
1550 if( item->Marker() & aMarker )
1551 garbage.emplace_back( item );
1552 }
1553
1554 for( ITEM* item : garbage )
1555 Remove( item );
1556}
1557
1558
1560 NET_HANDLE aNet )
1561{
1562 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1563
1564 if( !jtStart )
1565 return nullptr;
1566
1567 for( ITEM* item : jtStart->LinkList() )
1568 {
1569 if( item->OfKind( ITEM::SEGMENT_T ) )
1570 {
1571 SEGMENT* seg2 = (SEGMENT*)item;
1572
1573 const VECTOR2I a2( seg2->Seg().A );
1574 const VECTOR2I b2( seg2->Seg().B );
1575
1576 if( seg2->Layers().Start() == lr.Start()
1577 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1578 {
1579 return seg2;
1580 }
1581 }
1582 }
1583
1584 return nullptr;
1585}
1586
1587
1589{
1590 return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1591}
1592
1593
1595 NET_HANDLE aNet )
1596{
1597 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1598
1599 if( !jtStart )
1600 return nullptr;
1601
1602 for( ITEM* item : jtStart->LinkList() )
1603 {
1604 if( item->OfKind( ITEM::ARC_T ) )
1605 {
1606 ARC* seg2 = static_cast<ARC*>( item );
1607
1608 const VECTOR2I a2( seg2->Anchor( 0 ) );
1609 const VECTOR2I b2( seg2->Anchor( 1 ) );
1610
1611 if( seg2->Layers().Start() == lr.Start()
1612 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1613 {
1614 return seg2;
1615 }
1616 }
1617 }
1618
1619 return nullptr;
1620}
1621
1622
1624{
1625 return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1626}
1627
1628
1629int NODE::QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints, LAYER_RANGE aLayerMask,
1630 int aKindMask )
1631{
1632 int n = 0;
1633
1634 aJoints.clear();
1635
1636 for( JOINT_MAP::value_type& j : m_joints )
1637 {
1638 if( !j.second.Layers().Overlaps( aLayerMask ) )
1639 continue;
1640
1641 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1642 {
1643 aJoints.push_back( &j.second );
1644 n++;
1645 }
1646 }
1647
1648 if( isRoot() )
1649 return n;
1650
1651 for( JOINT_MAP::value_type& j : m_root->m_joints )
1652 {
1653 if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1654 {
1655 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1656 {
1657 aJoints.push_back( &j.second );
1658 n++;
1659 }
1660 }
1661 }
1662
1663 return n;
1664}
1665
1666
1668{
1669 if( aParent->IsConnected() )
1670 {
1671 const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1672 INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( cItem->GetNet() );
1673
1674 if( l_cur )
1675 {
1676 for( ITEM* item : *l_cur )
1677 {
1678 if( item->Parent() == aParent )
1679 return item;
1680 }
1681 }
1682 }
1683
1684 return nullptr;
1685}
1686
1687std::vector<ITEM*> NODE::FindItemsByZone( const ZONE* aParent )
1688{
1689 std::vector<ITEM*> ret;
1690
1691 for( ITEM* item : *m_index )
1692 {
1693 if( item->Parent() == aParent )
1694 ret.push_back( item );
1695 }
1696
1697 return ret;
1698}
1699}
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:79
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:136
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:273
NET_HANDLE Net() const override
Definition: pns_joint.h:268
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:288
LINKED_ITEM * NextSegment(ITEM *aCurrent, bool aAllowLockedSegs=false) const
Definition: pns_joint.h:226
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:322
void Link(ITEM *aItem)
Unlink a given board item from the joint (upon its removal from a NODE)
Definition: pns_joint.h:208
void Dump() const
Definition: pns_node.cpp:1302
HASH_TAG m_tag
< hash tag for unordered_multimap
Definition: pns_joint.h:334
bool IsLocked() const
Definition: pns_joint.h:327
void Merge(const JOINT &aJoint)
Definition: pns_joint.h:300
bool Unlink(ITEM *aItem)
For trivial joints, return the segment adjacent to (aCurrent).
Definition: pns_joint.h:218
const VECTOR2I & Pos() const
Definition: pns_joint.h:263
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:1544
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:1559
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:1110
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:1419
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:1438
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:1215
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:1332
void releaseGarbage()
Definition: pns_node.cpp:1451
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:1103
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:1252
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:1629
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:1144
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:1687
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:1505
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:1245
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:1322
void add(ITEM *aItem, bool aAllowRedundant=false)
Definition: pns_node.cpp:575
void KillChildren()
Definition: pns_node.cpp:1499
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:1667
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:1594
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:1534
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:1474
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:1313
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:1017
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:663
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:421
Handle a list of polygons defining a copper zone.
Definition: zone.h:73
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< int32_t > VECTOR2I
Definition: vector2d.h:676