Keep the router "world" - i.e. More...

#include <pns_node.h>

Classes
struct	DEFAULT_OBSTACLE_VISITOR

Public Types
enum	COLLISION_QUERY_SCOPE { CQS_ALL_RULES = 1 , CQS_IGNORE_HOLE_CLEARANCE = 2 }
	< Supported item types More...

typedef std::optional< OBSTACLE >	OPT_OBSTACLE

typedef std::vector< ITEM * >	ITEM_VECTOR

typedef std::vector< OBSTACLE >	OBSTACLES

Public Member Functions
	NODE ()

	~NODE ()
	Return the expected clearance between items a and b. More...

int	GetClearance (const ITEM aA, const ITEM aB, bool aUseClearanceEpsilon=true) const

int	GetHoleClearance (const ITEM aA, const ITEM aB, bool aUseClearanceEpsilon=true) const

int	GetHoleToHoleClearance (const ITEM aA, const ITEM aB, bool aUseClearanceEpsilon=true) const
	Return the pre-set worst case clearance between any pair of items. More...

int	GetMaxClearance () const
	Set the worst-case clearance between any pair of items. More...

void	SetMaxClearance (int aClearance)
	Assign a clearance resolution function object. More...

void	SetRuleResolver (RULE_RESOLVER *aFunc)

RULE_RESOLVER *	GetRuleResolver () const
	Return the number of joints. More...

int	JointCount () const
	Return the number of nodes in the inheritance chain (wrs to the root node). More...

int	Depth () const

int	QueryColliding (const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aOverrideClearance=-1)
	Find items colliding (closer than clearance) with the item aItem. More...

int	QueryJoints (const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)

OPT_OBSTACLE	NearestObstacle (const LINE aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM > *aRestrictedSet=nullptr, bool aUseClearanceEpsilon=true)
	Follow the line in search of an obstacle that is nearest to the starting to the line's starting point. More...

OPT_OBSTACLE	CheckColliding (const ITEM *aItem, int aKindMask=ITEM::ANY_T)
	Check if the item collides with anything else in the world, and if found, returns the obstacle. More...

OPT_OBSTACLE	CheckColliding (const ITEM_SET &aSet, int aKindMask=ITEM::ANY_T)
	Check if any item in the set collides with anything else in the world, and if found, returns the obstacle. More...

const ITEM_SET	HitTest (const VECTOR2I &aPoint) const
	Find all items that contain the point aPoint. More...

bool	Add (std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
	Add an item to the current node. More...

void	Add (std::unique_ptr< SOLID > aSolid)

void	Add (std::unique_ptr< VIA > aVia)

bool	Add (std::unique_ptr< ARC > aArc, bool aAllowRedundant=false)

void	Add (LINE &aLine, bool aAllowRedundant=false)

void	AddEdgeExclusion (std::unique_ptr< SHAPE > aShape)

bool	QueryEdgeExclusions (const VECTOR2I &aPos) const

void	Remove (ARC *aArc)
	Remove an item from this branch. More...

void	Remove (SOLID *aSolid)

void	Remove (VIA *aVia)

void	Remove (SEGMENT *aSegment)

void	Remove (ITEM *aItem)

void	Remove (LINE &aLine)
	Removes a line from this branch. More...

void	Replace (ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
	Replace an item with another one. More...

void	Replace (LINE &aOldLine, LINE &aNewLine)

NODE *	Branch ()
	Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs to the root. More...

const LINE	AssembleLine (LINKED_ITEM aSeg, int aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
	Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg. More...

void	Dump (bool aLong=false)

void	GetUpdatedItems (ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
	Return the list of items removed and added in this branch with respect to the root branch. More...

void	Commit (NODE *aNode)
	Apply the changes from a given branch (aNode) to the root branch. More...

JOINT *	FindJoint (const VECTOR2I &aPos, int aLayer, int aNet)
	Search for a joint at a given position, layer and belonging to given net. More...

void	LockJoint (const VECTOR2I &aPos, const ITEM *aItem, bool aLock)

JOINT *	FindJoint (const VECTOR2I &aPos, const ITEM *aItem)
	Search for a joint at a given position, linked to given item. More...

int	FindLinesBetweenJoints (const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
	Find the joints corresponding to the ends of line aLine. More...

void	FindLineEnds (const LINE &aLine, JOINT &aA, JOINT &aB)
	Destroy all child nodes. Applicable only to the root node. More...

void	KillChildren ()

void	AllItemsInNet (int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)

void	ClearRanks (int aMarkerMask=MK_HEAD\|MK_VIOLATION\|MK_HOLE)

void	RemoveByMarker (int aMarker)

ITEM *	FindItemByParent (const BOARD_ITEM *aParent)

bool	HasChildren () const

NODE *	GetParent () const
	Check if this branch contains an updated version of the m_item from the root branch. More...

bool	Overrides (ITEM *aItem) const

void	FixupVirtualVias ()

void	SetCollisionQueryScope (COLLISION_QUERY_SCOPE aScope)

COLLISION_QUERY_SCOPE	GetCollisionQueryScope () const

void	Add (std::unique_ptr< ITEM > aItem, bool aAllowRedundant=false)

Private Types
typedef std::unordered_multimap< JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH >	JOINT_MAP

typedef JOINT_MAP::value_type	TagJointPair

Private Member Functions
	NODE (const NODE &aB)
	nodes are not copyable More...

NODE &	operator= (const NODE &aB)
	Try to find matching joint and creates a new one if not found. More...

JOINT &	touchJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
	Touch a joint and links it to an m_item. More...

void	linkJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
	Unlink an item from a joint. More...

void	unlinkJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
	Helpers for adding/removing items. More...

void	addSolid (SOLID *aSeg)

void	addSegment (SEGMENT *aSeg)

void	addVia (VIA *aVia)

void	addArc (ARC *aVia)

void	removeSolidIndex (SOLID *aSeg)

void	removeSegmentIndex (SEGMENT *aSeg)

void	removeViaIndex (VIA *aVia)

void	removeArcIndex (ARC *aVia)

void	doRemove (ITEM *aItem)

void	unlinkParent ()

void	releaseChildren ()

void	releaseGarbage ()

void	rebuildJoint (JOINT aJoint, ITEM aItem)

bool	isRoot () const

SEGMENT *	findRedundantSegment (const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)

SEGMENT *	findRedundantSegment (SEGMENT *aSeg)

ARC *	findRedundantArc (const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)

ARC *	findRedundantArc (ARC *aSeg)
	Scan the joint map, forming a line starting from segment (current). More...

void	followLine (LINKED_ITEM aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I aCorners, LINKED_ITEM *aSegments, bool aArcReversed, bool &aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments)

Private Attributes
JOINT_MAP	m_joints
	hash table with the joints, linking the items. More...

NODE *	m_parent
	node this node was branched from More...

NODE *	m_root
	root node of the whole hierarchy More...

std::set< NODE * >	m_children
	list of nodes branched from this one More...

std::unordered_set< ITEM * >	m_override
	hash of root's items that have been changed in this node More...

int	m_maxClearance
	worst case item-item clearance More...

RULE_RESOLVER *	m_ruleResolver
	Design rules resolver. More...

INDEX *	m_index
	Geometric/Net index of the items. More...

int	m_depth
	depth of the node (number of parent nodes in the inheritance chain) More...

std::vector< std::unique_ptr< SHAPE > >	m_edgeExclusions

std::unordered_set< ITEM * >	m_garbageItems

COLLISION_QUERY_SCOPE	m_collisionQueryScope

Detailed Description

Keep the router "world" - i.e.

all the tracks, vias, solids in a hierarchical and indexed way.

Features:

spatial-indexed container for PCB item shapes.
collision search & clearance checking.
assembly of lines connecting joints, finding loops and unique paths.
lightweight cloning/branching (for recursive optimization and shove springback).

Definition at line 155 of file pns_node.h.

Member Typedef Documentation

◆ ITEM_VECTOR

typedef std::vector<ITEM*> PNS::NODE::ITEM_VECTOR

Definition at line 167 of file pns_node.h.

◆ JOINT_MAP

typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> PNS::NODE::JOINT_MAP

private

Definition at line 479 of file pns_node.h.

◆ OBSTACLES

typedef std::vector<OBSTACLE> PNS::NODE::OBSTACLES

Definition at line 168 of file pns_node.h.

◆ OPT_OBSTACLE

typedef std::optional<OBSTACLE> PNS::NODE::OPT_OBSTACLE

Definition at line 166 of file pns_node.h.

◆ TagJointPair

typedef JOINT_MAP::value_type PNS::NODE::TagJointPair

private

Definition at line 480 of file pns_node.h.

Member Enumeration Documentation

◆ COLLISION_QUERY_SCOPE

enum PNS::NODE::COLLISION_QUERY_SCOPE

< Supported item types

Enumerator
CQS_ALL_RULES	check all rules
CQS_IGNORE_HOLE_CLEARANCE	check everything except hole2hole / hole2copper

Definition at line 160 of file pns_node.h.

 {
 CQS_ALL_RULES = 1, 
 CQS_IGNORE_HOLE_CLEARANCE = 2 
 };

Constructor & Destructor Documentation

◆ NODE() [1/2]

PNS::NODE::NODE ( )

Definition at line 54 of file pns_node.cpp.

{
 m_depth = 0;
 m_root = this;
 m_parent = nullptr;
 m_maxClearance = 800000; // fixme: depends on how thick traces are.
 m_ruleResolver = nullptr;
 m_index = new INDEX;
 m_collisionQueryScope = CQS_ALL_RULES;
 
#ifdef DEBUG
 allocNodes.insert( this );
#endif
}

References CQS_ALL_RULES, m_collisionQueryScope, m_depth, m_index, m_maxClearance, m_parent, m_root, and m_ruleResolver.

Referenced by Branch().

◆ ~NODE()

PNS::NODE::~NODE ( )

Return the expected clearance between items a and b.

Definition at line 70 of file pns_node.cpp.

{
 if( !m_children.empty() )
 {
 wxLogTrace( wxT( "PNS" ), wxT( "attempting to free a node that has kids." ) );
 assert( false );
 }
 
#ifdef DEBUG
 if( allocNodes.find( this ) == allocNodes.end() )
 {
 wxLogTrace( wxT( "PNS" ), wxT( "attempting to free an already-free'd node." ) );
 assert( false );
 }
 
 allocNodes.erase( this );
#endif
 
 m_joints.clear();
 
 for( ITEM* item : *m_index )
 {
 if( item->BelongsTo( this ) )
 delete item;
 }
 
 releaseGarbage();
 unlinkParent();
 
 delete m_index;
}

References m_children, m_index, m_joints, releaseGarbage(), and unlinkParent().

◆ NODE() [2/2]

PNS::NODE::NODE ( const NODE & aB )

private

nodes are not copyable

Member Function Documentation

◆ Add() [1/6]

void PNS::NODE::Add	(	LINE &	aLine,
		bool	aAllowRedundant = `false`
	)

Definition at line 606 of file pns_node.cpp.

{
 assert( !aLine.IsLinked() );
 
 SHAPE_LINE_CHAIN& l = aLine.Line();
 
 for( size_t i = 0; i < l.ArcCount(); i++ )
 {
 auto s = l.Arc( i );
 ARC* rarc;
 
 if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(),
 aLine.Net() ) ) )
 {
 aLine.Link( rarc );
 }
 else
 {
 auto newarc = std::make_unique< ARC >( aLine, s );
 aLine.Link( newarc.get() );
 Add( std::move( newarc ), true );
 }
 }
 
 for( int i = 0; i < l.SegmentCount(); i++ )
 {
 if( l.IsArcSegment( i ) )
 continue;
 
 SEG s = l.CSegment( i );
 
 if( s.A != s.B )
 {
 SEGMENT* rseg;
 
 if( !aAllowRedundant && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(),
 aLine.Net() ) ) )
 {
 // another line could be referencing this segment too :(
 aLine.Link( rseg );
 }
 else
 {
 std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
 aLine.Link( newseg.get() );
 Add( std::move( newseg ), true );
 }
 }
 }
}

