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