KiCad PCB EDA Suite
shape_arc.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) 2017 CERN
5  * Copyright (C) 2019-2020 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
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
27 #include <geometry/seg.h> // for SEG
28 #include <geometry/shape_arc.h>
30 #include <trigo.h>
31 
32 
33 SHAPE_ARC::SHAPE_ARC( const VECTOR2I& aArcCenter, const VECTOR2I& aArcStartPoint,
34  double aCenterAngle, int aWidth ) :
35  SHAPE( SH_ARC ), m_width( aWidth )
36 {
37  m_start = aArcStartPoint;
38  m_mid = aArcStartPoint;
39  m_end = aArcStartPoint;
40 
41  RotatePoint( m_mid, aArcCenter, -aCenterAngle * 10.0 / 2.0 );
42  RotatePoint( m_end, aArcCenter, -aCenterAngle * 10.0 );
43 
44  update_bbox();
45 }
46 
47 
48 SHAPE_ARC::SHAPE_ARC( const VECTOR2I& aArcStart, const VECTOR2I& aArcMid,
49  const VECTOR2I& aArcEnd, int aWidth ) :
50  SHAPE( SH_ARC ), m_start( aArcStart ), m_mid( aArcMid ), m_end( aArcEnd ),
51  m_width( aWidth )
52 {
53  update_bbox();
54 }
55 
56 
58  : SHAPE( SH_ARC )
59 {
60  m_start = aOther.m_start;
61  m_end = aOther.m_end;
62  m_mid = aOther.m_mid;
63  m_width = aOther.m_width;
64  m_bbox = aOther.m_bbox;
65 }
66 
67 
68 bool SHAPE_ARC::Collide( const SEG& aSeg, int aClearance, int* aActual ) const
69 {
70  int minDist = aClearance + m_width / 2;
71  VECTOR2I center = GetCenter();
72  ecoord dist_sq = VECTOR2I::ECOORD_MAX;
73 
74  VECTOR2I ab = ( aSeg.B - aSeg.A );
75  VECTOR2I ac = ( center - aSeg.A );
76 
77  ecoord lenAbSq = ab.SquaredEuclideanNorm();
78  double lambda = (double) ac.Dot( ab ) / (double) lenAbSq;
79 
80  if( lambda >= 0.0 && lambda <= 1.0 )
81  {
82  VECTOR2I p;
83 
84  p.x = (double) aSeg.A.x * lambda + (double) aSeg.B.x * (1.0 - lambda);
85  p.y = (double) aSeg.A.y * lambda + (double) aSeg.B.y * (1.0 - lambda);
86 
87  dist_sq = std::min( dist_sq, ( m_start - p ).SquaredEuclideanNorm() );
88  dist_sq = std::min( dist_sq, ( m_end - p ).SquaredEuclideanNorm() );
89  }
90 
91  dist_sq = std::min( dist_sq, aSeg.SquaredDistance( m_start ) );
92  dist_sq = std::min( dist_sq, aSeg.SquaredDistance( m_end ) );
93 
94  if( dist_sq == 0 || dist_sq < (ecoord) minDist * minDist )
95  {
96  if( aActual )
97  *aActual = std::max( 0, (int) sqrt( dist_sq ) - m_width / 2 );
98 
99  return true;
100  }
101 
102  return false;
103 }
104 
105 
107 {
108  std::vector<VECTOR2I> points;
109  // Put start and end points in the point list
110  points.push_back( m_start );
111  points.push_back( m_end );
112 
113  double start_angle = GetStartAngle();
114  double end_angle = start_angle + GetCentralAngle();
115 
116  // we always count quadrants clockwise (increasing angle)
117  if( start_angle > end_angle )
118  std::swap( start_angle, end_angle );
119 
120  int quad_angle_start = std::ceil( start_angle / 90.0 );
121  int quad_angle_end = std::floor( end_angle / 90.0 );
122 
123  // count through quadrants included in arc
124  for( int quad_angle = quad_angle_start; quad_angle <= quad_angle_end; ++quad_angle )
125  {
126  const int radius = KiROUND( GetRadius() );
127  VECTOR2I quad_pt = GetCenter();
128 
129  switch( quad_angle % 4 )
130  {
131  case 0: quad_pt += { radius, 0 }; break;
132  case 1:
133  case -3: quad_pt += { 0, radius }; break;
134  case 2:
135  case -2: quad_pt += { -radius, 0 }; break;
136  case 3:
137  case -1: quad_pt += { 0, -radius }; break;
138  default: assert( false );
139  }
140 
141  points.push_back( quad_pt );
142  }
143 
144  m_bbox.Compute( points );
145 }
146 
147 
148 const BOX2I SHAPE_ARC::BBox( int aClearance ) const
149 {
150  BOX2I bbox( m_bbox );
151 
152  if( aClearance != 0 )
153  bbox.Inflate( aClearance );
154 
155  return bbox;
156 }
157 
158 
159 bool SHAPE_ARC::Collide( const VECTOR2I& aP, int aClearance, int* aActual ) const
160 {
161  int minDist = aClearance + m_width / 2;
162  auto bbox = BBox( minDist );
163 
164  if( !bbox.Contains( aP ) )
165  return false;
166 
167  ecoord min_dist_sq = (ecoord) minDist * minDist;
168  ecoord r = GetRadius();
169  ecoord r_sq = r * r;
170 
171  ecoord dist_sq = ( aP - GetCenter() ).SquaredEuclideanNorm();
172  ecoord dist_to_edge_sq = abs( dist_sq - r_sq );
173 
174  if( dist_to_edge_sq < min_dist_sq )
175  {
176  if( aActual )
177  *aActual = std::max( 0, (int) sqrt( dist_to_edge_sq ) - m_width / 2 );
178 
179  return true;
180  }
181 
182  return false;
183 }
184 
185 
187 {
188  VECTOR2D d( m_start - GetCenter() );
189 
190  auto ang = 180.0 / M_PI * atan2( d.y, d.x );
191 
192  return NormalizeAngleDegrees( ang, 0.0, 360.0 );
193 }
194 
195 
197 {
198  VECTOR2D d( m_end - GetCenter() );
199 
200  auto ang = 180.0 / M_PI * atan2( d.y, d.x );
201 
202  return NormalizeAngleDegrees( ang, 0.0, 360.0 );
203 }
204 
205 
207 {
208  return GetArcCenter( m_start, m_mid, m_end );
209 }
210 
211 
213 {
214  VECTOR2I center = GetCenter();
215  VECTOR2I p0 = m_start - center;
216  VECTOR2I p1 = m_mid - center;
217  VECTOR2I p2 = m_end - center;
218  double angle1 = ArcTangente( p1.y, p1.x ) - ArcTangente( p0.y, p0.x );
219  double angle2 = ArcTangente( p2.y, p2.x ) - ArcTangente( p1.y, p1.x );
220 
221  return ( NormalizeAngle180( angle1 ) + NormalizeAngle180( angle2 ) ) / 10.0;
222 }
223 
224 
225 double SHAPE_ARC::GetRadius() const
226 {
227  return ( m_start - GetCenter() ).EuclideanNorm();
228 }
229 
230 
231 const SHAPE_LINE_CHAIN SHAPE_ARC::ConvertToPolyline( double aAccuracy ) const
232 {
233  SHAPE_LINE_CHAIN rv;
234  double r = GetRadius();
235  double sa = GetStartAngle();
236  auto c = GetCenter();
237  double ca = GetCentralAngle();
238 
239  int n;
240 
241  if( r == 0.0 )
242  {
243  n = 0;
244  }
245  else
246  {
247  n = GetArcToSegmentCount( r, aAccuracy, ca );
248  }
249 
250  for( int i = 0; i <= n ; i++ )
251  {
252  double a = sa;
253 
254  if( n != 0 )
255  a += ( ca * i ) / n;
256 
257  double x = c.x + r * cos( a * M_PI / 180.0 );
258  double y = c.y + r * sin( a * M_PI / 180.0 );
259 
260  rv.Append( KiROUND( x ), KiROUND( y ) );
261  }
262 
263  return rv;
264 }
265 
266 
267 void SHAPE_ARC::Move( const VECTOR2I& aVector )
268 {
269  m_start += aVector;
270  m_end += aVector;
271  m_mid += aVector;
272  update_bbox();
273 }
274 
275 
276 void SHAPE_ARC::Rotate( double aAngle, const VECTOR2I& aCenter )
277 {
278  m_start -= aCenter;
279  m_end -= aCenter;
280  m_mid -= aCenter;
281 
282  m_start = m_start.Rotate( aAngle );
283  m_end = m_end.Rotate( aAngle );
284  m_mid = m_mid.Rotate( aAngle );
285 
286  m_start += aCenter;
287  m_end += aCenter;
288  m_mid += aCenter;
289 
290  update_bbox();
291 }
292 
293 
294 void SHAPE_ARC::Mirror( bool aX, bool aY, const VECTOR2I& aVector )
295 {
296  if( aX )
297  {
298  m_start.x = -m_start.x + 2 * aVector.x;
299  m_end.x = -m_end.x + 2 * aVector.x;
300  m_mid.x = -m_mid.x + 2 * aVector.x;
301  }
302 
303  if( aY )
304  {
305  m_start.y = -m_start.y + 2 * aVector.y;
306  m_end.y = -m_end.y + 2 * aVector.y;
307  m_mid.y = -m_mid.y + 2 * aVector.y;
308  }
309 
310  update_bbox();
311 }
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aVector={ 0, 0 })
Definition: shape_arc.cpp:294
void Rotate(double aAngle, const VECTOR2I &aCenter) override
Function Rotate rotates the arc by a given angle about a point.
Definition: shape_arc.cpp:276
double GetRadius() const
Definition: shape_arc.cpp:225
VECTOR2I m_end
Definition: shape_arc.h:142
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:91
extended_type SquaredEuclideanNorm() const
Function Squared Euclidean Norm computes the squared euclidean norm of the vector,...
Definition: vector2d.h:306
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:37
double GetStartAngle() const
Definition: shape_arc.cpp:186
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:208
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
T NormalizeAngle180(T Angle)
Normalize angle to be in the -180.0 .. 180.0 range.
Definition: trigo.h:345
VECTOR2I m_mid
Definition: shape_arc.h:141
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
compound shape, consisting of multiple simple shapes
Definition: shape.h:48
a few functions useful in geometry calculations.
SHAPE.
Definition: shape.h:74
double GetEndAngle() const
Definition: shape_arc.cpp:196
void update_bbox()
Definition: shape_arc.cpp:106
Definition: seg.h:39
void Move(const VECTOR2I &aVector) override
Definition: shape_arc.cpp:267
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
VECTOR2< T > Rotate(double aAngle) const
Function Rotate rotates the vector by a given angle.
Definition: vector2d.h:377
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:492
VECTOR2I::extended_type ecoord
Definition: shape.h:77
SHAPE_LINE_CHAIN.
VECTOR2I m_start
Definition: shape_arc.h:140
VECTOR2I A
Definition: seg.h:47
double GetCentralAngle() const
Definition: shape_arc.cpp:212
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
SHAPE_ARC()
Definition: shape_arc.h:37
double NormalizeAngleDegrees(double Angle, double aMin, double aMax)
Normalize angle to be aMin < angle <= aMax angle is in degrees.
Definition: trigo.h:292
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_arc.cpp:148
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
Definition: shape_arc.cpp:68
double ArcTangente(int dy, int dx)
Definition: trigo.cpp:162
const VECTOR2I GetArcCenter(const VECTOR2I &aStart, const VECTOR2I &aMid, const VECTOR2I &aEnd)
Determine the center of an arc or circle given three points on its circumference.
Definition: trigo.cpp:405
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:231
int m_width
Definition: shape_arc.h:144
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
BOX2I m_bbox
Definition: shape_arc.h:145
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:206
VECTOR2I B
Definition: seg.h:48