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