KiCad PCB EDA Suite
PNS::NODE Class Reference

NODE. More...

#include <pns_node.h>

Classes

struct  DEFAULT_OBSTACLE_VISITOR
 

Public Types

typedef OPT< OBSTACLEOPT_OBSTACLE
 
typedef std::vector< ITEM * > ITEM_VECTOR
 
typedef std::vector< OBSTACLEOBSTACLES
 

Public Member Functions

 NODE ()
 
 ~NODE ()
 
int GetClearance (const ITEM *aA, const ITEM *aB) const
 

Returns the expected clearance between items a and b.

More...
 
int GetMaxClearance () const
 

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

More...
 
void SetMaxClearance (int aClearance)
 

Sets the worst-case clerance between any pair of items

More...
 
void SetRuleResolver (RULE_RESOLVER *aFunc)
 

Assigns a clerance resolution function object

More...
 
RULE_RESOLVERGetRuleResolver () const
 
int JointCount () const
 

Returns the number of joints

More...
 
int Depth () const
 

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

More...
 
int QueryColliding (const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aForceClearance=-1)
 Function QueryColliding() More...
 
int QueryJoints (const BOX2I &aBox, std::vector< JOINT * > &aJoints, int aLayerMask=-1, int aKindMask=ITEM::ANY_T)
 
int QueryColliding (const ITEM *aItem, OBSTACLE_VISITOR &aVisitor)
 
