KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_topology.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2015 CERN
5 * Copyright (C) 2016-2023 KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#include "pns_line.h"
23#include "pns_segment.h"
24#include "pns_arc.h"
25#include "pns_node.h"
26#include "pns_joint.h"
27#include "pns_solid.h"
28#include "pns_router.h"
29#include "pns_utils.h"
30
31#include "pns_diff_pair.h"
32#include "pns_topology.h"
33
34#include <board.h>
35#include <pad.h>
36
37namespace PNS {
38
40{
41 if( !aLine->IsLinked() || !aLine->SegmentCount() )
42 return false;
43
44 LINKED_ITEM* root = aLine->GetLink( 0 );
45 LINE l = m_world->AssembleLine( root );
46 SHAPE_LINE_CHAIN simplified( l.CLine() );
47
48 simplified.Simplify();
49
50 if( simplified.PointCount() != l.PointCount() )
51 {
52 m_world->Remove( l );
53 LINE lnew( l );
54 lnew.SetShape( simplified );
55 m_world->Add( lnew );
56 return true;
57 }
58
59 return false;
60}
61
62
64{
65 std::deque<const JOINT*> searchQueue;
66 JOINT_SET processed;
67
68 searchQueue.push_back( aStart );
69 processed.insert( aStart );
70
71 while( !searchQueue.empty() )
72 {
73 const JOINT* current = searchQueue.front();
74 searchQueue.pop_front();
75
76 for( ITEM* item : current->LinkList() )
77 {
78 if( item->OfKind( ITEM::SEGMENT_T ) )
79 {
80 const JOINT* a = m_world->FindJoint( item->Anchor( 0 ), item );;
81 const JOINT* b = m_world->FindJoint( item->Anchor( 1 ), item );;
82 const JOINT* next = ( *a == *current ) ? b : a;
83
84 if( processed.find( next ) == processed.end() )
85 {
86 processed.insert( next );
87 searchQueue.push_back( next );
88 }
89 }
90 }
91 }
92
93 return processed;
94}
95
96
98 PNS_LAYER_RANGE& aLayers, ITEM*& aItem )
99{
100 LINE track( *aTrack );
101 VECTOR2I end;
102
103 if( !track.PointCount() )
104 return false;
105
106 std::unique_ptr<NODE> tmpNode( m_world->Branch() );
107
108 track.ClearLinks();
109 tmpNode->Add( track );
110
111 const JOINT* jt = tmpNode->FindJoint( track.CPoint( -1 ), &track );
112
113 if( !jt || m_world->GetRuleResolver()->NetCode( jt->Net() ) <= 0 )
114 return false;
115
116 if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 )
117 || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
118 {
119 end = jt->Pos();
120 aLayers = jt->Layers();
121 aItem = jt->LinkList()[0];
122 }
123 else
124 {
125 int anchor;
126
127 TOPOLOGY topo( tmpNode.get() );
128 ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
129
130 if( !it )
131 return false;
132
133 end = it->Anchor( anchor );
134 aLayers = it->Layers();
135 aItem = it;
136 }
137
138 aPoint = end;
139 return true;
140}
141
142
143bool TOPOLOGY::LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine )
144{
145 VECTOR2I end;
146 // Ratline doesn't care about the layer
147 PNS_LAYER_RANGE layers;
148 ITEM* unusedItem;
149
150 if( !NearestUnconnectedAnchorPoint( aTrack, end, layers, unusedItem ) )
151 return false;
152
153 aRatLine.Clear();
154 aRatLine.Append( aTrack->CPoint( -1 ) );
155 aRatLine.Append( end );
156 return true;
157}
158
159
160ITEM* TOPOLOGY::NearestUnconnectedItem( const JOINT* aStart, int* aAnchor, int aKindMask )
161{
162 std::set<ITEM*> disconnected;
163
164 m_world->AllItemsInNet( aStart->Net(), disconnected );
165
166 for( const JOINT* jt : ConnectedJoints( aStart ) )
167 {
168 for( ITEM* link : jt->LinkList() )
169 {
170 if( disconnected.find( link ) != disconnected.end() )
171 disconnected.erase( link );
172 }
173 }
174
175 int best_dist = INT_MAX;
176 ITEM* best = nullptr;
177
178 for( ITEM* item : disconnected )
179 {
180 if( item->OfKind( aKindMask ) )
181 {
182 for( int i = 0; i < item->AnchorCount(); i++ )
183 {
184 VECTOR2I p = item->Anchor( i );
185 int d = ( p - aStart->Pos() ).EuclideanNorm();
186
187 if( d < best_dist )
188 {
189 best_dist = d;
190 best = item;
191
192 if( aAnchor )
193 *aAnchor = i;
194 }
195 }
196 }
197 }
198
199 return best;
200}
201
202
203bool TOPOLOGY::followTrivialPath( LINE* aLine2, bool aLeft, ITEM_SET& aSet,
204 const JOINT** aTerminalJoint, bool aFollowLockedSegments )
205{
206 assert( aLine2->IsLinked() );
207 LINE* curr_line = aLine2;
208 std::set<ITEM*> visited;
209
210 while( true )
211 {
212 VECTOR2I anchor = aLeft ? curr_line->CPoint( 0 ) : curr_line->CPoint( -1 );
213 LINKED_ITEM* last = aLeft ? curr_line->Links().front() : curr_line->Links().back();
214 const JOINT* jt = m_world->FindJoint( anchor, curr_line );
215
216 assert( jt != nullptr );
217
218 if( !visited.insert( last ).second
219 || ( !jt->IsNonFanoutVia() && !jt->IsTraceWidthChange() ) )
220 {
221 if( aTerminalJoint )
222 *aTerminalJoint = jt;
223
224 return false;
225 }
226
227 ITEM* via = nullptr;
228 SEGMENT* next_seg = nullptr;
229
230 ITEM_SET links( jt->CLinks() );
231
232 for( ITEM* link : links )
233 {
234 if( link->OfKind( ITEM::VIA_T ) )
235 via = link;
236 else if( visited.insert( link ).second )
237 next_seg = static_cast<SEGMENT*>( link );
238 }
239
240 if( !next_seg )
241 {
242 if( aTerminalJoint )
243 *aTerminalJoint = jt;
244
245 return false;
246 }
247
248 LINE l = m_world->AssembleLine( next_seg, nullptr, false, aFollowLockedSegments );
249 VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
250
251 if( nextAnchor != anchor )
252 {
253 l.Reverse();
254 }
255
256 if( aLeft )
257 {
258 if( via )
259 aSet.Prepend( via );
260
261 aSet.Prepend( l );
262 curr_line = static_cast<PNS::LINE*>( aSet[0] );
263 }
264 else
265 {
266 if( via )
267 aSet.Add( via );
268
269 aSet.Add( l );
270 curr_line = static_cast<PNS::LINE*>( aSet[aSet.Size() - 1] );
271 }
272
273 continue;
274 }
275}
276
277
279 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
280 bool aFollowLockedSegments )
281{
283 LINKED_ITEM* seg = nullptr;
284
285 if( aStart->Kind() == ITEM::VIA_T )
286 {
287 VIA* via = static_cast<VIA*>( aStart );
288 const JOINT* jt = m_world->FindJoint( via->Pos(), via );
289
290 if( !jt->IsNonFanoutVia() )
291 return ITEM_SET();
292
293 ITEM_SET links( jt->CLinks() );
294
295 for( ITEM* item : links )
296 {
297 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
298 {
299 seg = static_cast<LINKED_ITEM*>( item );
300 break;
301 }
302 }
303 }
304 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
305 {
306 seg = static_cast<LINKED_ITEM*>( aStart );
307 }
308
309 if( !seg )
310 return ITEM_SET();
311
312 // Assemble a line following through locked segments
313 // TODO: consider if we want to allow tuning lines with different widths in the future
314 LINE l = m_world->AssembleLine( seg, nullptr, false, aFollowLockedSegments );
315
316 path.Add( l );
317
318 const JOINT* jointA = nullptr;
319 const JOINT* jointB = nullptr;
320
321 followTrivialPath( &l, false, path, &jointB, aFollowLockedSegments );
322 followTrivialPath( &l, true, path, &jointA, aFollowLockedSegments );
323
324 if( aTerminalJoints )
325 {
326 wxASSERT( jointA && jointB );
327 *aTerminalJoints = std::make_pair( jointA, jointB );
328 }
329
330 return path;
331}
332
333
334const ITEM_SET TOPOLOGY::AssembleTuningPath( ITEM* aStart, SOLID** aStartPad, SOLID** aEndPad )
335{
336 std::pair<const JOINT*, const JOINT*> joints;
337 ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints, true );
338
339 PAD* padA = nullptr;
340 PAD* padB = nullptr;
341
342 auto getPadFromJoint =
343 []( const JOINT* aJoint, PAD** aTargetPad, SOLID** aTargetSolid )
344 {
345 for( ITEM* item : aJoint->LinkList() )
346 {
347 if( item->OfKind( ITEM::SOLID_T ) )
348 {
349 BOARD_ITEM* bi = static_cast<SOLID*>( item )->Parent();
350
351 if( bi->Type() == PCB_PAD_T )
352 {
353 *aTargetPad = static_cast<PAD*>( bi );
354
355 if( aTargetSolid )
356 *aTargetSolid = static_cast<SOLID*>( item );
357 }
358
359 break;
360 }
361 }
362 };
363
364 if( joints.first )
365 getPadFromJoint( joints.first, &padA, aStartPad );
366
367 if( joints.second )
368 getPadFromJoint( joints.second, &padB, aEndPad );
369
370 if( !padA && !padB )
371 return initialPath;
372
373 auto clipLineToPad =
374 []( SHAPE_LINE_CHAIN& aLine, PAD* aPad, PCB_LAYER_ID aLayer, bool aForward = true )
375 {
376 const auto& shape = aPad->GetEffectivePolygon( aLayer, ERROR_INSIDE );
377
378 int start = aForward ? 0 : aLine.PointCount() - 1;
379 int delta = aForward ? 1 : -1;
380
381 // Skip the "first" (or last) vertex, we already know it's contained in the pad
382 int clip = start;
383
384 for( int vertex = start + delta;
385 aForward ? vertex < aLine.PointCount() : vertex >= 0;
386 vertex += delta )
387 {
388 SEG seg( aLine.GetPoint( vertex ), aLine.GetPoint( vertex - delta ) );
389
390 bool containsA = shape->Contains( seg.A );
391 bool containsB = shape->Contains( seg.B );
392
393 if( containsA && containsB )
394 {
395 // Whole segment is inside: clip out this segment
396 clip = vertex;
397 }
398 else if( containsB )
399 {
400 // Only one point inside: Find the intersection
401 VECTOR2I loc;
402
403 if( shape->Collide( seg, 0, nullptr, &loc ) )
404 {
405 aLine.Replace( vertex - delta, vertex - delta, loc );
406 }
407 }
408 }
409
410 if( !aForward && clip < start )
411 aLine.Remove( clip + 1, start );
412 else if( clip > start )
413 aLine.Remove( start, clip - 1 );
414
415 // Now connect the dots
416 aLine.Insert( aForward ? 0 : aLine.PointCount(), aPad->GetPosition() );
417 };
418
419 auto processPad =
420 [&]( const JOINT* aJoint, PAD* aPad, PCB_LAYER_ID aLayer )
421 {
422 const auto& shape = aPad->GetEffectivePolygon( aLayer, ERROR_INSIDE );
423
424 for( int idx = 0; idx < initialPath.Size(); idx++ )
425 {
426 if( initialPath[idx]->Kind() != ITEM::LINE_T )
427 continue;
428
429 LINE* line = static_cast<LINE*>( initialPath[idx] );
430
431 if( !aPad->FlashLayer( line->Layer() ) )
432 continue;
433
434 const std::vector<VECTOR2I>& points = line->CLine().CPoints();
435
436 if( points.front() != aJoint->Pos() && points.back() != aJoint->Pos() )
437 continue;
438
439 SHAPE_LINE_CHAIN& slc = line->Line();
440 const PCB_LAYER_ID& layer = static_cast<PCB_LAYER_ID>( line->Layer() );
441
442 if( shape->Contains( slc.CPoint( 0 ) ) )
443 clipLineToPad( slc, aPad, layer, true );
444 else if( shape->Contains( slc.CPoint( -1 ) ) )
445 clipLineToPad( slc, aPad, layer, false );
446 }
447 };
448
449 if( padA )
450 processPad( joints.first, padA, static_cast<PCB_LAYER_ID>( joints.first->Layer() ) );
451
452 if( padB )
453 processPad( joints.second, padB, static_cast<PCB_LAYER_ID>( joints.second->Layer() ) );
454
455 return initialPath;
456}
457
458
459const ITEM_SET TOPOLOGY::ConnectedItems( const JOINT* aStart, int aKindMask )
460{
461 return ITEM_SET();
462}
463
464
465const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
466{
467 return ITEM_SET();
468}
469
470
471bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
472
473
475{
476 NET_HANDLE refNet = aStart->Net();
477 NET_HANDLE coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
478 LINKED_ITEM* startItem = dynamic_cast<LINKED_ITEM*>( aStart );
479
480 if( !coupledNet || !startItem )
481 return false;
482
483 LINE lp = m_world->AssembleLine( startItem );
484
485 std::vector<ITEM*> pItems;
486 std::vector<ITEM*> nItems;
487
488 for( ITEM* item : lp.Links() )
489 {
490 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
491 pItems.push_back( item );
492 }
493
494 std::set<ITEM*> coupledItems;
495 m_world->AllItemsInNet( coupledNet, coupledItems );
496
497 for( ITEM* item : coupledItems )
498 {
499 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
500 nItems.push_back( item );
501 }
502
503 LINKED_ITEM* refItem = nullptr;
504 LINKED_ITEM* coupledItem = nullptr;
505 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
506 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
507 VECTOR2I targetPoint = aStart->Shape( -1 )->Centre();
508
509 auto findNItem = [&]( ITEM* p_item )
510 {
511 for( ITEM* n_item : nItems )
512 {
513 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
514
515 if( n_item->Kind() != p_item->Kind() )
516 continue;
517
518 if( p_item->Kind() == ITEM::SEGMENT_T )
519 {
520 const SEGMENT* p_seg = static_cast<const SEGMENT*>( p_item );
521 const SEGMENT* n_seg = static_cast<const SEGMENT*>( n_item );
522
523 if( n_seg->Width() != p_seg->Width() )
524 continue;
525
526 if( !p_seg->Seg().ApproxParallel( n_seg->Seg(), DP_PARALLELITY_THRESHOLD ) )
527 continue;
528
529 SEG p_clip, n_clip;
530
531 if( !commonParallelProjection( p_seg->Seg(), n_seg->Seg(), p_clip, n_clip ) )
532 continue;
533
534 dist_sq = n_seg->Seg().SquaredDistance( p_seg->Seg() );
535 }
536 else if( p_item->Kind() == ITEM::ARC_T )
537 {
538 const ARC* p_arc = static_cast<const ARC*>( p_item );
539 const ARC* n_arc = static_cast<const ARC*>( n_item );
540
541 if( n_arc->Width() != p_arc->Width() )
542 continue;
543
544 VECTOR2I centerDiff = n_arc->CArc().GetCenter() - p_arc->CArc().GetCenter();
545 SEG::ecoord centerDist_sq = centerDiff.SquaredEuclideanNorm();
546
547 if( centerDist_sq > SEG::Square( DP_PARALLELITY_THRESHOLD ) )
548 continue;
549
550 dist_sq = SEG::Square( p_arc->CArc().GetRadius() - n_arc->CArc().GetRadius() );
551 }
552
553 if( dist_sq <= minDist_sq )
554 {
555 SEG::ecoord distTarget_sq = n_item->Shape( -1 )->SquaredDistance( targetPoint );
556 if( distTarget_sq < minDistTarget_sq )
557 {
558 minDistTarget_sq = distTarget_sq;
559 minDist_sq = dist_sq;
560
561 refItem = static_cast<LINKED_ITEM*>( p_item );
562 coupledItem = static_cast<LINKED_ITEM*>( n_item );
563 }
564 }
565 }
566 };
567
568 findNItem( startItem );
569
570 if( !coupledItem )
571 {
572 LINKED_ITEM* linked = static_cast<LINKED_ITEM*>( startItem );
573 std::set<ITEM*> linksToTest;
574
575 for( int i = 0; i < linked->AnchorCount(); i++ )
576 {
577 const JOINT* jt = m_world->FindJoint( linked->Anchor( i ), linked );
578
579 if( !jt )
580 continue;
581
582 for( ITEM* link : jt->LinkList() )
583 {
584 if( link != linked )
585 linksToTest.emplace( link );
586 }
587 }
588
589 for( ITEM* link : linksToTest )
590 findNItem( link );
591 }
592
593 if( !coupledItem )
594 return false;
595
596 LINE ln = m_world->AssembleLine( coupledItem );
597
598 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
599 std::swap( lp, ln );
600
601 int gap = -1;
602
603 if( refItem && refItem->Kind() == ITEM::SEGMENT_T )
604 {
605 // Segments are parallel -> compute pair gap
606 const VECTOR2I refDir = refItem->Anchor( 1 ) - refItem->Anchor( 0 );
607 const VECTOR2I displacement = refItem->Anchor( 1 ) - coupledItem->Anchor( 1 );
608 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
609 }
610 else if( refItem && refItem->Kind() == ITEM::ARC_T )
611 {
612 const ARC* refArc = static_cast<ARC*>( refItem );
613 const ARC* coupledArc = static_cast<ARC*>( coupledItem );
614 gap = (int) std::abs( refArc->CArc().GetRadius() - coupledArc->CArc().GetRadius() ) - lp.Width();
615 }
616
617 aPair = DIFF_PAIR( lp, ln );
618 aPair.SetWidth( lp.Width() );
619 aPair.SetLayers( lp.Layers() );
620 aPair.SetGap( gap );
621
622 return true;
623}
624
625const TOPOLOGY::CLUSTER TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer, double aAreaExpansionLimit, NET_HANDLE aExcludedNet )
626{
627 CLUSTER cluster;
628 std::deque<ITEM*> pending;
629
631
632 opts.m_differentNetsOnly = false;
633 opts.m_overrideClearance = 0;
634
635 pending.push_back( aStart );
636
637 BOX2I clusterBBox = aStart->Shape( aLayer )->BBox();
638 int64_t initialArea = clusterBBox.GetArea();
639
640 while( !pending.empty() )
641 {
642 NODE::OBSTACLES obstacles;
643 ITEM* top = pending.front();
644
645 pending.pop_front();
646
647 cluster.m_items.insert( top );
648
649 m_world->QueryColliding( top, obstacles, opts ); // only query touching objects
650
651 for( const OBSTACLE& obs : obstacles )
652 {
653 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
654
655 if( trackOnTrack )
656 continue;
657
658 if( aExcludedNet && obs.m_item->Net() == aExcludedNet )
659 continue;
660
661 if( obs.m_item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && obs.m_item->Layers().Overlaps( aLayer ) )
662 {
663 auto line = m_world->AssembleLine( static_cast<LINKED_ITEM*>(obs.m_item) );
664 clusterBBox.Merge( line.CLine().BBox() );
665 }
666 else
667 {
668 clusterBBox.Merge( obs.m_item->Shape( aLayer )->BBox() );
669 }
670
671 const int64_t currentArea = clusterBBox.GetArea();
672 const double areaRatio = (double) currentArea / (double) ( initialArea + 1 );
673
674 if( aAreaExpansionLimit > 0.0 && areaRatio > aAreaExpansionLimit )
675 break;
676
677 if( cluster.m_items.find( obs.m_item ) == cluster.m_items.end() &&
678 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
679 {
680 cluster.m_items.insert( obs.m_item );
681 pending.push_back( obs.m_item );
682 }
683 }
684 }
685
686 return cluster;
687}
688
689}
@ ERROR_INSIDE
Definition: approximation.h:34
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:79
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:658
constexpr ecoord_type GetArea() const
Return the area of the rectangle.
Definition: box2.h:761
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:101
Definition: pad.h:54
int Width() const override
Definition: pns_arc.h:88
const SHAPE_ARC & CArc() const
Definition: pns_arc.h:116
Basic class for a differential pair.
void SetGap(int aGap)
void SetWidth(int aWidth)
int Size() const
Definition: pns_itemset.h:112
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:33
void Prepend(const LINE &aLine)
Definition: pns_itemset.cpp:41
Base class for PNS router board items.
Definition: pns_item.h:97
void SetLayers(const PNS_LAYER_RANGE &aLayers)
Definition: pns_item.h:200
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
Definition: pns_item.h:229
const PNS_LAYER_RANGE & Layers() const
Definition: pns_item.h:199
virtual NET_HANDLE Net() const
Definition: pns_item.h:197
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:170
virtual int Layer() const
Definition: pns_item.h:203
@ SEGMENT_T
Definition: pns_item.h:106
bool OfKind(int aKindMask) const
Definition: pns_item.h:178
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:255
virtual int AnchorCount() const
Definition: pns_item.h:260
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:43
const std::vector< ITEM * > & LinkList() const
Definition: pns_joint.h:303
NET_HANDLE Net() const override
Definition: pns_joint.h:298
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:318
bool IsNonFanoutVia() const
Definition: pns_joint.h:149
bool IsTraceWidthChange() const
Link the joint to a given board item (when it's added to the NODE).
Definition: pns_joint.h:183
const ITEM_SET & CLinks() const
Definition: pns_joint.h:308
const VECTOR2I & Pos() const
Definition: pns_joint.h:293
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:62
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:146
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:127
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:138
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:137
int SegmentCount() const
Definition: pns_line.h:140
int PointCount() const
Definition: pns_line.h:141
bool EndsWithVia() const
Definition: pns_line.h:190
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:1074
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:157
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:143
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.
Definition: pns_node.cpp:1242
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:269
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:665
std::set< OBSTACLE > OBSTACLES
Definition: pns_node.h:243
void AllItemsInNet(NET_HANDLE aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1529
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.
Definition: pns_node.cpp:255
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:906
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.
Definition: pns_node.cpp:1044
virtual int NetCode(NET_HANDLE aNet)=0
virtual NET_HANDLE DpCoupledNet(NET_HANDLE aNet)=0
virtual int DpNetPolarity(NET_HANDLE aNet)=0
const SEG & Seg() const
Definition: pns_segment.h:90
int Width() const override
Definition: pns_segment.h:85
ITEM * NearestUnconnectedItem(const JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
std::set< const JOINT * > JOINT_SET
Definition: pns_topology.h:49
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 int DP_PARALLELITY_THRESHOLD
Definition: pns_topology.h:103
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)
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.
Definition: pns_layerset.h:32
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
VECTOR2I::extended_type ecoord
Definition: seg.h:44
VECTOR2I B
Definition: seg.h:50
static SEG::ecoord Square(int a)
Definition: seg.h:123
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:489
double GetRadius() const
Definition: shape_arc.cpp:554
const VECTOR2I & GetCenter() const
Definition: shape_arc.cpp:523
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.
Definition: shape.h:232
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.
Definition: vector2d.h:542
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:307
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:283
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:60
Push and Shove diff pair dimensions (gap) settings dialog.
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
void * NET_HANDLE
Definition: pns_item.h:54
@ MK_HEAD
Definition: pns_item.h:42
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:390
CITER next(CITER it)
Definition: ptree.cpp:126
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:87
std::set< ITEM * > m_items
Definition: pns_topology.h:46
constexpr int delta
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87