References SEG::A, Add(), SHAPE_LINE_CHAIN::Arc(), SHAPE_LINE_CHAIN::ArcCount(), SEG::B, SHAPE_LINE_CHAIN::CSegment(), findRedundantArc(), findRedundantSegment(), SHAPE_LINE_CHAIN::IsArcSegment(), PNS::LINK_HOLDER::IsLinked(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::LINK_HOLDER::Link(), PNS::ITEM::Net(), and SHAPE_LINE_CHAIN::SegmentCount().

◆ Add() [2/6]

bool PNS::NODE::Add	(	std::unique_ptr< ARC >	aArc,
		bool	aAllowRedundant = `false`
	)

Definition at line 695 of file pns_node.cpp.

{
 const SHAPE_ARC& arc = aArc->CArc();
 
 if( !aAllowRedundant && findRedundantArc( arc.GetP0(), arc.GetP1(), aArc->Layers(),
 aArc->Net() ) )
 {
 return false;
 }
 
 aArc->SetOwner( this );
 addArc( aArc.release() );
 return true;
}

References addArc(), findRedundantArc(), SHAPE_ARC::GetP0(), and SHAPE_ARC::GetP1().

◆ Add() [3/6]

void PNS::NODE::Add	(	std::unique_ptr< ITEM >	aItem,
		bool	aAllowRedundant = `false`
	)

Definition at line 711 of file pns_node.cpp.

{
 switch( aItem->Kind() )
 {
 case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
 case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
 case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
 
 case ITEM::ARC_T:
  //todo(snh): Add redundant search
 Add( ItemCast<ARC>( std::move( aItem ) ) );
 break;
 
 case ITEM::LINE_T:
 {
 // fixme(twl): I don't like unique_ptr in this methods as the router has its own garbage
 // collecting mechanism. This particular case is used exclusively in
 // ROUTER::GetUpdatedItems() for dumping debug logs. Please don't call Add ( up<LINE> )
 // otherwise, dragons live here.
 LINE *l = static_cast<LINE*>( aItem.get() );
 Add( *l );
 break;
 }
 default:
 assert( false );
 }
}

References Add(), PNS::ITEM::ARC_T, PNS::ITEM::LINE_T, PNS::ITEM::SEGMENT_T, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

◆ Add() [4/6]

bool PNS::NODE::Add	(	std::unique_ptr< SEGMENT >	aSegment,
		bool	aAllowRedundant = `false`
	)

Add an item to the current node.

Parameters

aSegment	item to add.
aAllowRedundant	if true, duplicate items are allowed (e.g. a segment or via at the same coordinates as an existing one).

Returns: true if added

Definition at line 667 of file pns_node.cpp.

{
 if( aSegment->Seg().A == aSegment->Seg().B )
 {
 wxLogTrace( wxT( "PNS" ),
 wxT( "attempting to add a segment with same end coordinates, ignoring." ) );
 return false;
 }
 
 if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
 return false;
 
 aSegment->SetOwner( this );
 addSegment( aSegment.release() );
 
 return true;
}

References addSegment(), and findRedundantSegment().

Referenced by Add(), Commit(), PNS::COMPONENT_DRAGGER::Drag(), PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragShove(), PNS::DRAGGER::dragViaMarkObstacles(), PNS::DRAGGER::dragViaWalkaround(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::DP_MEANDER_PLACER::FixRoute(), PNS::MEANDER_PLACER::FixRoute(), FixupVirtualVias(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), PNS::LINE_PLACER::removeLoops(), Replace(), PNS::SHOVE::ShoveLines(), PNS::SHOVE::ShoveMultiLines(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), PNS::LINE_PLACER::SplitAdjacentSegments(), PNS_KICAD_IFACE_BASE::syncGraphicalItem(), PNS_KICAD_IFACE_BASE::syncTextItem(), PNS_KICAD_IFACE_BASE::SyncWorld(), and PNS_KICAD_IFACE_BASE::syncZone().

◆ Add() [5/6]

void PNS::NODE::Add ( std::unique_ptr< SOLID > aSolid )

Definition at line 584 of file pns_node.cpp.

{
 aSolid->SetOwner( this );
 addSolid( aSolid.release() );
}

References addSolid().

◆ Add() [6/6]

void PNS::NODE::Add ( std::unique_ptr< VIA > aVia )

Definition at line 599 of file pns_node.cpp.

{
 aVia->SetOwner( this );
 addVia( aVia.release() );
}

References addVia().

◆ addArc()

void PNS::NODE::addArc ( ARC * aVia )

private

Definition at line 686 of file pns_node.cpp.

{
 linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
 linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
 
 m_index->Add( aArc );
}

References PNS::INDEX::Add(), PNS::ARC::Anchor(), PNS::ITEM::Layers(), linkJoint(), m_index, and PNS::ITEM::Net().

Referenced by Add().

◆ AddEdgeExclusion()

void PNS::NODE::AddEdgeExclusion ( std::unique_ptr< SHAPE > aShape )

Definition at line 740 of file pns_node.cpp.

{
 m_edgeExclusions.push_back( std::move( aShape ) );
}

References m_edgeExclusions.

Referenced by PNS_KICAD_IFACE_BASE::SyncWorld().

◆ addSegment()

void PNS::NODE::addSegment ( SEGMENT * aSeg )

private

Definition at line 658 of file pns_node.cpp.

{
 linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
 linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
 
 m_index->Add( aSeg );
}

References SEG::A, PNS::INDEX::Add(), SEG::B, PNS::ITEM::Layers(), linkJoint(), m_index, PNS::ITEM::Net(), and PNS::SEGMENT::Seg().

Referenced by Add().

◆ addSolid()

void PNS::NODE::addSolid ( SOLID * aSeg )

private

Definition at line 575 of file pns_node.cpp.

{
 if( aSolid->IsRoutable() )
 linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
 
 m_index->Add( aSolid );
}

References PNS::INDEX::Add(), PNS::ITEM::IsRoutable(), PNS::ITEM::Layers(), linkJoint(), m_index, PNS::ITEM::Net(), and PNS::SOLID::Pos().

Referenced by Add().

◆ addVia()

void PNS::NODE::addVia ( VIA * aVia )

private

Definition at line 591 of file pns_node.cpp.

{
 linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
 
 m_index->Add( aVia );
}

References PNS::INDEX::Add(), PNS::ITEM::Layers(), linkJoint(), m_index, PNS::ITEM::Net(), and PNS::VIA::Pos().

Referenced by Add().

◆ AllItemsInNet()

void PNS::NODE::AllItemsInNet	(	int	aNet,
		std::set< ITEM * > &	aItems,
		int	aKindMask = `-1`
	)

Definition at line 1476 of file pns_node.cpp.

{
 INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
 
 if( l_cur )
 {
 for( ITEM* item : *l_cur )
 {
 if( item->OfKind( aKindMask ) && item->IsRoutable() )
 aItems.insert( item );
 }
 }
 
 if( !isRoot() )
 {
 INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
 
 if( l_root )
 {
 for( ITEM* item : *l_root )
 {
 if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
 aItems.insert( item );
 }
 }
 }
}

References PNS::INDEX::GetItemsForNet(), isRoot(), m_index, m_root, and Overrides().

Referenced by PNS::TOPOLOGY::AssembleDiffPair(), PNS::DIFF_PAIR_PLACER::FindDpPrimitivePair(), and PNS::TOPOLOGY::NearestUnconnectedItem().

◆ AssembleLine()

const LINE PNS::NODE::AssembleLine	(	LINKED_ITEM *	aSeg,
		int *	aOriginSegmentIndex = `nullptr`,
		bool	aStopAtLockedJoints = `false`,
		bool	aFollowLockedSegments = `false`
	)

Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.

Parameters

aSeg	the initial segment.
aOriginSegmentIndex	index of aSeg in the resulting line.
aStopAtLockedJoints	will terminate the line at the first locked joint encountered
aFollowLockedSegments	will consider a joint between a locked segment and an unlocked segment of the same width as a trivial joint.

Returns: the line Print the contents and joints structure.

Definition at line 1003 of file pns_node.cpp.

{
 const int MaxVerts = 1024 * 16;
 
 std::array<VECTOR2I, MaxVerts + 1> corners;
 std::array<LINKED_ITEM*, MaxVerts + 1> segs;
 std::array<bool, MaxVerts + 1> arcReversed;
 
 LINE pl;
 bool guardHit = false;
 
 int i_start = MaxVerts / 2;
 int i_end = i_start + 1;
 
 pl.SetWidth( aSeg->Width() );
 pl.SetLayers( aSeg->Layers() );
 pl.SetNet( aSeg->Net() );
 pl.SetOwner( this );
 
 followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
 
 if( !guardHit )
 {
 followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
 }
 
 int n = 0;
 
 LINKED_ITEM* prev_seg = nullptr;
 bool originSet = false;
 
 SHAPE_LINE_CHAIN& line = pl.Line();
 
 for( int i = i_start + 1; i < i_end; i++ )
 {
 const VECTOR2I& p = corners[i];
 LINKED_ITEM* li = segs[i];
 
 if( !li || li->Kind() != ITEM::ARC_T )
 line.Append( p );
 
 if( li && prev_seg != li )
 {
 if( li->Kind() == ITEM::ARC_T )
 {
 const ARC* arc = static_cast<const ARC*>( li );
 const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape() );
 
 int nSegs = line.PointCount();
 VECTOR2I last = nSegs ? line.CPoint( -1 ) : VECTOR2I();
 ssize_t lastShape = nSegs ? line.ArcIndex( static_cast<ssize_t>( nSegs ) - 1 ) : -1;
 
  line.Append( arcReversed[i] ? sa->Reversed() : *sa );
 }
 
 pl.Link( li );
 
 // latter condition to avoid loops
 if( li == aSeg && aOriginSegmentIndex && !originSet )
 {
 wxASSERT( n < line.SegmentCount() ||
 ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
 *aOriginSegmentIndex = line.PointCount() - 1;
 originSet = true;
 }
 }
 
 prev_seg = li;
 }
 
 // Remove duplicate verts, but do NOT remove colinear segments here!
 pl.Line().Simplify( false );
 
 // TODO: maintain actual segment index under simplification system
 if( aOriginSegmentIndex && *aOriginSegmentIndex >= pl.SegmentCount() )
 *aOriginSegmentIndex = pl.SegmentCount() - 1;
 
 assert( pl.SegmentCount() != 0 );
 
 return pl;
}

References SHAPE_LINE_CHAIN::Append(), PNS::ITEM::ARC_T, SHAPE_LINE_CHAIN::ArcIndex(), SHAPE_LINE_CHAIN::CPoint(), followLine(), PNS::ITEM::Kind(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::LINK_HOLDER::Link(), PNS::ITEM::Net(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_ARC::Reversed(), PNS::ITEM::SEGMENT_T, SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SegmentCount(), PNS::ITEM::SetLayers(), PNS::ITEM::SetNet(), PNS::ITEM::SetOwner(), PNS::LINE::SetWidth(), PNS::ARC::Shape(), SHAPE_LINE_CHAIN::Simplify(), and PNS::LINKED_ITEM::Width().

Referenced by PNS::TOPOLOGY::AssembleDiffPair(), PNS::SHOVE::assembleLine(), PNS::TOPOLOGY::AssembleTrivialPath(), Dump(), FindLinesBetweenJoints(), PNS::DRAGGER::findViaFanoutByHandle(), PNS::TOPOLOGY::followTrivialPath(), PNS::LINE_PLACER::removeLoops(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), PNS::MEANDER_PLACER::Start(), PNS::MEANDER_SKEW_PLACER::Start(), PNS::COMPONENT_DRAGGER::Start(), PNS::DRAGGER::startDragArc(), and PNS::DRAGGER::startDragSegment().

◆ Branch()

NODE * PNS::NODE::Branch ( )

Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs to the root.

Note: If there are any branches in use, their parents must not be deleted.

Returns: the new branch.

Definition at line 139 of file pns_node.cpp.

{
 NODE* child = new NODE;
 
 m_children.insert( child );
 
 child->m_depth = m_depth + 1;
 child->m_parent = this;
 child->m_ruleResolver = m_ruleResolver;
 child->m_root = isRoot() ? this : m_root;
 child->m_maxClearance = m_maxClearance;
 child->m_collisionQueryScope = m_collisionQueryScope;
 
 // Immediate offspring of the root branch needs not copy anything. For the rest, deep-copy
 // joints, overridden item maps and pointers to stored items.
 if( !isRoot() )
 {
 JOINT_MAP::iterator j;
 
 for( ITEM* item : *m_index )
 child->m_index->Add( item );
 
 child->m_joints = m_joints;
 child->m_override = m_override;
 }
 
#if 0
 wxLogTrace( wxT( "PNS" ), wxT( "%d items, %d joints, %d overrides" ),
 child->m_index->Size(),
 (int) child->m_joints.size(),
 (int) child->m_override.size() );
#endif
 
 return child;
}

References PNS::INDEX::Add(), isRoot(), m_children, m_collisionQueryScope, m_depth, m_index, m_joints, m_maxClearance, m_override, m_parent, m_root, m_ruleResolver, NODE(), and PNS::INDEX::Size().

Referenced by PNS::MEANDER_PLACER::doMove(), PNS::COMPONENT_DRAGGER::Drag(), PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragWalkaround(), PNS::LINE_PLACER::FixRoute(), PNS::DIFF_PAIR_PLACER::initPlacement(), PNS::LINE_PLACER::initPlacement(), PNS::DIFF_PAIR_PLACER::Move(), PNS::DP_MEANDER_PLACER::Move(), PNS::LINE_PLACER::Move(), PNS::TOPOLOGY::NearestUnconnectedAnchorPoint(), PNS::SHOVE::SetInitialLine(), PNS::SHOVE::ShoveDraggingVia(), PNS::SHOVE::ShoveLines(), PNS::SHOVE::ShoveMultiLines(), PNS::DP_MEANDER_PLACER::Start(), PNS::MEANDER_PLACER::Start(), PNS::MEANDER_SKEW_PLACER::Start(), PNS::DIFF_PAIR_PLACER::tryWalkDp(), and PNS::LINE_PLACER::UnfixRoute().

◆ CheckColliding() [1/2]

NODE::OPT_OBSTACLE PNS::NODE::CheckColliding	(	const ITEM *	aItem,
		int	aKindMask = `ITEM::ANY_T`
	)

Check if the item collides with anything else in the world, and if found, returns the obstacle.

Parameters

aItem	the item to find collisions with
aKindMask	mask of obstacle types to take into account

Returns: the obstacle, if found, otherwise empty.

Definition at line 475 of file pns_node.cpp.

{
 OBSTACLES obs;
 
 obs.reserve( 100 );
 
 if( aItemA->Kind() == ITEM::LINE_T )
 {
 int n = 0;
 const LINE* line = static_cast<const LINE*>( aItemA );
 const SHAPE_LINE_CHAIN& l = line->CLine();
 
 for( int i = 0; i < l.SegmentCount(); i++ )
 {
 // Note: Clearances between &s and other items are cached,
 // which means they'll be the same for all segments in the line.
 // Disabling the cache will lead to slowness.
 
 const SEGMENT s( *line, l.CSegment( i ) );
 n += QueryColliding( &s, obs, aKindMask, 1 );
 
 if( n )
 return OPT_OBSTACLE( obs[0] );
 }
 
 if( line->EndsWithVia() )
 {
 n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
 
 if( n )
 return OPT_OBSTACLE( obs[0] );
 }
 }
 else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
 {
 return OPT_OBSTACLE( obs[0] );
 }
 
 return OPT_OBSTACLE();
}

References PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CSegment(), PNS::LINE::EndsWithVia(), PNS::ITEM::Kind(), PNS::ITEM::LINE_T, QueryColliding(), SHAPE_LINE_CHAIN::SegmentCount(), and PNS::LINE::Via().

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), CheckColliding(), PNS::OPTIMIZER::checkColliding(), PNS::checkDpColliding(), PNS::DP_MEANDER_PLACER::CheckFit(), PNS::MEANDER_PLACER::CheckFit(), PNS::LINE_PLACER::clipAndCheckCollisions(), PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragViaWalkaround(), PNS::DRAGGER::dragWalkaround(), PNS::OPTIMIZER::fanoutCleanup(), PNS::COMPONENT_DRAGGER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::DIFF_PAIR_PLACER::propagateDpHeadForces(), PNS::VIA::PushoutForce(), PNS::SHOVE::reduceSpringback(), PNS::LINE_PLACER::reduceTail(), PNS::DIFF_PAIR_PLACER::rhMarkObstacles(), PNS::DIFF_PAIR_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), PNS::WALKAROUND::Route(), PNS::SHOVE::ShoveLines(), PNS::tightenSegment(), and PNS::verifyDpBypass().

◆ CheckColliding() [2/2]

NODE::OPT_OBSTACLE PNS::NODE::CheckColliding	(	const ITEM_SET &	aSet,
		int	aKindMask = `ITEM::ANY_T`
	)

Check if any item in the set collides with anything else in the world, and if found, returns the obstacle.

Parameters

aSet	set of items to find collisions with.
aKindMask	mask of obstacle types to take into account.

Returns: the obstacle, if found, otherwise empty.

Definition at line 461 of file pns_node.cpp.

{
 for( const ITEM* item : aSet.CItems() )
 {
 OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
 
 if( obs )
 return obs;
 }
 
 return OPT_OBSTACLE();
}

References CheckColliding(), and PNS::ITEM_SET::CItems().

◆ ClearRanks()

void PNS::NODE::ClearRanks ( int aMarkerMask = MK_HEAD | MK_VIOLATION | MK_HOLE )

Definition at line 1505 of file pns_node.cpp.

{
 for( ITEM* item : *m_index )
 {
 item->SetRank( -1 );
 item->Mark( item->Marker() & ~aMarkerMask );
 }
}

References m_index.

Referenced by PNS::SHOVE::ShoveDraggingVia(), PNS::SHOVE::ShoveLines(), and PNS::SHOVE::ShoveMultiLines().

◆ Commit()

void PNS::NODE::Commit ( NODE * aNode )

Apply the changes from a given branch (aNode) to the root branch.

Calling on a non-root branch will fail. Calling commit also kills all children nodes of the root branch.

Parameters

aNode node to commit changes from.

Definition at line 1450 of file pns_node.cpp.

{
 if( aNode->isRoot() )
 return;
 
 for( ITEM* item : aNode->m_override )
 Remove( item );
 
 for( ITEM* item : *aNode->m_index )
 {
 item->SetRank( -1 );
 item->Unmark();
 Add( std::unique_ptr<ITEM>( item ) );
 }
 
 releaseChildren();
 releaseGarbage();
}

References Add(), isRoot(), m_index, m_override, releaseChildren(), releaseGarbage(), Remove(), PNS::ITEM::SetRank(), and PNS::ITEM::Unmark().

◆ Depth()

int PNS::NODE::Depth ( ) const

inline

Definition at line 209 of file pns_node.h.

 {
 return m_depth;
 }

References m_depth.

Referenced by PNS::LINE_PLACER::Move().

◆ doRemove()

void PNS::NODE::doRemove ( ITEM * aItem )

private

Definition at line 758 of file pns_node.cpp.

{
 // case 1: removing an item that is stored in the root node from any branch:
 // mark it as overridden, but do not remove
 if( aItem->BelongsTo( m_root ) && !isRoot() )
 m_override.insert( aItem );
 
 // case 2: the item belongs to this branch or a parent, non-root branch,
 // or the root itself and we are the root: remove from the index
 else if( !aItem->BelongsTo( m_root ) || isRoot() )
 m_index->Remove( aItem );
 
 // the item belongs to this particular branch: un-reference it
 if( aItem->BelongsTo( this ) )
 {
 aItem->SetOwner( nullptr );
 m_root->m_garbageItems.insert( aItem );
 }
}

References PNS::ITEM::BelongsTo(), isRoot(), m_garbageItems, m_index, m_override, m_root, PNS::INDEX::Remove(), and PNS::ITEM::SetOwner().

Referenced by Remove().

◆ Dump()

void PNS::NODE::Dump ( bool aLong = false )

Definition at line 1316 of file pns_node.cpp.

{
#if 0
 std::unordered_set<SEGMENT*> all_segs;
 SHAPE_INDEX_LIST<ITEM*>::iterator i;
 
 for( i = m_items.begin(); i != m_items.end(); i++ )
 {
 if( (*i)->GetKind() == ITEM::SEGMENT_T )
 all_segs.insert( static_cast<SEGMENT*>( *i ) );
 }
 
 if( !isRoot() )
 {
 for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
 {
 if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
 all_segs.insert( static_cast<SEGMENT*>(*i) );
 }
 }
 
 JOINT_MAP::iterator j;
 
 if( aLong )
 {
 for( j = m_joints.begin(); j != m_joints.end(); ++j )
 {
 wxLogTrace( wxT( "PNS" ), wxT( "joint : %s, links : %d\n" ),
 j->second.GetPos().Format().c_str(), j->second.LinkCount() );
 JOINT::LINKED_ITEMS::const_iterator k;
 
 for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
 {
 const ITEM* m_item = *k;
 
 switch( m_item->GetKind() )
 {
 case ITEM::SEGMENT_T:
 {
 const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
 wxLogTrace( wxT( "PNS" ), wxT( " -> seg %s %s\n" ),
 seg->GetSeg().A.Format().c_str(),
 seg->GetSeg().B.Format().c_str() );
 break;
 }
 
 default:
 break;
 }
 }
 }
 }
 
 int lines_count = 0;
 
 while( !all_segs.empty() )
 {
 SEGMENT* s = *all_segs.begin();
 LINE* l = AssembleLine( s );
 
 LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
 
 if( aLong )
 {
 wxLogTrace( wxT( "PNS" ), wxT( "Line: %s, net %d " ),
 l->GetLine().Format().c_str(), l->GetNet() );
 }
 
 for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
 {
 wxLogTrace( wxT( "PNS" ), wxT( "%s " ), (*j)->GetSeg().A.Format().c_str() );
 
 if( j + 1 == seg_refs->end() )
 wxLogTrace( wxT( "PNS" ), wxT( "%s\n" ), (*j)->GetSeg().B.Format().c_str() );
 
 all_segs.erase( *j );
 }
 
 lines_count++;
 }
 
 wxLogTrace( wxT( "PNS" ), wxT( "Local joints: %d, lines : %d \n" ),
 m_joints.size(), lines_count );
#endif
}

References AssembleLine(), PNS::ITEM::Format(), PNS::SEGMENT::Format(), isRoot(), m_joints, m_root, and PNS::ITEM::SEGMENT_T.

◆ FindItemByParent()

ITEM * PNS::NODE::FindItemByParent ( const BOARD_ITEM * aParent )

Definition at line 1638 of file pns_node.cpp.

{
 if( aParent->IsConnected() )
 {
 const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
 
 INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( cItem->GetNetCode() );
 
 if( l_cur )
 {
 for( ITEM* item : *l_cur )
 {
 if( item->Parent() == aParent )
 return item;
 }
 }
 }
 
 return nullptr;
}

References PNS::INDEX::GetItemsForNet(), BOARD_CONNECTED_ITEM::GetNetCode(), BOARD_ITEM::IsConnected(), and m_index.

Referenced by ROUTER_TOOL::InlineBreakTrack(), ROUTER_TOOL::InlineDrag(), and ROUTER_TOOL::RouteSelected().

◆ FindJoint() [1/2]

JOINT * PNS::NODE::FindJoint	(	const VECTOR2I &	aPos,
		const ITEM *	aItem
	)

inline

Search for a joint at a given position, linked to given item.

Returns: the joint, if found, otherwise empty. Find all lines between a pair of joints. Used by the loop removal procedure.

Definition at line 376 of file pns_node.h.

References FindJoint(), PNS::ITEM::Layers(), PNS::ITEM::Net(), and LAYER_RANGE::Start().

◆ FindJoint() [2/2]

JOINT * PNS::NODE::FindJoint	(	const VECTOR2I &	aPos,
		int	aLayer,
		int	aNet
	)

Search for a joint at a given position, layer and belonging to given net.

Returns: the joint, if found, otherwise empty.

Definition at line 1201 of file pns_node.cpp.

{
 JOINT::HASH_TAG tag;
 
 tag.net = aNet;
 tag.pos = aPos;
 
 JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
 
 if( f == end && !isRoot() )
 {
 end = m_root->m_joints.end();
 f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
 }
 
 if( f == end )
 return nullptr;
 
 while( f != end )
 {
 if( f->second.Layers().Overlaps( aLayer ) )
 return &f->second;
 
 ++f;
 }
 
 return nullptr;
}

References isRoot(), m_joints, m_root, PNS::JOINT::HASH_TAG::net, and PNS::JOINT::HASH_TAG::pos.

Referenced by PNS::TOPOLOGY::AssembleTrivialPath(), PNS::DRAGGER::checkVirtualVia(), PNS::TOPOLOGY::ConnectedJoints(), FindJoint(), FindLineEnds(), PNS::OPTIMIZER::findPadOrVia(), findRedundantArc(), findRedundantSegment(), PNS::findViaByHandle(), PNS::DRAGGER::findViaFanoutByHandle(), PNS::SHOVE::fixupViaCollisions(), followLine(), PNS::TOPOLOGY::followTrivialPath(), PNS::getDanglingAnchor(), PNS::ROUTER::getNearestRatnestAnchor(), PNS::SHOVE::onCollidingSolid(), PNS::SHOVE::onReverseCollidingVia(), PNS::SHOVE::pushOrShoveVia(), removeSolidIndex(), removeViaIndex(), PNS::SHOVE::shoveLineToHullSet(), PNS::LINE_PLACER::simplifyNewLine(), PNS::LINE_PLACER::SplitAdjacentSegments(), and PNS::COMPONENT_DRAGGER::Start().

◆ FindLineEnds()

void PNS::NODE::FindLineEnds	(	const LINE &	aLine,
		JOINT &	aA,
		JOINT &	aB
	)

Destroy all child nodes. Applicable only to the root node.

Definition at line 1089 of file pns_node.cpp.

{
 aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
 aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
}

References PNS::LINE::CPoint(), and FindJoint().

Referenced by FindLinesBetweenJoints(), PNS::MEANDER_PLACER_BASE::GetTotalPadToDieLength(), and PNS::LINE_PLACER::removeLoops().

◆ FindLinesBetweenJoints()

int PNS::NODE::FindLinesBetweenJoints	(	const JOINT &	aA,
		const JOINT &	aB,
		std::vector< LINE > &	aLines
	)

Find the joints corresponding to the ends of line aLine.

Definition at line 1096 of file pns_node.cpp.

{
 for( ITEM* item : aA.LinkList() )
 {
 if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
 {
 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
 LINE line = AssembleLine( li );
 
 if( !line.Layers().Overlaps( aB.Layers() ) )
 continue;
 
 JOINT j_start, j_end;
 
 FindLineEnds( line, j_start, j_end );
 
 int id_start = line.CLine().Find( aA.Pos() );
 int id_end = line.CLine().Find( aB.Pos() );
 
 if( id_end < id_start )
 std::swap( id_end, id_start );
 
 if( id_start >= 0 && id_end >= 0 )
 {
 line.ClipVertexRange( id_start, id_end );
 aLines.push_back( line );
 }
 }
 }
 
 return 0;
}

References PNS::ITEM::ARC_T, AssembleLine(), PNS::LINE::CLine(), PNS::LINE::ClipVertexRange(), SHAPE_LINE_CHAIN::Find(), FindLineEnds(), PNS::ITEM::Layers(), PNS::JOINT::LinkList(), LAYER_RANGE::Overlaps(), PNS::JOINT::Pos(), and PNS::ITEM::SEGMENT_T.

Referenced by PNS::LINE_PLACER::removeLoops().

◆ findRedundantArc() [1/2]

ARC * PNS::NODE::findRedundantArc ( ARC * aSeg )

private

Scan the joint map, forming a line starting from segment (current).

Definition at line 1594 of file pns_node.cpp.

{
 return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
}

References PNS::ARC::Anchor(), findRedundantArc(), PNS::ITEM::Layers(), and PNS::ITEM::Net().

◆ findRedundantArc() [2/2]

ARC * PNS::NODE::findRedundantArc	(	const VECTOR2I &	A,
		const VECTOR2I &	B,
		const LAYER_RANGE &	lr,
		int	aNet
	)

private

Definition at line 1565 of file pns_node.cpp.

{
 JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
 
 if( !jtStart )
 return nullptr;
 
 for( ITEM* item : jtStart->LinkList() )
 {
 if( item->OfKind( ITEM::ARC_T ) )
 {
 ARC* seg2 = static_cast<ARC*>( item );
 
 const VECTOR2I a2( seg2->Anchor( 0 ) );
 const VECTOR2I b2( seg2->Anchor( 1 ) );
 
 if( seg2->Layers().Start() == lr.Start()
 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
 {
 return seg2;
 }
 }
 }
 
 return nullptr;
}

References PNS::ARC::Anchor(), PNS::ITEM::ARC_T, FindJoint(), PNS::ITEM::Layers(), PNS::JOINT::LinkList(), and LAYER_RANGE::Start().

Referenced by Add(), and findRedundantArc().

◆ findRedundantSegment() [1/2]

SEGMENT * PNS::NODE::findRedundantSegment	(	const VECTOR2I &	A,
		const VECTOR2I &	B,
		const LAYER_RANGE &	lr,
		int	aNet
	)

private

Definition at line 1530 of file pns_node.cpp.

{
 JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
 
  if( !jtStart )
 return nullptr;
 
 for( ITEM* item : jtStart->LinkList() )
 {
 if( item->OfKind( ITEM::SEGMENT_T ) )
 {
 SEGMENT* seg2 = (SEGMENT*)item;
 
 const VECTOR2I a2( seg2->Seg().A );
 const VECTOR2I b2( seg2->Seg().B );
 
 if( seg2->Layers().Start() == lr.Start()
 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
 {
 return seg2;
 }
 }
 }
 
 return nullptr;
}

References SEG::A, SEG::B, FindJoint(), PNS::ITEM::Layers(), PNS::JOINT::LinkList(), PNS::SEGMENT::Seg(), PNS::ITEM::SEGMENT_T, and LAYER_RANGE::Start().

Referenced by Add(), and findRedundantSegment().

◆ findRedundantSegment() [2/2]

SEGMENT * PNS::NODE::findRedundantSegment ( SEGMENT * aSeg )

private

Definition at line 1559 of file pns_node.cpp.

{
 return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
}

References SEG::A, SEG::B, findRedundantSegment(), PNS::ITEM::Layers(), PNS::ITEM::Net(), and PNS::SEGMENT::Seg().

◆ FixupVirtualVias()

void PNS::NODE::FixupVirtualVias ( )

Definition at line 1130 of file pns_node.cpp.

{
 SEGMENT* locked_seg = nullptr;
 std::vector<VVIA*> vvias;
 
 for( auto& jointPair : m_joints )
 {
 JOINT joint = jointPair.second;
 
 if( joint.Layers().IsMultilayer() )
 continue;
 
 int n_seg = 0, n_solid = 0, n_vias = 0;
 int prev_w = -1;
 int max_w = -1;
 bool is_width_change = false;
 bool is_locked = false;
 
 for( const auto& lnk : joint.LinkList() )
 {
 if( lnk.item->OfKind( ITEM::VIA_T ) )
 {
 n_vias++;
 }
 else if( lnk.item->OfKind( ITEM::SOLID_T ) )
 {
 n_solid++;
 }
 else if( const auto t = dyn_cast<PNS::SEGMENT*>( lnk.item ) )
 {
 int w = t->Width();
 
 if( prev_w >= 0 && w != prev_w )
 {
 is_width_change = true;
 }
 
 max_w = std::max( w, max_w );
 prev_w = w;
 
 is_locked = t->IsLocked();
 locked_seg = t;
 }
 }
 
 if( ( is_width_change || n_seg >= 3 || is_locked ) && n_solid == 0 && n_vias == 0 )
 {
 // fixme: the hull margin here is an ugly temporary workaround. The real fix
 // is to use octagons for via force propagation.
 vvias.push_back( new VVIA( joint.Pos(), joint.Layers().Start(),
 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
 }
 
 if( is_locked )
 {
 const VECTOR2I& secondPos = ( locked_seg->Seg().A == joint.Pos() ) ?
 locked_seg->Seg().B :
 locked_seg->Seg().A;
 
 vvias.push_back( new VVIA( secondPos, joint.Layers().Start(),
 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
 }
 }
 
 for( auto vvia : vvias )
 {
 Add( ItemCast<VIA>( std::move( std::unique_ptr<VVIA>( vvia ) ) ) );
 }
}

References SEG::A, Add(), SEG::B, LAYER_RANGE::IsMultilayer(), PNS::ITEM::Layers(), PNS::JOINT::LinkList(), m_joints, PNS::JOINT::Net(), PNS_HULL_MARGIN, PNS::JOINT::Pos(), PNS::SEGMENT::Seg(), PNS::ITEM::SOLID_T, LAYER_RANGE::Start(), and PNS::ITEM::VIA_T.

◆ followLine()

void PNS::NODE::followLine	(	LINKED_ITEM *	aCurrent,
		bool	aScanDirection,
		int &	aPos,
		int	aLimit,
		VECTOR2I *	aCorners,
		LINKED_ITEM **	aSegments,
		bool *	aArcReversed,
		bool &	aGuardHit,
		bool	aStopAtLockedJoints,
		bool	aFollowLockedSegments
	)

private

Definition at line 954 of file pns_node.cpp.

{
 bool prevReversed = false;
 
 const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
 
 for( int count = 0 ; ; ++count )
 {
 const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
 const JOINT* jt = FindJoint( p, aCurrent );
 
 assert( jt );
 
 aCorners[aPos] = jt->Pos();
 aSegments[aPos] = aCurrent;
 aArcReversed[aPos] = false;
 
 if( aCurrent->Kind() == ITEM::ARC_T )
 {
 if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) )
 || ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
 aArcReversed[aPos] = true;
 }
 
 aPos += ( aScanDirection ? 1 : -1 );
 
 if( count && guard == p )
 {
 if( aPos >= 0 && aPos < aLimit )
 aSegments[aPos] = nullptr;
 
 aGuardHit = true;
 break;
 }
 
 bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
 
 if( locked || !jt->IsLineCorner( aFollowLockedSegments ) || aPos < 0 || aPos == aLimit )
 break;
 
 aCurrent = jt->NextSegment( aCurrent, aFollowLockedSegments );
 
 prevReversed = ( aCurrent && jt->Pos() == aCurrent->Anchor( aScanDirection ) );
 }
}

References PNS::ITEM::Anchor(), PNS::ITEM::ARC_T, FindJoint(), PNS::JOINT::IsLineCorner(), PNS::JOINT::IsLocked(), PNS::ITEM::Kind(), locked, PNS::JOINT::NextSegment(), and PNS::JOINT::Pos().

Referenced by AssembleLine().

◆ GetClearance()

int PNS::NODE::GetClearance	(	const ITEM *	aA,
		const ITEM *	aB,
		bool	aUseClearanceEpsilon = `true`
	)		const

Definition at line 103 of file pns_node.cpp.

{
 if( !m_ruleResolver )
 return 100000;
 
 if( aA->IsVirtual() || aB->IsVirtual() )
 return 0;
 
 return m_ruleResolver->Clearance( aA, aB, aUseClearanceEpsilon );
}

References PNS::RULE_RESOLVER::Clearance(), PNS::ITEM::IsVirtual(), and m_ruleResolver.

Referenced by PNS::ITEM::collideSimple(), PNS::SHOVE::getClearance(), PNS::ROUTER::markViolations(), NearestObstacle(), PNS::DIFF_PAIR_PLACER::propagateDpHeadForces(), PNS::VIA::PushoutForce(), and PNS::LINE_PLACER::rhMarkObstacles().

◆ GetCollisionQueryScope()

COLLISION_QUERY_SCOPE PNS::NODE::GetCollisionQueryScope ( ) const

inline

Definition at line 421 of file pns_node.h.

 {
 return m_collisionQueryScope;
 }

References m_collisionQueryScope.

Referenced by PNS::ITEM::collideSimple(), and PNS::VIA::PushoutForce().

◆ GetHoleClearance()

int PNS::NODE::GetHoleClearance	(	const ITEM *	aA,
		const ITEM *	aB,
		bool	aUseClearanceEpsilon = `true`
	)		const

Definition at line 115 of file pns_node.cpp.

{
 if( !m_ruleResolver )
 return 0;
 
 if( aA->IsVirtual() || aB->IsVirtual() )
 return 0;
 
 return m_ruleResolver->HoleClearance( aA, aB, aUseClearanceEpsilon );
}

References PNS::RULE_RESOLVER::HoleClearance(), PNS::ITEM::IsVirtual(), and m_ruleResolver.

Referenced by PNS::ITEM::collideSimple(), PNS::SHOVE::getHoleClearance(), PNS::ROUTER::markViolations(), NearestObstacle(), and PNS::VIA::PushoutForce().

◆ GetHoleToHoleClearance()

int PNS::NODE::GetHoleToHoleClearance	(	const ITEM *	aA,
		const ITEM *	aB,
		bool	aUseClearanceEpsilon = `true`
	)		const

Return the pre-set worst case clearance between any pair of items.

Definition at line 127 of file pns_node.cpp.

{
 if( !m_ruleResolver )
 return 0;
 
 if( aA->IsVirtual() || aB->IsVirtual() )
 return 0;
 
 return m_ruleResolver->HoleToHoleClearance( aA, aB, aUseClearanceEpsilon );
}

References PNS::RULE_RESOLVER::HoleToHoleClearance(), PNS::ITEM::IsVirtual(), and m_ruleResolver.

Referenced by PNS::ITEM::collideSimple(), NearestObstacle(), and PNS::VIA::PushoutForce().

◆ GetMaxClearance()

int PNS::NODE::GetMaxClearance ( ) const

inline

Set the worst-case clearance between any pair of items.

Definition at line 180 of file pns_node.h.

References m_maxClearance.

◆ GetParent()

NODE * PNS::NODE::GetParent ( void ) const

inline

Check if this branch contains an updated version of the m_item from the root branch.

Definition at line 403 of file pns_node.h.

References m_parent.

◆ GetRuleResolver()

RULE_RESOLVER * PNS::NODE::GetRuleResolver ( ) const

inline

Return the number of joints.

Definition at line 197 of file pns_node.h.

References m_ruleResolver.

Referenced by PNS::TOPOLOGY::AssembleDiffPair(), PNS::ITEM::collideSimple(), and PNS::DIFF_PAIR_PLACER::FindDpPrimitivePair().

◆ GetUpdatedItems()

void PNS::NODE::GetUpdatedItems	(	ITEM_VECTOR &	aRemoved,
		ITEM_VECTOR &	aAdded
	)

Return the list of items removed and added in this branch with respect to the root branch.

Parameters

aRemoved	removed items.
aAdded	added items.

Definition at line 1403 of file pns_node.cpp.

{
 if( isRoot() )
 return;
 
 if( m_override.size() )
 aRemoved.reserve( m_override.size() );
 
 if( m_index->Size() )
 aAdded.reserve( m_index->Size() );
 
 for( ITEM* item : m_override )
 aRemoved.push_back( item );
 
 for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
 aAdded.push_back( *i );
}

References PNS::INDEX::begin(), PNS::INDEX::end(), isRoot(), m_index, m_override, and PNS::INDEX::Size().

Referenced by PNS::ROUTER::CommitRouting(), PNS::LINE_PLACER::FixRoute(), PNS::ROUTER::GetUpdatedItems(), PNS_LOG_PLAYER::ReplayLog(), PNS::LINE_PLACER::simplifyNewLine(), and PNS::ROUTER::updateView().

◆ HasChildren()

bool PNS::NODE::HasChildren ( ) const

inline

Definition at line 398 of file pns_node.h.

 {
 return !m_children.empty();
 }

References m_children.

◆ HitTest()

const ITEM_SET PNS::NODE::HitTest ( const VECTOR2I & aPoint ) const

Find all items that contain the point aPoint.

Parameters

aPoint the point.

Returns: the items.

Definition at line 546 of file pns_node.cpp.

{
 ITEM_SET items;
 
 // fixme: we treat a point as an infinitely small circle - this is inefficient.
 SHAPE_CIRCLE s( aPoint, 0 );
 HIT_VISITOR visitor( items, aPoint );
 visitor.SetWorld( this, nullptr );
 
 m_index->Query( &s, m_maxClearance, visitor );
 
 if( !isRoot() ) // fixme: could be made cleaner
 {
 ITEM_SET items_root;
 visitor.SetWorld( m_root, nullptr );
 HIT_VISITOR visitor_root( items_root, aPoint );
 m_root->m_index->Query( &s, m_maxClearance, visitor_root );
 
 for( ITEM* item : items_root.Items() )
 {
 if( !Overrides( item ) )
 items.Add( item );
 }
 }
 
 return items;
}

References PNS::ITEM_SET::Add(), isRoot(), PNS::ITEM_SET::Items(), m_index, m_maxClearance, m_root, Overrides(), PNS::INDEX::Query(), and PNS::OBSTACLE_VISITOR::SetWorld().

◆ isRoot()

bool PNS::NODE::isRoot ( ) const

inlineprivate

Definition at line 460 of file pns_node.h.

 {
 return m_parent == nullptr;
 }

References m_parent.

Referenced by AllItemsInNet(), Branch(), Commit(), doRemove(), Dump(), FindJoint(), GetUpdatedItems(), HitTest(), QueryColliding(), QueryJoints(), releaseGarbage(), touchJoint(), and unlinkParent().

◆ JointCount()

int PNS::NODE::JointCount ( ) const

inline

Return the number of nodes in the inheritance chain (wrs to the root node).

Definition at line 203 of file pns_node.h.

References m_joints.

Referenced by PNS::SHOVE::shoveMainLoop().

◆ KillChildren()

void PNS::NODE::KillChildren ( )

Definition at line 1470 of file pns_node.cpp.

{
 releaseChildren();
}

References releaseChildren().

Referenced by PNS::DIFF_PAIR_PLACER::AbortPlacement(), PNS::DP_MEANDER_PLACER::AbortPlacement(), PNS::LINE_PLACER::AbortPlacement(), PNS::MEANDER_PLACER::AbortPlacement(), PNS::LINE_PLACER::CommitPlacement(), PNS::COMPONENT_DRAGGER::Drag(), PNS::DIFF_PAIR_PLACER::initPlacement(), PNS::LINE_PLACER::initPlacement(), PNS::SHOVE::RewindSpringbackTo(), and PNS::LINE_PLACER::UnfixRoute().

◆ linkJoint()

void PNS::NODE::linkJoint	(	const VECTOR2I &	aPos,
		const LAYER_RANGE &	aLayers,
		int	aNet,
		ITEM *	aWhere
	)

private

Unlink an item from a joint.

Definition at line 1299 of file pns_node.cpp.

{
 JOINT& jt = touchJoint( aPos, aLayers, aNet );
 
 jt.Link( aWhere );
}

References PNS::JOINT::Link(), and touchJoint().

Referenced by addArc(), addSegment(), addSolid(), addVia(), and rebuildJoint().

◆ LockJoint()

void PNS::NODE::LockJoint	(	const VECTOR2I &	aPos,
		const ITEM *	aItem,
		bool	aLock
	)

Definition at line 1231 of file pns_node.cpp.

{
 JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
 jt.Lock( aLock );
}

References PNS::ITEM::Layers(), PNS::JOINT::Lock(), PNS::ITEM::Net(), and touchJoint().

Referenced by PNS::SHOVE::ShoveLines().

◆ NearestObstacle()

NODE::OPT_OBSTACLE PNS::NODE::NearestObstacle	(	const LINE *	aLine,
		int	aKindMask = `ITEM::ANY_T`,
		const std::set< ITEM * > *	aRestrictedSet = `nullptr`,
		bool	aUseClearanceEpsilon = `true`
	)

Follow the line in search of an obstacle that is nearest to the starting to the line's starting point.

Parameters

aLine	the item to find collisions with
aKindMask	mask of obstacle types to take into account
aRestrictedSet	is an optional set of items that should be considered as obstacles
aUseClearanceEpsilon	determines if the epsilon is subtracted from the hull size

Returns: the obstacle, if found, otherwise empty.

Definition at line 303 of file pns_node.cpp.

{
 OBSTACLES obstacleList;
 obstacleList.reserve( 100 );
 
 for( int i = 0; i < aLine->CLine().SegmentCount(); i++ )
 {
 // Note: Clearances between &s and other items are cached,
 // which means they'll be the same for all segments in the line.
 // Disabling the cache will lead to slowness.
 
 const SEGMENT s( *aLine, aLine->CLine().CSegment( i ) );
 QueryColliding( &s, obstacleList, aKindMask );
 }
 
 if( aLine->EndsWithVia() )
 QueryColliding( &aLine->Via(), obstacleList, aKindMask );
 
 if( obstacleList.empty() )
 return OPT_OBSTACLE();
 
 OBSTACLE nearest;
 nearest.m_head = nullptr;
 nearest.m_item = nullptr;
 nearest.m_distFirst = INT_MAX;
 nearest.m_maxFanoutWidth = 0;
 
 auto updateNearest =
 [&]( const SHAPE_LINE_CHAIN::INTERSECTION& pt, ITEM* obstacle,
 const SHAPE_LINE_CHAIN& hull, bool isHole )
 {
 int dist = aLine->CLine().PathLength( pt.p, pt.index_their );
 
 if( dist < nearest.m_distFirst )
 {
 nearest.m_distFirst = dist;
 nearest.m_ipFirst = pt.p;
 nearest.m_item = obstacle;
 nearest.m_hull = hull;
 
 obstacle->Mark( isHole ? obstacle->Marker() | MK_HOLE
 : obstacle->Marker() & ~MK_HOLE );
 }
 };
 
 SHAPE_LINE_CHAIN obstacleHull;
 DEBUG_DECORATOR* debugDecorator = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
 std::vector<SHAPE_LINE_CHAIN::INTERSECTION> intersectingPts;
 int layer = aLine->Layer();
 
 for( const OBSTACLE& obstacle : obstacleList )
 {
 if( aRestrictedSet && aRestrictedSet->find( obstacle.m_item ) == aRestrictedSet->end() )
 continue;
 
 int clearance =
 GetClearance( obstacle.m_item, aLine, aUseClearanceEpsilon ) + aLine->Width() / 2;
 
 obstacleHull = obstacle.m_item->Hull( clearance, 0, layer );
 //debugDecorator->AddLine( obstacleHull, 2, 40000, "obstacle-hull-test" );
 //debugDecorator->AddLine( aLine->CLine(), 5, 40000, "obstacle-test-line" );
 
 intersectingPts.clear();
 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
 
 for( const auto& ip : intersectingPts )
 {
 //debugDecorator->AddPoint( ip.p, ip.valid?3:6, 100000, (const char *) wxString::Format("obstacle-isect-point-%d" ).c_str() );
 if( ip.valid )
 updateNearest( ip, obstacle.m_item, obstacleHull, false );
 }
 
 if( aLine->EndsWithVia() )
 {
 const VIA& via = aLine->Via();
 // Don't use via.Drill(); it doesn't include the plating thickness
 
 int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
 
 int viaClearance = GetClearance( obstacle.m_item, &via, aUseClearanceEpsilon )
 + via.Diameter() / 2;
 int holeClearance =
 GetHoleClearance( obstacle.m_item, &via, aUseClearanceEpsilon ) + viaHoleRadius;
 
 if( holeClearance > viaClearance )
 viaClearance = holeClearance;
 
 obstacleHull = obstacle.m_item->Hull( viaClearance, 0, layer );
 //debugDecorator->AddLine( obstacleHull, 3 );
 
 intersectingPts.clear();
 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
 
 // obstacleHull.Intersect( aLine->CLine(), intersectingPts, true );
 
 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
 updateNearest( ip, obstacle.m_item, obstacleHull, false );
 }
 
 if( ( m_collisionQueryScope == CQS_ALL_RULES
 || !ROUTER::GetInstance()->GetInterface()->IsFlashedOnLayer( obstacle.m_item,
 layer ) )
 && obstacle.m_item->Hole() )
 {
 clearance = GetHoleClearance( obstacle.m_item, aLine, aUseClearanceEpsilon );
 int copperClearance = GetClearance( obstacle.m_item, aLine, aUseClearanceEpsilon );
 
 clearance = std::max( clearance, copperClearance );
 
 obstacleHull = obstacle.m_item->HoleHull( clearance, aLine->Width(), layer );
 
 intersectingPts.clear();
 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
 
 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
 updateNearest( ip, obstacle.m_item, obstacleHull, true );
 
 if( aLine->EndsWithVia() )
 {
 const VIA& via = aLine->Via();
 // Don't use via.Drill(); it doesn't include the plating thickness
 int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
 
 int viaClearance = GetClearance( obstacle.m_item, &via, aUseClearanceEpsilon )
 + via.Diameter() / 2;
 int holeClearance = GetHoleClearance( obstacle.m_item, &via, aUseClearanceEpsilon )
 + viaHoleRadius;
 int holeToHole =
 GetHoleToHoleClearance( obstacle.m_item, &via, aUseClearanceEpsilon )
 + viaHoleRadius;
 
 if( holeClearance > viaClearance )
 viaClearance = holeClearance;
 
 if( holeToHole > viaClearance )
 viaClearance = holeToHole;
 
 obstacleHull = obstacle.m_item->Hull( viaClearance, 0, layer );
 //debugDecorator->AddLine( obstacleHull, 5 );
 
 intersectingPts.clear();
 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
 
 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
 updateNearest( ip, obstacle.m_item, obstacleHull, true );
 }
 }
 }
 
 if( nearest.m_distFirst == INT_MAX )
 nearest.m_item = obstacleList[0].m_item;
 
 return nearest;
}

References PNS::LINE::CLine(), CQS_ALL_RULES, SHAPE_LINE_CHAIN::CSegment(), PNS::LINE::EndsWithVia(), GetClearance(), PNS::ROUTER_IFACE::GetDebugDecorator(), GetHoleClearance(), GetHoleToHoleClearance(), PNS::ROUTER::GetInstance(), PNS::ROUTER::GetInterface(), PNS::HullIntersection(), SHAPE_LINE_CHAIN::INTERSECTION::index_their, PNS::ITEM::Layer(), m_collisionQueryScope, PNS::OBSTACLE::m_distFirst, PNS::OBSTACLE::m_head, PNS::OBSTACLE::m_hull, PNS::OBSTACLE::m_ipFirst, PNS::OBSTACLE::m_item, PNS::OBSTACLE::m_maxFanoutWidth, PNS::MK_HOLE, SHAPE_LINE_CHAIN::INTERSECTION::p, SHAPE_LINE_CHAIN::PathLength(), QueryColliding(), via, PNS::LINE::Via(), and PNS::LINE::Width().

Referenced by PNS::LINE::ClipToNearestObstacle(), PNS::WALKAROUND::nearestObstacle(), PNS::LINE_PLACER::rhMarkObstacles(), and PNS::SHOVE::shoveIteration().

◆ operator=()

NODE & PNS::NODE::operator= ( const NODE & aB )

private

Try to find matching joint and creates a new one if not found.

◆ Overrides()

bool PNS::NODE::Overrides ( ITEM * aItem ) const

inline

Definition at line 409 of file pns_node.h.

 {
 return m_override.find( aItem ) != m_override.end();
 }

References m_override.

Referenced by AllItemsInNet(), HitTest(), QueryJoints(), and PNS::OBSTACLE_VISITOR::visit().

◆ QueryColliding()

int PNS::NODE::QueryColliding	(	const ITEM *	aItem,
		NODE::OBSTACLES &	aObstacles,
		int	aKindMask = `ITEM::ANY_T`,
		int	aLimitCount = `-1`,
		bool	aDifferentNetsOnly = `true`,
		int	aOverrideClearance = `-1`
	)

Find items colliding (closer than clearance) with the item aItem.

Parameters

aItem	item to check collisions against
aObstacles	set of colliding objects found
aKindMask	mask of obstacle types to take into account
aLimitCount	stop looking for collisions after finding this number of colliding items

Returns: number of obstacles found

By default, virtual items cannot collide

Definition at line 272 of file pns_node.cpp.

{
 if( aItem->IsVirtual() )
 return 0;
 
 DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly,
 aOverrideClearance );
 
#ifdef DEBUG
 assert( allocNodes.find( this ) != allocNodes.end() );
#endif
 
 visitor.SetCountLimit( aLimitCount );
 visitor.SetWorld( this, nullptr );
 
 // first, look for colliding items in the local index
 m_index->Query( aItem, m_maxClearance, visitor );
 
 // if we haven't found enough items, look in the root branch as well.
 if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
 {
 visitor.SetWorld( m_root, this );
 m_root->m_index->Query( aItem, m_maxClearance, visitor );
 }
 
 return aObstacles.size();
}

References isRoot(), PNS::ITEM::IsVirtual(), m_index, PNS::NODE::DEFAULT_OBSTACLE_VISITOR::m_matchCount, m_maxClearance, m_root, PNS::INDEX::Query(), PNS::NODE::DEFAULT_OBSTACLE_VISITOR::SetCountLimit(), and PNS::OBSTACLE_VISITOR::SetWorld().

Referenced by PNS::TOPOLOGY::AssembleCluster(), CheckColliding(), PNS::ROUTER::markViolations(), and NearestObstacle().

◆ QueryEdgeExclusions()

bool PNS::NODE::QueryEdgeExclusions ( const VECTOR2I & aPos ) const

Definition at line 746 of file pns_node.cpp.

{
 for( const std::unique_ptr<SHAPE>& edgeExclusion : m_edgeExclusions )
 {
 if( edgeExclusion->Collide( aPos ) )
 return true;
 }
 
 return false;
}

References m_edgeExclusions.

Referenced by PNS::ITEM::collideSimple().

◆ QueryJoints()

int PNS::NODE::QueryJoints	(	const BOX2I &	aBox,
		std::vector< JOINT * > &	aJoints,
		LAYER_RANGE	aLayerMask = `LAYER_RANGE::All()`,
		int	aKindMask = `ITEM::ANY_T`
	)

Definition at line 1600 of file pns_node.cpp.

{
 int n = 0;
 
 aJoints.clear();
 
 for( JOINT_MAP::value_type& j : m_joints )
 {
 if( !j.second.Layers().Overlaps( aLayerMask ) )
 continue;
 
 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
 {
 aJoints.push_back( &j.second );
 n++;
 }
 }
 
 if( isRoot() )
 return n;
 
 for( JOINT_MAP::value_type& j : m_root->m_joints )
 {
 if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
 {
 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
 {
 aJoints.push_back( &j.second );
 n++;
 }
 }
 }
 
 return n;
}

References BOX2< Vec >::Contains(), isRoot(), m_joints, m_root, and Overrides().

Referenced by PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), and PNS::COMPONENT_DRAGGER::Start().

◆ rebuildJoint()

void PNS::NODE::rebuildJoint	(	JOINT *	aJoint,
		ITEM *	aItem
	)

private

Definition at line 793 of file pns_node.cpp.

{
 // We have to split a single joint (associated with a via or a pad, binding together multiple
 // layers) into multiple independent joints. As I'm a lazy bastard, I simply delete the
 // via/solid and all its links and re-insert them.
 
 JOINT::LINKED_ITEMS links( aJoint->LinkList() );
 JOINT::HASH_TAG tag;
 int net = aItem->Net();
 
 tag.net = net;
 tag.pos = aJoint->Pos();
 
 bool split;
 
 do
 {
 split = false;
 auto range = m_joints.equal_range( tag );
 
 if( range.first == m_joints.end() )
 break;
 
 // find and remove all joints containing the via to be removed
 
 for( auto f = range.first; f != range.second; ++f )
 {
 if( aItem->LayersOverlap( &f->second ) )
 {
 m_joints.erase( f );
 split = true;
 break;
 }
 }
 } while( split );
 
 // and re-link them, using the former via's link list
 for( ITEM* link : links )
 {
 if( link != aItem )
 linkJoint( tag.pos, link->Layers(), net, link );
 }
}

References PNS::ITEM::LayersOverlap(), linkJoint(), PNS::JOINT::LinkList(), m_joints, PNS::ITEM::Net(), PNS::JOINT::HASH_TAG::net, PNS::JOINT::HASH_TAG::pos, PNS::JOINT::Pos(), and split().

Referenced by removeSolidIndex(), and removeViaIndex().

◆ releaseChildren()

void PNS::NODE::releaseChildren ( )

private

Definition at line 1422 of file pns_node.cpp.

{
 // copy the kids as the NODE destructor erases the item from the parent node.
 std::set<NODE*> kids = m_children;
 
 for( NODE* node : kids )
 {
 node->releaseChildren();
 delete node;
 }
}

References m_children.

Referenced by Commit(), and KillChildren().

◆ releaseGarbage()

void PNS::NODE::releaseGarbage ( )

private

Definition at line 1435 of file pns_node.cpp.

{
 if( !isRoot() )
 return;
 
 for( ITEM* item : m_garbageItems )
 {
 if( !item->BelongsTo( this ) )
 delete item;
 }
 
 m_garbageItems.clear();
}

References isRoot(), and m_garbageItems.

Referenced by Commit(), and ~NODE().

◆ Remove() [1/6]

void PNS::NODE::Remove ( ARC * aArc )

Remove an item from this branch.

Definition at line 893 of file pns_node.cpp.

{
 removeArcIndex( aArc );
 doRemove( aArc );
}

References doRemove(), and removeArcIndex().

Referenced by Commit(), PNS::COMPONENT_DRAGGER::Drag(), PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragViaMarkObstacles(), PNS::DRAGGER::dragViaWalkaround(), PNS::DRAGGER::dragWalkaround(), PNS::SHOVE::pushOrShoveVia(), Remove(), RemoveByMarker(), PNS::LINE_PLACER::removeLoops(), Replace(), PNS::SHOVE::SetInitialLine(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), PNS::LINE_PLACER::SplitAdjacentSegments(), PNS::DP_MEANDER_PLACER::Start(), PNS::MEANDER_PLACER::Start(), and PNS::MEANDER_SKEW_PLACER::Start().

◆ Remove() [2/6]

void PNS::NODE::Remove ( ITEM * aItem )

Definition at line 900 of file pns_node.cpp.

{
 switch( aItem->Kind() )
 {
 case ITEM::ARC_T:
 Remove( static_cast<ARC*>( aItem ) );
 break;
 
 case ITEM::SOLID_T:
 Remove( static_cast<SOLID*>( aItem ) );
 break;
 
 case ITEM::SEGMENT_T:
 Remove( static_cast<SEGMENT*>( aItem ) );
 break;
 
 case ITEM::LINE_T:
 {
 LINE* l = static_cast<LINE*>( aItem );
 
 for ( LINKED_ITEM* s : l->Links() )
 Remove( s );
 
 break;
 }
 
 case ITEM::VIA_T:
 Remove( static_cast<VIA*>( aItem ) );
 break;
 
 default:
 break;
 }
}

References PNS::ITEM::ARC_T, PNS::ITEM::Kind(), PNS::ITEM::LINE_T, PNS::LINK_HOLDER::Links(), Remove(), PNS::ITEM::SEGMENT_T, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

◆ Remove() [3/6]

void PNS::NODE::Remove ( LINE & aLine )

Removes a line from this branch.

Parameters

aLine item to remove

Definition at line 936 of file pns_node.cpp.

{
 // LINE does not have a separate remover, as LINEs are never truly a member of the tree
 std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
 
 for( LINKED_ITEM* li : segRefs )
 {
 if( li->OfKind( ITEM::SEGMENT_T ) )
 Remove( static_cast<SEGMENT*>( li ) );
 else if( li->OfKind( ITEM::ARC_T ) )
 Remove( static_cast<ARC*>( li ) );
 }
 
 aLine.SetOwner( nullptr );
 aLine.ClearLinks();
}

References PNS::ITEM::ARC_T, PNS::LINK_HOLDER::ClearLinks(), PNS::LINK_HOLDER::Links(), Remove(), PNS::ITEM::SEGMENT_T, and PNS::ITEM::SetOwner().

◆ Remove() [4/6]

void PNS::NODE::Remove ( SEGMENT * aSegment )

Definition at line 886 of file pns_node.cpp.

{
 removeSegmentIndex( aSegment );
 doRemove( aSegment );
}

References doRemove(), and removeSegmentIndex().

◆ Remove() [5/6]

void PNS::NODE::Remove ( SOLID * aSolid )

Definition at line 872 of file pns_node.cpp.

{
 removeSolidIndex( aSolid );
 doRemove( aSolid );
}

References doRemove(), and removeSolidIndex().

◆ Remove() [6/6]

void PNS::NODE::Remove ( VIA * aVia )

Definition at line 879 of file pns_node.cpp.

{
 removeViaIndex( aVia );
 doRemove( aVia );
}

References doRemove(), and removeViaIndex().

◆ removeArcIndex()

void PNS::NODE::removeArcIndex ( ARC * aVia )

private

Definition at line 786 of file pns_node.cpp.

{
 unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
 unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
}

References PNS::ARC::Anchor(), PNS::ITEM::Layers(), PNS::ITEM::Net(), and unlinkJoint().

Referenced by Remove().

◆ RemoveByMarker()

void PNS::NODE::RemoveByMarker ( int aMarker )

Definition at line 1515 of file pns_node.cpp.

{
 std::vector<ITEM*> garbage;
 
 for( ITEM* item : *m_index )
 {
 if( item->Marker() & aMarker )
 garbage.emplace_back( item );
 }
 
 for( ITEM* item : garbage )
 Remove( item );
}

References m_index, and Remove().

Referenced by PNS::SHOVE::ShoveLines(), and PNS::SHOVE::ShoveMultiLines().

◆ removeSegmentIndex()

void PNS::NODE::removeSegmentIndex ( SEGMENT * aSeg )

private

Definition at line 779 of file pns_node.cpp.

{
 unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
 unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
}

References SEG::A, SEG::B, PNS::ITEM::Layers(), PNS::ITEM::Net(), PNS::SEGMENT::Seg(), and unlinkJoint().

Referenced by Remove().

◆ removeSolidIndex()

void PNS::NODE::removeSolidIndex ( SOLID * aSeg )

private

Definition at line 846 of file pns_node.cpp.

{
 if( !aSolid->IsRoutable() )
 return;
 
 // fixme: redundant code
 JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
 assert( jt );
 rebuildJoint( jt, aSolid );
}

References FindJoint(), PNS::ITEM::IsRoutable(), PNS::ITEM::Layers(), PNS::ITEM::Net(), PNS::SOLID::Pos(), rebuildJoint(), and LAYER_RANGE::Start().

Referenced by Remove().

◆ removeViaIndex()

void PNS::NODE::removeViaIndex ( VIA * aVia )

private

Definition at line 838 of file pns_node.cpp.

{
 JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
 assert( jt );
 rebuildJoint( jt, aVia );
}

References FindJoint(), PNS::ITEM::Layers(), PNS::ITEM::Net(), PNS::VIA::Pos(), rebuildJoint(), and LAYER_RANGE::Start().

Referenced by Remove().

◆ Replace() [1/2]

void PNS::NODE::Replace	(	ITEM *	aOldItem,
		std::unique_ptr< ITEM >	aNewItem
	)

Replace an item with another one.

Parameters

aOldItem	item to be removed
aNewItem	item add instead

Definition at line 858 of file pns_node.cpp.

{
 Remove( aOldItem );
 Add( std::move( aNewItem ) );
}

References Add(), and Remove().

Referenced by PNS::SHOVE::replaceItems(), and PNS::SHOVE::replaceLine().

◆ Replace() [2/2]

void PNS::NODE::Replace	(	LINE &	aOldLine,
		LINE &	aNewLine
	)

Definition at line 865 of file pns_node.cpp.

{
 Remove( aOldLine );
 Add( aNewLine );
}

References Add(), and Remove().

◆ SetCollisionQueryScope()

void PNS::NODE::SetCollisionQueryScope ( COLLISION_QUERY_SCOPE aScope )

inline

Definition at line 416 of file pns_node.h.

 {
 m_collisionQueryScope = aScope;
 }

References m_collisionQueryScope.

◆ SetMaxClearance()

void PNS::NODE::SetMaxClearance ( int aClearance )

inline

Assign a clearance resolution function object.

Definition at line 186 of file pns_node.h.

References m_maxClearance.

Referenced by PNS_KICAD_IFACE_BASE::SyncWorld().

◆ SetRuleResolver()

void PNS::NODE::SetRuleResolver ( RULE_RESOLVER * aFunc )

inline

Definition at line 192 of file pns_node.h.

 {
 m_ruleResolver = aFunc;
 }

References m_ruleResolver.

Referenced by PNS_KICAD_IFACE_BASE::SyncWorld().

◆ touchJoint()

JOINT & PNS::NODE::touchJoint	(	const VECTOR2I &	aPos,
		const LAYER_RANGE &	aLayers,
		int	aNet
	)

private

Touch a joint and links it to an m_item.

Definition at line 1238 of file pns_node.cpp.

{
 JOINT::HASH_TAG tag;
 
 tag.pos = aPos;
 tag.net = aNet;
 
 // try to find the joint in this node.
 JOINT_MAP::iterator f = m_joints.find( tag );
 
 std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
 
 // not found and we are not root? find in the root and copy results here.
 if( f == m_joints.end() && !isRoot() )
 {
 range = m_root->m_joints.equal_range( tag );
 
 for( f = range.first; f != range.second; ++f )
 m_joints.insert( *f );
 }
 
 // now insert and combine overlapping joints
 JOINT jt( aPos, aLayers, aNet );
 
 bool merged;
 
 do
 {
 merged = false;
 range = m_joints.equal_range( tag );
 
 if( range.first == m_joints.end() )
 break;
 
 for( f = range.first; f != range.second; ++f )
 {
 if( aLayers.Overlaps( f->second.Layers() ) )
 {
 jt.Merge( f->second );
 m_joints.erase( f );
 merged = true;
 break;
 }
 }
 } while( merged );
 
 return m_joints.insert( TagJointPair( tag, jt ) )->second;
}

References isRoot(), m_joints, m_root, PNS::JOINT::Merge(), PNS::JOINT::HASH_TAG::net, LAYER_RANGE::Overlaps(), and PNS::JOINT::HASH_TAG::pos.

Referenced by linkJoint(), LockJoint(), and unlinkJoint().

◆ unlinkJoint()

void PNS::NODE::unlinkJoint	(	const VECTOR2I &	aPos,
		const LAYER_RANGE &	aLayers,
		int	aNet,
		ITEM *	aWhere
	)

private

Helpers for adding/removing items.

Definition at line 1307 of file pns_node.cpp.

{
 // fixme: remove dangling joints
 JOINT& jt = touchJoint( aPos, aLayers, aNet );
 
 jt.Unlink( aWhere );
}

References touchJoint(), and PNS::JOINT::Unlink().

Referenced by removeArcIndex(), and removeSegmentIndex().

◆ unlinkParent()

void PNS::NODE::unlinkParent ( )

private

Definition at line 176 of file pns_node.cpp.

{
 if( isRoot() )
 return;
 
 m_parent->m_children.erase( this );
}

References isRoot(), m_children, and m_parent.

Referenced by ~NODE().

Member Data Documentation

◆ m_children

std::set<NODE*> PNS::NODE::m_children

private

list of nodes branched from this one

Definition at line 487 of file pns_node.h.

Referenced by Branch(), HasChildren(), releaseChildren(), unlinkParent(), and ~NODE().

◆ m_collisionQueryScope

COLLISION_QUERY_SCOPE PNS::NODE::m_collisionQueryScope

private

Definition at line 502 of file pns_node.h.

Referenced by Branch(), GetCollisionQueryScope(), NearestObstacle(), NODE(), and SetCollisionQueryScope().

◆ m_depth

int PNS::NODE::m_depth

private

depth of the node (number of parent nodes in the inheritance chain)

Definition at line 495 of file pns_node.h.

Referenced by Branch(), Depth(), and NODE().

◆ m_edgeExclusions

std::vector< std::unique_ptr<SHAPE> > PNS::NODE::m_edgeExclusions

private

Definition at line 498 of file pns_node.h.

Referenced by AddEdgeExclusion(), and QueryEdgeExclusions().

◆ m_garbageItems

std::unordered_set<ITEM*> PNS::NODE::m_garbageItems

private

Definition at line 500 of file pns_node.h.

Referenced by doRemove(), and releaseGarbage().

◆ m_index

INDEX* PNS::NODE::m_index

private

Geometric/Net index of the items.

Definition at line 494 of file pns_node.h.

Referenced by addArc(), addSegment(), addSolid(), addVia(), AllItemsInNet(), Branch(), ClearRanks(), Commit(), doRemove(), FindItemByParent(), GetUpdatedItems(), HitTest(), NODE(), QueryColliding(), RemoveByMarker(), and ~NODE().

◆ m_joints

JOINT_MAP PNS::NODE::m_joints

private

hash table with the joints, linking the items.

Joints are hashed by their position, layer set and net.

Definition at line 482 of file pns_node.h.

Referenced by Branch(), Dump(), FindJoint(), FixupVirtualVias(), JointCount(), QueryJoints(), rebuildJoint(), touchJoint(), and ~NODE().

◆ m_maxClearance

int PNS::NODE::m_maxClearance

private

worst case item-item clearance

Definition at line 492 of file pns_node.h.

Referenced by Branch(), GetMaxClearance(), HitTest(), NODE(), QueryColliding(), and SetMaxClearance().

◆ m_override

std::unordered_set<ITEM*> PNS::NODE::m_override

private

hash of root's items that have been changed in this node

Definition at line 489 of file pns_node.h.

Referenced by Branch(), Commit(), doRemove(), GetUpdatedItems(), and Overrides().

◆ m_parent

NODE* PNS::NODE::m_parent

private

node this node was branched from

Definition at line 485 of file pns_node.h.

Referenced by Branch(), GetParent(), isRoot(), NODE(), and unlinkParent().

◆ m_root

NODE* PNS::NODE::m_root

private

root node of the whole hierarchy

Definition at line 486 of file pns_node.h.

Referenced by AllItemsInNet(), Branch(), doRemove(), Dump(), FindJoint(), HitTest(), NODE(), QueryColliding(), QueryJoints(), and touchJoint().

◆ m_ruleResolver

RULE_RESOLVER* PNS::NODE::m_ruleResolver

private

Design rules resolver.

Definition at line 493 of file pns_node.h.

Referenced by Branch(), GetClearance(), GetHoleClearance(), GetHoleToHoleClearance(), GetRuleResolver(), NODE(), and SetRuleResolver().

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

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ITEM_VECTOR

◆ JOINT_MAP

◆ OBSTACLES

◆ OPT_OBSTACLE

◆ TagJointPair

Member Enumeration Documentation

◆ COLLISION_QUERY_SCOPE

Constructor & Destructor Documentation

◆ NODE() [1/2]

◆ ~NODE()

◆ NODE() [2/2]

Member Function Documentation

◆ Add() [1/6]

◆ Add() [2/6]

◆ Add() [3/6]

◆ Add() [4/6]

◆ Add() [5/6]

◆ Add() [6/6]

◆ addArc()

◆ AddEdgeExclusion()

◆ addSegment()

◆ addSolid()

◆ addVia()

◆ AllItemsInNet()

◆ AssembleLine()

◆ Branch()

◆ CheckColliding() [1/2]

◆ CheckColliding() [2/2]

◆ ClearRanks()

◆ Commit()

◆ Depth()

◆ doRemove()

◆ Dump()

◆ FindItemByParent()

◆ FindJoint() [1/2]

◆ FindJoint() [2/2]

◆ FindLineEnds()

◆ FindLinesBetweenJoints()

◆ findRedundantArc() [1/2]

◆ findRedundantArc() [2/2]

◆ findRedundantSegment() [1/2]

◆ findRedundantSegment() [2/2]

◆ FixupVirtualVias()

◆ followLine()

◆ GetClearance()

◆ GetCollisionQueryScope()

◆ GetHoleClearance()

◆ GetHoleToHoleClearance()

◆ GetMaxClearance()

◆ GetParent()

◆ GetRuleResolver()

◆ GetUpdatedItems()

◆ HasChildren()

◆ HitTest()

◆ isRoot()

◆ JointCount()

◆ KillChildren()

◆ linkJoint()

◆ LockJoint()

◆ NearestObstacle()

◆ operator=()

◆ Overrides()

◆ QueryColliding()

◆ QueryEdgeExclusions()

◆ QueryJoints()

◆ rebuildJoint()

◆ releaseChildren()

◆ releaseGarbage()

◆ Remove() [1/6]

◆ Remove() [2/6]

◆ Remove() [3/6]

◆ Remove() [4/6]