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