KiCad PCB EDA Suite
pns_line_placer.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2017 CERN
5 * Copyright (C) 2016-2021 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 along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#include <optional>
23#include <memory>
24
25#include "pns_arc.h"
26#include "pns_debug_decorator.h"
27#include "pns_line_placer.h"
28#include "pns_node.h"
29#include "pns_router.h"
30#include "pns_shove.h"
31#include "pns_solid.h"
32#include "pns_topology.h"
33#include "pns_walkaround.h"
35#include "pns_utils.h"
36
37#include <wx/log.h>
38
39namespace PNS {
40
42 PLACEMENT_ALGO( aRouter )
43{
45 m_world = nullptr;
46 m_shove = nullptr;
47 m_currentNode = nullptr;
48 m_idle = true;
49
50 // Init temporary variables (do not leave uninitialized members)
51 m_lastNode = nullptr;
52 m_placingVia = false;
53 m_currentNet = 0;
55 m_startItem = nullptr;
56 m_endItem = nullptr;
57 m_chainedPlacement = false;
58 m_orthoMode = false;
59 m_placementCorrect = false;
60}
61
62
64{
65}
66
67
69{
70 m_world = aWorld;
71}
72
73
75{
78
79 return VIA( aP, layers, m_sizes.ViaDiameter(), m_sizes.ViaDrill(), -1, m_sizes.ViaType() );
80}
81
82
83bool LINE_PLACER::ToggleVia( bool aEnabled )
84{
85 m_placingVia = aEnabled;
86
87 if( !aEnabled )
89
90 return true;
91}
92
93
95{
96 m_initial_direction = aDirection;
97
98 if( m_tail.SegmentCount() == 0 )
99 m_direction = aDirection;
100}
101
102
104{
106 SHAPE_LINE_CHAIN& head = m_head.Line();
107 SHAPE_LINE_CHAIN& tail = m_tail.Line();
108
109 // if there is no tail, there is nothing to intersect with
110 if( tail.PointCount() < 2 )
111 return false;
112
113 if( head.PointCount() < 2 )
114 return false;
115
116 // completely new head trace? chop off the tail
117 if( tail.CPoint(0) == head.CPoint(0) )
118 {
119 m_p_start = tail.CPoint( 0 );
120 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [sameP0]" ) );
122 tail.Clear();
123 return true;
124 }
125
126 tail.Intersect( head, ips );
127
128 // no intesection points - nothing to reduce
129 if( ips.empty() )
130 return false;
131
132 int n = INT_MAX;
133 VECTOR2I ipoint;
134
135 // if there is more than one intersection, find the one that is
136 // closest to the beginning of the tail.
137 for( const SHAPE_LINE_CHAIN::INTERSECTION& i : ips )
138 {
139 if( i.index_our < n )
140 {
141 n = i.index_our;
142 ipoint = i.p;
143 }
144 }
145
146 // ignore the point where head and tail meet
147 if( ipoint == head.CPoint( 0 ) || ipoint == tail.CPoint( -1 ) )
148 return false;
149
150 // Intersection point is on the first or the second segment: just start routing
151 // from the beginning
152 if( n < 2 )
153 {
154 m_p_start = tail.CPoint( 0 );
155 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [self-isect1]" ) );
156
158 tail.Clear();
159 head.Clear();
160
161 return true;
162 }
163 else
164 {
165 // Clip till the last tail segment before intersection.
166 // Set the direction to the one of this segment.
167 const SEG last = tail.CSegment( n - 1 );
168 m_p_start = last.A;
169 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [self-isect2]" ) );
170
171 m_direction = DIRECTION_45( last );
172 tail.Remove( n, -1 );
173 return true;
174 }
175
176 return false;
177}
178
179
181{
182 SHAPE_LINE_CHAIN& head = m_head.Line();
183 SHAPE_LINE_CHAIN& tail = m_tail.Line();
184
185 if( head.PointCount() < 2 )
186 return false;
187
188 int n = tail.PointCount();
189
190 if( n == 0 )
191 {
192 return false;
193 }
194 else if( n == 1 )
195 {
196 m_p_start = tail.CPoint( 0 );
197 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [pullback]" ) );
198
199 tail.Clear();
200 return true;
201 }
202
203 DIRECTION_45 first_head, last_tail;
204
205 wxASSERT( tail.PointCount() >= 2 );
206
207 if( !head.IsPtOnArc( 0 ) )
208 first_head = DIRECTION_45( head.CSegment( 0 ) );
209 else
210 first_head = DIRECTION_45( head.CArcs()[head.ArcIndex(0)] );
211
212 int lastSegIdx = tail.PointCount() - 2;
213
214 if( !tail.IsPtOnArc( lastSegIdx ) )
215 last_tail = DIRECTION_45( tail.CSegment( lastSegIdx ) );
216 else
217 last_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex(lastSegIdx)] );
218
219 DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
220
221 // case 1: we have a defined routing direction, and the currently computed
222 // head goes in different one.
223 bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
224
225 // case 2: regardless of the current routing direction, if the tail/head
226 // extremities form an acute or right angle, reduce the tail by one segment
227 // (and hope that further iterations) will result with a cleaner trace
228 bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
229
230 if( pullback_1 || pullback_2 )
231 {
232 lastSegIdx = tail.PrevShape( -1 );
233
234 if( !tail.IsPtOnArc( lastSegIdx ) )
235 {
236 const SEG& seg = tail.CSegment( lastSegIdx );
237 m_direction = DIRECTION_45( seg );
238 m_p_start = seg.A;
239 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [pullback3]" ) );
240
241 }
242 else
243 {
244 const SHAPE_ARC& arc = tail.CArcs()[tail.ArcIndex( lastSegIdx )];
245 m_direction = DIRECTION_45( arc );
246 m_p_start = arc.GetP0();
247 }
248
249 wxLogTrace( wxT( "PNS" ), wxT( "Placer: pullback triggered [%d] [%s %s]" ),
250 n, last_tail.Format().c_str(), first_head.Format().c_str() );
251
252 // erase the last point in the tail, hoping that the next iteration will
253 // result with a head trace that starts with a segment following our
254 // current direction.
255 if( n < 2 )
256 tail.Clear(); // don't leave a single-point tail
257 else
258 tail.RemoveShape( -1 );
259
260 if( !tail.SegmentCount() )
262
263 return true;
264 }
265
266 return false;
267}
268
269
271{
272 SHAPE_LINE_CHAIN& head = m_head.Line();
273 SHAPE_LINE_CHAIN& tail = m_tail.Line();
274
275 int n = tail.SegmentCount();
276
277 if( head.SegmentCount() < 1 )
278 return false;
279
280 // Don't attempt this for too short tails
281 if( n < 2 )
282 return false;
283
284 // Start from the segment farthest from the end of the tail
285 // int start_index = std::max(n - 1 - ReductionDepth, 0);
286
287 DIRECTION_45 new_direction;
288 VECTOR2I new_start;
289 int reduce_index = -1;
290
291 for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
292 {
293 const SEG s = tail.CSegment( i );
294 DIRECTION_45 dir( s );
295
296 // calculate a replacement route and check if it matches
297 // the direction of the segment to be replaced
298 SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
299
300 if( replacement.SegmentCount() < 1 )
301 continue;
302
303 LINE tmp( m_tail, replacement );
304
306 break;
307
308 if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
309 {
310 new_start = s.A;
311 new_direction = dir;
312 reduce_index = i;
313 }
314 }
315
316 if( reduce_index >= 0 )
317 {
318 wxLogTrace( wxT( "PNS" ), wxT( "Placer: reducing tail: %d" ), reduce_index );
319 SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
320
321 m_p_start = new_start;
322 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [reduceTail]" ) );
323
324 m_direction = new_direction;
325 tail.Remove( reduce_index + 1, -1 );
326 head.Clear();
327 return true;
328 }
329
330 if( !tail.SegmentCount() )
332
333 return false;
334}
335
336
338{
339 SHAPE_LINE_CHAIN& head = m_head.Line();
340 SHAPE_LINE_CHAIN& tail = m_tail.Line();
341
342 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE
345
346 head.Simplify();
347 tail.Simplify();
348
349 int n_head = head.ShapeCount();
350 int n_tail = tail.ShapeCount();
351
352 if( n_head < 3 )
353 {
354 wxLogTrace( wxT( "PNS" ), wxT( "Merge failed: not enough head segs." ) );
355 return false;
356 }
357
358 if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
359 {
360 wxLogTrace( wxT( "PNS" ), wxT( "Merge failed: head and tail discontinuous." ) );
361 return false;
362 }
363
364 if( m_head.CountCorners( ForbiddenAngles ) != 0 )
365 return false;
366
367 DIRECTION_45 dir_tail, dir_head;
368
369 if( !head.IsPtOnArc( 0 ) )
370 dir_head = DIRECTION_45( head.CSegment( 0 ) );
371 else
372 dir_head = DIRECTION_45( head.CArcs()[head.ArcIndex( 0 )] );
373
374 if( n_tail )
375 {
376 wxASSERT( tail.PointCount() >= 2 );
377 int lastSegIdx = tail.PointCount() - 2;
378
379 if( !tail.IsPtOnArc( lastSegIdx ) )
380 dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
381 else
382 dir_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
383
384 if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
385 return false;
386 }
387
388 tail.Append( head );
389
390 tail.Simplify();
391
392 SEG last = tail.CSegment( -1 );
393 m_p_start = last.B;
394
395 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [mergeHead]" ) );
396
397
398 int lastSegIdx = tail.PointCount() - 2;
399
400 if( !tail.IsArcSegment( lastSegIdx ) )
401 m_direction = DIRECTION_45( tail.CSegment( -1 ) );
402 else
403 m_direction = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
404
405 head.Remove( 0, -1 );
406
407 // wxLogTrace( wxT( "PNS" ), wxT( "Placer: merge %d, new direction: %s" ), n_head,
408// m_direction.Format().c_str() );
409
410 head.Simplify();
411 tail.Simplify();
412
413 return true;
414}
415
416
418{
419 // Keep distances squared for performance
420 SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
421 VECTOR2I closest;
422
423 for( int i = 0; i < line.SegmentCount(); i++ )
424 {
425 const SEG& s = line.CSegment( i );
426 VECTOR2I a = s.NearestPoint( p );
427 int d_sq = (a - p).SquaredEuclideanNorm();
428
429 if( d_sq < min_dist_sq )
430 {
431 min_dist_sq = d_sq;
432 closest = a;
433 }
434 }
435
436 return closest;
437}
438
439
440static bool cursorDistMinimum( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aCursor, double lengthThreshold, int& theDist, VECTOR2I& aNearest )
441{
442 std::vector<int> dists;
443 std::vector<VECTOR2I> pts;
444
445 if( aL.PointCount() == 0 )
446 return false;
447
448 VECTOR2I lastP = aL.CPoint(-1);
449 int accumulatedDist = 0;
450
451 dists.reserve( 2 * aL.PointCount() );
452
453 for( int i = 0; i < aL.SegmentCount(); i++ )
454 {
455 const SEG& s = aL.CSegment( i );
456
457 dists.push_back( ( aCursor - s.A ).EuclideanNorm() );
458 pts.push_back( s.A );
459 auto pn = s.NearestPoint( aCursor );
460
461 if( pn != s.A && pn != s.B )
462 {
463 dists.push_back( ( pn - aCursor ).EuclideanNorm() );
464 pts.push_back( pn );
465 }
466
467 accumulatedDist += s.Length();
468
469 if ( accumulatedDist > lengthThreshold )
470 {
471 lastP = s.B;
472 break;
473 }
474 }
475
476 dists.push_back( ( aCursor - lastP ).EuclideanNorm() );
477 pts.push_back( lastP );
478
479 int minDistLoc = std::numeric_limits<int>::max();
480 int minPLoc = -1;
481 int minDistGlob = std::numeric_limits<int>::max();
482 int minPGlob = -1;
483
484 for( int i = 0; i < dists.size(); i++ )
485 {
486 int d = dists[i];
487
488 if( d < minDistGlob )
489 {
490 minDistGlob = d;
491 minPGlob = i;
492 }
493 }
494
495 if( dists.size() >= 3 )
496 {
497 for( int i = 0; i < dists.size() - 3; i++ )
498 {
499 if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
500 {
501 int d = dists[i + 1];
502 if( d < minDistLoc )
503 {
504 minDistLoc = d;
505 minPLoc = i + 1;
506 }
507 }
508 }
509
510 if( dists.back() < minDistLoc && minPLoc >= 0 )
511 {
512 minDistLoc = dists.back();
513 minPLoc = dists.size() - 1;
514 }
515 }
516 else
517 {
518 // Too few points: just use the global
519 minDistLoc = minDistGlob;
520 minPLoc = minPGlob;
521 }
522
523// fixme: I didn't make my mind yet if local or global minimum feels better. I'm leaving both
524// in the code, enabling the global one by default
525 minPLoc = -1;
526
527 if( minPLoc < 0 )
528 {
529 theDist = minDistGlob;
530 aNearest = pts[minPGlob];
531 return true;
532 }
533 else
534 {
535 theDist = minDistLoc;
536 aNearest = pts[minPLoc];
537 return true;
538 }
539}
540
541
542bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
543{
544 LINE initTrack( m_head );
545 LINE walkFull( m_head );
546
547 initTrack.RemoveVia();
548 walkFull.RemoveVia();
549
550 int effort = 0;
551 bool viaOk = false;
552
553 VECTOR2I walkP = aP;
554
555 WALKAROUND walkaround( m_currentNode, Router() );
556
557 walkaround.SetSolidsOnly( false );
558 walkaround.SetDebugDecorator( Dbg() );
559 walkaround.SetLogger( Logger() );
560 walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
561
562 char name[50];
563 int round = 0;
564
565 do {
566 snprintf( name, sizeof( name ), "walk-round-%d", round );
567 PNS_DBG( Dbg(), BeginGroup, name, 0 );
568
569 viaOk = buildInitialLine( walkP, initTrack, round == 0 );
570
571 double initialLength = initTrack.CLine().Length();
572 double hugThresholdLength = initialLength * Settings().WalkaroundHugLengthThreshold();
573
574 WALKAROUND::RESULT wr = walkaround.Route( initTrack );
575
576 SHAPE_LINE_CHAIN l_cw = wr.lineCw.CLine();
577 SHAPE_LINE_CHAIN l_ccw = wr.lineCcw.CLine();
578
580 {
581 int len_cw = wr.statusCw == WALKAROUND::DONE ? l_cw.Length() : INT_MAX;
582 int len_ccw = wr.statusCcw == WALKAROUND::DONE ? l_ccw.Length() : INT_MAX;
583
584 PNS_DBG( Dbg(), AddItem, &wr.lineCw, CYAN, 10000, wxT( "wf-result-cw" ) );
585 PNS_DBG( Dbg(), AddItem, &wr.lineCcw, BLUE, 20000, wxT( "wf-result-ccw" ) );
586
587 int bestLength = len_cw < len_ccw ? len_cw : len_ccw;
588
589 if( bestLength > hugThresholdLength )
590 {
593 }
594
595 SHAPE_LINE_CHAIN& bestLine = len_cw < len_ccw ? l_cw : l_ccw;
596 walkFull.SetShape( bestLine );
597 }
598
600 {
601 bool valid_cw = false, valid_ccw = false;
602 VECTOR2I p_cw, p_ccw;
603 int dist_ccw = 0, dist_cw = 0;
604
606 {
607 valid_ccw = cursorDistMinimum( l_ccw, aP, hugThresholdLength, dist_ccw, p_ccw );
608
609 if( valid_ccw )
610 {
611 int idx_ccw = l_ccw.Split( p_ccw );
612 l_ccw = l_ccw.Slice( 0, idx_ccw );
613 PNS_DBG( Dbg(), AddPoint, p_ccw, BLUE, 500000, wxT( "hug-target-ccw" ) );
614 PNS_DBG( Dbg(), AddShape, &l_ccw, MAGENTA, 200000, wxT( "wh-result-ccw" ) );
615 }
616 }
617
619 {
620 valid_cw = cursorDistMinimum( l_cw, aP, hugThresholdLength, dist_cw, p_cw );
621
622 if( valid_cw )
623 {
624 int idx_cw = l_cw.Split( p_cw );
625 l_cw = l_cw.Slice( 0, idx_cw );
626 PNS_DBG( Dbg(), AddPoint, p_cw, YELLOW, 500000, wxT( "hug-target-cw" ) );
627 PNS_DBG( Dbg(), AddShape, &l_cw, BLUE, 200000, wxT( "wh-result-cw" ) );
628 }
629 }
630
631 if( dist_cw < dist_ccw && valid_cw )
632 {
633 walkFull.SetShape( l_cw );
634 walkP = p_cw;
635 }
636 else if ( valid_ccw )
637 {
638 walkFull.SetShape( l_ccw );
639 walkP = p_ccw;
640 }
641 else
642 {
643 PNS_DBGN( Dbg(), EndGroup );
644 return false;
645 }
646 }
647 else if ( wr.statusCcw == WALKAROUND::STUCK || wr.statusCw == WALKAROUND::STUCK )
648 {
649 PNS_DBGN( Dbg(), EndGroup );
650 return false;
651 }
652
653 PNS_DBGN( Dbg(), EndGroup );
654
655 round++;
656 } while( round < 2 && m_placingVia );
657
658 PNS_DBG( Dbg(), AddItem, &walkFull, GREEN, 200000, wxT( "walk-full" ) );
659
660 switch( Settings().OptimizerEffort() )
661 {
662 case OE_LOW:
663 effort = 0;
664 break;
665
666 case OE_MEDIUM:
667 case OE_FULL:
669 break;
670 }
671
673
674 // Smart Pads is incompatible with 90-degree mode for now
675 if( Settings().SmartPads()
676 && ( cornerMode == DIRECTION_45::MITERED_45 || cornerMode == DIRECTION_45::ROUNDED_45 )
678 {
679 effort |= OPTIMIZER::SMART_PADS;
680 }
681
682 if( m_placingVia && viaOk )
683 {
684 walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
685 }
686
687 OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
688
689 if( m_currentNode->CheckColliding( &walkFull ) )
690 {
691 return false;
692 }
693
694 aNewHead = walkFull;
695
696 return true;
697}
698
699
700bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead )
701{
703 m_head.SetBlockingObstacle( nullptr );
704
705 auto obs = m_currentNode->NearestObstacle( &m_head );
706
707 // If the head is in colliding state, snap to the hull of the first obstacle.
708 // This way, one can route tracks as tightly as possible without enabling
709 // the shove/walk mode that certain users find too intrusive.
710 if( obs )
711 {
712 int cl = m_currentNode->GetClearance( obs->m_item, &m_head, false );
713 auto hull = obs->m_item->Hull( cl, m_head.Width() );
714
715 auto nearest = hull.NearestPoint( aP );
716
717 if( ( nearest - aP ).EuclideanNorm() < m_head.Width() / 2 )
718 {
719 buildInitialLine( nearest, m_head );
720 }
721 }
722
723 // Note: Something like the below could be used to implement a "stop at first obstacle" mode,
724 // but we don't have one right now and there isn't a lot of demand for one. If we do end up
725 // doing that, put it in a new routing mode as "highlight collisions" mode should not have
726 // collision handling other than highlighting.
727#if 0
728 if( !Settings().AllowDRCViolations() )
729 {
731
732 if( obs && obs->m_distFirst != INT_MAX )
733 {
734 buildInitialLine( obs->m_ipFirst, m_head );
735 m_head.SetBlockingObstacle( obs->m_item );
736 }
737 }
738#endif
739
740 aNewHead = m_head;
741
742 return true;
743}
744
745
746bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
747{
748 LINE initTrack( m_head );
749 LINE walkSolids, l2;
750
751 bool viaOk = buildInitialLine( aP, initTrack );
752
753 m_currentNode = m_shove->CurrentNode();
754
755 m_shove->SetLogger( Logger() );
756 m_shove->SetDebugDecorator( Dbg() );
757
758 OPTIMIZER optimizer( m_currentNode );
759
760 WALKAROUND walkaround( m_currentNode, Router() );
761
762 walkaround.SetSolidsOnly( true );
763 walkaround.SetIterationLimit( 10 );
764 walkaround.SetDebugDecorator( Dbg() );
765 walkaround.SetLogger( Logger() );
766 WALKAROUND::WALKAROUND_STATUS stat_solids = walkaround.Route( initTrack, walkSolids );
767
769 optimizer.SetCollisionMask( ITEM::SOLID_T );
770 optimizer.Optimize( &walkSolids );
771
772 if( stat_solids == WALKAROUND::DONE )
773 l2 = walkSolids;
774 else
775 l2 = initTrack.ClipToNearestObstacle( m_shove->CurrentNode() );
776
777 LINE l( m_tail );
778 l.Line().Append( l2.CLine() );
779 l.Line().Simplify();
780
781 if( l.PointCount() == 0 || l2.PointCount() == 0 )
782 {
783 aNewHead = m_head;
784 return false;
785 }
786
787 if( m_placingVia && viaOk )
788 {
789 VIA v1( makeVia( l.CPoint( -1 ) ) );
790 VIA v2( makeVia( l2.CPoint( -1 ) ) );
791
792 l.AppendVia( v1 );
793 l2.AppendVia( v2 );
794 }
795
796 l.Line().Simplify();
797
798 // in certain, uncommon cases there may be loops in the head+tail, In such case, we don't
799 // shove to avoid screwing up the database.
800 if( l.HasLoops() )
801 {
802 aNewHead = m_head;
803 return false;
804 }
805
806 if( m_endItem )
807 {
808 // Make sure the springback algorithm won't erase the NODE that owns m_endItem.
809 m_shove->SetSpringbackDoNotTouchNode( m_endItem->Owner() );
810 }
811
812 SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
813
814 m_currentNode = m_shove->CurrentNode();
815
816 if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
817 {
818 if( status == SHOVE::SH_HEAD_MODIFIED )
819 l2 = m_shove->NewHead();
820
821 optimizer.SetWorld( m_currentNode );
822
823 int effortLevel = OPTIMIZER::MERGE_OBTUSE;
824
825 if( Settings().SmartPads() && !m_mouseTrailTracer.IsManuallyForced() )
826 effortLevel = OPTIMIZER::SMART_PADS;
827
828 optimizer.SetEffortLevel( effortLevel );
829
830 optimizer.SetCollisionMask( ITEM::ANY_T );
831 optimizer.Optimize( &l2 );
832
833 aNewHead = l2;
834
835 return true;
836 }
837 else
838 {
839 walkaround.SetWorld( m_currentNode );
840 walkaround.SetSolidsOnly( false );
841 walkaround.SetIterationLimit( 10 );
842 walkaround.Route( initTrack, l2 );
843 aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
844
845 return false;
846 }
847
848 return false;
849}
850
851
852bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead )
853{
854 switch( Settings().Mode() )
855 {
856 case RM_MarkObstacles:
857 return rhMarkObstacles( aP, aNewHead );
858 case RM_Walkaround:
859 return rhWalkOnly( aP, aNewHead );
860 case RM_Shove:
861 return rhShoveOnly( aP, aNewHead );
862 default:
863 break;
864 }
865
866 return false;
867}
868
869
871{
872 LINE linetmp = Trace();
873
874 PNS_DBG( Dbg(), Message, "optimize HT" );
875
876 // NOTE: FANOUT_CLEANUP can override posture setting at the moment
879 {
880 if( linetmp.SegmentCount() < 1 )
881 return false;
882
883 m_head = linetmp;
884 m_p_start = linetmp.CLine().CPoint( 0 );
885
886 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [optFanoutCleanup]" ) );
887
888 m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
889 m_tail.Line().Clear();
890
891 return true;
892 }
893
894 SHAPE_LINE_CHAIN& head = m_head.Line();
895 SHAPE_LINE_CHAIN& tail = m_tail.Line();
896
897 int tailLookbackSegments = 3;
898
899 //if(m_currentMode() == RM_Walkaround)
900 // tailLookbackSegments = 10000;
901
902 int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
903
904 if( tail.ShapeCount() < 3 )
905 return false;
906
907 // assemble TailLookbackSegments tail segments with the current head
908 SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
909
910 int end = std::min(2, head.PointCount() - 1 );
911
912 opt_line.Append( head.Slice( 0, end ) );
913
914 LINE new_head( m_tail, opt_line );
915
916 // and see if it could be made simpler by merging obtuse/collnear segments.
917 // If so, replace the (threshold) last tail points and the head with
918 // the optimized line
919
920
921 PNS_DBG( Dbg(), AddItem, &new_head, LIGHTCYAN, 10000, wxT( "ht-newline" ) );
922
924 {
925 LINE tmp( m_tail, opt_line );
926
927 head.Clear();
928 tail.Replace( -threshold, -1, new_head.CLine() );
929 tail.Simplify();
930
931 m_p_start = new_head.CLine().CPoint( -1 );
932
933 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [opt-tail-head]" ) );
934
935 m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
936
937 return true;
938 }
939
940 return false;
941}
942
943
945{
946 bool fail = false;
947 bool go_back = false;
948
949 int i, n_iter = 1;
950
951 LINE new_head;
952
953 wxLogTrace( wxT( "PNS" ), wxT( "routeStep: direction: %s head: %d, tail: %d shapes" ),
954 m_direction.Format().c_str(),
956 m_tail.ShapeCount() );
957
958 PNS_DBG( Dbg(), BeginGroup, wxT( "route-step" ), 0 );
959
960 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-init" ) );
961 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-init" ) );
962
963 for( i = 0; i < n_iter; i++ )
964 {
965 if( !go_back && Settings().FollowMouse() )
966 reduceTail( aP );
967
968 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-after-reduce" ) );
969 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-after-reduce" ) );
970
971 go_back = false;
972
973 if( !routeHead( aP, new_head ) )
974 {
975 fail = true;
976 }
977
978 PNS_DBG( Dbg(), AddItem, &new_head, LIGHTGREEN, 100000, wxString::Format( "new_head [fail: %d]", fail?1:0 ) );
979
980 if( fail )
981 break;
982
983 m_head = new_head;
984
986 {
987 n_iter++;
988 go_back = true;
989 }
990
991 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-after-si" ) );
992 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-after-si" ) );
993
994 if( !go_back && handlePullback() )
995 {
996 n_iter++;
997 go_back = true;
998 }
999
1000 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 100000, wxT( "tail-after-pb" ) );
1001 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 100000, wxT( "head-after-pb" ) );
1002 }
1003
1004 if( fail )
1005 {
1006 PNS_DBG( Dbg(), Message, "routeStep failed" );
1007
1008 if( m_last_head.PointCount() > 0 )
1009 {
1011 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 100000, "head-before-re-route" );
1012
1013 VECTOR2I lastValidRoutePoint = m_head.CPoint( m_head.PointCount() - 1 );
1014
1015 // Re-route, so the shove state gets reverted
1016 if( !routeHead( lastValidRoutePoint, m_head ) )
1017 PNS_DBG( Dbg(), Message, "****Unable to recover.***** Route head failed, second time" );
1018
1019 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 100000, "head-after-re-route" );
1020 }
1021 else
1022 {
1023 m_head.RemoveVia();
1024 m_head.Clear();
1025 }
1026 }
1027 else
1028 {
1030 }
1031
1032 if( !fail && Settings().FollowMouse() )
1033 {
1034 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-pre-merge" ) );
1035 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-pre-merge" ) );
1036
1038 {
1039 mergeHead();
1040 }
1041
1042 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 100000, wxT( "tail-post-merge" ) );
1043 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 100000, wxT( "head-post-merge" ) );
1044 }
1045
1046 PNS_DBGN( Dbg(), EndGroup );
1047}
1048
1049
1051{
1052 routeStep( aP );
1053
1054 if (!m_head.PointCount() )
1055 return false;
1056
1057 return m_head.CPoint(-1) == aP;
1058}
1059
1060
1062{
1063 LINE tmp( m_head );
1064
1065 tmp.SetShape( m_tail.CLine() );
1066 tmp.Line().Append( m_head.CLine() );
1067
1068 PNS_DBG( Dbg(), AddItem, &m_tail, GREEN, 100000, wxT( "tmp-tail" ) );
1069 PNS_DBG( Dbg(), AddItem, &m_head, LIGHTGREEN, 100000, wxT( "tmp-head" ) );
1070
1071 tmp.Line().Simplify();
1072 return tmp;
1073}
1074
1075
1077{
1079 return ITEM_SET( &m_currentTrace );
1080}
1081
1082
1084{
1086}
1087
1088
1089NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
1090{
1091 if( aLoopsRemoved && m_lastNode )
1092 return m_lastNode;
1093
1094 return m_currentNode;
1095}
1096
1097
1099{
1100 if( !aSeg )
1101 return false;
1102
1103 if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
1104 return false;
1105
1106 JOINT* jt = aNode->FindJoint( aP, aSeg );
1107
1108 if( jt && jt->LinkCount() >= 1 )
1109 return false;
1110
1111 SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
1112
1113 std::unique_ptr<SEGMENT> s_new[2] = { Clone( *s_old ), Clone( *s_old ) };
1114
1115 s_new[0]->SetEnds( s_old->Seg().A, aP );
1116 s_new[1]->SetEnds( aP, s_old->Seg().B );
1117
1118 aNode->Remove( s_old );
1119 aNode->Add( std::move( s_new[0] ), true );
1120 aNode->Add( std::move( s_new[1] ), true );
1121
1122 return true;
1123}
1124
1125
1126bool LINE_PLACER::SetLayer( int aLayer )
1127{
1128 if( m_idle )
1129 {
1130 m_currentLayer = aLayer;
1131 return true;
1132 }
1133 else if( m_chainedPlacement )
1134 {
1135 return false;
1136 }
1137 else if( !m_startItem
1138 || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) )
1139 || ( m_startItem->OfKind( ITEM::SOLID_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
1140 {
1141 m_currentLayer = aLayer;
1145 m_head.Line().Clear();
1146 m_tail.Line().Clear();
1148 m_head.RemoveVia();
1149 m_tail.RemoveVia();
1153 Move( m_currentEnd, nullptr );
1154 return true;
1155 }
1156
1157 return false;
1158}
1159
1160
1161bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
1162{
1163 m_placementCorrect = false;
1164 m_currentStart = VECTOR2I( aP );
1165 m_currentEnd = VECTOR2I( aP );
1166 m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
1167 m_startItem = aStartItem;
1168 m_placingVia = false;
1169 m_chainedPlacement = false;
1171 m_endItem = nullptr;
1172
1173 setInitialDirection( Settings().InitialDirection() );
1174
1175 initPlacement();
1176
1177 DIRECTION_45 initialDir = m_initial_direction;
1179
1180 if( aStartItem && aStartItem->Kind() == ITEM::SEGMENT_T )
1181 {
1182 // If we land on a segment endpoint, assume the starting direction is continuing along
1183 // the same direction as the endpoint. If we started in the middle, don't set a
1184 // direction so that the posture solver is not biased.
1185 SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
1186
1187 if( aP == seg.A )
1188 lastSegDir = DIRECTION_45( seg.Reversed() );
1189 else if( aP == seg.B )
1190 lastSegDir = DIRECTION_45( seg );
1191 }
1192 else if( aStartItem && aStartItem->Kind() == ITEM::SOLID_T &&
1193 static_cast<SOLID*>( aStartItem )->Parent()->Type() == PCB_PAD_T )
1194 {
1195 double angle = static_cast<SOLID*>( aStartItem )->GetOrientation().AsDegrees();
1196 angle = ( angle + 22.5 ) / 45.0;
1197 initialDir = DIRECTION_45( static_cast<DIRECTION_45::Directions>( int( angle ) ) );
1198 }
1199
1200 wxLogTrace( wxT( "PNS" ), wxT( "Posture: init %s, last seg %s" ),
1201 initialDir.Format(), lastSegDir.Format() );
1202
1207 m_mouseTrailTracer.SetMouseDisabled( !Settings().GetAutoPosture() );
1208
1209 NODE *n;
1210
1211 if ( Settings().Mode() == PNS::RM_Shove )
1212 n = m_shove->CurrentNode();
1213 else
1214 n = m_currentNode;
1215
1217
1218 return true;
1219}
1220
1221
1223{
1224 m_idle = false;
1225
1226 m_head.Line().Clear();
1227 m_tail.Line().Clear();
1234 m_head.RemoveVia();
1235 m_tail.RemoveVia();
1236
1239
1240 NODE* world = Router()->GetWorld();
1241
1242 world->KillChildren();
1243 NODE* rootNode = world->Branch();
1244
1246
1247 setWorld( rootNode );
1248
1249 wxLogTrace( wxT( "PNS" ), wxT( "world %p, intitial-direction %s layer %d" ),
1250 m_world,
1251 m_direction.Format().c_str(),
1253
1254 m_lastNode = nullptr;
1256
1257 m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1258}
1259
1260
1261bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
1262{
1263 LINE current;
1264 VECTOR2I p = aP;
1265 int eiDepth = -1;
1266
1267 if( aEndItem && aEndItem->Owner() )
1268 eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
1269
1270 if( m_lastNode )
1271 {
1272 delete m_lastNode;
1273 m_lastNode = nullptr;
1274 }
1275
1276 m_endItem = aEndItem;
1277
1278 bool reachesEnd = route( p );
1279
1280 current = Trace();
1281
1282 if( !current.PointCount() )
1284 else
1285 m_currentEnd = current.CLine().CPoint( -1 );
1286
1287 NODE* latestNode = m_currentNode;
1288 m_lastNode = latestNode->Branch();
1289
1290 if( reachesEnd
1291 && eiDepth >= 0
1292 && aEndItem && latestNode->Depth() >= eiDepth
1293 && current.SegmentCount() )
1294 {
1295 SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1296
1297 if( Settings().RemoveLoops() )
1298 removeLoops( m_lastNode, current );
1299 }
1300
1303 return true;
1304}
1305
1306
1307bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1308{
1309 bool fixAll = Settings().GetFixAllSegments();
1310 bool realEnd = false;
1311
1312 LINE pl = Trace();
1313
1314 if( Settings().Mode() == RM_MarkObstacles )
1315 {
1316 // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1317 // user has more responsibility and authority.
1318
1319 if( aEndItem )
1320 {
1321 // The user has indicated a connection should be made. If either the trace or
1322 // endItem is net-less, then allow the connection by adopting the net of the other.
1323 if( m_currentNet <= 0 )
1324 {
1325 m_currentNet = aEndItem->Net();
1326 pl.SetNet( m_currentNet );
1327 }
1328 else if (aEndItem->Net() <= 0 )
1329 {
1330 aEndItem->SetNet( m_currentNet );
1331 }
1332 }
1333
1334 // Collisions still prevent fixing unless "Allow DRC violations" is checked
1335 if( !Settings().AllowDRCViolations() && m_world->CheckColliding( &pl ) )
1336 return false;
1337 }
1338
1339 const SHAPE_LINE_CHAIN& l = pl.CLine();
1340
1341 if( !l.SegmentCount() )
1342 {
1343 if( m_lastNode )
1344 {
1345 // Do a final optimization to the stored state
1346 NODE::ITEM_VECTOR removed, added;
1347 m_lastNode->GetUpdatedItems( removed, added );
1348
1349 if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1350 simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1351 }
1352
1353 // Nothing to commit if we have an empty line
1354 if( !pl.EndsWithVia() )
1355 return false;
1356
1359 if( m_lastNode )
1360 {
1361 m_lastNode->Add( Clone( pl.Via() ) );
1362 m_shove->AddLockedSpringbackNode( m_lastNode );
1363 }
1364
1365 m_currentNode = nullptr;
1366
1367 m_idle = true;
1368 m_placementCorrect = true;
1369 return true;
1370 }
1371
1372 VECTOR2I p_pre_last = l.CPoint( -1 );
1373 const VECTOR2I p_last = l.CPoint( -1 );
1374
1375 if( l.PointCount() > 2 )
1376 p_pre_last = l.CPoint( -2 );
1377
1378 if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1379 realEnd = true;
1380
1381 if( aForceFinish )
1382 realEnd = true;
1383
1384 // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1385 // so if we are, act as though we are in fix-all mode.
1386 if( !fixAll && l.ArcCount() )
1387 fixAll = true;
1388
1389 // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1390 SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1391 DIRECTION_45 d_last( lastDirSeg );
1392
1393 int lastV;
1394
1395 if( realEnd || m_placingVia || fixAll )
1396 lastV = l.SegmentCount();
1397 else
1398 lastV = std::max( 1, l.SegmentCount() - 1 );
1399
1400 ARC arc;
1401 SEGMENT seg;
1402 LINKED_ITEM* lastItem = nullptr;
1403 int lastArc = -1;
1404
1405 for( int i = 0; i < lastV; i++ )
1406 {
1407 ssize_t arcIndex = l.ArcIndex( i );
1408
1409 if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && !l.IsPtOnArc( lastV ) ) )
1410 {
1411 seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1412 seg.SetWidth( pl.Width() );
1413 seg.SetLayer( m_currentLayer );
1414
1415 std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1416 lastItem = sp.get();
1417
1418 if( !m_lastNode->Add( std::move( sp ) ) )
1419 lastItem = nullptr;
1420 }
1421 else
1422 {
1423 if( arcIndex == lastArc )
1424 continue;
1425
1426 arc = ARC( l.Arc( arcIndex ), m_currentNet );
1427 arc.SetWidth( pl.Width() );
1428 arc.SetLayer( m_currentLayer );
1429
1430 std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1431 lastItem = ap.get();
1432
1433 if( !m_lastNode->Add( std::move( ap ) ) )
1434 lastItem = nullptr;
1435
1436 lastArc = arcIndex;
1437 }
1438 }
1439
1440 if( pl.EndsWithVia() )
1441 m_lastNode->Add( Clone( pl.Via() ) );
1442
1443 if( realEnd && lastItem )
1444 simplifyNewLine( m_lastNode, lastItem );
1445
1446 if( !realEnd )
1447 {
1448 setInitialDirection( d_last );
1449 m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1450
1451 VECTOR2I ps;
1452 if( m_tail.SegmentCount() )
1453 ps = m_tail.CPoint( 0 );
1454 else
1455 ps = m_p_start;
1456
1458
1459 m_startItem = nullptr;
1460 m_placingVia = false;
1462
1465
1466 m_head.Line().Clear();
1467 m_tail.Line().Clear();
1468 m_head.RemoveVia();
1469 m_tail.RemoveVia();
1472
1473 m_shove->AddLockedSpringbackNode( m_currentNode );
1474
1475 DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1476
1481
1482 m_placementCorrect = true;
1483 }
1484 else
1485 {
1486 m_shove->AddLockedSpringbackNode( m_lastNode );
1487 m_placementCorrect = true;
1488 m_idle = true;
1489 }
1490
1491 return realEnd;
1492}
1493
1494
1496{
1498
1499 if ( !m_fixedTail.PopStage( st ) )
1500 return false;
1501
1502 m_head.Line().Clear();
1503 m_tail.Line().Clear();
1504 m_startItem = nullptr;
1505 m_p_start = st.pts[0].p;
1506 m_direction = st.pts[0].direction;
1507 m_placingVia = st.pts[0].placingVias;
1508 m_currentNode = st.commit;
1509 m_currentLayer = st.pts[0].layer;
1512 m_head.RemoveVia();
1513 m_tail.RemoveVia();
1514
1518
1519 m_shove->RewindSpringbackTo( m_currentNode );
1520 m_shove->UnlockSpringbackNode( m_currentNode );
1521
1522 if( Settings().Mode() == PNS::RM_Shove )
1523 {
1524 m_currentNode = m_shove->CurrentNode();
1526 }
1527
1529
1530 return true;
1531}
1532
1533
1535{
1537}
1538
1539
1541{
1542 if( Settings().Mode() == PNS::RM_Shove )
1543 {
1544 m_shove->RewindToLastLockedNode();
1545 m_lastNode = m_shove->CurrentNode();
1547 }
1548
1549 if( m_lastNode )
1551
1552 m_lastNode = nullptr;
1553 m_currentNode = nullptr;
1554 return true;
1555}
1556
1557
1558void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1559{
1560 if( !aLatest.SegmentCount() )
1561 return;
1562
1563 if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1564 return;
1565
1566 std::set<LINKED_ITEM *> toErase;
1567 aNode->Add( aLatest, true );
1568
1569 for( int s = 0; s < aLatest.LinkCount(); s++ )
1570 {
1571 LINKED_ITEM* seg = aLatest.GetLink(s);
1572 LINE ourLine = aNode->AssembleLine( seg );
1573 JOINT a, b;
1574 std::vector<LINE> lines;
1575
1576 aNode->FindLineEnds( ourLine, a, b );
1577
1578 if( a == b )
1579 aNode->FindLineEnds( aLatest, a, b );
1580
1581 aNode->FindLinesBetweenJoints( a, b, lines );
1582
1583 int removedCount = 0;
1584 int total = 0;
1585
1586 for( LINE& line : lines )
1587 {
1588 total++;
1589
1590 if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1591 {
1592 for( LINKED_ITEM* ss : line.Links() )
1593 toErase.insert( ss );
1594
1595 removedCount++;
1596 }
1597 }
1598
1599 wxLogTrace( wxT( "PNS" ), wxT( "total segs removed: %d/%d" ), removedCount, total );
1600 }
1601
1602 for( LINKED_ITEM* s : toErase )
1603 aNode->Remove( s );
1604
1605 aNode->Remove( aLatest );
1606}
1607
1608
1610{
1611 wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1612
1613 // Before we assemble the final line and run the optimizer, do a separate pass to clean up
1614 // colinear segments that exist on non-line-corner joints, as these will prevent proper assembly
1615 // of the line and won't get cleaned up by the optimizer.
1616 NODE::ITEM_VECTOR removed, added;
1617 aNode->GetUpdatedItems( removed, added );
1618
1619 std::set<ITEM*> cleanup;
1620
1621 auto processJoint =
1622 [&]( JOINT* aJoint, ITEM* aItem )
1623 {
1624 if( !aJoint || aJoint->IsLineCorner() )
1625 return;
1626
1627 SEG refSeg = static_cast<SEGMENT*>( aItem )->Seg();
1628
1629 NODE::ITEM_VECTOR toRemove;
1630
1631 for( ITEM* neighbor : aJoint->Links() )
1632 {
1633 if( neighbor == aItem
1634 || !neighbor->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T )
1635 || !neighbor->LayersOverlap( aItem ) )
1636 {
1637 continue;
1638 }
1639
1640 if( static_cast<SEGMENT*>( neighbor )->Width()
1641 != static_cast<SEGMENT*>( aItem )->Width() )
1642 {
1643 continue;
1644 }
1645
1646 const SEG& testSeg = static_cast<SEGMENT*>( neighbor )->Seg();
1647
1648 if( refSeg.Contains( testSeg ) )
1649 {
1650 JOINT* nA = aNode->FindJoint( neighbor->Anchor( 0 ), neighbor );
1651 JOINT* nB = aNode->FindJoint( neighbor->Anchor( 1 ), neighbor );
1652
1653 if( ( nA == aJoint && nB->LinkCount() == 1 ) ||
1654 ( nB == aJoint && nA->LinkCount() == 1 ) )
1655 {
1656 cleanup.insert( neighbor );
1657 }
1658 }
1659 }
1660 };
1661
1662 for( ITEM* item : added )
1663 {
1664 if( !item->OfKind( ITEM::SEGMENT_T ) || cleanup.count( item ) )
1665 continue;
1666
1667 JOINT* jA = aNode->FindJoint( item->Anchor( 0 ), item );
1668 JOINT* jB = aNode->FindJoint( item->Anchor( 1 ), item );
1669
1670 processJoint( jA, item );
1671 processJoint( jB, item );
1672 }
1673
1674 for( ITEM* seg : cleanup )
1675 aNode->Remove( seg );
1676
1677 // And now we can proceed with assembling the final line and optimizing it.
1678
1679 LINE l = aNode->AssembleLine( aLatest );
1680
1681 bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1682
1683 SHAPE_LINE_CHAIN simplified( l.CLine() );
1684
1685 simplified.Simplify();
1686
1687 if( optimized || simplified.PointCount() != l.PointCount() )
1688 {
1689 aNode->Remove( l );
1690 l.SetShape( simplified );
1691 aNode->Add( l );
1692 }
1693}
1694
1695
1697{
1698 m_sizes = aSizes;
1699
1700 if( !m_idle )
1701 {
1702 // If the track width continues from an existing track, we don't want to change the width.
1703 // Disallow changing width after the first segment has been fixed because we don't want to
1704 // go back and rip up tracks or allow DRC errors
1706 && ( !m_startItem || m_startItem->Kind() != ITEM::SEGMENT_T ) ) )
1707 {
1711 }
1712
1713 if( m_head.EndsWithVia() )
1714 {
1717 }
1718 }
1719}
1720
1721
1723{
1724 LINE current = Trace();
1725 SHAPE_LINE_CHAIN ratLine;
1726 TOPOLOGY topo( m_lastNode );
1727
1728 if( topo.LeadingRatLine( &current, ratLine ) )
1729 m_router->GetInterface()->DisplayRatline( ratLine, 5 );
1730}
1731
1732
1733void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1734{
1735 m_orthoMode = aOrthoMode;
1736}
1737
1738
1739bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aForceNoVia )
1740{
1742 DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
1743
1744 wxLogTrace( wxT( "PNS" ),
1745 wxT( "buildInitialLine: m_direction %s, guessedDir %s, tail points %d" ),
1746 m_direction.Format(), guessedDir.Format(), m_tail.PointCount() );
1747
1749 // Rounded corners don't make sense when routing orthogonally (single track at a time)
1750 if( m_orthoMode )
1751 cornerMode = DIRECTION_45::CORNER_MODE::MITERED_45;
1752
1753 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "pstart [buildInitial]" ) );
1754
1755
1756 if( m_p_start == aP )
1757 {
1758 l.Clear();
1759 }
1760 else
1761 {
1762 if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1763 {
1764 l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1765 }
1766 else
1767 {
1768 if( !m_tail.PointCount() )
1769 l = guessedDir.BuildInitialTrace( m_p_start, aP, false, cornerMode );
1770 else
1771 l = m_direction.BuildInitialTrace( m_p_start, aP, false, cornerMode );
1772 }
1773
1774 if( l.SegmentCount() > 1 && m_orthoMode )
1775 {
1776 VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1777
1778 l.Remove( -1, -1 );
1779 l.SetPoint( 1, newLast );
1780 }
1781 }
1782
1783 aHead.SetLayer( m_currentLayer );
1784 aHead.SetShape( l );
1785
1786 PNS_DBG( Dbg(), AddItem, &aHead, CYAN, 10000, wxT( "initial-trace" ) );
1787
1788
1789 if( !m_placingVia || aForceNoVia )
1790 return true;
1791
1792 VIA v( makeVia( aP ) );
1793 v.SetNet( aHead.Net() );
1794
1795 if( Settings().Mode() == RM_MarkObstacles )
1796 {
1797 aHead.AppendVia( v );
1798 return true;
1799 }
1800
1801 VECTOR2I force;
1802 VECTOR2I lead = aP - m_p_start;
1803
1804 bool solidsOnly = ( Settings().Mode() != RM_Walkaround );
1805
1806 if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1807 {
1808 SHAPE_LINE_CHAIN line =
1809 guessedDir.BuildInitialTrace( m_p_start, aP + force, false, cornerMode );
1810 aHead = LINE( aHead, line );
1811
1812 v.SetPos( v.Pos() + force );
1813 return true;
1814 }
1815
1816 return false; // via placement unsuccessful
1817}
1818
1819
1820void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1821{
1822 aNets.push_back( m_currentNet );
1823}
1824
1825
1827{
1829 return true;
1830}
1831
1832
1833FIXED_TAIL::FIXED_TAIL( int aLineCount )
1834{
1835
1836}
1837
1838
1840{
1841
1842}
1843
1844
1846{
1847 m_stages.clear();
1848}
1849
1850
1851void FIXED_TAIL::AddStage( const VECTOR2I& aStart, int aLayer, bool placingVias,
1852 DIRECTION_45 direction, NODE* aNode )
1853{
1854 STAGE st;
1855 FIX_POINT pt;
1856
1857 pt.p = aStart;
1858 pt.layer = aLayer;
1859 pt.direction = direction;
1860 pt.placingVias = placingVias;
1861
1862 st.pts.push_back(pt);
1863 st.commit = aNode;
1864
1865 m_stages.push_back( st );
1866}
1867
1868
1870{
1871 if( !m_stages.size() )
1872 return false;
1873
1874 aStage = m_stages.back();
1875
1876 if( m_stages.size() > 1 )
1877 m_stages.pop_back();
1878
1879 return true;
1880}
1881
1882
1884{
1885 return m_stages.size();
1886}
1887
1888}
1889
const char * name
Definition: DXF_plotter.cpp:56
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:37
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:181
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:78
Directions
Available directions, there are 8 of them, as on a rectilinear map (north = up) + an extra undefined ...
Definition: direction45.h:49
CORNER_MODE
Corner modes.
Definition: direction45.h:67
@ ROUNDED_45
H/V/45 with filleted corners.
Definition: direction45.h:69
@ MITERED_45
H/V/45 with mitered corners (default)
Definition: direction45.h:68
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:129
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:97
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
Definition: pns_algo_base.h:73
void SetLogger(LOGGER *aLogger)
Definition: pns_algo_base.h:65
virtual LOGGER * Logger()
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
ROUTER * m_router
Definition: pns_algo_base.h:87
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void SetWidth(int aWidth) override
Definition: pns_arc.h:82
FIXED_TAIL(int aLineCount=1)
int StageCount() const
bool PopStage(STAGE &aStage)
void AddStage(const VECTOR2I &aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
std::vector< STAGE > m_stages
Base class for PNS router board items.
Definition: pns_item.h:56
BOARD_ITEM * Parent() const
Definition: pns_item.h:151
void SetNet(int aNet)
Definition: pns_item.h:153
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:132
NODE * Owner() const
Return the owner of this item, or NULL if there's none.
Definition: pns_item.h:173
void SetLayer(int aLayer)
Definition: pns_item.h:159
@ SOLID_T
Definition: pns_item.h:63
@ SEGMENT_T
Definition: pns_item.h:66
const LAYER_RANGE & Layers() const
Definition: pns_item.h:156
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:140
int Net() const
Definition: pns_item.h:154
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
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:256
ITEM_SET & Links()
Definition: pns_joint.h:251
bool IsLineCorner(bool aAllowLockedSegs=false) const
Checks if a joint connects two segments of the same net, layer, and width.
Definition: pns_joint.h:103
bool mergeHead()
Moves "established" segments from the head to the tail if certain conditions are met.
bool handleSelfIntersections()
Check if the head of the track intersects its tail.
LINE_PLACER(ROUTER *aRouter)
bool SetLayer(int aLayer) override
Set the current routing layer.
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
bool route(const VECTOR2I &aP)
Re-route the current track to point aP.
bool AbortPlacement() override
std::unique_ptr< SHOVE > m_shove
The shove engine.
const LINE Trace() const
Return the complete routed line.
bool handlePullback()
Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direct...
void setWorld(NODE *aWorld)
Set the board to route.
void UpdateSizes(const SIZES_SETTINGS &aSizes) override
Perform on-the-fly update of the width, via diameter & drill size from a settings class.
bool reduceTail(const VECTOR2I &aEnd)
Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest ...
void SetOrthoMode(bool aOrthoMode) override
Function SetOrthoMode()
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
MOUSE_TRAIL_TRACER m_mouseTrailTracer
LINE m_last_head
Most recent successful (non-colliding) head.
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).
bool optimizeTailHeadTransition()
Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segme...
bool HasPlacedAnything() const override
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead)
void routeStep(const VECTOR2I &aP)
Perform a single routing algorithm step, for the end point aP.
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aForceNoVia=false)
NODE * m_currentNode
Current world state.
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
void removeLoops(NODE *aNode, LINE &aLatest)
Searches aNode for traces concurrent to aLatest and removes them.
bool routeHead(const VECTOR2I &aP, LINE &aNewHead)
Compute the head trace between the current start point (m_p_start) and point aP, starting with direct...
NODE * m_world
pointer to world to search colliding items
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step shove mode.
DIRECTION_45 m_initial_direction
routing direction for new traces
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
SIZES_SETTINGS m_sizes
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Check if point aP lies on segment aSeg.
void setInitialDirection(const DIRECTION_45 &aDirection)
Set preferred direction of the very first track segment to be laid.
void updateLeadingRatLine()
Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest y...
bool UnfixRoute() override
void FlipPosture() override
Toggle the current posture (straight/diagonal) of the trace head.
const VIA makeVia(const VECTOR2I &aP)
void GetModifiedNets(std::vector< int > &aNets) const override
Function GetModifiedNets.
bool CommitPlacement() override
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Move the end of the currently routed trace to the point aP, taking aEndItem as anchor (if not NULL).
void simplifyNewLine(NODE *aNode, LINKED_ITEM *aLatest)
Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertic...
DIRECTION_45 m_direction
current routing direction
void initPlacement()
Initialize placement of a new line with given parameters.
FIXED_TAIL m_fixedTail
const ITEM_SET Traces() override
Return the complete routed line, as a single-member ITEM_SET.
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish) override
Commit the currently routed track to the parent node taking aP as the final end point and aEndItem as...
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step mark obstacles mode.
bool ToggleVia(bool aEnabled) override
Enable/disable a via at the end of currently routed trace.
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
void SetViaDrill(int aDrill)
Definition: pns_line.h:197
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
void RemoveVia()
Definition: pns_line.h:192
int CountCorners(int aAngles) const
Definition: pns_line.cpp:135
bool HasLoops() const
Definition: pns_line.cpp:1107
const VIA & Via() const
Definition: pns_line.h:194
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
void Clear()
Definition: pns_line.cpp:1227
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
Definition: pns_line.cpp:536
int SegmentCount() const
Definition: pns_line.h:139
void SetViaDiameter(int aDiameter)
Definition: pns_line.h:196
int PointCount() const
Definition: pns_line.h:140
int ShapeCount() const
Return the aIdx-th point of the line.
Definition: pns_line.h:142
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:1016
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:149
void SetBlockingObstacle(ITEM *aObstacle)
Definition: pns_line.h:203
bool EndsWithVia() const
Definition: pns_line.h:189
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:146
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
void SetMouseDisabled(bool aDisabled=true)
Disables the mouse-trail portion of the posture solver; leaving only the manual posture switch and th...
void AddTrailPoint(const VECTOR2I &aP)
DIRECTION_45 GetPosture(const VECTOR2I &aP)
Keep the router "world" - i.e.
Definition: pns_node.h:155
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:139
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
Definition: pns_node.cpp:1076
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:166
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:103
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1384
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:468
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:165
int Depth() const
Definition: pns_node.h:208
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1069
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:656
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr, bool aUseClearanceEpsilon=true)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:301
void KillChildren()
Definition: pns_node.cpp:1451
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1181
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:873
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:983
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:95
void SetWorld(NODE *aNode)
void SetCollisionMask(int aMask)
void SetEffortLevel(int aEffort)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
@ SMART_PADS
Reroute pad exits.
@ FANOUT_CLEANUP
Simplify pad-pad and pad-via connections if possible.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
@ MERGE_COLINEAR
Merge co-linear segments.
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
virtual void DisplayRatline(const SHAPE_LINE_CHAIN &aRatline, int aColor=-1)=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:210
void CommitRouting()
Definition: pns_router.cpp:840
NODE * GetWorld() const
Definition: pns_router.h:156
double WalkaroundHugLengthThreshold() const
PNS_MODE Mode() const
Set the routing mode.
DIRECTION_45::CORNER_MODE GetCornerMode() const
const SEG & Seg() const
Definition: pns_segment.h:84
int Width() const override
Definition: pns_segment.h:79
void SetWidth(int aWidth) override
Definition: pns_segment.h:74
@ SH_HEAD_MODIFIED
Definition: pns_shove.h:54
VIATYPE ViaType() const
bool TrackWidthIsExplicit() const
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
const VECTOR2I & Pos() const
Definition: pns_via.h:100
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:102
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, bool aSolidsOnly=true, int aMaxIterations=10)
Definition: pns_via.cpp:65
void SetIterationLimit(const int aIterLimit)
void SetSolidsOnly(bool aSolidsOnly)
void SetWorld(NODE *aNode)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I::extended_type ecoord
Definition: seg.h:44
VECTOR2I B
Definition: seg.h:50
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:261
int Length() const
Return the length (this).
Definition: seg.h:351
bool Contains(const SEG &aSeg) const
Definition: seg.h:332
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:302
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:381
const VECTOR2I & GetP0() const
Definition: shape_arc.h:112
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsPtOnArc(size_t aPtIndex) const
const SHAPE_ARC & Arc(size_t aArc) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
int PrevShape(int aPointIndex) const
int ShapeCount() const
Return the number of shapes (line segments or arcs) in this line chain.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Clear()
Remove all points from the line chain.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
const std::vector< SHAPE_ARC > & CArcs() const
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] 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
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
@ LIGHTGREEN
Definition: color4d.h:63
@ WHITE
Definition: color4d.h:48
@ BLUE
Definition: color4d.h:56
@ MAGENTA
Definition: color4d.h:60
@ GREEN
Definition: color4d.h:57
@ CYAN
Definition: color4d.h:58
@ LIGHTCYAN
Definition: color4d.h:64
@ YELLOW
Definition: color4d.h:67
@ B_Cu
Definition: layer_ids.h:95
@ F_Cu
Definition: layer_ids.h:64
Push and Shove diff pair dimensions (gap) settings dialog.
@ RM_MarkObstacles
Ignore collisions, mark obstacles.
@ RM_Walkaround
Only walk around.
@ RM_Shove
Only shove.
static bool cursorDistMinimum(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aCursor, double lengthThreshold, int &theDist, VECTOR2I &aNearest)
VECTOR2I closestProjectedPoint(const SHAPE_LINE_CHAIN &line, const VECTOR2I &p)
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:277
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
std::vector< FIX_POINT > pts
WALKAROUND_STATUS statusCcw
WALKAROUND_STATUS statusCw
Represent an intersection between two line segments.
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618