46 LINE l =
m_world->AssembleLine( root,
nullptr,
false,
false,
false );
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();
81 const JOINT* a =
m_world->FindJoint( item->Anchor( 0 ), item );;
82 const JOINT* b =
m_world->FindJoint( item->Anchor( 1 ), item );;
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 );
107 std::unique_ptr<NODE> tmpNode(
m_world->Branch() );
110 tmpNode->Add( track );
114 if( !jt ||
m_world->GetRuleResolver()->NetCode( jt->
Net() ) <= 0 )
163 std::set<ITEM*> disconnected;
165 m_world->AllItemsInNet( aStart->
Net(), 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 std::set<ITEM*>& aVisited,
206 bool aFollowLockedSegments )
213 for(
ITEM* link : links )
215 if( link->OfKind(
ITEM::VIA_T ) && !aVisited.contains( link ) )
219 for(
ITEM* link : links )
222 && link != aPrev && !aVisited.contains( link ) )
225 false, aFollowLockedSegments );
233 aVisited.insert( ll );
236 aVisited.insert(
via );
257 aVisited.erase( ll );
260 aVisited.erase(
via );
272 const JOINT** aTerminalJointB,
273 bool aFollowLockedSegments )
280 std::set<ITEM*> visited;
283 visited.insert( link );
291 if( aTerminalJointA )
292 *aTerminalJointA =
left.m_end;
294 if( aTerminalJointB )
295 *aTerminalJointB =
right.m_end;
297 for(
int i =
left.m_items.Size() - 1; i >= 0; i-- )
308 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
309 bool aFollowLockedSegments )
324 for(
ITEM* item : links )
343 LINE l =
m_world->AssembleLine( seg,
nullptr,
false, aFollowLockedSegments );
345 const JOINT* jointA =
nullptr;
346 const JOINT* jointB =
nullptr;
350 if( aTerminalJoints )
352 wxASSERT( jointA && jointB );
353 *aTerminalJoints = std::make_pair( jointA, jointB );
363 std::pair<const JOINT*, const JOINT*> joints;
369 auto getPadFromJoint =
370 [](
const JOINT* aJoint,
PAD** aTargetPad,
SOLID** aTargetSolid )
380 *aTargetPad =
static_cast<PAD*
>( bi );
383 *aTargetSolid =
static_cast<SOLID*
>( item );
392 getPadFromJoint( joints.first, &padA, aStartPad );
395 getPadFromJoint( joints.second, &padB, aEndPad );
400 auto processPad = [&](
PAD* aPad,
int aLayer )
402 for(
int idx = 0; idx < initialPath.
Size(); idx++ )
407 LINE* line =
static_cast<LINE*
>( initialPath[idx] );
416 processPad( padA, joints.first->Layer() );
419 processPad( padB, joints.second->Layer() );
446 if( !coupledNet || !startItem )
451 std::vector<ITEM*> pItems;
452 std::vector<ITEM*> nItems;
457 pItems.push_back( item );
460 std::set<ITEM*> coupledItems;
461 m_world->AllItemsInNet( coupledNet, coupledItems );
463 for(
ITEM* item : coupledItems )
466 nItems.push_back( item );
471 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
472 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
475 auto findNItem = [&](
ITEM* p_item )
477 for(
ITEM* n_item : nItems )
479 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
481 if( n_item->Kind() != p_item->Kind() )
504 const ARC* p_arc =
static_cast<const ARC*
>( p_item );
505 const ARC* n_arc =
static_cast<const ARC*
>( n_item );
519 if( dist_sq <= minDist_sq )
521 SEG::ecoord distTarget_sq = n_item->Shape( -1 )->SquaredDistance( targetPoint );
522 if( distTarget_sq < minDistTarget_sq )
524 minDistTarget_sq = distTarget_sq;
525 minDist_sq = dist_sq;
534 findNItem( startItem );
539 std::set<ITEM*> linksToTest;
551 linksToTest.emplace( link );
555 for(
ITEM* link : linksToTest )
564 if(
m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
578 const ARC* refArc =
static_cast<ARC*
>( refItem );
579 const ARC* coupledArc =
static_cast<ARC*
>( coupledItem );
594 std::deque<ITEM*> pending;
601 pending.push_back( aStart );
604 int64_t initialArea = clusterBBox.
GetArea();
606 while( !pending.empty() )
609 ITEM* top = pending.front();
615 m_world->QueryColliding( top, obstacles, opts );
617 for(
const OBSTACLE& obs : obstacles )
624 if( aExcludedNet && obs.m_item->Net() == aExcludedNet )
630 clusterBBox.
Merge( line.CLine().BBox() );
634 clusterBBox.
Merge( obs.m_item->Shape( aLayer )->BBox() );
637 const int64_t currentArea = clusterBBox.
GetArea();
638 const double areaRatio = (double) currentArea / (
double) ( initialArea + 1 );
640 if( aAreaExpansionLimit > 0.0 && areaRatio > aAreaExpansionLimit )
643 if( cluster.
m_items.find( obs.m_item ) == cluster.
m_items.end() &&
644 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() &
MK_HEAD ) )
646 cluster.
m_items.insert( obs.m_item );
647 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)
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
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.
std::set< OBSTACLE > OBSTACLES
virtual PCB_LAYER_ID GetBoardLayerFromPNSLayer(int aLayer) const =0
int Width() const override
PATH_RESULT followBranch(const JOINT *aJoint, LINKED_ITEM *aPrev, std::set< ITEM * > &aVisited, bool aFollowLockedSegments)
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)
ITEM_SET followTrivialPath(LINE *aLine, const JOINT **aTerminalJointA, const JOINT **aTerminalJointB, 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.
long long int Length() const
Return length of the line chain in Euclidean metric.
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
VECTOR2< int32_t > VECTOR2I