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
205 std::set<ITEM*>& aVisited,
206 bool aFollowLockedSegments )
207{
208 PATH_RESULT best;
209
210 ITEM* via = nullptr;
211 ITEM_SET links( aJoint->CLinks() );
212
213 for( ITEM* link : links )
214 {
215 if( link->OfKind( ITEM::VIA_T ) && !aVisited.contains( link ) )
216 via = link;
217 }
218
219 for( ITEM* link : links )
220 {
221 if( link->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T )
222 && link != aPrev && !aVisited.contains( link ) )
223 {
224 LINE l = m_world->AssembleLine( static_cast<LINKED_ITEM*>( link ), nullptr,
225 false, aFollowLockedSegments );
226
227 if( l.CPoint( 0 ) != aJoint->Pos() )
228 l.Reverse();
229
230 const JOINT* next = m_world->FindJoint( l.CLastPoint(), &l );
231
232 for( LINKED_ITEM* ll : l.Links() )
233 aVisited.insert( ll );
234
235 if( via )
236 aVisited.insert( via );
237
238 PATH_RESULT sub = followBranch( next, l.Links().back(), aVisited, aFollowLockedSegments );
239
240 ITEM_SET tmp;
241 if( via )
242 tmp.Add( via );
243 tmp.Add( l );
244 for( ITEM* it : sub.m_items )
245 tmp.Add( it );
246
247 int len = l.CLine().Length() + sub.m_length;
248
249 if( len > best.m_length )
250 {
251 best.m_length = len;
252 best.m_end = sub.m_end;
253 best.m_items = tmp;
254 }
255
256 for( LINKED_ITEM* ll : l.Links() )
257 aVisited.erase( ll );
258
259 if( via )
260 aVisited.erase( via );
261 }
262 }
263
264 if( !best.m_end )
265 best.m_end = aJoint;
266
267 return best;
268}
269
270
271ITEM_SET TOPOLOGY::followTrivialPath( LINE* aLine2, const JOINT** aTerminalJointA,
272 const JOINT** aTerminalJointB,
273 bool aFollowLockedSegments )
274{
275 assert( aLine2->IsLinked() );
276
278 path.Add( *aLine2 );
279
280 std::set<ITEM*> visited;
281
282 for( LINKED_ITEM* link : aLine2->Links() )
283 visited.insert( link );
284
285 const JOINT* jtA = m_world->FindJoint( aLine2->CPoint( 0 ), aLine2 );
286 const JOINT* jtB = m_world->FindJoint( aLine2->CLastPoint(), aLine2 );
287
288 PATH_RESULT left = followBranch( jtA, aLine2->Links().front(), visited, aFollowLockedSegments );
289 PATH_RESULT right = followBranch( jtB, aLine2->Links().back(), visited, aFollowLockedSegments );
290
291 if( aTerminalJointA )
292 *aTerminalJointA = left.m_end;
293
294 if( aTerminalJointB )
295 *aTerminalJointB = right.m_end;
296
297 for( int i = left.m_items.Size() - 1; i >= 0; i-- )
298 path.Prepend( left.m_items[i] );
299
300 for( ITEM* item : right.m_items )
301 path.Add( item );
302
303 return path;
304}
305
306
308 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
309 bool aFollowLockedSegments )
310{
312 LINKED_ITEM* seg = nullptr;
313
314 if( aStart->Kind() == ITEM::VIA_T )
315 {
316 VIA* via = static_cast<VIA*>( aStart );
317 const JOINT* jt = m_world->FindJoint( via->Pos(), via );
318
319 if( !jt->IsNonFanoutVia() )
320 return ITEM_SET();
321
322 ITEM_SET links( jt->CLinks() );
323
324 for( ITEM* item : links )
325 {
326 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
327 {
328 seg = static_cast<LINKED_ITEM*>( item );
329 break;
330 }
331 }
332 }
333 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
334 {
335 seg = static_cast<LINKED_ITEM*>( aStart );
336 }
337
338 if( !seg )
339 return ITEM_SET();
340
341 // Assemble a line following through locked segments
342 // TODO: consider if we want to allow tuning lines with different widths in the future
343 LINE l = m_world->AssembleLine( seg, nullptr, false, aFollowLockedSegments );
344
345 const JOINT* jointA = nullptr;
346 const JOINT* jointB = nullptr;
347
348 path = followTrivialPath( &l, &jointA, &jointB, aFollowLockedSegments );
349
350 if( aTerminalJoints )
351 {
352 wxASSERT( jointA && jointB );
353 *aTerminalJoints = std::make_pair( jointA, jointB );
354 }
355
356 return path;
357}
358
359
360const ITEM_SET TOPOLOGY::AssembleTuningPath( ROUTER_IFACE* aRouterIface, ITEM* aStart, SOLID** aStartPad,
361 SOLID** aEndPad )
362{
363 std::pair<const JOINT*, const JOINT*> joints;
364 ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints, true );
365
366 PAD* padA = nullptr;
367 PAD* padB = nullptr;
368
369 auto getPadFromJoint =
370 []( const JOINT* aJoint, PAD** aTargetPad, SOLID** aTargetSolid )
371 {
372 for( ITEM* item : aJoint->LinkList() )
373 {
374 if( item->OfKind( ITEM::SOLID_T ) )
375 {
376 BOARD_ITEM* bi = static_cast<SOLID*>( item )->Parent();
377
378 if( bi->Type() == PCB_PAD_T )
379 {
380 *aTargetPad = static_cast<PAD*>( bi );
381
382 if( aTargetSolid )
383 *aTargetSolid = static_cast<SOLID*>( item );
384 }
385
386 break;
387 }
388 }
389 };
390
391 if( joints.first )
392 getPadFromJoint( joints.first, &padA, aStartPad );
393
394 if( joints.second )
395 getPadFromJoint( joints.second, &padB, aEndPad );
396
397 if( !padA && !padB )
398 return initialPath;
399
400 auto processPad = [&]( PAD* aPad, int aLayer )
401 {
402 for( int idx = 0; idx < initialPath.Size(); idx++ )
403 {
404 if( initialPath[idx]->Kind() != ITEM::LINE_T )
405 continue;
406
407 LINE* line = static_cast<LINE*>( initialPath[idx] );
408 SHAPE_LINE_CHAIN& slc = line->Line();
409 const PCB_LAYER_ID pcbLayer = aRouterIface->GetBoardLayerFromPNSLayer( line->Layer() );
410
412 }
413 };
414
415 if( padA )
416 processPad( padA, joints.first->Layer() );
417
418 if( padB )
419 processPad( padB, joints.second->Layer() );
420
421 return initialPath;
422}
423
424
425const ITEM_SET TOPOLOGY::ConnectedItems( const JOINT* aStart, int aKindMask )
426{
427 return ITEM_SET();
428}
429
430
431const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
432{
433 return ITEM_SET();
434}
435
436
437bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
438
439
441{
442 NET_HANDLE refNet = aStart->Net();
443 NET_HANDLE coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
444 LINKED_ITEM* startItem = dynamic_cast<LINKED_ITEM*>( aStart );
445
446 if( !coupledNet || !startItem )
447 return false;
448
449 LINE lp = m_world->AssembleLine( startItem );
450
451 std::vector<ITEM*> pItems;
452 std::vector<ITEM*> nItems;
453
454 for( ITEM* item : lp.Links() )
455 {
456 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
457 pItems.push_back( item );
458 }
459
460 std::set<ITEM*> coupledItems;
461 m_world->AllItemsInNet( coupledNet, coupledItems );
462
463 for( ITEM* item : coupledItems )
464 {
465 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
466 nItems.push_back( item );
467 }
468
469 LINKED_ITEM* refItem = nullptr;
470 LINKED_ITEM* coupledItem = nullptr;
471 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
472 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
473 VECTOR2I targetPoint = aStart->Shape( -1 )->Centre();
474
475 auto findNItem = [&]( ITEM* p_item )
476 {
477 for( ITEM* n_item : nItems )
478 {
479 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
480
481 if( n_item->Kind() != p_item->Kind() )
482 continue;
483
484 if( p_item->Kind() == ITEM::SEGMENT_T )
485 {
486 const SEGMENT* p_seg = static_cast<const SEGMENT*>( p_item );
487 const SEGMENT* n_seg = static_cast<const SEGMENT*>( n_item );
488
489 if( n_seg->Width() != p_seg->Width() )
490 continue;
491
492 if( !p_seg->Seg().ApproxParallel( n_seg->Seg(), DP_PARALLELITY_THRESHOLD ) )
493 continue;
494
495 SEG p_clip, n_clip;
496
497 if( !commonParallelProjection( p_seg->Seg(), n_seg->Seg(), p_clip, n_clip ) )
498 continue;
499
500 dist_sq = n_seg->Seg().SquaredDistance( p_seg->Seg() );
501 }
502 else if( p_item->Kind() == ITEM::ARC_T )
503 {
504 const ARC* p_arc = static_cast<const ARC*>( p_item );
505 const ARC* n_arc = static_cast<const ARC*>( n_item );
506
507 if( n_arc->Width() != p_arc->Width() )
508 continue;
509
510 VECTOR2I centerDiff = n_arc->CArc().GetCenter() - p_arc->CArc().GetCenter();
511 SEG::ecoord centerDist_sq = centerDiff.SquaredEuclideanNorm();
512
513 if( centerDist_sq > SEG::Square( DP_PARALLELITY_THRESHOLD ) )
514 continue;
515
516 dist_sq = SEG::Square( p_arc->CArc().GetRadius() - n_arc->CArc().GetRadius() );
517 }
518
519 if( dist_sq <= minDist_sq )
520 {
521 SEG::ecoord distTarget_sq = n_item->Shape( -1 )->SquaredDistance( targetPoint );
522 if( distTarget_sq < minDistTarget_sq )
523 {
524 minDistTarget_sq = distTarget_sq;
525 minDist_sq = dist_sq;
526
527 refItem = static_cast<LINKED_ITEM*>( p_item );
528 coupledItem = static_cast<LINKED_ITEM*>( n_item );
529 }
530 }
531 }
532 };
533
534 findNItem( startItem );
535
536 if( !coupledItem )
537 {
538 LINKED_ITEM* linked = static_cast<LINKED_ITEM*>( startItem );
539 std::set<ITEM*> linksToTest;
540
541 for( int i = 0; i < linked->AnchorCount(); i++ )
542 {
543 const JOINT* jt = m_world->FindJoint( linked->Anchor( i ), linked );
544
545 if( !jt )
546 continue;
547
548 for( ITEM* link : jt->LinkList() )
549 {
550 if( link != linked )
551 linksToTest.emplace( link );
552 }
553 }
554
555 for( ITEM* link : linksToTest )
556 findNItem( link );
557 }
558
559 if( !coupledItem )
560 return false;
561
562 LINE ln = m_world->AssembleLine( coupledItem );
563
564 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
565 std::swap( lp, ln );
566
567 int gap = -1;
568
569 if( refItem && refItem->Kind() == ITEM::SEGMENT_T )
570 {
571 // Segments are parallel -> compute pair gap
572 const VECTOR2I refDir = refItem->Anchor( 1 ) - refItem->Anchor( 0 );
573 const VECTOR2I displacement = refItem->Anchor( 1 ) - coupledItem->Anchor( 1 );
574 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
575 }
576 else if( refItem && refItem->Kind() == ITEM::ARC_T )
577 {
578 const ARC* refArc = static_cast<ARC*>( refItem );
579 const ARC* coupledArc = static_cast<ARC*>( coupledItem );
580 gap = (int) std::abs( refArc->CArc().GetRadius() - coupledArc->CArc().GetRadius() ) - lp.Width();
581 }
582
583 aPair = DIFF_PAIR( lp, ln );
584 aPair.SetWidth( lp.Width() );
585 aPair.SetLayers( lp.Layers() );
586 aPair.SetGap( gap );
587
588 return true;
589}
590
591const TOPOLOGY::CLUSTER TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer, double aAreaExpansionLimit, NET_HANDLE aExcludedNet )
592{
593 CLUSTER cluster;
594 std::deque<ITEM*> pending;
595
597
598 opts.m_differentNetsOnly = false;
599 opts.m_overrideClearance = 0;
600
601 pending.push_back( aStart );
602
603 BOX2I clusterBBox = aStart->Shape( aLayer )->BBox();
604 int64_t initialArea = clusterBBox.GetArea();
605
606 while( !pending.empty() )
607 {
608 NODE::OBSTACLES obstacles;
609 ITEM* top = pending.front();
610
611 pending.pop_front();
612
613 cluster.m_items.insert( top );
614
615 m_world->QueryColliding( top, obstacles, opts ); // only query touching objects
616
617 for( const OBSTACLE& obs : obstacles )
618 {
619 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
620
621 if( trackOnTrack )
622 continue;
623
624 if( aExcludedNet && obs.m_item->Net() == aExcludedNet )
625 continue;
626
627 if( obs.m_item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && obs.m_item->Layers().Overlaps( aLayer ) )
628 {
629 auto line = m_world->AssembleLine( static_cast<LINKED_ITEM*>(obs.m_item) );
630 clusterBBox.Merge( line.CLine().BBox() );
631 }
632 else
633 {
634 clusterBBox.Merge( obs.m_item->Shape( aLayer )->BBox() );
635 }
636
637 const int64_t currentArea = clusterBBox.GetArea();
638 const double areaRatio = (double) currentArea / (double) ( initialArea + 1 );
639
640 if( aAreaExpansionLimit > 0.0 && areaRatio > aAreaExpansionLimit )
641 break;
642
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 ) )
645 {
646 cluster.m_items.insert( obs.m_item );
647 pending.push_back( obs.m_item );
648 }
649 }
650 }
651
652 return cluster;
653}
654
655}
BOX2< VECTOR2I > BOX2I
Definition box2.h:922
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
void Add(const LINE &aLine)
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
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
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).
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition pns_line.h:158
std::set< OBSTACLE > OBSTACLES
Definition pns_node.h:244
virtual PCB_LAYER_ID GetBoardLayerFromPNSLayer(int aLayer) const =0
const SEG & Seg() const
Definition pns_segment.h:93
int Width() const override
Definition pns_segment.h:88
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
TOPOLOGY(NODE *aNode)
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 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:778
double GetRadius() 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.
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
@ DIFF_PAIR
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
VECTOR2I end
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition typeinfo.h:87
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:695