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 
26 #include <algorithm>
27 #include <math.h>
28 #include <vector>
29 
31 #include <geometry/seg.h> // for SEG
32 #include <geometry/shape_arc.h>
34 #include <math.h> // for cos, sin, M_PI, atan2, ceil
35 #include <math/box2.h> // for BOX2I
36 #include <math/vector2d.h> // for VECTOR2I, VECTOR2D, VECTOR2
37 #include <type_traits> // for swap
38 
39 
40 bool SHAPE_ARC::Collide( const SEG& aSeg, int aClearance ) const
41 {
42  int minDist = aClearance + m_width / 2;
43  auto centerDist = aSeg.Distance( m_pc );
44  auto p1 = GetP1();
45 
46  if( centerDist < minDist )
47  return true;
48 
49  auto ab = (aSeg.B - aSeg.A );
50  auto ac = ( m_pc - aSeg.A );
51 
52  auto lenAbSq = ab.SquaredEuclideanNorm();
53 
54  auto lambda = (double) ac.Dot( ab ) / (double) lenAbSq;
55 
56 
57  if( lambda >= 0.0 && lambda <= 1.0 )
58  {
59  VECTOR2I p;
60 
61  p.x = (double) aSeg.A.x * lambda + (double) aSeg.B.x * (1.0 - lambda);
62  p.y = (double) aSeg.A.y * lambda + (double) aSeg.B.y * (1.0 - lambda);
63 
64  auto p0pdist = ( m_p0 - p ).EuclideanNorm();
65 
66  if( p0pdist < minDist )
67  return true;
68 
69  auto p1pdist = ( p1 - p ).EuclideanNorm();
70 
71  if( p1pdist < minDist )
72  return true;
73  }
74 
75  auto p0dist = aSeg.Distance( m_p0 );
76 
77  if( p0dist > minDist )
78  return true;
79 
80  auto p1dist = aSeg.Distance( p1 );
81 
82  if( p1dist > minDist )
83  return false;
84 
85 
86  return true;
87 }
88 
89 #if 0
90 bool SHAPE_ARC::ConstructFromCorners( VECTOR2I aP0, VECTOR2I aP1, double aCenterAngle )
91 {
92  VECTOR2D mid = ( VECTOR2D( aP0 ) + VECTOR2D( aP1 ) ) * 0.5;
93  VECTOR2D chord = VECTOR2D( aP1 ) - VECTOR2D( aP0 );
94  double c = (aP1 - aP0).EuclideanNorm() / 2;
95  VECTOR2D d = chord.Rotate( M_PI / 2.0 ).Resize( c );
96 
97  m_pc = mid + d * ( 1.0 / tan( aCenterAngle / 2.0 * M_PI / 180.0 ) );
98  m_p0 = aP0;
99  m_p1 = aP1;
100 
101  return true;
102 }
103 
104 bool SHAPE_ARC::ConstructFromCornerAndAngles( VECTOR2I aP0,
105  double aStartAngle,
106  double aCenterAngle,
107  double aRadius )
108 {
109  m_p0 = aP0;
110  auto d1 = VECTOR2D( 1.0, 0.0 ).Rotate( aStartAngle * M_PI / 180.0 ) * aRadius;
111  auto d2 =
112  VECTOR2D( 1.0, 0.0 ).Rotate( (aStartAngle + aCenterAngle) * M_PI / 180.0 ) * aRadius;
113 
114  m_pc = m_p0 - (VECTOR2I) d1;
115  m_p1 = m_pc + (VECTOR2I) d2;
116 
117  if( aCenterAngle < 0 )
118  std::swap( m_p0, m_p1 );
119 
120  return true;
121 }
122 
123 bool SHAPE_ARC::ConstructFromCenterAndAngles( VECTOR2I aCenter, double aRadius, double aStartAngle, double aCenterAngle )
124 {
125  double ea = aStartAngle + aCenterAngle;
126 
127  m_fullCircle = false;
128  m_pc = aCenter;
129  m_p0.x = (int) ( (double) aCenter.x + aRadius * cos( aStartAngle * M_PI / 180.0 ) );
130  m_p0.y = (int) ( (double) aCenter.y + aRadius * sin( aStartAngle * M_PI / 180.0 ) );
131  m_p1.x = (int) ( (double) aCenter.x + aRadius * cos( ea * M_PI / 180.0 ) );
132  m_p1.y = (int) ( (double) aCenter.y + aRadius * sin( ea * M_PI / 180.0 ) );
133 
134  if( aCenterAngle == 360.0 )
135  {
136  m_fullCircle = true;
137  return true;
138  }
139  else if ( aCenterAngle < 0.0 )
140  {
141  std::swap(m_p0, m_p1);
142  }
143 
144  return true;
145 }
146 #endif
147 
148 
150 {
151  VECTOR2D rvec = m_p0 - m_pc;
152  auto ca = m_centralAngle * M_PI / 180.0;
153  VECTOR2I p1;
154 
155  p1.x = KiROUND( m_pc.x + rvec.x * cos( ca ) - rvec.y * sin( ca ) );
156  p1.y = KiROUND( m_pc.y + rvec.x * sin( ca ) + rvec.y * cos( ca ) );
157 
158  return p1;
159 }
160 
161 
163 {
164  VECTOR2D rvec = m_p0 - m_pc;
165  auto ca = m_centralAngle / 2.0 * M_PI / 180.0;
166  VECTOR2I p1;
167 
168  p1.x = KiROUND( m_pc.x + rvec.x * cos( ca ) - rvec.y * sin( ca ) );
169  p1.y = KiROUND( m_pc.y + rvec.x * sin( ca ) + rvec.y * cos( ca ) );
170 
171  return p1;
172 }
173 
174 
176 {
177  std::vector<VECTOR2I> points;
178  // Put start and end points in the point list
179  points.push_back( m_p0 );
180  points.push_back( GetP1() );
181  // points.push_back( m_pc ); the center point is not necessary in the BBox
182 
183  double start_angle = GetStartAngle();
184  double end_angle = start_angle + GetCentralAngle();
185 
186  // we always count quadrants clockwise (increasing angle)
187  if( start_angle > end_angle )
188  std::swap( start_angle, end_angle );
189 
190  int quad_angle_start = std::ceil( start_angle / 90.0 );
191  int quad_angle_end = std::floor( end_angle / 90.0 );
192 
193  // count through quadrants included in arc
194  for( int quad_angle = quad_angle_start; quad_angle <= quad_angle_end; ++quad_angle )
195  {
196  const int radius = GetRadius();
197  VECTOR2I quad_pt = m_pc;
198 
199  switch( quad_angle % 4 )
200  {
201  case 0: quad_pt += { radius, 0 }; break;
202  case 1:
203  case -3: quad_pt += { 0, radius }; break;
204  case 2:
205  case -2: quad_pt += { -radius, 0 }; break;
206  case 3:
207  case -1: quad_pt += { 0, -radius }; break;
208  default: assert( false );
209  }
210 
211  points.push_back( quad_pt );
212  }
213 
214  m_bbox.Compute( points );
215 }
216 
217 
218 const BOX2I SHAPE_ARC::BBox( int aClearance ) const
219 {
220  BOX2I bbox( m_bbox );
221 
222  if( aClearance != 0 )
223  bbox.Inflate( aClearance );
224 
225  return bbox;
226 }
227 
228 
229 bool SHAPE_ARC::Collide( const VECTOR2I& aP, int aClearance ) const
230 {
231  int minDist = aClearance + m_width / 2;
232  auto bbox = BBox( minDist );
233 
234  if( !bbox.Contains( aP ) )
235  return false;
236 
237  auto dist = ( aP - GetCenter() ).SquaredEuclideanNorm();
238 
239  return dist <= ( GetRadius() + minDist ) && dist >= ( GetRadius() - minDist );
240 }
241 
242 
244 {
245  VECTOR2D d( m_p0 - m_pc );
246 
247  auto ang = 180.0 / M_PI * atan2( d.y, d.x );
248 
249  return ang;
250 }
251 
253 {
254  double a = GetStartAngle() + m_centralAngle;
255 
256  if( a < 0.0 )
257  a += 360.0;
258  else if ( a >= 360.0 )
259  a -= 360.0;
260 
261  return a;
262 }
263 
265 {
266  return m_centralAngle;
267 }
268 
270 {
271  return (m_p0 - m_pc).EuclideanNorm();
272 }
273 
274 const SHAPE_LINE_CHAIN SHAPE_ARC::ConvertToPolyline( double aAccuracy ) const
275 {
276  SHAPE_LINE_CHAIN rv;
277  double r = GetRadius();
278  double sa = GetStartAngle();
279  auto c = GetCenter();
280  int n;
281 
282  if( r == 0.0 )
283  {
284  n = 0;
285  }
286  else
287  {
288  n = GetArcToSegmentCount( r, aAccuracy, m_centralAngle );
289  }
290 
291  for( int i = 0; i <= n ; i++ )
292  {
293  double a = sa;
294 
295  if( n != 0 )
296  a += m_centralAngle * (double) i / (double) n;
297 
298  double x = c.x + r * cos( a * M_PI / 180.0 );
299  double y = c.y + r * sin( a * M_PI / 180.0 );
300 
301  rv.Append( (int) x, (int) y );
302  }
303 
304  return rv;
305 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
static const int dist[10][10]
Definition: ar_matrix.cpp:326
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:90
double GetStartAngle() const
Definition: shape_arc.cpp:243
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
int GetRadius() const
Definition: shape_arc.cpp:269
VECTOR2< double > VECTOR2D
Definition: vector2d.h:593
bool Collide(const SEG &aSeg, int aClearance=0) const override
Function Collide()
Definition: shape_arc.cpp:40
VECTOR2I m_p0
Definition: shape_arc.h:190
const VECTOR2I & GetCenter() const
Definition: shape_arc.h:77
const VECTOR2I GetP1() const
Definition: shape_arc.cpp:149
a few functions useful in geometry calculations.
const VECTOR2I GetArcMid() const
Definition: shape_arc.cpp:162
double GetEndAngle() const
Definition: shape_arc.cpp:252
void update_bbox()
Definition: shape_arc.cpp:175
Definition: seg.h:39
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:301
VECTOR2< T > Rotate(double aAngle) const
Function Rotate rotates the vector by a given angle.
Definition: vector2d.h:377
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:47
double GetCentralAngle() const
Definition: shape_arc.cpp:264
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:61
VECTOR2I m_pc
Definition: shape_arc.h:190
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_arc.cpp:218
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:274
int m_width
Definition: shape_arc.h:193
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
BOX2I m_bbox
Definition: shape_arc.h:194
double m_centralAngle
Definition: shape_arc.h:191
VECTOR2I B
Definition: seg.h:48