64 std::deque<const JOINT*> searchQueue;
67 searchQueue.push_back( aStart );
68 processed.insert( aStart );
70 while( !searchQueue.empty() )
72 const JOINT* current = searchQueue.front();
73 searchQueue.pop_front();
81 const JOINT*
next = ( *a == *current ) ? b : a;
83 if( processed.find(
next ) == processed.end() )
85 processed.insert(
next );
86 searchQueue.push_back(
next );
99 LINE track( *aTrack );
106 tmpNode->Add( track );
108 const JOINT* jt = tmpNode->FindJoint( track.
CPoint( -1 ), &track );
159 std::set<ITEM*> disconnected;
165 for(
ITEM* link : jt->LinkList() )
167 if( disconnected.find( link ) != disconnected.end() )
168 disconnected.erase( link );
172 int best_dist = INT_MAX;
173 ITEM* best =
nullptr;
175 for(
ITEM* item : disconnected )
177 if( item->OfKind( aKindMask ) )
179 for(
int i = 0; i < item->AnchorCount(); i++ )
201 std::set<ITEM*>& aVisited,
const JOINT** aTerminalJoint )
209 assert( jt !=
nullptr );
211 aVisited.insert( last );
220 for(
ITEM* link : links )
224 else if( aVisited.find( link ) == aVisited.end() )
225 next_seg =
static_cast<SEGMENT*
>( link );
231 *aTerminalJoint = jt;
240 if( nextAnchor !=
anchor )
264 *aTerminalJoint = jt;
271 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
272 bool aFollowLockedSegments )
275 std::set<ITEM*> visited;
288 for(
ITEM* item : links )
311 const JOINT* jointA =
nullptr;
312 const JOINT* jointB =
nullptr;
317 if( aTerminalJoints )
319 wxASSERT( jointA && jointB );
320 *aTerminalJoints = std::make_pair( jointA, jointB );
329 std::pair<const JOINT*, const JOINT*> joints;
335 auto getPadFromJoint =
336 [](
const JOINT* aJoint,
PAD** aTargetPad,
SOLID** aTargetSolid )
346 *aTargetPad =
static_cast<PAD*
>( bi );
349 *aTargetSolid =
static_cast<SOLID*
>( item );
358 getPadFromJoint( joints.first, &padA, aStartPad );
361 getPadFromJoint( joints.second, &padB, aEndPad );
369 const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
371 int start = aForward ? 0 : aLine.
PointCount() - 1;
372 int delta = aForward ? 1 : -1;
377 for(
int vertex = start +
delta;
378 aForward ? vertex < aLine.
PointCount() : vertex >= 0;
383 bool containsA = shape->Contains( seg.
A );
384 bool containsB = shape->Contains( seg.
B );
386 if( containsA && containsB )
396 if( shape->Collide( seg, 0,
nullptr, &loc ) )
403 if( !aForward && clip < start )
404 aLine.
Remove( clip + 1, start );
405 else if( clip > start )
406 aLine.
Remove( start, clip - 1 );
413 [&](
const JOINT* aJoint,
PAD* aPad )
415 const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
417 for(
int idx = 0; idx < initialPath.
Size(); idx++ )
422 LINE* line =
static_cast<LINE*
>( initialPath[idx] );
424 if( !aPad->FlashLayer( line->
Layer() ) )
427 const std::vector<VECTOR2I>& points = line->
CLine().
CPoints();
429 if( points.front() != aJoint->
Pos() && points.back() != aJoint->
Pos() )
434 if( shape->Contains( slc.
CPoint( 0 ) ) )
435 clipLineToPad( slc, aPad,
true );
436 else if( shape->Contains( slc.
CPoint( -1 ) ) )
437 clipLineToPad( slc, aPad,
false );
442 processPad( joints.first, padA );
445 processPad( joints.second, padB );
474 std::set<ITEM*> coupledItems;
478 SEGMENT* coupledSeg =
nullptr, *refSeg;
479 int minDist = std::numeric_limits<int>::max();
481 if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) !=
nullptr )
483 for(
ITEM* item : coupledItems )
485 if(
SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
487 if( s->Layers().Start() == refSeg->Layers().Start() &&
488 s->Width() == refSeg->Width() )
490 int dist = s->Seg().Distance( refSeg->Seg() );
497 if( isParallel && isCoupled && dist < minDist )
527 const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
528 const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->
Anchor( 1 );
542 std::set<ITEM*> visited;
543 std::deque<ITEM*> pending;
550 pending.push_back( aStart );
552 while( !pending.empty() )
555 ITEM* top = pending.front();
559 visited.insert( top );
563 for(
const OBSTACLE& obs : obstacles )
570 if( visited.find( obs.m_item ) == visited.end() &&
571 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() &
MK_HEAD ) )
573 visited.insert( obs.m_item );
574 pending.push_back( obs.m_item );
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
KICAD_T Type() const
Returns the type of object.
Represent a contiguous set of PCB layers.
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 LAYER_RANGE &aLayers)
virtual NET_HANDLE Net() const
PnsKind Kind() const
Return the type (kind) of the item.
virtual int Layer() const
const LAYER_RANGE & Layers() const
bool OfKind(int aKindMask) const
virtual VECTOR2I Anchor(int n) 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
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.
LINKED_ITEM * GetLink(int aIndex) const
Erase the linking information. Used to detach the line from the owning node.
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.
std::set< OBSTACLE > OBSTACLES
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.
bool Add(std::unique_ptr< SEGMENT > &&aSegment, bool aAllowRedundant=false)
Add an item to the current node.
void Remove(ARC *aArc)
Remove an item from this branch.
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
virtual int NetCode(NET_HANDLE aNet)=0
virtual NET_HANDLE DpCoupledNet(NET_HANDLE aNet)=0
virtual int DpNetPolarity(NET_HANDLE aNet)=0
virtual VECTOR2I Anchor(int n) 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 NearestUnconnectedAnchorPoint(const LINE *aTrack, VECTOR2I &aPoint, LAYER_RANGE &aLayers, ITEM *&aItem)
const ITEM_SET ConnectedItems(const JOINT *aStart, int aKindMask=ITEM::ANY_T)
const JOINT_SET ConnectedJoints(const JOINT *aStart)
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 followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, const JOINT **aTerminalJoint=nullptr)
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
bool SimplifyLine(LINE *aLine)
const ITEM_SET AssembleTuningPath(ITEM *aStart, SOLID **aStartPad=nullptr, SOLID **aEndPad=nullptr)
Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fu...
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
virtual const VECTOR2I GetPoint(int aIndex) const override
int PointCount() const
Return the number of points (vertices) in this line chain.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
void Clear()
Remove all points from the line chain.
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.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
void Insert(size_t aVertex, const VECTOR2I &aP)
const std::vector< VECTOR2I > & CPoints() const
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
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.
double EuclideanNorm(const VECTOR2I &vector)
@ PCB_PAD_T
class PAD, a pad in a footprint