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