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 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 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, bool aForward = true )
373 {
374 const auto& shape = aPad->GetEffectivePolygon( 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 )
419 {
420 const auto& shape = aPad->GetEffectivePolygon( 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
439 if( shape->Contains( slc.CPoint( 0 ) ) )
440 clipLineToPad( slc, aPad, true );
441 else if( shape->Contains( slc.CPoint( -1 ) ) )
442 clipLineToPad( slc, aPad, false );
443 }
444 };
445
446 if( padA )
447 processPad( joints.first, padA );
448
449 if( padB )
450 processPad( joints.second, padB );
451
452 return initialPath;
453}
454
455
456const ITEM_SET TOPOLOGY::ConnectedItems( const JOINT* aStart, int aKindMask )
457{
458 return ITEM_SET();
459}
460
461
462const ITEM_SET TOPOLOGY::ConnectedItems( ITEM* aStart, int aKindMask )
463{
464 return ITEM_SET();
465}
466
467
468bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip );
469
470
472{
473 NET_HANDLE refNet = aStart->Net();
474 NET_HANDLE coupledNet = m_world->GetRuleResolver()->DpCoupledNet( refNet );
475 LINKED_ITEM* startItem = dynamic_cast<LINKED_ITEM*>( aStart );
476
477 if( !coupledNet || !startItem )
478 return false;
479
480 LINE lp = m_world->AssembleLine( startItem );
481
482 std::vector<ITEM*> pItems;
483 std::vector<ITEM*> nItems;
484
485 for( ITEM* item : lp.Links() )
486 {
487 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
488 pItems.push_back( item );
489 }
490
491 std::set<ITEM*> coupledItems;
492 m_world->AllItemsInNet( coupledNet, coupledItems );
493
494 for( ITEM* item : coupledItems )
495 {
496 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->Layers() == startItem->Layers() )
497 nItems.push_back( item );
498 }
499
500 LINKED_ITEM* refItem = nullptr;
501 LINKED_ITEM* coupledItem = nullptr;
502 SEG::ecoord minDist_sq = std::numeric_limits<SEG::ecoord>::max();
503 SEG::ecoord minDistTarget_sq = std::numeric_limits<SEG::ecoord>::max();
504 VECTOR2I targetPoint = aStart->Shape()->Centre();
505
506 auto findNItem = [&]( ITEM* p_item )
507 {
508 for( ITEM* n_item : nItems )
509 {
510 SEG::ecoord dist_sq = std::numeric_limits<SEG::ecoord>::max();
511
512 if( n_item->Kind() != p_item->Kind() )
513 continue;
514
515 if( p_item->Kind() == ITEM::SEGMENT_T )
516 {
517 const SEGMENT* p_seg = static_cast<const SEGMENT*>( p_item );
518 const SEGMENT* n_seg = static_cast<const SEGMENT*>( n_item );
519
520 if( n_seg->Width() != p_seg->Width() )
521 continue;
522
523 if( !p_seg->Seg().ApproxParallel( n_seg->Seg(), DP_PARALLELITY_THRESHOLD ) )
524 continue;
525
526 SEG p_clip, n_clip;
527
528 if( !commonParallelProjection( p_seg->Seg(), n_seg->Seg(), p_clip, n_clip ) )
529 continue;
530
531 dist_sq = n_seg->Seg().SquaredDistance( p_seg->Seg() );
532 }
533 else if( p_item->Kind() == ITEM::ARC_T )
534 {
535 const ARC* p_arc = static_cast<const ARC*>( p_item );
536 const ARC* n_arc = static_cast<const ARC*>( n_item );
537
538 if( n_arc->Width() != p_arc->Width() )
539 continue;
540
541 VECTOR2I centerDiff = n_arc->CArc().GetCenter() - p_arc->CArc().GetCenter();
542 SEG::ecoord centerDist_sq = centerDiff.SquaredEuclideanNorm();
543
544 if( centerDist_sq > SEG::Square( DP_PARALLELITY_THRESHOLD ) )
545 continue;
546
547 dist_sq = SEG::Square( p_arc->CArc().GetRadius() - n_arc->CArc().GetRadius() );
548 }
549
550 if( dist_sq <= minDist_sq )
551 {
552 SEG::ecoord distTarget_sq = n_item->Shape()->SquaredDistance( targetPoint );
553 if( distTarget_sq < minDistTarget_sq )
554 {
555 minDistTarget_sq = distTarget_sq;
556 minDist_sq = dist_sq;
557
558 refItem = static_cast<LINKED_ITEM*>( p_item );
559 coupledItem = static_cast<LINKED_ITEM*>( n_item );
560 }
561 }
562 }
563 };
564
565 findNItem( startItem );
566
567 if( !coupledItem )
568 {
569 LINKED_ITEM* linked = static_cast<LINKED_ITEM*>( startItem );
570 std::set<ITEM*> linksToTest;
571
572 for( int i = 0; i < linked->AnchorCount(); i++ )
573 {
574 const JOINT* jt = m_world->FindJoint( linked->Anchor( i ), linked );
575
576 if( !jt )
577 continue;
578
579 for( ITEM* link : jt->LinkList() )
580 {
581 if( link != linked )
582 linksToTest.emplace( link );
583 }
584 }
585
586 for( ITEM* link : linksToTest )
587 findNItem( link );
588 }
589
590 if( !coupledItem )
591 return false;
592
593 LINE ln = m_world->AssembleLine( coupledItem );
594
595 if( m_world->GetRuleResolver()->DpNetPolarity( refNet ) < 0 )
596 std::swap( lp, ln );
597
598 int gap = -1;
599
600 if( refItem && refItem->Kind() == ITEM::SEGMENT_T )
601 {
602 // Segments are parallel -> compute pair gap
603 const VECTOR2I refDir = refItem->Anchor( 1 ) - refItem->Anchor( 0 );
604 const VECTOR2I displacement = refItem->Anchor( 1 ) - coupledItem->Anchor( 1 );
605 gap = (int) std::abs( refDir.Cross( displacement ) / refDir.EuclideanNorm() ) - lp.Width();
606 }
607 else if( refItem && refItem->Kind() == ITEM::ARC_T )
608 {
609 const ARC* refArc = static_cast<ARC*>( refItem );
610 const ARC* coupledArc = static_cast<ARC*>( coupledItem );
611 gap = (int) std::abs( refArc->CArc().GetRadius() - coupledArc->CArc().GetRadius() ) - lp.Width();
612 }
613
614 aPair = DIFF_PAIR( lp, ln );
615 aPair.SetWidth( lp.Width() );
616 aPair.SetLayers( lp.Layers() );
617 aPair.SetGap( gap );
618
619 return true;
620}
621
622const std::set<ITEM*> TOPOLOGY::AssembleCluster( ITEM* aStart, int aLayer )
623{
624 std::set<ITEM*> visited;
625 std::deque<ITEM*> pending;
626
628
629 opts.m_differentNetsOnly = false;
630 opts.m_overrideClearance = 0;
631
632 pending.push_back( aStart );
633
634 while( !pending.empty() )
635 {
636 NODE::OBSTACLES obstacles;
637 ITEM* top = pending.front();
638
639 pending.pop_front();
640
641 visited.insert( top );
642
643 m_world->QueryColliding( top, obstacles, opts ); // only query touching objects
644
645 for( const OBSTACLE& obs : obstacles )
646 {
647 bool trackOnTrack = ( obs.m_item->Net() != top->Net() ) && obs.m_item->OfKind( ITEM::SEGMENT_T ) && top->OfKind( ITEM::SEGMENT_T );
648
649 if( trackOnTrack )
650 continue;
651
652 if( visited.find( obs.m_item ) == visited.end() &&
653 obs.m_item->Layers().Overlaps( aLayer ) && !( obs.m_item->Marker() & MK_HEAD ) )
654 {
655 visited.insert( obs.m_item );
656 pending.push_back( obs.m_item );
657 }
658 }
659 }
660
661 return visited;
662}
663
664}
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:77
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:100
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
Definition: pad.h:53
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 LAYER_RANGE &aLayers)
Definition: pns_item.h:197
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
const LAYER_RANGE & Layers() const
Definition: pns_item.h:196
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:274
NET_HANDLE Net() const override
Definition: pns_joint.h:269
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:289
bool IsNonFanoutVia() const
Definition: pns_joint.h:150
bool IsTraceWidthChange() const
Link the joint to a given board item (when it's added to the NODE).
Definition: pns_joint.h:177
const ITEM_SET & CLinks() const
Definition: pns_joint.h:279
const VECTOR2I & Pos() const
Definition: pns_joint.h:264
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
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:1043
int SegmentCount() const
Definition: pns_line.h:138
int PointCount() const
Definition: pns_line.h:139
bool EndsWithVia() const
Definition: pns_line.h:188
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:1212
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:1502
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:1014
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)
bool NearestUnconnectedAnchorPoint(const LINE *aTrack, VECTOR2I &aPoint, LAYER_RANGE &aLayers, ITEM *&aItem)
const ITEM_SET ConnectedItems(const JOINT *aStart, int aKindMask=ITEM::ANY_T)
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...
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:402
double GetRadius() const
Definition: shape_arc.cpp:536
const VECTOR2I & GetCenter() const
Definition: shape_arc.cpp:505
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
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:302
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:278
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:500
@ ERROR_INSIDE
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