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