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_segment.h>
28 
29 #include <cmath>
30 
31 namespace PNS {
32 
33 const SHAPE_LINE_CHAIN OctagonalHull( const VECTOR2I& aP0, const VECTOR2I& aSize,
34  int aClearance, int aChamfer )
35 {
37 
38  s.SetClosed( true );
39 
40  s.Append( aP0.x - aClearance, aP0.y - aClearance + aChamfer );
41  s.Append( aP0.x - aClearance + aChamfer, aP0.y - aClearance );
42  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y - aClearance );
43  s.Append( aP0.x + aSize.x + aClearance, aP0.y - aClearance + aChamfer );
44  s.Append( aP0.x + aSize.x + aClearance, aP0.y + aSize.y + aClearance - aChamfer );
45  s.Append( aP0.x + aSize.x + aClearance - aChamfer, aP0.y + aSize.y + aClearance );
46  s.Append( aP0.x - aClearance + aChamfer, aP0.y + aSize.y + aClearance );
47  s.Append( aP0.x - aClearance, aP0.y + aSize.y + aClearance - aChamfer );
48 
49  return s;
50 }
51 
52 
53 const SHAPE_LINE_CHAIN SegmentHull ( const SHAPE_SEGMENT& aSeg, int aClearance,
54  int aWalkaroundThickness )
55 {
56  int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
57  int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d );
58 
59  const VECTOR2I a = aSeg.GetSeg().A;
60  const VECTOR2I b = aSeg.GetSeg().B;
61 
62  VECTOR2I dir = b - a;
63  VECTOR2I p0 = dir.Perpendicular().Resize( d );
64  VECTOR2I ds = dir.Perpendicular().Resize( x / 2 );
65  VECTOR2I pd = dir.Resize( x / 2 );
66  VECTOR2I dp = dir.Resize( d );
67 
69 
70  s.SetClosed( true );
71 
72  s.Append( b + p0 + pd );
73  s.Append( b + dp + ds );
74  s.Append( b + dp - ds );
75  s.Append( b - p0 + pd );
76  s.Append( a - p0 - pd );
77  s.Append( a - dp - ds );
78  s.Append( a - dp + ds );
79  s.Append( a + p0 - pd );
80 
81  // make sure the hull outline is always clockwise
82  if( s.CSegment( 0 ).Side( a ) < 0 )
83  return s.Reverse();
84  else
85  return s;
86 }
87 
88 
89 static void MoveDiagonal( SEG& aDiagonal, const SHAPE_LINE_CHAIN& aVertices, int aClearance )
90 {
91  int dist;
92 
93  aVertices.NearestPoint( aDiagonal, dist );
94  dist -= HULL_MARGIN;
95  VECTOR2I moveBy = ( aDiagonal.A - aDiagonal.B ).Perpendicular().Resize( dist - aClearance );
96  aDiagonal.A += moveBy;
97  aDiagonal.B += moveBy;
98 }
99 
100 
101 const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_CONVEX& aConvex, int aClearance )
102 {
103  // this defines the horizontal and vertical lines in the hull octagon
104  BOX2I box = aConvex.BBox( aClearance + HULL_MARGIN );
105  box.Normalize();
106 
107  SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
108  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
109  SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
110  VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
111  SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
112  box.GetOrigin() );
113  SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );
114 
115  const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();
116 
117  // top right diagonal
118  VECTOR2I corner = box.GetOrigin() + box.GetSize();
119  SEG toprightline = SEG( corner,
120  corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
121  MoveDiagonal( toprightline, vertices, aClearance );
122 
123  // bottom right diagonal
124  corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
125  SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
126  corner );
127  MoveDiagonal( bottomrightline, vertices, aClearance );
128 
129  // bottom left diagonal
130  corner = box.GetOrigin();
131  SEG bottomleftline = SEG( corner,
132  corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
133  MoveDiagonal( bottomleftline, vertices, aClearance );
134 
135  // top left diagonal
136  corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
137  SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
138  corner );
139  MoveDiagonal( topleftline, vertices, aClearance );
140 
141  SHAPE_LINE_CHAIN octagon;
142  octagon.SetClosed( true );
143 
144  octagon.Append( leftline.IntersectLines( bottomleftline ).get() );
145  octagon.Append( bottomline.IntersectLines( bottomleftline ).get() );
146  octagon.Append( bottomline.IntersectLines( bottomrightline ).get() );
147  octagon.Append( rightline.IntersectLines( bottomrightline ).get() );
148  octagon.Append( rightline.IntersectLines( toprightline ).get() );
149  octagon.Append( topline.IntersectLines( toprightline ).get() );
150  octagon.Append( topline.IntersectLines( topleftline ).get() );
151  octagon.Append( leftline.IntersectLines( topleftline ).get() );
152 
153  return octagon;
154 }
155 
156 
158 {
159  SHAPE_RECT r;
160 
161  VECTOR2I delta( aSeg.GetWidth() / 2, aSeg.GetWidth() / 2 );
162  VECTOR2I p0( aSeg.GetSeg().A - delta );
163  VECTOR2I p1( aSeg.GetSeg().B + delta );
164 
165  return SHAPE_RECT( std::min( p0.x, p1.x ), std::min( p0.y, p1.y ),
166  std::abs( p1.x - p0.x ), std::abs( p1.y - p0.y ) );
167 }
168 
169 #if 0
170 void DrawDebugPoint( VECTOR2I aP, int aColor )
171 {
173 
174  l.Append( aP - VECTOR2I( -50000, -50000 ) );
175  l.Append( aP + VECTOR2I( -50000, -50000 ) );
176 
177  ROUTER::GetInstance()->DisplayDebugLine ( l, aColor, 10000 );
178 
179  l.Clear();
180  l.Append( aP - VECTOR2I( 50000, -50000 ) );
181  l.Append( aP + VECTOR2I( 50000, -50000 ) );
182 
183  ROUTER::GetInstance()->DisplayDebugLine( l, aColor, 10000 );
184 }
185 
186 
187 void DrawDebugBox( BOX2I aB, int aColor )
188 {
190 
191  VECTOR2I o = aB.GetOrigin();
192  VECTOR2I s = aB.GetSize();
193 
194  l.Append( o );
195  l.Append( o.x + s.x, o.y );
196  l.Append( o.x + s.x, o.y + s.y );
197  l.Append( o.x, o.y + s.y );
198  l.Append( o );
199 
200  ROUTER::GetInstance()->DisplayDebugLine( l, aColor, 10000 );
201 }
202 
203 
204 void DrawDebugSeg( SEG aS, int aColor )
205 {
207 
208  l.Append( aS.A );
209  l.Append( aS.B );
210 
211  ROUTER::GetInstance()->DisplayDebugLine( l, aColor, 10000 );
212 }
213 
214 
215 void DrawDebugDirs( VECTOR2D aP, int aMask, int aColor )
216 {
217  BOX2I b( aP - VECTOR2I( 10000, 10000 ), VECTOR2I( 20000, 20000 ) );
218 
219  DrawDebugBox( b, aColor );
220  for( int i = 0; i < 8; i++ )
221  {
222  if( ( 1 << i ) & aMask )
223  {
224  VECTOR2I v = DIRECTION_45( ( DIRECTION_45::Directions ) i ).ToVector() * 100000;
225  DrawDebugSeg( SEG( aP, aP + v ), aColor );
226  }
227  }
228 }
229 #endif
230 
231 OPT_BOX2I ChangedArea( const ITEM* aItemA, const ITEM* aItemB )
232 {
233  if( aItemA->OfKind( ITEM::VIA_T ) && aItemB->OfKind( ITEM::VIA_T ) )
234  {
235  const VIA* va = static_cast<const VIA*>( aItemA );
236  const VIA* vb = static_cast<const VIA*>( aItemB );
237 
238  return va->ChangedArea( vb );
239  }
240  else if( aItemA->OfKind( ITEM::LINE_T ) && aItemB->OfKind( ITEM::LINE_T ) )
241  {
242  const LINE* la = static_cast<const LINE*> ( aItemA );
243  const LINE* lb = static_cast<const LINE*> ( aItemB );
244 
245  return la->ChangedArea( lb );
246  }
247 
248  return OPT_BOX2I();
249 }
250 
251 OPT_BOX2I ChangedArea( const LINE& aLineA, const LINE& aLineB )
252 {
253  return aLineA.ChangedArea( &aLineB );
254 }
255 
256 }
const VECTOR2I ToVector() const
Function ToVector()
Definition: direction45.h:295
const Vec & GetOrigin() const
Definition: box2.h:181
Class ITEM.
Definition: pns_item.h:53
coord_type GetY() const
Definition: box2.h:179
constexpr int HULL_MARGIN
Definition: pns_utils.h:34
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_convex.h:74
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:388
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:123
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:804
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:170
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:65
static const int dist[10][10]
Definition: dist.cpp:57
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Class SHAPE_CONVEX.
Definition: shape_convex.h:42
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:231
const Vec & GetSize() const
Definition: box2.h:177
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590
#define abs(a)
Definition: auxiliary.h:84
static const int delta[8][2]
Definition: solve.cpp:112
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:53
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
coord_type GetWidth() const
Definition: box2.h:185
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:130
const SEG CSegment(int aIndex) const
Function CSegment()
void SetClosed(bool aClosed)
Function SetClosed()
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_convex.h:139
static void MoveDiagonal(SEG &aDiagonal, const SHAPE_LINE_CHAIN &aVertices, int aClearance)
Definition: pns_utils.cpp:89
Class DIRECTION_45.
Definition: direction45.h:33
BOX2< Vec > & Normalize()
Function Normalize ensures that the height ant width are positive.
Definition: box2.h:117
int GetWidth() const
Definition: shape_segment.h:80
const SHAPE_LINE_CHAIN ConvexHull(const SHAPE_CONVEX &aConvex, int aClearance)
Function ConvexHull()
Definition: pns_utils.cpp:101
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Various utility functions.
Definition: pns_utils.cpp:33
Definition: seg.h:37
coord_type GetHeight() const
Definition: box2.h:186
const SEG & GetSeg() const
Definition: shape_segment.h:70
Class SHAPE_LINE_CHAIN.
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:157
VECTOR2I A
Definition: seg.h:47
VECTOR2< T > Perpendicular() const
Function Perpendicular computes the perpendicular vector.
Definition: vector2d.h:316
void Clear()
Function Clear() Removes all points from the line chain.
Directions
Enum Directions Represents available directions - there are 8 of them, as on a rectilinear map (north...
Definition: direction45.h:42
coord_type GetX() const
Definition: box2.h:178
Push and Shove diff pair dimensions (gap) settings dialog.
boost::optional< BOX2I > OPT_BOX2I
Definition: box2.h:471
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
#define min(a, b)
Definition: auxiliary.h:85
OPT_BOX2I ChangedArea(const VIA *aOther) const
Definition: pns_via.cpp:102
VECTOR2I B
Definition: seg.h:48