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