65 std::deque<const JOINT*> searchQueue;
68 searchQueue.push_back( aStart );
69 processed.insert( aStart );
71 while( !searchQueue.empty() )
73 const JOINT* current = searchQueue.front();
74 searchQueue.pop_front();
82 const JOINT*
next = ( *a == *current ) ? b : a;
84 if( processed.find(
next ) == processed.end() )
86 processed.insert(
next );
87 searchQueue.push_back(
next );
100 LINE track( *aTrack );
107 tmpNode->Add( track );
109 const JOINT* jt = tmpNode->FindJoint( track.
CPoint( -1 ), &track );
160 std::set<ITEM*> disconnected;
166 for(
ITEM* link : jt->LinkList() )
168 if( disconnected.find( link ) != disconnected.end() )
169 disconnected.erase( link );
173 int best_dist = INT_MAX;
174 ITEM* best =
nullptr;
176 for(
ITEM* item : disconnected )
178 if( item->OfKind( aKindMask ) )
180 for(
int i = 0; i < item->AnchorCount(); i++ )
183 int d = ( p - aStart->
Pos() ).EuclideanNorm();
202 const JOINT** aTerminalJoint,
bool aFollowLockedSegments )
205 LINE* curr_line = aLine2;
206 std::set<ITEM*> visited;
214 assert( jt !=
nullptr );
216 if( !visited.insert( last ).second
220 *aTerminalJoint = jt;
230 for(
ITEM* link : links )
234 else if( visited.insert( link ).second )
235 next_seg =
static_cast<SEGMENT*
>( link );
241 *aTerminalJoint = jt;
249 if( nextAnchor !=
anchor )
260 curr_line =
static_cast<PNS::LINE*
>( aSet[0] );
268 curr_line =
static_cast<PNS::LINE*
>( aSet[aSet.
Size() - 1] );
277 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
278 bool aFollowLockedSegments )
293 for(
ITEM* item : links )
316 const JOINT* jointA =
nullptr;
317 const JOINT* jointB =
nullptr;
322 if( aTerminalJoints )
324 wxASSERT( jointA && jointB );
325 *aTerminalJoints = std::make_pair( jointA, jointB );
334 std::pair<const JOINT*, const JOINT*> joints;
340 auto getPadFromJoint =
341 [](
const JOINT* aJoint,
PAD** aTargetPad,
SOLID** aTargetSolid )
351 *aTargetPad =
static_cast<PAD*
>( bi );
354 *aTargetSolid =
static_cast<SOLID*
>( item );
363 getPadFromJoint( joints.first, &padA, aStartPad );
366 getPadFromJoint( joints.second, &padB, aEndPad );
374 const auto& shape = aPad->GetEffectivePolygon( aLayer,
ERROR_INSIDE );
376 int start = aForward ? 0 : aLine.
PointCount() - 1;
377 int delta = aForward ? 1 : -1;
382 for(
int vertex = start +
delta;
383 aForward ? vertex < aLine.
PointCount() : vertex >= 0;
388 bool containsA = shape->Contains( seg.
A );
389 bool containsB = shape->Contains( seg.
B );
391 if( containsA && containsB )
401 if( shape->Collide( seg, 0,
nullptr, &loc ) )
408 if( !aForward && clip < start )
409 aLine.
Remove( clip + 1, start );
410 else if( clip > start )
411 aLine.
Remove( start, clip - 1 );
420 const auto& shape = aPad->GetEffectivePolygon( aLayer,
ERROR_INSIDE );
422 for(
int idx = 0; idx < initialPath.
Size(); idx++ )
427 LINE* line =
static_cast<LINE*
>( initialPath[idx] );
429 if( !aPad->FlashLayer( line->
Layer() ) )
432 const std::vector<VECTOR2I>& points = line->
CLine().
CPoints();
434 if( points.front() != aJoint->
Pos() && points.back() != aJoint->
Pos() )
440 if( shape->Contains( slc.
CPoint( 0 ) ) )
441 clipLineToPad( slc, aPad, layer,
true );
442 else if( shape->Contains( slc.
CPoint( -1 ) ) )
443 clipLineToPad( slc, aPad, layer,
false );
448 processPad( joints.first, padA,
static_cast<PCB_LAYER_ID>( joints.first->Layer() ) );
451 processPad( joints.second, padB,
static_cast<PCB_LAYER_ID>( joints.second->Layer() ) );
478 if( !coupledNet || !startItem )
483 std::vector<ITEM*> pItems;
484 std::vector<ITEM*> nItems;
489 pItems.push_back( item );
492 std::set<ITEM*> coupledItems;
495 for(
ITEM* item : coupledItems )
498 nItems.push_back( item );
503 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
504 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
507 auto findNItem = [&](
ITEM* p_item )
509 for(
ITEM* n_item : nItems )
511 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
513 if( n_item->Kind() != p_item->Kind() )
536 const ARC* p_arc =
static_cast<const ARC*
>( p_item );
537 const ARC* n_arc =
static_cast<const ARC*
>( n_item );
551 if( dist_sq <= minDist_sq )
553 SEG::ecoord distTarget_sq = n_item->Shape()->SquaredDistance( targetPoint );
554 if( distTarget_sq < minDistTarget_sq )
556 minDistTarget_sq = distTarget_sq;
557 minDist_sq = dist_sq;
566 findNItem( startItem );
571 std::set<ITEM*> linksToTest;
583 linksToTest.emplace( link );
587 for(
ITEM* link : linksToTest )
610 const ARC* refArc =
static_cast<ARC*
>( refItem );
611 const ARC* coupledArc =
static_cast<ARC*
>( coupledItem );
625 std::set<ITEM*> visited;
626 std::deque<ITEM*> pending;
633 pending.push_back( aStart );
635 while( !pending.empty() )
638 ITEM* top = pending.front();
642 visited.insert( top );
646 for(
const OBSTACLE& obs : obstacles )
653 if( visited.find( obs.m_item ) == visited.end() &&
654 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() &
MK_HEAD ) )
656 visited.insert( obs.m_item );
657 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.
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)
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
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
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
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.
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
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.
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
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 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.
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 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...
virtual const VECTOR2I GetPoint(int aIndex) const override
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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
virtual VECTOR2I Centre() const
Compute a center-of-mass of the shape.
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.
@ PCB_PAD_T
class PAD, a pad in a footprint