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
20 * along with this program. If not, see <https://www.gnu.org/licenses/>.
21 */
22
23#include <vector>
24#include <cassert>
25#include <utility>
26
27#include <math/vector2d.h>
28#include <thread_pool.h>
29
30#include <geometry/seg.h>
32#include <pcb_track.h>
33#include <zone.h>
34
35#include <wx/log.h>
36
37#include "pns_arc.h"
38#include "pns_item.h"
39#include "pns_itemset.h"
40#include "pns_line.h"
41#include "pns_node.h"
42#include "pns_via.h"
43#include "pns_solid.h"
44#include "pns_joint.h"
45#include "pns_index.h"
46#include "pns_debug_decorator.h"
47#include "pns_router.h"
48#include "pns_utils.h"
49
50
51namespace PNS {
52
53#ifdef DEBUG
54static std::unordered_set<const NODE*> allocNodes;
55#endif
56
58{
59 m_depth = 0;
60 m_root = this;
61 m_parent = nullptr;
62 m_maxClearance = 800000; // fixme: depends on how thick traces are.
63 m_ruleResolver = nullptr;
64 m_index = new INDEX;
65
66#ifdef DEBUG
67 allocNodes.insert( this );
68#endif
69}
70
71
73{
74 if( !m_children.empty() )
75 {
76 wxLogTrace( wxT( "PNS" ), wxT( "attempting to free a node that has kids." ) );
77 assert( false );
78 }
79
80#ifdef DEBUG
81 if( allocNodes.find( this ) == allocNodes.end() )
82 {
83 wxLogTrace( wxT( "PNS" ), wxT( "attempting to free an already-free'd node." ) );
84 assert( false );
85 }
86
87 allocNodes.erase( this );
88#endif
89
90 m_joints.clear();
91
92 std::vector<const ITEM*> toDelete;
93 std::vector<const ITEM*> parentedHoles;
94
95 toDelete.reserve( m_index->Size() );
96
97 for( ITEM* item : *m_index )
98 {
99 if( item->BelongsTo( this ) )
100 {
101 if ( item->OfKind( ITEM::HOLE_T ) )
102 {
103 HOLE* hole = static_cast<HOLE*>( item );
104 if( hole->ParentPadVia() )
105 {
106 // If a hole is no longer owned by the same NODE as its parent then we're in a
107 // heap of trouble.
108 assert( hole->ParentPadVia()->BelongsTo( this ) );
109
110 // Its parent comes by as a VIA or SOLID, and deletes only a hole it owns
111 if( hole->ParentPadVia()->BelongsTo( this ) )
112 {
113 hole->SetOwner( hole->ParentPadVia() );
114 parentedHoles.push_back( hole );
115 }
116 }
117 else
118 {
119 // freestanding hole
120 toDelete.push_back(item);
121 }
122 }
123 else {
124 // other geometry with no holes
125 toDelete.push_back(item);
126 }
127 }
128 }
129
130 if( m_ruleResolver )
131 {
132 m_ruleResolver->ClearCacheForItems( toDelete );
133 m_ruleResolver->ClearCacheForItems( parentedHoles );
134 }
135
136 for( const ITEM* item : toDelete )
137 {
138 wxLogTrace( wxT( "PNS" ), wxT( "del item %p type %s" ), item, item->KindStr().c_str() );
139 delete item;
140 }
141
143 unlinkParent();
144
145 delete m_index;
146}
147
148int NODE::GetClearance( const ITEM* aA, const ITEM* aB, bool aUseClearanceEpsilon, const COLLISION_SEARCH_OPTIONS& aOpts ) const
149{
150 if( !m_ruleResolver )
151 return 100000;
152
153 if( aA->IsVirtual() || aB->IsVirtual() )
154 return 0;
155
156 int rrClearance = m_ruleResolver->Clearance( aA, aB, aUseClearanceEpsilon );
157
158 if( aOpts.m_overrideClearance && ( rrClearance > 0 || aOpts.m_overrideExemptPairs ) )
159 {
160 int overriddenClearance = aOpts.m_overrideClearance( aA, aB, CLEARANCE_ASPECT::ASP_DEFAULT );
161
162 // fixme: negative return value from clearance override lambda indicates return to default. Perhaps an enum or a constant
163 // for this case would be better here
164 if( overriddenClearance < 0 )
165 return rrClearance;
166 else
167 return overriddenClearance;
168 }
169
170 return rrClearance;
171}
172
173
175{
176 NODE* child = new NODE;
177
178 m_children.insert( child );
179
180 child->m_depth = m_depth + 1;
181 child->m_parent = this;
183 child->m_root = isRoot() ? this : m_root;
185
186 // Immediate offspring of the root branch needs not copy anything. For the rest, clone
187 // the spatial index, joints, and overridden item maps.
188 if( !isRoot() )
189 {
190 delete child->m_index;
191 child->m_index = m_index->Clone().release();
192
193 child->m_joints = m_joints;
194 child->m_override = m_override;
195 }
196
197#if 0
198 wxLogTrace( wxT( "PNS" ), wxT( "%d items, %d joints, %d overrides" ),
199 child->m_index->Size(),
200 (int) child->m_joints.size(),
201 (int) child->m_override.size() );
202#endif
203
204 return child;
205}
206
207
209{
210 if( isRoot() )
211 return;
212
213 m_parent->m_children.erase( this );
214}
215
216
218 m_item( aItem ),
219 m_node( nullptr ),
220 m_override( nullptr )
221{
222}
223
224
225void OBSTACLE_VISITOR::SetWorld( const NODE* aNode, const NODE* aOverride )
226{
227 m_node = aNode;
228 m_override = aOverride;
229}
230
231
232bool OBSTACLE_VISITOR::visit( ITEM* aCandidate )
233{
234 // check if there is a more recent branch with a newer (possibly modified) version of this
235 // item.
236 if( m_override && m_override->Overrides( aCandidate ) )
237 return true;
238
239 return false;
240}
241
242
243// function object that visits potential obstacles and performs the actual collision refining
245{
247
249 OBSTACLE_VISITOR( aItem ),
250 m_ctx( aCtx )
251 {
252 }
253
255 {
256 }
257
258 bool operator()( ITEM* aCandidate ) override
259 {
260 if( !aCandidate->OfKind( m_ctx->options.m_kindMask ) )
261 return true;
262
263 // Collisions with self aren't a thing; don't spend time on them.
264 if( m_item == aCandidate )
265 return true;
266
267 if( m_ctx->options.m_filter && !m_ctx->options.m_filter( aCandidate, m_item ) )
268 return true;
269
270 if( visit( aCandidate ) )
271 return true;
272
273 if( !aCandidate->Collide( m_item, m_node, m_layerContext.value_or( -1 ), m_ctx ) )
274 return true;
275
276 if( m_ctx->options.m_limitCount > 0 && (int) m_ctx->obstacles.size() >= m_ctx->options.m_limitCount )
277 return false;
278
279 return true;
280 };
281};
282
283
284int NODE::QueryColliding( const ITEM* aItem, NODE::OBSTACLES& aObstacles,
285 const COLLISION_SEARCH_OPTIONS& aOpts ) const
286{
287 COLLISION_SEARCH_CONTEXT ctx( aObstacles, aOpts );
288
290 if( aItem->IsVirtual() )
291 return 0;
292
293 DEFAULT_OBSTACLE_VISITOR visitor( &ctx, aItem );
294
295#ifdef DEBUG
296 assert( allocNodes.find( this ) != allocNodes.end() );
297#endif
298
299 visitor.SetWorld( this, nullptr );
300
301 // first, look for colliding items in the local index
302 m_index->Query( aItem, m_maxClearance, visitor );
303
304 // if we haven't found enough items, look in the root branch as well.
305 if( !isRoot() && ( (int) ctx.obstacles.size() < aOpts.m_limitCount || aOpts.m_limitCount < 0 ) )
306 {
307 visitor.SetWorld( m_root, this );
308 m_root->m_index->Query( aItem, m_maxClearance, visitor );
309 }
310
311 return aObstacles.size();
312}
313
314
316 const COLLISION_SEARCH_OPTIONS& aOpts )
317{
319 OBSTACLES obstacleSet;
320
321 for( int i = 0; i < aLine->CLine().SegmentCount(); i++ )
322 {
323 // Note: Clearances between &s and other items are cached,
324 // which means they'll be the same for all segments in the line.
325 // Disabling the cache will lead to slowness.
326
327 const SEGMENT s( *aLine, aLine->CLine().CSegment( i ) );
328 QueryColliding( &s, obstacleSet, aOpts );
329 }
330
331 if( aLine->EndsWithVia() )
332 QueryColliding( &aLine->Via(), obstacleSet, aOpts );
333
334 if( obstacleSet.empty() )
335 return OPT_OBSTACLE();
336
337 // Convert to indexed vector for parallel access.
338 std::vector<OBSTACLE> obstacles( obstacleSet.begin(), obstacleSet.end() );
339 const int numObstacles = (int) obstacles.size();
340
341 const int layer = aLine->Layer();
342 RULE_RESOLVER* ruleResolver = GetRuleResolver();
343 const bool simplifyHull = ( cornerMode == DIRECTION_45::MITERED_90
344 || cornerMode == DIRECTION_45::ROUNDED_90 );
345 const bool hasVia = aLine->EndsWithVia();
346
347 auto makeHull = [&]( const SHAPE_LINE_CHAIN& cachedHull ) -> SHAPE_LINE_CHAIN
348 {
349 if( simplifyHull )
350 {
351 BOX2I bbox = cachedHull.BBox();
352 SHAPE_LINE_CHAIN hull;
353 hull.Append( bbox.GetLeft(), bbox.GetTop() );
354 hull.Append( bbox.GetRight(), bbox.GetTop() );
355 hull.Append( bbox.GetRight(), bbox.GetBottom() );
356 hull.Append( bbox.GetLeft(), bbox.GetBottom() );
357 hull.SetClosed( true );
358 return hull;
359 }
360
361 return cachedHull;
362 };
363
364 // The first step here is sequential since GetClearance() and HullCache() are not thread-safe.
365 // So, we populate all caches first and copy the returned hull references into owned values
366 // before releasing the sequential phase.
367 struct ObstacleHullData
368 {
369 SHAPE_LINE_CHAIN lineHull;
370 SHAPE_LINE_CHAIN viaHull; // only populated when hasVia
371 };
372
373 std::vector<ObstacleHullData> hullData( numObstacles );
374
375 for( int i = 0; i < numObstacles; i++ )
376 {
377 const OBSTACLE& obstacle = obstacles[i];
378
379 int clearance = GetClearance( obstacle.m_item, aLine, aOpts.m_useClearanceEpsilon, aOpts )
380 + aLine->Width() / 2;
381
382 hullData[i].lineHull = makeHull( ruleResolver->HullCache( obstacle.m_item, clearance,
383 0, layer ) );
384
385 if( hasVia )
386 {
387 const VIA& via = aLine->Via();
388 int viaClearance = GetClearance( obstacle.m_item, &via, aOpts.m_useClearanceEpsilon, aOpts )
389 + via.Diameter( aLine->Layer() ) / 2;
390
391 hullData[i].viaHull = makeHull( ruleResolver->HullCache( obstacle.m_item,
392 viaClearance, 0, layer ) );
393 }
394 }
395
396 // Run the obstacle finding in parallel and bring the results together afte
397 struct ObstacleResult
398 {
399 int dist = INT_MAX;
400 VECTOR2I ip;
401 };
402
403 std::vector<ObstacleResult> results( numObstacles );
404 const SHAPE_LINE_CHAIN& linePath = aLine->CLine();
405
406 auto processObstacle = [&]( int i )
407 {
408 std::vector<SHAPE_LINE_CHAIN::INTERSECTION> ips;
409 ObstacleResult& result = results[i];
410
411 HullIntersection( hullData[i].lineHull, linePath, ips );
412
413 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : ips )
414 {
415 if( !ip.valid )
416 continue;
417
418 int dist = linePath.PathLength( ip.p, ip.index_their );
419
420 if( dist < result.dist )
421 {
422 result.dist = dist;
423 result.ip = ip.p;
424 }
425 }
426
427 if( hasVia )
428 {
429 ips.clear();
430 HullIntersection( hullData[i].viaHull, linePath, ips );
431
432 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : ips )
433 {
434 if( !ip.valid )
435 continue;
436
437 int dist = linePath.PathLength( ip.p, ip.index_their );
438
439 if( dist < result.dist )
440 {
441 result.dist = dist;
442 result.ip = ip.p;
443 }
444 }
445 }
446 };
447
448 // Each task submission locks the thread pool's priority queue mutex, and thread wakeup
449 // latency is ~5-20µs. With too few items per block the synchronization cost exceeds the
450 // geometry work. Use a minimum chunk size so blocks are always worth dispatching, while
451 // still entering the parallel path at a lower obstacle count than a flat threshold allows.
452 constexpr int MIN_OBSTACLES_PER_BLOCK = 8;
453 constexpr int PARALLEL_THRESHOLD = MIN_OBSTACLES_PER_BLOCK;
454
455 if( numObstacles > PARALLEL_THRESHOLD )
456 {
458 std::size_t numBlocks = std::max<std::size_t>( 1, numObstacles / MIN_OBSTACLES_PER_BLOCK );
459
460 auto futures = tp.submit_loop( 0, numObstacles, [&]( int i ) { processObstacle( i ); },
461 numBlocks );
462 futures.wait();
463 }
464 else
465 {
466 for( int i = 0; i < numObstacles; i++ )
467 processObstacle( i );
468 }
469
470 OBSTACLE nearest;
471 nearest.m_head = nullptr;
472 nearest.m_item = nullptr;
473 nearest.m_distFirst = INT_MAX;
474 nearest.m_maxFanoutWidth = 0;
475
476 for( int i = 0; i < numObstacles; i++ )
477 {
478 if( results[i].dist < nearest.m_distFirst )
479 {
480 nearest = obstacles[i];
481 nearest.m_distFirst = results[i].dist;
482 nearest.m_ipFirst = results[i].ip;
483
484 if( results[i].dist == 0 )
485 break;
486 }
487 }
488
489 if( nearest.m_distFirst == INT_MAX )
490 nearest = obstacles[0];
491
492 return nearest;
493}
494
495
497{
498 for( const ITEM* item : aSet.CItems() )
499 {
500 OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
501
502 if( obs )
503 return obs;
504 }
505
506 return OPT_OBSTACLE();
507}
508
509
510NODE::OPT_OBSTACLE NODE::CheckColliding( const ITEM* aItemA, int aKindMask )
511{
513
514 opts.m_kindMask = aKindMask;
515 opts.m_limitCount = 1;
516
517 return CheckColliding( aItemA, opts );
518}
519
521{
522 OBSTACLES obs;
523
524 if( aItemA->Kind() == ITEM::LINE_T )
525 {
526 int n = 0;
527 const LINE* line = static_cast<const LINE*>( aItemA );
528 const SHAPE_LINE_CHAIN& l = line->CLine();
529
530 for( int i = 0; i < l.SegmentCount(); i++ )
531 {
532 // Note: Clearances between &s and other items are cached,
533 // which means they'll be the same for all segments in the line.
534 // Disabling the cache will lead to slowness.
535
536 const SEGMENT s( *line, l.CSegment( i ) );
537 n += QueryColliding( &s, obs, aOpts );
538
539 if( n )
540 return OPT_OBSTACLE( *obs.begin() );
541 }
542
543 if( line->EndsWithVia() )
544 {
545 n += QueryColliding( &line->Via(), obs, aOpts );
546
547 if( n )
548 return OPT_OBSTACLE( *obs.begin() );
549 }
550 }
551 else if( QueryColliding( aItemA, obs, aOpts ) > 0 )
552 {
553 return OPT_OBSTACLE( *obs.begin() );
554 }
555
556 return OPT_OBSTACLE();
557}
558
559
561{
564
565 HIT_VISITOR( ITEM_SET& aTab, const VECTOR2I& aPoint ) :
566 OBSTACLE_VISITOR( nullptr ),
567 m_items( aTab ),
568 m_point( aPoint )
569 {}
570
571 virtual ~HIT_VISITOR()
572 {
573 }
574
575 bool operator()( ITEM* aItem ) override
576 {
577 SHAPE_CIRCLE cp( m_point, 0 );
578
579 int cl = 0;
580
581 // TODO(JE) padstacks -- this may not work
582 if( aItem->Shape( -1 )->Collide( &cp, cl ) )
583 m_items.Add( aItem );
584
585 return true;
586 }
587};
588
589
590const ITEM_SET NODE::HitTest( const VECTOR2I& aPoint ) const
591{
592 ITEM_SET items;
593
594 // fixme: we treat a point as an infinitely small circle - this is inefficient.
595 SHAPE_CIRCLE s( aPoint, 0 );
596 HIT_VISITOR visitor( items, aPoint );
597 visitor.SetWorld( this, nullptr );
598
599 m_index->Query( &s, m_maxClearance, visitor );
600
601 if( !isRoot() ) // fixme: could be made cleaner
602 {
603 ITEM_SET items_root;
604 visitor.SetWorld( m_root, nullptr );
605 HIT_VISITOR visitor_root( items_root, aPoint );
606 m_root->m_index->Query( &s, m_maxClearance, visitor_root );
607
608 for( ITEM* item : items_root.Items() )
609 {
610 if( !Overrides( item ) )
611 items.Add( item );
612 }
613 }
614
615 return items;
616}
617
618
619void NODE::addSolid( SOLID* aSolid )
620{
621 if( aSolid->HasHole() )
622 {
623 assert( aSolid->Hole()->BelongsTo( aSolid ) );
624 addHole( aSolid->Hole() );
625 }
626
627 if( aSolid->IsRoutable() )
628 linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
629
630 aSolid->SetOwner( this );
631 m_index->Add( aSolid );
632}
633
634
635void NODE::Add( std::unique_ptr< SOLID > aSolid )
636{
637 aSolid->SetOwner( this );
638 addSolid( aSolid.release() );
639}
640
641
642void NODE::addVia( VIA* aVia )
643{
644 if( aVia->HasHole() )
645 {
646 if( ! aVia->Hole()->BelongsTo( aVia ) )
647 {
648 assert( false );
649 }
650 addHole( aVia->Hole() );
651 }
652
653 linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
654 aVia->SetOwner( this );
655
656 m_index->Add( aVia );
657}
658
659
660void NODE::addHole( HOLE* aHole )
661{
662 // do we need holes in the connection graph?
663 //linkJoint( aHole->Pos(), aHole->Layers(), aHole->Net(), aHole );
664
665 aHole->SetOwner( this );
666 m_index->Add( aHole );
667}
668
669
670void NODE::Add( std::unique_ptr< VIA > aVia )
671{
672 addVia( aVia.release() );
673}
674
675
676void NODE::add( ITEM* aItem, bool aAllowRedundant )
677{
678 switch( aItem->Kind() )
679 {
680 case ITEM::ARC_T:
681 addArc( static_cast<ARC*>( aItem ) );
682 break;
683 case ITEM::SEGMENT_T:
684 addSegment( static_cast<SEGMENT*>( aItem ) );
685 break;
686 case ITEM::VIA_T:
687 addVia( static_cast<VIA*>( aItem ) );
688 break;
689 case ITEM::SOLID_T:
690 addSolid( static_cast<SOLID*>( aItem ) );
691 break;
692 case ITEM::HOLE_T:
693 // added by parent VIA_T or SOLID_T (pad)
694 break;
695 default:
696 assert( false );
697 }
698}
699
700
701void NODE::Add( LINE& aLine, bool aAllowRedundant )
702{
703 assert( !aLine.IsLinked() );
704
705 SHAPE_LINE_CHAIN& l = aLine.Line();
706
707 for( size_t i = 0; i < l.ArcCount(); i++ )
708 {
709 auto s = l.Arc( i );
710 ARC* rarc;
711
712 if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(),
713 aLine.Net() ) ) )
714 {
715 aLine.Link( rarc );
716 }
717 else
718 {
719 auto newarc = std::make_unique< ARC >( aLine, s );
720 aLine.Link( newarc.get() );
721 Add( std::move( newarc ), true );
722 }
723 }
724
725 for( int i = 0; i < l.SegmentCount(); i++ )
726 {
727 if( l.IsArcSegment( i ) )
728 continue;
729
730 SEG s = l.CSegment( i );
731
732 if( s.A != s.B )
733 {
734 SEGMENT* rseg;
735
736 if( !aAllowRedundant && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(),
737 aLine.Net() ) ) )
738 {
739 // another line could be referencing this segment too :(
740 if( !aLine.ContainsLink( rseg ) )
741 aLine.Link( rseg );
742 }
743 else
744 {
745 std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
746 aLine.Link( newseg.get() );
747 Add( std::move( newseg ), true );
748 }
749 }
750 }
751}
752
753
755{
756 aSeg->SetOwner( this );
757
758 linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
759 linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
760
761 m_index->Add( aSeg );
762}
763
764
765bool NODE::Add( std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant )
766{
767 if( aSegment->Seg().A == aSegment->Seg().B )
768 {
769 wxLogTrace( wxT( "PNS" ),
770 wxT( "attempting to add a segment with same end coordinates, ignoring." ) );
771 return false;
772 }
773
774 if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
775 return false;
776
777 addSegment( aSegment.release() );
778
779 return true;
780}
781
782
783void NODE::addArc( ARC* aArc )
784{
785 aArc->SetOwner( this );
786
787 linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
788 linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
789
790 m_index->Add( aArc );
791}
792
793
794bool NODE::Add( std::unique_ptr< ARC > aArc, bool aAllowRedundant )
795{
796 const SHAPE_ARC& arc = aArc->CArc();
797
798 if( !aAllowRedundant && findRedundantArc( arc.GetP0(), arc.GetP1(), aArc->Layers(),
799 aArc->Net() ) )
800 {
801 return false;
802 }
803
804 addArc( aArc.release() );
805 return true;
806}
807
808
809void NODE::AddEdgeExclusion( std::unique_ptr<SHAPE> aShape )
810{
811 m_edgeExclusions.push_back( std::move( aShape ) );
812}
813
814
815bool NODE::QueryEdgeExclusions( const VECTOR2I& aPos ) const
816{
817 for( const std::unique_ptr<SHAPE>& edgeExclusion : m_edgeExclusions )
818 {
819 if( edgeExclusion->Collide( aPos ) )
820 return true;
821 }
822
823 return false;
824}
825
826
827void NODE::doRemove( ITEM* aItem )
828{
829 bool holeRemoved = false; // fixme: better logic, I don't like this
830
831 // case 1: removing an item that is stored in the root node from any branch:
832 // mark it as overridden, but do not remove
833 if( aItem->BelongsTo( m_root ) && !isRoot() )
834 {
835 m_override.insert( aItem );
836
837 if( aItem->HasHole() )
838 m_override.insert( aItem->Hole() );
839 }
840
841 // case 2: the item belongs to this branch or a parent, non-root branch,
842 // or the root itself and we are the root: remove from the index
843 else if( !aItem->BelongsTo( m_root ) || isRoot() )
844 {
845 m_index->Remove( aItem );
846
847 if( aItem->HasHole() )
848 {
849 m_index->Remove( aItem->Hole() );
850 holeRemoved = true;
851 }
852 }
853
854 // the item belongs to this particular branch: un-reference it
855 if( aItem->BelongsTo( this ) )
856 {
857 aItem->SetOwner( nullptr );
858 m_root->m_garbageItems.insert( aItem );
859 HOLE *hole = aItem->Hole();
860
861 if( hole )
862 {
863 if( ! holeRemoved )
864 {
865 m_index->Remove( hole ); // hole is not directly owned by NODE but by the parent SOLID/VIA.
866 }
867
868 hole->SetOwner( aItem );
869 }
870 }
871}
872
873
875{
876 unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
877 unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
878}
879
880
882{
883 unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
884 unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
885}
886
887
888void NODE::rebuildJoint( const JOINT* aJoint, const ITEM* aItem )
889{
890 if( !aJoint )
891 return;
892
893 // We have to split a single joint (associated with a via or a pad, binding together multiple
894 // layers) into multiple independent joints. As I'm a lazy bastard, I simply delete the
895 // via/solid and all its links and re-insert them.
896
897 std::vector<ITEM*> links( aJoint->LinkList() );
898 JOINT::HASH_TAG tag;
899 NET_HANDLE net = aItem->Net();
900
901 tag.net = net;
902 tag.pos = aJoint->Pos();
903
904 bool split;
905
906 do
907 {
908 split = false;
909 auto range = m_joints.equal_range( tag );
910
911 if( range.first == m_joints.end() )
912 break;
913
914 // find and remove all joints containing the via to be removed
915
916 for( auto f = range.first; f != range.second; ++f )
917 {
918 if( aItem->LayersOverlap( &f->second ) )
919 {
920 m_joints.erase( f );
921 split = true;
922 break;
923 }
924 }
925 } while( split );
926
927 bool completelyErased = false;
928
929 if( !isRoot() && m_joints.find( tag ) == m_joints.end() )
930 {
931 JOINT jtDummy( tag.pos, PNS_LAYER_RANGE(-1), tag.net );
932
933 m_joints.insert( TagJointPair( tag, jtDummy ) );
934 completelyErased = true;
935 }
936
937
938 // and re-link them, using the former via's link list
939 for( ITEM* link : links )
940 {
941 if( link != aItem )
942 linkJoint( tag.pos, link->Layers(), net, link );
943 else if( !completelyErased )
944 unlinkJoint( tag.pos, link->Layers(), net, link );
945 }
946}
947
948
950{
951 const JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
952 assert( jt );
953 rebuildJoint( jt, aVia );
954}
955
956
958{
959 if( !aSolid->IsRoutable() )
960 return;
961
962 // fixme: redundant code
963 const JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
964 assert( jt );
965 rebuildJoint( jt, aSolid );
966}
967
968
969void NODE::Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem )
970{
971 Remove( aOldItem );
972 add( aNewItem.release() );
973}
974
975
976void NODE::Replace( LINE& aOldLine, LINE& aNewLine, bool aAllowRedundantSegments )
977{
978 Remove( aOldLine );
979 Add( aNewLine, aAllowRedundantSegments );
980}
981
982
983void NODE::Remove( SOLID* aSolid )
984{
985 removeSolidIndex( aSolid );
986 doRemove( aSolid );
987}
988
989
990void NODE::Remove( VIA* aVia )
991{
992 removeViaIndex( aVia );
993 doRemove( aVia );
994
995 if( !aVia->Owner() )
996 {
997 assert( aVia->Hole()->BelongsTo( aVia ) );
998 }
999}
1000
1001
1002void NODE::Remove( SEGMENT* aSegment )
1003{
1004 removeSegmentIndex( aSegment );
1005 doRemove( aSegment );
1006}
1007
1008
1009void NODE::Remove( ARC* aArc )
1010{
1011 removeArcIndex( aArc );
1012 doRemove( aArc );
1013}
1014
1015
1016void NODE::Remove( ITEM* aItem )
1017{
1018 switch( aItem->Kind() )
1019 {
1020 case ITEM::ARC_T:
1021 Remove( static_cast<ARC*>( aItem ) );
1022 break;
1023
1024 case ITEM::SOLID_T:
1025 {
1026 SOLID* solid = static_cast<SOLID*>( aItem );
1027
1028 if( solid->HasHole() )
1029 {
1030 Remove( solid->Hole() );
1031 solid->Hole()->SetOwner( solid );
1032 }
1033
1034 Remove( static_cast<SOLID*>( aItem ) );
1035 break;
1036 }
1037
1038 case ITEM::SEGMENT_T:
1039 Remove( static_cast<SEGMENT*>( aItem ) );
1040 break;
1041
1042 case ITEM::LINE_T:
1043 {
1044 LINE* l = static_cast<LINE*>( aItem );
1045
1046 for ( LINKED_ITEM* s : l->Links() )
1047 Remove( s );
1048
1049 break;
1050 }
1051
1052 case ITEM::VIA_T:
1053 {
1054 VIA* via = static_cast<VIA*>( aItem );
1055
1056 if( via->HasHole() )
1057 {
1058 Remove( via->Hole() );
1059 via->Hole()->SetOwner( via );
1060 }
1061
1062 Remove( static_cast<VIA*>( aItem ) );
1063 break;
1064 }
1065
1066 default:
1067 break;
1068 }
1069}
1070
1071
1072void NODE::Remove( LINE& aLine )
1073{
1074 // LINE does not have a separate remover, as LINEs are never truly a member of the tree
1075 std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
1076
1077 for( LINKED_ITEM* li : segRefs )
1078 {
1079 if( li->OfKind( ITEM::SEGMENT_T ) )
1080 Remove( static_cast<SEGMENT*>( li ) );
1081 else if( li->OfKind( ITEM::ARC_T ) )
1082 Remove( static_cast<ARC*>( li ) );
1083 else if( li->OfKind( ITEM::VIA_T ) )
1084 Remove( static_cast<VIA*>( li ) );
1085 }
1086
1087 aLine.SetOwner( nullptr );
1088 aLine.ClearLinks();
1089}
1090
1091
1092void NODE::followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
1093 VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
1094 bool& aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments,
1095 bool aAllowSegmentSizeMismatch )
1096{
1097 bool prevReversed = false;
1098
1099 const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
1100 const int startWidth = aCurrent->Width();
1101
1102 for( int count = 0 ; ; ++count )
1103 {
1104 const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
1105 const JOINT* jt = FindJoint( p, aCurrent );
1106
1107 if( !jt )
1108 break;
1109
1110 aCorners[aPos] = jt->Pos();
1111 aSegments[aPos] = aCurrent;
1112 aArcReversed[aPos] = false;
1113
1114 if( aCurrent->Kind() == ITEM::ARC_T )
1115 {
1116 if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) )
1117 || ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
1118 {
1119 aArcReversed[aPos] = true;
1120 }
1121 }
1122
1123 aPos += ( aScanDirection ? 1 : -1 );
1124
1125 if( count && guard == p )
1126 {
1127 if( aPos >= 0 && aPos < aLimit )
1128 aSegments[aPos] = nullptr;
1129
1130 aGuardHit = true;
1131 break;
1132 }
1133
1134 bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
1135
1136 if( locked || aPos < 0 || aPos == aLimit )
1137 break;
1138
1139 LINKED_ITEM* next = jt->NextSegment( aCurrent, aFollowLockedSegments );
1140
1141 if( !next || ( !aAllowSegmentSizeMismatch && next->Width() != startWidth ) )
1142 break;
1143
1144 aCurrent = next;
1145 prevReversed = ( aCurrent && jt->Pos() == aCurrent->Anchor( aScanDirection ) );
1146 }
1147}
1148
1149
1150const LINE NODE::AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex, bool aStopAtLockedJoints,
1151 bool aFollowLockedSegments, bool aAllowSegmentSizeMismatch )
1152{
1153 const int MaxVerts = 1024 * 16;
1154
1155 std::array<VECTOR2I, MaxVerts + 1> corners;
1156 std::array<LINKED_ITEM*, MaxVerts + 1> segs;
1157 std::array<bool, MaxVerts + 1> arcReversed;
1158
1159 LINE pl;
1160 bool guardHit = false;
1161
1162 int i_start = MaxVerts / 2;
1163 int i_end = i_start + 1;
1164
1165 pl.SetWidth( aSeg->Width() );
1166 pl.SetLayers( aSeg->Layers() );
1167 pl.SetNet( aSeg->Net() );
1168 pl.SetParent( nullptr );
1169 pl.SetSourceItem( aSeg->GetSourceItem() );
1170 pl.SetOwner( this );
1171
1172 followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1173 guardHit, aStopAtLockedJoints, aFollowLockedSegments, aAllowSegmentSizeMismatch );
1174
1175 if( !guardHit )
1176 {
1177 followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1178 guardHit, aStopAtLockedJoints, aFollowLockedSegments, aAllowSegmentSizeMismatch );
1179 }
1180
1181 int n = 0;
1182
1183 LINKED_ITEM* prev_seg = nullptr;
1184 bool originSet = false;
1185
1186 SHAPE_LINE_CHAIN& line = pl.Line();
1187
1188 for( int i = i_start + 1; i < i_end; i++ )
1189 {
1190 const VECTOR2I& p = corners[i];
1191 LINKED_ITEM* li = segs[i];
1192
1193 if( !li || li->Kind() != ITEM::ARC_T )
1194 line.Append( p );
1195
1196 if( li && prev_seg != li )
1197 {
1198 if( li->Kind() == ITEM::ARC_T )
1199 {
1200 const ARC* arc = static_cast<const ARC*>( li );
1201 const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape( -1 ) );
1202
1203 line.Append( arcReversed[i] ? sa->Reversed() : *sa );
1204 }
1205
1206 pl.Link( li );
1207
1208 // latter condition to avoid loops
1209 if( li == aSeg && aOriginSegmentIndex && !originSet )
1210 {
1211 wxASSERT( n < line.SegmentCount() ||
1212 ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
1213 *aOriginSegmentIndex = line.PointCount() - 1;
1214 originSet = true;
1215 }
1216 }
1217
1218 prev_seg = li;
1219 }
1220
1221 // Remove duplicate verts, but do NOT remove colinear segments here!
1223
1224 // TODO: maintain actual segment index under simplification system
1225 if( aOriginSegmentIndex && *aOriginSegmentIndex >= pl.SegmentCount() )
1226 *aOriginSegmentIndex = pl.SegmentCount() - 1;
1227
1228 wxASSERT_MSG( pl.SegmentCount() != 0, "assembled line should never be empty" );
1229
1230 return pl;
1231}
1232
1233
1234void NODE::FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB )
1235{
1236 aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
1237 aB = *FindJoint( aLine.CLastPoint(), &aLine );
1238}
1239
1240
1241int NODE::FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines )
1242{
1243 for( ITEM* item : aA.LinkList() )
1244 {
1245 if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
1246 {
1247 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1248 LINE line = AssembleLine( li );
1249
1250 if( !line.Layers().Overlaps( aB.Layers() ) )
1251 continue;
1252
1253 JOINT j_start, j_end;
1254
1255 FindLineEnds( line, j_start, j_end );
1256
1257 int id_start = line.CLine().Find( aA.Pos() );
1258 int id_end = line.CLine().Find( aB.Pos() );
1259
1260 if( id_end < id_start )
1261 std::swap( id_end, id_start );
1262
1263 if( id_start >= 0 && id_end >= 0 )
1264 {
1265 line.ClipVertexRange( id_start, id_end );
1266 aLines.push_back( line );
1267 }
1268 }
1269 }
1270
1271 return 0;
1272}
1273
1274
1276{
1277 m_index->SetDeferred( true );
1278}
1279
1280
1282{
1283 m_index->SetDeferred( false );
1284 m_index->BuildSpatialIndex();
1285}
1286
1287
1289{
1290 const SEGMENT* locked_seg = nullptr;
1291 std::vector<VVIA*> vvias;
1292
1293 for( auto& jointPair : m_joints )
1294 {
1295 JOINT joint = jointPair.second;
1296
1297 if( joint.Layers().IsMultilayer() )
1298 continue;
1299
1300 int n_seg = 0;
1301 int n_solid = 0;
1302 int n_vias = 0;
1303 int prev_w = -1;
1304 bool prev_mask = false;
1305 std::optional<int> prev_mask_margin;
1306 int max_w = -1;
1307 bool is_width_change = false;
1308 bool is_locked = false;
1309
1310 for( const ITEM* item : joint.LinkList() )
1311 {
1312 if( item->OfKind( ITEM::VIA_T ) )
1313 {
1314 n_vias++;
1315 }
1316 else if( item->OfKind( ITEM::SOLID_T ) )
1317 {
1318 n_solid++;
1319 }
1320 else if( const auto t = dyn_cast<const PNS::SEGMENT*>( item ) )
1321 {
1322 int w = t->Width();
1323 bool mask = false;
1324 std::optional<int> mask_margin;
1325
1326 if( PCB_TRACK* track = static_cast<PCB_TRACK*>( t->Parent() ) )
1327 {
1328 mask = track->HasSolderMask();
1329 mask_margin = track->GetLocalSolderMaskMargin();
1330 }
1331
1332 if( prev_w < 0 )
1333 {
1334 prev_w = w;
1335 prev_mask = mask;
1336 prev_mask_margin = mask_margin;
1337 }
1338 else if( w != prev_w || mask != prev_mask || mask_margin != prev_mask_margin )
1339 {
1340 is_width_change = true;
1341 }
1342
1343 max_w = std::max( w, max_w );
1344 prev_w = w;
1345
1346 is_locked = t->IsLocked();
1347 locked_seg = t;
1348 }
1349 }
1350
1351 if( ( is_width_change || n_seg >= 3 || is_locked ) && n_solid == 0 && n_vias == 0 )
1352 {
1353 // fixme: the hull margin here is an ugly temporary workaround. The real fix
1354 // is to use octagons for via force propagation.
1355 vvias.push_back( new VVIA( joint.Pos(), joint.Layers().Start(),
1356 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1357 }
1358
1359 if( is_locked )
1360 {
1361 const VECTOR2I& secondPos = ( locked_seg->Seg().A == joint.Pos() ) ?
1362 locked_seg->Seg().B :
1363 locked_seg->Seg().A;
1364
1365 vvias.push_back( new VVIA( secondPos, joint.Layers().Start(),
1366 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1367 }
1368 }
1369
1370 for( auto vvia : vvias )
1371 {
1372 Add( ItemCast<VIA>( std::unique_ptr<VVIA>( vvia ) ) );
1373 }
1374}
1375
1376
1377const JOINT* NODE::FindJoint( const VECTOR2I& aPos, int aLayer, NET_HANDLE aNet ) const
1378{
1379 JOINT::HASH_TAG tag;
1380
1381 tag.net = aNet;
1382 tag.pos = aPos;
1383
1384 JOINT_MAP::const_iterator f = m_joints.find( tag ), end = m_joints.end();
1385
1386 if( f == end && !isRoot() )
1387 {
1388 end = m_root->m_joints.end();
1389 f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1390 }
1391
1392 while( f != end )
1393 {
1394 if( f->second.Pos() == aPos && f->second.Net() == aNet && f->second.Layers().Overlaps( aLayer ) )
1395 return &f->second;
1396
1397 f++;
1398 }
1399
1400 return nullptr;
1401}
1402
1403
1404void NODE::LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock )
1405{
1406 JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1407 jt.Lock( aLock );
1408}
1409
1410
1411JOINT& NODE::touchJoint( const VECTOR2I& aPos, const PNS_LAYER_RANGE& aLayers, NET_HANDLE aNet )
1412{
1413 JOINT::HASH_TAG tag;
1414
1415 tag.pos = aPos;
1416 tag.net = aNet;
1417
1418 // try to find the joint in this node.
1419 JOINT_MAP::iterator f = m_joints.find( tag );
1420
1421 std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1422
1423 // not found and we are not root? find in the root and copy results here.
1424 if( f == m_joints.end() && !isRoot() )
1425 {
1426 range = m_root->m_joints.equal_range( tag );
1427
1428 for( f = range.first; f != range.second; ++f )
1429 m_joints.insert( *f );
1430 }
1431
1432 // now insert and combine overlapping joints
1433 JOINT jt( aPos, aLayers, aNet );
1434
1435 bool merged;
1436
1437 do
1438 {
1439 merged = false;
1440 range = m_joints.equal_range( tag );
1441
1442 if( range.first == m_joints.end() )
1443 break;
1444
1445 for( f = range.first; f != range.second; ++f )
1446 {
1447 if( aLayers.Overlaps( f->second.Layers() ) )
1448 {
1449 jt.Merge( f->second );
1450 m_joints.erase( f );
1451 merged = true;
1452 break;
1453 }
1454 }
1455 } while( merged );
1456
1457 return m_joints.insert( TagJointPair( tag, jt ) )->second;
1458}
1459
1460
1461void JOINT::Dump() const
1462{
1463 wxLogTrace( wxT( "PNS" ), wxT( "joint layers %d-%d, net %d, pos %s, links: %d" ),
1464 m_layers.Start(),
1465 m_layers.End(),
1466 m_tag.net,
1467 m_tag.pos.Format().c_str(),
1468 LinkCount() );
1469}
1470
1471
1472void NODE::linkJoint( const VECTOR2I& aPos, const PNS_LAYER_RANGE& aLayers, NET_HANDLE aNet,
1473 ITEM* aWhere )
1474{
1475 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1476
1477 jt.Link( aWhere );
1478}
1479
1480
1481void NODE::unlinkJoint( const VECTOR2I& aPos, const PNS_LAYER_RANGE& aLayers, NET_HANDLE aNet,
1482 ITEM* aWhere )
1483{
1484 // fixme: remove dangling joints
1485 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1486
1487 jt.Unlink( aWhere );
1488}
1489
1490
1491void NODE::Dump( bool aLong )
1492{
1493#if 0
1494 std::unordered_set<SEGMENT*> all_segs;
1496
1497 for( i = m_items.begin(); i != m_items.end(); i++ )
1498 {
1499 if( (*i)->GetKind() == ITEM::SEGMENT_T )
1500 all_segs.insert( static_cast<SEGMENT*>( *i ) );
1501 }
1502
1503 if( !isRoot() )
1504 {
1505 for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1506 {
1507 if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1508 all_segs.insert( static_cast<SEGMENT*>(*i) );
1509 }
1510 }
1511
1512 JOINT_MAP::iterator j;
1513
1514 if( aLong )
1515 {
1516 for( j = m_joints.begin(); j != m_joints.end(); ++j )
1517 {
1518 wxLogTrace( wxT( "PNS" ), wxT( "joint : %s, links : %d\n" ),
1519 j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1520 JOINT::LINKED_ITEMS::const_iterator k;
1521
1522 for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1523 {
1524 const ITEM* m_item = *k;
1525
1526 switch( m_item->GetKind() )
1527 {
1528 case ITEM::SEGMENT_T:
1529 {
1530 const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1531 wxLogTrace( wxT( "PNS" ), wxT( " -> seg %s %s\n" ),
1532 seg->GetSeg().A.Format().c_str(),
1533 seg->GetSeg().B.Format().c_str() );
1534 break;
1535 }
1536
1537 default:
1538 break;
1539 }
1540 }
1541 }
1542 }
1543
1544 int lines_count = 0;
1545
1546 while( !all_segs.empty() )
1547 {
1548 SEGMENT* s = *all_segs.begin();
1549 LINE* l = AssembleLine( s );
1550
1551 LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1552
1553 if( aLong )
1554 {
1555 wxLogTrace( wxT( "PNS" ), wxT( "Line: %s, net %d " ),
1556 l->GetLine().Format().c_str(), l->GetNet() );
1557 }
1558
1559 for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1560 {
1561 wxLogTrace( wxT( "PNS" ), wxT( "%s " ), (*j)->GetSeg().A.Format().c_str() );
1562
1563 if( j + 1 == seg_refs->end() )
1564 wxLogTrace( wxT( "PNS" ), wxT( "%s\n" ), (*j)->GetSeg().B.Format().c_str() );
1565
1566 all_segs.erase( *j );
1567 }
1568
1569 lines_count++;
1570 }
1571
1572 wxLogTrace( wxT( "PNS" ), wxT( "Local joints: %d, lines : %d \n" ),
1573 m_joints.size(), lines_count );
1574#endif
1575}
1576
1577
1579{
1580 if( isRoot() )
1581 return;
1582
1583 if( m_override.size() )
1584 aRemoved.reserve( m_override.size() );
1585
1586 if( m_index->Size() )
1587 aAdded.reserve( m_index->Size() );
1588
1589 for( ITEM* item : m_override )
1590 aRemoved.push_back( item );
1591
1592 for( ITEM* item : *m_index )
1593 aAdded.push_back( item );
1594}
1595
1596
1598{
1599 // copy the kids as the NODE destructor erases the item from the parent node.
1600 std::set<NODE*> kids = m_children;
1601
1602 for( NODE* node : kids )
1603 {
1604 node->releaseChildren();
1605 delete node;
1606 }
1607}
1608
1609
1611{
1612 if( !isRoot() )
1613 return;
1614
1615 std::vector<const ITEM*> toDelete;
1616 toDelete.reserve( m_garbageItems.size() );
1617
1618 std::vector<const ITEM*> holes;
1619
1620 for( ITEM* item : m_garbageItems )
1621 {
1622 if( !item->BelongsTo( this ) )
1623 {
1624 toDelete.push_back( item );
1625
1626 if( item->HasHole() )
1627 holes.push_back( item->Hole() );
1628 }
1629 }
1630
1631 if( m_ruleResolver )
1632 {
1633 m_ruleResolver->ClearCacheForItems( toDelete );
1634 m_ruleResolver->ClearCacheForItems( holes );
1635 }
1636
1637 for( const ITEM* item : toDelete)
1638 {
1639 delete item;
1640 }
1641
1642 m_garbageItems.clear();
1643}
1644
1645
1646void NODE::Commit( NODE* aNode )
1647{
1648 if( aNode->isRoot() )
1649 return;
1650
1651 for( ITEM* item : aNode->m_override )
1652 Remove( item );
1653
1654 for( ITEM* item : *aNode->m_index )
1655 {
1656 if( item->HasHole() )
1657 {
1658 item->Hole()->SetOwner( item );
1659 }
1660
1661 item->SetRank( -1 );
1662 item->Unmark();
1663 add( item );
1664 }
1665
1668}
1669
1670
1672{
1674}
1675
1676
1677void NODE::AllItemsInNet( NET_HANDLE aNet, std::set<ITEM*>& aItems, int aKindMask )
1678{
1679 INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1680
1681 if( l_cur )
1682 {
1683 for( ITEM* item : *l_cur )
1684 {
1685 if( item->OfKind( aKindMask ) && item->IsRoutable() )
1686 aItems.insert( item );
1687 }
1688 }
1689
1690 if( !isRoot() )
1691 {
1692 INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1693
1694 if( l_root )
1695 {
1696 for( ITEM* item : *l_root )
1697 {
1698 if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1699 aItems.insert( item );
1700 }
1701 }
1702 }
1703}
1704
1705
1706void NODE::ClearRanks( int aMarkerMask )
1707{
1708 for( ITEM* item : *m_index )
1709 {
1710 item->SetRank( -1 );
1711 item->Mark( item->Marker() & ~aMarkerMask );
1712 }
1713}
1714
1715
1716void NODE::RemoveByMarker( int aMarker )
1717{
1718 std::vector<ITEM*> garbage;
1719
1720 for( ITEM* item : *m_index )
1721 {
1722 if( item->Marker() & aMarker )
1723 garbage.emplace_back( item );
1724 }
1725
1726 for( ITEM* item : garbage )
1727 Remove( item );
1728}
1729
1730
1732 NET_HANDLE aNet )
1733{
1734 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1735
1736 if( !jtStart )
1737 return nullptr;
1738
1739 for( ITEM* item : jtStart->LinkList() )
1740 {
1741 if( item->OfKind( ITEM::SEGMENT_T ) )
1742 {
1743 SEGMENT* seg2 = (SEGMENT*)item;
1744
1745 const VECTOR2I a2( seg2->Seg().A );
1746 const VECTOR2I b2( seg2->Seg().B );
1747
1748 if( seg2->Layers().Start() == lr.Start()
1749 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1750 {
1751 return seg2;
1752 }
1753 }
1754 }
1755
1756 return nullptr;
1757}
1758
1759
1761{
1762 return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1763}
1764
1765
1767 NET_HANDLE aNet )
1768{
1769 const JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1770
1771 if( !jtStart )
1772 return nullptr;
1773
1774 for( ITEM* item : jtStart->LinkList() )
1775 {
1776 if( item->OfKind( ITEM::ARC_T ) )
1777 {
1778 ARC* seg2 = static_cast<ARC*>( item );
1779
1780 const VECTOR2I a2( seg2->Anchor( 0 ) );
1781 const VECTOR2I b2( seg2->Anchor( 1 ) );
1782
1783 if( seg2->Layers().Start() == lr.Start()
1784 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1785 {
1786 return seg2;
1787 }
1788 }
1789 }
1790
1791 return nullptr;
1792}
1793
1794
1796{
1797 return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1798}
1799
1800
1801int NODE::QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints, PNS_LAYER_RANGE aLayerMask,
1802 int aKindMask )
1803{
1804 int n = 0;
1805
1806 aJoints.clear();
1807
1808 for( JOINT_MAP::value_type& j : m_joints )
1809 {
1810 if( !j.second.Layers().Overlaps( aLayerMask ) )
1811 continue;
1812
1813 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1814 {
1815 aJoints.push_back( &j.second );
1816 n++;
1817 }
1818 }
1819
1820 if( isRoot() )
1821 return n;
1822
1823 for( JOINT_MAP::value_type& j : m_root->m_joints )
1824 {
1825 if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1826 {
1827 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1828 {
1829 aJoints.push_back( &j.second );
1830 n++;
1831 }
1832 }
1833 }
1834
1835 return n;
1836}
1837
1838
1840{
1841 if( aParent && aParent->IsConnected() )
1842 {
1843 const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1844 INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( cItem->GetNet() );
1845
1846 if( l_cur )
1847 {
1848 for( ITEM* item : *l_cur )
1849 {
1850 if( item->Parent() == aParent )
1851 return item;
1852 }
1853 }
1854 }
1855
1856 return nullptr;
1857}
1858
1859
1860std::vector<ITEM*> NODE::FindItemsByParent( const BOARD_ITEM* aParent )
1861{
1862 std::vector<ITEM*> ret;
1863
1864 for( ITEM* item : *m_index )
1865 {
1866 if( item->Parent() == aParent )
1867 ret.push_back( item );
1868 }
1869
1870 return ret;
1871}
1872
1873
1874VIA* NODE::FindViaByHandle ( const VIA_HANDLE& handle ) const
1875{
1876 const JOINT* jt = FindJoint( handle.pos, handle.layers.Start(), handle.net );
1877
1878 if( !jt )
1879 return nullptr;
1880
1881 for( ITEM* item : jt->LinkList() )
1882 {
1883 if( item->OfKind( ITEM::VIA_T ) )
1884 {
1885 if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1886 return static_cast<VIA*>( item );
1887 }
1888 }
1889
1890 return nullptr;
1891}
1892
1893}
BOX2< VECTOR2I > BOX2I
Definition box2.h:917
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
NETINFO_ITEM * GetNet() const
Return NETINFO_ITEM 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:99
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition board_item.h:187
constexpr coord_type GetLeft() const
Definition box2.h:231
constexpr bool Contains(const Vec &aPoint) const
Definition box2.h:171
constexpr coord_type GetRight() const
Definition box2.h:220
constexpr coord_type GetTop() const
Definition box2.h:232
constexpr coord_type GetBottom() const
Definition box2.h:225
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:102
const SHAPE * Shape(int aLayer) const override
Return the geometrical shape of the item.
Definition pns_arc.h:80
ITEM * ParentPadVia() const override
Definition pns_hole.h:72
INDEX.
Definition pns_index.h:47
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:144
void Add(const LINE &aLine)
std::vector< ITEM * > & Items()
Definition pns_itemset.h:95
const std::vector< ITEM * > & CItems() const
Definition pns_itemset.h:96
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:341
virtual void Unmark(int aMarker=-1) const
Definition pns_item.h:266
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
Definition pns_item.h:246
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:327
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:269
virtual int Layer() const
Definition pns_item.h:216
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:308
bool OfKind(int aKindMask) const
Definition pns_item.h:181
bool IsVirtual() const
Definition pns_item.h:299
bool IsRoutable() const
Definition pns_item.h:288
virtual VECTOR2I Anchor(int n) const
Definition pns_item.h:272
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:308
virtual bool HasHole() const
Definition pns_item.h:307
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:307
NET_HANDLE Net() const override
Definition pns_joint.h:302
int LinkCount(int aMask=-1) const
Definition pns_joint.h:322
void Lock(bool aLock=true)
Definition pns_joint.h:356
void Link(ITEM *aItem)
Link the joint to a given board item (when it's added to the NODE).
Definition pns_joint.h:215
void Dump() const
LINKED_ITEM * NextSegment(LINKED_ITEM *aCurrent, bool aAllowLockedSegs=false) const
For trivial joints, return the segment adjacent to (aCurrent).
Definition pns_joint.h:240
HASH_TAG m_tag
hash tag for unordered_multimap
Definition pns_joint.h:368
bool IsLocked() const
Definition pns_joint.h:361
void Merge(const JOINT &aJoint)
Definition pns_joint.h:334
bool Unlink(ITEM *aItem)
Unlink a given board item from the joint (upon its removal from a NODE)
Definition pns_joint.h:228
const VECTOR2I & Pos() const
Definition pns_joint.h:297
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)
Clip the line to a given range of vertices.
const VECTOR2I & CPoint(int aIdx) const
Return the aIdx-th point of the line.
Definition pns_line.h:157
const SHAPE_LINE_CHAIN & CLine() const
Definition pns_line.h:149
const VECTOR2I & CLastPoint() const
Definition pns_line.h:158
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape.
Definition pns_line.h:148
VIA & Via()
Definition pns_line.h:212
int SegmentCount() const
Definition pns_line.h:151
void SetWidth(int aWidth)
Set line width.
Definition pns_line.h:162
bool EndsWithVia() const
Definition pns_line.h:204
int Width() const
Return line width.
Definition pns_line.h:169
virtual int Width() const
Keep the router "world" - i.e.
Definition pns_node.h:274
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition pns_node.cpp:174
void RemoveByMarker(int aMarker)
NODE * m_root
root node of the whole hierarchy
Definition pns_node.h:628
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find all lines between a pair of joints. Used by the loop removal procedure.
void BeginBulkAdd()
Defer spatial index insertion during bulk population.
std::vector< ITEM * > ITEM_VECTOR
Definition pns_node.h:285
void addSolid(SOLID *aSeg)
Helpers for adding/removing items.
Definition pns_node.cpp:619
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition pns_node.cpp:969
bool Overrides(ITEM *aItem) const
Check if this branch contains an updated version of the m_item from the root branch.
Definition pns_node.h:545
void removeSegmentIndex(SEGMENT *aSeg)
Definition pns_node.cpp:874
void rebuildJoint(const JOINT *aJoint, const ITEM *aItem)
Definition pns_node.cpp:888
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.
void addSegment(SEGMENT *aSeg)
Definition pns_node.cpp:754
std::vector< std::unique_ptr< SHAPE > > m_edgeExclusions
Definition pns_node.h:640
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const PNS_LAYER_RANGE &lr, NET_HANDLE aNet)
void releaseChildren()
JOINT_MAP::value_type TagJointPair
Definition pns_node.h:622
void addVia(VIA *aVia)
Definition pns_node.cpp:642
bool QueryEdgeExclusions(const VECTOR2I &aPos) const
Definition pns_node.cpp:815
void doRemove(ITEM *aItem)
Definition pns_node.cpp:827
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:510
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.
void addHole(HOLE *aHole)
Definition pns_node.cpp:660
std::optional< OBSTACLE > OPT_OBSTACLE
Definition pns_node.h:284
void unlinkJoint(const VECTOR2I &aPos, const PNS_LAYER_RANGE &aLayers, NET_HANDLE aNet, ITEM *aWhere)
Unlink an item from a joint.
std::unordered_set< ITEM * > m_garbageItems
Definition pns_node.h:642
void Dump(bool aLong=false)
Print the contents and joints structure.
void releaseGarbage()
void addArc(ARC *aVia)
Definition pns_node.cpp:783
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Find the joints corresponding to the ends of line aLine.
RULE_RESOLVER * GetRuleResolver() const
Definition pns_node.h:323
JOINT & touchJoint(const VECTOR2I &aPos, const PNS_LAYER_RANGE &aLayers, NET_HANDLE aNet)
Try to find matching joint and creates a new one if not found.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition pns_node.cpp:765
void FixupVirtualVias()
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, PNS_LAYER_RANGE aLayerMask=PNS_LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
std::set< OBSTACLE > OBSTACLES
Definition pns_node.h:286
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.
INDEX * m_index
Geometric/Net index of the items.
Definition pns_node.h:636
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition pns_node.h:631
void AllItemsInNet(NET_HANDLE aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
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:315
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
void removeArcIndex(ARC *aVia)
Definition pns_node.cpp:881
void AddEdgeExclusion(std::unique_ptr< SHAPE > aShape)
Definition pns_node.cpp:809
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:284
int m_maxClearance
worst case item-item clearance
Definition pns_node.h:634
bool isRoot() const
Definition pns_node.h:600
VIA * FindViaByHandle(const VIA_HANDLE &handle) const
void removeViaIndex(VIA *aVia)
Definition pns_node.cpp:949
void add(ITEM *aItem, bool aAllowRedundant=false)
Definition pns_node.cpp:676
void followLine(LINKED_ITEM *aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool *aArcReversed, bool &aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments, bool aAllowSegmentSizeMismatch)
Scan the joint map, forming a line starting from segment (current).
void KillChildren()
Destroy all child nodes. Applicable only to the root node.
void removeSolidIndex(SOLID *aSeg)
Definition pns_node.cpp:957
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition pns_node.h:637
std::set< NODE * > m_children
list of nodes branched from this one
Definition pns_node.h:629
ITEM * FindItemByParent(const BOARD_ITEM *aParent)
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition pns_node.h:624
std::vector< ITEM * > FindItemsByParent(const BOARD_ITEM *aParent)
NODE * m_parent
node this node was branched from
Definition pns_node.h:627
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
void Remove(ARC *aArc)
Remove an item from this branch.
void unlinkParent()
Definition pns_node.cpp:208
void Commit(NODE *aNode)
Apply the changes from a given branch (aNode) to the root branch.
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition pns_node.h:635
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const PNS_LAYER_RANGE &lr, NET_HANDLE aNet)
void linkJoint(const VECTOR2I &aPos, const PNS_LAYER_RANGE &aLayers, NET_HANDLE aNet, ITEM *aWhere)
Touch a joint and links it to an m_item.
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS()) const
Return the expected clearance between items a and b.
Definition pns_node.cpp:148
void FinalizeBulkAdd()
Build the spatial index from all items added since BeginBulkAdd().
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition pns_node.cpp:590
OBSTACLE_VISITOR(const ITEM *aItem)
Definition pns_node.cpp:217
const NODE * m_node
node we are searching in (either root or a branch)
Definition pns_node.h:240
const ITEM * m_item
the item we are looking for collisions with
Definition pns_node.h:238
bool visit(ITEM *aCandidate)
Definition pns_node.cpp:232
std::optional< int > m_layerContext
Definition pns_node.h:242
void SetWorld(const NODE *aNode, const NODE *aOverride=nullptr)
Definition pns_node.cpp:225
const NODE * m_override
node that overrides root entries
Definition pns_node.h:241
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
ROUTING_SETTINGS & Settings()
Definition pns_router.h:240
static ROUTER * GetInstance()
DIRECTION_45::CORNER_MODE GetCornerMode() const
virtual const SHAPE_LINE_CHAIN & HullCache(const ITEM *aItem, int aClearance, int aWalkaroundThickness, int aLayer)
Definition pns_node.h:208
virtual const std::string Format() const override
const SEG & Seg() const
virtual bool HasHole() const override
Definition pns_solid.h:153
virtual HOLE * Hole() const override
Definition pns_solid.h:154
const VECTOR2I & Pos() const
Definition pns_solid.h:119
const VECTOR2I & Pos() const
Definition pns_via.h:206
virtual HOLE * Hole() const override
Definition pns_via.h:340
virtual bool HasHole() const override
Definition pns_via.h:339
Represent a contiguous set of PCB layers.
int Start() const
bool Overlaps(const PNS_LAYER_RANGE &aOther) const
bool IsMultilayer() const
Definition seg.h:38
VECTOR2I A
Definition seg.h:45
VECTOR2I B
Definition seg.h:46
SHAPE_ARC Reversed() const
const VECTOR2I & GetP1() const
Definition shape_arc.h:115
const VECTOR2I & GetP0() const
Definition shape_arc.h:114
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
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this 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...
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.
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
Push and Shove diff pair dimensions (gap) settings dialog.
std::unique_ptr< T > ItemCast(std::unique_ptr< S > aPtr)
Definition pns_item.h:340
void * NET_HANDLE
Definition pns_item.h:55
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, std::vector< SHAPE_LINE_CHAIN::INTERSECTION > &ips)
#define PNS_HULL_MARGIN
Definition pns_line.h:45
CITER next(CITER it)
Definition ptree.cpp:120
static std::vector< std::string > split(const std::string &aStr, const std::string &aDelim)
Split the input string into a vector of output strings.
std::set< OBSTACLE > & obstacles
Definition pns_node.h:166
CLEARANCE_OVERRIDE_FUNC m_overrideClearance
Definition pns_node.h:140
bool m_overrideExemptPairs
Apply m_overrideClearance even to pairs the resolver exempts, such as same-net items.
Definition pns_node.h:143
bool operator()(ITEM *aItem) override
Definition pns_node.cpp:575
const VECTOR2I & m_point
Definition pns_node.cpp:563
HIT_VISITOR(ITEM_SET &aTab, const VECTOR2I &aPoint)
Definition pns_node.cpp:565
virtual ~HIT_VISITOR()
Definition pns_node.cpp:571
ITEM_SET & m_items
Definition pns_node.cpp:562
Joints are hashed by their position, layers and net.
Definition pns_joint.h:48
bool operator()(ITEM *aCandidate) override
Definition pns_node.cpp:258
COLLISION_SEARCH_CONTEXT * m_ctx
Definition pns_node.cpp:246
DEFAULT_OBSTACLE_VISITOR(COLLISION_SEARCH_CONTEXT *aCtx, const ITEM *aItem)
Definition pns_node.cpp:248
Hold an object colliding with another object, along with some useful data about the collision.
Definition pns_node.h:98
int m_distFirst
... and the distance thereof
Definition pns_node.h:104
int m_maxFanoutWidth
worst case (largest) width of the tracks connected to the item
Definition pns_node.h:105
ITEM * m_head
Line we search collisions against.
Definition pns_node.h:99
VECTOR2I m_ipFirst
First intersection between m_head and m_hull.
Definition pns_node.h:101
ITEM * m_item
Item found to be colliding with m_head.
Definition pns_node.h:100
VECTOR2I pos
Definition pns_via.h:55
NET_HANDLE net
Definition pns_via.h:57
PNS_LAYER_RANGE layers
Definition pns_via.h:56
Represent an intersection between two line segments.
VECTOR2I end
int clearance
wxString result
Test unit parsing edge cases and error handling.
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
static thread_pool * tp
BS::priority_thread_pool thread_pool
Definition thread_pool.h:27
Casted dyn_cast(From aObject)
A lightweight dynamic downcast.
Definition typeinfo.h:55
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708