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=nullptr)
 Follow the line in search of an obstacle that is nearest to the starting to the line's starting point. More...
 
OPT_OBSTACLE CheckColliding (const ITEM *aItem, int aKindMask=ITEM::ANY_T)
 Check if the item collides with anything else in the world, and if found, returns the obstacle. More...
 
OPT_OBSTACLE CheckColliding (const ITEM_SET &aSet, int aKindMask=ITEM::ANY_T)
 Check if any item in the set collides with anything else in the world, and if found, returns the obstacle. More...
 
const ITEM_SET HitTest (const VECTOR2I &aPoint) const
 Find all items that contain the point aPoint. More...
 
bool Add (std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
 Add an item to the current node. More...
 
void Add (std::unique_ptr< SOLID > aSolid)
 
void Add (std::unique_ptr< VIA > aVia)
 
bool Add (std::unique_ptr< ARC > aArc, bool aAllowRedundant=false)
 
void Add (LINE &aLine, bool aAllowRedundant=false)
 
void Remove (ARC *aArc)
 Remove an item from this branch. More...
 
void Remove (SOLID *aSolid)
 
void Remove (VIA *aVia)
 
void Remove (SEGMENT *aSegment)
 
void Remove (ITEM *aItem)
 
void Remove (LINE &aLine)
 Removes a line from this branch. More...
 
void Replace (ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
 Replace an item with another one. More...
 
void Replace (LINE &aOldLine, LINE &aNewLine)
 
NODEBranch ()
 Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs to the root. More...
 
const LINE AssembleLine (LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
 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 = nullptr;
58  m_maxClearance = 800000; // fixme: depends on how thick traces are.
59  m_ruleResolver = nullptr;
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
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, and m_ruleResolver.

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:173
INDEX * m_index
Geometric/Net index of the items.
Definition: pns_node.h:452
void releaseGarbage()
Definition: pns_node.cpp:1370
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 638 of file pns_node.cpp.

639 {
640  if( aSegment->Seg().A == aSegment->Seg().B )
641  {
642  wxLogTrace( "PNS", "attempting to add a segment with same end coordinates, ignoring." );
643  return false;
644  }
645 
646  if( !aAllowRedundant && findRedundantSegment( aSegment.get() ) )
647  return false;
648 
649  aSegment->SetOwner( this );
650  addSegment( aSegment.release() );
651 
652  return true;
653 }
void addSegment(SEGMENT *aSeg)
Definition: pns_node.cpp:629
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1465

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

556 {
557  aSolid->SetOwner( this );
558  addSolid( aSolid.release() );
559 }
void addSolid(SOLID *aSeg)
Definition: pns_node.cpp:546

References addSolid().

◆ Add() [3/6]

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

Definition at line 570 of file pns_node.cpp.

571 {
572  aVia->SetOwner( this );
573  addVia( aVia.release() );
574 }
void addVia(VIA *aVia)
Definition: pns_node.cpp:562

References addVia().

◆ Add() [4/6]

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

Definition at line 665 of file pns_node.cpp.

666 {
667  const SHAPE_ARC& arc = aArc->CArc();
668 
669  if( !aAllowRedundant && findRedundantArc( arc.GetP0(), arc.GetP1(), aArc->Layers(),
670  aArc->Net() ) )
671  {
672  return false;
673  }
674 
675  aArc->SetOwner( this );
676  addArc( aArc.release() );
677  return true;
678 }
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1500
void addArc(ARC *aVia)
Definition: pns_node.cpp:656
const VECTOR2I & GetP1() const
Definition: shape_arc.h:112

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

◆ Add() [5/6]

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

Definition at line 577 of file pns_node.cpp.

578 {
579  assert( !aLine.IsLinked() );
580 
581  SHAPE_LINE_CHAIN& l = aLine.Line();
582 
583  for( size_t i = 0; i < l.ArcCount(); i++ )
584  {
585  auto s = l.Arc( i );
586  ARC* rarc;
587 
588  if( !aAllowRedundant && ( rarc = findRedundantArc( s.GetP0(), s.GetP1(), aLine.Layers(),
589  aLine.Net() ) ) )
590  {
591  aLine.Link( rarc );
592  }
593  else
594  {
595  auto newarc = std::make_unique< ARC >( aLine, s );
596  aLine.Link( newarc.get() );
597  Add( std::move( newarc ), true );
598  }
599  }
600 
601  for( int i = 0; i < l.SegmentCount(); i++ )
602  {
603  if( l.IsArcSegment( i ) )
604  continue;
605 
606  SEG s = l.CSegment( i );
607 
608  if( s.A != s.B )
609  {
610  SEGMENT* rseg;
611 
612  if( !aAllowRedundant && ( rseg = findRedundantSegment( s.A, s.B, aLine.Layers(),
613  aLine.Net() ) ) )
614  {
615  // another line could be referencing this segment too :(
616  aLine.Link( rseg );
617  }
618  else
619  {
620  std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
621  aLine.Link( newseg.get() );
622  Add( std::move( newseg ), true );
623  }
624  }
625  }
626 }
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:1465
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1500
Definition: seg.h:40
Represent a polyline (an zero-thickness chain of connected line segments).
VECTOR2I A
Definition: seg.h:48
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
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 681 of file pns_node.cpp.

682 {
683  switch( aItem->Kind() )
684  {
685  case ITEM::SOLID_T: Add( ItemCast<SOLID>( std::move( aItem ) ) ); break;
686  case ITEM::SEGMENT_T: Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant ); break;
687  case ITEM::VIA_T: Add( ItemCast<VIA>( std::move( aItem ) ) ); break;
688 
689  case ITEM::ARC_T:
690  //todo(snh): Add redundant search
691  Add( ItemCast<ARC>( std::move( aItem ) ) );
692  break;
693 
694  case ITEM::LINE_T:
695  default:
696  assert( false );
697  }
698 }
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638

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

657 {
658  linkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
659  linkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
660 
661  m_index->Add( aArc );
662 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1239
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 629 of file pns_node.cpp.

630 {
631  linkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
632  linkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
633 
634  m_index->Add( aSeg );
635 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1239
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 546 of file pns_node.cpp.

547 {
548  if( aSolid->IsRoutable() )
549  linkJoint( aSolid->Pos(), aSolid->Layers(), aSolid->Net(), aSolid );
550 
551  m_index->Add( aSolid );
552 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1239
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 562 of file pns_node.cpp.

563 {
564  linkJoint( aVia->Pos(), aVia->Layers(), aVia->Net(), aVia );
565 
566  m_index->Add( aVia );
567 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1239
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 1411 of file pns_node.cpp.

1412 {
1413  INDEX::NET_ITEMS_LIST* l_cur = m_index->GetItemsForNet( aNet );
1414 
1415  if( l_cur )
1416  {
1417  for( ITEM* item : *l_cur )
1418  {
1419  if( item->OfKind( aKindMask ) && item->IsRoutable() )
1420  aItems.insert( item );
1421  }
1422  }
1423 
1424  if( !isRoot() )
1425  {
1426  INDEX::NET_ITEMS_LIST* l_root = m_root->m_index->GetItemsForNet( aNet );
1427 
1428  if( l_root )
1429  {
1430  for( ITEM* item : *l_root )
1431  {
1432  if( !Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1433  aItems.insert( item );
1434  }
1435  }
1436  }
1437 }
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 = nullptr,
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 946 of file pns_node.cpp.

948 {
949  const int MaxVerts = 1024 * 16;
950 
951  std::array<VECTOR2I, MaxVerts + 1> corners;
952  std::array<LINKED_ITEM*, MaxVerts + 1> segs;
953  std::array<bool, MaxVerts + 1> arcReversed;
954 
955  LINE pl;
956  bool guardHit = false;
957 
958  int i_start = MaxVerts / 2;
959  int i_end = i_start + 1;
960 
961  pl.SetWidth( aSeg->Width() );
962  pl.SetLayers( aSeg->Layers() );
963  pl.SetNet( aSeg->Net() );
964  pl.SetOwner( this );
965 
966  followLine( aSeg, false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
967  guardHit, aStopAtLockedJoints );
968 
969  if( !guardHit )
970  {
971  followLine( aSeg, true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
972  guardHit, aStopAtLockedJoints );
973  }
974 
975  int n = 0;
976 
977  LINKED_ITEM* prev_seg = nullptr;
978  bool originSet = false;
979 
980  SHAPE_LINE_CHAIN& line = pl.Line();
981 
982  for( int i = i_start + 1; i < i_end; i++ )
983  {
984  const VECTOR2I& p = corners[i];
985  LINKED_ITEM* li = segs[i];
986 
987  if( !li || li->Kind() != ITEM::ARC_T )
988  line.Append( p );
989 
990  if( li && prev_seg != li )
991  {
992  if( li->Kind() == ITEM::ARC_T )
993  {
994  const ARC* arc = static_cast<const ARC*>( li );
995  const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->Shape() );
996 
997  int nSegs = line.PointCount();
998  VECTOR2I last = nSegs ? line.CPoint( -1 ) : VECTOR2I();
999  ssize_t lastShape = nSegs ? line.ArcIndex( static_cast<ssize_t>( nSegs ) - 1 ) : -1;
1000 
1001  line.Append( arcReversed[i] ? sa->Reversed() : *sa );
1002  }
1003 
1004  pl.Link( li );
1005 
1006  // latter condition to avoid loops
1007  if( li == aSeg && aOriginSegmentIndex && !originSet )
1008  {
1009  wxASSERT( n < line.SegmentCount() ||
1010  ( n == line.SegmentCount() && li->Kind() == ITEM::SEGMENT_T ) );
1011  *aOriginSegmentIndex = line.PointCount() - 1;
1012  originSet = true;
1013  }
1014  }
1015 
1016  prev_seg = li;
1017  }
1018 
1019  // Remove duplicate verts, but do NOT remove colinear segments here!
1020  pl.Line().Simplify( false );
1021 
1022  assert( pl.SegmentCount() != 0 );
1023 
1024  return pl;
1025 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Return the number of points (vertices) in this line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
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:897
SHAPE_ARC Reversed() const
Definition: shape_arc.cpp:624

References SHAPE_LINE_CHAIN::Append(), PNS::ITEM::ARC_T, SHAPE_LINE_CHAIN::ArcIndex(), SHAPE_LINE_CHAIN::CPoint(), followLine(), PNS::ITEM::Kind(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::LINK_HOLDER::Link(), PNS::ITEM::Net(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_ARC::Reversed(), PNS::ITEM::SEGMENT_T, 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 137 of file pns_node.cpp.

138 {
139  NODE* child = new NODE;
140 
141  m_children.insert( child );
142 
143  child->m_depth = m_depth + 1;
144  child->m_parent = this;
145  child->m_ruleResolver = m_ruleResolver;
146  child->m_root = isRoot() ? this : m_root;
148 
149  // Immediate offspring of the root branch needs not copy anything. For the rest, deep-copy
150  // joints, overridden item maps and pointers to stored items.
151  if( !isRoot() )
152  {
153  JOINT_MAP::iterator j;
154 
155  for( ITEM* item : *m_index )
156  child->m_index->Add( item );
157 
158  child->m_joints = m_joints;
159  child->m_override = m_override;
160  }
161 
162 #if 0
163  wxLogTrace( "PNS", "%d items, %d joints, %d overrides",
164  child->m_index->Size(),
165  (int) child->m_joints.size(),
166  (int) child->m_override.size() );
167 #endif
168 
169  return child;
170 }
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 450 of file pns_node.cpp.

451 {
452  OBSTACLES obs;
453 
454  obs.reserve( 100 );
455 
456  if( aItemA->Kind() == ITEM::LINE_T )
457  {
458  int n = 0;
459  const LINE* line = static_cast<const LINE*>( aItemA );
460  const SHAPE_LINE_CHAIN& l = line->CLine();
461 
462  for( int i = 0; i < l.SegmentCount(); i++ )
463  {
464  const SEGMENT s( *line, l.CSegment( i ) );
465  n += QueryColliding( &s, obs, aKindMask, 1 );
466 
467  if( n )
468  return OPT_OBSTACLE( obs[0] );
469  }
470 
471  if( line->EndsWithVia() )
472  {
473  n += QueryColliding( &line->Via(), obs, aKindMask, 1 );
474 
475  if( n )
476  return OPT_OBSTACLE( obs[0] );
477  }
478  }
479  else if( QueryColliding( aItemA, obs, aKindMask, 1 ) > 0 )
480  {
481  return OPT_OBSTACLE( obs[0] );
482  }
483 
484  return OPT_OBSTACLE();
485 }
int SegmentCount() const
Return the number of segments in this line chain.
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:266
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
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 436 of file pns_node.cpp.

437 {
438  for( const ITEM* item : aSet.CItems() )
439  {
440  OPT_OBSTACLE obs = CheckColliding( item, aKindMask );
441 
442  if( obs )
443  return obs;
444  }
445 
446  return OPT_OBSTACLE();
447 }
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:450
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 1440 of file pns_node.cpp.

1441 {
1442  for( ITEM* item : *m_index )
1443  {
1444  item->SetRank( -1 );
1445  item->Mark( item->Marker() & ~aMarkerMask );
1446  }
1447 }
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 1385 of file pns_node.cpp.

1386 {
1387  if( aNode->isRoot() )
1388  return;
1389 
1390  for( ITEM* item : aNode->m_override )
1391  Remove( item );
1392 
1393  for( ITEM* item : *aNode->m_index )
1394  {
1395  item->SetRank( -1 );
1396  item->Unmark();
1397  Add( std::unique_ptr<ITEM>( item ) );
1398  }
1399 
1400  releaseChildren();
1401  releaseGarbage();
1402 }
void releaseChildren()
Definition: pns_node.cpp:1357
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
void releaseGarbage()
Definition: pns_node.cpp:1370
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638

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

702 {
703  // case 1: removing an item that is stored in the root node from any branch:
704  // mark it as overridden, but do not remove
705  if( aItem->BelongsTo( m_root ) && !isRoot() )
706  m_override.insert( aItem );
707 
708  // case 2: the item belongs to this branch or a parent, non-root branch,
709  // or the root itself and we are the root: remove from the index
710  else if( !aItem->BelongsTo( m_root ) || isRoot() )
711  m_index->Remove( aItem );
712 
713  // the item belongs to this particular branch: un-reference it
714  if( aItem->BelongsTo( this ) )
715  {
716  aItem->SetOwner( nullptr );
717  m_root->m_garbageItems.insert( aItem );
718  }
719 }
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
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, PNS::INDEX::Remove(), and PNS::ITEM::SetOwner().

Referenced by Remove().

◆ Dump()

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

Definition at line 1256 of file pns_node.cpp.

1257 {
1258 #if 0
1259  std::unordered_set<SEGMENT*> all_segs;
1261 
1262  for( i = m_items.begin(); i != m_items.end(); i++ )
1263  {
1264  if( (*i)->GetKind() == ITEM::SEGMENT_T )
1265  all_segs.insert( static_cast<SEGMENT*>( *i ) );
1266  }
1267 
1268  if( !isRoot() )
1269  {
1270  for( i = m_root->m_items.begin(); i != m_root->m_items.end(); i++ )
1271  {
1272  if( (*i)->GetKind() == ITEM::SEGMENT_T && !overrides( *i ) )
1273  all_segs.insert( static_cast<SEGMENT*>(*i) );
1274  }
1275  }
1276 
1277  JOINT_MAP::iterator j;
1278 
1279  if( aLong )
1280  {
1281  for( j = m_joints.begin(); j != m_joints.end(); ++j )
1282  {
1283  wxLogTrace( "PNS", "joint : %s, links : %d\n",
1284  j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1285  JOINT::LINKED_ITEMS::const_iterator k;
1286 
1287  for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1288  {
1289  const ITEM* m_item = *k;
1290 
1291  switch( m_item->GetKind() )
1292  {
1293  case ITEM::SEGMENT_T:
1294  {
1295  const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1296  wxLogTrace( "PNS", " -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1297  seg->GetSeg().B.Format().c_str() );
1298  break;
1299  }
1300 
1301  default:
1302  break;
1303  }
1304  }
1305  }
1306  }
1307 
1308  int lines_count = 0;
1309 
1310  while( !all_segs.empty() )
1311  {
1312  SEGMENT* s = *all_segs.begin();
1313  LINE* l = AssembleLine( s );
1314 
1315  LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1316 
1317  if( aLong )
1318  wxLogTrace( "PNS", "Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1319 
1320  for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1321  {
1322  wxLogTrace( "PNS", "%s ", (*j)->GetSeg().A.Format().c_str() );
1323 
1324  if( j + 1 == seg_refs->end() )
1325  wxLogTrace( "PNS", "%s\n", (*j)->GetSeg().B.Format().c_str() );
1326 
1327  all_segs.erase( *j );
1328  }
1329 
1330  lines_count++;
1331  }
1332 
1333  wxLogTrace( "PNS", "Local joints: %d, lines : %d \n", m_joints.size(), lines_count );
1334 #endif
1335 }
bool isRoot() const
Definition: pns_node.h:418
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
JOINT_MAP m_joints
hash table with the joints, linking the items.
Definition: pns_node.h:440
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946

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

◆ FindItemByParent()

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

Definition at line 1573 of file pns_node.cpp.

1574 {
1575  if( aParent->IsConnected() )
1576  {
1577  const BOARD_CONNECTED_ITEM* cItem = static_cast<const BOARD_CONNECTED_ITEM*>( aParent );
1578 
1580 
1581  if( l_cur )
1582  {
1583  for( ITEM* item : *l_cur )
1584  {
1585  if( item->Parent() == aParent )
1586  return item;
1587  }
1588  }
1589  }
1590 
1591  return nullptr;
1592 }
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
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:103

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

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

1141 {
1142  JOINT::HASH_TAG tag;
1143 
1144  tag.net = aNet;
1145  tag.pos = aPos;
1146 
1147  JOINT_MAP::iterator f = m_joints.find( tag ), end = m_joints.end();
1148 
1149  if( f == end && !isRoot() )
1150  {
1151  end = m_root->m_joints.end();
1152  f = m_root->m_joints.find( tag ); // m_root->FindJoint(aPos, aLayer, aNet);
1153  }
1154 
1155  if( f == end )
1156  return nullptr;
1157 
1158  while( f != end )
1159  {
1160  if( f->second.Layers().Overlaps( aLayer ) )
1161  return &f->second;
1162 
1163  ++f;
1164  }
1165 
1166  return nullptr;
1167 }
bool isRoot() const
Definition: pns_node.h:418
NODE * m_root
root node of the whole hierarchy
Definition: pns_node.h:444
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, 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 1028 of file pns_node.cpp.

1029 {
1030  aA = *FindJoint( aLine.CPoint( 0 ), &aLine );
1031  aB = *FindJoint( aLine.CPoint( -1 ), &aLine );
1032 }
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:1140

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

1036 {
1037  for( ITEM* item : aA.LinkList() )
1038  {
1039  if( item->Kind() == ITEM::SEGMENT_T || item->Kind() == ITEM::ARC_T )
1040  {
1041  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1042  LINE line = AssembleLine( li );
1043 
1044  if( !line.Layers().Overlaps( aB.Layers() ) )
1045  continue;
1046 
1047  JOINT j_start, j_end;
1048 
1049  FindLineEnds( line, j_start, j_end );
1050 
1051  int id_start = line.CLine().Find( aA.Pos() );
1052  int id_end = line.CLine().Find( aB.Pos() );
1053 
1054  if( id_end < id_start )
1055  std::swap( id_end, id_start );
1056 
1057  if( id_start >= 0 && id_end >= 0 )
1058  {
1059  line.ClipVertexRange( id_start, id_end );
1060  aLines.push_back( line );
1061  }
1062  }
1063  }
1064 
1065  return 0;
1066 }
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1028
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946

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

1502 {
1503  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1504 
1505  if( !jtStart )
1506  return nullptr;
1507 
1508  for( ITEM* item : jtStart->LinkList() )
1509  {
1510  if( item->OfKind( ITEM::ARC_T ) )
1511  {
1512  ARC* seg2 = static_cast<ARC*>( item );
1513 
1514  const VECTOR2I a2( seg2->Anchor( 0 ) );
1515  const VECTOR2I b2( seg2->Anchor( 1 ) );
1516 
1517  if( seg2->Layers().Start() == lr.Start()
1518  && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1519  {
1520  return seg2;
1521  }
1522  }
1523  }
1524 
1525  return nullptr;
1526 }
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:1140

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

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

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

1467 {
1468  JOINT* jtStart = FindJoint( A, lr.Start(), aNet );
1469 
1470  if( !jtStart )
1471  return nullptr;
1472 
1473  for( ITEM* item : jtStart->LinkList() )
1474  {
1475  if( item->OfKind( ITEM::SEGMENT_T ) )
1476  {
1477  SEGMENT* seg2 = (SEGMENT*)item;
1478 
1479  const VECTOR2I a2( seg2->Seg().A );
1480  const VECTOR2I b2( seg2->Seg().B );
1481 
1482  if( seg2->Layers().Start() == lr.Start()
1483  && ( ( A == a2 && B == b2 ) || ( A == b2 && B == a2 ) ) )
1484  {
1485  return seg2;
1486  }
1487  }
1488  }
1489 
1490  return nullptr;
1491 }
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:1140

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

1495 {
1496  return findRedundantSegment( aSeg->Seg().A, aSeg->Seg().B, aSeg->Layers(), aSeg->Net() );
1497 }
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
Definition: pns_node.cpp:1465

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

◆ FixupVirtualVias()

void PNS::NODE::FixupVirtualVias ( )

Definition at line 1069 of file pns_node.cpp.

1070 {
1071  SEGMENT* locked_seg = nullptr;
1072  std::vector<VVIA*> vvias;
1073 
1074  for( auto& jointPair : m_joints )
1075  {
1076  JOINT joint = jointPair.second;
1077 
1078  if( joint.Layers().IsMultilayer() )
1079  continue;
1080 
1081  int n_seg = 0, n_solid = 0, n_vias = 0;
1082  int prev_w = -1;
1083  int max_w = -1;
1084  bool is_width_change = false;
1085  bool is_locked = false;
1086 
1087  for( const auto& lnk : joint.LinkList() )
1088  {
1089  if( lnk.item->OfKind( ITEM::VIA_T ) )
1090  {
1091  n_vias++;
1092  }
1093  else if( lnk.item->OfKind( ITEM::SOLID_T ) )
1094  {
1095  n_solid++;
1096  }
1097  else if( const auto t = dyn_cast<PNS::SEGMENT*>( lnk.item ) )
1098  {
1099  int w = t->Width();
1100 
1101  if( prev_w >= 0 && w != prev_w )
1102  {
1103  is_width_change = true;
1104  }
1105 
1106  max_w = std::max( w, max_w );
1107  prev_w = w;
1108 
1109  is_locked = t->IsLocked();
1110  locked_seg = t;
1111  }
1112  }
1113 
1114  if( ( is_width_change || n_seg >= 3 || is_locked ) && n_solid == 0 && n_vias == 0 )
1115  {
1116  // fixme: the hull margin here is an ugly temporary workaround. The real fix
1117  // is to use octagons for via force propagation.
1118  vvias.push_back( new VVIA( joint.Pos(), joint.Layers().Start(),
1119  max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1120  }
1121 
1122  if( is_locked )
1123  {
1124  const VECTOR2I& secondPos = ( locked_seg->Seg().A == joint.Pos() ) ?
1125  locked_seg->Seg().B :
1126  locked_seg->Seg().A;
1127 
1128  vvias.push_back( new VVIA( secondPos, joint.Layers().Start(),
1129  max_w + 2 * PNS_HULL_MARGIN, joint.Net() ) );
1130  }
1131  }
1132 
1133  for( auto vvia : vvias )
1134  {
1135  Add( ItemCast<VIA>( std::move( std::unique_ptr<VVIA>( vvia ) ) ) );
1136  }
1137 }
#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:638

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

◆ followLine()

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

Definition at line 897 of file pns_node.cpp.

900 {
901  bool prevReversed = false;
902 
903  const VECTOR2I guard = aCurrent->Anchor( aScanDirection );
904 
905  for( int count = 0 ; ; ++count )
906  {
907  const VECTOR2I p = aCurrent->Anchor( aScanDirection ^ prevReversed );
908  const JOINT* jt = FindJoint( p, aCurrent );
909 
910  assert( jt );
911 
912  aCorners[aPos] = jt->Pos();
913  aSegments[aPos] = aCurrent;
914  aArcReversed[aPos] = false;
915 
916  if( aCurrent->Kind() == ITEM::ARC_T )
917  {
918  if( ( aScanDirection && jt->Pos() == aCurrent->Anchor( 0 ) ) ||
919  ( !aScanDirection && jt->Pos() == aCurrent->Anchor( 1 ) ) )
920  aArcReversed[aPos] = true;
921  }
922 
923  aPos += ( aScanDirection ? 1 : -1 );
924 
925  if( count && guard == p )
926  {
927  if( aPos >= 0 && aPos < aLimit )
928  aSegments[aPos] = nullptr;
929 
930  aGuardHit = true;
931  break;
932  }
933 
934  bool locked = aStopAtLockedJoints ? jt->IsLocked() : false;
935 
936  if( locked || !jt->IsLineCorner() || aPos < 0 || aPos == aLimit )
937  break;
938 
939  aCurrent = jt->NextSegment( aCurrent );
940 
941  prevReversed = ( aCurrent && jt->Pos() == aCurrent->Anchor( aScanDirection ) );
942  }
943 }
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:1140

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

Referenced by AssembleLine().

◆ GetClearance()

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

Definition at line 101 of file pns_node.cpp.

102 {
103  if( !m_ruleResolver )
104  return 100000;
105 
106  if( aA->IsVirtual() || aB->IsVirtual() )
107  return 0;
108 
109  return m_ruleResolver->Clearance( aA, aB );
110 }
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(), PNS::ITEM::IsVirtual(), 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 113 of file pns_node.cpp.

114 {
115  if( !m_ruleResolver )
116  return 0;
117 
118  if( aA->IsVirtual() || aB->IsVirtual() )
119  return 0;
120 
121  return m_ruleResolver->HoleClearance( aA, aB );
122 }
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(), PNS::ITEM::IsVirtual(), 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 125 of file pns_node.cpp.

126 {
127  if( !m_ruleResolver )
128  return 0;
129 
130  if( aA->IsVirtual() || aB->IsVirtual() )
131  return 0;
132 
133  return m_ruleResolver->HoleToHoleClearance( aA, aB );
134 }
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(), PNS::ITEM::IsVirtual(), 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 1338 of file pns_node.cpp.

1339 {
1340  if( isRoot() )
1341  return;
1342 
1343  if( m_override.size() )
1344  aRemoved.reserve( m_override.size() );
1345 
1346  if( m_index->Size() )
1347  aAdded.reserve( m_index->Size() );
1348 
1349  for( ITEM* item : m_override )
1350  aRemoved.push_back( item );
1351 
1352  for( INDEX::ITEM_SET::iterator i = m_index->begin(); i != m_index->end(); ++i )
1353  aAdded.push_back( *i );
1354 }
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 517 of file pns_node.cpp.

518 {
519  ITEM_SET items;
520 
521  // fixme: we treat a point as an infinitely small circle - this is inefficient.
522  SHAPE_CIRCLE s( aPoint, 0 );
523  HIT_VISITOR visitor( items, aPoint );
524  visitor.SetWorld( this, nullptr );
525 
526  m_index->Query( &s, m_maxClearance, visitor );
527 
528  if( !isRoot() ) // fixme: could be made cleaner
529  {
530  ITEM_SET items_root;
531  visitor.SetWorld( m_root, nullptr );
532  HIT_VISITOR visitor_root( items_root, aPoint );
533  m_root->m_index->Query( &s, m_maxClearance, visitor_root );
534 
535  for( ITEM* item : items_root.Items() )
536  {
537  if( !Overrides( item ) )
538  items.Add( item );
539  }
540  }
541 
542  return items;
543 }
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
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, 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 == nullptr;
421  }
NODE * m_parent
node this node was branched from
Definition: pns_node.h:443

References m_parent.

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

◆ JointCount()

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

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

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

1240 {
1241  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1242 
1243  jt.Link( aWhere );
1244 }
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:1177

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

1171 {
1172  JOINT& jt = touchJoint( aPos, aItem->Layers(), aItem->Net() );
1173  jt.Lock( aLock );
1174 }
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:1177

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

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

◆ NearestObstacle()

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

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

298 {
299  OBSTACLES obstacleList;
300  obstacleList.reserve( 100 );
301 
302  for( int i = 0; i < aLine->CLine().SegmentCount(); i++ )
303  {
304  const SEGMENT s( *aLine, aLine->CLine().CSegment( i ) );
305  QueryColliding( &s, obstacleList, aKindMask );
306  }
307 
308  if( aLine->EndsWithVia() )
309  QueryColliding( &aLine->Via(), obstacleList, aKindMask );
310 
311  if( obstacleList.empty() )
312  return OPT_OBSTACLE();
313 
314  OBSTACLE nearest;
315  nearest.m_item = nullptr;
316  nearest.m_distFirst = INT_MAX;
317 
318  auto updateNearest =
319  [&]( const SHAPE_LINE_CHAIN::INTERSECTION& pt, ITEM* obstacle,
320  const SHAPE_LINE_CHAIN& hull, bool isHole )
321  {
322  int dist = aLine->CLine().PathLength( pt.p, pt.index_their );
323 
324  if( dist < nearest.m_distFirst )
325  {
326  nearest.m_distFirst = dist;
327  nearest.m_ipFirst = pt.p;
328  nearest.m_item = obstacle;
329  nearest.m_hull = hull;
330 
331  obstacle->Mark( isHole ? obstacle->Marker() | MK_HOLE
332  : obstacle->Marker() & ~MK_HOLE );
333  }
334  };
335 
336  SHAPE_LINE_CHAIN obstacleHull;
337  DEBUG_DECORATOR* debugDecorator = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
338  std::vector<SHAPE_LINE_CHAIN::INTERSECTION> intersectingPts;
339  int layer = aLine->Layer();
340 
341 
342  for( const OBSTACLE& obstacle : obstacleList )
343  {
344  if( aRestrictedSet && aRestrictedSet->find( obstacle.m_item ) == aRestrictedSet->end() )
345  continue;
346 
347  int clearance = GetClearance( obstacle.m_item, aLine ) + aLine->Width() / 2;
348  obstacleHull = obstacle.m_item->Hull( clearance + PNS_HULL_MARGIN, 0, layer );
349  //debugDecorator->AddLine( obstacleHull, 2, 40000, "obstacle-hull-test" );
350  //debugDecorator->AddLine( aLine->CLine(), 5, 40000, "obstacle-test-line" );
351 
352  intersectingPts.clear();
353  HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
354 
355  for( const auto& ip : intersectingPts )
356  {
357  //debugDecorator->AddPoint( ip.p, ip.valid?3:6, 100000, (const char *) wxString::Format("obstacle-isect-point-%d" ).c_str() );
358  if(ip.valid)
359  updateNearest( ip, obstacle.m_item, obstacleHull, false );
360  }
361 
362  if( aLine->EndsWithVia() )
363  {
364  const VIA& via = aLine->Via();
365  // Don't use via.Drill(); it doesn't include the plating thickness
366 
367  int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
368 
369  int viaClearance = GetClearance( obstacle.m_item, &via ) + via.Diameter() / 2;
370  int holeClearance = GetHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
371 
372  if( holeClearance > viaClearance )
373  viaClearance = holeClearance;
374 
375  obstacleHull = obstacle.m_item->Hull( viaClearance + PNS_HULL_MARGIN, 0, layer );
376  //debugDecorator->AddLine( obstacleHull, 3 );
377 
378  intersectingPts.clear();
379  HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
380 
381  // obstacleHull.Intersect( aLine->CLine(), intersectingPts, true );
382 
383  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
384  updateNearest( ip, obstacle.m_item, obstacleHull, false );
385  }
386 
387  if( obstacle.m_item->Hole() )
388  {
389  clearance = GetHoleClearance( obstacle.m_item, aLine ) + aLine->Width() / 2;
390  obstacleHull = obstacle.m_item->HoleHull( clearance + PNS_HULL_MARGIN, 0, layer );
391  //debugDecorator->AddLine( obstacleHull, 4 );
392 
393  intersectingPts.clear();
394  HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
395 
396  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
397  updateNearest( ip, obstacle.m_item, obstacleHull, true );
398 
399  if( aLine->EndsWithVia() )
400  {
401  const VIA& via = aLine->Via();
402  // Don't use via.Drill(); it doesn't include the plating thickness
403  int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.Hole() )->GetRadius();
404 
405  int viaClearance = GetClearance( obstacle.m_item, &via ) + via.Diameter() / 2;
406  int holeClearance = GetHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
407  int holeToHole = GetHoleToHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
408 
409  if( holeClearance > viaClearance )
410  viaClearance = holeClearance;
411 
412  if( holeToHole > viaClearance )
413  viaClearance = holeToHole;
414 
415  obstacleHull = obstacle.m_item->Hull( viaClearance + PNS_HULL_MARGIN, 0, layer );
416  //debugDecorator->AddLine( obstacleHull, 5 );
417 
418  intersectingPts.clear();
419  HullIntersection( obstacleHull, aLine->CLine(), intersectingPts );
420 
421  for( const SHAPE_LINE_CHAIN::INTERSECTION& ip : intersectingPts )
422  updateNearest( ip, obstacle.m_item, obstacleHull, true );
423  }
424  }
425  }
426 
427  if( nearest.m_distFirst == INT_MAX )
428  nearest.m_item = obstacleList[0].m_item;
429 
430  // debugDecorator->AddLine( nearest.m_hull, YELLOW, 60000, "obstacle-nearest-hull" );
431 
432  return nearest;
433 }
Represent an intersection between two line segments.
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:125
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:113
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:101
Normal via.
Definition: router_tool.cpp:72
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:266
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
int index_their
When true, the corner [index_our] of the 'our' line lies exactly on 'their' line.
Represent a polyline (an zero-thickness chain of connected line segments).
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:207
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, 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

By default, virtual items cannot collide

Definition at line 266 of file pns_node.cpp.

268 {
270  if( aItem->IsVirtual() )
271  return 0;
272 
273  DEFAULT_OBSTACLE_VISITOR visitor( aObstacles, aItem, aKindMask, aDifferentNetsOnly );
274 
275 #ifdef DEBUG
276  assert( allocNodes.find( this ) != allocNodes.end() );
277 #endif
278 
279  visitor.SetCountLimit( aLimitCount );
280  visitor.SetWorld( this, nullptr );
281 
282  // first, look for colliding items in the local index
283  m_index->Query( aItem, m_maxClearance, visitor );
284 
285  // if we haven't found enough items, look in the root branch as well.
286  if( !isRoot() && ( visitor.m_matchCount < aLimitCount || aLimitCount < 0 ) )
287  {
288  visitor.SetWorld( m_root, this );
289  m_root->m_index->Query( aItem, m_maxClearance, visitor );
290  }
291 
292  return aObstacles.size();
293 }
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
int m_maxClearance
worst case item-item clearance
Definition: pns_node.h:450

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

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

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

1537 {
1538  int n = 0;
1539 
1540  aJoints.clear();
1541 
1542  for( JOINT_MAP::value_type& j : m_joints )
1543  {
1544  if( !j.second.Layers().Overlaps( aLayerMask ) )
1545  continue;
1546 
1547  if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1548  {
1549  aJoints.push_back( &j.second );
1550  n++;
1551  }
1552  }
1553 
1554  if( isRoot() )
1555  return n;
1556 
1557  for( JOINT_MAP::value_type& j : m_root->m_joints )
1558  {
1559  if( !Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1560  {
1561  if( aBox.Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1562  {
1563  aJoints.push_back( &j.second );
1564  n++;
1565  }
1566  }
1567  }
1568 
1569  return n;
1570 }
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
Definition: box2.h:134
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 736 of file pns_node.cpp.

737 {
738  // We have to split a single joint (associated with a via or a pad, binding together multiple
739  // layers) into multiple independent joints. As I'm a lazy bastard, I simply delete the
740  // via/solid and all its links and re-insert them.
741 
742  JOINT::LINKED_ITEMS links( aJoint->LinkList() );
743  JOINT::HASH_TAG tag;
744  int net = aItem->Net();
745 
746  tag.net = net;
747  tag.pos = aJoint->Pos();
748 
749  bool split;
750 
751  do
752  {
753  split = false;
754  auto range = m_joints.equal_range( tag );
755 
756  if( range.first == m_joints.end() )
757  break;
758 
759  // find and remove all joints containing the via to be removed
760 
761  for( auto f = range.first; f != range.second; ++f )
762  {
763  if( aItem->LayersOverlap( &f->second ) )
764  {
765  m_joints.erase( f );
766  split = true;
767  break;
768  }
769  }
770  } while( split );
771 
772  // and re-link them, using the former via's link list
773  for( ITEM* link : links )
774  {
775  if( link != aItem )
776  linkJoint( tag.pos, link->Layers(), net, link );
777  }
778 }
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
Definition: pns_node.cpp:1239
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: string_utils.h:293

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

1358 {
1359  // copy the kids as the NODE destructor erases the item from the parent node.
1360  std::set<NODE*> kids = m_children;
1361 
1362  for( NODE* node : kids )
1363  {
1364  node->releaseChildren();
1365  delete node;
1366  }
1367 }
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 1370 of file pns_node.cpp.

1371 {
1372  if( !isRoot() )
1373  return;
1374 
1375  for( ITEM* item : m_garbageItems )
1376  {
1377  if( !item->BelongsTo( this ) )
1378  delete item;
1379  }
1380 
1381  m_garbageItems.clear();
1382 }
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 815 of file pns_node.cpp.

816 {
817  removeSolidIndex( aSolid );
818  doRemove( aSolid );
819 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:701
void removeSolidIndex(SOLID *aSeg)
Definition: pns_node.cpp:789

References doRemove(), and removeSolidIndex().

◆ Remove() [3/6]

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

Definition at line 822 of file pns_node.cpp.

823 {
824  removeViaIndex( aVia );
825  doRemove( aVia );
826 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:701
void removeViaIndex(VIA *aVia)
Definition: pns_node.cpp:781

References doRemove(), and removeViaIndex().

◆ Remove() [4/6]

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

Definition at line 829 of file pns_node.cpp.

830 {
831  removeSegmentIndex( aSegment );
832  doRemove( aSegment );
833 }
void doRemove(ITEM *aItem)
Definition: pns_node.cpp:701
void removeSegmentIndex(SEGMENT *aSeg)
Definition: pns_node.cpp:722

References doRemove(), and removeSegmentIndex().

◆ Remove() [5/6]

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

Definition at line 843 of file pns_node.cpp.

844 {
845  switch( aItem->Kind() )
846  {
847  case ITEM::ARC_T:
848  Remove( static_cast<ARC*>( aItem ) );
849  break;
850 
851  case ITEM::SOLID_T:
852  Remove( static_cast<SOLID*>( aItem ) );
853  break;
854 
855  case ITEM::SEGMENT_T:
856  Remove( static_cast<SEGMENT*>( aItem ) );
857  break;
858 
859  case ITEM::LINE_T:
860  {
861  LINE* l = static_cast<LINE*>( aItem );
862 
863  for ( LINKED_ITEM* s : l->Links() )
864  Remove( s );
865 
866  break;
867  }
868 
869  case ITEM::VIA_T:
870  Remove( static_cast<VIA*>( aItem ) );
871  break;
872 
873  default:
874  break;
875  }
876 }
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836

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

880 {
881  // LINE does not have a separate remover, as LINEs are never truly a member of the tree
882  std::vector<LINKED_ITEM*>& segRefs = aLine.Links();
883 
884  for( LINKED_ITEM* li : segRefs )
885  {
886  if( li->OfKind( ITEM::SEGMENT_T ) )
887  Remove( static_cast<SEGMENT*>( li ) );
888  else if( li->OfKind( ITEM::ARC_T ) )
889  Remove( static_cast<ARC*>( li ) );
890  }
891 
892  aLine.SetOwner( nullptr );
893  aLine.ClearLinks();
894 }
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836

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

730 {
731  unlinkJoint( aArc->Anchor( 0 ), aArc->Layers(), aArc->Net(), aArc );
732  unlinkJoint( aArc->Anchor( 1 ), aArc->Layers(), aArc->Net(), aArc );
733 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1247

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

1451 {
1452  std::vector<ITEM*> garbage;
1453 
1454  for( ITEM* item : *m_index )
1455  {
1456  if( item->Marker() & aMarker )
1457  garbage.emplace_back( item );
1458  }
1459 
1460  for( ITEM* item : garbage )
1461  Remove( item );
1462 }
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:836

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

723 {
724  unlinkJoint( aSeg->Seg().A, aSeg->Layers(), aSeg->Net(), aSeg );
725  unlinkJoint( aSeg->Seg().B, aSeg->Layers(), aSeg->Net(), aSeg );
726 }
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
Definition: pns_node.cpp:1247

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

790 {
791  if( !aSolid->IsRoutable() )
792  return;
793 
794  // fixme: redundant code
795  JOINT* jt = FindJoint( aSolid->Pos(), aSolid->Layers().Start(), aSolid->Net() );
796  assert( jt );
797  rebuildJoint( jt, aSolid );
798 }
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:736
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:1140

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

782 {
783  JOINT* jt = FindJoint( aVia->Pos(), aVia->Layers().Start(), aVia->Net() );
784  assert( jt );
785  rebuildJoint( jt, aVia );
786 }
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
Definition: pns_node.cpp:736
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:1140

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

802 {
803  Remove( aOldItem );
804  Add( std::move( aNewItem ) );
805 }
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638

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

809 {
810  Remove( aOldLine );
811  Add( aNewLine );
812 }
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638

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

1178 {
1179  JOINT::HASH_TAG tag;
1180 
1181  tag.pos = aPos;
1182  tag.net = aNet;
1183 
1184  // try to find the joint in this node.
1185  JOINT_MAP::iterator f = m_joints.find( tag );
1186 
1187  std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1188 
1189  // not found and we are not root? find in the root and copy results here.
1190  if( f == m_joints.end() && !isRoot() )
1191  {
1192  range = m_root->m_joints.equal_range( tag );
1193 
1194  for( f = range.first; f != range.second; ++f )
1195  m_joints.insert( *f );
1196  }
1197 
1198  // now insert and combine overlapping joints
1199  JOINT jt( aPos, aLayers, aNet );
1200 
1201  bool merged;
1202 
1203  do
1204  {
1205  merged = false;
1206  range = m_joints.equal_range( tag );
1207 
1208  if( range.first == m_joints.end() )
1209  break;
1210 
1211  for( f = range.first; f != range.second; ++f )
1212  {
1213  if( aLayers.Overlaps( f->second.Layers() ) )
1214  {
1215  jt.Merge( f->second );
1216  m_joints.erase( f );
1217  merged = true;
1218  break;
1219  }
1220  }
1221  }
1222  while( merged );
1223 
1224  return m_joints.insert( TagJointPair( tag, jt ) )->second;
1225 }
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 1247 of file pns_node.cpp.

1248 {
1249  // fixme: remove dangling joints
1250  JOINT& jt = touchJoint( aPos, aLayers, aNet );
1251 
1252  jt.Unlink( aWhere );
1253 }
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:1177

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

Referenced by removeArcIndex(), and removeSegmentIndex().

◆ unlinkParent()

void PNS::NODE::unlinkParent ( )
private

Definition at line 173 of file pns_node.cpp.

174 {
175  if( isRoot() )
176  return;
177 
178  m_parent->m_children.erase( this );
179 }
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: