trigo.cpp File Reference

Trigonometric and geometric basic functions. More...

`#include <fctsys.h>`
`#include <macros.h>`
`#include <trigo.h>`
`#include <common.h>`
`#include <math_for_graphics.h>`

Go to the source code of this file.

## Functions

bool IsPointOnSegment (const wxPoint &aSegStart, const wxPoint &aSegEnd, const wxPoint &aTestPoint)
Function IsPointOnSegment. More...

bool SegmentIntersectsSegment (const wxPoint &a_p1_l1, const wxPoint &a_p2_l1, const wxPoint &a_p1_l2, const wxPoint &a_p2_l2)
Function SegmentIntersectsSegment. More...

bool TestSegmentHit (const wxPoint &aRefPoint, wxPoint aStart, wxPoint aEnd, int aDist)
Function TestSegmentHit test for hit on line segment i.e. More...

double ArcTangente (int dy, int dx)

void RotatePoint (int *pX, int *pY, double angle)

void RotatePoint (int *pX, int *pY, int cx, int cy, double angle)

void RotatePoint (wxPoint *point, const wxPoint &centre, double angle)

void RotatePoint (VECTOR2I &point, const VECTOR2I &centre, double angle)

void RotatePoint (double *pX, double *pY, double cx, double cy, double angle)

void RotatePoint (double *pX, double *pY, double angle)

const VECTOR2I GetArcCenter (const VECTOR2I &aStart, const VECTOR2I &aMid, const VECTOR2I &aEnd)
Determine the center of an arc/circle, given three points on its circumference. More...

## Detailed Description

Trigonometric and geometric basic functions.

Definition in file trigo.cpp.

## ◆ ArcTangente()

 double ArcTangente ( int dy, int dx )

Definition at line 170 of file trigo.cpp.

171 {
172
173  /* gcc is surprisingly smart in optimizing these conditions in
174  a tree! */
175
176  if( dx == 0 && dy == 0 )
177  return 0;
178
179  if( dy == 0 )
180  {
181  if( dx >= 0 )
182  return 0;
183  else
184  return -1800;
185  }
186
187  if( dx == 0 )
188  {
189  if( dy >= 0 )
190  return 900;
191  else
192  return -900;
193  }
194
195  if( dx == dy )
196  {
197  if( dx >= 0 )
198  return 450;
199  else
200  return -1800 + 450;
201  }
202
203  if( dx == -dy )
204  {
205  if( dx >= 0 )
206  return -450;
207  else
208  return 1800 - 450;
209  }
210
211  // Of course dy and dx are treated as double
212  return RAD2DECIDEG( atan2( (double) dy, (double) dx ) );
213 }
Definition: trigo.h:213

## ◆ GetArcCenter()

 const VECTOR2I GetArcCenter ( const VECTOR2I & aStart, const VECTOR2I & aMid, const VECTOR2I & aEnd )

Determine the center of an arc/circle, given three points on its circumference.

Parameters
 aStart The starting point of the circle (equivalent to aEnd) aMid The point on the arc, half-way between aStart and aEnd aEnd The ending point of the circle (equivalent to aStart)
Returns
The center of the circle

Definition at line 349 of file trigo.cpp.

