The actual Push and Shove algorithm. More...

#include <pns_shove.h>

Inheritance diagram for PNS::SHOVE:

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 LOGGER *	Logger () override

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	ShoveObstacleLine (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)

void	ForceClearance (bool aEnabled, int aClearance)

NODE *	CurrentNode ()

const LINE	NewHead () const

void	SetInitialLine (LINE &aInitial)

bool	AddLockedSpringbackNode (NODE *aNode)

void	UnlockSpringbackNode (NODE *aNode)

bool	RewindSpringbackTo (NODE *aNode)

ROUTER *	Router () const
	Return current router settings. More...

ROUTING_SETTINGS &	Settings () const
	Return the logger object, allowing to dump geometry to a file. More...

void	SetLogger (LOGGER *aLogger)

void	SetDebugDecorator (DEBUG_DECORATOR *aDecorator)
	Assign a debug decorator allowing this algo to draw extra graphics for visual debugging. More...

DEBUG_DECORATOR *	Dbg () const

const BOX2I &	VisibleViewArea () const

Protected Attributes
DEBUG_DECORATOR *	m_debugDecorator

ROUTER *	m_router

Private Types
typedef std::vector< SHAPE_LINE_CHAIN >	HULL_SET

typedef OPT< LINE >	OPT_LINE

typedef std::pair< LINE, LINE >	LINE_PAIR

typedef std::vector< LINE_PAIR >	LINE_PAIR_VEC

Private Member Functions
SHOVE_STATUS	shoveLineToHullSet (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)

NODE *	reduceSpringback (const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)

bool	pushSpringback (NODE aNode, const OPT_BOX2I &aAffectedArea, VIA aDraggedVia)

SHOVE_STATUS	shoveLineFromLoneVia (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)

bool	checkShoveDirection (const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) 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=nullptr)

void	replaceItems (ITEM *aOld, std::unique_ptr< ITEM > aNew)

void	replaceLine (LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)

LINE *	findRootLine (LINE *aLine)

SHOVE_STATUS	shoveIteration (int aIter)

SHOVE_STATUS	shoveMainLoop ()

int	getClearance (const ITEM aA, const ITEM aB) const

int	getHoleClearance (const ITEM aA, const ITEM aB) const

void	sanityCheck (LINE aOld, LINE aNew)

Private Attributes
OPT_BOX2I	m_affectedArea

std::vector< SPRINGBACK_TAG >	m_nodeStack

std::vector< LINE >	m_lineStack

std::vector< LINE >	m_optimizerQueue

std::unordered_map< const LINKED_ITEM , LINE >	m_rootLineHistory

NODE *	m_root

NODE *	m_currentNode

int	m_restrictSpringbackTagId

OPT_LINE	m_newHead

LOGGER	m_logger

VIA *	m_draggedVia

int	m_iter

int	m_forceClearance

bool	m_multiLineMode

Detailed Description

The actual Push and Shove algorithm.

Definition at line 45 of file pns_shove.h.

Member Typedef Documentation

◆ HULL_SET

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

private

Definition at line 93 of file pns_shove.h.

◆ LINE_PAIR

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

private

Definition at line 95 of file pns_shove.h.

◆ LINE_PAIR_VEC

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

private

Definition at line 96 of file pns_shove.h.

◆ OPT_LINE

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

private

Definition at line 94 of file pns_shove.h.

Member Enumeration Documentation

◆ SHOVE_STATUS

enum PNS::SHOVE::SHOVE_STATUS

Enumerator
SH_OK
SH_NULL
SH_INCOMPLETE
SH_HEAD_MODIFIED
SH_TRY_WALK

Definition at line 49 of file pns_shove.h.

  {
  SH_OK = 0,
  SH_NULL,
  SH_INCOMPLETE,
  SH_HEAD_MODIFIED,
  SH_TRY_WALK
  };

Constructor & Destructor Documentation

◆ SHOVE()

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

Definition at line 159 of file pns_shove.cpp.

  :
  ALGO_BASE( aRouter )
 {
  m_forceClearance = -1;
  m_root = aWorld;
  m_currentNode = aWorld;
  SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );
 
  // Initialize other temporary variables:
  m_draggedVia = nullptr;
  m_iter = 0;
  m_multiLineMode = false;
  m_restrictSpringbackTagId = 0;
 }

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

◆ ~SHOVE()

PNS::SHOVE::~SHOVE ( )

Definition at line 175 of file pns_shove.cpp.

 {
  std::unordered_set<LINE*> alreadyDeleted;
 
  for( auto it : m_rootLineHistory )
  {
  auto it2 = alreadyDeleted.find( it.second );
 
  if( it2 == alreadyDeleted.end() )
  {
  alreadyDeleted.insert( it.second );
  delete it.second;
  }
  }
 }

References m_rootLineHistory.

Member Function Documentation

◆ AddLockedSpringbackNode()

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

Definition at line 1801 of file pns_shove.cpp.

 {
  SPRINGBACK_TAG sp;
  sp.m_node = aNode;
  sp.m_locked = true;
 
  m_nodeStack.push_back(sp);
  return true;
 }

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 = `nullptr`
	)

private

Definition at line 192 of file pns_shove.cpp.

 {
  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
 }

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

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

◆ checkShoveDirection()

bool PNS::SHOVE::checkShoveDirection	(	const LINE &	aCurLine,
		const LINE &	aObstacleLine,
		const LINE &	aShovedLine
	)		const

private

Definition at line 206 of file pns_shove.cpp.

 {
  SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
  checker.AddPolyline( aObstacleLine.CLine() );
  checker.AddPolyline( aShovedLine.CLine().Reverse() );
 
  bool inside = checker.IsInside();
 
  return !inside;
 }

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

Referenced by shoveLineToHullSet().

◆ CurrentNode()

NODE * PNS::SHOVE::CurrentNode ( )

Definition at line 1780 of file pns_shove.cpp.

 {
  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
 }

References m_nodeStack, and m_root.

◆ Dbg()

DEBUG_DECORATOR* PNS::ALGO_BASE::Dbg ( ) const

inlineinherited

Definition at line 78 of file pns_algo_base.h.

  {
  return m_debugDecorator;
  }

References PNS::ALGO_BASE::m_debugDecorator.

