KiCad PCB EDA Suite
PNS::NODE Class Reference

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< OBSTACLEOPT_OBSTACLE
 
typedef std::vector< ITEM * > ITEM_VECTOR
 
typedef std::vector< OBSTACLEOBSTACLES
 

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_RESOLVERGetRuleResolver () 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)
 
NODEBranch ()
 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...
 
JOINTFindJoint (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)
 
JOINTFindJoint (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)
 
ITEMFindItemByParent (const BOARD_ITEM *aParent)
 
bool HasChildren () const
 
NODEGetParent () 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_HASHJOINT_MAP
 
typedef JOINT_MAP::value_type TagJointPair
 

Private Member Functions

 NODE (const NODE &aB)
 nodes are not copyable More...
 
NODEoperator= (const NODE &aB)
 Try to find matching joint and creates a new one if not found. More...
 
JOINTtouchJoint (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
 
SEGMENTfindRedundantSegment (const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
 
SEGMENTfindRedundantSegment (SEGMENT *aSeg)
 
ARCfindRedundantArc (const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
 
ARCfindRedundantArc (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...
 
NODEm_parent
 node this node was branched from More...
 
NODEm_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_RESOLVERm_ruleResolver
 Design rules resolver. More...
 
INDEXm_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

< 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.

161 {
162 CQS_ALL_RULES = 1,
164 };
@ CQS_IGNORE_HOLE_CLEARANCE
check everything except hole2hole / hole2copper
Definition: pns_node.h:163
@ CQS_ALL_RULES
check all rules
Definition: pns_node.h:162

Constructor & Destructor Documentation

◆ NODE() [1/2]

PNS::NODE::NODE ( )

Definition at line 54 of file pns_node.cpp.

55{
56 m_depth = 0;
57 m_root = this;
58 m_parent = nullptr;
59 m_maxClearance = 800000; // fixme: depends on how thick traces are.
60 m_ruleResolver = nullptr;
61 m_index = new INDEX;
63
64#ifdef DEBUG
65 allocNodes.insert( this );
66#endif
67}
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:486
COLLISION_QUERY_SCOPE m_collisionQueryScope
Definition: pns_node.h:502
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:494
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:492
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:495
NODE * m_parent
node this node was branched from
Definition: pns_node.h:485
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:493

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.

71{
72 if( !m_children.empty() )
73 {
74 wxLogTrace( wxT( "PNS" ), wxT( "attempting to free a node that has kids." ) );
75 assert( false );
76 }
77
78#ifdef DEBUG
79 if( allocNodes.find( this ) == allocNodes.end() )
80 {
81 wxLogTrace( wxT( "PNS" ), wxT( "attempting to free an already-free'd node." ) );
82 assert( false );
83 }
84
85 allocNodes.erase( this );
86#endif
87
88 m_joints.clear();
89
90 for( ITEM* item : *m_index )
91 {
92 if( item->BelongsTo( this ) )
93 delete item;
94 }
95
98
99 delete m_index;
100}
void releaseGarbage()
Definition: pns_node.cpp:1435
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:487
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:482
void unlinkParent()
Definition: pns_node.cpp:176

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.

607{
608 assert( !aLine.IsLinked() );
609
610 SHAPE_LINE_CHAIN& l = aLine.Line();
611
612 for( size_t i = 0; i < l.ArcCount(); i++ )
613 {
614 auto s = l.Arc( i );
615 ARC* rarc;
616
617 if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(),
618 aLine.Net() ) ) )
619 {
620 aLine.Link( rarc );
621 }
622 else
623 {
624 auto newarc = std::make_unique< ARC >( aLine, s );
625 aLine.Link( newarc.get() );
626 Add( std::move( newarc ), true );
627 }
628 }
629
630 for( int i = 0; i < l.SegmentCount(); i++ )
631 {
632 if( l.IsArcSegment( i ) )
633 continue;
634
635 SEG s = l.CSegment( i );
636
637 if( s.A != s.B )
638 {
639 SEGMENT* rseg;
640
641 if( !aAllowRedundant && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(),
642 aLine.Net() ) ) )
643 {
644 // another line could be referencing this segment too :(
645 aLine.Link( rseg );
646 }
647 else
648 {
649 std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
650 aLine.Link( newseg.get() );
651 Add( std::move( newseg ), true );
652 }
653 }
654 }
655}
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:667
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1565
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1530
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_ARC & Arc(size_t aArc) const
int SegmentCount() const
Return the number of segments in this line chain.
size_t ArcCount() const
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const

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.

696{
697 const SHAPE_ARC& arc = aArc->CArc();
698
699 if( !aAllowRedundant && findRedundantArc( arc.GetP0(), arc.GetP1(), aArc->Layers(),
700 aArc->Net() ) )
701 {
702 return false;
703 }
704
705 aArc->SetOwner( this );
706 addArc( aArc.release() );
707 return true;
708}
void addArc(ARC *aVia)
Definition: pns_node.cpp:686
const VECTOR2I & GetP1() const
Definition: shape_arc.h:113
const VECTOR2I & GetP0() const
Definition: shape_arc.h:112

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.

