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( "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( "attempt %d fail vfirst-last", attempt ) );
333  continue;
334  }
335 
336  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
337  {
338  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail vend-start\n", attempt ) );
339  continue;
340  }
341 
342  if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
343  {
344  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail direction-check",
345  attempt ) );
346  aResultLine.SetShape( l.CLine() );
347  continue;
348  }
349 
350  if( path.SelfIntersecting() )
351  {
352  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail self-intersect",
353  attempt ) );
354  continue;
355  }
356 
357  bool colliding = l.Collide( &aCurLine, m_currentNode );
358 
359 #ifdef DEBUG
360  char str[128];
361  sprintf( str, "att-%d-shoved", attempt );
362  Dbg()->AddLine( l.CLine(), BLUE, 20000, str );
363 #endif
364 
365  if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
366  {
367  JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
368 
369  for( ITEM* item : jtStart->LinkList() )
370  {
371  if( item->Collide( &l, m_currentNode ) )
372  colliding = true;
373  }
374  }
375 
376  if( colliding )
377  {
378  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail coll-check", attempt ) );
379  continue;
380  }
381 
382  aResultLine.SetShape( l.CLine() );
383 
384  return SH_OK;
385  }
386 
387  return SH_INCOMPLETE;
388 }
389 
390 
391 /*
392  * Push aObstacleLine line away from aCurLine by the clearance distance, and return the result in
393  * aResultLine.
394  */
395 SHOVE::SHOVE_STATUS SHOVE::ShoveObstacleLine( const LINE& aCurLine, const LINE& aObstacleLine,
396  LINE& aResultLine )
397 {
398  aResultLine.ClearLinks();
399 
400  bool obstacleIsHead = false;
401 
402  for( LINKED_ITEM* s : aObstacleLine.Links() )
403  {
404  if( s->Marker() & MK_HEAD )
405  {
406  obstacleIsHead = true;
407  break;
408  }
409  }
410 
411  SHOVE_STATUS rv;
412  bool viaOnEnd = aCurLine.EndsWithVia();
413 
414  if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
415  {
416  // Shove aObstacleLine to the hull of aCurLine's via.
417 
418  rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
419  }
420  else
421  {
422  // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
423  // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
424  // hull it will be at the appropriate clearance.
425 
426  int obstacleLineWidth = aObstacleLine.Width();
427  int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
428  int currentLineSegmentCount = aCurLine.SegmentCount();
429  HULL_SET hulls;
430 
431  hulls.reserve( currentLineSegmentCount + 1 );
432 
433 #ifdef DEBUG
434  Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d",
435  aCurLine.Net(), aObstacleLine.Net(), clearance ) );
436 #endif
437 
438  for( int i = 0; i < currentLineSegmentCount; i++ )
439  {
440  SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
441  int extra = 0;
442 
443  // Arcs need additional clearance to ensure the hulls are always bigger than the arc
444  if( aCurLine.CLine().IsArcSegment( i ) )
446 
447  SHAPE_LINE_CHAIN hull =
448  seg.Hull( clearance + extra, obstacleLineWidth, aObstacleLine.Layer() );
449 
450  hulls.push_back( hull );
451  }
452 
453  if( viaOnEnd )
454  {
455  const VIA& via = aCurLine.Via();
456  int viaClearance = getClearance( &via, &aObstacleLine );
457  int holeClearance = getHoleClearance( &via, &aObstacleLine );
458 
459  if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
460  viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
461 
462  hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
463  }
464 
465 #ifdef DEBUG
466  char str[128];
467  sprintf( str, "current-cl-%d", clearance );
468  Dbg()->AddLine( aCurLine.CLine(), BLUE, 20000, str );
469 #endif
470 
471  rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
472  }
473 
474  if( obstacleIsHead )
475  aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
476 
477  return rv;
478 }
479 
480 
481 /*
482  * TODO describe....
483  */
485 {
486  int segIndex;
487  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
488  LINE shovedLine( obstacleLine );
489  SEGMENT tmp( *aObstacleSeg );
490 
491  if( obstacleLine.HasLockedSegments() )
492  return SH_TRY_WALK;
493 
494  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
495 
496  const double extensionWalkThreshold = 1.0;
497 
498  double obsLen = obstacleLine.CLine().Length();
499  double shovedLen = shovedLine.CLine().Length();
500  double extensionFactor = 0.0;
501 
502  if( obsLen != 0.0f )
503  extensionFactor = shovedLen / obsLen - 1.0;
504 
505  if( extensionFactor > extensionWalkThreshold )
506  return SH_TRY_WALK;
507 
508  assert( obstacleLine.LayersOverlap( &shovedLine ) );
509 
510  if( Dbg() )
511  {
512  Dbg()->BeginGroup( wxString::Format( "on-colliding-segment-iter-%d",
513  m_iter ).ToStdString() );
514  Dbg()->AddSegment( tmp.Seg(), WHITE, "obstacle-segment" );
515  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
516  Dbg()->AddLine( obstacleLine.CLine(), GREEN, 10000, "obstacle-line" );
517  Dbg()->AddLine( shovedLine.CLine(), BLUE, 10000, "shoved-line" );
518 
519  if( rv == SH_OK )
520  Dbg()->Message( "Shove success" );
521  else
522  Dbg()->Message( "Shove FAIL" );
523 
524  Dbg()->EndGroup();
525  }
526 
527  if( rv == SH_OK )
528  {
529  if( shovedLine.Marker() & MK_HEAD )
530  {
531  if( m_multiLineMode )
532  return SH_INCOMPLETE;
533 
534  m_newHead = shovedLine;
535  }
536 
537  int rank = aCurrent.Rank();
538  shovedLine.SetRank( rank - 1 );
539 
540  sanityCheck( &obstacleLine, &shovedLine );
541  replaceLine( obstacleLine, shovedLine );
542 
543  if( !pushLineStack( shovedLine ) )
544  rv = SH_INCOMPLETE;
545  }
546 
547  return rv;
548 }
549 
550 
551 /*
552  * TODO describe....
553  */
555 {
556  int segIndex;
557  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
558  LINE shovedLine( obstacleLine );
559  ARC tmp( *aObstacleArc );
560 
561  if( obstacleLine.HasLockedSegments() )
562  return SH_TRY_WALK;
563 
564  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
565 
566  const double extensionWalkThreshold = 1.0;
567 
568  double obsLen = obstacleLine.CLine().Length();
569  double shovedLen = shovedLine.CLine().Length();
570  double extensionFactor = 0.0;
571 
572  if( obsLen != 0.0f )
573  extensionFactor = shovedLen / obsLen - 1.0;
574 
575  if( extensionFactor > extensionWalkThreshold )
576  return SH_TRY_WALK;
577 
578  assert( obstacleLine.LayersOverlap( &shovedLine ) );
579 
580  if ( Dbg() )
581  {
582  Dbg()->BeginGroup( wxString::Format( "on-colliding-arc-iter-%d", m_iter ).ToStdString() );
583  Dbg()->AddLine( tmp.CLine(), WHITE, 10000, "obstacle-segment" );
584  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
585  Dbg()->AddLine( obstacleLine.CLine(), GREEN, 10000, "obstacle-line" );
586  Dbg()->AddLine( shovedLine.CLine(), BLUE, 10000, "shoved-line" );
587  Dbg()->EndGroup();
588  }
589 
590  if( rv == SH_OK )
591  {
592  if( shovedLine.Marker() & MK_HEAD )
593  {
594  if( m_multiLineMode )
595  return SH_INCOMPLETE;
596 
597  m_newHead = shovedLine;
598  }
599 
600  int rank = aCurrent.Rank();
601  shovedLine.SetRank( rank - 1 );
602 
603  sanityCheck( &obstacleLine, &shovedLine );
604  replaceLine( obstacleLine, shovedLine );
605 
606  if( !pushLineStack( shovedLine ) )
607  rv = SH_INCOMPLETE;
608  }
609 
610  return rv;
611 }
612 
613 
614 /*
615  * TODO describe....
616  */
618 {
619  LINE shovedLine( aObstacle );
620 
621  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
622 
623  Dbg()->BeginGroup( "on-colliding-line" );
624  Dbg()->AddLine( aObstacle.CLine(), RED, 100000, "obstacle-line" );
625  Dbg()->AddLine( aCurrent.CLine(), GREEN, 150000, "current-line" );
626  Dbg()->AddLine( shovedLine.CLine(), BLUE, 200000, "shoved-line" );
627 
628  if( rv == SH_OK )
629  {
630  if( shovedLine.Marker() & MK_HEAD )
631  {
632  if( m_multiLineMode )
633  return SH_INCOMPLETE;
634 
635  m_newHead = shovedLine;
636  }
637 
638  sanityCheck( &aObstacle, &shovedLine );
639  replaceLine( aObstacle, shovedLine );
640 
641  int rank = aObstacle.Rank();
642  shovedLine.SetRank( rank - 1 );
643 
644 
645  if( !pushLineStack( shovedLine ) )
646  {
647  rv = SH_INCOMPLETE;
648  }
649  }
650 
651  return rv;
652 }
653 
654 
655 /*
656  * TODO describe....
657  */
659 {
660  WALKAROUND walkaround( m_currentNode, Router() );
661  LINE walkaroundLine( aCurrent );
662 
663  if( aCurrent.EndsWithVia() )
664  {
665  VIA vh = aCurrent.Via();
666  VIA* via = nullptr;
667  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
668 
669  if( !jtStart )
670  return SH_INCOMPLETE;
671 
672  for( ITEM* item : jtStart->LinkList() )
673  {
674  if( item->OfKind( ITEM::VIA_T ) )
675  {
676  via = (VIA*) item;
677  break;
678  }
679  }
680 
681  if( via && via->Collide( aObstacle, m_currentNode ) )
682  return onCollidingVia( aObstacle, via );
683  }
684 
685  TOPOLOGY topo( m_currentNode );
686 
687  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
688 
689  walkaround.SetSolidsOnly( false );
690  walkaround.RestrictToSet( true, cluster );
691  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
692 
693  int currentRank = aCurrent.Rank();
694  int nextRank;
695 
696  bool success = false;
697 
698  for( int attempt = 0; attempt < 2; attempt++ )
699  {
700  if( attempt == 1 || Settings().JumpOverObstacles() )
701  {
702 
703  nextRank = currentRank - 1;
704  walkaround.SetSingleDirection( true );
705  }
706  else
707  {
708  nextRank = currentRank + 10000;
709  walkaround.SetSingleDirection( false );
710  }
711 
712 
713  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
714 
715  if( status != WALKAROUND::DONE )
716  continue;
717 
718  walkaroundLine.ClearLinks();
719  walkaroundLine.Unmark();
720  walkaroundLine.Line().Simplify();
721 
722  if( walkaroundLine.HasLoops() )
723  continue;
724 
725  if( aCurrent.Marker() & MK_HEAD )
726  {
727  walkaroundLine.Mark( MK_HEAD );
728 
729  if( m_multiLineMode )
730  continue;
731 
732  m_newHead = walkaroundLine;
733  }
734 
735  sanityCheck( &aCurrent, &walkaroundLine );
736 
737  if( !m_lineStack.empty() )
738  {
739  LINE lastLine = m_lineStack.front();
740 
741  if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
742  {
743  LINE dummy( lastLine );
744 
745  if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
746  {
747  success = true;
748  break;
749  }
750  }
751  else
752  {
753  success = true;
754  break;
755  }
756  }
757  }
758 
759  if(!success)
760  return SH_INCOMPLETE;
761 
762  replaceLine( aCurrent, walkaroundLine );
763  walkaroundLine.SetRank( nextRank );
764 
765  if( Dbg() )
766  {
767  Dbg()->BeginGroup( "on-colliding-solid" );
768  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
769  Dbg()->AddLine( walkaroundLine.CLine(), BLUE, 10000, "walk-line" );
770  Dbg()->EndGroup();
771  }
772 
773  popLineStack();
774 
775  if( !pushLineStack( walkaroundLine ) )
776  return SH_INCOMPLETE;
777 
778  return SH_OK;
779 }
780 
781 
782 /*
783  * Pops NODE stackframes which no longer collide with aHeadSet. Optionally sets aDraggedVia
784  * to the dragged via of the last unpopped state.
785  */
786 NODE* SHOVE::reduceSpringback( const ITEM_SET& aHeadSet, VIA_HANDLE& aDraggedVia )
787 {
788  while( !m_nodeStack.empty() )
789  {
790  SPRINGBACK_TAG& spTag = m_nodeStack.back();
791 
792  // Prevent the springback algo from erasing NODEs that might contain items used by the ROUTER_TOOL/LINE_PLACER.
793  // I noticed this can happen for the endItem provided to LINE_PLACER::Move() and cause a nasty crash.
794  if( spTag.m_node == m_springbackDoNotTouchNode )
795  break;
796 
797  OPT<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
798 
799  if( !obs && !spTag.m_locked )
800  {
801  aDraggedVia = spTag.m_draggedVia;
802  aDraggedVia.valid = true;
803 
804  delete spTag.m_node;
805  m_nodeStack.pop_back();
806  }
807  else
808  {
809  break;
810  }
811  }
812 
813  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
814 }
815 
816 
817 /*
818  * Push the current NODE on to the stack. aDraggedVia is the dragged via *before* the push
819  * (which will be restored in the event the stackframe is popped).
820  */
821 bool SHOVE::pushSpringback( NODE* aNode, const OPT_BOX2I& aAffectedArea, VIA* aDraggedVia )
822 {
823  SPRINGBACK_TAG st;
824  OPT_BOX2I prev_area;
825 
826  if( !m_nodeStack.empty() )
827  prev_area = m_nodeStack.back().m_affectedArea;
828 
829  if( aDraggedVia )
830  {
831  st.m_draggedVia = aDraggedVia->MakeHandle();
832  }
833 
834  st.m_node = aNode;
835 
836  if( aAffectedArea )
837  {
838  if( prev_area )
839  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
840  else
841  st.m_affectedArea = aAffectedArea;
842  }
843  else
844  {
845  st.m_affectedArea = prev_area;
846  }
847 
848  st.m_seq = ( m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1 );
849  st.m_locked = false;
850 
851  m_nodeStack.push_back( st );
852 
853  return true;
854 }
855 
856 
857 /*
858  * Push or shove a via by at least aForce. (The via might be pushed or shoved slightly further
859  * to keep it from landing on an existing joint.)
860  */
861 SHOVE::SHOVE_STATUS SHOVE::pushOrShoveVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank )
862 {
863  LINE_PAIR_VEC draggedLines;
864  VECTOR2I p0( aVia->Pos() );
865  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
866  VECTOR2I p0_pushed( p0 + aForce );
867 
868  PNS_DBG( Dbg(), Message, wxString::Format( "via force [%d %d]\n", aForce.x, aForce.y ) );
869 
870  // nothing to do...
871  if ( aForce.x == 0 && aForce.y == 0 )
872  return SH_OK;
873 
874  if( !jt )
875  {
876  PNS_DBG( Dbg(), Message,
877  wxString::Format( "weird, can't find the center-of-via joint\n" ) );
878  return SH_INCOMPLETE;
879  }
880 
881  if( aVia->IsLocked() )
882  return SH_TRY_WALK;
883 
884  if( jt->IsLocked() )
885  return SH_INCOMPLETE;
886 
887  // make sure pushed via does not overlap with any existing joint
888  while( true )
889  {
890  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
891 
892  if( !jt_next )
893  break;
894 
895  p0_pushed += aForce.Resize( 2 );
896  }
897 
898  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
899  pushedVia->SetPos( p0_pushed );
900  pushedVia->Mark( aVia->Marker() );
901 
902  for( ITEM* item : jt->LinkList() )
903  {
904  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
905  {
906  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
907  LINE_PAIR lp;
908  int segIndex;
909 
910  lp.first = assembleLine( li, &segIndex );
911 
912  if( lp.first.HasLockedSegments() )
913  return SH_TRY_WALK;
914 
915  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
916 
917  if( segIndex == 0 )
918  lp.first.Reverse();
919 
920  lp.second = lp.first;
921  lp.second.ClearLinks();
922  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
923  lp.second.AppendVia( *pushedVia );
924  draggedLines.push_back( lp );
925  }
926  }
927 
928  pushedVia->SetRank( aCurrentRank - 1 );
929 
930  if( aVia->Marker() & MK_HEAD ) // push
931  {
932  m_draggedVia = pushedVia.get();
933  }
934  else
935  { // shove
936  if( jt->IsStitchingVia() )
937  pushLineStack( LINE( *pushedVia ) );
938  }
939 
940  PNS_DBG( Dbg(), AddPoint, aVia->Pos(), LIGHTGREEN, 100000, "via-pre" );
941  PNS_DBG( Dbg(), AddPoint, pushedVia->Pos(), LIGHTRED, 100000, "via-post" );
942 
943  replaceItems( aVia, std::move( pushedVia ) );
944 
945  for( LINE_PAIR lp : draggedLines )
946  {
947  if( lp.first.Marker() & MK_HEAD )
948  {
949  lp.second.Mark( MK_HEAD );
950 
951  if( m_multiLineMode )
952  return SH_INCOMPLETE;
953 
954  m_newHead = lp.second;
955  }
956 
957  unwindLineStack( &lp.first );
958 
959  if( lp.second.SegmentCount() )
960  {
961  replaceLine( lp.first, lp.second );
962  lp.second.SetRank( aCurrentRank - 1 );
963 
964  if( !pushLineStack( lp.second, true ) )
965  return SH_INCOMPLETE;
966  }
967  else
968  {
969  m_currentNode->Remove( lp.first );
970  }
971 
972  PNS_DBG( Dbg(), AddLine, lp.first.CLine(), LIGHTGREEN, 10000, "fan-pre" );
973  PNS_DBG( Dbg(), AddLine, lp.second.CLine(), LIGHTRED, 10000, "fan-post" );
974  }
975 
976  return SH_OK;
977 }
978 
979 
980 /*
981  * Calculate the minimum translation vector required to resolve a collision with a via and
982  * shove the via by that distance.
983  */
985 {
986  int clearance = getClearance( aCurrent, aObstacleVia );
987  VECTOR2I mtv;
988  int rank = -1;
989 
990  bool lineCollision = false;
991  bool viaCollision = false;
992  VECTOR2I mtvLine, mtvVia;
993 
994  PNS_DBG( Dbg(), BeginGroup, "push-via-by-line" );
995 
996  if( aCurrent->OfKind( ITEM::LINE_T ) )
997  {
998  LINE* currentLine = (LINE*) aCurrent;
999 
1000 #if 0
1001  m_logger.NewGroup( "push-via-by-line", m_iter );
1002  m_logger.Log( currentLine, 4, "current" );
1003 #endif
1004 
1005  lineCollision = aObstacleVia->Shape()->Collide( currentLine->Shape(),
1006  clearance + currentLine->Width() / 2,
1007  &mtvLine );
1008 
1009  // Check the via if present. Via takes priority.
1010  if( currentLine->EndsWithVia() )
1011  {
1012  const VIA& currentVia = currentLine->Via();
1013  int viaClearance = getClearance( &currentVia, aObstacleVia );
1014 
1015  viaCollision = aObstacleVia->Shape()->Collide( currentVia.Shape(), viaClearance,
1016  &mtvVia );
1017  }
1018  }
1019  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
1020  {
1021  // TODO: is this possible at all? We don't shove solids.
1022  return SH_INCOMPLETE;
1023  }
1024 
1025  // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
1026  if( viaCollision )
1027  mtv = mtvVia;
1028  else if ( lineCollision )
1029  mtv = -mtvLine;
1030  else
1031  mtv = VECTOR2I(0, 0);
1032 
1033  SHOVE::SHOVE_STATUS st = pushOrShoveVia( aObstacleVia, -mtv, rank );
1034 
1035  PNS_DBGN( Dbg(), EndGroup );
1036 
1037  return st;
1038 }
1039 
1040 
1041 /*
1042  * TODO describe....
1043  */
1045 {
1046  int n = 0;
1047  LINE cur( aCurrent );
1048  cur.ClearLinks();
1049 
1050  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
1051  LINE shoved( aCurrent );
1052  shoved.ClearLinks();
1053 
1054  cur.RemoveVia();
1055  unwindLineStack( &aCurrent );
1056 
1057  for( ITEM* item : jt->LinkList() )
1058  {
1059  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
1060  {
1061  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1062  LINE head = assembleLine( li );
1063 
1064  head.AppendVia( *aObstacleVia );
1065 
1066  SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
1067 
1068  if( st != SH_OK )
1069  {
1070 #if 0
1071  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
1072  m_logger.Log( aObstacleVia, 0, "the-via" );
1073  m_logger.Log( &aCurrent, 1, "current-line" );
1074  m_logger.Log( &shoved, 3, "shoved-line" );
1075 #endif
1076 
1077  return st;
1078  }
1079 
1080  cur.SetShape( shoved.CLine() );
1081  n++;
1082  }
1083  }
1084 
1085  if( !n )
1086  {
1087 #if 0
1088  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
1089  m_logger.Log( aObstacleVia, 0, "the-via" );
1090  m_logger.Log( &aCurrent, 1, "current-line" );
1091 #endif
1092 
1093  LINE head( aCurrent );
1094  head.Line().Clear();
1095  head.AppendVia( *aObstacleVia );
1096  head.ClearLinks();
1097 
1098  SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
1099 
1100  if( st != SH_OK )
1101  return st;
1102 
1103  cur.SetShape( shoved.CLine() );
1104  }
1105 
1106  if( aCurrent.EndsWithVia() )
1107  shoved.AppendVia( aCurrent.Via() );
1108 
1109 #if 0
1110  m_logger.NewGroup( "on-reverse-via", m_iter );
1111  m_logger.Log( aObstacleVia, 0, "the-via" );
1112  m_logger.Log( &aCurrent, 1, "current-line" );
1113  m_logger.Log( &shoved, 3, "shoved-line" );
1114 #endif
1115  int currentRank = aCurrent.Rank();
1116  replaceLine( aCurrent, shoved );
1117 
1118  if( !pushLineStack( shoved ) )
1119  return SH_INCOMPLETE;
1120 
1121  shoved.SetRank( currentRank );
1122 
1123  return SH_OK;
1124 }
1125 
1126 
1128 {
1129  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1130  {
1131  if( i->ContainsLink( aSeg ) )
1132  i = m_lineStack.erase( i );
1133  else
1134  i++;
1135  }
1136 
1137  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1138  {
1139  if( i->ContainsLink( aSeg ) )
1140  i = m_optimizerQueue.erase( i );
1141  else
1142  i++;
1143  }
1144 }
1145 
1146 
1148 {
1149  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1150  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1151  else if( aItem->OfKind( ITEM::LINE_T ) )
1152  {
1153  LINE* l = static_cast<LINE*>( aItem );
1154 
1155  for( LINKED_ITEM* seg : l->Links() )
1156  unwindLineStack( seg );
1157  }
1158 }
1159 
1160 
1161 bool SHOVE::pushLineStack( const LINE& aL, bool aKeepCurrentOnTop )
1162 {
1163  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1164  return false;
1165 
1166  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1167  {
1168  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1169  }
1170  else
1171  {
1172  m_lineStack.push_back( aL );
1173  }
1174 
1175  m_optimizerQueue.push_back( aL );
1176 
1177  return true;
1178 }
1179 
1180 
1182 {
1183  LINE& l = m_lineStack.back();
1184 
1185  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1186  {
1187  bool found = false;
1188 
1189  for( LINKED_ITEM* s : l.Links() )
1190  {
1191  if( i->ContainsLink( s ) )
1192  {
1193  i = m_optimizerQueue.erase( i );
1194  found = true;
1195  break;
1196  }
1197  }
1198 
1199  if( !found )
1200  i++;
1201  }
1202 
1203  m_lineStack.pop_back();
1204 }
1205 
1206 
1207 /*
1208  * Resolve the next collision.
1209  */
1211 {
1212  LINE currentLine = m_lineStack.back();
1213  NODE::OPT_OBSTACLE nearest;
1214  SHOVE_STATUS st = SH_NULL;
1215 
1216 #ifdef DEBUG
1217  Dbg()->SetIteration( aIter );
1218 #endif
1219 
1220  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1221  {
1222  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1223 
1224  if( nearest )
1225  PNS_DBG( Dbg(), Message,
1226  wxString::Format( "nearest %p %s", nearest->m_item,
1227  nearest->m_item->KindStr() ) );
1228 
1229  if( nearest )
1230  break;
1231  }
1232 
1233  if( !nearest )
1234  {
1235  m_lineStack.pop_back();
1236  PNS_DBG( Dbg(), Message, "no-nearest-item ");
1237  return SH_OK;
1238  }
1239 
1240  ITEM* ni = nearest->m_item;
1241 
1242  unwindLineStack( ni );
1243 
1244  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1245  {
1246  // Collision with a higher-ranking object (ie: one that we've already shoved)
1247  //
1248  switch( ni->Kind() )
1249  {
1250  case ITEM::VIA_T:
1251  {
1252  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-via", aIter ) );
1253 
1254  if( currentLine.EndsWithVia() )
1255  {
1256  st = SH_INCOMPLETE;
1257  }
1258  else
1259  {
1260  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1261  }
1262 
1263  break;
1264  }
1265 
1266  case ITEM::SEGMENT_T:
1267  {
1268  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-segment ",
1269  aIter ) );
1270  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1271 
1272  popLineStack();
1273  st = onCollidingLine( revLine, currentLine );
1274 
1275  if( !pushLineStack( revLine ) )
1276  return SH_INCOMPLETE;
1277 
1278  break;
1279  }
1280 
1281  case ITEM::ARC_T:
1282  {
1283  //TODO(snh): Handle Arc shove separate from track
1284  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-arc ", aIter ) );
1285  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1286 
1287  popLineStack();
1288  st = onCollidingLine( revLine, currentLine );
1289 
1290  if( !pushLineStack( revLine ) )
1291  return SH_INCOMPLETE;
1292 
1293  break;
1294  }
1295 
1296  default:
1297  assert( false );
1298  }
1299  }
1300  else
1301  {
1302  // Collision with a lower-ranking object or a solid
1303  //
1304  switch( ni->Kind() )
1305  {
1306  case ITEM::SEGMENT_T:
1307  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: collide-segment ", aIter ) );
1308 
1309  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1310 
1311  if( st == SH_TRY_WALK )
1312  st = onCollidingSolid( currentLine, ni );
1313 
1314  break;
1315 
1316  //TODO(snh): Customize Arc collide
1317  case ITEM::ARC_T:
1318  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: collide-arc ", aIter ) );
1319 
1320  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1321 
1322  if( st == SH_TRY_WALK )
1323  st = onCollidingSolid( currentLine, ni );
1324 
1325  break;
1326 
1327  case ITEM::VIA_T:
1328  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: shove-via ", aIter ) );
1329  st = onCollidingVia( &currentLine, (VIA*) ni );
1330 
1331  if( st == SH_TRY_WALK )
1332  st = onCollidingSolid( currentLine, ni );
1333 
1334  break;
1335 
1336  case ITEM::SOLID_T:
1337  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: walk-solid ", aIter ) );
1338  st = onCollidingSolid( currentLine, (SOLID*) ni );
1339  break;
1340 
1341  default:
1342  break;
1343  }
1344  }
1345 
1346  return st;
1347 }
1348 
1349 
1350 /*
1351  * Resolve collisions.
1352  * Each iteration pushes the next colliding object out of the way. Iterations are continued as
1353  * long as they propagate further collisions, or until the iteration timeout or max iteration
1354  * count is reached.
1355  */
1357 {
1358  SHOVE_STATUS st = SH_OK;
1359 
1361 
1362  PNS_DBG( Dbg(), Message, wxString::Format( "ShoveStart [root: %d jts, current: %d jts]",
1363  m_root->JointCount(),
1364  m_currentNode->JointCount() ) );
1365 
1366  int iterLimit = Settings().ShoveIterationLimit();
1367  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1368 
1369  m_iter = 0;
1370 
1371  timeLimit.Restart();
1372 
1373  if( m_lineStack.empty() && m_draggedVia )
1374  {
1375  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1376  // the stack.
1378  }
1379 
1380  while( !m_lineStack.empty() )
1381  {
1382  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: node %p stack %d ", m_iter,
1383  m_currentNode, (int) m_lineStack.size() ) );
1384 
1385  st = shoveIteration( m_iter );
1386 
1387  m_iter++;
1388 
1389  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1390  {
1391  st = SH_INCOMPLETE;
1392  break;
1393  }
1394  }
1395 
1396  return st;
1397 }
1398 
1399 
1401 {
1402  OPT_BOX2I area;
1403 
1404  if( !m_nodeStack.empty() )
1405  area = m_nodeStack.back().m_affectedArea;
1406 
1407  if( area && m_affectedArea)
1408  area->Merge( *m_affectedArea );
1409  else if( !area )
1410  area = m_affectedArea;
1411 
1412  return area;
1413 }
1414 
1415 
1417 {
1418  SHOVE_STATUS st = SH_OK;
1419 
1420  m_multiLineMode = false;
1421 
1422  PNS_DBG( Dbg(), Message,
1423  wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) )
1424 
1425  // empty head? nothing to shove...
1426  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1427  return SH_INCOMPLETE;
1428 
1429  LINE head( aCurrentHead );
1430  head.ClearLinks();
1431 
1432  m_lineStack.clear();
1433  m_optimizerQueue.clear();
1434  m_newHead = OPT_LINE();
1435 
1436 #if 0
1437  m_logger.Clear();
1438 #endif
1439 
1440  // Pop NODEs containing previous shoves which are no longer necessary
1441  //
1442  ITEM_SET headSet;
1443  headSet.Add( aCurrentHead );
1444 
1445  VIA_HANDLE dummyVia;
1446 
1447  NODE* parent = reduceSpringback( headSet, dummyVia );
1448 
1449  // Create a new NODE to store this version of the world
1450  m_currentNode = parent->Branch();
1452  m_currentNode->Add( head );
1453 
1454  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1455 
1456  if( !head.EndsWithVia() )
1457  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1458 
1459  head.Mark( MK_HEAD );
1460  head.SetRank( 100000 );
1461 
1462  PNS_DBG( Dbg(), AddLine, head.CLine(), CYAN, head.Width(), "head, after shove" );
1463 
1464  if( head.EndsWithVia() )
1465  {
1466  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1467  headVia->Mark( MK_HEAD );
1468  headVia->SetRank( 100000 );
1469  m_currentNode->Add( std::move( headVia ) );
1470  }
1471 
1472  if( !pushLineStack( head ) )
1473  {
1474  delete m_currentNode;
1475  m_currentNode = parent;
1476 
1477  return SH_INCOMPLETE;
1478  }
1479 
1480  st = shoveMainLoop();
1481 
1482  if( st == SH_OK )
1483  {
1485 
1486  if( m_newHead )
1488  else
1489  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1490  }
1491 
1493 
1494  PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1495  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter ) );
1496 
1497  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1498  {
1500  }
1501  else
1502  {
1503  delete m_currentNode;
1504 
1505  m_currentNode = parent;
1506  m_newHead = OPT_LINE();
1507  }
1508 
1509  if(m_newHead)
1510  m_newHead->Unmark();
1511 
1512  if( m_newHead && head.EndsWithVia() )
1513  {
1514  VIA v = head.Via();
1515  v.SetPos( m_newHead->CPoint( -1 ) );
1516  m_newHead->AppendVia(v);
1517  }
1518 
1519  return st;
1520 }
1521 
1522 
1524 {
1525  SHOVE_STATUS st = SH_OK;
1526 
1527  m_multiLineMode = true;
1528 
1529  ITEM_SET headSet;
1530 
1531  for( const ITEM* item : aHeadSet.CItems() )
1532  {
1533  const LINE* headOrig = static_cast<const LINE*>( item );
1534 
1535  // empty head? nothing to shove...
1536  if( !headOrig->SegmentCount() )
1537  return SH_INCOMPLETE;
1538 
1539  headSet.Add( *headOrig );
1540  }
1541 
1542  m_lineStack.clear();
1543  m_optimizerQueue.clear();
1544 
1545 #if 0
1546  m_logger.Clear();
1547 #endif
1548 
1549  VIA_HANDLE dummyVia;
1550 
1551  NODE* parent = reduceSpringback( headSet, dummyVia );
1552 
1553  m_currentNode = parent->Branch();
1555  int n = 0;
1556 
1557  for( const ITEM* item : aHeadSet.CItems() )
1558  {
1559  const LINE* headOrig = static_cast<const LINE*>( item );
1560  LINE head( *headOrig );
1561  head.ClearLinks();
1562 
1563  m_currentNode->Add( head );
1564 
1565  head.Mark( MK_HEAD );
1566  head.SetRank( 100000 );
1567  n++;
1568 
1569  if( !pushLineStack( head ) )
1570  return SH_INCOMPLETE;
1571 
1572  if( head.EndsWithVia() )
1573  {
1574  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1575  headVia->Mark( MK_HEAD );
1576  headVia->SetRank( 100000 );
1577  m_currentNode->Add( std::move( headVia ) );
1578  }
1579  }
1580 
1581  st = shoveMainLoop();
1582 
1583  if( st == SH_OK )
1585 
1587 
1588  PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1589  ( st == SH_OK ? "OK" : "FAILURE"), m_iter ) );
1590 
1591  if( st == SH_OK )
1592  {
1594  }
1595  else
1596  {
1597  delete m_currentNode;
1598  m_currentNode = parent;
1599  }
1600 
1601  return st;
1602 }
1603 
1604 
1605 static VIA* findViaByHandle ( NODE *aNode, const VIA_HANDLE& handle )
1606 {
1607  JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1608 
1609  if( !jt )
1610  return nullptr;
1611 
1612  for( ITEM* item : jt->LinkList() )
1613  {
1614  if( item->OfKind( ITEM::VIA_T ) )
1615  {
1616  if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1617  return static_cast<VIA*>( item );
1618  }
1619  }
1620 
1621  return nullptr;
1622 }
1623 
1624 
1626  VIA_HANDLE& aNewVia )
1627 {
1628  SHOVE_STATUS st = SH_OK;
1629 
1630  m_lineStack.clear();
1631  m_optimizerQueue.clear();
1632  m_newHead = OPT_LINE();
1633  m_draggedVia = nullptr;
1634 
1635  VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1636 
1637  if( !viaToDrag )
1638  return SH_INCOMPLETE;
1639 
1640  // Pop NODEs containing previous shoves which are no longer necessary
1641  ITEM_SET headSet;
1642 
1643  VIA headVia ( *viaToDrag );
1644  headVia.SetPos( aWhere );
1645  headSet.Add( headVia );
1646  VIA_HANDLE prevViaHandle;
1647  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1648 
1649  if( prevViaHandle.valid )
1650  {
1651  aNewVia = prevViaHandle;
1652  viaToDrag = findViaByHandle( parent, prevViaHandle );
1653  }
1654 
1655  // Create a new NODE to store this version of the world
1656  m_currentNode = parent->Branch();
1658 
1659  viaToDrag->Mark( MK_HEAD );
1660  viaToDrag->SetRank( 100000 );
1661 
1662  // Push the via to its new location
1663  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1664 
1665  // Shove any colliding objects out of the way
1666  if( st == SH_OK )
1667  st = shoveMainLoop();
1668 
1669  if( st == SH_OK )
1671 
1672  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1673  {
1674  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1675 
1676  if (!m_draggedVia)
1677  m_draggedVia = viaToDrag;
1678 
1679  aNewVia = m_draggedVia->MakeHandle();
1680 
1682  }
1683  else
1684  {
1685  delete m_currentNode;
1686  m_currentNode = parent;
1687  }
1688 
1689  return st;
1690 }
1691 
1692 
1694 {
1695  for( auto link : aLine->Links() )
1696  {
1697  if( auto seg = dyn_cast<SEGMENT*>( link ) )
1698  {
1699  auto it = m_rootLineHistory.find( seg );
1700 
1701  if( it != m_rootLineHistory.end() )
1702  return it->second;
1703  }
1704  }
1705 
1706  return nullptr;
1707 }
1708 
1709 
1711 {
1712  OPTIMIZER optimizer( aNode );
1713  int optFlags = 0;
1714  int n_passes = 0;
1715 
1717 
1718  OPT_BOX2I area = totalAffectedArea();
1719 
1720  int maxWidth = 0;
1721 
1722  for( LINE& line : m_optimizerQueue )
1723  maxWidth = std::max( line.Width(), maxWidth );
1724 
1725  if( area )
1726  {
1727  area->Inflate( maxWidth );
1728  area = area->Intersect( VisibleViewArea() );
1729  }
1730 
1731  switch( effort )
1732  {
1733  case OE_LOW:
1734  optFlags |= OPTIMIZER::MERGE_OBTUSE;
1735  n_passes = 1;
1736  break;
1737 
1738  case OE_MEDIUM:
1739  optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1740 
1741  n_passes = 2;
1742  break;
1743 
1744  case OE_FULL:
1745  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1746  n_passes = 2;
1747  break;
1748 
1749  default:
1750  break;
1751  }
1752 
1753  optFlags |= OPTIMIZER::LIMIT_CORNER_COUNT;
1754 
1755  if( area )
1756  {
1757  if( Dbg() )
1758  {
1759  Dbg()->AddBox( *area, BLUE, "opt-area" );
1760  }
1761 
1762  optFlags |= OPTIMIZER::RESTRICT_AREA;
1763  optimizer.SetRestrictArea( *area, false );
1764  }
1765 
1766  if( Settings().SmartPads() )
1767  optFlags |= OPTIMIZER::SMART_PADS;
1768 
1769 
1770  optimizer.SetEffortLevel( optFlags & ~m_optFlagDisableMask );
1771  optimizer.SetCollisionMask( ITEM::ANY_T );
1772 
1773  for( int pass = 0; pass < n_passes; pass++ )
1774  {
1775  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1776 
1777  for( LINE& line : m_optimizerQueue)
1778  {
1779  if( !( line.Marker() & MK_HEAD ) )
1780  {
1781  LINE optimized;
1782  LINE* root = findRootLine( &line );
1783 
1784  if( optimizer.Optimize( &line, &optimized, root ) )
1785  {
1786  replaceLine( line, optimized, false, aNode );
1787  line = optimized; // keep links in the lines in the queue up to date
1788  }
1789  }
1790  }
1791  }
1792 }
1793 
1794 
1796 {
1797  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1798 }
1799 
1800 
1801 const LINE SHOVE::NewHead() const
1802 {
1803  assert( m_newHead );
1804 
1805  return *m_newHead;
1806 }
1807 
1808 
1809 void SHOVE::SetInitialLine( LINE& aInitial )
1810 {
1811  m_root = m_root->Branch();
1812  m_root->Remove( aInitial );
1813 }
1814 
1815 
1817 {
1818  SPRINGBACK_TAG sp;
1819  sp.m_node = aNode;
1820  sp.m_locked = true;
1821 
1822  m_nodeStack.push_back(sp);
1823  return true;
1824 }
1825 
1826 
1828 {
1829  bool found = false;
1830 
1831  auto iter = m_nodeStack.begin();
1832 
1833  while( iter != m_nodeStack.end() )
1834  {
1835  if ( iter->m_node == aNode )
1836  {
1837  found = true;
1838  break;
1839  }
1840 
1841  iter++;
1842  }
1843 
1844  if( !found )
1845  return false;
1846 
1847  auto start = iter;
1848 
1849  aNode->KillChildren();
1850  m_nodeStack.erase( start, m_nodeStack.end() );
1851 
1852  return true;
1853 }
1854 
1855 
1857 {
1858  if( m_nodeStack.empty() )
1859  return false;
1860 
1861  while( !m_nodeStack.back().m_locked && m_nodeStack.size() > 1 )
1862  m_nodeStack.pop_back();
1863 
1864  return m_nodeStack.back().m_locked;
1865 }
1866 
1867 
1869 {
1870  auto iter = m_nodeStack.begin();
1871 
1872  while( iter != m_nodeStack.end() )
1873  {
1874  if ( iter->m_node == aNode )
1875  {
1876  iter->m_locked = false;
1877  break;
1878  }
1879 
1880  iter++;
1881  }
1882 }
1883 
1884 
1886 {
1887  m_optFlagDisableMask = aMask;
1888 }
1889 
1890 
1892 {
1894 }
1895 
1896 }
1897 
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1441
LINE * findRootLine(LINE *aLine)
Definition: pns_shove.cpp:1693
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1161
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:123
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:1181
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:146
VECTOR2I::extended_type ecoord
Definition: pns_shove.cpp:47
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:658
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1127
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 SegmentCount() const
Definition: pns_line.h:139
const LINE NewHead() const
Definition: pns_shove.cpp:1801
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:554
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:1827
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:185
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:395
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:220
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:249
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 GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:114
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:861
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:1891
bool EndsWithVia() const
Definition: pns_line.h:191
void DisablePostShoveOptimizations(int aMask)
Definition: pns_shove.cpp:1885
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:837
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:99
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:617
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:1044
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:1400
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:786
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:1416
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
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:102
void KillChildren()
Definition: pns_node.cpp:1406
bool IsArcSegment(size_t aSegment) const
bool AddLockedSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:1816
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:984
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1710
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:1210
int Net() const
Definition: pns_item.h:152
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1605
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:821
virtual void SetRank(int aRank)
Definition: pns_item.h:214
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:484
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:218
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:1868
void Clear()
Definition: pns_logger.cpp:40
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr)
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
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:1141
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:1625
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:802
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1451
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:451
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:1856
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:1356
bool IsLocked() const
Definition: pns_item.h:227
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509
void SetInitialLine(LINE &aInitial)
Definition: pns_shove.cpp:1809
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:149
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:947
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:143
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:1523
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:639
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:1795
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:1171
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