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