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 for( OPT_CONSTRAINT* c : m_constraints )
124 delete c;
125
126 m_constraints.clear();
127}
128
129
131{
132 CACHE_VISITOR( const ITEM* aOurItem, NODE* aNode, int aMask ) :
133 m_ourItem( aOurItem ),
134 m_collidingItem( nullptr ),
135 m_node( aNode ),
136 m_mask( aMask )
137 {}
138
139 bool operator()( ITEM* aOtherItem )
140 {
141 if( !( m_mask & aOtherItem->Kind() ) )
142 return true;
143
144 if( !aOtherItem->Collide( m_ourItem, m_node ) )
145 return true;
146
147 m_collidingItem = aOtherItem;
148 return false;
149 }
150
155};
156
157
158void OPTIMIZER::cacheAdd( ITEM* aItem, bool aIsStatic = false )
159{
160 if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
161 return;
162
163 m_cache.Add( aItem );
164 m_cacheTags[aItem].m_hits = 1;
165 m_cacheTags[aItem].m_isStatic = aIsStatic;
166}
167
168
169void OPTIMIZER::removeCachedSegments( LINE* aLine, int aStartVertex, int aEndVertex )
170{
171 if( !aLine->IsLinked() )
172 return;
173
174 auto links = aLine->Links();
175
176 if( aEndVertex < 0 )
177 aEndVertex += aLine->PointCount();
178
179 for( int i = aStartVertex; i < aEndVertex - 1; i++ )
180 {
181 LINKED_ITEM* s = links[i];
182 m_cacheTags.erase( s );
183 m_cache.Remove( s );
184 }
185}
186
187
189{
190 if( aItem->Kind() == ITEM::LINE_T )
191 removeCachedSegments( static_cast<LINE*>( aItem ) );
192}
193
194
195void OPTIMIZER::ClearCache( bool aStaticOnly )
196{
197 if( !aStaticOnly )
198 {
199 m_cacheTags.clear();
200 m_cache.Clear();
201 return;
202 }
203
204 for( auto i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
205 {
206 if( i->second.m_isStatic )
207 {
208 m_cache.Remove( i->first );
209 m_cacheTags.erase( i->first );
210 }
211 }
212}
213
214
215bool AREA_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
216 const SHAPE_LINE_CHAIN& aCurrentPath,
217 const SHAPE_LINE_CHAIN& aReplacement )
218{
219 const VECTOR2I& p1 = aOriginLine->CPoint( aVertex1 );
220 const VECTOR2I& p2 = aOriginLine->CPoint( aVertex2 );
221
222 bool p1_in = m_allowedArea.Contains( p1 );
223 bool p2_in = m_allowedArea.Contains( p2 );
224
225 if( m_allowedAreaStrict ) // strict restriction? both points must be inside the restricted area
226 return p1_in && p2_in;
227 else // loose restriction
228 return p1_in || p2_in;
229}
230
231
232bool PRESERVE_VERTEX_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
233 const SHAPE_LINE_CHAIN& aCurrentPath,
234 const SHAPE_LINE_CHAIN& aReplacement )
235{
236 bool cv = false;
237
238 for( int i = aVertex1; i < aVertex2; i++ )
239 {
240 SEG::ecoord dist = aCurrentPath.CSegment(i).SquaredDistance( m_v );
241
242 if ( dist <= 1 )
243 {
244 cv = true;
245 break;
246 }
247 }
248
249 if( !cv )
250 return true;
251
252 for( int i = 0; i < aReplacement.SegmentCount(); i++ )
253 {
254 SEG::ecoord dist = aReplacement.CSegment(i).SquaredDistance( m_v );
255
256 if ( dist <= 1 )
257 return true;
258 }
259
260 return false;
261}
262
263
264bool RESTRICT_VERTEX_RANGE_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
265 const SHAPE_LINE_CHAIN& aCurrentPath,
266 const SHAPE_LINE_CHAIN& aReplacement )
267{
268 return true;
269}
270
271
272bool CORNER_COUNT_LIMIT_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
273 const SHAPE_LINE_CHAIN& aCurrentPath,
274 const SHAPE_LINE_CHAIN& aReplacement )
275{
276 LINE newPath( *aOriginLine, aCurrentPath );
277 newPath.Line().Replace( aVertex1, aVertex2, aReplacement );
278 newPath.Line().Simplify();
279 int cc = newPath.CountCorners( m_angleMask );
280
281 if( cc >= m_minCorners )
282 return true;
283
284 // fixme: something fishy with the max corneriness limit
285 // (cc <= m_maxCorners)
286
287 return false;
288}
289
290
302static bool pointInside2( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aP )
303{
304 if( !aL.IsClosed() || aL.SegmentCount() < 3 )
305 return false;
306
307 int result = 0;
308 size_t cnt = aL.PointCount();
309
310 VECTOR2I ip = aL.CPoint( 0 );
311
312 for( size_t i = 1; i <= cnt; ++i )
313 {
314 VECTOR2I ipNext = ( i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ) );
315
316 if( ipNext.y == aP.y )
317 {
318 if( ( ipNext.x == aP.x )
319 || ( ip.y == aP.y && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
320 return true; // pt on polyground boundary
321 }
322
323 if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
324 {
325 if( ip.x >=aP.x )
326 {
327 if( ipNext.x >aP.x )
328 {
329 result = 1 - result;
330 }
331 else
332 {
333 double d = static_cast<double>( ip.x - aP.x ) *
334 static_cast<double>( ipNext.y - aP.y ) -
335 static_cast<double>( ipNext.x - aP.x ) *
336 static_cast<double>( ip.y - aP.y );
337
338 if( !d )
339 return true; // pt on polyground boundary
340
341 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
342 result = 1 - result;
343 }
344 }
345 else
346 {
347 if( ipNext.x >aP.x )
348 {
349 double d = ( (double) ip.x - aP.x ) * ( (double) ipNext.y - aP.y )
350 - ( (double) ipNext.x - aP.x ) * ( (double) ip.y - aP.y );
351
352 if( !d )
353 return true; // pt on polyground boundary
354
355 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
356 result = 1 - result;
357 }
358 }
359 }
360
361 ip = ipNext;
362 }
363
364 return result > 0;
365}
366
367
368bool KEEP_TOPOLOGY_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
369 const SHAPE_LINE_CHAIN& aCurrentPath,
370 const SHAPE_LINE_CHAIN& aReplacement )
371{
372 SHAPE_LINE_CHAIN encPoly = aOriginLine->CLine().Slice( aVertex1, aVertex2 );
373
374 // fixme: this is a remarkably shitty implementation...
375 encPoly.Append( aReplacement.Reverse() );
376 encPoly.SetClosed( true );
377
378 BOX2I bb = encPoly.BBox();
379 std::vector<JOINT*> joints;
380
381 int cnt = m_world->QueryJoints( bb, joints, aOriginLine->Layers(), ITEM::SOLID_T );
382
383 if( !cnt )
384 return true;
385
386 for( JOINT* j : joints )
387 {
388 if( j->Net() == aOriginLine->Net() )
389 continue;
390
391 if( pointInside2( encPoly, j->Pos() ) )
392 {
393 bool falsePositive = false;
394
395 for( int k = 0; k < encPoly.PointCount(); k++ )
396 {
397 if( encPoly.CPoint(k) == j->Pos() )
398 {
399 falsePositive = true;
400 break;
401 }
402 }
403
404 if( !falsePositive )
405 {
406 //dbg->AddPoint(j->Pos(), 5);
407 return false;
408 }
409 }
410 }
411
412 return true;
413}
414
415
416bool OPTIMIZER::checkColliding( ITEM* aItem, bool aUpdateCache )
417{
419
420 return static_cast<bool>( m_world->CheckColliding( aItem ) );
421}
422
423
425{
426 m_constraints.push_back( aConstraint );
427}
428
429
430bool OPTIMIZER::checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
431 const SHAPE_LINE_CHAIN& aCurrentPath,
432 const SHAPE_LINE_CHAIN& aReplacement )
433{
434 for( OPT_CONSTRAINT* c : m_constraints )
435 {
436 if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
437 return false;
438 }
439
440 return true;
441}
442
443
444bool OPTIMIZER::checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath )
445{
446 LINE tmp( *aLine, aOptPath );
447
448 return checkColliding( &tmp );
449}
450
451
453{
454 SHAPE_LINE_CHAIN& line = aLine->Line();
455
456 int step = line.PointCount() - 3;
457 int iter = 0;
458 int segs_pre = line.SegmentCount();
459
460 if( step < 0 )
461 return false;
462
463 SHAPE_LINE_CHAIN current_path( line );
464
465 while( 1 )
466 {
467 iter++;
468 int n_segs = current_path.SegmentCount();
469 int max_step = n_segs - 2;
470
471 if( step > max_step )
472 step = max_step;
473
474 if( step < 2 )
475 {
476 line = current_path;
477 return current_path.SegmentCount() < segs_pre;
478 }
479
480 bool found_anything = false;
481
482 for( int n = 0; n < n_segs - step; n++ )
483 {
484 const SEG s1 = current_path.CSegment( n );
485 const SEG s2 = current_path.CSegment( n + step );
486 SEG s1opt, s2opt;
487
488 if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
489 {
490 VECTOR2I ip = *s1.IntersectLines( s2 );
491
492 s1opt = SEG( s1.A, ip );
493 s2opt = SEG( ip, s2.B );
494
495 if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
496 {
497 SHAPE_LINE_CHAIN opt_path;
498 opt_path.Append( s1opt.A );
499 opt_path.Append( s1opt.B );
500 opt_path.Append( s2opt.B );
501
502 LINE opt_track( *aLine, opt_path );
503
504 if( !checkColliding( &opt_track ) )
505 {
506 current_path.Replace( s1.Index() + 1, s2.Index(), ip );
507
508 // removeCachedSegments(aLine, s1.Index(), s2.Index());
509 n_segs = current_path.SegmentCount();
510 found_anything = true;
511 break;
512 }
513 }
514 }
515 }
516
517 if( !found_anything )
518 {
519 if( step <= 2 )
520 {
521 line = current_path;
522 return line.SegmentCount() < segs_pre;
523 }
524
525 step--;
526 }
527 }
528
529 return line.SegmentCount() < segs_pre;
530}
531
532
534{
535 SHAPE_LINE_CHAIN& line = aLine->Line();
536 int step = line.SegmentCount() - 1;
537
538 int segs_pre = line.SegmentCount();
539
540 line.Simplify();
541
542 if( step < 0 )
543 return false;
544
545 SHAPE_LINE_CHAIN current_path( line );
546
547 while( 1 )
548 {
549 int n_segs = current_path.SegmentCount();
550 int max_step = n_segs - 2;
551
552 if( step > max_step )
553 step = max_step;
554
555 if( step < 1 )
556 break;
557
558 bool found_anything = mergeStep( aLine, current_path, step );
559
560 if( !found_anything )
561 step--;
562
563 if( !step )
564 break;
565 }
566
567 aLine->SetShape( current_path );
568
569 return current_path.SegmentCount() < segs_pre;
570}
571
572
574{
575 SHAPE_LINE_CHAIN& line = aLine->Line();
576
577 int nSegs = line.SegmentCount();
578
579 for( int segIdx = 0; segIdx < line.SegmentCount() - 1; ++segIdx )
580 {
581 SEG s1 = line.CSegment( segIdx );
582 SEG s2 = line.CSegment( segIdx + 1 );
583
584 // Skip zero-length segs caused by abutting arcs
585 if( s1.SquaredLength() == 0 || s2.SquaredLength() == 0 )
586 continue;
587
588 if( s1.Collinear( s2 ) && !line.IsPtOnArc( segIdx + 1 ) )
589 {
590 line.Remove( segIdx + 1 );
591 }
592 }
593
594 return line.SegmentCount() < nSegs;
595}
596
597
598bool OPTIMIZER::Optimize( LINE* aLine, LINE* aResult, LINE* aRoot )
599{
601
602 if( aRoot )
603 {
604 PNS_DBG( dbg, AddItem, aRoot, BLUE, 100000, wxT( "root-line" ) );
605 }
606
607
608 if( !aResult )
609 {
610 aResult = aLine;
611 }
612 else
613 {
614 *aResult = *aLine;
615 aResult->ClearLinks();
616 }
617
618 bool hasArcs = aLine->ArcCount();
619 bool rv = false;
620
621 if( (m_effortLevel & LIMIT_CORNER_COUNT) && aRoot )
622 {
623 const int angleMask = DIRECTION_45::ANG_OBTUSE;
624 int rootObtuseCorners = aRoot->CountCorners( angleMask );
625 auto c = new CORNER_COUNT_LIMIT_CONSTRAINT( m_world, rootObtuseCorners,
626 aLine->SegmentCount(), angleMask );
627 PNS_DBG( dbg, Message,
628 wxString::Format( "opt limit-corner-count root %d maxc %d mask %x",
629 rootObtuseCorners, aLine->SegmentCount(), angleMask ) );
630
631 addConstraint( c );
632 }
633
635 {
637 addConstraint( c );
638 }
639
641 {
644 addConstraint( c );
645 }
646
648 {
651 PNS_DBG( dbg, AddShape, &r, YELLOW, 0, wxT( "area-constraint" ) );
652 addConstraint( c );
653 }
654
656 {
657 auto c = new KEEP_TOPOLOGY_CONSTRAINT( m_world );
658 addConstraint( c );
659 }
660
661 // TODO: Fix for arcs
662 if( !hasArcs && m_effortLevel & MERGE_SEGMENTS )
663 rv |= mergeFull( aResult );
664
665 // TODO: Fix for arcs
666 if( !hasArcs && m_effortLevel & MERGE_OBTUSE )
667 rv |= mergeObtuse( aResult );
668
670 rv |= mergeColinear( aResult );
671
672 // TODO: Fix for arcs
673 if( !hasArcs && m_effortLevel & SMART_PADS )
674 rv |= runSmartPads( aResult );
675
676 // TODO: Fix for arcs
677 if( !hasArcs && m_effortLevel & FANOUT_CLEANUP )
678 rv |= fanoutCleanup( aResult );
679
680 return rv;
681}
682
683
684bool OPTIMIZER::mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentPath, int step )
685{
686 int n_segs = aCurrentPath.SegmentCount();
687
688 int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
689
690 if( aLine->SegmentCount() < 2 )
691 return false;
692
694 bool is90mode = cornerMode == DIRECTION_45::MITERED_90 || cornerMode == DIRECTION_45::ROUNDED_90;
695
696 DIRECTION_45 orig_start( aLine->CSegment( 0 ), is90mode );
697 DIRECTION_45 orig_end( aLine->CSegment( -1 ), is90mode );
698
699
700 for( int n = 0; n < n_segs - step; n++ )
701 {
702 // Do not attempt to merge false segments that are part of an arc
703 if( aCurrentPath.IsArcSegment( n )
704 || aCurrentPath.IsArcSegment( static_cast<std::size_t>( n ) + step ) )
705 {
706 continue;
707 }
708
709 const SEG s1 = aCurrentPath.CSegment( n );
710 const SEG s2 = aCurrentPath.CSegment( n + step );
711
713 SHAPE_LINE_CHAIN* picked = nullptr;
714 int cost[2];
715
716 for( int i = 0; i < 2; i++ )
717 {
718 SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i, cornerMode );
719 cost[i] = INT_MAX;
720
721 bool ok = false;
722
723 if( !checkColliding( aLine, bypass ) )
724 {
725 ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
726 }
727
728 if( ok )
729 {
730 path[i] = aCurrentPath;
731 path[i].Replace( s1.Index(), s2.Index(), bypass );
732 path[i].Simplify();
733 cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
734 }
735 }
736
737 if( cost[0] < cost_orig && cost[0] < cost[1] )
738 picked = &path[0];
739 else if( cost[1] < cost_orig )
740 picked = &path[1];
741
742 if( picked )
743 {
744 n_segs = aCurrentPath.SegmentCount();
745 aCurrentPath = *picked;
746 return true;
747 }
748 }
749
750 return false;
751}
752
753
755 bool aPermitDiagonal ) const
756{
757 BREAKOUT_LIST breakouts;
758
760 {
761 const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
763 VECTOR2I p0 = cir->GetCenter();
764 VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
765
766 RotatePoint( v0, -angle );
767
768 l.Append( p0 );
769 l.Append( p0 + v0 );
770 breakouts.push_back( l );
771 }
772
773 return breakouts;
774}
775
776
778 bool aPermitDiagonal ) const
779{
780 BREAKOUT_LIST breakouts;
781 const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
782
783 BOX2I bbox = convex->BBox( 0 );
784 VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
785 // must be large enough to guarantee intersecting the convex polygon
786 int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
787 EDA_ANGLE increment = ( aPermitDiagonal ? ANGLE_45 : ANGLE_90 );
788
789 for( EDA_ANGLE angle = ANGLE_0; angle < ANGLE_360; angle += increment )
790 {
792 VECTOR2I v0( p0 + VECTOR2I( length, 0 ) );
793 RotatePoint( v0, p0, -angle );
794
796 int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
797
798 // if n == 1 intersected a segment
799 // if n == 2 intersected the common point of 2 segments
800 // n == 0 can not happen I think, but...
801 if( n > 0 )
802 {
803 l.Append( p0 );
804
805 // for a breakout distance relative to the distance between
806 // center and polygon edge
807 //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
808
809 // for an absolute breakout distance, e.g. 0.1 mm
810 //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
811
812 // for the breakout right on the polygon edge
813 l.Append( intersections[0].p );
814
815 breakouts.push_back( l );
816 }
817 }
818
819 return breakouts;
820}
821
822
824 bool aPermitDiagonal ) const
825{
826 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
827 VECTOR2I s = rect->GetSize();
828 VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
829
830 BREAKOUT_LIST breakouts;
831 breakouts.reserve( 12 );
832
833 VECTOR2I d_offset;
834
835 d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
836 d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
837
838 VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
839 VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
840
841 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
842 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
843 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
844 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
845
846 if( aPermitDiagonal )
847 {
848 int l = aWidth + std::min( s.x, s.y ) / 2;
849 VECTOR2I d_diag;
850
851 if( s.x >= s.y )
852 {
853 breakouts.emplace_back(
854 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
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 }
862 else
863 {
864 // fixme: this could be done more efficiently
865 breakouts.emplace_back(
866 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
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 }
874 }
875
876 return breakouts;
877}
878
879
881 bool aPermitDiagonal ) const
882{
883 switch( aItem->Kind() )
884 {
885 case ITEM::VIA_T:
886 {
887 const VIA* via = static_cast<const VIA*>( aItem );
888 return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
889 }
890
891 case ITEM::SOLID_T:
892 {
893 const SHAPE* shape = aItem->Shape();
894
895 switch( shape->Type() )
896 {
897 case SH_RECT:
898 return rectBreakouts( aWidth, shape, aPermitDiagonal );
899
900 case SH_SEGMENT:
901 {
902 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
903 const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
904 return rectBreakouts( aWidth, &rect, aPermitDiagonal );
905 }
906
907 case SH_CIRCLE:
908 return circleBreakouts( aWidth, shape, aPermitDiagonal );
909
910 case SH_SIMPLE:
911 return customBreakouts( aWidth, aItem, aPermitDiagonal );
912
913 default:
914 break;
915 }
916
917 break;
918 }
919
920 default:
921 break;
922 }
923
924 return BREAKOUT_LIST();
925}
926
927
928ITEM* OPTIMIZER::findPadOrVia( int aLayer, NET_HANDLE aNet, const VECTOR2I& aP ) const
929{
930 const JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
931
932 if( !jt )
933 return nullptr;
934
935 for( ITEM* item : jt->LinkList() )
936 {
937 if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
938 return item;
939 }
940
941 return nullptr;
942}
943
944
945int OPTIMIZER::smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex )
946{
947 DIRECTION_45 dir;
948
949 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
951
952 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
953 std::vector<RtVariant> variants;
954
955 SOLID* solid = dyn_cast<SOLID*>( aPad );
956
957 // don't do optimized connections for offset pads
958 if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
959 return -1;
960
961 // don't do optimization on vias, they are always round at the moment and the optimizer
962 // will possibly mess up an intended via exit posture
963 if( aPad->Kind() == ITEM::VIA_T )
964 return -1;
965
966 BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
967 SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
968 int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
969
970 // Start at 1 to find a potentially better breakout (0 is the pad connection)
971 for( int p = 1; p <= p_end; p++ )
972 {
973 // If the line is contained inside the pad, don't optimize
974 if( solid && solid->Shape() && !solid->Shape()->Collide(
975 SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
976 {
977 continue;
978 }
979
980 for( SHAPE_LINE_CHAIN & breakout : breakouts )
981 {
982 for( int diag = 0; diag < 2; diag++ )
983 {
986 breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
987
988 DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
989
990 if( !connect.SegmentCount() )
991 continue;
992
993 int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
994
995 if( ang1 & ForbiddenAngles )
996 continue;
997
998 if( breakout.Length() > line.Length() )
999 continue;
1000
1001 v = breakout;
1002 v.Append( connect );
1003
1004 for( int i = p + 1; i < line.PointCount(); i++ )
1005 v.Append( line.CPoint( i ) );
1006
1007 LINE tmp( *aLine, v );
1008 int cc = tmp.CountCorners( ForbiddenAngles );
1009
1010 if( cc == 0 )
1011 {
1012 RtVariant vp;
1013 std::get<0>( vp ) = p;
1014 std::get<1>( vp ) = breakout.Length();
1015 std::get<2>( vp ) = aEnd ? v.Reverse() : v;
1016 std::get<2>( vp ).Simplify();
1017 variants.push_back( vp );
1018 }
1019 }
1020 }
1021 }
1022
1023 // We attempt to minimize the corner cost (minimizes the segments and types of corners)
1024 // but given two, equally valid costs, we want to pick the longer pad exit. The logic
1025 // here is that if the pad is oblong, the track should not exit the shorter side and parallel
1026 // the pad but should follow the pad's preferential direction before exiting.
1027 // The baseline guess is to start with the existing line the user has drawn.
1028 int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
1029 long long int max_length = 0;
1030 bool found = false;
1031 int p_best = -1;
1032 SHAPE_LINE_CHAIN l_best;
1033
1034 for( RtVariant& vp : variants )
1035 {
1036 LINE tmp( *aLine, std::get<2>( vp ) );
1037 int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
1038 long long int len = std::get<1>( vp );
1039
1040 if( !checkColliding( &tmp ) )
1041 {
1042 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1043 {
1044 l_best = std::get<2>( vp );
1045 p_best = std::get<0>( vp );
1046 found = true;
1047
1048 if( cost <= min_cost )
1049 max_length = std::max<int>( len, max_length );
1050
1051 min_cost = std::min( cost, min_cost );
1052 }
1053 }
1054 }
1055
1056 if( found )
1057 {
1058 aLine->SetShape( l_best );
1059 return p_best;
1060 }
1061
1062 return -1;
1063}
1064
1065
1067{
1068 SHAPE_LINE_CHAIN& line = aLine->Line();
1069
1070 if( line.PointCount() < 3 )
1071 return false;
1072
1073 VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
1074
1075 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1076 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1077
1078 int vtx = -1;
1079
1080 if( startPad )
1081 vtx = smartPadsSingle( aLine, startPad, false, 3 );
1082
1083 if( endPad )
1084 smartPadsSingle( aLine, endPad, true,
1085 vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1086
1087 aLine->Line().Simplify();
1088
1089 return true;
1090}
1091
1092
1093bool OPTIMIZER::Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld, const VECTOR2I& aV )
1094{
1095 OPTIMIZER opt( aWorld );
1096
1097 opt.SetEffortLevel( aEffortLevel );
1098 opt.SetCollisionMask( -1 );
1099
1100 if( aEffortLevel & OPTIMIZER::PRESERVE_VERTEX )
1101 opt.SetPreserveVertex( aV );
1102
1103 return opt.Optimize( aLine );
1104}
1105
1106
1108{
1109 if( aLine->PointCount() < 3 )
1110 return false;
1111
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, cornerMode );
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}
size_type GetHeight() const
Definition: box2.h:205
size_type GetWidth() const
Definition: box2.h:204
bool Contains(const Vec &aPoint) const
Definition: box2.h:158
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:194
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:167
virtual int Layer() const
Definition: pns_item.h:200
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:225
const LAYER_RANGE & Layers() const
Definition: pns_item.h:196
bool OfKind(int aKindMask) const
Definition: pns_item.h:175
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:273
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:43
const std::vector< ITEM * > & LinkList() const
Definition: pns_joint.h:273
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:1215
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1629
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)
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 addConstraint(OPT_CONSTRAINT *aConstraint)
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:354
int Length() const
Return the length (this).
Definition: seg.h:336
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:461
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:279
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:220
ecoord SquaredLength() const
Definition: seg.h:341
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:371
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:98
int GetRadius() const
Definition: shape_circle.h:118
const VECTOR2I GetCenter() const
Definition: shape_circle.h:123
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:380
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:401
static constexpr EDA_ANGLE ANGLE_90
Definition: eda_angle.h:403
static constexpr EDA_ANGLE ANGLE_45
Definition: eda_angle.h:402
static constexpr EDA_ANGLE ANGLE_360
Definition: eda_angle.h:407
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:355
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:390
#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
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:673