712{
713 switch( aItem->Kind() )
714 {
715 case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
716 case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
717 case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
718
719 case ITEM::ARC_T:
720 //todo(snh): Add redundant search
721 Add( ItemCast<ARC>( std::move( aItem ) ) );
722 break;
723
724 case ITEM::LINE_T:
725 {
726 // fixme(twl): I don't like unique_ptr in this methods as the router has its own garbage
727 // collecting mechanism. This particular case is used exclusively in
728 // ROUTER::GetUpdatedItems() for dumping debug logs. Please don't call Add ( up<LINE> )
729 // otherwise, dragons live here.
730 LINE *l = static_cast<LINE*>( aItem.get() );
731 Add( *l );
732 break;
733 }
734 default:
735 assert( false );
736 }
737}
@ SOLID_T
Definition: pns_item.h:63
@ LINE_T
Definition: pns_item.h:64
@ SEGMENT_T
Definition: pns_item.h:66

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
aSegmentitem to add.
aAllowRedundantif 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.

668{
669 if( aSegment->Seg().A == aSegment->Seg().B )
670 {
671 wxLogTrace( wxT( "PNS" ),
672 wxT( "attempting to add a segment with same end coordinates, ignoring." ) );
673 return false;
674 }
675
676 if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
677 return false;
678
679 aSegment->SetOwner( this );
680 addSegment( aSegment.release() );
681
682 return true;
683}
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:658

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.

585{
586 aSolid->SetOwner( this );
587 addSolid( aSolid.release() );
588}
void addSolid(SOLID *aSeg)
Definition: pns_node.cpp:575

References addSolid().

◆ Add() [6/6]

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

Definition at line 599 of file pns_node.cpp.

600{
601 aVia->SetOwner( this );
602 addVia( aVia.release() );
603}
void addVia(VIA *aVia)
Definition: pns_node.cpp:591

References addVia().

◆ addArc()

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

Definition at line 686 of file pns_node.cpp.

687{
688 linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
689 linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
690
691 m_index->Add( aArc );
692}
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1299

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.

741{
742 m_edgeExclusions.push_back( std::move( aShape ) );
743}
std::vector< std::unique_ptr< SHAPE > > m_edgeExclusions
Definition: pns_node.h:498

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.

659{
660 linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
661 linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
662
663 m_index->Add( aSeg );
664}

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.

576{
577 if( aSolid->IsRoutable() )
578 linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
579
580 m_index->Add( aSolid );
581}

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.

592{
593 linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
594
595 m_index->Add( aVia );
596}

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.

1477{
1479
1480 if( l_cur )
1481 {
1482 for( ITEM* item : *l_cur )
1483 {
1484 if( item->OfKind( aKindMask ) && item->IsRoutable() )
1485 aItems.insert( item );
1486 }
1487 }
1488
1489 if( !isRoot() )
1490 {
1492
1493 if( l_root )
1494 {
1495 for( ITEM* item : *l_root )
1496 {
1497 if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1498 aItems.insert( item );
1499 }
1500 }
1501 }
1502}
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Returns list of all items in a given net.
Definition: pns_index.cpp:71
bool Overrides(ITEM *aItem) const
Definition: pns_node.h:409
bool isRoot() const
Definition: pns_node.h:460

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
aSegthe initial segment.
aOriginSegmentIndexindex of aSeg in the resulting line.
aStopAtLockedJointswill terminate the line at the first locked joint encountered
aFollowLockedSegmentswill 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.

1005{
1006 const int MaxVerts = 1024 * 16;
1007
1008 std::array<VECTOR2I, MaxVerts + 1> corners;
1009 std::array<LINKED_ITEM*, MaxVerts + 1> segs;
1010 std::array<bool, MaxVerts + 1> arcReversed;
1011
1012 LINE pl;
1013 bool guardHit = false;
1014
1015 int i_start = MaxVerts / 2;
1016 int i_end = i_start + 1;
1017
1018 pl.SetWidth( aSeg->Width() );
1019 pl.SetLayers( aSeg->Layers() );
1020 pl.SetNet( aSeg->Net() );
1021 pl.SetOwner( this );
1022
1023 followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1024 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1025
1026 if( !guardHit )
1027 {
1028 followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
1029 guardHit, aStopAtLockedJoints, aFollowLockedSegments );
1030 }
1031
1032 int n = 0;
1033
1034 LINKED_ITEM* prev_seg = nullptr;
1035 bool originSet = false;
1036
1037 SHAPE_LINE_CHAIN& line = pl.Line();
1038
1039 for( int i = i_start + 1; i < i_end; i++ )
1040 {
1041 const VECTOR2I& p = corners[i];
1042 LINKED_ITEM* li = segs[i];
1043
1044 if( !li || li->Kind() != ITEM::ARC_T )
1045 line.Append( p );
1046
1047 if( li && prev_seg != li )
1048 {
1049 if( li->Kind() == ITEM::ARC_T )
1050 {
1051 const ARC* arc = static_cast<const ARC*>( li );
1052 const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape() );
1053
1054 int nSegs = line.PointCount();
1055 VECTOR2I last = nSegs ? line.CPoint( -1 ) : VECTOR2I();
1056 ssize_t lastShape = nSegs ? line.ArcIndex( static_cast<ssize_t>( nSegs ) - 1 ) : -1;
1057
1058 line.Append( arcReversed[i] ? sa->Reversed() : *sa );
1059 }
1060
1061 pl.Link( li );
1062
1063 // latter condition to avoid loops
1064 if( li == aSeg && aOriginSegmentIndex && !originSet )
1065 {
1066 wxASSERT( n < line.SegmentCount() ||
1067 ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
1068 *aOriginSegmentIndex = line.PointCount() - 1;
1069 originSet = true;
1070 }
1071 }
1072
1073 prev_seg = li;
1074 }
1075
1076 // Remove duplicate verts, but do NOT remove colinear segments here!
1077 pl.Line().Simplify( false );
1078
1079 // TODO: maintain actual segment index under simplification system
1080 if( aOriginSegmentIndex && *aOriginSegmentIndex >= pl.SegmentCount() )
1081 *aOriginSegmentIndex = pl.SegmentCount() - 1;
1082
1083 assert( pl.SegmentCount() != 0 );
1084
1085 return pl;
1086}
void followLine(LINKED_ITEM *aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool *aArcReversed, bool &aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments)
Definition: pns_node.cpp:954
SHAPE_ARC Reversed() const
Definition: shape_arc.cpp:587
int PointCount() const
Return the number of points (vertices) in this line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590

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.

