KiCad PCB EDA Suite
pns_utils.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <[email protected]>
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 "pns_utils.h"
23 #include "pns_line.h"
24 #include "pns_via.h"
25 #include "pns_router.h"
26 #include "pns_debug_decorator.h"
27 
28 #include <geometry/shape_arc.h>
29 #include <geometry/shape_segment.h>
30 #include <math/box2.h>
31 
32 #include <cmath>
33 
34 namespace PNS {
35 
36 const SHAPE_LINE_CHAIN OctagonalHull( const VECTOR2I& aP0, const VECTOR2I& aSize,
37  int aClearance, int aChamfer )
38 {
40 
41  s.SetClosed( true );
42 
43  s.Append( aP0.x - aClearance, aP0.y - aClearance + aChamfer );
44 
45  if( aChamfer )
46  s.Append( aP0.x - aClearance + aChamfer, aP0.y - aClearance );
47 
48  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y - aClearance );
49 
50  if( aChamfer )
51  s.Append( aP0.x + aSize.x + aClearance, aP0.y - aClearance + aChamfer );
52 
53  s.Append( aP0.x + aSize.x + aClearance, aP0.y + aSize.y + aClearance - aChamfer );
54 
55  if( aChamfer )
56  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y + aSize.y + aClearance );
57 
58  s.Append( aP0.x - aClearance + aChamfer, aP0.y + aSize.y + aClearance );
59 
60  if( aChamfer )
61  s.Append( aP0.x - aClearance, aP0.y + aSize.y + aClearance - aChamfer );
62 
63  return s;
64 }
65 
66 
67 const SHAPE_LINE_CHAIN ArcHull( const SHAPE_ARC& aSeg, int aClearance, int aWalkaroundThickness )
68 {
69  int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2
71  int x = (int) ( 2.0 / ( 1.0 + M_SQRT2 ) * d ) / 2;
72 
73  auto line = aSeg.ConvertToPolyline();
74 
76  s.SetClosed( true );
77  std::vector<VECTOR2I> reverse_line;
78 
79  auto seg = line.Segment( 0 );
80  VECTOR2I dir = seg.B - seg.A;
81  VECTOR2I p0 = -dir.Perpendicular().Resize( d );
82  VECTOR2I ds = -dir.Perpendicular().Resize( x );
83  VECTOR2I pd = dir.Resize( x );
84  VECTOR2I dp = dir.Resize( d );
85 
86  // Append the first curve
87  s.Append( seg.A + p0 - pd );
88  s.Append( seg.A - dp + ds );
89  s.Append( seg.A - dp - ds );
90  s.Append( seg.A - p0 - pd );
91 
92  for( int i = 1; i < line.SegmentCount(); i++ )
93  {
94  // calculate a vertex normal (average of segment normals)
95  auto pp =
96  ( line.CSegment( i - 1 ).B - line.CSegment( i - 1 ).A ).Perpendicular().Resize( d );
97  auto pp2 = ( line.CSegment( i ).B - line.CSegment( i ).A ).Perpendicular().Resize( d );
98 
99  auto sa_out = line.CSegment( i - 1 ), sa_in = line.CSegment( i - 1 );
100  auto sb_out = line.CSegment( i ), sb_in = line.CSegment( i );
101 
102  sa_out.A += pp;
103  sa_out.B += pp;
104  sb_out.A += pp2;
105  sb_out.B += pp2;
106 
107  sa_in.A -= pp;
108  sa_in.B -= pp;
109  sb_in.A -= pp2;
110  sb_in.B -= pp2;
111 
112  auto ip_out = sa_out.IntersectLines( sb_out );
113  auto ip_in = sa_in.IntersectLines( sb_in );
114 
115  seg = line.CSegment( i );
116  auto lead = ( pp + pp2 ) / 2;
117 
118  s.Append( *ip_out );
119  reverse_line.push_back( *ip_in );
120  }
121 
122  seg = line.CSegment( -1 );
123  dir = seg.B - seg.A;
124  p0 = -dir.Perpendicular().Resize( d );
125  ds = -dir.Perpendicular().Resize( x );
126  pd = dir.Resize( x );
127  dp = dir.Resize( d );
128  s.Append( seg.B - p0 + pd );
129  s.Append( seg.B + dp - ds );
130  s.Append( seg.B + dp + ds );
131  s.Append( seg.B + p0 + pd );
132 
133  for( int i = reverse_line.size() - 1; i >= 0; i-- )
134  s.Append( reverse_line[i] );
135 
136  // make sure the hull outline is always clockwise
137  // make sure the hull outline is always clockwise
138  if( s.CSegment( 0 ).Side( line.Segment( 0 ).A ) < 0 )
139  return s.Reverse();
140  else
141  return s;
142 }
143 
144 
145 static bool IsSegment45Degree( const SEG& aS )
146 {
147  VECTOR2I dir( aS.B - aS.A );
148 
149  if( std::abs( dir.x ) <= 1 )
150  return true;
151 
152  if( std::abs( dir.y ) <= 1 )
153  return true;
154 
155  int delta = std::abs(dir.x) - std::abs(dir.y);
156 
157  if( delta >= -1 && delta <= 1)
158  return true;
159 
160  return false;
161 }
162 
163 
164 template <typename T> int sgn(T val) {
165  return (T(0) < val) - (val < T(0));
166 }
167 
168 
169 const SHAPE_LINE_CHAIN SegmentHull ( const SHAPE_SEGMENT& aSeg, int aClearance,
170  int aWalkaroundThickness )
171 {
172  const int kinkThreshold = aClearance / 10;
173 
174  int cl = aClearance + aWalkaroundThickness / 2;
175  double d = (double)aSeg.GetWidth() / 2.0 + cl;
176  double x = 2.0 / ( 1.0 + M_SQRT2 ) * d;
177  int dr = KiROUND( d );
178  int xr = KiROUND( x );
179  int xr2 = KiROUND( x / 2.0 );
180 
181  const VECTOR2I a = aSeg.GetSeg().A;
182  VECTOR2I b = aSeg.GetSeg().B;
183  int len = aSeg.GetSeg().Length();
184  int w = b.x - a.x;
185  int h = b.y - a.y;
186 
187  /*
188  auto dbg = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
189 
190  if( len < kinkThreshold )
191  {
192  PNS_DBG( dbg, AddShape, &aSeg, CYAN, 10000, wxString::Format( "kinky-seg 45 %d l %d dx %d dy %d", !!IsSegment45Degree( aSeg.GetSeg() ), len, w, h ) );
193  }
194  */
195 
196  if ( !IsSegment45Degree( aSeg.GetSeg() ) )
197  {
198  if ( len <= kinkThreshold && len > 0 )
199  {
200  int ll = std::max( std::abs( w ), std::abs( h ) );
201 
202  b = a + VECTOR2I( sgn( w ) * ll, sgn( h ) * ll );
203  }
204  }
205  else
206  {
207  if( len <= kinkThreshold )
208  {
209  int delta45 = std::abs( std::abs(w) - std::abs(h) );
210  if( std::abs(w) <= 1 ) // almost vertical
211  {
212  w = 0;
213  cl ++;
214  }
215  else if ( std::abs(h) <= 1 ) // almost horizontal
216  {
217  h = 0;
218  cl ++;
219  }
220  else if ( delta45 <= 2 ) // almost 45 degree
221  {
222  int newW = sgn( w ) * std::max( std::abs(w), std::abs( h ) );
223  int newH = sgn( h ) * std::max( std::abs(w), std::abs( h ) );
224  w = newW;
225  h = newH;
226  cl += 2;
227  //PNS_DBG( dbg, AddShape, &aSeg, CYAN, 10000, wxString::Format( "almostkinky45 45 %d l %d dx %d dy %d", !!IsSegment45Degree( aSeg.GetSeg() ), len, w, h ) );
228 
229  }
230 
231  b.x = a.x + w;
232  b.y = a.y + h;
233  }
234  }
235 
236  if( a == b )
237  {
238  int xx2 = KiROUND( 2.0 * ( 1.0 - M_SQRT2 ) * d );
239 
240  return OctagonalHull( a - VECTOR2I( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 ),
241  VECTOR2I( aSeg.GetWidth(), aSeg.GetWidth() ),
242  cl,
243  xx2 );
244  }
245 
246  VECTOR2I dir = b - a;
247  VECTOR2I p0 = dir.Perpendicular().Resize( dr );
248  VECTOR2I ds = dir.Perpendicular().Resize( xr2 );
249  VECTOR2I pd = dir.Resize( xr2 );
250  VECTOR2I dp = dir.Resize( dr );
251 
253 
254  s.SetClosed( true );
255 
256  s.Append( b + p0 + pd );
257  s.Append( b + dp + ds );
258  s.Append( b + dp - ds );
259  s.Append( b - p0 + pd );
260  s.Append( a - p0 - pd );
261  s.Append( a - dp - ds );
262  s.Append( a - dp + ds );
263  s.Append( a + p0 - pd );
264 
265  // make sure the hull outline is always clockwise
266  if( s.CSegment( 0 ).Side( a ) < 0 )
267  return s.Reverse();
268  else
269  return s;
270 }
271 
272 
273 static void MoveDiagonal( SEG& aDiagonal, const SHAPE_LINE_CHAIN& aVertices, int aClearance )
274 {
275  int dist;
276 
277  aVertices.NearestPoint( aDiagonal, dist );
278  VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
279  aDiagonal.A += moveBy;
280  aDiagonal.B += moveBy;
281 }
282 
283 
284 const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_SIMPLE& aConvex, int aClearance )
285 {
286  // this defines the horizontal and vertical lines in the hull octagon
287  BOX2I box = aConvex.BBox( aClearance );
288  box.Normalize();
289 
290  SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
291  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
292  SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
293  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
294  SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
295  box.GetOrigin() );
296  SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
297 
298  const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
299 
300  // top right diagonal
301  VECTOR2I corner = box.GetOrigin() + box.GetSize();
302  SEG toprightline = SEG( corner,
303  corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
304  MoveDiagonal( toprightline, vertices, aClearance );
305 
306  // bottom right diagonal
307  corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
308  SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
309  corner );
310  MoveDiagonal( bottomrightline, vertices, aClearance );
311 
312  // bottom left diagonal
313  corner = box.GetOrigin();
314  SEG bottomleftline = SEG( corner,
315  corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
316  MoveDiagonal( bottomleftline, vertices, aClearance );
317 
318  // top left diagonal
319  corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
320  SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
321  corner );
322  MoveDiagonal( topleftline, vertices, aClearance );
323 
324  SHAPE_LINE_CHAIN octagon;
325  octagon.SetClosed( true );
326 
327  octagon.Append( *leftline.IntersectLines( bottomleftline ) );
328  octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
329  octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
330  octagon.Append( *rightline.IntersectLines( bottomrightline ) );
331  octagon.Append( *rightline.IntersectLines( toprightline ) );
332  octagon.Append( *topline.IntersectLines( toprightline ) );
333  octagon.Append( *topline.IntersectLines( topleftline ) );
334  octagon.Append( *leftline.IntersectLines( topleftline ) );
335 
336  return octagon;
337 }
338 
339 
341 {
342  SHAPE_RECT r;
343 
344  VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
345  VECTOR2I p0( aSeg.GetSeg().A - delta );
346  VECTOR2I p1( aSeg.GetSeg().B + delta );
347 
348  return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
349  std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
350 }
351 
352 
353 OPT_BOX2I ChangedArea( const ITEM* aItemA, const ITEM* aItemB )
354 {
355  if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
356  {
357  const VIA* va = static_cast<const VIA*>( aItemA );
358  const VIA* vb = static_cast<const VIA*>( aItemB );
359 
360  return va->ChangedArea( vb );
361  }
362  else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
363  {
364  const LINE* la = static_cast<const LINE*> ( aItemA );
365  const LINE* lb = static_cast<const LINE*> ( aItemB );
366 
367  return la->ChangedArea( lb );
368  }
369 
370  return OPT_BOX2I();
371 }
372 
373 OPT_BOX2I ChangedArea( const LINE& aLineA, const LINE& aLineB )
374 {
375  return aLineA.ChangedArea( &aLineB );
376 }
377 
378 
379 void HullIntersection( const SHAPE_LINE_CHAIN& hull, const SHAPE_LINE_CHAIN& line,
381 {
383 
384  if( line.PointCount() < 2 )
385  return;
386 
387  hull.Intersect( line, ips_raw );
388 
389  for( auto& p : ips_raw )
390  {
392 
393  SEG d1[2];
394  VECTOR2I d2[2];
395  int d1_idx = 0, d2_idx = 0;
396 
397  ipp = p;
398  ipp.valid = false;
399 
400  if( !p.is_corner_our && !p.is_corner_their )
401  {
402  ipp.valid = true;
403  ips.push_back( ipp );
404  continue;
405  }
406 
407  if( p.index_our >= hull.SegmentCount() )
408  p.index_our -= hull.SegmentCount();
409 
410  if( p.is_corner_our )
411  {
412  d1[0] = hull.CSegment( p.index_our );
413  d1[1] = hull.CSegment( p.index_our - 1 );
414  d1_idx = 2;
415  }
416  else
417  {
418  d1[0] = hull.CSegment( p.index_our );
419  d1_idx = 1;
420  }
421 
422  if( p.is_corner_their )
423  {
424  if( p.index_their > 0 )
425  {
426  d2[d2_idx++] = line.CSegment( p.index_their - 1 ).A;
427  }
428  if( p.index_their < line.PointCount() - 1 )
429  {
430  d2[d2_idx++] = line.CSegment( p.index_their ).B;
431  }
432  }
433  else
434  {
435  d2[d2_idx++] = line.CSegment( p.index_their ).A;
436  d2[d2_idx++] = line.CSegment( p.index_their ).B;
437  }
438 
439  for( int i = 0; i < d1_idx; i++ )
440  {
441  for( int j = 0; j < d2_idx; j++ )
442  {
443  if( d1[i].Side( d2[j] ) > 0 )
444  {
445  ipp.valid = true;
446  }
447  }
448  }
449 
450 #ifdef TOM_EXTRA_DEBUG
451  printf("p %d %d hi %d their %d co %d ct %d ipv %d\n", p.p.x, p.p.y, p.index_our, p.index_their, p.is_corner_our?1:0, p.is_corner_their?1:0, ipp.valid ?1:0);
452  printf("d1 %d d2 %d\n", d1_idx, d2_idx );
453 #endif
454  if( ipp.valid )
455  {
456  ips.push_back( ipp );
457  }
458  }
459 }
460 
461 }
int Length() const
Return the length (this).
Definition: seg.h:350
Represent an intersection between two line segments.
Base class for PNS router board items.
Definition: pns_item.h:55
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
Definition: pns_utils.cpp:379
const SHAPE_LINE_CHAIN ConvexHull(const SHAPE_SIMPLE &aConvex, int aClearance)
Function ConvexHull()
Definition: pns_utils.cpp:284
Represent a simple polygon consisting of a zero-thickness closed chain of connected line segments.
Definition: shape_simple.h:41
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
std::vector< INTERSECTION > INTERSECTIONS
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:1166
coord_type GetX() const
Definition: box2.h:173
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
Define a general 2D-vector/point.
Definition: vector2d.h:61
OPT_BOX2I ChangedArea(const VIA *aOther) const
Definition: pns_via.cpp:122
static bool IsSegment45Degree(const SEG &aS)
Definition: pns_utils.cpp:145
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:209
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:220
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:353
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_simple.h:78
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
int PointCount() const
Return the number of points (vertices) in this line chain.
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:169
const SEG & GetSeg() const
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
static void MoveDiagonal(SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
Definition: pns_utils.cpp:273
coord_type GetWidth() const
Definition: box2.h:180
BOX2< Vec > & Normalize()
Ensure that the height ant width are positive.
Definition: box2.h:112
const SHAPE_LINE_CHAIN & Vertices() const
Return the list of vertices defining this simple polygon.
Definition: shape_simple.h:124
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Definition: pns_utils.cpp:36
int sgn(T val)
Definition: pns_utils.cpp:164
E_SERIE r
Definition: eserie.cpp:41
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
coord_type GetY() const
Definition: box2.h:174
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
const SHAPE_LINE_CHAIN ArcHull(const SHAPE_ARC &aSeg, int aClearance, int aWalkaroundThickness)
Various utility functions.
Definition: pns_utils.cpp:67
int GetWidth() const
Definition: shape_arc.h:156
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=DefaultAccuracyForPCB(), double *aEffectiveAccuracy=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:458
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:340
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:138
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:73
coord_type GetHeight() const
Definition: box2.h:181
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509
constexpr int delta
const Vec & GetSize() const
Definition: box2.h:172
const Vec & GetOrigin() const
Definition: box2.h:176
Push and Shove diff pair dimensions (gap) settings dialog.
int GetWidth() const
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:142
VECTOR2I B
Definition: seg.h:49