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

typedef OPT< 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) const
 
int GetHoleClearance (const ITEM *aA, const ITEM *aB) const
 
int GetHoleToHoleClearance (const ITEM *aA, const ITEM *aB) 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)
 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=NULL)
 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)
 
void Add (std::unique_ptr< ARC > aArc)
 
void Add (LINE &aLine, bool aAllowRedundant=false)
 
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=NULL, bool aStopAtLockedJoints=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 ()
 

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

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

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

Member Typedef Documentation

◆ ITEM_VECTOR

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

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

◆ OBSTACLES

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

Definition at line 149 of file pns_node.h.

◆ OPT_OBSTACLE

Definition at line 147 of file pns_node.h.

◆ TagJointPair

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

Definition at line 438 of file pns_node.h.

Constructor & Destructor Documentation

◆ NODE() [1/2]

PNS::NODE::NODE ( )

Definition at line 53 of file pns_node.cpp.

54 {
55  m_depth = 0;
56  m_root = this;
57  m_parent = NULL;
58  m_maxClearance = 800000; // fixme: depends on how thick traces are.
60  m_index = new INDEX;
61 
62 #ifdef DEBUG
63  allocNodes.insert( this );
64 #endif
65 }
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:453
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:451
#define NULL
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:450
NODE * m_parent
node this node was branched from
Definition: pns_node.h:443

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

Referenced by Branch().

◆ ~NODE()

PNS::NODE::~NODE ( )

Return the expected clearance between items a and b.

Definition at line 68 of file pns_node.cpp.

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

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 
)

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

622 {
623  if( aSegment->Seg().A == aSegment->Seg().B )
624  {
625  wxLogTrace( "PNS", "attempting to add a segment with same end coordinates, ignoring." );
626  return false;
627  }
628 
629  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
630  return false;
631 
632  aSegment->SetOwner( this );
633  addSegment( aSegment.release() );
634 
635  return true;
636 }
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:1429

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(), 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() [2/6]

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

Definition at line 538 of file pns_node.cpp.

539 {
540  aSolid->SetOwner( this );
541  addSolid( aSolid.release() );
542 }
void addSolid(SOLID *aSeg)
Definition: pns_node.cpp:529

References addSolid().

◆ Add() [3/6]

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

Definition at line 553 of file pns_node.cpp.

554 {
555  aVia->SetOwner( this );
556  addVia( aVia.release() );
557 }
void addVia(VIA *aVia)
Definition: pns_node.cpp:545

References addVia().

◆ Add() [4/6]

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

Definition at line 648 of file pns_node.cpp.

649 {
650  aArc->SetOwner( this );
651  addArc( aArc.release() );
652 }
void addArc(ARC *aVia)
Definition: pns_node.cpp:639

References addArc().

◆ Add() [5/6]

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

Definition at line 560 of file pns_node.cpp.

561 {
562  assert( !aLine.IsLinked() );
563 
564  SHAPE_LINE_CHAIN& l = aLine.Line();
565 
566  for( size_t i = 0; i < l.ArcCount(); i++ )
567  {
568  auto s = l.Arc( i );
569  ARC* rarc;
570 
571  if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(),
572  aLine.Net() ) ) )
573  {
574  aLine.Link( rarc );
575  }
576  else
577  {
578  auto newarc = std::make_unique< ARC >( aLine, s );
579  aLine.Link( newarc.get() );
580  Add( std::move( newarc ), true );
581  }
582  }
583 
584  for( int i = 0; i < l.SegmentCount(); i++ )
585  {
586  if( l.isArc( i ) )
587  continue;
588 
589  SEG s = l.CSegment( i );
590 
591  if( s.A != s.B )
592  {
593  SEGMENT* rseg;
594 
595  if( !aAllowRedundant && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(),
596  aLine.Net() ) ) )
597  {
598  // another line could be referencing this segment too :(
599  aLine.Link( rseg );
600  }
601  else
602  {
603  std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
604  aLine.Link( newseg.get() );
605  Add( std::move( newseg ), true );
606  }
607  }
608  }
609 }
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:1429
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1464
Definition: seg.h:40
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:48
usual segment : line with rounded ends
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621
VECTOR2I B
Definition: seg.h:49

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

◆ Add() [6/6]

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

Definition at line 655 of file pns_node.cpp.

656 {
657  switch( aItem->Kind() )
658  {
659  case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
660  case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
661  case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
662 
663  case ITEM::ARC_T:
664  //todo(snh): Add redundant search
665  Add( ItemCast<ARC>( std::move( aItem ) ) );
666  break;
667 
668  case ITEM::LINE_T:
669  default:
670  assert( false );
671  }
672 }
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621

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

640 {
641  linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
642  linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
643 
644  m_index->Add( aArc );
645 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1203
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28

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)
Unlink an item from a joint.
Definition: pns_node.cpp:1203
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28

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

