KiCad PCB EDA Suite
pns_diff_pair.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2015 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 
22 #include <cstdio>
23 #include <cstdlib>
24 #include <cmath>
25 #include <limits>
26 
27 #include <geometry/direction45.h>
28 #include <geometry/shape.h>
29 #include <geometry/shape_rect.h>
30 #include <geometry/shape_circle.h>
31 #include <geometry/shape_segment.h>
32 
33 
34 #include "pns_diff_pair.h"
35 #include "pns_router.h"
36 #include "pns_solid.h"
37 #include "pns_utils.h"
38 #include "pns_debug_decorator.h"
39 
40 namespace PNS {
41 
42 class LINE;
43 
45 {
46  m_primP = aPrimP->Clone();
47  m_primN = aPrimN->Clone();
48 
49  m_anchorP = m_primP->Anchor( 0 );
50  m_anchorN = m_primN->Anchor( 0 );
51 }
52 
53 
54 void DP_PRIMITIVE_PAIR::SetAnchors( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN )
55 {
56  m_anchorP = aAnchorP;
57  m_anchorN = aAnchorN;
58 }
59 
60 
61 DP_PRIMITIVE_PAIR::DP_PRIMITIVE_PAIR( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN )
62 {
63  m_anchorP = aAnchorP;
64  m_anchorN = aAnchorN;
65  m_primP = m_primN = NULL;
66 }
67 
68 
70 {
71  m_primP = m_primN = NULL;
72 
73  if( aOther.m_primP )
74  m_primP = aOther.m_primP->Clone();
75 
76  if( aOther.m_primN )
77  m_primN = aOther.m_primN->Clone();
78 
79  m_anchorP = aOther.m_anchorP;
80  m_anchorN = aOther.m_anchorN;
81 }
82 
83 
85 {
86  if( aOther.m_primP )
87  m_primP = aOther.m_primP->Clone();
88  if( aOther.m_primN )
89  m_primN = aOther.m_primN->Clone();
90 
91  m_anchorP = aOther.m_anchorP;
92  m_anchorN = aOther.m_anchorN;
93 
94  return *this;
95 }
96 
97 
99 {
100  delete m_primP;
101  delete m_primN;
102 }
103 
104 
106 {
107  if( !m_primP )
108  return false;
109 
110  return m_primP->OfKind( ITEM::SEGMENT_T );
111 }
112 
113 
115 {
116  if( !aItem->OfKind ( ITEM::SEGMENT_T ) )
117  return DIRECTION_45();
118 
119  SEGMENT* s = static_cast<SEGMENT*>( aItem );
120 
121  if( s->Seg().A == aP )
122  return DIRECTION_45( s->Seg().A - s->Seg().B );
123  else
124  return DIRECTION_45( s->Seg().B - s->Seg().A );
125 }
126 
127 void DP_PRIMITIVE_PAIR::CursorOrientation( const VECTOR2I& aCursorPos, VECTOR2I& aMidpoint, VECTOR2I& aDirection ) const
128 {
129  assert( m_primP && m_primN );
130 
131  VECTOR2I aP, aN, dir, midpoint;
132 
134  {
135  aP = m_primP->Anchor( 1 );
136  aN = m_primN->Anchor( 1 );
137  midpoint = ( aP + aN ) / 2;
138  SEG s = static_cast <SEGMENT*>( m_primP )->Seg();
139 
140  if ( s.B != s.A )
141  {
142  dir = s.B - s.A;
143  }
144  else
145  {
146  dir = VECTOR2I( 0, 1 );
147  }
148 
149  dir = dir.Resize( ( aP - aN ).EuclideanNorm() );
150 
151  }
152  else
153  {
154  aP = m_primP->Anchor( 0 );
155  aN = m_primN->Anchor( 0 );
156  midpoint = ( aP + aN ) / 2;
157  dir = ( aP - aN ).Perpendicular();
158 
159  if ( dir.Dot( aCursorPos - midpoint ) < 0 )
160  dir = -dir;
161  }
162 
163  aMidpoint = midpoint;
164  aDirection = dir;
165 }
166 
167 
169 {
170  return anchorDirection( m_primP, m_anchorP );
171 }
172 
173 
175 {
176  return anchorDirection( m_primN, m_anchorN );
177 }
178 
179 
180 static DIRECTION_45::AngleType angle( const VECTOR2I &a, const VECTOR2I &b )
181 {
182  DIRECTION_45 dir_a( a );
183  DIRECTION_45 dir_b( b );
184 
185  return dir_a.Angle( dir_b );
186 }
187 
188 
189 static bool checkGap( const SHAPE_LINE_CHAIN &p, const SHAPE_LINE_CHAIN &n, int gap )
190 {
191  int i, j;
192 
193  for( i = 0; i < p.SegmentCount(); i++ )
194  {
195  for( j = 0; j < n.SegmentCount() ; j++ )
196  {
197  int dist = p.CSegment( i ).Distance( n.CSegment( j ) );
198 
199  if( dist < gap - 100 )
200  return false;
201  }
202  }
203 
204  return true;
205 }
206 
207 
209 {
212 }
213 
214 
215 bool DIFF_PAIR::BuildInitial( const DP_GATEWAY& aEntry, const DP_GATEWAY &aTarget, bool aPrefDiagonal )
216 {
217  SHAPE_LINE_CHAIN p = DIRECTION_45().BuildInitialTrace ( aEntry.AnchorP(), aTarget.AnchorP(), aPrefDiagonal );
218  SHAPE_LINE_CHAIN n = DIRECTION_45().BuildInitialTrace ( aEntry.AnchorN(), aTarget.AnchorN(), aPrefDiagonal );
219 
221 
222  SHAPE_LINE_CHAIN sum_n, sum_p;
223  m_p = p;
224  m_n = n;
225 
226  if( aEntry.HasEntryLines() )
227  {
228  if( !aEntry.Entry().CheckConnectionAngle( *this, mask ) )
229  return false;
230 
231  sum_p = aEntry.Entry().CP();
232  sum_n = aEntry.Entry().CN();
233  sum_p.Append( p );
234  sum_n.Append( n );
235  }
236  else
237  {
238  sum_p = p;
239  sum_n = n;
240  }
241 
243 
244  m_p = sum_p;
245  m_n = sum_n;
246 
247  if( aTarget.HasEntryLines() )
248  {
249  DP_GATEWAY t(aTarget) ;
250  t.Reverse();
251 
252  if( !CheckConnectionAngle( t.Entry(), mask ) )
253  return false;
254 
255  sum_p.Append( t.Entry().CP() );
256  sum_n.Append( t.Entry().CN() );
257  }
258 
259  m_p = sum_p;
260  m_n = sum_n;
261 
262  if( !checkGap ( p, n, m_gapConstraint ) )
263  return false;
264 
265  if( p.SelfIntersecting() || n.SelfIntersecting() )
266  return false;
267 
268  if( p.Intersects( n ) )
269  return false;
270 
271  return true;
272 }
273 
274 
275 bool DIFF_PAIR::CheckConnectionAngle( const DIFF_PAIR& aOther, int aAllowedAngles ) const
276 {
277  bool checkP, checkN;
278 
279  if( m_p.SegmentCount() == 0 || aOther.m_p.SegmentCount() == 0 )
280  checkP = true;
281  else
282  {
283  DIRECTION_45 p0( m_p.CSegment( -1 ) );
284  DIRECTION_45 p1( aOther.m_p.CSegment( 0 ) );
285 
286  checkP = ( p0.Angle( p1 ) & aAllowedAngles ) != 0;
287  }
288 
289  if( m_n.SegmentCount() == 0 || aOther.m_n.SegmentCount() == 0 )
290  checkN = true;
291  else
292  {
293  DIRECTION_45 n0( m_n.CSegment( -1 ) );
294  DIRECTION_45 n1( aOther.m_n.CSegment( 0 ) );
295 
296  checkN = ( n0.Angle( n1 ) & aAllowedAngles ) != 0;
297  }
298 
299  return checkP && checkN;
300 }
301 
302 
304 {
305  return DIFF_PAIR( m_entryP, m_entryN, 0 );
306 }
307 
308 
310  const VECTOR2I& aCursorPos, int aOrthoScore )
311 {
312  for( DP_GATEWAY g : aEntries.Gateways() )
313  {
314  VECTOR2I midpoint( ( g.AnchorP() + g.AnchorN() ) / 2 );
315  SEG guide_s( midpoint, midpoint + VECTOR2I( 1, 0 ) );
316  SEG guide_d( midpoint, midpoint + VECTOR2I( 1, 1 ) );
317 
318  VECTOR2I proj_s = guide_s.LineProject( aCursorPos );
319  VECTOR2I proj_d = guide_d.LineProject( aCursorPos );
320 
321  int dist_s = ( proj_s - aCursorPos ).EuclideanNorm();
322  int dist_d = ( proj_d - aCursorPos ).EuclideanNorm();
323 
324 
325  VECTOR2I proj = ( dist_s < dist_d ? proj_s : proj_d );
326 
327  DP_GATEWAYS targets( m_gap );
328 
329  targets.m_viaGap = m_viaGap;
330  targets.m_viaDiameter = m_viaDiameter;
331  targets.m_fitVias = m_fitVias;
332 
333  targets.BuildForCursor( proj );
334 
335  for( DP_GATEWAY t : targets.Gateways() )
336  {
337  t.SetPriority( aOrthoScore );
338  m_gateways.push_back( t );
339  }
340  }
341 }
342 
343 
345  bool aPrefDiagonal, DIFF_PAIR& aDp )
346 {
347  DP_CANDIDATE best;
348 
349  int n = 0;
350  int bestScore = -1000;
351  bool found = false;
352 
353  for( const DP_GATEWAY& g_entry : aEntry.Gateways() )
354  {
355  for( const DP_GATEWAY& g_target : aTarget.Gateways() )
356  {
357  n++;
358 
359  for( int attempt = 0; attempt < 2; attempt++ )
360  {
361  int score = ( attempt == 1 ? -3 : 0 );
362  score += g_entry.Priority();
363  score += g_target.Priority();
364 
365  if( score < bestScore )
366  continue;
367 
368  DIFF_PAIR l( m_gap );
369 
370  if( l.BuildInitial( g_entry, g_target, aPrefDiagonal ^ ( attempt ? true : false ) ) )
371  {
372  best.p = l.CP();
373  best.n = l.CN();
374  bestScore = score;
375  found = true;
376  }
377  }
378  }
379  }
380 
381 
382  if( found )
383  {
384  aDp.SetGap( m_gap );
385  aDp.SetShape( best.p, best.n );
386  return true;
387  }
388 
389  return false;
390 }
391 
392 
393 bool DP_GATEWAYS::checkDiagonalAlignment( const VECTOR2I& a, const VECTOR2I& b ) const
394 {
395  VECTOR2I dir ( std::abs (a.x - b.x), std::abs ( a.y - b.y ));
396 
397  return (dir.x == 0 && dir.y != 0) || (dir.x == dir.y) || (dir.y == 0 && dir.x != 0);
398 }
399 
400 
401 void DP_GATEWAYS::FilterByOrientation ( int aAngleMask, DIRECTION_45 aRefOrientation )
402 {
403  std::remove_if( m_gateways.begin(), m_gateways.end(), [aAngleMask, aRefOrientation]( const DP_GATEWAY& dp) {
404  DIRECTION_45 orient( dp.AnchorP() - dp.AnchorN() );
405  return !( orient.Angle( aRefOrientation ) & aAngleMask );
406  } );
407 }
408 
409 static VECTOR2I makeGapVector( VECTOR2I dir, int length )
410 {
411  int l = length / 2;
412  VECTOR2I rv;
413 
414  if( dir.EuclideanNorm() == 0 )
415  return dir;
416 
417  do
418  {
419  rv = dir.Resize( l );
420  l++;
421  } while( ( rv * 2 ).EuclideanNorm() < length );
422 
423  return rv;
424 }
425 
426 void DP_GATEWAYS::BuildFromPrimitivePair( DP_PRIMITIVE_PAIR aPair, bool aPreferDiagonal )
427 {
428  VECTOR2I majorDirection;
429  VECTOR2I p0_p, p0_n;
430  int orthoFanDistance;
431  int diagFanDistance;
432  const SHAPE* shP = NULL;
433 
434  if( aPair.PrimP() == NULL )
435  {
436  BuildGeneric( aPair.AnchorP(), aPair.AnchorN(), true );
437  return;
438  }
439 
440  const int pvMask = ITEM::SOLID_T | ITEM::VIA_T;
441 
442  if( aPair.PrimP()->OfKind( pvMask ) && aPair.PrimN()->OfKind( pvMask ) )
443  {
444  p0_p = aPair.AnchorP();
445  p0_n = aPair.AnchorN();
446 
447  shP = aPair.PrimP()->Shape();
448  }
449  else if( aPair.PrimP()->OfKind( ITEM::SEGMENT_T ) && aPair.PrimN()->OfKind( ITEM::SEGMENT_T ) )
450  {
451  buildDpContinuation( aPair, aPreferDiagonal );
452 
453  return;
454  }
455 
456  majorDirection = ( p0_p - p0_n ).Perpendicular();
457 
458  if( shP == NULL )
459  return;
460 
461  switch( shP->Type() )
462  {
463  case SH_RECT:
464  {
465  int w = static_cast<const SHAPE_RECT*>( shP )->GetWidth();
466  int h = static_cast<const SHAPE_RECT*>( shP )->GetHeight();
467 
468  if( w < h )
469  std::swap( w, h );
470 
471  orthoFanDistance = ( w + 1 )* 3 / 2;
472  diagFanDistance = ( w - h );
473  break;
474  }
475 
476  case SH_SEGMENT:
477  {
478  int w = static_cast<const SHAPE_SEGMENT*>( shP )->GetWidth();
479  SEG s = static_cast<const SHAPE_SEGMENT*>( shP )->GetSeg();
480 
481  orthoFanDistance = w + ( s.B - s.A ).EuclideanNorm();
482  diagFanDistance = ( s.B - s.A ).EuclideanNorm();
483  break;
484  }
485 
486  default:
487  BuildGeneric ( p0_p, p0_n, true );
488  return;
489  }
490 
491  if( checkDiagonalAlignment( p0_p, p0_n ) )
492  {
493  int padDist = ( p0_p - p0_n ).EuclideanNorm();
494 
495  for( int k = 0; k < 2; k++ )
496  {
497  VECTOR2I dir, dp, dv;
498 
499  if( k == 0 )
500  {
501  dir = makeGapVector( majorDirection, orthoFanDistance );
502  int d = ( padDist - m_gap );
503  dp = makeGapVector( dir, d );
504  dv = makeGapVector( p0_n - p0_p, d );
505  }
506  else
507  {
508  dir = makeGapVector( majorDirection, diagFanDistance );
509  int d = ( padDist - m_gap );
510  dp = makeGapVector( dir, d );
511  dv = makeGapVector( p0_n - p0_p, d );
512  }
513 
514  for( int i = 0; i < 2; i++ )
515  {
516  int sign = i ? -1 : 1;
517 
518  VECTOR2I gw_p( p0_p + sign * ( dir + dp ) + dv );
519  VECTOR2I gw_n( p0_n + sign * ( dir + dp ) - dv );
520 
521  SHAPE_LINE_CHAIN entryP( p0_p, p0_p + sign * dir, gw_p );
522  SHAPE_LINE_CHAIN entryN( p0_n, p0_n + sign * dir, gw_n );
523 
524  DP_GATEWAY gw( gw_p, gw_n, false );
525 
526  gw.SetEntryLines( entryP, entryN );
527  gw.SetPriority( 100 - k );
528  m_gateways.push_back( gw );
529  }
530  }
531  }
532 
533  BuildGeneric( p0_p, p0_n, true );
534 }
535 
536 
537 void DP_GATEWAYS::BuildForCursor( const VECTOR2I& aCursorPos )
538 {
539  int gap = m_fitVias ? m_viaGap + m_viaDiameter : m_gap;
540 
541  for( int attempt = 0; attempt < 2; attempt++ )
542  {
543  for( int i = 0; i < 4; i++ )
544  {
545  VECTOR2I dir;
546 
547  if( !attempt )
548  {
549  dir = makeGapVector( VECTOR2I( gap, gap ), gap );
550 
551  if( i % 2 == 0 )
552  dir.x = -dir.x;
553 
554  if( i / 2 == 0 )
555  dir.y = -dir.y;
556  }
557  else
558  {
559  if( i /2 == 0 )
560  dir = VECTOR2I( (gap + 1) / 2 * ( ( i % 2 ) ? -1 : 1 ), 0 );
561  else
562  dir = VECTOR2I( 0, (gap + 1) / 2 * ( ( i % 2 ) ? -1 : 1) );
563  }
564 
565  if( m_fitVias )
566  BuildGeneric( aCursorPos + dir, aCursorPos - dir, true, true );
567  else
568  m_gateways.push_back( DP_GATEWAY( aCursorPos + dir,
569  aCursorPos - dir, attempt ? true : false ) );
570 
571  }
572  }
573 }
574 
575 
576 void DP_GATEWAYS::buildEntries( const VECTOR2I& p0_p, const VECTOR2I& p0_n )
577 {
578  for( DP_GATEWAY &g : m_gateways )
579  {
580  if( !g.HasEntryLines() )
581  {
582  SHAPE_LINE_CHAIN lead_p = DIRECTION_45().BuildInitialTrace ( g.AnchorP(), p0_p, g.IsDiagonal() ).Reverse();
583  SHAPE_LINE_CHAIN lead_n = DIRECTION_45().BuildInitialTrace ( g.AnchorN(), p0_n, g.IsDiagonal() ).Reverse();
584  g.SetEntryLines( lead_p, lead_n );
585  }
586  }
587 }
588 
589 
591 {
592  DP_GATEWAY gw( aPair.AnchorP(), aPair.AnchorN(), aIsDiagonal );
593  gw.SetPriority( 100 );
594  m_gateways.push_back( gw );
595 
596  if( !aPair.Directional() )
597  return;
598 
599  DIRECTION_45 dP = aPair.DirP();
600  DIRECTION_45 dN = aPair.DirN();
601 
602  int gap = ( aPair.AnchorP() - aPair.AnchorN() ).EuclideanNorm();
603 
604  VECTOR2I vdP = aPair.AnchorP() + dP.Left().ToVector();
605  VECTOR2I vdN = aPair.AnchorN() + dN.Left().ToVector();
606 
607  SEGMENT* sP = static_cast<SEGMENT*>( aPair.PrimP() );
608 
609  VECTOR2I t1, t2;
610 
611  auto vL = makeGapVector( dP.Left().ToVector(), ( gap + 1 ) / 2 );
612  auto vR = makeGapVector( dP.Right().ToVector(), ( gap + 1 ) / 2 );
613 
614  if( sP->Seg().Side( vdP ) == sP->Seg().Side( vdN ) )
615  {
616  t1 = aPair.AnchorP() + vL;
617  t2 = aPair.AnchorN() + vR;
618  }
619  else
620  {
621  t1 = aPair.AnchorP() + vR;
622  t2 = aPair.AnchorN() + vL;
623  }
624 
625  DP_GATEWAY gwL( t2, aPair.AnchorN(), !aIsDiagonal );
626  SHAPE_LINE_CHAIN ep = dP.BuildInitialTrace( aPair.AnchorP(), t2, !aIsDiagonal );
627  gwL.SetPriority( 10 );
628  gwL.SetEntryLines( ep , SHAPE_LINE_CHAIN() );
629 
630  m_gateways.push_back( gwL );
631 
632  DP_GATEWAY gwR( aPair.AnchorP(), t1, !aIsDiagonal );
633  SHAPE_LINE_CHAIN en = dP.BuildInitialTrace( aPair.AnchorN(), t1, !aIsDiagonal );
634  gwR.SetPriority( 10) ;
635  gwR.SetEntryLines( SHAPE_LINE_CHAIN(), en );
636 
637  m_gateways.push_back( gwR );
638 }
639 
640 
641 void DP_GATEWAYS::BuildGeneric( const VECTOR2I& p0_p, const VECTOR2I& p0_n, bool aBuildEntries, bool aViaMode )
642 {
643  SEG st_p[2], st_n[2];
644  SEG d_n[2], d_p[2];
645 
646  const int padToGapThreshold = 3;
647  int padDist = ( p0_p - p0_p ).EuclideanNorm();
648 
649  st_p[0] = SEG(p0_p + VECTOR2I( -100, 0 ), p0_p + VECTOR2I( 100, 0 ) );
650  st_n[0] = SEG(p0_n + VECTOR2I( -100, 0 ), p0_n + VECTOR2I( 100, 0 ) );
651  st_p[1] = SEG(p0_p + VECTOR2I( 0, -100 ), p0_p + VECTOR2I( 0, 100 ) );
652  st_n[1] = SEG(p0_n + VECTOR2I( 0, -100 ), p0_n + VECTOR2I( 0, 100 ) );
653  d_p[0] = SEG( p0_p + VECTOR2I( -100, -100 ), p0_p + VECTOR2I( 100, 100 ) );
654  d_p[1] = SEG( p0_p + VECTOR2I( 100, -100 ), p0_p + VECTOR2I( -100, 100 ) );
655  d_n[0] = SEG( p0_n + VECTOR2I( -100, -100 ), p0_n + VECTOR2I( 100, 100 ) );
656  d_n[1] = SEG( p0_n + VECTOR2I( 100, -100 ), p0_n + VECTOR2I( -100, 100 ) );
657 
658  // midpoint exit & side-by exits
659  for( int i = 0; i < 2; i++ )
660  {
661  bool straightColl = st_p[i].Collinear( st_n[i] );
662  bool diagColl = d_p[i].Collinear( d_n[i] );
663 
664  if( straightColl || diagColl )
665  {
666  VECTOR2I dir = makeGapVector( p0_n - p0_p, m_gap / 2 );
667  VECTOR2I m = ( p0_p + p0_n ) / 2;
668  int prio = ( padDist > padToGapThreshold * m_gap ? 2 : 1);
669 
670  if( !aViaMode )
671  {
672  m_gateways.push_back( DP_GATEWAY( m - dir, m + dir, diagColl, DIRECTION_45::ANG_RIGHT, prio ) );
673 
674  dir = makeGapVector( p0_n - p0_p, 2 * m_gap );
675  m_gateways.push_back( DP_GATEWAY( p0_p - dir, p0_p - dir + dir.Perpendicular(), diagColl ) );
676  m_gateways.push_back( DP_GATEWAY( p0_p - dir, p0_p - dir - dir.Perpendicular(), diagColl ) );
677  m_gateways.push_back( DP_GATEWAY( p0_n + dir + dir.Perpendicular(), p0_n + dir, diagColl ) );
678  m_gateways.push_back( DP_GATEWAY( p0_n + dir - dir.Perpendicular(), p0_n + dir, diagColl ) );
679  }
680  }
681  }
682 
683  for( int i = 0; i < 2; i++ )
684  {
685  for( int j = 0; j < 2; j++ )
686  {
687  OPT_VECTOR2I ips[2];
688 
689  ips[0] = d_n[i].IntersectLines( d_p[j] );
690  ips[1] = st_p[i].IntersectLines( st_n[j] );
691 
692  if( d_n[i].Collinear( d_p[j] ) )
693  ips[0] = OPT_VECTOR2I();
694  if( st_p[i].Collinear( st_p[j] ) )
695  ips[1] = OPT_VECTOR2I();
696 
697  // diagonal-diagonal and straight-straight cases - the most typical case if the pads
698  // are on the same straight/diagonal line
699  for( int k = 0; k < 2; k++ )
700  {
701  if( ips[k] )
702  {
703  const VECTOR2I m( *ips[k] );
704 
705  if( m != p0_p && m != p0_n )
706  {
707  int prio = ( padDist > padToGapThreshold * m_gap ? 10 : 20 );
708  VECTOR2I g_p( ( p0_p - m ).Resize( ceil( (double) m_gap * M_SQRT1_2 ) ) );
709  VECTOR2I g_n( ( p0_n - m ).Resize( ceil( (double) m_gap * M_SQRT1_2 ) ) );
710 
711  m_gateways.push_back( DP_GATEWAY( m + g_p, m + g_n, k == 0 ? true : false, DIRECTION_45::ANG_OBTUSE, prio ) );
712  }
713  }
714  }
715 
716  ips[0] = st_n[i].IntersectLines( d_p[j] );
717  ips[1] = st_p[i].IntersectLines( d_n[j] );
718 
719 // diagonal-straight cases: 8 possibilities of "weirder" exists
720  for( int k = 0; k < 2; k++ )
721  {
722  if( ips[k] )
723  {
724  const VECTOR2I m( *ips[k] );
725 
726  if( !aViaMode && m != p0_p && m != p0_n )
727  {
728  VECTOR2I g_p, g_n;
729 
730  g_p = ( p0_p - m ).Resize( ceil( (double) m_gap * M_SQRT2 ) );
731  g_n = ( p0_n - m ).Resize( ceil( (double) m_gap ) );
732 
733  if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE )
734  m_gateways.push_back( DP_GATEWAY( m + g_p, m + g_n, true ) );
735 
736  g_p = ( p0_p - m ).Resize( m_gap );
737  g_n = ( p0_n - m ).Resize( ceil( (double) m_gap * M_SQRT2 ) );
738 
739  if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE )
740  m_gateways.push_back( DP_GATEWAY( m + g_p, m + g_n, true ) );
741  }
742  }
743  }
744  }
745  }
746 
747  if( aBuildEntries )
748  buildEntries( p0_p, p0_n );
749 }
750 
751 
753 {
754  if( m_hasVias )
755  return DP_PRIMITIVE_PAIR( &m_via_p, &m_via_n );
756  else
757  {
758  const LINE lP( PLine() );
759  const LINE lN( NLine() );
760 
761  SEGMENT sP( lP, lP.CSegment( -1 ) );
762  SEGMENT sN( lN, lN.CSegment( -1 ) );
763 
764  DP_PRIMITIVE_PAIR dpair( &sP, &sN );
765  dpair.SetAnchors( sP.Seg().B, sN.Seg().B );
766 
767  return dpair;
768  }
769 }
770 
771 
772 bool commonParallelProjection( SEG n, SEG p, SEG &pClip, SEG& nClip )
773 {
774  SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
775 
776  int64_t t_a = 0;
777  int64_t t_b = p.TCoef( p.B );
778 
779  int64_t tproj_a = p.TCoef( n_proj_p.A );
780  int64_t tproj_b = p.TCoef( n_proj_p.B );
781 
782  if( t_b < t_a )
783  std::swap( t_b, t_a );
784 
785  if( tproj_b < tproj_a )
786  std::swap( tproj_b, tproj_a );
787 
788  if( t_b <= tproj_a )
789  return false;
790 
791  if( t_a >= tproj_b )
792  return false;
793 
794  int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
795  std::vector<int64_t> tv( t, t + 4 );
796  std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
797 
798  int64_t pLenSq = p.SquaredLength();
799 
800  VECTOR2I dp = p.B - p.A;
801  pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
802  pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
803 
804  pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
805  pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
806 
807  nClip.A = n.LineProject( pClip.A );
808  nClip.B = n.LineProject( pClip.B );
809 
810  return true;
811 }
812 
813 
814 double DIFF_PAIR::Skew() const
815 {
816  return m_p.Length() - m_n.Length();
817 }
818 
819 
821 {
822  SHAPE_LINE_CHAIN p( m_p );
823  SHAPE_LINE_CHAIN n( m_n );
824 
825  p.Simplify();
826  n.Simplify();
827 
828  for( int i = 0; i < p.SegmentCount(); i++ )
829  {
830  for( int j = 0; j < n.SegmentCount(); j++ )
831  {
832  SEG sp = p.CSegment( i );
833  SEG sn = n.CSegment( j );
834 
835  SEG p_clip, n_clip;
836 
837  int64_t dist = std::abs( sp.Distance( sn ) - m_width );
838 
839  if( sp.ApproxParallel( sn ) && m_gapConstraint.Matches( dist ) && commonParallelProjection( sp, sn, p_clip, n_clip ) )
840  {
841  const COUPLED_SEGMENTS spair( p_clip, sp, i, n_clip, sn, j );
842  aPairs.push_back( spair );
843  }
844  }
845  }
846 }
847 
848 
849 int64_t DIFF_PAIR::CoupledLength( const SHAPE_LINE_CHAIN& aP, const SHAPE_LINE_CHAIN& aN ) const
850 {
851  int64_t total = 0;
852 
853  for( int i = 0; i < aP.SegmentCount(); i++ )
854  {
855  for( int j = 0; j < aN.SegmentCount(); j++ )
856  {
857  SEG sp = aP.CSegment( i );
858  SEG sn = aN.CSegment( j );
859 
860  SEG p_clip, n_clip;
861 
862  int64_t dist = std::abs( sp.Distance(sn) - m_width );
863 
864  if( sp.ApproxParallel( sn ) && m_gapConstraint.Matches( dist ) &&
865  commonParallelProjection( sp, sn, p_clip, n_clip ) )
866  total += p_clip.Length();
867  }
868  }
869 
870  return total;
871 }
872 
873 
875 {
876  COUPLED_SEGMENTS_VEC pairs;
877 
878  CoupledSegmentPairs( pairs );
879 
880  double l = 0.0;
881  for( unsigned int i = 0; i < pairs.size(); i++ )
882  l += pairs[i].coupledP.Length();
883 
884  return l;
885 }
886 
887 
889 {
890  double t = TotalLength();
891 
892  if( t == 0.0 )
893  return 0.0;
894 
895  return CoupledLength() / t;
896 }
897 
898 
900 {
901  double lenP = m_p.Length();
902  double lenN = m_n.Length();
903 
904  return (lenN + lenP ) / 2.0;
905 }
906 
907 
908 int DIFF_PAIR::CoupledLength ( const SEG& aP, const SEG& aN ) const
909 {
910  SEG p_clip, n_clip;
911  int64_t dist = std::abs( aP.Distance( aN ) - m_width );
912 
913  if( aP.ApproxParallel( aN ) && m_gapConstraint.Matches( dist ) &&
914  commonParallelProjection ( aP, aN, p_clip, n_clip ) )
915  return p_clip.Length();
916 
917  return 0;
918 }
919 
920 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:112
void CursorOrientation(const VECTOR2I &aCursorPos, VECTOR2I &aMidpoint, VECTOR2I &aDirection) const
const VECTOR2I ToVector() const
Function ToVector()
Definition: direction45.h:295
double CoupledLength() const
Class ITEM.
Definition: pns_item.h:53
static bool checkGap(const SHAPE_LINE_CHAIN &p, const SHAPE_LINE_CHAIN &n, int gap)
void buildEntries(const VECTOR2I &p0_p, const VECTOR2I &p0_n)
virtual ITEM * Clone() const =0
Function Clone()
DP_PRIMITIVE_PAIR & operator=(const DP_PRIMITIVE_PAIR &aOther)
bool FitGateways(DP_GATEWAYS &aEntry, DP_GATEWAYS &aTarget, bool aPrefDiagonal, DIFF_PAIR &aDp)
ecoord SquaredLength() const
Definition: seg.h:297
void BuildForCursor(const VECTOR2I &aCursorPos)
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:487
bool checkDiagonalAlignment(const VECTOR2I &a, const VECTOR2I &b) const
const DIFF_PAIR Entry() const
const VECTOR2I & AnchorN() const
Definition: pns_diff_pair.h:79
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
void SetPriority(int aPriority)
Definition: pns_diff_pair.h:99
const VECTOR2I & AnchorN() const
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:387
void BuildFromPrimitivePair(DP_PRIMITIVE_PAIR aPair, bool aPreferDiagonal)
int AllowedAngles() const
Function AllowedAngles()
Definition: pns_diff_pair.h:87
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:132
int Length() const
Function Length()
Definition: seg.h:292
double TotalLength() const
RANGED_NUM< int > m_gapConstraint
std::vector< DP_GATEWAY > m_gateways
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:331
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:179
SHAPE_LINE_CHAIN m_entryN
void FilterByOrientation(int aAngleMask, DIRECTION_45 aRefOrientation)
std::vector< DP_GATEWAY > & Gateways()
static const int dist[10][10]
Definition: dist.cpp:57
const SHAPE_LINE_CHAIN & CN() const
virtual const SHAPE * Shape() const
Function Shape()
Definition: pns_item.h:296
DIRECTION_45 DirN() const
const DIRECTION_45 Left() const
Function Left()
Definition: direction45.h:275
ITEM * PrimP() const
bool BuildInitial(const DP_GATEWAY &aEntry, const DP_GATEWAY &aTarget, bool aPrefDiagonal)
void SetEntryLines(const SHAPE_LINE_CHAIN &aEntryP, const SHAPE_LINE_CHAIN &aEntryN)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:589
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
#define abs(a)
Definition: auxiliary.h:84
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:130
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:358
const SEG CSegment(int aIndex) const
Function CSegment()
ITEM * PrimN() const
void SetGap(int aGap)
std::vector< COUPLED_SEGMENTS > COUPLED_SEGMENTS_VEC
DIRECTION_45 anchorDirection(ITEM *aItem, const VECTOR2I &aP) const
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:294
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:34
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
const VECTOR2I & AnchorP() const
Definition: pns_diff_pair.h:77
SHAPE_LINE_CHAIN m_p
bool CheckConnectionAngle(const DIFF_PAIR &aOther, int allowedAngles) const
const VECTOR2I & AnchorP() const
Class DIRECTION_45.
Definition: direction45.h:33
double Skew() const
SHAPE_LINE_CHAIN m_entryP
Class SHAPE.
Definition: shape.h:57
bool HasEntryLines() const
SHAPE_LINE_CHAIN m_n
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
void buildDpContinuation(DP_PRIMITIVE_PAIR aPair, bool aIsDiagonal)
Definition: seg.h:36
Class DIFF_PAIR.
const SEG CSegment(int aIdx) const
Returns the aIdx-th segment of the line
Definition: pns_line.h:147
static VECTOR2I makeGapVector(VECTOR2I dir, int length)
AngleType
Enum AngleType Represents kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:59
void BuildOrthoProjections(DP_GATEWAYS &aEntries, const VECTOR2I &aCursorPos, int aOrthoScore)
void CoupledSegmentPairs(COUPLED_SEGMENTS_VEC &aPairs) const
Class DP_PRIMITIVE_PAIR.
DIRECTION_45 DirP() const
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:82
Class SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
VECTOR2I A
Definition: seg.h:46
AngleType Angle(const DIRECTION_45 &aOther) const
Function Angle() Returns the type of angle between directions (this) and aOther.
Definition: direction45.h:146
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:326
VECTOR2< T > Perpendicular() const
Function Perpendicular computes the perpendicular vector.
Definition: vector2d.h:315
const DIRECTION_45 Right() const
Function Right()
Definition: direction45.h:259
bool Matches(const T &aOther) const
Definition: ranged_num.h:43
double CoupledLengthFactor() const
const SEG & Seg() const
Definition: pns_segment.h:93
Definition: shape.h:43
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false) const
Function BuildInitialTrace()
Definition: direction45.h:199
void BuildGeneric(const VECTOR2I &p0_p, const VECTOR2I &p0_n, bool aBuildEntries=false, bool aViaMode=false)
bool Collinear(const SEG &aSeg) const
Function Collinear()
Definition: seg.h:231
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:253
Class DP_GATEWAYS.
Push and Shove diff pair dimensions (gap) settings dialog.
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
int SegmentCount() const
Function SegmentCount()
bool commonParallelProjection(SEG n, SEG p, SEG &pClip, SEG &nClip)
Class DP_GATEWAY.
Definition: pns_diff_pair.h:47
DP_PRIMITIVE_PAIR EndingPrimitives()
void SetAnchors(const VECTOR2I &aAnchorP, const VECTOR2I &aAnchorN)
int Length() const
Function Length()
const SHAPE_LINE_CHAIN & CP() const
axis-aligned rectangle
Definition: shape.h:44
int sign(T val)
Definition: math_util.h:44
VECTOR2I B
Definition: seg.h:47