KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_tracks_spreader.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
5 *
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 <algorithm>
23#include <deque>
24
25#include "pns_router.h"
26#include "pns_debug_decorator.h"
27#include "pns_utils.h"
28#include "pns_tracks_spreader.h"
29#include "pns_walkaround.h"
30#include "pns_optimizer.h"
31#include "pns_utils.h"
32
33#undef SPREAD_TRACKS_EXTRA_VERBOSE
34
35namespace PNS
36{
37
39 PLACEMENT_ALGO( aRouter )
40{
41 m_startItem = nullptr;
42 m_currentNode = nullptr;
43}
44
45
49
50
51bool TRACKS_SPREADER::Start( const VECTOR2I& aP, ITEM* aStartItem )
52{
53 if( m_auxItems.Empty() )
54 return false;
55
56 if( !aStartItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
57 return false;
58
59 m_startItem = static_cast<LINKED_ITEM*>( aStartItem );
60 m_startAnchor = aP;
61 m_currentNode = nullptr;
62
64 return false;
65
66 return true;
67}
68
69
70bool approxSegOverlaps( const SEG& aA, const SEG& aB, int aThreshold, int& aOverlapDist )
71{
72 if( aA.A == aA.B ) // single point corner case
73 {
74 if( aB.A == aA.A || aB.B == aA.A )
75 return true;
76
77 if( aB.Contains( aA.A, aThreshold ) )
78 {
79 aOverlapDist = aB.Distance( aA.A );
80 return true;
81 }
82 }
83
84 if( !aB.ApproxCollinear( aA, aThreshold ) )
85 return false;
86
87 if( aB.Contains( aA.A, aThreshold ) )
88 {
89 aOverlapDist = aB.Distance( aA.A );
90 return true;
91 }
92
93 if( aB.Contains( aA.B, aThreshold ) )
94 {
95 aOverlapDist = aB.Distance( aA.B );
96 return true;
97 }
98
99 if( aA.Contains( aB.A, aThreshold ) )
100 {
101 aOverlapDist = aA.Distance( aB.A );
102 return true;
103 }
104
105 if( aA.Contains( aB.B, aThreshold ) )
106 {
107 aOverlapDist = aA.Distance( aB.B );
108 return true;
109 }
110
111 return 0;
112}
113
114
115bool TRACKS_SPREADER::Move( const VECTOR2I& aP, ITEM* aEndItem )
116{
117 auto rnearest = m_rootLine.CLine().NearestPoint( aP );
118
119 PNS_DBG( Dbg(), AddPoint, m_startAnchor, GREEN, 300000, wxT( "move=start" ) );
120 PNS_DBG( Dbg(), AddPoint, rnearest, GREEN, 300000, wxT( "move=end" ) );
121
122 if( m_currentNode )
123 {
124 delete m_currentNode;
126 }
127
128 NODE* spreadNode = m_preSpreadNode->Branch();
129
130 auto clippedHead = breakAndReassemble( spreadNode, &m_rootLine, m_startAnchor, rnearest );
131 m_spreadableItems.clear();
132
133 if( clippedHead )
134 {
135#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
136 PNS_DBG( Dbg(), AddItem, &( *clippedHead ), GREEN, 10000,
137 wxString::Format( "clip-head %d", (int) clippedHead->LinkCount() ) );
138#endif
139
140 for( auto& lnk : clippedHead->Links() )
141 {
142 m_spreadableItems.insert( lnk );
143#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
144 PNS_DBG( Dbg(), AddItem, static_cast<const ITEM*>( lnk ), GREEN, 10000,
145 wxString::Format( "cliplinkd %d", 0 ) );
146#endif
147 }
148 }
149
150 for( SPREADABLE_LINE& l : m_lines )
151 {
152 LINE lrem( l.spreadableLine );
153#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
154 PNS_DBG( Dbg(), AddItem, &l.spreadableLine, RED, 10000,
155 wxString::Format( "rem-line l %d", (int) l.spreadableLine.LinkCount() ) );
156#endif
157 spreadNode->Remove( lrem );
158 }
159
160 std::unordered_set<ITEM*> processedItems;
161
162 auto spreadClearanceFunc = [&]( const ITEM* aA, const ITEM* aB, CLEARANCE_ASPECT aAspect ) -> int
163 {
164 auto lnkA = static_cast<const LINKED_ITEM*>( aA );
165 auto lnkB = static_cast<const LINKED_ITEM*>( aB );
166
167 if( !alg::contains( processedItems, aA ) && !alg::contains( processedItems, aB ) )
168 return 0;
169
170 if( aA->Net() == aB->Net() )
171 return -1;
172
173 bool Asp = m_spreadableItems.find( lnkA ) != m_spreadableItems.end();
174 bool Bsp = m_spreadableItems.find( lnkB ) != m_spreadableItems.end();
175
176 return Asp || Bsp ? Router()->Settings().GetSpreadTracksDistance() : -1;
177 };
178
179 for( LINKED_ITEM* lnk : clippedHead->Links() )
180 processedItems.insert( lnk );
181
182 for( SPREADABLE_LINE& entry : m_lines )
183 {
184 WALKAROUND walkaround( spreadNode, Router() );
186 walkaround.SetClearanceOverride( spreadClearanceFunc );
187 walkaround.SetDebugDecorator( Dbg() );
188 walkaround.SetUseClustering( false );
189 walkaround.SetLengthLimit( false, 0.0 );
190
191 PNS_DBG( Dbg(), BeginGroup, wxT( "grp-walk-details" ), 0 );
192 auto ret = walkaround.Route( entry.spreadableLine );
193 PNS_DBGN( Dbg(), EndGroup );
194
195 bool success = false;
196
197 for( auto policy : { WALKAROUND::WP_CW, WALKAROUND::WP_CCW } )
198 {
199 if( ret.status[policy] == WALKAROUND::ST_DONE )
200 {
201 spreadNode->Add( ret.lines[policy] );
202 entry.forwardLine = ret.lines[policy];
203
204
205 for( auto lnk : ret.lines[policy].Links() )
206 processedItems.insert( lnk );
207#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
208 PNS_DBG( Dbg(), AddItem, &ret.lines[policy], GREEN, 10000,
209 wxString::Format( "walk-line l %d pitems %d", ret.lines[policy].LinkCount(),
210 (int) processedItems.size() ) );
211#endif
212 for( auto lnk : ret.lines[policy].Links() )
213 {
214 bool spreadable = true;
215
216#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
217 PNS_DBG( Dbg(), BeginGroup, "spreadable-propagate", 0 );
218 PNS_DBG( Dbg(), AddItem, lnk, WHITE, 100000, wxString::Format( "lnk" ) );
219#endif
220 for( int i = 0; i < entry.spreadableLine.SegmentCount(); i++ )
221 {
222 const SEG& s = entry.spreadableLine.CSegment( i );
223
224 SEGMENT* ps = dynamic_cast<SEGMENT*>( lnk );
225 if( ps )
226 {
227 int overlapDist = 0;
228 if( ps->Seg() == s || s.ApproxOverlaps( ps->Seg() ) )
229 {
230 SEG c1, c2;
231 if( !commonParallelProjection( s, ps->Seg(), c1, c2 ) )
232 continue;
233
234 overlapDist = c1.Length();
235
236#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
237 PNS_DBG( Dbg(), AddShape, s, RED, 100000,
238 wxString::Format( "ns-dist %d", overlapDist ) );
239#endif
240
241 if( overlapDist > 100 ) // fixme: make configurable
242 spreadable = false;
243
244 break;
245 }
246 }
247 }
248#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
249 PNS_DBGN( Dbg(), EndGroup );
250#endif
251
252 if( spreadable )
253 {
254 m_spreadableItems.insert( lnk );
255#ifdef SPREAD_TRACKS_EXTRA_VERBOSE
256 PNS_DBG( Dbg(), AddItem, lnk, WHITE, 100000, wxString::Format( "spreadable" ) );
257#endif
258 }
259 }
260 success = true;
261 break;
262 }
263 }
264 if( !success )
265 {
266 PNS_DBG( Dbg(), AddItem, &entry.originLine, WHITE, 100000, wxString::Format( "failing-line" ) );
267 break;
268 }
269 }
270
271 for( auto& ent : m_lines )
272 {
273 spreadNode->Remove( ent.forwardLine );
274 ent.forwardLine.Line().Simplify2();
275 }
276
277 OPT_BOX2I totalAffectedArea;
278
279 for( SPREADABLE_LINE& entry : m_lines | std::views::reverse )
280 {
281 WALKAROUND walkaround( spreadNode, Router() );
283 walkaround.SetDebugDecorator( Dbg() );
284 walkaround.SetUseClustering( false );
285 walkaround.SetLengthLimit( false, 0.0 );
286
287 PNS_DBG( Dbg(), BeginGroup, wxT( "grp-back-details" ), 0 );
288 auto ret = walkaround.Route( entry.forwardLine );
289 PNS_DBGN( Dbg(), EndGroup );
290
291 bool success = false;
292 for( auto policy : { WALKAROUND::WP_CW, WALKAROUND::WP_CCW } )
293 {
294 if( ret.status[policy] == WALKAROUND::ST_DONE )
295 {
296 entry.backwardLine = ret.lines[policy];
297 OPT_BOX2I affectedArea = entry.backwardLine.ChangedArea( &entry.spreadableLine );
298 if( affectedArea.has_value() )
299 {
300 if( !totalAffectedArea )
301 totalAffectedArea = affectedArea;
302 else
303 totalAffectedArea->Merge( affectedArea.value() );
304 }
305 entry.backwardLine.Line().Simplify2();
306 spreadNode->Add( entry.backwardLine );
307
308 success = true;
309 break;
310 }
311 }
312 if( !success )
313 {
314 PNS_DBG( Dbg(), AddItem, &entry.originLine, WHITE, 100000, wxString::Format( "failing-line-back" ) );
315 break;
316 }
317 }
318
319 // stage 3: optimize
320
321 if( totalAffectedArea )
322 {
323 int delta = 4 * m_rootLine.Width(); // 4 is a perfectly fair choice for a fudge factor, isn't it?
324 totalAffectedArea->Inflate( delta );
325 }
326
327
328 for( SPREADABLE_LINE& entry : m_lines | std::views::reverse )
329 {
330 OPTIMIZER optimizer( spreadNode );
331 std::vector<SEG> doNotOptimizeSegs = findNoOptSegments( clippedHead.value(), entry );
332
333 int effort = OPTIMIZER::MERGE_SEGMENTS;
334
337
338 optimizer.SetEffortLevel( effort );
339 optimizer.SetPreserveSegments( doNotOptimizeSegs );
340
341 if( totalAffectedArea )
342 optimizer.SetRestrictArea( *totalAffectedArea );
343
344 spreadNode->Remove( entry.backwardLine );
345 optimizer.Optimize( &entry.backwardLine, &entry.optimizedLine );
346 spreadNode->Add( entry.optimizedLine );
347 }
348
349
350 m_currentNode = spreadNode;
351
352 return true;
353}
354
355
356bool TRACKS_SPREADER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
357{
358 if( !m_currentNode )
359 return false;
360
361 return true;
362}
363
364
366{
367 if( !m_currentNode )
368 return false;
369
371
372
373 return true;
374}
375
376
378{
380 m_currentNode = nullptr;
381 return true;
382}
383
384
386{
387 return true;
388}
389
390
391NODE* TRACKS_SPREADER::CurrentNode( bool aLoopsRemoved ) const
392{
394}
395
396
398{
399 return ITEM_SET();
400}
401
402
404{
405 return m_startAnchor;
406}
407
408
410{
411 return m_endAnchor;
412}
413
414
415const std::vector<NET_HANDLE> TRACKS_SPREADER::CurrentNets() const
416{
417 return std::vector<NET_HANDLE>();
418}
419
420
422{
423 return -1;
424}
425
426
428{
429 m_lines.clear();
430
431 NODE* world = Router()->GetWorld();
432
433 std::deque<LINKED_ITEM*> pending;
434
435 for( ITEM* item : m_auxItems.CItems() )
436 {
437 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
438 pending.push_back( static_cast<LINKED_ITEM*>( item ) );
439 }
440
441
443
444 // prepare a list of unique LINEs composed of the segments/arcs selected by the users
445 while( !pending.empty() )
446 {
447 LINKED_ITEM* item = pending.front();
448 pending.pop_front();
449
450 bool alreadyAssembled =
451 std::any_of( m_lines.begin(), m_lines.end(),
452 [item, this]( const SPREADABLE_LINE& aLine )
453 {
454 return aLine.originLine.ContainsLink( item ) || m_rootLine.ContainsLink( item );
455 } );
456
457 if( alreadyAssembled )
458 continue;
459
460 SPREADABLE_LINE line;
461 line.originLine = world->AssembleLine( item );
462 m_lines.push_back( line );
463 }
464
465 int margin = m_rootLine.Width();
466
467 for( const SPREADABLE_LINE& entry : m_lines )
468 margin += entry.originLine.Width();
469
470 margin += 0; //static_cast<int>( m_originLines.size() ) * Settings().GetSpreadTracksGap();
471
472
473 for( SPREADABLE_LINE& entry : m_lines )
474 {
475 const SHAPE_LINE_CHAIN& shape = entry.originLine.CLine();
476
477 int plNearest = -1;
478 int plFarthest = -1;
479
480 for( ITEM* item : m_auxItems.CItems() )
481 {
482 if( !item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
483 continue;
484
485 LINKED_ITEM* litem = static_cast<LINKED_ITEM*>( item );
486
487 if( !entry.originLine.ContainsLink( litem ) )
488 continue;
489
490 for( int i = 0; i < litem->AnchorCount(); i++ )
491 {
492 auto nearest = shape.NearestPoint( litem->Anchor( i ), false );
493 int pl = shape.PathLength( nearest );
494
495 if( pl < 0 )
496 continue;
497
498 if( plNearest < 0 || pl < plNearest )
499 plNearest = pl;
500
501 if( pl > plFarthest )
502 plFarthest = pl;
503 }
504 }
505
506
507 //PNS_DBG( Dbg(), AddItem, &entry.originLine, WHITE, 100000,
508 // wxString::Format( wxT( "pl-nearest %d pl-farthest %d orig-sc %d orig-lc %d" ), (int) plNearest, (int) plFarthest, entry.originLine.SegmentCount(), entry.originLine.LinkCount() ) );
509
510 if( plFarthest < 0 )
511 continue;
512
513 int lineLength = static_cast<int>( shape.Length() );
514
515 VECTOR2I pNearest = shape.PointAlong( std::max( 0, plNearest - margin ) );
516 VECTOR2I pFarthest = shape.PointAlong( std::min( lineLength, plFarthest + margin ) );
517
518 SHAPE_LINE_CHAIN pre, mid, post;
519 shape.Split( pNearest, pFarthest, pre, mid, post );
520
521 entry.spreadableLine = LINE( entry.originLine, mid );
522 entry.p_start = pNearest;
523 entry.p_end = pFarthest;
524 }
525
526 PNS_DBG( Dbg(), BeginGroup, "spreadable-lines", 0 );
527
528 for( const SPREADABLE_LINE& entry : m_lines )
529 PNS_DBG( Dbg(), AddItem, &entry.originLine, GREEN, 10000, wxT( "origin-line" ) );
530
531 PNS_DBGN( Dbg(), EndGroup );
532
533 PNS_DBG( Dbg(), BeginGroup, "spreadable-spans", 0 );
534
536
537 m_preSpreadNode = world->Branch();
538
539 for( size_t i = 0; i < m_lines.size(); i++ )
540 {
541 SPREADABLE_LINE& entry = m_lines[i];
542
543 PNS_DBG( Dbg(), AddPoint, entry.p_start, CYAN, 200000, wxString::Format( wxT( "span-nearest-%d" ), (int) i ) );
544 PNS_DBG( Dbg(), AddPoint, entry.p_end, LIGHTBLUE, 200000,
545 wxString::Format( wxT( "span-farthest-%d" ), (int) i ) );
546
547
548 auto adjusted = breakAndReassemble( m_preSpreadNode, &entry.originLine, entry.p_start, entry.p_end );
549
550 PNS_DBG( Dbg(), AddItem, &entry.originLine, YELLOW, 20000,
551 wxString::Format( wxT( "spreadable-line-%d sc %d lc %d adj %d" ), (int) i, 0, 0,
552 adjusted.has_value() ? 1 : 0 ) );
553
554
555 if( adjusted )
556 {
557 PNS_DBG( Dbg(), AddItem, &( *adjusted ), YELLOW, 20000, wxString::Format( wxT( "adj-line-%d" ), (int) i ) );
558
559 entry.spreadableLine = *adjusted;
560 }
561 }
562
563
564 PNS_DBGN( Dbg(), EndGroup );
565
566 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "total-spreadable %d" ), (int) m_spreadableItems.size() ) );
567
568
569 return true;
570}
571
572
574{
575 std::sort(
576 m_lines.begin(), m_lines.end(),
577 [this]( const SPREADABLE_LINE& aA, const SPREADABLE_LINE& aB )
578 {
579 SEG::ecoord distA =
580 ( aA.originLine.CLine().NearestPoint( m_startAnchor ) - m_startAnchor ).SquaredEuclideanNorm();
581 SEG::ecoord distB =
582 ( aB.originLine.CLine().NearestPoint( m_startAnchor ) - m_startAnchor ).SquaredEuclideanNorm();
583
584 return distA < distB;
585 } );
586}
587
588
589std::optional<LINE> TRACKS_SPREADER::breakAndReassemble( NODE* aNode, LINE* aOrigLine, const VECTOR2I& aP1,
590 const VECTOR2I& aP2 )
591{
592 LINE current( *aOrigLine );
593 aNode->Remove( aOrigLine );
594 SHAPE_LINE_CHAIN newShape( aOrigLine->CLine() );
595 newShape.Split( aP1 );
596 newShape.Split( aP2 );
597 LINE newLine( *aOrigLine, newShape );
598 aNode->Add( newLine );
599
600 auto jtA = aNode->FindJoint( aP1, &newLine );
601 auto jtB = aNode->FindJoint( aP2, &newLine );
602
603 if( !jtA || !jtB )
604 return std::nullopt;
605
606 std::vector<LINE> adjustedLines;
607
608 aNode->FindLinesBetweenJoints( *jtA, *jtB, adjustedLines );
609
610 if( adjustedLines.empty() )
611 return std::nullopt;
612
613 return adjustedLines[0];
614}
615
616
618{
619 m_auxItems = aAuxItems;
620}
621
622
623const std::vector<SEG> TRACKS_SPREADER::findNoOptSegments( const LINE& aClippedHead,
624 const TRACKS_SPREADER::SPREADABLE_LINE& aEntry ) const
625{
626 std::vector<SEG> segs;
627
628 const SHAPE_LINE_CHAIN& headShape = aClippedHead.CLine();
629 for( int s = 0; s < headShape.SegmentCount(); s++ )
630 {
631 const SEG& headSeg = headShape.CSegment( s );
632
633 for( int s2 = 0; s2 < aEntry.forwardLine.SegmentCount(); s2++ )
634 {
635 const SEG& spreadSeg = aEntry.forwardLine.CSegment( s2 );
636 SEG c1, c2;
637
638 if( commonParallelProjection( headSeg, spreadSeg, c1, c2 ) )
639 {
640 int dist = headSeg.Distance( spreadSeg );
641
642 PNS_DBG( Dbg(), AddShape, spreadSeg, LIGHTBLUE, 200000, wxString::Format( "com-par dist %d", dist ) );
643 segs.push_back( spreadSeg );
644 }
645 }
646 }
647
648 return segs;
649}
650} // namespace PNS
std::optional< BOX2I > OPT_BOX2I
Definition box2.h:921
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
ROUTER * Router() const
Return the instance of our router.
DEBUG_DECORATOR * Dbg() const
Base class for PNS router board items.
Definition pns_item.h:98
virtual NET_HANDLE Net() const
Definition pns_item.h:210
bool OfKind(int aKindMask) const
Definition pns_item.h:181
virtual VECTOR2I Anchor(int n) const
Definition pns_item.h:272
virtual int AnchorCount() const
Definition pns_item.h:277
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:62
const SHAPE_LINE_CHAIN & CLine() const
Definition pns_line.h:149
int SegmentCount() const
Definition pns_line.h:151
const SEG CSegment(int aIdx) const
Definition pns_line.h:159
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
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.
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.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition pns_node.cpp:765
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.
void KillChildren()
Destroy all child nodes. Applicable only to the root node.
void Remove(ARC *aArc)
Remove an item from this branch.
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
void SetRestrictArea(const BOX2I &aArea, bool aStrict=true)
void SetPreserveSegments(const std::vector< SEG > &aSegs)
void SetEffortLevel(int aEffort)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
A quick shortcut to optimize a line without creating and setting up an optimizer.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
@ MERGE_COLINEAR
Merge co-linear segments.
@ REQUIRE_OBTUSE_ANGLES
Try to prevent 90-degree or acute corners in a drag.
PLACEMENT_ALGO(ROUTER *aRouter)
void CommitRouting()
ROUTING_SETTINGS & Settings()
Definition pns_router.h:240
NODE * GetWorld() const
Definition pns_router.h:212
const SEG & Seg() const
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent board state.
std::vector< SPREADABLE_LINE > m_lines
virtual bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start placement/drag operation at point aP, taking item aStartItem as anchor (unless NULL).
const std::vector< NET_HANDLE > CurrentNets() const override
Returns the net(s) of currently routed track(s).
void SetSpreadableItems(const ITEM_SET &aAuxItems)
const VECTOR2I & CurrentStart() const override
Return the current start of the line(s) being placed/tuned.
TRACKS_SPREADER(ROUTER *aRouter)
const std::vector< SEG > findNoOptSegments(const LINE &aClippedHead, const TRACKS_SPREADER::SPREADABLE_LINE &aEntry) const
virtual bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Move the end of the currently routed primtive(s) to the point aP, taking aEndItem as the anchor (if n...
std::unordered_set< const LINKED_ITEM * > m_spreadableItems
const ITEM_SET Traces() override
Return all routed/tuned traces.
int CurrentLayer() const override
Return the layer of currently routed track.
virtual bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish=false) override
Commit the currently routed items to the parent node, taking aP as the final end point and aEndItem a...
static std::optional< LINE > breakAndReassemble(NODE *aNode, LINE *aOrigLine, const VECTOR2I &aP1, const VECTOR2I &aP2)
const VECTOR2I & CurrentEnd() const override
Return the current end of the line(s) being placed/tuned.
bool HasPlacedAnything() const override
void SetLengthLimit(bool aEnable, double aLengthExpansionFactor)
void SetUseClustering(bool aEnabled)
void SetAllowedPolicies(std::vector< WALK_POLICY > aPolicies, bool aAnyCompletePolicyIsSuccess=false)
STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void SetClearanceOverride(CLEARANCE_OVERRIDE_FUNC aFunc)
Definition seg.h:38
VECTOR2I A
Definition seg.h:45
VECTOR2I B
Definition seg.h:46
int Length() const
Return the length (this).
Definition seg.h:361
bool ApproxCollinear(const SEG &aSeg, int aDistanceThreshold=1) const
Definition seg.cpp:759
bool ApproxOverlaps(const SEG &aSeg, int aThreshold=3) const
Definition seg.h:320
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition seg.cpp:668
bool Contains(const SEG &aSeg) const
Definition seg.h:342
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const VECTOR2I PointAlong(int aPathLength) const
int Split(const VECTOR2I &aP, bool aExact=false)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
int SegmentCount() const
Return the number of segments in this line chain.
int PathLength(const VECTOR2I &aP, int aIndex=-1) const
Compute the walk path length from the beginning of the line chain and the point aP belonging to our l...
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
long long int Length() const
Return length of the line chain in Euclidean metric.
@ LIGHTBLUE
Definition color4d.h:58
@ WHITE
Definition color4d.h:44
@ GREEN
Definition color4d.h:53
@ CYAN
Definition color4d.h:54
@ YELLOW
Definition color4d.h:63
@ RED
Definition color4d.h:55
Push and Shove diff pair dimensions (gap) settings dialog.
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
CLEARANCE_ASPECT
Definition pns_node.h:69
bool approxSegOverlaps(const SEG &aA, const SEG &aB, int aThreshold, int &aOverlapDist)
bool contains(const _Container &__container, _Value __value)
Returns true if the container contains the given value.
Definition kicad_algo.h:96
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
int delta
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708