140{
141 NODE* child = new NODE;
142
143 m_children.insert( child );
144
145 child->m_depth = m_depth + 1;
146 child->m_parent = this;
147 child->m_ruleResolver = m_ruleResolver;
148 child->m_root = isRoot() ? this : m_root;
150 child->m_collisionQueryScope = m_collisionQueryScope;
151
152 // Immediate offspring of the root branch needs not copy anything. For the rest, deep-copy
153 // joints, overridden item maps and pointers to stored items.
154 if( !isRoot() )
155 {
156 JOINT_MAP::iterator j;
157
158 for( ITEM* item : *m_index )
159 child->m_index->Add( item );
160
161 child->m_joints = m_joints;
162 child->m_override = m_override;
163 }
164
165#if 0
166 wxLogTrace( wxT( "PNS" ), wxT( "%d items, %d joints, %d overrides" ),
167 child->m_index->Size(),
168 (int) child->m_joints.size(),
169 (int) child->m_override.size() );
170#endif
171
172 return child;
173}
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:489

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
aItemthe item to find collisions with
aKindMaskmask of obstacle types to take into account
Returns
the obstacle, if found, otherwise empty.

Definition at line 475 of file pns_node.cpp.

476{
477 OBSTACLES obs;
478
479 obs.reserve( 100 );
480
481 if( aItemA->Kind() == ITEM::LINE_T )
482 {
483 int n = 0;
484 const LINE* line = static_cast<const LINE*>( aItemA );
485 const SHAPE_LINE_CHAIN& l = line->CLine();
486
487 for( int i = 0; i < l.SegmentCount(); i++ )
488 {
489 // Note: Clearances between &s and other items are cached,
490 // which means they'll be the same for all segments in the line.
491 // Disabling the cache will lead to slowness.
492
493 const SEGMENT s( *line, l.CSegment( i ) );
494 n += QueryColliding( &s, obs, aKindMask, 1 );
495
496 if( n )
497 return OPT_OBSTACLE( obs[0] );
498 }
499
500 if( line->EndsWithVia() )
501 {
502 n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
503
504 if( n )
505 return OPT_OBSTACLE( obs[0] );
506 }
507 }
508 else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
509 {
510 return OPT_OBSTACLE( obs[0] );
511 }
512
513 return OPT_OBSTACLE();
514}
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.
Definition: pns_node.cpp:272
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:166
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:168

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
aSetset of items to find collisions with.
aKindMaskmask of obstacle types to take into account.
Returns
the obstacle, if found, otherwise empty.

Definition at line 461 of file pns_node.cpp.

462{
463 for( const ITEM* item : aSet.CItems() )
464 {
465 OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
466
467 if( obs )
468 return obs;
469 }
470
471 return OPT_OBSTACLE();
472}
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:475

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.

1506{
1507 for( ITEM* item : *m_index )
1508 {
1509 item->SetRank( -1 );
1510 item->Mark( item->Marker() & ~aMarkerMask );
1511 }
1512}

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
aNodenode to commit changes from.

Definition at line 1450 of file pns_node.cpp.

1451{
1452 if( aNode->isRoot() )
1453 return;
1454
1455 for( ITEM* item : aNode->m_override )
1456 Remove( item );
1457
1458 for( ITEM* item : *aNode->m_index )
1459 {
1460 item->SetRank( -1 );
1461 item->Unmark();
1462 Add( std::unique_ptr<ITEM>( item ) );
1463 }
1464
1467}
void releaseChildren()
Definition: pns_node.cpp:1422
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:893

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.

210 {
211 return m_depth;
212 }

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.

759{
760 // case 1: removing an item that is stored in the root node from any branch:
761 // mark it as overridden, but do not remove
762 if( aItem->BelongsTo( m_root ) && !isRoot() )
763 m_override.insert( aItem );
764
765 // case 2: the item belongs to this branch or a parent, non-root branch,
766 // or the root itself and we are the root: remove from the index
767 else if( !aItem->BelongsTo( m_root ) || isRoot() )
768 m_index->Remove( aItem );
769
770 // the item belongs to this particular branch: un-reference it
771 if( aItem->BelongsTo( this ) )
772 {
773 aItem->SetOwner( nullptr );
774 m_root->m_garbageItems.insert( aItem );
775 }
776}
void Remove(ITEM *aItem)
Removes an item from the spatial index.
Definition: pns_index.cpp:46
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:500

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.

