KiCad PCB EDA Suite
direction_45.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2019 KiCad Developers, see AUTHORS.txt for contributors.
5  *
6  * This program is free software: you can redistribute it and/or modify it
7  * under the terms of the GNU General Public License as published by the
8  * Free Software Foundation, either version 3 of the License, or (at your
9  * option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License along
17  * with this program. If not, see <http://www.gnu.or/licenses/>.
18  */
19 
20 #include <geometry/direction45.h>
21 
22 
24  bool aStartDiagonal,
25  CORNER_MODE aMode ) const
26 
27 {
28  bool startDiagonal;
29 
30  if( m_dir == UNDEFINED )
31  startDiagonal = aStartDiagonal;
32  else
33  startDiagonal = IsDiagonal();
34 
35  int w = abs( aP1.x - aP0.x );
36  int h = abs( aP1.y - aP0.y );
37  int sw = sign( aP1.x - aP0.x );
38  int sh = sign( aP1.y - aP0.y );
39 
40  bool is90mode = aMode == CORNER_MODE::ROUNDED_90 || aMode == CORNER_MODE::MITERED_90;
42 
43  // Shortcut where we can generate just one segment and quit. Avoids more complicated handling
44  // of precision errors if filleting is enabled
45  if( w == 0 || h == 0 || ( !is90mode && h == w ) )
46  {
47  pl.Append( aP0 );
48  pl.Append( aP1 );
49  return pl;
50  }
51 
52  VECTOR2I mp0, mp1;
53  int tangentLength;
54 
55  if( is90mode )
56  {
57  if( startDiagonal == ( h >= w ) )
58  {
59  mp0 = VECTOR2I( w * sw, 0 ); // direction: E
60  }
61  else
62  {
63  mp0 = VECTOR2I( 0, sh * h ); // direction: N
64  }
65  }
66  else
67  {
68  if( w > h )
69  {
70  mp0 = VECTOR2I( ( w - h ) * sw, 0 ); // direction: E
71  mp1 = VECTOR2I( h * sw, h * sh ); // direction: NE
72  tangentLength = ( w - h ) - mp1.EuclideanNorm();
73  }
74  else
75  {
76  mp0 = VECTOR2I( 0, sh * ( h - w ) ); // direction: N
77  mp1 = VECTOR2I( sw * w, sh * w ); // direction: NE
78  tangentLength = ( h - w ) - mp1.EuclideanNorm();
79  }
80  }
81 
82  SHAPE_ARC arc;
83  VECTOR2I arcEndpoint;
84 
85  switch( aMode )
86  {
87  case CORNER_MODE::MITERED_45:
88  /*
89  * For width greater than height, we're calculating something like this.
90  * mp0 will be used if we start straight; mp1 if we start diagonal.
91  *
92  * aP0 ----------------- mp0
93  * . \
94  * . \
95  * . \
96  * mp1 . . . . . . . . aP1
97  *
98  */
99  pl.Append( aP0 );
100  pl.Append( startDiagonal ? ( aP0 + mp1 ) : ( aP0 + mp0 ) );
101  pl.Append( aP1 );
102  break;
103 
104  case CORNER_MODE::ROUNDED_45:
105  {
106  /*
107  * For a fillet, we need to know the arc start point (A in the diagram below)
108  * A straight segment will be needed between aP0 and A if we are starting straight,
109  * or between the arc end and aP1 if we are starting diagonally.
110  *
111  * aP0 -- A --___ mp0
112  * . ---
113  * . --
114  * . --
115  * mp1 . . . . . . . . aP1
116  *
117  * For the length of this segment (tangentLength), we subtract the length of the "diagonal"
118  * line from the "straight" line (i.e. dist(aP0, mp0) - dist(mp0, aP1))
119  * In the example above, we will have a straight segment from aP0 to A, and then we can use
120  * the distance from A to aP1 (diagLength) to calculate the radius of the arc.
121  */
122  if( w == h )
123  {
124  pl.Append( aP0 );
125  pl.Append( aP1 );
126  break;
127  }
128 
129  double diag2 = tangentLength >= 0 ? mp1.SquaredEuclideanNorm() : mp0.SquaredEuclideanNorm();
130  double diagLength = std::sqrt( ( 2 * diag2 ) - ( 2 * diag2 * std::cos( 3 * M_PI_4 ) ) );
131  int arcRadius = KiROUND( diagLength / ( 2.0 * std::cos( 67.5 * M_PI / 180.0 ) ) );
132 
133  // There are four different ways to build an arc, depending on whether or not we are
134  // starting diagonally and whether or not we have a negative tangent length (meaning the
135  // arc has to be on the opposite end of the line from normal). This math could probably
136  // be condensed and optimized but I'm tired of staring at it for now (and it works!)
137 
138  if( startDiagonal )
139  {
140  int rotationSign = ( w > h ) ? ( sw * sh * -1 ) : ( sw * sh );
141 
142  if( tangentLength >= 0 )
143  {
144  // Positive tangentLength, diagonal start: arc goes at the start
145  arcEndpoint = aP1 - mp0.Resize( tangentLength );
146  arc.ConstructFromStartEndAngle( aP0, arcEndpoint, 45 * rotationSign );
147 
148  if( arc.GetP0() == arc.GetP1() )
149  pl.Append( aP0 );
150  else
151  pl.Append( arc );
152 
153  pl.Append( aP1 );
154  }
155  else
156  {
157  // Negative tangentLength, diagonal start: arc goes at the end
158  arcEndpoint = aP0 + mp1.Resize( std::abs( tangentLength ) );
159  arc.ConstructFromStartEndAngle( arcEndpoint, aP1, 45 * rotationSign );
160 
161  pl.Append( aP0 );
162 
163  if( arc.GetP0() == arc.GetP1() )
164  pl.Append( aP1 );
165  else
166  pl.Append( arc );
167  }
168  }
169  else
170  {
171  int rotationSign = ( w > h ) ? ( sw * sh ) : ( sw * sh * -1 );
172  VECTOR2D centerDir( mp0.Rotate( M_PI_2 * rotationSign ) );
173 
174  if( tangentLength >= 0 )
175  {
176  // Positive tangentLength: arc goes at the end
177  arcEndpoint = aP0 + mp0.Resize( tangentLength );
178  arc.ConstructFromStartEndAngle( arcEndpoint, aP1, 45 * rotationSign );
179 
180  pl.Append( aP0 );
181 
182  if( arc.GetP0() == arc.GetP1() )
183  pl.Append( aP1 );
184  else
185  pl.Append( arc );
186  }
187  else
188  {
189  // Negative tangentLength: arc goes at the start
190  VECTOR2I arcCenter = aP0 + centerDir.Resize( arcRadius );
191  SHAPE_ARC ca( arcCenter, aP0, 45 * rotationSign );
192 
193  // Constructing with a center can lead to imprecise endpoint. We need to guarantee
194  // tangency of the endpoint.
195  // TODO: update the math above to calculate the proper endpoint directly
196  VECTOR2I endpoint( ca.GetP1() );
197 
198  if( std::abs( endpoint.y - aP1.y ) < SHAPE_ARC::MIN_PRECISION_IU )
199  {
200  VECTOR2I fixedEnd( endpoint.x, aP1.y );
201  ca.ConstructFromStartEndAngle( ca.GetP0(), fixedEnd, 45 * rotationSign );
202  }
203  else if( std::abs( endpoint.x - aP1.x ) < SHAPE_ARC::MIN_PRECISION_IU )
204  {
205  VECTOR2I fixedEnd( aP1.x, endpoint.y );
206  ca.ConstructFromStartEndAngle( ca.GetP0(), fixedEnd, 45 * rotationSign );
207  }
208 
209  if( ca.GetP0() == ca.GetP1() )
210  pl.Append( aP0 );
211  else
212  pl.Append( ca );
213 
214  pl.Append( aP1 );
215  }
216  }
217  break;
218  }
219  case CORNER_MODE::MITERED_90:
220  /*
221  * For width greater than height, we're calculating something like this.
222  *
223  * <-mp0->
224  * aP0 -------------------+
225  * |
226  * |
227  * |
228  * aP1
229  */
230  pl.Append( aP0 );
231  pl.Append( aP0 + mp0 );
232  pl.Append( aP1 );
233  break;
234 
235  case CORNER_MODE::ROUNDED_90:
236  /*
237  * For a fillet, we need to know the arc end point
238  * A straight segment will be needed between aP0 and arcEnd in case distance aP0,mp0 is bigger
239  * than the distance mp0,aP1, if the distance is shorter the straigth segment is between
240  * arcEnd and aP1. If both distances are equal, we don't need a straight segment.
241  *
242  * aP0 ----- arcEnd ---__
243  * --
244  * \
245  * |
246  * arcCenter aP1
247  *
248  * For the length of the radius we use the shorter of the horizontal and vertical distance.
249  */
250  SHAPE_ARC arc;
251 
252  if( w == h ) // we only need one arc without a straigth line.
253  {
254  arc.ConstructFromStartEndCenter( aP0, aP1, aP1 - mp0, sh == sw != startDiagonal );
255  pl.Append( arc );
256  return pl;
257  }
258 
259  VECTOR2I arcEnd; // Arc position that is not at aP0 nor aP1
260  VECTOR2I arcCenter;
261 
262  if( startDiagonal ) //Means start with the arc first
263  {
264  if( h > w ) // Arc followed by a vertical line
265  {
266  int y = aP0.y + ( w * sh );
267  arcEnd = VECTOR2I( aP1.x, y );
268  arcCenter = VECTOR2I( aP0.x, y );
269  arc.ConstructFromStartEndCenter( aP0, arcEnd, arcCenter, sh != sw );
270  pl.Append( arc );
271  pl.Append( aP1 );
272  }
273  else // Arc followed by a horizontal line
274  {
275  int x = aP0.x + ( h * sw );
276  arcEnd = VECTOR2I( x, aP1.y );
277  arcCenter = VECTOR2I( x, aP0.y );
278  arc.ConstructFromStartEndCenter( aP0, arcEnd, arcCenter, sh == sw );
279  pl.Append( arc );
280  pl.Append( aP1 );
281  }
282  }
283  else
284  {
285  if( w > h ) // Horizontal line followed by the arc
286  {
287  int x = aP1.x - ( h * sw );
288  arcEnd = VECTOR2I( x, aP0.y );
289  arcCenter = VECTOR2I( x, aP1.y );
290  pl.Append( aP0 );
291  arc.ConstructFromStartEndCenter( arcEnd, aP1, arcCenter, sh != sw );
292  pl.Append( arc );
293  }
294  else // Vertical line followed by the arc
295  {
296  int y = aP1.y - ( w * sh );
297  arcEnd = VECTOR2I( aP0.x, y );
298  arcCenter = VECTOR2I( aP1.x, y );
299  pl.Append( aP0 );
300  arc.ConstructFromStartEndCenter( arcEnd, aP1, arcCenter, sh == sw );
301  pl.Append( arc );
302  }
303  }
304  break;
305  }
306 
307  pl.Simplify();
308  return pl;
309 }
int sign(T val)
Definition: util.h:104
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
#define M_PI_2
Definition: transline.cpp:40
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
SHAPE_ARC & ConstructFromStartEndAngle(const VECTOR2I &aStart, const VECTOR2I &aEnd, double aAngle, double aWidth=0)
Construct this arc from the given start, end and angle.
Definition: shape_arc.cpp:183
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:300
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
CORNER_MODE
Corner modes.
Definition: direction45.h:66
static const int MIN_PRECISION_IU
This is the minimum precision for all the points in a shape.
Definition: shape.h:122
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
Definition: direction45.h:213
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
VECTOR2< T > Rotate(double aAngle) const
Rotate the vector by a given angle.
Definition: vector2d.h:371
SHAPE_ARC & ConstructFromStartEndCenter(const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aClockwise=false, double aWidth=0)
Constructs this arc from the given start, end and center.
Definition: shape_arc.cpp:201
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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
Directions m_dir
Are we routing on 45 or 90 degree increments.
Definition: direction45.h:346
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
const VECTOR2I & GetP1() const
Definition: shape_arc.h:112