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