350 {
351  VECTOR2I center;
352  double yDelta_21 = aMid.y - aStart.y;
353  double xDelta_21 = aMid.x - aStart.x;
354  double yDelta_32 = aEnd.y - aMid.y;
355  double xDelta_32 = aEnd.x - aMid.x;
356
357  // This is a special case for aMid as the half-way point when aSlope = 0 and bSlope = inf
358  // or the other way around. In that case, the center lies in a straight line between
359  // aStart and aEnd
360  if( ( ( xDelta_21 == 0.0 ) && ( yDelta_32 == 0.0 ) ) ||
361  ( ( yDelta_21 == 0.0 ) && ( xDelta_32 == 0.0 ) ) )
362  {
363  center.x = KiROUND( ( aStart.x + aEnd.x ) / 2.0 );
364  center.y = KiROUND( ( aStart.y + aEnd.y ) / 2.0 );
365  return center;
366  }
367
368  // Prevent div=0 errors
369  if( xDelta_21 == 0.0 )
370  xDelta_21 = std::numeric_limits<double>::epsilon();
371
372  if( xDelta_32 == 0.0 )
373  xDelta_32 = -std::numeric_limits<double>::epsilon();
374
375  double aSlope = yDelta_21 / xDelta_21;
376  double bSlope = yDelta_32 / xDelta_32;
377
378  // If the points are colinear, the center is at infinity, so offset
379  // the slope by a minimal amount
380  // Warning: This will induce a small error in the center location
381  if( yDelta_32 * xDelta_21 == yDelta_21 * xDelta_32 )
382  {
383  aSlope += std::numeric_limits<double>::epsilon();
384  bSlope -= std::numeric_limits<double>::epsilon();
385  }
386
387  if( aSlope == 0.0 )
388  aSlope = std::numeric_limits<double>::epsilon();
389
390  if( bSlope == 0.0 )
391  bSlope = -std::numeric_limits<double>::epsilon();
392
393
394  double result = ( aSlope * bSlope * ( aStart.y - aEnd.y ) +
395  bSlope * ( aStart.x + aMid.x ) -
396  aSlope * ( aMid.x + aEnd.x ) ) / ( 2 * ( bSlope - aSlope ) );
397
398  center.x = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() / 2 ),
399  result,
400  double( std::numeric_limits<int>::max() / 2 ) ) );
401
402  result = ( ( ( aStart.x + aMid.x ) / 2.0 - center.x ) / aSlope +
403  ( aStart.y + aMid.y ) / 2.0 );
404
405  center.y = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() / 2 ),
406  result,
407  double( std::numeric_limits<int>::max() / 2 ) ) );
408
409  return center;
410 }
static int KiROUND(double v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: common.h:118
#define max(a, b)
Definition: auxiliary.h:86
#define min(a, b)
Definition: auxiliary.h:85

References KiROUND(), max, min, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by POINT_EDITOR::updateItem().

## ◆ IsPointOnSegment()

 bool IsPointOnSegment ( const wxPoint & aSegStart, const wxPoint & aSegEnd, const wxPoint & aTestPoint )

Function IsPointOnSegment.

Parameters
 aSegStart The first point of the segment S. aSegEnd The second point of the segment S. aTestPoint The point P to test.
Returns
true if the point P is on the segment S. faster than TestSegmentHit() because P should be exactly on S therefore works fine only for H, V and 45 deg segm. suitable for busses and wires in eeschema, otherwise use TestSegmentHit()

Definition at line 39 of file trigo.cpp.

41 {
42  wxPoint vectSeg = aSegEnd - aSegStart; // Vector from S1 to S2
43  wxPoint vectPoint = aTestPoint - aSegStart; // Vector from S1 to P
44
45  // Use long long here to avoid overflow in calculations
46  if( (long long) vectSeg.x * vectPoint.y - (long long) vectSeg.y * vectPoint.x )
47  return false; /* Cross product non-zero, vectors not parallel */
48
49  if( ( (long long) vectSeg.x * vectPoint.x + (long long) vectSeg.y * vectPoint.y ) <
50  ( (long long) vectPoint.x * vectPoint.x + (long long) vectPoint.y * vectPoint.y ) )
51  return false; /* Point not on segment */
52
53  return true;
54 }

## ◆ RotatePoint() [1/6]

 void RotatePoint ( int * pX, int * pY, double angle )

Definition at line 216 of file trigo.cpp.

217 {
218  int tmp;
219
221
222  // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
223  if( angle == 0 )
224  return;
225
226  if( angle == 900 ) /* sin = 1, cos = 0 */
227  {
228  tmp = *pX;
229  *pX = *pY;
230  *pY = -tmp;
231  }
232  else if( angle == 1800 ) /* sin = 0, cos = -1 */
233  {
234  *pX = -*pX;
235  *pY = -*pY;
236  }
237  else if( angle == 2700 ) /* sin = -1, cos = 0 */
238  {
239  tmp = *pX;
240  *pX = -*pY;
241  *pY = tmp;
242  }
243  else
244  {
245  double fangle = DECIDEG2RAD( angle );
246  double sinus = sin( fangle );
247  double cosinus = cos( fangle );
248  double fpx = (*pY * sinus ) + (*pX * cosinus );
249  double fpy = (*pY * cosinus ) - (*pX * sinus );
250  *pX = KiROUND( fpx );
251  *pY = KiROUND( fpy );
252  }
253 }
static int KiROUND(double v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: common.h:118
void NORMALIZE_ANGLE_POS(T &Angle)
Definition: trigo.h:250
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
Definition: trigo.h:212

References PNS::angle(), DECIDEG2RAD(), KiROUND(), and NORMALIZE_ANGLE_POS().

## ◆ RotatePoint() [2/6]

 void RotatePoint ( int * pX, int * pY, int cx, int cy, double angle )

Definition at line 256 of file trigo.cpp.

257 {
258  int ox, oy;
259
260  ox = *pX - cx;
261  oy = *pY - cy;
262
263  RotatePoint( &ox, &oy, angle );
264
265  *pX = ox + cx;
266  *pY = oy + cy;
267 }
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:216
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)

References PNS::angle(), and RotatePoint().

## ◆ RotatePoint() [3/6]

 void RotatePoint ( wxPoint * point, const wxPoint & centre, double angle )

Definition at line 270 of file trigo.cpp.

271 {
272  int ox, oy;
273
274  ox = point->x - centre.x;
275  oy = point->y - centre.y;
276
277  RotatePoint( &ox, &oy, angle );
278  point->x = ox + centre.x;
279  point->y = oy + centre.y;
280 }
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:216
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)

