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  do
414  {
415  rv = dir.Resize( l );
416  l++;
417  } while( ( rv * 2 ).EuclideanNorm() < length );
418 
419  return rv;
420 }
421 
422 void DP_GATEWAYS::BuildFromPrimitivePair( DP_PRIMITIVE_PAIR aPair, bool aPreferDiagonal )
423 {
424  VECTOR2I majorDirection;
425  VECTOR2I p0_p, p0_n;
426  int orthoFanDistance;
427  int diagFanDistance;
428  const SHAPE* shP = NULL;
429 
430  if( aPair.PrimP() == NULL )
431  {
432  BuildGeneric( aPair.AnchorP(), aPair.AnchorN(), true );
433  return;
434  }
435 
436  const int pvMask = ITEM::SOLID_T | ITEM::VIA_T;
437 
438  if( aPair.PrimP()->OfKind( pvMask ) && aPair.PrimN()->OfKind( pvMask ) )
439  {
440  p0_p = aPair.AnchorP();
441  p0_n = aPair.AnchorN();
442 
443  shP = aPair.PrimP()->Shape();
444  }
445  else if( aPair.PrimP()->OfKind( ITEM::SEGMENT_T ) && aPair.PrimN()->OfKind( ITEM::SEGMENT_T ) )
446  {
447  buildDpContinuation( aPair, aPreferDiagonal );
448 
449  return;
450  }
451 
452  majorDirection = ( p0_p - p0_n ).Perpendicular();
453 
454  if( shP == NULL )
455  return;
456 
457  switch( shP->Type() )
458  {
459  case SH_RECT:
460  {
461  int w = static_cast<const SHAPE_RECT*>( shP )->GetWidth();
462  int h = static_cast<const SHAPE_RECT*>( shP )->GetHeight();
463 
464  if( w < h )
465  std::swap( w, h );
466 
467  orthoFanDistance = ( w + 1 )* 3 / 2;
468  diagFanDistance = ( w - h );
469  break;
470  }
471 
472  case SH_SEGMENT:
473  {
474  int w = static_cast<const SHAPE_SEGMENT*>( shP )->GetWidth();
475  SEG s = static_cast<const SHAPE_SEGMENT*>( shP )->GetSeg();
476 
477  orthoFanDistance = w + ( s.B - s.A ).EuclideanNorm();
478  diagFanDistance = ( s.B - s.A ).EuclideanNorm();
479  break;
480  }
481 
482  default:
483  BuildGeneric ( p0_p, p0_n, true );
484  return;
485  }
486 
487  if( checkDiagonalAlignment( p0_p, p0_n ) )
488  {
489  int padDist = ( p0_p - p0_n ).EuclideanNorm();
490 
491  for( int k = 0; k < 2; k++ )
492  {
493  VECTOR2I dir, dp, dv;
494 
495  if( k == 0 )
496  {
497  dir = makeGapVector( majorDirection, orthoFanDistance );
498  int d = ( padDist - m_gap );
499  dp = makeGapVector( dir, d );
500  dv = makeGapVector( p0_n - p0_p, d );
501  }
502  else
503  {
504  dir = makeGapVector( majorDirection, diagFanDistance );
505  int d = ( padDist - m_gap );
506  dp = makeGapVector( dir, d );
507  dv = makeGapVector( p0_n - p0_p, d );
508  }
509 
510  for( int i = 0; i < 2; i++ )
511  {
512  int sign = i ? -1 : 1;
513 
514  VECTOR2I gw_p( p0_p + sign * ( dir + dp ) + dv );
515  VECTOR2I gw_n( p0_n + sign * ( dir + dp ) - dv );
516 
517  SHAPE_LINE_CHAIN entryP( p0_p, p0_p + sign * dir, gw_p );
518  SHAPE_LINE_CHAIN entryN( p0_n, p0_n + sign * dir, gw_n );
519 
520  DP_GATEWAY gw( gw_p, gw_n, false );
521 
522  gw.SetEntryLines( entryP, entryN );
523  gw.SetPriority( 100 - k );
524  m_gateways.push_back( gw );
525  }
526  }
527  }
528 
529  BuildGeneric( p0_p, p0_n, true );
530 }
531 
532 
533 void DP_GATEWAYS::BuildForCursor( const VECTOR2I& aCursorPos )
534 {
535  int gap = m_fitVias ? m_viaGap + m_viaDiameter : m_gap;
536 
537  for( int attempt = 0; attempt < 2; attempt++ )
538  {
539  for( int i = 0; i < 4; i++ )
540  {
541  VECTOR2I dir;
542 
543  if( !attempt )
544  {
545  dir = makeGapVector( VECTOR2I( gap, gap ), gap );
546 
547  if( i % 2 == 0 )
548  dir.x = -dir.x;
549 
550  if( i / 2 == 0 )
551  dir.y = -dir.y;
552  }
553  else
554  {
555  if( i /2 == 0 )
556  dir = VECTOR2I( (gap + 1) / 2 * ( ( i % 2 ) ? -1 : 1 ), 0 );
557  else
558  dir = VECTOR2I( 0, (gap + 1) / 2 * ( ( i % 2 ) ? -1 : 1) );
559  }
560 
561  if( m_fitVias )
562  BuildGeneric( aCursorPos + dir, aCursorPos - dir, true, true );
563  else
564  m_gateways.push_back( DP_GATEWAY( aCursorPos + dir,
565  aCursorPos - dir, attempt ? true : false ) );
566 
567  }
568  }
569 }
570 
571 
572 void DP_GATEWAYS::buildEntries( const VECTOR2I& p0_p, const VECTOR2I& p0_n )
573 {
574  for( DP_GATEWAY &g : m_gateways )
575  {
576  if( !g.HasEntryLines() )
577  {
578  SHAPE_LINE_CHAIN lead_p = DIRECTION_45().BuildInitialTrace ( g.AnchorP(), p0_p, g.IsDiagonal() ).Reverse();
579  SHAPE_LINE_CHAIN lead_n = DIRECTION_45().BuildInitialTrace ( g.AnchorN(), p0_n, g.IsDiagonal() ).Reverse();
580  g.SetEntryLines( lead_p, lead_n );
581  }
582  }
583 }
584 
585 
587 {
588  DP_GATEWAY gw( aPair.AnchorP(), aPair.AnchorN(), aIsDiagonal );
589  gw.SetPriority( 100 );
590  m_gateways.push_back( gw );
591 
592  if( !aPair.Directional() )
593  return;
594 
595  DIRECTION_45 dP = aPair.DirP();
596  DIRECTION_45 dN = aPair.DirN();
597 
598  int gap = ( aPair.AnchorP() - aPair.AnchorN() ).EuclideanNorm();
599 
600  VECTOR2I vdP = aPair.AnchorP() + dP.Left().ToVector();
601  VECTOR2I vdN = aPair.AnchorN() + dN.Left().ToVector();
602 
603  SEGMENT* sP = static_cast<SEGMENT*>( aPair.PrimP() );
604 
605  VECTOR2I t1, t2;
606 
607  auto vL = makeGapVector( dP.Left().ToVector(), ( gap + 1 ) / 2 );
608  auto vR = makeGapVector( dP.Right().ToVector(), ( gap + 1 ) / 2 );
609 
610  if( sP->Seg().Side( vdP ) == sP->Seg().Side( vdN ) )
611  {
612  t1 = aPair.AnchorP() + vL;
613  t2 = aPair.AnchorN() + vR;
614  }
615  else
616  {
617  t1 = aPair.AnchorP() + vR;
618  t2 = aPair.AnchorN() + vL;
619  }
620 
621  DP_GATEWAY gwL( t2, aPair.AnchorN(), !aIsDiagonal );
622  SHAPE_LINE_CHAIN ep = dP.BuildInitialTrace( aPair.AnchorP(), t2, !aIsDiagonal );
623  gwL.SetPriority( 10 );
624  gwL.SetEntryLines( ep , SHAPE_LINE_CHAIN() );
625 
626  m_gateways.push_back( gwL );
627 
628  DP_GATEWAY gwR( aPair.AnchorP(), t1, !aIsDiagonal );
629  SHAPE_LINE_CHAIN en = dP.BuildInitialTrace( aPair.AnchorN(), t1, !aIsDiagonal );
630  gwR.SetPriority( 10) ;
631  gwR.SetEntryLines( SHAPE_LINE_CHAIN(), en );
632 
633  m_gateways.push_back( gwR );
634 }
635 
636 
637 void DP_GATEWAYS::BuildGeneric( const VECTOR2I& p0_p, const VECTOR2I& p0_n, bool aBuildEntries, bool aViaMode )
638 {
639  SEG st_p[2], st_n[2];
640  SEG d_n[2], d_p[2];
641 
642  const int padToGapThreshold = 3;
643  int padDist = ( p0_p - p0_p ).EuclideanNorm();
644 
645  st_p[0] = SEG(p0_p + VECTOR2I( -100, 0 ), p0_p + VECTOR2I( 100, 0 ) );
646  st_n[0] = SEG(p0_n + VECTOR2I( -100, 0 ), p0_n + VECTOR2I( 100, 0 ) );
647  st_p[1] = SEG(p0_p + VECTOR2I( 0, -100 ), p0_p + VECTOR2I( 0, 100 ) );
648  st_n[1] = SEG(p0_n + VECTOR2I( 0, -100 ), p0_n + VECTOR2I( 0, 100 ) );
649  d_p[0] = SEG( p0_p + VECTOR2I( -100, -100 ), p0_p + VECTOR2I( 100, 100 ) );
650  d_p[1] = SEG( p0_p + VECTOR2I( 100, -100 ), p0_p + VECTOR2I( -100, 100 ) );
651  d_n[0] = SEG( p0_n + VECTOR2I( -100, -100 ), p0_n + VECTOR2I( 100, 100 ) );
652  d_n[1] = SEG( p0_n + VECTOR2I( 100, -100 ), p0_n + VECTOR2I( -100, 100 ) );
653 
654  // midpoint exit & side-by exits
655  for( int i = 0; i < 2; i++ )
656  {
657  bool straightColl = st_p[i].Collinear( st_n[i] );
658  bool diagColl = d_p[i].Collinear( d_n[i] );
659 
660  if( straightColl || diagColl )
661  {
662  VECTOR2I dir = makeGapVector( p0_n - p0_p, m_gap / 2 );
663  VECTOR2I m = ( p0_p + p0_n ) / 2;
664  int prio = ( padDist > padToGapThreshold * m_gap ? 2 : 1);
665 
666  if( !aViaMode )
667  {
668  m_gateways.push_back( DP_GATEWAY( m - dir, m + dir, diagColl, DIRECTION_45::ANG_RIGHT, prio ) );
669 
670  dir = makeGapVector( p0_n - p0_p, 2 * m_gap );
671  m_gateways.push_back( DP_GATEWAY( p0_p - dir, p0_p - dir + dir.Perpendicular(), diagColl ) );
672  m_gateways.push_back( DP_GATEWAY( p0_p - dir, p0_p - dir - dir.Perpendicular(), diagColl ) );
673  m_gateways.push_back( DP_GATEWAY( p0_n + dir + dir.Perpendicular(), p0_n + dir, diagColl ) );
674  m_gateways.push_back( DP_GATEWAY( p0_n + dir - dir.Perpendicular(), p0_n + dir, diagColl ) );
675  }
676  }
677  }
678 
679  for( int i = 0; i < 2; i++ )
680  {
681  for( int j = 0; j < 2; j++ )
682  {
683  OPT_VECTOR2I ips[2];
684 
685  ips[0] = d_n[i].IntersectLines( d_p[j] );
686  ips[1] = st_p[i].IntersectLines( st_n[j] );
687 
688  if( d_n[i].Collinear( d_p[j] ) )
689  ips[0] = boost::none;
690  if( st_p[i].Collinear( st_p[j] ) )
691  ips[1] = boost::none;
692 
693  // diagonal-diagonal and straight-straight cases - the most typical case if the pads
694  // are on the same straight/diagonal line
695  for( int k = 0; k < 2; k++ )
696  {
697  if( ips[k] )
698  {
699  const VECTOR2I m( *ips[k] );
700 
701  if( m != p0_p && m != p0_n )
702  {
703  int prio = ( padDist > padToGapThreshold * m_gap ? 10 : 20 );
704  VECTOR2I g_p( ( p0_p - m ).Resize( ceil( (double) m_gap * M_SQRT1_2 ) ) );
705  VECTOR2I g_n( ( p0_n - m ).Resize( ceil( (double) m_gap * M_SQRT1_2 ) ) );
706 
707  m_gateways.push_back( DP_GATEWAY( m + g_p, m + g_n, k == 0 ? true : false, DIRECTION_45::ANG_OBTUSE, prio ) );
708  }
709  }
710  }
711 
712  ips[0] = st_n[i].IntersectLines( d_p[j] );
713  ips[1] = st_p[i].IntersectLines( d_n[j] );
714 
715 // diagonal-straight cases: 8 possibilities of "weirder" exists
716  for( int k = 0; k < 2; k++ )
717  {
718  if( ips[k] )
719  {
720  const VECTOR2I m( *ips[k] );
721 
722  if( !aViaMode && m != p0_p && m != p0_n )
723  {
724  VECTOR2I g_p, g_n;
725 
726  g_p = ( p0_p - m ).Resize( ceil( (double) m_gap * M_SQRT2 ) );
727  g_n = ( p0_n - m ).Resize( ceil( (double) m_gap ) );
728 
729  if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE )
730  m_gateways.push_back( DP_GATEWAY( m + g_p, m + g_n, true ) );
731 
732  g_p = ( p0_p - m ).Resize( m_gap );
733  g_n = ( p0_n - m ).Resize( ceil( (double) m_gap * M_SQRT2 ) );
734 
735  if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE )
736  m_gateways.push_back( DP_GATEWAY( m + g_p, m + g_n, true ) );
737  }
738  }
739  }
740  }
741  }
742 
743  if( aBuildEntries )
744  buildEntries( p0_p, p0_n );
745 }
746 
747 
749 {
750  if( m_hasVias )
751  return DP_PRIMITIVE_PAIR( &m_via_p, &m_via_n );
752  else
753  {
754  const LINE lP( PLine() );
755  const LINE lN( NLine() );
756 
757  SEGMENT sP( lP, lP.CSegment( -1 ) );
758  SEGMENT sN( lN, lN.CSegment( -1 ) );
759 
760  DP_PRIMITIVE_PAIR dpair( &sP, &sN );
761  dpair.SetAnchors( sP.Seg().B, sN.Seg().B );
762 
763  return dpair;
764  }
765 }
766 
767 
768 bool commonParallelProjection( SEG n, SEG p, SEG &pClip, SEG& nClip )
769 {
770  SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
771 
772  int64_t t_a = 0;
773  int64_t t_b = p.TCoef( p.B );
774 
775  int64_t tproj_a = p.TCoef( n_proj_p.A );
776  int64_t tproj_b = p.TCoef( n_proj_p.B );
777 
778  if( t_b < t_a )
779  std::swap( t_b, t_a );
780 
781  if( tproj_b < tproj_a )
782  std::swap( tproj_b, tproj_a );
783 
784  if( t_b <= tproj_a )
785  return false;
786 
787  if( t_a >= tproj_b )
788  return false;
789 
790  int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
791  std::vector<int64_t> tv( t, t + 4 );
792  std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
793 
794  int64_t pLenSq = p.SquaredLength();
795 
796  VECTOR2I dp = p.B - p.A;
797  pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
798  pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
799 
800  pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
801  pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
802 
803  nClip.A = n.LineProject( pClip.A );
804  nClip.B = n.LineProject( pClip.B );
805 
806  return true;
807 }
808 
809 
810 double DIFF_PAIR::Skew() const
811 {
812  return m_p.Length() - m_n.Length();
813 }
814 
815 
817 {
818  SHAPE_LINE_CHAIN p( m_p );
819  SHAPE_LINE_CHAIN n( m_n );
820 
821  p.Simplify();
822  n.Simplify();
823 
824  for( int i = 0; i < p.SegmentCount(); i++ )
825  {
826  for( int j = 0; j < n.SegmentCount(); j++ )
827  {
828  SEG sp = p.CSegment( i );
829  SEG sn = n.CSegment( j );
830 
831  SEG p_clip, n_clip;
832 
833  int64_t dist = std::abs( sp.Distance( sn ) - m_width );
834 
835  if( sp.ApproxParallel( sn ) && m_gapConstraint.Matches( dist ) && commonParallelProjection( sp, sn, p_clip, n_clip ) )
836  {
837  const COUPLED_SEGMENTS spair( p_clip, sp, i, n_clip, sn, j );
838  aPairs.push_back( spair );
839  }
840  }
841  }
842 }
843 
844 
845 int64_t DIFF_PAIR::CoupledLength( const SHAPE_LINE_CHAIN& aP, const SHAPE_LINE_CHAIN& aN ) const
846 {
847  int64_t total = 0;
848 
849  for( int i = 0; i < aP.SegmentCount(); i++ )
850  {
851  for( int j = 0; j < aN.SegmentCount(); j++ )
852  {
853  SEG sp = aP.CSegment( i );
854  SEG sn = aN.CSegment( j );
855 
856  SEG p_clip, n_clip;
857 
858  int64_t dist = std::abs( sp.Distance(sn) - m_width );
859 
860  if( sp.ApproxParallel( sn ) && m_gapConstraint.Matches( dist ) &&
861  commonParallelProjection( sp, sn, p_clip, n_clip ) )
862  total += p_clip.Length();
863  }
864  }
865 
866  return total;
867 }
868 
869 
871 {
872  COUPLED_SEGMENTS_VEC pairs;
873 
874  CoupledSegmentPairs( pairs );
875 
876  double l = 0.0;
877  for( unsigned int i = 0; i < pairs.size(); i++ )
878  l += pairs[i].coupledP.Length();
879 
880  return l;
881 }
882 
883 
885 {
886  double t = TotalLength();
887 
888  if( t == 0.0 )
889  return 0.0;
890 
891  return CoupledLength() / t;
892 }
893 
894 
896 {
897  double lenP = m_p.Length();
898  double lenN = m_n.Length();
899 
900  return (lenN + lenP ) / 2.0;
901 }
902 
903 
904 int DIFF_PAIR::CoupledLength ( const SEG& aP, const SEG& aN ) const
905 {
906  SEG p_clip, n_clip;
907  int64_t dist = std::abs( aP.Distance( aN ) - m_width );
908 
909  if( aP.ApproxParallel( aN ) && m_gapConstraint.Matches( dist ) &&
910  commonParallelProjection ( aP, aN, p_clip, n_clip ) )
911  return p_clip.Length();
912 
913  return 0;
914 }
915 
916 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:104
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:289
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:478
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:378
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:125
int Length() const
Function Length()
Definition: seg.h:284
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:323
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:171
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:580
#define abs(a)
Definition: auxiliary.h:84
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const boost::optional< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
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:350
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
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:37
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:49
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:306
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:223
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:245
Class DP_GATEWAYS.
Push and Shove diff pair dimensions (gap) settings dialog.
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:187
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:50