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>
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 );
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{
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.contains( link ) )
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( ROUTER_IFACE* aRouterIface, ITEM* aStart, SOLID** aStartPad,
335 SOLID** aEndPad )
336{
337 std::pair<const JOINT*, const JOINT*> joints;
338 ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints, true );
339
340 PAD* padA = nullptr;
341 PAD* padB = nullptr;
342
343 auto getPadFromJoint =
344 []( const JOINT* aJoint, PAD** aTargetPad, SOLID** aTargetSolid )
345 {
346 for( ITEM* item : aJoint->LinkList() )
347 {
348 if( item->OfKind( ITEM::SOLID_T ) )
349 {
350 BOARD_ITEM* bi = static_cast<SOLID*>( item )->Parent();
351
352 if( bi->Type() == PCB_PAD_T )
353 {
354 *aTargetPad = static_cast<PAD*>( bi );
355
356 if( aTargetSolid )
357 *aTargetSolid = static_cast<SOLID*>( item );
358 }
359
360 break;
361 }
362 }
363 };
364
365 if( joints.first )
366 getPadFromJoint( joints.first, &padA, aStartPad );
367
368 if( joints.second )
369 getPadFromJoint( joints.second, &padB, aEndPad );
370
371 if( !padA && !padB )
372 return initialPath;
373
374 auto processPad = [&]( PAD* aPad, int aLayer )
375 {
376 for( int idx = 0; idx < initialPath.Size(); idx++ )
377 {
378 if( initialPath[idx]->Kind() != ITEM::LINE_T )
379 continue;
380
381 LINE* line = static_cast<LINE*>( initialPath[idx] );
382 SHAPE_LINE_CHAIN& slc = line->Line();
383 const PCB_LAYER_ID pcbLayer = aRouterIface->GetBoardLayerFromPNSLayer( line->Layer() );
384
386 }
387 };
388
389 if( padA )
390 processPad( padA, joints.first->Layer() );
391
392 if( padB )
393 processPad( padB, joints.second->Layer() );
394
395 return initialPath;
396}
397
398
399const ITEM_SET TOPOLOGY::ConnectedItems( const JOINT* aStart, int aKindMask )
400{
401 return ITEM_SET();
402}
403
404
405const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
406{
407 return ITEM_SET();
408}
409
410
411bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
412
413
415{
416 NET_HANDLE refNet = aStart->Net();
417 NET_HANDLE coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
418 LINKED_ITEM* startItem = dynamic_cast<LINKED_ITEM*>( aStart );
419
420 if( !coupledNet || !startItem )
421 return false;
422
423 LINE lp = m_world->AssembleLine( startItem );
424
425 std::vector<ITEM*> pItems;
426 std::vector<ITEM*> nItems;
427
428 for( ITEM* item : lp.Links() )
429 {
430 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
431 pItems.push_back( item );
432 }
433
434 std::set<ITEM*> coupledItems;
435 m_world->AllItemsInNet( coupledNet, coupledItems );
436
437 for( ITEM* item : coupledItems )
438 {
439 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
440 nItems.push_back( item );
441 }
442
443 LINKED_ITEM* refItem = nullptr;
444 LINKED_ITEM* coupledItem = nullptr;
445 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
446 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
447 VECTOR2I targetPoint = aStart->Shape( -1 )->Centre();
448
449 auto findNItem = [&]( ITEM* p_item )
450 {
451 for( ITEM* n_item : nItems )
452 {
453 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
454
455 if( n_item->Kind() != p_item->Kind() )
456 continue;
457
458 if( p_item->Kind() == ITEM::SEGMENT_T )
459 {
460 const SEGMENT* p_seg = static_cast<const SEGMENT*>( p_item );
461 const SEGMENT* n_seg = static_cast<const SEGMENT*>( n_item );
462
463 if( n_seg->Width() != p_seg->Width() )
464 continue;
465
466 if( !p_seg->Seg().ApproxParallel( n_seg->Seg(), DP_PARALLELITY_THRESHOLD ) )
467 continue;
468
469 SEG p_clip, n_clip;
470
471 if( !commonParallelProjection( p_seg->Seg(), n_seg->Seg(), p_clip, n_clip ) )
472 continue;
473
474 dist_sq = n_seg->Seg().SquaredDistance( p_seg->Seg() );
475 }
476 else if( p_item->Kind() == ITEM::ARC_T )
477 {
478 const ARC* p_arc = static_cast<const ARC*>( p_item );
479 const ARC* n_arc = static_cast<const ARC*>( n_item );
480
481 if( n_arc->Width() != p_arc->Width() )
482 continue;
483
484 VECTOR2I centerDiff = n_arc->CArc().GetCenter() - p_arc->CArc().GetCenter();
485 SEG::ecoord centerDist_sq = centerDiff.SquaredEuclideanNorm();
486
487 if( centerDist_sq > SEG::Square( DP_PARALLELITY_THRESHOLD ) )
488 continue;
489
490 dist_sq = SEG::Square( p_arc->CArc().GetRadius() - n_arc->CArc().GetRadius() );
491 }
492
493 if( dist_sq <= minDist_sq )
494 {
495 SEG::ecoord distTarget_sq = n_item->Shape( -1 )->SquaredDistance( targetPoint );
496 if( distTarget_sq < minDistTarget_sq )
497 {
498 minDistTarget_sq = distTarget_sq;
499 minDist_sq = dist_sq;
500
501 refItem = static_cast<LINKED_ITEM*>( p_item );
502 coupledItem = static_cast<LINKED_ITEM*>( n_item );
503 }
504 }
505 }
506 };
507
508 findNItem( startItem );
509
510 if( !coupledItem )
511 {
512 LINKED_ITEM* linked = static_cast<LINKED_ITEM*>( startItem );
513 std::set<ITEM*> linksToTest;
514
515 for( int i = 0; i < linked->AnchorCount(); i++ )
516 {
517 const JOINT* jt = m_world->FindJoint( linked->Anchor( i ), linked );
518
519 if( !jt )
520 continue;
521
522 for( ITEM* link : jt->LinkList() )
523 {
524 if( link != linked )
525 linksToTest.emplace( link );
526 }
527 }
528
529 for( ITEM* link : linksToTest )
530 findNItem( link );
531 }
532
533 if( !coupledItem )
534 return false;
535
536 LINE ln = m_world->AssembleLine( coupledItem );
537
538 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
539 std::swap( lp, ln );
540
541 int gap = -1;
542
543 if( refItem && refItem->Kind() == ITEM::SEGMENT_T )
544 {
545 // Segments are parallel -> compute pair gap
546 const VECTOR2I refDir = refItem->Anchor( 1 ) - refItem->Anchor( 0 );
547 const VECTOR2I displacement = refItem->Anchor( 1 ) - coupledItem->Anchor( 1 );
548 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
549 }
550 else if( refItem && refItem->Kind() == ITEM::ARC_T )
551 {
552 const ARC* refArc = static_cast<ARC*>( refItem );
553 const ARC* coupledArc = static_cast<ARC*>( coupledItem );
554 gap = (int) std::abs( refArc->CArc().GetRadius() - coupledArc->CArc().GetRadius() ) - lp.Width();
555 }
556
557 aPair = DIFF_PAIR( lp, ln );
558 aPair.SetWidth( lp.Width() );
559 aPair.SetLayers( lp.Layers() );
560 aPair.SetGap( gap );
561
562 return true;
563}
564
565const TOPOLOGY::CLUSTER TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer, double aAreaExpansionLimit, NET_HANDLE aExcludedNet )
566{
567 CLUSTER cluster;
568 std::deque<ITEM*> pending;
569
571
572 opts.m_differentNetsOnly = false;
573 opts.m_overrideClearance = 0;
574
575 pending.push_back( aStart );
576
577 BOX2I clusterBBox = aStart->Shape( aLayer )->BBox();
578 int64_t initialArea = clusterBBox.GetArea();
579
580 while( !pending.empty() )
581 {
582 NODE::OBSTACLES obstacles;
583 ITEM* top = pending.front();
584
585 pending.pop_front();
586
587 cluster.m_items.insert( top );
588
589 m_world->QueryColliding( top, obstacles, opts ); // only query touching objects
590
591 for( const OBSTACLE& obs : obstacles )
592 {
593 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
594
595 if( trackOnTrack )
596 continue;
597
598 if( aExcludedNet && obs.m_item->Net() == aExcludedNet )
599 continue;
600
601 if( obs.m_item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && obs.m_item->Layers().Overlaps( aLayer ) )
602 {
603 auto line = m_world->AssembleLine( static_cast<LINKED_ITEM*>(obs.m_item) );
604 clusterBBox.Merge( line.CLine().BBox() );
605 }
606 else
607 {
608 clusterBBox.Merge( obs.m_item->Shape( aLayer )->BBox() );
609 }
610
611 const int64_t currentArea = clusterBBox.GetArea();
612 const double areaRatio = (double) currentArea / (double) ( initialArea + 1 );
613
614 if( aAreaExpansionLimit > 0.0 && areaRatio > aAreaExpansionLimit )
615 break;
616
617 if( cluster.m_items.find( obs.m_item ) == cluster.m_items.end() &&
618 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
619 {
620 cluster.m_items.insert( obs.m_item );
621 pending.push_back( obs.m_item );
622 }
623 }
624 }
625
626 return cluster;
627}
628
629}
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:109
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
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:1078
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: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:550
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.
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:393
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