1317{
1318#if 0
1319 std::unordered_set<SEGMENT*> all_segs;
1321
1322 for( i = m_items.begin(); i != m_items.end(); i++ )
1323 {
1324 if( (*i)->GetKind() == ITEM::SEGMENT_T )
1325 all_segs.insert( static_cast<SEGMENT*>( *i ) );
1326 }
1327
1328 if( !isRoot() )
1329 {
1330 for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1331 {
1332 if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1333 all_segs.insert( static_cast<SEGMENT*>(*i) );
1334 }
1335 }
1336
1337 JOINT_MAP::iterator j;
1338
1339 if( aLong )
1340 {
1341 for( j = m_joints.begin(); j != m_joints.end(); ++j )
1342 {
1343 wxLogTrace( wxT( "PNS" ), wxT( "joint : %s, links : %d\n" ),
1344 j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1345 JOINT::LINKED_ITEMS::const_iterator k;
1346
1347 for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1348 {
1349 const ITEM* m_item = *k;
1350
1351 switch( m_item->GetKind() )
1352 {
1353 case ITEM::SEGMENT_T:
1354 {
1355 const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1356 wxLogTrace( wxT( "PNS" ), wxT( " -> seg %s %s\n" ),
1357 seg->GetSeg().A.Format().c_str(),
1358 seg->GetSeg().B.Format().c_str() );
1359 break;
1360 }
1361
1362 default:
1363 break;
1364 }
1365 }
1366 }
1367 }
1368
1369 int lines_count = 0;
1370
1371 while( !all_segs.empty() )
1372 {
1373 SEGMENT* s = *all_segs.begin();
1374 LINE* l = AssembleLine( s );
1375
1376 LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1377
1378 if( aLong )
1379 {
1380 wxLogTrace( wxT( "PNS" ), wxT( "Line: %s, net %d " ),
1381 l->GetLine().Format().c_str(), l->GetNet() );
1382 }
1383
1384 for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1385 {
1386 wxLogTrace( wxT( "PNS" ), wxT( "%s " ), (*j)->GetSeg().A.Format().c_str() );
1387
1388 if( j + 1 == seg_refs->end() )
1389 wxLogTrace( wxT( "PNS" ), wxT( "%s\n" ), (*j)->GetSeg().B.Format().c_str() );
1390
1391 all_segs.erase( *j );
1392 }
1393
1394 lines_count++;
1395 }
1396
1397 wxLogTrace( wxT( "PNS" ), wxT( "Local joints: %d, lines : %d \n" ),
1398 m_joints.size(), lines_count );
1399#endif
1400}
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:1003

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.

1639{
1640 if( aParent->IsConnected() )
1641 {
1642 const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1643
1645
1646 if( l_cur )
1647 {
1648 for( ITEM* item : *l_cur )
1649 {
1650 if( item->Parent() == aParent )
1651 return item;
1652 }
1653 }
1654 }
1655
1656 return nullptr;
1657}
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:127

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.

1202{
1203 JOINT::HASH_TAG tag;
1204
1205 tag.net = aNet;
1206 tag.pos = aPos;
1207
1208 JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
1209
1210 if( f == end && !isRoot() )
1211 {
1212 end = m_root->m_joints.end();
1213 f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1214 }
1215
1216 if( f == end )
1217 return nullptr;
1218
1219 while( f != end )
1220 {
1221 if( f->second.Layers().Overlaps( aLayer ) )
1222 return &f->second;
1223
1224 ++f;
1225 }
1226
1227 return nullptr;
1228}

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.

1090{
1091 aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
1092 aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
1093}
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1201

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.

1097{
1098 for( ITEM* item : aA.LinkList() )
1099 {
1100 if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
1101 {
1102 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1103 LINE line = AssembleLine( li );
1104
1105 if( !line.Layers().Overlaps( aB.Layers() ) )
1106 continue;
1107
1108 JOINT j_start, j_end;
1109
1110 FindLineEnds( line, j_start, j_end );
1111
1112 int id_start = line.CLine().Find( aA.Pos() );
1113 int id_end = line.CLine().Find( aB.Pos() );
1114
1115 if( id_end < id_start )
1116 std::swap( id_end, id_start );
1117
1118 if( id_start >= 0 && id_end >= 0 )
1119 {
1120 line.ClipVertexRange( id_start, id_end );
1121 aLines.push_back( line );
1122 }
1123 }
1124 }
1125
1126 return 0;
1127}
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1089

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.

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

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.

1567{
1568 JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1569
1570 if( !jtStart )
1571 return nullptr;
1572
1573 for( ITEM* item : jtStart->LinkList() )
1574 {
1575 if( item->OfKind( ITEM::ARC_T ) )
1576 {
1577 ARC* seg2 = static_cast<ARC*>( item );
1578
1579 const VECTOR2I a2( seg2->Anchor( 0 ) );
1580 const VECTOR2I b2( seg2->Anchor( 1 ) );
1581
1582 if( seg2->Layers().Start() == lr.Start()
1583 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1584 {
1585 return seg2;
1586 }
1587 }
1588 }
1589
1590 return nullptr;
1591}
int Start() const
Definition: pns_layerset.h:82

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.

1532{
1533 JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1534
1535 if( !jtStart )
1536 return nullptr;
1537
1538 for( ITEM* item : jtStart->LinkList() )
1539 {
1540 if( item->OfKind( ITEM::SEGMENT_T ) )
1541 {
1542 SEGMENT* seg2 = (SEGMENT*)item;
1543
1544 const VECTOR2I a2( seg2->Seg().A );
1545 const VECTOR2I b2( seg2->Seg().B );
1546
1547 if( seg2->Layers().Start() == lr.Start()
1548 && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1549 {
1550 return seg2;
1551 }
1552 }
1553 }
1554
1555 return nullptr;
1556}

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.

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

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.

1131{
1132 SEGMENT* locked_seg = nullptr;
1133 std::vector<VVIA*> vvias;
1134
1135 for( auto& jointPair : m_joints )
1136 {
1137 JOINT joint = jointPair.second;
1138
1139 if( joint.Layers().IsMultilayer() )
1140 continue;
1141
1142 int n_seg = 0, n_solid = 0, n_vias = 0;
1143 int prev_w = -1;
1144 int max_w = -1;
1145 bool is_width_change = false;
1146 bool is_locked = false;
1147
1148 for( const auto& lnk : joint.LinkList() )
1149 {
1150 if( lnk.item->OfKind( ITEM::VIA_T ) )
1151 {
1152 n_vias++;
1153 }
1154 else if( lnk.item->OfKind( ITEM::SOLID_T ) )
1155 {
1156 n_solid++;
1157 }
1158 else if( const auto t = dyn_cast<PNS::SEGMENT*>( lnk.item ) )
1159 {
1160 int w = t->Width();
1161
1162 if( prev_w >= 0 && w != prev_w )
1163 {
1164 is_width_change = true;
1165 }
1166
1167 max_w = std::max( w, max_w );
1168 prev_w = w;
1169
1170 is_locked = t->IsLocked();
1171 locked_seg = t;
1172 }
1173 }
1174
1175 if( ( is_width_change || n_seg >= 3 || is_locked ) && n_solid == 0 && n_vias == 0 )
1176 {
1177 // fixme: the hull margin here is an ugly temporary workaround. The real fix
1178 // is to use octagons for via force propagation.
1179 vvias.push_back( new VVIA( joint.Pos(), joint.Layers().Start(),
1180 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1181 }
1182
1183 if( is_locked )
1184 {
1185 const VECTOR2I& secondPos = ( locked_seg->Seg().A == joint.Pos() ) ?
1186 locked_seg->Seg().B :
1187 locked_seg->Seg().A;
1188
1189 vvias.push_back( new VVIA( secondPos, joint.Layers().Start(),
1190 max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1191 }
1192 }
1193
1194 for( auto vvia : vvias )
1195 {
1196 Add( ItemCast<VIA>( std::move( std::unique_ptr<VVIA>( vvia ) ) ) );
1197 }
1198}
#define PNS_HULL_MARGIN
Definition: pns_line.h:44

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.

957{
958 bool prevReversed = false;
959
960 const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
961
962 for( int count = 0 ; ; ++count )
963 {
964 const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
965 const JOINT* jt = FindJoint( p, aCurrent );
966
967 assert( jt );
968
969 aCorners[aPos] = jt->Pos();
970 aSegments[aPos] = aCurrent;
971 aArcReversed[aPos] = false;
972
973 if( aCurrent->Kind() == ITEM::ARC_T )
974 {
975 if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) )
976 || ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
977 aArcReversed[aPos] = true;
978 }
979
980 aPos += ( aScanDirection ? 1 : -1 );
981
982 if( count && guard == p )
983 {
984 if( aPos >= 0 && aPos < aLimit )
985 aSegments[aPos] = nullptr;
986
987 aGuardHit = true;
988 break;
989 }
990
991 bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
992
993 if( locked || !jt->IsLineCorner( aFollowLockedSegments ) || aPos < 0 || aPos == aLimit )
994 break;
995
996 aCurrent = jt->NextSegment( aCurrent, aFollowLockedSegments );
997
998 prevReversed = ( aCurrent && jt->Pos() == aCurrent->Anchor( aScanDirection ) );
999 }
1000}

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.

104{
105 if( !m_ruleResolver )
106 return 100000;
107
108 if( aA->IsVirtual() || aB->IsVirtual() )
109 return 0;
110
111 return m_ruleResolver->Clearance( aA, aB, aUseClearanceEpsilon );
112}
virtual int Clearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true)=0

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.

422 {
424 }

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.

116{
117 if( !m_ruleResolver )
118 return 0;
119
120 if( aA->IsVirtual() || aB->IsVirtual() )
121 return 0;
122
123 return m_ruleResolver->HoleClearance( aA, aB, aUseClearanceEpsilon );
124}
virtual int HoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true)=0

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.

128{
129 if( !m_ruleResolver )
130 return 0;
131
132 if( aA->IsVirtual() || aB->IsVirtual() )
133 return 0;
134
135 return m_ruleResolver->HoleToHoleClearance( aA, aB, aUseClearanceEpsilon );
136}
virtual int HoleToHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true)=0

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
aRemovedremoved items.
aAddedadded items.

Definition at line 1403 of file pns_node.cpp.

1404{
1405 if( isRoot() )
1406 return;
1407
1408 if( m_override.size() )
1409 aRemoved.reserve( m_override.size() );
1410
1411 if( m_index->Size() )
1412 aAdded.reserve( m_index->Size() );
1413
1414 for( ITEM* item : m_override )
1415 aRemoved.push_back( item );
1416
1417 for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1418 aAdded.push_back( *i );
1419}
int Size() const
Returns number of items stored in the index.
Definition: pns_index.h:115
ITEM_SET::iterator end()
Definition: pns_index.h:118
ITEM_SET::iterator begin()
Definition: pns_index.h:117

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.

399 {
400 return !m_children.empty();
401 }

References m_children.

◆ HitTest()

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

Find all items that contain the point aPoint.

Parameters
aPointthe point.
Returns
the items.

Definition at line 546 of file pns_node.cpp.

547{
548 ITEM_SET items;
549
550 // fixme: we treat a point as an infinitely small circle - this is inefficient.
551 SHAPE_CIRCLE s( aPoint, 0 );
552 HIT_VISITOR visitor( items, aPoint );
553 visitor.SetWorld( this, nullptr );
554
555 m_index->Query( &s, m_maxClearance, visitor );
556
557 if( !isRoot() ) // fixme: could be made cleaner
558 {
559 ITEM_SET items_root;
560 visitor.SetWorld( m_root, nullptr );
561 HIT_VISITOR visitor_root( items_root, aPoint );
562 m_root->m_index->Query( &s, m_maxClearance, visitor_root );
563
564 for( ITEM* item : items_root.Items() )
565 {
566 if( !Overrides( item ) )
567 items.Add( item );
568 }
569 }
570
571 return items;
572}
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor) const
Searches items in the index that are in proximity of aItem.
Definition: pns_index.h:141

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.

461 {
462 return m_parent == nullptr;
463 }

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()

◆ 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.

1300{
1301 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1302
1303 jt.Link( aWhere );
1304}
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
Touch a joint and links it to an m_item.
Definition: pns_node.cpp:1238

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.

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

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
aLinethe item to find collisions with
aKindMaskmask of obstacle types to take into account
aRestrictedSetis an optional set of items that should be considered as obstacles
aUseClearanceEpsilondetermines 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.

306{
307 OBSTACLES obstacleList;
308 obstacleList.reserve( 100 );
309
310 for( int i = 0; i < aLine->CLine().SegmentCount(); i++ )
311 {
312 // Note: Clearances between &s and other items are cached,
313 // which means they'll be the same for all segments in the line.
314 // Disabling the cache will lead to slowness.
315
316 const SEGMENT s( *aLine, aLine->CLine().CSegment( i ) );
317 QueryColliding( &s, obstacleList, aKindMask );
318 }
319
320 if( aLine->EndsWithVia() )
321 QueryColliding( &aLine->Via(), obstacleList, aKindMask );
322
323 if( obstacleList.empty() )
324 return OPT_OBSTACLE();
325
326 OBSTACLE nearest;
327 nearest.m_head = nullptr;
328 nearest.m_item = nullptr;
329 nearest.m_distFirst = INT_MAX;
330 nearest.m_maxFanoutWidth = 0;
331
332 auto updateNearest =
333 [&]( const SHAPE_LINE_CHAIN::INTERSECTION& pt, ITEM* obstacle,
334 const SHAPE_LINE_CHAIN& hull, bool isHole )
335 {
336 int dist = aLine->CLine().PathLength( pt.p, pt.index_their );
337
338 if( dist < nearest.m_distFirst )
339 {
340 nearest.m_distFirst = dist;
341 nearest.m_ipFirst = pt.p;
342 nearest.m_item = obstacle;
343 nearest.m_hull = hull;
344
345 obstacle->Mark( isHole ? obstacle->Marker() | MK_HOLE
346 : obstacle->Marker() & ~MK_HOLE );
347 }
348 };
349
350 SHAPE_LINE_CHAIN obstacleHull;
351 DEBUG_DECORATOR* debugDecorator = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
352 std::vector<SHAPE_LINE_CHAIN::INTERSECTION> intersectingPts;
353 int layer = aLine->Layer();
354
355 for( const OBSTACLE& obstacle : obstacleList )
356 {
357 if( aRestrictedSet && aRestrictedSet->find( obstacle.m_item ) == aRestrictedSet->end() )
358 continue;
359
360 int clearance =
361 GetClearance( obstacle.m_item, aLine, aUseClearanceEpsilon ) + aLine->Width() / 2;
362
363 obstacleHull = obstacle.m_item->Hull( clearance, 0, layer );
364 //debugDecorator->AddLine( obstacleHull, 2, 40000, "obstacle-hull-test" );
365 //debugDecorator->AddLine( aLine->CLine(), 5, 40000, "obstacle-test-line" );
366
367 intersectingPts.clear();
368 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
369
370 for( const auto& ip : intersectingPts )
371 {
372 //debugDecorator->AddPoint( ip.p, ip.valid?3:6, 100000, (const char *) wxString::Format("obstacle-isect-point-%d" ).c_str() );
373 if( ip.valid )
374 updateNearest( ip, obstacle.m_item, obstacleHull, false );
375 }
376
377 if( aLine->EndsWithVia() )
378 {
379 const VIA& via = aLine->Via();
380 // Don't use via.Drill(); it doesn't include the plating thickness
381
382 int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
383
384 int viaClearance = GetClearance( obstacle.m_item, &via, aUseClearanceEpsilon )
385 + via.Diameter() / 2;
386 int holeClearance =
387 GetHoleClearance( obstacle.m_item, &via, aUseClearanceEpsilon ) + viaHoleRadius;
388
389 if( holeClearance > viaClearance )
390 viaClearance = holeClearance;
391
392 obstacleHull = obstacle.m_item->Hull( viaClearance, 0, layer );
393 //debugDecorator->AddLine( obstacleHull, 3 );
394
395 intersectingPts.clear();
396 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
397
398 // obstacleHull.Intersect( aLine->CLine(), intersectingPts, true );
399
400 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
401 updateNearest( ip, obstacle.m_item, obstacleHull, false );
402 }
403
405 || !ROUTER::GetInstance()->GetInterface()->IsFlashedOnLayer( obstacle.m_item,
406 layer ) )
407 && obstacle.m_item->Hole() )
408 {
409 clearance = GetHoleClearance( obstacle.m_item, aLine, aUseClearanceEpsilon );
410 int copperClearance = GetClearance( obstacle.m_item, aLine, aUseClearanceEpsilon );
411
412 clearance = std::max( clearance, copperClearance );
413
414 obstacleHull = obstacle.m_item->HoleHull( clearance, aLine->Width(), layer );
415
416 intersectingPts.clear();
417 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
418
419 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
420 updateNearest( ip, obstacle.m_item, obstacleHull, true );
421
422 if( aLine->EndsWithVia() )
423 {
424 const VIA& via = aLine->Via();
425 // Don't use via.Drill(); it doesn't include the plating thickness
426 int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
427
428 int viaClearance = GetClearance( obstacle.m_item, &via, aUseClearanceEpsilon )
429 + via.Diameter() / 2;
430 int holeClearance = GetHoleClearance( obstacle.m_item, &via, aUseClearanceEpsilon )
431 + viaHoleRadius;
432 int holeToHole =
433 GetHoleToHoleClearance( obstacle.m_item, &via, aUseClearanceEpsilon )
434 + viaHoleRadius;
435
436 if( holeClearance > viaClearance )
437 viaClearance = holeClearance;
438
439 if( holeToHole > viaClearance )
440 viaClearance = holeToHole;
441
442 obstacleHull = obstacle.m_item->Hull( viaClearance, 0, layer );
443 //debugDecorator->AddLine( obstacleHull, 5 );
444
445 intersectingPts.clear();
446 HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
447
448 for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
449 updateNearest( ip, obstacle.m_item, obstacleHull, true );
450 }
451 }
452 }
453
454 if( nearest.m_distFirst == INT_MAX )
455 nearest.m_item = obstacleList[0].m_item;
456
457 return nearest;
458}
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:103
int GetHoleToHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:127
int GetHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:115
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
Definition: pns_utils.cpp:384
@ MK_HOLE
Definition: pns_item.h:45
@ VIA
Normal via.
Definition: router_tool.cpp:90
Represent an intersection between two line segments.
VECTOR2I p
< Point of intersection between our and their.
int index_their
When true, the corner [index_our] of the 'our' line lies exactly on 'their' line.

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.

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

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
aItemitem to check collisions against
aObstaclesset of colliding objects found
aKindMaskmask of obstacle types to take into account
aLimitCountstop 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.