Referenced by PNS::MEANDER_PLACER::doMove(), PNS::COMPONENT_DRAGGER::Drag(), PNS::DRAGGER::dragShove(), PNS::DRAGGER::dragWalkaround(), PNS::MEANDER_SKEW_PLACER::Move(), PNS::DP_MEANDER_PLACER::Move(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onCollidingVia(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), PNS::LINE_PLACER::optimizeTailHeadTransition(), pushOrShoveVia(), replaceLine(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), PNS::LINE_PLACER::routeStep(), runOptimizer(), shoveIteration(), ShoveLines(), shoveLineToHullSet(), shoveMainLoop(), ShoveMultiLines(), ShoveObstacleLine(), PNS::WALKAROUND::singleStep(), PNS::DRAGGER::Start(), and PNS::DRAGGER::tryWalkaround().

◆ findRootLine()

LINE * PNS::SHOVE::findRootLine ( LINE * aLine )

private

Definition at line 1679 of file pns_shove.cpp.

 {
  for( auto link : aLine->Links() )
  {
  if( auto seg = dyn_cast<SEGMENT*>( link ) )
  {
  auto it = m_rootLineHistory.find( seg );
 
  if( it != m_rootLineHistory.end() )
  return it->second;
  }
  }
 
  return nullptr;
 }

References PNS::LINK_HOLDER::Links(), and m_rootLineHistory.

Referenced by runOptimizer().

◆ ForceClearance()

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

inline

Definition at line 74 of file pns_shove.h.

  {
  if( aEnabled )
  m_forceClearance = aClearance;
  else
  m_forceClearance = -1;
  }

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 134 of file pns_shove.cpp.

 {
  if( m_forceClearance >= 0 )
  return m_forceClearance;
 
  return m_currentNode->GetClearance( aA, aB );
 }

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

Referenced by onCollidingVia(), shoveLineFromLoneVia(), and ShoveObstacleLine().

◆ getHoleClearance()

int PNS::SHOVE::getHoleClearance	(	const ITEM *	aA,
		const ITEM *	aB
	)		const

private

Definition at line 143 of file pns_shove.cpp.

 {
  if( m_forceClearance >= 0 )
  return m_forceClearance;
 
  return m_currentNode->GetHoleClearance( aA, aB );
 }

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

Referenced by shoveLineFromLoneVia(), and ShoveObstacleLine().

◆ Logger()

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

inlineoverridevirtual

Reimplemented from PNS::ALGO_BASE.

Definition at line 61 of file pns_shove.h.

  {
  return &m_logger;
  }

References m_logger.

◆ NewHead()

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

Definition at line 1786 of file pns_shove.cpp.

 {
  assert( m_newHead );
 
  return *m_newHead;
 }

References m_newHead.

◆ onCollidingArc()

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

private

Definition at line 545 of file pns_shove.cpp.

 {
  int segIndex;
  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
  LINE shovedLine( obstacleLine );
  ARC tmp( *aObstacleArc );
 
  if( obstacleLine.HasLockedSegments() )
  return SH_TRY_WALK;
 
  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
 
  const double extensionWalkThreshold = 1.0;
 
  double obsLen = obstacleLine.CLine().Length();
  double shovedLen = shovedLine.CLine().Length();
  double extensionFactor = 0.0;
 
  if( obsLen != 0.0f )
  extensionFactor = shovedLen / obsLen - 1.0;
 
  if( extensionFactor > extensionWalkThreshold )
  return SH_TRY_WALK;
 
  assert( obstacleLine.LayersOverlap( &shovedLine ) );
 
  if ( Dbg() )
  {
  Dbg()->BeginGroup( wxString::Format( "on-colliding-arc-iter-%d", m_iter ).ToStdString() );
  Dbg()->AddLine( tmp.CLine(), WHITE, 10000, "obstacle-segment" );
  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
  Dbg()->AddLine( obstacleLine.CLine(), GREEN, 10000, "obstacle-line" );
  Dbg()->AddLine( shovedLine.CLine(), BLUE, 10000, "shoved-line" );
  Dbg()->EndGroup();
  }
 
  if( rv == SH_OK )
  {
  if( shovedLine.Marker() & MK_HEAD )
  {
  if( m_multiLineMode )
  return SH_INCOMPLETE;
 
  m_newHead = shovedLine;
  }
 
  int rank = aCurrent.Rank();
  shovedLine.SetRank( rank - 1 );
 
  sanityCheck( &obstacleLine, &shovedLine );
  replaceLine( obstacleLine, shovedLine );
 
  if( !pushLineStack( shovedLine ) )
  rv = SH_INCOMPLETE;
  }
 
  return rv;
 }

References PNS::DEBUG_DECORATOR::AddLine(), assembleLine(), PNS::DEBUG_DECORATOR::BeginGroup(), BLUE, PNS::ARC::CLine(), PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::DEBUG_DECORATOR::EndGroup(), Format(), GREEN, PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), m_iter, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, SH_TRY_WALK, ShoveObstacleLine(), and WHITE.

Referenced by shoveIteration().

◆ onCollidingLine()

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

private

Definition at line 608 of file pns_shove.cpp.

 {
  LINE shovedLine( aObstacle );
 
  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
 
  Dbg()->BeginGroup( "on-colliding-line" );
  Dbg()->AddLine( aObstacle.CLine(), RED, 100000, "obstacle-line" );
  Dbg()->AddLine( aCurrent.CLine(), GREEN, 150000, "current-line" );
  Dbg()->AddLine( shovedLine.CLine(), BLUE, 200000, "shoved-line" );
 
  if( rv == SH_OK )
  {
  if( shovedLine.Marker() & MK_HEAD )
  {
  if( m_multiLineMode )
  return SH_INCOMPLETE;
 
  m_newHead = shovedLine;
  }
 
  sanityCheck( &aObstacle, &shovedLine );
  replaceLine( aObstacle, shovedLine );
 
  int rank = aObstacle.Rank();
  shovedLine.SetRank( rank - 1 );
 
 
  if( !pushLineStack( shovedLine ) )
  {
  rv = SH_INCOMPLETE;
  }
  }
 
  return rv;
 }

References PNS::DEBUG_DECORATOR::AddLine(), PNS::DEBUG_DECORATOR::BeginGroup(), BLUE, PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), GREEN, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and ShoveObstacleLine().

Referenced by shoveIteration().

◆ onCollidingSegment()

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

private

Definition at line 475 of file pns_shove.cpp.

 {
  int segIndex;
  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
  LINE shovedLine( obstacleLine );
  SEGMENT tmp( *aObstacleSeg );
 
  if( obstacleLine.HasLockedSegments() )
  return SH_TRY_WALK;
 
  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
 
  const double extensionWalkThreshold = 1.0;
 
  double obsLen = obstacleLine.CLine().Length();
  double shovedLen = shovedLine.CLine().Length();
  double extensionFactor = 0.0;
 
  if( obsLen != 0.0f )
  extensionFactor = shovedLen / obsLen - 1.0;
 
  if( extensionFactor > extensionWalkThreshold )
  return SH_TRY_WALK;
 
  assert( obstacleLine.LayersOverlap( &shovedLine ) );
 
  if( Dbg() )
  {
  Dbg()->BeginGroup( wxString::Format( "on-colliding-segment-iter-%d",
  m_iter ).ToStdString() );
  Dbg()->AddSegment( tmp.Seg(), WHITE, "obstacle-segment" );
  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
  Dbg()->AddLine( obstacleLine.CLine(), GREEN, 10000, "obstacle-line" );
  Dbg()->AddLine( shovedLine.CLine(), BLUE, 10000, "shoved-line" );
 
  if( rv == SH_OK )
  Dbg()->Message( "Shove success" );
  else
  Dbg()->Message( "Shove FAIL" );
 
  Dbg()->EndGroup();
  }
 
  if( rv == SH_OK )
  {
  if( shovedLine.Marker() & MK_HEAD )
  {
  if( m_multiLineMode )
  return SH_INCOMPLETE;
 
  m_newHead = shovedLine;
  }
 
  int rank = aCurrent.Rank();
  shovedLine.SetRank( rank - 1 );
 
  sanityCheck( &obstacleLine, &shovedLine );
  replaceLine( obstacleLine, shovedLine );
 
  if( !pushLineStack( shovedLine ) )
  rv = SH_INCOMPLETE;
  }
 
  return rv;
 }

