KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_topology.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2015 CERN
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22#include <wx/log.h>
23
24#include <chrono>
25#include <stack>
26
27#include <advanced_config.h>
28
29#include "pns_line.h"
30#include "pns_segment.h"
31#include "pns_arc.h"
32#include "pns_node.h"
33#include "pns_joint.h"
34#include "pns_solid.h"
35#include "pns_router.h"
36#include "pns_utils.h"
37
38#include "pns_diff_pair.h"
39#include "pns_topology.h"
40
41#include "pcb_track.h"
42
43#include <board.h>
45#include <pad.h>
46
47namespace PNS {
48
50{
51 if( !aLine->IsLinked() || !aLine->SegmentCount() )
52 return false;
53
54 LINKED_ITEM* root = aLine->GetLink( 0 );
55 LINE l = m_world->AssembleLine( root, nullptr, false, false, false );
56 SHAPE_LINE_CHAIN simplified( l.CLine() );
57
58 simplified.Simplify();
59
60 if( simplified.PointCount() != l.PointCount() )
61 {
62 m_world->Remove( l );
63 LINE lnew( l );
64 lnew.SetShape( simplified );
65 m_world->Add( lnew );
66 return true;
67 }
68
69 return false;
70}
71
72
74{
75 std::deque<const JOINT*> searchQueue;
76 JOINT_SET processed;
77
78 searchQueue.push_back( aStart );
79 processed.insert( aStart );
80
81 while( !searchQueue.empty() )
82 {
83 const JOINT* current = searchQueue.front();
84 searchQueue.pop_front();
85
86 for( ITEM* item : current->LinkList() )
87 {
88 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
89 {
90 const JOINT* a = m_world->FindJoint( item->Anchor( 0 ), item );;
91 const JOINT* b = m_world->FindJoint( item->Anchor( 1 ), item );;
92 const JOINT* next = ( *a == *current ) ? b : a;
93
94 if( processed.find( next ) == processed.end() )
95 {
96 processed.insert( next );
97 searchQueue.push_back( next );
98 }
99 }
100 }
101 }
102
103 return processed;
104}
105
106
108 PNS_LAYER_RANGE& aLayers, ITEM*& aItem )
109{
110 LINE track( *aTrack );
112
113 if( !track.PointCount() )
114 return false;
115
116 std::unique_ptr<NODE> tmpNode( m_world->Branch() );
117
118 track.ClearLinks();
119 tmpNode->Add( track );
120
121 const JOINT* jt = tmpNode->FindJoint( track.CLastPoint(), &track );
122
123 if( !jt || m_world->GetRuleResolver()->NetCode( jt->Net() ) <= 0 )
124 return false;
125
126 ITEM* connected = nullptr;
127
128 if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 )
129 || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
130 {
131 // tmpNode's own track is freed on return, skip it to avoid a dangling anchor item
132 for( ITEM* link : jt->LinkList() )
133 {
134 if( !link->BelongsTo( tmpNode.get() ) )
135 {
136 connected = link;
137 break;
138 }
139 }
140 }
141
142 if( connected )
143 {
144 end = jt->Pos();
145 aLayers = jt->Layers();
146 aItem = connected;
147 }
148 else
149 {
150 int anchor;
151
152 TOPOLOGY topo( tmpNode.get(), m_iface );
153 ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
154
155 if( !it )
156 return false;
157
158 end = it->Anchor( anchor );
159 aLayers = it->Layers();
160 aItem = it;
161 }
162
163 aPoint = end;
164 return true;
165}
166
167
168bool TOPOLOGY::LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine )
169{
171 // Ratline doesn't care about the layer
172 PNS_LAYER_RANGE layers;
173 ITEM* unusedItem;
174
175 if( !NearestUnconnectedAnchorPoint( aTrack, end, layers, unusedItem ) )
176 return false;
177
178 aRatLine.Clear();
179 aRatLine.Append( aTrack->CLastPoint() );
180 aRatLine.Append( end );
181 return true;
182}
183
184
185ITEM* TOPOLOGY::NearestUnconnectedItem( const JOINT* aStart, int* aAnchor, int aKindMask )
186{
187 std::set<ITEM*> disconnected;
188 std::vector<const ITEM*> joined;
189
190 m_world->AllItemsInNet( aStart->Net(), disconnected );
191
192 for( const JOINT* jt : ConnectedJoints( aStart ) )
193 {
194 for( ITEM* link : jt->LinkList() )
195 {
196 if( disconnected.find( link ) != disconnected.end() )
197 disconnected.erase( link );
198
199 joined.push_back( link );
200 }
201 }
202
203 // The router does not model zones, so the board decides what they already join us to
204 if( m_iface )
205 m_iface->RemoveBoardConnected( joined, disconnected );
206
207 int best_dist = INT_MAX;
208 ITEM* best = nullptr;
209
210 for( ITEM* item : disconnected )
211 {
212 if( item->OfKind( aKindMask ) )
213 {
214 for( int i = 0; i < item->AnchorCount(); i++ )
215 {
216 VECTOR2I p = item->Anchor( i );
217 int d = ( p - aStart->Pos() ).EuclideanNorm();
218
219 if( d < best_dist )
220 {
221 best_dist = d;
222 best = item;
223
224 if( aAnchor )
225 *aAnchor = i;
226 }
227 }
228 }
229 }
230
231 return best;
232}
233
234
236 std::set<ITEM*>& aVisited,
237 bool aFollowLockedSegments )
238{
239 using clock = std::chrono::steady_clock;
240
241 PATH_RESULT best;
242 best.m_end = aStartJoint;
243
244 const int timeoutMs = ADVANCED_CFG::GetCfg().m_FollowBranchTimeout;
245 auto startTime = clock::now();
246
247 // State for iterative DFS: current joint, previous item, accumulated path items,
248 // accumulated length, and the set of visited joints for this path
249 struct STATE
250 {
251 const JOINT* joint;
252 LINKED_ITEM* prev;
253 ITEM_SET pathItems;
254 int pathLength;
255 std::set<const JOINT*> visitedJoints;
256 ITEM* via;
257 };
258
259 std::stack<STATE> stateStack;
260
261 // Initialize with starting state
262 STATE initial;
263 initial.joint = aStartJoint;
264 initial.prev = aPrev;
265 initial.pathLength = 0;
266 initial.visitedJoints.insert( aStartJoint );
267 initial.via = nullptr;
268
269 stateStack.push( std::move( initial ) );
270
271 while( !stateStack.empty() )
272 {
273 // Check timeout
274 auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(
275 clock::now() - startTime ).count();
276
277 if( elapsed > timeoutMs )
278 {
279 wxLogTrace( wxT( "PNS_TUNE" ),
280 wxT( "followBranch: timeout after %lld ms, returning best path found" ),
281 elapsed );
282 break;
283 }
284
285 STATE current = std::move( stateStack.top() );
286 stateStack.pop();
287
288 const JOINT* joint = current.joint;
289 ITEM_SET links( joint->CLinks() );
290
291 // Check for via at this joint
292 ITEM* via = nullptr;
293
294 for( ITEM* link : links )
295 {
296 if( link->OfKind( ITEM::VIA_T ) && !aVisited.contains( link ) )
297 {
298 via = link;
299 break;
300 }
301 }
302
303 // Find all unvisited branches from this joint
304 bool foundBranch = false;
305
306 for( ITEM* link : links )
307 {
308 if( !link->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
309 continue;
310
311 if( link == current.prev )
312 continue;
313
314 if( aVisited.contains( link ) )
315 continue;
316
317 LINE l = m_world->AssembleLine( static_cast<LINKED_ITEM*>( link ), nullptr,
318 false, aFollowLockedSegments );
319
320 if( l.CPoint( 0 ) != joint->Pos() )
321 l.Reverse();
322
323 const JOINT* nextJoint = m_world->FindJoint( l.CLastPoint(), &l );
324
325 // Skip if we've already visited this joint in the current path
326 if( current.visitedJoints.count( nextJoint ) )
327 continue;
328
329 foundBranch = true;
330
331 // Build new state for this branch
332 STATE nextState;
333 nextState.joint = nextJoint;
334 nextState.prev = l.Links().back();
335 nextState.pathItems = current.pathItems;
336 nextState.pathLength = current.pathLength + l.CLine().Length();
337 nextState.visitedJoints = current.visitedJoints;
338 nextState.visitedJoints.insert( nextJoint );
339 nextState.via = via;
340
341 // Add via and line to path
342 if( via )
343 nextState.pathItems.Add( via );
344
345 nextState.pathItems.Add( l );
346
347 stateStack.push( std::move( nextState ) );
348 }
349
350 // If no branches found, this is a terminal joint - check if it's the best path
351 if( !foundBranch )
352 {
353 if( current.pathLength > best.m_length )
354 {
355 best.m_length = current.pathLength;
356 best.m_end = joint;
357 best.m_items = current.pathItems;
358 }
359 }
360 }
361
362 wxLogTrace( wxT( "PNS_TUNE" ),
363 wxT( "followBranch: completed with best path length=%d, %d items" ),
364 best.m_length, best.m_items.Size() );
365
366 return best;
367}
368
369
370ITEM_SET TOPOLOGY::followTrivialPath( LINE* aLine2, const JOINT** aTerminalJointA,
371 const JOINT** aTerminalJointB,
372 bool aFollowLockedSegments )
373{
374 assert( aLine2->IsLinked() );
375
376 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "=== followTrivialPath START ===" ) );
377 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "followTrivialPath: initial line has %d segments, %zu links" ),
378 aLine2->SegmentCount(), aLine2->Links().size() );
379 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "followTrivialPath: line endpoints: (%d,%d) to (%d,%d)" ),
380 aLine2->CPoint( 0 ).x, aLine2->CPoint( 0 ).y,
381 aLine2->CLastPoint().x, aLine2->CLastPoint().y );
382
384 path.Add( *aLine2 );
385
386 std::set<ITEM*> visited;
387
388 for( LINKED_ITEM* link : aLine2->Links() )
389 visited.insert( link );
390
391 const JOINT* jtA = m_world->FindJoint( aLine2->CPoint( 0 ), aLine2 );
392 const JOINT* jtB = m_world->FindJoint( aLine2->CLastPoint(), aLine2 );
393
394 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "followTrivialPath: LEFT branch starting from joint at (%d,%d)" ),
395 jtA->Pos().x, jtA->Pos().y );
396 PATH_RESULT left = followBranch( jtA, aLine2->Links().front(), visited, aFollowLockedSegments );
397 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "followTrivialPath: LEFT branch result: length=%d, %d items" ),
398 left.m_length, left.m_items.Size() );
399
400 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "followTrivialPath: RIGHT branch starting from joint at (%d,%d)" ),
401 jtB->Pos().x, jtB->Pos().y );
402 PATH_RESULT right = followBranch( jtB, aLine2->Links().back(), visited, aFollowLockedSegments );
403 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "followTrivialPath: RIGHT branch result: length=%d, %d items" ),
404 right.m_length, right.m_items.Size() );
405
406 if( aTerminalJointA )
407 *aTerminalJointA = left.m_end;
408
409 if( aTerminalJointB )
410 *aTerminalJointB = right.m_end;
411
412 // Count segments as we build the final path
413 int leftSegCount = 0;
414 int rightSegCount = 0;
415 int initialSegCount = 0;
416
417 // Count initial segments
418 for( int i = 0; i < aLine2->SegmentCount(); i++ )
419 initialSegCount++;
420
421 // Add left items
422 for( ITEM* item : left.m_items )
423 {
424 path.Prepend( item );
425 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
426 {
427 LINE* l = dynamic_cast<LINE*>( item );
428 if( l )
429 leftSegCount += l->SegmentCount();
430 else
431 leftSegCount++;
432 }
433 }
434
435 // Add right items
436 for( ITEM* item : right.m_items )
437 {
438 path.Add( item );
439 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
440 {
441 LINE* l = dynamic_cast<LINE*>( item );
442 if( l )
443 rightSegCount += l->SegmentCount();
444 else
445 rightSegCount++;
446 }
447 }
448
449 // Calculate total path length
450 int totalLength = left.m_length + aLine2->CLine().Length() + right.m_length;
451
452 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "" ) );
453 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "=== followTrivialPath SUMMARY ===" ) );
454 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "Starting segment count: %d" ), initialSegCount );
455 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "Left branch: %d segments, length=%d" ), leftSegCount, left.m_length );
456 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "Initial line: %d segments, length=%lld" ), initialSegCount, aLine2->CLine().Length() );
457 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "Right branch: %d segments, length=%d" ), rightSegCount, right.m_length );
458 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "Total segments in path: %d" ), leftSegCount + initialSegCount + rightSegCount );
459 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "Total path length: %d" ), totalLength );
460 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "Total items in result: %d" ), path.Size() );
461 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "=== followTrivialPath END ===" ) );
462 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "" ) );
463
464 return path;
465}
466
467
469 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
470 bool aFollowLockedSegments )
471{
472 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "*** AssembleTrivialPath: START ***" ) );
473 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: aStart=%p, kind=%s" ),
474 aStart, aStart->KindStr().c_str() );
475
477 LINKED_ITEM* seg = nullptr;
478
479 if( aStart->Kind() == ITEM::VIA_T )
480 {
481 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: starting from VIA" ) );
482 VIA* via = static_cast<VIA*>( aStart );
483 const JOINT* jt = m_world->FindJoint( via->Pos(), via );
484
485 if( !jt->IsNonFanoutVia() )
486 {
487 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: VIA is fanout, returning empty" ) );
488 return ITEM_SET();
489 }
490
491 ITEM_SET links( jt->CLinks() );
492
493 for( ITEM* item : links )
494 {
495 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
496 {
497 seg = static_cast<LINKED_ITEM*>( item );
498 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: found segment/arc from VIA" ) );
499 break;
500 }
501 }
502 }
503 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
504 {
505 seg = static_cast<LINKED_ITEM*>( aStart );
506 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: starting from SEGMENT/ARC" ) );
507 }
508
509 if( !seg )
510 {
511 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: no segment found, returning empty" ) );
512 return ITEM_SET();
513 }
514
515 // Assemble a line following through locked segments
516 // TODO: consider if we want to allow tuning lines with different widths in the future
517 LINE l = m_world->AssembleLine( seg, nullptr, false, aFollowLockedSegments );
518
519 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: assembled line with %d segments, length=%lld" ),
520 l.SegmentCount(), l.CLine().Length() );
521
522 const JOINT* jointA = nullptr;
523 const JOINT* jointB = nullptr;
524
525 path = followTrivialPath( &l, &jointA, &jointB, aFollowLockedSegments );
526
527 if( aTerminalJoints )
528 {
529 wxASSERT( jointA && jointB );
530 *aTerminalJoints = std::make_pair( jointA, jointB );
531 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: terminal joints at (%d,%d) and (%d,%d)" ),
532 jointA->Pos().x, jointA->Pos().y, jointB->Pos().x, jointB->Pos().y );
533 }
534
535 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTrivialPath: returning path with %d items" ), path.Size() );
536 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "*** AssembleTrivialPath: END ***" ) );
537 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "" ) );
538
539 return path;
540}
541
542
543std::vector<LINE> TOPOLOGY::findLinesFromVia( ROUTER_IFACE* aRouterIface, VIA* aVia, const std::set<ITEM*>& aVisited )
544{
545 std::vector<LINE> result;
546 NODE::OBSTACLES obstacles;
548
549 opts.m_differentNetsOnly = false;
551 opts.m_overrideExemptPairs = true;
553
554 m_world->QueryColliding( aVia, obstacles, opts );
555
556 NET_HANDLE net = aVia->Net();
557 std::set<LINKED_ITEM*> assembled;
558
559 const PCB_VIA* pcbVia = ( aVia->Parent() && aVia->Parent()->Type() == PCB_VIA_T )
560 ? static_cast<const PCB_VIA*>( aVia->Parent() )
561 : nullptr;
562
563
564 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "findLinesFromVia: VIA at (%d,%d), net=%p, %zu obstacles" ), aVia->Pos().x,
565 aVia->Pos().y, net, obstacles.size() );
566
567 for( const OBSTACLE& obs : obstacles )
568 {
569 if( obs.m_item->Net() != net )
570 continue;
571
572 LINKED_ITEM* linked = static_cast<LINKED_ITEM*>( obs.m_item );
573
574 if( aVisited.contains( linked ) )
575 continue;
576
577 if( assembled.contains( linked ) )
578 continue;
579
580 // Make sure at least one anchor is inside the via pad
581 VECTOR2I anchor0 = linked->Anchor( 0 );
582 VECTOR2I anchor1 = linked->Anchor( 1 );
583
584 bool anchor0Inside, anchor1Inside;
585
586 if( pcbVia )
587 {
588 PCB_LAYER_ID pcbLayer = aRouterIface->GetBoardLayerFromPNSLayer( linked->Layer() );
589 anchor0Inside = LENGTH_DELAY_CALCULATION::IsPointInsideViaPad( pcbVia, anchor0, pcbLayer );
590 anchor1Inside = LENGTH_DELAY_CALCULATION::IsPointInsideViaPad( pcbVia, anchor1, pcbLayer );
591 }
592 else
593 {
594 // Fallback to PNS shape collision
595 const SHAPE* shape = aVia->Shape( aVia->Layer() );
596 anchor0Inside = shape && shape->Collide( anchor0, 0 );
597 anchor1Inside = shape && shape->Collide( anchor1, 0 );
598 }
599
600 if( !anchor0Inside && !anchor1Inside )
601 {
602 wxLogTrace( wxT( "PNS_TUNE" ), wxT( " skip collision: layer=%d anchor0=(%d,%d) anchor1=(%d,%d)" ),
603 linked->Layer(), anchor0.x, anchor0.y, anchor1.x, anchor1.y );
604 continue;
605 }
606
607 LINE l = m_world->AssembleLine( linked, nullptr, false, true );
608
609 for( LINKED_ITEM* link : l.Links() )
610 assembled.insert( link );
611
612 result.push_back( l );
613 }
614
615 return result;
616}
617
618
619TOPOLOGY::WALK_RESULT TOPOLOGY::walkTuningPath( ROUTER_IFACE* aRouterIface, LINE& aStartLine, bool aStartFromBack,
620 const std::set<ITEM*>& aVisited )
621{
622 using clock = std::chrono::steady_clock;
623
624 WALK_RESULT best;
625
626 NET_HANDLE net = aStartLine.Net();
627 const int timeoutMs = ADVANCED_CFG::GetCfg().m_FollowBranchTimeout;
628 auto startTime = clock::now();
629
630 struct STATE
631 {
632 VECTOR2I endpoint;
633 ITEM_SET pathItems;
634 int64_t pathLength;
635 std::set<ITEM*> visited;
636 };
637
638 std::stack<STATE> stateStack;
639
640 STATE initial;
641 initial.endpoint = aStartFromBack ? aStartLine.CLastPoint() : aStartLine.CPoint( 0 );
642 initial.pathLength = 0;
643 initial.visited = aVisited;
644 stateStack.push( std::move( initial ) );
645
646 while( !stateStack.empty() )
647 {
648 auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>( clock::now() - startTime ).count();
649
650 if( elapsed > timeoutMs )
651 {
652 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "walkTuningPath: timeout after %lld ms" ), elapsed );
653 break;
654 }
655
656 STATE current = std::move( stateStack.top() );
657 stateStack.pop();
658
659 ITEM_SET hits = m_world->HitTest( current.endpoint );
660
661 SOLID* pad = nullptr;
662
663 for( ITEM* item : hits )
664 {
665 if( item->OfKind( ITEM::SOLID_T ) && item->Net() == net && !current.visited.contains( item ) )
666 {
667 pad = static_cast<SOLID*>( item );
668 break;
669 }
670 }
671
672 if( pad )
673 {
674 if( current.pathLength > best.m_length )
675 {
676 best.m_length = current.pathLength;
677 best.m_items = current.pathItems;
678 best.m_endPad = pad;
679 }
680
681 // Continue through an in-line pad so tuning spans the whole net.
682 current.visited.insert( pad );
683
684 for( ITEM* item : hits )
685 {
686 if( !item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
687 continue;
688
689 if( item->Net() != net || current.visited.contains( item ) )
690 continue;
691
692 LINE contLine = m_world->AssembleLine( static_cast<LINKED_ITEM*>( item ), nullptr, false, true );
693
694 VECTOR2I ep = current.endpoint;
695 bool startNear = ( contLine.CPoint( 0 ) - ep ).SquaredEuclideanNorm()
696 <= ( contLine.CLastPoint() - ep ).SquaredEuclideanNorm();
697
698 STATE nextState;
699 nextState.endpoint = startNear ? contLine.CLastPoint() : contLine.CPoint( 0 );
700 nextState.pathItems = current.pathItems;
701 nextState.pathItems.Add( contLine );
702 nextState.pathLength = current.pathLength + contLine.CLine().Length();
703 nextState.visited = current.visited;
704
705 for( LINKED_ITEM* link : contLine.Links() )
706 nextState.visited.insert( link );
707
708 stateStack.push( std::move( nextState ) );
709 }
710
711 continue;
712 }
713
714 VIA* via = nullptr;
715
716 for( ITEM* item : hits )
717 {
718 if( item->OfKind( ITEM::VIA_T ) && item->Net() == net && !item->IsVirtual()
719 && !current.visited.contains( item ) )
720 {
721 via = static_cast<VIA*>( item );
722 break;
723 }
724 }
725
726 if( via )
727 {
728 current.visited.insert( via );
729
730 std::vector<LINE> continuations = findLinesFromVia( aRouterIface, via, current.visited );
731
732 for( LINE& contLine : continuations )
733 {
734 VECTOR2I ep = current.endpoint;
735 bool startNearVia = ( contLine.CPoint( 0 ) - ep ).SquaredEuclideanNorm()
736 <= ( contLine.CLastPoint() - ep ).SquaredEuclideanNorm();
737
738 VECTOR2I forwardEndpoint = startNearVia ? contLine.CLastPoint() : contLine.CPoint( 0 );
739
740 int64_t contLength = contLine.CLine().Length();
741
742 if( const BOARD_ITEM* parent = via->Parent(); parent && parent->Type() == PCB_VIA_T )
743 {
744 const PCB_VIA* pcbVia = static_cast<const PCB_VIA*>( parent );
745 SHAPE_LINE_CHAIN clipped = contLine.Line();
746 const PCB_LAYER_ID pcbLayer = aRouterIface->GetBoardLayerFromPNSLayer( contLine.Layer() );
747
748 LENGTH_DELAY_CALCULATION::OptimiseTraceInVia( clipped, pcbVia, pcbLayer );
749 contLength = clipped.Length();
750 }
751
752 STATE nextState;
753 nextState.endpoint = forwardEndpoint;
754 nextState.pathItems = current.pathItems;
755 nextState.pathItems.Add( via );
756 nextState.pathItems.Add( contLine );
757 nextState.pathLength = current.pathLength + contLength;
758 nextState.visited = current.visited;
759
760 for( LINKED_ITEM* link : contLine.Links() )
761 nextState.visited.insert( link );
762
763 stateStack.push( std::move( nextState ) );
764 }
765
766 if( continuations.empty() )
767 {
768 if( current.pathLength > best.m_length )
769 {
770 best.m_length = current.pathLength;
771 best.m_items = current.pathItems;
772 best.m_items.Add( via );
773 best.m_endPad = nullptr;
774 }
775 }
776 }
777 else
778 {
779 if( current.pathLength > best.m_length )
780 {
781 best.m_length = current.pathLength;
782 best.m_items = current.pathItems;
783 best.m_endPad = nullptr;
784 }
785 }
786 }
787
788 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "walkTuningPath: completed, best length=%lld, %d items, pad=%p" ),
789 best.m_length, best.m_items.Size(), best.m_endPad );
790
791 return best;
792}
793
794
795const ITEM_SET TOPOLOGY::AssembleTuningPath( ROUTER_IFACE* aRouterIface, ITEM* aStart, SOLID** aStartPad,
796 SOLID** aEndPad )
797{
798 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "" ) );
799 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "########## AssembleTuningPath: START ##########" ) );
800 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: aStart=%p, kind=%s" ),
801 aStart, aStart->KindStr().c_str() );
802
803 LINKED_ITEM* seg = nullptr;
804
805 if( aStart->Kind() == ITEM::VIA_T )
806 {
807 VIA* via = static_cast<VIA*>( aStart );
808
809 const JOINT* jt = m_world->FindJoint( via->Pos(), via );
810
811 if( jt && jt->IsNonFanoutVia() )
812 {
813 ITEM_SET links( jt->CLinks() );
814
815 for( ITEM* item : links )
816 {
817 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
818 {
819 seg = static_cast<LINKED_ITEM*>( item );
820 break;
821 }
822 }
823 }
824
825 if( !seg )
826 {
827 std::vector<LINE> continuations = findLinesFromVia( aRouterIface, via, {} );
828
829 if( continuations.empty() )
830 {
831 wxLogTrace( wxT( "PNS_TUNE" ),
832 wxT( "AssembleTuningPath: no via continuation found, returning empty" ) );
833 return ITEM_SET();
834 }
835
836 for( LINKED_ITEM* link : continuations.front().Links() )
837 {
838 if( link->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
839 {
840 seg = link;
841 break;
842 }
843 }
844 }
845 }
846 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
847 {
848 seg = static_cast<LINKED_ITEM*>( aStart );
849 }
850
851 if( !seg )
852 {
853 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: no segment found, returning empty" ) );
854 return ITEM_SET();
855 }
856
857 LINE l = m_world->AssembleLine( seg, nullptr, false, true );
858
859 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: initial line %d segments, length=%lld" ), l.SegmentCount(),
860 l.CLine().Length() );
861
862 std::set<ITEM*> visited;
863
864 for( LINKED_ITEM* link : l.Links() )
865 visited.insert( link );
866
867 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: walking LEFT from (%d,%d)" ), l.CPoint( 0 ).x,
868 l.CPoint( 0 ).y );
869 WALK_RESULT left = walkTuningPath( aRouterIface, l, false, visited );
870
871 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: walking RIGHT from (%d,%d)" ), l.CLastPoint().x,
872 l.CLastPoint().y );
873 WALK_RESULT right = walkTuningPath( aRouterIface, l, true, visited );
874
876
877 for( ITEM* item : left.m_items )
878 path.Prepend( item );
879
880 path.Add( l );
881
882 for( ITEM* item : right.m_items )
883 path.Add( item );
884
885 PAD* padA = nullptr;
886 PAD* padB = nullptr;
887
888 if( left.m_endPad )
889 {
890 BOARD_ITEM* bi = left.m_endPad->Parent();
891
892 if( bi && bi->Type() == PCB_PAD_T )
893 {
894 padA = static_cast<PAD*>( bi );
895
896 if( aStartPad )
897 *aStartPad = left.m_endPad;
898
899 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: found start pad" ) );
900 }
901 }
902
903 if( right.m_endPad )
904 {
905 BOARD_ITEM* bi = right.m_endPad->Parent();
906
907 if( bi && bi->Type() == PCB_PAD_T )
908 {
909 padB = static_cast<PAD*>( bi );
910
911 if( aEndPad )
912 *aEndPad = right.m_endPad;
913
914 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: found end pad" ) );
915 }
916 }
917
918 if( !padA && !padB )
919 {
920 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: no pads found, returning path" ) );
921 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "########## AssembleTuningPath: END ##########" ) );
922 return path;
923 }
924
925 auto processPad = [&]( PAD* aPad )
926 {
927 for( int idx = 0; idx < path.Size(); idx++ )
928 {
929 if( path[idx]->Kind() != ITEM::LINE_T )
930 continue;
931
932 LINE* line = static_cast<LINE*>( path[idx] );
933 SHAPE_LINE_CHAIN& slc = line->Line();
934 const PCB_LAYER_ID pcbLayer = aRouterIface->GetBoardLayerFromPNSLayer( line->Layer() );
935
937 }
938 };
939
940 if( padA )
941 processPad( padA );
942
943 if( padB )
944 processPad( padB );
945
946 std::set<PAD*> processedPads;
947
948 if( padA )
949 processedPads.insert( padA );
950
951 if( padB )
952 processedPads.insert( padB );
953
954 for( int idx = 0; idx < path.Size(); idx++ )
955 {
956 if( path[idx]->Kind() != ITEM::LINE_T )
957 continue;
958
959 LINE* line = static_cast<LINE*>( path[idx] );
960
961 for( const VECTOR2I& pt : { line->CPoint( 0 ), line->CLastPoint() } )
962 {
963 ITEM_SET hits = m_world->HitTest( pt );
964
965 for( ITEM* item : hits )
966 {
967 if( item->OfKind( ITEM::SOLID_T ) && item->Net() == line->Net() )
968 {
969 SOLID* solid = static_cast<SOLID*>( item );
970 BOARD_ITEM* bi = solid->Parent();
971
972 if( bi && bi->Type() == PCB_PAD_T )
973 {
974 PAD* intermediatePad = static_cast<PAD*>( bi );
975
976 if( processedPads.find( intermediatePad ) == processedPads.end() )
977 {
978 wxLogTrace( wxT( "PNS_TUNE" ),
979 wxT( "AssembleTuningPath: processing intermediate"
980 " pad at (%d,%d)" ),
981 pt.x, pt.y );
982 processPad( intermediatePad );
983 processedPads.insert( intermediatePad );
984 }
985 }
986
987 break;
988 }
989 }
990 }
991 }
992
993 // Clip in-VIA portions and add residual path to VIA centre.
994 for( int idx = 0; idx < path.Size(); idx++ )
995 {
996 if( path[idx]->Kind() != ITEM::VIA_T )
997 continue;
998
999 VIA* pnsVia = static_cast<VIA*>( path[idx] );
1000 BOARD_ITEM* parent = pnsVia->Parent();
1001
1002 if( !parent || parent->Type() != PCB_VIA_T )
1003 continue;
1004
1005 const PCB_VIA* pcbVia = static_cast<const PCB_VIA*>( parent );
1006
1007 for( int delta : { -1, 1 } )
1008 {
1009 int j = idx + delta;
1010
1011 if( j < 0 || j >= path.Size() || path[j]->Kind() != ITEM::LINE_T )
1012 continue;
1013
1014 LINE* line = static_cast<LINE*>( path[j] );
1015 SHAPE_LINE_CHAIN& slc = line->Line();
1016 const PCB_LAYER_ID pcbLayer = aRouterIface->GetBoardLayerFromPNSLayer( line->Layer() );
1017
1018 LENGTH_DELAY_CALCULATION::OptimiseTraceInVia( slc, pcbVia, pcbLayer );
1019 }
1020 }
1021
1022 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "AssembleTuningPath: final path has %d items" ), path.Size() );
1023 wxLogTrace( wxT( "PNS_TUNE" ), wxT( "########## AssembleTuningPath: END ##########" ) );
1024
1025 return path;
1026}
1027
1028
1029const ITEM_SET TOPOLOGY::ConnectedItems( const JOINT* aStart, int aKindMask )
1030{
1031 return ITEM_SET();
1032}
1033
1034
1035const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
1036{
1037 return ITEM_SET();
1038}
1039
1040
1041bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
1042
1043
1045{
1046 NET_HANDLE refNet = aStart->Net();
1047 NET_HANDLE coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
1048 LINKED_ITEM* startItem = dynamic_cast<LINKED_ITEM*>( aStart );
1049
1050 if( !coupledNet || !startItem )
1051 return false;
1052
1053 LINE lp = m_world->AssembleLine( startItem, nullptr, false, false, false );
1054
1055 std::vector<ITEM*> pItems;
1056 std::vector<ITEM*> nItems;
1057
1058 for( ITEM* item : lp.Links() )
1059 {
1060 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
1061 pItems.push_back( item );
1062 }
1063
1064 std::set<ITEM*> coupledItems;
1065 m_world->AllItemsInNet( coupledNet, coupledItems );
1066
1067 for( ITEM* item : coupledItems )
1068 {
1069 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
1070 nItems.push_back( item );
1071 }
1072
1073 LINKED_ITEM* refItem = nullptr;
1074 LINKED_ITEM* coupledItem = nullptr;
1075 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
1076 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
1077 VECTOR2I targetPoint = aStart->Shape( -1 )->Centre();
1078
1079 auto findNItem = [&]( ITEM* p_item )
1080 {
1081 for( ITEM* n_item : nItems )
1082 {
1083 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
1084
1085 if( n_item->Kind() != p_item->Kind() )
1086 continue;
1087
1088 if( p_item->Kind() == ITEM::SEGMENT_T )
1089 {
1090 const SEGMENT* p_seg = static_cast<const SEGMENT*>( p_item );
1091 const SEGMENT* n_seg = static_cast<const SEGMENT*>( n_item );
1092
1093 if( n_seg->Width() != p_seg->Width() )
1094 continue;
1095
1096 if( !p_seg->Seg().ApproxParallel( n_seg->Seg(), DIFF_PAIR::DP_PARALLELITY_THRESHOLD ) )
1097 continue;
1098
1099 SEG p_clip, n_clip;
1100
1101 if( !commonParallelProjection( p_seg->Seg(), n_seg->Seg(), p_clip, n_clip ) )
1102 continue;
1103
1104 dist_sq = n_seg->Seg().SquaredDistance( p_seg->Seg() );
1105 }
1106 else if( p_item->Kind() == ITEM::ARC_T )
1107 {
1108 const ARC* p_arc = static_cast<const ARC*>( p_item );
1109 const ARC* n_arc = static_cast<const ARC*>( n_item );
1110
1111 if( n_arc->Width() != p_arc->Width() )
1112 continue;
1113
1114 VECTOR2I centerDiff = n_arc->CArc().GetCenter() - p_arc->CArc().GetCenter();
1115 SEG::ecoord centerDist_sq = centerDiff.SquaredEuclideanNorm();
1116
1117 if( centerDist_sq > SEG::Square( DIFF_PAIR::DP_PARALLELITY_THRESHOLD ) )
1118 continue;
1119
1120 dist_sq = SEG::Square( p_arc->CArc().GetRadius() - n_arc->CArc().GetRadius() );
1121 }
1122
1123 if( dist_sq <= minDist_sq )
1124 {
1125 SEG::ecoord distTarget_sq = n_item->Shape( -1 )->SquaredDistance( targetPoint );
1126 if( distTarget_sq < minDistTarget_sq )
1127 {
1128 minDistTarget_sq = distTarget_sq;
1129 minDist_sq = dist_sq;
1130
1131 refItem = static_cast<LINKED_ITEM*>( p_item );
1132 coupledItem = static_cast<LINKED_ITEM*>( n_item );
1133 }
1134 }
1135 }
1136 };
1137
1138 findNItem( startItem );
1139
1140 if( !coupledItem )
1141 {
1142 LINKED_ITEM* linked = static_cast<LINKED_ITEM*>( startItem );
1143 std::set<ITEM*> linksToTest;
1144
1145 for( int i = 0; i < linked->AnchorCount(); i++ )
1146 {
1147 const JOINT* jt = m_world->FindJoint( linked->Anchor( i ), linked );
1148
1149 if( !jt )
1150 continue;
1151
1152 for( ITEM* link : jt->LinkList() )
1153 {
1154 if( link != linked )
1155 linksToTest.emplace( link );
1156 }
1157 }
1158
1159 for( ITEM* link : linksToTest )
1160 findNItem( link );
1161 }
1162
1163 if( !coupledItem )
1164 return false;
1165
1166 LINE ln = m_world->AssembleLine( coupledItem, nullptr, false, false, false );
1167
1168 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
1169 std::swap( lp, ln );
1170
1171 int gap = -1;
1172
1173 if( refItem && refItem->Kind() == ITEM::SEGMENT_T )
1174 {
1175 // Segments are parallel -> compute pair gap
1176 const VECTOR2I refDir = refItem->Anchor( 1 ) - refItem->Anchor( 0 );
1177 const VECTOR2I displacement = refItem->Anchor( 1 ) - coupledItem->Anchor( 1 );
1178 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
1179 }
1180 else if( refItem && refItem->Kind() == ITEM::ARC_T )
1181 {
1182 const ARC* refArc = static_cast<ARC*>( refItem );
1183 const ARC* coupledArc = static_cast<ARC*>( coupledItem );
1184 gap = (int) std::abs( refArc->CArc().GetRadius() - coupledArc->CArc().GetRadius() ) - lp.Width();
1185 }
1186
1187 aPair = DIFF_PAIR( lp, ln, DP_DIMENSIONS( lp.Width(), gap ) );
1188 aPair.SetLayers( lp.Layers() );
1189
1190 return true;
1191}
1192
1193const TOPOLOGY::CLUSTER TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer, double aAreaExpansionLimit, NET_HANDLE aExcludedNet, int aOverrideClearance )
1194{
1195 CLUSTER cluster;
1196 std::deque<ITEM*> pending;
1197
1199
1200 opts.m_differentNetsOnly = false;
1201 opts.SetFixedClearanceOverride( aOverrideClearance );
1202
1203 pending.push_back( aStart );
1204
1205 BOX2I clusterBBox = aStart->Shape( aLayer )->BBox();
1206 int64_t initialArea = clusterBBox.GetArea();
1207 std::unordered_set<ITEM*> processed;
1208
1209 while( !pending.empty() )
1210 {
1211 NODE::OBSTACLES obstacles;
1212 ITEM* top = pending.front();
1213
1214 pending.pop_front();
1215
1216 if( processed.find( top ) == processed.end() )
1217 {
1218 cluster.m_items.push_back( top );
1219 }
1220
1221 processed.insert( top );
1222
1223 m_world->QueryColliding( top, obstacles, opts ); // only query touching objects
1224
1225 for( const OBSTACLE& obs : obstacles )
1226 {
1227 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
1228
1229 if( trackOnTrack )
1230 continue;
1231
1232 if( aExcludedNet && obs.m_item->Net() == aExcludedNet )
1233 continue;
1234
1235 if( obs.m_item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && obs.m_item->Layers().Overlaps( aLayer ) )
1236 {
1237 auto line = m_world->AssembleLine( static_cast<LINKED_ITEM*>(obs.m_item) );
1238 clusterBBox.Merge( line.CLine().BBox() );
1239 }
1240 else
1241 {
1242 clusterBBox.Merge( obs.m_item->Shape( aLayer )->BBox() );
1243 }
1244
1245 const int64_t currentArea = clusterBBox.GetArea();
1246 const double areaRatio = (double) currentArea / (double) ( initialArea + 1 );
1247
1248 if( aAreaExpansionLimit > 0.0 && areaRatio > aAreaExpansionLimit )
1249 break;
1250
1251 if( processed.find( obs.m_item ) == processed.end() &&
1252 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
1253 {
1254 processed.insert( obs.m_item );
1255 cluster.m_items.push_back( obs.m_item );
1256 pending.push_back( obs.m_item );
1257 }
1258 }
1259 }
1260
1261 return cluster;
1262}
1263
1264}
BOX2< VECTOR2I > BOX2I
Definition box2.h:917
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition board_item.h:99
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition box2.h:597
constexpr ecoord_type GetArea() const
Return the area of the rectangle.
Definition box2.h:700
KICAD_T Type() const
Returns the type of object.
Definition eda_item.h:110
static void OptimiseTraceInVia(SHAPE_LINE_CHAIN &aLine, const PCB_VIA *aVia, PCB_LAYER_ID aLayer)
Clips trace portions inside a VIA pad and replaces them with a straight-line segment from the VIA edg...
static bool IsPointInsideViaPad(const PCB_VIA *aVia, const VECTOR2I &aPoint, PCB_LAYER_ID aLayer)
Returns true if the given point falls inside VIA pad shape on the given layer.
static void OptimiseTraceInPad(SHAPE_LINE_CHAIN &aLine, const PAD *aPad, PCB_LAYER_ID aPcbLayer)
Optimises the given trace / line to minimise the electrical path length within the given pad.
Definition pad.h:61
int Width() const override
Definition pns_arc.h:90
const SHAPE_ARC & CArc() const
Definition pns_arc.h:118
Basic class for a differential pair.
static constexpr int DP_PARALLELITY_THRESHOLD
int Size() const
void Add(const LINE &aLine)
Base class for PNS router board items.
Definition pns_item.h:98
BOARD_ITEM * Parent() const
Definition pns_item.h:199
void SetLayers(const PNS_LAYER_RANGE &aLayers)
Definition pns_item.h:213
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
Definition pns_item.h:246
const PNS_LAYER_RANGE & Layers() const
Definition pns_item.h:212
virtual NET_HANDLE Net() const
Definition pns_item.h:210
PnsKind Kind() const
Return the type (kind) of the item.
Definition pns_item.h:173
virtual int Layer() const
Definition pns_item.h:216
bool OfKind(int aKindMask) const
Definition pns_item.h:181
virtual VECTOR2I Anchor(int n) const
Definition pns_item.h:272
std::string KindStr() const
Definition pns_item.cpp:318
virtual int AnchorCount() const
Definition pns_item.h:277
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
bool IsNonFanoutVia() const
Definition pns_joint.h:150
const ITEM_SET & CLinks() const
Definition pns_joint.h:312
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
const VECTOR2I & CPoint(int aIdx) const
Return the aIdx-th point of the line.
Definition pns_line.h:157
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assign a shape to the line (a polyline/line chain).
Definition pns_line.h:138
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
int SegmentCount() const
Definition pns_line.h:151
int PointCount() const
Definition pns_line.h:152
bool EndsWithVia() const
Definition pns_line.h:204
void Reverse()
Reverse the point/vertex order.
int Width() const
Return line width.
Definition pns_line.h:169
std::set< OBSTACLE > OBSTACLES
Definition pns_node.h:286
virtual PCB_LAYER_ID GetBoardLayerFromPNSLayer(int aLayer) const =0
const SEG & Seg() const
int Width() const override
Definition pns_segment.h:96
ITEM * NearestUnconnectedItem(const JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
std::set< const JOINT * > JOINT_SET
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
const CLUSTER AssembleCluster(ITEM *aStart, int aLayer, double aAreaExpansionLimit=0.0, NET_HANDLE aExcludedNet=nullptr, int aOverrideClearance=0)
std::vector< LINE > findLinesFromVia(ROUTER_IFACE *aRouterIface, VIA *aVia, const std::set< ITEM * > &aVisited)
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
WALK_RESULT walkTuningPath(ROUTER_IFACE *aRouterIface, LINE &aStartLine, bool aStartFromBack, const std::set< ITEM * > &aVisited)
ITEM_SET followTrivialPath(LINE *aLine, const JOINT **aTerminalJointA, const JOINT **aTerminalJointB, bool aFollowLockedSegments=false)
TOPOLOGY(NODE *aNode, ROUTER_IFACE *aIface=nullptr)
const ITEM_SET ConnectedItems(const JOINT *aStart, int aKindMask=ITEM::ANY_T)
bool NearestUnconnectedAnchorPoint(const LINE *aTrack, VECTOR2I &aPoint, PNS_LAYER_RANGE &aLayers, ITEM *&aItem)
const JOINT_SET ConnectedJoints(const JOINT *aStart)
const ITEM_SET AssembleTuningPath(ROUTER_IFACE *aRouterIface, ITEM *aStart, SOLID **aStartPad=nullptr, SOLID **aEndPad=nullptr)
Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fu...
PATH_RESULT followBranch(const JOINT *aStartJoint, LINKED_ITEM *aPrev, std::set< ITEM * > &aVisited, bool aFollowLockedSegments)
const ITEM_SET AssembleTrivialPath(ITEM *aStart, std::pair< const JOINT *, const JOINT * > *aTerminalJoints=nullptr, bool aFollowLockedSegments=false)
Assemble a trivial path between two joints given a starting item.
ROUTER_IFACE * m_iface
bool SimplifyLine(LINE *aLine)
const VECTOR2I & Pos() const
Definition pns_via.h:206
const SHAPE * Shape(int aLayer) const override
Return the geometrical shape of the item.
Definition pns_via.h:302
Represent a contiguous set of PCB layers.
Definition seg.h:38
ecoord SquaredDistance(const SEG &aSeg) const
Definition seg.cpp:35
VECTOR2I::extended_type ecoord
Definition seg.h:40
static SEG::ecoord Square(int a)
Definition seg.h:119
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition seg.cpp:771
double GetRadius() const
const VECTOR2I & GetCenter() const
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
long long int Length() const
Return length of the line chain in Euclidean metric.
An abstract shape on 2D plane.
Definition shape.h:124
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
virtual VECTOR2I Centre() const
Compute a center-of-mass of the shape.
Definition shape.h:242
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
constexpr extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition vector2d.h:559
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition vector2d.h:312
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition vector2d.h:281
int m_FollowBranchTimeout
Timeout for the PNS router's followBranch path search, in milliseconds.
PCB_LAYER_ID
A quick note on layer IDs:
Definition layer_ids.h:56
Push and Shove diff pair dimensions (gap) settings dialog.
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
void * NET_HANDLE
Definition pns_item.h:55
@ MK_HEAD
Definition pns_item.h:43
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition eda_angle.h:461
@ DIFF_PAIR
CITER next(CITER it)
Definition ptree.cpp:120
void SetFixedClearanceOverride(int aClearance)
Definition pns_node.h:147
bool m_overrideExemptPairs
Apply m_overrideClearance even to pairs the resolver exempts, such as same-net items.
Definition pns_node.h:143
Hold an object colliding with another object, along with some useful data about the collision.
Definition pns_node.h:98
std::vector< ITEM * > m_items
std::string path
KIBIS top(path, &reporter)
VECTOR2I end
wxString result
Test unit parsing edge cases and error handling.
int delta
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition typeinfo.h:89
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition typeinfo.h:79
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708
VIA_CROSS_SECTION_GEOMETRY::STATE STATE