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 
57 SHAPE_ARC::SHAPE_ARC( const SEG& aSegmentA, const SEG& aSegmentB, int aRadius, int aWidth )
58  : SHAPE( SH_ARC )
59 {
60  /*
61  * Construct an arc that is tangent to two segments with a given radius.
62  *
63  * p
64  * A
65  * A \
66  * / \
67  * / , * , \ segB
68  * /* *\
69  * segA / c \
70  * / B
71  * /
72  * /
73  * B
74  *
75  *
76  * segA is the fist segment (with its points A and B)
77  * segB is the second segment (with its points A and B)
78  * p is the point at which segA and segB would intersect if they were projected
79  * c is the centre of the arc to be constructed
80  * rad is the radius of the arc to be constructed
81  *
82  * We can create two vectors, betweeen point p and segA /segB
83  * pToA = p - segA.B //< note that segA.A would also be valid as it is colinear
84  * pToB = p - segB.B //< note that segB.A would also be valid as it is colinear
85  *
86  * Let the angle formed by segA and segB be called 'alpha':
87  * alpha = angle( pToA ) - angle( pToB )
88  *
89  * The distance PC can be computed as
90  * distPC = rad / abs( sin( alpha / 2 ) )
91  *
92  * The polar angle of the vector PC can be computed as:
93  * anglePC = angle( pToA ) + alpha / 2
94  *
95  * Therefore:
96  * C.x = P.x + distPC*cos( anglePC )
97  * C.y = P.y + distPC*sin( anglePC )
98  */
99 
100  OPT_VECTOR2I p = aSegmentA.Intersect( aSegmentB, true, true );
101 
102  if( !p || aSegmentA.Length() == 0 || aSegmentB.Length() == 0 )
103  {
104  // Catch bugs in debug
105  wxASSERT_MSG( false, "The input segments do not intersect or one is zero length." );
106 
107  // Make a 180 degree arc around aSegmentA in case we end up here in release
108  m_start = aSegmentA.A;
109  m_end = aSegmentA.B;
110  m_mid = m_start;
111 
112  VECTOR2I arcCenter = aSegmentA.Center();
113  RotatePoint( m_mid, arcCenter, 900.0 ); // mid point at 90 degrees
114  }
115  else
116  {
117  VECTOR2I pToA = aSegmentA.B - p.get();
118  VECTOR2I pToB = aSegmentB.B - p.get();
119 
120  if( pToA.EuclideanNorm() == 0 )
121  pToA = aSegmentA.A - p.get();
122 
123  if( pToB.EuclideanNorm() == 0 )
124  pToB = aSegmentB.A - p.get();
125 
126  double pToAangle = ArcTangente( pToA.y, pToA.x );
127  double pToBangle = ArcTangente( pToB.y, pToB.x );
128 
129  double alpha = NormalizeAngle180( pToAangle - pToBangle );
130 
131  double distPC = (double) aRadius / abs( sin( DECIDEG2RAD( alpha / 2 ) ) );
132  double angPC = pToAangle - alpha / 2;
133 
134  VECTOR2I arcCenter;
135 
136  arcCenter.x = p.get().x + KiROUND( distPC * cos( DECIDEG2RAD( angPC ) ) );
137  arcCenter.y = p.get().y + KiROUND( distPC * sin( DECIDEG2RAD( angPC ) ) );
138 
139  // The end points of the arc are the orthogonal projected lines from the line segments
140  // to the center of the arc
141  m_start = aSegmentA.LineProject( arcCenter );
142  m_end = aSegmentB.LineProject( arcCenter );
143 
144  //The mid point is rotated start point around center, half the angle of the arc.
145  VECTOR2I startVector = m_start - arcCenter;
146  VECTOR2I endVector = m_end - arcCenter;
147 
148  double startAngle = ArcTangente( startVector.y, startVector.x );
149  double endAngle = ArcTangente( endVector.y, endVector.x );
150 
151  double midPointRotAngle = NormalizeAngle180( startAngle - endAngle ) / 2;
152  m_mid = m_start;
153  RotatePoint( m_mid, arcCenter, midPointRotAngle );
154  }
155 
156  update_bbox();
157 }
158 
159 
161  : SHAPE( SH_ARC )
162 {
163  m_start = aOther.m_start;
164  m_end = aOther.m_end;
165  m_mid = aOther.m_mid;
166  m_width = aOther.m_width;
167  m_bbox = aOther.m_bbox;
168 }
169 
170 
171 bool SHAPE_ARC::Collide( const SEG& aSeg, int aClearance, int* aActual, VECTOR2I* aLocation ) const
172 {
173  int minDist = aClearance + m_width / 2;
174  VECTOR2I center = GetCenter();
175  ecoord dist_sq;
176  ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
177  VECTOR2I nearest;
178 
179  VECTOR2I ab = ( aSeg.B - aSeg.A );
180  VECTOR2I ac = ( center - aSeg.A );
181 
182  ecoord lenAbSq = ab.SquaredEuclideanNorm();
183  double lambda = (double) ac.Dot( ab ) / (double) lenAbSq;
184 
185  if( lambda >= 0.0 && lambda <= 1.0 )
186  {
187  VECTOR2I p;
188 
189  p.x = (double) aSeg.A.x * lambda + (double) aSeg.B.x * (1.0 - lambda);
190  p.y = (double) aSeg.A.y * lambda + (double) aSeg.B.y * (1.0 - lambda);
191 
192  dist_sq = ( m_start - p ).SquaredEuclideanNorm();
193 
194  if( dist_sq < closest_dist_sq )
195  {
196  closest_dist_sq = dist_sq;
197  nearest = p;
198  }
199 
200  dist_sq = ( m_end - p ).SquaredEuclideanNorm();
201 
202  if( dist_sq < closest_dist_sq )
203  {
204  closest_dist_sq = dist_sq;
205  nearest = p;
206  }
207  }
208 
209  dist_sq = aSeg.SquaredDistance( m_start );
210 
211  if( dist_sq < closest_dist_sq )
212  {
213  closest_dist_sq = dist_sq;
214  nearest = m_start;
215  }
216 
217  dist_sq = aSeg.SquaredDistance( m_end );
218 
219  if( dist_sq < closest_dist_sq )
220  {
221  closest_dist_sq = dist_sq;
222  nearest = m_end;
223  }
224 
225  if( closest_dist_sq == 0 || closest_dist_sq < SEG::Square( minDist ) )
226  {
227  if( aLocation )
228  *aLocation = nearest;
229 
230  if( aActual )
231  *aActual = std::max( 0, (int) sqrt( closest_dist_sq ) - m_width / 2 );
232 
233  return true;
234  }
235 
236  return false;
237 }
238 
239 
241 {
242  std::vector<VECTOR2I> points;
243  // Put start and end points in the point list
244  points.push_back( m_start );
245  points.push_back( m_end );
246 
247  double start_angle = GetStartAngle();
248  double end_angle = start_angle + GetCentralAngle();
249 
250  // we always count quadrants clockwise (increasing angle)
251  if( start_angle > end_angle )
252  std::swap( start_angle, end_angle );
253 
254  int quad_angle_start = std::ceil( start_angle / 90.0 );
255  int quad_angle_end = std::floor( end_angle / 90.0 );
256 
257  // count through quadrants included in arc
258  for( int quad_angle = quad_angle_start; quad_angle <= quad_angle_end; ++quad_angle )
259  {
260  const int radius = KiROUND( GetRadius() );
261  VECTOR2I quad_pt = GetCenter();
262 
263  switch( quad_angle % 4 )
264  {
265  case 0: quad_pt += { radius, 0 }; break;
266  case 1:
267  case -3: quad_pt += { 0, radius }; break;
268  case 2:
269  case -2: quad_pt += { -radius, 0 }; break;
270  case 3:
271  case -1: quad_pt += { 0, -radius }; break;
272  default: assert( false );
273  }
274 
275  points.push_back( quad_pt );
276  }
277 
278  m_bbox.Compute( points );
279 }
280 
281 
282 const BOX2I SHAPE_ARC::BBox( int aClearance ) const
283 {
284  BOX2I bbox( m_bbox );
285 
286  if( aClearance != 0 )
287  bbox.Inflate( aClearance );
288 
289  return bbox;
290 }
291 
292 
293 bool SHAPE_ARC::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
294  VECTOR2I* aLocation ) const
295 {
296  int minDist = aClearance + m_width / 2;
297  auto bbox = BBox( minDist );
298 
299  if( !bbox.Contains( aP ) )
300  return false;
301 
302  ecoord min_dist_sq = SEG::Square( minDist );
303  ecoord r_sq = SEG::Square( GetRadius() );
304 
305  ecoord dist_sq = ( aP - GetCenter() ).SquaredEuclideanNorm();
306  ecoord dist_to_edge_sq = abs( dist_sq - r_sq );
307 
308  if( dist_to_edge_sq == 0 || dist_to_edge_sq < min_dist_sq )
309  {
310  if( aLocation )
311  *aLocation = ( aP + GetCenter() ) / 2;
312 
313  if( aActual )
314  *aActual = std::max( 0, (int) sqrt( dist_to_edge_sq ) - m_width / 2 );
315 
316  return true;
317  }
318 
319  return false;
320 }
321 
322 
324 {
325  VECTOR2D d( m_start - GetCenter() );
326 
327  auto ang = 180.0 / M_PI * atan2( d.y, d.x );
328 
329  return NormalizeAngleDegrees( ang, 0.0, 360.0 );
330 }
331 
332 
334 {
335  VECTOR2D d( m_end - GetCenter() );
336 
337  auto ang = 180.0 / M_PI * atan2( d.y, d.x );
338 
339  return NormalizeAngleDegrees( ang, 0.0, 360.0 );
340 }
341 
342 
344 {
345  return GetArcCenter( m_start, m_mid, m_end );
346 }
347 
348 
350 {
351  VECTOR2I center = GetCenter();
352  VECTOR2I p0 = m_start - center;
353  VECTOR2I p1 = m_mid - center;
354  VECTOR2I p2 = m_end - center;
355  double angle1 = ArcTangente( p1.y, p1.x ) - ArcTangente( p0.y, p0.x );
356  double angle2 = ArcTangente( p2.y, p2.x ) - ArcTangente( p1.y, p1.x );
357 
358  return ( NormalizeAngle180( angle1 ) + NormalizeAngle180( angle2 ) ) / 10.0;
359 }
360 
361 
362 double SHAPE_ARC::GetRadius() const
363 {
364  return ( m_start - GetCenter() ).EuclideanNorm();
365 }
366 
367 
368 const SHAPE_LINE_CHAIN SHAPE_ARC::ConvertToPolyline( double aAccuracy ) const
369 {
370  SHAPE_LINE_CHAIN rv;
371  double r = GetRadius();
372  double sa = GetStartAngle();
373  auto c = GetCenter();
374  double ca = GetCentralAngle();
375 
376  int n;
377 
378  if( r == 0.0 )
379  {
380  n = 0;
381  }
382  else
383  {
384  n = GetArcToSegmentCount( r, aAccuracy, ca );
385  }
386 
387  for( int i = 0; i <= n ; i++ )
388  {
389  double a = sa;
390 
391  if( n != 0 )
392  a += ( ca * i ) / n;
393 
394  double x = c.x + r * cos( a * M_PI / 180.0 );
395  double y = c.y + r * sin( a * M_PI / 180.0 );
396 
397  rv.Append( KiROUND( x ), KiROUND( y ) );
398  }
399 
400  return rv;
401 }
402 
403 
404 void SHAPE_ARC::Move( const VECTOR2I& aVector )
405 {
406  m_start += aVector;
407  m_end += aVector;
408  m_mid += aVector;
409  update_bbox();
410 }
411 
412 
413 void SHAPE_ARC::Rotate( double aAngle, const VECTOR2I& aCenter )
414 {
415  m_start -= aCenter;
416  m_end -= aCenter;
417  m_mid -= aCenter;
418 
419  m_start = m_start.Rotate( aAngle );
420  m_end = m_end.Rotate( aAngle );
421  m_mid = m_mid.Rotate( aAngle );
422 
423  m_start += aCenter;
424  m_end += aCenter;
425  m_mid += aCenter;
426 
427  update_bbox();
428 }
429 
430 
431 void SHAPE_ARC::Mirror( bool aX, bool aY, const VECTOR2I& aVector )
432 {
433  if( aX )
434  {
435  m_start.x = -m_start.x + 2 * aVector.x;
436  m_end.x = -m_end.x + 2 * aVector.x;
437  m_mid.x = -m_mid.x + 2 * aVector.x;
438  }
439 
440  if( aY )
441  {
442  m_start.y = -m_start.y + 2 * aVector.y;
443  m_end.y = -m_end.y + 2 * aVector.y;
444  m_mid.y = -m_mid.y + 2 * aVector.y;
445  }
446 
447  update_bbox();
448 }
int Length() const
Function Length()
Definition: seg.h:319
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aVector={ 0, 0 })
Definition: shape_arc.cpp:431
void Rotate(double aAngle, const VECTOR2I &aCenter) override
Function Rotate rotates the arc by a given angle about a point.
Definition: shape_arc.cpp:413
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
Definition: shape_arc.cpp:171
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:104
double GetRadius() const
Definition: shape_arc.cpp:362
VECTOR2I m_end
Definition: shape_arc.h:159
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:323
VECTOR2I Center() const
Returns the center point of the line
Definition: seg.h:350
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:208
static SEG::ecoord Square(int a)
Definition: seg.h:116
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:365
VECTOR2I m_mid
Definition: shape_arc.h:158
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:362
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:37
compound shape, consisting of multiple simple shapes
Definition: shape.h:50
a few functions useful in geometry calculations.
SHAPE.
Definition: shape.h:122
double GetEndAngle() const
Definition: shape_arc.cpp:333
void update_bbox()
Definition: shape_arc.cpp:240
Definition: seg.h:39
void Move(const VECTOR2I &aVector) override
Definition: shape_arc.cpp:404
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:125
SHAPE_LINE_CHAIN.
VECTOR2I m_start
Definition: shape_arc.h:157
VECTOR2I A
Definition: seg.h:47
double GetCentralAngle() const
Definition: shape_arc.cpp:349
double DECIDEG2RAD(double deg)
Definition: trigo.h:224
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:42
double NormalizeAngleDegrees(double Angle, double aMin, double aMax)
Normalize angle to be aMin < angle <= aMax angle is in degrees.
Definition: trigo.h:312
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_arc.cpp:282
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:299
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:430
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:368
int m_width
Definition: shape_arc.h:161
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
BOX2I m_bbox
Definition: shape_arc.h:162
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:343
VECTOR2I B
Definition: seg.h:48