References PNS::angle(), and RotatePoint().

## ◆ RotatePoint() [4/6]

 void RotatePoint ( VECTOR2I & point, const VECTOR2I & centre, double angle )

Definition at line 282 of file trigo.cpp.

283 {
284  wxPoint c( centre.x, centre.y );
285  wxPoint p( point.x, point.y );
286
287  RotatePoint(&p, c, angle);
288
289  point.x = p.x;
290  point.y = p.y;
291 }
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:216
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)

References PNS::angle(), RotatePoint(), VECTOR2< T >::x, and VECTOR2< T >::y.

## ◆ RotatePoint() [5/6]

 void RotatePoint ( double * pX, double * pY, double cx, double cy, double angle )

Definition at line 294 of file trigo.cpp.

295 {
296  double ox, oy;
297
298  ox = *pX - cx;
299  oy = *pY - cy;
300
301  RotatePoint( &ox, &oy, angle );
302
303  *pX = ox + cx;
304  *pY = oy + cy;
305 }
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:216
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)

References PNS::angle(), and RotatePoint().

## ◆ RotatePoint() [6/6]

 void RotatePoint ( double * pX, double * pY, double angle )

Definition at line 308 of file trigo.cpp.

309 {
310  double tmp;
311
313
314  // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
315  if( angle == 0 )
316  return;
317
318  if( angle == 900 ) /* sin = 1, cos = 0 */
319  {
320  tmp = *pX;
321  *pX = *pY;
322  *pY = -tmp;
323  }
324  else if( angle == 1800 ) /* sin = 0, cos = -1 */
325  {
326  *pX = -*pX;
327  *pY = -*pY;
328  }
329  else if( angle == 2700 ) /* sin = -1, cos = 0 */
330  {
331  tmp = *pX;
332  *pX = -*pY;
333  *pY = tmp;
334  }
335  else
336  {
337  double fangle = DECIDEG2RAD( angle );
338  double sinus = sin( fangle );
339  double cosinus = cos( fangle );
340
341  double fpx = (*pY * sinus ) + (*pX * cosinus );
342  double fpy = (*pY * cosinus ) - (*pX * sinus );
343  *pX = fpx;
344  *pY = fpy;
345  }
346 }
void NORMALIZE_ANGLE_POS(T &Angle)
Definition: trigo.h:250
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
Definition: trigo.h:212

## ◆ SegmentIntersectsSegment()

 bool SegmentIntersectsSegment ( const wxPoint & a_p1_l1, const wxPoint & a_p2_l1, const wxPoint & a_p1_l2, const wxPoint & a_p2_l2 )

Function SegmentIntersectsSegment.

Parameters
 a_p1_l1 The first point of the first line. a_p2_l1 The second point of the first line. a_p1_l2 The first point of the second line. a_p2_l2 The second point of the second line.
Returns
bool - true if the two segments defined by four points intersect. (i.e. if the 2 segments have at least a common point)

Definition at line 58 of file trigo.cpp.

