1 /*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2018-2021 KiCad Developers, see AUTHORS.txt for contributors.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, you may find one here:
18 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
19 * or you may search the http://www.gnu.org website for the version 2 license,
20 * or you may write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22 */
23
24 #ifndef TRIGO_H
25 #define TRIGO_H
26
27 /**
28 * @file trigo.h
29 */
30
31 #include <cmath>
32 #include <math/vector2d.h>
33 #include <wx/gdicmn.h> // For wxPoint
34
35 /**
36 * Test if \a aTestPoint is on line defined by \a aSegStart and \a aSegEnd.
37 *
38 * This function is faster than #TestSegmentHit() because \a aTestPoint should be exactly on
39 * the line. This works fine only for H, V and 45 degree line segments.
40 *
41 * @param aSegStart The first point of the line segment.
42 * @param aSegEnd The second point of the line segment.
43 * @param aTestPoint The point to test.
44 *
45 * @return true if the point is on the line segment.
46 */
47 bool IsPointOnSegment( const wxPoint& aSegStart, const wxPoint& aSegEnd,
48 const wxPoint& aTestPoint );
49
50 /**
51 * Test if two lines intersect.
52 *
53 * @param a_p1_l1 The first point of the first line.
54 * @param a_p2_l1 The second point of the first line.
55 * @param a_p1_l2 The first point of the second line.
56 * @param a_p2_l2 The second point of the second line.
57 * @param aIntersectionPoint is filled with the intersection point if it exists
58 * @return bool - true if the two segments defined by four points intersect.
59 * (i.e. if the 2 segments have at least a common point)
60 */
61 bool SegmentIntersectsSegment( const wxPoint& a_p1_l1, const wxPoint& a_p2_l1,
62 const wxPoint& a_p1_l2, const wxPoint& a_p2_l2,
63 wxPoint* aIntersectionPoint = nullptr );
64
65 /*
66 * Calculate the new point of coord coord pX, pY,
67 * for a rotation center 0, 0, and angle in (1 / 10 degree)
68 */
69 void RotatePoint( int *pX, int *pY, double angle );
70
71 /*
72 * Calculate the new point of coord coord pX, pY,
73 * for a rotation center cx, cy, and angle in (1 / 10 degree)
74 */
75 void RotatePoint( int *pX, int *pY, int cx, int cy, double angle );
76
77 /*
78 * Calculate the new coord point point for a rotation angle in (1 / 10 degree).
79 */
RotatePoint(wxPoint * point,double angle)80 inline void RotatePoint( wxPoint* point, double angle )
81 {
82 RotatePoint( &point->x, &point->y, angle );
83 }
84
RotatePoint(VECTOR2I & point,double angle)85 inline void RotatePoint( VECTOR2I& point, double angle )
86 {
87 RotatePoint( &point.x, &point.y, angle );
88 }
89
90 void RotatePoint( VECTOR2I& point, const VECTOR2I& centre, double angle );
91
92 /*
93 * Calculate the new coord point point for a center rotation center and angle in (1 / 10 degree).
94 */
95 void RotatePoint( wxPoint *point, const wxPoint & centre, double angle );
96
97 void RotatePoint( double *pX, double *pY, double angle );
98
99 void RotatePoint( double *pX, double *pY, double cx, double cy, double angle );
100
101 /**
102 * Determine the center of an arc or circle given three points on its circumference.
103 *
104 * @param aStart The starting point of the circle (equivalent to aEnd)
105 * @param aMid The point on the arc, half-way between aStart and aEnd
106 * @param aEnd The ending point of the circle (equivalent to aStart)
107 * @return The center of the circle
108 */
109 const VECTOR2I CalcArcCenter( const VECTOR2I& aStart, const VECTOR2I& aMid, const VECTOR2I& aEnd );
110 const VECTOR2D CalcArcCenter( const VECTOR2D& aStart, const VECTOR2D& aMid, const VECTOR2D& aEnd );
111 const wxPoint CalcArcCenter( const wxPoint& aStart, const wxPoint& aMid, const wxPoint& aEnd );
112 const wxPoint CalcArcCenter( const VECTOR2I& aStart, const VECTOR2I& aEnd, double aAngle );
113
114 /**
115 * Return the subtended angle for a given arc.
116 */
117 double CalcArcAngle( const VECTOR2I& aStart, const VECTOR2I& aMid, const VECTOR2I& aEnd );
118
119 /**
120 * Return the middle point of an arc, half-way between aStart and aEnd. There are two possible
121 * solutions which can be found by toggling aMinArcAngle. The behaviour is undefined for
122 * semicircles (i.e. 180 degree arcs).
123 *
124 * @param aStart The starting point of the arc (for calculating the radius)
125 * @param aEnd The end point of the arc (for determining the arc angle)
126 * @param aCenter The center point of the arc
127 * @param aMinArcAngle If true, returns the point that results in the smallest arc angle.
128 * @return The middle point of the arc
129 */
130 const VECTOR2I CalcArcMid( const VECTOR2I& aStart, const VECTOR2I& aEnd, const VECTOR2I& aCenter,
131 bool aMinArcAngle = true );
132
133 /* Return the arc tangent of 0.1 degrees coord vector dx, dy
134 * between -1800 and 1800
135 * Equivalent to atan2 (but faster for calculations if
136 * the angle is 0 to -1800, or + - 900)
137 * Lorenzo: In fact usually atan2 already has to do these optimizations
138 * (due to the discontinuity in tan) but this function also returns
139 * in decidegrees instead of radians, so it's handier
140 */
141 double ArcTangente( int dy, int dx );
142
143 //! @brief Euclidean norm of a 2D vector
144 //! @param vector Two-dimensional vector
145 //! @return Euclidean norm of the vector
EuclideanNorm(const wxPoint & vector)146 inline double EuclideanNorm( const wxPoint &vector )
147 {
148 // this is working with doubles
149 return hypot( vector.x, vector.y );
150 }
151
EuclideanNorm(const wxSize & vector)152 inline double EuclideanNorm( const wxSize &vector )
153 {
154 // this is working with doubles, too
155 return hypot( vector.x, vector.y );
156 }
157
158 //! @brief Compute the distance between a line and a reference point
159 //! Reference: http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html
160 //! @param linePointA Point on line
161 //! @param linePointB Point on line
162 //! @param referencePoint Reference point
DistanceLinePoint(const wxPoint & linePointA,const wxPoint & linePointB,const wxPoint & referencePoint)163 inline double DistanceLinePoint( const wxPoint& linePointA,
164 const wxPoint& linePointB,
165 const wxPoint& referencePoint )
166 {
167 // Some of the multiple double casts are redundant. However in the previous
168 // definition the cast was (implicitly) done too late, just before
169 // the division (EuclideanNorm gives a double so from int it would
170 // be promoted); that means that the whole expression were
171 // vulnerable to overflow during int multiplications
172 return fabs( ( static_cast<double>( linePointB.x - linePointA.x ) *
173 static_cast<double>( linePointA.y - referencePoint.y ) -
174 static_cast<double>( linePointA.x - referencePoint.x ) *
175 static_cast<double>( linePointB.y - linePointA.y) )
176 / EuclideanNorm( linePointB - linePointA ) );
177 }
178
179 //! @brief Test, if two points are near each other
180 //! @param pointA First point
181 //! @param pointB Second point
182 //! @param threshold The maximum distance
183 //! @return True or false
HitTestPoints(const wxPoint & pointA,const wxPoint & pointB,double threshold)184 inline bool HitTestPoints( const wxPoint& pointA, const wxPoint& pointB, double threshold )
185 {
186 wxPoint vectorAB = pointB - pointA;
187
188 // Compare the distances squared. The double is needed to avoid
189 // overflow during int multiplication
190 double sqdistance = (double)vectorAB.x * vectorAB.x + (double)vectorAB.y * vectorAB.y;
191
192 return sqdistance < threshold * threshold;
193 }
194
195 //! @brief Determine the cross product
196 //! @param vectorA Two-dimensional vector
197 //! @param vectorB Two-dimensional vector
CrossProduct(const wxPoint & vectorA,const wxPoint & vectorB)198 inline double CrossProduct( const wxPoint& vectorA, const wxPoint& vectorB )
199 {
200 // As before the cast is to avoid int overflow
201 return (double)vectorA.x * vectorB.y - (double)vectorA.y * vectorB.x;
202 }
203
204 /**
205 * Test if \a aRefPoint is with \a aDistance on the line defined by \a aStart and \a aEnd..
206 *
207 * @param aRefPoint = reference point to test
208 * @param aStart is the first end-point of the line segment
209 * @param aEnd is the second end-point of the line segment
210 * @param aDist = maximum distance for hit
211 */
212 bool TestSegmentHit( const wxPoint& aRefPoint, const wxPoint& aStart, const wxPoint& aEnd,
213 int aDist );
214
215 /**
216 * Return the length of a line segment defined by \a aPointA and \a aPointB.
217 *
218 * See also EuclideanNorm and Distance for the single vector or four scalar versions.
219 *
220 * @return Length of a line (as double)
221 */
GetLineLength(const wxPoint & aPointA,const wxPoint & aPointB)222 inline double GetLineLength( const wxPoint& aPointA, const wxPoint& aPointB )
223 {
224 // Implicitly casted to double
225 return hypot( aPointA.x - aPointB.x, aPointA.y - aPointB.y );
226 }
227
228 // These are the usual degrees <-> radians conversion routines
DEG2RAD(double deg)229 inline double DEG2RAD( double deg ) { return deg * M_PI / 180.0; }
RAD2DEG(double rad)230 inline double RAD2DEG( double rad ) { return rad * 180.0 / M_PI; }
231
232 // These are the same *but* work with the internal 'decidegrees' unit
DECIDEG2RAD(double deg)233 inline double DECIDEG2RAD( double deg ) { return deg * M_PI / 1800.0; }
RAD2DECIDEG(double rad)234 inline double RAD2DECIDEG( double rad ) { return rad * 1800.0 / M_PI; }
235
236 /* These are templated over T (and not simply double) because Eeschema
237 is still using int for angles in some place */
238
239 /// Normalize angle to be >=-360.0 and <= 360.0
240 /// Angle can be equal to -360 or +360
NormalizeAngle360Max(T Angle)241 template <class T> inline T NormalizeAngle360Max( T Angle )
242 {
243 while( Angle < -3600 )
244 Angle += 3600;
245
246 while( Angle > 3600 )
247 Angle -= 3600;
248
249 return Angle;
250 }
251
252 /// Normalize angle to be > -360.0 and < 360.0
253 /// Angle equal to -360 or +360 are set to 0
NormalizeAngle360Min(T Angle)254 template <class T> inline T NormalizeAngle360Min( T Angle )
255 {
256 while( Angle <= -3600 )
257 Angle += 3600;
258
259 while( Angle >= 3600 )
260 Angle -= 3600;
261
262 return Angle;
263 }
264
265
266 /// Normalize angle to be in the 0.0 .. -360.0 range: angle is in 1/10 degrees.
267 template <class T>
NormalizeAngleNeg(T Angle)268 inline T NormalizeAngleNeg( T Angle )
269 {
270 while( Angle <= -3600 )
271 Angle += 3600;
272
273 while( Angle > 0 )
274 Angle -= 3600;
275
276 return Angle;
277 }
278
279
280 /// Normalize angle to be in the 0.0 .. 360.0 range: angle is in 1/10 degrees.
NormalizeAnglePos(T Angle)281 template <class T> inline T NormalizeAnglePos( T Angle )
282 {
283 while( Angle < 0 )
284 Angle += 3600;
285 while( Angle >= 3600 )
286 Angle -= 3600;
287 return Angle;
288 }
289
NORMALIZE_ANGLE_POS(T & Angle)290 template <class T> inline void NORMALIZE_ANGLE_POS( T& Angle )
291 {
292 Angle = NormalizeAnglePos( Angle );
293 }
294
295
296 /// Normalize angle to be in the 0.0 .. 360.0 range: angle is in degrees.
NormalizeAngleDegreesPos(double Angle)297 inline double NormalizeAngleDegreesPos( double Angle )
298 {
299 while( Angle < 0 )
300 Angle += 360.0;
301
302 while( Angle >= 360.0 )
303 Angle -= 360.0;
304
305 return Angle;
306 }
307
308
NORMALIZE_ANGLE_DEGREES_POS(double & Angle)309 inline void NORMALIZE_ANGLE_DEGREES_POS( double& Angle )
310 {
311 Angle = NormalizeAngleDegreesPos( Angle );
312 }
313
314
NormalizeAngleRadiansPos(double Angle)315 inline double NormalizeAngleRadiansPos( double Angle )
316 {
317 while( Angle < 0 )
318 Angle += (2 * M_PI );
319
320 while( Angle >= ( 2 * M_PI ) )
321 Angle -= ( 2 * M_PI );
322
323 return Angle;
324 }
325
326 /// Normalize angle to be aMin < angle <= aMax angle is in degrees.
NormalizeAngleDegrees(double Angle,double aMin,double aMax)327 inline double NormalizeAngleDegrees( double Angle, double aMin, double aMax )
328 {
329 while( Angle < aMin )
330 Angle += 360.0;
331
332 while( Angle >= aMax )
333 Angle -= 360.0;
334
335 return Angle;
336 }
337
338 /// Add two angles (keeping the result normalized). T2 is here
339 // because most of the time it's an int (and templates don't promote in
340 // that way)
AddAngles(T a1,T2 a2)341 template <class T, class T2> inline T AddAngles( T a1, T2 a2 )
342 {
343 a1 += a2;
344 NORMALIZE_ANGLE_POS( a1 );
345 return a1;
346 }
347
348
NegateAndNormalizeAnglePos(T Angle)349 template <class T> inline T NegateAndNormalizeAnglePos( T Angle )
350 {
351 Angle = -Angle;
352
353 while( Angle < 0 )
354 Angle += 3600;
355
356 while( Angle >= 3600 )
357 Angle -= 3600;
358
359 return Angle;
360 }
361
NEGATE_AND_NORMALIZE_ANGLE_POS(T & Angle)362 template <class T> inline void NEGATE_AND_NORMALIZE_ANGLE_POS( T& Angle )
363 {
364 Angle = NegateAndNormalizeAnglePos( Angle );
365 }
366
367
368 /// Normalize angle to be in the -90.0 .. 90.0 range
NormalizeAngle90(T Angle)369 template <class T> inline T NormalizeAngle90( T Angle )
370 {
371 while( Angle < -900 )
372 Angle += 1800;
373
374 while( Angle > 900 )
375 Angle -= 1800;
376
377 return Angle;
378 }
379
NORMALIZE_ANGLE_90(T & Angle)380 template <class T> inline void NORMALIZE_ANGLE_90( T& Angle )
381 {
382 Angle = NormalizeAngle90( Angle );
383 }
384
385
386 /// Normalize angle to be in the -180.0 .. 180.0 range
NormalizeAngle180(T Angle)387 template <class T> inline T NormalizeAngle180( T Angle )
388 {
389 while( Angle <= -1800 )
390 Angle += 3600;
391
392 while( Angle > 1800 )
393 Angle -= 3600;
394
395 return Angle;
396 }
397
NORMALIZE_ANGLE_180(T & Angle)398 template <class T> inline void NORMALIZE_ANGLE_180( T& Angle )
399 {
400 Angle = NormalizeAngle180( Angle );
401 }
402
403 /**
404 * Test if an arc from \a aStartAngle to \a aEndAngle crosses the positive X axis (0 degrees).
405 *
406 * Testing is performed in the quadrant 1 to quadrant 4 direction (counter-clockwise).
407 *
408 * @param aStartAngle The arc start angle in degrees.
409 * @param aEndAngle The arc end angle in degrees.
410 */
InterceptsPositiveX(double aStartAngle,double aEndAngle)411 inline bool InterceptsPositiveX( double aStartAngle, double aEndAngle )
412 {
413 double end = aEndAngle;
414
415 if( aStartAngle > aEndAngle )
416 end += 360.0;
417
418 return aStartAngle < 360.0 && end > 360.0;
419 }
420
421 /**
422 * Test if an arc from \a aStartAngle to \a aEndAngle crosses the negative X axis (180 degrees).
423 *
424 * Testing is performed in the quadrant 1 to quadrant 4 direction (counter-clockwise).
425 *
426 * @param aStartAngle The arc start angle in degrees.
427 * @param aEndAngle The arc end angle in degrees.
428 */
InterceptsNegativeX(double aStartAngle,double aEndAngle)429 inline bool InterceptsNegativeX( double aStartAngle, double aEndAngle )
430 {
431 double end = aEndAngle;
432
433 if( aStartAngle > aEndAngle )
434 end += 360.0;
435
436 return aStartAngle < 180.0 && end > 180.0;
437 }
438
439 /**
440 * Circle generation utility: computes r * sin(a)
441 * Where a is in decidegrees, not in radians.
442 */
sindecideg(double r,double a)443 inline double sindecideg( double r, double a )
444 {
445 return r * sin( DECIDEG2RAD( a ) );
446 }
447
448 /**
449 * Circle generation utility: computes r * cos(a)
450 * Where a is in decidegrees, not in radians.
451 */
cosdecideg(double r,double a)452 inline double cosdecideg( double r, double a )
453 {
454 return r * cos( DECIDEG2RAD( a ) );
455 }
456
457 #endif
458