References PNS::DEBUG_DECORATOR::AddLine(), PNS::DEBUG_DECORATOR::AddSegment(), assembleLine(), PNS::DEBUG_DECORATOR::BeginGroup(), BLUE, PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::DEBUG_DECORATOR::EndGroup(), Format(), GREEN, PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), m_iter, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::DEBUG_DECORATOR::Message(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), sanityCheck(), PNS::SEGMENT::Seg(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, SH_TRY_WALK, ShoveObstacleLine(), and WHITE.

Referenced by shoveIteration().

◆ onCollidingSolid()

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

private

Definition at line 649 of file pns_shove.cpp.

 {
  WALKAROUND walkaround( m_currentNode, Router() );
  LINE walkaroundLine( aCurrent );
 
  if( aCurrent.EndsWithVia() )
  {
  VIA vh = aCurrent.Via();
  VIA* via = nullptr;
  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
 
  if( !jtStart )
  return SH_INCOMPLETE;
 
  for( ITEM* item : jtStart->LinkList() )
  {
  if( item->OfKind( ITEM::VIA_T ) )
  {
  via = (VIA*) item;
  break;
  }
  }
 
  if( via && via->Collide( aObstacle, m_currentNode ) )
  return onCollidingVia( aObstacle, via );
  }
 
  TOPOLOGY topo( m_currentNode );
 
  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
 
  walkaround.SetSolidsOnly( false );
  walkaround.RestrictToSet( true, cluster );
  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
 
  int currentRank = aCurrent.Rank();
   int nextRank;
 
  bool success = false;
 
  for( int attempt = 0; attempt < 2; attempt++ )
  {
  if( attempt == 1 || Settings().JumpOverObstacles() )
  {
 
  nextRank = currentRank - 1;
  walkaround.SetSingleDirection( true );
  }
  else
  {
  nextRank = currentRank + 10000;
  walkaround.SetSingleDirection( false );
  }
 
 
  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
 
  if( status != WALKAROUND::DONE )
  continue;
 
  walkaroundLine.ClearLinks();
  walkaroundLine.Unmark();
  walkaroundLine.Line().Simplify();
 
  if( walkaroundLine.HasLoops() )
  continue;
 
  if( aCurrent.Marker() & MK_HEAD )
  {
  walkaroundLine.Mark( MK_HEAD );
 
  if( m_multiLineMode )
  continue;
 
  m_newHead = walkaroundLine;
  }
 
  sanityCheck( &aCurrent, &walkaroundLine );
 
  if( !m_lineStack.empty() )
  {
  LINE lastLine = m_lineStack.front();
 
  if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
  {
  LINE dummy( lastLine );
 
  if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
  {
  success = true;
  break;
  }
  }
  else
  {
  success = true;
  break;
  }
  }
  }
 
  if(!success)
  return SH_INCOMPLETE;
 
  replaceLine( aCurrent, walkaroundLine );
  walkaroundLine.SetRank( nextRank );
 
  if( Dbg() )
  {
  Dbg()->BeginGroup( "on-colliding-solid" );
  Dbg()->AddLine( aCurrent.CLine(), RED, 10000, "current-line" );
  Dbg()->AddLine( walkaroundLine.CLine(), BLUE, 10000, "walk-line" );
  Dbg()->EndGroup();
  }
 
  popLineStack();
 
  if( !pushLineStack( walkaroundLine ) )
  return SH_INCOMPLETE;
 
  return SH_OK;
 }

References PNS::DEBUG_DECORATOR::AddLine(), PNS::TOPOLOGY::AssembleCluster(), PNS::DEBUG_DECORATOR::BeginGroup(), BLUE, PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::ITEM::Collide(), PNS::ALGO_BASE::Dbg(), PNS::WALKAROUND::DONE, dummy(), PNS::DEBUG_DECORATOR::EndGroup(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::HasLoops(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::JOINT::LinkList(), m_currentNode, m_lineStack, m_multiLineMode, m_newHead, PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, onCollidingVia(), popLineStack(), PNS::VIA::Pos(), pushLineStack(), PNS::LINE::Rank(), RED, 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, ShoveObstacleLine(), SHAPE_LINE_CHAIN::Simplify(), LAYER_RANGE::Start(), PNS::LINE::Unmark(), PNS::LINE::Via(), via, and PNS::ITEM::VIA_T.

Referenced by shoveIteration().

◆ onCollidingVia()

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

private

Definition at line 970 of file pns_shove.cpp.

 {
  int clearance = getClearance( aCurrent, aObstacleVia );
  VECTOR2I mtv;
  int rank = -1;
 
  bool lineCollision = false;
  bool viaCollision = false;
  VECTOR2I mtvLine, mtvVia;
 
  PNS_DBG( Dbg(), BeginGroup, "push-via-by-line" );
 
  if( aCurrent->OfKind( ITEM::LINE_T ) )
  {
  LINE* currentLine = (LINE*) aCurrent;
 
 #if 0
  m_logger.NewGroup( "push-via-by-line", m_iter );
  m_logger.Log( currentLine, 4, "current" );
 #endif
 
  lineCollision = aObstacleVia->Shape()->Collide( currentLine->Shape(),
  clearance + currentLine->Width() / 2,
  &mtvLine );
 
  // Check the via if present. Via takes priority.
  if( currentLine->EndsWithVia() )
  {
  const VIA& currentVia = currentLine->Via();
  int viaClearance = getClearance( &currentVia, aObstacleVia );
 
  viaCollision = aObstacleVia->Shape()->Collide( currentVia.Shape(), viaClearance,
  &mtvVia );
  }
  }
  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
  {
  // TODO: is this possible at all? We don't shove solids.
  return SH_INCOMPLETE;
  }
 
  // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
  if( viaCollision )
  mtv = mtvVia;
  else if ( lineCollision )
  mtv = -mtvLine;
  else
  mtv = VECTOR2I(0, 0);
 
  SHOVE::SHOVE_STATUS st = pushOrShoveVia( aObstacleVia, -mtv, rank );
 
  PNS_DBGN( Dbg(), EndGroup );
 
  return st;
 }

References SHAPE::Collide(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), getClearance(), PNS::ITEM::LINE_T, PNS::LOGGER::Log(), m_iter, m_logger, PNS::ITEM::OfKind(), PNS_DBG, PNS_DBGN, pushOrShoveVia(), SH_INCOMPLETE, PNS::VIA::Shape(), PNS::LINE::Shape(), PNS::ITEM::SOLID_T, 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 1030 of file pns_shove.cpp.

 {
  int n = 0;
  LINE cur( aCurrent );
  cur.ClearLinks();
 
  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
  LINE shoved( aCurrent );
  shoved.ClearLinks();
 
  cur.RemoveVia();
  unwindLineStack( &aCurrent );
 
  for( ITEM* item : jt->LinkList() )
  {
  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
  {
  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
  LINE head = assembleLine( li );
 
  head.AppendVia( *aObstacleVia );
 
  SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
 
  if( st != SH_OK )
  {
 #if 0
  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
  m_logger.Log( aObstacleVia, 0, "the-via" );
  m_logger.Log( &aCurrent, 1, "current-line" );
  m_logger.Log( &shoved, 3, "shoved-line" );
 #endif
 
  return st;
  }
 
  cur.SetShape( shoved.CLine() );
  n++;
  }
  }
 
  if( !n )
  {
 #if 0
  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
  m_logger.Log( aObstacleVia, 0, "the-via" );
  m_logger.Log( &aCurrent, 1, "current-line" );
 #endif
 
  LINE head( aCurrent );
  head.Line().Clear();
  head.AppendVia( *aObstacleVia );
  head.ClearLinks();
 
  SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
 
  if( st != SH_OK )
  return st;
 
  cur.SetShape( shoved.CLine() );
  }
 
  if( aCurrent.EndsWithVia() )
  shoved.AppendVia( aCurrent.Via() );
 
 #if 0
  m_logger.NewGroup( "on-reverse-via", m_iter );
  m_logger.Log( aObstacleVia, 0, "the-via" );
  m_logger.Log( &aCurrent, 1, "current-line" );
  m_logger.Log( &shoved, 3, "shoved-line" );
 #endif
  int currentRank = aCurrent.Rank();
  replaceLine( aCurrent, shoved );
 
  if( !pushLineStack( shoved ) )
  return SH_INCOMPLETE;
 
  shoved.SetRank( currentRank );
 
  return SH_OK;
 }

References PNS::LINE::AppendVia(), PNS::ITEM::ARC_T, assembleLine(), SHAPE_LINE_CHAIN::Clear(), PNS::LINK_HOLDER::ClearLinks(), 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::VIA::Pos(), pushLineStack(), PNS::LINE::Rank(), PNS::LINE::RemoveVia(), replaceLine(), PNS::ITEM::SEGMENT_T, PNS::LINE::SetRank(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, ShoveObstacleLine(), unwindLineStack(), and PNS::LINE::Via().

Referenced by shoveIteration().

◆ popLineStack()

void PNS::SHOVE::popLineStack ( )

private

Definition at line 1167 of file pns_shove.cpp.

 {
  LINE& l = m_lineStack.back();
 
  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
  {
  bool found = false;
 
  for( LINKED_ITEM* s : l.Links() )
  {
  if( i->ContainsLink( s ) )
  {
  i = m_optimizerQueue.erase( i );
  found = true;
  break;
  }
  }
 
  if( !found )
  i++;
  }
 
  m_lineStack.pop_back();
 }

References PNS::LINK_HOLDER::Links(), m_lineStack, and m_optimizerQueue.

Referenced by onCollidingSolid(), and shoveIteration().

◆ pushLineStack()

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

private

Definition at line 1147 of file pns_shove.cpp.

 {
  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
  return false;
 
  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
  {
  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
  }
  else
  {
  m_lineStack.push_back( aL );
  }
 
  m_optimizerQueue.push_back( aL );
 
  return true;
 }

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 847 of file pns_shove.cpp.

 {
  LINE_PAIR_VEC draggedLines;
  VECTOR2I p0( aVia->Pos() );
  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
  VECTOR2I p0_pushed( p0 + aForce );
 
  PNS_DBG( Dbg(), Message, wxString::Format( "via force [%d %d]\n", aForce.x, aForce.y ) );
 
  // nothing to do...
  if ( aForce.x == 0 && aForce.y == 0 )
  return SH_OK;
 
  if( !jt )
  {
  PNS_DBG( Dbg(), Message,
  wxString::Format( "weird, can't find the center-of-via joint\n" ) );
  return SH_INCOMPLETE;
  }
 
  if( aVia->IsLocked() )
  return SH_TRY_WALK;
 
  if( jt->IsLocked() )
  return SH_INCOMPLETE;
 
  // make sure pushed via does not overlap with any existing joint
  while( true )
  {
  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
 
  if( !jt_next )
  break;
 
  p0_pushed += aForce.Resize( 2 );
  }
 
  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
  pushedVia->SetPos( p0_pushed );
  pushedVia->Mark( aVia->Marker() );
 
  for( ITEM* item : jt->LinkList() )
  {
  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
  {
  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
  LINE_PAIR lp;
  int segIndex;
 
  lp.first = assembleLine( li, &segIndex );
 
  if( lp.first.HasLockedSegments() )
  return SH_TRY_WALK;
 
  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
 
  if( segIndex == 0 )
  lp.first.Reverse();
 
  lp.second = lp.first;
  lp.second.ClearLinks();
  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
  lp.second.AppendVia( *pushedVia );
  draggedLines.push_back( lp );
  }
  }
 
  pushedVia->SetRank( aCurrentRank - 1 );
 
  if( aVia->Marker() & MK_HEAD ) // push
  {
  m_draggedVia = pushedVia.get();
  }
  else
  { // shove
  if( jt->IsStitchingVia() )
  pushLineStack( LINE( *pushedVia ) );
  }
 
  PNS_DBG( Dbg(), AddPoint, aVia->Pos(), LIGHTGREEN, 100000, "via-pre" );
  PNS_DBG( Dbg(), AddPoint, pushedVia->Pos(), LIGHTRED, 100000, "via-post" );
 
  replaceItems( aVia, std::move( pushedVia ) );
 
  for( LINE_PAIR lp : draggedLines )
  {
  if( lp.first.Marker() & MK_HEAD )
  {
  lp.second.Mark( MK_HEAD );
 
  if( m_multiLineMode )
  return SH_INCOMPLETE;
 
  m_newHead = lp.second;
  }
 
  unwindLineStack( &lp.first );
 
  if( lp.second.SegmentCount() )
  {
  replaceLine( lp.first, lp.second );
  lp.second.SetRank( aCurrentRank - 1 );
 
  if( !pushLineStack( lp.second, true ) )
  return SH_INCOMPLETE;
  }
  else
  {
  m_currentNode->Remove( lp.first );
  }
 
  PNS_DBG( Dbg(), AddLine, lp.first.CLine(), LIGHTGREEN, 10000, "fan-pre" );
  PNS_DBG( Dbg(), AddLine, lp.second.CLine(), LIGHTRED, 10000, "fan-post" );
  }
 
  return SH_OK;
 }

References PNS::ITEM::ARC_T, assembleLine(), PNS::Clone(), PNS::ALGO_BASE::Dbg(), PNS::NODE::FindJoint(), Format(), PNS::ITEM::IsLocked(), LIGHTGREEN, LIGHTRED, m_currentNode, m_draggedVia, m_multiLineMode, m_newHead, PNS::ITEM::Marker(), PNS::MK_HEAD, PNS_DBG, 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 807 of file pns_shove.cpp.

 {
  SPRINGBACK_TAG st;
  OPT_BOX2I prev_area;
 
  if( !m_nodeStack.empty() )
  prev_area = m_nodeStack.back().m_affectedArea;
 
  if( aDraggedVia )
  {
  st.m_draggedVia = aDraggedVia->MakeHandle();
  }
 
  st.m_node = aNode;
 
  if( aAffectedArea )
  {
  if( prev_area )
  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
  else
  st.m_affectedArea = aAffectedArea;
  }
  else
  {
  st.m_affectedArea = prev_area;
  }
 
  st.m_seq = ( m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1 );
  st.m_locked = false;
 
  m_nodeStack.push_back( st );
 
  return true;
 }

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 777 of file pns_shove.cpp.

 {
  while( !m_nodeStack.empty() )
  {
  SPRINGBACK_TAG& spTag = m_nodeStack.back();
 
  OPT<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
 
  if( !obs && !spTag.m_locked )
  {
  aDraggedVia = spTag.m_draggedVia;
  aDraggedVia.valid = true;
 
  delete spTag.m_node;
  m_nodeStack.pop_back();
  }
  else
  {
  break;
  }
  }
 
  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
 }

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 51 of file pns_shove.cpp.

 {
  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
 
  if( changed_area )
  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
 
  m_currentNode->Replace( aOld, std::move( aNew ) );
 }

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

Referenced by pushOrShoveVia().

◆ replaceLine()

void PNS::SHOVE::replaceLine	(	LINE &	aOld,
		LINE &	aNew,
		bool	aIncludeInChangedArea = `true`,
		NODE *	aNode = `nullptr`
	)

private

Definition at line 62 of file pns_shove.cpp.

 {
  if( aIncludeInChangedArea )
  {
  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
 
  if( changed_area )
  {
  if( Dbg() )
  {
  Dbg()->AddBox( *changed_area, BLUE, "shove-changed-area" );
  }
 
  m_affectedArea =
  m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
  }
  }
 
  bool foundPredecessor = false;
  LINE* rootLine = nullptr;
 
  // Keep track of the 'root lines', i.e. the unmodified (pre-shove) versions
  // of the affected tracks in a map. The optimizer can then query the pre-shove shape
  // for each shoved line and perform additional constraint checks (i.e. prevent overzealous
  // optimizations)
 
  // Check if the shoved line already has an ancestor (e.g. line from a previous shove
  // iteration/cursor movement)
  for( auto link : aOld.Links() )
  {
  auto oldLineIter = m_rootLineHistory.find( link );
 
  if( oldLineIter != m_rootLineHistory.end() )
  {
  rootLine = oldLineIter->second;
  foundPredecessor = true;
  break;
  }
  }
 
  // If found, use it, otherwise, create new entry in the map (we have a genuine new 'root' line)
  if( !foundPredecessor )
  {
  for( auto link : aOld.Links() )
  {
  if( ! rootLine )
  {
  rootLine = aOld.Clone();
  }
 
  m_rootLineHistory[link] = rootLine;
  }
  }
 
  // Now update the NODE (calling Replace invalidates the Links() in a LINE)
  if( aNode )
  {
  aNode->Replace( aOld, aNew );
  }
  else
  {
  m_currentNode->Replace( aOld, aNew );
  }
 
  // point the Links() of the new line to its oldest ancestor
  for( auto link : aNew.Links() )
  {
  m_rootLineHistory[ link ] = rootLine;
  }
 }

References PNS::DEBUG_DECORATOR::AddBox(), BLUE, PNS::ChangedArea(), PNS::LINE::Clone(), PNS::ALGO_BASE::Dbg(), PNS::LINK_HOLDER::Links(), m_affectedArea, m_currentNode, m_rootLineHistory, and PNS::NODE::Replace().

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

◆ RewindSpringbackTo()

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

Definition at line 1812 of file pns_shove.cpp.

 {
  bool found = false;
 
  auto iter = m_nodeStack.begin();
 
  while( iter != m_nodeStack.end() )
  {
  if ( iter->m_node == aNode )
  {
  found = true;
  break;
  }
 
  iter++;
  }
 
  if( !found )
  return false;
 
  auto start = iter;
 
  aNode->KillChildren();
  m_nodeStack.erase( start, m_nodeStack.end() );
 
  return true;
 }

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

◆ Router()

ROUTER* PNS::ALGO_BASE::Router ( ) const

inlineinherited

◆ runOptimizer()

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

private

Definition at line 1696 of file pns_shove.cpp.

 {
  OPTIMIZER optimizer( aNode );
  int optFlags = 0;
  int n_passes = 0;
 
  PNS_OPTIMIZATION_EFFORT effort = Settings().OptimizerEffort();
 
  OPT_BOX2I area = totalAffectedArea();
 
  int maxWidth = 0;
 
  for( LINE& line : m_optimizerQueue )
  maxWidth = std::max( line.Width(), maxWidth );
 
  if( area )
  {
  area->Inflate( maxWidth );
  area = area->Intersect( VisibleViewArea() );
  }
 
  switch( effort )
  {
  case OE_LOW:
  optFlags |= OPTIMIZER::MERGE_OBTUSE;
  n_passes = 1;
  break;
 
  case OE_MEDIUM:
  optFlags |= OPTIMIZER::MERGE_SEGMENTS;
 
  n_passes = 2;
  break;
 
  case OE_FULL:
  optFlags = OPTIMIZER::MERGE_SEGMENTS;
  n_passes = 2;
  break;
 
  default:
  break;
  }
 
  optFlags |= OPTIMIZER::LIMIT_CORNER_COUNT;
 
  if( area )
  {
  if( Dbg() )
  {
  Dbg()->AddBox( *area, BLUE, "opt-area" );
  }
 
  optFlags |= OPTIMIZER::RESTRICT_AREA;
  optimizer.SetRestrictArea( *area, false );
  }
 
  if( Settings().SmartPads() )
  optFlags |= OPTIMIZER::SMART_PADS;
 
  optimizer.SetEffortLevel( optFlags );
  optimizer.SetCollisionMask( ITEM::ANY_T );
 
  for( int pass = 0; pass < n_passes; pass++ )
  {
  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
 
  for( LINE& line : m_optimizerQueue)
  {
  if( !( line.Marker() & MK_HEAD ) )
  {
  LINE optimized;
  LINE* root = findRootLine( &line );
 
  if( optimizer.Optimize( &line, &optimized, root ) )
  {
  replaceLine( line, optimized, false, aNode );
  line = optimized; // keep links in the lines in the queue up to date
  }
  }
  }
  }
 }

References PNS::DEBUG_DECORATOR::AddBox(), PNS::ITEM::ANY_T, BLUE, PNS::ALGO_BASE::Dbg(), findRootLine(), PNS::OPTIMIZER::LIMIT_CORNER_COUNT, 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(), replaceLine(), PNS::OPTIMIZER::RESTRICT_AREA, PNS::OPTIMIZER::SetCollisionMask(), PNS::OPTIMIZER::SetEffortLevel(), PNS::OPTIMIZER::SetRestrictArea(), PNS::ALGO_BASE::Settings(), PNS::OPTIMIZER::SMART_PADS, totalAffectedArea(), and PNS::ALGO_BASE::VisibleViewArea().

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

◆ sanityCheck()

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

private

Definition at line 152 of file pns_shove.cpp.

 {
  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
 }

References PNS::LINE::CPoint().

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

◆ SetDebugDecorator()

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

inlineinherited

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

Definition at line 73 of file pns_algo_base.h.

  {
  m_debugDecorator = aDecorator;
  }

References PNS::ALGO_BASE::m_debugDecorator.

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

◆ SetInitialLine()

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

Definition at line 1794 of file pns_shove.cpp.

 {
  m_root = m_root->Branch();
  m_root->Remove( aInitial );
 }

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

◆ SetLogger()

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

inlineinherited

Definition at line 65 of file pns_algo_base.h.

  {
  m_logger = aLogger;
  }

References PNS::ALGO_BASE::m_logger.

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

◆ Settings()

ROUTING_SETTINGS & PNS::ALGO_BASE::Settings ( ) const

inherited

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

Definition at line 28 of file pns_algo_base.cpp.

 {
  return m_router->Settings();
 }

References PNS::ALGO_BASE::m_router, and PNS::ROUTER::Settings().

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), PNS::LINE_PLACER::buildInitialLine(), PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragShove(), PNS::DRAGGER::dragWalkaround(), PNS::COMPONENT_DRAGGER::FixRoute(), PNS::DRAGGER::FixRoute(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::LINE_PLACER::Move(), onCollidingSolid(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), PNS::DIFF_PAIR_PLACER::propagateDpHeadForces(), PNS::LINE_PLACER::rhMarkObstacles(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), PNS::DIFF_PAIR_PLACER::route(), PNS::LINE_PLACER::routeHead(), PNS::LINE_PLACER::routeStep(), runOptimizer(), shoveMainLoop(), PNS::DRAGGER::Start(), PNS::LINE_PLACER::Start(), PNS::DRAGGER::tryWalkaround(), and PNS::LINE_PLACER::UnfixRoute().

◆ ShoveDraggingVia()

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

Definition at line 1611 of file pns_shove.cpp.

 {
  SHOVE_STATUS st = SH_OK;
 
  m_lineStack.clear();
  m_optimizerQueue.clear();
  m_newHead = OPT_LINE();
  m_draggedVia = nullptr;
 
  VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
 
  if( !viaToDrag )
  return SH_INCOMPLETE;
 
  // Pop NODEs containing previous shoves which are no longer necessary
  ITEM_SET headSet;
 
  VIA headVia ( *viaToDrag );
  headVia.SetPos( aWhere );
  headSet.Add( headVia );
  VIA_HANDLE prevViaHandle;
  NODE* parent = reduceSpringback( headSet, prevViaHandle );
 
  if( prevViaHandle.valid )
  {
  aNewVia = prevViaHandle;
  viaToDrag = findViaByHandle( parent, prevViaHandle );
  }
 
  // Create a new NODE to store this version of the world
  m_currentNode = parent->Branch();
  m_currentNode->ClearRanks();
 
  viaToDrag->Mark( MK_HEAD );
  viaToDrag->SetRank( 100000 );
 
  // Push the via to its new location
  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
 
  // Shove any colliding objects out of the way
  if( st == SH_OK )
  st = shoveMainLoop();
 
  if( st == SH_OK )
  runOptimizer( m_currentNode );
 
  if( st == SH_OK || st == SH_HEAD_MODIFIED )
  {
  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
 
  if (!m_draggedVia)
  m_draggedVia = viaToDrag;
 
  aNewVia = m_draggedVia->MakeHandle();
 
  pushSpringback( m_currentNode, m_affectedArea, viaToDrag );
  }
  else
  {
  delete m_currentNode;
  m_currentNode = parent;
  }
 
  return st;
 }

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::ITEM::Mark(), PNS::MK_HEAD, PNS::VIA::Pos(), pushOrShoveVia(), pushSpringback(), reduceSpringback(), runOptimizer(), PNS::VIA::SetPos(), PNS::ITEM::SetRank(), 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 1196 of file pns_shove.cpp.

 {
  LINE currentLine = m_lineStack.back();
  NODE::OPT_OBSTACLE nearest;
  SHOVE_STATUS st = SH_NULL;
 
 #ifdef DEBUG
  Dbg()->SetIteration( aIter );
 #endif
 
  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
  {
  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
 
  if( nearest )
  PNS_DBG( Dbg(), Message,
  wxString::Format( "nearest %p %s", nearest->m_item,
  nearest->m_item->KindStr() ) );
 
  if( nearest )
  break;
  }
 
  if( !nearest )
  {
  m_lineStack.pop_back();
  PNS_DBG( Dbg(), Message, "no-nearest-item ");
  return SH_OK;
  }
 
  ITEM* ni = nearest->m_item;
 
  unwindLineStack( ni );
 
  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
  {
  // Collision with a higher-ranking object (ie: one that we've already shoved)
  //
  switch( ni->Kind() )
  {
  case ITEM::VIA_T:
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-via", aIter ) );
 
  if( currentLine.EndsWithVia() )
  {
  st = SH_INCOMPLETE;
  }
  else
  {
   st = onReverseCollidingVia( currentLine, (VIA*) ni );
  }
 
  break;
  }
 
  case ITEM::SEGMENT_T:
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-segment ",
  aIter ) );
  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
 
  popLineStack();
  st = onCollidingLine( revLine, currentLine );
 
  if( !pushLineStack( revLine ) )
  return SH_INCOMPLETE;
 
  break;
  }
 
  case ITEM::ARC_T:
  {
  //TODO(snh): Handle Arc shove separate from track
  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: reverse-collide-arc ", aIter ) );
  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
 
  popLineStack();
  st = onCollidingLine( revLine, currentLine );
 
  if( !pushLineStack( revLine ) )
  return SH_INCOMPLETE;
 
  break;
  }
 
  default:
  assert( false );
  }
  }
  else
  {
  // Collision with a lower-ranking object or a solid
  //
  switch( ni->Kind() )
  {
  case ITEM::SEGMENT_T:
  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: collide-segment ", aIter ) );
 
  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
 
  if( st == SH_TRY_WALK )
  st = onCollidingSolid( currentLine, ni );
 
  break;
 
  //TODO(snh): Customize Arc collide
  case ITEM::ARC_T:
  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: collide-arc ", aIter ) );
 
  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
 
  if( st == SH_TRY_WALK )
  st = onCollidingSolid( currentLine, ni );
 
  break;
 
  case ITEM::VIA_T:
  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: shove-via ", aIter ) );
  st = onCollidingVia( &currentLine, (VIA*) ni );
 
  if( st == SH_TRY_WALK )
  st = onCollidingSolid( currentLine, ni );
 
  break;
 
  case ITEM::SOLID_T:
  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: walk-solid ", aIter ) );
  st = onCollidingSolid( currentLine, (SOLID*) ni );
  break;
 
  default:
  break;
  }
  }
 
  return st;
 }

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