60 {
61
62  //We are forced to use 64bit ints because the internal units can oveflow 32bit ints when
63  // multiplied with each other, the alternative would be to scale the units down (i.e. divide
64  // by a fixed number).
65  long long dX_a, dY_a, dX_b, dY_b, dX_ab, dY_ab;
66  long long num_a, num_b, den;
67
68  //Test for intersection within the bounds of both line segments using line equations of the
69  // form:
70  // x_k(u_k) = u_k * dX_k + x_k(0)
71  // y_k(u_k) = u_k * dY_k + y_k(0)
72  // with 0 <= u_k <= 1 and k = [ a, b ]
73
74  dX_a = a_p2_l1.x - a_p1_l1.x;
75  dY_a = a_p2_l1.y - a_p1_l1.y;
76  dX_b = a_p2_l2.x - a_p1_l2.x;
77  dY_b = a_p2_l2.y - a_p1_l2.y;
78  dX_ab = a_p1_l2.x - a_p1_l1.x;
79  dY_ab = a_p1_l2.y - a_p1_l1.y;
80
81  den = dY_a * dX_b - dY_b * dX_a ;
82
83  //Check if lines are parallel
84  if( den == 0 )
85  return false;
86
87  num_a = dY_ab * dX_b - dY_b * dX_ab;
88  num_b = dY_ab * dX_a - dY_a * dX_ab;
89
90  //We wont calculate directly the u_k of the intersection point to avoid floating point
91  // division but they could be calculated with:
92  // u_a = (float) num_a / (float) den;
93  // u_b = (float) num_b / (float) den;
94
95  if( den < 0 )
96  {
97  den = -den;
98  num_a = -num_a;
99  num_b = -num_b;
100  }
101
102  //Test sign( u_a ) and return false if negative
103  if( num_a < 0 )
104  return false;
105
106  //Test sign( u_b ) and return false if negative
107  if( num_b < 0 )
108  return false;
109
110  //Test to ensure (u_a <= 1)
111  if( num_a > den )
112  return false;
113
114  //Test to ensure (u_b <= 1)
115  if( num_b > den )
116  return false;
117
118  return true;
119 }

Referenced by EDA_RECT::Intersects().

## ◆ TestSegmentHit()

 bool TestSegmentHit ( const wxPoint & aRefPoint, wxPoint aStart, wxPoint aEnd, int aDist )

Function TestSegmentHit test for hit on line segment i.e.

a reference point is within a given distance from segment

Parameters
 aRefPoint = reference point to test aStart is the first end-point of the line segment aEnd is the second end-point of the line segment aDist = maximum distance for hit

Definition at line 122 of file trigo.cpp.

123 {
124  int xmin = aStart.x;
125  int xmax = aEnd.x;
126  int ymin = aStart.y;
127  int ymax = aEnd.y;
128  wxPoint delta = aStart - aRefPoint;
129
130  if( xmax < xmin )
131  std::swap( xmax, xmin );
132
133  if( ymax < ymin )
134  std::swap( ymax, ymin );
135
136  // First, check if we are outside of the bounding box
137  if( ( ymin - aRefPoint.y > aDist ) || ( aRefPoint.y - ymax > aDist ) )
138  return false;
139
140  if( ( xmin - aRefPoint.x > aDist ) || ( aRefPoint.x - xmax > aDist ) )
141  return false;
142
143  // Next, eliminate easy cases
144  if( aStart.x == aEnd.x && aRefPoint.y > ymin && aRefPoint.y < ymax )
145  return std::abs( delta.x ) <= aDist;
146
147  if( aStart.y == aEnd.y && aRefPoint.x > xmin && aRefPoint.x < xmax )
148  return std::abs( delta.y ) <= aDist;
149
150  wxPoint len = aEnd - aStart;
151  // Precision note here:
152  // These are 32-bit integers, so squaring requires 64 bits to represent
153  // exactly. 64-bit Doubles have only 52 bits in the mantissa, so we start to lose
154  // precision at 2^53, which corresponds to ~ ±1nm @ 9.5cm, 2nm at 90cm, etc...
155  // Long doubles avoid this ambiguity as well as the more expensive denormal double calc
156  // Long doubles usually (sometimes more if SIMD) have at least 64 bits in the mantissa
157  long double length_square = (long double) len.x * len.x + (long double) len.y * len.y;
158  long double cross = std::abs( (long double) len.x * delta.y - (long double) len.y * delta.x );
160
161  // The perpendicular distance to a line is the vector magnitude of the line from
162  // a test point to the test line. That is the 2d determinant. Because we handled
163  // the zero length case above, so we are guaranteed a unique solution.
164
165  return ( ( length_square >= cross && dist_square >= cross ) ||
166  ( length_square * dist_square >= cross * cross ) );
167 }
#define abs(a)
Definition: auxiliary.h:84
static const int delta[8][2]
Definition: solve.cpp:112

References abs, and delta.