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