47 static std::unordered_set<NODE*> allocNodes;
60 allocNodes.insert(
this );
69 wxLogTrace(
"PNS",
"attempting to free a node that has kids." );
74 if( allocNodes.find(
this ) == allocNodes.end() )
76 wxLogTrace(
"PNS",
"attempting to free an already-free'd node." );
80 allocNodes.erase(
this );
87 if( item->BelongsTo(
this ) )
140 JOINT_MAP::iterator j;
150 wxLogTrace(
"PNS",
"%d items, %d joints, %d overrides",
173 m_extraClearance( 0 )
208 bool aDifferentNetsOnly ) :
237 if(
visit( aCandidate ) )
247 m_tab.push_back( obs );
260 int aLimitCount,
bool aDifferentNetsOnly )
265 assert( allocNodes.find(
this ) != allocNodes.end() );
281 return aObstacles.size();
286 const std::set<ITEM*>* aRestrictedSet )
289 obstacleList.reserve( 100 );
300 if( obstacleList.empty() )
316 nearest.
m_item = obstacle;
319 obstacle->Mark( isHole ? obstacle->Marker() |
MK_HOLE 320 : obstacle->Marker() & ~
MK_HOLE );
326 std::vector<SHAPE_LINE_CHAIN::INTERSECTION> intersectingPts;
327 int layer = aLine->
Layer();
329 for(
const OBSTACLE& obstacle : obstacleList )
331 if( aRestrictedSet && aRestrictedSet->find( obstacle.m_item ) == aRestrictedSet->end() )
335 obstacleHull = obstacle.m_item->Hull( clearance +
PNS_HULL_MARGIN, 0, layer );
336 debugDecorator->
AddLine( obstacleHull, 2 );
338 intersectingPts.clear();
342 updateNearest( ip.p, obstacle.m_item, obstacleHull,
false );
346 const VIA& via = aLine->
Via();
348 int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.
Hole() )->GetRadius();
351 int holeClearance =
GetHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
353 if( holeClearance > viaClearance )
354 viaClearance = holeClearance;
356 obstacleHull = obstacle.m_item->Hull( viaClearance +
PNS_HULL_MARGIN, 0, layer );
357 debugDecorator->
AddLine( obstacleHull, 3 );
359 intersectingPts.clear();
363 updateNearest( ip.p, obstacle.m_item, obstacleHull,
false );
366 if( obstacle.m_item->Hole() )
369 obstacleHull = obstacle.m_item->HoleHull( clearance +
PNS_HULL_MARGIN, 0, layer );
370 debugDecorator->
AddLine( obstacleHull, 4 );
372 intersectingPts.clear();
376 updateNearest( ip.p, obstacle.m_item, obstacleHull,
true );
380 const VIA& via = aLine->
Via();
382 int viaHoleRadius = static_cast<const SHAPE_CIRCLE*>( via.
Hole() )->GetRadius();
385 int holeClearance =
GetHoleClearance( obstacle.m_item, &via ) + viaHoleRadius;
388 if( holeClearance > viaClearance )
389 viaClearance = holeClearance;
391 if( holeToHole > viaClearance )
392 viaClearance = holeToHole;
394 obstacleHull = obstacle.m_item->Hull( viaClearance +
PNS_HULL_MARGIN, 0, layer );
395 debugDecorator->
AddLine( obstacleHull, 5 );
397 intersectingPts.clear();
401 updateNearest( ip.p, obstacle.m_item, obstacleHull,
true );
407 nearest.
m_item = obstacleList[0].m_item;
436 const LINE* line = static_cast<const LINE*>( aItemA );
534 aSolid->SetOwner(
this );
549 aVia->SetOwner(
this );
560 for(
size_t i = 0; i < l.ArcCount(); i++ )
572 auto newarc = std::make_unique< ARC >( aLine, s );
573 aLine.
Link( newarc.get() );
574 Add( std::move( newarc ),
true );
578 for(
int i = 0; i < l.SegmentCount(); i++ )
583 SEG s = l.CSegment( i );
597 std::unique_ptr<SEGMENT> newseg = std::make_unique<SEGMENT>( aLine, s );
598 aLine.
Link( newseg.get() );
599 Add( std::move( newseg ),
true );
615 bool NODE::Add( std::unique_ptr< SEGMENT > aSegment,
bool aAllowRedundant )
617 if( aSegment->Seg().A == aSegment->Seg().B )
619 wxLogTrace(
"PNS",
"attempting to add a segment with same end coordinates, ignoring." );
626 aSegment->SetOwner(
this );
644 aArc->SetOwner(
this );
649 void NODE::Add( std::unique_ptr< ITEM > aItem,
bool aAllowRedundant )
651 switch( aItem->Kind() )
654 case ITEM::SEGMENT_T:
Add( ItemCast<SEGMENT>( std::move( aItem ) ), aAllowRedundant );
break;
655 case ITEM::VIA_T:
Add( ItemCast<VIA>( std::move( aItem ) ) );
break;
659 Add( ItemCast<ARC>( std::move( aItem ) ) );
712 int net = aItem->
Net();
715 tag.pos = aJoint->
Pos();
722 auto range =
m_joints.equal_range( tag );
729 for(
auto f = range.first; f != range.second; ++f )
741 for(
ITEM* link : links )
744 linkJoint( tag.pos, link->Layers(), net, link );
772 Add( std::move( aNewItem ) );
813 switch( aItem->
Kind() )
816 Remove( static_cast<ARC*>( aItem ) );
820 Remove( static_cast<SOLID*>( aItem ) );
824 Remove( static_cast<SEGMENT*>( aItem ) );
829 LINE* l = static_cast<LINE*>( aItem );
838 Remove( static_cast<VIA*>( aItem ) );
850 std::vector<LINKED_ITEM*>& segRefs = aLine.
Links();
855 Remove( static_cast<SEGMENT*>( li ) );
857 Remove( static_cast<ARC*>( li ) );
867 bool& aGuardHit,
bool aStopAtLockedJoints )
869 bool prevReversed =
false;
873 for(
int count = 0 ; ; ++count )
875 const VECTOR2I p = aCurrent->
Anchor( aScanDirection ^ prevReversed );
880 aCorners[aPos] = jt->
Pos();
881 aSegments[aPos] = aCurrent;
882 aArcReversed[aPos] =
false;
886 if( ( aScanDirection && jt->
Pos() == aCurrent->
Anchor( 0 ) ) ||
887 ( !aScanDirection && jt->
Pos() == aCurrent->
Anchor( 1 ) ) )
888 aArcReversed[aPos] =
true;
891 aPos += ( aScanDirection ? 1 : -1 );
893 if( count && guard == p )
895 aSegments[aPos] =
NULL;
900 bool locked = aStopAtLockedJoints ? jt->
IsLocked() :
false;
902 if( locked || !jt->
IsLineCorner() || aPos < 0 || aPos == aLimit )
907 prevReversed = ( jt->
Pos() == aCurrent->
Anchor( aScanDirection ) );
913 bool aStopAtLockedJoints )
915 const int MaxVerts = 1024 * 16;
917 std::array<VECTOR2I, MaxVerts + 1> corners;
918 std::array<LINKED_ITEM*, MaxVerts + 1> segs;
919 std::array<bool, MaxVerts + 1> arcReversed;
922 bool guardHit =
false;
924 int i_start = MaxVerts / 2, i_end = i_start + 1;
931 followLine( aSeg,
false, i_start, MaxVerts, corners.data(), segs.data(), arcReversed.data(),
932 guardHit, aStopAtLockedJoints );
936 followLine( aSeg,
true, i_end, MaxVerts, corners.data(), segs.data(), arcReversed.data(), guardHit,
937 aStopAtLockedJoints );
943 bool originSet =
false;
945 for(
int i = i_start + 1; i < i_end; i++ )
953 if( li && prev_seg != li )
957 const ARC* arc = static_cast<const ARC*>( li );
958 const SHAPE_ARC* sa = static_cast<const SHAPE_ARC*>( arc->
Shape() );
965 if( li == aSeg && aOriginSegmentIndex && !originSet )
967 *aOriginSegmentIndex = n;
999 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1005 JOINT j_start, j_end;
1012 if( id_end < id_start )
1013 std::swap( id_end, id_start );
1015 if( id_start >= 0 && id_end >= 0 )
1018 aLines.push_back( line );
1036 if( f == end && !
isRoot() )
1047 if( f->second.Layers().Overlaps( aLayer ) )
1072 JOINT_MAP::iterator f =
m_joints.find( tag );
1074 std::pair<JOINT_MAP::iterator, JOINT_MAP::iterator> range;
1081 for( f = range.first; f != range.second; ++f )
1086 JOINT jt( aPos, aLayers, aNet );
1093 range =
m_joints.equal_range( tag );
1095 if( range.first ==
m_joints.end() )
1098 for( f = range.first; f != range.second; ++f )
1100 if( aLayers.
Overlaps( f->second.Layers() ) )
1102 jt.
Merge( f->second );
1117 wxLogTrace(
"PNS",
"joint layers %d-%d, net %d, pos %s, links: %d",
1146 std::unordered_set<SEGMENT*> all_segs;
1149 for( i = m_items.begin(); i != m_items.end(); i++ )
1152 all_segs.insert( static_cast<SEGMENT*>( *i ) );
1157 for( i =
m_root->m_items.begin(); i !=
m_root->m_items.end(); i++ )
1160 all_segs.insert( static_cast<SEGMENT*>(*i) );
1164 JOINT_MAP::iterator j;
1170 wxLogTrace(
"PNS",
"joint : %s, links : %d\n",
1171 j->second.GetPos().Format().c_str(), j->second.LinkCount() );
1172 JOINT::LINKED_ITEMS::const_iterator k;
1174 for( k = j->second.GetLinkList().begin(); k != j->second.GetLinkList().end(); ++k )
1176 const ITEM* m_item = *k;
1178 switch( m_item->GetKind() )
1182 const SEGMENT* seg = static_cast<const SEGMENT*>( m_item );
1183 wxLogTrace(
"PNS",
" -> seg %s %s\n", seg->GetSeg().A.Format().c_str(),
1184 seg->GetSeg().B.Format().c_str() );
1195 int lines_count = 0;
1197 while( !all_segs.empty() )
1199 SEGMENT* s = *all_segs.begin();
1202 LINE::LinkedSegments* seg_refs = l->GetLinkedSegments();
1205 wxLogTrace(
"PNS",
"Line: %s, net %d ", l->GetLine().Format().c_str(), l->GetNet() );
1207 for( std::vector<SEGMENT*>::iterator j = seg_refs->begin(); j != seg_refs->end(); ++j )
1209 wxLogTrace(
"PNS",
"%s ", (*j)->GetSeg().A.Format().c_str() );
1211 if( j + 1 == seg_refs->end() )
1212 wxLogTrace(
"PNS",
"%s\n", (*j)->GetSeg().B.Format().c_str() );
1214 all_segs.erase( *j );
1220 wxLogTrace(
"PNS",
"Local joints: %d, lines : %d \n",
m_joints.size(), lines_count );
1237 aRemoved.push_back( item );
1240 aAdded.push_back( *i );
1249 for(
NODE* node : kids )
1251 node->releaseChildren();
1264 if( !item->BelongsTo(
this ) )
1284 Add( std::unique_ptr<ITEM>( item ) );
1304 for(
ITEM* item : *l_cur )
1306 if( item->OfKind( aKindMask ) && item->IsRoutable() )
1307 aItems.insert( item );
1317 for(
ITEM* item : *l_root )
1319 if( !
Overrides( item ) && item->OfKind( aKindMask ) && item->IsRoutable() )
1320 aItems.insert( item );
1331 item->SetRank( -1 );
1332 item->Mark( item->Marker() & ~aMarkerMask );
1339 std::list<ITEM*> garbage;
1343 if( item->Marker() & aMarker )
1344 garbage.push_back( item );
1347 for(
ITEM* item : garbage )
1370 && ( (
A == a2 &&
B == b2 ) || (
A == b2 &&
B == a2 ) ) )
1399 ARC* seg2 = static_cast<ARC*>( item );
1405 && ( (
A == a2 &&
B == b2 ) || (
A == b2 &&
B == a2 ) ) )
1429 for( JOINT_MAP::value_type& j :
m_joints )
1431 if( !j.second.Layers().Overlaps( aLayerMask ) )
1434 if( aBox.
Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1436 aJoints.push_back( &j.second );
1446 if( !
Overrides( &j.second ) && j.second.Layers().Overlaps( aLayerMask ) )
1448 if( aBox.
Contains( j.second.Pos() ) && j.second.LinkCount( aKindMask ) )
1450 aJoints.push_back( &j.second );
1470 for(
ITEM* item : *l_cur )
1472 if( item->Parent() == aParent )
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
int Find(const VECTOR2I &aP) const
Function Find()
const SHAPE_LINE_CHAIN & CLine() const
Base class for PNS router board items.
int Query(const ITEM *aItem, int aMinDistance, Visitor &aVisitor) const
Searches items in the index that are in proximity of aItem.
std::list< ITEM * > NET_ITEMS_LIST
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...
std::set< NODE * > m_children
list of nodes branched from this one
ITEM * m_item
Item found to be colliding with m_head.
const SHAPE_ARC & Arc(size_t aArc) const
DEFAULT_OBSTACLE_VISITOR(NODE::OBSTACLES &aTab, const ITEM *aItem, int aKindMask, bool aDifferentNetsOnly)
const NODE * m_node
node we are searching in (either root or a branch)
void SetOwner(NODE *aOwner)
Set the node that owns this item.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
virtual int Layer() const
Keep the router "world" - i.e.
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
int GetHoleToHoleClearance(const ITEM *aA, const ITEM *aB) const
Return the pre-set worst case clearance between any pair of items.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
void SetCountLimit(int aLimit)
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
bool Unlink(ITEM *aItem)
For trivial joints, return the segment adjacent to (aCurrent).
LINKED_ITEM * NextSegment(ITEM *aCurrent) const
int m_distFirst
... and the distance thereof
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
void doRemove(ITEM *aItem)
void removeSegmentIndex(SEGMENT *aSeg)
bool Overlaps(const LAYER_RANGE &aOther) const
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
void Link(LINKED_ITEM *aLink)
Return the list of links from the owning node that constitute this line (or NULL if the line is not l...
virtual int Clearance(const ITEM *aA, const ITEM *aB)=0
void Lock(bool aLock=true)
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
virtual void Unmark(int aMarker=-1) const
bool Overrides(ITEM *aItem) const
void linkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Unlink an item from a joint.
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
void Add(const LINE &aLine)
void Commit(NODE *aNode)
Apply the changes from a given branch (aNode) to the root branch.
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
const VECTOR2I & Pos() const
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
void unlinkJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet, ITEM *aWhere)
Helpers for adding/removing items.
bool operator()(ITEM *aItem) override
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
int PathLength(const VECTOR2I &aP) const
Function PathLength()
INDEX * m_index
Geometric/Net index of the items.
void Remove(ARC *aArc)
Remove an item from this branch.
void SetWidth(int aWidth)
Return line width.
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
const VECTOR2I & CPoint(int aIdx) const
virtual int Width() const
void addSegment(SEGMENT *aSeg)
NODE * m_root
root node of the whole hierarchy
int m_depth
depth of the node (number of parent nodes in the inheritance chain)
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
RULE_RESOLVER * m_ruleResolver
Design rules resolver.
bool IsLineCorner() const
void addSolid(SOLID *aSeg)
int GetClearance(const ITEM *aA, const ITEM *aB) const
bool BelongsTo(NODE *aNode) const
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.
void rebuildJoint(JOINT *aJoint, ITEM *aItem)
ITEM * FindItemByParent(const BOARD_ITEM *aParent)
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
HIT_VISITOR(ITEM_SET &aTab, const VECTOR2I &aPoint)
SEGMENT * findRedundantSegment(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
bool IsLinked() const
Check if the segment aLink is a part of the line.
bool Contains(const Vec &aPoint) const
Function Contains.
const std::string Format() const
Return the vector formatted as a string.
virtual int HoleClearance(const ITEM *aA, const ITEM *aB)=0
OBSTACLE_VISITOR(const ITEM *aItem)
void ClipVertexRange(int aStart, int aEnd)
Return the number of corners of angles specified by mask aAngles.
bool operator()(ITEM *aCandidate) override
bool visit(ITEM *aCandidate)
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true) const
Check for a collision (clearance violation) with between us and item aOther.
std::unordered_set< ITEM * > m_override
hash of root's items that have been changed in this node
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
const SHAPE_CIRCLE * Hole() const override
void SetWorld(const NODE *aNode, const NODE *aOverride=NULL)
int m_kindMask
(solids, vias, segments, etc...)
virtual int HoleToHoleClearance(const ITEM *aA, const ITEM *aB)=0
const ITEM * m_item
the item we are looking for collisions with
ITEM_SET::ENTRIES LINKED_ITEMS
Joints are hashed by their position, layers and net.
virtual void SetRank(int aRank)
const LINKED_ITEMS & LinkList() const
~NODE()
Return the expected clearance between items a and b.
int SegmentCount() const
Function SegmentCount()
ARC * findRedundantArc(const VECTOR2I &A, const VECTOR2I &B, const LAYER_RANGE &lr, int aNet)
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
void SetLayers(const LAYER_RANGE &aLayers)
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.
SHAPE_LINE_CHAIN m_hull
Hull of the colliding m_item.
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
SHAPE_LINE_CHAIN & Line()
NET_ITEMS_LIST * GetItemsForNet(int aNet)
Returns list of all items in a given net.
const VECTOR2I & Pos() const
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
virtual VECTOR2I Anchor(int n) const
void RemoveByMarker(int aMarker)
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
const SHAPE * Shape() const override
Return the geometrical shape of the item.
void removeSolidIndex(SOLID *aSeg)
JOINT_MAP::value_type TagJointPair
ITEM_SET::iterator begin()
void Dump(bool aLong=false)
const SEG CSegment(int aIndex) const
Function CSegment()
int Size() const
Returns number of items stored in the index.
virtual void ClearLinks()
Return the number of segments that were assembled together to form this line.
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
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.
HASH_TAG m_tag
< hash tag for unordered_multimap
JOINT & touchJoint(const VECTOR2I &aPos, const LAYER_RANGE &aLayers, int aNet)
Touch a joint and links it to an m_item.
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
std::unordered_set< ITEM * > m_garbageItems
void Add(ITEM *aItem)
Adds item to the spatial index.
const ENTRIES & CItems() const
void removeViaIndex(VIA *aVia)
int Width() const
Return true if the line is geometrically identical as line aOther.
void followLine(LINKED_ITEM *aCurrent, bool aScanDirection, int &aPos, int aLimit, VECTOR2I *aCorners, LINKED_ITEM **aSegments, bool *aArcReversed, bool &aGuardHit, bool aStopAtLockedJoints)
const ITEM * m_head
Item we search collisions with.
void Merge(const JOINT &aJoint)
virtual ~DEFAULT_OBSTACLE_VISITOR()
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.
void removeArcIndex(ARC *aVia)
PnsKind Kind() const
Return the type (kind) of the item.
OPT< OBSTACLE > OPT_OBSTACLE
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
SHAPE_ARC Reversed() const
int LinkCount(int aMask=-1) const
const VECTOR2I & Pos() const
int m_maxClearance
worst case item-item clearance
void Link(ITEM *aItem)
Unlink a given board item from the joint (upon its removal from a NODE)
JOINT_MAP m_joints
hash table with the joints, linking the items.
VECTOR2I m_ipFirst
First intersection between m_head and m_hull.
std::vector< OBSTACLE > OBSTACLES
const NODE * m_override
node that overrides root entries
Push and Shove diff pair dimensions (gap) settings dialog.
virtual VECTOR2I Anchor(int n) const override
NODE * m_parent
node this node was branched from
void Remove(ITEM *aItem)
Removes an item from the spatial index.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
ROUTER_IFACE * GetInterface() const
static ROUTER * GetInstance()
Represent a contiguous set of PCB layers.
const LAYER_RANGE & Layers() const
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
std::vector< ITEM * > ITEM_VECTOR
static std::vector< std::string > split(const std::string &aStr, const std::string &aDelim)
Splits the input string into a vector of output strings.
Hold an object colliding with another object, along with some useful data about the collision.