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 );
699 
700  int effortLevel = OPTIMIZER::MERGE_OBTUSE;
701  if( Settings().SmartPads() )
702  {
703  effortLevel = OPTIMIZER::SMART_PADS;
704  }
705  optimizer.SetEffortLevel( effortLevel );
706 
707  optimizer.SetCollisionMask( ITEM::ANY_T );
708  optimizer.Optimize( &l2 );
709 
710  aNewHead = l2;
711 
712  return true;
713  }
714  else
715  {
716  walkaround.SetWorld( m_currentNode );
717  walkaround.SetSolidsOnly( false );
718  walkaround.SetIterationLimit( 10 );
719  walkaround.SetApproachCursor( true, aP );
720  walkaround.Route( initTrack, l2 );
721  aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
722 
723  return false;
724  }
725 
726  return false;
727 }
728 
729 
730 bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead )
731 {
732  switch( m_currentMode )
733  {
734  case RM_MarkObstacles:
735  return rhMarkObstacles( aP, aNewHead );
736  case RM_Walkaround:
737  return rhWalkOnly( aP, aNewHead );
738  case RM_Shove:
739  return rhShoveOnly( aP, aNewHead );
740  default:
741  break;
742  }
743 
744  return false;
745 }
746 
747 
749 {
750  LINE linetmp = Trace();
751 
753  {
754  if( linetmp.SegmentCount() < 1 )
755  return false;
756 
757  m_head = linetmp;
758  m_p_start = linetmp.CLine().CPoint( 0 );
759  m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
760  m_tail.Line().Clear();
761 
762  return true;
763  }
764 
765  SHAPE_LINE_CHAIN& head = m_head.Line();
766  SHAPE_LINE_CHAIN& tail = m_tail.Line();
767 
768  int tailLookbackSegments = 3;
769 
770  //if(m_currentMode() == RM_Walkaround)
771  // tailLookbackSegments = 10000;
772 
773  int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
774 
775  if( tail.SegmentCount() < 3 )
776  return false;
777 
778  // assemble TailLookbackSegments tail segments with the current head
779  SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
780 
781  int end = std::min(2, head.PointCount() - 1 );
782 
783  opt_line.Append( head.Slice( 0, end ) );
784 
785  LINE new_head( m_tail, opt_line );
786 
787  // and see if it could be made simpler by merging obtuse/collnear segments.
788  // If so, replace the (threshold) last tail points and the head with
789  // the optimized line
790 
792  {
793  LINE tmp( m_tail, opt_line );
794 
795  wxLogTrace( "PNS", "Placer: optimize tail-head [%d]", threshold );
796 
797  head.Clear();
798  tail.Replace( -threshold, -1, new_head.CLine() );
799  tail.Simplify();
800 
801  m_p_start = new_head.CLine().CPoint( -1 );
802  m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
803 
804  return true;
805  }
806 
807  return false;
808 }
809 
810 
812 {
813  bool fail = false;
814  bool go_back = false;
815 
816  int i, n_iter = 1;
817 
818  LINE new_head;
819 
820  wxLogTrace( "PNS", "INIT-DIR: %s head: %d, tail: %d segs",
822 
823  for( i = 0; i < n_iter; i++ )
824  {
825  if( !go_back && Settings().FollowMouse() )
826  reduceTail( aP );
827 
828  go_back = false;
829 
830  if( !routeHead( aP, new_head ) )
831  fail = true;
832 
833  if( !new_head.Is45Degree() )
834  fail = true;
835 
836  if( !Settings().FollowMouse() )
837  return;
838 
839  m_head = new_head;
840 
842  {
843  n_iter++;
844  go_back = true;
845  }
846 
847  if( !go_back && handlePullback() )
848  {
849  n_iter++;
850  go_back = true;
851  }
852 
853  }
854 
855  if( !fail )
856  {
858  return;
859 
860  mergeHead();
861  }
862 }
863 
864 
865 bool LINE_PLACER::route( const VECTOR2I& aP )
866 {
867  routeStep( aP );
868 
869  if (!m_head.PointCount() )
870  return false;
871 
872  return m_head.CPoint(-1) == aP;
873 }
874 
875 
877 {
878  LINE tmp( m_head );
879 
880  tmp.SetShape( m_tail.CLine() );
881  tmp.Line().Append( m_head.CLine() );
882  tmp.Line().Simplify();
883  return tmp;
884 }
885 
886 
888 {
889  m_currentTrace = Trace();
890  return ITEM_SET( &m_currentTrace );
891 }
892 
893 
895 {
897 }
898 
899 
900 NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
901 {
902  if( aLoopsRemoved && m_lastNode )
903  return m_lastNode;
904 
905  return m_currentNode;
906 }
907 
908 
909 bool LINE_PLACER::SplitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP )
910 {
911  if( !aSeg )
912  return false;
913 
914  if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
915  return false;
916 
917  JOINT* jt = aNode->FindJoint( aP, aSeg );
918 
919  if( jt && jt->LinkCount() >= 1 )
920  return false;
921 
922  SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
923 
924  std::unique_ptr< SEGMENT > s_new[2] = {
925  Clone( *s_old ),
926  Clone( *s_old )
927  };
928 
929  s_new[0]->SetEnds( s_old->Seg().A, aP );
930  s_new[1]->SetEnds( aP, s_old->Seg().B );
931 
932  aNode->Remove( s_old );
933  aNode->Add( std::move( s_new[0] ), true );
934  aNode->Add( std::move( s_new[1] ), true );
935 
936  return true;
937 }
938 
939 
940 bool LINE_PLACER::SetLayer( int aLayer )
941 {
942  if( m_idle )
943  {
944  m_currentLayer = aLayer;
945  return true;
946  }
947  else if( m_chainedPlacement )
948  {
949  return false;
950  }
951  else if( !m_startItem || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
952  {
953  m_currentLayer = aLayer;
954  m_head.Line().Clear();
955  m_tail.Line().Clear();
958  Move( m_currentEnd, NULL );
959  return true;
960  }
961 
962  return false;
963 }
964 
965 
966 bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
967 {
968  m_placementCorrect = false;
969  m_currentStart = VECTOR2I( aP );
970  m_currentEnd = VECTOR2I( aP );
971  m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
972  m_startItem = aStartItem;
973  m_placingVia = false;
974  m_chainedPlacement = false;
975  m_fixedTail.Clear();
976 
977  setInitialDirection( Settings().InitialDirection() );
978 
979  initPlacement();
980 
985 
986  NODE *n;
987 
988  if ( m_shove )
989  n = m_shove->CurrentNode();
990  else
991  n = m_currentNode;
992 
994 
995  return true;
996 }
997 
998 
1000 {
1001  m_idle = false;
1002 
1003  m_head.Line().Clear();
1004  m_tail.Line().Clear();
1011  m_head.RemoveVia();
1012  m_tail.RemoveVia();
1013 
1016 
1017  NODE* world = Router()->GetWorld();
1018 
1019  world->KillChildren();
1020  NODE* rootNode = world->Branch();
1021 
1023 
1024  setWorld( rootNode );
1025 
1026  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
1027  m_world, m_direction.Format().c_str(), m_currentLayer );
1028 
1029  m_lastNode = NULL;
1031  m_currentMode = Settings().Mode();
1032 
1033  m_shove.reset();
1034 
1036  {
1037  m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1038  }
1039 }
1040 
1041 
1042 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
1043 {
1044  LINE current;
1045  VECTOR2I p = aP;
1046  int eiDepth = -1;
1047 
1048  if( aEndItem && aEndItem->Owner() )
1049  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
1050 
1051  if( m_lastNode )
1052  {
1053  delete m_lastNode;
1054  m_lastNode = NULL;
1055  }
1056 
1057  bool reachesEnd = route( p );
1058 
1059  current = Trace();
1060 
1061  if( !current.PointCount() )
1063  else
1064  m_currentEnd = current.CLine().CPoint( -1 );
1065 
1066  NODE* latestNode = m_currentNode;
1067  m_lastNode = latestNode->Branch();
1068 
1069  if( reachesEnd && eiDepth >= 0 && aEndItem && latestNode->Depth() > eiDepth && current.SegmentCount() )
1070  {
1071  SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1072 
1073  if( Settings().RemoveLoops() )
1074  removeLoops( m_lastNode, current );
1075  }
1076 
1079  return true;
1080 }
1081 
1082 
1083 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1084 {
1085  bool realEnd = false;
1086  int lastV;
1087 
1088  LINE pl = Trace();
1089 
1091  {
1092  // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1093  // user has more responsibility and authority.
1094 
1095  if( aEndItem )
1096  {
1097  // The user has indicated a connection should be made. If either the
1098  // trace or endItem is netless, then allow the connection by adopting the net of the other.
1099  if( m_currentNet <= 0 )
1100  {
1101  m_currentNet = aEndItem->Net();
1102  pl.SetNet( m_currentNet );
1103  }
1104  else if (aEndItem->Net() <= 0 )
1105  aEndItem->SetNet( m_currentNet );
1106  }
1107 
1108  // Collisions still prevent fixing unless "Allow DRC violations" is checked
1109  if( !Settings().CanViolateDRC() && m_world->CheckColliding( &pl ) )
1110  return false;
1111  }
1112 
1113  const SHAPE_LINE_CHAIN& l = pl.CLine();
1114 
1115  if( !l.SegmentCount() )
1116  {
1117  // Nothing to commit if we have an empty line
1118  if( !pl.EndsWithVia() )
1119  return false;
1120 
1121  m_lastNode->Add( Clone( pl.Via() ) );
1122  m_currentNode = NULL;
1123 
1124  m_idle = true;
1125  m_placementCorrect = true;
1126  return true;
1127  }
1128 
1129  VECTOR2I p_pre_last = l.CPoint( -1 );
1130  const VECTOR2I p_last = l.CPoint( -1 );
1131  DIRECTION_45 d_last( l.CSegment( -1 ) );
1132 
1133  if( l.PointCount() > 2 )
1134  p_pre_last = l.CPoint( -2 );
1135 
1136  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1137  realEnd = true;
1138 
1139  if( aForceFinish )
1140  realEnd = true;
1141 
1142  if( realEnd || m_placingVia )
1143  lastV = l.SegmentCount();
1144  else
1145  lastV = std::max( 1, l.SegmentCount() - 1 );
1146 
1147  SEGMENT* lastSeg = nullptr;
1148  int lastArc = -1;
1149 
1150  for( int i = 0; i < lastV; i++ )
1151  {
1152  ssize_t arcIndex = l.ArcIndex( i );
1153 
1154  if( arcIndex < 0 )
1155  {
1156  const SEG& s = pl.CSegment( i );
1157  auto seg = std::make_unique<SEGMENT>( s, m_currentNet );
1158  seg->SetWidth( pl.Width() );
1159  seg->SetLayer( m_currentLayer );
1160  if( !m_lastNode->Add( std::move( seg ) ) )
1161  lastSeg = nullptr;
1162  }
1163  else
1164  {
1165  if( arcIndex == lastArc )
1166  continue;
1167 
1168  auto arc = std::make_unique<ARC>( l.Arc( arcIndex ), m_currentNet );
1169  arc->SetWidth( pl.Width() );
1170  arc->SetLayer( m_currentLayer );
1171  m_lastNode->Add( std::move( arc ) );
1172  lastSeg = nullptr;
1173  lastArc = arcIndex;
1174  }
1175  }
1176 
1177  if( pl.EndsWithVia() )
1178  {
1179  m_lastNode->Add( Clone( pl.Via() ) );
1180  }
1181 
1182  if( realEnd && lastSeg )
1183  simplifyNewLine( m_lastNode, lastSeg );
1184 
1185 
1186  if( !realEnd )
1187  {
1188  setInitialDirection( d_last );
1189  m_currentStart = m_placingVia ? p_last : p_pre_last;
1190 
1192 
1193  m_startItem = NULL;
1194  m_placingVia = false;
1196 
1199 
1200  m_head.Line().Clear();
1201  m_tail.Line().Clear();
1202  m_head.RemoveVia();
1203  m_tail.RemoveVia();
1206 
1207  if ( m_shove )
1208  {
1209  m_shove->AddLockedSpringbackNode( m_currentNode );
1210  }
1211 
1212 
1217 
1218  m_placementCorrect = true;
1219  }
1220  else
1221  {
1222  m_placementCorrect = true;
1223  m_idle = true;
1224  }
1225 
1226  return realEnd;
1227 }
1228 
1229 
1231 {
1232  FIXED_TAIL::STAGE st;
1233 
1234  if ( !m_fixedTail.PopStage( st ) )
1235  return false;
1236 
1237  m_head.Line().Clear();
1238  m_tail.Line().Clear();
1239  m_startItem = NULL;
1240  m_p_start = st.pts[0].p;
1241  m_direction = st.pts[0].direction;
1242  m_placingVia = st.pts[0].placingVias;
1243  m_currentNode = st.commit;
1244  m_currentLayer = st.pts[0].layer;
1247  m_head.RemoveVia( );
1248  m_tail.RemoveVia( );
1249 
1250  if (m_shove)
1251  {
1252  m_shove->RewindSpringbackTo( m_currentNode );
1253  m_shove->UnlockSpringbackNode( m_currentNode );
1254  m_currentNode = m_shove->CurrentNode();
1256  }
1257 
1259 
1260  return true;
1261 }
1262 
1263 
1265 {
1266  return m_placementCorrect || m_fixedTail.StageCount() > 1;
1267 }
1268 
1269 
1271 {
1272  if( m_lastNode )
1274 
1275  m_lastNode = NULL;
1276  m_currentNode = NULL;
1277  return true;
1278 }
1279 
1280 
1281 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1282 {
1283  if( !aLatest.SegmentCount() )
1284  return;
1285 
1286  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1287  return;
1288 
1289  std::set<LINKED_ITEM *> toErase;
1290  aNode->Add( aLatest, true );
1291 
1292  for( int s = 0; s < aLatest.LinkCount(); s++ )
1293  {
1294  auto seg = aLatest.GetLink(s);
1295  LINE ourLine = aNode->AssembleLine( seg );
1296  JOINT a, b;
1297  std::vector<LINE> lines;
1298 
1299  aNode->FindLineEnds( ourLine, a, b );
1300 
1301  if( a == b )
1302  {
1303  aNode->FindLineEnds( aLatest, a, b );
1304  }
1305 
1306  aNode->FindLinesBetweenJoints( a, b, lines );
1307 
1308  int removedCount = 0;
1309  int total = 0;
1310 
1311  for( LINE& line : lines )
1312  {
1313  total++;
1314 
1315  if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1316  {
1317  for( auto ss : line.Links() )
1318  toErase.insert( ss );
1319 
1320  removedCount++;
1321  }
1322  }
1323 
1324  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1325  }
1326 
1327  for( auto s : toErase )
1328  aNode->Remove( s );
1329 
1330  aNode->Remove( aLatest );
1331 }
1332 
1333 
1335 {
1336  LINE l = aNode->AssembleLine( aLatest );
1337  SHAPE_LINE_CHAIN simplified( l.CLine() );
1338 
1339  simplified.Simplify();
1340 
1341  if( simplified.PointCount() != l.PointCount() )
1342  {
1343  aNode->Remove( l );
1344  l.SetShape( simplified );
1345  aNode->Add( l );
1346  }
1347 }
1348 
1349 
1351 {
1352  // initPlacement will kill the tail, don't do that unless the track size has changed
1353  if( !m_idle && aSizes.TrackWidth() != m_sizes.TrackWidth() )
1354  {
1355  m_sizes = aSizes;
1356  initPlacement();
1357  }
1358 
1359  m_sizes = aSizes;
1360 }
1361 
1362 
1364 {
1365  LINE current = Trace();
1366  SHAPE_LINE_CHAIN ratLine;
1367  TOPOLOGY topo( m_lastNode );
1368 
1369  if( topo.LeadingRatLine( &current, ratLine ) )
1370  Dbg()->AddLine( ratLine, 5, 10000 );
1371 }
1372 
1373 
1374 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1375 {
1376  m_orthoMode = aOrthoMode;
1377 }
1378 
1379 
1381 {
1382  SHAPE_LINE_CHAIN l;
1383  int initial_radius = 0;
1384 
1385  auto guessedDir = m_postureSolver.GetPosture( aP );
1386 
1387  if( m_p_start == aP )
1388  {
1389  l.Clear();
1390  }
1391  else
1392  {
1393  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1394  {
1395  l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1396  }
1397  else
1398  {
1399  // Rounded corners don't make sense when routing orthogonally (single track at a time)
1400  if( Settings().GetRounded() && !m_orthoMode )
1401  initial_radius = Settings().GetMaxRadius();
1402 
1403 
1404  if( !m_tail.PointCount() )
1405  l = guessedDir.BuildInitialTrace( m_p_start, aP, false, initial_radius );
1406  else
1407  l = m_direction.BuildInitialTrace( m_p_start, aP, false, initial_radius );
1408  }
1409 
1410  if( l.SegmentCount() > 1 && m_orthoMode )
1411  {
1412  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1413 
1414  l.Remove( -1, -1 );
1415  l.SetPoint( 1, newLast );
1416  }
1417  }
1418 
1419  aHead.SetLayer( m_currentLayer );
1420  aHead.SetShape( l );
1421 
1422  if( !m_placingVia )
1423  return true;
1424 
1425  VIA v( makeVia( aP ) );
1426  v.SetNet( aHead.Net() );
1427 
1429  {
1430  aHead.AppendVia( v );
1431  return true;
1432  }
1433 
1434  VECTOR2I force;
1435  VECTOR2I lead = aP - m_p_start;
1436 
1437  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1438 
1439  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1440  {
1441  SHAPE_LINE_CHAIN line = m_direction.BuildInitialTrace( m_p_start, aP + force, initial_radius );
1442  aHead = LINE( aHead, line );
1443 
1444  v.SetPos( v.Pos() + force );
1445  return true;
1446  }
1447 
1448  return false; // via placement unsuccessful
1449 }
1450 
1451 
1452 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1453 {
1454  aNets.push_back( m_currentNet );
1455 }
1456 
1457 
1459 {
1460  m_world->KillChildren();
1461  return true;
1462 }
1463 
1464 FIXED_TAIL::FIXED_TAIL ( int aLineCount )
1465 {
1466 
1467 }
1468 
1470 {
1471 
1472 }
1473 
1475 {
1476  m_stages.clear();
1477 }
1478 
1479 void FIXED_TAIL::AddStage( VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode )
1480 {
1481  STAGE st;
1482  FIX_POINT pt;
1483 
1484  pt.p = aStart;
1485  pt.layer = aLayer;
1486  pt.direction = direction;
1487  pt.placingVias = placingVias;
1488 
1489  st.pts.push_back(pt);
1490  st.commit = aNode;
1491 
1492  m_stages.push_back( st );
1493 }
1494 
1496 {
1497  if( !m_stages.size() )
1498  return false;
1499 
1500 
1501  aStage = m_stages.back();
1502 
1503  if( m_stages.size() > 1 )
1504  m_stages.pop_back();
1505 
1506  return true;
1507 }
1508 
1509 
1511 {
1512  return m_stages.size();
1513 }
1514 
1516 {
1517  m_forced = false;
1518  m_tollerance = 0;
1519 }
1520 
1522 
1524 {
1525  m_forced = false;
1526  m_trail.Clear();
1527 }
1528 
1530 {
1531  if( m_trail.SegmentCount() == 0 )
1532  {
1533  m_trail.Append(aP);
1534  } else {
1535  SEG s_new ( m_trail.CPoint(-1), aP );
1536 
1537  for( int i = 0; i < m_trail.SegmentCount() - 1; i++ )
1538  {
1539  const auto& s_trail = m_trail.CSegment(i);
1540  if( s_trail.Distance( s_new ) <= m_tollerance )
1541  {
1542  m_trail = m_trail.Slice( 0, i );
1543  break;
1544  }
1545  }
1546 
1547  m_trail.Append( aP );
1548  }
1549 
1550  m_trail.Simplify();
1551 
1553 
1554  dbg->AddLine(m_trail, 5, 100000 );
1555 
1556 }
1557 
1559 {
1560  if( m_trail.PointCount() < 2)
1561  return m_initDirection;
1562 
1564 
1565  auto p0 = m_trail.CPoint(0);
1566  auto bb = m_trail.BBox();
1567 
1568  double refArea = bb.GetArea();
1569 
1570 
1571  SHAPE_LINE_CHAIN straight( DIRECTION_45().BuildInitialTrace( p0, aP, false ) );
1572  straight.SetClosed(true);
1573  straight.Append(m_trail.Reverse());
1574  dbg->AddLine(straight, 2, 100000 );
1575 
1576  double areaS = straight.Area();
1577 
1578  SHAPE_LINE_CHAIN diag ( DIRECTION_45().BuildInitialTrace( p0, aP, true ) );
1579  diag.Append(m_trail.Reverse());
1580  diag.SetClosed(true);
1581  dbg->AddLine(diag, 1, 100000 );
1582 
1583  double areaDiag = diag.Area();
1584  double ratio = abs(areaS) / (fabs(areaDiag) + 1.0);
1585 
1586  printf("posture forced %d initdir %s\n", !!m_forced, m_initDirection.Format().c_str() );
1587 
1588  // heuristic to detect that the user dragged back the cursor to the beginning of the trace
1589  // in this case, we cancel any forced posture
1590  if( sqrt(refArea) < 4 * m_tollerance )
1591  {
1592  m_forced = false;
1593  }
1594 
1595  if( m_forced )
1596  return m_initDirection;
1597  else if( ratio > areaRatioThreshold)
1598  return DIRECTION_45::NE;
1599  else if ( ratio < 1.0 / areaRatioThreshold )
1600  return DIRECTION_45::N;
1602  return m_lastSegDirection;
1603  else
1604  return m_initDirection;
1605 
1606 }
1607 
1608 
1610 {
1612  m_forced = true;
1613 }
1614 
1615 
1616 }
1617 
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:149
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:155
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
DIRECTION_45 m_lastSegDirection
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:179
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:402
void CommitRouting()
Definition: pns_router.cpp:443
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
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:237
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)
POSTURE_SOLVER m_postureSolver
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:839
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
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead)
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:161
bool RemoveLoops() const
Returns true if loop (redundant track) removal is on.
bool EndsWithVia() const
Definition: pns_line.h:234
DIRECTION_45 GetPosture(const VECTOR2I &aP)
SHAPE_LINE_CHAIN m_trail
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:185
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:173
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:130
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
void SetTollerance(int toll)
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetClosed(bool aClosed)
Function SetClosed()
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:362
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
const BOX2I BBox(int aClearance=0) const override
Function BBox()
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()
void AddTrailPoint(const VECTOR2I &aP)
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
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:77
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
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:431
const double areaRatioThreshold
void updateLeadingRatLine()
Function updateLeadingRatLine()
PNS_MODE Mode() const
Returns the routing mode.
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:395
bool routeHead(const VECTOR2I &aP, LINE &aNewHead)
Function routeHead()
void SetSolidsOnly(bool aSolidsOnly)
bool HasPlacedAnything() const override
DIRECTION_45 m_initDirection
ecoord_type GetArea() const
Function GetArea returns the area of the rectangle.
Definition: box2.h:427
bool handleSelfIntersections()
Function handleSelfIntersections()
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:147
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:143
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
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
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:901
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:192
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:239
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:154
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
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:233
void SetIterationLimit(const int aIterLimit)
bool UnfixRoute() override
static ROUTER * GetInstance()
Definition: pns_router.cpp:85
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:134
VECTOR2I B
Definition: seg.h:48