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-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 <deque>
23 #include <cassert>
24 #include <math/box2.h>
25 
27 
28 #include <wx/log.h>
29 
30 #include "pns_arc.h"
31 #include "pns_line.h"
32 #include "pns_node.h"
33 #include "pns_debug_decorator.h"
34 #include "pns_walkaround.h"
35 #include "pns_shove.h"
36 #include "pns_solid.h"
37 #include "pns_optimizer.h"
38 #include "pns_via.h"
39 #include "pns_utils.h"
40 #include "pns_router.h"
41 #include "pns_topology.h"
42 
43 #include "time_limit.h"
44 
45 // fixme - move all logger calls to debug decorator
46 
48 
49 namespace PNS {
50 
51 void SHOVE::replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew )
52 {
53  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
54 
55  if( changed_area )
56  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
57 
58  m_currentNode->Replace( aOld, std::move( aNew ) );
59 }
60 
61 void SHOVE::replaceLine( LINE& aOld, LINE& aNew, bool aIncludeInChangedArea, NODE* aNode )
62 {
63  if( aIncludeInChangedArea )
64  {
65  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
66 
67  if( changed_area )
68  {
69  if( Dbg() )
70  {
71  Dbg()->AddBox( *changed_area, BLUE, "shove-changed-area" );
72  }
73 
74  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
75  }
76  }
77 
78  bool foundPredecessor = false;
79  LINE* rootLine = nullptr;
80 
81  // Keep track of the 'root lines', i.e. the unmodified (pre-shove) versions
82  // of the affected tracks in a map. The optimizer can then query the pre-shove shape
83  // for each shoved line and perform additional constraint checks (i.e. prevent overzealous optimizations)
84 
85  // Check if the shoved line already has an ancestor (e.g. line from a previous shove iteration/cursor movement)
86  for( auto link : aOld.Links() )
87  {
88  auto oldLineIter = m_rootLineHistory.find( link );
89  if( oldLineIter != m_rootLineHistory.end() )
90  {
91  rootLine = oldLineIter->second;
92  foundPredecessor = true;
93  break;
94  }
95  }
96 
97  // If found, use it, otherwise, create new entry in the map (we have a genuine new 'root' line)
98  if( !foundPredecessor )
99  {
100  for( auto link : aOld.Links() )
101  {
102  if( ! rootLine )
103  {
104  rootLine = aOld.Clone();
105  }
106  m_rootLineHistory[link] = rootLine;
107  }
108  }
109 
110  // Now update the NODE (calling Replace invalidates the Links() in a LINE)
111  if( aNode )
112  {
113  aNode->Replace( aOld, aNew );
114  }
115  else
116  {
117  m_currentNode->Replace( aOld, aNew );
118  }
119 
120  // point the Links() of the new line to its oldest ancestor
121  for( auto link : aNew.Links() )
122  {
123  m_rootLineHistory[ link ] = rootLine;
124  }
125 }
126 
127 int SHOVE::getClearance( const ITEM* aA, const ITEM* aB ) const
128 {
129  if( m_forceClearance >= 0 )
130  return m_forceClearance;
131 
132  return m_currentNode->GetClearance( aA, aB );
133 }
134 
135 int SHOVE::getHoleClearance( const ITEM* aA, const ITEM* aB ) const
136 {
137  if( m_forceClearance >= 0 )
138  return m_forceClearance;
139 
140  return m_currentNode->GetHoleClearance( aA, aB );
141 }
142 
143 
144 void SHOVE::sanityCheck( LINE* aOld, LINE* aNew )
145 {
146  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
147  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
148 }
149 
150 
151 SHOVE::SHOVE( NODE* aWorld, ROUTER* aRouter ) :
152  ALGO_BASE( aRouter )
153 {
154  m_forceClearance = -1;
155  m_root = aWorld;
156  m_currentNode = aWorld;
158 
159  // Initialize other temporary variables:
160  m_draggedVia = NULL;
161  m_iter = 0;
162  m_multiLineMode = false;
164 }
165 
166 
168 {
169  std::unordered_set<LINE*> alreadyDeleted;
170  for( auto it : m_rootLineHistory )
171  {
172  auto it2 = alreadyDeleted.find( it.second );
173  if( it2 == alreadyDeleted.end() )
174  {
175  alreadyDeleted.insert( it.second );
176  delete it.second;
177  }
178  }
179 }
180 
181 
182 LINE SHOVE::assembleLine( const LINKED_ITEM* aSeg, int* aIndex )
183 {
184  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
185 }
186 
187 // A dumb function that checks if the shoved line is shoved the right way, e.g. visually
188 // "outwards" of the line/via applying pressure on it. Unfortunately there's no mathematical
189 // concept of orientation of an open curve, so we use some primitive heuristics: if the shoved
190 // line wraps around the start of the "pusher", it's likely shoved in wrong direction.
191 
192 // Update: there's no concept of an orientation of an open curve, but nonetheless Tom's dumb as.... (censored)
193 // Two open curves put together make a closed polygon... Tom should learn high school geometry!
194 
195 bool SHOVE::checkShoveDirection( const LINE& aCurLine, const LINE& aObstacleLine,
196  const LINE& aShovedLine ) const
197 {
198  SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
199  checker.AddPolyline( aObstacleLine.CLine() );
200  checker.AddPolyline( aShovedLine.CLine().Reverse() );
201 
202  bool inside = checker.IsInside();
203 
204  return !inside;
205 }
206 
207 
208 /*
209  * Push aObstacleLine away from aCurLine's via by the clearance distance, returning the result
210  * in aResultLine.
211  *
212  * Must be called only when aCurLine itself is on another layer (or has no segments) so that it
213  * can be ignored.
214  */
215 SHOVE::SHOVE_STATUS SHOVE::shoveLineFromLoneVia( const LINE& aCurLine, const LINE& aObstacleLine,
216  LINE& aResultLine )
217 {
218  // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
219 
220  int obstacleLineWidth = aObstacleLine.Width();
221  int clearance = getClearance( &aCurLine, &aObstacleLine );
222  int holeClearance = getHoleClearance( &aCurLine.Via(), &aObstacleLine );
223 
224  if( holeClearance + aCurLine.Via().Drill() / 2 > clearance + aCurLine.Via().Diameter() / 2 )
225  clearance = holeClearance + aCurLine.Via().Drill() / 2 - aCurLine.Via().Diameter() / 2;
226 
227  SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
228  SHAPE_LINE_CHAIN path_cw;
229  SHAPE_LINE_CHAIN path_ccw;
230 
231  if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
232  return SH_INCOMPLETE;
233 
234  if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
235  return SH_INCOMPLETE;
236 
237  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
238 
239  if( shortest.PointCount() < 2 )
240  return SH_INCOMPLETE;
241 
242  if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
243  return SH_INCOMPLETE;
244 
245  if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
246  return SH_INCOMPLETE;
247 
248  aResultLine.SetShape( shortest );
249 
250  if( aResultLine.Collide( &aCurLine, m_currentNode ) )
251  return SH_INCOMPLETE;
252 
253  return SH_OK;
254 }
255 
256 
257 /*
258  * Re-walk aObstacleLine around the given set of hulls, returning the result in aResultLine.
259  */
260 SHOVE::SHOVE_STATUS SHOVE::shoveLineToHullSet( const LINE& aCurLine, const LINE& aObstacleLine,
261  LINE& aResultLine, const HULL_SET& aHulls )
262 {
263  const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();
264 
265  int attempt;
266 
267  for( attempt = 0; attempt < 4; attempt++ )
268  {
269  bool invertTraversal = ( attempt >= 2 );
270  bool clockwise = attempt % 2;
271  int vFirst = -1, vLast = -1;
272 
273  LINE l( aObstacleLine );
274  SHAPE_LINE_CHAIN path( l.CLine() );
275 
276  for( int i = 0; i < (int) aHulls.size(); i++ )
277  {
278  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
279 
280  PNS_DBG( Dbg(), AddLine, hull, YELLOW, 10000, "hull" );
281  PNS_DBG( Dbg(), AddLine, path, WHITE, l.Width(), "path" );
282  PNS_DBG( Dbg(), AddLine, obs, LIGHTGRAY, aObstacleLine.Width(), "obs" );
283  if( ! l.Walkaround( hull, path, clockwise ) )
284  {
285  PNS_DBG( Dbg(), Message, wxString::Format( "Fail-Walk %s %s %d\n", hull.Format().c_str(), l.CLine().Format().c_str(), clockwise? 1:0) );
286  return SH_INCOMPLETE;
287  }
288 
289  path.Simplify();
290  l.SetShape( path );
291  }
292 
293  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
294  {
295  if( path.CPoint( i ) != obs.CPoint( i ) )
296  {
297  vFirst = i;
298  break;
299  }
300  }
301 
302  int k = obs.PointCount() - 1;
303  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
304  {
305  if( path.CPoint( i ) != obs.CPoint( k ) )
306  {
307  vLast = i;
308  break;
309  }
310  }
311 
312  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
313  {
314  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail vfirst-last", attempt ) );
315  continue;
316  }
317 
318  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
319  {
320  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail vend-start\n", attempt ) );
321  continue;
322  }
323 
324  if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
325  {
326  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail direction-check", attempt ) );
327  aResultLine.SetShape( l.CLine() );
328 
329  continue;
330  }
331 
332  if( path.SelfIntersecting() )
333  {
334  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail self-intersect", attempt ) );
335  continue;
336  }
337 
338  bool colliding = l.Collide( &aCurLine, m_currentNode );
339 
340 #ifdef DEBUG
341  char str[128];
342  sprintf( str, "att-%d-shoved", attempt );
343  Dbg()->AddLine( l.CLine(), BLUE, 20000, str );
344 #endif
345 
346  if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
347  {
348  JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
349 
350  for( ITEM* item : jtStart->LinkList() )
351  {
352  if( item->Collide( &l, m_currentNode ) )
353  colliding = true;
354  }
355  }
356 
357  if( colliding )
358  {
359  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail coll-check", attempt ) );
360  continue;
361  }
362 
363  aResultLine.SetShape( l.CLine() );
364 
365  return SH_OK;
366  }
367 
368  return SH_INCOMPLETE;
369 }
370 
371 
372 /*
373  * Push aObstacleLine line away from aCurLine by the clearance distance, and return the result in
374  * aResultLine.
375  */
376 SHOVE::SHOVE_STATUS SHOVE::ShoveObstacleLine( const LINE& aCurLine, const LINE& aObstacleLine,
377  LINE& aResultLine )
378 {
379  aResultLine.ClearLinks();
380 
381  bool obstacleIsHead = false;
382 
383  for( LINKED_ITEM* s : aObstacleLine.Links() )
384  {
385  if( s->Marker() & MK_HEAD )
386  {
387  obstacleIsHead = true;
388  break;
389  }
390  }
391 
392  SHOVE_STATUS rv;
393  bool viaOnEnd = aCurLine.EndsWithVia();
394 
395  if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
396  {
397  // Shove aObstacleLine to the hull of aCurLine's via.
398 
399  rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
400  }
401  else
402  {
403  // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
404  // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
405  // hull it will be at the appropriate clearance.
406 
407  int obstacleLineWidth = aObstacleLine.Width();
408  int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
409  int currentLineSegmentCount = aCurLine.SegmentCount();
410  HULL_SET hulls;
411 
412  hulls.reserve( currentLineSegmentCount + 1 );
413 
414 #ifdef DEBUG
415  Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d",
416  aCurLine.Net(),
417  aObstacleLine.Net(),
418  clearance ) );
419 #endif
420 
421  for( int i = 0; i < currentLineSegmentCount; i++ )
422  {
423  SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
424  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, obstacleLineWidth, aObstacleLine.Layer() );
425 
426  hulls.push_back( hull );
427  }
428 
429  if( viaOnEnd )
430  {
431  const VIA& via = aCurLine.Via();
432  int viaClearance = getClearance( &via, &aObstacleLine );
433  int holeClearance = getHoleClearance( &via, &aObstacleLine );
434 
435  if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
436  viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
437 
438  hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
439  }
440 
441 #ifdef DEBUG
442  char str[128];
443  sprintf( str, "current-cl-%d", clearance );
444  Dbg()->AddLine( aCurLine.CLine(), BLUE, 20000, str );
445 #endif
446 
447  rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
448  }
449 
450  if( obstacleIsHead )
451  aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
452 
453  return rv;
454 }
455 
456 
457 /*
458  * TODO describe....
459  */
461 {
462  int segIndex;
463  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
464  LINE shovedLine( obstacleLine );
465  SEGMENT tmp( *aObstacleSeg );
466 
467  if( obstacleLine.HasLockedSegments() )
468  return SH_TRY_WALK;
469 
470  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
471 
472  const double extensionWalkThreshold = 1.0;
473 
474  double obsLen = obstacleLine.CLine().Length();
475  double shovedLen = shovedLine.CLine().Length();
476  double extensionFactor = 0.0;
477 
478  if( obsLen != 0.0f )
479  extensionFactor = shovedLen / obsLen - 1.0;
480 
481  if( extensionFactor > extensionWalkThreshold )
482  return SH_TRY_WALK;
483 
484  assert( obstacleLine.LayersOverlap( &shovedLine ) );
485 
486  if( Dbg() )
487  {
488  Dbg()->BeginGroup( wxString::Format( "on-colliding-segment-iter-%d", m_iter ).ToStdString() );
489  Dbg()->AddSegment( tmp.Seg(), WHITE, "obstacle-segment" );
490  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
491  Dbg()->AddLine( obstacleLine.CLine(), GREEN, 10000, "obstacle-line" );
492  Dbg()->AddLine( shovedLine.CLine(), BLUE, 10000, "shoved-line" );
493  if( rv == SH_OK )
494  Dbg()->Message("Shove success");
495  else
496  Dbg()->Message("Shove FAIL");
497  Dbg()->EndGroup();
498  }
499 
500  if( rv == SH_OK )
501  {
502  if( shovedLine.Marker() & MK_HEAD )
503  {
504  if( m_multiLineMode )
505  return SH_INCOMPLETE;
506 
507  m_newHead = shovedLine;
508  }
509 
510  int rank = aCurrent.Rank();
511  shovedLine.SetRank( rank - 1 );
512 
513  sanityCheck( &obstacleLine, &shovedLine );
514  replaceLine( obstacleLine, shovedLine );
515 
516  if( !pushLineStack( shovedLine ) )
517  rv = SH_INCOMPLETE;
518  }
519 
520  return rv;
521 }
522 
523 
524 /*
525  * TODO describe....
526  */
528 {
529  int segIndex;
530  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
531  LINE shovedLine( obstacleLine );
532  ARC tmp( *aObstacleArc );
533 
534  if( obstacleLine.HasLockedSegments() )
535  return SH_TRY_WALK;
536 
537  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
538 
539  const double extensionWalkThreshold = 1.0;
540 
541  double obsLen = obstacleLine.CLine().Length();
542  double shovedLen = shovedLine.CLine().Length();
543  double extensionFactor = 0.0;
544 
545  if( obsLen != 0.0f )
546  extensionFactor = shovedLen / obsLen - 1.0;
547 
548  if( extensionFactor > extensionWalkThreshold )
549  return SH_TRY_WALK;
550 
551  assert( obstacleLine.LayersOverlap( &shovedLine ) );
552 
553  if ( Dbg() )
554  {
555  Dbg()->BeginGroup( wxString::Format( "on-colliding-arc-iter-%d", m_iter ).ToStdString() );
556  Dbg()->AddLine( tmp.CLine(), WHITE, 10000, "obstacle-segment" );
557  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
558  Dbg()->AddLine( obstacleLine.CLine(), GREEN, 10000, "obstacle-line" );
559  Dbg()->AddLine( shovedLine.CLine(), BLUE, 10000, "shoved-line" );
560  Dbg()->EndGroup();
561  }
562 
563  if( rv == SH_OK )
564  {
565  if( shovedLine.Marker() & MK_HEAD )
566  {
567  if( m_multiLineMode )
568  return SH_INCOMPLETE;
569 
570  m_newHead = shovedLine;
571  }
572 
573  int rank = aCurrent.Rank();
574  shovedLine.SetRank( rank - 1 );
575 
576  sanityCheck( &obstacleLine, &shovedLine );
577  replaceLine( obstacleLine, shovedLine );
578 
579  if( !pushLineStack( shovedLine ) )
580  rv = SH_INCOMPLETE;
581  }
582 
583  return rv;
584 }
585 
586 
587 /*
588  * TODO describe....
589  */
591 {
592  LINE shovedLine( aObstacle );
593 
594  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
595 
596  Dbg()->BeginGroup( "on-colliding-line" );
597  Dbg()->AddLine( aObstacle.CLine(), RED, 100000, "obstacle-line" );
598  Dbg()->AddLine( aCurrent.CLine(), GREEN, 150000, "current-line" );
599  Dbg()->AddLine( shovedLine.CLine(), BLUE, 200000, "shoved-line" );
600 
601  if( rv == SH_OK )
602  {
603  if( shovedLine.Marker() & MK_HEAD )
604  {
605  if( m_multiLineMode )
606  return SH_INCOMPLETE;
607 
608  m_newHead = shovedLine;
609  }
610 
611  sanityCheck( &aObstacle, &shovedLine );
612  replaceLine( aObstacle, shovedLine );
613 
614  int rank = aObstacle.Rank();
615  shovedLine.SetRank( rank - 1 );
616 
617 
618  if( !pushLineStack( shovedLine ) )
619  {
620  rv = SH_INCOMPLETE;
621  }
622  }
623 
624  return rv;
625 }
626 
627 
628 /*
629  * TODO describe....
630  */
632 {
633  WALKAROUND walkaround( m_currentNode, Router() );
634  LINE walkaroundLine( aCurrent );
635 
636  if( aCurrent.EndsWithVia() )
637  {
638  VIA vh = aCurrent.Via();
639  VIA* via = NULL;
640  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
641 
642  if( !jtStart )
643  return SH_INCOMPLETE;
644 
645  for( ITEM* item : jtStart->LinkList() )
646  {
647  if( item->OfKind( ITEM::VIA_T ) )
648  {
649  via = (VIA*) item;
650  break;
651  }
652  }
653 
654  if( via && via->Collide( aObstacle, m_currentNode ) )
655  return onCollidingVia( aObstacle, via );
656  }
657 
658  TOPOLOGY topo( m_currentNode );
659 
660  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
661 
662  walkaround.SetSolidsOnly( false );
663  walkaround.RestrictToSet( true, cluster );
664  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
665 
666  int currentRank = aCurrent.Rank();
667  int nextRank;
668 
669  bool success = false;
670 
671  for( int attempt = 0; attempt < 2; attempt++ )
672  {
673  if( attempt == 1 || Settings().JumpOverObstacles() )
674  {
675 
676  nextRank = currentRank - 1;
677  walkaround.SetSingleDirection( true );
678  }
679  else
680  {
681  nextRank = currentRank + 10000;
682  walkaround.SetSingleDirection( false );
683  }
684 
685 
686  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
687 
688  if( status != WALKAROUND::DONE )
689  continue;
690 
691  walkaroundLine.ClearLinks();
692  walkaroundLine.Unmark();
693  walkaroundLine.Line().Simplify();
694 
695  if( walkaroundLine.HasLoops() )
696  continue;
697 
698  if( aCurrent.Marker() & MK_HEAD )
699  {
700  walkaroundLine.Mark( MK_HEAD );
701 
702  if( m_multiLineMode )
703  continue;
704 
705  m_newHead = walkaroundLine;
706  }
707 
708  sanityCheck( &aCurrent, &walkaroundLine );
709 
710  if( !m_lineStack.empty() )
711  {
712  LINE lastLine = m_lineStack.front();
713 
714  if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
715  {
716  LINE dummy( lastLine );
717 
718  if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
719  {
720  success = true;
721  break;
722  }
723  } else {
724  success = true;
725  break;
726  }
727  }
728  }
729 
730  if(!success)
731  return SH_INCOMPLETE;
732 
733  replaceLine( aCurrent, walkaroundLine );
734  walkaroundLine.SetRank( nextRank );
735 
736  if( Dbg() )
737  {
738  Dbg()->BeginGroup( "on-colliding-solid" );
739  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
740  Dbg()->AddLine( walkaroundLine.CLine(), BLUE, 10000, "walk-line" );
741  Dbg()->EndGroup();
742  }
743 
744  popLineStack();
745 
746  if( !pushLineStack( walkaroundLine ) )
747  return SH_INCOMPLETE;
748 
749  return SH_OK;
750 }
751 
752 
753 /*
754  * Pops NODE stackframes which no longer collide with aHeadSet. Optionally sets aDraggedVia
755  * to the dragged via of the last unpopped state.
756  */
757 NODE* SHOVE::reduceSpringback( const ITEM_SET& aHeadSet, VIA_HANDLE& aDraggedVia )
758 {
759  while( !m_nodeStack.empty() )
760  {
761  SPRINGBACK_TAG& spTag = m_nodeStack.back();
762 
763  OPT<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
764 
765  if( !obs && !spTag.m_locked )
766  {
767  aDraggedVia = spTag.m_draggedVia;
768  aDraggedVia.valid = true;
769 
770  delete spTag.m_node;
771  m_nodeStack.pop_back();
772  }
773  else
774  break;
775  }
776 
777  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
778 }
779 
780 
781 /*
782  * Push the current NODE on to the stack. aDraggedVia is the dragged via *before* the push
783  * (which will be restored in the event the stackframe is popped).
784  */
785 bool SHOVE::pushSpringback( NODE* aNode, const OPT_BOX2I& aAffectedArea, VIA* aDraggedVia )
786 {
787  SPRINGBACK_TAG st;
788  OPT_BOX2I prev_area;
789 
790  if( !m_nodeStack.empty() )
791  prev_area = m_nodeStack.back().m_affectedArea;
792 
793  if( aDraggedVia )
794  {
795  st.m_draggedVia = aDraggedVia->MakeHandle();
796  }
797 
798  st.m_node = aNode;
799 
800  if( aAffectedArea )
801  {
802  if( prev_area )
803  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
804  else
805  st.m_affectedArea = aAffectedArea;
806  } else
807  st.m_affectedArea = prev_area;
808 
809  st.m_seq = (m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1);
810  st.m_locked = false;
811 
812  m_nodeStack.push_back( st );
813 
814  return true;
815 }
816 
817 
818 /*
819  * Push or shove a via by at least aForce. (The via might be pushed or shoved slightly further
820  * to keep it from landing on an existing joint.)
821  */
822 SHOVE::SHOVE_STATUS SHOVE::pushOrShoveVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank )
823 {
824  LINE_PAIR_VEC draggedLines;
825  VECTOR2I p0( aVia->Pos() );
826  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
827  VECTOR2I p0_pushed( p0 + aForce );
828 
829  PNS_DBG( Dbg(), Message, wxString::Format( "via force [%d %d]\n", aForce.x, aForce.y ) );
830 
831  // nothing to do...
832  if ( aForce.x == 0 && aForce.y == 0 )
833  return SH_OK;
834 
835  if( !jt )
836  {
837  PNS_DBG( Dbg(), Message, wxString::Format( "weird, can't find the center-of-via joint\n" ) );
838  return SH_INCOMPLETE;
839  }
840 
841  if( aVia->IsLocked() )
842  return SH_TRY_WALK;
843 
844  if( jt->IsLocked() )
845  return SH_INCOMPLETE;
846 
847  // make sure pushed via does not overlap with any existing joint
848  while( true )
849  {
850  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
851 
852  if( !jt_next )
853  break;
854 
855  p0_pushed += aForce.Resize( 2 );
856  }
857 
858  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
859  pushedVia->SetPos( p0_pushed );
860  pushedVia->Mark( aVia->Marker() );
861 
862  for( ITEM* item : jt->LinkList() )
863  {
864  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
865  {
866  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
867  LINE_PAIR lp;
868  int segIndex;
869 
870  lp.first = assembleLine( li, &segIndex );
871 
872  if( lp.first.HasLockedSegments() )
873  return SH_TRY_WALK;
874 
875  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
876 
877  if( segIndex == 0 )
878  lp.first.Reverse();
879 
880  lp.second = lp.first;
881  lp.second.ClearLinks();
882  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
883  lp.second.AppendVia( *pushedVia );
884  draggedLines.push_back( lp );
885  }
886  }
887 
888 
889  pushedVia->SetRank( aCurrentRank - 1 );
890 
891 
892  if( aVia->Marker() & MK_HEAD ) // push
893  {
894  m_draggedVia = pushedVia.get();
895  }
896  else
897  { // shove
898  if( jt->IsStitchingVia() )
899  pushLineStack( LINE( *pushedVia ) );
900  }
901 
902 
903  PNS_DBG( Dbg(), AddPoint, aVia->Pos(), LIGHTGREEN, 100000, "via-pre" );
904  PNS_DBG( Dbg(), AddPoint, pushedVia->Pos(), LIGHTRED, 100000, "via-post" );
905 
906  replaceItems( aVia, std::move( pushedVia ) );
907 
908  for( LINE_PAIR lp : draggedLines )
909  {
910  if( lp.first.Marker() & MK_HEAD )
911  {
912  lp.second.Mark( MK_HEAD );
913 
914  if( m_multiLineMode )
915  return SH_INCOMPLETE;
916 
917  m_newHead = lp.second;
918  }
919 
920  unwindLineStack( &lp.first );
921 
922  if( lp.second.SegmentCount() )
923  {
924  replaceLine( lp.first, lp.second );
925  lp.second.SetRank( aCurrentRank - 1 );
926 
927  if( !pushLineStack( lp.second, true ) )
928  return SH_INCOMPLETE;
929  }
930  else
931  {
932  m_currentNode->Remove( lp.first );
933  }
934 
935  PNS_DBG( Dbg(), AddLine, lp.first.CLine(), LIGHTGREEN, 10000, "fan-pre" );
936  PNS_DBG( Dbg(), AddLine, lp.second.CLine(), LIGHTRED, 10000, "fan-post" );
937  }
938 
939  return SH_OK;
940 }
941 
942 
943 /*
944  * Calculate the minimum translation vector required to resolve a collision with a via and
945  * shove the via by that distance.
946  */
948 {
949  int clearance = getClearance( aCurrent, aObstacleVia );
950  VECTOR2I mtv;
951  int rank = -1;
952 
953  bool lineCollision = false;
954  bool viaCollision = false;
955  VECTOR2I mtvLine, mtvVia;
956 
957  PNS_DBG( Dbg(), BeginGroup, "push-via-by-line" );
958 
959  if( aCurrent->OfKind( ITEM::LINE_T ) )
960  {
961  LINE* currentLine = (LINE*) aCurrent;
962 
963 #if 0
964  m_logger.NewGroup( "push-via-by-line", m_iter );
965  m_logger.Log( currentLine, 4, "current" );
966 #endif
967 
968  lineCollision = aObstacleVia->Shape()->Collide( currentLine->Shape(), clearance + currentLine->Width() / 2, &mtvLine );
969 
970  // Check the via if present. Via takes priority.
971  if( currentLine->EndsWithVia() )
972  {
973  const VIA& currentVia = currentLine->Via();
974  int viaClearance = getClearance( &currentVia, aObstacleVia );
975 
976  viaCollision = aObstacleVia->Shape()->Collide( currentVia.Shape(), viaClearance, &mtvVia );
977  }
978  }
979  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
980  {
981  // TODO: is this possible at all? We don't shove solids.
982  return SH_INCOMPLETE;
983  }
984 
985  // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
986  if( viaCollision )
987  mtv = mtvVia;
988  else if ( lineCollision )
989  mtv = -mtvLine;
990  else
991  mtv = VECTOR2I(0, 0);
992 
993  SHOVE::SHOVE_STATUS st = pushOrShoveVia( aObstacleVia, -mtv, rank );
994 
995  PNS_DBGN( Dbg(), EndGroup );
996 
997  return st;
998 }
999 
1000 
1001 /*
1002  * TODO describe....
1003  */
1005 {
1006  int n = 0;
1007  LINE cur( aCurrent );
1008  cur.ClearLinks();
1009 
1010  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
1011  LINE shoved( aCurrent );
1012  shoved.ClearLinks();
1013 
1014  cur.RemoveVia();
1015  unwindLineStack( &aCurrent );
1016 
1017  for( ITEM* item : jt->LinkList() )
1018  {
1019  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
1020  {
1021  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1022  LINE head = assembleLine( li );
1023 
1024  head.AppendVia( *aObstacleVia );
1025 
1026  SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
1027 
1028  if( st != SH_OK )
1029  {
1030 #if 0
1031  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
1032  m_logger.Log( aObstacleVia, 0, "the-via" );
1033  m_logger.Log( &aCurrent, 1, "current-line" );
1034  m_logger.Log( &shoved, 3, "shoved-line" );
1035 #endif
1036 
1037  return st;
1038  }
1039 
1040  cur.SetShape( shoved.CLine() );
1041  n++;
1042  }
1043  }
1044 
1045  if( !n )
1046  {
1047 #if 0
1048  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
1049  m_logger.Log( aObstacleVia, 0, "the-via" );
1050  m_logger.Log( &aCurrent, 1, "current-line" );
1051 #endif
1052 
1053  LINE head( aCurrent );
1054  head.Line().Clear();
1055  head.AppendVia( *aObstacleVia );
1056  head.ClearLinks();
1057 
1058  SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
1059 
1060  if( st != SH_OK )
1061  return st;
1062 
1063  cur.SetShape( shoved.CLine() );
1064  }
1065 
1066  if( aCurrent.EndsWithVia() )
1067  shoved.AppendVia( aCurrent.Via() );
1068 
1069 #if 0
1070  m_logger.NewGroup( "on-reverse-via", m_iter );
1071  m_logger.Log( aObstacleVia, 0, "the-via" );
1072  m_logger.Log( &aCurrent, 1, "current-line" );
1073  m_logger.Log( &shoved, 3, "shoved-line" );
1074 #endif
1075  int currentRank = aCurrent.Rank();
1076  replaceLine( aCurrent, shoved );
1077 
1078  if( !pushLineStack( shoved ) )
1079  return SH_INCOMPLETE;
1080 
1081  shoved.SetRank( currentRank );
1082 
1083  return SH_OK;
1084 }
1085 
1086 
1088 {
1089  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1090  {
1091  if( i->ContainsLink( aSeg ) )
1092  i = m_lineStack.erase( i );
1093  else
1094  i++;
1095  }
1096 
1097  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1098  {
1099  if( i->ContainsLink( aSeg ) )
1100  i = m_optimizerQueue.erase( i );
1101  else
1102  i++;
1103  }
1104 }
1105 
1106 
1108 {
1109  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1110  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1111  else if( aItem->OfKind( ITEM::LINE_T ) )
1112  {
1113  LINE* l = static_cast<LINE*>( aItem );
1114 
1115  for( LINKED_ITEM* seg : l->Links() )
1116  unwindLineStack( seg );
1117  }
1118 }
1119 
1120 
1121 bool SHOVE::pushLineStack( const LINE& aL, bool aKeepCurrentOnTop )
1122 {
1123  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1124  return false;
1125 
1126  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1127  {
1128  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1129  }
1130  else
1131  {
1132  m_lineStack.push_back( aL );
1133  }
1134 
1135  m_optimizerQueue.push_back( aL );
1136 
1137  return true;
1138 }
1139 
1141 {
1142  LINE& l = m_lineStack.back();
1143 
1144  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1145  {
1146  bool found = false;
1147 
1148  for( LINKED_ITEM* s : l.Links() )
1149  {
1150  if( i->ContainsLink( s ) )
1151  {
1152  i = m_optimizerQueue.erase( i );
1153  found = true;
1154  break;
1155  }
1156  }
1157 
1158  if( !found )
1159  i++;
1160  }
1161 
1162  m_lineStack.pop_back();
1163 }
1164 
1165 
1166 /*
1167  * Resolve the next collision.
1168  */
1170 {
1171  LINE currentLine = m_lineStack.back();
1172  NODE::OPT_OBSTACLE nearest;
1173  SHOVE_STATUS st = SH_NULL;
1174 
1175 #ifdef DEBUG
1176  Dbg()->SetIteration( aIter );
1177 #endif
1178 
1179  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1180  {
1181  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1182  if (nearest)
1183  PNS_DBG( Dbg(), Message, wxString::Format( "nearest %p %s", nearest->m_item, nearest->m_item->KindStr() ) );
1184 
1185  if( nearest )
1186  break;
1187  }
1188 
1189  if( !nearest )
1190  {
1191  m_lineStack.pop_back();
1192  PNS_DBG( Dbg(), Message, "no-nearest-item ");
1193  return SH_OK;
1194  }
1195 
1196  ITEM* ni = nearest->m_item;
1197 
1198  unwindLineStack( ni );
1199 
1200  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1201  {
1202  // Collision with a higher-ranking object (ie: one that we've already shoved)
1203  //
1204  switch( ni->Kind() )
1205  {
1206  case ITEM::VIA_T:
1207  {
1208  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-via", aIter ) );
1209 
1210  if( currentLine.EndsWithVia() )
1211  {
1212  st = SH_INCOMPLETE;
1213  }
1214  else
1215  {
1216  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1217  }
1218 
1219  break;
1220  }
1221 
1222  case ITEM::SEGMENT_T:
1223  {
1224  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-segment ", aIter ) );
1225  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1226 
1227  popLineStack();
1228  st = onCollidingLine( revLine, currentLine );
1229  if( !pushLineStack( revLine ) )
1230  return SH_INCOMPLETE;
1231 
1232  break;
1233  }
1234 
1235  case ITEM::ARC_T:
1236  {
1237  //TODO(snh): Handle Arc shove separate from track
1238  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-arc ", aIter ) );
1239  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1240 
1241  popLineStack();
1242  st = onCollidingLine( revLine, currentLine );
1243  if( !pushLineStack( revLine ) )
1244  return SH_INCOMPLETE;
1245 
1246  break;
1247  }
1248 
1249  default:
1250  assert( false );
1251  }
1252  }
1253  else
1254  {
1255  // Collision with a lower-ranking object or a solid
1256  //
1257  switch( ni->Kind() )
1258  {
1259  case ITEM::SEGMENT_T:
1260  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: collide-segment ", aIter ) );
1261 
1262  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1263 
1264  if( st == SH_TRY_WALK )
1265  st = onCollidingSolid( currentLine, ni );
1266 
1267  break;
1268 
1269  //TODO(snh): Customize Arc collide
1270  case ITEM::ARC_T:
1271  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: collide-arc ", aIter ) );
1272 
1273  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1274 
1275  if( st == SH_TRY_WALK )
1276  st = onCollidingSolid( currentLine, ni );
1277 
1278  break;
1279 
1280  case ITEM::VIA_T:
1281  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: shove-via ", aIter ) );
1282  st = onCollidingVia( &currentLine, (VIA*) ni );
1283 
1284  if( st == SH_TRY_WALK )
1285  st = onCollidingSolid( currentLine, ni );
1286 
1287  break;
1288 
1289  case ITEM::SOLID_T:
1290  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: walk-solid ", aIter ) );
1291  st = onCollidingSolid( currentLine, (SOLID*) ni );
1292  break;
1293 
1294  default:
1295  break;
1296  }
1297  }
1298 
1299  return st;
1300 }
1301 
1302 
1303 /*
1304  * Resolve collisions.
1305  * Each iteration pushes the next colliding object out of the way. Iterations are continued as
1306  * long as they propagate further collisions, or until the iteration timeout or max iteration
1307  * count is reached.
1308  */
1310 {
1311  SHOVE_STATUS st = SH_OK;
1312 
1314 
1315  PNS_DBG( Dbg(), Message, wxString::Format( "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1316  m_currentNode->JointCount() ) );
1317 
1318  int iterLimit = Settings().ShoveIterationLimit();
1319  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1320 
1321  m_iter = 0;
1322 
1323  timeLimit.Restart();
1324 
1325  if( m_lineStack.empty() && m_draggedVia )
1326  {
1327  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1328  // the stack.
1330  }
1331 
1332  while( !m_lineStack.empty() )
1333  {
1334  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: node %p stack %d ", m_iter, m_currentNode, (int) m_lineStack.size() ) );
1335 
1336  st = shoveIteration( m_iter );
1337 
1338  m_iter++;
1339 
1340  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1341  {
1342  st = SH_INCOMPLETE;
1343  break;
1344  }
1345  }
1346 
1347  return st;
1348 }
1349 
1350 
1352 {
1353  OPT_BOX2I area;
1354 
1355  if( !m_nodeStack.empty() )
1356  area = m_nodeStack.back().m_affectedArea;
1357 
1358  if( area && m_affectedArea)
1359  area->Merge( *m_affectedArea );
1360  else if( !area )
1361  area = m_affectedArea;
1362 
1363  return area;
1364 }
1365 
1366 
1368 {
1369  SHOVE_STATUS st = SH_OK;
1370 
1371  m_multiLineMode = false;
1372 
1373  if( Dbg() )
1374  {
1375  Dbg()->Message( wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) );
1376  }
1377 
1378  // empty head? nothing to shove...
1379 
1380  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1381  return SH_INCOMPLETE;
1382 
1383  LINE head( aCurrentHead );
1384  head.ClearLinks();
1385 
1386  m_lineStack.clear();
1387  m_optimizerQueue.clear();
1388  m_newHead = OPT_LINE();
1389 #if 0
1390  m_logger.Clear();
1391 #endif
1392 
1393  // Pop NODEs containing previous shoves which are no longer necessary
1394  //
1395  ITEM_SET headSet;
1396  headSet.Add( aCurrentHead );
1397 
1398  VIA_HANDLE dummyVia;
1399 
1400  NODE* parent = reduceSpringback( headSet, dummyVia );
1401 
1402  // Create a new NODE to store this version of the world
1403  //
1404  m_currentNode = parent->Branch();
1406  m_currentNode->Add( head );
1407 
1408  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1409 
1410  if( !head.EndsWithVia() )
1411  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1412 
1413  head.Mark( MK_HEAD );
1414  head.SetRank( 100000 );
1415 
1416  if ( Dbg() )
1417  {
1418 
1419  Dbg()->BeginGroup( "initial" );
1420  Dbg()->AddLine(head.CLine(), CYAN, head.Width(), "head" );
1421  Dbg()->EndGroup();
1422  }
1423 
1424  if( head.EndsWithVia() )
1425  {
1426  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1427  headVia->Mark( MK_HEAD );
1428  headVia->SetRank( 100000 );
1429  m_currentNode->Add( std::move( headVia ) );
1430  }
1431 
1432  if( !pushLineStack( head ) )
1433  {
1434  delete m_currentNode;
1435  m_currentNode = parent;
1436 
1437  return SH_INCOMPLETE;
1438  }
1439 
1440  st = shoveMainLoop();
1441 
1442  if( st == SH_OK )
1443  {
1445 
1446  if( m_newHead )
1448  else
1449  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1450  }
1451 
1453 
1454  PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1455  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter ) );
1456 
1457  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1458  {
1460  }
1461  else
1462  {
1463  delete m_currentNode;
1464 
1465  m_currentNode = parent;
1466  m_newHead = OPT_LINE();
1467  }
1468 
1469  if(m_newHead)
1470  m_newHead->Unmark();
1471 
1472  if( m_newHead && head.EndsWithVia() )
1473  {
1474  VIA v = head.Via();
1475  v.SetPos( m_newHead->CPoint( -1 ) );
1476  m_newHead->AppendVia(v);
1477  }
1478 
1479  return st;
1480 }
1481 
1482 
1484 {
1485  SHOVE_STATUS st = SH_OK;
1486 
1487  m_multiLineMode = true;
1488 
1489  ITEM_SET headSet;
1490 
1491  for( const ITEM* item : aHeadSet.CItems() )
1492  {
1493  const LINE* headOrig = static_cast<const LINE*>( item );
1494 
1495  // empty head? nothing to shove...
1496  if( !headOrig->SegmentCount() )
1497  return SH_INCOMPLETE;
1498 
1499  headSet.Add( *headOrig );
1500  }
1501 
1502  m_lineStack.clear();
1503  m_optimizerQueue.clear();
1504 #if 0
1505  m_logger.Clear();
1506 #endif
1507 
1508  VIA_HANDLE dummyVia;
1509 
1510  NODE* parent = reduceSpringback( headSet, dummyVia );
1511 
1512  m_currentNode = parent->Branch();
1514  int n = 0;
1515 
1516  for( const ITEM* item : aHeadSet.CItems() )
1517  {
1518  const LINE* headOrig = static_cast<const LINE*>( item );
1519  LINE head( *headOrig );
1520  head.ClearLinks();
1521 
1522  m_currentNode->Add( head );
1523 
1524  head.Mark( MK_HEAD );
1525  head.SetRank( 100000 );
1526  n++;
1527 
1528  if( !pushLineStack( head ) )
1529  return SH_INCOMPLETE;
1530 
1531  if( head.EndsWithVia() )
1532  {
1533  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1534  headVia->Mark( MK_HEAD );
1535  headVia->SetRank( 100000 );
1536  m_currentNode->Add( std::move( headVia ) );
1537  }
1538  }
1539 
1540  st = shoveMainLoop();
1541 
1542  if( st == SH_OK )
1544 
1546 
1547  PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1548  ( st == SH_OK ? "OK" : "FAILURE"), m_iter ) );
1549 
1550  if( st == SH_OK )
1551  {
1553  }
1554  else
1555  {
1556  delete m_currentNode;
1557  m_currentNode = parent;
1558  }
1559 
1560  return st;
1561 }
1562 
1563 static VIA* findViaByHandle ( NODE *aNode, const VIA_HANDLE& handle )
1564 {
1565  JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1566 
1567  if( !jt )
1568  return nullptr;
1569 
1570  for( ITEM* item : jt->LinkList() )
1571  {
1572  if( item->OfKind( ITEM::VIA_T ) )
1573  {
1574  if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1575  return static_cast<VIA*>( item );
1576  }
1577  }
1578 
1579  return nullptr;
1580 }
1581 
1583 {
1584  SHOVE_STATUS st = SH_OK;
1585 
1586  m_lineStack.clear();
1587  m_optimizerQueue.clear();
1588  m_newHead = OPT_LINE();
1589  m_draggedVia = NULL;
1590 
1591  VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1592 
1593  if( !viaToDrag )
1594  return SH_INCOMPLETE;
1595 
1596  // Pop NODEs containing previous shoves which are no longer necessary
1597  ITEM_SET headSet;
1598 
1599  VIA headVia ( *viaToDrag );
1600  headVia.SetPos( aWhere );
1601  headSet.Add( headVia );
1602  VIA_HANDLE prevViaHandle;
1603  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1604 
1605  if( prevViaHandle.valid )
1606  {
1607  aNewVia = prevViaHandle;
1608  viaToDrag = findViaByHandle( parent, prevViaHandle );
1609  }
1610 
1611  // Create a new NODE to store this version of the world
1612  //
1613  m_currentNode = parent->Branch();
1615 
1616  viaToDrag->Mark( MK_HEAD );
1617  viaToDrag->SetRank( 100000 );
1618 
1619  // Push the via to its new location
1620  //
1621  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1622 
1623  // Shove any colliding objects out of the way
1624  //
1625  if( st == SH_OK )
1626  st = shoveMainLoop();
1627 
1628  if( st == SH_OK )
1630 
1631  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1632  {
1633  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1634 
1635  if (!m_draggedVia)
1636  m_draggedVia = viaToDrag;
1637 
1638  aNewVia = m_draggedVia->MakeHandle();
1639 
1641  }
1642  else
1643  {
1644  delete m_currentNode;
1645  m_currentNode = parent;
1646  }
1647 
1648  return st;
1649 }
1650 
1651 
1653 {
1654  for( auto link : aLine->Links() )
1655  {
1656  if( auto seg = dyn_cast<SEGMENT*>( link ) )
1657  {
1658  auto it = m_rootLineHistory.find( seg );
1659 
1660  if( it != m_rootLineHistory.end() )
1661  return it->second;
1662  }
1663  }
1664 
1665  return nullptr;
1666 }
1667 
1668 
1670 {
1671  OPTIMIZER optimizer( aNode );
1672  int optFlags = 0;
1673  int n_passes = 0;
1674 
1676 
1677  OPT_BOX2I area = totalAffectedArea();
1678 
1679  int maxWidth = 0;
1680 
1681  for( LINE& line : m_optimizerQueue )
1682  maxWidth = std::max( line.Width(), maxWidth );
1683 
1684  if( area )
1685  {
1686  area->Inflate( maxWidth );
1687  area = area->Intersect( VisibleViewArea() );
1688  }
1689 
1690  switch( effort )
1691  {
1692  case OE_LOW:
1693  optFlags |= OPTIMIZER::MERGE_OBTUSE;
1694  n_passes = 1;
1695  break;
1696 
1697  case OE_MEDIUM:
1698  optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1699 
1700  n_passes = 2;
1701  break;
1702 
1703  case OE_FULL:
1704  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1705  n_passes = 2;
1706  break;
1707 
1708  default:
1709  break;
1710  }
1711 
1712  optFlags |= OPTIMIZER::LIMIT_CORNER_COUNT;
1713 
1714  if( area )
1715  {
1716  if( Dbg() )
1717  {
1718  Dbg()->AddBox( *area, BLUE, "opt-area" );
1719  }
1720 
1721  optFlags |= OPTIMIZER::RESTRICT_AREA;
1722  optimizer.SetRestrictArea( *area, false );
1723  }
1724 
1725  if( Settings().SmartPads() )
1726  optFlags |= OPTIMIZER::SMART_PADS;
1727 
1728  optimizer.SetEffortLevel( optFlags );
1729  optimizer.SetCollisionMask( ITEM::ANY_T );
1730 
1731  for( int pass = 0; pass < n_passes; pass++ )
1732  {
1733  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1734 
1735  for( LINE& line : m_optimizerQueue)
1736  {
1737  if( !( line.Marker() & MK_HEAD ) )
1738  {
1739  LINE optimized;
1740  LINE* root = findRootLine( &line );
1741 
1742  if( optimizer.Optimize( &line, &optimized, root ) )
1743  {
1744  replaceLine( line, optimized, false, aNode );
1745  line = optimized; // keep links in the lines in the queue up to date
1746  }
1747  }
1748  }
1749  }
1750 }
1751 
1752 
1754 {
1755  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1756 }
1757 
1758 
1759 const LINE SHOVE::NewHead() const
1760 {
1761  assert( m_newHead );
1762 
1763  return *m_newHead;
1764 }
1765 
1766 
1767 void SHOVE::SetInitialLine( LINE& aInitial )
1768 {
1769  m_root = m_root->Branch();
1770  m_root->Remove( aInitial );
1771 }
1772 
1773 
1775 {
1776  SPRINGBACK_TAG sp;
1777  sp.m_node = aNode;
1778  sp.m_locked = true;
1779 
1780  m_nodeStack.push_back(sp);
1781  return true;
1782 }
1783 
1784 
1786 {
1787  bool found = false;
1788 
1789  auto iter = m_nodeStack.begin();
1790 
1791  while( iter != m_nodeStack.end() )
1792  {
1793  if ( iter->m_node == aNode )
1794  {
1795  found = true;
1796  break;
1797  }
1798  iter++;
1799  }
1800 
1801  if( !found )
1802  return false;
1803 
1804  auto start = iter;
1805 
1806  aNode->KillChildren();
1807  m_nodeStack.erase( start, m_nodeStack.end() );
1808 
1809  return true;
1810 }
1811 
1812 
1814 {
1815  auto iter = m_nodeStack.begin();
1816 
1817  while( iter != m_nodeStack.end() )
1818  {
1819  if ( iter->m_node == aNode )
1820  {
1821  iter->m_locked = false;
1822  break;
1823  }
1824  iter++;
1825  }
1826 }
1827 
1828 }
1829 
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1404
LINE * findRootLine(LINE *aLine)
Definition: pns_shove.cpp:1652
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1121
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:76
#define PNS_DBGN(dbg, method)
virtual void SetIteration(int iter)
Base class for PNS router board items.
Definition: pns_item.h:55
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:122
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:281
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:182
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
long long int Length() const
Function Length()
void popLineStack()
Definition: pns_shove.cpp:1140
virtual void AddBox(BOX2I aB, const KIGFX::COLOR4D &aColor, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
int m_restrictSpringbackTagId
Definition: pns_shove.h:170
virtual int Layer() const
Definition: pns_item.h:156
Keep the router "world" - i.e.
Definition: pns_node.h:144
virtual void Message(const wxString msg, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
VECTOR2I::extended_type ecoord
Definition: pns_shove.cpp:47
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:631
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1087
virtual void Mark(int aMarker) const
Definition: pns_item.h:208
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
bool Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculate a line tightly wrapping a convex hull of an obstacle object (aObstacle).
int SegmentCount() const
Definition: pns_line.h:139
const LINE NewHead() const
Definition: pns_shove.cpp:1759
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:146
SHOVE_STATUS shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
Definition: pns_shove.cpp:260
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:527
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
Definition: pns_via.cpp:74
int Rank() const override
Definition: pns_line.cpp:1050
Base class for all P&S algorithms (shoving, walkaround, line placement, dragging, etc....
Definition: pns_algo_base.h:42
void SetRestrictArea(const BOX2I &aArea, bool aStrict=true)
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:165
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, const KIGFX::COLOR4D &aColor, int aWidth, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
bool RewindSpringbackTo(NODE *aNode)
Definition: pns_shove.cpp:1785
void SetSingleDirection(bool aForceSingleDirection)
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:183
void RemoveVia()
Definition: pns_line.h:194
NODE * m_root
Definition: pns_shove.h:168
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:96
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:1027
virtual void EndGroup(const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
const SEG & Seg() const
Definition: pns_segment.h:84
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:376
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:249
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:109
int PointCount() const
Function PointCount()
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:822
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_via.h:128
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:127
const VECTOR2I & Pos() const
Definition: pns_via.h:99
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:165
bool EndsWithVia() const
Definition: pns_line.h:191
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:810
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:590
int Start() const
Definition: pns_layerset.h:82
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:161
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:1004
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:94
void SetCollisionMask(int aMask)
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
Definition: sch_symbol.cpp:70
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
bool IsLinkedChecked() const
Assign a shape to the line (a polyline/line chain).
Definition: pns_line.h:120
Definition: color4d.h:67
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1351
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:757
const SHAPE * Shape() const override
Modifiable accessor to the underlying shape.
Definition: pns_line.h:133
SHOVE_STATUS ShoveLines(const LINE &aCurrentHead)
Definition: pns_shove.cpp:1367
const VECTOR2I & CPoint(int aIndex) const
Function Point()
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
Definition: pns_joint.h:42
int Diameter() const
Definition: pns_via.h:111
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:100
void KillChildren()
Definition: pns_node.cpp:1369
bool AddLockedSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:1774
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:920
#define NULL
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:947
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1669
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:144
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1169
int Net() const
Definition: pns_item.h:150
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1563
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
Definition: color4d.h:57
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
void RestrictToSet(bool aEnabled, const std::set< ITEM * > &aSet)
#define PNS_DBG(dbg, method,...)
SHOVE(NODE *aWorld, ROUTER *aRouter)
Definition: pns_shove.cpp:151
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:97
Definition: color4d.h:58
void SetSolidsOnly(bool aSolidsOnly)
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:166
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:785
virtual void SetRank(int aRank)
Definition: pns_item.h:212
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:460
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:195
const std::string Format() const override
void SetRank(int aRank) override
Definition: pns_line.cpp:1040
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
Definition: color4d.h:59
void UnlockSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:1813
void Clear()
Definition: pns_logger.cpp:40
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1104
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:61
SHOVE_STATUS ShoveDraggingVia(const VIA_HANDLE aOldVia, const VECTOR2I &aWhere, VIA_HANDLE &aNewVia)
Definition: pns_shove.cpp:1582
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:101
virtual void AddSegment(SEG aS, const KIGFX::COLOR4D &aColor, const std::string aName, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
Definition: color4d.h:48
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:775
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1414
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:163
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
virtual void BeginGroup(const std::string name, const SRC_LOCATION_INFO &aSrcLoc=SRC_LOCATION_INFO())
const BOX2I & VisibleViewArea() const
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
Definition: color4d.h:56
VIA * m_draggedVia
Definition: pns_shove.h:175
virtual int Rank() const
Definition: pns_item.h:213
virtual int Marker() const override
Definition: pns_line.cpp:108
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:155
Reduce corner cost by merging obtuse segments.
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:265
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:433
const SHAPE_LINE_CHAIN CLine() const
Definition: pns_arc.h:92
bool HasLoops() const
Definition: pns_line.cpp:1136
LAYER_RANGE layers
Definition: pns_via.h:44
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
Definition: pns_shove.cpp:195
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:136
const ENTRIES & CItems() const
Definition: pns_itemset.h:139
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1309
bool IsLocked() const
Definition: pns_item.h:225
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:515
void SetInitialLine(LINE &aInitial)
Definition: pns_shove.cpp:1767
boost::optional< T > OPT
Definition: optional.h:7
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
Definition: pns_algo_base.h:73
VECTOR2I pos
Definition: pns_via.h:43
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:128
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:94
void Clear()
Function Clear() Removes all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:127
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:135
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:51
void SetEffortLevel(int aEffort)
bool m_multiLineMode
Definition: pns_shove.h:179
OPT_LINE m_newHead
Definition: pns_shove.h:172
std::vector< LINE > m_lineStack
Definition: pns_shove.h:164
SHOVE_STATUS ShoveMultiLines(const ITEM_SET &aHeadSet)
Definition: pns_shove.cpp:1483
NODE * m_currentNode
Definition: pns_shove.h:169
const VIA & Via() const
Definition: pns_line.h:196
int Drill() const
Definition: pns_via.h:119
Push and Shove diff pair dimensions (gap) settings dialog.
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:64
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:210
bool Expired() const
Definition: time_limit.cpp:39
virtual LINE * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:81
LOGGER m_logger
Definition: pns_shove.h:174
int m_iter
Definition: pns_shove.h:177
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:215
NODE * CurrentNode()
Definition: pns_shove.cpp:1753
void SetIterationLimit(const int aIterLimit)
const LAYER_RANGE & Layers() const
Definition: pns_item.h:152
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1134
virtual int Marker() const
Definition: pns_item.h:210
int m_forceClearance
Definition: pns_shove.h:178
virtual void Unmark(int aMarker=-1) const override
Definition: pns_line.cpp:99
Reroute pad exits.
bool HasLockedSegments() const
Definition: pns_line.cpp:1246
virtual void Mark(int aMarker) const override
Definition: pns_line.cpp:89
TIME_LIMIT ShoveTimeLimit() const