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