530 {
531  if( aSolid->IsRoutable() )
532  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
533 
534  m_index->Add( aSolid );
535 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1203
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28

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

546 {
547  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
548 
549  m_index->Add( aVia );
550 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1203
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
void Add(ITEM *aItem)
Adds item to the spatial index.
Definition: pns_index.cpp:28

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

1376 {
1377  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1378 
1379  if( l_cur )
1380  {
1381  for( ITEM* item : *l_cur )
1382  {
1383  if( item->OfKind( aKindMask ) && item->IsRoutable() )
1384  aItems.insert( item );
1385  }
1386  }
1387 
1388  if( !isRoot() )
1389  {
1390  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1391 
1392  if( l_root )
1393  {
1394  for( ITEM* item : *l_root )
1395  {
1396  if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1397  aItems.insert( item );
1398  }
1399  }
1400  }
1401 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
bool Overrides(ITEM *aItem) const
Definition: pns_node.h:378
bool isRoot() const
Definition: pns_node.h:418
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Returns list of all items in a given net.
Definition: pns_index.cpp:71

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 
)

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.
Returns
the linePrint the contents and joints structure.

Definition at line 920 of file pns_node.cpp.

922 {
923  const int MaxVerts = 1024 * 16;
924 
925  std::array<VECTOR2I, MaxVerts + 1> corners;
926  std::array<LINKED_ITEM*, MaxVerts + 1> segs;
927  std::array<bool, MaxVerts + 1> arcReversed;
928 
929  LINE pl;
930  bool guardHit = false;
931 
932  int i_start = MaxVerts / 2;
933  int i_end = i_start + 1;
934 
935  pl.SetWidth( aSeg->Width() );
936  pl.SetLayers( aSeg->Layers() );
937  pl.SetNet( aSeg->Net() );
938  pl.SetOwner( this );
939 
940  followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
941  guardHit, aStopAtLockedJoints );
942 
943  if( !guardHit )
944  {
945  followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
946  guardHit, aStopAtLockedJoints );
947  }
948 
949  int n = 0;
950 
951  LINKED_ITEM* prev_seg = NULL;
952  bool originSet = false;
953 
954  SHAPE_LINE_CHAIN& line = pl.Line();
955 
956  for( int i = i_start + 1; i < i_end; i++ )
957  {
958  const VECTOR2I& p = corners[i];
959  LINKED_ITEM* li = segs[i];
960 
961  if( !li || li->Kind() != ITEM::ARC_T )
962  line.Append( p );
963 
964  if( li && prev_seg != li )
965  {
966  int segIdxIncrement = 1;
967 
968  if( li->Kind() == ITEM::ARC_T )
969  {
970  const ARC* arc = static_cast<const ARC*>( li );
971  const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape() );
972 
973  int nSegs = line.PointCount();
974  VECTOR2I last = nSegs ? line.CPoint( -1 ) : VECTOR2I();
975  ssize_t lastShape = nSegs ? line.CShapes()[nSegs - 1] : -1;
976 
977  line.Append( arcReversed[i] ? sa->Reversed() : *sa );
978 
979  segIdxIncrement = line.PointCount() - nSegs - 1;
980 
981  // Are we adding an arc after an arc? add the hidden segment if the arcs overlap.
982  // If they don't overlap, don't add this, as it will have been added as a segment.
983  if( lastShape >= 0 && last == line.CPoint( nSegs ) )
984  segIdxIncrement++;
985  }
986 
987  pl.Link( li );
988 
989  // latter condition to avoid loops
990  if( li == aSeg && aOriginSegmentIndex && !originSet )
991  {
992  wxASSERT( n < line.SegmentCount() ||
993  ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
994  *aOriginSegmentIndex = n;
995  originSet = true;
996  }
997 
998  n += segIdxIncrement;
999  }
1000 
1001  prev_seg = li;
1002  }
1003 
1004  // Remove duplicate verts, but do NOT remove colinear segments here!
1005  pl.Line().Simplify( false );
1006 
1007  assert( pl.SegmentCount() != 0 );
1008 
1009  return pl;
1010 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Function PointCount()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const std::vector< ssize_t > & CShapes() const
const VECTOR2I & CPoint(int aIndex) const
Function Point()
#define NULL
int SegmentCount() const
Function SegmentCount()
SHAPE_LINE_CHAIN.
void followLine(LINKED_ITEM *aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool *aArcReversed, bool &aGuardHit, bool aStopAtLockedJoints)
Definition: pns_node.cpp:871
SHAPE_ARC Reversed() const
Definition: shape_arc.cpp:522

References SHAPE_LINE_CHAIN::Append(), PNS::ITEM::ARC_T, SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CShapes(), followLine(), PNS::ITEM::Kind(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::LINK_HOLDER::Link(), PNS::ITEM::Net(), NULL, SHAPE_LINE_CHAIN::PointCount(), SHAPE_ARC::Reversed(), PNS::ITEM::SEGMENT_T, PNS::LINE::SegmentCount(), SHAPE_LINE_CHAIN::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_SKEW_PLACER::Start(), PNS::COMPONENT_DRAGGER::Start(), PNS::MEANDER_PLACER::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 127 of file pns_node.cpp.

128 {
129  NODE* child = new NODE;
130 
131  m_children.insert( child );
132 
133  child->m_depth = m_depth + 1;
134  child->m_parent = this;
135  child->m_ruleResolver = m_ruleResolver;
136  child->m_root = isRoot() ? this : m_root;
138 
139  // Immediate offspring of the root branch needs not copy anything. For the rest, deep-copy
140  // joints, overridden item maps and pointers to stored items.
141  if( !isRoot() )
142  {
143  JOINT_MAP::iterator j;
144 
145  for( ITEM* item : *m_index )
146  child->m_index->Add( item );
147 
148  child->m_joints = m_joints;
149  child->m_override = m_override;
150  }
151 
152 #if 0
153  wxLogTrace( "PNS", "%d items, %d joints, %d overrides",
154  child->m_index->Size(),
155  (int) child->m_joints.size(),
156  (int) child->m_override.size() );
157 #endif
158 
159  return child;
160 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:445
bool isRoot() const
Definition: pns_node.h:418
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Definition: pns_node.h:453
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:451
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:447
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:450
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:440

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::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/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 433 of file pns_node.cpp.

434 {
435  OBSTACLES obs;
436 
437  obs.reserve( 100 );
438 
439  if( aItemA->Kind() == ITEM::LINE_T )
440  {
441  int n = 0;
442  const LINE* line = static_cast<const LINE*>( aItemA );
443  const SHAPE_LINE_CHAIN& l = line->CLine();
444 
445  for( int i = 0; i < l.SegmentCount(); i++ )
446  {
447  const SEGMENT s( *line, l.CSegment( i ) );
448  n += QueryColliding( &s, obs, aKindMask, 1 );
449 
450  if( n )
451  return OPT_OBSTACLE( obs[0] );
452  }
453 
454  if( line->EndsWithVia() )
455  {
456  n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
457 
458  if( n )
459  return OPT_OBSTACLE( obs[0] );
460  }
461  }
462  else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
463  {
464  return OPT_OBSTACLE( obs[0] );
465  }
466 
467  return OPT_OBSTACLE();
468 }
int SegmentCount() const
Function SegmentCount()
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true)
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:255
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
usual segment : line with rounded ends
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:149

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

420 {
421  for( const ITEM* item : aSet.CItems() )
422  {
423  OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
424 
425  if( obs )
426  return obs;
427  }
428 
429  return OPT_OBSTACLE();
430 }
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:433
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147

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

◆ ClearRanks()

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

Definition at line 1404 of file pns_node.cpp.

1405 {
1406  for( ITEM* item : *m_index )
1407  {
1408  item->SetRank( -1 );
1409  item->Mark( item->Marker() & ~aMarkerMask );
1410  }
1411 }
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452

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

1350 {
1351  if( aNode->isRoot() )
1352  return;
1353 
1354  for( ITEM* item : aNode->m_override )
1355  Remove( item );
1356 
1357  for( ITEM* item : *aNode->m_index )
1358  {
1359  item->SetRank( -1 );
1360  item->Unmark();
1361  Add( std::unique_ptr<ITEM>( item ) );
1362  }
1363 
1364  releaseChildren();
1365  releaseGarbage();
1366 }
void releaseChildren()
Definition: pns_node.cpp:1321
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:810
void releaseGarbage()
Definition: pns_node.cpp:1334
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621

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

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

References m_depth.

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

◆ doRemove()

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

Definition at line 675 of file pns_node.cpp.

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

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)

Definition at line 1220 of file pns_node.cpp.

1221 {
1222 #if 0
1223  std::unordered_set<SEGMENT*> all_segs;
1225 
1226  for( i = m_items.begin(); i != m_items.end(); i++ )
1227  {
1228  if( (*i)->GetKind() == ITEM::SEGMENT_T )
1229  all_segs.insert( static_cast<SEGMENT*>( *i ) );
1230  }
1231 
1232  if( !isRoot() )
1233  {
1234  for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1235  {
1236  if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1237  all_segs.insert( static_cast<SEGMENT*>(*i) );
1238  }
1239  }
1240 
1241  JOINT_MAP::iterator j;
1242 
1243  if( aLong )
1244  {
1245  for( j = m_joints.begin(); j != m_joints.end(); ++j )
1246  {
1247  wxLogTrace( "PNS", "joint : %s, links : %d\n",
1248  j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1249  JOINT::LINKED_ITEMS::const_iterator k;
1250 
1251  for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1252  {
1253  const ITEM* m_item = *k;
1254 
1255  switch( m_item->GetKind() )
1256  {
1257  case ITEM::SEGMENT_T:
1258  {
1259  const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1260  wxLogTrace( "PNS", " -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1261  seg->GetSeg().B.Format().c_str() );
1262  break;
1263  }
1264 
1265  default:
1266  break;
1267  }
1268  }
1269  }
1270  }
1271 
1272  int lines_count = 0;
1273 
1274  while( !all_segs.empty() )
1275  {
1276  SEGMENT* s = *all_segs.begin();
1277  LINE* l = AssembleLine( s );
1278 
1279  LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1280 
1281  if( aLong )
1282  wxLogTrace( "PNS", "Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1283 
1284  for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1285  {
1286  wxLogTrace( "PNS", "%s ", (*j)->GetSeg().A.Format().c_str() );
1287 
1288  if( j + 1 == seg_refs->end() )
1289  wxLogTrace( "PNS", "%s\n", (*j)->GetSeg().B.Format().c_str() );
1290 
1291  all_segs.erase( *j );
1292  }
1293 
1294  lines_count++;
1295  }
1296 
1297  wxLogTrace( "PNS", "Local joints: %d, lines : %d \n", m_joints.size(), lines_count );
1298 #endif
1299 }
bool isRoot() const
Definition: pns_node.h:418
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:920
usual segment : line with rounded ends
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:440

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

◆ FindItemByParent()

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

Definition at line 1537 of file pns_node.cpp.

1538 {
1539  if( aParent->IsConnected() )
1540  {
1541  const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1542 
1544 
1545  if( l_cur )
1546  {
1547  for( ITEM* item : *l_cur )
1548  {
1549  if( item->Parent() == aParent )
1550  return item;
1551  }
1552  }
1553  }
1554 
1555  return NULL;
1556 }
std::list< ITEM * > NET_ITEMS_LIST
Definition: pns_index.h:48
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
#define NULL
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Returns list of all items in a given net.
Definition: pns_index.cpp:71
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:134

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

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

◆ FindJoint() [1/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 1104 of file pns_node.cpp.

1105 {
1106  JOINT::HASH_TAG tag;
1107 
1108  tag.net = aNet;
1109  tag.pos = aPos;
1110 
1111  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
1112 
1113  if( f == end && !isRoot() )
1114  {
1115  end = m_root->m_joints.end();
1116  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1117  }
1118 
1119  if( f == end )
1120  return NULL;
1121 
1122  while( f != end )
1123  {
1124  if( f->second.Layers().Overlaps( aLayer ) )
1125  return &f->second;
1126 
1127  ++f;
1128  }
1129 
1130  return NULL;
1131 }
bool isRoot() const
Definition: pns_node.h:418
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
#define NULL
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:440

References isRoot(), m_joints, m_root, PNS::JOINT::HASH_TAG::net, NULL, 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(), followLine(), PNS::TOPOLOGY::followTrivialPath(), PNS::getDanglingAnchor(), 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().

◆ FindJoint() [2/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 345 of file pns_node.h.

References FindJoint(), PNS::ITEM::Layers(), PNS::ITEM::Net(), and LAYER_RANGE::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 1013 of file pns_node.cpp.

1014 {
1015  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
1016  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
1017 }
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:1104

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

1021 {
1022  for( ITEM* item : aA.LinkList() )
1023  {
1024  if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
1025  {
1026  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1027  LINE line = AssembleLine( li );
1028 
1029  if( !line.Layers().Overlaps( aB.Layers() ) )
1030  continue;
1031 
1032  JOINT j_start, j_end;
1033 
1034  FindLineEnds( line, j_start, j_end );
1035 
1036  int id_start = line.CLine().Find( aA.Pos() );
1037  int id_end = line.CLine().Find( aB.Pos() );
1038 
1039  if( id_end < id_start )
1040  std::swap( id_end, id_start );
1041 
1042  if( id_start >= 0 && id_end >= 0 )
1043  {
1044  line.ClipVertexRange( id_start, id_end );
1045  aLines.push_back( line );
1046  }
1047  }
1048  }
1049 
1050  return 0;
1051 }
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1013
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:920

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

Definition at line 1464 of file pns_node.cpp.

1466 {
1467  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1468 
1469  if( !jtStart )
1470  return nullptr;
1471 
1472  for( ITEM* item : jtStart->LinkList() )
1473  {
1474  if( item->OfKind( ITEM::ARC_T ) )
1475  {
1476  ARC* seg2 = static_cast<ARC*>( item );
1477 
1478  const VECTOR2I a2( seg2->Anchor( 0 ) );
1479  const VECTOR2I b2( seg2->Anchor( 1 ) );
1480 
1481  if( seg2->Layers().Start() == lr.Start()
1482  && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1483  {
1484  return seg2;
1485  }
1486  }
1487  }
1488 
1489  return nullptr;
1490 }
int Start() const
Definition: pns_layerset.h:82
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:1104

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

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

Definition at line 1493 of file pns_node.cpp.

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

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

1431 {
1432  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1433 
1434  if( !jtStart )
1435  return nullptr;
1436 
1437  for( ITEM* item : jtStart->LinkList() )
1438  {
1439  if( item->OfKind( ITEM::SEGMENT_T ) )
1440  {
1441  SEGMENT* seg2 = (SEGMENT*)item;
1442 
1443  const VECTOR2I a2( seg2->Seg().A );
1444  const VECTOR2I b2( seg2->Seg().B );
1445 
1446  if( seg2->Layers().Start() == lr.Start()
1447  && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1448  {
1449  return seg2;
1450  }
1451  }
1452  }
1453 
1454  return nullptr;
1455 }
int Start() const
Definition: pns_layerset.h:82
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:1104
usual segment : line with rounded ends

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

1459 {
1460  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1461 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1429

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

◆ FixupVirtualVias()

void PNS::NODE::FixupVirtualVias ( )

Definition at line 1054 of file pns_node.cpp.

1055 {
1056  std::vector<VVIA*> vvias;
1057 
1058  for( auto& joint : m_joints )
1059  {
1060  if( joint.second.Layers().IsMultilayer() )
1061  continue;
1062 
1063  int n_seg = 0, n_solid = 0, n_vias = 0;
1064  int prev_w = -1;
1065  int max_w = -1;
1066  bool is_width_change = false;
1067 
1068  for( const auto& lnk : joint.second.LinkList() )
1069  {
1070  if( lnk.item->OfKind( ITEM::VIA_T ) )
1071  n_vias++;
1072  else if( lnk.item->OfKind( ITEM::SOLID_T ) )
1073  n_solid++;
1074  else if( const auto t = dyn_cast<PNS::SEGMENT*>( lnk.item ) )
1075  {
1076  int w = t->Width();
1077 
1078  if( prev_w >= 0 && w != prev_w )
1079  {
1080  is_width_change = true;
1081  }
1082 
1083  max_w = std::max( w, max_w );
1084  prev_w = w;
1085  }
1086  }
1087 
1088  if( ( is_width_change || n_seg >= 3 ) && n_solid == 0 && n_vias == 0 )
1089  {
1090  // fixme: the hull margin here is an ugly temporary workaround. The real fix
1091  // is to use octagons for via force propagation.
1092  vvias.push_back( new VVIA( joint.second.Pos(), joint.second.Layers().Start(),
1093  max_w + 2 * PNS_HULL_MARGIN, joint.second.Net() ) );
1094  }
1095  }
1096 
1097  for( auto vvia : vvias )
1098  {
1099  Add( ItemCast<VIA>( std::move( std::unique_ptr<VVIA>( vvia ) ) ) );
1100  }
1101 }
#define PNS_HULL_MARGIN
Definition: pns_line.h:44
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:440
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621

References Add(), m_joints, PNS_HULL_MARGIN, PNS::ITEM::SOLID_T, 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 
)
private

Definition at line 871 of file pns_node.cpp.

874 {
875  bool prevReversed = false;
876 
877  const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
878 
879  for( int count = 0 ; ; ++count )
880  {
881  const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
882  const JOINT* jt = FindJoint( p, aCurrent );
883 
884  assert( jt );
885 
886  aCorners[aPos] = jt->Pos();
887  aSegments[aPos] = aCurrent;
888  aArcReversed[aPos] = false;
889 
890  if( aCurrent->Kind() == ITEM::ARC_T )
891  {
892  if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) ) ||
893  ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
894  aArcReversed[aPos] = true;
895  }
896 
897  aPos += ( aScanDirection ? 1 : -1 );
898 
899  if( count && guard == p )
900  {
901  if( aPos >= 0 && aPos < aLimit )
902  aSegments[aPos] = NULL;
903 
904  aGuardHit = true;
905  break;
906  }
907 
908  bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
909 
910  if( locked || !jt->IsLineCorner() || aPos < 0 || aPos == aLimit )
911  break;
912 
913  aCurrent = jt->NextSegment( aCurrent );
914 
915  prevReversed = ( aCurrent && jt->Pos() == aCurrent->Anchor( aScanDirection ) );
916  }
917 }
#define NULL
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:1104

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

Referenced by AssembleLine().

◆ GetClearance()

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

Definition at line 100 of file pns_node.cpp.

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

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

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

◆ GetHoleClearance()

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

Definition at line 109 of file pns_node.cpp.

110  {
111  if( !m_ruleResolver )
112  return 0;
113 
114  return m_ruleResolver->HoleClearance( aA, aB );
115  }
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:451
virtual int HoleClearance(const ITEM *aA, const ITEM *aB)=0

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

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

◆ GetHoleToHoleClearance()

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

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

Definition at line 118 of file pns_node.cpp.

119 {
120  if( !m_ruleResolver )
121  return 0;
122 
123  return m_ruleResolver->HoleToHoleClearance( aA, aB );
124 }
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
Definition: pns_node.h:451
virtual int HoleToHoleClearance(const ITEM *aA, const ITEM *aB)=0

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

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

◆ GetMaxClearance()

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

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

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

References m_parent.

◆ GetRuleResolver()

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

Return the number of joints.

Definition at line 177 of file pns_node.h.

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 
)

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

1303 {
1304  if( isRoot() )
1305  return;
1306 
1307  if( m_override.size() )
1308  aRemoved.reserve( m_override.size() );
1309 
1310  if( m_index->Size() )
1311  aAdded.reserve( m_index->Size() );
1312 
1313  for( ITEM* item : m_override )
1314  aRemoved.push_back( item );
1315 
1316  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1317  aAdded.push_back( *i );
1318 }
bool isRoot() const
Definition: pns_node.h:418
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
Definition: pns_node.h:447
ITEM_SET::iterator end()
Definition: pns_index.h:118
ITEM_SET::iterator begin()
Definition: pns_index.h:117
int Size() const
Returns number of items stored in the index.
Definition: pns_index.h:115

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_TEST_ENVIRONMENT::ReplayLog(), PNS::LINE_PLACER::simplifyNewLine(), and PNS::ROUTER::updateView().

◆ HasChildren()

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

Definition at line 367 of file pns_node.h.

368  {
369  return !m_children.empty();
370  }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:445

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

501 {
502  ITEM_SET items;
503 
504  // fixme: we treat a point as an infinitely small circle - this is inefficient.
505  SHAPE_CIRCLE s( aPoint, 0 );
506  HIT_VISITOR visitor( items, aPoint );
507  visitor.SetWorld( this, NULL );
508 
509  m_index->Query( &s, m_maxClearance, visitor );
510 
511  if( !isRoot() ) // fixme: could be made cleaner
512  {
513  ITEM_SET items_root;
514  visitor.SetWorld( m_root, NULL );
515  HIT_VISITOR visitor_root( items_root, aPoint );
516  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
517 
518  for( ITEM* item : items_root.Items() )
519  {
520  if( !Overrides( item ) )
521  items.Add( item );
522  }
523  }
524 
525  return items;
526 }
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
bool Overrides(ITEM *aItem) const
Definition: pns_node.h:378
bool isRoot() const
Definition: pns_node.h:418
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
#define NULL
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:450

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

419  {
420  return m_parent == NULL;
421  }
#define NULL
NODE * m_parent
node this node was branched from
Definition: pns_node.h:443

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

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

Definition at line 183 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 1203 of file pns_node.cpp.

1204 {
1205  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1206 
1207  jt.Link( aWhere );
1208 }
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:1141

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

1135 {
1136  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1137  jt.Lock( aLock );
1138 }
void Lock(bool aLock=true)
Definition: pns_joint.h:244
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:1141

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 = NULL 
)

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
Returns
the obstacle, if found, otherwise empty.

Definition at line 281 of file pns_node.cpp.

283 {
284  OBSTACLES obstacleList;
285  obstacleList.reserve( 100 );
286 
287  for( int i = 0; i < aLine->CLine().SegmentCount(); i++ )
288  {
289  const SEGMENT s( *aLine, aLine->CLine().CSegment( i ) );
290  QueryColliding( &s, obstacleList, aKindMask );
291  }
292 
293  if( aLine->EndsWithVia() )
294  QueryColliding( &aLine->Via(), obstacleList, aKindMask );
295 
296  if( obstacleList.empty() )
297  return OPT_OBSTACLE();
298 
299  OBSTACLE nearest;
300  nearest.m_item = NULL;
301  nearest.m_distFirst = INT_MAX;
302 
303  auto updateNearest =
304  [&]( const SHAPE_LINE_CHAIN::INTERSECTION& pt, ITEM* obstacle, const SHAPE_LINE_CHAIN& hull, bool isHole )
305  {
306  int dist = aLine->CLine().PathLength( pt.p, pt.index_their );
307 
308  if( dist < nearest.m_distFirst )
309  {
310  nearest.m_distFirst = dist;
311  nearest.m_ipFirst = pt.p;
312  nearest.m_item = obstacle;
313  nearest.m_hull = hull;
314 
315  obstacle->Mark( isHole ? obstacle->Marker() | MK_HOLE
316  : obstacle->Marker() & ~MK_HOLE );
317  }
318  };
319 
320  SHAPE_LINE_CHAIN obstacleHull;
321  DEBUG_DECORATOR* debugDecorator = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
322  std::vector<SHAPE_LINE_CHAIN::INTERSECTION> intersectingPts;
323  int layer = aLine->Layer();
324 
325 
326  for( const OBSTACLE& obstacle : obstacleList )
327  {
328  if( aRestrictedSet && aRestrictedSet->find( obstacle.m_item ) == aRestrictedSet->end() )
329  continue;
330 
331  int clearance = GetClearance( obstacle.m_item, aLine ) + aLine->Width() / 2;
332  obstacleHull = obstacle.m_item->Hull( clearance + PNS_HULL_MARGIN, 0, layer );
333  //debugDecorator->AddLine( obstacleHull, 2, 40000, "obstacle-hull-test" );
334  //debugDecorator->AddLine( aLine->CLine(), 5, 40000, "obstacle-test-line" );
335 
336  intersectingPts.clear();
337  HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
338 
339  for( const auto& ip : intersectingPts )
340  {
341  //debugDecorator->AddPoint( ip.p, ip.valid?3:6, 100000, (const char *) wxString::Format("obstacle-isect-point-%d" ).c_str() );
342  if(ip.valid)
343  updateNearest( ip, obstacle.m_item, obstacleHull, false );
344  }
345 
346  if( aLine->EndsWithVia() )
347  {
348  const VIA& via = aLine->Via();
349  // Don't use via.Drill(); it doesn't include the plating thickness
350  int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
351 
352  int viaClearance = GetClearance( obstacle.m_item, &via ) + via.Diameter() / 2;
353  int holeClearance = GetHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
354 
355  if( holeClearance > viaClearance )
356  viaClearance = holeClearance;
357 
358  obstacleHull = obstacle.m_item->Hull( viaClearance + PNS_HULL_MARGIN, 0, layer );
359  //debugDecorator->AddLine( obstacleHull, 3 );
360 
361  intersectingPts.clear();
362  HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
363 
364 // obstacleHull.Intersect( aLine->CLine(), intersectingPts, true );
365 
366  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
367  updateNearest( ip, obstacle.m_item, obstacleHull, false );
368  }
369 
370  if( obstacle.m_item->Hole() )
371  {
372  clearance = GetHoleClearance( obstacle.m_item, aLine ) + aLine->Width() / 2;
373  obstacleHull = obstacle.m_item->HoleHull( clearance + PNS_HULL_MARGIN, 0, layer );
374  //debugDecorator->AddLine( obstacleHull, 4 );
375 
376  intersectingPts.clear();
377  HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
378 
379  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
380  updateNearest( ip, obstacle.m_item, obstacleHull, true );
381 
382  if( aLine->EndsWithVia() )
383  {
384  const VIA& via = aLine->Via();
385  // Don't use via.Drill(); it doesn't include the plating thickness
386  int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
387 
388  int viaClearance = GetClearance( obstacle.m_item, &via ) + via.Diameter() / 2;
389  int holeClearance = GetHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
390  int holeToHole = GetHoleToHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
391 
392  if( holeClearance > viaClearance )
393  viaClearance = holeClearance;
394 
395  if( holeToHole > viaClearance )
396  viaClearance = holeToHole;
397 
398  obstacleHull = obstacle.m_item->Hull( viaClearance + PNS_HULL_MARGIN, 0, layer );
399  //debugDecorator->AddLine( obstacleHull, 5 );
400 
401  intersectingPts.clear();
402  HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
403 
404  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
405  updateNearest( ip, obstacle.m_item, obstacleHull, true );
406  }
407  }
408  }
409 
410  if( nearest.m_distFirst == INT_MAX )
411  nearest.m_item = obstacleList[0].m_item;
412 
413  // debugDecorator->AddLine( nearest.m_hull, YELLOW, 60000, "obstacle-nearest-hull" );
414 
415  return nearest;
416 }
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
Definition: pns_utils.cpp:275
int GetHoleToHoleClearance(const ITEM *aA, const ITEM *aB) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:118
VECTOR2I p
point of intersection between our and their.
#define PNS_HULL_MARGIN
Definition: pns_line.h:44
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:109
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:100
Normal via.
Definition: router_tool.cpp:70
#define NULL
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true)
Find items colliding (closer than clearance) with the item aItem.
Definition: pns_node.cpp:255
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
int index_their
index of the intersecting corner/segment in the 'their' (Intersect() method parameter) line
SHAPE_LINE_CHAIN.
usual segment : line with rounded ends
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
std::vector< OBSTACLE > OBSTACLES
Definition: pns_node.h:149
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:210
static ROUTER * GetInstance()
Definition: pns_router.cpp:78

References PNS::LINE::CLine(), 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(), PNS::OBSTACLE::m_distFirst, PNS::OBSTACLE::m_hull, PNS::OBSTACLE::m_ipFirst, PNS::OBSTACLE::m_item, PNS::MK_HOLE, NULL, SHAPE_LINE_CHAIN::INTERSECTION::p, SHAPE_LINE_CHAIN::PathLength(), PNS_HULL_MARGIN, QueryColliding(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::Via(), 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 378 of file pns_node.h.

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

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 
)

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

Definition at line 255 of file pns_node.cpp.

257 {
258  DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly );
259 
260 #ifdef DEBUG
261  assert( allocNodes.find( this ) != allocNodes.end() );
262 #endif
263 
264  visitor.SetCountLimit( aLimitCount );
265  visitor.SetWorld( this, NULL );
266 
267  // first, look for colliding items in the local index
268  m_index->Query( aItem, m_maxClearance, visitor );
269 
270  // if we haven't found enough items, look in the root branch as well.
271  if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
272  {
273  visitor.SetWorld( m_root, this );
274  m_root->m_index->Query( aItem, m_maxClearance, visitor );
275  }
276 
277  return aObstacles.size();
278 }
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
bool isRoot() const
Definition: pns_node.h:418
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
#define NULL
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:450

References isRoot(), 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(), and NearestObstacle().

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

1501 {
1502  int n = 0;
1503 
1504  aJoints.clear();
1505 
1506  for( JOINT_MAP::value_type& j : m_joints )
1507  {
1508  if( !j.second.Layers().Overlaps( aLayerMask ) )
1509  continue;
1510 
1511  if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1512  {
1513  aJoints.push_back( &j.second );
1514  n++;
1515  }
1516  }
1517 
1518  if( isRoot() )
1519  return n;
1520 
1521  for( JOINT_MAP::value_type& j : m_root->m_joints )
1522  {
1523  if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1524  {
1525  if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1526  {
1527  aJoints.push_back( &j.second );
1528  n++;
1529  }
1530  }
1531  }
1532 
1533  return n;
1534 }
bool Overrides(ITEM *aItem) const
Definition: pns_node.h:378
bool isRoot() const
Definition: pns_node.h:418
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:141
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:440

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

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

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

Referenced by removeSolidIndex(), and removeViaIndex().

◆ releaseChildren()

void PNS::NODE::releaseChildren ( )
private

Definition at line 1321 of file pns_node.cpp.

1322 {
1323  // copy the kids as the NODE destructor erases the item from the parent node.
1324  std::set<NODE*> kids = m_children;
1325 
1326  for( NODE* node : kids )
1327  {
1328  node->releaseChildren();
1329  delete node;
1330  }
1331 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:445

References m_children.

Referenced by Commit(), and KillChildren().

◆ releaseGarbage()

void PNS::NODE::releaseGarbage ( )
private

Definition at line 1334 of file pns_node.cpp.

1335 {
1336  if( !isRoot() )
1337  return;
1338 
1339  for( ITEM* item : m_garbageItems )
1340  {
1341  if( !item->BelongsTo( this ) )
1342  delete item;
1343  }
1344 
1345  m_garbageItems.clear();
1346 }
bool isRoot() const
Definition: pns_node.h:418
std::unordered_set< ITEM * > m_garbageItems
Definition: pns_node.h:456

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

790 {
791  removeSolidIndex( aSolid );
792  doRemove( aSolid );
793 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:675
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:763

References doRemove(), and removeSolidIndex().

◆ Remove() [3/6]

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

Definition at line 796 of file pns_node.cpp.

797 {
798  removeViaIndex( aVia );
799  doRemove( aVia );
800 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:675
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:755

References doRemove(), and removeViaIndex().

◆ Remove() [4/6]

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

Definition at line 803 of file pns_node.cpp.

804 {
805  removeSegmentIndex( aSegment );
806  doRemove( aSegment );
807 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:675
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:696

References doRemove(), and removeSegmentIndex().

◆ Remove() [5/6]

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

Definition at line 817 of file pns_node.cpp.

818 {
819  switch( aItem->Kind() )
820  {
821  case ITEM::ARC_T:
822  Remove( static_cast<ARC*>( aItem ) );
823  break;
824 
825  case ITEM::SOLID_T:
826  Remove( static_cast<SOLID*>( aItem ) );
827  break;
828 
829  case ITEM::SEGMENT_T:
830  Remove( static_cast<SEGMENT*>( aItem ) );
831  break;
832 
833  case ITEM::LINE_T:
834  {
835  LINE* l = static_cast<LINE*>( aItem );
836 
837  for ( LINKED_ITEM* s : l->Links() )
838  Remove( s );
839 
840  break;
841  }
842 
843  case ITEM::VIA_T:
844  Remove( static_cast<VIA*>( aItem ) );
845  break;
846 
847  default:
848  break;
849  }
850 }
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:810

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() [6/6]

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

Removes a line from this branch.

Parameters
aLineitem to remove

Definition at line 853 of file pns_node.cpp.

854 {
855  // LINE does not have a separate remover, as LINEs are never truly a member of the tree
856  std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
857 
858  for( LINKED_ITEM* li : segRefs )
859  {
860  if( li->OfKind( ITEM::SEGMENT_T ) )
861  Remove( static_cast<SEGMENT*>( li ) );
862  else if( li->OfKind( ITEM::ARC_T ) )
863  Remove( static_cast<ARC*>( li ) );
864  }
865 
866  aLine.SetOwner( nullptr );
867  aLine.ClearLinks();
868 }
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:810

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

◆ removeArcIndex()

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

Definition at line 703 of file pns_node.cpp.

704 {
705  unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
706  unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
707 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1211

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

1415 {
1416  std::vector<ITEM*> garbage;
1417 
1418  for( ITEM* item : *m_index )
1419  {
1420  if( item->Marker() & aMarker )
1421  garbage.emplace_back( item );
1422  }
1423 
1424  for( ITEM* item : garbage )
1425  Remove( item );
1426 }
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:810

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

697 {
698  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
699  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
700 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1211

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

764 {
765  if( !aSolid->IsRoutable() )
766  return;
767 
768  // fixme: redundant code
769  JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
770  assert( jt );
771  rebuildJoint( jt, aSolid );
772 }
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:710
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:1104

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

756 {
757  JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
758  assert( jt );
759  rebuildJoint( jt, aVia );
760 }
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:710
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:1104

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

776 {
777  Remove( aOldItem );
778  Add( std::move( aNewItem ) );
779 }
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:810
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621

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

783 {
784  Remove( aOldLine );
785  Add( aNewLine );
786 }
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:810
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621

References Add(), and Remove().

◆ SetMaxClearance()

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

Assign a clearance resolution function object.

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

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

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

1142 {
1143  JOINT::HASH_TAG tag;
1144 
1145  tag.pos = aPos;
1146  tag.net = aNet;
1147 
1148  // try to find the joint in this node.
1149  JOINT_MAP::iterator f = m_joints.find( tag );
1150 
1151  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1152 
1153  // not found and we are not root? find in the root and copy results here.
1154  if( f == m_joints.end() && !isRoot() )
1155  {
1156  range = m_root->m_joints.equal_range( tag );
1157 
1158  for( f = range.first; f != range.second; ++f )
1159  m_joints.insert( *f );
1160  }
1161 
1162  // now insert and combine overlapping joints
1163  JOINT jt( aPos, aLayers, aNet );
1164 
1165  bool merged;
1166 
1167  do
1168  {
1169  merged = false;
1170  range = m_joints.equal_range( tag );
1171 
1172  if( range.first == m_joints.end() )
1173  break;
1174 
1175  for( f = range.first; f != range.second; ++f )
1176  {
1177  if( aLayers.Overlaps( f->second.Layers() ) )
1178  {
1179  jt.Merge( f->second );
1180  m_joints.erase( f );
1181  merged = true;
1182  break;
1183  }
1184  }
1185  }
1186  while( merged );
1187 
1188  return m_joints.insert( TagJointPair( tag, jt ) )->second;
1189 }
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
bool isRoot() const
Definition: pns_node.h:418
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
JOINT_MAP::value_type TagJointPair
Definition: pns_node.h:438
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:440

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

1212 {
1213  // fixme: remove dangling joints
1214  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1215 
1216  jt.Unlink( aWhere );
1217 }
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:1141

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

Referenced by removeArcIndex(), and removeSegmentIndex().

◆ unlinkParent()

void PNS::NODE::unlinkParent ( )
private

Definition at line 163 of file pns_node.cpp.

164 {
165  if( isRoot() )
166  return;
167 
168  m_parent->m_children.erase( this );
169 }
std::set< NODE * > m_children
list of nodes branched from this one
Definition: pns_node.h:445
bool isRoot() const
Definition: pns_node.h:418
NODE * m_parent
node this node was branched from
Definition: pns_node.h:443

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 445 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 453 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 456 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 440 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 450 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 447 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 443 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 444 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 451 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: