KiCad PCB EDA Suite
Loading...
Searching...
No Matches
trigo.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) 2014 Jean-Pierre Charras, jp.charras at wanadoo.fr
5 * Copyright (C) 2014-2023 KiCad Developers, see AUTHORS.txt for contributors.
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
30#include <limits> // for numeric_limits
31#include <stdlib.h> // for abs
32#include <type_traits> // for swap
33
34#include <geometry/seg.h>
35#include <math/util.h>
36#include <math/vector2d.h> // for VECTOR2I
37#include <trigo.h>
38
39
40/*
41CircleCenterFrom3Points calculate the center of a circle defined by 3 points
42It is similar to CalcArcCenter( const VECTOR2D& aStart, const VECTOR2D& aMid, const VECTOR2D& aEnd )
43but it was needed to debug CalcArcCenter, so I keep it available for other issues in CalcArcCenter
44
45The perpendicular bisector of the segment between two points is the
46set of all points equidistant from both. So if you take the
47perpendicular bisector of (x1,y1) and (x2,y2) and the perpendicular
48bisector of the segment from (x2,y2) to (x3,y3) and find the
49intersection of those lines, that point will be the center.
50
51To find the equation of the perpendicular bisector of (x1,y1) to (x2,y2),
52you know that it passes through the midpoint of the segment:
53((x1+x2)/2,(y1+y2)/2), and if the slope of the line
54connecting (x1,y1) to (x2,y2) is m, the slope of the perpendicular
55bisector is -1/m. Work out the equations for the two lines, find
56their intersection, and bingo! You've got the coordinates of the center.
57
58An error should occur if the three points lie on a line, and you'll
59need special code to check for the case where one of the slopes is zero.
60
61see https://web.archive.org/web/20171223103555/http://mathforum.org/library/drmath/view/54323.html
62*/
63
64//#define USE_ALTERNATE_CENTER_ALGO
65
66#ifdef USE_ALTERNATE_CENTER_ALGO
67bool CircleCenterFrom3Points( const VECTOR2D& p1, const VECTOR2D& p2, const VECTOR2D& p3, VECTOR2D* aCenter )
68{
69 // Move coordinate origin to p2, to simplify calculations
70 VECTOR2D b = p1 - p2;
71 VECTOR2D d = p3 - p2;
72 double bc = ( b.x*b.x + b.y*b.y ) / 2.0;
73 double cd = ( -d.x*d.x - d.y*d.y ) / 2.0;
74 double det = -b.x*d.y + d.x*b.y;
75
76 if( fabs(det) < 1.0e-6 ) // arbitrary limit to avoid divide by 0
77 return false;
78
79 det = 1/det;
80 aCenter->x = ( -bc*d.y - cd*b.y ) * det;
81 aCenter->y = ( b.x*cd + d.x*bc ) * det;
82 *aCenter += p2;
83
84 return true;
85}
86#endif
87
88bool IsPointOnSegment( const VECTOR2I& aSegStart, const VECTOR2I& aSegEnd,
89 const VECTOR2I& aTestPoint )
90{
91 VECTOR2I vectSeg = aSegEnd - aSegStart; // Vector from S1 to S2
92 VECTOR2I vectPoint = aTestPoint - aSegStart; // Vector from S1 to P
93
94 // Use long long here to avoid overflow in calculations
95 if( (long long) vectSeg.x * vectPoint.y - (long long) vectSeg.y * vectPoint.x )
96 return false; /* Cross product non-zero, vectors not parallel */
97
98 if( ( (long long) vectSeg.x * vectPoint.x + (long long) vectSeg.y * vectPoint.y ) <
99 ( (long long) vectPoint.x * vectPoint.x + (long long) vectPoint.y * vectPoint.y ) )
100 return false; /* Point not on segment */
101
102 return true;
103}
104
105
106bool SegmentIntersectsSegment( const VECTOR2I& a_p1_l1, const VECTOR2I& a_p2_l1,
107 const VECTOR2I& a_p1_l2, const VECTOR2I& a_p2_l2,
108 VECTOR2I* aIntersectionPoint )
109{
110
111 // We are forced to use 64bit ints because the internal units can overflow 32bit ints when
112 // multiplied with each other, the alternative would be to scale the units down (i.e. divide
113 // by a fixed number).
114 int64_t dX_a, dY_a, dX_b, dY_b, dX_ab, dY_ab;
115 int64_t num_a, num_b, den;
116
117 // Test for intersection within the bounds of both line segments using line equations of the
118 // form:
119 // x_k(u_k) = u_k * dX_k + x_k(0)
120 // y_k(u_k) = u_k * dY_k + y_k(0)
121 // with 0 <= u_k <= 1 and k = [ a, b ]
122
123 dX_a = int64_t{ a_p2_l1.x } - a_p1_l1.x;
124 dY_a = int64_t{ a_p2_l1.y } - a_p1_l1.y;
125 dX_b = int64_t{ a_p2_l2.x } - a_p1_l2.x;
126 dY_b = int64_t{ a_p2_l2.y } - a_p1_l2.y;
127 dX_ab = int64_t{ a_p1_l2.x } - a_p1_l1.x;
128 dY_ab = int64_t{ a_p1_l2.y } - a_p1_l1.y;
129
130 den = dY_a * dX_b - dY_b * dX_a ;
131
132 // Check if lines are parallel.
133 if( den == 0 )
134 return false;
135
136 num_a = dY_ab * dX_b - dY_b * dX_ab;
137 num_b = dY_ab * dX_a - dY_a * dX_ab;
138
139 // Only compute the intersection point if requested.
140 if( aIntersectionPoint )
141 {
142 *aIntersectionPoint = a_p1_l1;
143 aIntersectionPoint->x += KiROUND( dX_a * ( double )num_a / ( double )den );
144 aIntersectionPoint->y += KiROUND( dY_a * ( double )num_b / ( double )den );
145 }
146
147 if( den < 0 )
148 {
149 den = -den;
150 num_a = -num_a;
151 num_b = -num_b;
152 }
153
154 // Test sign( u_a ) and return false if negative.
155 if( num_a < 0 )
156 return false;
157
158 // Test sign( u_b ) and return false if negative.
159 if( num_b < 0 )
160 return false;
161
162 // Test to ensure (u_a <= 1).
163 if( num_a > den )
164 return false;
165
166 // Test to ensure (u_b <= 1).
167 if( num_b > den )
168 return false;
169
170 return true;
171}
172
173
174bool TestSegmentHit( const VECTOR2I& aRefPoint, const VECTOR2I& aStart, const VECTOR2I& aEnd,
175 int aDist )
176{
177 int xmin = aStart.x;
178 int xmax = aEnd.x;
179 int ymin = aStart.y;
180 int ymax = aEnd.y;
181 VECTOR2I delta = aStart - aRefPoint;
182
183 if( xmax < xmin )
184 std::swap( xmax, xmin );
185
186 if( ymax < ymin )
187 std::swap( ymax, ymin );
188
189 // Check if we are outside of the bounding box.
190 if( ( ymin - aRefPoint.y > aDist ) || ( aRefPoint.y - ymax > aDist ) )
191 return false;
192
193 if( ( xmin - aRefPoint.x > aDist ) || ( aRefPoint.x - xmax > aDist ) )
194 return false;
195
196 // Eliminate easy cases.
197 if( aStart.x == aEnd.x && aRefPoint.y > ymin && aRefPoint.y < ymax )
198 return std::abs( delta.x ) <= aDist;
199
200 if( aStart.y == aEnd.y && aRefPoint.x > xmin && aRefPoint.x < xmax )
201 return std::abs( delta.y ) <= aDist;
202
203 SEG segment( aStart, aEnd );
204 return segment.SquaredDistance( aRefPoint ) < SEG::Square( aDist + 1 );
205}
206
207
208const VECTOR2I CalcArcMid( const VECTOR2I& aStart, const VECTOR2I& aEnd, const VECTOR2I& aCenter,
209 bool aMinArcAngle )
210{
211 VECTOR2I startVector = aStart - aCenter;
212 VECTOR2I endVector = aEnd - aCenter;
213
214 EDA_ANGLE startAngle( startVector );
215 EDA_ANGLE endAngle( endVector );
216 EDA_ANGLE midPointRotAngle = ( startAngle - endAngle ).Normalize180() / 2;
217
218 if( !aMinArcAngle )
219 midPointRotAngle += ANGLE_180;
220
221 VECTOR2I newMid = aStart;
222 RotatePoint( newMid, aCenter, midPointRotAngle );
223
224 return newMid;
225}
226
227
228void RotatePoint( int* pX, int* pY, const EDA_ANGLE& aAngle )
229{
230 VECTOR2I pt;
231 EDA_ANGLE angle = aAngle;
232
233 angle.Normalize();
234
235 // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
236 if( angle == ANGLE_0 )
237 {
238 pt = VECTOR2I( *pX, *pY );
239 }
240 else if( angle == ANGLE_90 ) /* sin = 1, cos = 0 */
241 {
242 pt = VECTOR2I( *pY, -*pX );
243 }
244 else if( angle == ANGLE_180 ) /* sin = 0, cos = -1 */
245 {
246 pt = VECTOR2I( -*pX, -*pY );
247 }
248 else if( angle == ANGLE_270 ) /* sin = -1, cos = 0 */
249 {
250 pt = VECTOR2I( -*pY, *pX );
251 }
252 else
253 {
254 double sinus = angle.Sin();
255 double cosinus = angle.Cos();
256
257 pt.x = KiROUND( ( *pY * sinus ) + ( *pX * cosinus ) );
258 pt.y = KiROUND( ( *pY * cosinus ) - ( *pX * sinus ) );
259 }
260
261 *pX = pt.x;
262 *pY = pt.y;
263}
264
265
266void RotatePoint( int* pX, int* pY, int cx, int cy, const EDA_ANGLE& angle )
267{
268 int ox, oy;
269
270 ox = *pX - cx;
271 oy = *pY - cy;
272
273 RotatePoint( &ox, &oy, angle );
274
275 *pX = ox + cx;
276 *pY = oy + cy;
277}
278
279
280void RotatePoint( double* pX, double* pY, double cx, double cy, const EDA_ANGLE& angle )
281{
282 double ox, oy;
283
284 ox = *pX - cx;
285 oy = *pY - cy;
286
287 RotatePoint( &ox, &oy, angle );
288
289 *pX = ox + cx;
290 *pY = oy + cy;
291}
292
293
294void RotatePoint( double* pX, double* pY, const EDA_ANGLE& aAngle )
295{
296 EDA_ANGLE angle = aAngle;
297 VECTOR2D pt;
298
299 angle.Normalize();
300
301 // Cheap and dirty optimizations for 0, 90, 180, and 270 degrees.
302 if( angle == ANGLE_0 )
303 {
304 pt = VECTOR2D( *pX, *pY );
305 }
306 else if( angle == ANGLE_90 ) /* sin = 1, cos = 0 */
307 {
308 pt = VECTOR2D( *pY, -*pX );
309 }
310 else if( angle == ANGLE_180 ) /* sin = 0, cos = -1 */
311 {
312 pt = VECTOR2D( -*pX, -*pY );
313 }
314 else if( angle == ANGLE_270 ) /* sin = -1, cos = 0 */
315 {
316 pt = VECTOR2D( -*pY, *pX );
317 }
318 else
319 {
320 double sinus = angle.Sin();
321 double cosinus = angle.Cos();
322
323 pt.x = ( *pY * sinus ) + ( *pX * cosinus );
324 pt.y = ( *pY * cosinus ) - ( *pX * sinus );
325 }
326
327 *pX = pt.x;
328 *pY = pt.y;
329}
330
331
332const VECTOR2D CalcArcCenter( const VECTOR2D& aStart, const VECTOR2D& aEnd,
333 const EDA_ANGLE& aAngle )
334{
335 EDA_ANGLE angle( aAngle );
336 VECTOR2D start = aStart;
337 VECTOR2D end = aEnd;
338
339 if( angle < ANGLE_0 )
340 {
341 std::swap( start, end );
342 angle = -angle;
343 }
344
345 if( angle > ANGLE_180 )
346 {
347 std::swap( start, end );
348 angle = ANGLE_360 - angle;
349 }
350
351 double chord = ( start - end ).EuclideanNorm();
352 double r = ( chord / 2.0 ) / ( angle / 2.0 ).Sin();
353 double d_squared = r * r - chord* chord / 4.0;
354 double d = 0.0;
355
356 if( d_squared > 0.0 )
357 d = sqrt( d_squared );
358
359 VECTOR2D vec2 = VECTOR2D(end - start).Resize( d );
360 VECTOR2D vc = VECTOR2D(end - start).Resize( chord / 2 );
361
362 RotatePoint( vec2, -ANGLE_90 );
363
364 return VECTOR2D( start + vc + vec2 );
365}
366
367
368const VECTOR2D CalcArcCenter( const VECTOR2D& aStart, const VECTOR2D& aMid, const VECTOR2D& aEnd )
369{
370 VECTOR2D center;
371
372 double yDelta_21 = aMid.y - aStart.y;
373 double xDelta_21 = aMid.x - aStart.x;
374 double yDelta_32 = aEnd.y - aMid.y;
375 double xDelta_32 = aEnd.x - aMid.x;
376
377 // This is a special case for aMid as the half-way point when aSlope = 0 and bSlope = inf
378 // or the other way around. In that case, the center lies in a straight line between
379 // aStart and aEnd
380 if( ( ( xDelta_21 == 0.0 ) && ( yDelta_32 == 0.0 ) ) ||
381 ( ( yDelta_21 == 0.0 ) && ( xDelta_32 == 0.0 ) ) )
382 {
383 center.x = ( aStart.x + aEnd.x ) / 2.0;
384 center.y = ( aStart.y + aEnd.y ) / 2.0 ;
385 return center;
386 }
387
388 // Prevent div=0 errors
389 if( xDelta_21 == 0.0 )
390 xDelta_21 = std::numeric_limits<double>::epsilon();
391
392 if( xDelta_32 == 0.0 )
393 xDelta_32 = -std::numeric_limits<double>::epsilon();
394
395 double aSlope = yDelta_21 / xDelta_21;
396 double bSlope = yDelta_32 / xDelta_32;
397
398 double daSlope = aSlope * VECTOR2D( 0.5 / yDelta_21, 0.5 / xDelta_21 ).EuclideanNorm();
399 double dbSlope = bSlope * VECTOR2D( 0.5 / yDelta_32, 0.5 / xDelta_32 ).EuclideanNorm();
400
401 if( aSlope == bSlope )
402 {
403 if( aStart == aEnd )
404 {
405 // This is a special case for a 360 degrees arc. In this case, the center is
406 // halfway between the midpoint and either end point.
407 center.x = ( aStart.x + aMid.x ) / 2.0;
408 center.y = ( aStart.y + aMid.y ) / 2.0 ;
409 return center;
410 }
411 else
412 {
413 // If the points are colinear, the center is at infinity, so offset
414 // the slope by a minimal amount
415 // Warning: This will induce a small error in the center location
416 aSlope += std::numeric_limits<double>::epsilon();
417 bSlope -= std::numeric_limits<double>::epsilon();
418 }
419 }
420#ifdef USE_ALTERNATE_CENTER_ALGO
421 // We can call ArcCenterFrom3Points from here because special cases are filtered.
422 CircleCenterFrom3Points( aStart, aMid, aEnd, &center );
423 return center;
424#endif
425
426 // Prevent divide by zero error
427 // a small value is used. std::numeric_limits<double>::epsilon() is too small and
428 // generate false results
429 if( aSlope == 0.0 )
430 aSlope = 1e-10;
431 if( bSlope == 0.0 )
432 bSlope = 1e-10;
433
434 // What follows is the calculation of the center using the slope of the two lines as well as
435 // the propagated error that occurs when rounding to the nearest nanometer. The error can be
436 // ±0.5 units but can add up to multiple nanometers after the full calculation is performed.
437 // All variables starting with `d` are the delta of that variable. This is approximately equal
438 // to the standard deviation.
439 // We ignore the possible covariance between variables. We also truncate our series expansion
440 // at the first term. These are reasonable assumptions as the worst-case scenario is that we
441 // underestimate the potential uncertainty, which would potentially put us back at the status
442 // quo.
443 double abSlopeStartEndY = aSlope * bSlope * ( aStart.y - aEnd.y );
444 double dabSlopeStartEndY = abSlopeStartEndY *
445 std::sqrt( ( daSlope / aSlope * daSlope / aSlope )
446 + ( dbSlope / bSlope * dbSlope / bSlope )
447 + ( M_SQRT1_2 / ( aStart.y - aEnd.y )
448 * M_SQRT1_2 / ( aStart.y - aEnd.y ) ) );
449
450 double bSlopeStartMidX = bSlope * ( aStart.x + aMid.x );
451 double dbSlopeStartMidX = bSlopeStartMidX * std::sqrt( ( dbSlope / bSlope * dbSlope / bSlope )
452 + ( M_SQRT1_2 / ( aStart.x + aMid.x )
453 * M_SQRT1_2 / ( aStart.x + aMid.x ) ) );
454
455 double aSlopeMidEndX = aSlope * ( aMid.x + aEnd.x );
456 double daSlopeMidEndX = aSlopeMidEndX * std::sqrt( ( daSlope / aSlope * daSlope / aSlope )
457 + ( M_SQRT1_2 / ( aMid.x + aEnd.x )
458 * M_SQRT1_2 / ( aMid.x + aEnd.x ) ) );
459
460 double twiceBASlopeDiff = 2 * ( bSlope - aSlope );
461 double dtwiceBASlopeDiff = 2 * std::sqrt( dbSlope * dbSlope + daSlope * daSlope );
462
463 double centerNumeratorX = abSlopeStartEndY + bSlopeStartMidX - aSlopeMidEndX;
464 double dCenterNumeratorX = std::sqrt( dabSlopeStartEndY * dabSlopeStartEndY
465 + dbSlopeStartMidX * dbSlopeStartMidX
466 + daSlopeMidEndX * daSlopeMidEndX );
467
468 double centerX = ( abSlopeStartEndY + bSlopeStartMidX - aSlopeMidEndX ) / twiceBASlopeDiff;
469 double dCenterX = centerX * std::sqrt( ( dCenterNumeratorX / centerNumeratorX *
470 dCenterNumeratorX / centerNumeratorX )
471 + ( dtwiceBASlopeDiff / twiceBASlopeDiff *
472 dtwiceBASlopeDiff / twiceBASlopeDiff ) );
473
474
475 double centerNumeratorY = ( ( aStart.x + aMid.x ) / 2.0 - centerX );
476 double dCenterNumeratorY = std::sqrt( 1.0 / 8.0 + dCenterX * dCenterX );
477
478 double centerFirstTerm = centerNumeratorY / aSlope;
479 double dcenterFirstTermY = centerFirstTerm * std::sqrt(
480 ( dCenterNumeratorY/ centerNumeratorY *
481 dCenterNumeratorY / centerNumeratorY )
482 + ( daSlope / aSlope * daSlope / aSlope ) );
483
484 double centerY = centerFirstTerm + ( aStart.y + aMid.y ) / 2.0;
485 double dCenterY = std::sqrt( dcenterFirstTermY * dcenterFirstTermY + 1.0 / 8.0 );
486
487 double rounded100CenterX = std::floor( ( centerX + 50.0 ) / 100.0 ) * 100.0;
488 double rounded100CenterY = std::floor( ( centerY + 50.0 ) / 100.0 ) * 100.0;
489 double rounded10CenterX = std::floor( ( centerX + 5.0 ) / 10.0 ) * 10.0;
490 double rounded10CenterY = std::floor( ( centerY + 5.0 ) / 10.0 ) * 10.0;
491
492 // The last step is to find the nice, round numbers near our baseline estimate and see if
493 // they are within our uncertainty range. If they are, then we use this round value as the
494 // true value. This is justified because ALL values within the uncertainty range are equally
495 // true. Using a round number will make sure that we are on a multiple of 1mil or 100nm
496 // when calculating centers.
497 if( std::abs( rounded100CenterX - centerX ) < dCenterX &&
498 std::abs( rounded100CenterY - centerY ) < dCenterY )
499 {
500 center.x = rounded100CenterX;
501 center.y = rounded100CenterY;
502 }
503 else if( std::abs( rounded10CenterX - centerX ) < dCenterX &&
504 std::abs( rounded10CenterY - centerY ) < dCenterY )
505 {
506 center.x = rounded10CenterX;
507 center.y = rounded10CenterY;
508 }
509 else
510 {
511 center.x = centerX;
512 center.y = centerY;
513 }
514
515
516 return center;
517}
518
519
520const VECTOR2I CalcArcCenter( const VECTOR2I& aStart, const VECTOR2I& aMid, const VECTOR2I& aEnd )
521{
522 VECTOR2D dStart( static_cast<double>( aStart.x ), static_cast<double>( aStart.y ) );
523 VECTOR2D dMid( static_cast<double>( aMid.x ), static_cast<double>( aMid.y ) );
524 VECTOR2D dEnd( static_cast<double>( aEnd.x ), static_cast<double>( aEnd.y ) );
525 VECTOR2D dCenter = CalcArcCenter( dStart, dMid, dEnd );
526
527 VECTOR2I iCenter;
528
529 iCenter.x = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() + 100 ),
530 dCenter.x,
531 double( std::numeric_limits<int>::max() - 100 ) ) );
532
533 iCenter.y = KiROUND( Clamp<double>( double( std::numeric_limits<int>::min() + 100 ),
534 dCenter.y,
535 double( std::numeric_limits<int>::max() - 100 ) ) );
536
537 return iCenter;
538}
539
540
541bool TestSegmentHitFast( const VECTOR2I& aRefPoint, const VECTOR2I& aStart, const VECTOR2I& aEnd,
542 int aDist )
543{
544 int xmin = std::min( aStart.x, aEnd.x );
545 int xmax = std::max( aStart.x, aEnd.x );
546 int ymin = std::min( aStart.y, aEnd.y );
547 int ymax = std::max( aStart.y, aEnd.y );
548 VECTOR2I delta = aStart - aRefPoint;
549
550 // Check if we are outside of the bounding box.
551 if( ( ymin - aRefPoint.y > aDist ) || ( aRefPoint.y - ymax > aDist ) )
552 return false;
553
554 if( ( xmin - aRefPoint.x > aDist ) || ( aRefPoint.x - xmax > aDist ) )
555 return false;
556
557 // Eliminate easy cases.
558 if( aStart.x == aEnd.x && aRefPoint.y > ymin && aRefPoint.y < ymax )
559 return std::abs( delta.x ) <= aDist;
560
561 if( aStart.y == aEnd.y && aRefPoint.x > xmin && aRefPoint.x < xmax )
562 return std::abs( delta.y ) <= aDist;
563
564 VECTOR2I::extended_type len = ( aEnd - aStart ).EuclideanNorm();
565 VECTOR2I::extended_type area = len * aDist;
566
567 return std::abs( ParallelogramArea( aStart, aRefPoint, aEnd ) ) <= area;
568}
EDA_ANGLE Normalize()
Definition: eda_angle.h:255
double Sin() const
Definition: eda_angle.h:212
double Cos() const
Definition: eda_angle.h:227
Definition: seg.h:42
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
static SEG::ecoord Square(int a)
Definition: seg.h:123
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:265
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:72
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:350
static constexpr EDA_ANGLE ANGLE_0
Definition: eda_angle.h:435
static constexpr EDA_ANGLE ANGLE_90
Definition: eda_angle.h:437
static constexpr EDA_ANGLE ANGLE_270
Definition: eda_angle.h:440
static constexpr EDA_ANGLE ANGLE_360
Definition: eda_angle.h:441
static constexpr EDA_ANGLE ANGLE_180
Definition: eda_angle.h:439
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:424
constexpr int delta
const VECTOR2I CalcArcMid(const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aMinArcAngle)
Return the middle point of an arc, half-way between aStart and aEnd.
Definition: trigo.cpp:208
bool TestSegmentHit(const VECTOR2I &aRefPoint, const VECTOR2I &aStart, const VECTOR2I &aEnd, int aDist)
Test if aRefPoint is with aDistance on the line defined by aStart and aEnd.
Definition: trigo.cpp:174
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Calculate the new point of coord coord pX, pY, for a rotation center 0, 0.
Definition: trigo.cpp:228
bool SegmentIntersectsSegment(const VECTOR2I &a_p1_l1, const VECTOR2I &a_p2_l1, const VECTOR2I &a_p1_l2, const VECTOR2I &a_p2_l2, VECTOR2I *aIntersectionPoint)
Test if two lines intersect.
Definition: trigo.cpp:106
bool IsPointOnSegment(const VECTOR2I &aSegStart, const VECTOR2I &aSegEnd, const VECTOR2I &aTestPoint)
Test if aTestPoint is on line defined by aSegStart and aSegEnd.
Definition: trigo.cpp:88
bool TestSegmentHitFast(const VECTOR2I &aRefPoint, const VECTOR2I &aStart, const VECTOR2I &aEnd, int aDist)
Test if a point hits a line segment within a given distance.
Definition: trigo.cpp:541
const VECTOR2D CalcArcCenter(const VECTOR2D &aStart, const VECTOR2D &aEnd, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:332
VECTOR2< T >::extended_type ParallelogramArea(const VECTOR2< T > &aPointA, const VECTOR2< T > &aPointB, const VECTOR2< T > &aPointC)
Calculate the area of a parallelogram defined by aPointA, aPointB, and aPointC.
Definition: trigo.h:289
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:128
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:85
VECTOR2< double > VECTOR2D
Definition: vector2d.h:587
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588