274{
276 if( aItem->IsVirtual() )
277 return 0;
278
279 DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly,
280 aOverrideClearance );
281
282#ifdef DEBUG
283 assert( allocNodes.find( this ) != allocNodes.end() );
284#endif
285
286 visitor.SetCountLimit( aLimitCount );
287 visitor.SetWorld( this, nullptr );
288
289 // first, look for colliding items in the local index
290 m_index->Query( aItem, m_maxClearance, visitor );
291
292 // if we haven't found enough items, look in the root branch as well.
293 if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
294 {
295 visitor.SetWorld( m_root, this );
296 m_root->m_index->Query( aItem, m_maxClearance, visitor );
297 }
298
299 return aObstacles.size();
300}

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.

747{
748 for( const std::unique_ptr<SHAPE>& edgeExclusion : m_edgeExclusions )
749 {
750 if( edgeExclusion->Collide( aPos ) )
751 return true;
752 }
753
754 return false;
755}

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.

1602{
1603 int n = 0;
1604
1605 aJoints.clear();
1606
1607 for( JOINT_MAP::value_type& j : m_joints )
1608 {
1609 if( !j.second.Layers().Overlaps( aLayerMask ) )
1610 continue;
1611
1612 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1613 {
1614 aJoints.push_back( &j.second );
1615 n++;
1616 }
1617 }
1618
1619 if( isRoot() )
1620 return n;
1621
1622 for( JOINT_MAP::value_type& j : m_root->m_joints )
1623 {
1624 if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1625 {
1626 if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1627 {
1628 aJoints.push_back( &j.second );
1629 n++;
1630 }
1631 }
1632 }
1633
1634 return n;
1635}
bool Contains(const Vec &aPoint) const
Definition: box2.h:141

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.

