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 <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 "pns_utils.h"
23 #include "pns_line.h"
24 #include "pns_via.h"
25 #include "pns_router.h"
26 
27 #include <geometry/shape_arc.h>
28 #include <geometry/shape_segment.h>
29 #include <math/box2.h>
30 
31 #include <cmath>
32 
33 namespace PNS {
34 
35 const SHAPE_LINE_CHAIN OctagonalHull( const VECTOR2I& aP0, const VECTOR2I& aSize,
36  int aClearance, int aChamfer )
37 {
39 
40  s.SetClosed( true );
41 
42  s.Append( aP0.x - aClearance, aP0.y - aClearance + aChamfer );
43 
44  if( aChamfer )
45  s.Append( aP0.x - aClearance + aChamfer, aP0.y - aClearance );
46 
47  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y - aClearance );
48 
49  if( aChamfer )
50  s.Append( aP0.x + aSize.x + aClearance, aP0.y - aClearance + aChamfer );
51 
52  s.Append( aP0.x + aSize.x + aClearance, aP0.y + aSize.y + aClearance - aChamfer );
53 
54  if( aChamfer )
55  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y + aSize.y + aClearance );
56 
57  s.Append( aP0.x - aClearance + aChamfer, aP0.y + aSize.y + aClearance );
58 
59  if( aChamfer )
60  s.Append( aP0.x - aClearance, aP0.y + aSize.y + aClearance - aChamfer );
61 
62  return s;
63 }
64 
65 
66 const SHAPE_LINE_CHAIN ArcHull( const SHAPE_ARC& aSeg, int aClearance,
67  int aWalkaroundThickness )
68 {
69  int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
70  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d ) / 2;
71 
72  auto line = aSeg.ConvertToPolyline();
73 
75  s.SetClosed( true );
76  std::vector<VECTOR2I> reverse_line;
77 
78  auto seg = line.Segment( 0 );
79  VECTOR2I dir = seg.B - seg.A;
80  VECTOR2I p0 = dir.Perpendicular().Resize( d );
81  VECTOR2I ds = dir.Perpendicular().Resize( x );
82  VECTOR2I pd = dir.Resize( x );
83  VECTOR2I dp = dir.Resize( d );
84 
85  // Append the first curve
86  s.Append( seg.A + p0 - pd );
87  s.Append( seg.A - dp + ds );
88  s.Append( seg.A - dp - ds );
89  s.Append( seg.A - p0 - pd );
90 
91  for( int i = 1; i < line.SegmentCount(); i++ )
92  {
93  auto old_seg = seg;
94  auto endpt = ( old_seg.A - old_seg.B ).Resize( seg.Length() );
95  old_seg.A = old_seg.B + endpt;
96 
97  seg = line.Segment( i );
98  auto dir2 = old_seg.A - seg.B;
99 
100  p0 = dir2.Perpendicular().Resize( d );
101  s.Append( seg.A - p0 );
102  reverse_line.push_back( seg.A + p0 );
103  }
104 
105  pd = dir.Resize( x );
106  dp = dir.Resize( d );
107  s.Append( seg.B - p0 + pd );
108  s.Append( seg.B + dp - ds );
109  s.Append( seg.B + dp + ds );
110  s.Append( seg.B + p0 + pd );
111 
112  for( int i = reverse_line.size() - 1; i >= 0; i-- )
113  s.Append( reverse_line[i] );
114 
115  // make sure the hull outline is always clockwise
116  if( s.CSegment( 0 ).Side( line.Segment( 0 ).A ) < 0 )
117  return s.Reverse();
118  else
119  return s;
120 }
121 
122 
123 const SHAPE_LINE_CHAIN SegmentHull ( const SHAPE_SEGMENT& aSeg, int aClearance,
124  int aWalkaroundThickness )
125 {
126  int cl = aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
127  int d = aSeg.GetWidth() / 2 + cl;
128  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d );
129 
130  const VECTOR2I a = aSeg.GetSeg().A;
131  const VECTOR2I b = aSeg.GetSeg().B;
132 
133  if( a == b )
134  {
135  return OctagonalHull( a - VECTOR2I( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 ),
136  VECTOR2I( aSeg.GetWidth(), aSeg.GetWidth() ),
137  cl + 1,
138  2.0 * ( 1.0 - M_SQRT1_2 ) * d );
139  }
140 
141  VECTOR2I dir = b - a;
142  VECTOR2I p0 = dir.Perpendicular().Resize( d );
143  VECTOR2I ds = dir.Perpendicular().Resize( x / 2 );
144  VECTOR2I pd = dir.Resize( x / 2 );
145  VECTOR2I dp = dir.Resize( d );
146 
148 
149  s.SetClosed( true );
150 
151  s.Append( b + p0 + pd );
152  s.Append( b + dp + ds );
153  s.Append( b + dp - ds );
154  s.Append( b - p0 + pd );
155  s.Append( a - p0 - pd );
156  s.Append( a - dp - ds );
157  s.Append( a - dp + ds );
158  s.Append( a + p0 - pd );
159 
160  // make sure the hull outline is always clockwise
161  if( s.CSegment( 0 ).Side( a ) < 0 )
162  return s.Reverse();
163  else
164  return s;
165 }
166 
167 
168 static void MoveDiagonal( SEG& aDiagonal, const SHAPE_LINE_CHAIN& aVertices, int aClearance )
169 {
170  int dist;
171 
172  aVertices.NearestPoint( aDiagonal, dist );
173  dist -= HULL_MARGIN;
174  VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
175  aDiagonal.A += moveBy;
176  aDiagonal.B += moveBy;
177 }
178 
179 
180 const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_SIMPLE& aConvex, int aClearance )
181 {
182  // this defines the horizontal and vertical lines in the hull octagon
183  BOX2I box = aConvex.BBox( aClearance + HULL_MARGIN );
184  box.Normalize();
185 
186  SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
187  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
188  SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
189  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
190  SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
191  box.GetOrigin() );
192  SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
193 
194  const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
195 
196  // top right diagonal
197  VECTOR2I corner = box.GetOrigin() + box.GetSize();
198  SEG toprightline = SEG( corner,
199  corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
200  MoveDiagonal( toprightline, vertices, aClearance );
201 
202  // bottom right diagonal
203  corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
204  SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
205  corner );
206  MoveDiagonal( bottomrightline, vertices, aClearance );
207 
208  // bottom left diagonal
209  corner = box.GetOrigin();
210  SEG bottomleftline = SEG( corner,
211  corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
212  MoveDiagonal( bottomleftline, vertices, aClearance );
213 
214  // top left diagonal
215  corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
216  SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
217  corner );
218  MoveDiagonal( topleftline, vertices, aClearance );
219 
220  SHAPE_LINE_CHAIN octagon;
221  octagon.SetClosed( true );
222 
223  octagon.Append( *leftline.IntersectLines( bottomleftline ) );
224  octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
225  octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
226  octagon.Append( *rightline.IntersectLines( bottomrightline ) );
227  octagon.Append( *rightline.IntersectLines( toprightline ) );
228  octagon.Append( *topline.IntersectLines( toprightline ) );
229  octagon.Append( *topline.IntersectLines( topleftline ) );
230  octagon.Append( *leftline.IntersectLines( topleftline ) );
231 
232  return octagon;
233 }
234 
235 
237 {
238  SHAPE_RECT r;
239 
240  VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
241  VECTOR2I p0( aSeg.GetSeg().A - delta );
242  VECTOR2I p1( aSeg.GetSeg().B + delta );
243 
244  return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
245  std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
246 }
247 
248 
249 OPT_BOX2I ChangedArea( const ITEM* aItemA, const ITEM* aItemB )
250 {
251  if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
252  {
253  const VIA* va = static_cast<const VIA*>( aItemA );
254  const VIA* vb = static_cast<const VIA*>( aItemB );
255 
256  return va->ChangedArea( vb );
257  }
258  else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
259  {
260  const LINE* la = static_cast<const LINE*> ( aItemA );
261  const LINE* lb = static_cast<const LINE*> ( aItemB );
262 
263  return la->ChangedArea( lb );
264  }
265 
266  return OPT_BOX2I();
267 }
268 
269 OPT_BOX2I ChangedArea( const LINE& aLineA, const LINE& aLineB )
270 {
271  return aLineA.ChangedArea( &aLineB );
272 }
273 
274 
275 void HullIntersection( const SHAPE_LINE_CHAIN& hull, const SHAPE_LINE_CHAIN& line,
277 {
279 
280  if( line.PointCount() < 2 )
281  return;
282 
283  hull.Intersect( line, ips_raw );
284 
285  for( auto& p : ips_raw )
286  {
288 
289  SEG d1[2];
290  VECTOR2I d2[2];
291  int d1_idx = 0, d2_idx = 0;
292 
293  ipp = p;
294  ipp.valid = false;
295 
296  if( !p.is_corner_our && !p.is_corner_their )
297  {
298  ipp.valid = true;
299  ips.push_back( ipp );
300  continue;
301  }
302 
303  if( p.index_our >= hull.SegmentCount() )
304  p.index_our -= hull.SegmentCount();
305 
306  if( p.is_corner_our )
307  {
308  d1[0] = hull.CSegment( p.index_our );
309  d1[1] = hull.CSegment( p.index_our - 1 );
310  d1_idx = 2;
311  }
312  else
313  {
314  d1[0] = hull.CSegment( p.index_our );
315  d1_idx = 1;
316  }
317 
318  if( p.is_corner_their )
319  {
320  if( p.index_their > 0 )
321  {
322  d2[d2_idx++] = line.CSegment( p.index_their - 1 ).A;
323  }
324  if( p.index_their < line.PointCount() - 1 )
325  {
326  d2[d2_idx++] = line.CSegment( p.index_their ).B;
327  }
328  }
329  else
330  {
331  d2[d2_idx++] = line.CSegment( p.index_their ).A;
332  d2[d2_idx++] = line.CSegment( p.index_their ).B;
333  }
334 
335  for( int i = 0; i < d1_idx; i++ )
336  {
337  for( int j = 0; j < d2_idx; j++ )
338  {
339  if( d1[i].Side( d2[j] ) > 0 )
340  {
341  ipp.valid = true;
342  }
343  }
344  }
345 
346 #ifdef TOM_EXTRA_DEBUG
347  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);
348  printf("d1 %d d2 %d\n", d1_idx, d2_idx );
349 #endif
350  if( ipp.valid )
351  {
352  ips.push_back( ipp );
353  }
354  }
355 }
356 
357 }
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:275
const SHAPE_LINE_CHAIN ConvexHull(const SHAPE_SIMPLE &aConvex, int aClearance)
Function ConvexHull()
Definition: pns_utils.cpp:180
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
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:1151
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:110
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
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:249
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:623
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:123
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:168
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:35
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:66
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:498
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:236
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
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