KiCad PCB EDA Suite
pns_optimizer.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <[email protected]>
7  *
8  * This program is free software: you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
10  * Free Software Foundation, either version 3 of the License, or (at your
11  * option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
23 #include <geometry/shape_rect.h>
24 #include <geometry/shape_simple.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 
40 namespace PNS {
41 
42 
43 int 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 
70 int COST_ESTIMATOR::CornerCost( const LINE& aLine )
71 {
72  return CornerCost( aLine.CLine() );
73 }
74 
75 
76 void COST_ESTIMATOR::Add( const LINE& aLine )
77 {
78  m_lengthCost += aLine.CLine().Length();
79  m_cornerCost += CornerCost( aLine );
80 }
81 
82 
83 void COST_ESTIMATOR::Remove( const LINE& aLine )
84 {
85  m_lengthCost -= aLine.CLine().Length();
86  m_cornerCost -= CornerCost( aLine );
87 }
88 
89 
90 void 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 
99 bool COST_ESTIMATOR::IsBetter( const COST_ESTIMATOR& aOther, double aLengthTolerance,
100  double aCornerTolerance ) const
101 {
102  if( aOther.m_cornerCost < m_cornerCost && aOther.m_lengthCost < m_lengthCost )
103  return true;
104  else if( aOther.m_cornerCost < m_cornerCost * aCornerTolerance &&
105  aOther.m_lengthCost < m_lengthCost * aLengthTolerance )
106  return true;
107 
108  return false;
109 }
110 
111 
113  m_world( aWorld ),
114  m_collisionKindMask( ITEM::ANY_T ),
115  m_effortLevel( MERGE_SEGMENTS ),
116  m_restrictAreaIsStrict( false )
117 {
118 }
119 
120 
122 {
123 }
124 
125 
127 {
128  CACHE_VISITOR( const ITEM* aOurItem, NODE* aNode, int aMask ) :
129  m_ourItem( aOurItem ),
130  m_collidingItem( nullptr ),
131  m_node( aNode ),
132  m_mask( aMask )
133  {}
134 
135  bool operator()( ITEM* aOtherItem )
136  {
137  if( !( m_mask & aOtherItem->Kind() ) )
138  return true;
139 
140  if( !aOtherItem->Collide( m_ourItem, m_node ) )
141  return true;
142 
143  m_collidingItem = aOtherItem;
144  return false;
145  }
146 
147  const ITEM* m_ourItem;
150  int m_mask;
151 };
152 
153 
154 void OPTIMIZER::cacheAdd( ITEM* aItem, bool aIsStatic = false )
155 {
156  if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
157  return;
158 
159  m_cache.Add( aItem );
160  m_cacheTags[aItem].m_hits = 1;
161  m_cacheTags[aItem].m_isStatic = aIsStatic;
162 }
163 
164 
165 void OPTIMIZER::removeCachedSegments( LINE* aLine, int aStartVertex, int aEndVertex )
166 {
167  if( !aLine->IsLinked() )
168  return;
169 
170  auto links = aLine->Links();
171 
172  if( aEndVertex < 0 )
173  aEndVertex += aLine->PointCount();
174 
175  for( int i = aStartVertex; i < aEndVertex - 1; i++ )
176  {
177  LINKED_ITEM* s = links[i];
178  m_cacheTags.erase( s );
179  m_cache.Remove( s );
180  }
181 }
182 
183 
185 {
186  if( aItem->Kind() == ITEM::LINE_T )
187  removeCachedSegments( static_cast<LINE*>( aItem ) );
188 }
189 
190 
191 void OPTIMIZER::ClearCache( bool aStaticOnly )
192 {
193  if( !aStaticOnly )
194  {
195  m_cacheTags.clear();
196  m_cache.Clear();
197  return;
198  }
199 
200  for( auto i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
201  {
202  if( i->second.m_isStatic )
203  {
204  m_cache.Remove( i->first );
205  m_cacheTags.erase( i->first );
206  }
207  }
208 }
209 
210 
211 bool AREA_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
212  const SHAPE_LINE_CHAIN& aCurrentPath,
213  const SHAPE_LINE_CHAIN& aReplacement )
214 {
215  const VECTOR2I& p1 = aOriginLine->CPoint( aVertex1 );
216  const VECTOR2I& p2 = aOriginLine->CPoint( aVertex2 );
217 
218  bool p1_in = m_allowedArea.Contains( p1 );
219  bool p2_in = m_allowedArea.Contains( p2 );
220 
221  if( m_allowedAreaStrict ) // strict restriction? both points must be inside the restricted area
222  return p1_in && p2_in;
223  else // loose restriction
224  return p1_in || p2_in;
225 }
226 
227 
228 bool PRESERVE_VERTEX_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
229  const SHAPE_LINE_CHAIN& aCurrentPath,
230  const SHAPE_LINE_CHAIN& aReplacement )
231 {
232  bool cv = false;
233 
234  for( int i = aVertex1; i < aVertex2; i++ )
235  {
236  SEG::ecoord dist = aCurrentPath.CSegment(i).SquaredDistance( m_v );
237 
238  if ( dist <= 1 )
239  {
240  cv = true;
241  break;
242  }
243  }
244 
245  if( !cv )
246  return true;
247 
248  for( int i = 0; i < aReplacement.SegmentCount(); i++ )
249  {
250  SEG::ecoord dist = aReplacement.CSegment(i).SquaredDistance( m_v );
251 
252  if ( dist <= 1 )
253  return true;
254  }
255 
256  return false;
257 }
258 
259 
260 bool RESTRICT_VERTEX_RANGE_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
261  const SHAPE_LINE_CHAIN& aCurrentPath,
262  const SHAPE_LINE_CHAIN& aReplacement )
263 {
264  return true;
265 }
266 
267 
268 bool CORNER_COUNT_LIMIT_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
269  const SHAPE_LINE_CHAIN& aCurrentPath,
270  const SHAPE_LINE_CHAIN& aReplacement )
271 {
272  LINE newPath( *aOriginLine, aCurrentPath );
273  newPath.Line().Replace( aVertex1, aVertex2, aReplacement );
274  newPath.Line().Simplify();
275  int cc = newPath.CountCorners( m_angleMask );
276 
277  if( cc >= m_minCorners && cc <= m_maxCorners )
278  return true;
279 
280  return false;
281 }
282 
283 
295 static bool pointInside2( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aP )
296 {
297  if( !aL.IsClosed() || aL.SegmentCount() < 3 )
298  return false;
299 
300  int result = 0;
301  size_t cnt = aL.PointCount();
302 
303  VECTOR2I ip = aL.CPoint( 0 );
304 
305  for( size_t i = 1; i <= cnt; ++i )
306  {
307  VECTOR2I ipNext = ( i == cnt ? aL.CPoint( 0 ) : aL.CPoint( i ) );
308 
309  if( ipNext.y == aP.y )
310  {
311  if( ( ipNext.x == aP.x )
312  || ( ip.y == aP.y && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
313  return true; // pt on polyground boundary
314  }
315 
316  if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
317  {
318  if( ip.x >=aP.x )
319  {
320  if( ipNext.x >aP.x )
321  {
322  result = 1 - result;
323  }
324  else
325  {
326  double d = static_cast<double>( ip.x - aP.x ) *
327  static_cast<double>( ipNext.y - aP.y ) -
328  static_cast<double>( ipNext.x - aP.x ) *
329  static_cast<double>( ip.y - aP.y );
330 
331  if( !d )
332  return true; // pt on polyground boundary
333 
334  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
335  result = 1 - result;
336  }
337  }
338  else
339  {
340  if( ipNext.x >aP.x )
341  {
342  double d = ( (double) ip.x - aP.x ) * ( (double) ipNext.y - aP.y )
343  - ( (double) ipNext.x - aP.x ) * ( (double) ip.y - aP.y );
344 
345  if( !d )
346  return true; // pt on polyground boundary
347 
348  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
349  result = 1 - result;
350  }
351  }
352  }
353 
354  ip = ipNext;
355  }
356 
357  return result > 0;
358 }
359 
360 
361 bool KEEP_TOPOLOGY_CONSTRAINT::Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
362  const SHAPE_LINE_CHAIN& aCurrentPath,
363  const SHAPE_LINE_CHAIN& aReplacement )
364 {
365  SHAPE_LINE_CHAIN encPoly = aOriginLine->CLine().Slice( aVertex1, aVertex2 );
366 
367  // fixme: this is a remarkably shitty implementation...
368  encPoly.Append( aReplacement.Reverse() );
369  encPoly.SetClosed( true );
370 
371  BOX2I bb = encPoly.BBox();
372  std::vector<JOINT*> joints;
373 
374  int cnt = m_world->QueryJoints( bb, joints, aOriginLine->Layers(), ITEM::SOLID_T );
375 
376  if( !cnt )
377  return true;
378 
379  for( JOINT* j : joints )
380  {
381  if( j->Net() == aOriginLine->Net() )
382  continue;
383 
384  if( pointInside2( encPoly, j->Pos() ) )
385  {
386  bool falsePositive = false;
387 
388  for( int k = 0; k < encPoly.PointCount(); k++ )
389  {
390  if( encPoly.CPoint(k) == j->Pos() )
391  {
392  falsePositive = true;
393  break;
394  }
395  }
396 
397  if( !falsePositive )
398  {
399  //dbg->AddPoint(j->Pos(), 5);
400  return false;
401  }
402  }
403  }
404 
405  return true;
406 }
407 
408 
409 bool OPTIMIZER::checkColliding( ITEM* aItem, bool aUpdateCache )
410 {
412 
413  return static_cast<bool>( m_world->CheckColliding( aItem ) );
414 }
415 
416 
418 {
419  for( OPT_CONSTRAINT* c : m_constraints )
420  delete c;
421 
422  m_constraints.clear();
423 }
424 
425 
427 {
428  m_constraints.push_back( aConstraint );
429 }
430 
431 
432 bool OPTIMIZER::checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
433  const SHAPE_LINE_CHAIN& aCurrentPath,
434  const SHAPE_LINE_CHAIN& aReplacement )
435 {
436  for( OPT_CONSTRAINT* c : m_constraints )
437  {
438  if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
439  return false;
440  }
441 
442  return true;
443 }
444 
445 
446 bool OPTIMIZER::checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath )
447 {
448  LINE tmp( *aLine, aOptPath );
449 
450  return checkColliding( &tmp );
451 }
452 
453 
455 {
456  SHAPE_LINE_CHAIN& line = aLine->Line();
457 
458  int step = line.PointCount() - 3;
459  int iter = 0;
460  int segs_pre = line.SegmentCount();
461 
462  if( step < 0 )
463  return false;
464 
465  SHAPE_LINE_CHAIN current_path( line );
466 
467  while( 1 )
468  {
469  iter++;
470  int n_segs = current_path.SegmentCount();
471  int max_step = n_segs - 2;
472 
473  if( step > max_step )
474  step = max_step;
475 
476  if( step < 2 )
477  {
478  line = current_path;
479  return current_path.SegmentCount() < segs_pre;
480  }
481 
482  bool found_anything = false;
483 
484  for( int n = 0; n < n_segs - step; n++ )
485  {
486  const SEG s1 = current_path.CSegment( n );
487  const SEG s2 = current_path.CSegment( n + step );
488  SEG s1opt, s2opt;
489 
490  if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
491  {
492  VECTOR2I ip = *s1.IntersectLines( s2 );
493 
494  s1opt = SEG( s1.A, ip );
495  s2opt = SEG( ip, s2.B );
496 
497  if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
498  {
499  SHAPE_LINE_CHAIN opt_path;
500  opt_path.Append( s1opt.A );
501  opt_path.Append( s1opt.B );
502  opt_path.Append( s2opt.B );
503 
504  LINE opt_track( *aLine, opt_path );
505 
506  if( !checkColliding( &opt_track ) )
507  {
508  current_path.Replace( s1.Index() + 1, s2.Index(), ip );
509 
510  // removeCachedSegments(aLine, s1.Index(), s2.Index());
511  n_segs = current_path.SegmentCount();
512  found_anything = true;
513  break;
514  }
515  }
516  }
517  }
518 
519  if( !found_anything )
520  {
521  if( step <= 2 )
522  {
523  line = current_path;
524  return line.SegmentCount() < segs_pre;
525  }
526 
527  step--;
528  }
529  }
530 
531  return line.SegmentCount() < segs_pre;
532 }
533 
534 
536 {
537  SHAPE_LINE_CHAIN& line = aLine->Line();
538  int step = line.SegmentCount() - 1;
539 
540  int segs_pre = line.SegmentCount();
541 
542  line.Simplify();
543 
544  if( step < 0 )
545  return false;
546 
547  SHAPE_LINE_CHAIN current_path( line );
548 
549  while( 1 )
550  {
551  int n_segs = current_path.SegmentCount();
552  int max_step = n_segs - 2;
553 
554  if( step > max_step )
555  step = max_step;
556 
557  if( step < 1 )
558  break;
559 
560  bool found_anything = mergeStep( aLine, current_path, step );
561 
562  if( !found_anything )
563  step--;
564 
565  if( !step )
566  break;
567  }
568 
569  aLine->SetShape( current_path );
570 
571  return current_path.SegmentCount() < segs_pre;
572 }
573 
574 
576 {
577  SHAPE_LINE_CHAIN& line = aLine->Line();
578 
579  int nSegs = line.SegmentCount();
580 
581  for( int segIdx = 0; segIdx < line.SegmentCount() - 1; ++segIdx )
582  {
583  SEG s1 = line.CSegment( segIdx );
584  SEG s2 = line.CSegment( segIdx + 1 );
585 
586  // Skip zero-length segs caused by abutting arcs
587  if( s1.SquaredLength() == 0 || s2.SquaredLength() == 0 )
588  continue;
589 
590  if( s1.Collinear( s2 ) && !line.IsPtOnArc( segIdx + 1 ) )
591  {
592  line.Remove( segIdx + 1 );
593  }
594  }
595 
596  return line.SegmentCount() < nSegs;
597 }
598 
599 
600 bool OPTIMIZER::Optimize( LINE* aLine, LINE* aResult, LINE* aRoot )
601 {
603 
604  if( aRoot )
605  {
606  PNS_DBG( dbg, AddLine, aRoot->CLine(), BLUE, 100000, "root-line" );
607  }
608 
609 
610  if( !aResult )
611  {
612  aResult = aLine;
613  }
614  else
615  {
616  *aResult = *aLine;
617  aResult->ClearLinks();
618  }
619 
620  bool hasArcs = aLine->ArcCount();
621  bool rv = false;
622 
623  if( (m_effortLevel & LIMIT_CORNER_COUNT) && aRoot )
624  {
625  const int angleMask = DIRECTION_45::ANG_OBTUSE;
626  int rootObtuseCorners = aRoot->CountCorners( angleMask );
627  auto c = new CORNER_COUNT_LIMIT_CONSTRAINT( m_world, rootObtuseCorners,
628  aLine->SegmentCount(), angleMask );
629  AddConstraint( c );
630  }
631 
633  {
635  AddConstraint( c );
636  }
637 
639  {
641  m_restrictedVertexRange.second );
642  AddConstraint( c );
643  }
644 
646  {
648  AddConstraint( c );
649  }
650 
652  {
653  auto c = new KEEP_TOPOLOGY_CONSTRAINT( m_world );
654  AddConstraint( c );
655  }
656 
657  // TODO: Fix for arcs
658  if( !hasArcs && m_effortLevel & MERGE_SEGMENTS )
659  rv |= mergeFull( aResult );
660 
661  // TODO: Fix for arcs
662  if( !hasArcs && m_effortLevel & MERGE_OBTUSE )
663  rv |= mergeObtuse( aResult );
664 
666  rv |= mergeColinear( aResult );
667 
668  // TODO: Fix for arcs
669  if( !hasArcs && m_effortLevel & SMART_PADS )
670  rv |= runSmartPads( aResult );
671 
672  // TODO: Fix for arcs
673  if( !hasArcs && m_effortLevel & FANOUT_CLEANUP )
674  rv |= fanoutCleanup( aResult );
675 
676  return rv;
677 }
678 
679 
680 bool OPTIMIZER::mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentPath, int step )
681 {
682  int n_segs = aCurrentPath.SegmentCount();
683 
684  int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
685 
686  if( aLine->SegmentCount() < 2 )
687  return false;
688 
689  DIRECTION_45 orig_start( aLine->CSegment( 0 ) );
690  DIRECTION_45 orig_end( aLine->CSegment( -1 ) );
691 
692 
693  for( int n = 0; n < n_segs - step; n++ )
694  {
695  // Do not attempt to merge false segments that are part of an arc
696  if( aCurrentPath.IsArcSegment( n )
697  || aCurrentPath.IsArcSegment( static_cast<std::size_t>( n ) + step ) )
698  {
699  continue;
700  }
701 
702  const SEG s1 = aCurrentPath.CSegment( n );
703  const SEG s2 = aCurrentPath.CSegment( n + step );
704 
706  SHAPE_LINE_CHAIN* picked = nullptr;
707  int cost[2];
708 
709  for( int i = 0; i < 2; i++ )
710  {
711  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i );
712  cost[i] = INT_MAX;
713 
714  bool ok = false;
715 
716  if( !checkColliding( aLine, bypass ) )
717  {
718  //printf("Chk-constraints: %d %d\n", n, n+step+1 );
719  ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
720  }
721 
722  if( ok )
723  {
724  path[i] = aCurrentPath;
725  path[i].Replace( s1.Index(), s2.Index(), bypass );
726  path[i].Simplify();
727  cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
728  }
729  }
730 
731  if( cost[0] < cost_orig && cost[0] < cost[1] )
732  picked = &path[0];
733  else if( cost[1] < cost_orig )
734  picked = &path[1];
735 
736  if( picked )
737  {
738  n_segs = aCurrentPath.SegmentCount();
739  aCurrentPath = *picked;
740  return true;
741  }
742  }
743 
744  return false;
745 }
746 
747 
749  bool aPermitDiagonal ) const
750 {
751  BREAKOUT_LIST breakouts;
752 
753  for( int angle = 0; angle < 360; angle += 45 )
754  {
755  const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
757  VECTOR2I p0 = cir->GetCenter();
758  VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
759 
760  l.Append( p0 );
761  l.Append( p0 + v0.Rotate( angle * M_PI / 180.0 ) );
762  breakouts.push_back( l );
763  }
764 
765  return breakouts;
766 }
767 
768 
770  bool aPermitDiagonal ) const
771 {
772  BREAKOUT_LIST breakouts;
773  const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
774 
775  BOX2I bbox = convex->BBox( 0 );
776  VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
777  // must be large enough to guarantee intersecting the convex polygon
778  int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
779 
780  for( int angle = 0; angle < 360; angle += ( aPermitDiagonal ? 45 : 90 ) )
781  {
783  VECTOR2I v0( p0 + VECTOR2I( length, 0 ).Rotate( angle * M_PI / 180.0 ) );
784  SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
785  int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
786 
787  // if n == 1 intersected a segment
788  // if n == 2 intersected the common point of 2 segments
789  // n == 0 can not happen I think, but...
790  if( n > 0 )
791  {
792  l.Append( p0 );
793 
794  // for a breakout distance relative to the distance between
795  // center and polygon edge
796  //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
797 
798  // for an absolute breakout distance, e.g. 0.1 mm
799  //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
800 
801  // for the breakout right on the polygon edge
802  l.Append( intersections[0].p );
803 
804  breakouts.push_back( l );
805  }
806  }
807 
808  return breakouts;
809 }
810 
811 
813  bool aPermitDiagonal ) const
814 {
815  const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
816  VECTOR2I s = rect->GetSize();
817  VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
818  BREAKOUT_LIST breakouts;
819 
820  VECTOR2I d_offset;
821 
822  d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
823  d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
824 
825  VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
826  VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
827 
828  breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
829  breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
830  breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
831  breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
832 
833  if( aPermitDiagonal )
834  {
835  int l = aWidth + std::min( s.x, s.y ) / 2;
836  VECTOR2I d_diag;
837 
838  if( s.x >= s.y )
839  {
840  breakouts.emplace_back(
841  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
842  breakouts.emplace_back(
843  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
844  breakouts.emplace_back(
845  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
846  breakouts.emplace_back(
847  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
848  }
849  else
850  {
851  // fixme: this could be done more efficiently
852  breakouts.emplace_back(
853  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
854  breakouts.emplace_back(
855  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
856  breakouts.emplace_back(
857  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
858  breakouts.emplace_back(
859  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
860  }
861  }
862 
863  return breakouts;
864 }
865 
866 
868  bool aPermitDiagonal ) const
869 {
870  switch( aItem->Kind() )
871  {
872  case ITEM::VIA_T:
873  {
874  const VIA* via = static_cast<const VIA*>( aItem );
875  return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
876  }
877 
878  case ITEM::SOLID_T:
879  {
880  const SHAPE* shape = aItem->Shape();
881 
882  switch( shape->Type() )
883  {
884  case SH_RECT:
885  return rectBreakouts( aWidth, shape, aPermitDiagonal );
886 
887  case SH_SEGMENT:
888  {
889  const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
890  const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
891  return rectBreakouts( aWidth, &rect, aPermitDiagonal );
892  }
893 
894  case SH_CIRCLE:
895  return circleBreakouts( aWidth, shape, aPermitDiagonal );
896 
897  case SH_SIMPLE:
898  return customBreakouts( aWidth, aItem, aPermitDiagonal );
899 
900  default:
901  break;
902  }
903 
904  break;
905  }
906 
907  default:
908  break;
909  }
910 
911  return BREAKOUT_LIST();
912 }
913 
914 
915 ITEM* OPTIMIZER::findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const
916 {
917  JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
918 
919  if( !jt )
920  return nullptr;
921 
922  for( ITEM* item : jt->LinkList() )
923  {
924  if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
925  return item;
926  }
927 
928  return nullptr;
929 }
930 
931 
932 int OPTIMIZER::smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex )
933 {
934  DIRECTION_45 dir;
935 
936  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
938 
939  typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
940  std::vector<RtVariant> variants;
941 
942  SOLID* solid = dyn_cast<SOLID*>( aPad );
943 
944  // don't do optimized connections for offset pads
945  if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
946  return -1;
947 
948  // don't do optimization on vias, they are always round at the moment and the optimizer
949  // will possibly mess up an intended via exit posture
950  if( aPad->Kind() == ITEM::VIA_T )
951  return -1;
952 
953  BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
954  SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
955  int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
956 
957  // Start at 1 to find a potentially better breakout (0 is the pad connection)
958  for( int p = 1; p <= p_end; p++ )
959  {
960  // If the line is contained inside the pad, don't optimize
961  if( solid && solid->Shape() && !solid->Shape()->Collide(
962  SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
963  {
964  continue;
965  }
966 
967  for( SHAPE_LINE_CHAIN & breakout : breakouts )
968  {
969  for( int diag = 0; diag < 2; diag++ )
970  {
972  SHAPE_LINE_CHAIN connect = dir.BuildInitialTrace(
973  breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
974 
975  DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
976 
977  if( !connect.SegmentCount() )
978  continue;
979 
980  int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
981 
982  if( ang1 & ForbiddenAngles )
983  continue;
984 
985  if( breakout.Length() > line.Length() )
986  continue;
987 
988  v = breakout;
989  v.Append( connect );
990 
991  for( int i = p + 1; i < line.PointCount(); i++ )
992  v.Append( line.CPoint( i ) );
993 
994  LINE tmp( *aLine, v );
995  int cc = tmp.CountCorners( ForbiddenAngles );
996 
997  if( cc == 0 )
998  {
999  RtVariant vp;
1000  std::get<0>( vp ) = p;
1001  std::get<1>( vp ) = breakout.Length();
1002  std::get<2>( vp ) = aEnd ? v.Reverse() : v;
1003  std::get<2>( vp ).Simplify();
1004  variants.push_back( vp );
1005  }
1006  }
1007  }
1008  }
1009 
1010  // We attempt to minimize the corner cost (minimizes the segments and types of corners)
1011  // but given two, equally valid costs, we want to pick the longer pad exit. The logic
1012  // here is that if the pad is oblong, the track should not exit the shorter side and parallel
1013  // the pad but should follow the pad's preferential direction before exiting.
1014  // The baseline guess is to start with the existing line the user has drawn.
1015  int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
1016  long long int max_length = 0;
1017  bool found = false;
1018  int p_best = -1;
1019  SHAPE_LINE_CHAIN l_best;
1020 
1021  for( RtVariant& vp : variants )
1022  {
1023  LINE tmp( *aLine, std::get<2>( vp ) );
1024  int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
1025  long long int len = std::get<1>( vp );
1026 
1027  if( !checkColliding( &tmp ) )
1028  {
1029  if( cost < min_cost || ( cost == min_cost && len > max_length ) )
1030  {
1031  l_best = std::get<2>( vp );
1032  p_best = std::get<0>( vp );
1033  found = true;
1034 
1035  if( cost <= min_cost )
1036  max_length = std::max<int>( len, max_length );
1037 
1038  min_cost = std::min( cost, min_cost );
1039  }
1040  }
1041  }
1042 
1043  if( found )
1044  {
1045  aLine->SetShape( l_best );
1046  return p_best;
1047  }
1048 
1049  return -1;
1050 }
1051 
1052 
1054 {
1055  SHAPE_LINE_CHAIN& line = aLine->Line();
1056 
1057  if( line.PointCount() < 3 )
1058  return false;
1059 
1060  VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
1061 
1062  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1063  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1064 
1065  int vtx = -1;
1066 
1067  if( startPad )
1068  vtx = smartPadsSingle( aLine, startPad, false, 3 );
1069 
1070  if( endPad )
1071  smartPadsSingle( aLine, endPad, true,
1072  vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1073 
1074  aLine->Line().Simplify();
1075 
1076  return true;
1077 }
1078 
1079 
1080 bool OPTIMIZER::Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld, const VECTOR2I& aV )
1081 {
1082  OPTIMIZER opt( aWorld );
1083 
1084  opt.SetEffortLevel( aEffortLevel );
1085  opt.SetCollisionMask( -1 );
1086 
1087  if( aEffortLevel & OPTIMIZER::PRESERVE_VERTEX )
1088  opt.SetPreserveVertex( aV );
1089 
1090  return opt.Optimize( aLine );
1091 }
1092 
1093 
1095 {
1096  if( aLine->PointCount() < 3 )
1097  return false;
1098 
1099  VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
1100 
1101  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1102  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1103 
1104  int thr = aLine->Width() * 10;
1105  int len = aLine->CLine().Length();
1106 
1107  if( !startPad )
1108  return false;
1109 
1110  bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1111  bool endMatch = false;
1112 
1113  if(endPad)
1114  {
1115  endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1116  }
1117  else
1118  {
1119  endMatch = aLine->EndsWithVia();
1120  }
1121 
1122  if( startMatch && endMatch && len < thr )
1123  {
1124  for( int i = 0; i < 2; i++ )
1125  {
1126  SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1127  LINE repl;
1128  repl = LINE( *aLine, l2 );
1129 
1130  if( !m_world->CheckColliding( &repl ) )
1131  {
1132  aLine->SetShape( repl.CLine() );
1133  return true;
1134  }
1135  }
1136  }
1137 
1138  return false;
1139 }
1140 
1141 
1142 int findCoupledVertices( const VECTOR2I& aVertex, const SEG& aOrigSeg,
1143  const SHAPE_LINE_CHAIN& aCoupled, DIFF_PAIR* aPair, int* aIndices )
1144 {
1145  int count = 0;
1146 
1147  for ( int i = 0; i < aCoupled.SegmentCount(); i++ )
1148  {
1149  SEG s = aCoupled.CSegment( i );
1150  VECTOR2I projOverCoupled = s.LineProject ( aVertex );
1151 
1152  if( s.ApproxParallel( aOrigSeg ) )
1153  {
1154  int64_t dist =
1155  int64_t{ ( ( projOverCoupled - aVertex ).EuclideanNorm() ) } - aPair->Width();
1156 
1157  if( aPair->GapConstraint().Matches( dist ) )
1158  {
1159  *aIndices++ = i;
1160  count++;
1161  }
1162  }
1163  }
1164 
1165  return count;
1166 }
1167 
1168 
1169 bool verifyDpBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aNewRef,
1170  const SHAPE_LINE_CHAIN& aNewCoupled )
1171 {
1172  LINE refLine ( aRefIsP ? aPair->PLine() : aPair->NLine(), aNewRef );
1173  LINE coupledLine ( aRefIsP ? aPair->NLine() : aPair->PLine(), aNewCoupled );
1174 
1175  if( refLine.Collide( &coupledLine, aNode ) )
1176  return false;
1177 
1178  if( aNode->CheckColliding ( &refLine ) )
1179  return false;
1180 
1181  if( aNode->CheckColliding ( &coupledLine ) )
1182  return false;
1183 
1184  return true;
1185 }
1186 
1187 
1188 bool coupledBypass( NODE* aNode, DIFF_PAIR* aPair, bool aRefIsP, const SHAPE_LINE_CHAIN& aRef,
1189  const SHAPE_LINE_CHAIN& aRefBypass, const SHAPE_LINE_CHAIN& aCoupled,
1190  SHAPE_LINE_CHAIN& aNewCoupled )
1191 {
1192  int vStartIdx[1024]; // fixme: possible overflow
1193  int nStarts = findCoupledVertices( aRefBypass.CPoint( 0 ),
1194  aRefBypass.CSegment( 0 ),
1195  aCoupled, aPair, vStartIdx );
1196  DIRECTION_45 dir( aRefBypass.CSegment( 0 ) );
1197 
1198  int64_t bestLength = -1;
1199  bool found = false;
1200  SHAPE_LINE_CHAIN bestBypass;
1201  int si, ei;
1202 
1203  for( int i=0; i< nStarts; i++ )
1204  {
1205  for( int j = 1; j < aCoupled.PointCount() - 1; j++ )
1206  {
1207  int delta = std::abs ( vStartIdx[i] - j );
1208 
1209  if( delta > 1 )
1210  {
1211  const VECTOR2I& vs = aCoupled.CPoint( vStartIdx[i] );
1212  SHAPE_LINE_CHAIN bypass = dir.BuildInitialTrace( vs, aCoupled.CPoint(j),
1213  dir.IsDiagonal() );
1214 
1215  int64_t coupledLength = aPair->CoupledLength( aRef, bypass );
1216 
1217  SHAPE_LINE_CHAIN newCoupled = aCoupled;
1218 
1219  si = vStartIdx[i];
1220  ei = j;
1221 
1222  if(si < ei)
1223  newCoupled.Replace( si, ei, bypass );
1224  else
1225  newCoupled.Replace( ei, si, bypass.Reverse() );
1226 
1227  if( coupledLength > bestLength && verifyDpBypass( aNode, aPair, aRefIsP, aRef,
1228  newCoupled) )
1229  {
1230  bestBypass = newCoupled;
1231  bestLength = coupledLength;
1232  found = true;
1233  }
1234  }
1235  }
1236  }
1237 
1238  if( found )
1239  aNewCoupled = bestBypass;
1240 
1241  return found;
1242 }
1243 
1244 
1245 bool checkDpColliding( NODE* aNode, DIFF_PAIR* aPair, bool aIsP, const SHAPE_LINE_CHAIN& aPath )
1246 {
1247  LINE tmp ( aIsP ? aPair->PLine() : aPair->NLine(), aPath );
1248 
1249  return static_cast<bool>( aNode->CheckColliding( &tmp ) );
1250 }
1251 
1252 
1253 bool OPTIMIZER::mergeDpStep( DIFF_PAIR* aPair, bool aTryP, int step )
1254 {
1255  int n = 1;
1256 
1257  SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1258  SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1259 
1260  int n_segs = currentPath.SegmentCount() - 1;
1261 
1262  int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1263  int64_t budget = clenPre / 10; // fixme: come up with something more intelligent here...
1264 
1265  while( n < n_segs - step )
1266  {
1267  const SEG s1 = currentPath.CSegment( n );
1268  const SEG s2 = currentPath.CSegment( n + step );
1269 
1270  DIRECTION_45 dir1( s1 );
1271  DIRECTION_45 dir2( s2 );
1272 
1273  if( dir1.IsObtuse( dir2 ) )
1274  {
1275  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B,
1276  dir1.IsDiagonal() );
1277  SHAPE_LINE_CHAIN newRef;
1278  SHAPE_LINE_CHAIN newCoup;
1279  int64_t deltaCoupled = -1, deltaUni = -1;
1280 
1281  newRef = currentPath;
1282  newRef.Replace( s1.Index(), s2.Index(), bypass );
1283 
1284  deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1285 
1286  if( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1287  {
1288  deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1289 
1290  if( deltaCoupled >= 0 )
1291  {
1292  newRef.Simplify();
1293  newCoup.Simplify();
1294 
1295  aPair->SetShape( newRef, newCoup, !aTryP );
1296  return true;
1297  }
1298  }
1299  else if( deltaUni >= 0 && verifyDpBypass( m_world, aPair, aTryP, newRef, coupledPath ) )
1300  {
1301  newRef.Simplify();
1302  coupledPath.Simplify();
1303 
1304  aPair->SetShape( newRef, coupledPath, !aTryP );
1305  return true;
1306  }
1307  }
1308 
1309  n++;
1310  }
1311 
1312  return false;
1313 }
1314 
1315 
1317 {
1318  int step_p = aPair->CP().SegmentCount() - 2;
1319  int step_n = aPair->CN().SegmentCount() - 2;
1320 
1321  while( 1 )
1322  {
1323  int n_segs_p = aPair->CP().SegmentCount();
1324  int n_segs_n = aPair->CN().SegmentCount();
1325 
1326  int max_step_p = n_segs_p - 2;
1327  int max_step_n = n_segs_n - 2;
1328 
1329  if( step_p > max_step_p )
1330  step_p = max_step_p;
1331 
1332  if( step_n > max_step_n )
1333  step_n = max_step_n;
1334 
1335  if( step_p < 1 && step_n < 1 )
1336  break;
1337 
1338  bool found_anything_p = false;
1339  bool found_anything_n = false;
1340 
1341  if( step_p > 1 )
1342  found_anything_p = mergeDpStep( aPair, true, step_p );
1343 
1344  if( step_n > 1 )
1345  found_anything_n = mergeDpStep( aPair, false, step_n );
1346 
1347  if( !found_anything_n && !found_anything_p )
1348  {
1349  step_n--;
1350  step_p--;
1351  }
1352  }
1353  return true;
1354 }
1355 
1356 
1358 {
1359  return mergeDpSegments( aPair );
1360 }
1361 
1362 
1363 static int64_t shovedArea( const SHAPE_LINE_CHAIN& aOld, const SHAPE_LINE_CHAIN& aNew )
1364 {
1365  int64_t area = 0;
1366  const int oc = aOld.PointCount();
1367  const int nc = aNew.PointCount();
1368  const int total = oc + nc;
1369 
1370  for(int i = 0; i < total; i++)
1371  {
1372  int i_next = (i + 1 == total ? 0 : i + 1);
1373 
1374  const VECTOR2I &v0 = i < oc ? aOld.CPoint(i)
1375  : aNew.CPoint( nc - 1 - (i - oc) );
1376  const VECTOR2I &v1 = i_next < oc ? aOld.CPoint ( i_next )
1377  : aNew.CPoint( nc - 1 - (i_next - oc) );
1378  area += -(int64_t) v0.y * v1.x + (int64_t) v0.x * v1.y;
1379  }
1380 
1381  return std::abs( area / 2 );
1382 }
1383 
1384 
1385 bool tightenSegment( bool dir, NODE *aNode, const LINE& cur, const SHAPE_LINE_CHAIN& in,
1386  SHAPE_LINE_CHAIN& out )
1387 {
1388  SEG a = in.CSegment(0);
1389  SEG center = in.CSegment(1);
1390  SEG b = in.CSegment(2);
1391 
1392  DIRECTION_45 dirA ( a );
1393  DIRECTION_45 dirCenter ( center );
1394  DIRECTION_45 dirB ( b );
1395 
1396  if (!dirA.IsObtuse( dirCenter) || !dirCenter.IsObtuse(dirB))
1397  return false;
1398 
1399  //VECTOR2I perp = (center.B - center.A).Perpendicular();
1400  VECTOR2I guideA, guideB ;
1401 
1402  SEG guide;
1403  int initial;
1404 
1405  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1406  if ( dirA.Angle ( dirB ) != DIRECTION_45::ANG_RIGHT )
1407  return false;
1408 
1409  {
1410  /*
1411  auto rC = *a.IntersectLines( b );
1412  dbg->AddSegment ( SEG( center.A, rC ), 1 );
1413  dbg->AddSegment ( SEG( center.B, rC ), 2 );
1414  auto perp = dirCenter.Left().Left();
1415 
1416  SEG sperp ( center.A, center.A + perp.ToVector() );
1417 
1418  auto vpc = sperp.LineProject( rC );
1419  auto vpa = sperp.LineProject( a.A );
1420  auto vpb = sperp.LineProject( b.B );
1421 
1422  auto da = (vpc - vpa).EuclideanNorm();
1423  auto db = (vpc - vpb).EuclideanNorm();
1424 
1425  auto vp = (da < db) ? vpa : vpb;
1426  dbg->AddSegment ( SEG( vpc, vp ), 5 );
1427 
1428 
1429  guide = SEG ( vpc, vp );
1430  */
1431  }
1432 
1433  int da = a.Length();
1434  int db = b.Length();
1435 
1436  if( da < db )
1437  guide = a;
1438  else
1439  guide = b;
1440 
1441  initial = guide.Length();
1442 
1443  int step = initial;
1444  int current = step;
1445  SHAPE_LINE_CHAIN snew;
1446 
1447  while( step > 1 )
1448  {
1449  LINE l( cur );
1450 
1451  snew.Clear();
1452  snew.Append( a.A );
1453  snew.Append( a.B + ( a.A - a.B ).Resize( current ) );
1454  snew.Append( b.A + ( b.B - b.A ).Resize( current ) );
1455  snew.Append( b.B );
1456 
1457  step /= 2;
1458 
1459  l.SetShape(snew);
1460 
1461  if( aNode->CheckColliding(&l) )
1462  current -= step;
1463  else if ( current + step >= initial )
1464  current = initial;
1465  else
1466  current += step;
1467 
1468  //dbg->AddSegment ( SEG( center.A , a.LineProject( center.A + gr ) ), 3 );
1469  //dbg->AddSegment ( SEG( center.A , center.A + guideA ), 3 );
1470  //dbg->AddSegment ( SEG( center.B , center.B + guideB ), 4 );
1471 
1472  if ( current == initial )
1473  break;
1474 
1475 
1476  }
1477 
1478  out = snew;
1479 
1480  //dbg->AddLine ( snew, 3, 100000 );
1481 
1482  return true;
1483 }
1484 
1485 
1486 void Tighten( NODE *aNode, const SHAPE_LINE_CHAIN& aOldLine, const LINE& aNewLine,
1487  LINE& aOptimized )
1488 {
1489  LINE tmp;
1490 
1491  if( aNewLine.SegmentCount() < 3 )
1492  return;
1493 
1494  SHAPE_LINE_CHAIN current ( aNewLine.CLine() );
1495 
1496  for( int step = 0; step < 3; step++ )
1497  {
1498  current.Simplify();
1499 
1500  for( int i = 0; i <= current.SegmentCount() - 3; i++ )
1501  {
1502  SHAPE_LINE_CHAIN l_in, l_out;
1503 
1504  l_in = current.Slice( i, i + 3 );
1505 
1506  for( int dir = 0; dir <= 1; dir++ )
1507  {
1508  if( tightenSegment( dir ? true : false, aNode, aNewLine, l_in, l_out ) )
1509  {
1510  SHAPE_LINE_CHAIN opt = current;
1511  opt.Replace( i, i + 3, l_out );
1512  auto optArea = std::abs( shovedArea( aOldLine, opt ) );
1513  auto prevArea = std::abs( shovedArea( aOldLine, current ) );
1514 
1515  if( optArea < prevArea )
1516  current = opt;
1517 
1518  break;
1519  }
1520  }
1521  }
1522  }
1523 
1524  aOptimized = LINE( aNewLine, current );
1525 
1526  //auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
1527  //dbg->AddLine ( current, 4, 100000 );
1528 }
1529 
1530 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
int Length() const
Return the length (this).
Definition: seg.h:350
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
static bool pointInside2(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aP)
Determine if a point is located within a given polygon.
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
Base class for PNS router board items.
Definition: pns_item.h:55
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:368
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_solid.h:79
long long int Length() const
Return length of the line chain in Euclidean metric.
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
Definition: shape_simple.h:41
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
std::vector< INTERSECTION > INTERSECTIONS
virtual int Layer() const
Definition: pns_item.h:158
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
VECTOR2I Offset() const
Definition: pns_solid.h:117
Keep the router "world" - i.e.
Definition: pns_node.h:148
void CacheRemove(ITEM *aItem)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
int GetRadius() const
Definition: shape_circle.h:107
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
ecoord SquaredLength() const
Definition: seg.h:355
int SegmentCount() const
Definition: pns_line.h:139
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:146
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.
~OPTIMIZER()
A quick shortcut to optimize a line without creating and setting up an optimizer.
Simplify pad-pad and pad-via connections if possible.
int Width() const
const SHAPE_LINE_CHAIN & CN() const
VECTOR2I::extended_type ecoord
Definition: seg.h:43
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
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.
void Add(const LINE &aLine)
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:72
double CoupledLength() const
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:209
const VECTOR2I GetCenter() const
Definition: shape_circle.h:112
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
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
bool runSmartPads(LINE *aLine)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
bool mergeFull(LINE *aLine)
int PointCount() const
Return the number of points (vertices) in this line chain.
const RANGED_NUM< int > GapConstraint() const
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
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:165
int PointCount() const
Definition: pns_line.h:140
bool EndsWithVia() const
Definition: pns_line.h:191
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
bool m_restrictAreaIsStrict
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.h:290
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
void SetCollisionMask(int aMask)
const VECTOR2I GetSize() const
Definition: shape_rect.h:124
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:181
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void AddConstraint(OPT_CONSTRAINT *aConstraint)
int ArcCount() const
Definition: pns_line.h:141
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
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:42
static int64_t shovedArea(const SHAPE_LINE_CHAIN &aOld, const SHAPE_LINE_CHAIN &aNew)
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
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:301
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
bool IsArcSegment(size_t aSegment) const
bool IsClosed() const override
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:200
int Net() const
Definition: pns_item.h:152
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:116
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
bool Contains(const Vec &aPoint) const
Definition: box2.h:134
bool mergeDpSegments(DIFF_PAIR *aPair)
#define PNS_DBG(dbg, method,...)
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 SetPreserveVertex(const VECTOR2I &aV)
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:131
int QueryJoints(const BOX2I &aBox, std::vector< JOINT * > &aJoints, LAYER_RANGE aLayerMask=LAYER_RANGE::All(), int aKindMask=ITEM::ANY_T)
Definition: pns_node.cpp:1554
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
Definition: direction45.h:213
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
Definition: shape_simple.h:124
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
bool mergeObtuse(LINE *aLine)
An abstract shape on 2D plane.
Definition: shape.h:116
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:233
void Remove(const LINE &aLine)
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
int SegmentCount() const
Return the number of segments in this line chain.
bool IsPtOnArc(size_t aPtIndex) const
int findCoupledVertices(const VECTOR2I &aVertex, const SEG &aOrigSeg, const SHAPE_LINE_CHAIN &aCoupled, DIFF_PAIR *aPair, int *aIndices)
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
circle
Definition: shape.h:46
std::vector< OPT_CONSTRAINT * > m_constraints
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1154
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
bool tightenSegment(bool dir, NODE *aNode, const LINE &cur, const SHAPE_LINE_CHAIN &in, SHAPE_LINE_CHAIN &out)
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:268
Definition: seg.h:40
OPTIMIZER(NODE *aWorld)
VECTOR2I m_preservedVertex
Basic class for a differential pair.
void cacheAdd(ITEM *aItem, bool aIsStatic)
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
bool operator()(ITEM *aOtherItem)
const SHAPE_LINE_CHAIN & CP() const
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
Definition: color4d.h:56
VECTOR2< T > Rotate(double aAngle) const
Rotate the vector by a given angle.
Definition: vector2d.h:371
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
CACHE_VISITOR(const ITEM *aOurItem, NODE *aNode, int aMask)
static int CornerCost(const SHAPE_LINE_CHAIN &aLine)
Reduce corner cost by merging obtuse segments.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsBetter(const COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
bool fanoutCleanup(LINE *aLine)
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:340
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:463
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool mergeColinear(LINE *aLine)
VECTOR2I A
Definition: seg.h:48
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:138
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
static int CornerCost(const SEG &aA, const SEG &aB)
void Replace(const LINE &aOldLine, const LINE &aNewLine)
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:130
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:94
void Clear()
Remove all points from the line chain.
bool Matches(const T &aOther) const
Definition: ranged_num.h:43
constexpr int delta
Merge co-linear segments.
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
SHAPE_INDEX_LIST< ITEM * > m_cache
void SetEffortLevel(int aEffort)
axis-aligned rectangle
Definition: shape.h:43
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
Calculate the cost of a given line, taking corner angles and total length into account.
Definition: pns_optimizer.h:48
Push and Shove diff pair dimensions (gap) settings dialog.
bool checkDpColliding(NODE *aNode, DIFF_PAIR *aPair, bool aIsP, const SHAPE_LINE_CHAIN &aPath)
simple polygon
Definition: shape.h:47
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:94
std::pair< int, int > m_restrictedVertexRange
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:208
void ClearCache(bool aStaticOnly=false)
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
const LAYER_RANGE & Layers() const
Definition: pns_item.h:154
bool IsObtuse(const DIRECTION_45 &aOther) const
Definition: direction45.h:203
void Tighten(NODE *aNode, const SHAPE_LINE_CHAIN &aOldLine, const LINE &aNewLine, LINE &aOptimized)
Reroute pad exits.
line segment
Definition: shape.h:44
int CountCorners(int aAngles) const
Definition: pns_line.cpp:135
VECTOR2I B
Definition: seg.h:49