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  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
25 #include <assert.h> // for assert
26 #include <math.h> // for cos, sin, M_PI, atan2, ceil
27 #include <type_traits> // for swap
28 #include <vector>
29 
31 #include <geometry/seg.h> // for SEG
32 #include <geometry/shape_arc.h>
34 #include <math/box2.h> // for BOX2I
35 #include <math/vector2d.h> // for VECTOR2I, VECTOR2D, VECTOR2
36 
37 
38 bool SHAPE_ARC::Collide( const SEG& aSeg, int aClearance ) const
39 {
40  int minDist = aClearance + m_width / 2;
41  auto centerDist = aSeg.Distance( m_pc );
42  auto p1 = GetP1();
43 
44  if( centerDist < minDist )
45  return true;
46 
47  auto ab = (aSeg.B - aSeg.A );
48  auto ac = ( m_pc - aSeg.A );
49 
50  auto lenAbSq = ab.SquaredEuclideanNorm();
51 
52  auto lambda = (double) ac.Dot( ab ) / (double) lenAbSq;
53 
54 
55  if( lambda >= 0.0 && lambda <= 1.0 )
56  {
57  VECTOR2I p;
58 
59  p.x = (double) aSeg.A.x * lambda + (double) aSeg.B.x * (1.0 - lambda);
60  p.y = (double) aSeg.A.y * lambda + (double) aSeg.B.y * (1.0 - lambda);
61 
62  auto p0pdist = ( m_p0 - p ).EuclideanNorm();
63 
64  if( p0pdist < minDist )
65  return true;
66 
67  auto p1pdist = ( p1 - p ).EuclideanNorm();
68 
69  if( p1pdist < minDist )
70  return true;
71  }
72 
73  auto p0dist = aSeg.Distance( m_p0 );
74 
75  if( p0dist > minDist )
76  return true;
77 
78  auto p1dist = aSeg.Distance( p1 );
79 
80  if( p1dist > minDist )
81  return false;
82 
83 
84  return true;
85 }
86 
87 #if 0
88 bool SHAPE_ARC::ConstructFromCorners( VECTOR2I aP0, VECTOR2I aP1, double aCenterAngle )
89 {
90  VECTOR2D mid = ( VECTOR2D( aP0 ) + VECTOR2D( aP1 ) ) * 0.5;
91  VECTOR2D chord = VECTOR2D( aP1 ) - VECTOR2D( aP0 );
92  double c = (aP1 - aP0).EuclideanNorm() / 2;
93  VECTOR2D d = chord.Rotate( M_PI / 2.0 ).Resize( c );
94 
95  m_pc = mid + d * ( 1.0 / tan( aCenterAngle / 2.0 * M_PI / 180.0 ) );
96  m_p0 = aP0;
97  m_p1 = aP1;
98 
99  return true;
100 }
101 
102 bool SHAPE_ARC::ConstructFromCornerAndAngles( VECTOR2I aP0,
103  double aStartAngle,
104  double aCenterAngle,
105  double aRadius )
106 {
107  m_p0 = aP0;
108  auto d1 = VECTOR2D( 1.0, 0.0 ).Rotate( aStartAngle * M_PI / 180.0 ) * aRadius;
109  auto d2 =
110  VECTOR2D( 1.0, 0.0 ).Rotate( (aStartAngle + aCenterAngle) * M_PI / 180.0 ) * aRadius;
111 
112  m_pc = m_p0 - (VECTOR2I) d1;
113  m_p1 = m_pc + (VECTOR2I) d2;
114 
115  if( aCenterAngle < 0 )
116  std::swap( m_p0, m_p1 );
117 
118  return true;
119 }
120 
121 bool SHAPE_ARC::ConstructFromCenterAndAngles( VECTOR2I aCenter, double aRadius, double aStartAngle, double aCenterAngle )
122 {
123  double ea = aStartAngle + aCenterAngle;
124 
125  m_fullCircle = false;
126  m_pc = aCenter;
127  m_p0.x = (int) ( (double) aCenter.x + aRadius * cos( aStartAngle * M_PI / 180.0 ) );
128  m_p0.y = (int) ( (double) aCenter.y + aRadius * sin( aStartAngle * M_PI / 180.0 ) );
129  m_p1.x = (int) ( (double) aCenter.x + aRadius * cos( ea * M_PI / 180.0 ) );
130  m_p1.y = (int) ( (double) aCenter.y + aRadius * sin( ea * M_PI / 180.0 ) );
131 
132  if( aCenterAngle == 360.0 )
133  {
134  m_fullCircle = true;
135  return true;
136  }
137  else if ( aCenterAngle < 0.0 )
138  {
139  std::swap(m_p0, m_p1);
140  }
141 
142  return true;
143 }
144 #endif
145 
146 
148 {
149  VECTOR2D rvec = m_p0 - m_pc;
150  auto ca = m_centralAngle * M_PI / 180.0;
151  VECTOR2I p1;
152 
153  p1.x = (int) ( m_pc.x + rvec.x * cos( ca ) - rvec.y * sin( ca ) );
154  p1.y = (int) ( m_pc.y + rvec.x * sin( ca ) + rvec.y * cos( ca ) );
155 
156  return p1;
157 }
158 
159 
160 const BOX2I SHAPE_ARC::BBox( int aClearance ) const
161 {
162  BOX2I bbox;
163  std::vector<VECTOR2I> points;
164  // Put start and end points in the point list
165  points.push_back( m_p0 );
166  points.push_back( GetP1() );
167  // points.push_back( m_pc ); the center point is not necessary in the BBox
168 
169  double start_angle = GetStartAngle();
170  double end_angle = start_angle + GetCentralAngle();
171 
172  // we always count quadrants clockwise (increasing angle)
173  if( start_angle > end_angle )
174  std::swap( start_angle, end_angle );
175 
176  int quad_angle_start = std::ceil( start_angle / 90.0 );
177  int quad_angle_end = std::floor( end_angle / 90.0 );
178 
179  // count through quadrants included in arc
180  for( int quad_angle = quad_angle_start; quad_angle <= quad_angle_end; ++quad_angle )
181  {
182  const int radius = GetRadius();
183  VECTOR2I quad_pt = m_pc;
184 
185  switch( quad_angle % 4 )
186  {
187  case 0: quad_pt += { radius, 0 }; break;
188  case 1:
189  case -3: quad_pt += { 0, radius }; break;
190  case 2:
191  case -2: quad_pt += { -radius, 0 }; break;
192  case 3:
193  case -1: quad_pt += { 0, -radius }; break;
194  default: assert( false );
195  }
196 
197  points.push_back( quad_pt );
198  }
199 
200  bbox.Compute( points );
201 
202  if( aClearance != 0 )
203  bbox.Inflate( aClearance );
204 
205  return bbox;
206 }
207 
208 
209 bool SHAPE_ARC::Collide( const VECTOR2I& aP, int aClearance ) const
210 {
211  assert( false );
212  return false;
213 }
214 
215 
217 {
218  VECTOR2D d( m_p0 - m_pc );
219 
220  auto ang = 180.0 / M_PI * atan2( d.y, d.x );
221 
222  return ang;
223 }
224 
226 {
227  double a = GetStartAngle() + m_centralAngle;
228 
229  if( a < 0.0 )
230  a += 360.0;
231  else if ( a >= 360.0 )
232  a -= 360.0;
233 
234  return a;
235 }
236 
238 {
239  return m_centralAngle;
240 }
241 
243 {
244  return (m_p0 - m_pc).EuclideanNorm();
245 }
246 
247 const SHAPE_LINE_CHAIN SHAPE_ARC::ConvertToPolyline( double aAccuracy ) const
248 {
249  SHAPE_LINE_CHAIN rv;
250  double r = GetRadius();
251  double sa = GetStartAngle();
252  auto c = GetCenter();
253  int n;
254 
255  if( r == 0.0 )
256  {
257  n = 0;
258  }
259  else
260  {
261  n = GetArcToSegmentCount( r, aAccuracy, m_centralAngle );
262  }
263 
264  for( int i = 0; i <= n ; i++ )
265  {
266  double a = sa;
267 
268  if( n != 0 )
269  a += m_centralAngle * (double) i / (double) n;
270 
271  double x = c.x + r * cos( a * M_PI / 180.0 );
272  double y = c.y + r * sin( a * M_PI / 180.0 );
273 
274  rv.Append( (int) x, (int) y );
275  }
276 
277  return rv;
278 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:123
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:202
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:216
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:242
VECTOR2< double > VECTOR2D
Definition: vector2d.h:593
bool Collide(const SEG &aSeg, int aClearance=0) const override
Function Collide()
Definition: shape_arc.cpp:38
VECTOR2I m_p0
Definition: shape_arc.h:145
const VECTOR2I & GetCenter() const
Definition: shape_arc.h:73
const VECTOR2I GetP1() const
Definition: shape_arc.cpp:147
a few functions useful in geometry calculations.
double GetEndAngle() const
Definition: shape_arc.cpp:225
Definition: seg.h:39
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
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:237
VECTOR2I m_pc
Definition: shape_arc.h:145
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_arc.cpp:160
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:247
int m_width
Definition: shape_arc.h:148
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
double m_centralAngle
Definition: shape_arc.h:146
VECTOR2I B
Definition: seg.h:48