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-2020 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 
24 #include "pns_arc.h"
25 #include "pns_debug_decorator.h"
26 #include "pns_line_placer.h"
27 #include "pns_node.h"
28 #include "pns_router.h"
29 #include "pns_shove.h"
30 #include "pns_topology.h"
31 #include "pns_utils.h"
32 #include "pns_walkaround.h"
33 
34 #include <class_board_item.h>
35 
36 #include <memory>
37 
38 namespace PNS {
39 
41  PLACEMENT_ALGO( aRouter )
42 {
44  m_world = NULL;
45  m_shove = NULL;
47  m_idle = true;
48 
49  // Init temporary variables (do not leave uninitialized members)
50  m_lastNode = NULL;
51  m_placingVia = false;
52  m_currentNet = 0;
53  m_currentLayer = 0;
55  m_startItem = NULL;
56  m_chainedPlacement = false;
57  m_orthoMode = false;
58  m_placementCorrect = false;
59 }
60 
61 
63 {
64 }
65 
66 
67 void LINE_PLACER::setWorld( NODE* aWorld )
68 {
69  m_world = aWorld;
70 }
71 
72 
73 const VIA LINE_PLACER::makeVia( const VECTOR2I& aP )
74 {
76 
77  return VIA( aP, layers, m_sizes.ViaDiameter(), m_sizes.ViaDrill(), -1, m_sizes.ViaType() );
78 }
79 
80 
81 bool LINE_PLACER::ToggleVia( bool aEnabled )
82 {
83  m_placingVia = aEnabled;
84 
85  if( !aEnabled )
86  m_head.RemoveVia();
87 
88  return true;
89 }
90 
91 
93 {
94  m_initial_direction = aDirection;
95 
96  if( m_tail.SegmentCount() == 0 )
97  m_direction = aDirection;
98 }
99 
100 
102 {
104  SHAPE_LINE_CHAIN& head = m_head.Line();
105  SHAPE_LINE_CHAIN& tail = m_tail.Line();
106 
107  // if there is no tail, there is nothing to intersect with
108  if( tail.PointCount() < 2 )
109  return false;
110 
111  if( head.PointCount() < 2 )
112  return false;
113 
114  // completely new head trace? chop off the tail
115  if( tail.CPoint(0) == head.CPoint(0) )
116  {
117  m_p_start = tail.CPoint( 0 );
119  tail.Clear();
120  return true;
121  }
122 
123 
124  tail.Intersect( head, ips );
125 
126  // no intesection points - nothing to reduce
127  if( ips.empty() )
128  return false;
129 
130  int n = INT_MAX;
131  VECTOR2I ipoint;
132 
133  // if there is more than one intersection, find the one that is
134  // closest to the beginning of the tail.
135  for( const SHAPE_LINE_CHAIN::INTERSECTION& i : ips )
136  {
137  if( i.our.Index() < n )
138  {
139  n = i.our.Index();
140  ipoint = i.p;
141  }
142  }
143 
144  // ignore the point where head and tail meet
145  if( ipoint == head.CPoint( 0 ) || ipoint == tail.CPoint( -1 ) )
146  return false;
147 
148  // Intersection point is on the first or the second segment: just start routing
149  // from the beginning
150  if( n < 2 )
151  {
152  m_p_start = tail.CPoint( 0 );
154  tail.Clear();
155  head.Clear();
156 
157  return true;
158  }
159  else
160  {
161  // Clip till the last tail segment before intersection.
162  // Set the direction to the one of this segment.
163  const SEG last = tail.CSegment( n - 1 );
164  m_p_start = last.A;
165  m_direction = DIRECTION_45( last );
166  tail.Remove( n, -1 );
167  return true;
168  }
169 
170  return false;
171 }
172 
173 
175 {
176  SHAPE_LINE_CHAIN& head = m_head.Line();
177  SHAPE_LINE_CHAIN& tail = m_tail.Line();
178 
179  if( head.PointCount() < 2 )
180  return false;
181 
182  int n = tail.PointCount();
183 
184  if( n == 0 )
185  return false;
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( head.CSegment( 0 ) );
194  DIRECTION_45 last_tail( tail.CSegment( -1 ) );
195  DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
196 
197  // case 1: we have a defined routing direction, and the currently computed
198  // head goes in different one.
199  bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
200 
201  // case 2: regardless of the current routing direction, if the tail/head
202  // extremities form an acute or right angle, reduce the tail by one segment
203  // (and hope that further iterations) will result with a cleaner trace
204  bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
205 
206  if( pullback_1 || pullback_2 )
207  {
208  const SEG last = tail.CSegment( -1 );
209  m_direction = DIRECTION_45( last );
210  m_p_start = last.A;
211 
212  wxLogTrace( "PNS", "Placer: pullback triggered [%d] [%s %s]",
213  n, last_tail.Format().c_str(), first_head.Format().c_str() );
214 
215  // erase the last point in the tail, hoping that the next iteration will
216  // result with a head trace that starts with a segment following our
217  // current direction.
218  if( n < 2 )
219  tail.Clear(); // don't leave a single-point tail
220  else
221  tail.Remove( -1, -1 );
222 
223  if( !tail.SegmentCount() )
225 
226  return true;
227  }
228 
229  return false;
230 }
231 
232 
234 {
235  SHAPE_LINE_CHAIN& head = m_head.Line();
236  SHAPE_LINE_CHAIN& tail = m_tail.Line();
237 
238  int n = tail.SegmentCount();
239 
240  if( head.SegmentCount() < 1 )
241  return false;
242 
243  // Don't attempt this for too short tails
244  if( n < 2 )
245  return false;
246 
247  // Start from the segment farthest from the end of the tail
248  // int start_index = std::max(n - 1 - ReductionDepth, 0);
249 
250  DIRECTION_45 new_direction;
251  VECTOR2I new_start;
252  int reduce_index = -1;
253 
254  for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
255  {
256  const SEG s = tail.CSegment( i );
257  DIRECTION_45 dir( s );
258 
259  // calculate a replacement route and check if it matches
260  // the direction of the segment to be replaced
261  SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
262 
263  if( replacement.SegmentCount() < 1 )
264  continue;
265 
266  LINE tmp( m_tail, replacement );
267 
269  break;
270 
271  if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
272  {
273  new_start = s.A;
274  new_direction = dir;
275  reduce_index = i;
276  }
277  }
278 
279  if( reduce_index >= 0 )
280  {
281  wxLogTrace( "PNS", "Placer: reducing tail: %d", reduce_index );
282  SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
283 
284  m_p_start = new_start;
285  m_direction = new_direction;
286  tail.Remove( reduce_index + 1, -1 );
287  head.Clear();
288  return true;
289  }
290 
291  if( !tail.SegmentCount() )
293 
294  return false;
295 }
296 
297 
298 bool LINE_PLACER::checkObtusity( const SEG& aA, const SEG& aB ) const
299 {
300  const DIRECTION_45 dir_a( aA );
301  const DIRECTION_45 dir_b( aB );
302 
303  return dir_a.IsObtuse( dir_b ) || dir_a == dir_b;
304 }
305 
306 
308 {
309  SHAPE_LINE_CHAIN& head = m_head.Line();
310  SHAPE_LINE_CHAIN& tail = m_tail.Line();
311 
312  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE |
315 
316  head.Simplify();
317  tail.Simplify();
318 
319  int n_head = head.SegmentCount();
320  int n_tail = tail.SegmentCount();
321 
322  if( n_head < 3 )
323  {
324  wxLogTrace( "PNS", "Merge failed: not enough head segs." );
325  return false;
326  }
327 
328  if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
329  {
330  wxLogTrace( "PNS", "Merge failed: head and tail discontinuous." );
331  return false;
332  }
333 
334  if( m_head.CountCorners( ForbiddenAngles ) != 0 )
335  return false;
336 
337  DIRECTION_45 dir_tail, dir_head;
338 
339  dir_head = DIRECTION_45( head.CSegment( 0 ) );
340 
341  if( n_tail )
342  {
343  dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
344 
345  if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
346  return false;
347  }
348 
349  tail.Append( head );
350  tail.Remove( -1 );
351 
352  tail.Simplify();
353 
354  SEG last = tail.CSegment( -1 );
355 
356  m_p_start = last.B;
357  m_direction = DIRECTION_45( last ).Right();
358 
359  head.Remove( 0, -1 );
360 
361  wxLogTrace( "PNS", "Placer: merge %d, new direction: %s", n_head, m_direction.Format().c_str() );
362 
363  head.Simplify();
364  tail.Simplify();
365 
366  return true;
367 }
368 
369 
371 {
372  int min_dist = INT_MAX;
373  VECTOR2I closest;
374 
375  for(int i = 0; i < line.SegmentCount(); i++ )
376  {
377  const auto& s = line.CSegment(i);
378  auto a = s.NearestPoint( p );
379  auto d = (a - p).EuclideanNorm();
380 
381  if( d < min_dist )
382  {
383  min_dist = d;
384  closest = a;
385  }
386  }
387 
388  return closest;
389 }
390 
391 
392 bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
393 {
394  LINE initTrack( m_head );
395  LINE walkFull( m_head );
396  int effort = 0;
397  bool rv = true, viaOk;
398 
399  viaOk = buildInitialLine( aP, initTrack );
400 
401  WALKAROUND walkaround( m_currentNode, Router() );
402 
403  walkaround.SetSolidsOnly( false );
404  walkaround.SetDebugDecorator( Dbg() );
405  walkaround.SetLogger( Logger() );
406  walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
407 
408  WALKAROUND::RESULT wr = walkaround.Route( initTrack );
409  //WALKAROUND::WALKAROUND_STATUS wf = walkaround.Route( initTrack, walkFull, false );
410 
411  auto l_cw = wr.lineCw.CLine();
412  auto l_ccw = wr.lineCcw.CLine();
413 
415  {
416 
417  auto p_cw = closestProjectedPoint( l_cw, aP );
418  auto p_ccw = closestProjectedPoint( l_ccw, aP );
419 
420  int idx_cw = l_cw.Split( p_cw );
421  int idx_ccw = l_ccw.Split( p_ccw );
422 
423  l_cw = l_cw.Slice( 0, idx_cw );
424  l_ccw = l_ccw.Slice( 0, idx_ccw );
425 
426  //Dbg()->AddLine( wr.lineCw.CLine(), 3, 40000 );
427 
428  //Dbg()->AddPoint( p_cw, 4 );
429  //Dbg()->AddPoint( p_ccw, 5 );
430 
431  Dbg()->AddLine( wr.lineCw.CLine(), 4, 1000 );
432  Dbg()->AddLine( wr.lineCcw.CLine(), 5, 1000 );
433 
434  }
435 
436  walkFull.SetShape( l_ccw.Length() < l_cw.Length() ? l_ccw : l_cw );
437 
438  Dbg()->AddLine( walkFull.CLine(), 2, 100000, "walk-full" );
439 
440  switch( Settings().OptimizerEffort() )
441  {
442  case OE_LOW:
443  effort = 0;
444  break;
445 
446  case OE_MEDIUM:
447  case OE_FULL:
448  effort = OPTIMIZER::MERGE_SEGMENTS;
449  break;
450  }
451 
452  if( Settings().SmartPads() )
453  effort |= OPTIMIZER::SMART_PADS;
454 
456  {
457  walkFull = walkFull.ClipToNearestObstacle( m_currentNode );
458  rv = true;
459  }
460  else if( m_placingVia && viaOk )
461  {
462  walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
463  }
464 
465  OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
466 
467  if( m_currentNode->CheckColliding( &walkFull ) )
468  {
469  aNewHead = m_head;
470  return false;
471  }
472 
473  m_head = walkFull;
474  aNewHead = walkFull;
475 
476  return rv;
477 }
478 
479 
480 bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead )
481 {
482  LINE newHead( m_head ), bestHead( m_head );
483  bool hasBest = false;
484 
485  buildInitialLine( aP, newHead );
486 
487  NODE::OBSTACLES obstacles;
488 
489  m_currentNode->QueryColliding( &newHead, obstacles );
490 
491  // If we are allowing DRC violations, we don't push back to the hull
492  if( !Settings().CanViolateDRC() )
493  {
494  for( auto& obs : obstacles )
495  {
496  int cl = m_currentNode->GetClearance( obs.m_item, &newHead );
497  auto hull = obs.m_item->Hull( cl, newHead.Width() );
498 
499  auto nearest = hull.NearestPoint( aP );
500  Dbg()->AddLine( hull, 2, 10000 );
501 
502  if( ( nearest - aP ).EuclideanNorm() < newHead.Width() + cl )
503  {
504  buildInitialLine( nearest, newHead );
505 
506  // We want the shortest line here to ensure we don't break a clearance
507  // rule on larger, overlapping items (e.g. vias)
508  if( newHead.CLine().Length() < bestHead.CLine().Length() )
509  {
510  bestHead = newHead;
511  hasBest = true;
512  }
513  }
514  }
515  }
516 
517  if( hasBest )
518  m_head = bestHead;
519  else
520  m_head = newHead;
521 
522  aNewHead = m_head;
523 
524  return static_cast<bool>( m_currentNode->CheckColliding( &m_head ) );
525 }
526 
527 
528 const LINE LINE_PLACER::reduceToNearestObstacle( const LINE& aOriginalLine )
529 {
530  const auto& l0 = aOriginalLine.CLine();
531 
532  if ( !l0.PointCount() )
533  return aOriginalLine;
534 
535  int l = l0.Length();
536  int step = l / 2;
537  VECTOR2I target;
538 
539  LINE l_test( aOriginalLine );
540 
541  while( step > 0 )
542  {
543  target = l0.PointAlong( l );
544  SHAPE_LINE_CHAIN l_cur( l0 );
545 
546  int index = l_cur.Split( target );
547 
548  l_test.SetShape( l_cur.Slice( 0, index ) );
549 
550  if ( m_currentNode->CheckColliding( &l_test ) )
551  l -= step;
552  else
553  l += step;
554 
555  step /= 2;
556  }
557 
558  l = l_test.CLine().Length();
559 
560  while( m_currentNode->CheckColliding( &l_test ) && l > 0 )
561  {
562  l--;
563  target = l0.PointAlong( l );
564  SHAPE_LINE_CHAIN l_cur( l0 );
565 
566  int index = l_cur.Split( target );
567 
568  l_test.SetShape( l_cur.Slice( 0, index ) );
569  }
570 
571  return l_test;
572 }
573 
574 
576 {
577  LINE l0;
578  l0 = m_head;
579 
580  buildInitialLine( aP, l0 );
581 
582  LINE l_cur = reduceToNearestObstacle( l0 );
583 
584  const auto l_shape = l_cur.CLine();
585 
586  if( l_shape.SegmentCount() == 0 )
587  {
588  return false;
589  }
590 
591  if( l_shape.SegmentCount() == 1 )
592  {
593  auto s = l_shape.CSegment( 0 );
594 
595  VECTOR2I dL( DIRECTION_45( s ).Left().ToVector() );
596  VECTOR2I dR( DIRECTION_45( s ).Right().ToVector() );
597 
598  SEG leadL( s.B, s.B + dL );
599  SEG leadR( s.B, s.B + dR );
600 
601  SEG segL( s.B, leadL.LineProject( aP ) );
602  SEG segR( s.B, leadR.LineProject( aP ) );
603 
604  LINE finishL( l0, SHAPE_LINE_CHAIN( { segL.A, segL.B } ) );
605  LINE finishR( l0, SHAPE_LINE_CHAIN( { segR.A, segR.B } ) );
606 
607  LINE reducedL = reduceToNearestObstacle( finishL );
608  LINE reducedR = reduceToNearestObstacle( finishR );
609 
610  int lL = reducedL.CLine().Length();
611  int lR = reducedR.CLine().Length();
612 
613  if( lL > lR )
614  l_cur.Line().Append( reducedL.CLine() );
615  else
616  l_cur.Line().Append( reducedR.CLine() );
617 
618  l_cur.Line().Simplify();
619  }
620 
621  m_head = l_cur;
622  aNewHead = m_head;
623  return true;
624 }
625 
626 
627 bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
628 {
629  LINE initTrack( m_head );
630  LINE walkSolids, l2;
631 
632  bool viaOk = buildInitialLine( aP, initTrack );
633 
634  m_currentNode = m_shove->CurrentNode();
635 
636  m_shove->SetLogger( Logger() );
637  m_shove->SetDebugDecorator( Dbg() );
638 
639  OPTIMIZER optimizer( m_currentNode );
640 
641  WALKAROUND walkaround( m_currentNode, Router() );
642 
643  walkaround.SetSolidsOnly( true );
644  walkaround.SetIterationLimit( 10 );
645  walkaround.SetDebugDecorator( Dbg() );
646  walkaround.SetLogger( Logger() );
647  WALKAROUND::WALKAROUND_STATUS stat_solids = walkaround.Route( initTrack, walkSolids );
648 
650  optimizer.SetCollisionMask( ITEM::SOLID_T );
651  optimizer.Optimize( &walkSolids );
652 
653  if( stat_solids == WALKAROUND::DONE )
654  l2 = walkSolids;
655  else
656  l2 = initTrack.ClipToNearestObstacle( m_shove->CurrentNode() );
657 
658  LINE l( m_tail );
659  l.Line().Append( l2.CLine() );
660  l.Line().Simplify();
661 
662  if( l.PointCount() == 0 || l2.PointCount() == 0 )
663  {
664  aNewHead = m_head;
665  return false;
666  }
667 
668  if( m_placingVia && viaOk )
669  {
670  VIA v1( makeVia( l.CPoint( -1 ) ) );
671  VIA v2( makeVia( l2.CPoint( -1 ) ) );
672 
673  l.AppendVia( v1 );
674  l2.AppendVia( v2 );
675  }
676 
677  l.Line().Simplify();
678 
679  // in certain, uncommon cases there may be loops in the head+tail, In such case, we don't shove to avoid
680  // screwing up the database.
681  if( l.HasLoops() )
682  {
683  aNewHead = m_head;
684  return false;
685  }
686 
687  SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
688 
689  m_currentNode = m_shove->CurrentNode();
690 
691  if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
692  {
693  if( status == SHOVE::SH_HEAD_MODIFIED )
694  {
695  l2 = m_shove->NewHead();
696  }
697 
698  optimizer.SetWorld( m_currentNode );
700  optimizer.SetCollisionMask( ITEM::ANY_T );
701  optimizer.Optimize( &l2 );
702 
703  aNewHead = l2;
704 
705  return true;
706  }
707  else
708  {
709  walkaround.SetWorld( m_currentNode );
710  walkaround.SetSolidsOnly( false );
711  walkaround.SetIterationLimit( 10 );
712  walkaround.SetApproachCursor( true, aP );
713  walkaround.Route( initTrack, l2 );
714  aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
715 
716  return false;
717  }
718 
719  return false;
720 }
721 
722 
723 bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead )
724 {
725  switch( m_currentMode )
726  {
727  case RM_MarkObstacles:
728  return rhMarkObstacles( aP, aNewHead );
729  case RM_Walkaround:
730  return rhWalkOnly( aP, aNewHead );
731  case RM_Shove:
732  return rhShoveOnly( aP, aNewHead );
733  default:
734  break;
735  }
736 
737  return false;
738 }
739 
740 
742 {
743  LINE linetmp = Trace();
744 
746  {
747  if( linetmp.SegmentCount() < 1 )
748  return false;
749 
750  m_head = linetmp;
751  m_p_start = linetmp.CLine().CPoint( 0 );
752  m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
753  m_tail.Line().Clear();
754 
755  return true;
756  }
757 
758  SHAPE_LINE_CHAIN& head = m_head.Line();
759  SHAPE_LINE_CHAIN& tail = m_tail.Line();
760 
761  int tailLookbackSegments = 3;
762 
763  //if(m_currentMode() == RM_Walkaround)
764  // tailLookbackSegments = 10000;
765 
766  int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
767 
768  if( tail.SegmentCount() < 3 )
769  return false;
770 
771  // assemble TailLookbackSegments tail segments with the current head
772  SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
773 
774  int end = std::min(2, head.PointCount() - 1 );
775 
776  opt_line.Append( head.Slice( 0, end ) );
777 
778  LINE new_head( m_tail, opt_line );
779 
780  // and see if it could be made simpler by merging obtuse/collnear segments.
781  // If so, replace the (threshold) last tail points and the head with
782  // the optimized line
783 
785  {
786  LINE tmp( m_tail, opt_line );
787 
788  wxLogTrace( "PNS", "Placer: optimize tail-head [%d]", threshold );
789 
790  head.Clear();
791  tail.Replace( -threshold, -1, new_head.CLine() );
792  tail.Simplify();
793 
794  m_p_start = new_head.CLine().CPoint( -1 );
795  m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
796 
797  return true;
798  }
799 
800  return false;
801 }
802 
803 
805 {
806  bool fail = false;
807  bool go_back = false;
808 
809  int i, n_iter = 1;
810 
811  LINE new_head;
812 
813  wxLogTrace( "PNS", "INIT-DIR: %s head: %d, tail: %d segs",
815 
816  for( i = 0; i < n_iter; i++ )
817  {
818  if( !go_back && Settings().FollowMouse() )
819  reduceTail( aP );
820 
821  go_back = false;
822 
823  if( !routeHead( aP, new_head ) )
824  fail = true;
825 
826  if( !new_head.Is45Degree() )
827  fail = true;
828 
829  if( !Settings().FollowMouse() )
830  return;
831 
832  m_head = new_head;
833 
835  {
836  n_iter++;
837  go_back = true;
838  }
839 
840  if( !go_back && handlePullback() )
841  {
842  n_iter++;
843  go_back = true;
844  }
845 
846  }
847 
848  if( !fail )
849  {
851  return;
852 
853  mergeHead();
854  }
855 }
856 
857 
858 bool LINE_PLACER::route( const VECTOR2I& aP )
859 {
860  routeStep( aP );
861 
862  if (!m_head.PointCount() )
863  return false;
864 
865  return m_head.CPoint(-1) == aP;
866 }
867 
868 
870 {
871  LINE tmp( m_head );
872 
873  tmp.SetShape( m_tail.CLine() );
874  tmp.Line().Append( m_head.CLine() );
875  tmp.Line().Simplify();
876  return tmp;
877 }
878 
879 
881 {
882  m_currentTrace = Trace();
883  return ITEM_SET( &m_currentTrace );
884 }
885 
886 
888 {
891 }
892 
893 
894 NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
895 {
896  if( aLoopsRemoved && m_lastNode )
897  return m_lastNode;
898 
899  return m_currentNode;
900 }
901 
902 
903 bool LINE_PLACER::SplitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP )
904 {
905  if( !aSeg )
906  return false;
907 
908  if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
909  return false;
910 
911  JOINT* jt = aNode->FindJoint( aP, aSeg );
912 
913  if( jt && jt->LinkCount() >= 1 )
914  return false;
915 
916  SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
917 
918  std::unique_ptr< SEGMENT > s_new[2] = {
919  Clone( *s_old ),
920  Clone( *s_old )
921  };
922 
923  s_new[0]->SetEnds( s_old->Seg().A, aP );
924  s_new[1]->SetEnds( aP, s_old->Seg().B );
925 
926  aNode->Remove( s_old );
927  aNode->Add( std::move( s_new[0] ), true );
928  aNode->Add( std::move( s_new[1] ), true );
929 
930  return true;
931 }
932 
933 
934 bool LINE_PLACER::SetLayer( int aLayer )
935 {
936  if( m_idle )
937  {
938  m_currentLayer = aLayer;
939  return true;
940  }
941  else if( m_chainedPlacement )
942  {
943  return false;
944  }
945  else if( !m_startItem || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
946  {
947  m_currentLayer = aLayer;
948  m_head.Line().Clear();
949  m_tail.Line().Clear();
952  Move( m_currentEnd, NULL );
953  return true;
954  }
955 
956  return false;
957 }
958 
959 
960 bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
961 {
962  m_placementCorrect = false;
963  m_currentStart = VECTOR2I( aP );
964  m_currentEnd = VECTOR2I( aP );
965  m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
966  m_startItem = aStartItem;
967  m_placingVia = false;
968  m_chainedPlacement = false;
969  m_fixedTail.Clear();
970 
971  setInitialDirection( Settings().InitialDirection() );
972 
973  initPlacement();
974 
975  NODE *n;
976 
977  if ( m_shove )
978  n = m_shove->CurrentNode();
979  else
980  n = m_currentNode;
981 
983 
984  return true;
985 }
986 
987 
989 {
990  m_idle = false;
991 
992  m_head.Line().Clear();
993  m_tail.Line().Clear();
1000  m_head.RemoveVia();
1001  m_tail.RemoveVia();
1002 
1005 
1006  NODE* world = Router()->GetWorld();
1007 
1008  world->KillChildren();
1009  NODE* rootNode = world->Branch();
1010 
1012 
1013  setWorld( rootNode );
1014 
1015  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
1016  m_world, m_direction.Format().c_str(), m_currentLayer );
1017 
1018  m_lastNode = NULL;
1020  m_currentMode = Settings().Mode();
1021 
1022  m_shove.reset();
1023 
1025  {
1026  m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1027  }
1028 }
1029 
1030 
1031 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
1032 {
1033  LINE current;
1034  VECTOR2I p = aP;
1035  int eiDepth = -1;
1036 
1037  if( aEndItem && aEndItem->Owner() )
1038  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
1039 
1040  if( m_lastNode )
1041  {
1042  delete m_lastNode;
1043  m_lastNode = NULL;
1044  }
1045 
1046  bool reachesEnd = route( p );
1047 
1048  current = Trace();
1049 
1050  if( !current.PointCount() )
1052  else
1053  m_currentEnd = current.CLine().CPoint( -1 );
1054 
1055  NODE* latestNode = m_currentNode;
1056  m_lastNode = latestNode->Branch();
1057 
1058  if( reachesEnd && eiDepth >= 0 && aEndItem && latestNode->Depth() > eiDepth && current.SegmentCount() )
1059  {
1060  SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1061 
1062  if( Settings().RemoveLoops() )
1063  removeLoops( m_lastNode, current );
1064  }
1065 
1067  return true;
1068 }
1069 
1070 
1071 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1072 {
1073  bool realEnd = false;
1074  int lastV;
1075 
1076  LINE pl = Trace();
1077 
1079  {
1080  // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1081  // user has more responsibility and authority.
1082 
1083  if( aEndItem )
1084  {
1085  // The user has indicated a connection should be made. If either the
1086  // trace or endItem is netless, then allow the connection by adopting the net of the other.
1087  if( m_currentNet <= 0 )
1088  {
1089  m_currentNet = aEndItem->Net();
1090  pl.SetNet( m_currentNet );
1091  }
1092  else if (aEndItem->Net() <= 0 )
1093  aEndItem->SetNet( m_currentNet );
1094  }
1095 
1096  // Collisions still prevent fixing unless "Allow DRC violations" is checked
1097  if( !Settings().CanViolateDRC() && m_world->CheckColliding( &pl ) )
1098  return false;
1099  }
1100 
1101  const SHAPE_LINE_CHAIN& l = pl.CLine();
1102 
1103  if( !l.SegmentCount() )
1104  {
1105  // Nothing to commit if we have an empty line
1106  if( !pl.EndsWithVia() )
1107  return false;
1108 
1109  m_lastNode->Add( Clone( pl.Via() ) );
1110  m_currentNode = NULL;
1111 
1112  m_idle = true;
1113  m_placementCorrect = true;
1114  return true;
1115  }
1116 
1117  VECTOR2I p_pre_last = l.CPoint( -1 );
1118  const VECTOR2I p_last = l.CPoint( -1 );
1119  DIRECTION_45 d_last( l.CSegment( -1 ) );
1120 
1121  if( l.PointCount() > 2 )
1122  p_pre_last = l.CPoint( -2 );
1123 
1124  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1125  realEnd = true;
1126 
1127  if( aForceFinish )
1128  realEnd = true;
1129 
1130  if( realEnd || m_placingVia )
1131  lastV = l.SegmentCount();
1132  else
1133  lastV = std::max( 1, l.SegmentCount() - 1 );
1134 
1135  SEGMENT* lastSeg = nullptr;
1136  int lastArc = -1;
1137 
1138  for( int i = 0; i < lastV; i++ )
1139  {
1140  ssize_t arcIndex = l.ArcIndex( i );
1141 
1142  if( arcIndex < 0 )
1143  {
1144  const SEG& s = pl.CSegment( i );
1145  auto seg = std::make_unique<SEGMENT>( s, m_currentNet );
1146  seg->SetWidth( pl.Width() );
1147  seg->SetLayer( m_currentLayer );
1148  if( !m_lastNode->Add( std::move( seg ) ) )
1149  lastSeg = nullptr;
1150  }
1151  else
1152  {
1153  if( arcIndex == lastArc )
1154  continue;
1155 
1156  auto arc = std::make_unique<ARC>( l.Arc( arcIndex ), m_currentNet );
1157  arc->SetWidth( pl.Width() );
1158  arc->SetLayer( m_currentLayer );
1159  m_lastNode->Add( std::move( arc ) );
1160  lastSeg = nullptr;
1161  lastArc = arcIndex;
1162  }
1163  }
1164 
1165  if( pl.EndsWithVia() )
1166  {
1167  m_lastNode->Add( Clone( pl.Via() ) );
1168  }
1169 
1170  if( realEnd && lastSeg )
1171  simplifyNewLine( m_lastNode, lastSeg );
1172 
1173 
1174  if( !realEnd )
1175  {
1176  setInitialDirection( d_last );
1177  m_currentStart = m_placingVia ? p_last : p_pre_last;
1178 
1180 
1181  m_startItem = NULL;
1182  m_placingVia = false;
1184 
1187 
1188  m_head.Line().Clear();
1189  m_tail.Line().Clear();
1190  m_head.RemoveVia();
1191  m_tail.RemoveVia();
1194 
1195  if ( m_shove )
1196  {
1197  m_shove->AddLockedSpringbackNode( m_currentNode );
1198  }
1199 
1200  m_placementCorrect = true;
1201  }
1202  else
1203  {
1204  m_placementCorrect = true;
1205  m_idle = true;
1206  }
1207 
1208  return realEnd;
1209 }
1210 
1211 
1213 {
1214  FIXED_TAIL::STAGE st;
1215 
1216  if ( !m_fixedTail.PopStage( st ) )
1217  return false;
1218 
1219  m_head.Line().Clear();
1220  m_tail.Line().Clear();
1221  m_startItem = NULL;
1222  m_p_start = st.pts[0].p;
1223  m_direction = st.pts[0].direction;
1224  m_placingVia = st.pts[0].placingVias;
1225  m_currentNode = st.commit;
1226  m_currentLayer = st.pts[0].layer;
1229  m_head.RemoveVia( );
1230  m_tail.RemoveVia( );
1231 
1232  if (m_shove)
1233  {
1234  m_shove->RewindSpringbackTo( m_currentNode );
1235  m_shove->UnlockSpringbackNode( m_currentNode );
1236  m_currentNode = m_shove->CurrentNode();
1238  }
1239 
1241 
1242  return true;
1243 }
1244 
1245 
1247 {
1248  return m_placementCorrect || m_fixedTail.StageCount() > 1;
1249 }
1250 
1251 
1253 {
1254  if( m_lastNode )
1256 
1257  m_lastNode = NULL;
1258  m_currentNode = NULL;
1259  return true;
1260 }
1261 
1262 
1263 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1264 {
1265  if( !aLatest.SegmentCount() )
1266  return;
1267 
1268  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1269  return;
1270 
1271  std::set<LINKED_ITEM *> toErase;
1272  aNode->Add( aLatest, true );
1273 
1274  for( int s = 0; s < aLatest.LinkCount(); s++ )
1275  {
1276  auto seg = aLatest.GetLink(s);
1277  LINE ourLine = aNode->AssembleLine( seg );
1278  JOINT a, b;
1279  std::vector<LINE> lines;
1280 
1281  aNode->FindLineEnds( ourLine, a, b );
1282 
1283  if( a == b )
1284  {
1285  aNode->FindLineEnds( aLatest, a, b );
1286  }
1287 
1288  aNode->FindLinesBetweenJoints( a, b, lines );
1289 
1290  int removedCount = 0;
1291  int total = 0;
1292 
1293  for( LINE& line : lines )
1294  {
1295  total++;
1296 
1297  if( !( line.ContainsSegment( seg ) ) && line.SegmentCount() )
1298  {
1299  for( auto ss : line.LinkedSegments() )
1300  toErase.insert( ss );
1301 
1302  removedCount++;
1303  }
1304  }
1305 
1306  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1307  }
1308 
1309  for( auto s : toErase )
1310  aNode->Remove( s );
1311 
1312  aNode->Remove( aLatest );
1313 }
1314 
1315 
1317 {
1318  LINE l = aNode->AssembleLine( aLatest );
1319  SHAPE_LINE_CHAIN simplified( l.CLine() );
1320 
1321  simplified.Simplify();
1322 
1323  if( simplified.PointCount() != l.PointCount() )
1324  {
1325  aNode->Remove( l );
1326  l.SetShape( simplified );
1327  aNode->Add( l );
1328  }
1329 }
1330 
1331 
1333 {
1334  // initPlacement will kill the tail, don't do that unless the track size has changed
1335  if( !m_idle && aSizes.TrackWidth() != m_sizes.TrackWidth() )
1336  {
1337  m_sizes = aSizes;
1338  initPlacement();
1339  }
1340 
1341  m_sizes = aSizes;
1342 }
1343 
1344 
1346 {
1347  LINE current = Trace();
1348  SHAPE_LINE_CHAIN ratLine;
1349  TOPOLOGY topo( m_lastNode );
1350 
1351  if( topo.LeadingRatLine( &current, ratLine ) )
1352  Dbg()->AddLine( ratLine, 5, 10000 );
1353 }
1354 
1355 
1356 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1357 {
1358  m_orthoMode = aOrthoMode;
1359 }
1360 
1361 
1362 bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aInvertPosture )
1363 {
1364  SHAPE_LINE_CHAIN l;
1365  int initial_radius = 0;
1366 
1367  if( m_p_start == aP )
1368  {
1369  l.Clear();
1370  }
1371  else
1372  {
1373  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1374  {
1375  l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1376  }
1377  else
1378  {
1379  // Rounded corners don't make sense when routing orthogonally (single track at a time)
1380  if( Settings().GetRounded() && !m_orthoMode )
1381  initial_radius = Settings().GetMaxRadius();
1382 
1383  if ( aInvertPosture )
1384  l = m_direction.Right().BuildInitialTrace( m_p_start, aP, false, initial_radius );
1385  else
1386  l = m_direction.BuildInitialTrace( m_p_start, aP, false, initial_radius );
1387  }
1388 
1389  if( l.SegmentCount() > 1 && m_orthoMode )
1390  {
1391  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1392 
1393  l.Remove( -1, -1 );
1394  l.SetPoint( 1, newLast );
1395  }
1396  }
1397 
1398  aHead.SetLayer( m_currentLayer );
1399  aHead.SetShape( l );
1400 
1401  if( !m_placingVia )
1402  return true;
1403 
1404  VIA v( makeVia( aP ) );
1405  v.SetNet( aHead.Net() );
1406 
1408  {
1409  aHead.AppendVia( v );
1410  return true;
1411  }
1412 
1413  VECTOR2I force;
1414  VECTOR2I lead = aP - m_p_start;
1415 
1416  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1417 
1418  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1419  {
1420  SHAPE_LINE_CHAIN line = m_direction.BuildInitialTrace( m_p_start, aP + force, initial_radius );
1421  aHead = LINE( aHead, line );
1422 
1423  v.SetPos( v.Pos() + force );
1424  return true;
1425  }
1426 
1427  return false; // via placement unsuccessful
1428 }
1429 
1430 
1431 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1432 {
1433  aNets.push_back( m_currentNet );
1434 }
1435 
1436 
1438 {
1439  m_world->KillChildren();
1440  return true;
1441 }
1442 
1443 FIXED_TAIL::FIXED_TAIL ( int aLineCount )
1444 {
1445 
1446 }
1447 
1449 {
1450 
1451 }
1452 
1454 {
1455  m_stages.clear();
1456 }
1457 
1458 void FIXED_TAIL::AddStage( VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode )
1459 {
1460  STAGE st;
1461  FIX_POINT pt;
1462 
1463  pt.p = aStart;
1464  pt.layer = aLayer;
1465  pt.direction = direction;
1466  pt.placingVias = placingVias;
1467 
1468  st.pts.push_back(pt);
1469  st.commit = aNode;
1470 
1471  m_stages.push_back( st );
1472 }
1473 
1475 {
1476  if( !m_stages.size() )
1477  return false;
1478 
1479 
1480  aStage = m_stages.back();
1481 
1482  if( m_stages.size() > 1 )
1483  m_stages.pop_back();
1484 
1485  return true;
1486 }
1487 
1488 
1490 {
1491  return m_stages.size();
1492 }
1493 
1494 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:144
ITEM.
Definition: pns_item.h:53
bool SmartPads() const
Returns true if Smart Pads (optimized connections) is enabled.
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:51
const SHAPE_ARC & Arc(size_t aArc) const
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
const ITEM_SET Traces() override
Function Traces()
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
std::vector< INTERSECTION > INTERSECTIONS
NODE.
Definition: pns_node.h:145
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 routeStep(const VECTOR2I &aP)
Function routeStep()
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:150
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:154
const SEG CSegment(int aIdx) const
Returns the aIdx-th segment of the line
Definition: pns_line.h:174
bool checkObtusity(const SEG &aA, const SEG &aB) const
Function checkObtusity()
Classes BOARD_ITEM and BOARD_CONNECTED_ITEM.
const std::string Format() const
Function Format() Formats the direction in a human readable word.
Definition: direction45.h:101
bool Is45Degree() const
Definition: pns_line.cpp:408
void CommitRouting()
Definition: pns_router.cpp:422
void removeLoops(NODE *aNode, LINE &aLatest)
Function removeLoops()
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
Ignore collisions, mark obstacles
LINKED_ITEM * GetLink(int aIndex) const
Definition: pns_line.h:231
int FindLinesBetweenJoints(JOINT &aA, JOINT &aB, std::vector< LINE > &aLines)
finds all lines between a pair of joints. Used by the loop removal procedure.
Definition: pns_node.cpp:993
WALKAROUND_STATUS statusCw
const LINE reduceToNearestObstacle(const LINE &aOriginalLine)
virtual LOGGER * Logger()
Returns the logger object, allowing to dump geometry to a file.
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:948
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, bool aSolidsOnly=true, int aMaxIterations=10)
Definition: pns_via.cpp:32
LINE m_head
routing "head": volatile part of the track from the previously analyzed point to the current routing ...
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:68
void RemoveVia()
Definition: pns_line.h:279
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead)
route step, walkaround mode
SIZES_SETTINGS m_sizes
std::vector< FIX_POINT > pts
bool PopStage(STAGE &aStage)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
FIXED_TAIL(int aLineCount=1)
const LINE Trace() const
Function Trace()
void simplifyNewLine(NODE *aNode, SEGMENT *aLatest)
Function simplifyNewLine()
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:859
const SEG & Seg() const
Definition: pns_segment.h:83
bool reduceTail(const VECTOR2I &aEnd)
Function reduceTail()
int Depth() const
Returns the number of nodes in the inheritance chain (wrs to the root node)
Definition: pns_node.h:188
const DIRECTION_45 Right() const
Function Right()
Definition: direction45.h:228
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish) override
Function FixRoute()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
int PointCount() const
Function PointCount()
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
const VECTOR2I & Pos() const
Definition: pns_via.h:100
int PointCount() const
Returns the number of points in the line
Definition: pns_line.h:156
bool RemoveLoops() const
Returns true if loop (redundant track) removal is on.
bool EndsWithVia() const
Definition: pns_line.h:276
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
void SetWidth(int aWidth)
Sets line width
Definition: pns_line.h:180
void SetNet(int aNet)
Definition: pns_item.h:148
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:168
VIATYPE ViaType() const
bool handlePullback()
Function handlePullback()
void SetCollisionMask(int aMask)
LINE_PLACER(ROUTER *aRouter)
bool FollowMouse() const
Returns true if follow mouse mode is active (permanently on for the moment).
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assigns a shape to the line (a polyline/line chain)
Definition: pns_line.h:125
ssize_t ArcIndex(size_t aSegment) const
ROUTING_SETTINGS & Settings() const
Returns current router settings
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
AngleType Angle(const DIRECTION_45 &aOther) const
Function Angle() Returns the type of angle between directions (this) and aOther.
Definition: direction45.h:153
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetApproachCursor(bool aEnabled, const VECTOR2I &aPos)
JOINT.
Definition: pns_joint.h:43
void UpdateSizes(const SIZES_SETTINGS &aSizes) override
Function UpdateSizes()
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:364
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
DIRECTION_45 m_initial_direction
routing direction for new traces
void KillChildren()
Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1288
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
#define NULL
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)
Function setInitialDirection()
int Net() const
Definition: pns_item.h:149
DIRECTION_45.
Definition: direction45.h:37
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Function SplitAdjacentSegments()
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Returns the optimizer effort. Bigger means cleaner traces, but slower routing.
DIRECTION_45 m_direction
current routing direction
void initPlacement()
Function startPlacement()
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
a quick shortcut to optmize a line without creating and setting up an optimizer
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aInvertPosture=false)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:77
const LINE ClipToNearestObstacle(NODE *aNode) const
Clips the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:437
void updateLeadingRatLine()
Function updateLeadingRatLine()
PNS_MODE Mode() const
Returns the routing mode.
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:397
bool routeHead(const VECTOR2I &aP, LINE &aNewHead)
Function routeHead()
void SetSolidsOnly(bool aSolidsOnly)
bool HasPlacedAnything() const override
bool handleSelfIntersections()
Function handleSelfIntersections()
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:142
VECTOR2I closestProjectedPoint(const SHAPE_LINE_CHAIN &line, const VECTOR2I &p)
bool route(const VECTOR2I &aP)
Function route()
std::unique_ptr< SHOVE > m_shove
The shove engine
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)
route step, mark obstacles mode
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead)
route step, shove mode
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape
Definition: pns_line.h:138
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:105
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, int aMaxRadius=0) const
Function BuildInitialTrace()
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:271
Definition: seg.h:39
Only walkaround
NODE * m_currentNode
Current world state
AngleType
Enum AngleType Represents kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:64
void setWorld(NODE *aWorld)
Function setWorld()
bool optimizeTailHeadTransition()
Function optimizeTailHeadTransition()
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Function CurrentNode()
bool ToggleVia(bool aEnabled) override
Function ToggleVia()
void AddStage(VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
const SEG CSegment(int aIndex) const
Function CSegment()
void FlipPosture() override
Function FlipPosture()
bool m_placingVia
Are we placing a via?
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
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:921
VECTOR2I A
Definition: seg.h:47
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:133
int Width() const
Returns line width
Definition: pns_line.h:187
bool SetLayer(int aLayer) override
Function SetLayer()
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Function SetDebugDecorator.
Definition: pns_algo_base.h:72
OPTIMIZER.
Definition: pns_optimizer.h:95
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start point (end of tail, beginning of head)
void SetWorld(NODE *aNode)
bool mergeHead()
Function mergeHead()
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:211
void SetEffortLevel(int aEffort)
bool rhStopAtNearestObstacle(const VECTOR2I &aP, LINE &aNewHead)
void SetOrthoMode(bool aOrthoMode) override
Function SetOrthoMode()
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Function Start()
NODE * Owner() const
Function Owner()
Definition: pns_item.h:173
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
bool AbortPlacement() override
const VIA & Via() const
Definition: pns_line.h:281
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:150
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:62
NODE * GetWorld() const
Definition: pns_router.h:152
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aForceClearance=-1)
Function QueryColliding()
Definition: pns_node.cpp:278
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
void SetIterationLimit(const int aIterLimit)
bool UnfixRoute() override
LAYER_RANGE.
Definition: pns_layerset.h:32
const LAYER_RANGE & Layers() const
Definition: pns_item.h:151
bool IsObtuse(const DIRECTION_45 &aOther) const
Function IsObtuse()
Definition: direction45.h:176
int CountCorners(int aAngles) const
Returns the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:140
int LinkCount() const
Returns the number of segments that were assembled together to form this line.
Definition: pns_line.h:240
VECTOR2I B
Definition: seg.h:48