Referenced by shoveMainLoop().

◆ shoveLineFromLoneVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveLineFromLoneVia	(	const LINE &	aCurLine,
		const LINE &	aObstacleLine,
		LINE &	aResultLine
	)

private

Definition at line 226 of file pns_shove.cpp.

 {
  // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
 
  int obstacleLineWidth = aObstacleLine.Width();
  int clearance = getClearance( &aCurLine, &aObstacleLine );
  int holeClearance = getHoleClearance( &aCurLine.Via(), &aObstacleLine );
 
  if( holeClearance + aCurLine.Via().Drill() / 2 > clearance + aCurLine.Via().Diameter() / 2 )
  clearance = holeClearance + aCurLine.Via().Drill() / 2 - aCurLine.Via().Diameter() / 2;
 
  SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
  SHAPE_LINE_CHAIN path_cw;
  SHAPE_LINE_CHAIN path_ccw;
 
  if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
  return SH_INCOMPLETE;
 
  if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
  return SH_INCOMPLETE;
 
  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
 
  if( shortest.PointCount() < 2 )
  return SH_INCOMPLETE;
 
  if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
  return SH_INCOMPLETE;
 
  if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
  return SH_INCOMPLETE;
 
  aResultLine.SetShape( shortest );
 
  if( aResultLine.Collide( &aCurLine, m_currentNode ) )
  return SH_INCOMPLETE;
 
  return SH_OK;
 }

