KiCad PCB EDA Suite
PNS::SHOVE Class Reference

SHOVE. More...

#include <pns_shove.h>

Inheritance diagram for PNS::SHOVE:
PNS::ALGO_BASE

Classes

struct  SPRINGBACK_TAG
 

Public Types

enum  SHOVE_STATUS {
  SH_OK = 0, SH_NULL, SH_INCOMPLETE, SH_HEAD_MODIFIED,
  SH_TRY_WALK
}
 

Public Member Functions

 SHOVE (NODE *aWorld, ROUTER *aRouter)
 
 ~SHOVE ()
 
virtual LOGGERLogger () override
 

Returns the logger object, allowing to dump geometry to a file.

More...
 
SHOVE_STATUS ShoveLines (const LINE &aCurrentHead)
 
SHOVE_STATUS ShoveMultiLines (const ITEM_SET &aHeadSet)
 
SHOVE_STATUS ShoveDraggingVia (const VIA_HANDLE aOldVia, const VECTOR2I &aWhere, VIA_HANDLE &aNewVia)
 
SHOVE_STATUS ProcessSingleLine (LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
 
void ForceClearance (bool aEnabled, int aClearance)
 
NODECurrentNode ()
 
const LINE NewHead () const
 
void SetInitialLine (LINE &aInitial)
 
bool AddLockedSpringbackNode (NODE *aNode)
 
void UnlockSpringbackNode (NODE *aNode)
 
bool RewindSpringbackTo (NODE *aNode)
 
ROUTERRouter () const
 

Returns the instance of our router

More...
 
ROUTING_SETTINGSSettings () const
 

Returns current router settings

More...
 
void SetLogger (LOGGER *aLogger)
 
void SetDebugDecorator (DEBUG_DECORATOR *aDecorator)
 Function SetDebugDecorator. More...
 
DEBUG_DECORATORDbg () const
 

Protected Attributes

DEBUG_DECORATORm_debugDecorator
 
ROUTERm_router
 

Private Types

typedef std::vector< SHAPE_LINE_CHAINHULL_SET
 
typedef OPT< LINEOPT_LINE
 
typedef std::pair< LINE, LINELINE_PAIR
 
typedef std::vector< LINE_PAIRLINE_PAIR_VEC
 

Private Member Functions

SHOVE_STATUS processHullSet (LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
 
NODEreduceSpringback (const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
 
bool pushSpringback (NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
 
SHOVE_STATUS walkaroundLoneVia (LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
 
bool checkBumpDirection (const LINE &aCurrent, const LINE &aObstacle, const LINE &aShoved) const
 
SHOVE_STATUS onCollidingArc (LINE &aCurrent, ARC *aObstacleArc)
 
SHOVE_STATUS onCollidingLine (LINE &aCurrent, LINE &aObstacle)
 
SHOVE_STATUS onCollidingSegment (LINE &aCurrent, SEGMENT *aObstacleSeg)
 
SHOVE_STATUS onCollidingSolid (LINE &aCurrent, ITEM *aObstacle)
 
SHOVE_STATUS onCollidingVia (ITEM *aCurrent, VIA *aObstacleVia)
 
SHOVE_STATUS onReverseCollidingVia (LINE &aCurrent, VIA *aObstacleVia)
 
SHOVE_STATUS pushOrShoveVia (VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
 
OPT_BOX2I totalAffectedArea () const
 
void unwindLineStack (LINKED_ITEM *aSeg)
 
void unwindLineStack (ITEM *aItem)
 
void runOptimizer (NODE *aNode)
 
bool pushLineStack (const LINE &aL, bool aKeepCurrentOnTop=false)
 
void popLineStack ()
 
LINE assembleLine (const LINKED_ITEM *aSeg, int *aIndex=NULL)
 
void replaceItems (ITEM *aOld, std::unique_ptr< ITEM > aNew)
 
void replaceLine (LINE &aOld, LINE &aNew)
 
SHOVE_STATUS shoveIteration (int aIter)
 
SHOVE_STATUS shoveMainLoop ()
 
int getClearance (const ITEM *aA, const ITEM *aB) const
 
void sanityCheck (LINE *aOld, LINE *aNew)
 

Private Attributes

OPT_BOX2I m_affectedArea
 
std::vector< SPRINGBACK_TAGm_nodeStack
 
std::vector< LINEm_lineStack
 
std::vector< LINEm_optimizerQueue
 
NODEm_root
 
NODEm_currentNode
 
int m_restrictSpringbackTagId
 
OPT_LINE m_newHead
 
LOGGER m_logger
 
VIAm_draggedVia
 
int m_iter
 
int m_forceClearance
 
bool m_multiLineMode
 

Detailed Description

SHOVE.

The actual Push and Shove algorithm.

Definition at line 48 of file pns_shove.h.

Member Typedef Documentation

◆ HULL_SET

typedef std::vector<SHAPE_LINE_CHAIN> PNS::SHOVE::HULL_SET
private

Definition at line 94 of file pns_shove.h.

◆ LINE_PAIR

typedef std::pair<LINE, LINE> PNS::SHOVE::LINE_PAIR
private

Definition at line 96 of file pns_shove.h.

◆ LINE_PAIR_VEC

typedef std::vector<LINE_PAIR> PNS::SHOVE::LINE_PAIR_VEC
private

Definition at line 97 of file pns_shove.h.

◆ OPT_LINE

typedef OPT<LINE> PNS::SHOVE::OPT_LINE
private

Definition at line 95 of file pns_shove.h.

Member Enumeration Documentation

◆ SHOVE_STATUS

Enumerator
SH_OK 
SH_NULL 
SH_INCOMPLETE 
SH_HEAD_MODIFIED 
SH_TRY_WALK 

Definition at line 52 of file pns_shove.h.

Constructor & Destructor Documentation

◆ SHOVE()

PNS::SHOVE::SHOVE ( NODE aWorld,
ROUTER aRouter 
)

Definition at line 82 of file pns_shove.cpp.

82  :
83  ALGO_BASE( aRouter )
84 {
85  m_forceClearance = -1;
86  m_root = aWorld;
87  m_currentNode = aWorld;
88  SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );
89 
90  // Initialize other temporary variables:
92  m_iter = 0;
93  m_multiLineMode = false;
95 }
int m_restrictSpringbackTagId
Definition: pns_shove.h:163
NODE * m_root
Definition: pns_shove.h:161
#define NULL
ALGO_BASE(ROUTER *aRouter)
Definition: pns_algo_base.h:42
VIA * m_draggedVia
Definition: pns_shove.h:168
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Function SetDebugDecorator.
Definition: pns_algo_base.h:72
bool m_multiLineMode
Definition: pns_shove.h:172
NODE * m_currentNode
Definition: pns_shove.h:162
int m_iter
Definition: pns_shove.h:170
int m_forceClearance
Definition: pns_shove.h:171

References PNS::ROUTER_IFACE::GetDebugDecorator(), PNS::ROUTER::GetInterface(), m_currentNode, m_draggedVia, m_forceClearance, m_iter, m_multiLineMode, m_restrictSpringbackTagId, m_root, NULL, and PNS::ALGO_BASE::SetDebugDecorator().

◆ ~SHOVE()

PNS::SHOVE::~SHOVE ( )

Definition at line 98 of file pns_shove.cpp.

99 {
100 }

Member Function Documentation

◆ AddLockedSpringbackNode()

bool PNS::SHOVE::AddLockedSpringbackNode ( NODE aNode)

Definition at line 1615 of file pns_shove.cpp.

1616 {
1617  SPRINGBACK_TAG sp;
1618  sp.m_node = aNode;
1619  sp.m_locked = true;
1620 
1621  m_nodeStack.push_back(sp);
1622  return true;
1623 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

References PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, and m_nodeStack.

◆ assembleLine()

LINE PNS::SHOVE::assembleLine ( const LINKED_ITEM aSeg,
int *  aIndex = NULL 
)
private

Definition at line 103 of file pns_shove.cpp.

104 {
105  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
106 }
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
NODE * m_currentNode
Definition: pns_shove.h:162

References PNS::NODE::AssembleLine(), and m_currentNode.

Referenced by onCollidingArc(), onCollidingSegment(), onReverseCollidingVia(), pushOrShoveVia(), and shoveIteration().

◆ checkBumpDirection()

bool PNS::SHOVE::checkBumpDirection ( const LINE aCurrent,
const LINE aObstacle,
const LINE aShoved 
) const
private

Definition at line 116 of file pns_shove.cpp.

117 {
118  SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurrent.CPoint(0) );
119  checker.AddPolyline( aObstacle.CLine() );
120  checker.AddPolyline( aShoved.CLine().Reverse() );
121 
122  bool inside = checker.IsInside();
123 
124  return !inside;
125 }
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)

References SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::AddPolyline(), PNS::LINE::CLine(), PNS::LINE::CPoint(), and SHAPE_LINE_CHAIN::Reverse().

Referenced by processHullSet().

◆ CurrentNode()

NODE * PNS::SHOVE::CurrentNode ( )

Definition at line 1594 of file pns_shove.cpp.

1595 {
1596  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1597 }
NODE * m_root
Definition: pns_shove.h:161
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

References m_nodeStack, and m_root.

Referenced by PNS::DIFF_PAIR_PLACER::rhShoveOnly().

◆ Dbg()

◆ ForceClearance()

void PNS::SHOVE::ForceClearance ( bool  aEnabled,
int  aClearance 
)
inline

Definition at line 75 of file pns_shove.h.

76  {
77  if( aEnabled )
78  m_forceClearance = aClearance;
79  else
80  m_forceClearance = -1;
81  }
int m_forceClearance
Definition: pns_shove.h:171

References m_forceClearance.

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk().

◆ getClearance()

int PNS::SHOVE::getClearance ( const ITEM aA,
const ITEM aB 
) const
private

Definition at line 66 of file pns_shove.cpp.

67 {
68  if( m_forceClearance >= 0 )
69  return m_forceClearance;
70 
71  return m_currentNode->GetClearance( aA, aB );
72 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
NODE * m_currentNode
Definition: pns_shove.h:162
int m_forceClearance
Definition: pns_shove.h:171

References PNS::NODE::GetClearance(), m_currentNode, and m_forceClearance.

Referenced by onCollidingVia(), ProcessSingleLine(), and walkaroundLoneVia().

◆ Logger()

virtual LOGGER* PNS::SHOVE::Logger ( )
inlineoverridevirtual

Returns the logger object, allowing to dump geometry to a file.

Reimplemented from PNS::ALGO_BASE.

Definition at line 64 of file pns_shove.h.

65  {
66  return &m_logger;
67  }
LOGGER m_logger
Definition: pns_shove.h:167

References m_logger.

◆ NewHead()

const LINE PNS::SHOVE::NewHead ( ) const

Definition at line 1600 of file pns_shove.cpp.

1601 {
1602  assert( m_newHead );
1603 
1604  return *m_newHead;
1605 }
OPT_LINE m_newHead
Definition: pns_shove.h:165

References m_newHead.

◆ onCollidingArc()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingArc ( LINE aCurrent,
ARC aObstacleArc 
)
private

Definition at line 386 of file pns_shove.cpp.

387 {
388  int segIndex;
389  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
390  LINE shovedLine( obstacleLine );
391  ARC tmp( *aObstacleArc );
392 
393  if( obstacleLine.HasLockedSegments() )
394  return SH_TRY_WALK;
395 
396  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
397 
398  const double extensionWalkThreshold = 1.0;
399 
400  double obsLen = obstacleLine.CLine().Length();
401  double shovedLen = shovedLine.CLine().Length();
402  double extensionFactor = 0.0;
403 
404  if( obsLen != 0.0f )
405  extensionFactor = shovedLen / obsLen - 1.0;
406 
407  if( extensionFactor > extensionWalkThreshold )
408  return SH_TRY_WALK;
409 
410  assert( obstacleLine.LayersOverlap( &shovedLine ) );
411 
412 #ifdef DEBUG
413  m_logger.NewGroup( "on-colliding-segment", m_iter );
414  m_logger.Log( &tmp, 0, "obstacle-segment" );
415  m_logger.Log( &aCurrent, 1, "current-line" );
416  m_logger.Log( &obstacleLine, 2, "obstacle-line" );
417  m_logger.Log( &shovedLine, 3, "shoved-line" );
418 #endif
419 
420  if( rv == SH_OK )
421  {
422  if( shovedLine.Marker() & MK_HEAD )
423  {
424  if( m_multiLineMode )
425  return SH_INCOMPLETE;
426 
427  m_newHead = shovedLine;
428  }
429 
430  int rank = aCurrent.Rank();
431  shovedLine.SetRank( rank - 1 );
432 
433  sanityCheck( &obstacleLine, &shovedLine );
434  replaceLine( obstacleLine, shovedLine );
435 
436  if( !pushLineStack( shovedLine ) )
437  rv = SH_INCOMPLETE;
438  }
439 
440  return rv;
441 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:103
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:267
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:75
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References assembleLine(), PNS::LINE::CLine(), PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and SH_TRY_WALK.

Referenced by shoveIteration().

◆ onCollidingLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingLine ( LINE aCurrent,
LINE aObstacle 
)
private

Definition at line 447 of file pns_shove.cpp.

448 {
449  LINE shovedLine( aObstacle );
450 
451  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, aObstacle, shovedLine );
452 
453  #ifdef DEBUG
454  m_logger.NewGroup( "on-colliding-line", m_iter );
455  m_logger.Log( &aObstacle, 0, "obstacle-line" );
456  m_logger.Log( &aCurrent, 1, "current-line" );
457  m_logger.Log( &shovedLine, 3, "shoved-line" );
458  #endif
459 
460  if( rv == SH_OK )
461  {
462  if( shovedLine.Marker() & MK_HEAD )
463  {
464  if( m_multiLineMode )
465  return SH_INCOMPLETE;
466 
467  m_newHead = shovedLine;
468  }
469 
470  sanityCheck( &aObstacle, &shovedLine );
471  replaceLine( aObstacle, shovedLine );
472 
473  int rank = aObstacle.Rank();
474  shovedLine.SetRank( rank - 1 );
475 
476 
477  if( !pushLineStack( shovedLine ) )
478  {
479  rv = SH_INCOMPLETE;
480  }
481  }
482 
483  return rv;
484 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:267
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:75
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, and SH_OK.

Referenced by shoveIteration().

◆ onCollidingSegment()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingSegment ( LINE aCurrent,
SEGMENT aObstacleSeg 
)
private

Definition at line 325 of file pns_shove.cpp.

326 {
327  int segIndex;
328  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
329  LINE shovedLine( obstacleLine );
330  SEGMENT tmp( *aObstacleSeg );
331 
332  if( obstacleLine.HasLockedSegments() )
333  return SH_TRY_WALK;
334 
335  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
336 
337  const double extensionWalkThreshold = 1.0;
338 
339  double obsLen = obstacleLine.CLine().Length();
340  double shovedLen = shovedLine.CLine().Length();
341  double extensionFactor = 0.0;
342 
343  if( obsLen != 0.0f )
344  extensionFactor = shovedLen / obsLen - 1.0;
345 
346  if( extensionFactor > extensionWalkThreshold )
347  return SH_TRY_WALK;
348 
349  assert( obstacleLine.LayersOverlap( &shovedLine ) );
350 
351 #ifdef DEBUG
352  m_logger.NewGroup( "on-colliding-segment", m_iter );
353  m_logger.Log( &tmp, 0, "obstacle-segment" );
354  m_logger.Log( &aCurrent, 1, "current-line" );
355  m_logger.Log( &obstacleLine, 2, "obstacle-line" );
356  m_logger.Log( &shovedLine, 3, "shoved-line" );
357 #endif
358 
359  if( rv == SH_OK )
360  {
361  if( shovedLine.Marker() & MK_HEAD )
362  {
363  if( m_multiLineMode )
364  return SH_INCOMPLETE;
365 
366  m_newHead = shovedLine;
367  }
368 
369  int rank = aCurrent.Rank();
370  shovedLine.SetRank( rank - 1 );
371 
372  sanityCheck( &obstacleLine, &shovedLine );
373  replaceLine( obstacleLine, shovedLine );
374 
375  if( !pushLineStack( shovedLine ) )
376  rv = SH_INCOMPLETE;
377  }
378 
379  return rv;
380 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:103
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:267
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:75
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References assembleLine(), PNS::LINE::CLine(), PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and SH_TRY_WALK.

Referenced by shoveIteration().

◆ onCollidingSolid()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingSolid ( LINE aCurrent,
ITEM aObstacle 
)
private

Definition at line 490 of file pns_shove.cpp.

491 {
492  WALKAROUND walkaround( m_currentNode, Router() );
493  LINE walkaroundLine( aCurrent );
494 
495  if( aCurrent.EndsWithVia() )
496  {
497  VIA vh = aCurrent.Via();
498  VIA* via = NULL;
499  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
500 
501  if( !jtStart )
502  return SH_INCOMPLETE;
503 
504  for( ITEM* item : jtStart->LinkList() )
505  {
506  if( item->OfKind( ITEM::VIA_T ) )
507  {
508  via = (VIA*) item;
509  break;
510  }
511  }
512 
513  if( via && m_currentNode->CheckColliding( via, aObstacle ) )
514  return onCollidingVia( aObstacle, via );
515  }
516 
517  TOPOLOGY topo( m_currentNode );
518 
519  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
520 
521 #ifdef DEBUG
522  m_logger.NewGroup( "on-colliding-solid-cluster", m_iter );
523  for( ITEM* item : cluster )
524  {
525  m_logger.Log( item, 0, "cluster-entry" );
526  }
527 #endif
528 
529  walkaround.SetSolidsOnly( false );
530  walkaround.RestrictToSet( true, cluster );
531  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
532 
533  int currentRank = aCurrent.Rank();
534  int nextRank;
535 
536  bool success = false;
537 
538  for( int attempt = 0; attempt < 2; attempt++ )
539  {
540  if( attempt == 1 || Settings().JumpOverObstacles() )
541  {
542 
543  nextRank = currentRank - 1;
544  walkaround.SetSingleDirection( true );
545  }
546  else
547  {
548  nextRank = currentRank + 10000;
549  walkaround.SetSingleDirection( false );
550  }
551 
552 
553  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
554 
555  if( status != WALKAROUND::DONE )
556  continue;
557 
558  walkaroundLine.ClearSegmentLinks();
559  walkaroundLine.Unmark();
560  walkaroundLine.Line().Simplify();
561 
562  if( walkaroundLine.HasLoops() )
563  continue;
564 
565  if( aCurrent.Marker() & MK_HEAD )
566  {
567  walkaroundLine.Mark( MK_HEAD );
568 
569  if( m_multiLineMode )
570  continue;
571 
572  m_newHead = walkaroundLine;
573  }
574 
575  sanityCheck( &aCurrent, &walkaroundLine );
576 
577  if( !m_lineStack.empty() )
578  {
579  LINE lastLine = m_lineStack.front();
580 
581  if( m_currentNode->CheckColliding( &lastLine, &walkaroundLine ) )
582  {
583  LINE dummy( lastLine );
584 
585  if( ProcessSingleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
586  {
587  success = true;
588  break;
589  }
590  } else {
591  success = true;
592  break;
593  }
594  }
595  }
596 
597  if(!success)
598  return SH_INCOMPLETE;
599 
600  replaceLine( aCurrent, walkaroundLine );
601  walkaroundLine.SetRank( nextRank );
602 
603 #ifdef DEBUG
604  m_logger.NewGroup( "on-colliding-solid", m_iter );
605  m_logger.Log( aObstacle, 0, "obstacle-solid" );
606  m_logger.Log( &aCurrent, 1, "current-line" );
607  m_logger.Log( &walkaroundLine, 3, "walk-line" );
608 #endif
609 
610  popLineStack();
611 
612  if( !pushLineStack( walkaroundLine ) )
613  return SH_INCOMPLETE;
614 
615  return SH_OK;
616 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:51
void popLineStack()
Definition: pns_shove.cpp:1026
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:267
ROUTING_SETTINGS & Settings() const
Returns current router settings
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
#define NULL
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:815
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:75
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References PNS::TOPOLOGY::AssembleCluster(), PNS::NODE::CheckColliding(), PNS::LINE::ClearSegmentLinks(), PNS::WALKAROUND::DONE, dummy(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::HasLoops(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::JOINT::LinkList(), PNS::LOGGER::Log(), m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), NULL, onCollidingVia(), popLineStack(), PNS::VIA::Pos(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), PNS::WALKAROUND::RestrictToSet(), PNS::WALKAROUND::Route(), PNS::ALGO_BASE::Router(), sanityCheck(), PNS::WALKAROUND::SetIterationLimit(), PNS::LINE::SetRank(), PNS::WALKAROUND::SetSingleDirection(), PNS::WALKAROUND::SetSolidsOnly(), PNS::ALGO_BASE::Settings(), SH_INCOMPLETE, SH_OK, SHAPE_LINE_CHAIN::Simplify(), LAYER_RANGE::Start(), PNS::LINE::Unmark(), PNS::LINE::Via(), and PNS::ITEM::VIA_T.

Referenced by shoveIteration().

◆ onCollidingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingVia ( ITEM aCurrent,
VIA aObstacleVia 
)
private

Definition at line 815 of file pns_shove.cpp.

816 {
817  int clearance = getClearance( aCurrent, aObstacleVia ) + PNS_HULL_MARGIN;
818  LINE_PAIR_VEC draggedLines;
819  bool lineCollision = false;
820  bool viaCollision = false;
821  bool holeCollision = false;
822  LINE* currentLine = NULL;
823  VECTOR2I mtvLine; // Minimum translation vector to correct line collisions
824  VECTOR2I mtvVia; // MTV to correct via collisions
825  VECTOR2I mtvHoles; // MTV to correct hole collisions
826  VECTOR2I mtvSolid; // MTV to correct solid collisions
827  VECTOR2I mtv; // Union of relevant MTVs (will correct all collisions)
828  int rank = -1;
829 
830  if( aCurrent->OfKind( ITEM::LINE_T ) )
831  {
832 #ifdef DEBUG
833  m_logger.NewGroup( "push-via-by-line", m_iter );
834  m_logger.Log( aCurrent, 4, "current" );
835 #endif
836 
837  currentLine = (LINE*) aCurrent;
838  lineCollision = aObstacleVia->Shape()->Collide( currentLine->Shape(),
839  clearance + currentLine->Width() / 2,
840  &mtvLine );
841 
842  if( currentLine->EndsWithVia() )
843  {
844  int currentNet = currentLine->Net();
845  int obstacleNet = aObstacleVia->Net();
846 
847  if( currentNet != obstacleNet && currentNet >= 0 && obstacleNet >= 0 )
848  {
849  viaCollision = currentLine->Via().Shape()->Collide( aObstacleVia->Shape(),
850  clearance, &mtvVia );
851  }
852 
853  // hole-to-hole is a mechanical constraint (broken drill bits), not an electrical
854  // one, so it has to be checked irrespective of matching nets.
855 
856  // temporarily removed hole-to-hole collision check due to conflicts with the springback algorithm...
857  // we need to figure out a better solution here - TW
858  holeCollision = false; //rr->CollideHoles( &currentLine->Via(), aObstacleVia, true, &mtvHoles );
859  }
860 
861  // These aren't /actually/ lengths as we don't bother to do the square-root part,
862  // but we're just comparing them to each other so it's faster this way.
863  ecoord lineMTVLength = lineCollision ? mtvLine.SquaredEuclideanNorm() : 0;
864  ecoord viaMTVLength = viaCollision ? mtvVia.SquaredEuclideanNorm() : 0;
865  ecoord holeMTVLength = holeCollision ? mtvHoles.SquaredEuclideanNorm() : 0;
866 
867  if( lineMTVLength >= viaMTVLength && lineMTVLength >= holeMTVLength )
868  mtv = mtvLine;
869  else if( viaMTVLength >= lineMTVLength && viaMTVLength >= holeMTVLength )
870  mtv = mtvVia;
871  else
872  mtv = mtvHoles;
873 
874  rank = currentLine->Rank();
875  }
876  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
877  {
878  aObstacleVia->Shape()->Collide( aCurrent->Shape(), clearance, &mtvSolid );
879  mtv = -mtvSolid;
880  rank = aCurrent->Rank() + 10000;
881  }
882 
883  return pushOrShoveVia( aObstacleVia, mtv, rank );
884 }
#define PNS_HULL_MARGIN
LINE.
Definition: pns_line.h:59
extended_type SquaredEuclideanNorm() const
Function Squared Euclidean Norm computes the squared euclidean norm of the vector,...
Definition: vector2d.h:306
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:688
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
#define NULL
VECTOR2I::extended_type ecoord
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:66
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References SHAPE::Collide(), PNS::LINE::EndsWithVia(), getClearance(), PNS::ITEM::LINE_T, PNS::LOGGER::Log(), m_iter, m_logger, PNS::ITEM::Net(), PNS::LOGGER::NewGroup(), NULL, PNS::ITEM::OfKind(), PNS_HULL_MARGIN, pushOrShoveVia(), PNS::ITEM::Rank(), PNS::LINE::Rank(), PNS::LINE::Shape(), PNS::VIA::Shape(), PNS::ITEM::Shape(), PNS::ITEM::SOLID_T, VECTOR2< T >::SquaredEuclideanNorm(), PNS::LINE::Via(), and PNS::LINE::Width().

Referenced by onCollidingSolid(), and shoveIteration().

◆ onReverseCollidingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::onReverseCollidingVia ( LINE aCurrent,
VIA aObstacleVia 
)
private

Definition at line 890 of file pns_shove.cpp.

891 {
892  int n = 0;
893  LINE cur( aCurrent );
894  cur.ClearSegmentLinks();
895 
896  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
897  LINE shoved( aCurrent );
898  shoved.ClearSegmentLinks();
899 
900  cur.RemoveVia();
901  unwindLineStack( &aCurrent );
902 
903  for( ITEM* item : jt->LinkList() )
904  {
905  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
906  {
907  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
908  LINE head = assembleLine( li );
909 
910  head.AppendVia( *aObstacleVia );
911 
912  SHOVE_STATUS st = ProcessSingleLine( head, cur, shoved );
913 
914  if( st != SH_OK )
915  {
916 #ifdef DEBUG
917  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
918  m_logger.Log( aObstacleVia, 0, "the-via" );
919  m_logger.Log( &aCurrent, 1, "current-line" );
920  m_logger.Log( &shoved, 3, "shoved-line" );
921 #endif
922 
923  return st;
924  }
925 
926  cur.SetShape( shoved.CLine() );
927  n++;
928  }
929  }
930 
931  if( !n )
932  {
933 #ifdef DEBUG
934  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
935  m_logger.Log( aObstacleVia, 0, "the-via" );
936  m_logger.Log( &aCurrent, 1, "current-line" );
937 #endif
938 
939  LINE head( aCurrent );
940  head.Line().Clear();
941  head.AppendVia( *aObstacleVia );
942  head.ClearSegmentLinks();
943 
944  SHOVE_STATUS st = ProcessSingleLine( head, aCurrent, shoved );
945 
946  if( st != SH_OK )
947  return st;
948 
949  cur.SetShape( shoved.CLine() );
950  }
951 
952  if( aCurrent.EndsWithVia() )
953  shoved.AppendVia( aCurrent.Via() );
954 
955 #ifdef DEBUG
956  m_logger.NewGroup( "on-reverse-via", m_iter );
957  m_logger.Log( aObstacleVia, 0, "the-via" );
958  m_logger.Log( &aCurrent, 1, "current-line" );
959  m_logger.Log( &shoved, 3, "shoved-line" );
960 #endif
961  int currentRank = aCurrent.Rank();
962  replaceLine( aCurrent, shoved );
963 
964  if( !pushLineStack( shoved ) )
965  return SH_INCOMPLETE;
966 
967  shoved.SetRank( currentRank );
968 
969  return SH_OK;
970 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:103
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:973
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:267
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
NODE * m_currentNode
Definition: pns_shove.h:162
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References PNS::LINE::AppendVia(), PNS::ITEM::ARC_T, assembleLine(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::ClearSegmentLinks(), PNS::LINE::CLine(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::Line(), PNS::JOINT::LinkList(), PNS::LOGGER::Log(), m_currentNode, m_iter, m_logger, PNS::LOGGER::NewGroup(), PNS::VIA::Pos(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), PNS::LINE::RemoveVia(), replaceLine(), PNS::ITEM::SEGMENT_T, PNS::LINE::SetRank(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, unwindLineStack(), and PNS::LINE::Via().

Referenced by shoveIteration().

◆ popLineStack()

void PNS::SHOVE::popLineStack ( )
private

Definition at line 1026 of file pns_shove.cpp.

1027 {
1028  LINE& l = m_lineStack.back();
1029 
1030  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1031  {
1032  bool found = false;
1033 
1034  for( auto s : l.LinkedSegments() )
1035  {
1036  if( i->ContainsSegment( s ) )
1037  {
1038  i = m_optimizerQueue.erase( i );
1039  found = true;
1040  break;
1041  }
1042  }
1043 
1044  if( !found )
1045  i++;
1046  }
1047 
1048  m_lineStack.pop_back();
1049 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158

References PNS::LINE::LinkedSegments(), m_lineStack, and m_optimizerQueue.

Referenced by onCollidingSolid(), and shoveIteration().

◆ processHullSet()

SHOVE::SHOVE_STATUS PNS::SHOVE::processHullSet ( LINE aCurrent,
LINE aObstacle,
LINE aShoved,
const HULL_SET hulls 
)
private

Definition at line 164 of file pns_shove.cpp.

166 {
167  const SHAPE_LINE_CHAIN& obs = aObstacle.CLine();
168 
169  int attempt;
170 
171  for( attempt = 0; attempt < 4; attempt++ )
172  {
173  bool invertTraversal = ( attempt >= 2 );
174  bool clockwise = attempt % 2;
175  int vFirst = -1, vLast = -1;
176 
177  SHAPE_LINE_CHAIN path;
178  LINE l( aObstacle );
179 
180  for( int i = 0; i < (int) aHulls.size(); i++ )
181  {
182  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
183 
184  if( ! l.Walkaround( hull, path, clockwise ) )
185  return SH_INCOMPLETE;
186 
187  path.Simplify();
188  l.SetShape( path );
189  }
190 
191  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
192  {
193  if( path.CPoint( i ) != obs.CPoint( i ) )
194  {
195  vFirst = i;
196  break;
197  }
198  }
199 
200  int k = obs.PointCount() - 1;
201  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
202  {
203  if( path.CPoint( i ) != obs.CPoint( k ) )
204  {
205  vLast = i;
206  break;
207  }
208  }
209 
210  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacle.CLine() ) )
211  {
212  wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
213  continue;
214  }
215 
216  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
217  {
218  wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
219  continue;
220  }
221 
222  if( !checkBumpDirection( aCurrent, aObstacle, l ) )
223  {
224  wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
225  aShoved.SetShape( l.CLine() );
226 
227  continue;
228  }
229 
230  if( path.SelfIntersecting() )
231  {
232  wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
233  continue;
234  }
235 
236  bool colliding = m_currentNode->CheckColliding( &l, &aCurrent, ITEM::ANY_T, m_forceClearance );
237 
238  if( ( aCurrent.Marker() & MK_HEAD ) && !colliding )
239  {
240  JOINT* jtStart = m_currentNode->FindJoint( aCurrent.CPoint( 0 ), &aCurrent );
241 
242  for( ITEM* item : jtStart->LinkList() )
243  {
244  if( m_currentNode->CheckColliding( item, &l ) )
245  colliding = true;
246  }
247  }
248 
249  if( colliding )
250  {
251  wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
252  continue;
253  }
254 
255  aShoved.SetShape( l.CLine() );
256 
257  return SH_OK;
258  }
259 
260  return SH_INCOMPLETE;
261 }
bool checkBumpDirection(const LINE &aCurrent, const LINE &aObstacle, const LINE &aShoved) const
Definition: pns_shove.cpp:116
int PointCount() const
Function PointCount()
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
bool clockwise(const Point &p0, const Point &p1, const Point &p2)
Definition: delauney.h:217
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
NODE * m_currentNode
Definition: pns_shove.h:162
int m_forceClearance
Definition: pns_shove.h:171
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const

References PNS::ITEM::ANY_T, checkBumpDirection(), PNS::NODE::CheckColliding(), PNS::LINE::CLine(), clockwise(), SHAPE_LINE_CHAIN::CompareGeometry(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::NODE::FindJoint(), PNS::JOINT::LinkList(), m_currentNode, m_forceClearance, PNS::LINE::Marker(), PNS::MK_HEAD, SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::SelfIntersecting(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, SHAPE_LINE_CHAIN::Simplify(), and PNS::LINE::Walkaround().

Referenced by ProcessSingleLine().

◆ ProcessSingleLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::ProcessSingleLine ( LINE aCurrent,
LINE aObstacle,
LINE aShoved 
)

Definition at line 267 of file pns_shove.cpp.

268 {
269  aShoved.ClearSegmentLinks();
270 
271  bool obstacleIsHead = false;
272 
273  for( auto s : aObstacle.LinkedSegments() )
274  {
275  if( s->Marker() & MK_HEAD )
276  {
277  obstacleIsHead = true;
278  break;
279  }
280  }
281 
282  SHOVE_STATUS rv;
283 
284  bool viaOnEnd = aCurrent.EndsWithVia();
285 
286  if( viaOnEnd && ( !aCurrent.LayersOverlap( &aObstacle ) || aCurrent.SegmentCount() == 0 ) )
287  {
288  rv = walkaroundLoneVia( aCurrent, aObstacle, aShoved );
289  }
290  else
291  {
292  int w = aObstacle.Width();
293  int n_segs = aCurrent.SegmentCount();
294 
295  int clearance = getClearance( &aCurrent, &aObstacle ) + 1;
296 
297  HULL_SET hulls;
298 
299  hulls.reserve( n_segs + 1 );
300 
301  for( int i = 0; i < n_segs; i++ )
302  {
303  SEGMENT seg( aCurrent, aCurrent.CSegment( i ) );
304  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, w );
305 
306  hulls.push_back( hull );
307  }
308 
309  if( viaOnEnd )
310  hulls.push_back( aCurrent.Via().Hull( clearance, w ) );
311 
312  rv = processHullSet( aCurrent, aObstacle, aShoved, hulls );
313  }
314 
315  if( obstacleIsHead )
316  aShoved.Mark( aShoved.Marker() | MK_HEAD );
317 
318  return rv;
319 }
SHOVE_STATUS processHullSet(LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
Definition: pns_shove.cpp:164
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:94
SHAPE_LINE_CHAIN.
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:66
SHOVE_STATUS walkaroundLoneVia(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:128

References PNS::LINE::ClearSegmentLinks(), PNS::LINE::CSegment(), PNS::LINE::EndsWithVia(), getClearance(), PNS::VIA::Hull(), PNS::ITEM::LayersOverlap(), PNS::LINE::LinkedSegments(), PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, processHullSet(), PNS::LINE::SegmentCount(), PNS::LINE::Via(), walkaroundLoneVia(), and PNS::LINE::Width().

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), and onReverseCollidingVia().

◆ pushLineStack()

bool PNS::SHOVE::pushLineStack ( const LINE aL,
bool  aKeepCurrentOnTop = false 
)
private

Definition at line 1007 of file pns_shove.cpp.

1008 {
1009  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1010  return false;
1011 
1012  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1013  {
1014  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1015  }
1016  else
1017  {
1018  m_lineStack.push_back( aL );
1019  }
1020 
1021  m_optimizerQueue.push_back( aL );
1022 
1023  return true;
1024 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158

References PNS::LINE::IsLinkedChecked(), m_lineStack, m_optimizerQueue, and PNS::LINE::SegmentCount().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onReverseCollidingVia(), pushOrShoveVia(), shoveIteration(), ShoveLines(), shoveMainLoop(), and ShoveMultiLines().

◆ pushOrShoveVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::pushOrShoveVia ( VIA aVia,
const VECTOR2I aForce,
int  aCurrentRank 
)
private

Definition at line 688 of file pns_shove.cpp.

689 {
690  LINE_PAIR_VEC draggedLines;
691  VECTOR2I p0( aVia->Pos() );
692  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
693  VECTOR2I p0_pushed( p0 + aForce );
694 
695  // nothing to do...
696  if ( aForce.x == 0 && aForce.y == 0 )
697  return SH_OK;
698 
699  if( !jt )
700  {
701  wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
702  return SH_INCOMPLETE;
703  }
704 
705  if( aVia->IsLocked() )
706  return SH_TRY_WALK;
707 
708  if( jt->IsLocked() )
709  return SH_INCOMPLETE;
710 
711  // make sure pushed via does not overlap with any existing joint
712  while( true )
713  {
714  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
715 
716  if( !jt_next )
717  break;
718 
719  p0_pushed += aForce.Resize( 2 );
720  }
721 
722  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
723  pushedVia->SetPos( p0_pushed );
724  pushedVia->Mark( aVia->Marker() );
725 
726  for( ITEM* item : jt->LinkList() )
727  {
728  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
729  {
730  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
731  LINE_PAIR lp;
732  int segIndex;
733 
734  lp.first = assembleLine( li, &segIndex );
735 
736  if( lp.first.HasLockedSegments() )
737  return SH_TRY_WALK;
738 
739  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
740 
741  if( segIndex == 0 )
742  lp.first.Reverse();
743 
744  lp.second = lp.first;
745  lp.second.ClearSegmentLinks();
746  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
747  lp.second.AppendVia( *pushedVia );
748  draggedLines.push_back( lp );
749  }
750  }
751 
752 #ifdef DEBUG
753  m_logger.Log( aVia, 0, "obstacle-via" );
754 #endif
755 
756  pushedVia->SetRank( aCurrentRank - 1 );
757 
758 #ifdef DEBUG
759  m_logger.Log( pushedVia.get(), 1, "pushed-via" );
760 #endif
761 
762  if( aVia->Marker() & MK_HEAD ) // push
763  {
764  m_draggedVia = pushedVia.get();
765  }
766  else
767  { // shove
768  if( jt->IsStitchingVia() )
769  pushLineStack( LINE( *pushedVia ) );
770  }
771 
772  replaceItems( aVia, std::move( pushedVia ) );
773 
774  for( LINE_PAIR lp : draggedLines )
775  {
776  if( lp.first.Marker() & MK_HEAD )
777  {
778  lp.second.Mark( MK_HEAD );
779 
780  if( m_multiLineMode )
781  return SH_INCOMPLETE;
782 
783  m_newHead = lp.second;
784  }
785 
786  unwindLineStack( &lp.first );
787 
788  if( lp.second.SegmentCount() )
789  {
790  replaceLine( lp.first, lp.second );
791  lp.second.SetRank( aCurrentRank - 1 );
792 
793  if( !pushLineStack( lp.second, true ) )
794  return SH_INCOMPLETE;
795  }
796  else
797  {
798  m_currentNode->Remove( lp.first );
799  }
800 
801 #ifdef DEBUG
802  m_logger.Log( &lp.first, 2, "fan-pre" );
803  m_logger.Log( &lp.second, 3, "fan-post" );
804 #endif
805  }
806 
807  return SH_OK;
808 }
bool IsLocked() const override
Function IsLocked.
Definition: class_track.h:133
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:103
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:973
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:96
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:271
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
VIA * m_draggedVia
Definition: pns_shove.h:168
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:56
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:46
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
NODE * m_currentNode
Definition: pns_shove.h:162
LOGGER m_logger
Definition: pns_shove.h:167

References PNS::ITEM::ARC_T, assembleLine(), PNS::Clone(), PNS::NODE::FindJoint(), PNS::ITEM::IsLocked(), PNS::LOGGER::Log(), m_currentNode, m_draggedVia, m_logger, m_multiLineMode, m_newHead, PNS::ITEM::Marker(), PNS::MK_HEAD, PNS::VIA::Pos(), pushLineStack(), PNS::NODE::Remove(), replaceItems(), replaceLine(), VECTOR2< T >::Resize(), PNS::ITEM::SEGMENT_T, SH_INCOMPLETE, SH_OK, SH_TRY_WALK, unwindLineStack(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by onCollidingVia(), and ShoveDraggingVia().

◆ pushSpringback()

bool PNS::SHOVE::pushSpringback ( NODE aNode,
const OPT_BOX2I aAffectedArea,
VIA aDraggedVia 
)
private

Definition at line 651 of file pns_shove.cpp.

652 {
653  SPRINGBACK_TAG st;
654  OPT_BOX2I prev_area;
655 
656  if( !m_nodeStack.empty() )
657  prev_area = m_nodeStack.back().m_affectedArea;
658 
659  if( aDraggedVia )
660  {
661  st.m_draggedVia = aDraggedVia->MakeHandle();
662  }
663 
664  st.m_node = aNode;
665 
666  if( aAffectedArea )
667  {
668  if( prev_area )
669  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
670  else
671  st.m_affectedArea = aAffectedArea;
672  } else
673  st.m_affectedArea = prev_area;
674 
675  st.m_seq = (m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1);
676  st.m_locked = false;
677 
678  m_nodeStack.push_back( st );
679 
680  return true;
681 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524

References PNS::SHOVE::SPRINGBACK_TAG::m_affectedArea, PNS::SHOVE::SPRINGBACK_TAG::m_draggedVia, PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, m_nodeStack, PNS::SHOVE::SPRINGBACK_TAG::m_seq, and PNS::VIA::MakeHandle().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

◆ reduceSpringback()

NODE * PNS::SHOVE::reduceSpringback ( const ITEM_SET aHeadSet,
VIA_HANDLE aDraggedVia 
)
private

Definition at line 623 of file pns_shove.cpp.

624 {
625  while( !m_nodeStack.empty() )
626  {
627  SPRINGBACK_TAG& spTag = m_nodeStack.back();
628 
629  auto obs = spTag.m_node->CheckColliding( aHeadSet );
630 
631  if( !obs && !spTag.m_locked )
632  {
633  aDraggedVia = spTag.m_draggedVia;
634  aDraggedVia.valid = true;
635 
636  delete spTag.m_node;
637  m_nodeStack.pop_back();
638  }
639  else
640  break;
641  }
642 
643  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
644 }
NODE * m_root
Definition: pns_shove.h:161
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

References PNS::NODE::CheckColliding(), PNS::SHOVE::SPRINGBACK_TAG::m_draggedVia, PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, m_nodeStack, m_root, and PNS::VIA_HANDLE::valid.

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

◆ replaceItems()

void PNS::SHOVE::replaceItems ( ITEM aOld,
std::unique_ptr< ITEM aNew 
)
private

Definition at line 46 of file pns_shove.cpp.

47 {
48  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
49 
50  if( changed_area )
51  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
52 
53  m_currentNode->Replace( aOld, std::move( aNew ) );
54 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:290
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:766
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524
NODE * m_currentNode
Definition: pns_shove.h:162

References PNS::ChangedArea(), m_affectedArea, m_currentNode, and PNS::NODE::Replace().

Referenced by pushOrShoveVia().

◆ replaceLine()

void PNS::SHOVE::replaceLine ( LINE aOld,
LINE aNew 
)
private

Definition at line 56 of file pns_shove.cpp.

57 {
58  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
59 
60  if( changed_area )
61  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
62 
63  m_currentNode->Replace( aOld, aNew );
64 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:290
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:766
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524
NODE * m_currentNode
Definition: pns_shove.h:162

References PNS::ChangedArea(), m_affectedArea, m_currentNode, and PNS::NODE::Replace().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onReverseCollidingVia(), and pushOrShoveVia().

◆ RewindSpringbackTo()

bool PNS::SHOVE::RewindSpringbackTo ( NODE aNode)

Definition at line 1626 of file pns_shove.cpp.

1627 {
1628  bool found = false;
1629 
1630  auto iter = m_nodeStack.begin();
1631 
1632  while( iter != m_nodeStack.end() )
1633  {
1634  if ( iter->m_node == aNode )
1635  {
1636  found = true;
1637  break;
1638  }
1639  iter++;
1640  }
1641 
1642  if( !found )
1643  return false;
1644 
1645  auto start = iter;
1646 
1647  aNode->KillChildren();
1648  m_nodeStack.erase( start, m_nodeStack.end() );
1649 
1650  return true;
1651 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

References PNS::NODE::KillChildren(), and m_nodeStack.

◆ Router()

◆ runOptimizer()

void PNS::SHOVE::runOptimizer ( NODE aNode)
private

Definition at line 1523 of file pns_shove.cpp.

1524 {
1525  OPTIMIZER optimizer( aNode );
1526  int optFlags = 0;
1527  int n_passes = 0;
1528 
1530 
1531  OPT_BOX2I area = totalAffectedArea();
1532 
1533  int maxWidth = 0;
1534 
1535  for( LINE& line : m_optimizerQueue )
1536  maxWidth = std::max( line.Width(), maxWidth );
1537 
1538  if( area )
1539  area->Inflate( 10 * maxWidth );
1540 
1541  switch( effort )
1542  {
1543  case OE_LOW:
1544  optFlags = OPTIMIZER::MERGE_OBTUSE;
1545  n_passes = 1;
1546  break;
1547 
1548  case OE_MEDIUM:
1549  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1550 
1551  if( area )
1552  optimizer.SetRestrictArea( *area );
1553 
1554  n_passes = 2;
1555  break;
1556 
1557  case OE_FULL:
1558  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1559  n_passes = 2;
1560  break;
1561 
1562  default:
1563  break;
1564  }
1565 
1566  if( Settings().SmartPads() )
1567  optFlags |= OPTIMIZER::SMART_PADS;
1568 
1569  optimizer.SetEffortLevel( optFlags );
1570  optimizer.SetCollisionMask( ITEM::ANY_T );
1571 
1572  for( int pass = 0; pass < n_passes; pass++ )
1573  {
1574  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1575 
1576  for( LINE& line : m_optimizerQueue)
1577  {
1578  if( !( line.Marker() & MK_HEAD ) )
1579  {
1580  LINE optimized;
1581 
1582  if( optimizer.Optimize( &line, &optimized ) )
1583  {
1584  aNode->Remove( line );
1585  line.SetShape( optimized.CLine() );
1586  aNode->Add( line );
1587  }
1588  }
1589  }
1590  }
1591 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
ROUTING_SETTINGS & Settings() const
Returns current router settings
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1229
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Returns the optimizer effort. Bigger means cleaner traces, but slower routing.
PNS_OPTIMIZATION_EFFORT
Optimization effort
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524

References PNS::NODE::Add(), PNS::ITEM::ANY_T, PNS::LINE::CLine(), m_optimizerQueue, PNS::OPTIMIZER::MERGE_OBTUSE, PNS::OPTIMIZER::MERGE_SEGMENTS, PNS::MK_HEAD, PNS::OE_FULL, PNS::OE_LOW, PNS::OE_MEDIUM, PNS::OPTIMIZER::Optimize(), PNS::ROUTING_SETTINGS::OptimizerEffort(), PNS::NODE::Remove(), PNS::OPTIMIZER::SetCollisionMask(), PNS::OPTIMIZER::SetEffortLevel(), PNS::OPTIMIZER::SetRestrictArea(), PNS::ALGO_BASE::Settings(), PNS::OPTIMIZER::SMART_PADS, and totalAffectedArea().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

◆ sanityCheck()

void PNS::SHOVE::sanityCheck ( LINE aOld,
LINE aNew 
)
private

Definition at line 75 of file pns_shove.cpp.

76 {
77  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
78  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
79 }

References PNS::LINE::CPoint().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), and onCollidingSolid().

◆ SetDebugDecorator()

void PNS::ALGO_BASE::SetDebugDecorator ( DEBUG_DECORATOR aDecorator)
inlineinherited

Function SetDebugDecorator.

Assign a debug decorator allowing this algo to draw extra graphics for visual debugging

Definition at line 72 of file pns_algo_base.h.

73  {
74  m_debugDecorator = aDecorator;
75  }
DEBUG_DECORATOR * m_debugDecorator
Definition: pns_algo_base.h:83

References PNS::ALGO_BASE::m_debugDecorator.

Referenced by PNS::DRAGGER::dragWalkaround(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), and SHOVE().

◆ SetInitialLine()

void PNS::SHOVE::SetInitialLine ( LINE aInitial)

Definition at line 1608 of file pns_shove.cpp.

1609 {
1610  m_root = m_root->Branch();
1611  m_root->Remove( aInitial );
1612 }
NODE * m_root
Definition: pns_shove.h:161
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796

References PNS::NODE::Branch(), m_root, and PNS::NODE::Remove().

◆ SetLogger()

void PNS::ALGO_BASE::SetLogger ( LOGGER aLogger)
inlineinherited

Definition at line 62 of file pns_algo_base.h.

63  {
64  m_logger = aLogger;
65  }
LOGGER * m_logger
Definition: pns_algo_base.h:85

References PNS::ALGO_BASE::m_logger.

Referenced by PNS::DRAGGER::dragWalkaround(), PNS::LINE_PLACER::rhShoveOnly(), and PNS::LINE_PLACER::rhWalkOnly().

◆ Settings()

◆ ShoveDraggingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveDraggingVia ( const VIA_HANDLE  aOldVia,
const VECTOR2I aWhere,
VIA_HANDLE aNewVia 
)

Definition at line 1451 of file pns_shove.cpp.

1452 {
1453  SHOVE_STATUS st = SH_OK;
1454 
1455  m_lineStack.clear();
1456  m_optimizerQueue.clear();
1457  m_newHead = OPT_LINE();
1458  m_draggedVia = NULL;
1459 
1460  auto viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1461 
1462  if( !viaToDrag )
1463  {
1464  return SH_INCOMPLETE;
1465  }
1466 
1467  // Pop NODEs containing previous shoves which are no longer necessary
1468  ITEM_SET headSet;
1469 
1470  VIA headVia ( *viaToDrag );
1471  headVia.SetPos( aWhere );
1472  headSet.Add( headVia );
1473  VIA_HANDLE prevViaHandle;
1474  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1475 
1476  if( prevViaHandle.valid )
1477  {
1478  aNewVia = prevViaHandle;
1479  viaToDrag = findViaByHandle( parent, prevViaHandle );
1480  }
1481 
1482  // Create a new NODE to store this version of the world
1483  //
1484  m_currentNode = parent->Branch();
1486 
1487  viaToDrag->Mark( MK_HEAD );
1488  viaToDrag->SetRank( 100000 );
1489 
1490  // Push the via to its new location
1491  //
1492  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos()), 0 );
1493 
1494  // Shove any colliding objects out of the way
1495  //
1496  if( st == SH_OK )
1497  st = shoveMainLoop();
1498 
1499  if( st == SH_OK )
1501 
1502  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1503  {
1504  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1505 
1506  if (!m_draggedVia)
1507  m_draggedVia = viaToDrag;
1508 
1509  aNewVia = m_draggedVia->MakeHandle();
1510 
1512  }
1513  else
1514  {
1515  delete m_currentNode;
1516  m_currentNode = parent;
1517  }
1518 
1519  return st;
1520 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1316
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:115
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:688
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:623
#define NULL
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1523
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1432
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:651
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:146
VIA * m_draggedVia
Definition: pns_shove.h:168
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1189
OPT_LINE m_newHead
Definition: pns_shove.h:165
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162

References PNS::ITEM_SET::Add(), PNS::NODE::Branch(), PNS::NODE::ClearRanks(), PNS::findViaByHandle(), m_affectedArea, m_currentNode, m_draggedVia, m_lineStack, m_newHead, m_optimizerQueue, PNS::VIA::MakeHandle(), PNS::MK_HEAD, NULL, pushOrShoveVia(), pushSpringback(), reduceSpringback(), runOptimizer(), PNS::VIA::SetPos(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::VIA_HANDLE::valid.

◆ shoveIteration()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveIteration ( int  aIter)
private

Definition at line 1055 of file pns_shove.cpp.

1056 {
1057  LINE currentLine = m_lineStack.back();
1058  NODE::OPT_OBSTACLE nearest;
1059  SHOVE_STATUS st = SH_NULL;
1060 
1061  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1062  {
1063  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1064 
1065  if( nearest )
1066  break;
1067  }
1068 
1069  if( !nearest )
1070  {
1071  m_lineStack.pop_back();
1072  return SH_OK;
1073  }
1074 
1075  ITEM* ni = nearest->m_item;
1076 
1077  unwindLineStack( ni );
1078 
1079  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1080  {
1081  // Collision with a higher-ranking object (ie: one that we've already shoved)
1082  //
1083  switch( ni->Kind() )
1084  {
1085  case ITEM::VIA_T:
1086  {
1087  wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
1088 
1089  if( currentLine.EndsWithVia()
1090  && m_currentNode->CheckColliding( &currentLine.Via(), (VIA*) ni ) )
1091  {
1092  st = SH_INCOMPLETE;
1093  }
1094  else
1095  {
1096  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1097  }
1098 
1099  break;
1100  }
1101 
1102  case ITEM::SEGMENT_T:
1103  {
1104  wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
1105  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1106 
1107  popLineStack();
1108  st = onCollidingLine( revLine, currentLine );
1109  if( !pushLineStack( revLine ) )
1110  return SH_INCOMPLETE;
1111 
1112  break;
1113  }
1114 
1115  case ITEM::ARC_T:
1116  {
1117  //TODO(snh): Handle Arc shove separate from track
1118  wxLogTrace( "PNS", "iter %d: reverse-collide-arc ", aIter );
1119  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1120 
1121  popLineStack();
1122  st = onCollidingLine( revLine, currentLine );
1123  if( !pushLineStack( revLine ) )
1124  return SH_INCOMPLETE;
1125 
1126  break;
1127  }
1128 
1129  default:
1130  assert( false );
1131  }
1132  }
1133  else
1134  {
1135  // Collision with a lower-ranking object or a solid
1136  //
1137  switch( ni->Kind() )
1138  {
1139  case ITEM::SEGMENT_T:
1140  wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
1141 
1142  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1143 
1144  if( st == SH_TRY_WALK )
1145  st = onCollidingSolid( currentLine, ni );
1146 
1147  break;
1148 
1149  //TODO(snh): Customize Arc collide
1150  case ITEM::ARC_T:
1151  wxLogTrace( "PNS", "iter %d: collide-arc ", aIter );
1152 
1153  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1154 
1155  if( st == SH_TRY_WALK )
1156  st = onCollidingSolid( currentLine, ni );
1157 
1158  break;
1159 
1160  case ITEM::VIA_T:
1161  wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1162  st = onCollidingVia( &currentLine, (VIA*) ni );
1163 
1164  if( st == SH_TRY_WALK )
1165  st = onCollidingSolid( currentLine, ni );
1166 
1167  break;
1168 
1169  case ITEM::SOLID_T:
1170  wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1171  st = onCollidingSolid( currentLine, (SOLID*) ni );
1172  break;
1173 
1174  default:
1175  break;
1176  }
1177  }
1178 
1179  return st;
1180 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:103
void popLineStack()
Definition: pns_shove.cpp:1026
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:490
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:973
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:304
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:386
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:447
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:890
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:815
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:325
PnsKind
Supported item types
Definition: pns_item.h:59
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162

References PNS::ITEM::ARC_T, assembleLine(), PNS::NODE::CheckColliding(), PNS::LINE::EndsWithVia(), PNS::ITEM::Kind(), m_currentNode, m_lineStack, PNS::NODE::NearestObstacle(), PNS::ITEM::OfKind(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onCollidingVia(), onReverseCollidingVia(), popLineStack(), pushLineStack(), PNS::ITEM::Rank(), PNS::LINE::Rank(), PNS::ITEM::SEGMENT_T, SH_INCOMPLETE, SH_NULL, SH_OK, SH_TRY_WALK, PNS::ITEM::SOLID_T, unwindLineStack(), PNS::LINE::Via(), and PNS::ITEM::VIA_T.

Referenced by shoveMainLoop().

◆ ShoveLines()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveLines ( const LINE aCurrentHead)

Definition at line 1245 of file pns_shove.cpp.

1246 {
1247  SHOVE_STATUS st = SH_OK;
1248 
1249  m_multiLineMode = false;
1250 
1251  // empty head? nothing to shove...
1252 
1253  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1254  return SH_INCOMPLETE;
1255 
1256  LINE head( aCurrentHead );
1257  head.ClearSegmentLinks();
1258 
1259  m_lineStack.clear();
1260  m_optimizerQueue.clear();
1261  m_newHead = OPT_LINE();
1262  m_logger.Clear();
1263 
1264  // Pop NODEs containing previous shoves which are no longer necessary
1265  //
1266  ITEM_SET headSet;
1267  headSet.Add( aCurrentHead );
1268 
1269  VIA_HANDLE dummyVia;
1270 
1271  NODE* parent = reduceSpringback( headSet, dummyVia );
1272 
1273  // Create a new NODE to store this version of the world
1274  //
1275  m_currentNode = parent->Branch();
1277  m_currentNode->Add( head );
1278 
1279  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1280 
1281  if( !head.EndsWithVia() )
1282  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1283 
1284  head.Mark( MK_HEAD );
1285  head.SetRank( 100000 );
1286 
1287  m_logger.NewGroup( "initial", 0 );
1288  m_logger.Log( &head, 0, "head" );
1289 
1290  if( head.EndsWithVia() )
1291  {
1292  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1293  headVia->Mark( MK_HEAD );
1294  headVia->SetRank( 100000 );
1295  m_logger.Log( headVia.get(), 0, "head-via" );
1296  m_currentNode->Add( std::move( headVia ) );
1297  }
1298 
1299  if( !pushLineStack( head ) )
1300  {
1301  delete m_currentNode;
1302  m_currentNode = parent;
1303 
1304  return SH_INCOMPLETE;
1305  }
1306 
1307  st = shoveMainLoop();
1308 
1309  if( st == SH_OK )
1310  {
1312 
1313  if( m_newHead )
1315  else
1316  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1317  }
1318 
1320 
1321  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1322  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1323 
1324  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1325  {
1327  }
1328  else
1329  {
1330  delete m_currentNode;
1331 
1332  m_currentNode = parent;
1333  m_newHead = OPT_LINE();
1334  }
1335 
1336  if(m_newHead)
1337  m_newHead->Unmark();
1338 
1339  if( m_newHead && head.EndsWithVia() )
1340  {
1341  VIA v = head.Via();
1342  v.SetPos( m_newHead->CPoint( -1 ) );
1343  m_newHead->AppendVia(v);
1344  }
1345 
1346  return st;
1347 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1316
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:623
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1523
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:651
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:146
void Clear()
Definition: pns_logger.cpp:48
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:271
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1326
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1189
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1057

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::LOGGER::Clear(), PNS::NODE::ClearRanks(), PNS::LINE::ClearSegmentLinks(), PNS::Clone(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), PNS::NODE::LockJoint(), PNS::LOGGER::Log(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, m_optimizerQueue, PNS::LINE::Mark(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::VIA::SetPos(), PNS::LINE::SetRank(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::LINE::Via().

◆ shoveMainLoop()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveMainLoop ( )
private

Definition at line 1189 of file pns_shove.cpp.

1190 {
1191  SHOVE_STATUS st = SH_OK;
1192 
1194 
1195  wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1197 
1198  int iterLimit = Settings().ShoveIterationLimit();
1199  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1200 
1201  m_iter = 0;
1202 
1203  timeLimit.Restart();
1204 
1205  if( m_lineStack.empty() && m_draggedVia )
1206  {
1207  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1208  // the stack.
1210  }
1211 
1212  while( !m_lineStack.empty() )
1213  {
1214  st = shoveIteration( m_iter );
1215 
1216  m_iter++;
1217 
1218  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1219  {
1220  st = SH_INCOMPLETE;
1221  break;
1222  }
1223  }
1224 
1225  return st;
1226 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
int JointCount() const
Returns the number of joints
Definition: pns_node.h:182
NODE * m_root
Definition: pns_shove.h:161
ROUTING_SETTINGS & Settings() const
Returns current router settings
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1055
VIA * m_draggedVia
Definition: pns_shove.h:168
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162
int m_iter
Definition: pns_shove.h:170
TIME_LIMIT ShoveTimeLimit() const

References PNS::TIME_LIMIT::Expired(), PNS::NODE::JointCount(), m_affectedArea, m_currentNode, m_draggedVia, m_iter, m_lineStack, m_root, pushLineStack(), PNS::TIME_LIMIT::Restart(), PNS::ALGO_BASE::Settings(), SH_INCOMPLETE, SH_OK, shoveIteration(), PNS::ROUTING_SETTINGS::ShoveIterationLimit(), and PNS::ROUTING_SETTINGS::ShoveTimeLimit().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

◆ ShoveMultiLines()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveMultiLines ( const ITEM_SET aHeadSet)

Definition at line 1350 of file pns_shove.cpp.

1351 {
1352  SHOVE_STATUS st = SH_OK;
1353 
1354  m_multiLineMode = true;
1355 
1356  ITEM_SET headSet;
1357 
1358  for( const ITEM* item : aHeadSet.CItems() )
1359  {
1360  const LINE* headOrig = static_cast<const LINE*>( item );
1361 
1362  // empty head? nothing to shove...
1363  if( !headOrig->SegmentCount() )
1364  return SH_INCOMPLETE;
1365 
1366  headSet.Add( *headOrig );
1367  }
1368 
1369  m_lineStack.clear();
1370  m_optimizerQueue.clear();
1371  m_logger.Clear();
1372 
1373  VIA_HANDLE dummyVia;
1374 
1375  NODE* parent = reduceSpringback( headSet, dummyVia );
1376 
1377  m_currentNode = parent->Branch();
1379  int n = 0;
1380 
1381  for( const ITEM* item : aHeadSet.CItems() )
1382  {
1383  const LINE* headOrig = static_cast<const LINE*>( item );
1384  LINE head( *headOrig );
1385  head.ClearSegmentLinks();
1386 
1387  m_currentNode->Add( head );
1388 
1389  head.Mark( MK_HEAD );
1390  head.SetRank( 100000 );
1391  n++;
1392 
1393  if( !pushLineStack( head ) )
1394  return SH_INCOMPLETE;
1395 
1396  if( head.EndsWithVia() )
1397  {
1398  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1399  headVia->Mark( MK_HEAD );
1400  headVia->SetRank( 100000 );
1401  m_logger.Log( headVia.get(), 0, "head-via" );
1402  m_currentNode->Add( std::move( headVia ) );
1403  }
1404  }
1405 
1406  m_logger.NewGroup( "initial", 0 );
1407  //m_logger.Log( head, 0, "head" );
1408 
1409  st = shoveMainLoop();
1410 
1411  if( st == SH_OK )
1413 
1415 
1416  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1417  ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1418 
1419  if( st == SH_OK )
1420  {
1422  }
1423  else
1424  {
1425  delete m_currentNode;
1426  m_currentNode = parent;
1427  }
1428 
1429  return st;
1430 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1007
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1316
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:623
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1523
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:651
void Log(const ITEM *aItem, int aKind=0, const std::string &aName=std::string())
Definition: pns_logger.cpp:75
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:146
void Clear()
Definition: pns_logger.cpp:48
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:271
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1326
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1189
bool m_multiLineMode
Definition: pns_shove.h:172
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::ITEM_SET::CItems(), PNS::LOGGER::Clear(), PNS::NODE::ClearRanks(), PNS::LINE::ClearSegmentLinks(), PNS::Clone(), PNS::LINE::EndsWithVia(), PNS::LOGGER::Log(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_optimizerQueue, PNS::LINE::Mark(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::LINE::Via().

Referenced by PNS::DIFF_PAIR_PLACER::rhShoveOnly().

◆ totalAffectedArea()

OPT_BOX2I PNS::SHOVE::totalAffectedArea ( ) const
private

Definition at line 1229 of file pns_shove.cpp.

1230 {
1231  OPT_BOX2I area;
1232 
1233  if( !m_nodeStack.empty() )
1234  area = m_nodeStack.back().m_affectedArea;
1235 
1236  if( area && m_affectedArea)
1237  area->Merge( *m_affectedArea );
1238  else if( !area )
1239  area = m_affectedArea;
1240 
1241  return area;
1242 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:524

References m_affectedArea, and m_nodeStack.

Referenced by runOptimizer().

◆ UnlockSpringbackNode()

void PNS::SHOVE::UnlockSpringbackNode ( NODE aNode)

Definition at line 1654 of file pns_shove.cpp.

1655 {
1656  auto iter = m_nodeStack.begin();
1657 
1658  while( iter != m_nodeStack.end() )
1659  {
1660  if ( iter->m_node == aNode )
1661  {
1662  iter->m_locked = false;
1663  break;
1664  }
1665  iter++;
1666  }
1667 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

References m_nodeStack.

◆ unwindLineStack() [1/2]

void PNS::SHOVE::unwindLineStack ( LINKED_ITEM aSeg)
private

Definition at line 973 of file pns_shove.cpp.

974 {
975  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
976  {
977  if( i->ContainsSegment( aSeg ) )
978  i = m_lineStack.erase( i );
979  else
980  i++;
981  }
982 
983  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
984  {
985  if( i->ContainsSegment( aSeg ) )
986  i = m_optimizerQueue.erase( i );
987  else
988  i++;
989  }
990 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158

References m_lineStack, and m_optimizerQueue.

Referenced by onReverseCollidingVia(), pushOrShoveVia(), shoveIteration(), and unwindLineStack().

◆ unwindLineStack() [2/2]

void PNS::SHOVE::unwindLineStack ( ITEM aItem)
private

Definition at line 993 of file pns_shove.cpp.

994 {
995  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
996  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
997  else if( aItem->OfKind( ITEM::LINE_T ) )
998  {
999  LINE* l = static_cast<LINE*>( aItem );
1000 
1001  for( auto seg : l->LinkedSegments() )
1002  unwindLineStack( seg );
1003  }
1004 }
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:973

References PNS::ITEM::ARC_T, PNS::ITEM::LINE_T, PNS::LINE::LinkedSegments(), PNS::ITEM::OfKind(), PNS::ITEM::SEGMENT_T, and unwindLineStack().

◆ walkaroundLoneVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::walkaroundLoneVia ( LINE aCurrent,
LINE aObstacle,
LINE aShoved 
)
private

Definition at line 128 of file pns_shove.cpp.

129 {
130  int clearance = getClearance( &aCurrent, &aObstacle );
131  const SHAPE_LINE_CHAIN hull = aCurrent.Via().Hull( clearance, aObstacle.Width() );
132  SHAPE_LINE_CHAIN path_cw;
133  SHAPE_LINE_CHAIN path_ccw;
134 
135  if( ! aObstacle.Walkaround( hull, path_cw, true ) )
136  return SH_INCOMPLETE;
137 
138  if( ! aObstacle.Walkaround( hull, path_ccw, false ) )
139  return SH_INCOMPLETE;
140 
141  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
142 
143  if( shortest.PointCount() < 2 )
144  return SH_INCOMPLETE;
145 
146  if( aObstacle.CPoint( -1 ) != shortest.CPoint( -1 ) )
147  return SH_INCOMPLETE;
148 
149  if( aObstacle.CPoint( 0 ) != shortest.CPoint( 0 ) )
150  return SH_INCOMPLETE;
151 
152  aShoved.SetShape( shortest );
153 
154  if( m_currentNode->CheckColliding( &aShoved, &aCurrent ) )
155  return SH_INCOMPLETE;
156 
157  return SH_OK;
158 }
long long int Length() const
Function Length()
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:66
NODE * m_currentNode
Definition: pns_shove.h:162

References PNS::NODE::CheckColliding(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), getClearance(), PNS::VIA::Hull(), SHAPE_LINE_CHAIN::Length(), m_currentNode, SHAPE_LINE_CHAIN::PointCount(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, PNS::LINE::Via(), PNS::LINE::Walkaround(), and PNS::LINE::Width().

Referenced by ProcessSingleLine().

Member Data Documentation

◆ m_affectedArea

OPT_BOX2I PNS::SHOVE::m_affectedArea
private

◆ m_currentNode

◆ m_debugDecorator

DEBUG_DECORATOR* PNS::ALGO_BASE::m_debugDecorator
protectedinherited

Definition at line 83 of file pns_algo_base.h.

Referenced by PNS::ALGO_BASE::Dbg(), and PNS::ALGO_BASE::SetDebugDecorator().

◆ m_draggedVia

VIA* PNS::SHOVE::m_draggedVia
private

Definition at line 168 of file pns_shove.h.

Referenced by pushOrShoveVia(), SHOVE(), ShoveDraggingVia(), and shoveMainLoop().

◆ m_forceClearance

int PNS::SHOVE::m_forceClearance
private

Definition at line 171 of file pns_shove.h.

Referenced by ForceClearance(), getClearance(), processHullSet(), and SHOVE().

◆ m_iter

◆ m_lineStack

std::vector<LINE> PNS::SHOVE::m_lineStack
private

◆ m_logger

◆ m_multiLineMode

bool PNS::SHOVE::m_multiLineMode
private

◆ m_newHead

◆ m_nodeStack

std::vector<SPRINGBACK_TAG> PNS::SHOVE::m_nodeStack
private

◆ m_optimizerQueue

std::vector<LINE> PNS::SHOVE::m_optimizerQueue
private

◆ m_restrictSpringbackTagId

int PNS::SHOVE::m_restrictSpringbackTagId
private

Definition at line 163 of file pns_shove.h.

Referenced by SHOVE().

◆ m_root

NODE* PNS::SHOVE::m_root
private

Definition at line 161 of file pns_shove.h.

Referenced by CurrentNode(), reduceSpringback(), SetInitialLine(), SHOVE(), and shoveMainLoop().

◆ m_router

ROUTER* PNS::ALGO_BASE::m_router
protectedinherited

Definition at line 84 of file pns_algo_base.h.

Referenced by PNS::ALGO_BASE::Router(), and PNS::ALGO_BASE::Settings().


The documentation for this class was generated from the following files: