64 std::deque<JOINT*> searchQueue;
67 searchQueue.push_back( aStart );
68 processed.insert( aStart );
70 while( !searchQueue.empty() )
72 JOINT* current = searchQueue.front();
73 searchQueue.pop_front();
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 JOINT* jt = tmpNode->FindJoint( track.
CPoint( -1 ), &track );
110 if( !jt || jt->
Net() <= 0 )
156 std::set<ITEM*> disconnected;
162 for(
ITEM* link : jt->LinkList() )
164 if( disconnected.find( link ) != disconnected.end() )
165 disconnected.erase( link );
169 int best_dist = INT_MAX;
170 ITEM* best =
nullptr;
172 for(
ITEM* item : disconnected )
174 if( item->OfKind( aKindMask ) )
176 for(
int i = 0; i < item->AnchorCount(); i++ )
198 std::set<ITEM*>& aVisited,
JOINT** aTerminalJoint )
206 assert( jt !=
nullptr );
208 aVisited.insert( last );
219 else if( aVisited.find( link ) == aVisited.end() )
220 next_seg =
static_cast<SEGMENT*
>( link );
226 *aTerminalJoint = jt;
235 if( nextAnchor !=
anchor )
259 *aTerminalJoint = jt;
266 std::pair<JOINT*, JOINT*>* aTerminalJoints,
267 bool aFollowLockedSegments )
270 std::set<ITEM*> visited;
304 JOINT* jointA =
nullptr;
305 JOINT* jointB =
nullptr;
310 if( aTerminalJoints )
312 wxASSERT( jointA && jointB );
313 *aTerminalJoints = std::make_pair( jointA, jointB );
322 std::pair<JOINT*, JOINT*> joints;
328 auto getPadFromJoint =
339 *aTargetPad =
static_cast<PAD*
>( bi );
342 *aTargetSolid =
static_cast<SOLID*
>( item );
351 getPadFromJoint( joints.first, &padA, aStartPad );
354 getPadFromJoint( joints.second, &padB, aEndPad );
362 const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
364 int start = aForward ? 0 : aLine.
PointCount() - 1;
365 int delta = aForward ? 1 : -1;
370 for(
int vertex = start +
delta;
371 aForward ? vertex < aLine.
PointCount() : vertex >= 0;
376 bool containsA = shape->Contains( seg.
A );
377 bool containsB = shape->Contains( seg.
B );
379 if( containsA && containsB )
389 if( shape->Collide( seg, 0,
nullptr, &loc ) )
396 if( !aForward && clip < start )
397 aLine.
Remove( clip + 1, start );
398 else if( clip > start )
399 aLine.
Remove( start, clip - 1 );
408 const std::shared_ptr<SHAPE_POLY_SET>& shape = aPad->GetEffectivePolygon();
410 for(
int idx = 0; idx < initialPath.
Size(); idx++ )
415 LINE* line =
static_cast<LINE*
>( initialPath[idx] );
417 if( !aPad->FlashLayer( line->
Layer() ) )
420 const std::vector<VECTOR2I>& points = line->
CLine().
CPoints();
422 if( points.front() != aJoint->
Pos() && points.back() != aJoint->
Pos() )
427 if( shape->Contains( slc.
CPoint( 0 ) ) )
428 clipLineToPad( slc, aPad,
true );
429 else if( shape->Contains( slc.
CPoint( -1 ) ) )
430 clipLineToPad( slc, aPad,
false );
435 processPad( joints.first, padA );
438 processPad( joints.second, padB );
461 int refNet = aStart->
Net();
467 std::set<ITEM*> coupledItems;
471 SEGMENT* coupledSeg =
nullptr, *refSeg;
472 int minDist = std::numeric_limits<int>::max();
474 if( ( refSeg = dyn_cast<SEGMENT*>( aStart ) ) !=
nullptr )
476 for(
ITEM* item : coupledItems )
478 if(
SEGMENT* s = dyn_cast<SEGMENT*>( item ) )
480 if( s->Layers().Start() == refSeg->Layers().Start() &&
481 s->Width() == refSeg->Width() )
483 int dist = s->Seg().Distance( refSeg->Seg() );
490 if( isParallel && isCoupled && dist < minDist )
520 const VECTOR2I refDir = refSeg->Anchor( 1 ) - refSeg->Anchor( 0 );
521 const VECTOR2I displacement = refSeg->Anchor( 1 ) - coupledSeg->
Anchor( 1 );
535 std::set<ITEM*> visited;
536 std::deque<ITEM*> pending;
538 pending.push_back( aStart );
540 while( !pending.empty() )
543 ITEM* top = pending.front();
547 visited.insert( top );
558 if( visited.find( obs.m_item ) == visited.end() &&
559 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() &
MK_HEAD ) )
561 visited.insert( obs.m_item );
562 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)
PnsKind Kind() const
Return the type (kind) of the item.
virtual int Layer() const
const LAYER_RANGE & Layers() const
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
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...
int LinkCount(int aMask=-1) const
const LINKED_ITEMS & LinkList() const
bool IsNonFanoutVia() const
bool IsTraceWidthChange() const
Link the joint to a given board item (when it's added to the NODE).
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...
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, int aKindMask=ITEM::ANY_T, int aLimitCount=-1, bool aDifferentNetsOnly=true, int aOverrideClearance=-1)
Find items colliding (closer than clearance) with the item aItem.
void AllItemsInNet(int aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
std::vector< OBSTACLE > OBSTACLES
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
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 DpNetPolarity(int aNet)=0
virtual int DpCoupledNet(int aNet)=0
virtual VECTOR2I Anchor(int n) const override
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)
const ITEM_SET ConnectedItems(JOINT *aStart, int aKindMask=ITEM::ANY_T)
ITEM * NearestUnconnectedItem(JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
bool followTrivialPath(LINE *aLine, bool aLeft, ITEM_SET &aSet, std::set< ITEM * > &aVisited, JOINT **aTerminalJoint=nullptr)
const JOINT_SET ConnectedJoints(JOINT *aStart)
std::set< JOINT * > JOINT_SET
const ITEM_SET AssembleTrivialPath(ITEM *aStart, std::pair< JOINT *, JOINT * > *aTerminalJoints=nullptr, bool aFollowLockedSegments=false)
Assemble a trivial path between two joints given a starting item.
const int DP_PARALLELITY_THRESHOLD
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