References PNS::ITEM::Collide(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::VIA::Diameter(), PNS::VIA::Drill(), getClearance(), getHoleClearance(), PNS::VIA::Hull(), PNS::ITEM::Layer(), 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 ShoveObstacleLine().

◆ ShoveLines()

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

Definition at line 1402 of file pns_shove.cpp.

 {
  SHOVE_STATUS st = SH_OK;
 
  m_multiLineMode = false;
 
  PNS_DBG( Dbg(), Message,
  wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) )
 
  // empty head? nothing to shove...
  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
  return SH_INCOMPLETE;
 
  LINE head( aCurrentHead );
  head.ClearLinks();
 
  m_lineStack.clear();
  m_optimizerQueue.clear();
  m_newHead = OPT_LINE();
 
 #if 0
  m_logger.Clear();
 #endif
 
  // Pop NODEs containing previous shoves which are no longer necessary
  //
  ITEM_SET headSet;
  headSet.Add( aCurrentHead );
 
  VIA_HANDLE dummyVia;
 
  NODE* parent = reduceSpringback( headSet, dummyVia );
 
  // Create a new NODE to store this version of the world
  m_currentNode = parent->Branch();
  m_currentNode->ClearRanks();
  m_currentNode->Add( head );
 
  m_currentNode->LockJoint( head.CPoint(0), &head, true );
 
  if( !head.EndsWithVia() )
  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
 
  head.Mark( MK_HEAD );
  head.SetRank( 100000 );
 
  PNS_DBG( Dbg(), AddLine, head.CLine(), CYAN, head.Width(), "head, after shove" );
 
  if( head.EndsWithVia() )
  {
  std::unique_ptr< VIA >headVia = Clone( head.Via() );
  headVia->Mark( MK_HEAD );
  headVia->SetRank( 100000 );
  m_currentNode->Add( std::move( headVia ) );
  }
 
  if( !pushLineStack( head ) )
  {
  delete m_currentNode;
  m_currentNode = parent;
 
  return SH_INCOMPLETE;
  }
 
  st = shoveMainLoop();
 
  if( st == SH_OK )
  {
  runOptimizer( m_currentNode );
 
  if( m_newHead )
  st = m_currentNode->CheckColliding( &( *m_newHead ) ) ? SH_INCOMPLETE : SH_HEAD_MODIFIED;
  else
  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
  }
 
  m_currentNode->RemoveByMarker( MK_HEAD );
 
  PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter ) );
 
  if( st == SH_OK || st == SH_HEAD_MODIFIED )
  {
  pushSpringback( m_currentNode, m_affectedArea, nullptr );
  }
  else
  {
  delete m_currentNode;
 
  m_currentNode = parent;
  m_newHead = OPT_LINE();
  }
 
  if(m_newHead)
  m_newHead->Unmark();
 
  if( m_newHead && head.EndsWithVia() )
  {
  VIA v = head.Via();
  v.SetPos( m_newHead->CPoint( -1 ) );
  m_newHead->AppendVia(v);
  }
 
  return st;
 }

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::LOGGER::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::NODE::ClearRanks(), PNS::LINE::CLine(), PNS::Clone(), PNS::LINE::CPoint(), CYAN, PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), Format(), PNS::NODE::LockJoint(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, m_optimizerQueue, PNS::LINE::Mark(), PNS::MK_HEAD, PNS_DBG, pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::VIA::SetPos(), PNS::LINE::SetRank(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), PNS::LINE::Via(), and PNS::LINE::Width().

◆ shoveLineToHullSet()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveLineToHullSet	(	const LINE &	aCurLine,
		const LINE &	aObstacleLine,
		LINE &	aResultLine,
		const HULL_SET &	aHulls
	)

private

Definition at line 271 of file pns_shove.cpp.

 {
  const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();
 
  int attempt;
 
  for( attempt = 0; attempt < 4; attempt++ )
  {
  bool invertTraversal = ( attempt >= 2 );
  bool clockwise = attempt % 2;
  int vFirst = -1, vLast = -1;
 
  LINE l( aObstacleLine );
  SHAPE_LINE_CHAIN path( l.CLine() );
 
  for( int i = 0; i < (int) aHulls.size(); i++ )
  {
  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
 
  PNS_DBG( Dbg(), AddLine, hull, YELLOW, 10000, "hull" );
  PNS_DBG( Dbg(), AddLine, path, WHITE, l.Width(), "path" );
  PNS_DBG( Dbg(), AddLine, obs, LIGHTGRAY, aObstacleLine.Width(), "obs" );
 
  if( !l.Walkaround( hull, path, clockwise ) )
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "Fail-Walk %s %s %d\n",
  hull.Format().c_str(),
  l.CLine().Format().c_str(),
  clockwise? 1 : 0) );
  return SH_INCOMPLETE;
  }
 
  path.Simplify();
  l.SetShape( path );
  }
 
  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
  {
  if( path.CPoint( i ) != obs.CPoint( i ) )
  {
  vFirst = i;
  break;
  }
  }
 
  int k = obs.PointCount() - 1;
 
  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
  {
  if( path.CPoint( i ) != obs.CPoint( k ) )
  {
  vLast = i;
  break;
  }
  }
 
  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail vfirst-last", attempt ) );
  continue;
  }
 
  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail vend-start\n", attempt ) );
  continue;
  }
 
  if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail direction-check",
  attempt ) );
  aResultLine.SetShape( l.CLine() );
  continue;
  }
 
  if( path.SelfIntersecting() )
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail self-intersect",
  attempt ) );
  continue;
  }
 
  bool colliding = l.Collide( &aCurLine, m_currentNode );
 
 #ifdef DEBUG
  char str[128];
  sprintf( str, "att-%d-shoved", attempt );
  Dbg()->AddLine( l.CLine(), BLUE, 20000, str );
 #endif
 
  if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
  {
  JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
 
  for( ITEM* item : jtStart->LinkList() )
  {
  if( item->Collide( &l, m_currentNode ) )
  colliding = true;
  }
  }
 
  if( colliding )
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "attempt %d fail coll-check", attempt ) );
  continue;
  }
 
  aResultLine.SetShape( l.CLine() );
 
  return SH_OK;
  }
 
  return SH_INCOMPLETE;
 }

