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, bool aStopAtLockedJoints,
1048 bool aFollowLockedSegments, bool aAllowSegmentSizeMismatch )
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.SetParent( nullptr );
1066 pl.SetSourceItem( aSeg->GetSourceItem() );
1067 pl.SetOwner( this );
1068
1069 followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1070 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1071
1072 if( !guardHit )
1073 {
1074 followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1075 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1076 }
1077
1078 int n = 0;
1079
1080 LINKED_ITEM* prev_seg = nullptr;
1081 bool originSet = false;
1082
1083 SHAPE_LINE_CHAIN& line = pl.Line();
1084
1085 for( int i = i_start + 1; i < i_end; i++ )
1086 {
1087 const VECTOR2I& p = corners[i];
1088 LINKED_ITEM* li = segs[i];
1089
1090 if( !aAllowSegmentSizeMismatch && ( li && li->Width() != aSeg->Width() ) )
1091 continue;
1092
1093 if( !li || li->Kind() != ITEM::ARC_T )
1094 line.Append( p );
1095
1096 if( li && prev_seg != li )
1097 {
1098 if( li->Kind() == ITEM::ARC_T )
1099 {
1100 const ARC* arc = static_cast<const ARC*>( li );
1101 const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape( -1 ) );
1102
1103 int nSegs = line.PointCount();
1104 VECTOR2I last = nSegs ? line.CLastPoint() : VECTOR2I();
1105 ssize_t lastShape = nSegs ? line.ArcIndex( static_cast<ssize_t>( nSegs ) - 1 ) : -1;
1106
1107 line.Append( arcReversed[i] ? sa->Reversed() : *sa );
1108 }
1109
1110 pl.Link( li );
1111
1112 // latter condition to avoid loops
1113 if( li == aSeg && aOriginSegmentIndex && !originSet )
1114 {
1115 wxASSERT( n < line.SegmentCount() ||
1116 ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
1117 *aOriginSegmentIndex = line.PointCount() - 1;
1118 originSet = true;
1119 }
1120 }
1121
1122 prev_seg = li;
1123 }
1124
1125 // Remove duplicate verts, but do NOT remove colinear segments here!
1127
1128 // TODO: maintain actual segment index under simplification system
1129 if( aOriginSegmentIndex && *aOriginSegmentIndex >= pl.SegmentCount() )
1130 *aOriginSegmentIndex = pl.SegmentCount() - 1;
1131
1132 wxASSERT_MSG( pl.SegmentCount() != 0, "assembled line should never be empty" );
1133
1134 return pl;
1135}
1136
1137
1138void NODE::FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB )
1139{
1140 aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
1141 aB = *FindJoint( aLine.CLastPoint(), &aLine );
1142}
1143
1144
1145int NODE::FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines )
1146{
1147 for( ITEM* item : aA.LinkList() )
1148 {
1149 if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
1150 {
1151 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1152 LINE line = AssembleLine( li );
1153
1154 if( !line.Layers().Overlaps( aB.Layers() ) )
1155 continue;
1156
1157 JOINT j_start, j_end;
1158
1159 FindLineEnds( line, j_start, j_end );
1160
1161 int id_start = line.CLine().Find( aA.Pos() );
1162 int id_end = line.CLine().Find( aB.Pos() );
1163
1164 if( id_end < id_start )
1165 std::swap( id_end, id_start );
1166
1167 if( id_start >= 0 && id_end >= 0 )
1168 {
1169 line.ClipVertexRange( id_start, id_end );
1170 aLines.push_back( line );
1171 }
1172 }
1173 }
1174
1175 return 0;
1176}
1177
1178
1180{
1181 const SEGMENT* locked_seg = nullptr;
1182 std::vector<VVIA*> vvias;
1183
1184 for( auto& jointPair : m_joints )
1185 {
1186 JOINT joint = jointPair.second;
1187
1188 if( joint.Layers().IsMultilayer() )
1189 continue;
1190
1191 int n_seg = 0;
1192 int n_solid = 0;
1193 int n_vias = 0;
1194 int prev_w = -1;
1195 bool prev_mask = false;
1196 std::optional<int> prev_mask_margin;
1197 int max_w = -1;
1198 bool is_width_change = false;
1199 bool is_locked = false;
1200
1201 for( const ITEM* item : joint.LinkList() )
1202 {
1203 if( item->OfKind( ITEM::VIA_T ) )
1204 {
1205 n_vias++;
1206 }
1207 else if( item->OfKind( ITEM::SOLID_T ) )
1208 {
1209 n_solid++;
1210 }
1211 else if( const auto t = dyn_cast<const PNS::SEGMENT*>( item ) )
1212 {
1213 int w = t->Width();
1214 bool mask = false;
1215 std::optional<int> mask_margin;
1216
1217 if( PCB_TRACK* track = static_cast<PCB_TRACK*>( t->Parent() ) )
1218 {
1219 mask = track->HasSolderMask();
1220 mask_margin = track->GetLocalSolderMaskMargin();
1221 }
1222
1223 if( prev_w < 0 )
1224 {
1225 prev_w = w;
1226 prev_mask = mask;
1227 prev_mask_margin = mask_margin;
1228 }
1229 else if( w != prev_w || mask != prev_mask || mask_margin != prev_mask_margin )
1230 {
1231 is_width_change = true;
1232 }
1233
1234 max_w = std::max( w, max_w );
1235 prev_w = w;
1236
1237 is_locked = t->IsLocked();
1238 locked_seg = t;
1239 }
1240 }
1241
1242 if( ( is_width_change || n_seg >= 3 || is_locked ) && n_solid == 0 && n_vias == 0 )
1243 {
1244 // fixme: the hull margin here is an ugly temporary workaround. The real fix
1245 // is to use octagons for via force propagation.
1246 vvias.push_back( new VVIA( joint.Pos(), joint.Layers().Start(),
1247 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1248 }
1249
1250 if( is_locked )
1251 {
1252 const VECTOR2I& secondPos = ( locked_seg->Seg().A == joint.Pos() ) ?
1253 locked_seg->Seg().B :
1254 locked_seg->Seg().A;
1255
1256 vvias.push_back( new VVIA( secondPos, joint.Layers().Start(),
1257 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1258 }
1259 }
1260
1261 for( auto vvia : vvias )
1262 {
1263 Add( ItemCast<VIA>( std::move( std::unique_ptr<VVIA>( vvia ) ) ) );
1264 }
1265}
1266
1267
1268const JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, NET_HANDLE aNet ) const
1269{
1270 JOINT::HASH_TAG tag;
1271
1272 tag.net = aNet;
1273 tag.pos = aPos;
1274
1275 JOINT_MAP::const_iterator f = m_joints.find( tag ), end = m_joints.end();
1276
1277 if( f == end && !isRoot() )
1278 {
1279 end = m_root->m_joints.end();
1280 f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1281 }
1282
1283 while( f != end )
1284 {
1285 if( f->second.Pos() == aPos && f->second.Net() == aNet && f->second.Layers().Overlaps( aLayer ) )
1286 return &f->second;
1287
1288 f++;
1289 }
1290
1291 return nullptr;
1292}
1293
1294
1295void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
1296{
1297 JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1298 jt.Lock( aLock );
1299}
1300
1301
1302JOINT& NODE::touchJoint( const VECTOR2I& aPos, const PNS_LAYER_RANGE& aLayers, NET_HANDLE aNet )
1303{
1304 JOINT::HASH_TAG tag;
1305
1306 tag.pos = aPos;
1307 tag.net = aNet;
1308
1309 // try to find the joint in this node.
1310 JOINT_MAP::iterator f = m_joints.find( tag );
1311
1312 std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1313
1314 // not found and we are not root? find in the root and copy results here.
1315 if( f == m_joints.end() && !isRoot() )
1316 {
1317 range = m_root->m_joints.equal_range( tag );
1318
1319 for( f = range.first; f != range.second; ++f )
1320 m_joints.insert( *f );
1321 }
1322
1323 // now insert and combine overlapping joints
1324 JOINT jt( aPos, aLayers, aNet );
1325
1326 bool merged;
1327
1328 do
1329 {
1330 merged = false;
1331 range = m_joints.equal_range( tag );
1332
1333 if( range.first == m_joints.end() )
1334 break;
1335
1336 for( f = range.first; f != range.second; ++f )
1337 {
1338 if( aLayers.Overlaps( f->second.Layers() ) )
1339 {
1340 jt.Merge( f->second );
1341 m_joints.erase( f );
1342 merged = true;
1343 break;
1344 }
1345 }
1346 } while( merged );
1347
1348 return m_joints.insert( TagJointPair( tag, jt ) )->second;
1349}
1350
1351
1352void JOINT::Dump() const
1353{
1354 wxLogTrace( wxT( "PNS" ), wxT( "joint layers %d-%d, net %d, pos %s, links: %d" ),
1355 m_layers.Start(),
1356 m_layers.End(),
1357 m_tag.net,
1358 m_tag.pos.Format().c_str(),
1359 LinkCount() );
1360}
1361
1362
1363void NODE::linkJoint( const VECTOR2I& aPos, const PNS_LAYER_RANGE& aLayers, NET_HANDLE aNet,
1364 ITEM* aWhere )
1365{
1366 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1367
1368 jt.Link( aWhere );
1369}
1370
1371
1372void NODE::unlinkJoint( const VECTOR2I& aPos, const PNS_LAYER_RANGE& aLayers, NET_HANDLE aNet,
1373 ITEM* aWhere )
1374{
1375 // fixme: remove dangling joints
1376 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1377
1378 jt.Unlink( aWhere );
1379}
1380
1381
1382void NODE::Dump( bool aLong )
1383{
1384#if 0
1385 std::unordered_set<SEGMENT*> all_segs;
1387
1388 for( i = m_items.begin(); i != m_items.end(); i++ )
1389 {
1390 if( (*i)->GetKind() == ITEM::SEGMENT_T )
1391 all_segs.insert( static_cast<SEGMENT*>( *i ) );
1392 }
1393
1394 if( !isRoot() )
1395 {
1396 for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1397 {
1398 if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1399 all_segs.insert( static_cast<SEGMENT*>(*i) );
1400 }
1401 }
1402
1403 JOINT_MAP::iterator j;
1404
1405 if( aLong )
1406 {
1407 for( j = m_joints.begin(); j != m_joints.end(); ++j )
1408 {
1409 wxLogTrace( wxT( "PNS" ), wxT( "joint : %s, links : %d\n" ),
1410 j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1411 JOINT::LINKED_ITEMS::const_iterator k;
1412
1413 for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1414 {
1415 const ITEM* m_item = *k;
1416
1417 switch( m_item->GetKind() )
1418 {
1419 case ITEM::SEGMENT_T:
1420 {
1421 const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1422 wxLogTrace( wxT( "PNS" ), wxT( " -> seg %s %s\n" ),
1423 seg->GetSeg().A.Format().c_str(),
1424 seg->GetSeg().B.Format().c_str() );
1425 break;
1426 }
1427
1428 default:
1429 break;
1430 }
1431 }
1432 }
1433 }
1434
1435 int lines_count = 0;
1436
1437 while( !all_segs.empty() )
1438 {
1439 SEGMENT* s = *all_segs.begin();
1440 LINE* l = AssembleLine( s );
1441
1442 LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1443
1444 if( aLong )
1445 {
1446 wxLogTrace( wxT( "PNS" ), wxT( "Line: %s, net %d " ),
1447 l->GetLine().Format().c_str(), l->GetNet() );
1448 }
1449
1450 for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1451 {
1452 wxLogTrace( wxT( "PNS" ), wxT( "%s " ), (*j)->GetSeg().A.Format().c_str() );
1453
1454 if( j + 1 == seg_refs->end() )
1455 wxLogTrace( wxT( "PNS" ), wxT( "%s\n" ), (*j)->GetSeg().B.Format().c_str() );
1456
1457 all_segs.erase( *j );
1458 }
1459
1460 lines_count++;
1461 }
1462
1463 wxLogTrace( wxT( "PNS" ), wxT( "Local joints: %d, lines : %d \n" ),
1464 m_joints.size(), lines_count );
1465#endif
1466}
1467
1468
1470{
1471 if( isRoot() )
1472 return;
1473
1474 if( m_override.size() )
1475 aRemoved.reserve( m_override.size() );
1476
1477 if( m_index->Size() )
1478 aAdded.reserve( m_index->Size() );
1479
1480 for( ITEM* item : m_override )
1481 aRemoved.push_back( item );
1482
1483 for( ITEM* item : *m_index )
1484 aAdded.push_back( item );
1485}
1486
1487
1489{
1490 // copy the kids as the NODE destructor erases the item from the parent node.
1491 std::set<NODE*> kids = m_children;
1492
1493 for( NODE* node : kids )
1494 {
1495 node->releaseChildren();
1496 delete node;
1497 }
1498}
1499
1500
1502{
1503 if( !isRoot() )
1504 return;
1505
1506 std::vector<const ITEM*> cacheCheckItems;
1507 cacheCheckItems.reserve( m_garbageItems.size() );
1508
1509 for( ITEM* item : m_garbageItems )
1510 {
1511 if( !item->BelongsTo( this ) )
1512 delete item;
1513 }
1514
1515 m_garbageItems.clear();
1516
1517 if( m_ruleResolver )
1518 {
1519 m_ruleResolver->ClearCacheForItems( cacheCheckItems );
1520 }
1521}
1522
1523
1524void NODE::Commit( NODE* aNode )
1525{
1526 if( aNode->isRoot() )
1527 return;
1528
1529 for( ITEM* item : aNode->m_override )
1530 Remove( item );
1531
1532 for( ITEM* item : *aNode->m_index )
1533 {
1534 if( item->HasHole() )
1535 {
1536 item->Hole()->SetOwner( item );
1537 }
1538
1539 item->SetRank( -1 );
1540 item->Unmark();
1541 add( item );
1542 }
1543
1546}
1547
1548
1550{
1552}
1553
1554
1555void NODE::AllItemsInNet( NET_HANDLE aNet, std::set<ITEM*>& aItems, int aKindMask )
1556{
1558
1559 if( l_cur )
1560 {
1561 for( ITEM* item : *l_cur )
1562 {
1563 if( item->OfKind( aKindMask ) && item->IsRoutable() )
1564 aItems.insert( item );
1565 }
1566 }
1567
1568 if( !isRoot() )
1569 {
1571
1572 if( l_root )
1573 {
1574 for( ITEM* item : *l_root )
1575 {
1576 if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1577 aItems.insert( item );
1578 }
1579 }
1580 }
1581}
1582
1583
1584void NODE::ClearRanks( int aMarkerMask )
1585{
1586 for( ITEM* item : *m_index )
1587 {
1588 item->SetRank( -1 );
1589 item->Mark( item->Marker() & ~aMarkerMask );
1590 }
1591}
1592
1593
1594void NODE::RemoveByMarker( int aMarker )
1595{
1596 std::vector<ITEM*> garbage;
1597
1598 for( ITEM* item : *m_index )
1599 {
1600 if( item->Marker() & aMarker )
1601 garbage.emplace_back( item );
1602 }
1603
1604 for( ITEM* item : garbage )
1605 Remove( item );
1606}
1607
1608
1610 NET_HANDLE aNet )
1611{
1612 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1613
1614 if( !jtStart )
1615 return nullptr;
1616
1617 for( ITEM* item : jtStart->LinkList() )
1618 {
1619 if( item->OfKind( ITEM::SEGMENT_T ) )
1620 {
1621 SEGMENT* seg2 = (SEGMENT*)item;
1622
1623 const VECTOR2I a2( seg2->Seg().A );
1624 const VECTOR2I b2( seg2->Seg().B );
1625
1626 if( seg2->Layers().Start() == lr.Start()
1627 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1628 {
1629 return seg2;
1630 }
1631 }
1632 }
1633
1634 return nullptr;
1635}
1636
1637
1639{
1640 return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1641}
1642
1643
1645 NET_HANDLE aNet )
1646{
1647 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1648
1649 if( !jtStart )
1650 return nullptr;
1651
1652 for( ITEM* item : jtStart->LinkList() )
1653 {
1654 if( item->OfKind( ITEM::ARC_T ) )
1655 {
1656 ARC* seg2 = static_cast<ARC*>( item );
1657
1658 const VECTOR2I a2( seg2->Anchor( 0 ) );
1659 const VECTOR2I b2( seg2->Anchor( 1 ) );
1660
1661 if( seg2->Layers().Start() == lr.Start()
1662 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1663 {
1664 return seg2;
1665 }
1666 }
1667 }
1668
1669 return nullptr;
1670}
1671
1672
1674{
1675 return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1676}
1677
1678
1679int NODE::QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints, PNS_LAYER_RANGE aLayerMask,
1680 int aKindMask )
1681{
1682 int n = 0;
1683
1684 aJoints.clear();
1685
1686 for( JOINT_MAP::value_type& j : m_joints )
1687 {
1688 if( !j.second.Layers().Overlaps( aLayerMask ) )
1689 continue;
1690
1691 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1692 {
1693 aJoints.push_back( &j.second );
1694 n++;
1695 }
1696 }
1697
1698 if( isRoot() )
1699 return n;
1700
1701 for( JOINT_MAP::value_type& j : m_root->m_joints )
1702 {
1703 if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1704 {
1705 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1706 {
1707 aJoints.push_back( &j.second );
1708 n++;
1709 }
1710 }
1711 }
1712
1713 return n;
1714}
1715
1716
1718{
1719 if( aParent && aParent->IsConnected() )
1720 {
1721 const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1722 INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( cItem->GetNet() );
1723
1724 if( l_cur )
1725 {
1726 for( ITEM* item : *l_cur )
1727 {
1728 if( item->Parent() == aParent )
1729 return item;
1730 }
1731 }
1732 }
1733
1734 return nullptr;
1735}
1736
1737
1738std::vector<ITEM*> NODE::FindItemsByParent( const BOARD_ITEM* aParent )
1739{
1740 std::vector<ITEM*> ret;
1741
1742 for( ITEM* item : *m_index )
1743 {
1744 if( item->Parent() == aParent )
1745 ret.push_back( item );
1746 }
1747
1748 return ret;
1749}
1750
1751
1752VIA* NODE::FindViaByHandle ( const VIA_HANDLE& handle ) const
1753{
1754 const JOINT* jt = FindJoint( handle.pos, handle.layers.Start(), handle.net );
1755
1756 if( !jt )
1757 return nullptr;
1758
1759 for( ITEM* item : jt->LinkList() )
1760 {
1761 if( item->OfKind( ITEM::VIA_T ) )
1762 {
1763 if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1764 return static_cast<VIA*>( item );
1765 }
1766 }
1767
1768 return nullptr;
1769}
1770
1771}
1772
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:134
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:213
virtual const std::string Format() const
Definition: pns_item.cpp:338
virtual void Unmark(int aMarker=-1) const
Definition: pns_item.h:262
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
Definition: pns_item.h:242
void SetSourceItem(BOARD_ITEM *aSourceItem)
Definition: pns_item.h:201
const PNS_LAYER_RANGE & Layers() const
Definition: pns_item.h:212
virtual NET_HANDLE Net() const
Definition: pns_item.h:210
PNS_LAYER_RANGE m_layers
Definition: pns_item.h:323
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:173
void SetNet(NET_HANDLE aNet)
Definition: pns_item.h:209
BOARD_ITEM * GetSourceItem() const
Definition: pns_item.h:202
virtual void SetRank(int aRank)
Definition: pns_item.h:265
virtual int Layer() const
Definition: pns_item.h:216
@ SEGMENT_T
Definition: pns_item.h:107
void SetParent(BOARD_ITEM *aParent)
Definition: pns_item.h:191
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:305
bool OfKind(int aKindMask) const
Definition: pns_item.h:181
bool IsVirtual() const
Definition: pns_item.h:295
bool IsRoutable() const
Definition: pns_item.h:284
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:268
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:221
virtual HOLE * Hole() const
Definition: pns_item.h:304
virtual bool HasHole() const
Definition: pns_item.h:303
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:1352
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:1140
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:146
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:138
const VECTOR2I & CLastPoint() const
Definition: pns_line.h:147
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:137
VIA & Via()
Definition: pns_line.h:199
int SegmentCount() const
Definition: pns_line.h:140
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:151
bool EndsWithVia() const
Definition: pns_line.h:191
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:158
virtual int Width() const
Keep the router "world" - i.e.
Definition: pns_node.h:232
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:1594
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:574
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:1145
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:243
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:492
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:1469
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:654
std::vector< std::unique_ptr< SHAPE > > m_edgeExclusions
Definition: pns_node.h:586
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const PNS_LAYER_RANGE &lr, NET_HANDLE aNet)
Definition: pns_node.cpp:1644
void releaseChildren()
Definition: pns_node.cpp:1488
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:568
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:1268
void addHole(HOLE *aHole)
Definition: pns_node.cpp:560
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:242
void unlinkJoint(const VECTOR2I &aPos, const PNS_LAYER_RANGE &aLayers, NET_HANDLE aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1372
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:588
void Dump(bool aLong=false)
Definition: pns_node.cpp:1382
void releaseGarbage()
Definition: pns_node.cpp:1501
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:1138
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:270
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:1302
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:1179
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:1679
std::set< OBSTACLE > OBSTACLES
Definition: pns_node.h:244
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false, bool aAllowSegmentSizeMismatch=true)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:1047
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:582
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:577
void AllItemsInNet(NET_HANDLE aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1555
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:1295
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:580
bool isRoot() const
Definition: pns_node.h:547
VIA * FindViaByHandle(const VIA_HANDLE &handle) const
Definition: pns_node.cpp:1752
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:1549
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:583
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:575
ITEM * FindItemByParent(const BOARD_ITEM *aParent)
Definition: pns_node.cpp:1717
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:570
std::vector< ITEM * > FindItemsByParent(const BOARD_ITEM *aParent)
Definition: pns_node.cpp:1738
NODE * m_parent
node this node was branched from
Definition: pns_node.h:573
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1584
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:1524
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:581
~NODE()
Return the expected clearance between items a and b.
Definition: pns_node.cpp:70
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const PNS_LAYER_RANGE &lr, NET_HANDLE aNet)
Definition: pns_node.cpp:1609
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:1363
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:198
const ITEM * m_item
the item we are looking for collisions with
Definition: pns_node.h:196
bool visit(ITEM *aCandidate)
Definition: pns_node.cpp:203
std::optional< int > m_layerContext
Definition: pns_node.h:200
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:199
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:232
ROUTING_SETTINGS & Settings()
Definition: pns_router.h:206
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:168
virtual int ClearanceEpsilon() const
Definition: pns_node.h:172
virtual int Clearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true)=0
virtual const std::string Format() const override
Definition: pns_line.cpp:1332
const SEG & Seg() const
Definition: pns_segment.h:93
virtual bool HasHole() const override
Definition: pns_solid.h:151
virtual HOLE * Hole() const override
Definition: pns_solid.h:152
const VECTOR2I & Pos() const
Definition: pns_solid.h:117
const VECTOR2I & Pos() const
Definition: pns_via.h:184
virtual HOLE * Hole() const override
Definition: pns_via.h:285
virtual bool HasHole() const override
Definition: pns_via.h:284
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:1019
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.
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...
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
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:395
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:327
const COLLISION_SEARCH_OPTIONS options
Definition: pns_node.h:134
std::set< OBSTACLE > & obstacles
Definition: pns_node.h:133
std::function< bool(const ITEM *)> m_filter
Definition: pns_node.h:120
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:88
int m_distFirst
... and the distance thereof
Definition: pns_node.h:94
int m_maxFanoutWidth
worst case (largest) width of the tracks connected to the item
Definition: pns_node.h:95
ITEM * m_head
Line we search collisions against.
Definition: pns_node.h:89
VECTOR2I m_ipFirst
First intersection between m_head and m_hull.
Definition: pns_node.h:91
ITEM * m_item
Item found to be colliding with m_head.
Definition: pns_node.h:90
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