KiCad PCB EDA Suite
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
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 The KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
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 // TODO(JE) viastacks
145 if( !aOtherItem->Collide( m_ourItem, m_node, m_ourItem->Layer() ) )
146 return true;
147
148 m_collidingItem = aOtherItem;
149 return false;
150 }
151
156};
157
158
159void OPTIMIZER::cacheAdd( ITEM* aItem, bool aIsStatic = false )
160{
161 if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
162 return;
163
164 m_cache.Add( aItem );
165 m_cacheTags[aItem].m_hits = 1;
166 m_cacheTags[aItem].m_isStatic = aIsStatic;
167}
168
169
170void OPTIMIZER::removeCachedSegments( LINE* aLine, int aStartVertex, int aEndVertex )
171{
172 if( !aLine->IsLinked() )
173 return;
174
175 auto links = aLine->Links();
176
177 if( aEndVertex < 0 )
178 aEndVertex += aLine->PointCount();
179
180 for( int i = aStartVertex; i < aEndVertex - 1; i++ )
181 {
182 LINKED_ITEM* s = links[i];
183 m_cacheTags.erase( s );
184 m_cache.Remove( s );
185 }
186}
187
188
190{
191 if( aItem->Kind() == ITEM::LINE_T )
192 removeCachedSegments( static_cast<LINE*>( aItem ) );
193}
194
195
196void OPTIMIZER::ClearCache( bool aStaticOnly )
197{
198 if( !aStaticOnly )
199 {
200 m_cacheTags.clear();
201 m_cache.Clear();
202 return;
203 }
204
205 for( auto i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
206 {
207 if( i->second.m_isStatic )
208 {
209 m_cache.Remove( i->first );
210 m_cacheTags.erase( i->first );
211 }
212 }
213}
214
215
216bool AREA_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
217 const SHAPE_LINE_CHAIN& aCurrentPath,
218 const SHAPE_LINE_CHAIN& aReplacement )
219{
220 const VECTOR2I& p1 = aCurrentPath.CPoint( aVertex1 );
221 const VECTOR2I& p2 = aCurrentPath.CPoint( aVertex2 );
222
223 bool p1_in = m_allowedArea.Contains( p1 );
224 bool p2_in = m_allowedArea.Contains( p2 );
225
227
228 if( p1_in && p2_in )
229 return true;
230
231 if( aVertex1 < aCurrentPath.PointCount() - 1 && !p1_in && p2_in
232 && m_allowedArea.Contains( aCurrentPath.CPoint( aVertex1 + 1 ) ) )
233 return aReplacement.CSegment( 0 ).Angle( aCurrentPath.CSegment( aVertex1 ) ).IsHorizontal();
234
235 if( p1_in && !p2_in && m_allowedArea.Contains( aCurrentPath.CPoint( aVertex2 - 1 ) ) )
236 return aReplacement.CSegment( -1 )
237 .Angle( aCurrentPath.CSegment( aVertex2 - 1 ) )
238 .IsHorizontal();
239
240 //PNS_DBG( dbg, AddShape, m_allowedArea, YELLOW, 10000, wxT( "drag-affected-area" ) );
241 //PNS_DBG( dbg, AddPoint, p1, YELLOW, 1000000, wxT( "drag-p1" ) );
242 //PNS_DBG( dbg, AddPoint, p2, YELLOW, 1000000, wxT( "drag-p2" ) );
243
244 return false;
245}
246
247
248bool PRESERVE_VERTEX_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
249 const SHAPE_LINE_CHAIN& aCurrentPath,
250 const SHAPE_LINE_CHAIN& aReplacement )
251{
252 bool cv = false;
253
254 for( int i = aVertex1; i < aVertex2; i++ )
255 {
256 SEG::ecoord dist = aCurrentPath.CSegment(i).SquaredDistance( m_v );
257
258 if ( dist <= 1 )
259 {
260 cv = true;
261 break;
262 }
263 }
264
265 if( !cv )
266 return true;
267
268 for( int i = 0; i < aReplacement.SegmentCount(); i++ )
269 {
270 SEG::ecoord dist = aReplacement.CSegment(i).SquaredDistance( m_v );
271
272 if ( dist <= 1 )
273 return true;
274 }
275
276 return false;
277}
278
279
280bool RESTRICT_VERTEX_RANGE_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
281 const SHAPE_LINE_CHAIN& aCurrentPath,
282 const SHAPE_LINE_CHAIN& aReplacement )
283{
284 return true;
285}
286
287
288bool CORNER_COUNT_LIMIT_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
289 const SHAPE_LINE_CHAIN& aCurrentPath,
290 const SHAPE_LINE_CHAIN& aReplacement )
291{
292 LINE newPath( *aOriginLine, aCurrentPath );
293 newPath.Line().Replace( aVertex1, aVertex2, aReplacement );
294 newPath.Line().Simplify2();
295 int cc = newPath.CountCorners( m_angleMask );
296
297 if( cc >= m_minCorners )
298 return true;
299
300 // fixme: something fishy with the max corneriness limit
301 // (cc <= m_maxCorners)
302
303 return true;
304}
305
306
318static bool pointInside2( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aP )
319{
320 if( !aL.IsClosed() || aL.SegmentCount() < 3 )
321 return false;
322
323 int result = 0;
324 size_t cnt = aL.PointCount();
325
326 VECTOR2I ip = aL.CPoint( 0 );
327
328 for( size_t i = 1; i <= cnt; ++i )
329 {
330 VECTOR2I ipNext = ( i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ) );
331
332 if( ipNext.y == aP.y )
333 {
334 if( ( ipNext.x == aP.x )
335 || ( ip.y == aP.y && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
336 return true; // pt on polyground boundary
337 }
338
339 if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
340 {
341 if( ip.x >=aP.x )
342 {
343 if( ipNext.x >aP.x )
344 {
345 result = 1 - result;
346 }
347 else
348 {
349 double d = static_cast<double>( ip.x - aP.x ) *
350 static_cast<double>( ipNext.y - aP.y ) -
351 static_cast<double>( ipNext.x - aP.x ) *
352 static_cast<double>( ip.y - aP.y );
353
354 if( !d )
355 return true; // pt on polyground boundary
356
357 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
358 result = 1 - result;
359 }
360 }
361 else
362 {
363 if( ipNext.x >aP.x )
364 {
365 double d = ( (double) ip.x - aP.x ) * ( (double) ipNext.y - aP.y )
366 - ( (double) ipNext.x - aP.x ) * ( (double) ip.y - aP.y );
367
368 if( !d )
369 return true; // pt on polyground boundary
370
371 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
372 result = 1 - result;
373 }
374 }
375 }
376
377 ip = ipNext;
378 }
379
380 return result > 0;
381}
382
383
384bool KEEP_TOPOLOGY_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
385 const SHAPE_LINE_CHAIN& aCurrentPath,
386 const SHAPE_LINE_CHAIN& aReplacement )
387{
388 SHAPE_LINE_CHAIN encPoly = aOriginLine->CLine().Slice( aVertex1, aVertex2 );
389
390 // fixme: this is a remarkably shitty implementation...
391 encPoly.Append( aReplacement.Reverse() );
392 encPoly.SetClosed( true );
393
394 BOX2I bb = encPoly.BBox();
395 std::vector<JOINT*> joints;
396
397 int cnt = m_world->QueryJoints( bb, joints, aOriginLine->Layers(), ITEM::SOLID_T );
398
399 if( !cnt )
400 return true;
401
402 for( JOINT* j : joints )
403 {
404 if( j->Net() == aOriginLine->Net() )
405 continue;
406
407 if( pointInside2( encPoly, j->Pos() ) )
408 {
409 bool falsePositive = false;
410
411 for( int k = 0; k < encPoly.PointCount(); k++ )
412 {
413 if( encPoly.CPoint(k) == j->Pos() )
414 {
415 falsePositive = true;
416 break;
417 }
418 }
419
420 if( !falsePositive )
421 {
422 //dbg->AddPoint(j->Pos(), 5);
423 return false;
424 }
425 }
426 }
427
428 return true;
429}
430
431
432bool OPTIMIZER::checkColliding( ITEM* aItem, bool aUpdateCache )
433{
435
436 return static_cast<bool>( m_world->CheckColliding( aItem ) );
437}
438
439
441{
442 m_constraints.push_back( aConstraint );
443}
444
445
446bool OPTIMIZER::checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
447 const SHAPE_LINE_CHAIN& aCurrentPath,
448 const SHAPE_LINE_CHAIN& aReplacement )
449{
450 for( OPT_CONSTRAINT* c : m_constraints )
451 {
452 if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
453 return false;
454 }
455
456 return true;
457}
458
459
460bool OPTIMIZER::checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath )
461{
462 LINE tmp( *aLine, aOptPath );
463
464 return checkColliding( &tmp );
465}
466
467
469{
470 SHAPE_LINE_CHAIN& line = aLine->Line();
471
472 int step = line.PointCount() - 3;
473 int iter = 0;
474 int segs_pre = line.SegmentCount();
475
476 if( step < 0 )
477 return false;
478
479 SHAPE_LINE_CHAIN current_path( line );
480
481 while( 1 )
482 {
483 iter++;
484 int n_segs = current_path.SegmentCount();
485 int max_step = n_segs - 2;
486
487 if( step > max_step )
488 step = max_step;
489
490 if( step < 2 )
491 {
492 line = current_path;
493 return current_path.SegmentCount() < segs_pre;
494 }
495
496 bool found_anything = false;
497
498 for( int n = 0; n < n_segs - step; n++ )
499 {
500 const SEG s1 = current_path.CSegment( n );
501 const SEG s2 = current_path.CSegment( n + step );
502 SEG s1opt, s2opt;
503
504 if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
505 {
506 VECTOR2I ip = *s1.IntersectLines( s2 );
507
508 s1opt = SEG( s1.A, ip );
509 s2opt = SEG( ip, s2.B );
510
511 if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
512 {
513 SHAPE_LINE_CHAIN opt_path;
514 opt_path.Append( s1opt.A );
515 opt_path.Append( s1opt.B );
516 opt_path.Append( s2opt.B );
517
518 LINE opt_track( *aLine, opt_path );
519
520 if( !checkColliding( &opt_track ) )
521 {
522 current_path.Replace( s1.Index() + 1, s2.Index(), ip );
523
524 // removeCachedSegments(aLine, s1.Index(), s2.Index());
525 n_segs = current_path.SegmentCount();
526 found_anything = true;
527 break;
528 }
529 }
530 }
531 }
532
533 if( !found_anything )
534 {
535 if( step <= 2 )
536 {
537 line = current_path;
538 return line.SegmentCount() < segs_pre;
539 }
540
541 step--;
542 }
543 }
544
545 return line.SegmentCount() < segs_pre;
546}
547
548
550{
551 SHAPE_LINE_CHAIN& line = aLine->Line();
552 int step = line.SegmentCount() - 1;
553
554 int segs_pre = line.SegmentCount();
555
556 line.Simplify2();
557
558 if( step < 0 )
559 return false;
560
561 SHAPE_LINE_CHAIN current_path( line );
562
563 while( 1 )
564 {
565 int n_segs = current_path.SegmentCount();
566 int max_step = n_segs - 2;
567
568 if( step > max_step )
569 step = max_step;
570
571 if( step < 1 )
572 break;
573
574 bool found_anything = mergeStep( aLine, current_path, step );
575
576 if( !found_anything )
577 step--;
578
579 if( !step )
580 break;
581 }
582
583 aLine->SetShape( current_path );
584
585 return current_path.SegmentCount() < segs_pre;
586}
587
588
590{
591 SHAPE_LINE_CHAIN& line = aLine->Line();
592
593 int nSegs = line.SegmentCount();
594
595 for( int segIdx = 0; segIdx < line.SegmentCount() - 1; ++segIdx )
596 {
597 SEG s1 = line.CSegment( segIdx );
598 SEG s2 = line.CSegment( segIdx + 1 );
599
600 // Skip zero-length segs caused by abutting arcs
601 if( s1.SquaredLength() == 0 || s2.SquaredLength() == 0 )
602 continue;
603
604 if( s1.Collinear( s2 ) && !line.IsPtOnArc( segIdx + 1 ) )
605 {
606 line.Remove( segIdx + 1 );
607 }
608 }
609
610 return line.SegmentCount() < nSegs;
611}
612
613
614bool OPTIMIZER::Optimize( const LINE* aLine, LINE* aResult, LINE* aRoot )
615{
617
618 if( aRoot )
619 {
620 //PNS_DBG( dbg, AddItem, aRoot, BLUE, 100000, wxT( "root-line" ) );
621 }
622
623
624 if( !aResult )
625 return false;
626
627 *aResult = *aLine;
628 aResult->ClearLinks();
629
630 bool hasArcs = aLine->ArcCount();
631 bool rv = false;
632
633 if( (m_effortLevel & LIMIT_CORNER_COUNT) && aRoot )
634 {
635 const int angleMask = DIRECTION_45::ANG_OBTUSE;
636 int rootObtuseCorners = aRoot->CountCorners( angleMask );
637 auto c = new CORNER_COUNT_LIMIT_CONSTRAINT( m_world, rootObtuseCorners,
638 aLine->SegmentCount(), angleMask );
639 //PNS_DBG( dbg, Message,
640 // wxString::Format( "opt limit-corner-count root %d maxc %d mask %x",
641 // rootObtuseCorners, aLine->SegmentCount(), angleMask ) );
642
643 addConstraint( c );
644 }
645
647 {
649 addConstraint( c );
650 }
651
653 {
656 addConstraint( c );
657 }
658
660 {
663 //PNS_DBG( dbg, AddShape, &r, YELLOW, 0, wxT( "area-constraint" ) );
664 addConstraint( c );
665 }
666
668 {
669 auto c = new KEEP_TOPOLOGY_CONSTRAINT( m_world );
670 addConstraint( c );
671 }
672
673 // TODO: Fix for arcs
674 if( !hasArcs && m_effortLevel & MERGE_SEGMENTS )
675 rv |= mergeFull( aResult );
676
677 // TODO: Fix for arcs
678 if( !hasArcs && m_effortLevel & MERGE_OBTUSE )
679 rv |= mergeObtuse( aResult );
680
682 rv |= mergeColinear( aResult );
683
684 // TODO: Fix for arcs
685 if( !hasArcs && m_effortLevel & SMART_PADS )
686 rv |= runSmartPads( aResult );
687
688 // TODO: Fix for arcs
689 if( !hasArcs && m_effortLevel & FANOUT_CLEANUP )
690 rv |= fanoutCleanup( aResult );
691
692 return rv;
693}
694
695
696bool OPTIMIZER::mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentPath, int step )
697{
698 int n_segs = aCurrentPath.SegmentCount();
699
700 int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
701
702 if( aLine->SegmentCount() < 2 )
703 return false;
704
706 bool is90mode = cornerMode == DIRECTION_45::MITERED_90 || cornerMode == DIRECTION_45::ROUNDED_90;
707
708 DIRECTION_45 orig_start( aLine->CSegment( 0 ), is90mode );
709 DIRECTION_45 orig_end( aLine->CSegment( -1 ), is90mode );
710
711
712 for( int n = 0; n < n_segs - step; n++ )
713 {
714 // Do not attempt to merge false segments that are part of an arc
715 if( aCurrentPath.IsArcSegment( n )
716 || aCurrentPath.IsArcSegment( static_cast<std::size_t>( n ) + step ) )
717 {
718 continue;
719 }
720
721 const SEG s1 = aCurrentPath.CSegment( n );
722 const SEG s2 = aCurrentPath.CSegment( n + step );
723
725 SHAPE_LINE_CHAIN* picked = nullptr;
726 int cost[2];
727
728 for( int i = 0; i < 2; i++ )
729 {
730 SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i, cornerMode );
731 cost[i] = INT_MAX;
732
733 bool ok = false;
734
735 if( !checkColliding( aLine, bypass ) )
736 {
737 ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
738 }
739
740 if( ok )
741 {
742 path[i] = aCurrentPath;
743 path[i].Replace( s1.Index(), s2.Index(), bypass );
744 path[i].Simplify2();
745 cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
746 }
747 }
748
749 if( cost[0] < cost_orig && cost[0] < cost[1] )
750 picked = &path[0];
751 else if( cost[1] < cost_orig )
752 picked = &path[1];
753
754 if( picked )
755 {
756 n_segs = aCurrentPath.SegmentCount();
757 aCurrentPath = *picked;
758 return true;
759 }
760 }
761
762 return false;
763}
764
765
767 bool aPermitDiagonal ) const
768{
769 BREAKOUT_LIST breakouts;
770
772 {
773 const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
775 VECTOR2I p0 = cir->GetCenter();
776 VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
777
778 RotatePoint( v0, -angle );
779
780 l.Append( p0 );
781 l.Append( p0 + v0 );
782 breakouts.push_back( l );
783 }
784
785 return breakouts;
786}
787
788
790 bool aPermitDiagonal ) const
791{
792 BREAKOUT_LIST breakouts;
793 const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape( -1 ) );
794
795 BOX2I bbox = convex->BBox( 0 );
796 VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
797 // must be large enough to guarantee intersecting the convex polygon
798 int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
799 EDA_ANGLE increment = ( aPermitDiagonal ? ANGLE_45 : ANGLE_90 );
800
801 for( EDA_ANGLE angle = ANGLE_0; angle < ANGLE_360; angle += increment )
802 {
804 VECTOR2I v0( p0 + VECTOR2I( length, 0 ) );
805 RotatePoint( v0, p0, -angle );
806
808 int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
809
810 // if n == 1 intersected a segment
811 // if n == 2 intersected the common point of 2 segments
812 // n == 0 can not happen I think, but...
813 if( n > 0 )
814 {
815 l.Append( p0 );
816
817 // for a breakout distance relative to the distance between
818 // center and polygon edge
819 //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
820
821 // for an absolute breakout distance, e.g. 0.1 mm
822 //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
823
824 // for the breakout right on the polygon edge
825 l.Append( intersections[0].p );
826
827 breakouts.push_back( l );
828 }
829 }
830
831 return breakouts;
832}
833
834
836 bool aPermitDiagonal ) const
837{
838 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
839 VECTOR2I s = rect->GetSize();
840 VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
841
842 BREAKOUT_LIST breakouts;
843 breakouts.reserve( 12 );
844
845 VECTOR2I d_offset;
846
847 d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
848 d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
849
850 VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
851 VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
852
853 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
854 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
855 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
856 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
857
858 if( aPermitDiagonal )
859 {
860 int l = aWidth + std::min( s.x, s.y ) / 2;
861 VECTOR2I d_diag;
862
863 if( s.x >= s.y )
864 {
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 else
875 {
876 // fixme: this could be done more efficiently
877 breakouts.emplace_back(
878 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
879 breakouts.emplace_back(
880 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
881 breakouts.emplace_back(
882 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
883 breakouts.emplace_back(
884 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
885 }
886 }
887
888 return breakouts;
889}
890
891
893 bool aPermitDiagonal ) const
894{
895 switch( aItem->Kind() )
896 {
897 case ITEM::VIA_T:
898 {
899 const VIA* via = static_cast<const VIA*>( aItem );
900 // TODO(JE) padstacks -- computeBreakouts needs to have a layer argument
901 return circleBreakouts( aWidth, via->Shape( 0 ), aPermitDiagonal );
902 }
903
904 case ITEM::SOLID_T:
905 {
906 const SHAPE* shape = aItem->Shape( -1 );
907
908 switch( shape->Type() )
909 {
910 case SH_RECT:
911 return rectBreakouts( aWidth, shape, aPermitDiagonal );
912
913 case SH_SEGMENT:
914 {
915 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
916 const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
917 return rectBreakouts( aWidth, &rect, aPermitDiagonal );
918 }
919
920 case SH_CIRCLE:
921 return circleBreakouts( aWidth, shape, aPermitDiagonal );
922
923 case SH_SIMPLE:
924 return customBreakouts( aWidth, aItem, aPermitDiagonal );
925
926 default:
927 break;
928 }
929
930 break;
931 }
932
933 default:
934 break;
935 }
936
937 return BREAKOUT_LIST();
938}
939
940
941ITEM* OPTIMIZER::findPadOrVia( int aLayer, NET_HANDLE aNet, const VECTOR2I& aP ) const
942{
943 const JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
944
945 if( !jt )
946 return nullptr;
947
948 for( ITEM* item : jt->LinkList() )
949 {
950 if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
951 return item;
952 }
953
954 return nullptr;
955}
956
957
958int OPTIMIZER::smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex )
959{
960 DIRECTION_45 dir;
961
962 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
964
965 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
966 std::vector<RtVariant> variants;
967
968 SOLID* solid = dyn_cast<SOLID*>( aPad );
969
970 // don't do optimized connections for offset pads
971 if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
972 return -1;
973
974 // don't do optimization on vias, they are always round at the moment and the optimizer
975 // will possibly mess up an intended via exit posture
976 if( aPad->Kind() == ITEM::VIA_T )
977 return -1;
978
979 BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
980 SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
981 int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
982
983 // Start at 1 to find a potentially better breakout (0 is the pad connection)
984 for( int p = 1; p <= p_end; p++ )
985 {
986 // If the line is contained inside the pad, don't optimize
987 if( solid && solid->Shape( -1 ) && !solid->Shape( -1 )->Collide(
988 SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
989 {
990 continue;
991 }
992
993 for( SHAPE_LINE_CHAIN & breakout : breakouts )
994 {
995 for( int diag = 0; diag < 2; diag++ )
996 {
999 breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
1000
1001 DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
1002
1003 if( !connect.SegmentCount() )
1004 continue;
1005
1006 int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
1007
1008 if( ang1 & ForbiddenAngles )
1009 continue;
1010
1011 if( breakout.Length() > line.Length() )
1012 continue;
1013
1014 v = breakout;
1015 v.Append( connect );
1016
1017 for( int i = p + 1; i < line.PointCount(); i++ )
1018 v.Append( line.CPoint( i ) );
1019
1020 LINE tmp( *aLine, v );
1021 int cc = tmp.CountCorners( ForbiddenAngles );
1022
1023 if( cc == 0 )
1024 {
1025 RtVariant vp;
1026 std::get<0>( vp ) = p;
1027 std::get<1>( vp ) = breakout.Length();
1028 std::get<2>( vp ) = aEnd ? v.Reverse() : v;
1029 std::get<2>( vp ).Simplify2();
1030 variants.push_back( vp );
1031 }
1032 }
1033 }
1034 }
1035
1036 // We attempt to minimize the corner cost (minimizes the segments and types of corners)
1037 // but given two, equally valid costs, we want to pick the longer pad exit. The logic
1038 // here is that if the pad is oblong, the track should not exit the shorter side and parallel
1039 // the pad but should follow the pad's preferential direction before exiting.
1040 // The baseline guess is to start with the existing line the user has drawn.
1041 int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
1042 long long int max_length = 0;
1043 bool found = false;
1044 int p_best = -1;
1045 SHAPE_LINE_CHAIN l_best;
1046
1047 for( RtVariant& vp : variants )
1048 {
1049 LINE tmp( *aLine, std::get<2>( vp ) );
1050 int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
1051 long long int len = std::get<1>( vp );
1052
1053 if( !checkColliding( &tmp ) )
1054 {
1055 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1056 {
1057 l_best = std::get<2>( vp );
1058 p_best = std::get<0>( vp );
1059 found = true;
1060
1061 if( cost <= min_cost )
1062 max_length = std::max<int>( len, max_length );
1063
1064 min_cost = std::min( cost, min_cost );
1065 }
1066 }
1067 }
1068
1069 if( found )
1070 {
1071 aLine->SetShape( l_best );
1072 return p_best;
1073 }
1074
1075 return -1;
1076}
1077
1078
1080{
1081 SHAPE_LINE_CHAIN& line = aLine->Line();
1082
1083 if( line.PointCount() < 3 )
1084 return false;
1085
1086 VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
1087
1088 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1089 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1090
1091 int vtx = -1;
1092
1093 if( startPad )
1094 vtx = smartPadsSingle( aLine, startPad, false, 3 );
1095
1096 if( endPad )
1097 smartPadsSingle( aLine, endPad, true,
1098 vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1099
1100 aLine->Line().Simplify2();
1101
1102 return true;
1103}
1104
1105
1106bool OPTIMIZER::Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld, const VECTOR2I& aV )
1107{
1108 OPTIMIZER opt( aWorld );
1109
1110 opt.SetEffortLevel( aEffortLevel );
1111 opt.SetCollisionMask( -1 );
1112
1113 if( aEffortLevel & OPTIMIZER::PRESERVE_VERTEX )
1114 opt.SetPreserveVertex( aV );
1115
1116 LINE tmp( *aLine );
1117 return opt.Optimize( &tmp, aLine );
1118}
1119
1120
1122{
1123 if( aLine->PointCount() < 3 )
1124 return false;
1125
1127
1128 VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
1129
1130 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1131 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1132
1133 int thr = aLine->Width() * 10;
1134 int len = aLine->CLine().Length();
1135
1136 if( !startPad )
1137 return false;
1138
1139 bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1140 bool endMatch = false;
1141
1142 if(endPad)
1143 {
1144 endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1145 }
1146 else
1147 {
1148 endMatch = aLine->EndsWithVia();
1149 }
1150
1151 if( startMatch && endMatch && len < thr )
1152 {
1153 for( int i = 0; i < 2; i++ )
1154 {
1155 SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i, cornerMode );
1156 LINE repl;
1157 repl = LINE( *aLine, l2 );
1158
1159 if( !m_world->CheckColliding( &repl ) )
1160 {
1161 aLine->SetShape( repl.CLine() );
1162 return true;
1163 }
1164 }
1165 }
1166
1167 return false;
1168}
1169
1170
1171int findCoupledVertices( const VECTOR2I& aVertex, const SEG& aOrigSeg,
1172 const SHAPE_LINE_CHAIN& aCoupled, DIFF_PAIR* aPair, int* aIndices )
1173{
1174 int count = 0;
1175
1176 for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1177 {
1178 SEG s = aCoupled.CSegment( i );
1179 VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1180
1181 if( s.ApproxParallel( aOrigSeg ) )
1182 {
1183 int64_t dist =
1184 int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Width();
1185
1186 if( aPair->GapConstraint().Matches( dist ) )
1187 {
1188 *aIndices++ = i;
1189 count++;
1190 }
1191 }
1192 }
1193
1194 return count;
1195}
1196
1197
1198bool verifyDpBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aNewRef,
1199 const SHAPE_LINE_CHAIN& aNewCoupled )
1200{
1201 LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1202 LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1203
1204 if( refLine.Collide( &coupledLine, aNode, refLine.Layer() ) )
1205 return false;
1206
1207 if( aNode->CheckColliding ( &refLine ) )
1208 return false;
1209
1210 if( aNode->CheckColliding ( &coupledLine ) )
1211 return false;
1212
1213 return true;
1214}
1215
1216
1217bool coupledBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aRef,
1218 const SHAPE_LINE_CHAIN& aRefBypass, const SHAPE_LINE_CHAIN& aCoupled,
1219 SHAPE_LINE_CHAIN& aNewCoupled )
1220{
1221 int vStartIdx[1024]; // fixme: possible overflow
1222 int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ),
1223 aRefBypass.CSegment( 0 ),
1224 aCoupled, aPair, vStartIdx );
1225 DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1226
1227 int64_t bestLength = -1;
1228 bool found = false;
1229 SHAPE_LINE_CHAIN bestBypass;
1230 int si, ei;
1231
1232 for( int i=0; i< nStarts; i++ )
1233 {
1234 for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1235 {
1236 int delta = std::abs ( vStartIdx[i] - j );
1237
1238 if( delta > 1 )
1239 {
1240 const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1241 SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j),
1242 dir.IsDiagonal() );
1243
1244 int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1245
1246 SHAPE_LINE_CHAIN newCoupled = aCoupled;
1247
1248 si = vStartIdx[i];
1249 ei = j;
1250
1251 if(si < ei)
1252 newCoupled.Replace( si, ei, bypass );
1253 else
1254 newCoupled.Replace( ei, si, bypass.Reverse() );
1255
1256 if( coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1257 newCoupled) )
1258 {
1259 bestBypass = newCoupled;
1260 bestLength = coupledLength;
1261 found = true;
1262 }
1263 }
1264 }
1265 }
1266
1267 if( found )
1268 aNewCoupled = bestBypass;
1269
1270 return found;
1271}
1272
1273
1274bool checkDpColliding( NODE* aNode, DIFF_PAIR* aPair, bool aIsP, const SHAPE_LINE_CHAIN& aPath )
1275{
1276 LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1277
1278 return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1279}
1280
1281
1282bool OPTIMIZER::mergeDpStep( DIFF_PAIR* aPair, bool aTryP, int step )
1283{
1284 int n = 1;
1285
1286 SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1287 SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1288
1289 int n_segs = currentPath.SegmentCount() - 1;
1290
1291 int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1292 int64_t budget = clenPre / 10; // fixme: come up with something more intelligent here...
1293
1294 while( n < n_segs - step )
1295 {
1296 const SEG s1 = currentPath.CSegment( n );
1297 const SEG s2 = currentPath.CSegment( n + step );
1298
1299 DIRECTION_45 dir1( s1 );
1300 DIRECTION_45 dir2( s2 );
1301
1302 if( dir1.IsObtuse( dir2 ) )
1303 {
1305 dir1.IsDiagonal() );
1306 SHAPE_LINE_CHAIN newRef;
1307 SHAPE_LINE_CHAIN newCoup;
1308 int64_t deltaCoupled = -1, deltaUni = -1;
1309
1310 newRef = currentPath;
1311 newRef.Replace( s1.Index(), s2.Index(), bypass );
1312
1313 deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1314
1315 if( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1316 {
1317 deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1318
1319 if( deltaCoupled >= 0 )
1320 {
1321 newRef.Simplify2();
1322 newCoup.Simplify2();
1323
1324 aPair->SetShape( newRef, newCoup, !aTryP );
1325 return true;
1326 }
1327 }
1328 else if( deltaUni >= 0 && verifyDpBypass( m_world, aPair, aTryP, newRef, coupledPath ) )
1329 {
1330 newRef.Simplify2();
1331 coupledPath.Simplify2();
1332
1333 aPair->SetShape( newRef, coupledPath, !aTryP );
1334 return true;
1335 }
1336 }
1337
1338 n++;
1339 }
1340
1341 return false;
1342}
1343
1344
1346{
1347 int step_p = aPair->CP().SegmentCount() - 2;
1348 int step_n = aPair->CN().SegmentCount() - 2;
1349
1350 while( 1 )
1351 {
1352 int n_segs_p = aPair->CP().SegmentCount();
1353 int n_segs_n = aPair->CN().SegmentCount();
1354
1355 int max_step_p = n_segs_p - 2;
1356 int max_step_n = n_segs_n - 2;
1357
1358 if( step_p > max_step_p )
1359 step_p = max_step_p;
1360
1361 if( step_n > max_step_n )
1362 step_n = max_step_n;
1363
1364 if( step_p < 1 && step_n < 1 )
1365 break;
1366
1367 bool found_anything_p = false;
1368 bool found_anything_n = false;
1369
1370 if( step_p > 1 )
1371 found_anything_p = mergeDpStep( aPair, true, step_p );
1372
1373 if( step_n > 1 )
1374 found_anything_n = mergeDpStep( aPair, false, step_n );
1375
1376 if( !found_anything_n && !found_anything_p )
1377 {
1378 step_n--;
1379 step_p--;
1380 }
1381 }
1382 return true;
1383}
1384
1385
1387{
1388 return mergeDpSegments( aPair );
1389}
1390
1391
1392static int64_t shovedArea( const SHAPE_LINE_CHAIN& aOld, const SHAPE_LINE_CHAIN& aNew )
1393{
1394 int64_t area = 0;
1395 const int oc = aOld.PointCount();
1396 const int nc = aNew.PointCount();
1397 const int total = oc + nc;
1398
1399 for(int i = 0; i < total; i++)
1400 {
1401 int i_next = (i + 1 == total ? 0 : i + 1);
1402
1403 const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1404 : aNew.CPoint( nc - 1 - (i - oc) );
1405 const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1406 : aNew.CPoint( nc - 1 - (i_next - oc) );
1407 area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1408 }
1409
1410 return std::abs( area / 2 );
1411}
1412
1413
1414bool tightenSegment( bool dir, NODE *aNode, const LINE& cur, const SHAPE_LINE_CHAIN& in,
1415 SHAPE_LINE_CHAIN& out )
1416{
1417 SEG a = in.CSegment(0);
1418 SEG center = in.CSegment(1);
1419 SEG b = in.CSegment(2);
1420
1421 DIRECTION_45 dirA ( a );
1422 DIRECTION_45 dirCenter ( center );
1423 DIRECTION_45 dirB ( b );
1424
1425 if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1426 return false;
1427
1428 //VECTOR2I perp = (center.B - center.A).Perpendicular();
1429 VECTOR2I guideA, guideB ;
1430
1431 SEG guide;
1432 int initial;
1433
1434 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1435 if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1436 return false;
1437
1438 {
1439 /*
1440 auto rC = *a.IntersectLines( b );
1441 dbg->AddSegment ( SEG( center.A, rC ), 1 );
1442 dbg->AddSegment ( SEG( center.B, rC ), 2 );
1443 auto perp = dirCenter.Left().Left();
1444
1445 SEG sperp ( center.A, center.A + perp.ToVector() );
1446
1447 auto vpc = sperp.LineProject( rC );
1448 auto vpa = sperp.LineProject( a.A );
1449 auto vpb = sperp.LineProject( b.B );
1450
1451 auto da = (vpc - vpa).EuclideanNorm();
1452 auto db = (vpc - vpb).EuclideanNorm();
1453
1454 auto vp = (da < db) ? vpa : vpb;
1455 dbg->AddSegment ( SEG( vpc, vp ), 5 );
1456
1457
1458 guide = SEG ( vpc, vp );
1459 */
1460 }
1461
1462 int da = a.Length();
1463 int db = b.Length();
1464
1465 if( da < db )
1466 guide = a;
1467 else
1468 guide = b;
1469
1470 initial = guide.Length();
1471
1472 int step = initial;
1473 int current = step;
1474 SHAPE_LINE_CHAIN snew;
1475
1476 while( step > 1 )
1477 {
1478 LINE l( cur );
1479
1480 snew.Clear();
1481 snew.Append( a.A );
1482 snew.Append( a.B + ( a.A - a.B ).Resize( current ) );
1483 snew.Append( b.A + ( b.B - b.A ).Resize( current ) );
1484 snew.Append( b.B );
1485
1486 step /= 2;
1487
1488 l.SetShape(snew);
1489
1490 if( aNode->CheckColliding(&l) )
1491 current -= step;
1492 else if ( current + step >= initial )
1493 current = initial;
1494 else
1495 current += step;
1496
1497 //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1498 //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1499 //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1500
1501 if ( current == initial )
1502 break;
1503
1504
1505 }
1506
1507 out = snew;
1508
1509 //dbg->AddLine ( snew, 3, 100000 );
1510
1511 return true;
1512}
1513
1514
1515void Tighten( NODE *aNode, const SHAPE_LINE_CHAIN& aOldLine, const LINE& aNewLine,
1516 LINE& aOptimized )
1517{
1518 LINE tmp;
1519
1520 if( aNewLine.SegmentCount() < 3 )
1521 return;
1522
1523 SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1524
1525 for( int step = 0; step < 3; step++ )
1526 {
1527 current.Simplify2();
1528
1529 for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1530 {
1531 SHAPE_LINE_CHAIN l_in, l_out;
1532
1533 l_in = current.Slice( i, i + 3 );
1534
1535 for( int dir = 0; dir <= 1; dir++ )
1536 {
1537 if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1538 {
1539 SHAPE_LINE_CHAIN opt = current;
1540 opt.Replace( i, i + 3, l_out );
1541 auto optArea = std::abs( shovedArea( aOldLine, opt ) );
1542 auto prevArea = std::abs( shovedArea( aOldLine, current ) );
1543
1544 if( optArea < prevArea )
1545 current = opt;
1546
1547 break;
1548 }
1549 }
1550 }
1551 }
1552
1553 aOptimized = LINE( aNewLine, current );
1554
1555 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1556 //dbg->AddLine ( current, 4, 100000 );
1557}
1558
1559}
constexpr size_type GetWidth() const
Definition: box2.h:214
constexpr size_type GetHeight() const
Definition: box2.h:215
constexpr bool Contains(const Vec &aPoint) const
Definition: box2.h:168
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 IsHorizontal() const
Definition: eda_angle.h:138
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:98
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
Definition: pns_item.h:230
const PNS_LAYER_RANGE & Layers() const
Definition: pns_item.h:200
virtual NET_HANDLE Net() const
Definition: pns_item.h:198
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:171
virtual int Layer() const
Definition: pns_item.h:204
bool Collide(const ITEM *aHead, const NODE *aNode, int aLayer, COLLISION_SEARCH_CONTEXT *aCtx=nullptr) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:303
bool OfKind(int aKindMask) const
Definition: pns_item.h:179
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:303
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:62
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:146
int ArcCount() const
Definition: pns_line.h:142
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:127
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:138
int CountCorners(int aAngles) const
Definition: pns_line.cpp:167
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:137
int SegmentCount() const
Definition: pns_line.h:140
int PointCount() const
Definition: pns_line.h:141
bool EndsWithVia() const
Definition: pns_line.h:190
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:147
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:157
Keep the router "world" - i.e.
Definition: pns_node.h:231
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:1245
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, PNS_LAYER_RANGE aLayerMask=PNS_LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1656
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:223
ROUTING_SETTINGS & Settings()
Definition: pns_router.h:197
static ROUTER * GetInstance()
Definition: pns_router.cpp:81
DIRECTION_45::CORNER_MODE GetCornerMode() const
VECTOR2I Offset() const
Definition: pns_solid.h:117
const SHAPE * Shape(int aLayer) const override
Return the geometrical shape of the item.
Definition: pns_solid.h:92
bool Matches(const T &aOther) const
Definition: ranged_num.h:44
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:351
int Length() const
Return the length (this).
Definition: seg.h:333
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:489
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:276
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:338
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
EDA_ANGLE Angle(const SEG &aOther) const
Determine the smallest angle between two segments.
Definition: seg.cpp:97
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.
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.
SHAPE_LINE_CHAIN & Simplify2(bool aRemoveColinear=true)
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:160
const VECTOR2I GetSize() const
Definition: shape_rect.h:168
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:385
T y
Definition: vector3.h:64
T x
Definition: vector3.h:63
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:356
void * NET_HANDLE
Definition: pns_item.h:55
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
@ 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)
VECTOR2I center
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:229
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695