KiCad PCB EDA Suite
pns_shove.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016 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 #define PNS_DEBUG
23 
24 #include <deque>
25 #include <cassert>
26 
27 #include "range.h"
28 
29 #include "pns_line.h"
30 #include "pns_node.h"
31 #include "pns_walkaround.h"
32 #include "pns_shove.h"
33 #include "pns_solid.h"
34 #include "pns_optimizer.h"
35 #include "pns_via.h"
36 #include "pns_utils.h"
37 #include "pns_router.h"
38 #include "pns_shove.h"
39 #include "pns_utils.h"
40 #include "pns_topology.h"
41 
42 #include "time_limit.h"
43 
44 #include <profile.h>
45 
46 namespace PNS {
47 
48 void SHOVE::replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew )
49 {
50  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
51 
52  if( changed_area )
53  {
54  m_affectedAreaSum = m_affectedAreaSum ? m_affectedAreaSum->Merge( *changed_area ) : *changed_area;
55  }
56 
57  m_currentNode->Replace( aOld, std::move( aNew ) );
58 }
59 
60 void SHOVE::replaceLine( LINE& aOld, LINE& aNew )
61 {
62  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
63 
64  if( changed_area )
65  {
66  m_affectedAreaSum = m_affectedAreaSum ? m_affectedAreaSum->Merge( *changed_area ) : *changed_area;
67  }
68 
69  m_currentNode->Replace( aOld, aNew );
70 }
71 
72 int SHOVE::getClearance( const ITEM* aA, const ITEM* aB ) const
73 {
74  if( m_forceClearance >= 0 )
75  return m_forceClearance;
76 
77  return m_currentNode->GetClearance( aA, aB );
78 }
79 
80 
81 void SHOVE::sanityCheck( LINE* aOld, LINE* aNew )
82 {
83  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
84  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
85 }
86 
87 
88 SHOVE::SHOVE( NODE* aWorld, ROUTER* aRouter ) :
89  ALGO_BASE( aRouter )
90 {
91  m_forceClearance = -1;
92  m_root = aWorld;
93  m_currentNode = aWorld;
94 
95  // Initialize other temporary variables:
96  m_draggedVia = NULL;
97  m_iter = 0;
98  m_multiLineMode = false;
99 }
100 
101 
103 {
104 }
105 
106 
107 LINE SHOVE::assembleLine( const SEGMENT* aSeg, int* aIndex )
108 {
109  return m_currentNode->AssembleLine( const_cast<SEGMENT*>( aSeg ), aIndex, true );
110 }
111 
112 // A dumb function that checks if the shoved line is shoved the right way, e.g.
113 // visually "outwards" of the line/via applying pressure on it. Unfortunately there's no
114 // mathematical concept of orientation of an open curve, so we use some primitive heuristics:
115 // if the shoved line wraps around the start of the "pusher", it's likely shoved in wrong direction.
116 bool SHOVE::checkBumpDirection( const LINE& aCurrent, const LINE& aShoved ) const
117 {
118  const SEG& ss = aCurrent.CSegment( 0 );
119 
120  int dist = getClearance( &aCurrent, &aShoved ) + PNS_HULL_MARGIN;
121 
122  dist += aCurrent.Width() / 2;
123  dist += aShoved.Width() / 2;
124 
125  const VECTOR2I ps = ss.A - ( ss.B - ss.A ).Resize( dist );
126 
127  return !aShoved.CLine().PointOnEdge( ps );
128 }
129 
130 
132  LINE& aShoved )
133 {
134  int clearance = getClearance( &aCurrent, &aObstacle );
135  const SHAPE_LINE_CHAIN hull = aCurrent.Via().Hull( clearance, aObstacle.Width() );
136  SHAPE_LINE_CHAIN path_cw, path_ccw;
137 
138  aObstacle.Walkaround( hull, path_cw, true );
139  aObstacle.Walkaround( hull, path_ccw, false );
140 
141  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
142 
143  if( shortest.PointCount() < 2 )
144  return SH_INCOMPLETE;
145 
146  if( aObstacle.CPoint( -1 ) != shortest.CPoint( -1 ) )
147  return SH_INCOMPLETE;
148 
149  if( aObstacle.CPoint( 0 ) != shortest.CPoint( 0 ) )
150  return SH_INCOMPLETE;
151 
152  aShoved.SetShape( shortest );
153 
154  if( m_currentNode->CheckColliding( &aShoved, &aCurrent ) )
155  return SH_INCOMPLETE;
156 
157  return SH_OK;
158 }
159 
160 
162  LINE& aShoved, const HULL_SET& aHulls )
163 {
164  const SHAPE_LINE_CHAIN& obs = aObstacle.CLine();
165 
166  int attempt;
167 
168  for( attempt = 0; attempt < 4; attempt++ )
169  {
170  bool invertTraversal = ( attempt >= 2 );
171  bool clockwise = attempt % 2;
172  int vFirst = -1, vLast = -1;
173 
174  SHAPE_LINE_CHAIN path;
175  LINE l( aObstacle );
176 
177  for( int i = 0; i < (int) aHulls.size(); i++ )
178  {
179  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
180 
181  l.Walkaround( hull, path, clockwise );
182  path.Simplify();
183  l.SetShape( path );
184  }
185 
186  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
187  {
188  if( path.CPoint( i ) != obs.CPoint( i ) )
189  {
190  vFirst = i;
191  break;
192  }
193  }
194 
195  int k = obs.PointCount() - 1;
196  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
197  {
198  if( path.CPoint( i ) != obs.CPoint( k ) )
199  {
200  vLast = i;
201  break;
202  }
203  }
204 
205  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacle.CLine() ) )
206  {
207  wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
208  continue;
209  }
210 
211  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
212  {
213  wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
214  continue;
215  }
216 
217  if( !checkBumpDirection( aCurrent, l ) )
218  {
219  wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
220  aShoved.SetShape( l.CLine() );
221 
222  continue;
223  }
224 
225  if( path.SelfIntersecting() )
226  {
227  wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
228  continue;
229  }
230 
231  bool colliding = m_currentNode->CheckColliding( &l, &aCurrent, ITEM::ANY_T, m_forceClearance );
232 
233  if( ( aCurrent.Marker() & MK_HEAD ) && !colliding )
234  {
235  JOINT* jtStart = m_currentNode->FindJoint( aCurrent.CPoint( 0 ), &aCurrent );
236 
237  for( ITEM* item : jtStart->LinkList() )
238  {
239  if( m_currentNode->CheckColliding( item, &l ) )
240  colliding = true;
241  }
242  }
243 
244  if( colliding )
245  {
246  wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
247  continue;
248  }
249 
250  aShoved.SetShape( l.CLine() );
251 
252  return SH_OK;
253  }
254 
255  return SH_INCOMPLETE;
256 }
257 
258 
260  LINE& aShoved )
261 {
262  aShoved.ClearSegmentLinks();
263 
264  bool obstacleIsHead = false;
265 
266  for( SEGMENT* s : aObstacle.LinkedSegments() )
267  {
268  if( s->Marker() & MK_HEAD )
269  {
270  obstacleIsHead = true;
271  break;
272  }
273  }
274 
275  SHOVE_STATUS rv;
276 
277  bool viaOnEnd = aCurrent.EndsWithVia();
278 
279  if( viaOnEnd && ( !aCurrent.LayersOverlap( &aObstacle ) || aCurrent.SegmentCount() == 0 ) )
280  {
281  rv = walkaroundLoneVia( aCurrent, aObstacle, aShoved );
282  }
283  else
284  {
285  int w = aObstacle.Width();
286  int n_segs = aCurrent.SegmentCount();
287 
288  int clearance = getClearance( &aCurrent, &aObstacle ) + 1;
289 
290  HULL_SET hulls;
291 
292  hulls.reserve( n_segs + 1 );
293 
294  for( int i = 0; i < n_segs; i++ )
295  {
296  SEGMENT seg( aCurrent, aCurrent.CSegment( i ) );
297  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, w );
298 
299  hulls.push_back( hull );
300  }
301 
302  if( viaOnEnd )
303  hulls.push_back( aCurrent.Via().Hull( clearance, w ) );
304 
305  rv = processHullSet( aCurrent, aObstacle, aShoved, hulls );
306  }
307 
308  if( obstacleIsHead )
309  aShoved.Mark( aShoved.Marker() | MK_HEAD );
310 
311  return rv;
312 }
313 
314 
316 {
317  int segIndex;
318  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
319  LINE shovedLine( obstacleLine );
320  SEGMENT tmp( *aObstacleSeg );
321 
322  if( obstacleLine.HasLockedSegments() )
323  return SH_TRY_WALK;
324 
325  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
326 
327  const double extensionWalkThreshold = 1.0;
328 
329  double obsLen = obstacleLine.CLine().Length();
330  double shovedLen = shovedLine.CLine().Length();
331  double extensionFactor = 0.0;
332 
333  if( obsLen != 0.0f )
334  extensionFactor = shovedLen / obsLen - 1.0;
335 
336  if( extensionFactor > extensionWalkThreshold )
337  return SH_TRY_WALK;
338 
339  assert( obstacleLine.LayersOverlap( &shovedLine ) );
340 
341 #ifdef DEBUG
342  m_logger.NewGroup( "on-colliding-segment", m_iter );
343  m_logger.Log( &tmp, 0, "obstacle-segment" );
344  m_logger.Log( &aCurrent, 1, "current-line" );
345  m_logger.Log( &obstacleLine, 2, "obstacle-line" );
346  m_logger.Log( &shovedLine, 3, "shoved-line" );
347 #endif
348 
349  if( rv == SH_OK )
350  {
351  if( shovedLine.Marker() & MK_HEAD )
352  {
353  if( m_multiLineMode )
354  return SH_INCOMPLETE;
355 
356  m_newHead = shovedLine;
357  }
358 
359  int rank = aCurrent.Rank();
360  shovedLine.SetRank( rank - 1 );
361 
362  sanityCheck( &obstacleLine, &shovedLine );
363  replaceLine( obstacleLine, shovedLine );
364 
365  if( !pushLine( shovedLine ) )
366  rv = SH_INCOMPLETE;
367  }
368 
369  return rv;
370 }
371 
372 
374 {
375  LINE shovedLine( aObstacle );
376 
377  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, aObstacle, shovedLine );
378 
379  #ifdef DEBUG
380  m_logger.NewGroup( "on-colliding-line", m_iter );
381  m_logger.Log( &aObstacle, 0, "obstacle-line" );
382  m_logger.Log( &aCurrent, 1, "current-line" );
383  m_logger.Log( &shovedLine, 3, "shoved-line" );
384  #endif
385 
386  if( rv == SH_OK )
387  {
388  if( shovedLine.Marker() & MK_HEAD )
389  {
390  if( m_multiLineMode )
391  return SH_INCOMPLETE;
392 
393  m_newHead = shovedLine;
394  }
395 
396  sanityCheck( &aObstacle, &shovedLine );
397  replaceLine( aObstacle, shovedLine );
398 
399  int rank = aObstacle.Rank();
400  shovedLine.SetRank( rank - 1 );
401 
402 
403  if( !pushLine( shovedLine ) )
404  {
405  rv = SH_INCOMPLETE;
406  }
407  }
408 
409  return rv;
410 }
411 
413 {
414  WALKAROUND walkaround( m_currentNode, Router() );
415  LINE walkaroundLine( aCurrent );
416 
417  if( aCurrent.EndsWithVia() )
418  {
419  VIA vh = aCurrent.Via();
420  VIA* via = NULL;
421  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
422 
423  if( !jtStart )
424  return SH_INCOMPLETE;
425 
426  for( ITEM* item : jtStart->LinkList() )
427  {
428  if( item->OfKind( ITEM::VIA_T ) )
429  {
430  via = (VIA*) item;
431  break;
432  }
433  }
434 
435  if( via && m_currentNode->CheckColliding( via, aObstacle ) )
436  return onCollidingVia( aObstacle, via );
437  }
438 
439  TOPOLOGY topo( m_currentNode );
440 
441  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
442 
443 #ifdef DEBUG
444  m_logger.NewGroup( "on-colliding-solid-cluster", m_iter );
445  for( ITEM* item : cluster )
446  {
447  m_logger.Log( item, 0, "cluster-entry" );
448  }
449 #endif
450 
451  walkaround.SetSolidsOnly( false );
452  walkaround.RestrictToSet( true, cluster );
453  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
454 
455  int currentRank = aCurrent.Rank();
456  int nextRank;
457 
458  bool success = false;
459 
460  for( int attempt = 0; attempt < 2; attempt++ )
461  {
462  if( attempt == 1 || Settings().JumpOverObstacles() )
463  {
464 
465  nextRank = currentRank - 1;
466  walkaround.SetSingleDirection( true );
467  }
468  else
469  {
470  nextRank = currentRank + 10000;
471  walkaround.SetSingleDirection( false );
472  }
473 
474 
475  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
476 
477  if( status != WALKAROUND::DONE )
478  continue;
479 
480  walkaroundLine.ClearSegmentLinks();
481  walkaroundLine.Unmark();
482  walkaroundLine.Line().Simplify();
483 
484  if( walkaroundLine.HasLoops() )
485  continue;
486 
487  if( aCurrent.Marker() & MK_HEAD )
488  {
489  walkaroundLine.Mark( MK_HEAD );
490 
491  if( m_multiLineMode )
492  continue;
493 
494  m_newHead = walkaroundLine;
495  }
496 
497  sanityCheck( &aCurrent, &walkaroundLine );
498 
499  if( !m_lineStack.empty() )
500  {
501  LINE lastLine = m_lineStack.front();
502 
503  if( m_currentNode->CheckColliding( &lastLine, &walkaroundLine ) )
504  {
505  LINE dummy( lastLine );
506 
507  if( ProcessSingleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
508  {
509  success = true;
510  break;
511  }
512  } else {
513  success = true;
514  break;
515  }
516  }
517  }
518 
519  if(!success)
520  return SH_INCOMPLETE;
521 
522  replaceLine( aCurrent, walkaroundLine );
523  walkaroundLine.SetRank( nextRank );
524 
525 #ifdef DEBUG
526  m_logger.NewGroup( "on-colliding-solid", m_iter );
527  m_logger.Log( aObstacle, 0, "obstacle-solid" );
528  m_logger.Log( &aCurrent, 1, "current-line" );
529  m_logger.Log( &walkaroundLine, 3, "walk-line" );
530 #endif
531 
532  popLine();
533 
534  if( !pushLine( walkaroundLine ) )
535  return SH_INCOMPLETE;
536 
537  return SH_OK;
538 }
539 
540 
541 bool SHOVE::reduceSpringback( const ITEM_SET& aHeadSet )
542 {
543  bool rv = false;
544 
545  while( !m_nodeStack.empty() )
546  {
547  SPRINGBACK_TAG spTag = m_nodeStack.back();
548 
549  if( !spTag.m_node->CheckColliding( aHeadSet ) )
550  {
551  rv = true;
552 
553  delete spTag.m_node;
554  m_nodeStack.pop_back();
555  }
556  else
557  break;
558  }
559 
560  return rv;
561 }
562 
563 
564 bool SHOVE::pushSpringback( NODE* aNode, const ITEM_SET& aHeadItems,
565  const COST_ESTIMATOR& aCost, const OPT_BOX2I& aAffectedArea )
566 {
567  SPRINGBACK_TAG st;
568  OPT_BOX2I prev_area;
569 
570  if( !m_nodeStack.empty() )
571  prev_area = m_nodeStack.back().m_affectedArea;
572 
573  st.m_node = aNode;
574  st.m_cost = aCost;
575  st.m_headItems = aHeadItems;
576 
577  if( aAffectedArea )
578  {
579  if( prev_area )
580  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
581  else
582  st.m_affectedArea = aAffectedArea;
583  } else
584  st.m_affectedArea = prev_area;
585 
586  m_nodeStack.push_back( st );
587 
588  return true;
589 }
590 
591 
592 SHOVE::SHOVE_STATUS SHOVE::pushVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank, bool aDryRun )
593 {
594  LINE_PAIR_VEC draggedLines;
595  VECTOR2I p0( aVia->Pos() );
596  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
597  VECTOR2I p0_pushed( p0 + aForce );
598 
599  if( !jt )
600  {
601  wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
602  return SH_INCOMPLETE;
603  }
604 
605  if( aVia->IsLocked() )
606  return SH_TRY_WALK;
607 
608  if( jt->IsLocked() )
609  return SH_INCOMPLETE;
610 
611  // nothing to push...
612  if ( aForce.x == 0 && aForce.y == 0 )
613  return SH_OK;
614 
615  while( aForce.x != 0 || aForce.y != 0 )
616  {
617  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
618 
619  if( !jt_next )
620  break;
621 
622  p0_pushed += aForce.Resize( 2 ); // make sure pushed via does not overlap with any existing joint
623  }
624 
625  std::unique_ptr< VIA > pushedVia = Clone( *aVia );
626  pushedVia->SetPos( p0_pushed );
627  pushedVia->Mark( aVia->Marker() );
628 
629  for( ITEM* item : jt->LinkList() )
630  {
631  if( SEGMENT* seg = dyn_cast<SEGMENT*>( item ) )
632  {
633  LINE_PAIR lp;
634  int segIndex;
635 
636  lp.first = assembleLine( seg, &segIndex );
637 
638  if( lp.first.HasLockedSegments() )
639  return SH_TRY_WALK;
640 
641  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
642 
643  if( segIndex == 0 )
644  lp.first.Reverse();
645 
646  lp.second = lp.first;
647  lp.second.ClearSegmentLinks();
648  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
649  lp.second.AppendVia( *pushedVia );
650  draggedLines.push_back( lp );
651 
652  if( aVia->Marker() & MK_HEAD )
653  m_draggedViaHeadSet.Add( lp.second );
654  }
655  }
656 
657  m_draggedViaHeadSet.Add( pushedVia.get() );
658 
659  if( aDryRun )
660  return SH_OK;
661 
662 #ifdef DEBUG
663  m_logger.Log( aVia, 0, "obstacle-via" );
664 #endif
665 
666  pushedVia->SetRank( aCurrentRank - 1 );
667 
668 #ifdef DEBUG
669  m_logger.Log( pushedVia.get(), 1, "pushed-via" );
670 #endif
671 
672  if( aVia->Marker() & MK_HEAD )
673  {
674  m_draggedVia = pushedVia.get();
676  }
677 
678  replaceItems( aVia, std::move( pushedVia ) );
679 
680  for( LINE_PAIR lp : draggedLines )
681  {
682  if( lp.first.Marker() & MK_HEAD )
683  {
684  lp.second.Mark( MK_HEAD );
685 
686  if( m_multiLineMode )
687  return SH_INCOMPLETE;
688 
689  m_newHead = lp.second;
690  }
691 
692  unwindStack( &lp.first );
693 
694  if( lp.second.SegmentCount() )
695  {
696  replaceLine( lp.first, lp.second );
697  lp.second.SetRank( aCurrentRank - 1 );
698 
699  if( !pushLine( lp.second, true ) )
700  return SH_INCOMPLETE;
701  }
702  else
703  {
704  m_currentNode->Remove( lp.first );
705  }
706 
707 #ifdef DEBUG
708  m_logger.Log( &lp.first, 2, "fan-pre" );
709  m_logger.Log( &lp.second, 3, "fan-post" );
710 #endif
711  }
712 
713  return SH_OK;
714 }
715 
716 
718 {
719  int clearance = getClearance( aCurrent, aObstacleVia ) ;
720  LINE_PAIR_VEC draggedLines;
721  bool colLine = false, colVia = false;
722  LINE* currentLine = NULL;
723  VECTOR2I mtvLine, mtvVia, mtv, mtvSolid;
724  int rank = -1;
725 
726  if( aCurrent->OfKind( ITEM::LINE_T ) )
727  {
728 #ifdef DEBUG
729  m_logger.NewGroup( "push-via-by-line", m_iter );
730  m_logger.Log( aCurrent, 4, "current" );
731 #endif
732 
733  currentLine = (LINE*) aCurrent;
734  colLine = CollideShapes( aObstacleVia->Shape(), currentLine->Shape(),
735  clearance + currentLine->Width() / 2 + PNS_HULL_MARGIN,
736  true, mtvLine );
737 
738  if( currentLine->EndsWithVia() )
739  colVia = CollideShapes( currentLine->Via().Shape(), aObstacleVia->Shape(),
740  clearance + PNS_HULL_MARGIN, true, mtvVia );
741 
742  if( !colLine && !colVia )
743  return SH_OK;
744 
745  if( colLine && colVia )
746  mtv = mtvVia.EuclideanNorm() > mtvLine.EuclideanNorm() ? mtvVia : mtvLine;
747  else if( colLine )
748  mtv = mtvLine;
749  else
750  mtv = mtvVia;
751 
752  rank = currentLine->Rank();
753  }
754  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
755  {
756  CollideShapes( aObstacleVia->Shape(), aCurrent->Shape(),
757  clearance + PNS_HULL_MARGIN, true, mtvSolid );
758  mtv = -mtvSolid;
759  rank = aCurrent->Rank() + 10000;
760  }
761 
762  return pushVia( aObstacleVia, mtv, rank );
763 }
764 
765 
767 {
768  int n = 0;
769  LINE cur( aCurrent );
770  cur.ClearSegmentLinks();
771 
772  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
773  LINE shoved( aCurrent );
774  shoved.ClearSegmentLinks();
775 
776  cur.RemoveVia();
777  unwindStack( &aCurrent );
778 
779  for( ITEM* item : jt->LinkList() )
780  {
781  if( item->OfKind( ITEM::SEGMENT_T ) && item->LayersOverlap( &aCurrent ) )
782  {
783  SEGMENT* seg = (SEGMENT*) item;
784  LINE head = assembleLine( seg );
785 
786  head.AppendVia( *aObstacleVia );
787 
788  SHOVE_STATUS st = ProcessSingleLine( head, cur, shoved );
789 
790  if( st != SH_OK )
791  {
792 #ifdef DEBUG
793  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
794  m_logger.Log( aObstacleVia, 0, "the-via" );
795  m_logger.Log( &aCurrent, 1, "current-line" );
796  m_logger.Log( &shoved, 3, "shoved-line" );
797 #endif
798 
799  return st;
800  }
801 
802  cur.SetShape( shoved.CLine() );
803  n++;
804  }
805  }
806 
807  if( !n )
808  {
809 #ifdef DEBUG
810  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
811  m_logger.Log( aObstacleVia, 0, "the-via" );
812  m_logger.Log( &aCurrent, 1, "current-line" );
813 #endif
814 
815  LINE head( aCurrent );
816  head.Line().Clear();
817  head.AppendVia( *aObstacleVia );
818  head.ClearSegmentLinks();
819 
820  SHOVE_STATUS st = ProcessSingleLine( head, aCurrent, shoved );
821 
822  if( st != SH_OK )
823  return st;
824 
825  cur.SetShape( shoved.CLine() );
826  }
827 
828  if( aCurrent.EndsWithVia() )
829  shoved.AppendVia( aCurrent.Via() );
830 
831 #ifdef DEBUG
832  m_logger.NewGroup( "on-reverse-via", m_iter );
833  m_logger.Log( aObstacleVia, 0, "the-via" );
834  m_logger.Log( &aCurrent, 1, "current-line" );
835  m_logger.Log( &shoved, 3, "shoved-line" );
836 #endif
837  int currentRank = aCurrent.Rank();
838  replaceLine( aCurrent, shoved );
839 
840  if( !pushLine( shoved ) )
841  return SH_INCOMPLETE;
842 
843  shoved.SetRank( currentRank );
844 
845  return SH_OK;
846 }
847 
848 
850 {
851  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
852  {
853  if( i->ContainsSegment( aSeg ) )
854  i = m_lineStack.erase( i );
855  else
856  i++;
857  }
858 
859  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
860  {
861  if( i->ContainsSegment( aSeg ) )
862  i = m_optimizerQueue.erase( i );
863  else
864  i++;
865  }
866 }
867 
868 
869 void SHOVE::unwindStack( ITEM* aItem )
870 {
871  if( aItem->OfKind( ITEM::SEGMENT_T ) )
872  unwindStack( static_cast<SEGMENT*>( aItem ) );
873  else if( aItem->OfKind( ITEM::LINE_T ) )
874  {
875  LINE* l = static_cast<LINE*>( aItem );
876 
877  for( SEGMENT* seg : l->LinkedSegments() )
878  unwindStack( seg );
879  }
880 }
881 
882 
883 bool SHOVE::pushLine( const LINE& aL, bool aKeepCurrentOnTop )
884 {
885  if( !aL.IsLinkedChecked() )
886  return false;
887 
888  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
889  {
890  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
891  }
892  else
893  {
894  m_lineStack.push_back( aL );
895  }
896 
897  m_optimizerQueue.push_back( aL );
898 
899  return true;
900 }
901 
903 {
904  LINE& l = m_lineStack.back();
905 
906  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
907  {
908  bool found = false;
909 
910  for( SEGMENT *s : l.LinkedSegments() )
911  {
912  if( i->ContainsSegment( s ) )
913  {
914  i = m_optimizerQueue.erase( i );
915  found = true;
916  break;
917  }
918  }
919 
920  if( !found )
921  i++;
922  }
923 
924  m_lineStack.pop_back();
925 }
926 
927 
929 {
930  LINE currentLine = m_lineStack.back();
931  NODE::OPT_OBSTACLE nearest;
932  SHOVE_STATUS st = SH_NULL;
933 
935 
936  for( int i = 0; i < 3; i++ )
937  {
938  nearest = m_currentNode->NearestObstacle( &currentLine, search_order[i] );
939 
940  if( nearest )
941  break;
942  }
943 
944  if( !nearest )
945  {
946  m_lineStack.pop_back();
947  return SH_OK;
948  }
949 
950  ITEM* ni = nearest->m_item;
951 
952  unwindStack( ni );
953 
954  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
955  {
956  switch( ni->Kind() )
957  {
958  case ITEM::VIA_T:
959  {
960  VIA* revVia = (VIA*) ni;
961  wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
962 
963  if( currentLine.EndsWithVia() && m_currentNode->CheckColliding( &currentLine.Via(), revVia ) )
964  {
965  st = SH_INCOMPLETE;
966  }
967  else
968  {
969  st = onReverseCollidingVia( currentLine, revVia );
970  }
971 
972  break;
973  }
974 
975  case ITEM::SEGMENT_T:
976  {
977  SEGMENT* seg = (SEGMENT*) ni;
978  wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
979  LINE revLine = assembleLine( seg );
980 
981  popLine();
982  st = onCollidingLine( revLine, currentLine );
983  if( !pushLine( revLine ) )
984  return SH_INCOMPLETE;
985 
986  break;
987  }
988 
989  default:
990  assert( false );
991  }
992  }
993  else
994  { // "forward" collisions
995  switch( ni->Kind() )
996  {
997  case ITEM::SEGMENT_T:
998  wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
999 
1000  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1001 
1002  if( st == SH_TRY_WALK )
1003  {
1004  st = onCollidingSolid( currentLine, ni );
1005  }
1006  break;
1007 
1008  case ITEM::VIA_T:
1009  wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1010  st = onCollidingVia( &currentLine, (VIA*) ni );
1011 
1012  if( st == SH_TRY_WALK )
1013  {
1014  st = onCollidingSolid( currentLine, ni );
1015  }
1016  break;
1017 
1018  case ITEM::SOLID_T:
1019  wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1020  st = onCollidingSolid( currentLine, (SOLID*) ni );
1021  break;
1022 
1023  default:
1024  break;
1025  }
1026  }
1027 
1028  return st;
1029 }
1030 
1031 
1033 {
1034  SHOVE_STATUS st = SH_OK;
1035 
1037 
1038  wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1040 
1041  int iterLimit = Settings().ShoveIterationLimit();
1042  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1043 
1044  m_iter = 0;
1045 
1046  timeLimit.Restart();
1047 
1048  while( !m_lineStack.empty() )
1049  {
1050  st = shoveIteration( m_iter );
1051 
1052  m_iter++;
1053 
1054  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1055  {
1056  st = SH_INCOMPLETE;
1057  break;
1058  }
1059  }
1060 
1061  return st;
1062 }
1063 
1064 
1066 {
1067  OPT_BOX2I area;
1068  if( !m_nodeStack.empty() )
1069  area = m_nodeStack.back().m_affectedArea;
1070 
1071  if( area )
1072  {
1073  if( m_affectedAreaSum )
1074  area->Merge( *m_affectedAreaSum );
1075  } else
1076  area = m_affectedAreaSum;
1077 
1078  return area;
1079 }
1080 
1081 
1083 {
1084  SHOVE_STATUS st = SH_OK;
1085 
1086  m_multiLineMode = false;
1087 
1088  // empty head? nothing to shove...
1089 
1090  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1091  return SH_INCOMPLETE;
1092 
1093  LINE head( aCurrentHead );
1094  head.ClearSegmentLinks();
1095 
1096  m_lineStack.clear();
1097  m_optimizerQueue.clear();
1098  m_newHead = OPT_LINE();
1099  m_logger.Clear();
1100 
1101  ITEM_SET headSet;
1102  headSet.Add( aCurrentHead );
1103 
1104  reduceSpringback( headSet );
1105 
1106  NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1107 
1108  m_currentNode = parent->Branch();
1110  m_currentNode->Add( head );
1111 
1112  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1113 
1114  if( !head.EndsWithVia() )
1115  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1116 
1117  head.Mark( MK_HEAD );
1118  head.SetRank( 100000 );
1119 
1120  m_logger.NewGroup( "initial", 0 );
1121  m_logger.Log( &head, 0, "head" );
1122 
1123  if( head.EndsWithVia() )
1124  {
1125  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1126  headVia->Mark( MK_HEAD );
1127  headVia->SetRank( 100000 );
1128  m_logger.Log( headVia.get(), 0, "head-via" );
1129  m_currentNode->Add( std::move( headVia ) );
1130  }
1131 
1132  if( !pushLine( head ) )
1133  {
1134  delete m_currentNode;
1135  m_currentNode = parent;
1136 
1137  return SH_INCOMPLETE;
1138  }
1139 
1140  st = shoveMainLoop();
1141 
1142  if( st == SH_OK )
1143  {
1145 
1146  if( m_newHead )
1148  else
1149  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1150  }
1151 
1153 
1154  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1155  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1156 
1157  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1158  {
1160  }
1161  else
1162  {
1163  delete m_currentNode;
1164 
1165  m_currentNode = parent;
1166  m_newHead = OPT_LINE();
1167  }
1168 
1169  if(m_newHead)
1170  m_newHead->Unmark();
1171 
1172  if( m_newHead && head.EndsWithVia() )
1173  {
1174  VIA v = head.Via();
1175  v.SetPos( m_newHead->CPoint( -1 ) );
1176  m_newHead->AppendVia(v);
1177  }
1178 
1179  return st;
1180 }
1181 
1182 
1184 {
1185  SHOVE_STATUS st = SH_OK;
1186 
1187  m_multiLineMode = true;
1188 
1189  ITEM_SET headSet;
1190 
1191  for( const ITEM* item : aHeadSet.CItems() )
1192  {
1193  const LINE* headOrig = static_cast<const LINE*>( item );
1194 
1195  // empty head? nothing to shove...
1196  if( !headOrig->SegmentCount() )
1197  return SH_INCOMPLETE;
1198 
1199  headSet.Add( *headOrig );
1200  }
1201 
1202  m_lineStack.clear();
1203  m_optimizerQueue.clear();
1204  m_logger.Clear();
1205 
1206  reduceSpringback( headSet );
1207 
1208  NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1209 
1210  m_currentNode = parent->Branch();
1212  int n = 0;
1213 
1214  for( const ITEM* item : aHeadSet.CItems() )
1215  {
1216  const LINE* headOrig = static_cast<const LINE*>( item );
1217  LINE head( *headOrig );
1218  head.ClearSegmentLinks();
1219 
1220  m_currentNode->Add( head );
1221 
1222  head.Mark( MK_HEAD );
1223  head.SetRank( 100000 );
1224  n++;
1225 
1226  if( !pushLine( head ) )
1227  return SH_INCOMPLETE;
1228 
1229  if( head.EndsWithVia() )
1230  {
1231  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1232  headVia->Mark( MK_HEAD );
1233  headVia->SetRank( 100000 );
1234  m_logger.Log( headVia.get(), 0, "head-via" );
1235  m_currentNode->Add( std::move( headVia ) );
1236  }
1237  }
1238 
1239  m_logger.NewGroup( "initial", 0 );
1240  //m_logger.Log( head, 0, "head" );
1241 
1242  st = shoveMainLoop();
1243 
1244  if( st == SH_OK )
1246 
1248 
1249  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1250  ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1251 
1252  if( st == SH_OK )
1253  {
1255  }
1256  else
1257  {
1258  delete m_currentNode;
1259  m_currentNode = parent;
1260  }
1261 
1262  return st;
1263 }
1264 
1265 
1267  VIA** aNewVia )
1268 {
1269  SHOVE_STATUS st = SH_OK;
1270 
1271  m_lineStack.clear();
1272  m_optimizerQueue.clear();
1273  m_newHead = OPT_LINE();
1274  m_draggedVia = NULL;
1276 
1277  NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1278 
1279  m_currentNode = parent;
1280 
1281  parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1282 
1283  m_currentNode = parent->Branch();
1285 
1286  aVia->Mark( MK_HEAD );
1287 
1288  st = pushVia( aVia, ( aWhere - aVia->Pos() ), 0 );
1289  st = shoveMainLoop();
1290 
1291  if( st == SH_OK )
1293 
1294  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1295  {
1296  if( aNewVia )
1297  {
1298  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1299  *aNewVia = m_draggedVia;
1300  }
1301 
1303  }
1304  else
1305  {
1306  if( aNewVia )
1307  {
1308  *aNewVia = nullptr;
1309  }
1310 
1311  delete m_currentNode;
1312  m_currentNode = parent;
1313  }
1314 
1315  return st;
1316 }
1317 
1318 
1320 {
1321  OPTIMIZER optimizer( aNode );
1322  int optFlags = 0, n_passes = 0;
1323 
1325 
1326  OPT_BOX2I area = totalAffectedArea();
1327 
1328  int maxWidth = 0;
1329 
1330  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin();
1331  i != m_optimizerQueue.end(); ++i )
1332  {
1333  maxWidth = std::max( i->Width(), maxWidth );
1334  }
1335 
1336  if( area )
1337  {
1338  area->Inflate( 10 * maxWidth );
1339  }
1340 
1341  switch( effort )
1342  {
1343  case OE_LOW:
1344  optFlags = OPTIMIZER::MERGE_OBTUSE;
1345  n_passes = 1;
1346  break;
1347 
1348  case OE_MEDIUM:
1349  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1350 
1351  if( area )
1352  optimizer.SetRestrictArea( *area );
1353 
1354  n_passes = 2;
1355  break;
1356 
1357  case OE_FULL:
1358  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1359  n_passes = 2;
1360  break;
1361 
1362  default:
1363  break;
1364  }
1365 
1366  if( Settings().SmartPads() )
1367  optFlags |= OPTIMIZER::SMART_PADS;
1368 
1369  optimizer.SetEffortLevel( optFlags );
1370  optimizer.SetCollisionMask( ITEM::ANY_T );
1371 
1372  for( int pass = 0; pass < n_passes; pass++ )
1373  {
1375 
1376  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin();
1377  i != m_optimizerQueue.end(); ++i )
1378  {
1379  LINE& line = *i;
1380 
1381  if( !( line.Marker() & MK_HEAD ) )
1382  {
1383  LINE optimized;
1384 
1385  if( optimizer.Optimize( &line, &optimized ) )
1386  {
1387  aNode->Remove( line );
1388  line.SetShape( optimized.CLine() );
1389  aNode->Add( line );
1390  }
1391  }
1392  }
1393  }
1394 }
1395 
1396 
1398 {
1399  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1400 }
1401 
1402 
1403 const LINE SHOVE::NewHead() const
1404 {
1405  assert( m_newHead );
1406 
1407  return *m_newHead;
1408 }
1409 
1410 
1411 void SHOVE::SetInitialLine( LINE& aInitial )
1412 {
1413  m_root = m_root->Branch();
1414  m_root->Remove( aInitial );
1415 }
1416 
1417 }
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:123
TIME_LIMIT ShoveTimeLimit() const
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
Class ITEM.
Definition: pns_item.h:53
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1256
COST_ESTIMATOR m_cost
Definition: pns_shove.h:101
bool reduceSpringback(const ITEM_SET &aHeadItems)
Definition: pns_shove.cpp:541
const VIA & Via() const
Definition: pns_line.h:253
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Returns the optimizer effort. Bigger means cleaner traces, but slower routing.
Class NODE.
Definition: pns_node.h:137
const ENTRIES & CItems() const
Definition: pns_itemset.h:138
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:412
LINE assembleLine(const SEGMENT *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:107
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:302
OPT< LINE > OPT_LINE
Definition: pns_shove.h:90
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:209
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:387
int PointCount() const
Function PointCount()
int Rank() const override
Definition: pns_line.cpp:759
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:834
ITEM_SET m_draggedViaHeadSet
Definition: pns_shove.h:155
Class ALGO_BASE.
Definition: pns_algo_base.h:39
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:259
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
static const int dist[10][10]
Definition: dist.cpp:57
bool Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculates a line thightly wrapping a convex hull of an obstacle object (aObstacle).
Definition: pns_line.cpp:158
#define PNS_HULL_MARGIN
Class LINE.
Definition: pns_line.h:58
void SetSingleDirection(bool aForceSingleDirection)
SHOVE_STATUS processHullSet(LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
Definition: pns_shove.cpp:161
void RemoveVia()
Definition: pns_line.h:251
NODE * m_root
Definition: pns_shove.h:148
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:91
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
ROUTING_SETTINGS & Settings() const
Returns current router settings
virtual const SHAPE * Shape() const
Function Shape()
Definition: pns_item.h:298
void unwindStack(SEGMENT *aSeg)
Definition: pns_shove.cpp:849
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:736
const VECTOR2I & Pos() const
Definition: pns_via.h:88
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:231
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
virtual int Marker() const
Definition: pns_item.h:313
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:72
int Width() const
Returns line width
Definition: pns_line.h:159
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
const SHAPE * Shape() const override
Function Shape()
Definition: pns_via.h:136
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:107
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:92
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:373
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:766
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:89
void SetCollisionMask(int aMask)
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:132
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assigns a shape to the line (a polyline/line chain)
Definition: pns_line.h:105
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const SHAPE * Shape() const override
Returns the shape of the line
Definition: pns_line.h:111
SHOVE_STATUS ShoveLines(const LINE &aCurrentHead)
Definition: pns_shove.cpp:1082
Class JOINT.
Definition: pns_joint.h:43
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
bool IsLocked() const
Definition: pns_item.h:338
bool checkBumpDirection(const LINE &aCurrent, const LINE &aShoved) const
Definition: pns_shove.cpp:116
virtual int Rank() const
Definition: pns_item.h:323
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:294
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:717
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1319
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:81
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1065
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:928
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0) const override
Definition: pns_via.cpp:74
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:129
bool EndsWithVia() const
Definition: pns_line.h:248
void RestrictToSet(bool aEnabled, const std::set< ITEM * > &aSet)
SHOVE(NODE *aWorld, ROUTER *aRouter)
Definition: pns_shove.cpp:88
bool HasLockedSegments() const
Definition: pns_line.cpp:912
void SetSolidsOnly(bool aSolidsOnly)
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
int Start() const
Definition: pns_layerset.h:83
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:315
bool Expired() const
Definition: time_limit.cpp:39
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:49
void SetRank(int aRank) override
Definition: pns_line.cpp:749
virtual void Mark(int aMarker) override
Definition: pns_line.cpp:84
void Clear()
Definition: pns_logger.cpp:48
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
SHOVE_STATUS ShoveDraggingVia(VIA *aVia, const VECTOR2I &aWhere, VIA **aNewVia)
Definition: pns_shove.cpp:1266
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:968
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape
Definition: pns_line.h:117
const LINE NewHead() const
Definition: pns_shove.cpp:1403
PnsKind Kind() const
Function Kind()
Definition: pns_item.h:122
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:93
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:380
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:717
Definition: seg.h:36
PnsKind
Supported item types
Definition: pns_item.h:59
bool pushSpringback(NODE *aNode, const ITEM_SET &aHeadItems, const COST_ESTIMATOR &aCost, const OPT_BOX2I &aAffectedArea)
Definition: pns_shove.cpp:564
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
bool LayersOverlap(const ITEM *aOther) const
Function LayersOverlap()
Definition: pns_item.h:230
const SEG CSegment(int aIdx) const
Returns the aIdx-th segment of the line
Definition: pns_line.h:147
VIA * m_draggedVia
Definition: pns_shove.h:154
virtual int Marker() const override
Definition: pns_line.cpp:103
SEGMENT_REFS & LinkedSegments()
Returns the list of segments from the owning node that constitute this line (or NULL if the line is n...
Definition: pns_line.h:181
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:98
void ClearSegmentLinks()
Erases the linking information. Used to detach the line from the owning node.
Definition: pns_line.cpp:813
void popLine()
Definition: pns_shove.cpp:902
static LIB_PART * dummy()
Used when a LIB_PART is not found in library to draw a dummy shape This component is a 400 mils squar...
int JointCount() const
Returns the number of joints
Definition: pns_node.h:174
#define max(a, b)
Definition: auxiliary.h:86
Class SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
size_t i
Definition: json11.cpp:597
bool HasLoops() const
Definition: pns_line.cpp:798
VECTOR2I A
Definition: seg.h:46
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:60
bool IsLinkedChecked() const
Definition: pns_line.h:191
static void reverse(privcurve_t *curve)
Definition: trace.cpp:1025
PNS_OPTIMIZATION_EFFORT
Optimization effort
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1032
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:471
void SetInitialLine(LINE &aInitial)
Definition: pns_shove.cpp:1411
Class OPTIMIZER.
Definition: pns_optimizer.h:90
void Clear()
Function Clear() Removes all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:140
virtual void Mark(int aMarker)
Definition: pns_item.h:303
SHOVE_STATUS pushVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank, bool aDryRun=false)
Definition: pns_shove.cpp:592
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:48
void SetEffortLevel(int aEffort)
bool m_multiLineMode
Definition: pns_shove.h:159
OPT_LINE m_newHead
Definition: pns_shove.h:151
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
SHOVE_STATUS ShoveMultiLines(const ITEM_SET &aHeadSet)
Definition: pns_shove.cpp:1183
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:190
NODE * m_currentNode
Definition: pns_shove.h:149
void SetRestrictArea(const BOX2I &aArea)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld)
a quick shortcut to optmize a line without creating and setting up an optimizer
int RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1278
Class COST_ESTIMATOR.
Definition: pns_optimizer.h:45
Push and Shove diff pair dimensions (gap) settings dialog.
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:883
SHOVE_STATUS walkaroundLoneVia(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:131
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:594
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
virtual void Unmark(int aMarker=-1) override
Definition: pns_line.cpp:94
NODE * CurrentNode()
Definition: pns_shove.cpp:1397
void SetIterationLimit(const int aIterLimit)
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:998
int m_forceClearance
Definition: pns_shove.h:158
int Length() const
Function Length()
#define min(a, b)
Definition: auxiliary.h:85
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:141
VECTOR2I B
Definition: seg.h:47