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 tmpNode->Add( track );
108
109 const JOINT* jt = tmpNode->FindJoint( track.CPoint( -1 ), &track );
110
111 if( !jt || m_world->GetRuleResolver()->NetCode( jt->Net() ) <= 0 )
112 return false;
113
114 if( ( !track.EndsWithVia() && jt->LinkCount() >= 2 )
115 || ( track.EndsWithVia() && jt->LinkCount() >= 3 ) ) // we got something connected
116 {
117 end = jt->Pos();
118 aLayers = jt->Layers();
119 aItem = jt->LinkList()[0];
120 }
121 else
122 {
123 int anchor;
124
125 TOPOLOGY topo( tmpNode.get() );
126 ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
127
128 if( !it )
129 return false;
130
131 end = it->Anchor( anchor );
132 aLayers = it->Layers();
133 aItem = it;
134 }
135
136 aPoint = end;
137 return true;
138}
139
140
141bool TOPOLOGY::LeadingRatLine( const LINE* aTrack, SHAPE_LINE_CHAIN& aRatLine )
142{
143 VECTOR2I end;
144 // Ratline doesn't care about the layer
145 PNS_LAYER_RANGE layers;
146 ITEM* unusedItem;
147
148 if( !NearestUnconnectedAnchorPoint( aTrack, end, layers, unusedItem ) )
149 return false;
150
151 aRatLine.Clear();
152 aRatLine.Append( aTrack->CPoint( -1 ) );
153 aRatLine.Append( end );
154 return true;
155}
156
157
158ITEM* TOPOLOGY::NearestUnconnectedItem( const JOINT* aStart, int* aAnchor, int aKindMask )
159{
160 std::set<ITEM*> disconnected;
161
162 m_world->AllItemsInNet( aStart->Net(), disconnected );
163
164 for( const JOINT* jt : ConnectedJoints( aStart ) )
165 {
166 for( ITEM* link : jt->LinkList() )
167 {
168 if( disconnected.find( link ) != disconnected.end() )
169 disconnected.erase( link );
170 }
171 }
172
173 int best_dist = INT_MAX;
174 ITEM* best = nullptr;
175
176 for( ITEM* item : disconnected )
177 {
178 if( item->OfKind( aKindMask ) )
179 {
180 for( int i = 0; i < item->AnchorCount(); i++ )
181 {
182 VECTOR2I p = item->Anchor( i );
183 int d = ( p - aStart->Pos() ).EuclideanNorm();
184
185 if( d < best_dist )
186 {
187 best_dist = d;
188 best = item;
189
190 if( aAnchor )
191 *aAnchor = i;
192 }
193 }
194 }
195 }
196
197 return best;
198}
199
200
201bool TOPOLOGY::followTrivialPath( LINE* aLine2, bool aLeft, ITEM_SET& aSet,
202 const JOINT** aTerminalJoint, bool aFollowLockedSegments )
203{
204 assert( aLine2->IsLinked() );
205 LINE* curr_line = aLine2;
206 std::set<ITEM*> visited;
207
208 while( true )
209 {
210 VECTOR2I anchor = aLeft ? curr_line->CPoint( 0 ) : curr_line->CPoint( -1 );
211 LINKED_ITEM* last = aLeft ? curr_line->Links().front() : curr_line->Links().back();
212 const JOINT* jt = m_world->FindJoint( anchor, curr_line );
213
214 assert( jt != nullptr );
215
216 if( !visited.insert( last ).second
217 || ( !jt->IsNonFanoutVia() && !jt->IsTraceWidthChange() ) )
218 {
219 if( aTerminalJoint )
220 *aTerminalJoint = jt;
221
222 return false;
223 }
224
225 ITEM* via = nullptr;
226 SEGMENT* next_seg = nullptr;
227
228 ITEM_SET links( jt->CLinks() );
229
230 for( ITEM* link : links )
231 {
232 if( link->OfKind( ITEM::VIA_T ) )
233 via = link;
234 else if( visited.insert( link ).second )
235 next_seg = static_cast<SEGMENT*>( link );
236 }
237
238 if( !next_seg )
239 {
240 if( aTerminalJoint )
241 *aTerminalJoint = jt;
242
243 return false;
244 }
245
246 LINE l = m_world->AssembleLine( next_seg, nullptr, false, aFollowLockedSegments );
247 VECTOR2I nextAnchor = ( aLeft ? l.CLine().CPoint( -1 ) : l.CLine().CPoint( 0 ) );
248
249 if( nextAnchor != anchor )
250 {
251 l.Reverse();
252 }
253
254 if( aLeft )
255 {
256 if( via )
257 aSet.Prepend( via );
258
259 aSet.Prepend( l );
260 curr_line = static_cast<PNS::LINE*>( aSet[0] );
261 }
262 else
263 {
264 if( via )
265 aSet.Add( via );
266
267 aSet.Add( l );
268 curr_line = static_cast<PNS::LINE*>( aSet[aSet.Size() - 1] );
269 }
270
271 continue;
272 }
273}
274
275
277 std::pair<const JOINT*, const JOINT*>* aTerminalJoints,
278 bool aFollowLockedSegments )
279{
281 LINKED_ITEM* seg = nullptr;
282
283 if( aStart->Kind() == ITEM::VIA_T )
284 {
285 VIA* via = static_cast<VIA*>( aStart );
286 const JOINT* jt = m_world->FindJoint( via->Pos(), via );
287
288 if( !jt->IsNonFanoutVia() )
289 return ITEM_SET();
290
291 ITEM_SET links( jt->CLinks() );
292
293 for( ITEM* item : links )
294 {
295 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
296 {
297 seg = static_cast<LINKED_ITEM*>( item );
298 break;
299 }
300 }
301 }
302 else if( aStart->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
303 {
304 seg = static_cast<LINKED_ITEM*>( aStart );
305 }
306
307 if( !seg )
308 return ITEM_SET();
309
310 // Assemble a line following through locked segments
311 // TODO: consider if we want to allow tuning lines with different widths in the future
312 LINE l = m_world->AssembleLine( seg, nullptr, false, aFollowLockedSegments );
313
314 path.Add( l );
315
316 const JOINT* jointA = nullptr;
317 const JOINT* jointB = nullptr;
318
319 followTrivialPath( &l, false, path, &jointB, aFollowLockedSegments );
320 followTrivialPath( &l, true, path, &jointA, aFollowLockedSegments );
321
322 if( aTerminalJoints )
323 {
324 wxASSERT( jointA && jointB );
325 *aTerminalJoints = std::make_pair( jointA, jointB );
326 }
327
328 return path;
329}
330
331
332const ITEM_SET TOPOLOGY::AssembleTuningPath( ITEM* aStart, SOLID** aStartPad, SOLID** aEndPad )
333{
334 std::pair<const JOINT*, const JOINT*> joints;
335 ITEM_SET initialPath = AssembleTrivialPath( aStart, &joints, true );
336
337 PAD* padA = nullptr;
338 PAD* padB = nullptr;
339
340 auto getPadFromJoint =
341 []( const JOINT* aJoint, PAD** aTargetPad, SOLID** aTargetSolid )
342 {
343 for( ITEM* item : aJoint->LinkList() )
344 {
345 if( item->OfKind( ITEM::SOLID_T ) )
346 {
347 BOARD_ITEM* bi = static_cast<SOLID*>( item )->Parent();
348
349 if( bi->Type() == PCB_PAD_T )
350 {
351 *aTargetPad = static_cast<PAD*>( bi );
352
353 if( aTargetSolid )
354 *aTargetSolid = static_cast<SOLID*>( item );
355 }
356
357 break;
358 }
359 }
360 };
361
362 if( joints.first )
363 getPadFromJoint( joints.first, &padA, aStartPad );
364
365 if( joints.second )
366 getPadFromJoint( joints.second, &padB, aEndPad );
367
368 if( !padA && !padB )
369 return initialPath;
370
371 auto clipLineToPad =
372 []( SHAPE_LINE_CHAIN& aLine, PAD* aPad, PCB_LAYER_ID aLayer, bool aForward = true )
373 {
374 const auto& shape = aPad->GetEffectivePolygon( aLayer, ERROR_INSIDE );
375
376 int start = aForward ? 0 : aLine.PointCount() - 1;
377 int delta = aForward ? 1 : -1;
378
379 // Skip the "first" (or last) vertex, we already know it's contained in the pad
380 int clip = start;
381
382 for( int vertex = start + delta;
383 aForward ? vertex < aLine.PointCount() : vertex >= 0;
384 vertex += delta )
385 {
386 SEG seg( aLine.GetPoint( vertex ), aLine.GetPoint( vertex - delta ) );
387
388 bool containsA = shape->Contains( seg.A );
389 bool containsB = shape->Contains( seg.B );
390
391 if( containsA && containsB )
392 {
393 // Whole segment is inside: clip out this segment
394 clip = vertex;
395 }
396 else if( containsB )
397 {
398 // Only one point inside: Find the intersection
399 VECTOR2I loc;
400
401 if( shape->Collide( seg, 0, nullptr, &loc ) )
402 {
403 aLine.Replace( vertex - delta, vertex - delta, loc );
404 }
405 }
406 }
407
408 if( !aForward && clip < start )
409 aLine.Remove( clip + 1, start );
410 else if( clip > start )
411 aLine.Remove( start, clip - 1 );
412
413 // Now connect the dots
414 aLine.Insert( aForward ? 0 : aLine.PointCount(), aPad->GetPosition() );
415 };
416
417 auto processPad =
418 [&]( const JOINT* aJoint, PAD* aPad, PCB_LAYER_ID aLayer )
419 {
420 const auto& shape = aPad->GetEffectivePolygon( aLayer, ERROR_INSIDE );
421
422 for( int idx = 0; idx < initialPath.Size(); idx++ )
423 {
424 if( initialPath[idx]->Kind() != ITEM::LINE_T )
425 continue;
426
427 LINE* line = static_cast<LINE*>( initialPath[idx] );
428
429 if( !aPad->FlashLayer( line->Layer() ) )
430 continue;
431
432 const std::vector<VECTOR2I>& points = line->CLine().CPoints();
433
434 if( points.front() != aJoint->Pos() && points.back() != aJoint->Pos() )
435 continue;
436
437 SHAPE_LINE_CHAIN& slc = line->Line();
438 const PCB_LAYER_ID& layer = static_cast<PCB_LAYER_ID>( line->Layer() );
439
440 if( shape->Contains( slc.CPoint( 0 ) ) )
441 clipLineToPad( slc, aPad, layer, true );
442 else if( shape->Contains( slc.CPoint( -1 ) ) )
443 clipLineToPad( slc, aPad, layer, false );
444 }
445 };
446
447 if( padA )
448 processPad( joints.first, padA, static_cast<PCB_LAYER_ID>( joints.first->Layer() ) );
449
450 if( padB )
451 processPad( joints.second, padB, static_cast<PCB_LAYER_ID>( joints.second->Layer() ) );
452
453 return initialPath;
454}
455
456
457const ITEM_SET TOPOLOGY::ConnectedItems( const JOINT* aStart, int aKindMask )
458{
459 return ITEM_SET();
460}
461
462
463const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
464{
465 return ITEM_SET();
466}
467
468
469bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
470
471
473{
474 NET_HANDLE refNet = aStart->Net();
475 NET_HANDLE coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
476 LINKED_ITEM* startItem = dynamic_cast<LINKED_ITEM*>( aStart );
477
478 if( !coupledNet || !startItem )
479 return false;
480
481 LINE lp = m_world->AssembleLine( startItem );
482
483 std::vector<ITEM*> pItems;
484 std::vector<ITEM*> nItems;
485
486 for( ITEM* item : lp.Links() )
487 {
488 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
489 pItems.push_back( item );
490 }
491
492 std::set<ITEM*> coupledItems;
493 m_world->AllItemsInNet( coupledNet, coupledItems );
494
495 for( ITEM* item : coupledItems )
496 {
497 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
498 nItems.push_back( item );
499 }
500
501 LINKED_ITEM* refItem = nullptr;
502 LINKED_ITEM* coupledItem = nullptr;
503 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
504 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
505 VECTOR2I targetPoint = aStart->Shape()->Centre();
506
507 auto findNItem = [&]( ITEM* p_item )
508 {
509 for( ITEM* n_item : nItems )
510 {
511 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
512
513 if( n_item->Kind() != p_item->Kind() )
514 continue;
515
516 if( p_item->Kind() == ITEM::SEGMENT_T )
517 {
518 const SEGMENT* p_seg = static_cast<const SEGMENT*>( p_item );
519 const SEGMENT* n_seg = static_cast<const SEGMENT*>( n_item );
520
521 if( n_seg->Width() != p_seg->Width() )
522 continue;
523
524 if( !p_seg->Seg().ApproxParallel( n_seg->Seg(), DP_PARALLELITY_THRESHOLD ) )
525 continue;
526
527 SEG p_clip, n_clip;
528
529 if( !commonParallelProjection( p_seg->Seg(), n_seg->Seg(), p_clip, n_clip ) )
530 continue;
531
532 dist_sq = n_seg->Seg().SquaredDistance( p_seg->Seg() );
533 }
534 else if( p_item->Kind() == ITEM::ARC_T )
535 {
536 const ARC* p_arc = static_cast<const ARC*>( p_item );
537 const ARC* n_arc = static_cast<const ARC*>( n_item );
538
539 if( n_arc->Width() != p_arc->Width() )
540 continue;
541
542 VECTOR2I centerDiff = n_arc->CArc().GetCenter() - p_arc->CArc().GetCenter();
543 SEG::ecoord centerDist_sq = centerDiff.SquaredEuclideanNorm();
544
545 if( centerDist_sq > SEG::Square( DP_PARALLELITY_THRESHOLD ) )
546 continue;
547
548 dist_sq = SEG::Square( p_arc->CArc().GetRadius() - n_arc->CArc().GetRadius() );
549 }
550
551 if( dist_sq <= minDist_sq )
552 {
553 SEG::ecoord distTarget_sq = n_item->Shape()->SquaredDistance( targetPoint );
554 if( distTarget_sq < minDistTarget_sq )
555 {
556 minDistTarget_sq = distTarget_sq;
557 minDist_sq = dist_sq;
558
559 refItem = static_cast<LINKED_ITEM*>( p_item );
560 coupledItem = static_cast<LINKED_ITEM*>( n_item );
561 }
562 }
563 }
564 };
565
566 findNItem( startItem );
567
568 if( !coupledItem )
569 {
570 LINKED_ITEM* linked = static_cast<LINKED_ITEM*>( startItem );
571 std::set<ITEM*> linksToTest;
572
573 for( int i = 0; i < linked->AnchorCount(); i++ )
574 {
575 const JOINT* jt = m_world->FindJoint( linked->Anchor( i ), linked );
576
577 if( !jt )
578 continue;
579
580 for( ITEM* link : jt->LinkList() )
581 {
582 if( link != linked )
583 linksToTest.emplace( link );
584 }
585 }
586
587 for( ITEM* link : linksToTest )
588 findNItem( link );
589 }
590
591 if( !coupledItem )
592 return false;
593
594 LINE ln = m_world->AssembleLine( coupledItem );
595
596 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
597 std::swap( lp, ln );
598
599 int gap = -1;
600
601 if( refItem && refItem->Kind() == ITEM::SEGMENT_T )
602 {
603 // Segments are parallel -> compute pair gap
604 const VECTOR2I refDir = refItem->Anchor( 1 ) - refItem->Anchor( 0 );
605 const VECTOR2I displacement = refItem->Anchor( 1 ) - coupledItem->Anchor( 1 );
606 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
607 }
608 else if( refItem && refItem->Kind() == ITEM::ARC_T )
609 {
610 const ARC* refArc = static_cast<ARC*>( refItem );
611 const ARC* coupledArc = static_cast<ARC*>( coupledItem );
612 gap = (int) std::abs( refArc->CArc().GetRadius() - coupledArc->CArc().GetRadius() ) - lp.Width();
613 }
614
615 aPair = DIFF_PAIR( lp, ln );
616 aPair.SetWidth( lp.Width() );
617 aPair.SetLayers( lp.Layers() );
618 aPair.SetGap( gap );
619
620 return true;
621}
622
623const std::set<ITEM*> TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer )
624{
625 std::set<ITEM*> visited;
626 std::deque<ITEM*> pending;
627
629
630 opts.m_differentNetsOnly = false;
631 opts.m_overrideClearance = 0;
632
633 pending.push_back( aStart );
634
635 while( !pending.empty() )
636 {
637 NODE::OBSTACLES obstacles;
638 ITEM* top = pending.front();
639
640 pending.pop_front();
641
642 visited.insert( top );
643
644 m_world->QueryColliding( top, obstacles, opts ); // only query touching objects
645
646 for( const OBSTACLE& obs : obstacles )
647 {
648 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
649
650 if( trackOnTrack )
651 continue;
652
653 if( visited.find( obs.m_item ) == visited.end() &&
654 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
655 {
656 visited.insert( obs.m_item );
657 pending.push_back( obs.m_item );
658 }
659 }
660 }
661
662 return visited;
663}
664
665}
@ 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:80
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:32
void Prepend(const LINE &aLine)
Definition: pns_itemset.cpp:40
Base class for PNS router board items.
Definition: pns_item.h:97
void SetLayers(const PNS_LAYER_RANGE &aLayers)
Definition: pns_item.h:197
const PNS_LAYER_RANGE & Layers() const
Definition: pns_item.h:196
virtual NET_HANDLE Net() const
Definition: pns_item.h:194
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:167
virtual int Layer() const
Definition: pns_item.h:200
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:225
@ SEGMENT_T
Definition: pns_item.h:106
bool OfKind(int aKindMask) const
Definition: pns_item.h:175
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:237
virtual int AnchorCount() const
Definition: pns_item.h:242
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:273
NET_HANDLE Net() const override
Definition: pns_joint.h:268
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:288
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:176
const ITEM_SET & CLinks() const
Definition: pns_joint.h:278
const VECTOR2I & Pos() const
Definition: pns_joint.h:263
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:144
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:125
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:136
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:135
int SegmentCount() const
Definition: pns_line.h:138
int PointCount() const
Definition: pns_line.h:139
bool EndsWithVia() const
Definition: pns_line.h:188
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:1043
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:155
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:1215
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:245
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:663
std::set< OBSTACLE > OBSTACLES
Definition: pns_node.h:219
void AllItemsInNet(NET_HANDLE aNet, std::set< ITEM * > &aItems, int aKindMask=-1)
Definition: pns_node.cpp:1505
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:252
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:884
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:1017
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:84
int Width() const override
Definition: pns_segment.h:79
ITEM * NearestUnconnectedItem(const JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
std::set< const JOINT * > JOINT_SET
Definition: pns_topology.h:42
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 JOINT_SET ConnectedJoints(const JOINT *aStart)
const int DP_PARALLELITY_THRESHOLD
Definition: pns_topology.h:96
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.
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
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
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
constexpr int delta
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87