KiCad PCB EDA Suite
pns_optimizer.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright (C) 2016-2021 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
23#include <geometry/shape_rect.h>
25
26#include <cmath>
27
28#include "pns_arc.h"
29#include "pns_line.h"
30#include "pns_diff_pair.h"
31#include "pns_node.h"
32#include "pns_solid.h"
33#include "pns_optimizer.h"
34
35#include "pns_utils.h"
36#include "pns_router.h"
37#include "pns_debug_decorator.h"
38
39
40namespace PNS {
41
42
43int COST_ESTIMATOR::CornerCost( const SEG& aA, const SEG& aB )
44{
45 DIRECTION_45 dir_a( aA ), dir_b( aB );
46
47 switch( dir_a.Angle( dir_b ) )
48 {
49 case DIRECTION_45::ANG_OBTUSE: return 10;
50 case DIRECTION_45::ANG_STRAIGHT: return 5;
51 case DIRECTION_45::ANG_ACUTE: return 50;
52 case DIRECTION_45::ANG_RIGHT: return 30;
53 case DIRECTION_45::ANG_HALF_FULL: return 60;
54 default: return 100;
55 }
56}
57
58
60{
61 int total = 0;
62
63 for( int i = 0; i < aLine.SegmentCount() - 1; ++i )
64 total += CornerCost( aLine.CSegment( i ), aLine.CSegment( i + 1 ) );
65
66 return total;
67}
68
69
71{
72 return CornerCost( aLine.CLine() );
73}
74
75
76void COST_ESTIMATOR::Add( const LINE& aLine )
77{
78 m_lengthCost += aLine.CLine().Length();
79 m_cornerCost += CornerCost( aLine );
80}
81
82
83void COST_ESTIMATOR::Remove( const LINE& aLine )
84{
85 m_lengthCost -= aLine.CLine().Length();
86 m_cornerCost -= CornerCost( aLine );
87}
88
89
90void COST_ESTIMATOR::Replace( const LINE& aOldLine, const LINE& aNewLine )
91{
92 m_lengthCost -= aOldLine.CLine().Length();
93 m_cornerCost -= CornerCost( aOldLine );
94 m_lengthCost += aNewLine.CLine().Length();
95 m_cornerCost += CornerCost( aNewLine );
96}
97
98
99bool COST_ESTIMATOR::IsBetter( const COST_ESTIMATOR& aOther, double aLengthTolerance,
100 double aCornerTolerance ) const
101{
102 if( aOther.m_cornerCost < m_cornerCost && aOther.m_lengthCost < m_lengthCost )
103 return true;
104 else if( aOther.m_cornerCost < m_cornerCost * aCornerTolerance &&
105 aOther.m_lengthCost < m_lengthCost * aLengthTolerance )
106 return true;
107
108 return false;
109}
110
111
113 m_world( aWorld ),
114 m_collisionKindMask( ITEM::ANY_T ),
115 m_effortLevel( MERGE_SEGMENTS ),
116 m_restrictAreaIsStrict( false )
117{
118}
119
120
122{
123}
124
125
127{
128 CACHE_VISITOR( const ITEM* aOurItem, NODE* aNode, int aMask ) :
129 m_ourItem( aOurItem ),
130 m_collidingItem( nullptr ),
131 m_node( aNode ),
132 m_mask( aMask )
133 {}
134
135 bool operator()( ITEM* aOtherItem )
136 {
137 if( !( m_mask & aOtherItem->Kind() ) )
138 return true;
139
140 if( !aOtherItem->Collide( m_ourItem, m_node ) )
141 return true;
142
143 m_collidingItem = aOtherItem;
144 return false;
145 }
146
151};
152
153
154void OPTIMIZER::cacheAdd( ITEM* aItem, bool aIsStatic = false )
155{
156 if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
157 return;
158
159 m_cache.Add( aItem );
160 m_cacheTags[aItem].m_hits = 1;
161 m_cacheTags[aItem].m_isStatic = aIsStatic;
162}
163
164
165void OPTIMIZER::removeCachedSegments( LINE* aLine, int aStartVertex, int aEndVertex )
166{
167 if( !aLine->IsLinked() )
168 return;
169
170 auto links = aLine->Links();
171
172 if( aEndVertex < 0 )
173 aEndVertex += aLine->PointCount();
174
175 for( int i = aStartVertex; i < aEndVertex - 1; i++ )
176 {
177 LINKED_ITEM* s = links[i];
178 m_cacheTags.erase( s );
179 m_cache.Remove( s );
180 }
181}
182
183
185{
186 if( aItem->Kind() == ITEM::LINE_T )
187 removeCachedSegments( static_cast<LINE*>( aItem ) );
188}
189
190
191void OPTIMIZER::ClearCache( bool aStaticOnly )
192{
193 if( !aStaticOnly )
194 {
195 m_cacheTags.clear();
196 m_cache.Clear();
197 return;
198 }
199
200 for( auto i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
201 {
202 if( i->second.m_isStatic )
203 {
204 m_cache.Remove( i->first );
205 m_cacheTags.erase( i->first );
206 }
207 }
208}
209
210
211bool AREA_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
212 const SHAPE_LINE_CHAIN& aCurrentPath,
213 const SHAPE_LINE_CHAIN& aReplacement )
214{
215 const VECTOR2I& p1 = aOriginLine->CPoint( aVertex1 );
216 const VECTOR2I& p2 = aOriginLine->CPoint( aVertex2 );
217
218 bool p1_in = m_allowedArea.Contains( p1 );
219 bool p2_in = m_allowedArea.Contains( p2 );
220
221 if( m_allowedAreaStrict ) // strict restriction? both points must be inside the restricted area
222 return p1_in && p2_in;
223 else // loose restriction
224 return p1_in || p2_in;
225}
226
227
228bool PRESERVE_VERTEX_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
229 const SHAPE_LINE_CHAIN& aCurrentPath,
230 const SHAPE_LINE_CHAIN& aReplacement )
231{
232 bool cv = false;
233
234 for( int i = aVertex1; i < aVertex2; i++ )
235 {
236 SEG::ecoord dist = aCurrentPath.CSegment(i).SquaredDistance( m_v );
237
238 if ( dist <= 1 )
239 {
240 cv = true;
241 break;
242 }
243 }
244
245 if( !cv )
246 return true;
247
248 for( int i = 0; i < aReplacement.SegmentCount(); i++ )
249 {
250 SEG::ecoord dist = aReplacement.CSegment(i).SquaredDistance( m_v );
251
252 if ( dist <= 1 )
253 return true;
254 }
255
256 return false;
257}
258
259
260bool RESTRICT_VERTEX_RANGE_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
261 const SHAPE_LINE_CHAIN& aCurrentPath,
262 const SHAPE_LINE_CHAIN& aReplacement )
263{
264 return true;
265}
266
267
268bool CORNER_COUNT_LIMIT_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
269 const SHAPE_LINE_CHAIN& aCurrentPath,
270 const SHAPE_LINE_CHAIN& aReplacement )
271{
272 LINE newPath( *aOriginLine, aCurrentPath );
273 newPath.Line().Replace( aVertex1, aVertex2, aReplacement );
274 newPath.Line().Simplify();
275 int cc = newPath.CountCorners( m_angleMask );
276
277 if( cc >= m_minCorners )
278 return true;
279
280 // fixme: something fishy with the max corneriness limit
281 // (cc <= m_maxCorners)
282
283 return false;
284}
285
286
298static bool pointInside2( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aP )
299{
300 if( !aL.IsClosed() || aL.SegmentCount() < 3 )
301 return false;
302
303 int result = 0;
304 size_t cnt = aL.PointCount();
305
306 VECTOR2I ip = aL.CPoint( 0 );
307
308 for( size_t i = 1; i <= cnt; ++i )
309 {
310 VECTOR2I ipNext = ( i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ) );
311
312 if( ipNext.y == aP.y )
313 {
314 if( ( ipNext.x == aP.x )
315 || ( ip.y == aP.y && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
316 return true; // pt on polyground boundary
317 }
318
319 if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
320 {
321 if( ip.x >=aP.x )
322 {
323 if( ipNext.x >aP.x )
324 {
325 result = 1 - result;
326 }
327 else
328 {
329 double d = static_cast<double>( ip.x - aP.x ) *
330 static_cast<double>( ipNext.y - aP.y ) -
331 static_cast<double>( ipNext.x - aP.x ) *
332 static_cast<double>( ip.y - aP.y );
333
334 if( !d )
335 return true; // pt on polyground boundary
336
337 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
338 result = 1 - result;
339 }
340 }
341 else
342 {
343 if( ipNext.x >aP.x )
344 {
345 double d = ( (double) ip.x - aP.x ) * ( (double) ipNext.y - aP.y )
346 - ( (double) ipNext.x - aP.x ) * ( (double) ip.y - aP.y );
347
348 if( !d )
349 return true; // pt on polyground boundary
350
351 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
352 result = 1 - result;
353 }
354 }
355 }
356
357 ip = ipNext;
358 }
359
360 return result > 0;
361}
362
363
364bool KEEP_TOPOLOGY_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
365 const SHAPE_LINE_CHAIN& aCurrentPath,
366 const SHAPE_LINE_CHAIN& aReplacement )
367{
368 SHAPE_LINE_CHAIN encPoly = aOriginLine->CLine().Slice( aVertex1, aVertex2 );
369
370 // fixme: this is a remarkably shitty implementation...
371 encPoly.Append( aReplacement.Reverse() );
372 encPoly.SetClosed( true );
373
374 BOX2I bb = encPoly.BBox();
375 std::vector<JOINT*> joints;
376
377 int cnt = m_world->QueryJoints( bb, joints, aOriginLine->Layers(), ITEM::SOLID_T );
378
379 if( !cnt )
380 return true;
381
382 for( JOINT* j : joints )
383 {
384 if( j->Net() == aOriginLine->Net() )
385 continue;
386
387 if( pointInside2( encPoly, j->Pos() ) )
388 {
389 bool falsePositive = false;
390
391 for( int k = 0; k < encPoly.PointCount(); k++ )
392 {
393 if( encPoly.CPoint(k) == j->Pos() )
394 {
395 falsePositive = true;
396 break;
397 }
398 }
399
400 if( !falsePositive )
401 {
402 //dbg->AddPoint(j->Pos(), 5);
403 return false;
404 }
405 }
406 }
407
408 return true;
409}
410
411
412bool OPTIMIZER::checkColliding( ITEM* aItem, bool aUpdateCache )
413{
415
416 return static_cast<bool>( m_world->CheckColliding( aItem ) );
417}
418
419
421{
422 for( OPT_CONSTRAINT* c : m_constraints )
423 delete c;
424
425 m_constraints.clear();
426}
427
428
430{
431 m_constraints.push_back( aConstraint );
432}
433
434
435bool OPTIMIZER::checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
436 const SHAPE_LINE_CHAIN& aCurrentPath,
437 const SHAPE_LINE_CHAIN& aReplacement )
438{
439 for( OPT_CONSTRAINT* c : m_constraints )
440 {
441 if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
442 return false;
443 }
444
445 return true;
446}
447
448
449bool OPTIMIZER::checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath )
450{
451 LINE tmp( *aLine, aOptPath );
452
453 return checkColliding( &tmp );
454}
455
456
458{
459 SHAPE_LINE_CHAIN& line = aLine->Line();
460
461 int step = line.PointCount() - 3;
462 int iter = 0;
463 int segs_pre = line.SegmentCount();
464
465 if( step < 0 )
466 return false;
467
468 SHAPE_LINE_CHAIN current_path( line );
469
470 while( 1 )
471 {
472 iter++;
473 int n_segs = current_path.SegmentCount();
474 int max_step = n_segs - 2;
475
476 if( step > max_step )
477 step = max_step;
478
479 if( step < 2 )
480 {
481 line = current_path;
482 return current_path.SegmentCount() < segs_pre;
483 }
484
485 bool found_anything = false;
486
487 for( int n = 0; n < n_segs - step; n++ )
488 {
489 const SEG s1 = current_path.CSegment( n );
490 const SEG s2 = current_path.CSegment( n + step );
491 SEG s1opt, s2opt;
492
493 if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
494 {
495 VECTOR2I ip = *s1.IntersectLines( s2 );
496
497 s1opt = SEG( s1.A, ip );
498 s2opt = SEG( ip, s2.B );
499
500 if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
501 {
502 SHAPE_LINE_CHAIN opt_path;
503 opt_path.Append( s1opt.A );
504 opt_path.Append( s1opt.B );
505 opt_path.Append( s2opt.B );
506
507 LINE opt_track( *aLine, opt_path );
508
509 if( !checkColliding( &opt_track ) )
510 {
511 current_path.Replace( s1.Index() + 1, s2.Index(), ip );
512
513 // removeCachedSegments(aLine, s1.Index(), s2.Index());
514 n_segs = current_path.SegmentCount();
515 found_anything = true;
516 break;
517 }
518 }
519 }
520 }
521
522 if( !found_anything )
523 {
524 if( step <= 2 )
525 {
526 line = current_path;
527 return line.SegmentCount() < segs_pre;
528 }
529
530 step--;
531 }
532 }
533
534 return line.SegmentCount() < segs_pre;
535}
536
537
539{
540 SHAPE_LINE_CHAIN& line = aLine->Line();
541 int step = line.SegmentCount() - 1;
542
543 int segs_pre = line.SegmentCount();
544
545 line.Simplify();
546
547 if( step < 0 )
548 return false;
549
550 SHAPE_LINE_CHAIN current_path( line );
551
552 while( 1 )
553 {
554 int n_segs = current_path.SegmentCount();
555 int max_step = n_segs - 2;
556
557 if( step > max_step )
558 step = max_step;
559
560 if( step < 1 )
561 break;
562
563 bool found_anything = mergeStep( aLine, current_path, step );
564
565 if( !found_anything )
566 step--;
567
568 if( !step )
569 break;
570 }
571
572 aLine->SetShape( current_path );
573
574 return current_path.SegmentCount() < segs_pre;
575}
576
577
579{
580 SHAPE_LINE_CHAIN& line = aLine->Line();
581
582 int nSegs = line.SegmentCount();
583
584 for( int segIdx = 0; segIdx < line.SegmentCount() - 1; ++segIdx )
585 {
586 SEG s1 = line.CSegment( segIdx );
587 SEG s2 = line.CSegment( segIdx + 1 );
588
589 // Skip zero-length segs caused by abutting arcs
590 if( s1.SquaredLength() == 0 || s2.SquaredLength() == 0 )
591 continue;
592
593 if( s1.Collinear( s2 ) && !line.IsPtOnArc( segIdx + 1 ) )
594 {
595 line.Remove( segIdx + 1 );
596 }
597 }
598
599 return line.SegmentCount() < nSegs;
600}
601
602
603bool OPTIMIZER::Optimize( LINE* aLine, LINE* aResult, LINE* aRoot )
604{
606
607 if( aRoot )
608 {
609 PNS_DBG( dbg, AddItem, aRoot, BLUE, 100000, wxT( "root-line" ) );
610 }
611
612
613 if( !aResult )
614 {
615 aResult = aLine;
616 }
617 else
618 {
619 *aResult = *aLine;
620 aResult->ClearLinks();
621 }
622
623 bool hasArcs = aLine->ArcCount();
624 bool rv = false;
625
626 if( (m_effortLevel & LIMIT_CORNER_COUNT) && aRoot )
627 {
628 const int angleMask = DIRECTION_45::ANG_OBTUSE;
629 int rootObtuseCorners = aRoot->CountCorners( angleMask );
630 auto c = new CORNER_COUNT_LIMIT_CONSTRAINT( m_world, rootObtuseCorners,
631 aLine->SegmentCount(), angleMask );
632 PNS_DBG( dbg, Message,
633 wxString::Format( "opt limit-corner-count root %d maxc %d mask %x",
634 rootObtuseCorners, aLine->SegmentCount(), angleMask ) );
635
636 AddConstraint( c );
637 }
638
640 {
642 AddConstraint( c );
643 }
644
646 {
649 AddConstraint( c );
650 }
651
653 {
656 PNS_DBG( dbg, AddShape, &r, YELLOW, 0, wxT( "area-constraint" ) );
657 AddConstraint( c );
658 }
659
661 {
662 auto c = new KEEP_TOPOLOGY_CONSTRAINT( m_world );
663 AddConstraint( c );
664 }
665
666 // TODO: Fix for arcs
667 if( !hasArcs && m_effortLevel & MERGE_SEGMENTS )
668 rv |= mergeFull( aResult );
669
670 // TODO: Fix for arcs
671 if( !hasArcs && m_effortLevel & MERGE_OBTUSE )
672 rv |= mergeObtuse( aResult );
673
675 rv |= mergeColinear( aResult );
676
677 // TODO: Fix for arcs
678 if( !hasArcs && m_effortLevel & SMART_PADS )
679 rv |= runSmartPads( aResult );
680
681 // TODO: Fix for arcs
682 if( !hasArcs && m_effortLevel & FANOUT_CLEANUP )
683 rv |= fanoutCleanup( aResult );
684
685 return rv;
686}
687
688
689bool OPTIMIZER::mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentPath, int step )
690{
691 int n_segs = aCurrentPath.SegmentCount();
692
693 int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
694
695 if( aLine->SegmentCount() < 2 )
696 return false;
697
698 DIRECTION_45 orig_start( aLine->CSegment( 0 ) );
699 DIRECTION_45 orig_end( aLine->CSegment( -1 ) );
700
701
702 for( int n = 0; n < n_segs - step; n++ )
703 {
704 // Do not attempt to merge false segments that are part of an arc
705 if( aCurrentPath.IsArcSegment( n )
706 || aCurrentPath.IsArcSegment( static_cast<std::size_t>( n ) + step ) )
707 {
708 continue;
709 }
710
711 const SEG s1 = aCurrentPath.CSegment( n );
712 const SEG s2 = aCurrentPath.CSegment( n + step );
713
715 SHAPE_LINE_CHAIN* picked = nullptr;
716 int cost[2];
717
718 for( int i = 0; i < 2; i++ )
719 {
720 SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i );
721 cost[i] = INT_MAX;
722
723 bool ok = false;
724
725 if( !checkColliding( aLine, bypass ) )
726 {
727 //printf("Chk-constraints: %d %d\n", n, n+step+1 );
728 ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
729 }
730
731 if( ok )
732 {
733 path[i] = aCurrentPath;
734 path[i].Replace( s1.Index(), s2.Index(), bypass );
735 path[i].Simplify();
736 cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
737 }
738 }
739
740 if( cost[0] < cost_orig && cost[0] < cost[1] )
741 picked = &path[0];
742 else if( cost[1] < cost_orig )
743 picked = &path[1];
744
745 if( picked )
746 {
747 n_segs = aCurrentPath.SegmentCount();
748 aCurrentPath = *picked;
749 return true;
750 }
751 }
752
753 return false;
754}
755
756
758 bool aPermitDiagonal ) const
759{
760 BREAKOUT_LIST breakouts;
761
763 {
764 const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
766 VECTOR2I p0 = cir->GetCenter();
767 VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
768
769 RotatePoint( v0, -angle );
770
771 l.Append( p0 );
772 l.Append( p0 + v0 );
773 breakouts.push_back( l );
774 }
775
776 return breakouts;
777}
778
779
781 bool aPermitDiagonal ) const
782{
783 BREAKOUT_LIST breakouts;
784 const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
785
786 BOX2I bbox = convex->BBox( 0 );
787 VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
788 // must be large enough to guarantee intersecting the convex polygon
789 int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
790 EDA_ANGLE increment = ( aPermitDiagonal ? ANGLE_45 : ANGLE_90 );
791
792 for( EDA_ANGLE angle = ANGLE_0; angle < ANGLE_360; angle += increment )
793 {
795 VECTOR2I v0( p0 + VECTOR2I( length, 0 ) );
796 RotatePoint( v0, p0, -angle );
797
799 int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
800
801 // if n == 1 intersected a segment
802 // if n == 2 intersected the common point of 2 segments
803 // n == 0 can not happen I think, but...
804 if( n > 0 )
805 {
806 l.Append( p0 );
807
808 // for a breakout distance relative to the distance between
809 // center and polygon edge
810 //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
811
812 // for an absolute breakout distance, e.g. 0.1 mm
813 //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
814
815 // for the breakout right on the polygon edge
816 l.Append( intersections[0].p );
817
818 breakouts.push_back( l );
819 }
820 }
821
822 return breakouts;
823}
824
825
827 bool aPermitDiagonal ) const
828{
829 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
830 VECTOR2I s = rect->GetSize();
831 VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
832
833 BREAKOUT_LIST breakouts;
834 breakouts.reserve( 12 );
835
836 VECTOR2I d_offset;
837
838 d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
839 d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
840
841 VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
842 VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
843
844 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
845 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
846 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
847 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
848
849 if( aPermitDiagonal )
850 {
851 int l = aWidth + std::min( s.x, s.y ) / 2;
852 VECTOR2I d_diag;
853
854 if( s.x >= s.y )
855 {
856 breakouts.emplace_back(
857 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
858 breakouts.emplace_back(
859 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
860 breakouts.emplace_back(
861 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
862 breakouts.emplace_back(
863 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
864 }
865 else
866 {
867 // fixme: this could be done more efficiently
868 breakouts.emplace_back(
869 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
870 breakouts.emplace_back(
871 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
872 breakouts.emplace_back(
873 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
874 breakouts.emplace_back(
875 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
876 }
877 }
878
879 return breakouts;
880}
881
882
884 bool aPermitDiagonal ) const
885{
886 switch( aItem->Kind() )
887 {
888 case ITEM::VIA_T:
889 {
890 const VIA* via = static_cast<const VIA*>( aItem );
891 return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
892 }
893
894 case ITEM::SOLID_T:
895 {
896 const SHAPE* shape = aItem->Shape();
897
898 switch( shape->Type() )
899 {
900 case SH_RECT:
901 return rectBreakouts( aWidth, shape, aPermitDiagonal );
902
903 case SH_SEGMENT:
904 {
905 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
906 const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
907 return rectBreakouts( aWidth, &rect, aPermitDiagonal );
908 }
909
910 case SH_CIRCLE:
911 return circleBreakouts( aWidth, shape, aPermitDiagonal );
912
913 case SH_SIMPLE:
914 return customBreakouts( aWidth, aItem, aPermitDiagonal );
915
916 default:
917 break;
918 }
919
920 break;
921 }
922
923 default:
924 break;
925 }
926
927 return BREAKOUT_LIST();
928}
929
930
931ITEM* OPTIMIZER::findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const
932{
933 JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
934
935 if( !jt )
936 return nullptr;
937
938 for( ITEM* item : jt->LinkList() )
939 {
940 if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
941 return item;
942 }
943
944 return nullptr;
945}
946
947
948int OPTIMIZER::smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex )
949{
950 DIRECTION_45 dir;
951
952 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
954
955 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
956 std::vector<RtVariant> variants;
957
958 SOLID* solid = dyn_cast<SOLID*>( aPad );
959
960 // don't do optimized connections for offset pads
961 if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
962 return -1;
963
964 // don't do optimization on vias, they are always round at the moment and the optimizer
965 // will possibly mess up an intended via exit posture
966 if( aPad->Kind() == ITEM::VIA_T )
967 return -1;
968
969 BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
970 SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
971 int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
972
973 // Start at 1 to find a potentially better breakout (0 is the pad connection)
974 for( int p = 1; p <= p_end; p++ )
975 {
976 // If the line is contained inside the pad, don't optimize
977 if( solid && solid->Shape() && !solid->Shape()->Collide(
978 SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
979 {
980 continue;
981 }
982
983 for( SHAPE_LINE_CHAIN & breakout : breakouts )
984 {
985 for( int diag = 0; diag < 2; diag++ )
986 {
989 breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
990
991 DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
992
993 if( !connect.SegmentCount() )
994 continue;
995
996 int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
997
998 if( ang1 & ForbiddenAngles )
999 continue;
1000
1001 if( breakout.Length() > line.Length() )
1002 continue;
1003
1004 v = breakout;
1005 v.Append( connect );
1006
1007 for( int i = p + 1; i < line.PointCount(); i++ )
1008 v.Append( line.CPoint( i ) );
1009
1010 LINE tmp( *aLine, v );
1011 int cc = tmp.CountCorners( ForbiddenAngles );
1012
1013 if( cc == 0 )
1014 {
1015 RtVariant vp;
1016 std::get<0>( vp ) = p;
1017 std::get<1>( vp ) = breakout.Length();
1018 std::get<2>( vp ) = aEnd ? v.Reverse() : v;
1019 std::get<2>( vp ).Simplify();
1020 variants.push_back( vp );
1021 }
1022 }
1023 }
1024 }
1025
1026 // We attempt to minimize the corner cost (minimizes the segments and types of corners)
1027 // but given two, equally valid costs, we want to pick the longer pad exit. The logic
1028 // here is that if the pad is oblong, the track should not exit the shorter side and parallel
1029 // the pad but should follow the pad's preferential direction before exiting.
1030 // The baseline guess is to start with the existing line the user has drawn.
1031 int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
1032 long long int max_length = 0;
1033 bool found = false;
1034 int p_best = -1;
1035 SHAPE_LINE_CHAIN l_best;
1036
1037 for( RtVariant& vp : variants )
1038 {
1039 LINE tmp( *aLine, std::get<2>( vp ) );
1040 int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
1041 long long int len = std::get<1>( vp );
1042
1043 if( !checkColliding( &tmp ) )
1044 {
1045 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1046 {
1047 l_best = std::get<2>( vp );
1048 p_best = std::get<0>( vp );
1049 found = true;
1050
1051 if( cost <= min_cost )
1052 max_length = std::max<int>( len, max_length );
1053
1054 min_cost = std::min( cost, min_cost );
1055 }
1056 }
1057 }
1058
1059 if( found )
1060 {
1061 aLine->SetShape( l_best );
1062 return p_best;
1063 }
1064
1065 return -1;
1066}
1067
1068
1070{
1071 SHAPE_LINE_CHAIN& line = aLine->Line();
1072
1073 if( line.PointCount() < 3 )
1074 return false;
1075
1076 VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
1077
1078 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1079 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1080
1081 int vtx = -1;
1082
1083 if( startPad )
1084 vtx = smartPadsSingle( aLine, startPad, false, 3 );
1085
1086 if( endPad )
1087 smartPadsSingle( aLine, endPad, true,
1088 vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1089
1090 aLine->Line().Simplify();
1091
1092 return true;
1093}
1094
1095
1096bool OPTIMIZER::Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld, const VECTOR2I& aV )
1097{
1098 OPTIMIZER opt( aWorld );
1099
1100 opt.SetEffortLevel( aEffortLevel );
1101 opt.SetCollisionMask( -1 );
1102
1103 if( aEffortLevel & OPTIMIZER::PRESERVE_VERTEX )
1104 opt.SetPreserveVertex( aV );
1105
1106 return opt.Optimize( aLine );
1107}
1108
1109
1111{
1112 if( aLine->PointCount() < 3 )
1113 return false;
1114
1115 VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
1116
1117 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1118 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1119
1120 int thr = aLine->Width() * 10;
1121 int len = aLine->CLine().Length();
1122
1123 if( !startPad )
1124 return false;
1125
1126 bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1127 bool endMatch = false;
1128
1129 if(endPad)
1130 {
1131 endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1132 }
1133 else
1134 {
1135 endMatch = aLine->EndsWithVia();
1136 }
1137
1138 if( startMatch && endMatch && len < thr )
1139 {
1140 for( int i = 0; i < 2; i++ )
1141 {
1142 SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1143 LINE repl;
1144 repl = LINE( *aLine, l2 );
1145
1146 if( !m_world->CheckColliding( &repl ) )
1147 {
1148 aLine->SetShape( repl.CLine() );
1149 return true;
1150 }
1151 }
1152 }
1153
1154 return false;
1155}
1156
1157
1158int findCoupledVertices( const VECTOR2I& aVertex, const SEG& aOrigSeg,
1159 const SHAPE_LINE_CHAIN& aCoupled, DIFF_PAIR* aPair, int* aIndices )
1160{
1161 int count = 0;
1162
1163 for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1164 {
1165 SEG s = aCoupled.CSegment( i );
1166 VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1167
1168 if( s.ApproxParallel( aOrigSeg ) )
1169 {
1170 int64_t dist =
1171 int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Width();
1172
1173 if( aPair->GapConstraint().Matches( dist ) )
1174 {
1175 *aIndices++ = i;
1176 count++;
1177 }
1178 }
1179 }
1180
1181 return count;
1182}
1183
1184
1185bool verifyDpBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aNewRef,
1186 const SHAPE_LINE_CHAIN& aNewCoupled )
1187{
1188 LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1189 LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1190
1191 if( refLine.Collide( &coupledLine, aNode ) )
1192 return false;
1193
1194 if( aNode->CheckColliding ( &refLine ) )
1195 return false;
1196
1197 if( aNode->CheckColliding ( &coupledLine ) )
1198 return false;
1199
1200 return true;
1201}
1202
1203
1204bool coupledBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aRef,
1205 const SHAPE_LINE_CHAIN& aRefBypass, const SHAPE_LINE_CHAIN& aCoupled,
1206 SHAPE_LINE_CHAIN& aNewCoupled )
1207{
1208 int vStartIdx[1024]; // fixme: possible overflow
1209 int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ),
1210 aRefBypass.CSegment( 0 ),
1211 aCoupled, aPair, vStartIdx );
1212 DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1213
1214 int64_t bestLength = -1;
1215 bool found = false;
1216 SHAPE_LINE_CHAIN bestBypass;
1217 int si, ei;
1218
1219 for( int i=0; i< nStarts; i++ )
1220 {
1221 for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1222 {
1223 int delta = std::abs ( vStartIdx[i] - j );
1224
1225 if( delta > 1 )
1226 {
1227 const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1228 SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j),
1229 dir.IsDiagonal() );
1230
1231 int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1232
1233 SHAPE_LINE_CHAIN newCoupled = aCoupled;
1234
1235 si = vStartIdx[i];
1236 ei = j;
1237
1238 if(si < ei)
1239 newCoupled.Replace( si, ei, bypass );
1240 else
1241 newCoupled.Replace( ei, si, bypass.Reverse() );
1242
1243 if( coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1244 newCoupled) )
1245 {
1246 bestBypass = newCoupled;
1247 bestLength = coupledLength;
1248 found = true;
1249 }
1250 }
1251 }
1252 }
1253
1254 if( found )
1255 aNewCoupled = bestBypass;
1256
1257 return found;
1258}
1259
1260
1261bool checkDpColliding( NODE* aNode, DIFF_PAIR* aPair, bool aIsP, const SHAPE_LINE_CHAIN& aPath )
1262{
1263 LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1264
1265 return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1266}
1267
1268
1269bool OPTIMIZER::mergeDpStep( DIFF_PAIR* aPair, bool aTryP, int step )
1270{
1271 int n = 1;
1272
1273 SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1274 SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1275
1276 int n_segs = currentPath.SegmentCount() - 1;
1277
1278 int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1279 int64_t budget = clenPre / 10; // fixme: come up with something more intelligent here...
1280
1281 while( n < n_segs - step )
1282 {
1283 const SEG s1 = currentPath.CSegment( n );
1284 const SEG s2 = currentPath.CSegment( n + step );
1285
1286 DIRECTION_45 dir1( s1 );
1287 DIRECTION_45 dir2( s2 );
1288
1289 if( dir1.IsObtuse( dir2 ) )
1290 {
1292 dir1.IsDiagonal() );
1293 SHAPE_LINE_CHAIN newRef;
1294 SHAPE_LINE_CHAIN newCoup;
1295 int64_t deltaCoupled = -1, deltaUni = -1;
1296
1297 newRef = currentPath;
1298 newRef.Replace( s1.Index(), s2.Index(), bypass );
1299
1300 deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1301
1302 if( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1303 {
1304 deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1305
1306 if( deltaCoupled >= 0 )
1307 {
1308 newRef.Simplify();
1309 newCoup.Simplify();
1310
1311 aPair->SetShape( newRef, newCoup, !aTryP );
1312 return true;
1313 }
1314 }
1315 else if( deltaUni >= 0 && verifyDpBypass( m_world, aPair, aTryP, newRef, coupledPath ) )
1316 {
1317 newRef.Simplify();
1318 coupledPath.Simplify();
1319
1320 aPair->SetShape( newRef, coupledPath, !aTryP );
1321 return true;
1322 }
1323 }
1324
1325 n++;
1326 }
1327
1328 return false;
1329}
1330
1331
1333{
1334 int step_p = aPair->CP().SegmentCount() - 2;
1335 int step_n = aPair->CN().SegmentCount() - 2;
1336
1337 while( 1 )
1338 {
1339 int n_segs_p = aPair->CP().SegmentCount();
1340 int n_segs_n = aPair->CN().SegmentCount();
1341
1342 int max_step_p = n_segs_p - 2;
1343 int max_step_n = n_segs_n - 2;
1344
1345 if( step_p > max_step_p )
1346 step_p = max_step_p;
1347
1348 if( step_n > max_step_n )
1349 step_n = max_step_n;
1350
1351 if( step_p < 1 && step_n < 1 )
1352 break;
1353
1354 bool found_anything_p = false;
1355 bool found_anything_n = false;
1356
1357 if( step_p > 1 )
1358 found_anything_p = mergeDpStep( aPair, true, step_p );
1359
1360 if( step_n > 1 )
1361 found_anything_n = mergeDpStep( aPair, false, step_n );
1362
1363 if( !found_anything_n && !found_anything_p )
1364 {
1365 step_n--;
1366 step_p--;
1367 }
1368 }
1369 return true;
1370}
1371
1372
1374{
1375 return mergeDpSegments( aPair );
1376}
1377
1378
1379static int64_t shovedArea( const SHAPE_LINE_CHAIN& aOld, const SHAPE_LINE_CHAIN& aNew )
1380{
1381 int64_t area = 0;
1382 const int oc = aOld.PointCount();
1383 const int nc = aNew.PointCount();
1384 const int total = oc + nc;
1385
1386 for(int i = 0; i < total; i++)
1387 {
1388 int i_next = (i + 1 == total ? 0 : i + 1);
1389
1390 const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1391 : aNew.CPoint( nc - 1 - (i - oc) );
1392 const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1393 : aNew.CPoint( nc - 1 - (i_next - oc) );
1394 area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1395 }
1396
1397 return std::abs( area / 2 );
1398}
1399
1400
1401bool tightenSegment( bool dir, NODE *aNode, const LINE& cur, const SHAPE_LINE_CHAIN& in,
1402 SHAPE_LINE_CHAIN& out )
1403{
1404 SEG a = in.CSegment(0);
1405 SEG center = in.CSegment(1);
1406 SEG b = in.CSegment(2);
1407
1408 DIRECTION_45 dirA ( a );
1409 DIRECTION_45 dirCenter ( center );
1410 DIRECTION_45 dirB ( b );
1411
1412 if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1413 return false;
1414
1415 //VECTOR2I perp = (center.B - center.A).Perpendicular();
1416 VECTOR2I guideA, guideB ;
1417
1418 SEG guide;
1419 int initial;
1420
1421 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1422 if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1423 return false;
1424
1425 {
1426 /*
1427 auto rC = *a.IntersectLines( b );
1428 dbg->AddSegment ( SEG( center.A, rC ), 1 );
1429 dbg->AddSegment ( SEG( center.B, rC ), 2 );
1430 auto perp = dirCenter.Left().Left();
1431
1432 SEG sperp ( center.A, center.A + perp.ToVector() );
1433
1434 auto vpc = sperp.LineProject( rC );
1435 auto vpa = sperp.LineProject( a.A );
1436 auto vpb = sperp.LineProject( b.B );
1437
1438 auto da = (vpc - vpa).EuclideanNorm();
1439 auto db = (vpc - vpb).EuclideanNorm();
1440
1441 auto vp = (da < db) ? vpa : vpb;
1442 dbg->AddSegment ( SEG( vpc, vp ), 5 );
1443
1444
1445 guide = SEG ( vpc, vp );
1446 */
1447 }
1448
1449 int da = a.Length();
1450 int db = b.Length();
1451
1452 if( da < db )
1453 guide = a;
1454 else
1455 guide = b;
1456
1457 initial = guide.Length();
1458
1459 int step = initial;
1460 int current = step;
1461 SHAPE_LINE_CHAIN snew;
1462
1463 while( step > 1 )
1464 {
1465 LINE l( cur );
1466
1467 snew.Clear();
1468 snew.Append( a.A );
1469 snew.Append( a.B + ( a.A - a.B ).Resize( current ) );
1470 snew.Append( b.A + ( b.B - b.A ).Resize( current ) );
1471 snew.Append( b.B );
1472
1473 step /= 2;
1474
1475 l.SetShape(snew);
1476
1477 if( aNode->CheckColliding(&l) )
1478 current -= step;
1479 else if ( current + step >= initial )
1480 current = initial;
1481 else
1482 current += step;
1483
1484 //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1485 //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1486 //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1487
1488 if ( current == initial )
1489 break;
1490
1491
1492 }
1493
1494 out = snew;
1495
1496 //dbg->AddLine ( snew, 3, 100000 );
1497
1498 return true;
1499}
1500
1501
1502void Tighten( NODE *aNode, const SHAPE_LINE_CHAIN& aOldLine, const LINE& aNewLine,
1503 LINE& aOptimized )
1504{
1505 LINE tmp;
1506
1507 if( aNewLine.SegmentCount() < 3 )
1508 return;
1509
1510 SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1511
1512 for( int step = 0; step < 3; step++ )
1513 {
1514 current.Simplify();
1515
1516 for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1517 {
1518 SHAPE_LINE_CHAIN l_in, l_out;
1519
1520 l_in = current.Slice( i, i + 3 );
1521
1522 for( int dir = 0; dir <= 1; dir++ )
1523 {
1524 if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1525 {
1526 SHAPE_LINE_CHAIN opt = current;
1527 opt.Replace( i, i + 3, l_out );
1528 auto optArea = std::abs( shovedArea( aOldLine, opt ) );
1529 auto prevArea = std::abs( shovedArea( aOldLine, current ) );
1530
1531 if( optArea < prevArea )
1532 current = opt;
1533
1534 break;
1535 }
1536 }
1537 }
1538 }
1539
1540 aOptimized = LINE( aNewLine, current );
1541
1542 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1543 //dbg->AddLine ( current, 4, 100000 );
1544}
1545
1546}
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetWidth() const
Definition: box2.h:187
bool Contains(const Vec &aPoint) const
Definition: box2.h:141
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:37
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:181
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
Definition: direction45.h:213
bool IsObtuse(const DIRECTION_45 &aOther) const
Definition: direction45.h:203
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
Calculate the cost of a given line, taking corner angles and total length into account.
Definition: pns_optimizer.h:49
static int CornerCost(const SHAPE_LINE_CHAIN &aLine)
void Replace(const LINE &aOldLine, const LINE &aNewLine)
void Remove(const LINE &aLine)
void Add(const LINE &aLine)
static int CornerCost(const SEG &aA, const SEG &aB)
bool IsBetter(const COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
Basic class for a differential pair.
const SHAPE_LINE_CHAIN & CN() const
int Width() const
const RANGED_NUM< int > GapConstraint() const
double CoupledLength() const
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
const SHAPE_LINE_CHAIN & CP() const
Base class for PNS router board items.
Definition: pns_item.h:56
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true, int aOverrideClearance=-1) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:169
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:132
virtual int Layer() const
Definition: pns_item.h:160
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:202
@ SOLID_T
Definition: pns_item.h:63
@ LINE_T
Definition: pns_item.h:64
const LAYER_RANGE & Layers() const
Definition: pns_item.h:156
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:140
int Net() const
Definition: pns_item.h:154
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 LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:241
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
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:150
int ArcCount() const
Definition: pns_line.h:146
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
int CountCorners(int aAngles) const
Definition: pns_line.cpp:135
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:142
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:141
int SegmentCount() const
Definition: pns_line.h:144
int PointCount() const
Definition: pns_line.h:145
bool EndsWithVia() const
Definition: pns_line.h:194
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:151
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:161
Keep the router "world" - i.e.
Definition: pns_node.h:156
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:472
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1597
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1197
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:95
void SetPreserveVertex(const VECTOR2I &aV)
std::pair< int, int > m_restrictedVertexRange
std::vector< OPT_CONSTRAINT * > m_constraints
~OPTIMIZER()
A quick shortcut to optimize a line without creating and setting up an optimizer.
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
bool mergeColinear(LINE *aLine)
void cacheAdd(ITEM *aItem, bool aIsStatic)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
bool m_restrictAreaIsStrict
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
bool fanoutCleanup(LINE *aLine)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
bool mergeFull(LINE *aLine)
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
void AddConstraint(OPT_CONSTRAINT *aConstraint)
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
void CacheRemove(ITEM *aItem)
bool mergeObtuse(LINE *aLine)
void SetCollisionMask(int aMask)
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
OPTIMIZER(NODE *aWorld)
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
bool runSmartPads(LINE *aLine)
bool mergeDpSegments(DIFF_PAIR *aPair)
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
void SetEffortLevel(int aEffort)
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
VECTOR2I m_preservedVertex
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
void ClearCache(bool aStaticOnly=false)
@ LIMIT_CORNER_COUNT
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
@ SMART_PADS
Reroute pad exits.
@ FANOUT_CLEANUP
Simplify pad-pad and pad-via connections if possible.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
@ MERGE_COLINEAR
Merge co-linear segments.
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
SHAPE_INDEX_LIST< ITEM * > m_cache
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:214
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_solid.h:78
VECTOR2I Offset() const
Definition: pns_solid.h:116
bool Matches(const T &aOther) const
Definition: ranged_num.h:43
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
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:344
int Length() const
Return the length (this).
Definition: seg.h:326
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:393
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:269
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
ecoord SquaredLength() const
Definition: seg.h:331
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:302
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:95
int GetRadius() const
Definition: shape_circle.h:108
const VECTOR2I GetCenter() const
Definition: shape_circle.h:113
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
bool IsPtOnArc(size_t aPtIndex) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
bool IsClosed() const override
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
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.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
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.
int SegmentCount() const
Return the number of segments in this line chain.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:127
const VECTOR2I GetSize() const
Definition: shape_rect.h:135
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
Definition: shape_simple.h:42
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
Definition: shape_simple.h:124
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_simple.h:78
An abstract shape on 2D plane.
Definition: shape.h:123
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:178
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:378
T y
Definition: vector3.h:62
T x
Definition: vector3.h:61
@ BLUE
Definition: color4d.h:56
@ YELLOW
Definition: color4d.h:67
static constexpr EDA_ANGLE & ANGLE_360
Definition: eda_angle.h:418
static constexpr EDA_ANGLE & ANGLE_45
Definition: eda_angle.h:413
static constexpr EDA_ANGLE & ANGLE_90
Definition: eda_angle.h:414
static constexpr EDA_ANGLE & ANGLE_0
Definition: eda_angle.h:412
Push and Shove diff pair dimensions (gap) settings dialog.
bool tightenSegment(bool dir, NODE *aNode, const LINE &cur, const SHAPE_LINE_CHAIN &in, SHAPE_LINE_CHAIN &out)
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:345
int findCoupledVertices(const VECTOR2I &aVertex, const SEG &aOrigSeg, const SHAPE_LINE_CHAIN &aCoupled, DIFF_PAIR *aPair, int *aIndices)
bool coupledBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aRef, const SHAPE_LINE_CHAIN &aRefBypass, const SHAPE_LINE_CHAIN &aCoupled, SHAPE_LINE_CHAIN &aNewCoupled)
void Tighten(NODE *aNode, const SHAPE_LINE_CHAIN &aOldLine, const LINE &aNewLine, LINE &aOptimized)
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
bool checkDpColliding(NODE *aNode, DIFF_PAIR *aPair, bool aIsP, const SHAPE_LINE_CHAIN &aPath)
static bool pointInside2(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aP)
Determine if a point is located within a given polygon.
static int64_t shovedArea(const SHAPE_LINE_CHAIN &aOld, const SHAPE_LINE_CHAIN &aNew)
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401
#define PNS_DBG(dbg, method,...)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
@ SH_RECT
axis-aligned rectangle
Definition: shape.h:44
@ SH_CIRCLE
circle
Definition: shape.h:47
@ SH_SIMPLE
simple polygon
Definition: shape.h:48
@ SH_SEGMENT
line segment
Definition: shape.h:45
bool operator()(ITEM *aOtherItem)
CACHE_VISITOR(const ITEM *aOurItem, NODE *aNode, int aMask)
VECTOR3I v1(5, 5, 5)
constexpr int delta
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:183
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618