66 std::deque<const JOINT*> searchQueue;
69 searchQueue.push_back( aStart );
70 processed.insert( aStart );
72 while( !searchQueue.empty() )
74 const JOINT* current = searchQueue.front();
75 searchQueue.pop_front();
83 const JOINT*
next = ( *a == *current ) ? b : a;
85 if( processed.find(
next ) == processed.end() )
87 processed.insert(
next );
88 searchQueue.push_back(
next );
101 LINE track( *aTrack );
110 tmpNode->Add( track );
163 std::set<ITEM*> disconnected;
169 for(
ITEM* link : jt->LinkList() )
171 if( disconnected.find( link ) != disconnected.end() )
172 disconnected.erase( link );
176 int best_dist = INT_MAX;
177 ITEM* best =
nullptr;
179 for(
ITEM* item : disconnected )
181 if( item->OfKind( aKindMask ) )
183 for(
int i = 0; i < item->AnchorCount(); i++ )
186 int d = ( p - aStart->
Pos() ).EuclideanNorm();
205 const JOINT** aTerminalJoint,
bool aFollowLockedSegments )
208 LINE* curr_line = aLine2;
209 std::set<ITEM*> visited;
217 assert( jt !=
nullptr );
219 if( !visited.insert( last ).second
223 *aTerminalJoint = jt;
233 for(
ITEM* link : links )
237 else if( !visited.contains( link ) )
238 next_seg =
static_cast<SEGMENT*
>( link );
244 *aTerminalJoint = jt;
252 if( nextAnchor !=
anchor )
263 curr_line =
static_cast<PNS::LINE*
>( aSet[0] );
271 curr_line =
static_cast<PNS::LINE*
>( aSet[aSet.
Size() - 1] );
280 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
281 bool aFollowLockedSegments )
296 for(
ITEM* item : links )
319 const JOINT* jointA =
nullptr;
320 const JOINT* jointB =
nullptr;
325 if( aTerminalJoints )
327 wxASSERT( jointA && jointB );
328 *aTerminalJoints = std::make_pair( jointA, jointB );
338 std::pair<const JOINT*, const JOINT*> joints;
344 auto getPadFromJoint =
345 [](
const JOINT* aJoint,
PAD** aTargetPad,
SOLID** aTargetSolid )
355 *aTargetPad =
static_cast<PAD*
>( bi );
358 *aTargetSolid =
static_cast<SOLID*
>( item );
367 getPadFromJoint( joints.first, &padA, aStartPad );
370 getPadFromJoint( joints.second, &padB, aEndPad );
375 auto processPad = [&](
PAD* aPad,
int aLayer )
377 for(
int idx = 0; idx < initialPath.
Size(); idx++ )
382 LINE* line =
static_cast<LINE*
>( initialPath[idx] );
391 processPad( padA, joints.first->Layer() );
394 processPad( padB, joints.second->Layer() );
421 if( !coupledNet || !startItem )
426 std::vector<ITEM*> pItems;
427 std::vector<ITEM*> nItems;
432 pItems.push_back( item );
435 std::set<ITEM*> coupledItems;
438 for(
ITEM* item : coupledItems )
441 nItems.push_back( item );
446 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
447 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
450 auto findNItem = [&](
ITEM* p_item )
452 for(
ITEM* n_item : nItems )
454 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
456 if( n_item->Kind() != p_item->Kind() )
479 const ARC* p_arc =
static_cast<const ARC*
>( p_item );
480 const ARC* n_arc =
static_cast<const ARC*
>( n_item );
494 if( dist_sq <= minDist_sq )
496 SEG::ecoord distTarget_sq = n_item->Shape( -1 )->SquaredDistance( targetPoint );
497 if( distTarget_sq < minDistTarget_sq )
499 minDistTarget_sq = distTarget_sq;
500 minDist_sq = dist_sq;
509 findNItem( startItem );
514 std::set<ITEM*> linksToTest;
526 linksToTest.emplace( link );
530 for(
ITEM* link : linksToTest )
553 const ARC* refArc =
static_cast<ARC*
>( refItem );
554 const ARC* coupledArc =
static_cast<ARC*
>( coupledItem );
569 std::deque<ITEM*> pending;
576 pending.push_back( aStart );
579 int64_t initialArea = clusterBBox.
GetArea();
581 while( !pending.empty() )
584 ITEM* top = pending.front();
592 for(
const OBSTACLE& obs : obstacles )
599 if( aExcludedNet && obs.m_item->Net() == aExcludedNet )
605 clusterBBox.
Merge( line.CLine().BBox() );
609 clusterBBox.
Merge( obs.m_item->Shape( aLayer )->BBox() );
612 const int64_t currentArea = clusterBBox.
GetArea();
613 const double areaRatio = (double) currentArea / (
double) ( initialArea + 1 );
615 if( aAreaExpansionLimit > 0.0 && areaRatio > aAreaExpansionLimit )
618 if( cluster.
m_items.find( obs.m_item ) == cluster.
m_items.end() &&
619 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() &
MK_HEAD ) )
621 cluster.
m_items.insert( obs.m_item );
622 pending.push_back( obs.m_item );
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
constexpr ecoord_type GetArea() const
Return the area of the rectangle.
KICAD_T Type() const
Returns the type of object.
static void OptimiseTraceInPad(SHAPE_LINE_CHAIN &aLine, const PAD *aPad, PCB_LAYER_ID aPcbLayer)
Optimises the given trace / line to minimise the electrical path length within the given pad.
int Width() const override
const SHAPE_ARC & CArc() const
Basic class for a differential pair.
void SetWidth(int aWidth)
void Add(const LINE &aLine)
void Prepend(const LINE &aLine)
Base class for PNS router board items.
void SetLayers(const PNS_LAYER_RANGE &aLayers)
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
const PNS_LAYER_RANGE & Layers() const
virtual NET_HANDLE Net() const
PnsKind Kind() const
Return the type (kind) of the item.
virtual int Layer() const
bool OfKind(int aKindMask) const
virtual VECTOR2I Anchor(int n) const
virtual int AnchorCount() const
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
const std::vector< ITEM * > & LinkList() const
NET_HANDLE Net() const override
int LinkCount(int aMask=-1) const
bool IsNonFanoutVia() const
bool IsTraceWidthChange() const
Link the joint to a given board item (when it's added to the NODE).
const ITEM_SET & CLinks() const
const VECTOR2I & Pos() const
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
const VECTOR2I & CPoint(int aIdx) const
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
const SHAPE_LINE_CHAIN & CLine() const
const VECTOR2I & CLastPoint() const
SHAPE_LINE_CHAIN & Line()
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
int Width() const
Return true if the line is geometrically identical as line aOther.
bool IsLinked() const
Check if the segment aLink is a part of the line.
std::vector< LINKED_ITEM * > & Links()
LINKED_ITEM * GetLink(int aIndex) const
Erase the linking information. Used to detach the line from the owning node.
virtual void ClearLinks()
Return the number of segments that were assembled together to form this line.
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, NET_HANDLE aNet) const
Search for a joint at a given position, layer and belonging to given net.
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
std::set< OBSTACLE > OBSTACLES
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false, bool aAllowSegmentSizeMismatch=true)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
void AllItemsInNet(NET_HANDLE aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS()) const
Find items colliding (closer than clearance) with the item aItem.
void Remove(ARC *aArc)
Remove an item from this branch.
virtual PCB_LAYER_ID GetBoardLayerFromPNSLayer(int aLayer) const =0
virtual int NetCode(NET_HANDLE aNet)=0
virtual NET_HANDLE DpCoupledNet(NET_HANDLE aNet)=0
virtual int DpNetPolarity(NET_HANDLE aNet)=0
int Width() const override
ITEM * NearestUnconnectedItem(const JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
std::set< const JOINT * > JOINT_SET
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, const JOINT **aTerminalJoint=nullptr, bool aFollowLockedSegments=false)
const ITEM_SET ConnectedItems(const JOINT *aStart, int aKindMask=ITEM::ANY_T)
bool NearestUnconnectedAnchorPoint(const LINE *aTrack, VECTOR2I &aPoint, PNS_LAYER_RANGE &aLayers, ITEM *&aItem)
const CLUSTER AssembleCluster(ITEM *aStart, int aLayer, double aAreaExpansionLimit=0.0, NET_HANDLE aExcludedNet=nullptr)
const JOINT_SET ConnectedJoints(const JOINT *aStart)
const ITEM_SET AssembleTuningPath(ROUTER_IFACE *aRouterIface, ITEM *aStart, SOLID **aStartPad=nullptr, SOLID **aEndPad=nullptr)
Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fu...
const int DP_PARALLELITY_THRESHOLD
const ITEM_SET AssembleTrivialPath(ITEM *aStart, std::pair< const JOINT *, const JOINT * > *aTerminalJoints=nullptr, bool aFollowLockedSegments=false)
Assemble a trivial path between two joints given a starting item.
bool SimplifyLine(LINE *aLine)
Represent a contiguous set of PCB layers.
ecoord SquaredDistance(const SEG &aSeg) const
VECTOR2I::extended_type ecoord
static SEG::ecoord Square(int a)
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
const VECTOR2I & GetCenter() const
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
virtual VECTOR2I Centre() const
Compute a center-of-mass of the shape.
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
constexpr extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
PCB_LAYER_ID
A quick note on layer IDs:
Push and Shove diff pair dimensions (gap) settings dialog.
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Hold an object colliding with another object, along with some useful data about the collision.
std::set< ITEM * > m_items
@ PCB_PAD_T
class PAD, a pad in a footprint