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