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{
412 OBSTACLES obs;
414
415 opts.m_kindMask = aKindMask;
416 opts.m_limitCount = 1;
417
418 if( aItemA->Kind() == ITEM::LINE_T )
419 {
420 int n = 0;
421 const LINE* line = static_cast<const LINE*>( aItemA );
422 const SHAPE_LINE_CHAIN& l = line->CLine();
423
424 for( int i = 0; i < l.SegmentCount(); i++ )
425 {
426 // Note: Clearances between &s and other items are cached,
427 // which means they'll be the same for all segments in the line.
428 // Disabling the cache will lead to slowness.
429
430 const SEGMENT s( *line, l.CSegment( i ) );
431 n += QueryColliding( &s, obs, opts );
432
433 if( n )
434 return OPT_OBSTACLE( *obs.begin() );
435 }
436
437 if( line->EndsWithVia() )
438 {
439 n += QueryColliding( &line->Via(), obs, opts );
440
441 if( n )
442 return OPT_OBSTACLE( *obs.begin() );
443 }
444 }
445 else if( QueryColliding( aItemA, obs, opts ) > 0 )
446 {
447 return OPT_OBSTACLE( *obs.begin() );
448 }
449
450 return OPT_OBSTACLE();
451}
452
453
455{
458
459 HIT_VISITOR( ITEM_SET& aTab, const VECTOR2I& aPoint ) :
460 OBSTACLE_VISITOR( nullptr ),
461 m_items( aTab ),
462 m_point( aPoint )
463 {}
464
465 virtual ~HIT_VISITOR()
466 {
467 }
468
469 bool operator()( ITEM* aItem ) override
470 {
471 SHAPE_CIRCLE cp( m_point, 0 );
472
473 int cl = 0;
474
475 if( aItem->Shape()->Collide( &cp, cl ) )
476 m_items.Add( aItem );
477
478 return true;
479 }
480};
481
482
483const ITEM_SET NODE::HitTest( const VECTOR2I& aPoint ) const
484{
485 ITEM_SET items;
486
487 // fixme: we treat a point as an infinitely small circle - this is inefficient.
488 SHAPE_CIRCLE s( aPoint, 0 );
489 HIT_VISITOR visitor( items, aPoint );
490 visitor.SetWorld( this, nullptr );
491
492 m_index->Query( &s, m_maxClearance, visitor );
493
494 if( !isRoot() ) // fixme: could be made cleaner
495 {
496 ITEM_SET items_root;
497 visitor.SetWorld( m_root, nullptr );
498 HIT_VISITOR visitor_root( items_root, aPoint );
499 m_root->m_index->Query( &s, m_maxClearance, visitor_root );
500
501 for( ITEM* item : items_root.Items() )
502 {
503 if( !Overrides( item ) )
504 items.Add( item );
505 }
506 }
507
508 return items;
509}
510
511
512void NODE::addSolid( SOLID* aSolid )
513{
514 if( aSolid->HasHole() )
515 {
516 assert( aSolid->Hole()->BelongsTo( aSolid ) );
517 addHole( aSolid->Hole() );
518 }
519
520 if( aSolid->IsRoutable() )
521 linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
522
523 aSolid->SetOwner( this );
524 m_index->Add( aSolid );
525}
526
527
528void NODE::Add( std::unique_ptr< SOLID >&& aSolid )
529{
530 aSolid->SetOwner( this );
531 addSolid( aSolid.release() );
532}
533
534
535void NODE::addVia( VIA* aVia )
536{
537 if( aVia->HasHole() )
538 {
539 if( ! aVia->Hole()->BelongsTo( aVia ) )
540 {
541 assert( false );
542 }
543 addHole( aVia->Hole() );
544 }
545
546 linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
547 aVia->SetOwner( this );
548
549 m_index->Add( aVia );
550}
551
552
553void NODE::addHole( HOLE* aHole )
554{
555 // do we need holes in the connection graph?
556 //linkJoint( aHole->Pos(), aHole->Layers(), aHole->Net(), aHole );
557
558 aHole->SetOwner( this );
559 m_index->Add( aHole );
560}
561
562
563void NODE::Add( std::unique_ptr< VIA >&& aVia )
564{
565 addVia( aVia.release() );
566}
567
568
569void NODE::add( ITEM* aItem, bool aAllowRedundant )
570{
571 switch( aItem->Kind() )
572 {
573 case ITEM::ARC_T:
574 addArc( static_cast<ARC*>( aItem ) );
575 break;
576 case ITEM::SEGMENT_T:
577 addSegment( static_cast<SEGMENT*>( aItem ) );
578 break;
579 case ITEM::VIA_T:
580 addVia( static_cast<VIA*>( aItem ) );
581 break;
582 case ITEM::SOLID_T:
583 addSolid( static_cast<SOLID*>( aItem ) );
584 break;
585 case ITEM::HOLE_T:
586 // added by parent VIA_T or SOLID_T (pad)
587 break;
588 default:
589 assert( false );
590 }
591}
592
593
594void NODE::Add( LINE& aLine, bool aAllowRedundant )
595{
596 assert( !aLine.IsLinked() );
597
598 SHAPE_LINE_CHAIN& l = aLine.Line();
599
600 for( size_t i = 0; i < l.ArcCount(); i++ )
601 {
602 auto s = l.Arc( i );
603 ARC* rarc;
604
605 if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(),
606 aLine.Net() ) ) )
607 {
608 aLine.Link( rarc );
609 }
610 else
611 {
612 auto newarc = std::make_unique< ARC >( aLine, s );
613 aLine.Link( newarc.get() );
614 Add( std::move( newarc ), true );
615 }
616 }
617
618 for( int i = 0; i < l.SegmentCount(); i++ )
619 {
620 if( l.IsArcSegment( i ) )
621 continue;
622
623 SEG s = l.CSegment( i );
624
625 if( s.A != s.B )
626 {
627 SEGMENT* rseg;
628
629 if( !aAllowRedundant && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(),
630 aLine.Net() ) ) )
631 {
632 // another line could be referencing this segment too :(
633 aLine.Link( rseg );
634 }
635 else
636 {
637 std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
638 aLine.Link( newseg.get() );
639 Add( std::move( newseg ), true );
640 }
641 }
642 }
643}
644
645
647{
648 aSeg->SetOwner( this );
649
650 linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
651 linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
652
653 m_index->Add( aSeg );
654}
655
656
657bool NODE::Add( std::unique_ptr< SEGMENT >&& aSegment, bool aAllowRedundant )
658{
659 if( aSegment->Seg().A == aSegment->Seg().B )
660 {
661 wxLogTrace( wxT( "PNS" ),
662 wxT( "attempting to add a segment with same end coordinates, ignoring." ) );
663 return false;
664 }
665
666 if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
667 return false;
668
669 addSegment( aSegment.release() );
670
671 return true;
672}
673
674
675void NODE::addArc( ARC* aArc )
676{
677 aArc->SetOwner( this );
678
679 linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
680 linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
681
682 m_index->Add( aArc );
683}
684
685
686bool NODE::Add( std::unique_ptr< ARC >&& aArc, bool aAllowRedundant )
687{
688 const SHAPE_ARC& arc = aArc->CArc();
689
690 if( !aAllowRedundant && findRedundantArc( arc.GetP0(), arc.GetP1(), aArc->Layers(),
691 aArc->Net() ) )
692 {
693 return false;
694 }
695
696 addArc( aArc.release() );
697 return true;
698}
699
700
701void NODE::AddEdgeExclusion( std::unique_ptr<SHAPE> aShape )
702{
703 m_edgeExclusions.push_back( std::move( aShape ) );
704}
705
706
707bool NODE::QueryEdgeExclusions( const VECTOR2I& aPos ) const
708{
709 for( const std::unique_ptr<SHAPE>& edgeExclusion : m_edgeExclusions )
710 {
711 if( edgeExclusion->Collide( aPos ) )
712 return true;
713 }
714
715 return false;
716}
717
718
719void NODE::doRemove( ITEM* aItem )
720{
721 // case 1: removing an item that is stored in the root node from any branch:
722 // mark it as overridden, but do not remove
723 if( aItem->BelongsTo( m_root ) && !isRoot() )
724 {
725 m_override.insert( aItem );
726
727 if( aItem->HasHole() )
728 m_override.insert( aItem->Hole() );
729 }
730
731 // case 2: the item belongs to this branch or a parent, non-root branch,
732 // or the root itself and we are the root: remove from the index
733 else if( !aItem->BelongsTo( m_root ) || isRoot() )
734 {
735 m_index->Remove( aItem );
736
737 if( aItem->HasHole() )
738 m_index->Remove( aItem->Hole() );
739 }
740
741 // the item belongs to this particular branch: un-reference it
742 if( aItem->BelongsTo( this ) )
743 {
744 aItem->SetOwner( nullptr );
745
746 m_root->m_garbageItems.insert( aItem );
747
748 HOLE *hole = aItem->Hole();
749
750 if( hole )
751 {
752 m_index->Remove( hole ); // hole is not directly owned by NODE but by the parent SOLID/VIA.
753 hole->SetOwner( aItem );
754 }
755 }
756}
757
758
760{
761 unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
762 unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
763}
764
765
767{
768 unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
769 unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
770}
771
772
773void NODE::rebuildJoint( const JOINT* aJoint, const ITEM* aItem )
774{
775 // We have to split a single joint (associated with a via or a pad, binding together multiple
776 // layers) into multiple independent joints. As I'm a lazy bastard, I simply delete the
777 // via/solid and all its links and re-insert them.
778
779 std::vector<ITEM*> links( aJoint->LinkList() );
780 JOINT::HASH_TAG tag;
781 NET_HANDLE net = aItem->Net();
782
783 tag.net = net;
784 tag.pos = aJoint->Pos();
785
786 bool split;
787
788 do
789 {
790 split = false;
791 auto range = m_joints.equal_range( tag );
792
793 if( range.first == m_joints.end() )
794 break;
795
796 // find and remove all joints containing the via to be removed
797
798 for( auto f = range.first; f != range.second; ++f )
799 {
800 if( aItem->LayersOverlap( &f->second ) )
801 {
802 m_joints.erase( f );
803 split = true;
804 break;
805 }
806 }
807 } while( split );
808
809 // and re-link them, using the former via's link list
810 for( ITEM* link : links )
811 {
812 if( link != aItem )
813 linkJoint( tag.pos, link->Layers(), net, link );
814 }
815}
816
817
819{
820 const JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
821 assert( jt );
822 rebuildJoint( jt, aVia );
823}
824
825
827{
828 if( !aSolid->IsRoutable() )
829 return;
830
831 // fixme: redundant code
832 const JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
833 assert( jt );
834 rebuildJoint( jt, aSolid );
835}
836
837
838void NODE::Replace( ITEM* aOldItem, std::unique_ptr< ITEM >&& aNewItem )
839{
840 Remove( aOldItem );
841 add( aNewItem.release() );
842}
843
844
845void NODE::Replace( LINE& aOldLine, LINE& aNewLine )
846{
847 Remove( aOldLine );
848 Add( aNewLine );
849}
850
851
852void NODE::Remove( SOLID* aSolid )
853{
854 removeSolidIndex( aSolid );
855 doRemove( aSolid );
856}
857
858
859void NODE::Remove( VIA* aVia )
860{
861 removeViaIndex( aVia );
862 doRemove( aVia );
863
864 if( !aVia->Owner() )
865 {
866 assert( aVia->Hole()->BelongsTo( aVia ) );
867 }
868}
869
870
871void NODE::Remove( SEGMENT* aSegment )
872{
873 removeSegmentIndex( aSegment );
874 doRemove( aSegment );
875}
876
877
878void NODE::Remove( ARC* aArc )
879{
880 removeArcIndex( aArc );
881 doRemove( aArc );
882}
883
884
885void NODE::Remove( ITEM* aItem )
886{
887 switch( aItem->Kind() )
888 {
889 case ITEM::ARC_T:
890 Remove( static_cast<ARC*>( aItem ) );
891 break;
892
893 case ITEM::SOLID_T:
894 {
895 SOLID* solid = static_cast<SOLID*>( aItem );
896
897 if( solid->HasHole() )
898 {
899 Remove( solid->Hole() );
900 solid->Hole()->SetOwner( solid );
901 }
902
903 Remove( static_cast<SOLID*>( aItem ) );
904 break;
905 }
906
907 case ITEM::SEGMENT_T:
908 Remove( static_cast<SEGMENT*>( aItem ) );
909 break;
910
911 case ITEM::LINE_T:
912 {
913 LINE* l = static_cast<LINE*>( aItem );
914
915 for ( LINKED_ITEM* s : l->Links() )
916 Remove( s );
917
918 break;
919 }
920
921 case ITEM::VIA_T:
922 {
923 VIA* via = static_cast<VIA*>( aItem );
924
925 if( via->HasHole() )
926 {
927 Remove( via->Hole() );
928 via->Hole()->SetOwner( via );
929 }
930
931 Remove( static_cast<VIA*>( aItem ) );
932 break;
933 }
934
935 default:
936 break;
937 }
938}
939
940
941void NODE::Remove( LINE& aLine )
942{
943 // LINE does not have a separate remover, as LINEs are never truly a member of the tree
944 std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
945
946 for( LINKED_ITEM* li : segRefs )
947 {
948 if( li->OfKind( ITEM::SEGMENT_T ) )
949 Remove( static_cast<SEGMENT*>( li ) );
950 else if( li->OfKind( ITEM::ARC_T ) )
951 Remove( static_cast<ARC*>( li ) );
952 }
953
954 aLine.SetOwner( nullptr );
955 aLine.ClearLinks();
956}
957
958
959void NODE::followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
960 VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
961 bool& aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments )
962{
963 bool prevReversed = false;
964
965 const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
966
967 for( int count = 0 ; ; ++count )
968 {
969 const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
970 const JOINT* jt = FindJoint( p, aCurrent );
971
972 wxCHECK( jt, /* void */ );
973
974 aCorners[aPos] = jt->Pos();
975 aSegments[aPos] = aCurrent;
976 aArcReversed[aPos] = false;
977
978 if( aCurrent->Kind() == ITEM::ARC_T )
979 {
980 if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) )
981 || ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
982 aArcReversed[aPos] = true;
983 }
984
985 aPos += ( aScanDirection ? 1 : -1 );
986
987 if( count && guard == p )
988 {
989 if( aPos >= 0 && aPos < aLimit )
990 aSegments[aPos] = nullptr;
991
992 aGuardHit = true;
993 break;
994 }
995
996 bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
997
998 if( locked || !jt->IsLineCorner( aFollowLockedSegments ) || aPos < 0 || aPos == aLimit )
999 break;
1000
1001 aCurrent = jt->NextSegment( aCurrent, aFollowLockedSegments );
1002
1003 prevReversed = ( aCurrent && jt->Pos() == aCurrent->Anchor( aScanDirection ) );
1004 }
1005}
1006
1007
1008const LINE NODE::AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex,
1009 bool aStopAtLockedJoints, bool aFollowLockedSegments )
1010{
1011 const int MaxVerts = 1024 * 16;
1012
1013 std::array<VECTOR2I, MaxVerts + 1> corners;
1014 std::array<LINKED_ITEM*, MaxVerts + 1> segs;
1015 std::array<bool, MaxVerts + 1> arcReversed;
1016
1017 LINE pl;
1018 bool guardHit = false;
1019
1020 int i_start = MaxVerts / 2;
1021 int i_end = i_start + 1;
1022
1023 pl.SetWidth( aSeg->Width() );
1024 pl.SetLayers( aSeg->Layers() );
1025 pl.SetNet( aSeg->Net() );
1026 pl.SetOwner( this );
1027
1028 followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1029 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1030
1031 if( !guardHit )
1032 {
1033 followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1034 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1035 }
1036
1037 int n = 0;
1038
1039 LINKED_ITEM* prev_seg = nullptr;
1040 bool originSet = false;
1041
1042 SHAPE_LINE_CHAIN& line = pl.Line();
1043
1044 for( int i = i_start + 1; i < i_end; i++ )
1045 {
1046 const VECTOR2I& p = corners[i];
1047 LINKED_ITEM* li = segs[i];
1048
1049 if( !li || li->Kind() != ITEM::ARC_T )
1050 line.Append( p );
1051
1052 if( li && prev_seg != li )
1053 {
1054 if( li->Kind() == ITEM::ARC_T )
1055 {
1056 const ARC* arc = static_cast<const ARC*>( li );
1057 const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape() );
1058
1059 int nSegs = line.PointCount();
1060 VECTOR2I last = nSegs ? line.CPoint( -1 ) : VECTOR2I();
1061 ssize_t lastShape = nSegs ? line.ArcIndex( static_cast<ssize_t>( nSegs ) - 1 ) : -1;
1062
1063 line.Append( arcReversed[i] ? sa->Reversed() : *sa );
1064 }
1065
1066 pl.Link( li );
1067
1068 // latter condition to avoid loops
1069 if( li == aSeg && aOriginSegmentIndex && !originSet )
1070 {
1071 wxASSERT( n < line.SegmentCount() ||
1072 ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
1073 *aOriginSegmentIndex = line.PointCount() - 1;
1074 originSet = true;
1075 }
1076 }
1077
1078 prev_seg = li;
1079 }
1080
1081 // Remove duplicate verts, but do NOT remove colinear segments here!
1082 pl.Line().Simplify( false );
1083
1084 // TODO: maintain actual segment index under simplification system
1085 if( aOriginSegmentIndex && *aOriginSegmentIndex >= pl.SegmentCount() )
1086 *aOriginSegmentIndex = pl.SegmentCount() - 1;
1087
1088 assert( pl.SegmentCount() != 0 );
1089
1090 return pl;
1091}
1092
1093
1094void NODE::FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB )
1095{
1096 aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
1097 aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
1098}
1099
1100
1101int NODE::FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines )
1102{
1103 for( ITEM* item : aA.LinkList() )
1104 {
1105 if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
1106 {
1107 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1108 LINE line = AssembleLine( li );
1109
1110 if( !line.Layers().Overlaps( aB.Layers() ) )
1111 continue;
1112
1113 JOINT j_start, j_end;
1114
1115 FindLineEnds( line, j_start, j_end );
1116
1117 int id_start = line.CLine().Find( aA.Pos() );
1118 int id_end = line.CLine().Find( aB.Pos() );
1119
1120 if( id_end < id_start )
1121 std::swap( id_end, id_start );
1122
1123 if( id_start >= 0 && id_end >= 0 )
1124 {
1125 line.ClipVertexRange( id_start, id_end );
1126 aLines.push_back( line );
1127 }
1128 }
1129 }
1130
1131 return 0;
1132}
1133
1134
1136{
1137 const SEGMENT* locked_seg = nullptr;
1138 std::vector<VVIA*> vvias;
1139
1140 for( auto& jointPair : m_joints )
1141 {
1142 JOINT joint = jointPair.second;
1143
1144 if( joint.Layers().IsMultilayer() )
1145 continue;
1146
1147 int n_seg = 0, n_solid = 0, n_vias = 0;
1148 int prev_w = -1;
1149 int max_w = -1;
1150 bool is_width_change = false;
1151 bool is_locked = false;
1152
1153 for( const ITEM* item : joint.LinkList() )
1154 {
1155 if( item->OfKind( ITEM::VIA_T ) )
1156 {
1157 n_vias++;
1158 }
1159 else if( item->OfKind( ITEM::SOLID_T ) )
1160 {
1161 n_solid++;
1162 }
1163 else if( const auto t = dyn_cast<const PNS::SEGMENT*>( item ) )
1164 {
1165 int w = t->Width();
1166
1167 if( prev_w >= 0 && w != prev_w )
1168 {
1169 is_width_change = true;
1170 }
1171
1172 max_w = std::max( w, max_w );
1173 prev_w = w;
1174
1175 is_locked = t->IsLocked();
1176 locked_seg = t;
1177 }
1178 }
1179
1180 if( ( is_width_change || n_seg >= 3 || is_locked ) && n_solid == 0 && n_vias == 0 )
1181 {
1182 // fixme: the hull margin here is an ugly temporary workaround. The real fix
1183 // is to use octagons for via force propagation.
1184 vvias.push_back( new VVIA( joint.Pos(), joint.Layers().Start(),
1185 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1186 }
1187
1188 if( is_locked )
1189 {
1190 const VECTOR2I& secondPos = ( locked_seg->Seg().A == joint.Pos() ) ?
1191 locked_seg->Seg().B :
1192 locked_seg->Seg().A;
1193
1194 vvias.push_back( new VVIA( secondPos, joint.Layers().Start(),
1195 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1196 }
1197 }
1198
1199 for( auto vvia : vvias )
1200 {
1201 Add( ItemCast<VIA>( std::move( std::unique_ptr<VVIA>( vvia ) ) ) );
1202 }
1203}
1204
1205
1206const JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, NET_HANDLE aNet ) const
1207{
1208 JOINT::HASH_TAG tag;
1209
1210 tag.net = aNet;
1211 tag.pos = aPos;
1212
1213 JOINT_MAP::const_iterator f = m_joints.find( tag ), end = m_joints.end();
1214
1215 if( f == end && !isRoot() )
1216 {
1217 end = m_root->m_joints.end();
1218 f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1219 }
1220
1221 if( f == end )
1222 return nullptr;
1223
1224 while( f != end )
1225 {
1226 if( f->second.Layers().Overlaps( aLayer ) )
1227 return &f->second;
1228
1229 ++f;
1230 }
1231
1232 return nullptr;
1233}
1234
1235
1236void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
1237{
1238 JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1239 jt.Lock( aLock );
1240}
1241
1242
1243JOINT& NODE::touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet )
1244{
1245 JOINT::HASH_TAG tag;
1246
1247 tag.pos = aPos;
1248 tag.net = aNet;
1249
1250 // try to find the joint in this node.
1251 JOINT_MAP::iterator f = m_joints.find( tag );
1252
1253 std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1254
1255 // not found and we are not root? find in the root and copy results here.
1256 if( f == m_joints.end() && !isRoot() )
1257 {
1258 range = m_root->m_joints.equal_range( tag );
1259
1260 for( f = range.first; f != range.second; ++f )
1261 m_joints.insert( *f );
1262 }
1263
1264 // now insert and combine overlapping joints
1265 JOINT jt( aPos, aLayers, aNet );
1266
1267 bool merged;
1268
1269 do
1270 {
1271 merged = false;
1272 range = m_joints.equal_range( tag );
1273
1274 if( range.first == m_joints.end() )
1275 break;
1276
1277 for( f = range.first; f != range.second; ++f )
1278 {
1279 if( aLayers.Overlaps( f->second.Layers() ) )
1280 {
1281 jt.Merge( f->second );
1282 m_joints.erase( f );
1283 merged = true;
1284 break;
1285 }
1286 }
1287 } while( merged );
1288
1289 return m_joints.insert( TagJointPair( tag, jt ) )->second;
1290}
1291
1292
1293void JOINT::Dump() const
1294{
1295 wxLogTrace( wxT( "PNS" ), wxT( "joint layers %d-%d, net %d, pos %s, links: %d" ),
1296 m_layers.Start(),
1297 m_layers.End(),
1298 m_tag.net,
1299 m_tag.pos.Format().c_str(),
1300 LinkCount() );
1301}
1302
1303
1304void NODE::linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet,
1305 ITEM* aWhere )
1306{
1307 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1308
1309 jt.Link( aWhere );
1310}
1311
1312
1313void NODE::unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet,
1314 ITEM* aWhere )
1315{
1316 // fixme: remove dangling joints
1317 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1318
1319 jt.Unlink( aWhere );
1320}
1321
1322
1323void NODE::Dump( bool aLong )
1324{
1325#if 0
1326 std::unordered_set<SEGMENT*> all_segs;
1328
1329 for( i = m_items.begin(); i != m_items.end(); i++ )
1330 {
1331 if( (*i)->GetKind() == ITEM::SEGMENT_T )
1332 all_segs.insert( static_cast<SEGMENT*>( *i ) );
1333 }
1334
1335 if( !isRoot() )
1336 {
1337 for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1338 {
1339 if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1340 all_segs.insert( static_cast<SEGMENT*>(*i) );
1341 }
1342 }
1343
1344 JOINT_MAP::iterator j;
1345
1346 if( aLong )
1347 {
1348 for( j = m_joints.begin(); j != m_joints.end(); ++j )
1349 {
1350 wxLogTrace( wxT( "PNS" ), wxT( "joint : %s, links : %d\n" ),
1351 j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1352 JOINT::LINKED_ITEMS::const_iterator k;
1353
1354 for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1355 {
1356 const ITEM* m_item = *k;
1357
1358 switch( m_item->GetKind() )
1359 {
1360 case ITEM::SEGMENT_T:
1361 {
1362 const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1363 wxLogTrace( wxT( "PNS" ), wxT( " -> seg %s %s\n" ),
1364 seg->GetSeg().A.Format().c_str(),
1365 seg->GetSeg().B.Format().c_str() );
1366 break;
1367 }
1368
1369 default:
1370 break;
1371 }
1372 }
1373 }
1374 }
1375
1376 int lines_count = 0;
1377
1378 while( !all_segs.empty() )
1379 {
1380 SEGMENT* s = *all_segs.begin();
1381 LINE* l = AssembleLine( s );
1382
1383 LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1384
1385 if( aLong )
1386 {
1387 wxLogTrace( wxT( "PNS" ), wxT( "Line: %s, net %d " ),
1388 l->GetLine().Format().c_str(), l->GetNet() );
1389 }
1390
1391 for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1392 {
1393 wxLogTrace( wxT( "PNS" ), wxT( "%s " ), (*j)->GetSeg().A.Format().c_str() );
1394
1395 if( j + 1 == seg_refs->end() )
1396 wxLogTrace( wxT( "PNS" ), wxT( "%s\n" ), (*j)->GetSeg().B.Format().c_str() );
1397
1398 all_segs.erase( *j );
1399 }
1400
1401 lines_count++;
1402 }
1403
1404 wxLogTrace( wxT( "PNS" ), wxT( "Local joints: %d, lines : %d \n" ),
1405 m_joints.size(), lines_count );
1406#endif
1407}
1408
1409
1411{
1412 if( isRoot() )
1413 return;
1414
1415 if( m_override.size() )
1416 aRemoved.reserve( m_override.size() );
1417
1418 if( m_index->Size() )
1419 aAdded.reserve( m_index->Size() );
1420
1421 for( ITEM* item : m_override )
1422 aRemoved.push_back( item );
1423
1424 for( ITEM* item : *m_index )
1425 aAdded.push_back( item );
1426}
1427
1428
1430{
1431 // copy the kids as the NODE destructor erases the item from the parent node.
1432 std::set<NODE*> kids = m_children;
1433
1434 for( NODE* node : kids )
1435 {
1436 node->releaseChildren();
1437 delete node;
1438 }
1439}
1440
1441
1443{
1444 if( !isRoot() )
1445 return;
1446
1447 std::vector<const ITEM*> cacheCheckItems;
1448 cacheCheckItems.reserve( m_garbageItems.size() );
1449
1450 for( ITEM* item : m_garbageItems )
1451 {
1452 if( !item->BelongsTo( this ) )
1453 delete item;
1454 }
1455
1456 m_garbageItems.clear();
1457
1458 if( m_ruleResolver )
1459 {
1460 m_ruleResolver->ClearCacheForItems( cacheCheckItems );
1461 }
1462}
1463
1464
1465void NODE::Commit( NODE* aNode )
1466{
1467 if( aNode->isRoot() )
1468 return;
1469
1470 for( ITEM* item : aNode->m_override )
1471 Remove( item );
1472
1473 for( ITEM* item : *aNode->m_index )
1474 {
1475 if( item->HasHole() )
1476 {
1477 item->Hole()->SetOwner( item );
1478 }
1479
1480 item->SetRank( -1 );
1481 item->Unmark();
1482 add( item );
1483 }
1484
1487}
1488
1489
1491{
1493}
1494
1495
1496void NODE::AllItemsInNet( NET_HANDLE aNet, std::set<ITEM*>& aItems, int aKindMask )
1497{
1499
1500 if( l_cur )
1501 {
1502 for( ITEM* item : *l_cur )
1503 {
1504 if( item->OfKind( aKindMask ) && item->IsRoutable() )
1505 aItems.insert( item );
1506 }
1507 }
1508
1509 if( !isRoot() )
1510 {
1512
1513 if( l_root )
1514 {
1515 for( ITEM* item : *l_root )
1516 {
1517 if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1518 aItems.insert( item );
1519 }
1520 }
1521 }
1522}
1523
1524
1525void NODE::ClearRanks( int aMarkerMask )
1526{
1527 for( ITEM* item : *m_index )
1528 {
1529 item->SetRank( -1 );
1530 item->Mark( item->Marker() & ~aMarkerMask );
1531 }
1532}
1533
1534
1535void NODE::RemoveByMarker( int aMarker )
1536{
1537 std::vector<ITEM*> garbage;
1538
1539 for( ITEM* item : *m_index )
1540 {
1541 if( item->Marker() & aMarker )
1542 garbage.emplace_back( item );
1543 }
1544
1545 for( ITEM* item : garbage )
1546 Remove( item );
1547}
1548
1549
1551 NET_HANDLE aNet )
1552{
1553 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1554
1555 if( !jtStart )
1556 return nullptr;
1557
1558 for( ITEM* item : jtStart->LinkList() )
1559 {
1560 if( item->OfKind( ITEM::SEGMENT_T ) )
1561 {
1562 SEGMENT* seg2 = (SEGMENT*)item;
1563
1564 const VECTOR2I a2( seg2->Seg().A );
1565 const VECTOR2I b2( seg2->Seg().B );
1566
1567 if( seg2->Layers().Start() == lr.Start()
1568 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1569 {
1570 return seg2;
1571 }
1572 }
1573 }
1574
1575 return nullptr;
1576}
1577
1578
1580{
1581 return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1582}
1583
1584
1586 NET_HANDLE aNet )
1587{
1588 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1589
1590 if( !jtStart )
1591 return nullptr;
1592
1593 for( ITEM* item : jtStart->LinkList() )
1594 {
1595 if( item->OfKind( ITEM::ARC_T ) )
1596 {
1597 ARC* seg2 = static_cast<ARC*>( item );
1598
1599 const VECTOR2I a2( seg2->Anchor( 0 ) );
1600 const VECTOR2I b2( seg2->Anchor( 1 ) );
1601
1602 if( seg2->Layers().Start() == lr.Start()
1603 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1604 {
1605 return seg2;
1606 }
1607 }
1608 }
1609
1610 return nullptr;
1611}
1612
1613
1615{
1616 return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1617}
1618
1619
1620int NODE::QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints, LAYER_RANGE aLayerMask,
1621 int aKindMask )
1622{
1623 int n = 0;
1624
1625 aJoints.clear();
1626
1627 for( JOINT_MAP::value_type& j : m_joints )
1628 {
1629 if( !j.second.Layers().Overlaps( aLayerMask ) )
1630 continue;
1631
1632 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1633 {
1634 aJoints.push_back( &j.second );
1635 n++;
1636 }
1637 }
1638
1639 if( isRoot() )
1640 return n;
1641
1642 for( JOINT_MAP::value_type& j : m_root->m_joints )
1643 {
1644 if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1645 {
1646 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1647 {
1648 aJoints.push_back( &j.second );
1649 n++;
1650 }
1651 }
1652 }
1653
1654 return n;
1655}
1656
1657
1659{
1660 if( aParent->IsConnected() )
1661 {
1662 const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1663 INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( cItem->GetNet() );
1664
1665 if( l_cur )
1666 {
1667 for( ITEM* item : *l_cur )
1668 {
1669 if( item->Parent() == aParent )
1670 return item;
1671 }
1672 }
1673 }
1674
1675 return nullptr;
1676}
1677
1678std::vector<ITEM*> NODE::FindItemsByZone( const ZONE* aParent )
1679{
1680 std::vector<ITEM*> ret;
1681
1682 for( ITEM* item : *m_index )
1683 {
1684 if( item->Parent() == aParent )
1685 ret.push_back( item );
1686 }
1687
1688 return ret;
1689}
1690}
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:195
bool Contains(const Vec &aPoint) const
Definition: box2.h:142
coord_type GetRight() const
Definition: box2.h:190
coord_type GetLeft() const
Definition: box2.h:194
coord_type GetBottom() const
Definition: box2.h:191
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:196
virtual const std::string Format() const
Definition: pns_item.cpp:300
virtual void Unmark(int aMarker=-1) const
Definition: pns_item.h:230
virtual NET_HANDLE Net() const
Definition: pns_item.h:193
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:166
void SetNet(NET_HANDLE aNet)
Definition: pns_item.h:192
virtual void SetRank(int aRank)
Definition: pns_item.h:233
LAYER_RANGE m_layers
Definition: pns_item.h:287
virtual int Layer() const
Definition: pns_item.h:199
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:224
@ SEGMENT_T
Definition: pns_item.h:105
const LAYER_RANGE & Layers() const
Definition: pns_item.h:195
bool OfKind(int aKindMask) const
Definition: pns_item.h:174
bool IsVirtual() const
Definition: pns_item.h:263
bool IsRoutable() const
Definition: pns_item.h:252
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:236
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:204
virtual HOLE * Hole() const
Definition: pns_item.h:272
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:268
virtual bool HasHole() const
Definition: pns_item.h:271
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:272
NET_HANDLE Net() const override
Definition: pns_joint.h:267
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:287
LINKED_ITEM * NextSegment(ITEM *aCurrent, bool aAllowLockedSegs=false) const
Definition: pns_joint.h:225
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:321
void Link(ITEM *aItem)
Unlink a given board item from the joint (upon its removal from a NODE)
Definition: pns_joint.h:207
void Dump() const
Definition: pns_node.cpp:1293
HASH_TAG m_tag
< hash tag for unordered_multimap
Definition: pns_joint.h:333
bool IsLocked() const
Definition: pns_joint.h:326
void Merge(const JOINT &aJoint)
Definition: pns_joint.h:299
bool Unlink(ITEM *aItem)
For trivial joints, return the segment adjacent to (aCurrent).
Definition: pns_joint.h:217
const VECTOR2I & Pos() const
Definition: pns_joint.h:262
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:206
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:1535
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:530
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, NET_HANDLE aNet)
Definition: pns_node.cpp:1550
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:1101
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:217
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:959
void addSolid(SOLID *aSeg)
Definition: pns_node.cpp:512
bool Overrides(ITEM *aItem) const
Definition: pns_node.h:455
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:759
void rebuildJoint(const JOINT *aJoint, const ITEM *aItem)
Definition: pns_node.cpp:773
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:1410
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:646
std::vector< std::unique_ptr< SHAPE > > m_edgeExclusions
Definition: pns_node.h:542
void releaseChildren()
Definition: pns_node.cpp:1429
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:524
void addVia(VIA *aVia)
Definition: pns_node.cpp:535
bool QueryEdgeExclusions(const VECTOR2I &aPos) const
Definition: pns_node.cpp:707
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:719
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:1206
void addHole(HOLE *aHole)
Definition: pns_node.cpp:553
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:216
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:544
void Dump(bool aLong=false)
Definition: pns_node.cpp:1323
void releaseGarbage()
Definition: pns_node.cpp:1442
void addArc(ARC *aVia)
Definition: pns_node.cpp:675
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1094
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:1243
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:244
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1620
void FixupVirtualVias()
Definition: pns_node.cpp:1135
std::set< OBSTACLE > OBSTACLES
Definition: pns_node.h:218
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:538
std::vector< ITEM * > FindItemsByZone(const ZONE *aParent)
Definition: pns_node.cpp:1678
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:533
void AllItemsInNet(NET_HANDLE aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1496
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:1236
void removeArcIndex(ARC *aVia)
Definition: pns_node.cpp:766
void AddEdgeExclusion(std::unique_ptr< SHAPE > aShape)
Definition: pns_node.cpp:701
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:536
bool isRoot() const
Definition: pns_node.h:503
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:818
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, NET_HANDLE aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1313
void add(ITEM *aItem, bool aAllowRedundant=false)
Definition: pns_node.cpp:569
void KillChildren()
Definition: pns_node.cpp:1490
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:826
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:539
bool Add(std::unique_ptr< SEGMENT > &&aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:657
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:531
ITEM * FindItemByParent(const BOARD_ITEM *aParent)
Definition: pns_node.cpp:1658
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:526
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, NET_HANDLE aNet)
Definition: pns_node.cpp:1585
NODE * m_parent
node this node was branched from
Definition: pns_node.h:529
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1525
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > &&aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:838
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:878
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:1465
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:537
~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:1304
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:1008
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition: pns_node.cpp:483
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:192
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:190
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:193
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:217
ROUTING_SETTINGS & Settings()
Definition: pns_router.h:191
static ROUTER * GetInstance()
Definition: pns_router.cpp:82
DIRECTION_45::CORNER_MODE GetCornerMode() const
virtual void ClearCacheForItems(std::vector< const ITEM * > &aItems)
Definition: pns_node.h:165
virtual int ClearanceEpsilon() const
Definition: pns_node.h:169
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:588
const VECTOR2I & GetP1() const
Definition: shape_arc.h:113
const VECTOR2I & GetP0() const
Definition: shape_arc.h:112
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_ARC & Arc(size_t aArc) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int PointCount() const
Return the number of points (vertices) in this line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void 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...
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:378
Handle a list of polygons defining a copper zone.
Definition: zone.h:72
Push and Shove diff pair dimensions (gap) settings dialog.
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
Definition: pns_utils.cpp:384
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:134
std::set< OBSTACLE > & obstacles
Definition: pns_node.h:133
std::set< ITEM * > * m_restrictedSet
Definition: pns_node.h:121
bool operator()(ITEM *aItem) override
Definition: pns_node.cpp:469
const VECTOR2I & m_point
Definition: pns_node.cpp:457
HIT_VISITOR(ITEM_SET &aTab, const VECTOR2I &aPoint)
Definition: pns_node.cpp:459
virtual ~HIT_VISITOR()
Definition: pns_node.cpp:465
ITEM_SET & m_items
Definition: pns_node.cpp:456
< 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:588