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