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  m_width = aWidth;
61 
62  /*
63  * Construct an arc that is tangent to two segments with a given radius.
64  *
65  * p
66  * A
67  * A \
68  * / \
69  * / . . \ segB
70  * /. .\
71  * segA / c \
72  * / B
73  * /
74  * /
75  * B
76  *
77  *
78  * segA is the fist segment (with its points A and B)
79  * segB is the second segment (with its points A and B)
80  * p is the point at which segA and segB would intersect if they were projected
81  * c is the centre of the arc to be constructed
82  * rad is the radius of the arc to be constructed
83  *
84  * We can create two vectors, betweeen point p and segA /segB
85  * pToA = p - segA.B //< note that segA.A would also be valid as it is colinear
86  * pToB = p - segB.B //< note that segB.A would also be valid as it is colinear
87  *
88  * Let the angle formed by segA and segB be called 'alpha':
89  * alpha = angle( pToA ) - angle( pToB )
90  *
91  * The distance PC can be computed as
92  * distPC = rad / abs( sin( alpha / 2 ) )
93  *
94  * The polar angle of the vector PC can be computed as:
95  * anglePC = angle( pToA ) + alpha / 2
96  *
97  * Therefore:
98  * C.x = P.x + distPC*cos( anglePC )
99  * C.y = P.y + distPC*sin( anglePC )
100  */
101 
102  OPT_VECTOR2I p = aSegmentA.Intersect( aSegmentB, true, true );
103 
104  if( !p || aSegmentA.Length() == 0 || aSegmentB.Length() == 0 )
105  {
106  // Catch bugs in debug
107  wxASSERT_MSG( false, "The input segments do not intersect or one is zero length." );
108 
109  // Make a 180 degree arc around aSegmentA in case we end up here in release
110  m_start = aSegmentA.A;
111  m_end = aSegmentA.B;
112  m_mid = m_start;
113 
114  VECTOR2I arcCenter = aSegmentA.Center();
115  RotatePoint( m_mid, arcCenter, 900.0 ); // mid point at 90 degrees
116  }
117  else
118  {
119  VECTOR2I pToA = aSegmentA.B - p.get();
120  VECTOR2I pToB = aSegmentB.B - p.get();
121 
122  if( pToA.EuclideanNorm() == 0 )
123  pToA = aSegmentA.A - p.get();
124 
125  if( pToB.EuclideanNorm() == 0 )
126  pToB = aSegmentB.A - p.get();
127 
128  double pToAangle = ArcTangente( pToA.y, pToA.x );
129  double pToBangle = ArcTangente( pToB.y, pToB.x );
130 
131  double alpha = NormalizeAngle180( pToAangle - pToBangle );
132 
133  double distPC = (double) aRadius / abs( sin( DECIDEG2RAD( alpha / 2 ) ) );
134  double angPC = pToAangle - alpha / 2;
135 
136  VECTOR2I arcCenter;
137 
138  arcCenter.x = p.get().x + KiROUND( distPC * cos( DECIDEG2RAD( angPC ) ) );
139  arcCenter.y = p.get().y + KiROUND( distPC * sin( DECIDEG2RAD( angPC ) ) );
140 
141  // The end points of the arc are the orthogonal projected lines from the line segments
142  // to the center of the arc
143  m_start = aSegmentA.LineProject( arcCenter );
144  m_end = aSegmentB.LineProject( arcCenter );
145 
146  //The mid point is rotated start point around center, half the angle of the arc.
147  VECTOR2I startVector = m_start - arcCenter;
148  VECTOR2I endVector = m_end - arcCenter;
149 
150  double startAngle = ArcTangente( startVector.y, startVector.x );
151  double endAngle = ArcTangente( endVector.y, endVector.x );
152 
153  double midPointRotAngle = NormalizeAngle180( startAngle - endAngle ) / 2;
154  m_mid = m_start;
155  RotatePoint( m_mid, arcCenter, midPointRotAngle );
156  }
157 
158  update_bbox();
159 }
160 
161 
163  : SHAPE( SH_ARC )
164 {
165  m_start = aOther.m_start;
166  m_end = aOther.m_end;
167  m_mid = aOther.m_mid;
168  m_width = aOther.m_width;
169  m_bbox = aOther.m_bbox;
170 }
171 
172 
174  double aAngle, double aWidth )
175 {
176  m_start = aStart;
177  m_mid = aStart;
178  m_end = aEnd;
179  m_width = aWidth;
180 
181  VECTOR2I center( GetArcCenter( aStart, aEnd, aAngle ) );
182 
183  RotatePoint( m_mid, center, -aAngle * 10.0 / 2.0 );
184 
185  update_bbox();
186 
187  return *this;
188 }
189 
190 
191 bool SHAPE_ARC::Collide( const SEG& aSeg, int aClearance, int* aActual, VECTOR2I* aLocation ) const
192 {
193  if( aSeg.A == aSeg.B )
194  return Collide( aSeg.A, aClearance, aActual, aLocation );
195 
196  int minDist = aClearance + m_width / 2;
197  VECTOR2I center = GetCenter();
198  ecoord dist_sq;
199  ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
200  VECTOR2I nearest;
201 
202  VECTOR2I ab = ( aSeg.B - aSeg.A );
203  VECTOR2I ac = ( center - aSeg.A );
204 
205  ecoord lenAbSq = ab.SquaredEuclideanNorm();
206  double lambda = (double) ac.Dot( ab ) / (double) lenAbSq;
207 
208  if( lambda >= 0.0 && lambda <= 1.0 )
209  {
210  VECTOR2I p;
211 
212  p.x = (double) aSeg.A.x * lambda + (double) aSeg.B.x * (1.0 - lambda);
213  p.y = (double) aSeg.A.y * lambda + (double) aSeg.B.y * (1.0 - lambda);
214 
215  dist_sq = ( m_start - p ).SquaredEuclideanNorm();
216 
217  if( dist_sq < closest_dist_sq )
218  {
219  closest_dist_sq = dist_sq;
220  nearest = p;
221  }
222 
223  dist_sq = ( m_end - p ).SquaredEuclideanNorm();
224 
225  if( dist_sq < closest_dist_sq )
226  {
227  closest_dist_sq = dist_sq;
228  nearest = p;
229  }
230  }
231 
232  dist_sq = aSeg.SquaredDistance( m_start );
233 
234  if( dist_sq < closest_dist_sq )
235  {
236  closest_dist_sq = dist_sq;
237  nearest = m_start;
238  }
239 
240  dist_sq = aSeg.SquaredDistance( m_end );
241 
242  if( dist_sq < closest_dist_sq )
243  {
244  closest_dist_sq = dist_sq;
245  nearest = m_end;
246  }
247 
248  if( closest_dist_sq == 0 || closest_dist_sq < SEG::Square( minDist ) )
249  {
250  if( aLocation )
251  *aLocation = nearest;
252 
253  if( aActual )
254  *aActual = std::max( 0, (int) sqrt( closest_dist_sq ) - m_width / 2 );
255 
256  return true;
257  }
258 
259  return false;
260 }
261 
262 
264 {
265  std::vector<VECTOR2I> points;
266  // Put start and end points in the point list
267  points.push_back( m_start );
268  points.push_back( m_end );
269 
270  double start_angle = GetStartAngle();
271  double end_angle = start_angle + GetCentralAngle();
272 
273  // we always count quadrants clockwise (increasing angle)
274  if( start_angle > end_angle )
275  std::swap( start_angle, end_angle );
276 
277  int quad_angle_start = std::ceil( start_angle / 90.0 );
278  int quad_angle_end = std::floor( end_angle / 90.0 );
279 
280  // count through quadrants included in arc
281  for( int quad_angle = quad_angle_start; quad_angle <= quad_angle_end; ++quad_angle )
282  {
283  const int radius = KiROUND( GetRadius() );
284  VECTOR2I quad_pt = GetCenter();
285 
286  switch( quad_angle % 4 )
287  {
288  case 0: quad_pt += { radius, 0 }; break;
289  case 1:
290  case -3: quad_pt += { 0, radius }; break;
291  case 2:
292  case -2: quad_pt += { -radius, 0 }; break;
293  case 3:
294  case -1: quad_pt += { 0, -radius }; break;
295  default: assert( false );
296  }
297 
298  points.push_back( quad_pt );
299  }
300 
301  m_bbox.Compute( points );
302 }
303 
304 
305 const BOX2I SHAPE_ARC::BBox( int aClearance ) const
306 {
307  BOX2I bbox( m_bbox );
308 
309  if( aClearance != 0 )
310  bbox.Inflate( aClearance );
311 
312  return bbox;
313 }
314 
315 
316 bool SHAPE_ARC::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
317  VECTOR2I* aLocation ) const
318 {
319  int minDist = aClearance + m_width / 2;
320  auto bbox = BBox( minDist );
321 
322  // Fast check using bounding box:
323  if( !bbox.Contains( aP ) )
324  return false;
325 
326  VECTOR2I center = GetCenter();
327  VECTOR2I vec = aP - center;
328 
329  int dist = abs( vec.EuclideanNorm() - GetRadius() );
330 
331  // If not a 360 degree arc, need to use arc angles to decide if point collides
332  if( m_start != m_end )
333  {
334  bool ccw = GetCentralAngle() > 0.0;
335  double rotatedVecAngle = NormalizeAngleDegreesPos( NormalizeAngleDegreesPos( RAD2DEG( vec.Angle() ) )
336  - GetStartAngle() );
337  double rotatedEndAngle = NormalizeAngleDegreesPos( GetEndAngle() - GetStartAngle() );
338 
339  if( ( ccw && rotatedVecAngle > rotatedEndAngle )
340  || ( !ccw && rotatedVecAngle < rotatedEndAngle ) )
341  {
342  int distStartpt = ( aP - m_start ).EuclideanNorm();
343  int distEndpt = ( aP - m_end ).EuclideanNorm();
344  dist = std::min( distStartpt, distEndpt );
345  }
346  }
347 
348  if( dist <= minDist )
349  {
350  if( aLocation )
351  *aLocation = ( aP + GetCenter() ) / 2;
352 
353  if( aActual )
354  *aActual = std::max( 0, dist - m_width / 2 );
355 
356  return true;
357  }
358 
359  return false;
360 }
361 
362 
364 {
365  VECTOR2D d( m_start - GetCenter() );
366 
367  auto ang = 180.0 / M_PI * atan2( d.y, d.x );
368 
369  return NormalizeAngleDegrees( ang, 0.0, 360.0 );
370 }
371 
372 
374 {
375  VECTOR2D d( m_end - GetCenter() );
376 
377  auto ang = 180.0 / M_PI * atan2( d.y, d.x );
378 
379  return NormalizeAngleDegrees( ang, 0.0, 360.0 );
380 }
381 
382 
384 {
385  return GetArcCenter( m_start, m_mid, m_end );
386 }
387 
388 
389 double SHAPE_ARC::GetLength() const
390 {
391  double radius = GetRadius();
392  double includedAngle = std::abs( GetCentralAngle() );
393 
394  return radius * M_PI * includedAngle / 180.0;
395 }
396 
397 
399 {
400  VECTOR2I center = GetCenter();
401  VECTOR2I p0 = m_start - center;
402  VECTOR2I p1 = m_mid - center;
403  VECTOR2I p2 = m_end - center;
404  double angle1 = ArcTangente( p1.y, p1.x ) - ArcTangente( p0.y, p0.x );
405  double angle2 = ArcTangente( p2.y, p2.x ) - ArcTangente( p1.y, p1.x );
406 
407  return ( NormalizeAngle180( angle1 ) + NormalizeAngle180( angle2 ) ) / 10.0;
408 }
409 
410 
411 double SHAPE_ARC::GetRadius() const
412 {
413  return ( m_start - GetCenter() ).EuclideanNorm();
414 }
415 
416 
417 const SHAPE_LINE_CHAIN SHAPE_ARC::ConvertToPolyline( double aAccuracy ) const
418 {
419  SHAPE_LINE_CHAIN rv;
420  double r = GetRadius();
421  double sa = GetStartAngle();
422  auto c = GetCenter();
423  double ca = GetCentralAngle();
424 
425  int n;
426 
427  if( r < aAccuracy )
428  n = 0;
429  else
430  n = GetArcToSegmentCount( r, aAccuracy, ca );
431 
432  // Split the error on either side of the arc. Since we want the start and end points
433  // to be exactly on the arc, the first and last segments need to be shorter to stay within
434  // the error band (since segments normally start 1/2 the error band outside the arc).
435  r += aAccuracy / 2;
436  n = n * 2;
437 
438  rv.Append( m_start );
439 
440  for( int i = 1; i < n ; i += 2 )
441  {
442  double a = sa;
443 
444  if( n != 0 )
445  a += ( ca * i ) / n;
446 
447  double x = c.x + r * cos( a * M_PI / 180.0 );
448  double y = c.y + r * sin( a * M_PI / 180.0 );
449 
450  rv.Append( KiROUND( x ), KiROUND( y ) );
451  }
452 
453  rv.Append( m_end );
454 
455  return rv;
456 }
457 
458 
459 void SHAPE_ARC::Move( const VECTOR2I& aVector )
460 {
461  m_start += aVector;
462  m_end += aVector;
463  m_mid += aVector;
464  update_bbox();
465 }
466 
467 
468 void SHAPE_ARC::Rotate( double aAngle, const VECTOR2I& aCenter )
469 {
470  m_start -= aCenter;
471  m_end -= aCenter;
472  m_mid -= aCenter;
473 
474  m_start = m_start.Rotate( aAngle );
475  m_end = m_end.Rotate( aAngle );
476  m_mid = m_mid.Rotate( aAngle );
477 
478  m_start += aCenter;
479  m_end += aCenter;
480  m_mid += aCenter;
481 
482  update_bbox();
483 }
484 
485 
486 void SHAPE_ARC::Mirror( bool aX, bool aY, const VECTOR2I& aVector )
487 {
488  if( aX )
489  {
490  m_start.x = -m_start.x + 2 * aVector.x;
491  m_end.x = -m_end.x + 2 * aVector.x;
492  m_mid.x = -m_mid.x + 2 * aVector.x;
493  }
494 
495  if( aY )
496  {
497  m_start.y = -m_start.y + 2 * aVector.y;
498  m_end.y = -m_end.y + 2 * aVector.y;
499  m_mid.y = -m_mid.y + 2 * aVector.y;
500  }
501 
502  update_bbox();
503 }
504 
505 
506 void SHAPE_ARC::Mirror( const SEG& axis )
507 {
508  m_start = axis.ReflectPoint( m_start );
509  m_end = axis.ReflectPoint( m_end );
510  m_mid = axis.ReflectPoint( m_mid );
511 
512  update_bbox();
513 }
514 
515 
517 {
518  std::swap( m_start, m_end );
519 }
520 
521 
523 {
524  return SHAPE_ARC( m_end, m_mid, m_start, m_width );
525 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
int Length() const
Return the length (this).
Definition: seg.h:355
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aVector={ 0, 0 })
Definition: shape_arc.cpp:486
void Rotate(double aAngle, const VECTOR2I &aCenter) override
Function Rotate rotates the arc by a given angle about a point.
Definition: shape_arc.cpp:468
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the segment aSeg than aClearance,...
Definition: shape_arc.cpp:191
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
Definition: seg.cpp:119
double GetRadius() const
Definition: shape_arc.cpp:411
VECTOR2I m_end
Definition: shape_arc.h:180
double RAD2DEG(double rad)
Definition: trigo.h:232
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.h:458
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
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:91
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:300
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:39
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: shape_arc.h:169
double GetStartAngle() const
Definition: shape_arc.cpp:363
VECTOR2I Center() const
Definition: seg.h:391
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:228
static SEG::ecoord Square(int a)
Definition: seg.h:123
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:376
VECTOR2I m_mid
Definition: shape_arc.h:179
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.h:404
double NormalizeAngleDegreesPos(double Angle)
Normalize angle to be in the 0.0 .
Definition: trigo.h:296
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:417
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
circular arc
Definition: shape.h:50
a few functions useful in geometry calculations.
An abstract shape on 2D plane.
Definition: shape.h:116
double Angle() const
Compute the angle of the vector.
Definition: vector2d.h:307
double GetEndAngle() const
Definition: shape_arc.cpp:373
void update_bbox()
Definition: shape_arc.cpp:263
void Reverse()
Definition: shape_arc.cpp:516
Definition: seg.h:41
void Move(const VECTOR2I &aVector) override
Definition: shape_arc.cpp:459
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
Rotate the vector by a given angle.
Definition: vector2d.h:371
extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:521
VECTOR2I::extended_type ecoord
Definition: shape.h:236
SHAPE_LINE_CHAIN.
VECTOR2I m_start
Definition: shape_arc.h:178
VECTOR2I A
Definition: seg.h:49
double GetCentralAngle() const
Definition: shape_arc.cpp:398
double DECIDEG2RAD(double deg)
Definition: trigo.h:235
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:39
double NormalizeAngleDegrees(double Angle, double aMin, double aMax)
Normalize angle to be aMin < angle <= aMax angle is in degrees.
Definition: trigo.h:323
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_arc.cpp:305
SHAPE_ARC Reversed() const
Definition: shape_arc.cpp:522
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
double ArcTangente(int dy, int dx)
Definition: trigo.cpp:182
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:450
double GetLength() const
Definition: shape_arc.cpp:389
int m_width
Definition: shape_arc.h:182
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
BOX2I m_bbox
Definition: shape_arc.h:183
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:383
VECTOR2I B
Definition: seg.h:50