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  s.Append( aP0.x - aClearance + aChamfer, aP0.y - aClearance );
44  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y - aClearance );
45  s.Append( aP0.x + aSize.x + aClearance, aP0.y - aClearance + aChamfer );
46  s.Append( aP0.x + aSize.x + aClearance, aP0.y + aSize.y + aClearance - aChamfer );
47  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y + aSize.y + aClearance );
48  s.Append( aP0.x - aClearance + aChamfer, aP0.y + aSize.y + aClearance );
49  s.Append( aP0.x - aClearance, aP0.y + aSize.y + aClearance - aChamfer );
50 
51  return s;
52 }
53 
54 
55 const SHAPE_LINE_CHAIN ArcHull( const SHAPE_ARC& aSeg, int aClearance,
56  int aWalkaroundThickness )
57 {
58  int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
59  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d ) / 2;
60 
61  auto line = aSeg.ConvertToPolyline();
62 
64  s.SetClosed( true );
65  std::vector<VECTOR2I> reverse_line;
66 
67  auto seg = line.Segment( 0 );
68  VECTOR2I dir = seg.B - seg.A;
69  VECTOR2I p0 = dir.Perpendicular().Resize( d );
70  VECTOR2I ds = dir.Perpendicular().Resize( x );
71  VECTOR2I pd = dir.Resize( x );
72  VECTOR2I dp = dir.Resize( d );
73 
74  // Append the first curve
75  s.Append( seg.A + p0 - pd );
76  s.Append( seg.A - dp + ds );
77  s.Append( seg.A - dp - ds );
78  s.Append( seg.A - p0 - pd );
79 
80  for( int i = 1; i < line.SegmentCount(); i++ )
81  {
82  auto old_seg = seg;
83  auto endpt = ( old_seg.A - old_seg.B ).Resize( seg.Length() );
84  old_seg.A = old_seg.B + endpt;
85 
86  seg = line.Segment( i );
87  auto dir2 = old_seg.A - seg.B;
88 
89  p0 = dir2.Perpendicular().Resize( d );
90  s.Append( seg.A - p0 );
91  reverse_line.push_back( seg.A + p0 );
92  }
93 
94  pd = dir.Resize( x );
95  dp = dir.Resize( d );
96  s.Append( seg.B - p0 + pd );
97  s.Append( seg.B + dp - ds );
98  s.Append( seg.B + dp + ds );
99  s.Append( seg.B + p0 + pd );
100 
101  for( int i = reverse_line.size() - 1; i >= 0; i-- )
102  s.Append( reverse_line[i] );
103 
104  // make sure the hull outline is always clockwise
105  if( s.CSegment( 0 ).Side( line.Segment( 0 ).A ) < 0 )
106  return s.Reverse();
107  else
108  return s;
109 }
110 
111 
112 const SHAPE_LINE_CHAIN SegmentHull ( const SHAPE_SEGMENT& aSeg, int aClearance,
113  int aWalkaroundThickness )
114 {
115  int cl = aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
116  int d = aSeg.GetWidth() / 2 + cl;
117  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d );
118 
119  const VECTOR2I a = aSeg.GetSeg().A;
120  const VECTOR2I b = aSeg.GetSeg().B;
121 
122  if( a == b )
123  {
124  return OctagonalHull( a - VECTOR2I( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 ),
125  VECTOR2I( aSeg.GetWidth(), aSeg.GetWidth() ),
126  cl + 1,
127  0.52 * d );
128  }
129 
130  VECTOR2I dir = b - a;
131  VECTOR2I p0 = dir.Perpendicular().Resize( d );
132  VECTOR2I ds = dir.Perpendicular().Resize( x / 2 );
133  VECTOR2I pd = dir.Resize( x / 2 );
134  VECTOR2I dp = dir.Resize( d );
135 
137 
138  s.SetClosed( true );
139 
140  s.Append( b + p0 + pd );
141  s.Append( b + dp + ds );
142  s.Append( b + dp - ds );
143  s.Append( b - p0 + pd );
144  s.Append( a - p0 - pd );
145  s.Append( a - dp - ds );
146  s.Append( a - dp + ds );
147  s.Append( a + p0 - pd );
148 
149  // make sure the hull outline is always clockwise
150  if( s.CSegment( 0 ).Side( a ) < 0 )
151  return s.Reverse();
152  else
153  return s;
154 }
155 
156 
157 static void MoveDiagonal( SEG& aDiagonal, const SHAPE_LINE_CHAIN& aVertices, int aClearance )
158 {
159  int dist;
160 
161  aVertices.NearestPoint( aDiagonal, dist );
162  dist -= HULL_MARGIN;
163  VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
164  aDiagonal.A += moveBy;
165  aDiagonal.B += moveBy;
166 }
167 
168 
169 const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_SIMPLE& aConvex, int aClearance )
170 {
171  // this defines the horizontal and vertical lines in the hull octagon
172  BOX2I box = aConvex.BBox( aClearance + HULL_MARGIN );
173  box.Normalize();
174 
175  SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
176  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
177  SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
178  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
179  SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
180  box.GetOrigin() );
181  SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
182 
183  const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
184 
185  // top right diagonal
186  VECTOR2I corner = box.GetOrigin() + box.GetSize();
187  SEG toprightline = SEG( corner,
188  corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
189  MoveDiagonal( toprightline, vertices, aClearance );
190 
191  // bottom right diagonal
192  corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
193  SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
194  corner );
195  MoveDiagonal( bottomrightline, vertices, aClearance );
196 
197  // bottom left diagonal
198  corner = box.GetOrigin();
199  SEG bottomleftline = SEG( corner,
200  corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
201  MoveDiagonal( bottomleftline, vertices, aClearance );
202 
203  // top left diagonal
204  corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
205  SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
206  corner );
207  MoveDiagonal( topleftline, vertices, aClearance );
208 
209  SHAPE_LINE_CHAIN octagon;
210  octagon.SetClosed( true );
211 
212  octagon.Append( *leftline.IntersectLines( bottomleftline ) );
213  octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
214  octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
215  octagon.Append( *rightline.IntersectLines( bottomrightline ) );
216  octagon.Append( *rightline.IntersectLines( toprightline ) );
217  octagon.Append( *topline.IntersectLines( toprightline ) );
218  octagon.Append( *topline.IntersectLines( topleftline ) );
219  octagon.Append( *leftline.IntersectLines( topleftline ) );
220 
221  return octagon;
222 }
223 
224 
226 {
227  SHAPE_RECT r;
228 
229  VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
230  VECTOR2I p0( aSeg.GetSeg().A - delta );
231  VECTOR2I p1( aSeg.GetSeg().B + delta );
232 
233  return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
234  std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
235 }
236 
237 #if 0
238 void DrawDebugPoint( VECTOR2I aP, int aColor )
239 {
241 
242  l.Append( aP - VECTOR2I( -50000, -50000 ) );
243  l.Append( aP + VECTOR2I( -50000, -50000 ) );
244 
245  ROUTER::GetInstance()->DisplayDebugLine ( l, aColor, 10000 );
246 
247  l.Clear();
248  l.Append( aP - VECTOR2I( 50000, -50000 ) );
249  l.Append( aP + VECTOR2I( 50000, -50000 ) );
250 
251  ROUTER::GetInstance()->DisplayDebugLine( l, aColor, 10000 );
252 }
253 
254 
255 void DrawDebugBox( BOX2I aB, int aColor )
256 {
258 
259  VECTOR2I o = aB.GetOrigin();
260  VECTOR2I s = aB.GetSize();
261 
262  l.Append( o );
263  l.Append( o.x + s.x, o.y );
264  l.Append( o.x + s.x, o.y + s.y );
265  l.Append( o.x, o.y + s.y );
266  l.Append( o );
267 
268  ROUTER::GetInstance()->DisplayDebugLine( l, aColor, 10000 );
269 }
270 
271 
272 void DrawDebugSeg( SEG aS, int aColor )
273 {
275 
276  l.Append( aS.A );
277  l.Append( aS.B );
278 
279  ROUTER::GetInstance()->DisplayDebugLine( l, aColor, 10000 );
280 }
281 
282 
283 void DrawDebugDirs( VECTOR2D aP, int aMask, int aColor )
284 {
285  BOX2I b( aP - VECTOR2I( 10000, 10000 ), VECTOR2I( 20000, 20000 ) );
286 
287  DrawDebugBox( b, aColor );
288  for( int i = 0; i < 8; i++ )
289  {
290  if( ( 1 << i ) & aMask )
291  {
292  VECTOR2I v = DIRECTION_45( ( DIRECTION_45::Directions ) i ).ToVector() * 100000;
293  DrawDebugSeg( SEG( aP, aP + v ), aColor );
294  }
295  }
296 }
297 #endif
298 
299 OPT_BOX2I ChangedArea( const ITEM* aItemA, const ITEM* aItemB )
300 {
301  if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
302  {
303  const VIA* va = static_cast<const VIA*>( aItemA );
304  const VIA* vb = static_cast<const VIA*>( aItemB );
305 
306  return va->ChangedArea( vb );
307  }
308  else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
309  {
310  const LINE* la = static_cast<const LINE*> ( aItemA );
311  const LINE* lb = static_cast<const LINE*> ( aItemB );
312 
313  return la->ChangedArea( lb );
314  }
315 
316  return OPT_BOX2I();
317 }
318 
319 OPT_BOX2I ChangedArea( const LINE& aLineA, const LINE& aLineB )
320 {
321  return aLineA.ChangedArea( &aLineB );
322 }
323 
324 }
Directions
Available directions, there are 8 of them, as on a rectilinear map (north = up) + an extra undefined ...
Definition: direction45.h:48
Base class for PNS router board items.
Definition: pns_item.h:55
const SHAPE_LINE_CHAIN ConvexHull(const SHAPE_SIMPLE &aConvex, int aClearance)
Function ConvexHull()
Definition: pns_utils.cpp:169
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
SHAPE_SIMPLE.
Definition: shape_simple.h:43
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:1051
coord_type GetX() const
Definition: box2.h:190
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
const VECTOR2I ToVector() const
Definition: direction45.h:274
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:208
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:299
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
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:82
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
OPT_BOX2I ChangedArea(const VIA *aOther) const
Definition: pns_via.cpp:108
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:112
const SEG & GetSeg() const
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Finds a point on the line chain that is closest to point aP.
void SetClosed(bool aClosed)
Function SetClosed()
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:408
static void MoveDiagonal(SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
Definition: pns_utils.cpp:157
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
coord_type GetWidth() const
Definition: box2.h:197
BOX2< Vec > & Normalize()
Function Normalize ensures that the height ant width are positive.
Definition: box2.h:129
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:133
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Definition: pns_utils.cpp:35
Definition: seg.h:41
coord_type GetY() const
Definition: box2.h:191
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:55
int GetWidth() const
Definition: shape_arc.h:112
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:225
VECTOR2I A
Definition: seg.h:49
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:134
coord_type GetHeight() const
Definition: box2.h:198
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
void Clear()
Function Clear() Removes all points from the line chain.
const Vec & GetSize() const
Definition: box2.h:189
const Vec & GetOrigin() const
Definition: box2.h:193
Push and Shove diff pair dimensions (gap) settings dialog.
int GetWidth() const
static ROUTER * GetInstance()
Definition: pns_router.cpp:79
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:143
VECTOR2I B
Definition: seg.h:50