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