OPT_OBSTACLE NearestObstacle (const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
 Function NearestObstacle() More...
 
OPT_OBSTACLE CheckColliding (const ITEM *aItem, int aKindMask=ITEM::ANY_T)
 Function CheckColliding() More...
 
OPT_OBSTACLE CheckColliding (const ITEM_SET &aSet, int aKindMask=ITEM::ANY_T)
 Function CheckColliding() More...
 
bool CheckColliding (const ITEM *aItemA, const ITEM *aItemB, int aKindMask=ITEM::ANY_T, int aForceClearance=-1)
 Function CheckColliding() More...
 
const ITEM_SET HitTest (const VECTOR2I &aPoint) const
 Function HitTest() More...
 
bool Add (std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
 Function Add() More...
 
void Add (std::unique_ptr< SOLID > aSolid)
 
void Add (std::unique_ptr< VIA > aVia)
 
void Add (std::unique_ptr< ARC > aArc)
 
void Add (LINE &aLine, bool aAllowRedundant=false)
 
void Remove (ARC *aArc)
 Function Remove() More...
 
void Remove (SOLID *aSolid)
 
void Remove (VIA *aVia)
 
void Remove (SEGMENT *aSegment)
 
void Remove (ITEM *aItem)
 
void Remove (LINE &aLine)
 Function Remove() More...
 
void Replace (ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
 Function Replace() More...
 
void Replace (LINE &aOldLine, LINE &aNewLine)
 
NODEBranch ()
 Function Branch() More...
 
const LINE AssembleLine (LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
 Function AssembleLine() More...
 
void Dump (bool aLong=false)
 

Prints the contents and joints structure

More...
 
void GetUpdatedItems (ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
 Function GetUpdatedItems() More...
 
void Commit (NODE *aNode)
 Function Commit() More...
 
JOINTFindJoint (const VECTOR2I &aPos, int aLayer, int aNet)
 Function FindJoint() More...
 
void LockJoint (const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
 
JOINTFindJoint (const VECTOR2I &aPos, const ITEM *aItem)
 Function FindJoint() More...
 
int FindLinesBetweenJoints (JOINT &aA, JOINT &aB, std::vector< LINE > &aLines)
 

finds all lines between a pair of joints. Used by the loop removal procedure.

More...
 
void FindLineEnds (const LINE &aLine, JOINT &aA, JOINT &aB)
 

finds the joints corresponding to the ends of line aLine

More...
 
void KillChildren ()
 

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

More...
 
void AllItemsInNet (int aNet, std::set< ITEM * > &aItems)
 
void ClearRanks (int aMarkerMask=MK_HEAD|MK_VIOLATION)
 
void RemoveByMarker (int aMarker)
 
const ITEM_SET FindItemsByParent (const BOARD_CONNECTED_ITEM *aParent)
 
ITEMFindItemByParent (const BOARD_CONNECTED_ITEM *aParent)
 
bool HasChildren () const
 
NODEGetParent () const
 
bool Overrides (ITEM *aItem) const
 

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

More...
 

Private Types

typedef std::unordered_multimap< JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASHJOINT_MAP
 
typedef JOINT_MAP::value_type TagJointPair
 

Private Member Functions

void Add (std::unique_ptr< ITEM > aItem, bool aAllowRedundant=false)
 
 NODE (const NODE &aB)
 nodes are not copyable More...
 
NODEoperator= (const NODE &aB)
 
JOINTtouchJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
 

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

More...
 
void linkJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
 

touches a joint and links it to an m_item

More...
 
void unlinkJoint (const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
 

unlinks an item from a joint

More...
 
void addSolid (SOLID *aSeg)
 

helpers for adding/removing items

More...
 
void addSegment (SEGMENT *aSeg)
 
void addVia (VIA *aVia)
 
void addArc (ARC *aVia)
 
void removeLine (LINE &aLine)
 
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)
 
void followLine (LINKED_ITEM *aCurrent, int aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool &aGuardHit, bool aStopAtLockedJoints)
 

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

More...
 

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::unordered_set< ITEM * > m_garbageItems
 

Detailed Description

NODE.

Keeps 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 145 of file pns_node.h.

Member Typedef Documentation

◆ ITEM_VECTOR

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

Definition at line 149 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 440 of file pns_node.h.

◆ OBSTACLES

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

Definition at line 150 of file pns_node.h.

◆ OPT_OBSTACLE

Definition at line 148 of file pns_node.h.

◆ TagJointPair

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

Definition at line 442 of file pns_node.h.

Constructor & Destructor Documentation

◆ NODE() [1/2]

PNS::NODE::NODE ( )

Definition at line 47 of file pns_node.cpp.

48 {
49  wxLogTrace( "PNS", "NODE::create %p", this );
50  m_depth = 0;
51  m_root = this;
52  m_parent = NULL;
53  m_maxClearance = 800000; // fixme: depends on how thick traces are.
55  m_index = new INDEX;
56 
57 #ifdef DEBUG
58  allocNodes.insert( this );
59 #endif
60 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:520
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:514
#define NULL
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511
NODE * m_parent
node this node was branched from
Definition: pns_node.h:499

References m_depth, m_index, m_maxClearance, m_parent, m_root, m_ruleResolver, and NULL.

Referenced by Branch().

◆ ~NODE()

PNS::NODE::~NODE ( )

Definition at line 63 of file pns_node.cpp.

64 {
65  wxLogTrace( "PNS", "NODE::delete %p", this );
66 
67  if( !m_children.empty() )
68  {
69  wxLogTrace( "PNS", "attempting to free a node that has kids." );
70  assert( false );
71  }
72 
73 #ifdef DEBUG
74  if( allocNodes.find( this ) == allocNodes.end() )
75  {
76  wxLogTrace( "PNS", "attempting to free an already-free'd node." );
77  assert( false );
78  }
79 
80  allocNodes.erase( this );
81 #endif
82 
83  m_joints.clear();
84 
85  for( ITEM* item : *m_index )
86  {
87  if( item->BelongsTo( this ) )
88  delete item;
89  }
90 
92  unlinkParent();
93 
94  delete m_index;
95 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:505
void unlinkParent()
Definition: pns_node.cpp:140
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
void releaseGarbage()
Definition: pns_node.cpp:1253
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496

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]

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

Function Add()

Adds an item to the current node.

Parameters
aSegmentitem to add
aAllowRedundantif true, duplicate items are allowed (e.g. a segment or via
Returns
true if added at the same coordinates as an existing one)

Definition at line 620 of file pns_node.cpp.

621 {
622  if( aSegment->Seg().A == aSegment->Seg().B )
623  {
624  wxLogTrace( "PNS", "attempting to add a segment with same end coordinates, ignoring." );
625  return false;
626  }
627 
628  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
629  return false;
630 
631  aSegment->SetOwner( this );
632  addSegment( aSegment.release() );
633 
634  return true;
635 }
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:612
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1340

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::MEANDER_PLACER::FixRoute(), PNS::DP_MEANDER_PLACER::FixRoute(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), PNS::LINE_PLACER::removeLoops(), Replace(), PNS::SHOVE::runOptimizer(), 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() [2/6]

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

Definition at line 547 of file pns_node.cpp.

548 {
549  aSolid->SetOwner( this );
550  addSolid( aSolid.release() );
551 }
void addSolid(SOLID *aSeg)
helpers for adding/removing items
Definition: pns_node.cpp:539

References addSolid().

◆ Add() [3/6]

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

Definition at line 559 of file pns_node.cpp.

560 {
561  aVia->SetOwner( this );
562  addVia( aVia.release() );
563 }
void addVia(VIA *aVia)
Definition: pns_node.cpp:553

References addVia().

◆ Add() [4/6]

void PNS::NODE::Add ( std::unique_ptr< ARC aArc)

Definition at line 645 of file pns_node.cpp.

646 {
647  aArc->SetOwner( this );
648  addArc( aArc.release() );
649 }
void addArc(ARC *aVia)
Definition: pns_node.cpp:637

References addArc().

◆ Add() [5/6]

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

Definition at line 565 of file pns_node.cpp.

566 {
567  assert( !aLine.IsLinked() );
568 
569  SHAPE_LINE_CHAIN& l = aLine.Line();
570 
571  for( size_t i = 0; i < l.ArcCount(); i++ )
572  {
573  auto s = l.Arc( i );
574  ARC* rarc;
575 
576  if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(), aLine.Net() ) ) )
577  aLine.LinkSegment( rarc );
578  else
579  {
580  auto newarc = std::make_unique< ARC >( aLine, s );
581  aLine.LinkSegment( newarc.get() );
582  Add( std::move( newarc ), true );
583  }
584  }
585 
586  for( int i = 0; i < l.SegmentCount(); i++ )
587  {
588  if( l.isArc( i ) )
589  continue;
590 
591  SEG s = l.CSegment( i );
592 
593  if( s.A != s.B )
594  {
595  SEGMENT* rseg;
596  if( !aAllowRedundant &&
597  (rseg = findRedundantSegment( s.A, s.B, aLine.Layers(), aLine.Net() )) )
598  {
599  // another line could be referencing this segment too :(
600  aLine.LinkSegment( rseg );
601  }
602  else
603  {
604  std::unique_ptr< SEGMENT > newseg( new SEGMENT( aLine, s ) );
605  aLine.LinkSegment( newseg.get() );
606  Add( std::move( newseg ), true );
607  }
608  }
609  }
610 }
const SHAPE_ARC & Arc(size_t aArc) const
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1340
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1371
Definition: seg.h:39
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
VECTOR2I B
Definition: seg.h:48

References SEG::A, Add(), SHAPE_LINE_CHAIN::Arc(), SEG::B, findRedundantArc(), findRedundantSegment(), PNS::LINE::IsLinked(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::LINE::LinkSegment(), and PNS::ITEM::Net().

◆ Add() [6/6]

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

Definition at line 651 of file pns_node.cpp.

652 {
653  switch( aItem->Kind() )
654  {
655  case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
656  case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
657  case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
658 
659  case ITEM::ARC_T:
660  //todo(snh): Add redundant search
661  Add( ItemCast<ARC>( std::move( aItem ) ) );
662  break;
663 
664  case ITEM::LINE_T:
665  default:
666  assert( false );
667  }
668 }
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620

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

◆ addArc()

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

Definition at line 637 of file pns_node.cpp.

638 {
639  linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
640  linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
641 
642  m_index->Add( aArc );
643 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
touches a joint and links it to an m_item
Definition: pns_node.cpp:1122
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:86

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

Referenced by Add().

◆ addSegment()

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

Definition at line 612 of file pns_node.cpp.

613 {
614  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
615  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
616 
617  m_index->Add( aSeg );
618 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
touches a joint and links it to an m_item
Definition: pns_node.cpp:1122
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:86

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

helpers for adding/removing items

Definition at line 539 of file pns_node.cpp.

540 {
541  if( aSolid->IsRoutable() )
542  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
543 
544  m_index->Add( aSolid );
545 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
touches a joint and links it to an m_item
Definition: pns_node.cpp:1122
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:86

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 553 of file pns_node.cpp.

554 {
555  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
556  m_index->Add( aVia );
557 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
touches a joint and links it to an m_item
Definition: pns_node.cpp:1122
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
void Add(ITEM *aItem)
Function Add()
Definition: pns_index.cpp:86

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 
)

Definition at line 1294 of file pns_node.cpp.

1295 {
1296  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1297 
1298  if( l_cur )
1299  {
1300  for( ITEM*item : *l_cur )
1301  aItems.insert( item );
1302  }
1303 
1304  if( !isRoot() )
1305  {
1306  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1307 
1308  if( l_root )
1309  for( INDEX::NET_ITEMS_LIST::iterator i = l_root->begin(); i!= l_root->end(); ++i )
1310  if( !Overrides( *i ) )
1311  aItems.insert( *i );
1312  }
1313 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:49
bool Overrides(ITEM *aItem) const
checks if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:434
bool isRoot() const
Definition: pns_node.h:477
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.cpp:139

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 = NULL,
bool  aStopAtLockedJoints = false 
)

Function AssembleLine()

Follows 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
Returns
the line

Definition at line 893 of file pns_node.cpp.

894 {
895  const int MaxVerts = 1024 * 16;
896 
897  VECTOR2I corners[MaxVerts + 1];
898  LINKED_ITEM* segs[MaxVerts + 1];
899 
900  LINE pl;
901  bool guardHit = false;
902 
903  int i_start = MaxVerts / 2, i_end = i_start + 1;
904 
905  pl.SetWidth( aSeg->Width() );
906  pl.SetLayers( aSeg->Layers() );
907  pl.SetNet( aSeg->Net() );
908  pl.SetOwner( this );
909 
910  followLine( aSeg, false, i_start, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
911 
912  if( !guardHit )
913  followLine( aSeg, true, i_end, MaxVerts, corners, segs, guardHit, aStopAtLockedJoints );
914 
915  int n = 0;
916 
917  LINKED_ITEM* prev_seg = NULL;
918  bool originSet = false;
919 
920  for( int i = i_start + 1; i < i_end; i++ )
921  {
922  const VECTOR2I& p = corners[i];
923 
924  pl.Line().Append( p );
925 
926  if( segs[i] && prev_seg != segs[i] )
927  {
928  pl.LinkSegment( segs[i] );
929 
930  // latter condition to avoid loops
931  if( segs[i] == aSeg && aOriginSegmentIndex && !originSet )
932  {
933  *aOriginSegmentIndex = n;
934  originSet = true;
935  }
936  n++;
937  }
938 
939  prev_seg = segs[i];
940  }
941 
942  assert( pl.SegmentCount() != 0 );
943 
944  return pl;
945 }
#define NULL
void followLine(LINKED_ITEM *aCurrent, int aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool &aGuardHit, bool aStopAtLockedJoints)
scans the joint map, forming a line starting from segment (current).
Definition: pns_node.cpp:856

References SHAPE_LINE_CHAIN::Append(), followLine(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::LINE::LinkSegment(), PNS::ITEM::Net(), NULL, PNS::LINE::SegmentCount(), PNS::ITEM::SetLayers(), PNS::ITEM::SetNet(), PNS::ITEM::SetOwner(), PNS::LINE::SetWidth(), 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_SKEW_PLACER::Start(), PNS::COMPONENT_DRAGGER::Start(), PNS::MEANDER_PLACER::Start(), PNS::DRAGGER::startDragArc(), and PNS::DRAGGER::startDragSegment().

◆ Branch()

NODE * PNS::NODE::Branch ( )

Function Branch()

Creates a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs to the root. Note that if there are any branches in use, their parents must NOT be deleted.

Returns
the new branch

Definition at line 106 of file pns_node.cpp.

107 {
108  NODE* child = new NODE;
109 
110  wxLogTrace( "PNS", "NODE::branch %p (parent %p)", child, this );
111 
112  m_children.insert( child );
113 
114  child->m_depth = m_depth + 1;
115  child->m_parent = this;
116  child->m_ruleResolver = m_ruleResolver;
117  child->m_root = isRoot() ? this : m_root;
119 
120  // Immmediate offspring of the root branch needs not copy anything. For the rest, deep-copy
121  // joints, overridden item maps and pointers to stored items.
122  if( !isRoot() )
123  {
124  JOINT_MAP::iterator j;
125 
126  for( ITEM* item : *m_index )
127  child->m_index->Add( item );
128 
129  child->m_joints = m_joints;
130  child->m_override = m_override;
131  }
132 
133  wxLogTrace( "PNS", "%d items, %d joints, %d overrides",
134  child->m_index->Size(), (int) child->m_joints.size(), (int) child->m_override.size() );
135 
136  return child;
137 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:505
bool isRoot() const
Definition: pns_node.h:477
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:520
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:514
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:508
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496

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

Referenced by PNS::TOOL_BASE::deleteTraces(), 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::TOPOLOGY::LeadingRatLine(), PNS::DP_MEANDER_PLACER::Move(), PNS::DIFF_PAIR_PLACER::Move(), PNS::LINE_PLACER::Move(), PNS::SHOVE::SetInitialLine(), PNS::SHOVE::ShoveDraggingVia(), PNS::SHOVE::ShoveLines(), PNS::SHOVE::ShoveMultiLines(), PNS::MEANDER_SKEW_PLACER::Start(), PNS::MEANDER_PLACER::Start(), PNS::DP_MEANDER_PLACER::Start(), PNS::DIFF_PAIR_PLACER::tryWalkDp(), and PNS::LINE_PLACER::UnfixRoute().

◆ CheckColliding() [1/3]

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

Function CheckColliding()

Checks 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 427 of file pns_node.cpp.

428 {
429  OBSTACLES obs;
430 
431  obs.reserve( 100 );
432 
433  if( aItemA->Kind() == ITEM::LINE_T )
434  {
435  int n = 0;
436  const LINE* line = static_cast<const LINE*>( aItemA );
437  const SHAPE_LINE_CHAIN& l = line->CLine();
438 
439  for( int i = 0; i < l.SegmentCount(); i++ )
440  {
441  const SEGMENT s( *line, l.CSegment( i ) );
442  n += QueryColliding( &s, obs, aKindMask, 1 );
443 
444  if( n )
445  return OPT_OBSTACLE( obs[0] );
446  }
447 
448  if( line->EndsWithVia() )
449  {
450  n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
451 
452  if( n )
453  return OPT_OBSTACLE( obs[0] );
454  }
455  }
456  else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
457  return OPT_OBSTACLE( obs[0] );
458 
459  return OPT_OBSTACLE();
460 }
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:150
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aForceClearance=-1)
Function QueryColliding()
Definition: pns_node.cpp:278

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(), PNS::OPTIMIZER::checkColliding(), CheckColliding(), PNS::checkDpColliding(), PNS::MEANDER_PLACER::CheckFit(), PNS::DP_MEANDER_PLACER::CheckFit(), PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragWalkaround(), PNS::OPTIMIZER::fanoutCleanup(), PNS::COMPONENT_DRAGGER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::SHOVE::onCollidingSolid(), PNS::SHOVE::processHullSet(), PNS::VIA::PushoutForce(), PNS::SHOVE::reduceSpringback(), PNS::LINE_PLACER::reduceTail(), PNS::LINE_PLACER::reduceToNearestObstacle(), PNS::DIFF_PAIR_PLACER::rhMarkObstacles(), PNS::LINE_PLACER::rhMarkObstacles(), PNS::DIFF_PAIR_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), PNS::WALKAROUND::Route(), PNS::SHOVE::shoveIteration(), PNS::SHOVE::ShoveLines(), PNS::WALKAROUND::singleStep(), PNS::tightenSegment(), PNS::verifyDpBypass(), and PNS::SHOVE::walkaroundLoneVia().

◆ CheckColliding() [2/3]

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

Function CheckColliding()

Checks 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 413 of file pns_node.cpp.

414 {
415  for( const ITEM* item : aSet.CItems() )
416  {
417  OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
418 
419  if( obs )
420  return obs;
421  }
422 
423  return OPT_OBSTACLE();
424 }
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148

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

◆ CheckColliding() [3/3]

bool PNS::NODE::CheckColliding ( const ITEM aItemA,
const ITEM aItemB,
int  aKindMask = ITEM::ANY_T,
int  aForceClearance = -1 
)

Function CheckColliding()

Checks if 2 items collide. and if found, returns the obstacle.

Parameters
aItemAfirst item to find collisions with
aItemBsecond item to find collisions with
aKindMaskmask of obstacle types to take into account
Returns
the obstacle, if found, otherwise empty.

Definition at line 463 of file pns_node.cpp.

464 {
465  assert( aItemB );
466  int clearance;
467  if( aForceClearance >= 0 )
468  clearance = aForceClearance;
469  else
470  clearance = GetClearance( aItemA, aItemB );
471 
472  // fixme: refactor
473  if( aItemA->Kind() == ITEM::LINE_T )
474  clearance += static_cast<const LINE*>( aItemA )->Width() / 2;
475  if( aItemB->Kind() == ITEM::LINE_T )
476  clearance += static_cast<const LINE*>( aItemB )->Width() / 2;
477 
478  return aItemA->Collide( aItemB, clearance, false, nullptr, this );
479 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97

References PNS::ITEM::Collide(), GetClearance(), PNS::ITEM::Kind(), and PNS::ITEM::LINE_T.

◆ ClearRanks()

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

Definition at line 1316 of file pns_node.cpp.

1317 {
1318  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1319  {
1320  (*i)->SetRank( -1 );
1321  (*i)->Mark( (*i)->Marker() & (~aMarkerMask) );
1322  }
1323 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
ITEM_SET::iterator end()
Definition: pns_index.h:141
ITEM_SET::iterator begin()
Definition: pns_index.h:140

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

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

◆ Commit()

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

Function Commit()

Applies the changes from a given branch (aNode) to the root branch. Called 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 1268 of file pns_node.cpp.

1269  {
1270  if( aNode->isRoot() )
1271  return;
1272 
1273  for( ITEM* item : aNode->m_override )
1274  Remove( item );
1275 
1276  for( auto i : *aNode->m_index )
1277  {
1278  i->SetRank( -1 );
1279  i->Unmark();
1280  Add( std::unique_ptr<ITEM>( i ) );
1281  }
1282 
1283  releaseChildren();
1284  releaseGarbage();
1285  }
void releaseChildren()
Definition: pns_node.cpp:1240
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
void releaseGarbage()
Definition: pns_node.cpp:1253
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620

References Add(), isRoot(), m_index, m_override, releaseChildren(), releaseGarbage(), and Remove().

◆ Depth()

int PNS::NODE::Depth ( ) const
inline

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

Definition at line 188 of file pns_node.h.

189  {
190  return m_depth;
191  }
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:520

References m_depth.

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

◆ doRemove()

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

Definition at line 671 of file pns_node.cpp.

672 {
673  // case 1: removing an item that is stored in the root node from any branch:
674  // mark it as overridden, but do not remove
675  if( aItem->BelongsTo( m_root ) && !isRoot() )
676  m_override.insert( aItem );
677 
678  // case 2: the item belongs to this branch or a parent, non-root branch,
679  // or the root itself and we are the root: remove from the index
680  else if( !aItem->BelongsTo( m_root ) || isRoot() )
681  m_index->Remove( aItem );
682 
683  // the item belongs to this particular branch: un-reference it
684  if( aItem->BelongsTo( this ) )
685  {
686  aItem->SetOwner( NULL );
687  m_root->m_garbageItems.insert( aItem );
688  }
689 }
bool isRoot() const
Definition: pns_node.h:477
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
#define NULL
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:508
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:522
void Remove(ITEM *aItem)
Function Remove()
Definition: pns_index.cpp:103

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

Referenced by Remove().

◆ Dump()

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

Prints the contents and joints structure

Definition at line 1141 of file pns_node.cpp.

1142 {
1143 #if 0
1144  std::unordered_set<SEGMENT*> all_segs;
1146 
1147  for( i = m_items.begin(); i != m_items.end(); i++ )
1148  {
1149  if( (*i)->GetKind() == ITEM::SEGMENT_T )
1150  all_segs.insert( static_cast<SEGMENT*>( *i ) );
1151  }
1152 
1153  if( !isRoot() )
1154  {
1155  for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1156  {
1157  if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1158  all_segs.insert( static_cast<SEGMENT*>(*i) );
1159  }
1160  }
1161 
1162  JOINT_MAP::iterator j;
1163 
1164  if( aLong )
1165  for( j = m_joints.begin(); j != m_joints.end(); ++j )
1166  {
1167  wxLogTrace( "PNS", "joint : %s, links : %d\n",
1168  j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1169  JOINT::LINKED_ITEMS::const_iterator k;
1170 
1171  for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1172  {
1173  const ITEM* m_item = *k;
1174 
1175  switch( m_item->GetKind() )
1176  {
1177  case ITEM::SEGMENT_T:
1178  {
1179  const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1180  wxLogTrace( "PNS", " -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1181  seg->GetSeg().B.Format().c_str() );
1182  break;
1183  }
1184 
1185  default:
1186  break;
1187  }
1188  }
1189  }
1190 
1191 
1192  int lines_count = 0;
1193 
1194  while( !all_segs.empty() )
1195  {
1196  SEGMENT* s = *all_segs.begin();
1197  LINE* l = AssembleLine( s );
1198 
1199  LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1200 
1201  if( aLong )
1202  wxLogTrace( "PNS", "Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1203 
1204  for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1205  {
1206  wxLogTrace( "PNS", "%s ", (*j)->GetSeg().A.Format().c_str() );
1207 
1208  if( j + 1 == seg_refs->end() )
1209  wxLogTrace( "PNS", "%s\n", (*j)->GetSeg().B.Format().c_str() );
1210 
1211  all_segs.erase( *j );
1212  }
1213 
1214  lines_count++;
1215  }
1216 
1217  wxLogTrace( "PNS", "Local joints: %d, lines : %d \n", m_joints.size(), lines_count );
1218 #endif
1219 }
bool isRoot() const
Definition: pns_node.h:477
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
SEGMENT_REFS & LinkedSegments()
Returns the list of segments from the owning node that constitute this line (or NULL if the line is n...
Definition: pns_line.h:209
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496

References AssembleLine(), isRoot(), PNS::LINE::LinkedSegments(), m_joints, m_root, and PNS::ITEM::SEGMENT_T.

◆ FindItemByParent()

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

Definition at line 1443 of file pns_node.cpp.

1444 {
1445  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aParent->GetNetCode() );
1446 
1447  if( l_cur )
1448  {
1449  for( ITEM* item : *l_cur )
1450  if( item->Parent() == aParent )
1451  return item;
1452  }
1453 
1454  return NULL;
1455 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:49
int GetNetCode() const
Function GetNetCode.
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
#define NULL
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Function GetItemsForNet()
Definition: pns_index.cpp:139

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

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

◆ FindItemsByParent()

const ITEM_SET PNS::NODE::FindItemsByParent ( const BOARD_CONNECTED_ITEM aParent)

◆ FindJoint() [1/2]

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

Function FindJoint()

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

Returns
the joint, if found, otherwise empty

Definition at line 1027 of file pns_node.cpp.

1028 {
1029  JOINT::HASH_TAG tag;
1030 
1031  tag.net = aNet;
1032  tag.pos = aPos;
1033 
1034  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
1035 
1036  if( f == end && !isRoot() )
1037  {
1038  end = m_root->m_joints.end();
1039  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1040  }
1041 
1042  if( f == end )
1043  return NULL;
1044 
1045  while( f != end )
1046  {
1047  if( f->second.Layers().Overlaps( aLayer ) )
1048  return &f->second;
1049 
1050  ++f;
1051  }
1052 
1053  return NULL;
1054 }
bool isRoot() const
Definition: pns_node.h:477
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
#define NULL
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496

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

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

◆ FindJoint() [2/2]

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

Function FindJoint()

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

Returns
the joint, if found, otherwise empty

Definition at line 389 of file pns_node.h.

390  {
391  return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
392  }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

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

◆ FindLineEnds()

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

finds the joints corresponding to the ends of line aLine

Definition at line 948 of file pns_node.cpp.

949 {
950  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
951  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
952 }
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

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

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

◆ FindLinesBetweenJoints()

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

finds all lines between a pair of joints. Used by the loop removal procedure.

Definition at line 993 of file pns_node.cpp.

994 {
995  for( ITEM* item : aA.LinkList() )
996  {
997  if( item->Kind() == ITEM::SEGMENT_T )
998  {
999  SEGMENT* seg = static_cast<SEGMENT*>( item );
1000  LINE line = AssembleLine( seg );
1001 
1002  if( !line.Layers().Overlaps( aB.Layers() ) )
1003  continue;
1004 
1005  JOINT j_start, j_end;
1006 
1007  FindLineEnds( line, j_start, j_end );
1008 
1009  int id_start = line.CLine().Find( aA.Pos() );
1010  int id_end = line.CLine().Find( aB.Pos() );
1011 
1012  if( id_end < id_start )
1013  std::swap( id_end, id_start );
1014 
1015  if( id_start >= 0 && id_end >= 0 )
1016  {
1017  line.ClipVertexRange( id_start, id_end );
1018  aLines.push_back( line );
1019  }
1020  }
1021  }
1022 
1023  return 0;
1024 }
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:948
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893

References 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 ( const VECTOR2I A,
const VECTOR2I B,
const LAYER_RANGE lr,
int  aNet 
)
private

Definition at line 1371 of file pns_node.cpp.

1373 {
1374  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1375 
1376  if( !jtStart )
1377  return nullptr;
1378 
1379  for( ITEM* item : jtStart->LinkList() )
1380  {
1381  if( item->OfKind( ITEM::ARC_T ) )
1382  {
1383  ARC* seg2 = static_cast<ARC*>( item );
1384 
1385  const VECTOR2I a2( seg2->Anchor( 0 ) );
1386  const VECTOR2I b2( seg2->Anchor( 1 ) );
1387 
1388  if( seg2->Layers().Start() == lr.Start() &&
1389  ((A == a2 && B == b2) || (A == b2 && B == a2)) )
1390  return seg2;
1391  }
1392  }
1393 
1394  return nullptr;
1395 }
int Start() const
Definition: pns_layerset.h:83
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

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

Referenced by Add(), and findRedundantArc().

◆ findRedundantArc() [2/2]

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

Definition at line 1397 of file pns_node.cpp.

1398 {
1399  return findRedundantArc( aArc->Anchor( 0 ), aArc->Anchor( 1 ), aArc->Layers(), aArc->Net() );
1400 }
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1371

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

◆ findRedundantSegment() [1/2]

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

Definition at line 1340 of file pns_node.cpp.

1342 {
1343  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1344 
1345  if( !jtStart )
1346  return nullptr;
1347 
1348  for( ITEM* item : jtStart->LinkList() )
1349  {
1350  if( item->OfKind( ITEM::SEGMENT_T ) )
1351  {
1352  SEGMENT* seg2 = (SEGMENT*)item;
1353 
1354  const VECTOR2I a2( seg2->Seg().A );
1355  const VECTOR2I b2( seg2->Seg().B );
1356 
1357  if( seg2->Layers().Start() == lr.Start() &&
1358  ((A == a2 && B == b2) || (A == b2 && B == a2)) )
1359  return seg2;
1360  }
1361  }
1362 
1363  return nullptr;
1364 }
int Start() const
Definition: pns_layerset.h:83
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

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 1366 of file pns_node.cpp.

1367 {
1368  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1369 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1340

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

◆ followLine()

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

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

Definition at line 856 of file pns_node.cpp.

858 {
859  bool prevReversed = false;
860 
861  const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
862 
863  for( int count = 0 ; ; ++count )
864  {
865  const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
866  const JOINT* jt = FindJoint( p, aCurrent );
867 
868  assert( jt );
869 
870  aCorners[aPos] = jt->Pos();
871  aSegments[aPos] = aCurrent;
872  aPos += ( aScanDirection ? 1 : -1 );
873 
874  if( count && guard == p)
875  {
876  aSegments[aPos] = NULL;
877  aGuardHit = true;
878  break;
879  }
880 
881  bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
882 
883  if( locked || !jt->IsLineCorner() || aPos < 0 || aPos == aLimit )
884  break;
885 
886  aCurrent = jt->NextSegment( aCurrent );
887 
888  prevReversed = ( jt->Pos() == aCurrent->Anchor( aScanDirection ) );
889  }
890 }
#define NULL
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

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

Referenced by AssembleLine().

◆ GetClearance()

int PNS::NODE::GetClearance ( const ITEM aA,
const ITEM aB 
) const

Returns the expected clearance between items a and b.

Definition at line 97 of file pns_node.cpp.

98 {
99  if( !m_ruleResolver )
100  return 100000;
101 
102  return m_ruleResolver->Clearance( aA, aB );
103 }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:514
virtual int Clearance(const ITEM *aA, const ITEM *aB) const =0

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

Referenced by CheckColliding(), PNS::SHOVE::getClearance(), PNS::ROUTER::markViolations(), NearestObstacle(), PNS::OPTIMIZER::CACHE_VISITOR::operator()(), PNS::NODE::DEFAULT_OBSTACLE_VISITOR::operator()(), PNS::VIA::PushoutForce(), and PNS::LINE_PLACER::rhMarkObstacles().

◆ GetMaxClearance()

int PNS::NODE::GetMaxClearance ( ) const
inline

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

Definition at line 159 of file pns_node.h.

160  {
161  return m_maxClearance;
162  }
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511

References m_maxClearance.

◆ GetParent()

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

Definition at line 427 of file pns_node.h.

428  {
429  return m_parent;
430  }
NODE * m_parent
node this node was branched from
Definition: pns_node.h:499

References m_parent.

◆ GetRuleResolver()

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

Definition at line 176 of file pns_node.h.

177  {
178  return m_ruleResolver;
179  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:514

References m_ruleResolver.

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

◆ GetUpdatedItems()

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

Function GetUpdatedItems()

Returns the lists of items removed and added in this branch, with respect to the root branch.

Parameters
aRemovedremoved items
aAddedadded items

Definition at line 1222 of file pns_node.cpp.

1223 {
1224  if( isRoot() )
1225  return;
1226 
1227  if( m_override.size() )
1228  aRemoved.reserve( m_override.size() );
1229 
1230  if( m_index->Size() )
1231  aAdded.reserve( m_index->Size() );
1232 
1233  for( ITEM* item : m_override )
1234  aRemoved.push_back( item );
1235 
1236  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1237  aAdded.push_back( *i );
1238 }
bool isRoot() const
Definition: pns_node.h:477
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:508
ITEM_SET::iterator end()
Definition: pns_index.h:141
ITEM_SET::iterator begin()
Definition: pns_index.h:140
int Size() const
Function Size()
Definition: pns_index.h:138

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

Referenced by PNS::ROUTER::CommitRouting(), and PNS::ROUTER::updateView().

◆ HasChildren()

bool PNS::NODE::HasChildren ( ) const
inline

Definition at line 422 of file pns_node.h.

423  {
424  return !m_children.empty();
425  }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:505

References m_children.

◆ HitTest()

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

Function HitTest()

Finds all items that contain the point aPoint.

Parameters
aPointthe point
Returns
the items

Definition at line 510 of file pns_node.cpp.

511 {
512  ITEM_SET items;
513 
514  // fixme: we treat a point as an infinitely small circle - this is inefficient.
515  SHAPE_CIRCLE s( aPoint, 0 );
516  HIT_VISITOR visitor( items, aPoint );
517  visitor.SetWorld( this, NULL );
518 
519  m_index->Query( &s, m_maxClearance, visitor );
520 
521  if( !isRoot() ) // fixme: could be made cleaner
522  {
523  ITEM_SET items_root;
524  visitor.SetWorld( m_root, NULL );
525  HIT_VISITOR visitor_root( items_root, aPoint );
526  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
527 
528  for( ITEM* item : items_root.Items() )
529  {
530  if( !Overrides( item ) )
531  items.Add( item );
532  }
533  }
534 
535  return items;
536 }
bool Overrides(ITEM *aItem) const
checks if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:434
bool isRoot() const
Definition: pns_node.h:477
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
#define NULL
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:138
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:173
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511

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

◆ isRoot()

bool PNS::NODE::isRoot ( ) const
inlineprivate

Definition at line 477 of file pns_node.h.

478  {
479  return m_parent == NULL;
480  }
#define NULL
NODE * m_parent
node this node was branched from
Definition: pns_node.h:499

References m_parent, and NULL.

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

◆ JointCount()

int PNS::NODE::JointCount ( ) const
inline

Returns the number of joints

Definition at line 182 of file pns_node.h.

183  {
184  return m_joints.size();
185  }
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496

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

touches a joint and links it to an m_item

Definition at line 1122 of file pns_node.cpp.

1124 {
1125  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1126 
1127  jt.Link( aWhere );
1128 }
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
tries to find matching joint and creates a new one if not found
Definition: pns_node.cpp:1064

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 1057 of file pns_node.cpp.

1058 {
1059  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1060  jt.Lock( aLock );
1061 }
void Lock(bool aLock=true)
Definition: pns_joint.h:245
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
tries to find matching joint and creates a new one if not found
Definition: pns_node.cpp:1064

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 aItem,
int  aKindMask = ITEM::ANY_T,
const std::set< ITEM * > *  aRestrictedSet = NULL 
)

Function NearestObstacle()

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

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 304 of file pns_node.cpp.

306 {
307  OBSTACLES obs_list;
308  bool found_isects = false;
309 
310  const SHAPE_LINE_CHAIN& line = aItem->CLine();
311 
312  obs_list.reserve( 100 );
313 
314  int n = 0;
315 
316  for( int i = 0; i < line.SegmentCount(); i++ )
317  {
318  const SEGMENT s( *aItem, line.CSegment( i ) );
319  n += QueryColliding( &s, obs_list, aKindMask );
320  }
321 
322  if( aItem->EndsWithVia() )
323  n += QueryColliding( &aItem->Via(), obs_list, aKindMask );
324 
325  if( !n )
326  return OPT_OBSTACLE();
327 
328  LINE& aLine = (LINE&) *aItem;
329 
330  OBSTACLE nearest;
331  nearest.m_item = NULL;
332  nearest.m_distFirst = INT_MAX;
333 
334  for( const OBSTACLE& obs : obs_list )
335  {
336  VECTOR2I ip_last;
337  int dist_max = INT_MIN;
338 
339  if( aRestrictedSet && aRestrictedSet->find( obs.m_item ) == aRestrictedSet->end() )
340  continue;
341 
342  std::vector<SHAPE_LINE_CHAIN::INTERSECTION> isect_list;
343 
344  int clearance = GetClearance( obs.m_item, &aLine );
345 
346  SHAPE_LINE_CHAIN hull = obs.m_item->Hull( clearance, aItem->Width() );
347 
348  if( aLine.EndsWithVia() )
349  {
350  clearance = GetClearance( obs.m_item, &aLine.Via() );
351 
352  SHAPE_LINE_CHAIN viaHull = aLine.Via().Hull( clearance, aItem->Width() );
353 
354  viaHull.Intersect( hull, isect_list );
355 
356  for( const SHAPE_LINE_CHAIN::INTERSECTION& isect : isect_list )
357  {
358  int dist = aLine.CLine().Length() +
359  ( isect.p - aLine.Via().Pos() ).EuclideanNorm();
360 
361  if( dist < nearest.m_distFirst )
362  {
363  found_isects = true;
364  nearest.m_distFirst = dist;
365  nearest.m_ipFirst = isect.p;
366  nearest.m_item = obs.m_item;
367  nearest.m_hull = hull;
368  }
369 
370  if( dist > dist_max )
371  {
372  dist_max = dist;
373  ip_last = isect.p;
374  }
375  }
376  }
377 
378  isect_list.clear();
379 
380  hull.Intersect( aLine.CLine(), isect_list );
381 
382  for( const SHAPE_LINE_CHAIN::INTERSECTION& isect : isect_list )
383  {
384  int dist = aLine.CLine().PathLength( isect.p );
385 
386  if( dist < nearest.m_distFirst )
387  {
388  found_isects = true;
389  nearest.m_distFirst = dist;
390  nearest.m_ipFirst = isect.p;
391  nearest.m_item = obs.m_item;
392  nearest.m_hull = hull;
393  }
394 
395  if( dist > dist_max )
396  {
397  dist_max = dist;
398  ip_last = isect.p;
399  }
400  }
401 
402  nearest.m_ipLast = ip_last;
403  nearest.m_distLast = dist_max;
404  }
405 
406  if( !found_isects )
407  nearest.m_item = obs_list[0].m_item;
408 
409  return nearest;
410 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
static const int dist[10][10]
Definition: ar_matrix.cpp:326
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
#define NULL
int SegmentCount() const
Function SegmentCount()
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:150
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aForceClearance=-1)
Function QueryColliding()
Definition: pns_node.cpp:278

References PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CSegment(), dist, PNS::LINE::EndsWithVia(), EuclideanNorm(), GetClearance(), PNS::VIA::Hull(), SHAPE_LINE_CHAIN::Intersect(), SHAPE_LINE_CHAIN::Length(), PNS::OBSTACLE::m_distFirst, PNS::OBSTACLE::m_distLast, PNS::OBSTACLE::m_hull, PNS::OBSTACLE::m_ipFirst, PNS::OBSTACLE::m_ipLast, PNS::OBSTACLE::m_item, NULL, SHAPE_LINE_CHAIN::PathLength(), PNS::VIA::Pos(), QueryColliding(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::Via(), and PNS::LINE::Width().

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

◆ operator=()

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

◆ Overrides()

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

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

Definition at line 434 of file pns_node.h.

435  {
436  return m_override.find( aItem ) != m_override.end();
437  }
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:508

References m_override.

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

◆ QueryColliding() [1/2]

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

Function QueryColliding()

Finds items collliding (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

Definition at line 278 of file pns_node.cpp.

280 {
281  DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly );
282 
283 #ifdef DEBUG
284  assert( allocNodes.find( this ) != allocNodes.end() );
285 #endif
286 
287  visitor.SetCountLimit( aLimitCount );
288  visitor.SetWorld( this, NULL );
289  visitor.m_forceClearance = aForceClearance;
290  // first, look for colliding items in the local index
291  m_index->Query( aItem, m_maxClearance, visitor );
292 
293  // if we haven't found enough items, look in the root branch as well.
294  if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
295  {
296  visitor.SetWorld( m_root, this );
297  m_root->m_index->Query( aItem, m_maxClearance, visitor );
298  }
299 
300  return aObstacles.size();
301 }
bool isRoot() const
Definition: pns_node.h:477
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
#define NULL
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:173
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511

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

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

◆ QueryColliding() [2/2]

int PNS::NODE::QueryColliding ( const ITEM aItem,
OBSTACLE_VISITOR aVisitor 
)

Definition at line 262 of file pns_node.cpp.

263 {
264  aVisitor.SetWorld( this, NULL );
265  m_index->Query( aItem, m_maxClearance, aVisitor );
266 
267  // if we haven't found enough items, look in the root branch as well.
268  if( !isRoot() )
269  {
270  aVisitor.SetWorld( m_root, this );
271  m_root->m_index->Query( aItem, m_maxClearance, aVisitor );
272  }
273 
274  return 0;
275 }
bool isRoot() const
Definition: pns_node.h:477
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
#define NULL
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor)
Function Query()
Definition: pns_index.h:173
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511

References isRoot(), m_index, m_maxClearance, m_root, NULL, PNS::INDEX::Query(), and PNS::OBSTACLE_VISITOR::SetWorld().

◆ QueryJoints()

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

Definition at line 1403 of file pns_node.cpp.

1408 {
1409  int n = 0;
1410 
1411  aJoints.clear();
1412 
1413  for( auto j = m_joints.begin(); j != m_joints.end(); ++j )
1414  {
1415  if ( aBox.Contains(j->second.Pos()) && j->second.LinkCount ( aKindMask ) )
1416  {
1417  aJoints.push_back( &j->second );
1418  n++;
1419 
1420  }
1421  }
1422 
1423  if ( isRoot() )
1424  return n;
1425 
1426  for( auto j = m_root->m_joints.begin(); j != m_root->m_joints.end(); ++j )
1427  {
1428  if( ! Overrides( &j->second) )
1429  { if ( aBox.Contains(j->second.Pos()) && j->second.LinkCount ( aKindMask ) )
1430  {
1431  aJoints.push_back( &j->second );
1432  n++;
1433  }
1434  }
1435  }
1436 
1437  return n;
1438 
1439 
1440 }
bool Overrides(ITEM *aItem) const
checks if this branch contains an updated version of the m_item from the root branch.
Definition: pns_node.h:434
bool isRoot() const
Definition: pns_node.h:477
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:150
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496

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

Referenced by PNS::KEEP_TOPOLOGY_CONSTRAINT::Check().

◆ rebuildJoint()

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

Definition at line 706 of file pns_node.cpp.

707 {
708  // We have to split a single joint (associated with a via or a pad, binding together multiple layers)
709  // into multiple independent joints. As I'm a lazy bastard, I simply delete the via/solid and all its links and re-insert them.
710 
711  JOINT::LINKED_ITEMS links( aJoint->LinkList() );
712  JOINT::HASH_TAG tag;
713  int net = aItem->Net();
714 
715  tag.net = net;
716  tag.pos = aJoint->Pos();
717 
718  bool split;
719  do
720  {
721  split = false;
722  auto range = m_joints.equal_range( tag );
723 
724  if( range.first == m_joints.end() )
725  break;
726 
727  // find and remove all joints containing the via to be removed
728 
729  for( auto f = range.first; f != range.second; ++f )
730  {
731  if( aItem->LayersOverlap( &f->second ) )
732  {
733  m_joints.erase( f );
734  split = true;
735  break;
736  }
737  }
738  } while( split );
739 
740  // and re-link them, using the former via's link list
741  for(ITEM* link : links)
742  {
743  if( link != aItem )
744  linkJoint( tag.pos, link->Layers(), net, link );
745  }
746 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
touches a joint and links it to an m_item
Definition: pns_node.cpp:1122
ITEM_SET::ENTRIES LINKED_ITEMS
Definition: pns_joint.h:46
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496

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

Referenced by removeSolidIndex(), and removeViaIndex().

◆ releaseChildren()

void PNS::NODE::releaseChildren ( )
private

Definition at line 1240 of file pns_node.cpp.

1241 {
1242  // copy the kids as the NODE destructor erases the item from the parent node.
1243  std::set<NODE*> kids = m_children;
1244 
1245  for( NODE* node : kids )
1246  {
1247  node->releaseChildren();
1248  delete node;
1249  }
1250 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:505

References m_children.

Referenced by Commit(), and KillChildren().

◆ releaseGarbage()

void PNS::NODE::releaseGarbage ( )
private

Definition at line 1253 of file pns_node.cpp.

1254 {
1255  if( !isRoot() )
1256  return;
1257 
1258  for( ITEM* item : m_garbageItems )
1259  {
1260  if( !item->BelongsTo( this ) )
1261  delete item;
1262  }
1263 
1264  m_garbageItems.clear();
1265 }
bool isRoot() const
Definition: pns_node.h:477
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:522

References isRoot(), and m_garbageItems.

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

◆ Remove() [1/6]

◆ Remove() [2/6]

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

Definition at line 778 of file pns_node.cpp.

779 {
780  removeSolidIndex( aSolid );
781  doRemove( aSolid );
782 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:671
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:757

References doRemove(), and removeSolidIndex().

◆ Remove() [3/6]

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

Definition at line 784 of file pns_node.cpp.

785 {
786  removeViaIndex( aVia );
787  doRemove( aVia );
788 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:671
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:749

References doRemove(), and removeViaIndex().

◆ Remove() [4/6]

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

Definition at line 790 of file pns_node.cpp.

791 {
792  removeSegmentIndex( aSegment );
793  doRemove( aSegment );
794 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:671
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:692

References doRemove(), and removeSegmentIndex().

◆ Remove() [5/6]

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

Definition at line 802 of file pns_node.cpp.

803 {
804  switch( aItem->Kind() )
805  {
806  case ITEM::ARC_T:
807  Remove( static_cast<ARC*>( aItem ) );
808  break;
809 
810  case ITEM::SOLID_T:
811  Remove( static_cast<SOLID*>( aItem ) );
812  break;
813 
814  case ITEM::SEGMENT_T:
815  Remove( static_cast<SEGMENT*>( aItem ) );
816  break;
817 
818  case ITEM::LINE_T:
819  {
820  auto l = static_cast<LINE *> ( aItem );
821 
822  for ( auto s : l->LinkedSegments() )
823  Remove( s );
824 
825  break;
826  }
827 
828  case ITEM::VIA_T:
829  Remove( static_cast<VIA*>( aItem ) );
830  break;
831 
832  default:
833  break;
834  }
835 }
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796

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

◆ Remove() [6/6]

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

Function Remove()

Just as the name says, removes a line from this branch.

Parameters
aLineitem to remove

Definition at line 838 of file pns_node.cpp.

839 {
840  // LINE does not have a seperate remover, as LINEs are never truly a member of the tree
841  std::vector<LINKED_ITEM*>& segRefs = aLine.LinkedSegments();
842 
843  for( auto li : segRefs )
844  {
845  if( li->OfKind( ITEM::SEGMENT_T ) )
846  Remove( static_cast<SEGMENT*>( li ) );
847  else if( li->OfKind( ITEM::ARC_T ) )
848  Remove( static_cast<ARC*>( li ) );
849  }
850 
851  aLine.SetOwner( nullptr );
852  aLine.ClearSegmentLinks();
853 }
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796

References PNS::ITEM::ARC_T, PNS::LINE::ClearSegmentLinks(), PNS::LINE::LinkedSegments(), Remove(), PNS::ITEM::SEGMENT_T, and PNS::ITEM::SetOwner().

◆ removeArcIndex()

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

Definition at line 699 of file pns_node.cpp.

700 {
701  unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
702  unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
703 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1131

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 1326 of file pns_node.cpp.

1327 {
1328  std::list<ITEM*> garbage;
1329 
1330  for( ITEM* item : *m_index )
1331  {
1332  if( item->Marker() & aMarker )
1333  garbage.push_back( item );
1334  }
1335 
1336  for( ITEM* item : garbage )
1337  Remove( item );
1338 }
INDEX * m_index
Geometric/Net index of the items
Definition: pns_node.h:517
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796

References m_index, and Remove().

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

◆ removeLine()

void PNS::NODE::removeLine ( LINE aLine)
private

◆ removeSegmentIndex()

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

Definition at line 692 of file pns_node.cpp.

693 {
694  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
695  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
696 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
unlinks an item from a joint
Definition: pns_node.cpp:1131

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 757 of file pns_node.cpp.

758 {
759  // fixme: redundant code
760  JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
761  assert( jt );
762  rebuildJoint( jt, aSolid );
763 }
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:706
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

References FindJoint(), 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 749 of file pns_node.cpp.

750 {
751  JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
752  assert( jt );
753  rebuildJoint( jt, aVia );
754 }
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:706
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1027

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 
)

Function Replace()

Just as the name says, replaces an item with another one.

Parameters
aOldItemitem to be removed
aNewItemitem add instead

Definition at line 766 of file pns_node.cpp.

767 {
768  Remove( aOldItem );
769  Add( std::move( aNewItem ) );
770 }
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620

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 772 of file pns_node.cpp.

773 {
774  Remove( aOldLine );
775  Add( aNewLine );
776 }
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620

References Add(), and Remove().

◆ SetMaxClearance()

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

Sets the worst-case clerance between any pair of items

Definition at line 165 of file pns_node.h.

166  {
167  m_maxClearance = aClearance;
168  }
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:511

References m_maxClearance.

Referenced by PNS_KICAD_IFACE_BASE::SyncWorld().

◆ SetRuleResolver()

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

Assigns a clerance resolution function object

Definition at line 171 of file pns_node.h.

172  {
173  m_ruleResolver = aFunc;
174  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver
Definition: pns_node.h:514

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

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

Definition at line 1064 of file pns_node.cpp.

1065 {
1066  JOINT::HASH_TAG tag;
1067 
1068  tag.pos = aPos;
1069  tag.net = aNet;
1070 
1071  // try to find the joint in this node.
1072  JOINT_MAP::iterator f = m_joints.find( tag );
1073 
1074  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1075 
1076  // not found and we are not root? find in the root and copy results here.
1077  if( f == m_joints.end() && !isRoot() )
1078  {
1079  range = m_root->m_joints.equal_range( tag );
1080 
1081  for( f = range.first; f != range.second; ++f )
1082  m_joints.insert( *f );
1083  }
1084 
1085  // now insert and combine overlapping joints
1086  JOINT jt( aPos, aLayers, aNet );
1087 
1088  bool merged;
1089 
1090  do
1091  {
1092  merged = false;
1093  range = m_joints.equal_range( tag );
1094 
1095  if( range.first == m_joints.end() )
1096  break;
1097 
1098  for( f = range.first; f != range.second; ++f )
1099  {
1100  if( aLayers.Overlaps( f->second.Layers() ) )
1101  {
1102  jt.Merge( f->second );
1103  m_joints.erase( f );
1104  merged = true;
1105  break;
1106  }
1107  }
1108  }
1109  while( merged );
1110 
1111  return m_joints.insert( TagJointPair( tag, jt ) )->second;
1112 }
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:68
bool isRoot() const
Definition: pns_node.h:477
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:502
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:442
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:496

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

unlinks an item from a joint

Definition at line 1131 of file pns_node.cpp.

1133 {
1134  // fixme: remove dangling joints
1135  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1136 
1137  jt.Unlink( aWhere );
1138 }
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
tries to find matching joint and creates a new one if not found
Definition: pns_node.cpp:1064

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

Referenced by removeArcIndex(), and removeSegmentIndex().

◆ unlinkParent()

void PNS::NODE::unlinkParent ( )
private

Definition at line 140 of file pns_node.cpp.

141 {
142  if( isRoot() )
143  return;
144 
145  m_parent->m_children.erase( this );
146 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:505
bool isRoot() const
Definition: pns_node.h:477
NODE * m_parent
node this node was branched from
Definition: pns_node.h:499

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 505 of file pns_node.h.

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

◆ m_depth

int PNS::NODE::m_depth
private

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

Definition at line 520 of file pns_node.h.

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

◆ m_garbageItems

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

Definition at line 522 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 496 of file pns_node.h.

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

◆ m_maxClearance

int PNS::NODE::m_maxClearance
private

worst case item-item clearance

Definition at line 511 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 508 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 499 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 502 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 514 of file pns_node.h.

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


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