794{
795 // We have to split a single joint (associated with a via or a pad, binding together multiple
796 // layers) into multiple independent joints. As I'm a lazy bastard, I simply delete the
797 // via/solid and all its links and re-insert them.
798
799 JOINT::LINKED_ITEMS links( aJoint->LinkList() );
800 JOINT::HASH_TAG tag;
801 int net = aItem->Net();
802
803 tag.net = net;
804 tag.pos = aJoint->Pos();
805
806 bool split;
807
808 do
809 {
810 split = false;
811 auto range = m_joints.equal_range( tag );
812
813 if( range.first == m_joints.end() )
814 break;
815
816 // find and remove all joints containing the via to be removed
817
818 for( auto f = range.first; f != range.second; ++f )
819 {
820 if( aItem->LayersOverlap( &f->second ) )
821 {
822 m_joints.erase( f );
823 split = true;
824 break;
825 }
826 }
827 } while( split );
828
829 // and re-link them, using the former via's link list
830 for( ITEM* link : links )
831 {
832 if( link != aItem )
833 linkJoint( tag.pos, link->Layers(), net, link );
834 }
835}
ITEM_SET::ENTRIES LINKED_ITEMS
Joints are hashed by their position, layers and net.
Definition: pns_joint.h:45
static std::vector< std::string > split(const std::string &aStr, const std::string &aDelim)
Split the input string into a vector of output strings.
Definition: string_utils.h:296

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.

