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 The 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>
36#include <pad.h>
37
38namespace PNS {
39
41{
42 if( !aLine->IsLinked() || !aLine->SegmentCount() )
43 return false;
44
45 LINKED_ITEM* root = aLine->GetLink( 0 );
46 LINE l = m_world->AssembleLine( root, nullptr, false, false, false );
47 SHAPE_LINE_CHAIN simplified( l.CLine() );
48
49 simplified.Simplify();
50
51 if( simplified.PointCount() != l.PointCount() )
52 {
53 m_world->Remove( l );
54 LINE lnew( l );
55 lnew.SetShape( simplified );
56 m_world->Add( lnew );
57 return true;
58 }
59
60 return false;
61}
62
63
65{
66 std::deque<const JOINT*> searchQueue;
67 JOINT_SET processed;
68
69 searchQueue.push_back( aStart );
70 processed.insert( aStart );
71
72 while( !searchQueue.empty() )
73 {
74 const JOINT* current = searchQueue.front();
75 searchQueue.pop_front();
76
77 for( ITEM* item : current->LinkList() )
78 {
79 if( item->OfKind( ITEM::SEGMENT_T ) )
80 {
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;
84
85 if( processed.find( next ) == processed.end() )
86 {
87 processed.insert( next );
88 searchQueue.push_back( next );
89 }
90 }
91 }
92 }
93
94 return processed;
95}
96
97
99 PNS_LAYER_RANGE& aLayers, ITEM*& aItem )
100{
101 LINE track( *aTrack );
103
104 if( !track.PointCount() )
105 return false;
106
107 std::unique_ptr<NODE> tmpNode( m_world->Branch() );
108
109 track.ClearLinks();
110 tmpNode->Add( track );
111
112 const JOINT* jt = tmpNode->FindJoint( track.CLastPoint(), &track );
113
114 if( !jt || m_world->GetRuleResolver()->NetCode( jt->Net() ) <= 0 )
115 return false;
116
117 if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 )
118 || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
119 {
120 end = jt->Pos();
121 aLayers = jt->Layers();
122 aItem = jt->LinkList()[0];
123 }
124 else
125 {
126 int anchor;
127
128 TOPOLOGY topo( tmpNode.get() );
129 ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
130
131 if( !it )
132 return false;
133
134 end = it->Anchor( anchor );
135 aLayers = it->Layers();
136 aItem = it;
137 }
138
139 aPoint = end;
140 return true;
141}
142
143
144bool TOPOLOGY::LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine )
145{
147 // Ratline doesn't care about the layer
148 PNS_LAYER_RANGE layers;
149 ITEM* unusedItem;
150
151 if( !NearestUnconnectedAnchorPoint( aTrack, end, layers, unusedItem ) )
152 return false;
153
154 aRatLine.Clear();
155 aRatLine.Append( aTrack->CLastPoint() );
156 aRatLine.Append( end );
157 return true;
158}
159
160
161ITEM* TOPOLOGY::NearestUnconnectedItem( const JOINT* aStart, int* aAnchor, int aKindMask )
162{
163 std::set<ITEM*> disconnected;
164
165 m_world->AllItemsInNet( aStart->Net(), disconnected );
166
167 for( const JOINT* jt : ConnectedJoints( aStart ) )
168 {
169 for( ITEM* link : jt->LinkList() )
170 {
171 if( disconnected.find( link ) != disconnected.end() )
172 disconnected.erase( link );
173 }
174 }
175
176 int best_dist = INT_MAX;
177 ITEM* best = nullptr;
178
179 for( ITEM* item : disconnected )
180 {
181 if( item->OfKind( aKindMask ) )
182 {
183 for( int i = 0; i < item->AnchorCount(); i++ )
184 {
185 VECTOR2I p = item->Anchor( i );
186 int d = ( p - aStart->Pos() ).EuclideanNorm();
187
188 if( d < best_dist )
189 {
190 best_dist = d;
191 best = item;
192
193 if( aAnchor )
194 *aAnchor = i;
195 }
196 }
197 }
198 }
199
200 return best;
201}
202
203
204bool TOPOLOGY::followTrivialPath( LINE* aLine2, bool aLeft, ITEM_SET& aSet,
205 const JOINT** aTerminalJoint, bool aFollowLockedSegments )
206{
207 assert( aLine2->IsLinked() );
208 LINE* curr_line = aLine2;
209 std::set<ITEM*> visited;
210
211 while( true )
212 {
213 VECTOR2I anchor = aLeft ? curr_line->CPoint( 0 ) : curr_line->CLastPoint();
214 LINKED_ITEM* last = aLeft ? curr_line->Links().front() : curr_line->Links().back();
215 const JOINT* jt = m_world->FindJoint( anchor, curr_line );
216
217 assert( jt != nullptr );
218
219 if( !visited.insert( last ).second
220 || ( !jt->IsNonFanoutVia() && !jt->IsTraceWidthChange() ) )
221 {
222 if( aTerminalJoint )
223 *aTerminalJoint = jt;
224
225 return false;
226 }
227
228 ITEM* via = nullptr;
229 SEGMENT* next_seg = nullptr;
230
231 ITEM_SET links( jt->CLinks() );
232
233 for( ITEM* link : links )
234 {
235 if( link->OfKind( ITEM::VIA_T ) )
236 via = link;
237 else if( !visited.contains( link ) )
238 next_seg = static_cast<SEGMENT*>( link );
239 }
240
241 if( !next_seg )
242 {
243 if( aTerminalJoint )
244 *aTerminalJoint = jt;
245
246 return false;
247 }
248
249 LINE l = m_world->AssembleLine( next_seg, nullptr, false, aFollowLockedSegments );
250 VECTOR2I nextAnchor = ( aLeft ? l.CLine().CLastPoint() : l.CLine().CPoint( 0 ) );
251
252 if( nextAnchor != anchor )
253 {
254 l.Reverse();
255 }
256
257 if( aLeft )
258 {
259 if( via )
260 aSet.Prepend( via );
261
262 aSet.Prepend( l );
263 curr_line = static_cast<PNS::LINE*>( aSet[0] );
264 }
265 else
266 {
267 if( via )
268 aSet.Add( via );
269
270 aSet.Add( l );
271 curr_line = static_cast<PNS::LINE*>( aSet[aSet.Size() - 1] );
272 }
273
274 continue;
275 }
276}
277
278
280 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
281 bool aFollowLockedSegments )
282{
284 LINKED_ITEM* seg = nullptr;
285
286 if( aStart->Kind() == ITEM::VIA_T )
287 {
288 VIA* via = static_cast<VIA*>( aStart );
289 const JOINT* jt = m_world->FindJoint( via->Pos(), via );
290
291 if( !jt->IsNonFanoutVia() )
292 return ITEM_SET();
293
294 ITEM_SET links( jt->CLinks() );
295
296 for( ITEM* item : links )
297 {
298 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
299 {
300 seg = static_cast<LINKED_ITEM*>( item );
301 break;
302 }
303 }
304 }
305 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
306 {
307 seg = static_cast<LINKED_ITEM*>( aStart );
308 }
309
310 if( !seg )
311 return ITEM_SET();
312
313 // Assemble a line following through locked segments
314 // TODO: consider if we want to allow tuning lines with different widths in the future
315 LINE l = m_world->AssembleLine( seg, nullptr, false, aFollowLockedSegments );
316
317 path.Add( l );
318
319 const JOINT* jointA = nullptr;
320 const JOINT* jointB = nullptr;
321
322 followTrivialPath( &l, false, path, &jointB, aFollowLockedSegments );
323 followTrivialPath( &l, true, path, &jointA, aFollowLockedSegments );
324
325 if( aTerminalJoints )
326 {
327 wxASSERT( jointA && jointB );
328 *aTerminalJoints = std::make_pair( jointA, jointB );
329 }
330
331 return path;
332}
333
334
335const ITEM_SET TOPOLOGY::AssembleTuningPath( ROUTER_IFACE* aRouterIface, ITEM* aStart, SOLID** aStartPad,
336 SOLID** aEndPad )
337{
338 std::pair<const JOINT*, const JOINT*> joints;
339 ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints, true );
340
341 PAD* padA = nullptr;
342 PAD* padB = nullptr;
343
344 auto getPadFromJoint =
345 []( const JOINT* aJoint, PAD** aTargetPad, SOLID** aTargetSolid )
346 {
347 for( ITEM* item : aJoint->LinkList() )
348 {
349 if( item->OfKind( ITEM::SOLID_T ) )
350 {
351 BOARD_ITEM* bi = static_cast<SOLID*>( item )->Parent();
352
353 if( bi->Type() == PCB_PAD_T )
354 {
355 *aTargetPad = static_cast<PAD*>( bi );
356
357 if( aTargetSolid )
358 *aTargetSolid = static_cast<SOLID*>( item );
359 }
360
361 break;
362 }
363 }
364 };
365
366 if( joints.first )
367 getPadFromJoint( joints.first, &padA, aStartPad );
368
369 if( joints.second )
370 getPadFromJoint( joints.second, &padB, aEndPad );
371
372 if( !padA && !padB )
373 return initialPath;
374
375 auto processPad = [&]( PAD* aPad, int aLayer )
376 {
377 for( int idx = 0; idx < initialPath.Size(); idx++ )
378 {
379 if( initialPath[idx]->Kind() != ITEM::LINE_T )
380 continue;
381
382 LINE* line = static_cast<LINE*>( initialPath[idx] );
383 SHAPE_LINE_CHAIN& slc = line->Line();
384 const PCB_LAYER_ID pcbLayer = aRouterIface->GetBoardLayerFromPNSLayer( line->Layer() );
385
387 }
388 };
389
390 if( padA )
391 processPad( padA, joints.first->Layer() );
392
393 if( padB )
394 processPad( padB, joints.second->Layer() );
395
396 return initialPath;
397}
398
399
400const ITEM_SET TOPOLOGY::ConnectedItems( const JOINT* aStart, int aKindMask )
401{
402 return ITEM_SET();
403}
404
405
406const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
407{
408 return ITEM_SET();
409}
410
411
412bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
413
414
416{
417 NET_HANDLE refNet = aStart->Net();
418 NET_HANDLE coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
419 LINKED_ITEM* startItem = dynamic_cast<LINKED_ITEM*>( aStart );
420
421 if( !coupledNet || !startItem )
422 return false;
423
424 LINE lp = m_world->AssembleLine( startItem );
425
426 std::vector<ITEM*> pItems;
427 std::vector<ITEM*> nItems;
428
429 for( ITEM* item : lp.Links() )
430 {
431 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
432 pItems.push_back( item );
433 }
434
435 std::set<ITEM*> coupledItems;
436 m_world->AllItemsInNet( coupledNet, coupledItems );
437
438 for( ITEM* item : coupledItems )
439 {
440 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
441 nItems.push_back( item );
442 }
443
444 LINKED_ITEM* refItem = nullptr;
445 LINKED_ITEM* coupledItem = nullptr;
446 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
447 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
448 VECTOR2I targetPoint = aStart->Shape( -1 )->Centre();
449
450 auto findNItem = [&]( ITEM* p_item )
451 {
452 for( ITEM* n_item : nItems )
453 {
454 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
455
456 if( n_item->Kind() != p_item->Kind() )
457 continue;
458
459 if( p_item->Kind() == ITEM::SEGMENT_T )
460 {
461 const SEGMENT* p_seg = static_cast<const SEGMENT*>( p_item );
462 const SEGMENT* n_seg = static_cast<const SEGMENT*>( n_item );
463
464 if( n_seg->Width() != p_seg->Width() )
465 continue;
466
467 if( !p_seg->Seg().ApproxParallel( n_seg->Seg(), DP_PARALLELITY_THRESHOLD ) )
468 continue;
469
470 SEG p_clip, n_clip;
471
472 if( !commonParallelProjection( p_seg->Seg(), n_seg->Seg(), p_clip, n_clip ) )
473 continue;
474
475 dist_sq = n_seg->Seg().SquaredDistance( p_seg->Seg() );
476 }
477 else if( p_item->Kind() == ITEM::ARC_T )
478 {
479 const ARC* p_arc = static_cast<const ARC*>( p_item );
480 const ARC* n_arc = static_cast<const ARC*>( n_item );
481
482 if( n_arc->Width() != p_arc->Width() )
483 continue;
484
485 VECTOR2I centerDiff = n_arc->CArc().GetCenter() - p_arc->CArc().GetCenter();
486 SEG::ecoord centerDist_sq = centerDiff.SquaredEuclideanNorm();
487
488 if( centerDist_sq > SEG::Square( DP_PARALLELITY_THRESHOLD ) )
489 continue;
490
491 dist_sq = SEG::Square( p_arc->CArc().GetRadius() - n_arc->CArc().GetRadius() );
492 }
493
494 if( dist_sq <= minDist_sq )
495 {
496 SEG::ecoord distTarget_sq = n_item->Shape( -1 )->SquaredDistance( targetPoint );
497 if( distTarget_sq < minDistTarget_sq )
498 {
499 minDistTarget_sq = distTarget_sq;
500 minDist_sq = dist_sq;
501
502 refItem = static_cast<LINKED_ITEM*>( p_item );
503 coupledItem = static_cast<LINKED_ITEM*>( n_item );
504 }
505 }
506 }
507 };
508
509 findNItem( startItem );
510
511 if( !coupledItem )
512 {
513 LINKED_ITEM* linked = static_cast<LINKED_ITEM*>( startItem );
514 std::set<ITEM*> linksToTest;
515
516 for( int i = 0; i < linked->AnchorCount(); i++ )
517 {
518 const JOINT* jt = m_world->FindJoint( linked->Anchor( i ), linked );
519
520 if( !jt )
521 continue;
522
523 for( ITEM* link : jt->LinkList() )
524 {
525 if( link != linked )
526 linksToTest.emplace( link );
527 }
528 }
529
530 for( ITEM* link : linksToTest )
531 findNItem( link );
532 }
533
534 if( !coupledItem )
535 return false;
536
537 LINE ln = m_world->AssembleLine( coupledItem );
538
539 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
540 std::swap( lp, ln );
541
542 int gap = -1;
543
544 if( refItem && refItem->Kind() == ITEM::SEGMENT_T )
545 {
546 // Segments are parallel -> compute pair gap
547 const VECTOR2I refDir = refItem->Anchor( 1 ) - refItem->Anchor( 0 );
548 const VECTOR2I displacement = refItem->Anchor( 1 ) - coupledItem->Anchor( 1 );
549 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
550 }
551 else if( refItem && refItem->Kind() == ITEM::ARC_T )
552 {
553 const ARC* refArc = static_cast<ARC*>( refItem );
554 const ARC* coupledArc = static_cast<ARC*>( coupledItem );
555 gap = (int) std::abs( refArc->CArc().GetRadius() - coupledArc->CArc().GetRadius() ) - lp.Width();
556 }
557
558 aPair = DIFF_PAIR( lp, ln );
559 aPair.SetWidth( lp.Width() );
560 aPair.SetLayers( lp.Layers() );
561 aPair.SetGap( gap );
562
563 return true;
564}
565
566const TOPOLOGY::CLUSTER TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer, double aAreaExpansionLimit, NET_HANDLE aExcludedNet )
567{
568 CLUSTER cluster;
569 std::deque<ITEM*> pending;
570
572
573 opts.m_differentNetsOnly = false;
574 opts.m_overrideClearance = 0;
575
576 pending.push_back( aStart );
577
578 BOX2I clusterBBox = aStart->Shape( aLayer )->BBox();
579 int64_t initialArea = clusterBBox.GetArea();
580
581 while( !pending.empty() )
582 {
583 NODE::OBSTACLES obstacles;
584 ITEM* top = pending.front();
585
586 pending.pop_front();
587
588 cluster.m_items.insert( top );
589
590 m_world->QueryColliding( top, obstacles, opts ); // only query touching objects
591
592 for( const OBSTACLE& obs : obstacles )
593 {
594 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
595
596 if( trackOnTrack )
597 continue;
598
599 if( aExcludedNet && obs.m_item->Net() == aExcludedNet )
600 continue;
601
602 if( obs.m_item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && obs.m_item->Layers().Overlaps( aLayer ) )
603 {
604 auto line = m_world->AssembleLine( static_cast<LINKED_ITEM*>(obs.m_item) );
605 clusterBBox.Merge( line.CLine().BBox() );
606 }
607 else
608 {
609 clusterBBox.Merge( obs.m_item->Shape( aLayer )->BBox() );
610 }
611
612 const int64_t currentArea = clusterBBox.GetArea();
613 const double areaRatio = (double) currentArea / (double) ( initialArea + 1 );
614
615 if( aAreaExpansionLimit > 0.0 && areaRatio > aAreaExpansionLimit )
616 break;
617
618 if( cluster.m_items.find( obs.m_item ) == cluster.m_items.end() &&
619 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
620 {
621 cluster.m_items.insert( obs.m_item );
622 pending.push_back( obs.m_item );
623 }
624 }
625 }
626
627 return cluster;
628}
629
630}
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:110
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.
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:98
void SetLayers(const PNS_LAYER_RANGE &aLayers)
Definition: pns_item.h:213
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
Definition: pns_item.h:242
const PNS_LAYER_RANGE & Layers() const
Definition: pns_item.h:212
virtual NET_HANDLE Net() const
Definition: pns_item.h:210
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:173
virtual int Layer() const
Definition: pns_item.h:216
@ SEGMENT_T
Definition: pns_item.h:107
bool OfKind(int aKindMask) const
Definition: pns_item.h:181
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:268
virtual int AnchorCount() const
Definition: pns_item.h:273
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
const VECTOR2I & CLastPoint() const
Definition: pns_line.h:147
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:191
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:1077
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:158
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:1268
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:270
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:244
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false, bool aAllowSegmentSizeMismatch=true)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:1047
void AllItemsInNet(NET_HANDLE aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1555
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:909
virtual PCB_LAYER_ID GetBoardLayerFromPNSLayer(int aLayer) const =0
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:93
int Width() const override
Definition: pns_segment.h:88
ITEM * NearestUnconnectedItem(const JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
std::set< const JOINT * > JOINT_SET
Definition: pns_topology.h:50
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 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
Definition: pns_topology.h:104
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.
Definition: pns_layerset.h:32
Definition: seg.h:42
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:80
VECTOR2I::extended_type ecoord
Definition: seg.h:44
static SEG::ecoord Square(int a)
Definition: seg.h:123
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:780
double GetRadius() const
Definition: shape_arc.cpp:894
const VECTOR2I & GetCenter() const
Definition: shape_arc.cpp:849
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.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
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:546
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:55
@ MK_HEAD
Definition: pns_item.h:43
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:400
CITER next(CITER it)
Definition: ptree.cpp:124
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:88
std::set< ITEM * > m_items
Definition: pns_topology.h:47
VECTOR2I end
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87