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