1423{
1424 // copy the kids as the NODE destructor erases the item from the parent node.
1425 std::set<NODE*> kids = m_children;
1426
1427 for( NODE* node : kids )
1428 {
1429 node->releaseChildren();
1430 delete node;
1431 }
1432}

References m_children.

Referenced by Commit(), and KillChildren().

◆ releaseGarbage()

void PNS::NODE::releaseGarbage ( )
private

Definition at line 1435 of file pns_node.cpp.

1436{
1437 if( !isRoot() )
1438 return;
1439
1440 for( ITEM* item : m_garbageItems )
1441 {
1442 if( !item->BelongsTo( this ) )
1443 delete item;
1444 }
1445
1446 m_garbageItems.clear();
1447}

References isRoot(), and m_garbageItems.

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

◆ Remove() [1/6]

◆ Remove() [2/6]

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

Definition at line 900 of file pns_node.cpp.

901{
902 switch( aItem->Kind() )
903 {
904 case ITEM::ARC_T:
905 Remove( static_cast<ARC*>( aItem ) );
906 break;
907
908 case ITEM::SOLID_T:
909 Remove( static_cast<SOLID*>( aItem ) );
910 break;
911
912 case ITEM::SEGMENT_T:
913 Remove( static_cast<SEGMENT*>( aItem ) );
914 break;
915
916 case ITEM::LINE_T:
917 {
918 LINE* l = static_cast<LINE*>( aItem );
919
920 for ( LINKED_ITEM* s : l->Links() )
921 Remove( s );
922
923 break;
924 }
925
926 case ITEM::VIA_T:
927 Remove( static_cast<VIA*>( aItem ) );
928 break;
929
930 default:
931 break;
932 }
933}

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
aLineitem to remove

