KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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 ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
728 }
729
730 if( ok )
731 {
732 path[i] = aCurrentPath;
733 path[i].Replace( s1.Index(), s2.Index(), bypass );
734 path[i].Simplify();
735 cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
736 }
737 }
738
739 if( cost[0] < cost_orig && cost[0] < cost[1] )
740 picked = &path[0];
741 else if( cost[1] < cost_orig )
742 picked = &path[1];
743
744 if( picked )
745 {
746 n_segs = aCurrentPath.SegmentCount();
747 aCurrentPath = *picked;
748 return true;
749 }
750 }
751
752 return false;
753}
754
755
757 bool aPermitDiagonal ) const
758{
759 BREAKOUT_LIST breakouts;
760
762 {
763 const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
765 VECTOR2I p0 = cir->GetCenter();
766 VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
767
768 RotatePoint( v0, -angle );
769
770 l.Append( p0 );
771 l.Append( p0 + v0 );
772 breakouts.push_back( l );
773 }
774
775 return breakouts;
776}
777
778
780 bool aPermitDiagonal ) const
781{
782 BREAKOUT_LIST breakouts;
783 const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
784
785 BOX2I bbox = convex->BBox( 0 );
786 VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
787 // must be large enough to guarantee intersecting the convex polygon
788 int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
789 EDA_ANGLE increment = ( aPermitDiagonal ? ANGLE_45 : ANGLE_90 );
790
791 for( EDA_ANGLE angle = ANGLE_0; angle < ANGLE_360; angle += increment )
792 {
794 VECTOR2I v0( p0 + VECTOR2I( length, 0 ) );
795 RotatePoint( v0, p0, -angle );
796
798 int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
799
800 // if n == 1 intersected a segment
801 // if n == 2 intersected the common point of 2 segments
802 // n == 0 can not happen I think, but...
803 if( n > 0 )
804 {
805 l.Append( p0 );
806
807 // for a breakout distance relative to the distance between
808 // center and polygon edge
809 //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
810
811 // for an absolute breakout distance, e.g. 0.1 mm
812 //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
813
814 // for the breakout right on the polygon edge
815 l.Append( intersections[0].p );
816
817 breakouts.push_back( l );
818 }
819 }
820
821 return breakouts;
822}
823
824
826 bool aPermitDiagonal ) const
827{
828 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
829 VECTOR2I s = rect->GetSize();
830 VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
831
832 BREAKOUT_LIST breakouts;
833 breakouts.reserve( 12 );
834
835 VECTOR2I d_offset;
836
837 d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
838 d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
839
840 VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
841 VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
842
843 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
844 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
845 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
846 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
847
848 if( aPermitDiagonal )
849 {
850 int l = aWidth + std::min( s.x, s.y ) / 2;
851 VECTOR2I d_diag;
852
853 if( s.x >= s.y )
854 {
855 breakouts.emplace_back(
856 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
857 breakouts.emplace_back(
858 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
859 breakouts.emplace_back(
860 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
861 breakouts.emplace_back(
862 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
863 }
864 else
865 {
866 // fixme: this could be done more efficiently
867 breakouts.emplace_back(
868 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
869 breakouts.emplace_back(
870 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
871 breakouts.emplace_back(
872 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
873 breakouts.emplace_back(
874 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
875 }
876 }
877
878 return breakouts;
879}
880
881
883 bool aPermitDiagonal ) const
884{
885 switch( aItem->Kind() )
886 {
887 case ITEM::VIA_T:
888 {
889 const VIA* via = static_cast<const VIA*>( aItem );
890 return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
891 }
892
893 case ITEM::SOLID_T:
894 {
895 const SHAPE* shape = aItem->Shape();
896
897 switch( shape->Type() )
898 {
899 case SH_RECT:
900 return rectBreakouts( aWidth, shape, aPermitDiagonal );
901
902 case SH_SEGMENT:
903 {
904 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
905 const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
906 return rectBreakouts( aWidth, &rect, aPermitDiagonal );
907 }
908
909 case SH_CIRCLE:
910 return circleBreakouts( aWidth, shape, aPermitDiagonal );
911
912 case SH_SIMPLE:
913 return customBreakouts( aWidth, aItem, aPermitDiagonal );
914
915 default:
916 break;
917 }
918
919 break;
920 }
921
922 default:
923 break;
924 }
925
926 return BREAKOUT_LIST();
927}
928
929
930ITEM* OPTIMIZER::findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const
931{
932 const JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
933
934 if( !jt )
935 return nullptr;
936
937 for( ITEM* item : jt->LinkList() )
938 {
939 if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
940 return item;
941 }
942
943 return nullptr;
944}
945
946
947int OPTIMIZER::smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex )
948{
949 DIRECTION_45 dir;
950
951 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
953
954 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
955 std::vector<RtVariant> variants;
956
957 SOLID* solid = dyn_cast<SOLID*>( aPad );
958
959 // don't do optimized connections for offset pads
960 if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
961 return -1;
962
963 // don't do optimization on vias, they are always round at the moment and the optimizer
964 // will possibly mess up an intended via exit posture
965 if( aPad->Kind() == ITEM::VIA_T )
966 return -1;
967
968 BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
969 SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
970 int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
971
972 // Start at 1 to find a potentially better breakout (0 is the pad connection)
973 for( int p = 1; p <= p_end; p++ )
974 {
975 // If the line is contained inside the pad, don't optimize
976 if( solid && solid->Shape() && !solid->Shape()->Collide(
977 SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
978 {
979 continue;
980 }
981
982 for( SHAPE_LINE_CHAIN & breakout : breakouts )
983 {
984 for( int diag = 0; diag < 2; diag++ )
985 {
988 breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
989
990 DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
991
992 if( !connect.SegmentCount() )
993 continue;
994
995 int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
996
997 if( ang1 & ForbiddenAngles )
998 continue;
999
1000 if( breakout.Length() > line.Length() )
1001 continue;
1002
1003 v = breakout;
1004 v.Append( connect );
1005
1006 for( int i = p + 1; i < line.PointCount(); i++ )
1007 v.Append( line.CPoint( i ) );
1008
1009 LINE tmp( *aLine, v );
1010 int cc = tmp.CountCorners( ForbiddenAngles );
1011
1012 if( cc == 0 )
1013 {
1014 RtVariant vp;
1015 std::get<0>( vp ) = p;
1016 std::get<1>( vp ) = breakout.Length();
1017 std::get<2>( vp ) = aEnd ? v.Reverse() : v;
1018 std::get<2>( vp ).Simplify();
1019 variants.push_back( vp );
1020 }
1021 }
1022 }
1023 }
1024
1025 // We attempt to minimize the corner cost (minimizes the segments and types of corners)
1026 // but given two, equally valid costs, we want to pick the longer pad exit. The logic
1027 // here is that if the pad is oblong, the track should not exit the shorter side and parallel
1028 // the pad but should follow the pad's preferential direction before exiting.
1029 // The baseline guess is to start with the existing line the user has drawn.
1030 int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
1031 long long int max_length = 0;
1032 bool found = false;
1033 int p_best = -1;
1034 SHAPE_LINE_CHAIN l_best;
1035
1036 for( RtVariant& vp : variants )
1037 {
1038 LINE tmp( *aLine, std::get<2>( vp ) );
1039 int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
1040 long long int len = std::get<1>( vp );
1041
1042 if( !checkColliding( &tmp ) )
1043 {
1044 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1045 {
1046 l_best = std::get<2>( vp );
1047 p_best = std::get<0>( vp );
1048 found = true;
1049
1050 if( cost <= min_cost )
1051 max_length = std::max<int>( len, max_length );
1052
1053 min_cost = std::min( cost, min_cost );
1054 }
1055 }
1056 }
1057
1058 if( found )
1059 {
1060 aLine->SetShape( l_best );
1061 return p_best;
1062 }
1063
1064 return -1;
1065}
1066
1067
1069{
1070 SHAPE_LINE_CHAIN& line = aLine->Line();
1071
1072 if( line.PointCount() < 3 )
1073 return false;
1074
1075 VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
1076
1077 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1078 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1079
1080 int vtx = -1;
1081
1082 if( startPad )
1083 vtx = smartPadsSingle( aLine, startPad, false, 3 );
1084
1085 if( endPad )
1086 smartPadsSingle( aLine, endPad, true,
1087 vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1088
1089 aLine->Line().Simplify();
1090
1091 return true;
1092}
1093
1094
1095bool OPTIMIZER::Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld, const VECTOR2I& aV )
1096{
1097 OPTIMIZER opt( aWorld );
1098
1099 opt.SetEffortLevel( aEffortLevel );
1100 opt.SetCollisionMask( -1 );
1101
1102 if( aEffortLevel & OPTIMIZER::PRESERVE_VERTEX )
1103 opt.SetPreserveVertex( aV );
1104
1105 return opt.Optimize( aLine );
1106}
1107
1108
1110{
1111 if( aLine->PointCount() < 3 )
1112 return false;
1113
1114 VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
1115
1116 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1117 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1118
1119 int thr = aLine->Width() * 10;
1120 int len = aLine->CLine().Length();
1121
1122 if( !startPad )
1123 return false;
1124
1125 bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1126 bool endMatch = false;
1127
1128 if(endPad)
1129 {
1130 endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1131 }
1132 else
1133 {
1134 endMatch = aLine->EndsWithVia();
1135 }
1136
1137 if( startMatch && endMatch && len < thr )
1138 {
1139 for( int i = 0; i < 2; i++ )
1140 {
1141 SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1142 LINE repl;
1143 repl = LINE( *aLine, l2 );
1144
1145 if( !m_world->CheckColliding( &repl ) )
1146 {
1147 aLine->SetShape( repl.CLine() );
1148 return true;
1149 }
1150 }
1151 }
1152
1153 return false;
1154}
1155
1156
1157int findCoupledVertices( const VECTOR2I& aVertex, const SEG& aOrigSeg,
1158 const SHAPE_LINE_CHAIN& aCoupled, DIFF_PAIR* aPair, int* aIndices )
1159{
1160 int count = 0;
1161
1162 for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1163 {
1164 SEG s = aCoupled.CSegment( i );
1165 VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1166
1167 if( s.ApproxParallel( aOrigSeg ) )
1168 {
1169 int64_t dist =
1170 int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Width();
1171
1172 if( aPair->GapConstraint().Matches( dist ) )
1173 {
1174 *aIndices++ = i;
1175 count++;
1176 }
1177 }
1178 }
1179
1180 return count;
1181}
1182
1183
1184bool verifyDpBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aNewRef,
1185 const SHAPE_LINE_CHAIN& aNewCoupled )
1186{
1187 LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1188 LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1189
1190 if( refLine.Collide( &coupledLine, aNode ) )
1191 return false;
1192
1193 if( aNode->CheckColliding ( &refLine ) )
1194 return false;
1195
1196 if( aNode->CheckColliding ( &coupledLine ) )
1197 return false;
1198
1199 return true;
1200}
1201
1202
1203bool coupledBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aRef,
1204 const SHAPE_LINE_CHAIN& aRefBypass, const SHAPE_LINE_CHAIN& aCoupled,
1205 SHAPE_LINE_CHAIN& aNewCoupled )
1206{
1207 int vStartIdx[1024]; // fixme: possible overflow
1208 int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ),
1209 aRefBypass.CSegment( 0 ),
1210 aCoupled, aPair, vStartIdx );
1211 DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1212
1213 int64_t bestLength = -1;
1214 bool found = false;
1215 SHAPE_LINE_CHAIN bestBypass;
1216 int si, ei;
1217
1218 for( int i=0; i< nStarts; i++ )
1219 {
1220 for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1221 {
1222 int delta = std::abs ( vStartIdx[i] - j );
1223
1224 if( delta > 1 )
1225 {
1226 const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1227 SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j),
1228 dir.IsDiagonal() );
1229
1230 int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1231
1232 SHAPE_LINE_CHAIN newCoupled = aCoupled;
1233
1234 si = vStartIdx[i];
1235 ei = j;
1236
1237 if(si < ei)
1238 newCoupled.Replace( si, ei, bypass );
1239 else
1240 newCoupled.Replace( ei, si, bypass.Reverse() );
1241
1242 if( coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1243 newCoupled) )
1244 {
1245 bestBypass = newCoupled;
1246 bestLength = coupledLength;
1247 found = true;
1248 }
1249 }
1250 }
1251 }
1252
1253 if( found )
1254 aNewCoupled = bestBypass;
1255
1256 return found;
1257}
1258
1259
1260bool checkDpColliding( NODE* aNode, DIFF_PAIR* aPair, bool aIsP, const SHAPE_LINE_CHAIN& aPath )
1261{
1262 LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1263
1264 return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1265}
1266
1267
1268bool OPTIMIZER::mergeDpStep( DIFF_PAIR* aPair, bool aTryP, int step )
1269{
1270 int n = 1;
1271
1272 SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1273 SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1274
1275 int n_segs = currentPath.SegmentCount() - 1;
1276
1277 int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1278 int64_t budget = clenPre / 10; // fixme: come up with something more intelligent here...
1279
1280 while( n < n_segs - step )
1281 {
1282 const SEG s1 = currentPath.CSegment( n );
1283 const SEG s2 = currentPath.CSegment( n + step );
1284
1285 DIRECTION_45 dir1( s1 );
1286 DIRECTION_45 dir2( s2 );
1287
1288 if( dir1.IsObtuse( dir2 ) )
1289 {
1291 dir1.IsDiagonal() );
1292 SHAPE_LINE_CHAIN newRef;
1293 SHAPE_LINE_CHAIN newCoup;
1294 int64_t deltaCoupled = -1, deltaUni = -1;
1295
1296 newRef = currentPath;
1297 newRef.Replace( s1.Index(), s2.Index(), bypass );
1298
1299 deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1300
1301 if( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1302 {
1303 deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1304
1305 if( deltaCoupled >= 0 )
1306 {
1307 newRef.Simplify();
1308 newCoup.Simplify();
1309
1310 aPair->SetShape( newRef, newCoup, !aTryP );
1311 return true;
1312 }
1313 }
1314 else if( deltaUni >= 0 && verifyDpBypass( m_world, aPair, aTryP, newRef, coupledPath ) )
1315 {
1316 newRef.Simplify();
1317 coupledPath.Simplify();
1318
1319 aPair->SetShape( newRef, coupledPath, !aTryP );
1320 return true;
1321 }
1322 }
1323
1324 n++;
1325 }
1326
1327 return false;
1328}
1329
1330
1332{
1333 int step_p = aPair->CP().SegmentCount() - 2;
1334 int step_n = aPair->CN().SegmentCount() - 2;
1335
1336 while( 1 )
1337 {
1338 int n_segs_p = aPair->CP().SegmentCount();
1339 int n_segs_n = aPair->CN().SegmentCount();
1340
1341 int max_step_p = n_segs_p - 2;
1342 int max_step_n = n_segs_n - 2;
1343
1344 if( step_p > max_step_p )
1345 step_p = max_step_p;
1346
1347 if( step_n > max_step_n )
1348 step_n = max_step_n;
1349
1350 if( step_p < 1 && step_n < 1 )
1351 break;
1352
1353 bool found_anything_p = false;
1354 bool found_anything_n = false;
1355
1356 if( step_p > 1 )
1357 found_anything_p = mergeDpStep( aPair, true, step_p );
1358
1359 if( step_n > 1 )
1360 found_anything_n = mergeDpStep( aPair, false, step_n );
1361
1362 if( !found_anything_n && !found_anything_p )
1363 {
1364 step_n--;
1365 step_p--;
1366 }
1367 }
1368 return true;
1369}
1370
1371
1373{
1374 return mergeDpSegments( aPair );
1375}
1376
1377
1378static int64_t shovedArea( const SHAPE_LINE_CHAIN& aOld, const SHAPE_LINE_CHAIN& aNew )
1379{
1380 int64_t area = 0;
1381 const int oc = aOld.PointCount();
1382 const int nc = aNew.PointCount();
1383 const int total = oc + nc;
1384
1385 for(int i = 0; i < total; i++)
1386 {
1387 int i_next = (i + 1 == total ? 0 : i + 1);
1388
1389 const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1390 : aNew.CPoint( nc - 1 - (i - oc) );
1391 const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1392 : aNew.CPoint( nc - 1 - (i_next - oc) );
1393 area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1394 }
1395
1396 return std::abs( area / 2 );
1397}
1398
1399
1400bool tightenSegment( bool dir, NODE *aNode, const LINE& cur, const SHAPE_LINE_CHAIN& in,
1401 SHAPE_LINE_CHAIN& out )
1402{
1403 SEG a = in.CSegment(0);
1404 SEG center = in.CSegment(1);
1405 SEG b = in.CSegment(2);
1406
1407 DIRECTION_45 dirA ( a );
1408 DIRECTION_45 dirCenter ( center );
1409 DIRECTION_45 dirB ( b );
1410
1411 if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1412 return false;
1413
1414 //VECTOR2I perp = (center.B - center.A).Perpendicular();
1415 VECTOR2I guideA, guideB ;
1416
1417 SEG guide;
1418 int initial;
1419
1420 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1421 if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1422 return false;
1423
1424 {
1425 /*
1426 auto rC = *a.IntersectLines( b );
1427 dbg->AddSegment ( SEG( center.A, rC ), 1 );
1428 dbg->AddSegment ( SEG( center.B, rC ), 2 );
1429 auto perp = dirCenter.Left().Left();
1430
1431 SEG sperp ( center.A, center.A + perp.ToVector() );
1432
1433 auto vpc = sperp.LineProject( rC );
1434 auto vpa = sperp.LineProject( a.A );
1435 auto vpb = sperp.LineProject( b.B );
1436
1437 auto da = (vpc - vpa).EuclideanNorm();
1438 auto db = (vpc - vpb).EuclideanNorm();
1439
1440 auto vp = (da < db) ? vpa : vpb;
1441 dbg->AddSegment ( SEG( vpc, vp ), 5 );
1442
1443
1444 guide = SEG ( vpc, vp );
1445 */
1446 }
1447
1448 int da = a.Length();
1449 int db = b.Length();
1450
1451 if( da < db )
1452 guide = a;
1453 else
1454 guide = b;
1455
1456 initial = guide.Length();
1457
1458 int step = initial;
1459 int current = step;
1460 SHAPE_LINE_CHAIN snew;
1461
1462 while( step > 1 )
1463 {
1464 LINE l( cur );
1465
1466 snew.Clear();
1467 snew.Append( a.A );
1468 snew.Append( a.B + ( a.A - a.B ).Resize( current ) );
1469 snew.Append( b.A + ( b.B - b.A ).Resize( current ) );
1470 snew.Append( b.B );
1471
1472 step /= 2;
1473
1474 l.SetShape(snew);
1475
1476 if( aNode->CheckColliding(&l) )
1477 current -= step;
1478 else if ( current + step >= initial )
1479 current = initial;
1480 else
1481 current += step;
1482
1483 //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1484 //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1485 //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1486
1487 if ( current == initial )
1488 break;
1489
1490
1491 }
1492
1493 out = snew;
1494
1495 //dbg->AddLine ( snew, 3, 100000 );
1496
1497 return true;
1498}
1499
1500
1501void Tighten( NODE *aNode, const SHAPE_LINE_CHAIN& aOldLine, const LINE& aNewLine,
1502 LINE& aOptimized )
1503{
1504 LINE tmp;
1505
1506 if( aNewLine.SegmentCount() < 3 )
1507 return;
1508
1509 SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1510
1511 for( int step = 0; step < 3; step++ )
1512 {
1513 current.Simplify();
1514
1515 for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1516 {
1517 SHAPE_LINE_CHAIN l_in, l_out;
1518
1519 l_in = current.Slice( i, i + 3 );
1520
1521 for( int dir = 0; dir <= 1; dir++ )
1522 {
1523 if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1524 {
1525 SHAPE_LINE_CHAIN opt = current;
1526 opt.Replace( i, i + 3, l_out );
1527 auto optArea = std::abs( shovedArea( aOldLine, opt ) );
1528 auto prevArea = std::abs( shovedArea( aOldLine, current ) );
1529
1530 if( optArea < prevArea )
1531 current = opt;
1532
1533 break;
1534 }
1535 }
1536 }
1537 }
1538
1539 aOptimized = LINE( aNewLine, current );
1540
1541 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1542 //dbg->AddLine ( current, 4, 100000 );
1543}
1544
1545}
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:91
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:162
virtual int Layer() const
Definition: pns_item.h:195
virtual int Net() const
Definition: pns_item.h:189
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:220
@ SOLID_T
Definition: pns_item.h:98
@ LINE_T
Definition: pns_item.h:99
const LAYER_RANGE & Layers() const
Definition: pns_item.h:191
bool OfKind(int aKindMask) const
Definition: pns_item.h:170
bool Collide(const ITEM *aHead, const NODE *aNode, COLLISION_SEARCH_CONTEXT *aCtx=nullptr) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:237
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:239
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:144
int ArcCount() const
Definition: pns_line.h:140
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:125
int CountCorners(int aAngles) const
Definition: pns_line.cpp:155
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
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:145
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:155
Keep the router "world" - i.e.
Definition: pns_node.h:198
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:382
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1565
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet) const
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1158
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:215
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_solid.h:76
VECTOR2I Offset() const
Definition: pns_solid.h:104
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:403
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:312
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:96
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:124
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:179
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:350
T y
Definition: vector3.h:62
T x
Definition: vector3.h:61
@ BLUE
Definition: color4d.h:55
@ YELLOW
Definition: color4d.h:66
static constexpr EDA_ANGLE & ANGLE_360
Definition: eda_angle.h:435
static constexpr EDA_ANGLE & ANGLE_45
Definition: eda_angle.h:430
static constexpr EDA_ANGLE & ANGLE_90
Definition: eda_angle.h:431
static constexpr EDA_ANGLE & ANGLE_0
Definition: eda_angle.h:429
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:418
#define PNS_DBG(dbg, method,...)
@ SH_RECT
axis-aligned rectangle
Definition: shape.h:45
@ SH_CIRCLE
circle
Definition: shape.h:48
@ SH_SIMPLE
simple polygon
Definition: shape.h:49
@ SH_SEGMENT
line segment
Definition: shape.h:46
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:588