References PNS::DEBUG_DECORATOR::AddLine(), BLUE, checkShoveDirection(), PNS::LINE::CLine(), PNS::ITEM::Collide(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::ALGO_BASE::Dbg(), PNS::NODE::FindJoint(), Format(), SHAPE_LINE_CHAIN::Format(), LIGHTGRAY, PNS::JOINT::LinkList(), m_currentNode, PNS::LINE::Marker(), PNS::MK_HEAD, path, PNS_DBG, SHAPE_LINE_CHAIN::PointCount(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, PNS::LINE::Walkaround(), WHITE, PNS::LINE::Width(), and YELLOW.

Referenced by ShoveObstacleLine().

◆ shoveMainLoop()

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

private

Definition at line 1342 of file pns_shove.cpp.

 {
  SHOVE_STATUS st = SH_OK;
 
  m_affectedArea = OPT_BOX2I();
 
  PNS_DBG( Dbg(), Message, wxString::Format( "ShoveStart [root: %d jts, current: %d jts]",
  m_root->JointCount(),
  m_currentNode->JointCount() ) );
 
  int iterLimit = Settings().ShoveIterationLimit();
  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
 
  m_iter = 0;
 
  timeLimit.Restart();
 
  if( m_lineStack.empty() && m_draggedVia )
  {
  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
  // the stack.
  pushLineStack( LINE( *m_draggedVia ) );
  }
 
  while( !m_lineStack.empty() )
  {
  PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: node %p stack %d ", m_iter,
  m_currentNode, (int) m_lineStack.size() ) );
 
  st = shoveIteration( m_iter );
 
  m_iter++;
 
  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
  {
  st = SH_INCOMPLETE;
  break;
  }
  }
 
  return st;
 }

