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 The 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
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22#include <core/typeinfo.h>
24#include <geometry/shape_rect.h>
26
27#include <cmath>
28
29#include "pns_arc.h"
30#include "pns_line.h"
31#include "pns_diff_pair.h"
32#include "pns_node.h"
33#include "pns_solid.h"
34#include "pns_optimizer.h"
35
36#include "pns_utils.h"
37#include "pns_router.h"
38#include "pns_debug_decorator.h"
39
40
41namespace PNS {
42
43
44int COST_ESTIMATOR::CornerCost( const SEG& aA, const SEG& aB )
45{
46 DIRECTION_45 dir_a( aA ), dir_b( aB );
47
48 switch( dir_a.Angle( dir_b ) )
49 {
50 case DIRECTION_45::ANG_OBTUSE: return 10;
51 case DIRECTION_45::ANG_STRAIGHT: return 5;
52 case DIRECTION_45::ANG_ACUTE: return 50;
53 case DIRECTION_45::ANG_RIGHT: return 30;
54 case DIRECTION_45::ANG_HALF_FULL: return 60;
55 default: return 100;
56 }
57}
58
59
61{
62 int total = 0;
63
64 for( int i = 0; i < aLine.SegmentCount() - 1; ++i )
65 total += CornerCost( aLine.CSegment( i ), aLine.CSegment( i + 1 ) );
66
67 return total;
68}
69
70
72{
73 return CornerCost( aLine.CLine() );
74}
75
76
77void COST_ESTIMATOR::Add( const LINE& aLine )
78{
79 m_lengthCost += aLine.CLine().Length();
80 m_cornerCost += CornerCost( aLine );
81}
82
83
84void COST_ESTIMATOR::Remove( const LINE& aLine )
85{
86 m_lengthCost -= aLine.CLine().Length();
87 m_cornerCost -= CornerCost( aLine );
88}
89
90
91void COST_ESTIMATOR::Replace( const LINE& aOldLine, const LINE& aNewLine )
92{
93 m_lengthCost -= aOldLine.CLine().Length();
94 m_cornerCost -= CornerCost( aOldLine );
95 m_lengthCost += aNewLine.CLine().Length();
96 m_cornerCost += CornerCost( aNewLine );
97}
98
99
100bool COST_ESTIMATOR::IsBetter( const COST_ESTIMATOR& aOther, double aLengthTolerance,
101 double aCornerTolerance ) const
102{
103 if( aOther.m_cornerCost < m_cornerCost && aOther.m_lengthCost < m_lengthCost )
104 return true;
105 else if( aOther.m_cornerCost < m_cornerCost * aCornerTolerance &&
106 aOther.m_lengthCost < m_lengthCost * aLengthTolerance )
107 return true;
108
109 return false;
110}
111
112
114 m_world( aWorld ),
115 m_collisionKindMask( ITEM::ANY_T ),
118{
119}
120
121
123{
124 for( OPT_CONSTRAINT* c : m_constraints )
125 delete c;
126
127 m_constraints.clear();
128}
129
130
132{
133 CACHE_VISITOR( const ITEM* aOurItem, NODE* aNode, int aMask ) :
134 m_ourItem( aOurItem ),
135 m_collidingItem( nullptr ),
136 m_node( aNode ),
137 m_mask( aMask )
138 {}
139
140 bool operator()( ITEM* aOtherItem )
141 {
142 if( !( m_mask & aOtherItem->Kind() ) )
143 return true;
144
145 // TODO(JE) viastacks
146 if( !aOtherItem->Collide( m_ourItem, m_node, m_ourItem->Layer() ) )
147 return true;
148
149 m_collidingItem = aOtherItem;
150 return false;
151 }
152
157};
158
159
160void OPTIMIZER::cacheAdd( ITEM* aItem, bool aIsStatic = false )
161{
162 if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
163 return;
164
165 m_cache.Add( aItem );
166 m_cacheTags[aItem].m_hits = 1;
167 m_cacheTags[aItem].m_isStatic = aIsStatic;
168}
169
170
171void OPTIMIZER::removeCachedSegments( LINE* aLine, int aStartVertex, int aEndVertex )
172{
173 if( !aLine->IsLinked() )
174 return;
175
176 auto links = aLine->Links();
177
178 if( aEndVertex < 0 )
179 aEndVertex += aLine->PointCount();
180
181 for( int i = aStartVertex; i < aEndVertex - 1; i++ )
182 {
183 LINKED_ITEM* s = links[i];
184 m_cacheTags.erase( s );
185 m_cache.Remove( s );
186 }
187}
188
189
191{
192 if( aItem->Kind() == ITEM::LINE_T )
193 removeCachedSegments( static_cast<LINE*>( aItem ) );
194}
195
196
197void OPTIMIZER::ClearCache( bool aStaticOnly )
198{
199 if( !aStaticOnly )
200 {
201 m_cacheTags.clear();
202 m_cache.Clear();
203 return;
204 }
205
206 for( const std::pair<ITEM* const, CACHED_ITEM>& entry : m_cacheTags )
207 {
208 if( entry.second.m_isStatic )
209 m_cache.Remove( entry.first );
210 }
211
212 std::erase_if( m_cacheTags,
213 []( const std::pair<ITEM* const, CACHED_ITEM>& entry )
214 {
215 return entry.second.m_isStatic;
216 } );
217}
218
219
220bool AREA_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
221 const SHAPE_LINE_CHAIN& aCurrentPath,
222 const SHAPE_LINE_CHAIN& aReplacement )
223{
224 const VECTOR2I& p1 = aCurrentPath.CPoint( aVertex1 );
225 const VECTOR2I& p2 = aCurrentPath.CPoint( aVertex2 );
226
227 bool p1_in = m_allowedArea.Contains( p1 );
228 bool p2_in = m_allowedArea.Contains( p2 );
229
230 if( p1_in && p2_in )
231 return true;
232
233 if( aVertex1 < aCurrentPath.PointCount() - 1 && !p1_in && p2_in
234 && m_allowedArea.Contains( aCurrentPath.CPoint( aVertex1 + 1 ) ) )
235 return aReplacement.CSegment( 0 ).Angle( aCurrentPath.CSegment( aVertex1 ) ).IsHorizontal();
236
237 if( p1_in && !p2_in && m_allowedArea.Contains( aCurrentPath.CPoint( aVertex2 - 1 ) ) )
238 return aReplacement.CSegment( -1 )
239 .Angle( aCurrentPath.CSegment( aVertex2 - 1 ) )
240 .IsHorizontal();
241
242 //PNS_DBG( dbg, AddShape, m_allowedArea, YELLOW, 10000, wxT( "drag-affected-area" ) );
243 //PNS_DBG( dbg, AddPoint, p1, YELLOW, 1000000, wxT( "drag-p1" ) );
244 //PNS_DBG( dbg, AddPoint, p2, YELLOW, 1000000, wxT( "drag-p2" ) );
245
246 return false;
247}
248
249
250bool PRESERVE_VERTEX_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
251 const SHAPE_LINE_CHAIN& aCurrentPath,
252 const SHAPE_LINE_CHAIN& aReplacement )
253{
254 bool cv = false;
255
256 for( int i = aVertex1; i < aVertex2; i++ )
257 {
258 SEG::ecoord dist = aCurrentPath.CSegment(i).SquaredDistance( m_v );
259
260 if ( dist <= 1 )
261 {
262 cv = true;
263 break;
264 }
265 }
266
267 if( !cv )
268 return true;
269
270 for( int i = 0; i < aReplacement.SegmentCount(); i++ )
271 {
272 SEG::ecoord dist = aReplacement.CSegment(i).SquaredDistance( m_v );
273
274 if ( dist <= 1 )
275 return true;
276 }
277
278 return false;
279}
280
281
282bool PRESERVE_SEGMENTS_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
283 const SHAPE_LINE_CHAIN& aCurrentPath,
284 const SHAPE_LINE_CHAIN& aReplacement )
285{
286
287 /*
288 auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
289 PNS_DBG( dbg, Message, wxString::Format("pre chk %d %d", aVertex1, aVertex2 ));
290 */
291 for( const SEG& rSeg : m_segs )
292 {
293 for (int i = aVertex1; i < aVertex2; i++ )
294 {
295 const SEG& cSeg = aCurrentPath.CSegment( i );
296
297 /*
298 PNS_DBG( dbg, AddShape, rSeg, YELLOW, 100000, wxT("rseg"));
299 PNS_DBG( dbg, AddShape, cSeg, YELLOW, 100000, wxT("cseg"));
300 */
301
302 if( rSeg.ApproxOverlaps( cSeg ) )
303 return false;
304 }
305 }
306
307
308 return true;
309}
310
311
312
313bool RESTRICT_VERTEX_RANGE_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
314 const SHAPE_LINE_CHAIN& aCurrentPath,
315 const SHAPE_LINE_CHAIN& aReplacement )
316{
317 return true;
318}
319
320
321bool CORNER_COUNT_LIMIT_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
322 const SHAPE_LINE_CHAIN& aCurrentPath,
323 const SHAPE_LINE_CHAIN& aReplacement )
324{
325 LINE newPath( *aOriginLine, aCurrentPath );
326 newPath.Line().Replace( aVertex1, aVertex2, aReplacement );
327 newPath.Line().Simplify2();
328 int cc = newPath.CountCorners( m_angleMask );
329
330 if( cc >= m_minCorners )
331 return true;
332
333 // fixme: something fishy with the max corneriness limit
334 // (cc <= m_maxCorners)
335
336 return true;
337}
338
339bool OBTUSE_ONLY_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
340 const SHAPE_LINE_CHAIN& aCurrentPath,
341 const SHAPE_LINE_CHAIN& aReplacement )
342{
343 auto isAngleOk =
344 []( const SEG& aS1, const SEG& aS2 ) -> bool
345 {
346 DIRECTION_45 d1( aS1 );
347 DIRECTION_45 d2( aS2 );
349 };
350
351 int replSegs = aReplacement.SegmentCount();
352
353 if( replSegs < 1 )
354 return true;
355
356 for( int i = 0; i < replSegs - 1; i++ )
357 {
358 if( !isAngleOk( aReplacement.CSegment( i ), aReplacement.CSegment( i + 1 ) ) )
359 return false;
360 }
361
362 int pathSegs = aCurrentPath.SegmentCount();
363
364 SEG firstReplSeg = aReplacement.CSegment( 0 );
365 SEG lastReplSeg = aReplacement.CSegment( replSegs - 1 );
366
367 if( aVertex1 > 0 )
368 {
369 if( !isAngleOk( aCurrentPath.CSegment( aVertex1 - 1 ), firstReplSeg ) )
370 return false;
371 }
372
373 if( aVertex2 < pathSegs )
374 {
375 if( !isAngleOk( lastReplSeg, aCurrentPath.CSegment( aVertex2 ) ) )
376 return false;
377 }
378
379 return true;
380}
381
382
394static bool pointInside2( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aP )
395{
396 if( !aL.IsClosed() || aL.SegmentCount() < 3 )
397 return false;
398
399 int result = 0;
400 size_t cnt = aL.PointCount();
401
402 VECTOR2I ip = aL.CPoint( 0 );
403
404 for( size_t i = 1; i <= cnt; ++i )
405 {
406 VECTOR2I ipNext = ( i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ) );
407
408 if( ipNext.y == aP.y )
409 {
410 if( ( ipNext.x == aP.x )
411 || ( ip.y == aP.y && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
412 return true; // pt on polyground boundary
413 }
414
415 if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
416 {
417 if( ip.x >=aP.x )
418 {
419 if( ipNext.x >aP.x )
420 {
421 result = 1 - result;
422 }
423 else
424 {
425 double d = static_cast<double>( ip.x - aP.x ) *
426 static_cast<double>( ipNext.y - aP.y ) -
427 static_cast<double>( ipNext.x - aP.x ) *
428 static_cast<double>( ip.y - aP.y );
429
430 if( !d )
431 return true; // pt on polyground boundary
432
433 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
434 result = 1 - result;
435 }
436 }
437 else
438 {
439 if( ipNext.x >aP.x )
440 {
441 double d = ( (double) ip.x - aP.x ) * ( (double) ipNext.y - aP.y )
442 - ( (double) ipNext.x - aP.x ) * ( (double) ip.y - aP.y );
443
444 if( !d )
445 return true; // pt on polyground boundary
446
447 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
448 result = 1 - result;
449 }
450 }
451 }
452
453 ip = ipNext;
454 }
455
456 return result > 0;
457}
458
459
460bool KEEP_TOPOLOGY_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
461 const SHAPE_LINE_CHAIN& aCurrentPath,
462 const SHAPE_LINE_CHAIN& aReplacement )
463{
464 SHAPE_LINE_CHAIN encPoly = aOriginLine->CLine().Slice( aVertex1, aVertex2 );
465
466 // fixme: this is a remarkably shitty implementation...
467 encPoly.Append( aReplacement.Reverse() );
468 encPoly.SetClosed( true );
469
470 BOX2I bb = encPoly.BBox();
471 std::vector<JOINT*> joints;
472
473 int cnt = m_world->QueryJoints( bb, joints, aOriginLine->Layers(), ITEM::SOLID_T );
474
475 if( !cnt )
476 return true;
477
478 for( JOINT* j : joints )
479 {
480 if( j->Net() == aOriginLine->Net() )
481 continue;
482
483 if( pointInside2( encPoly, j->Pos() ) )
484 {
485 bool falsePositive = false;
486
487 for( int k = 0; k < encPoly.PointCount(); k++ )
488 {
489 if( encPoly.CPoint(k) == j->Pos() )
490 {
491 falsePositive = true;
492 break;
493 }
494 }
495
496 if( !falsePositive )
497 {
498 //dbg->AddPoint(j->Pos(), 5);
499 return false;
500 }
501 }
502 }
503
504 return true;
505}
506
507
508bool OPTIMIZER::checkColliding( ITEM* aItem, bool aUpdateCache )
509{
510 return static_cast<bool>( m_world->CheckColliding( aItem, m_collisionKindMask ) );
511}
512
513
515{
516 m_constraints.push_back( aConstraint );
517}
518
519
520bool OPTIMIZER::checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
521 const SHAPE_LINE_CHAIN& aCurrentPath,
522 const SHAPE_LINE_CHAIN& aReplacement )
523{
524 for( OPT_CONSTRAINT* c : m_constraints )
525 {
526 if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
527 return false;
528 }
529
530 return true;
531}
532
533
534bool OPTIMIZER::checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath )
535{
536 LINE tmp( *aLine, aOptPath );
537
538 return checkColliding( &tmp );
539}
540
541
543{
544 SHAPE_LINE_CHAIN& line = aLine->Line();
545
546 int step = line.PointCount() - 3;
547 int segs_pre = line.SegmentCount();
548
549 if( step < 0 )
550 return false;
551
552 SHAPE_LINE_CHAIN current_path( line );
553
554 while( true )
555 {
556 int n_segs = current_path.SegmentCount();
557 int max_step = n_segs - 2;
558
559 if( step > max_step )
560 step = max_step;
561
562 if( step < 2 )
563 {
564 line = std::move( current_path );
565 return line.SegmentCount() < segs_pre;
566 }
567
568 bool found_anything = false;
569
570 for( int n = 0; n < n_segs - step; n++ )
571 {
572 const SEG s1 = current_path.CSegment( n );
573 const SEG s2 = current_path.CSegment( n + step );
574 SEG s1opt, s2opt;
575
576 if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
577 {
578 VECTOR2I ip = *s1.IntersectLines( s2 );
579
580 s1opt = SEG( s1.A, ip );
581 s2opt = SEG( ip, s2.B );
582
583 if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
584 {
585 SHAPE_LINE_CHAIN opt_path;
586 opt_path.Append( s1opt.A );
587 opt_path.Append( s1opt.B );
588 opt_path.Append( s2opt.B );
589
590 LINE opt_track( *aLine, opt_path );
591
592 if( !checkColliding( &opt_track ) )
593 {
594 current_path.Replace( s1.Index() + 1, s2.Index(), ip );
595
596 // removeCachedSegments(aLine, s1.Index(), s2.Index());
597 n_segs = current_path.SegmentCount();
598 found_anything = true;
599 break;
600 }
601 }
602 }
603 }
604
605 if( !found_anything )
606 {
607 if( step <= 2 )
608 {
609 line = std::move( current_path );
610 return line.SegmentCount() < segs_pre;
611 }
612
613 step--;
614 }
615 }
616}
617
618
620{
621 SHAPE_LINE_CHAIN& line = aLine->Line();
622 int step = line.SegmentCount() - 1;
623
624 int segs_pre = line.SegmentCount();
625
626 line.Simplify2();
627
628 if( step < 0 )
629 return false;
630
631 SHAPE_LINE_CHAIN current_path( line );
632
633 while( true )
634 {
635 int n_segs = current_path.SegmentCount();
636 int max_step = n_segs - 2;
637
638 if( step > max_step )
639 step = max_step;
640
641 if( step < 1 )
642 break;
643
644 bool found_anything = mergeStep( aLine, current_path, step );
645
646 if( !found_anything )
647 step--;
648
649 if( !step )
650 break;
651 }
652
653 aLine->SetShape( current_path );
654
655 return current_path.SegmentCount() < segs_pre;
656}
657
658
660{
661 SHAPE_LINE_CHAIN& line = aLine->Line();
662
663 int nSegs = line.SegmentCount();
664
665 for( int segIdx = 0; segIdx < line.SegmentCount() - 1; ++segIdx )
666 {
667 SEG s1 = line.CSegment( segIdx );
668 SEG s2 = line.CSegment( segIdx + 1 );
669
670 // Skip zero-length segs caused by abutting arcs
671 if( s1.SquaredLength() == 0 || s2.SquaredLength() == 0 )
672 continue;
673
674 if( s1.Collinear( s2 ) && !line.IsPtOnArc( segIdx + 1 ) )
675 {
676 line.Remove( segIdx + 1 );
677 }
678 }
679
680 return line.SegmentCount() < nSegs;
681}
682
683
684bool OPTIMIZER::Optimize( const LINE* aLine, LINE* aResult, LINE* aRoot )
685{
686 if( !aResult )
687 return false;
688
689 *aResult = *aLine;
690 aResult->ClearLinks();
691
692 bool hasArcs = aLine->ArcCount();
693 bool rv = false;
694
695 if( (m_effortLevel & LIMIT_CORNER_COUNT) && aRoot )
696 {
697 const int angleMask = DIRECTION_45::ANG_OBTUSE;
698 int rootObtuseCorners = aRoot->CountCorners( angleMask );
699 auto c = new CORNER_COUNT_LIMIT_CONSTRAINT( m_world, rootObtuseCorners,
700 aLine->SegmentCount(), angleMask );
701 //PNS_DBG( dbg, Message,
702 // wxString::Format( "opt limit-corner-count root %d maxc %d mask %x",
703 // rootObtuseCorners, aLine->SegmentCount(), angleMask ) );
704
705 addConstraint( c );
706 }
707
709 {
711 addConstraint( c );
712 }
713
715 {
717 addConstraint( c );
718 }
719
721 {
724 addConstraint( c );
725 }
726
728 {
731 //PNS_DBG( dbg, AddShape, &r, YELLOW, 0, wxT( "area-constraint" ) );
732 addConstraint( c );
733 }
734
736 {
737 auto c = new KEEP_TOPOLOGY_CONSTRAINT( m_world );
738 addConstraint( c );
739 }
740
742 {
743 auto c = new OBTUSE_ONLY_CONSTRAINT( m_world );
744 addConstraint( c );
745 }
746
748 rv |= dragFixCorners( aResult );
749
750 // TODO: Fix for arcs
751 if( !hasArcs && m_effortLevel & MERGE_SEGMENTS )
752 rv |= mergeFull( aResult );
753
754 // TODO: Fix for arcs
755 if( !hasArcs && m_effortLevel & MERGE_OBTUSE )
756 rv |= mergeObtuse( aResult );
757
759 rv |= mergeColinear( aResult );
760
761 // TODO: Fix for arcs
762 if( !hasArcs && m_effortLevel & SMART_PADS )
763 rv |= runSmartPads( aResult );
764
765 // TODO: Fix for arcs
766 if( !hasArcs && m_effortLevel & FANOUT_CLEANUP )
767 rv |= fanoutCleanup( aResult );
768
769 return rv;
770}
771
772
773/*
774 * Check if aVIdx is a bad corner; if so, replace it if possible with an obtuse corner
775 */
776bool OPTIMIZER::dragFixCorner( LINE* aLine, int aVIdx )
777{
778 SHAPE_LINE_CHAIN& path = aLine->Line();
779
780 if( aVIdx <= 0 || aVIdx >= path.PointCount() - 1 )
781 return false;
782
783 if( path.IsArcSegment( aVIdx - 1 ) || path.IsArcSegment( aVIdx ) )
784 return false;
785
786 const SEG s1 = path.CSegment( aVIdx - 1 );
787 const SEG s2 = path.CSegment( aVIdx );
788
790
792 return false;
793
795 {
796 if( !m_restrictArea.Contains( path.CPoint( aVIdx ) ) )
797 return false;
798 }
799
800 SHAPE_LINE_CHAIN bestBypass;
801 double bestArea = std::numeric_limits<double>::max();
802
803 for( int posture = 0; posture < 2; posture++ )
804 {
805 SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, posture );
806
807 if( bypass.SegmentCount() < 1 )
808 continue;
809
810 if( checkColliding( aLine, bypass ) )
811 continue;
812
813 SHAPE_LINE_CHAIN loop;
814 loop.Append( s1.A );
815 loop.Append( path.CPoint( aVIdx ) );
816 loop.Append( s2.B );
817
818 for( int j = bypass.PointCount() - 1; j >= 0; j-- )
819 loop.Append( bypass.CPoint( j ) );
820
821 loop.SetClosed( true );
822
823 if( double area = std::abs( loop.Area() ); area < bestArea )
824 {
825 bestArea = area;
826 bestBypass = bypass;
827 }
828 }
829
830 if( bestBypass.SegmentCount() < 1 )
831 return false;
832
833 path.Replace( s1.Index(), s2.Index(), bestBypass );
834 path.Simplify2();
835 return true;
836}
837
838
840{
842 return false;
843
844 SHAPE_LINE_CHAIN& path = aLine->Line();
845
846 if( path.SegmentCount() == 0 )
847 return false;
848
850
851 int anchorIdx = path.Find( anchor );
852
853 if( anchorIdx <= 0 )
854 return false;
855
856 if( path.IsArcSegment( anchorIdx - 1 ) || path.IsArcSegment( anchorIdx ) )
857 return false;
858
859 bool changed = false;
860
861 if( anchorIdx >= path.PointCount() - 1 )
862 {
863 if( anchorIdx > 0 )
864 changed = dragFixCorner( aLine, anchorIdx - 1 );
865
866 return changed;
867 }
868
870 DIRECTION_45( path.CSegment( anchorIdx - 1 ) ).Angle( DIRECTION_45( path.CSegment( anchorIdx ) ) );
871
873 {
874 changed |= dragFixCorner( aLine, anchorIdx - 1 );
875
876 path.Split( anchor );
877 anchorIdx = path.Find( anchor );
878
879 if( anchorIdx > 0 && anchorIdx < path.PointCount() - 1 )
880 changed |= dragFixCorner( aLine, anchorIdx + 1 );
881 }
882 else
883 {
884 changed = dragFixCorner( aLine, anchorIdx );
885 }
886
887 return changed;
888}
889
890
891bool OPTIMIZER::mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentPath, int step )
892{
893 int n_segs = aCurrentPath.SegmentCount();
894
895 int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
896
897 if( aLine->SegmentCount() < 2 )
898 return false;
899
901 bool is90mode = cornerMode == DIRECTION_45::MITERED_90 || cornerMode == DIRECTION_45::ROUNDED_90;
902
903 DIRECTION_45 orig_start( aLine->CSegment( 0 ), is90mode );
904 DIRECTION_45 orig_end( aLine->CSegment( -1 ), is90mode );
905
906
907 for( int n = 0; n < n_segs - step; n++ )
908 {
909 // Do not attempt to merge false segments that are part of an arc
910 if( aCurrentPath.IsArcSegment( n )
911 || aCurrentPath.IsArcSegment( static_cast<std::size_t>( n ) + step ) )
912 {
913 continue;
914 }
915
916 const SEG s1 = aCurrentPath.CSegment( n );
917 const SEG s2 = aCurrentPath.CSegment( n + step );
918
920 SHAPE_LINE_CHAIN* picked = nullptr;
921 int cost[2];
922
923 for( int i = 0; i < 2; i++ )
924 {
925 SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i, cornerMode );
926 cost[i] = INT_MAX;
927
928 bool ok = false;
929
930 if( !checkColliding( aLine, bypass ) )
931 {
932 ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
933 }
934
935 if( ok )
936 {
937 path[i] = aCurrentPath;
938 path[i].Replace( s1.Index(), s2.Index(), bypass );
939 path[i].Simplify2();
940 cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
941 }
942 }
943
944 if( cost[0] < cost_orig && cost[0] < cost[1] )
945 picked = &path[0];
946 else if( cost[1] < cost_orig )
947 picked = &path[1];
948
949 if( picked )
950 {
951 n_segs = aCurrentPath.SegmentCount();
952 aCurrentPath = *picked;
953 return true;
954 }
955 }
956
957 return false;
958}
959
960
962 bool aPermitDiagonal ) const
963{
964 BREAKOUT_LIST breakouts;
965
967 {
968 const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
970 VECTOR2I p0 = cir->GetCenter();
971 VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
972
973 RotatePoint( v0, -angle );
974
975 l.Append( p0 );
976 l.Append( p0 + v0 );
977 breakouts.push_back( l );
978 }
979
980 return breakouts;
981}
982
983
985 bool aPermitDiagonal ) const
986{
987 BREAKOUT_LIST breakouts;
988 const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape( -1 ) );
989
990 BOX2I bbox = convex->BBox( 0 );
991 VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
992 // must be large enough to guarantee intersecting the convex polygon
993 int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
994 EDA_ANGLE increment = ( aPermitDiagonal ? ANGLE_45 : ANGLE_90 );
995
996 for( EDA_ANGLE angle = ANGLE_0; angle < ANGLE_360; angle += increment )
997 {
999 VECTOR2I v0( p0 + VECTOR2I( length, 0 ) );
1000 RotatePoint( v0, p0, -angle );
1001
1002 std::vector<SHAPE_LINE_CHAIN::INTERSECTION> intersections;
1003 int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
1004
1005 // if n == 1 intersected a segment
1006 // if n == 2 intersected the common point of 2 segments
1007 // n == 0 can not happen I think, but...
1008 if( n > 0 )
1009 {
1010 l.Append( p0 );
1011
1012 // for a breakout distance relative to the distance between
1013 // center and polygon edge
1014 //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
1015
1016 // for an absolute breakout distance, e.g. 0.1 mm
1017 //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
1018
1019 // for the breakout right on the polygon edge
1020 l.Append( intersections[0].p );
1021
1022 breakouts.push_back( l );
1023 }
1024 }
1025
1026 return breakouts;
1027}
1028
1029
1031 bool aPermitDiagonal ) const
1032{
1033 const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
1034 VECTOR2I s = rect->GetSize();
1035 VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
1036
1037 BREAKOUT_LIST breakouts;
1038 breakouts.reserve( 12 );
1039
1040 VECTOR2I d_offset;
1041
1042 d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
1043 d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
1044
1045 VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
1046 VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
1047
1048 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
1049 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
1050 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
1051 breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
1052
1053 if( aPermitDiagonal )
1054 {
1055 int l = aWidth + std::min( s.x, s.y ) / 2;
1056
1057 if( s.x >= s.y )
1058 {
1059 breakouts.emplace_back(
1060 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
1061 breakouts.emplace_back(
1062 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
1063 breakouts.emplace_back(
1064 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
1065 breakouts.emplace_back(
1066 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
1067 }
1068 else
1069 {
1070 // fixme: this could be done more efficiently
1071 breakouts.emplace_back(
1072 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
1073 breakouts.emplace_back(
1074 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
1075 breakouts.emplace_back(
1076 SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
1077 breakouts.emplace_back(
1078 SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
1079 }
1080 }
1081
1082 return breakouts;
1083}
1084
1085
1087 bool aPermitDiagonal ) const
1088{
1089 switch( aItem->Kind() )
1090 {
1091 case ITEM::VIA_T:
1092 {
1093 const VIA* via = static_cast<const VIA*>( aItem );
1094 // TODO(JE) padstacks -- computeBreakouts needs to have a layer argument
1095 return circleBreakouts( aWidth, via->Shape( 0 ), aPermitDiagonal );
1096 }
1097
1098 case ITEM::SOLID_T:
1099 {
1100 const SHAPE* shape = aItem->Shape( -1 );
1101
1102 switch( shape->Type() )
1103 {
1104 case SH_RECT:
1105 return rectBreakouts( aWidth, shape, aPermitDiagonal );
1106
1107 case SH_SEGMENT:
1108 {
1109 const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
1110 const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
1111 return rectBreakouts( aWidth, &rect, aPermitDiagonal );
1112 }
1113
1114 case SH_CIRCLE:
1115 return circleBreakouts( aWidth, shape, aPermitDiagonal );
1116
1117 case SH_SIMPLE:
1118 return customBreakouts( aWidth, aItem, aPermitDiagonal );
1119
1120 default:
1121 break;
1122 }
1123
1124 break;
1125 }
1126
1127 default:
1128 break;
1129 }
1130
1131 return BREAKOUT_LIST();
1132}
1133
1134
1135ITEM* OPTIMIZER::findPadOrVia( int aLayer, NET_HANDLE aNet, const VECTOR2I& aP ) const
1136{
1137 const JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
1138
1139 if( !jt )
1140 return nullptr;
1141
1142 for( ITEM* item : jt->LinkList() )
1143 {
1144 if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
1145 return item;
1146 }
1147
1148 return nullptr;
1149}
1150
1151
1152int OPTIMIZER::smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex )
1153{
1154 DIRECTION_45 dir;
1155
1156 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
1158
1159 typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
1160 std::vector<RtVariant> variants;
1161
1162 SOLID* solid = dyn_cast<SOLID*>( aPad );
1163
1164 // don't do optimized connections for offset pads
1165 if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
1166 return -1;
1167
1168 // don't do optimization on vias, they are always round at the moment and the optimizer
1169 // will possibly mess up an intended via exit posture
1170 if( aPad->Kind() == ITEM::VIA_T )
1171 return -1;
1172
1173 BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
1174 SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
1175 int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
1176
1177 // Start at 1 to find a potentially better breakout (0 is the pad connection)
1178 for( int p = 1; p <= p_end; p++ )
1179 {
1180 // If the line is contained inside the pad, don't optimize
1181 if( solid && solid->Shape( -1 ) && !solid->Shape( -1 )->Collide(
1182 SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
1183 {
1184 continue;
1185 }
1186
1187 for( SHAPE_LINE_CHAIN & breakout : breakouts )
1188 {
1189 for( int diag = 0; diag < 2; diag++ )
1190 {
1192 SHAPE_LINE_CHAIN connect = dir.BuildInitialTrace(
1193 breakout.CLastPoint(), line.CPoint( p ), diag == 0 );
1194
1195 DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
1196
1197 if( !connect.SegmentCount() )
1198 continue;
1199
1200 int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
1201
1202 if( ang1 & ForbiddenAngles )
1203 continue;
1204
1205 if( breakout.Length() > line.Length() )
1206 continue;
1207
1208 v = breakout;
1209 v.Append( connect );
1210
1211 for( int i = p + 1; i < line.PointCount(); i++ )
1212 v.Append( line.CPoint( i ) );
1213
1214 LINE tmp( *aLine, v );
1215 int cc = tmp.CountCorners( ForbiddenAngles );
1216
1217 if( cc == 0 )
1218 {
1219 RtVariant vp;
1220 std::get<0>( vp ) = p;
1221 std::get<1>( vp ) = breakout.Length();
1222 std::get<2>( vp ) = aEnd ? v.Reverse() : v;
1223 std::get<2>( vp ).Simplify2();
1224 variants.push_back( std::move( vp ) );
1225 }
1226 }
1227 }
1228 }
1229
1230 // We attempt to minimize the corner cost (minimizes the segments and types of corners)
1231 // but given two, equally valid costs, we want to pick the longer pad exit. The logic
1232 // here is that if the pad is oblong, the track should not exit the shorter side and parallel
1233 // the pad but should follow the pad's preferential direction before exiting.
1234 // The baseline guess is to start with the existing line the user has drawn.
1235 int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
1236 long long int max_length = 0;
1237 bool found = false;
1238 int p_best = -1;
1239 SHAPE_LINE_CHAIN l_best;
1240
1241 for( RtVariant& vp : variants )
1242 {
1243 LINE tmp( *aLine, std::get<2>( vp ) );
1244 int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
1245 long long int len = std::get<1>( vp );
1246
1247 if( !checkColliding( &tmp ) )
1248 {
1249 if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1250 {
1251 l_best = std::get<2>( vp );
1252 p_best = std::get<0>( vp );
1253 found = true;
1254
1255 if( cost <= min_cost )
1256 max_length = std::max<int>( len, max_length );
1257
1258 min_cost = std::min( cost, min_cost );
1259 }
1260 }
1261 }
1262
1263 if( found )
1264 {
1265 aLine->SetShape( l_best );
1266 return p_best;
1267 }
1268
1269 return -1;
1270}
1271
1272
1274{
1275 SHAPE_LINE_CHAIN& line = aLine->Line();
1276
1277 if( line.PointCount() < 3 )
1278 return false;
1279
1280 VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CLastPoint();
1281
1282 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1283 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1284
1285 int vtx = -1;
1286
1287 if( startPad )
1288 vtx = smartPadsSingle( aLine, startPad, false, 3 );
1289
1290 if( endPad )
1291 smartPadsSingle( aLine, endPad, true,
1292 vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1293
1294 aLine->Line().Simplify2();
1295
1296 return true;
1297}
1298
1299
1300bool OPTIMIZER::Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld, const VECTOR2I& aV )
1301{
1302 OPTIMIZER opt( aWorld );
1303
1304 opt.SetEffortLevel( aEffortLevel );
1305 opt.SetCollisionMask( -1 );
1306
1307 if( aEffortLevel & OPTIMIZER::PRESERVE_VERTEX )
1308 opt.SetPreserveVertex( aV );
1309
1310 LINE tmp( *aLine );
1311 return opt.Optimize( &tmp, aLine );
1312}
1313
1314
1316{
1317 if( aLine->PointCount() < 3 )
1318 return false;
1319
1321
1322 VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CLastPoint();
1323
1324 ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1325 ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1326
1327 int thr = aLine->Width() * 10;
1328 int len = aLine->CLine().Length();
1329
1330 if( !startPad )
1331 return false;
1332
1333 bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1334 bool endMatch = false;
1335
1336 if(endPad)
1337 {
1338 endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1339 }
1340 else
1341 {
1342 endMatch = aLine->EndsWithVia();
1343 }
1344
1345 if( startMatch && endMatch && len < thr )
1346 {
1347 for( int i = 0; i < 2; i++ )
1348 {
1349 SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i, cornerMode );
1350 LINE repl;
1351 repl = LINE( *aLine, l2 );
1352
1353 if( !m_world->CheckColliding( &repl ) )
1354 {
1355 aLine->SetShape( repl.CLine() );
1356 return true;
1357 }
1358 }
1359 }
1360
1361 return false;
1362}
1363
1364int findCoupledVertices( const VECTOR2I& aVertex, const SEG& aOrigSeg, const SHAPE_LINE_CHAIN& aCoupled,
1365 DIFF_PAIR* aPair, std::vector<int>* aIndices )
1366{
1367 int count = 0;
1368
1369 for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1370 {
1371 SEG s = aCoupled.CSegment( i );
1372 VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1373
1374 if( s.ApproxParallel( aOrigSeg ) )
1375 {
1376 int64_t dist =
1377 int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Dimensions().Width();
1378
1379 if( aPair->GapConstraint().Matches( dist ) )
1380 {
1381 aIndices->push_back( i );
1382 count++;
1383 }
1384 }
1385 }
1386
1387 return count;
1388}
1389
1390
1391bool verifyDpBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aNewRef,
1392 const SHAPE_LINE_CHAIN& aNewCoupled )
1393{
1394 LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1395 LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1396
1397 if( refLine.Collide( &coupledLine, aNode, refLine.Layer() ) )
1398 return false;
1399
1400 if( aNode->CheckColliding ( &refLine ) )
1401 return false;
1402
1403 if( aNode->CheckColliding ( &coupledLine ) )
1404 return false;
1405
1406 return true;
1407}
1408
1409
1410bool coupledBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aRef,
1411 const SHAPE_LINE_CHAIN& aRefBypass, const SHAPE_LINE_CHAIN& aCoupled,
1412 SHAPE_LINE_CHAIN& aNewCoupled )
1413{
1414 std::vector<int> vStartIdx;
1415 vStartIdx.reserve( 1024 );
1416
1417 int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ), aRefBypass.CSegment( 0 ), aCoupled,
1418 aPair, &vStartIdx );
1419 DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1420
1421 int64_t bestLength = -1;
1422 bool found = false;
1423 SHAPE_LINE_CHAIN bestBypass;
1424 int si, ei;
1425
1426 for( int i=0; i< nStarts; i++ )
1427 {
1428 for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1429 {
1430 int delta = std::abs ( vStartIdx[i] - j );
1431
1432 if( delta > 1 )
1433 {
1434 const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1435 SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j), dir.IsDiagonal() );
1436
1437 bool tmp;
1438 int64_t coupledLength;
1439
1440 std::tie( coupledLength, tmp ) = aPair->CoupledLength( aRef, bypass );
1441
1442 SHAPE_LINE_CHAIN newCoupled = aCoupled;
1443
1444 si = vStartIdx[i];
1445 ei = j;
1446
1447 if(si < ei)
1448 newCoupled.Replace( si, ei, bypass );
1449 else
1450 newCoupled.Replace( ei, si, bypass.Reverse() );
1451
1452 if( coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef, newCoupled) )
1453 {
1454 bestBypass = std::move( newCoupled );
1455 bestLength = coupledLength;
1456 found = true;
1457 }
1458 }
1459 }
1460 }
1461
1462 if( found )
1463 aNewCoupled = std::move( bestBypass );
1464
1465 return found;
1466}
1467
1468
1469bool checkDpColliding( NODE* aNode, DIFF_PAIR* aPair, bool aIsP, const SHAPE_LINE_CHAIN& aPath )
1470{
1471 LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1472
1473 return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1474}
1475
1476
1477bool OPTIMIZER::mergeDpStep( DIFF_PAIR* aPair, bool aTryP, int step )
1478{
1479 int n = 1;
1480
1481 SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1482 SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1483
1484 int n_segs = currentPath.SegmentCount() - 1;
1485
1486 bool tmp;
1487 int64_t clenPre;
1488 std::tie(clenPre, tmp) = aPair->CoupledLength( currentPath, coupledPath );
1489 int64_t budget = clenPre / 10; // fixme: come up with something more intelligent here...
1490
1491 while( n < n_segs - step )
1492 {
1493 const SEG s1 = currentPath.CSegment( n );
1494 const SEG s2 = currentPath.CSegment( n + step );
1495
1496 DIRECTION_45 dir1( s1 );
1497 DIRECTION_45 dir2( s2 );
1498
1499 if( dir1.IsObtuse( dir2 ) )
1500 {
1502 dir1.IsDiagonal() );
1503 SHAPE_LINE_CHAIN newRef;
1504 SHAPE_LINE_CHAIN newCoup;
1505 int64_t deltaCoupled = -1, deltaUni = -1;
1506
1507 newRef = currentPath;
1508 newRef.Replace( s1.Index(), s2.Index(), bypass );
1509 bool tmp2;
1510 std::tie(deltaUni, tmp2) = aPair->CoupledLength ( newRef, coupledPath );
1511 deltaUni += (- clenPre + budget);
1512
1513 if( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1514 {
1515 std::tie(deltaCoupled, tmp) = aPair->CoupledLength( newRef, newCoup );
1516 deltaCoupled += (- clenPre + budget);
1517
1518 if( deltaCoupled >= 0 )
1519 {
1520 newRef.Simplify2();
1521 newCoup.Simplify2();
1522
1523 aPair->SetShape( newRef, newCoup, !aTryP );
1524 return true;
1525 }
1526 }
1527 else if( deltaUni >= 0 && verifyDpBypass( m_world, aPair, aTryP, newRef, coupledPath ) )
1528 {
1529 newRef.Simplify2();
1530 coupledPath.Simplify2();
1531
1532 aPair->SetShape( newRef, coupledPath, !aTryP );
1533 return true;
1534 }
1535 }
1536
1537 n++;
1538 }
1539
1540 return false;
1541}
1542
1543
1545{
1546 int step_p = aPair->CP().SegmentCount() - 2;
1547 int step_n = aPair->CN().SegmentCount() - 2;
1548
1549 while( 1 )
1550 {
1551 int n_segs_p = aPair->CP().SegmentCount();
1552 int n_segs_n = aPair->CN().SegmentCount();
1553
1554 int max_step_p = n_segs_p - 2;
1555 int max_step_n = n_segs_n - 2;
1556
1557 if( step_p > max_step_p )
1558 step_p = max_step_p;
1559
1560 if( step_n > max_step_n )
1561 step_n = max_step_n;
1562
1563 if( step_p < 1 && step_n < 1 )
1564 break;
1565
1566 bool found_anything_p = false;
1567 bool found_anything_n = false;
1568
1569 if( step_p > 1 )
1570 found_anything_p = mergeDpStep( aPair, true, step_p );
1571
1572 if( step_n > 1 )
1573 found_anything_n = mergeDpStep( aPair, false, step_n );
1574
1575 if( !found_anything_n && !found_anything_p )
1576 {
1577 step_n--;
1578 step_p--;
1579 }
1580 }
1581 return true;
1582}
1583
1584
1586{
1587 return mergeDpSegments( aPair );
1588}
1589
1590
1591static int64_t shovedArea( const SHAPE_LINE_CHAIN& aOld, const SHAPE_LINE_CHAIN& aNew )
1592{
1593 int64_t area = 0;
1594 const int oc = aOld.PointCount();
1595 const int nc = aNew.PointCount();
1596 const int total = oc + nc;
1597
1598 for(int i = 0; i < total; i++)
1599 {
1600 int i_next = (i + 1 == total ? 0 : i + 1);
1601
1602 const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1603 : aNew.CPoint( nc - 1 - (i - oc) );
1604 const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1605 : aNew.CPoint( nc - 1 - (i_next - oc) );
1606 area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1607 }
1608
1609 return std::abs( area / 2 );
1610}
1611
1612
1613bool tightenSegment( bool dir, NODE *aNode, const LINE& cur, const SHAPE_LINE_CHAIN& in,
1614 SHAPE_LINE_CHAIN& out )
1615{
1616 SEG a = in.CSegment(0);
1617 SEG center = in.CSegment(1);
1618 SEG b = in.CSegment(2);
1619
1620 DIRECTION_45 dirA ( a );
1621 DIRECTION_45 dirCenter ( center );
1622 DIRECTION_45 dirB ( b );
1623
1624 if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1625 return false;
1626
1627 SEG guide;
1628 int initial;
1629
1630 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1631 if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1632 return false;
1633
1634 {
1635 /*
1636 auto rC = *a.IntersectLines( b );
1637 dbg->AddSegment ( SEG( center.A, rC ), 1 );
1638 dbg->AddSegment ( SEG( center.B, rC ), 2 );
1639 auto perp = dirCenter.Left().Left();
1640
1641 SEG sperp ( center.A, center.A + perp.ToVector() );
1642
1643 auto vpc = sperp.LineProject( rC );
1644 auto vpa = sperp.LineProject( a.A );
1645 auto vpb = sperp.LineProject( b.B );
1646
1647 auto da = (vpc - vpa).EuclideanNorm();
1648 auto db = (vpc - vpb).EuclideanNorm();
1649
1650 auto vp = (da < db) ? vpa : vpb;
1651 dbg->AddSegment ( SEG( vpc, vp ), 5 );
1652
1653
1654 guide = SEG ( vpc, vp );
1655 */
1656 }
1657
1658 int da = a.Length();
1659 int db = b.Length();
1660
1661 if( da < db )
1662 guide = a;
1663 else
1664 guide = b;
1665
1666 initial = guide.Length();
1667
1668 int step = initial;
1669 int current = step;
1670 SHAPE_LINE_CHAIN snew;
1671
1672 while( step > 1 )
1673 {
1674 LINE l( cur );
1675
1676 snew.Clear();
1677 snew.Append( a.A );
1678 snew.Append( a.B + ( a.A - a.B ).Resize( current ) );
1679 snew.Append( b.A + ( b.B - b.A ).Resize( current ) );
1680 snew.Append( b.B );
1681
1682 step /= 2;
1683
1684 l.SetShape(snew);
1685
1686 if( aNode->CheckColliding(&l) )
1687 current -= step;
1688 else if ( current + step >= initial )
1689 current = initial;
1690 else
1691 current += step;
1692
1693 //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1694 //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1695 //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1696
1697 if ( current == initial )
1698 break;
1699 }
1700
1701 //dbg->AddLine ( snew, 3, 100000 );
1702
1703 out = std::move( snew );
1704 return true;
1705}
1706
1707void Tighten( NODE *aNode, const SHAPE_LINE_CHAIN& aOldLine, const LINE& aNewLine,
1708 LINE& aOptimized )
1709{
1710 LINE tmp;
1711
1712 if( aNewLine.SegmentCount() < 3 )
1713 return;
1714
1715 SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1716
1717 for( int step = 0; step < 3; step++ )
1718 {
1719 current.Simplify2();
1720
1721 for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1722 {
1723 SHAPE_LINE_CHAIN l_in, l_out;
1724
1725 l_in = current.Slice( i, i + 3 );
1726
1727 for( int dir = 0; dir <= 1; dir++ )
1728 {
1729 if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1730 {
1731 SHAPE_LINE_CHAIN opt = current;
1732 opt.Replace( i, i + 3, l_out );
1733 long long int optArea = std::abs( shovedArea( aOldLine, opt ) );
1734 long long int prevArea = std::abs( shovedArea( aOldLine, current ) );
1735
1736 if( optArea < prevArea )
1737 current = std::move( opt );
1738
1739 break;
1740 }
1741 }
1742 }
1743 }
1744
1745 aOptimized = LINE( aNewLine, current );
1746
1747 //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1748 //dbg->AddLine ( current, 4, 100000 );
1749}
1750
1751
1752}
BOX2< VECTOR2I > BOX2I
Definition box2.h:917
constexpr size_type GetWidth() const
Definition box2.h:217
constexpr size_type GetHeight() const
Definition box2.h:218
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.
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition direction45.h:78
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
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
bool IsHorizontal() const
Definition eda_angle.h:141
bool Matches(const T v) const
Definition minoptmax.h:47
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
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
double CoupledLength() const
const DP_DIMENSIONS & Dimensions() const
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
const SHAPE_LINE_CHAIN & CP() const
const DP_GAP_CONSTRAINT GapConstraint() 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:246
const PNS_LAYER_RANGE & Layers() const
Definition pns_item.h:212
virtual NET_HANDLE Net() const
Definition pns_item.h:210
PnsKind Kind() const
Return the type (kind) of the item.
Definition pns_item.h:173
virtual int Layer() const
Definition pns_item.h:216
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:308
bool OfKind(int aKindMask) const
Definition pns_item.h:181
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:307
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
Return the aIdx-th point of the line.
Definition pns_line.h:157
int ArcCount() const
Definition pns_line.h:153
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assign a shape to the line (a polyline/line chain).
Definition pns_line.h:138
const SHAPE_LINE_CHAIN & CLine() const
Definition pns_line.h:149
const VECTOR2I & CLastPoint() const
Definition pns_line.h:158
int CountCorners(int aAngles) const
Return the number of corners of angles specified by mask aAngles.
Definition pns_line.cpp:212
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape.
Definition pns_line.h:148
int SegmentCount() const
Definition pns_line.h:151
int PointCount() const
Definition pns_line.h:152
bool EndsWithVia() const
Definition pns_line.h:204
const SEG CSegment(int aIdx) const
Definition pns_line.h:159
int Width() const
Return line width.
Definition pns_line.h:169
Keep the router "world" - i.e.
Definition pns_node.h:274
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:510
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
std::vector< SEG > m_preservedSegments
std::pair< int, int > m_restrictedVertexRange
std::vector< OPT_CONSTRAINT * > m_constraints
bool mergeColinear(LINE *aLine)
void cacheAdd(ITEM *aItem, bool aIsStatic)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
bool m_restrictAreaIsStrict
bool dragFixCorners(LINE *aLine)
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)
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)
bool dragFixCorner(LINE *aLine, int aVIdx)
ITEM * findPadOrVia(int aLayer, NET_HANDLE aNet, const VECTOR2I &aP) const
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))
A quick shortcut to optimize a line without creating and setting up an optimizer.
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.
@ MERGE_COLINEAR
Merge co-linear segments.
@ PRESERVE_SEGMENTS
do not remove segments from a restricted set
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
@ REQUIRE_OBTUSE_ANGLES
Try to prevent 90-degree or acute corners in a drag.
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
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
ROUTING_SETTINGS & Settings()
Definition pns_router.h:240
static ROUTER * GetInstance()
DIRECTION_45::CORNER_MODE GetCornerMode() const
VECTOR2I Offset() const
Definition pns_solid.h:135
const SHAPE * Shape(int aLayer) const override
Return the geometrical shape of the item.
Definition pns_solid.h:107
Definition seg.h:38
VECTOR2I A
Definition seg.h:45
ecoord SquaredDistance(const SEG &aSeg) const
Definition seg.cpp:35
VECTOR2I::extended_type ecoord
Definition seg.h:40
VECTOR2I B
Definition seg.h:46
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition seg.h:379
int Length() const
Return the length (this).
Definition seg.h:361
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition seg.cpp:771
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition seg.h:283
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition seg.h:217
ecoord SquaredLength() const
Definition seg.h:366
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:651
EDA_ANGLE Angle(const SEG &aOther) const
Determine the smallest angle between two segments.
Definition seg.cpp:66
SHAPE_TYPE Type() const
Return the type of the shape.
Definition shape.h:96
int GetRadius() const
const VECTOR2I GetCenter() const
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int Intersect(const SEG &aSeg, std::vector< INTERSECTION > &aIp) const
Find all intersection points between our line chain and the segment aSeg.
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 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.
double Area(bool aAbsolute=true) const
Return the area of this chain.
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.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
int SegmentCount() const
Return the number of segments in this line chain.
const VECTOR2I & CLastPoint() const
Return the last point in the 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
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.
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
An abstract shape on 2D plane.
Definition shape.h:124
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition shape.h:181
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition vector2d.h:406
static constexpr EDA_ANGLE ANGLE_0
Definition eda_angle.h:472
static constexpr EDA_ANGLE ANGLE_90
Definition eda_angle.h:474
static constexpr EDA_ANGLE ANGLE_45
Definition eda_angle.h:473
static constexpr EDA_ANGLE ANGLE_360
Definition eda_angle.h:478
Push and Shove diff pair dimensions (gap) settings dialog.
int findCoupledVertices(const VECTOR2I &aVertex, const SEG &aOrigSeg, const SHAPE_LINE_CHAIN &aCoupled, DIFF_PAIR *aPair, std::vector< int > *aIndices)
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)
void * NET_HANDLE
Definition pns_item.h:55
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:461
@ SH_RECT
axis-aligned rectangle
Definition shape.h:43
@ SH_CIRCLE
circle
Definition shape.h:46
@ SH_SIMPLE
simple polygon
Definition shape.h:47
@ SH_SEGMENT
line segment
Definition shape.h:44
bool operator()(ITEM *aOtherItem)
CACHE_VISITOR(const ITEM *aOurItem, NODE *aNode, int aMask)
std::string path
VECTOR3I v1(5, 5, 5)
VECTOR2I center
wxString result
Test unit parsing edge cases and error handling.
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:227
Casted dyn_cast(From aObject)
A lightweight dynamic downcast.
Definition typeinfo.h:55
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708
static PIECE rect(double aLeft, double aTop, double aRight, double aBottom, bool aMixed=false)