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, bool aFillet ) const
25 {
26  bool startDiagonal;
27 
28  if( m_dir == UNDEFINED )
29  startDiagonal = aStartDiagonal;
30  else
31  startDiagonal = IsDiagonal();
32 
33  int w = abs( aP1.x - aP0.x );
34  int h = abs( aP1.y - aP0.y );
35  int sw = sign( aP1.x - aP0.x );
36  int sh = sign( aP1.y - aP0.y );
37 
38  VECTOR2I mp0, mp1;
39 
40  /*
41  * Non-filleted case:
42  *
43  * For width greater than height, we're calculating something like this.
44  * mp0 will be used if we start straight; mp1 if we start diagonal.
45  *
46  * aP0 ----------------- mp0
47  * . \
48  * . \
49  * . \
50  * mp1 . . . . . . . . aP1
51  *
52  * Filleted case:
53  *
54  * For a fillet, we need to know the arc start point (A in the diagram below)
55  * A straight segment will be needed between aP0 and A if we are starting straight,
56  * or between the arc end and aP1 if we are starting diagonally.
57  *
58  * aP0 -- A --___ mp0
59  * . ---
60  * . --
61  * . --
62  * mp1 . . . . . . . . aP1
63  *
64  * For the length of this segment (tangentLength), we subtract the length of the "diagonal"
65  * line from the "straight" line (i.e. dist(aP0, mp0) - dist(mp0, aP1))
66  * In the example above, we will have a straight segment from aP0 to A, and then we can use
67  * the distance from A to aP1 (diagLength) to calculate the radius of the arc.
68  */
69 
70  int tangentLength;
71 
72  if( w > h )
73  {
74  mp0 = VECTOR2I( ( w - h ) * sw, 0 ); // direction: E
75  mp1 = VECTOR2I( h * sw, h * sh ); // direction: NE
76  tangentLength = ( w - h ) - mp1.EuclideanNorm();
77  }
78  else
79  {
80  mp0 = VECTOR2I( 0, sh * ( h - w ) ); // direction: N
81  mp1 = VECTOR2I( sw * w, sh * w ); // direction: NE
82  tangentLength = ( h - w ) - mp1.EuclideanNorm();
83  }
84 
86 
87  // Shortcut where we can generate just one segment and quit. Avoids more complicated handling
88  // of precision errors if filleting is enabled
89  // TODO: needs refactoring if we support 90-degree arcs via this function
90  if( w == h || w == 0 || h == 0 )
91  {
92  pl.Append( aP0 );
93  pl.Append( aP1 );
94  return pl;
95  }
96 
97  // TODO: if tangentLength zero, we could still place a small arc at the start...
98  if( aFillet )
99  {
100  SHAPE_ARC arc;
101  VECTOR2I arcEndpoint;
102 
103  double diag2 = tangentLength >= 0 ? mp1.SquaredEuclideanNorm() : mp0.SquaredEuclideanNorm();
104  double diagLength = std::sqrt( ( 2 * diag2 ) - ( 2 * diag2 * std::cos( 3 * M_PI_4 ) ) );
105  int arcRadius = KiROUND( diagLength / ( 2.0 * std::cos( 67.5 * M_PI / 180.0 ) ) );
106 
107  // There are four different ways to build an arc, depending on whether or not we are
108  // starting diagonally and whether or not we have a negative tangent length (meaning the
109  // arc has to be on the opposite end of the line from normal). This math could probably
110  // be condensed and optimized but I'm tired of staring at it for now (and it works!)
111 
112  if( startDiagonal )
113  {
114  int rotationSign = ( w > h ) ? ( sw * sh * -1 ) : ( sw * sh );
115 
116  if( tangentLength >= 0 )
117  {
118  // Positive tangentLength, diagonal start: arc goes at the start
119  arcEndpoint = aP1 - mp0.Resize( tangentLength );
120  arc.ConstructFromStartEndAngle( aP0, arcEndpoint, 45 * rotationSign );
121 
122  if( arc.GetP0() == arc.GetP1() )
123  pl.Append( aP0 );
124  else
125  pl.Append( arc );
126 
127  pl.Append( aP1 );
128  }
129  else
130  {
131  // Negative tangentLength, diagonal start: arc goes at the end
132  arcEndpoint = aP0 + mp1.Resize( std::abs( tangentLength ) );
133  arc.ConstructFromStartEndAngle( arcEndpoint, aP1, 45 * rotationSign );
134 
135  pl.Append( aP0 );
136 
137  if( arc.GetP0() == arc.GetP1() )
138  pl.Append( aP1 );
139  else
140  pl.Append( arc );
141  }
142  }
143  else
144  {
145  int rotationSign = ( w > h ) ? ( sw * sh ) : ( sw * sh * -1 );
146  VECTOR2D centerDir( mp0.Rotate( M_PI_2 * rotationSign ) );
147 
148  if( tangentLength >= 0 )
149  {
150  // Positive tangentLength: arc goes at the end
151  arcEndpoint = aP0 + mp0.Resize( tangentLength );
152  arc.ConstructFromStartEndAngle( arcEndpoint, aP1, 45 * rotationSign );
153 
154  pl.Append( aP0 );
155 
156  if( arc.GetP0() == arc.GetP1() )
157  pl.Append( aP1 );
158  else
159  pl.Append( arc );
160  }
161  else
162  {
163  // Negative tangentLength: arc goes at the start
164  VECTOR2I arcCenter = aP0 + centerDir.Resize( arcRadius );
165  SHAPE_ARC ca( arcCenter, aP0, 45 * rotationSign );
166 
167  // Constructing with a center can lead to imprecise endpoint. We need to guarantee
168  // tangency of the endpoint.
169  // TODO: update the math above to calculate the proper endpoint directly
170  VECTOR2I endpoint( ca.GetP1() );
171 
172  if( std::abs( endpoint.y - aP1.y ) < SHAPE_ARC::MIN_PRECISION_IU )
173  {
174  VECTOR2I fixedEnd( endpoint.x, aP1.y );
175  ca.ConstructFromStartEndAngle( ca.GetP0(), fixedEnd, 45 * rotationSign );
176  }
177  else if( std::abs( endpoint.x - aP1.x ) < SHAPE_ARC::MIN_PRECISION_IU )
178  {
179  VECTOR2I fixedEnd( aP1.x, endpoint.y );
180  ca.ConstructFromStartEndAngle( ca.GetP0(), fixedEnd, 45 * rotationSign );
181  }
182 
183  if( ca.GetP0() == ca.GetP1() )
184  pl.Append( aP0 );
185  else
186  pl.Append( ca );
187 
188  pl.Append( aP1 );
189  }
190  }
191  }
192  else
193  {
194  pl.Append( aP0 );
195  pl.Append( startDiagonal ? ( aP0 + mp1 ) : ( aP0 + mp0 ) );
196  pl.Append( aP1 );
197  }
198 
199  pl.Simplify();
200  return pl;
201 }
int sign(T val)
Definition: util.h:101
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
#define M_PI_2
Definition: transline.cpp:37
SHAPE_ARC & ConstructFromStartEndAngle(const VECTOR2I &aStart, const VECTOR2I &aEnd, double aAngle, double aWidth=0)
Constructs this arc from the given start, end and angle.
Definition: shape_arc.cpp:173
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:623
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const VECTOR2I & GetP0() const
Definition: shape_arc.h:95
static const int MIN_PRECISION_IU
This is the minimum precision for all the points in a shape.
Definition: shape.h:122
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
Definition: direction45.h:201
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_LINE_CHAIN.
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:68
Directions m_dir
Are we routing on 45 or 90 degree increments.
Definition: direction45.h:334
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:96