References PNS::ALGO_BASE::Dbg(), PNS::TIME_LIMIT::Expired(), Format(), PNS::NODE::JointCount(), m_affectedArea, m_currentNode, m_draggedVia, m_iter, m_lineStack, m_root, PNS_DBG, 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 1509 of file pns_shove.cpp.

 {
  SHOVE_STATUS st = SH_OK;
 
  m_multiLineMode = true;
 
  ITEM_SET headSet;
 
  for( const ITEM* item : aHeadSet.CItems() )
  {
  const LINE* headOrig = static_cast<const LINE*>( item );
 
  // empty head? nothing to shove...
  if( !headOrig->SegmentCount() )
  return SH_INCOMPLETE;
 
  headSet.Add( *headOrig );
  }
 
  m_lineStack.clear();
  m_optimizerQueue.clear();
 
 #if 0
  m_logger.Clear();
 #endif
 
  VIA_HANDLE dummyVia;
 
  NODE* parent = reduceSpringback( headSet, dummyVia );
 
  m_currentNode = parent->Branch();
  m_currentNode->ClearRanks();
  int n = 0;
 
  for( const ITEM* item : aHeadSet.CItems() )
  {
  const LINE* headOrig = static_cast<const LINE*>( item );
  LINE head( *headOrig );
  head.ClearLinks();
 
  m_currentNode->Add( head );
 
  head.Mark( MK_HEAD );
  head.SetRank( 100000 );
  n++;
 
  if( !pushLineStack( head ) )
  return SH_INCOMPLETE;
 
  if( head.EndsWithVia() )
  {
  std::unique_ptr< VIA > headVia = Clone( head.Via() );
  headVia->Mark( MK_HEAD );
  headVia->SetRank( 100000 );
  m_currentNode->Add( std::move( headVia ) );
  }
  }
 
  st = shoveMainLoop();
 
  if( st == SH_OK )
  runOptimizer( m_currentNode );
 
  m_currentNode->RemoveByMarker( MK_HEAD );
 
  PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
  ( st == SH_OK ? "OK" : "FAILURE"), m_iter ) );
 
  if( st == SH_OK )
  {
  pushSpringback( m_currentNode, m_affectedArea, nullptr );
  }
  else
  {
  delete m_currentNode;
  m_currentNode = parent;
  }
 
  return st;
 }

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

◆ ShoveObstacleLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveObstacleLine	(	const LINE &	aCurLine,
		const LINE &	aObstacleLine,
		LINE &	aResultLine
	)

Definition at line 393 of file pns_shove.cpp.

 {
  aResultLine.ClearLinks();
 
  bool obstacleIsHead = false;
 
  for( LINKED_ITEM* s : aObstacleLine.Links() )
  {
  if( s->Marker() & MK_HEAD )
  {
  obstacleIsHead = true;
  break;
  }
  }
 
  SHOVE_STATUS rv;
  bool viaOnEnd = aCurLine.EndsWithVia();
 
  if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
  {
  // Shove aObstacleLine to the hull of aCurLine's via.
 
  rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
  }
  else
  {
  // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
  // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
  // hull it will be at the appropriate clearance.
 
  int obstacleLineWidth = aObstacleLine.Width();
  int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
  int currentLineSegmentCount = aCurLine.SegmentCount();
  HULL_SET hulls;
 
  hulls.reserve( currentLineSegmentCount + 1 );
 
 #ifdef DEBUG
  Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d",
  aCurLine.Net(), aObstacleLine.Net(), clearance ) );
 #endif
 
  for( int i = 0; i < currentLineSegmentCount; i++ )
  {
  SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, obstacleLineWidth, aObstacleLine.Layer() );
 
  hulls.push_back( hull );
  }
 
  if( viaOnEnd )
  {
  const VIA& via = aCurLine.Via();
  int viaClearance = getClearance( &via, &aObstacleLine );
  int holeClearance = getHoleClearance( &via, &aObstacleLine );
 
  if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
  viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
 
  hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
  }
 
 #ifdef DEBUG
  char str[128];
  sprintf( str, "current-cl-%d", clearance );
  Dbg()->AddLine( aCurLine.CLine(), BLUE, 20000, str );
 #endif
 
  rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
  }
 
  if( obstacleIsHead )
  aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
 
  return rv;
 }

References PNS::DEBUG_DECORATOR::AddLine(), BLUE, PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::LINE::CSegment(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), Format(), getClearance(), getHoleClearance(), PNS::VIA::Hull(), PNS::ITEM::Layer(), PNS::ITEM::LayersOverlap(), PNS::LINK_HOLDER::Links(), PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::DEBUG_DECORATOR::Message(), PNS::MK_HEAD, PNS::ITEM::Net(), PNS::LINE::SegmentCount(), shoveLineFromLoneVia(), shoveLineToHullSet(), PNS::LINE::Via(), via, and PNS::LINE::Width().

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

◆ totalAffectedArea()

OPT_BOX2I PNS::SHOVE::totalAffectedArea ( ) const

private

Definition at line 1386 of file pns_shove.cpp.

 {
  OPT_BOX2I area;
 
  if( !m_nodeStack.empty() )
  area = m_nodeStack.back().m_affectedArea;
 
  if( area && m_affectedArea)
  area->Merge( *m_affectedArea );
  else if( !area )
  area = m_affectedArea;
 
  return area;
 }