Definition at line 936 of file pns_node.cpp.

937{
938 // LINE does not have a separate remover, as LINEs are never truly a member of the tree
939 std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
940
941 for( LINKED_ITEM* li : segRefs )
942 {
943 if( li->OfKind( ITEM::SEGMENT_T ) )
944 Remove( static_cast<SEGMENT*>( li ) );
945 else if( li->OfKind( ITEM::ARC_T ) )
946 Remove( static_cast<ARC*>( li ) );
947 }
948
949 aLine.SetOwner( nullptr );
950 aLine.ClearLinks();
951}

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.

887{
888 removeSegmentIndex( aSegment );
889 doRemove( aSegment );
890}
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:779

References doRemove(), and removeSegmentIndex().

◆ Remove() [5/6]

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

Definition at line 872 of file pns_node.cpp.

873{
874 removeSolidIndex( aSolid );
875 doRemove( aSolid );
876}
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:846

References doRemove(), and removeSolidIndex().

◆ Remove() [6/6]

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

Definition at line 879 of file pns_node.cpp.

880{
881 removeViaIndex( aVia );
882 doRemove( aVia );
883}
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:838

References doRemove(), and removeViaIndex().

◆ removeArcIndex()

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

Definition at line 786 of file pns_node.cpp.

787{
788 unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
789 unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
790}
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1307

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.

1516{
1517 std::vector<ITEM*> garbage;
1518
1519 for( ITEM* item : *m_index )
1520 {
1521 if( item->Marker() & aMarker )
1522 garbage.emplace_back( item );
1523 }
1524
1525 for( ITEM* item : garbage )
1526 Remove( item );
1527}

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.

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

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.

847{
848 if( !aSolid->IsRoutable() )
849 return;
850
851 // fixme: redundant code
852 JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
853 assert( jt );
854 rebuildJoint( jt, aSolid );
855}
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:793

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.

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

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
aOldItemitem to be removed
aNewItemitem add instead

Definition at line 858 of file pns_node.cpp.

859{
860 Remove( aOldItem );
861 Add( std::move( aNewItem ) );
862}

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.

866{
867 Remove( aOldLine );
868 Add( aNewLine );
869}

References Add(), and Remove().

◆ SetCollisionQueryScope()

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

Definition at line 416 of file pns_node.h.

417 {
418 m_collisionQueryScope = aScope;
419 }

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.

193 {
194 m_ruleResolver = aFunc;
195 }

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.

1239{
1240 JOINT::HASH_TAG tag;
1241
1242 tag.pos = aPos;
1243 tag.net = aNet;
1244
1245 // try to find the joint in this node.
1246 JOINT_MAP::iterator f = m_joints.find( tag );
1247
1248 std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1249
1250 // not found and we are not root? find in the root and copy results here.
1251 if( f == m_joints.end() && !isRoot() )
1252 {
1253 range = m_root->m_joints.equal_range( tag );
1254
1255 for( f = range.first; f != range.second; ++f )
1256 m_joints.insert( *f );
1257 }
1258
1259 // now insert and combine overlapping joints
1260 JOINT jt( aPos, aLayers, aNet );
1261
1262 bool merged;
1263
1264 do
1265 {
1266 merged = false;
1267 range = m_joints.equal_range( tag );
1268
1269 if( range.first == m_joints.end() )
1270 break;
1271
1272 for( f = range.first; f != range.second; ++f )
1273 {
1274 if( aLayers.Overlaps( f->second.Layers() ) )
1275 {
1276 jt.Merge( f->second );
1277 m_joints.erase( f );
1278 merged = true;
1279 break;
1280 }
1281 }
1282 } while( merged );
1283
1284 return m_joints.insert( TagJointPair( tag, jt ) )->second;
1285}
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:480

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.

1308{
1309 // fixme: remove dangling joints
1310 JOINT& jt = touchJoint( aPos, aLayers, aNet );
1311
1312 jt.Unlink( aWhere );
1313}

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.

177{
178 if( isRoot() )
179 return;
180
181 m_parent->m_children.erase( this );
182}

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

◆ 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

◆ 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: