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 <tomasz.wlostowski@cern.ch>
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 <core/optional.h>
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"
34 #include "pns_mouse_trail_tracer.h"
35 
36 namespace PNS {
37 
39  PLACEMENT_ALGO( aRouter )
40 {
42  m_world = nullptr;
43  m_shove = nullptr;
44  m_currentNode = nullptr;
45  m_idle = true;
46 
47  // Init temporary variables (do not leave uninitialized members)
48  m_lastNode = nullptr;
49  m_placingVia = false;
50  m_currentNet = 0;
51  m_currentLayer = 0;
53  m_startItem = nullptr;
54  m_chainedPlacement = false;
55  m_orthoMode = false;
56  m_placementCorrect = false;
57 }
58 
59 
61 {
62 }
63 
64 
65 void LINE_PLACER::setWorld( NODE* aWorld )
66 {
67  m_world = aWorld;
68 }
69 
70 
71 const VIA LINE_PLACER::makeVia( const VECTOR2I& aP )
72 {
75 
76  return VIA( aP, layers, m_sizes.ViaDiameter(), m_sizes.ViaDrill(), -1, m_sizes.ViaType() );
77 }
78 
79 
80 bool LINE_PLACER::ToggleVia( bool aEnabled )
81 {
82  m_placingVia = aEnabled;
83 
84  if( !aEnabled )
85  m_head.RemoveVia();
86 
87  return true;
88 }
89 
90 
92 {
93  m_initial_direction = aDirection;
94 
95  if( m_tail.SegmentCount() == 0 )
96  m_direction = aDirection;
97 }
98 
99 
101 {
103  SHAPE_LINE_CHAIN& head = m_head.Line();
104  SHAPE_LINE_CHAIN& tail = m_tail.Line();
105 
106  // if there is no tail, there is nothing to intersect with
107  if( tail.PointCount() < 2 )
108  return false;
109 
110  if( head.PointCount() < 2 )
111  return false;
112 
113  // completely new head trace? chop off the tail
114  if( tail.CPoint(0) == head.CPoint(0) )
115  {
116  m_p_start = tail.CPoint( 0 );
118  tail.Clear();
119  return true;
120  }
121 
122  tail.Intersect( head, ips );
123 
124  // no intesection points - nothing to reduce
125  if( ips.empty() )
126  return false;
127 
128  int n = INT_MAX;
129  VECTOR2I ipoint;
130 
131  // if there is more than one intersection, find the one that is
132  // closest to the beginning of the tail.
133  for( const SHAPE_LINE_CHAIN::INTERSECTION& i : ips )
134  {
135  if( i.our.Index() < n )
136  {
137  n = i.our.Index();
138  ipoint = i.p;
139  }
140  }
141 
142  // ignore the point where head and tail meet
143  if( ipoint == head.CPoint( 0 ) || ipoint == tail.CPoint( -1 ) )
144  return false;
145 
146  // Intersection point is on the first or the second segment: just start routing
147  // from the beginning
148  if( n < 2 )
149  {
150  m_p_start = tail.CPoint( 0 );
152  tail.Clear();
153  head.Clear();
154 
155  return true;
156  }
157  else
158  {
159  // Clip till the last tail segment before intersection.
160  // Set the direction to the one of this segment.
161  const SEG last = tail.CSegment( n - 1 );
162  m_p_start = last.A;
163  m_direction = DIRECTION_45( last );
164  tail.Remove( n, -1 );
165  return true;
166  }
167 
168  return false;
169 }
170 
171 
173 {
174  SHAPE_LINE_CHAIN& head = m_head.Line();
175  SHAPE_LINE_CHAIN& tail = m_tail.Line();
176 
177  if( head.PointCount() < 2 )
178  return false;
179 
180  int n = tail.PointCount();
181 
182  if( n == 0 )
183  {
184  return false;
185  }
186  else if( n == 1 )
187  {
188  m_p_start = tail.CPoint( 0 );
189  tail.Clear();
190  return true;
191  }
192 
193  DIRECTION_45 first_head, last_tail;
194 
195  const std::vector<ssize_t>& headShapes = head.CShapes();
196  const std::vector<ssize_t>& tailShapes = tail.CShapes();
197 
198  wxASSERT( tail.PointCount() >= 2 );
199 
200  if( headShapes[0] == -1 )
201  first_head = DIRECTION_45( head.CSegment( 0 ) );
202  else
203  first_head = DIRECTION_45( head.CArcs()[ headShapes[0] ] );
204 
205  int lastSegIdx = tail.PointCount() - 2;
206 
207  if( tailShapes[lastSegIdx] == -1 )
208  last_tail = DIRECTION_45( tail.CSegment( lastSegIdx ) );
209  else
210  last_tail = DIRECTION_45( tail.CArcs()[tailShapes[lastSegIdx]] );
211 
212  DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
213 
214  // case 1: we have a defined routing direction, and the currently computed
215  // head goes in different one.
216  bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
217 
218  // case 2: regardless of the current routing direction, if the tail/head
219  // extremities form an acute or right angle, reduce the tail by one segment
220  // (and hope that further iterations) will result with a cleaner trace
221  bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
222 
223  if( pullback_1 || pullback_2 )
224  {
225  lastSegIdx = tail.PrevShape( -1 );
226 
227  if( tailShapes[lastSegIdx] == -1 )
228  {
229  const SEG& seg = tail.CSegment( lastSegIdx );
230  m_direction = DIRECTION_45( seg );
231  m_p_start = seg.A;
232  }
233  else
234  {
235  const SHAPE_ARC& arc = tail.CArcs()[tailShapes[lastSegIdx]];
236  m_direction = DIRECTION_45( arc );
237  m_p_start = arc.GetP0();
238  }
239 
240  wxLogTrace( "PNS", "Placer: pullback triggered [%d] [%s %s]",
241  n, last_tail.Format().c_str(), first_head.Format().c_str() );
242 
243  // erase the last point in the tail, hoping that the next iteration will
244  // result with a head trace that starts with a segment following our
245  // current direction.
246  if( n < 2 )
247  tail.Clear(); // don't leave a single-point tail
248  else
249  tail.RemoveShape( -1 );
250 
251  if( !tail.SegmentCount() )
253 
254  return true;
255  }
256 
257  return false;
258 }
259 
260 
262 {
263  SHAPE_LINE_CHAIN& head = m_head.Line();
264  SHAPE_LINE_CHAIN& tail = m_tail.Line();
265 
266  int n = tail.SegmentCount();
267 
268  if( head.SegmentCount() < 1 )
269  return false;
270 
271  // Don't attempt this for too short tails
272  if( n < 2 )
273  return false;
274 
275  // Start from the segment farthest from the end of the tail
276  // int start_index = std::max(n - 1 - ReductionDepth, 0);
277 
278  DIRECTION_45 new_direction;
279  VECTOR2I new_start;
280  int reduce_index = -1;
281 
282  for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
283  {
284  const SEG s = tail.CSegment( i );
285  DIRECTION_45 dir( s );
286 
287  // calculate a replacement route and check if it matches
288  // the direction of the segment to be replaced
289  SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
290 
291  if( replacement.SegmentCount() < 1 )
292  continue;
293 
294  LINE tmp( m_tail, replacement );
295 
297  break;
298 
299  if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
300  {
301  new_start = s.A;
302  new_direction = dir;
303  reduce_index = i;
304  }
305  }
306 
307  if( reduce_index >= 0 )
308  {
309  wxLogTrace( "PNS", "Placer: reducing tail: %d", reduce_index );
310  SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
311 
312  m_p_start = new_start;
313  m_direction = new_direction;
314  tail.Remove( reduce_index + 1, -1 );
315  head.Clear();
316  return true;
317  }
318 
319  if( !tail.SegmentCount() )
321 
322  return false;
323 }
324 
325 
327 {
328  SHAPE_LINE_CHAIN& head = m_head.Line();
329  SHAPE_LINE_CHAIN& tail = m_tail.Line();
330 
331  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE
334 
335  head.Simplify();
336  tail.Simplify();
337 
338  int n_head = head.ShapeCount();
339  int n_tail = tail.ShapeCount();
340 
341  if( n_head < 3 )
342  {
343  wxLogTrace( "PNS", "Merge failed: not enough head segs." );
344  return false;
345  }
346 
347  if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
348  {
349  wxLogTrace( "PNS", "Merge failed: head and tail discontinuous." );
350  return false;
351  }
352 
353  if( m_head.CountCorners( ForbiddenAngles ) != 0 )
354  return false;
355 
356  DIRECTION_45 dir_tail, dir_head;
357 
358  const std::vector<ssize_t>& headShapes = head.CShapes();
359  const std::vector<ssize_t>& tailShapes = tail.CShapes();
360 
361  if( headShapes[0] == -1 )
362  dir_head = DIRECTION_45( head.CSegment( 0 ) );
363  else
364  dir_head = DIRECTION_45( head.CArcs()[ headShapes[0] ] );
365 
366  if( n_tail )
367  {
368  wxASSERT( tail.PointCount() >= 2 );
369  int lastSegIdx = tail.PointCount() - 2;
370 
371  if( tailShapes[lastSegIdx] == -1 )
372  dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
373  else
374  dir_tail = DIRECTION_45( tail.CArcs()[ tailShapes[lastSegIdx] ] );
375 
376  if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
377  return false;
378  }
379 
380  tail.Append( head );
381 
382  tail.Simplify();
383 
384  SEG last = tail.CSegment( -1 );
385  m_p_start = last.B;
386 
387  int lastSegIdx = tail.PointCount() - 2;
388 
389  if( tailShapes[lastSegIdx] == -1 )
390  m_direction = DIRECTION_45( tail.CSegment( -1 ) );
391  else
392  m_direction = DIRECTION_45( tail.CArcs()[ tailShapes[lastSegIdx] ] );
393 
394  head.Remove( 0, -1 );
395 
396  wxLogTrace( "PNS", "Placer: merge %d, new direction: %s", n_head,
397  m_direction.Format().c_str() );
398 
399  head.Simplify();
400  tail.Simplify();
401 
402  return true;
403 }
404 
405 
407 {
408  // Keep distances squared for performance
409  SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
410  VECTOR2I closest;
411 
412  for( int i = 0; i < line.SegmentCount(); i++ )
413  {
414  const SEG& s = line.CSegment( i );
415  VECTOR2I a = s.NearestPoint( p );
416  int d_sq = (a - p).SquaredEuclideanNorm();
417 
418  if( d_sq < min_dist_sq )
419  {
420  min_dist_sq = d_sq;
421  closest = a;
422  }
423  }
424 
425  return closest;
426 }
427 
428 
429 bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
430 {
431  LINE initTrack( m_head );
432  LINE walkFull( m_head );
433  int effort = 0;
434  bool rv = true, viaOk;
435 
436  viaOk = buildInitialLine( aP, initTrack );
437 
438  WALKAROUND walkaround( m_currentNode, Router() );
439 
440  walkaround.SetSolidsOnly( false );
441  walkaround.SetDebugDecorator( Dbg() );
442  walkaround.SetLogger( Logger() );
443  walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
444 
445  WALKAROUND::RESULT wr = walkaround.Route( initTrack );
446  //WALKAROUND::WALKAROUND_STATUS wf = walkaround.Route( initTrack, walkFull, false );
447 
448  SHAPE_LINE_CHAIN l_cw = wr.lineCw.CLine();
449  SHAPE_LINE_CHAIN l_ccw = wr.lineCcw.CLine();
450 
452  {
453 
454  VECTOR2I p_cw = closestProjectedPoint( l_cw, aP );
455  VECTOR2I p_ccw = closestProjectedPoint( l_ccw, aP );
456 
457  int idx_cw = l_cw.Split( p_cw );
458  int idx_ccw = l_ccw.Split( p_ccw );
459 
460  l_cw = l_cw.Slice( 0, idx_cw );
461  l_ccw = l_ccw.Slice( 0, idx_ccw );
462 
463  //Dbg()->AddLine( wr.lineCw.CLine(), 3, 40000 );
464 
465  //Dbg()->AddPoint( p_cw, 4 );
466  //Dbg()->AddPoint( p_ccw, 5 );
467 
468  Dbg()->AddLine( wr.lineCw.CLine(), 4, 1000 );
469  Dbg()->AddLine( wr.lineCcw.CLine(), 5, 1000 );
470 
471  }
472 
473  walkFull.SetShape( l_ccw.Length() < l_cw.Length() ? l_ccw : l_cw );
474 
475  Dbg()->AddLine( walkFull.CLine(), 2, 100000, "walk-full" );
476 
477  switch( Settings().OptimizerEffort() )
478  {
479  case OE_LOW:
480  effort = 0;
481  break;
482 
483  case OE_MEDIUM:
484  case OE_FULL:
485  effort = OPTIMIZER::MERGE_SEGMENTS;
486  break;
487  }
488 
490  effort |= OPTIMIZER::SMART_PADS;
491 
493  {
494  walkFull = walkFull.ClipToNearestObstacle( m_currentNode );
495  rv = true;
496  }
497  else if( m_placingVia && viaOk )
498  {
499  walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
500  }
501 
502  OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
503 
504  if( m_currentNode->CheckColliding( &walkFull ) )
505  {
506  aNewHead = m_head;
507  return false;
508  }
509 
510  m_head = walkFull;
511  aNewHead = walkFull;
512 
513  return rv;
514 }
515 
516 
517 bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead )
518 {
519  buildInitialLine( aP, m_head );
520  m_head.SetBlockingObstacle( nullptr );
521 
522  // If we are enforcing DRC violations, push back to the hull
523  if( !Settings().CanViolateDRC() )
524  {
526 
527  if( obs && obs->m_distFirst != INT_MAX )
528  {
529  buildInitialLine( obs->m_ipFirst, m_head );
530  m_head.SetBlockingObstacle( obs->m_item );
531  }
532  }
533 
534  aNewHead = m_head;
535 
536  return static_cast<bool>( m_currentNode->CheckColliding( &m_head ) );
537 }
538 
539 
540 bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
541 {
542  LINE initTrack( m_head );
543  LINE walkSolids, l2;
544 
545  bool viaOk = buildInitialLine( aP, initTrack );
546 
547  m_currentNode = m_shove->CurrentNode();
548 
549  m_shove->SetLogger( Logger() );
550  m_shove->SetDebugDecorator( Dbg() );
551 
552  OPTIMIZER optimizer( m_currentNode );
553 
554  WALKAROUND walkaround( m_currentNode, Router() );
555 
556  walkaround.SetSolidsOnly( true );
557  walkaround.SetIterationLimit( 10 );
558  walkaround.SetDebugDecorator( Dbg() );
559  walkaround.SetLogger( Logger() );
560  WALKAROUND::WALKAROUND_STATUS stat_solids = walkaround.Route( initTrack, walkSolids );
561 
563  optimizer.SetCollisionMask( ITEM::SOLID_T );
564  optimizer.Optimize( &walkSolids );
565 
566  if( stat_solids == WALKAROUND::DONE )
567  l2 = walkSolids;
568  else
569  l2 = initTrack.ClipToNearestObstacle( m_shove->CurrentNode() );
570 
571  LINE l( m_tail );
572  l.Line().Append( l2.CLine() );
573  l.Line().Simplify();
574 
575  if( l.PointCount() == 0 || l2.PointCount() == 0 )
576  {
577  aNewHead = m_head;
578  return false;
579  }
580 
581  if( m_placingVia && viaOk )
582  {
583  VIA v1( makeVia( l.CPoint( -1 ) ) );
584  VIA v2( makeVia( l2.CPoint( -1 ) ) );
585 
586  l.AppendVia( v1 );
587  l2.AppendVia( v2 );
588  }
589 
590  l.Line().Simplify();
591 
592  // in certain, uncommon cases there may be loops in the head+tail, In such case, we don't
593  // shove to avoid screwing up the database.
594  if( l.HasLoops() )
595  {
596  aNewHead = m_head;
597  return false;
598  }
599 
600  SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
601 
602  m_currentNode = m_shove->CurrentNode();
603 
604  if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
605  {
606  if( status == SHOVE::SH_HEAD_MODIFIED )
607  l2 = m_shove->NewHead();
608 
609  optimizer.SetWorld( m_currentNode );
610 
611  int effortLevel = OPTIMIZER::MERGE_OBTUSE;
612 
613  if( Settings().SmartPads() && !m_mouseTrailTracer.IsManuallyForced() )
614  effortLevel = OPTIMIZER::SMART_PADS;
615 
616  optimizer.SetEffortLevel( effortLevel );
617 
618  optimizer.SetCollisionMask( ITEM::ANY_T );
619  optimizer.Optimize( &l2 );
620 
621  aNewHead = l2;
622 
623  return true;
624  }
625  else
626  {
627  walkaround.SetWorld( m_currentNode );
628  walkaround.SetSolidsOnly( false );
629  walkaround.SetIterationLimit( 10 );
630  walkaround.SetApproachCursor( true, aP );
631  walkaround.Route( initTrack, l2 );
632  aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
633 
634  return false;
635  }
636 
637  return false;
638 }
639 
640 
641 bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead )
642 {
643  switch( m_currentMode )
644  {
645  case RM_MarkObstacles:
646  return rhMarkObstacles( aP, aNewHead );
647  case RM_Walkaround:
648  return rhWalkOnly( aP, aNewHead );
649  case RM_Shove:
650  return rhShoveOnly( aP, aNewHead );
651  default:
652  break;
653  }
654 
655  return false;
656 }
657 
658 
660 {
661  LINE linetmp = Trace();
662 
664  {
665  if( linetmp.SegmentCount() < 1 )
666  return false;
667 
668  m_head = linetmp;
669  m_p_start = linetmp.CLine().CPoint( 0 );
670  m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
671  m_tail.Line().Clear();
672 
673  return true;
674  }
675 
676  SHAPE_LINE_CHAIN& head = m_head.Line();
677  SHAPE_LINE_CHAIN& tail = m_tail.Line();
678 
679  int tailLookbackSegments = 3;
680 
681  //if(m_currentMode() == RM_Walkaround)
682  // tailLookbackSegments = 10000;
683 
684  int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
685 
686  if( tail.ShapeCount() < 3 )
687  return false;
688 
689  // assemble TailLookbackSegments tail segments with the current head
690  SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
691 
692  int end = std::min(2, head.PointCount() - 1 );
693 
694  opt_line.Append( head.Slice( 0, end ) );
695 
696  LINE new_head( m_tail, opt_line );
697 
698  // and see if it could be made simpler by merging obtuse/collnear segments.
699  // If so, replace the (threshold) last tail points and the head with
700  // the optimized line
701 
703  {
704  LINE tmp( m_tail, opt_line );
705 
706  wxLogTrace( "PNS", "Placer: optimize tail-head [%d]", threshold );
707 
708  head.Clear();
709  tail.Replace( -threshold, -1, new_head.CLine() );
710  tail.Simplify();
711 
712  m_p_start = new_head.CLine().CPoint( -1 );
713  m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
714 
715  return true;
716  }
717 
718  return false;
719 }
720 
721 
723 {
724  bool fail = false;
725  bool go_back = false;
726 
727  int i, n_iter = 1;
728 
729  LINE new_head;
730 
731  wxLogTrace( "PNS", "routeStep: direction: %s head: %d, tail: %d shapes",
732  m_direction.Format().c_str(),
733  m_head.ShapeCount(),
734  m_tail.ShapeCount() );
735 
736  for( i = 0; i < n_iter; i++ )
737  {
738  if( !go_back && Settings().FollowMouse() )
739  reduceTail( aP );
740 
741  go_back = false;
742 
743  if( !routeHead( aP, new_head ) )
744  fail = true;
745 
746  if( !new_head.Is45Degree() )
747  fail = true;
748 
749  if( !Settings().FollowMouse() )
750  return;
751 
752  m_head = new_head;
753 
755  {
756  n_iter++;
757  go_back = true;
758  }
759 
760  if( !go_back && handlePullback() )
761  {
762  n_iter++;
763  go_back = true;
764  }
765  }
766 
767  if( !fail )
768  {
770  return;
771 
772  mergeHead();
773  }
774 }
775 
776 
777 bool LINE_PLACER::route( const VECTOR2I& aP )
778 {
779  routeStep( aP );
780 
781  if (!m_head.PointCount() )
782  return false;
783 
784  return m_head.CPoint(-1) == aP;
785 }
786 
787 
789 {
790  LINE tmp( m_head );
791 
792  tmp.SetShape( m_tail.CLine() );
793  tmp.Line().Append( m_head.CLine() );
794  tmp.Line().Simplify();
795  return tmp;
796 }
797 
798 
800 {
801  m_currentTrace = Trace();
802  return ITEM_SET( &m_currentTrace );
803 }
804 
805 
807 {
809 }
810 
811 
812 NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
813 {
814  if( aLoopsRemoved && m_lastNode )
815  return m_lastNode;
816 
817  return m_currentNode;
818 }
819 
820 
821 bool LINE_PLACER::SplitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP )
822 {
823  if( !aSeg )
824  return false;
825 
826  if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
827  return false;
828 
829  JOINT* jt = aNode->FindJoint( aP, aSeg );
830 
831  if( jt && jt->LinkCount() >= 1 )
832  return false;
833 
834  SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
835 
836  std::unique_ptr<SEGMENT> s_new[2] = { Clone( *s_old ), Clone( *s_old ) };
837 
838  s_new[0]->SetEnds( s_old->Seg().A, aP );
839  s_new[1]->SetEnds( aP, s_old->Seg().B );
840 
841  aNode->Remove( s_old );
842  aNode->Add( std::move( s_new[0] ), true );
843  aNode->Add( std::move( s_new[1] ), true );
844 
845  return true;
846 }
847 
848 
849 bool LINE_PLACER::SetLayer( int aLayer )
850 {
851  if( m_idle )
852  {
853  m_currentLayer = aLayer;
854  return true;
855  }
856  else if( m_chainedPlacement )
857  {
858  return false;
859  }
860  else if( !m_startItem
861  || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) )
862  || ( m_startItem->OfKind( ITEM::SOLID_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
863  {
864  m_currentLayer = aLayer;
865  m_head.Line().Clear();
866  m_tail.Line().Clear();
869  Move( m_currentEnd, nullptr );
870  return true;
871  }
872 
873  return false;
874 }
875 
876 
877 bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
878 {
879  m_placementCorrect = false;
880  m_currentStart = VECTOR2I( aP );
881  m_currentEnd = VECTOR2I( aP );
882  m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
883  m_startItem = aStartItem;
884  m_placingVia = false;
885  m_chainedPlacement = false;
886  m_fixedTail.Clear();
887 
888  setInitialDirection( Settings().InitialDirection() );
889 
890  initPlacement();
891 
892  DIRECTION_45 initialDir = m_initial_direction;
894 
895  if( aStartItem && aStartItem->Kind() == ITEM::SEGMENT_T )
896  {
897  // If we land on a segment endpoint, assume the starting direction is continuing along
898  // the same direction as the endpoint. If we started in the middle, don't set a
899  // direction so that the posture solver is not biased.
900  SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
901 
902  if( aP == seg.A )
903  lastSegDir = DIRECTION_45( seg.Reversed() );
904  else if( aP == seg.B )
905  lastSegDir = DIRECTION_45( seg );
906  }
907  else if( aStartItem && aStartItem->Kind() == ITEM::SOLID_T &&
908  static_cast<SOLID*>( aStartItem )->Parent()->Type() == PCB_PAD_T )
909  {
910  double angle = static_cast<SOLID*>( aStartItem )->GetOrientation() / 10.0;
911  angle = ( angle + 22.5 ) / 45.0;
912  initialDir = DIRECTION_45( static_cast<DIRECTION_45::Directions>( int( angle ) ) );
913  }
914 
915  wxLogTrace( "PNS", "Posture: init %s, last seg %s", initialDir.Format(), lastSegDir.Format() );
916 
921  m_mouseTrailTracer.SetMouseDisabled( !Settings().GetAutoPosture() );
922 
923  NODE *n;
924 
925  if ( m_shove )
926  n = m_shove->CurrentNode();
927  else
928  n = m_currentNode;
929 
931 
932  return true;
933 }
934 
935 
937 {
938  m_idle = false;
939 
940  m_head.Line().Clear();
941  m_tail.Line().Clear();
948  m_head.RemoveVia();
949  m_tail.RemoveVia();
950 
953 
954  NODE* world = Router()->GetWorld();
955 
956  world->KillChildren();
957  NODE* rootNode = world->Branch();
958 
960 
961  setWorld( rootNode );
962 
963  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
964  m_world,
965  m_direction.Format().c_str(),
966  m_currentLayer );
967 
968  m_lastNode = nullptr;
971 
972  m_shove.reset();
973 
975  m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
976 }
977 
978 
979 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
980 {
981  LINE current;
982  VECTOR2I p = aP;
983  int eiDepth = -1;
984 
985  if( aEndItem && aEndItem->Owner() )
986  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
987 
988  if( m_lastNode )
989  {
990  delete m_lastNode;
991  m_lastNode = nullptr;
992  }
993 
994  bool reachesEnd = route( p );
995 
996  current = Trace();
997 
998  if( !current.PointCount() )
1000  else
1001  m_currentEnd = current.CLine().CPoint( -1 );
1002 
1003  NODE* latestNode = m_currentNode;
1004  m_lastNode = latestNode->Branch();
1005 
1006  if( reachesEnd
1007  && eiDepth >= 0
1008  && aEndItem && latestNode->Depth() > eiDepth
1009  && current.SegmentCount() )
1010  {
1011  SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1012 
1013  if( Settings().RemoveLoops() )
1014  removeLoops( m_lastNode, current );
1015  }
1016 
1019  return true;
1020 }
1021 
1022 
1023 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1024 {
1025  bool fixAll = Settings().GetFixAllSegments();
1026  bool realEnd = false;
1027 
1028  LINE pl = Trace();
1029 
1031  {
1032  // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1033  // user has more responsibility and authority.
1034 
1035  if( aEndItem )
1036  {
1037  // The user has indicated a connection should be made. If either the trace or
1038  // endItem is net-less, then allow the connection by adopting the net of the other.
1039  if( m_currentNet <= 0 )
1040  {
1041  m_currentNet = aEndItem->Net();
1042  pl.SetNet( m_currentNet );
1043  }
1044  else if (aEndItem->Net() <= 0 )
1045  {
1046  aEndItem->SetNet( m_currentNet );
1047  }
1048  }
1049 
1050  // Collisions still prevent fixing unless "Allow DRC violations" is checked
1051  if( !Settings().CanViolateDRC() && m_world->CheckColliding( &pl ) )
1052  return false;
1053  }
1054 
1055  const SHAPE_LINE_CHAIN& l = pl.CLine();
1056 
1057  if( !l.SegmentCount() )
1058  {
1059  if( m_lastNode )
1060  {
1061  // Do a final optimization to the stored state
1062  NODE::ITEM_VECTOR removed, added;
1063  m_lastNode->GetUpdatedItems( removed, added );
1064 
1065  if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1066  simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1067  }
1068 
1069  // Nothing to commit if we have an empty line
1070  if( !pl.EndsWithVia() )
1071  return false;
1072 
1075  if( m_lastNode )
1076  m_lastNode->Add( Clone( pl.Via() ) );
1077 
1078  m_currentNode = nullptr;
1079 
1080  m_idle = true;
1081  m_placementCorrect = true;
1082  return true;
1083  }
1084 
1085  VECTOR2I p_pre_last = l.CPoint( -1 );
1086  const VECTOR2I p_last = l.CPoint( -1 );
1087 
1088  if( l.PointCount() > 2 )
1089  p_pre_last = l.CPoint( -2 );
1090 
1091  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1092  realEnd = true;
1093 
1094  if( aForceFinish )
1095  realEnd = true;
1096 
1097  // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1098  // so if we are, act as though we are in fix-all mode.
1099  if( !fixAll && l.ArcCount() )
1100  fixAll = true;
1101 
1102  // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1103  SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1104  DIRECTION_45 d_last( lastDirSeg );
1105 
1106  int lastV;
1107 
1108  if( realEnd || m_placingVia || fixAll )
1109  lastV = l.SegmentCount();
1110  else
1111  lastV = std::max( 1, l.SegmentCount() - 1 );
1112 
1113  ARC arc;
1114  SEGMENT seg;
1115  LINKED_ITEM* lastItem = nullptr;
1116  int lastArc = -1;
1117 
1118  for( int i = 0; i < lastV; i++ )
1119  {
1120  ssize_t arcIndex = l.ArcIndex( i );
1121 
1122  if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && l.CShapes()[lastV] == -1 ) )
1123  {
1124  seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1125  seg.SetWidth( pl.Width() );
1126  seg.SetLayer( m_currentLayer );
1127 
1128  if( m_lastNode->Add( std::make_unique<SEGMENT>( seg ) ) )
1129  lastItem = &seg;
1130  }
1131  else
1132  {
1133  if( arcIndex == lastArc )
1134  continue;
1135 
1136  arc = ARC( l.Arc( arcIndex ), m_currentNet );
1137  arc.SetWidth( pl.Width() );
1138  arc.SetLayer( m_currentLayer );
1139 
1140  m_lastNode->Add( std::make_unique<ARC>( arc ) );
1141  lastItem = &arc;
1142  lastArc = arcIndex;
1143  }
1144  }
1145 
1146  if( pl.EndsWithVia() )
1147  m_lastNode->Add( Clone( pl.Via() ) );
1148 
1149  if( realEnd && lastItem )
1150  simplifyNewLine( m_lastNode, lastItem );
1151 
1152  if( !realEnd )
1153  {
1154  setInitialDirection( d_last );
1155  m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1156 
1158 
1159  m_startItem = nullptr;
1160  m_placingVia = false;
1162 
1165 
1166  m_head.Line().Clear();
1167  m_tail.Line().Clear();
1168  m_head.RemoveVia();
1169  m_tail.RemoveVia();
1172 
1173  if( m_shove )
1174  m_shove->AddLockedSpringbackNode( m_currentNode );
1175 
1176  DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1177 
1182 
1183  m_placementCorrect = true;
1184  }
1185  else
1186  {
1187  m_placementCorrect = true;
1188  m_idle = true;
1189  }
1190 
1191  return realEnd;
1192 }
1193 
1194 
1196 {
1197  FIXED_TAIL::STAGE st;
1198 
1199  if ( !m_fixedTail.PopStage( st ) )
1200  return false;
1201 
1202  m_head.Line().Clear();
1203  m_tail.Line().Clear();
1204  m_startItem = nullptr;
1205  m_p_start = st.pts[0].p;
1206  m_direction = st.pts[0].direction;
1207  m_placingVia = st.pts[0].placingVias;
1208  m_currentNode = st.commit;
1209  m_currentLayer = st.pts[0].layer;
1212  m_head.RemoveVia();
1213  m_tail.RemoveVia();
1214 
1218 
1219  if( m_shove )
1220  {
1221  m_shove->RewindSpringbackTo( m_currentNode );
1222  m_shove->UnlockSpringbackNode( m_currentNode );
1223  m_currentNode = m_shove->CurrentNode();
1225  }
1226 
1228 
1229  return true;
1230 }
1231 
1232 
1234 {
1235  return m_placementCorrect || m_fixedTail.StageCount() > 1;
1236 }
1237 
1238 
1240 {
1241  if( m_lastNode )
1243 
1244  m_lastNode = nullptr;
1245  m_currentNode = nullptr;
1246  return true;
1247 }
1248 
1249 
1250 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1251 {
1252  if( !aLatest.SegmentCount() )
1253  return;
1254 
1255  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1256  return;
1257 
1258  std::set<LINKED_ITEM *> toErase;
1259  aNode->Add( aLatest, true );
1260 
1261  for( int s = 0; s < aLatest.LinkCount(); s++ )
1262  {
1263  LINKED_ITEM* seg = aLatest.GetLink(s);
1264  LINE ourLine = aNode->AssembleLine( seg );
1265  JOINT a, b;
1266  std::vector<LINE> lines;
1267 
1268  aNode->FindLineEnds( ourLine, a, b );
1269 
1270  if( a == b )
1271  aNode->FindLineEnds( aLatest, a, b );
1272 
1273  aNode->FindLinesBetweenJoints( a, b, lines );
1274 
1275  int removedCount = 0;
1276  int total = 0;
1277 
1278  for( LINE& line : lines )
1279  {
1280  total++;
1281 
1282  if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1283  {
1284  for( LINKED_ITEM* ss : line.Links() )
1285  toErase.insert( ss );
1286 
1287  removedCount++;
1288  }
1289  }
1290 
1291  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1292  }
1293 
1294  for( LINKED_ITEM* s : toErase )
1295  aNode->Remove( s );
1296 
1297  aNode->Remove( aLatest );
1298 }
1299 
1300 
1302 {
1303  wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1304  LINE l = aNode->AssembleLine( aLatest );
1305 
1306  bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1307 
1308  SHAPE_LINE_CHAIN simplified( l.CLine() );
1309 
1310  simplified.Simplify();
1311 
1312  if( optimized || simplified.PointCount() != l.PointCount() )
1313  {
1314  aNode->Remove( l );
1315  l.SetShape( simplified );
1316  aNode->Add( l );
1317  }
1318 }
1319 
1320 
1322 {
1323  // initPlacement will kill the tail, don't do that unless the track size has changed
1324  if( !m_idle && aSizes.TrackWidth() != m_sizes.TrackWidth() )
1325  {
1326  m_sizes = aSizes;
1327  initPlacement();
1328  }
1329 
1330  m_sizes = aSizes;
1331 
1332  if( !m_idle )
1333  {
1336 
1337  if( m_head.EndsWithVia() )
1338  {
1341  }
1342  }
1343 }
1344 
1345 
1347 {
1348  LINE current = Trace();
1349  SHAPE_LINE_CHAIN ratLine;
1350  TOPOLOGY topo( m_lastNode );
1351 
1352  if( topo.LeadingRatLine( &current, ratLine ) )
1353  m_router->GetInterface()->DisplayRatline( ratLine, 5 );
1354 }
1355 
1356 
1357 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1358 {
1359  m_orthoMode = aOrthoMode;
1360 }
1361 
1362 
1364 {
1365  SHAPE_LINE_CHAIN l;
1366  DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
1367 
1368  wxLogTrace( "PNS", "buildInitialLine: m_direction %s, guessedDir %s, tail points %d",
1369  m_direction.Format(), guessedDir.Format(), m_tail.PointCount() );
1370 
1371  // Rounded corners don't make sense when routing orthogonally (single track at a time)
1372  bool fillet = !m_orthoMode && Settings().GetCornerMode() == CORNER_MODE::ROUNDED_45;
1373 
1374  if( m_p_start == aP )
1375  {
1376  l.Clear();
1377  }
1378  else
1379  {
1380  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1381  {
1382  l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1383  }
1384  else
1385  {
1386  if( !m_tail.PointCount() )
1387  l = guessedDir.BuildInitialTrace( m_p_start, aP, false, fillet );
1388  else
1389  l = m_direction.BuildInitialTrace( m_p_start, aP, false, fillet );
1390  }
1391 
1392  if( l.SegmentCount() > 1 && m_orthoMode )
1393  {
1394  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1395 
1396  l.Remove( -1, -1 );
1397  l.SetPoint( 1, newLast );
1398  }
1399  }
1400 
1401  aHead.SetLayer( m_currentLayer );
1402  aHead.SetShape( l );
1403 
1404  if( !m_placingVia )
1405  return true;
1406 
1407  VIA v( makeVia( aP ) );
1408  v.SetNet( aHead.Net() );
1409 
1411  {
1412  aHead.AppendVia( v );
1413  return true;
1414  }
1415 
1416  VECTOR2I force;
1417  VECTOR2I lead = aP - m_p_start;
1418 
1419  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1420 
1421  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1422  {
1423  SHAPE_LINE_CHAIN line = guessedDir.BuildInitialTrace( m_p_start, aP + force, false,
1424  fillet );
1425  aHead = LINE( aHead, line );
1426 
1427  v.SetPos( v.Pos() + force );
1428  return true;
1429  }
1430 
1431  return false; // via placement unsuccessful
1432 }
1433 
1434 
1435 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1436 {
1437  aNets.push_back( m_currentNet );
1438 }
1439 
1440 
1442 {
1443  m_world->KillChildren();
1444  return true;
1445 }
1446 
1447 
1448 FIXED_TAIL::FIXED_TAIL( int aLineCount )
1449 {
1450 
1451 }
1452 
1453 
1455 {
1456 
1457 }
1458 
1459 
1461 {
1462  m_stages.clear();
1463 }
1464 
1465 
1466 void FIXED_TAIL::AddStage( VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction,
1467  NODE *aNode )
1468 {
1469  STAGE st;
1470  FIX_POINT pt;
1471 
1472  pt.p = aStart;
1473  pt.layer = aLayer;
1474  pt.direction = direction;
1475  pt.placingVias = placingVias;
1476 
1477  st.pts.push_back(pt);
1478  st.commit = aNode;
1479 
1480  m_stages.push_back( st );
1481 }
1482 
1483 
1485 {
1486  if( !m_stages.size() )
1487  return false;
1488 
1489  aStage = m_stages.back();
1490 
1491  if( m_stages.size() > 1 )
1492  m_stages.pop_back();
1493 
1494  return true;
1495 }
1496 
1497 
1499 {
1500  return m_stages.size();
1501 }
1502 
1503 }
1504 
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
int PrevShape(int aPointIndex) const
Base class for PNS router board items.
Definition: pns_item.h:55
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:285
bool SmartPads() const
Enable/disable Smart Pads (optimized connections).
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
const SHAPE_ARC & Arc(size_t aArc) const
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
void SetViaDiameter(int aDiameter)
Definition: pns_line.h:198
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
const ITEM_SET Traces() override
Return the complete routed line, as a single-member ITEM_SET.
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).
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
std::vector< INTERSECTION > INTERSECTIONS
Keep the router "world" - i.e.
Definition: pns_node.h:149
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
void RemoveShape(int aPointIndex)
Removes the shape at the given index from the line chain.
void routeStep(const VECTOR2I &aP)
Perform a single routing algorithm step, for the end point aP.
int SegmentCount() const
Definition: pns_line.h:139
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
std::vector< STAGE > m_stages
void SetPoint(int aIndex, const VECTOR2I &aPos)
Accessor Function to move a point to a specific location.
NODE * m_world
pointer to world to search colliding items
void SetLayer(int aLayer)
Definition: pns_item.h:153
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:146
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
bool Is45Degree() const
Print out all linked segments.
Definition: pns_line.cpp:427
void CommitRouting()
Definition: pns_router.cpp:655
H/V/45 with filleted corners.
void removeLoops(NODE *aNode, LINE &aLatest)
Searches aNode for traces concurrent to aLatest and removes them.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
Simplify pad-pad and pad-via connections if possible.
WALKAROUND_STATUS statusCw
void simplifyNewLine(NODE *aNode, LINKED_ITEM *aLatest)
Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertex...
VECTOR2I::extended_type ecoord
Definition: seg.h:44
virtual LOGGER * Logger()
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:986
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, bool aSolidsOnly=true, int aMaxIterations=10)
Definition: pns_via.cpp:32
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
void RemoveVia()
Definition: pns_line.h:194
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step shove mode.
SIZES_SETTINGS m_sizes
std::vector< FIX_POINT > pts
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:993
bool PopStage(STAGE &aStage)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
FIXED_TAIL(int aLineCount=1)
const LINE Trace() const
Return the complete routed line.
class PAD, a pad in a footprint
Definition: typeinfo.h:89
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:870
virtual void DisplayRatline(const SHAPE_LINE_CHAIN &aRatline, int aColor=-1)=0
size_t ArcCount() const
const SEG & Seg() const
Definition: pns_segment.h:84
bool reduceTail(const VECTOR2I &aEnd)
Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest ...
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
int Depth() const
Definition: pns_node.h:194
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead)
const std::vector< SHAPE_ARC > & CArcs() const
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...
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Function PointCount()
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:124
const VECTOR2I & Pos() const
Definition: pns_via.h:96
int PointCount() const
Definition: pns_line.h:140
bool RemoveLoops() const
Enable/disable loop (redundant track) removal.
bool EndsWithVia() const
Definition: pns_line.h:191
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:804
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:149
void SetNet(int aNet)
Definition: pns_item.h:147
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
VIATYPE ViaType() const
bool handlePullback()
Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direct...
void SetCollisionMask(int aMask)
LINE_PLACER(ROUTER *aRouter)
bool FollowMouse() const
Return true if smoothing segments during dragging is enabled.
const std::vector< ssize_t > & CShapes() const
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
ssize_t ArcIndex(size_t aSegment) const
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:169
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetApproachCursor(bool aEnabled, const VECTOR2I &aPos)
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
Definition: pns_joint.h:42
void UpdateSizes(const SIZES_SETTINGS &aSizes) override
Perform on-the-fly update of the width, via diameter & drill size from a settings class.
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.h:389
ROUTER * m_router
Definition: pns_algo_base.h:87
DIRECTION_45 m_initial_direction
routing direction for new traces
void KillChildren()
Definition: pns_node.cpp:1292
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:912
void SetWorld(NODE *aNode)
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
void setInitialDirection(const DIRECTION_45 &aDirection)
Set preferred direction of the very first track segment to be laid.
void SetWidth(int aWidth) override
Definition: pns_segment.h:74
int Net() const
Definition: pns_item.h:148
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Check if point aP lies on segment aSeg.
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
std::unique_ptr< SHOVE > m_shove
The shove engine.
DIRECTION_45 m_direction
current routing direction
const VECTOR2I & GetP0() const
Definition: shape_arc.h:95
void initPlacement()
Initialize placement of a new line with given parameters.
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void AddTrailPoint(const VECTOR2I &aP)
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
Definition: pns_line.cpp:456
void updateLeadingRatLine()
Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest y...
PNS_MODE Mode() const
Set the routing mode.
void SetWidth(int aWidth) override
Definition: pns_arc.h:83
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.h:422
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...
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
void SetSolidsOnly(bool aSolidsOnly)
int ShapeCount() const
Returns the number of shapes (line segments or arcs) in this line chain.
bool HasPlacedAnything() const override
MOUSE_TRAIL_TRACER m_mouseTrailTracer
bool handleSelfIntersections()
Check if the head of the track intersects its tail.
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
VECTOR2I closestProjectedPoint(const SHAPE_LINE_CHAIN &line, const VECTOR2I &p)
bool route(const VECTOR2I &aP)
Re-route the current track to point aP.
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
void GetModifiedNets(std::vector< int > &aNets) const override
Function GetModifiedNets.
FIXED_TAIL m_fixedTail
int SegmentCount() const
Function SegmentCount()
bool CommitPlacement() override
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead)
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:1027
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step mark obstacles mode.
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:98
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:370
Definition: seg.h:41
void SetViaDrill(int aDrill)
Definition: pns_line.h:199
Guess what's better, try to make least mess on the PCB.
NODE * m_currentNode
Current world state.
int ShapeCount() const
Return the aIdx-th point of the line.
Definition: pns_line.h:142
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:65
void setWorld(NODE *aWorld)
Set the board to route.
bool optimizeTailHeadTransition()
Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segme...
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
Ignore collisions, mark obstacles.
bool ToggleVia(bool aEnabled) override
Enable/disable a via at the end of currently routed trace.
CORNER_MODE GetCornerMode() const
void AddStage(VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
Reduce corner cost by merging obtuse segments.
const SEG CSegment(int aIndex) const
Function CSegment()
void FlipPosture() override
Toggle the current posture (straight/diagonal) of the trace head.
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:257
SHAPE_LINE_CHAIN.
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:427
WALKAROUND_STATUS statusCcw
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool HasLoops() const
Definition: pns_line.cpp:979
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
VECTOR2I A
Definition: seg.h:49
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:134
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
bool SetLayer(int aLayer) override
Set the current routing layer.
Only walk around.
DIRECTION_45 GetPosture(const VECTOR2I &aP)
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:1225
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
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:126
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:94
void Clear()
Function Clear() Removes all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:152
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
void SetWorld(NODE *aNode)
Merge co-linear segments.
bool mergeHead()
Moves "established" segments from the head to the tail if certain conditions are met.
void SetMouseDisabled(bool aDisabled=true)
Disables the mouse-trail portion of the posture solver; leaving only the manual posture switch and th...
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:210
void SetEffortLevel(int aEffort)
void SetOrthoMode(bool aOrthoMode) override
Function SetOrthoMode()
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).
NODE * Owner() const
Return the owner of this item, or NULL if there's none.
Definition: pns_item.h:167
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
bool AbortPlacement() override
const VIA & Via() const
Definition: pns_line.h:196
const VIA makeVia(const VECTOR2I &aP)
int StageCount() const
Push and Shove diff pair dimensions (gap) settings dialog.
void SetLogger(LOGGER *aLogger)
Definition: pns_algo_base.h:65
NODE * GetWorld() const
Definition: pns_router.h:158
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:615
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
void SetIterationLimit(const int aIterLimit)
bool UnfixRoute() override
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:31
const LAYER_RANGE & Layers() const
Definition: pns_item.h:150
Reroute pad exits.
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:153
int CountCorners(int aAngles) const
Definition: pns_line.cpp:136
void SetBlockingObstacle(ITEM *aObstacle)
Definition: pns_line.h:205
VECTOR2I B
Definition: seg.h:50