References m_affectedArea, and m_nodeStack.

Referenced by runOptimizer().

◆ UnlockSpringbackNode()

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

Definition at line 1841 of file pns_shove.cpp.

 {
  auto iter = m_nodeStack.begin();
 
  while( iter != m_nodeStack.end() )
  {
  if ( iter->m_node == aNode )
  {
  iter->m_locked = false;
  break;
  }
 
  iter++;
  }
 }

References m_nodeStack.

◆ unwindLineStack() [1/2]

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

private

Definition at line 1113 of file pns_shove.cpp.

 {
  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
  {
  if( i->ContainsLink( aSeg ) )
  i = m_lineStack.erase( i );
  else
  i++;
  }
 
  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
  {
  if( i->ContainsLink( aSeg ) )
  i = m_optimizerQueue.erase( i );
  else
  i++;
  }
 }

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 1133 of file pns_shove.cpp.

 {
  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
  else if( aItem->OfKind( ITEM::LINE_T ) )
  {
  LINE* l = static_cast<LINE*>( aItem );
 
  for( LINKED_ITEM* seg : l->Links() )
  unwindLineStack( seg );
  }
 }

References PNS::ITEM::ARC_T, PNS::ITEM::LINE_T, PNS::LINK_HOLDER::Links(), PNS::ITEM::OfKind(), PNS::ITEM::SEGMENT_T, and unwindLineStack().

◆ VisibleViewArea()

const BOX2I & PNS::ALGO_BASE::VisibleViewArea ( ) const

inherited

Definition at line 40 of file pns_algo_base.cpp.

 {
  return m_router->VisibleViewArea();
 }

References PNS::ALGO_BASE::m_router, and PNS::ROUTER::VisibleViewArea().

Referenced by PNS::DRAGGER::optimizeAndUpdateDraggedLine(), and runOptimizer().

Member Data Documentation

◆ m_affectedArea

OPT_BOX2I PNS::SHOVE::m_affectedArea

private

Definition at line 155 of file pns_shove.h.

Referenced by replaceItems(), replaceLine(), ShoveDraggingVia(), ShoveLines(), shoveMainLoop(), ShoveMultiLines(), and totalAffectedArea().

◆ m_currentNode

NODE* PNS::SHOVE::m_currentNode

private

Definition at line 171 of file pns_shove.h.

Referenced by assembleLine(), getClearance(), getHoleClearance(), onCollidingSolid(), onReverseCollidingVia(), pushOrShoveVia(), replaceItems(), replaceLine(), SHOVE(), ShoveDraggingVia(), shoveIteration(), shoveLineFromLoneVia(), ShoveLines(), shoveLineToHullSet(), shoveMainLoop(), and ShoveMultiLines().

◆ m_debugDecorator

DEBUG_DECORATOR* PNS::ALGO_BASE::m_debugDecorator

protectedinherited

Definition at line 86 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 177 of file pns_shove.h.

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

◆ m_forceClearance

int PNS::SHOVE::m_forceClearance

private

Definition at line 180 of file pns_shove.h.

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

◆ m_iter

int PNS::SHOVE::m_iter

private

Definition at line 179 of file pns_shove.h.

Referenced by onCollidingArc(), onCollidingSegment(), onCollidingVia(), onReverseCollidingVia(), SHOVE(), ShoveLines(), shoveMainLoop(), and ShoveMultiLines().

◆ m_lineStack

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

private

Definition at line 166 of file pns_shove.h.

Referenced by onCollidingSolid(), popLineStack(), pushLineStack(), ShoveDraggingVia(), shoveIteration(), ShoveLines(), shoveMainLoop(), ShoveMultiLines(), and unwindLineStack().

◆ m_logger

LOGGER PNS::SHOVE::m_logger

private

Definition at line 176 of file pns_shove.h.

Referenced by Logger(), onCollidingVia(), onReverseCollidingVia(), ShoveLines(), and ShoveMultiLines().

◆ m_multiLineMode

bool PNS::SHOVE::m_multiLineMode

private

Definition at line 181 of file pns_shove.h.

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), pushOrShoveVia(), SHOVE(), ShoveLines(), and ShoveMultiLines().

◆ m_newHead

OPT_LINE PNS::SHOVE::m_newHead

private

Definition at line 174 of file pns_shove.h.

Referenced by NewHead(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), pushOrShoveVia(), ShoveDraggingVia(), and ShoveLines().

◆ m_nodeStack

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

private

Definition at line 165 of file pns_shove.h.

Referenced by AddLockedSpringbackNode(), CurrentNode(), pushSpringback(), reduceSpringback(), RewindSpringbackTo(), totalAffectedArea(), and UnlockSpringbackNode().

◆ m_optimizerQueue

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

private

Definition at line 167 of file pns_shove.h.

Referenced by popLineStack(), pushLineStack(), runOptimizer(), ShoveDraggingVia(), ShoveLines(), ShoveMultiLines(), and unwindLineStack().

◆ m_restrictSpringbackTagId

int PNS::SHOVE::m_restrictSpringbackTagId

private

Definition at line 172 of file pns_shove.h.

Referenced by SHOVE().

◆ m_root

NODE* PNS::SHOVE::m_root

private

Definition at line 170 of file pns_shove.h.

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

◆ m_rootLineHistory

std::unordered_map<const LINKED_ITEM*, LINE*> PNS::SHOVE::m_rootLineHistory

private

Definition at line 168 of file pns_shove.h.

Referenced by findRootLine(), replaceLine(), and ~SHOVE().

◆ m_router

ROUTER* PNS::ALGO_BASE::m_router

protectedinherited

Definition at line 87 of file pns_algo_base.h.

Referenced by PNS::MEANDER_PLACER_BASE::lineLength(), PNS::ALGO_BASE::Router(), PNS::ALGO_BASE::Settings(), PNS::DIFF_PAIR_PLACER::updateLeadingRatLine(), PNS::LINE_PLACER::updateLeadingRatLine(), and PNS::ALGO_BASE::VisibleViewArea().

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

Classes

Public Types

Public Member Functions

Protected Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ HULL_SET

◆ LINE_PAIR

◆ LINE_PAIR_VEC

◆ OPT_LINE

Member Enumeration Documentation

◆ SHOVE_STATUS

Constructor & Destructor Documentation

◆ SHOVE()

◆ ~SHOVE()

Member Function Documentation

◆ AddLockedSpringbackNode()

◆ assembleLine()

◆ checkShoveDirection()

◆ CurrentNode()

◆ Dbg()

◆ findRootLine()

◆ ForceClearance()

◆ getClearance()

◆ getHoleClearance()

◆ Logger()

◆ NewHead()

◆ onCollidingArc()

◆ onCollidingLine()

◆ onCollidingSegment()

◆ onCollidingSolid()

◆ onCollidingVia()

◆ onReverseCollidingVia()

◆ popLineStack()

◆ pushLineStack()

◆ pushOrShoveVia()

◆ pushSpringback()

◆ reduceSpringback()

◆ replaceItems()

◆ replaceLine()

◆ RewindSpringbackTo()

◆ Router()

◆ runOptimizer()

◆ sanityCheck()

◆ SetDebugDecorator()

◆ SetInitialLine()

◆ SetLogger()

◆ Settings()

◆ ShoveDraggingVia()

◆ shoveIteration()

◆ shoveLineFromLoneVia()

◆ ShoveLines()

◆ shoveLineToHullSet()

◆ shoveMainLoop()

◆ ShoveMultiLines()

◆ ShoveObstacleLine()

◆ totalAffectedArea()

◆ UnlockSpringbackNode()

◆ unwindLineStack() [1/2]

◆ unwindLineStack() [2/2]

◆ VisibleViewArea()

Member Data Documentation

◆ m_affectedArea

◆ m_currentNode

◆ m_debugDecorator

◆ m_draggedVia

◆ m_forceClearance

◆ m_iter

◆ m_lineStack

◆ m_logger

◆ m_multiLineMode

◆ m_newHead

◆ m_nodeStack

◆ m_optimizerQueue

◆ m_restrictSpringbackTagId

◆ m_root

◆ m_rootLineHistory