KiCad PCB EDA Suite
Loading...
Searching...
No Matches
seg.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) 2013 CERN
5 * @author Tomasz Wlostowski <[email protected]>
6 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
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
26#include <algorithm> // for min
27#include <geometry/seg.h>
28#include <math/util.h> // for rescale
29#include <math/vector2d.h> // for VECTOR2I, VECTOR2
30#include <trigo.h> // for RAD2DEG
31
32template <typename T>
33int sgn( T aVal )
34{
35 return ( T( 0 ) < aVal ) - ( aVal < T( 0 ) );
36}
37
38template <typename T>
39constexpr T sqrt_helper(T x, T lo, T hi)
40{
41 if (lo == hi)
42 return lo;
43
44 const T mid = (lo + hi + 1) / 2;
45 if (x / mid < mid)
46 return sqrt_helper<T>(x, lo, mid - 1);
47 else
48 return sqrt_helper(x, mid, hi);
49}
50
51template <typename T>
52constexpr T ct_sqrt(T x)
53{
54 return sqrt_helper<T>(x, 0, x / 2 + 1);
55}
56
57template <typename T>
58static constexpr T sqrt_max_typed = ct_sqrt( std::numeric_limits<T>::max() );
59
60template <typename T>
62{
63 T sqrt_max = sqrt_max_typed<T>;
64
65 if( x < 0 )
66 return sqrt_max;
67
68 T r = (T) std::sqrt( (double) x );
69
70 while( r < sqrt_max && r * r < x )
71 r++;
72
73 while( r > sqrt_max || r * r > x )
74 r--;
75
76 return r;
77}
78
79
81{
82 if( Intersects( aSeg ) )
83 return 0;
84
85 const VECTOR2I pts[4] =
86 {
87 aSeg.NearestPoint( A ) - A,
88 aSeg.NearestPoint( B ) - B,
89 NearestPoint( aSeg.A ) - aSeg.A,
90 NearestPoint( aSeg.B ) - aSeg.B
91 };
92
94
95 for( int i = 0; i < 4; i++ )
96 m = std::min( m, pts[i].SquaredEuclideanNorm() );
97
98 return m;
99}
100
101
102EDA_ANGLE SEG::Angle( const SEG& aOther ) const
103{
104 EDA_ANGLE thisAngle = EDA_ANGLE( A - B ).Normalize180();
105 EDA_ANGLE otherAngle = EDA_ANGLE( aOther.A - aOther.B ).Normalize180();
106
107 EDA_ANGLE angle = std::abs( ( thisAngle - otherAngle ).Normalize180() );
108
109 return std::min( ANGLE_180 - angle, angle );
110}
111
112
113const VECTOR2I SEG::NearestPoint( const SEG& aSeg ) const
114{
115 if( OPT_VECTOR2I p = Intersect( aSeg ) )
116 return *p;
117
118 const VECTOR2I pts_origin[4] =
119 {
120 aSeg.NearestPoint( A ),
121 aSeg.NearestPoint( B ),
122 NearestPoint( aSeg.A ),
123 NearestPoint( aSeg.B )
124 };
125
126
127 const VECTOR2I* pts_out[4] =
128 {
129 &A,
130 &B,
131 &pts_origin[2],
132 &pts_origin[3]
133 };
134
135 const ecoord pts_dist[4] =
136 {
137 ( pts_origin[0] - A ).SquaredEuclideanNorm(),
138 ( pts_origin[1] - B ).SquaredEuclideanNorm(),
139 ( pts_origin[2] - aSeg.A ).SquaredEuclideanNorm(),
140 ( pts_origin[3] - aSeg.B ).SquaredEuclideanNorm()
141 };
142
143 int min_i = 0;
144
145 for( int i = 0; i < 4; i++ )
146 {
147 if( pts_dist[i] < pts_dist[min_i] )
148 min_i = i;
149 }
150
151 return *pts_out[min_i];
152}
153
154
155bool SEG::NearestPoints( const SEG& aSeg, VECTOR2I& aPtA, VECTOR2I& aPtB, int64_t& aDistSq ) const
156{
157 if( OPT_VECTOR2I p = Intersect( aSeg ) )
158 {
159 aPtA = aPtB = *p;
160 aDistSq = 0;
161
162 return true;
163 }
164
165 const VECTOR2I pts_origin[4] =
166 {
167 aSeg.NearestPoint( A ),
168 aSeg.NearestPoint( B ),
169 NearestPoint( aSeg.A ),
170 NearestPoint( aSeg.B )
171 };
172
173 const VECTOR2I* pts_a_out[4] =
174 {
175 &A,
176 &B,
177 &pts_origin[2],
178 &pts_origin[3]
179 };
180
181 const VECTOR2I* pts_b_out[4] =
182 {
183 &pts_origin[0],
184 &pts_origin[1],
185 &aSeg.A,
186 &aSeg.B
187 };
188
189 const ecoord pts_dist[4] =
190 {
191 ( pts_origin[0] - A ).SquaredEuclideanNorm(),
192 ( pts_origin[1] - B ).SquaredEuclideanNorm(),
193 ( pts_origin[2] - aSeg.A ).SquaredEuclideanNorm(),
194 ( pts_origin[3] - aSeg.B ).SquaredEuclideanNorm()
195 };
196
197 int min_i = 0;
198
199 for( int i = 0; i < 4; i++ )
200 {
201 if( pts_dist[i] < pts_dist[min_i] )
202 min_i = i;
203 }
204
205 aPtA = *pts_a_out[min_i];
206 aPtB = *pts_b_out[min_i];
207 aDistSq = pts_dist[min_i];
208
209 return true;
210}
211
212
213bool SEG::checkCollinearOverlap( const SEG& aSeg, bool useXAxis, bool aIgnoreEndpoints, VECTOR2I* aPt ) const
214{
215 // Extract coordinates based on the chosen axis
216 int seg1_start, seg1_end, seg2_start, seg2_end;
217 int coord1_start, coord1_end; // For calculating other axis coordinate
218
219 if( useXAxis )
220 {
221 seg1_start = A.x; seg1_end = B.x;
222 seg2_start = aSeg.A.x; seg2_end = aSeg.B.x;
223 coord1_start = A.y; coord1_end = B.y;
224 }
225 else
226 {
227 seg1_start = A.y; seg1_end = B.y;
228 seg2_start = aSeg.A.y; seg2_end = aSeg.B.y;
229 coord1_start = A.x; coord1_end = B.x;
230 }
231
232 // Find segment ranges on the projection axis
233 const int seg1_min = std::min( seg1_start, seg1_end );
234 const int seg1_max = std::max( seg1_start, seg1_end );
235 const int seg2_min = std::min( seg2_start, seg2_end );
236 const int seg2_max = std::max( seg2_start, seg2_end );
237
238 // Check for overlap
239 const bool overlaps = seg1_max >= seg2_min && seg2_max >= seg1_min;
240 if( !overlaps )
241 return false;
242
243 // Check if intersection is only at endpoints when aIgnoreEndpoints is true
244 if( aIgnoreEndpoints )
245 {
246 // Calculate overlap region
247 const int overlap_start = std::max( seg1_min, seg2_min );
248 const int overlap_end = std::min( seg1_max, seg2_max );
249
250 // If overlap region has zero length, segments only touch at endpoint
251 if( overlap_start == overlap_end )
252 {
253 // Check if this endpoint touching involves actual segment endpoints
254 // (not just projected endpoints due to min/max calculation)
255 bool isEndpointTouch = false;
256
257 // Check if the touch point corresponds to actual segment endpoints
258 if( overlap_start == seg1_min || overlap_start == seg1_max )
259 {
260 // Touch point is at seg1's endpoint, check if it's also at seg2's endpoint
261 if( overlap_start == seg2_min || overlap_start == seg2_max )
262 {
263 isEndpointTouch = true;
264 }
265 }
266
267 if( isEndpointTouch )
268 return false; // Ignore endpoint-only intersection
269 }
270 }
271
272 // Calculate intersection point if requested
273 if( aPt )
274 {
275 // Find midpoint of overlap region
276 const int overlap_start = std::max( seg1_min, seg2_min );
277 const int overlap_end = std::min( seg1_max, seg2_max );
278 const int intersection_proj = ( overlap_start + overlap_end ) / 2;
279
280 // Calculate corresponding coordinate on the other axis
281 int intersection_other;
282 if( seg1_end != seg1_start )
283 {
284 // Use this segment's line equation to find other coordinate
285 intersection_other = coord1_start + static_cast<int>(
286 rescale( intersection_proj - seg1_start, coord1_end - coord1_start, seg1_end - seg1_start ) );
287 }
288 else
289 {
290 // Degenerate segment (point) or perpendicular to projection axis
291 intersection_other = coord1_start;
292 }
293
294 // Set result based on projection axis
295 if( useXAxis )
296 *aPt = VECTOR2I( intersection_proj, intersection_other );
297 else
298 *aPt = VECTOR2I( intersection_other, intersection_proj );
299 }
300
301 return true;
302}
303
304
305bool SEG::intersects( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines, VECTOR2I* aPt ) const
306{
307 // Quick rejection: check if segment bounding boxes overlap
308 // (Skip for line mode since infinite lines can intersect anywhere)
309 if( !aLines )
310 {
311 const int this_min_x = std::min( A.x, B.x );
312 const int this_max_x = std::max( A.x, B.x );
313 const int this_min_y = std::min( A.y, B.y );
314 const int this_max_y = std::max( A.y, B.y );
315
316 const int other_min_x = std::min( aSeg.A.x, aSeg.B.x );
317 const int other_max_x = std::max( aSeg.A.x, aSeg.B.x );
318 const int other_min_y = std::min( aSeg.A.y, aSeg.B.y );
319 const int other_max_y = std::max( aSeg.A.y, aSeg.B.y );
320
321 if( this_max_x < other_min_x || other_max_x < this_min_x ||
322 this_max_y < other_min_y || other_max_y < this_min_y )
323 {
324 return false;
325 }
326 }
327
328 // Calculate direction vectors and offset vector using VECTOR2 operations
329 // Using parametric form: P₁ = A + t*dir1, P₂ = aSeg.A + s*dir2
330 const VECTOR2L dir1 = VECTOR2L( B ) - A; // direction vector e
331 const VECTOR2L dir2 = VECTOR2L( aSeg.B ) - aSeg.A; // direction vector f
332 const VECTOR2L offset = VECTOR2L( aSeg.A ) - A; // offset vector ac
333 const ecoord determinant = dir2.Cross( dir1 );
334
335 // Handle parallel/collinear case
336 if( determinant == 0 )
337 {
338 // Check if lines are collinear (not just parallel) using cross product
339 // Lines are collinear if offset vector is also parallel to direction vector
340 const ecoord collinear_test = dir1.Cross( offset );
341
342 if( collinear_test != 0 )
343 return false; // Parallel but not collinear
344
345 // Lines are collinear - for infinite lines, they always intersect
346 if( aLines )
347 {
348 // For infinite collinear lines, intersection point is ambiguous
349 // Use the midpoint between the two segment start points as a reasonable choice
350 if( aPt )
351 {
352 // If aSeg is degenerate (point), use its start point
353 if( aSeg.A == aSeg.B )
354 {
355 *aPt = aSeg.A;
356 }
357 else if( A == B )
358 { // If this segment is degenerate (point), use its start point
359 *aPt = A;
360 }
361 else
362 {
363 const VECTOR2I midpoint = ( A + aSeg.A ) / 2;
364 *aPt = midpoint;
365 }
366 }
367 return true;
368 }
369
370 // For segments, check overlap using the axis with larger coordinate range
371 const bool use_x_axis = std::abs( dir1.x ) >= std::abs( dir1.y );
372 return checkCollinearOverlap( aSeg, use_x_axis, aIgnoreEndpoints, aPt );
373 }
374
375 // param2_num = f × ac (parameter for second segment: s = p/d)
376 // param1_num = e × ac (parameter for first segment: t = q/d)
377 const ecoord param2_num = dir2.Cross( offset );
378 const ecoord param1_num = dir1.Cross( offset );
379
380 // For segments (not infinite lines), check if intersection is within both segments
381 if( !aLines )
382 {
383 // Parameters must be in [0,1] for intersection within segments
384 // Since we're comparing t = q/d and s = p/d to [0,1], we need to handle sign of d
385 if( determinant > 0 )
386 {
387 // d > 0: check 0 ≤ q ≤ d and 0 ≤ p ≤ d
388 if( param1_num < 0 || param1_num > determinant ||
389 param2_num < 0 || param2_num > determinant )
390 return false;
391 }
392 else
393 {
394 // d < 0: check d ≤ q ≤ 0 and d ≤ p ≤ 0
395 if( param1_num > 0 || param1_num < determinant ||
396 param2_num > 0 || param2_num < determinant )
397 return false;
398 }
399
400 // Optionally exclude endpoint intersections (when segments share vertices)
401 if( aIgnoreEndpoints &&
402 ( param1_num == 0 || param1_num == determinant ) &&
403 ( param2_num == 0 || param2_num == determinant ) )
404 {
405 return false;
406 }
407 }
408
409 if( aPt )
410 {
411 // Use parametric equation: intersection = aSeg.A + (q/d) * f
412 const VECTOR2L scaled_dir2( rescale( param1_num, dir2.x, determinant ),
413 rescale( param1_num, dir2.y, determinant ) );
414 const VECTOR2L result = VECTOR2L( aSeg.A ) + scaled_dir2;
415
416 // Verify result fits in coordinate type range
417 constexpr ecoord max_coord = std::numeric_limits<VECTOR2I::coord_type>::max();
418 constexpr ecoord min_coord = std::numeric_limits<VECTOR2I::coord_type>::min();
419
420 if( result.x > max_coord || result.x < min_coord ||
421 result.y > max_coord || result.y < min_coord )
422 {
423 return false; // Intersection exists but coordinates overflow
424 }
425
426 *aPt = VECTOR2I( static_cast<int>( result.x ), static_cast<int>( result.y ) );
427 }
428
429 return true;
430}
431
432
433bool SEG::Intersects( const SEG& aSeg ) const
434{
435 return intersects( aSeg );
436}
437
438
439OPT_VECTOR2I SEG::Intersect( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines ) const
440{
441 VECTOR2I ip;
442
443 if( intersects( aSeg, aIgnoreEndpoints, aLines, &ip ) )
444 return ip;
445 else
446 return OPT_VECTOR2I();
447}
448
449
450bool SEG::IntersectsLine( double aSlope, double aOffset, VECTOR2I& aIntersection ) const
451{
452 const VECTOR2L segA( A );
453 const VECTOR2L segB( B );
454 const VECTOR2L segDir = segB - segA;
455
456 // Handle vertical segment case
457 if( segDir.x == 0 )
458 {
459 // Vertical segment: x = A.x, find y on the line
460 const double intersect_y = aSlope * A.x + aOffset;
461 const int intersect_y_int = KiROUND( intersect_y );
462
463 // Check if intersection is within segment's y-range
464 const int seg_min_y = std::min( A.y, B.y );
465 const int seg_max_y = std::max( A.y, B.y );
466
467 if( intersect_y_int >= seg_min_y && intersect_y_int <= seg_max_y )
468 {
469 aIntersection = VECTOR2I( A.x, intersect_y_int );
470 return true;
471 }
472 return false;
473 }
474
475 const VECTOR2L lineDir( 1000, static_cast<ecoord>( aSlope * 1000 ) );
476 const ecoord cross_product = segDir.Cross( lineDir );
477
478 if( cross_product == 0 )
479 {
480 // Parallel lines - check if segment lies on the line
481 const double expected_y = aSlope * A.x + aOffset;
482 const double diff = std::abs( A.y - expected_y );
483
484 if( diff < 0.5 )
485 {
486 // Collinear: segment lies on the line, return midpoint
487 aIntersection = ( A + B ) / 2;
488 return true;
489 }
490
491 return false; // Parallel but not collinear
492 }
493
494 // Find intersection using parametric equations
495 // Segment: P = segA + t * segDir
496 // Line: y = aSlope * x + aOffset
497 //
498 // At intersection: segA.y + t * segDir.y = aSlope * (segA.x + t * segDir.x) + aOffset
499 // Solving for t: t = (aSlope * segA.x + aOffset - segA.y) / (segDir.y - aSlope * segDir.x)
500
501 const double numerator = aSlope * segA.x + aOffset - segA.y;
502 const double denominator = segDir.y - aSlope * segDir.x;
503
504 const double t = numerator / denominator;
505
506 // Check if intersection is within segment bounds
507 if( t >= 0.0 && t <= 1.0 )
508 {
509 const double intersect_x = segA.x + t * segDir.x;
510 const double intersect_y = segA.y + t * segDir.y;
511
512 aIntersection = VECTOR2I( KiROUND( intersect_x ), KiROUND( intersect_y ) );
513 return true;
514 }
515
516 return false;
517}
518
519
521{
522 VECTOR2I slope( B - A );
523 VECTOR2I endPoint = slope.Perpendicular() + aP;
524
525 return SEG( aP, endPoint );
526}
527
528
529SEG SEG::ParallelSeg( const VECTOR2I& aP ) const
530{
531 VECTOR2I slope( B - A );
532 VECTOR2I endPoint = slope + aP;
533
534 return SEG( aP, endPoint );
535}
536
537
538bool SEG::Collide( const SEG& aSeg, int aClearance, int* aActual ) const
539{
540 // Handle negative clearance
541 if( aClearance < 0 )
542 {
543 if( aActual )
544 *aActual = 0;
545
546 return false;
547 }
548
549 // Check for exact intersection first
550 if( intersects( aSeg, false, false ) )
551 {
552 if( aActual )
553 *aActual = 0;
554
555 return true;
556 }
557
558 const ecoord clearance_sq = static_cast<ecoord>( aClearance ) * aClearance;
559 ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
560
561 auto checkDistance = [&]( ecoord dist, ecoord& min_dist ) -> bool
562 {
563 if( dist == 0 )
564 {
565 if( aActual )
566 *aActual = 0;
567
568 return true;
569 }
570
571 min_dist = std::min( min_dist, dist );
572 return false; // Continue checking
573 };
574
575 // There are 4 points to check: start and end of this segment, and
576 // start and end of the other segment.
577 if( checkDistance( SquaredDistance( aSeg.A ), min_dist_sq ) ||
578 checkDistance( SquaredDistance( aSeg.B ), min_dist_sq ) ||
579 checkDistance( aSeg.SquaredDistance( A ), min_dist_sq ) ||
580 checkDistance( aSeg.SquaredDistance( B ), min_dist_sq ) )
581 {
582 return true;
583 }
584
585 if( min_dist_sq < clearance_sq )
586 {
587 if( aActual )
588 *aActual = static_cast<int>( isqrt( min_dist_sq ) );
589
590 return true;
591 }
592
593 if( aActual )
594 *aActual = static_cast<int>( isqrt( min_dist_sq ) );
595
596 return false;
597}
598
599
600bool SEG::Contains( const VECTOR2I& aP ) const
601{
602 return SquaredDistance( aP ) <= 3;
603}
604
605
606const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const
607{
608 // Inlined for performance reasons
609 VECTOR2L d;
610 d.x = static_cast<int64_t>( B.x ) - A.x;
611 d.y = static_cast<int64_t>( B.y ) - A.y;
612
613 ecoord l_squared( d.x * d.x + d.y * d.y );
614
615 if( l_squared == 0 )
616 return A;
617
618 // Inlined for performance reasons
619 VECTOR2L pa;
620 pa.x = static_cast<int64_t>( aP.x ) - A.x;
621 pa.y = static_cast<int64_t>( aP.y ) - A.y;
622
623 ecoord t = d.Dot( pa );
624
625 if( t < 0 )
626 return A;
627 else if( t > l_squared )
628 return B;
629
630 ecoord xp = rescale( t, (ecoord) d.x, l_squared );
631 ecoord yp = rescale( t, (ecoord) d.y, l_squared );
632
633 return VECTOR2<ecoord>( A.x + xp, A.y + yp );
634}
635
636
637const VECTOR2I SEG::ReflectPoint( const VECTOR2I& aP ) const
638{
639 VECTOR2I d = B - A;
640 VECTOR2I::extended_type l_squared = d.Dot( d );
641 VECTOR2I::extended_type t = d.Dot( aP - A );
643
644 if( !l_squared )
645 {
646 c = aP;
647 }
648 else
649 {
650 c.x = A.x + rescale( t, static_cast<VECTOR2I::extended_type>( d.x ), l_squared );
651 c.y = A.y + rescale( t, static_cast<VECTOR2I::extended_type>( d.y ), l_squared );
652 }
653
654 return VECTOR2<ecoord>( 2 * c.x - aP.x, 2 * c.y - aP.y );
655}
656
657
659{
660 VECTOR2I d = B - A;
661 ecoord l_squared = d.Dot( d );
662
663 if( l_squared == 0 )
664 return A;
665
666 ecoord t = d.Dot( aP - A );
667
668 ecoord xp = rescale( t, ecoord{ d.x }, l_squared );
669 ecoord yp = rescale( t, ecoord{ d.y }, l_squared );
670
671 return VECTOR2<ecoord>( A.x + xp, A.y + yp );
672}
673
674
675int SEG::Distance( const SEG& aSeg ) const
676{
677 return int( isqrt( SquaredDistance( aSeg ) ) );
678}
679
680
681int SEG::Distance( const VECTOR2I& aP ) const
682{
683 return int( isqrt( SquaredDistance( aP ) ) );
684}
685
686
688{
689 VECTOR2<ecoord> ab( ecoord( B.x ) - A.x, ecoord( B.y ) - A.y );
690 VECTOR2<ecoord> ap( ecoord( aP.x ) - A.x, ecoord( aP.y ) - A.y );
691
692 ecoord e = ap.Dot( ab );
693
694 if( e <= 0 )
695 return ap.SquaredEuclideanNorm();
696
698
699 if( e >= f )
700 {
701 VECTOR2<ecoord> bp( ecoord( aP.x ) - B.x, ecoord( aP.y ) - B.y );
702
703 return bp.Dot( bp );
704 }
705
706 const double g = ap.SquaredEuclideanNorm() - ( double( e ) * e ) / f;
707
708 // The only way g can be negative is if there was a rounding error since
709 // e is the projection of aP onto ab and therefore cannot be greater than
710 // the length of ap and f is guaranteed to be greater than e, meaning
711 // e * e / f cannot be greater than ap.SquaredEuclideanNorm()
712 if( g < 0 || g > static_cast<double>( std::numeric_limits<ecoord>::max() ) )
713 return 0;
714
715 return KiROUND<double, ecoord>( g );
716}
717
718
719int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const
720{
721 ecoord p = ecoord{ A.y } - B.y;
722 ecoord q = ecoord{ B.x } - A.x;
723 ecoord r = -p * A.x - q * A.y;
724 ecoord l = p * p + q * q;
725 ecoord det = p * aP.x + q * aP.y + r;
726 ecoord dist_sq = 0;
727
728 if( l > 0 )
729 {
730 dist_sq = rescale( det, det, l );
731 }
732
733 ecoord dist = isqrt( dist_sq );
734
735 return static_cast<int>( aDetermineSide ? sgn( det ) * dist : std::abs( dist ) );
736}
737
738
739bool SEG::mutualDistanceSquared( const SEG& aSeg, ecoord& aD1, ecoord& aD2 ) const
740{
741 SEG a( *this );
742 SEG b( aSeg );
743
744 if( a.SquaredLength() < b.SquaredLength() )
745 std::swap(a, b);
746
747 ecoord p = ecoord{ a.A.y } - a.B.y;
748 ecoord q = ecoord{ a.B.x } - a.A.x;
749 ecoord r = -p * a.A.x - q * a.A.y;
750
751 ecoord l = p * p + q * q;
752
753 if( l == 0 )
754 return false;
755
756 ecoord det1 = p * b.A.x + q * b.A.y + r;
757 ecoord det2 = p * b.B.x + q * b.B.y + r;
758
759 ecoord dsq1 = rescale( det1, det1, l );
760 ecoord dsq2 = rescale( det2, det2, l );
761
762 aD1 = sgn( det1 ) * dsq1;
763 aD2 = sgn( det2 ) * dsq2;
764
765 return true;
766}
767
768bool SEG::ApproxCollinear( const SEG& aSeg, int aDistanceThreshold ) const
769{
770 ecoord thresholdSquared = Square( aDistanceThreshold );
771 ecoord d1_sq, d2_sq;
772
773 if( !mutualDistanceSquared( aSeg, d1_sq, d2_sq ) )
774 return false;
775
776 return std::abs( d1_sq ) <= thresholdSquared && std::abs( d2_sq ) <= thresholdSquared;
777}
778
779
780bool SEG::ApproxParallel( const SEG& aSeg, int aDistanceThreshold ) const
781{
782 ecoord thresholdSquared = Square( aDistanceThreshold );
783 ecoord d1_sq, d2_sq;
784
785 if( ! mutualDistanceSquared( aSeg, d1_sq, d2_sq ) )
786 return false;
787
788 return std::abs( d1_sq - d2_sq ) <= thresholdSquared;
789}
790
791
792bool SEG::ApproxPerpendicular( const SEG& aSeg ) const
793{
794 SEG perp = PerpendicularSeg( A );
795
796 return aSeg.ApproxParallel( perp );
797}
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
Definition: box2.h:990
EDA_ANGLE Normalize180()
Definition: eda_angle.h:268
Definition: seg.h:42
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:637
VECTOR2I A
Definition: seg.h:49
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.cpp:719
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:80
bool IntersectsLine(double aSlope, double aOffset, VECTOR2I &aIntersection) const
Check if this segment intersects a line defined by slope aSlope and offset aOffset.
Definition: seg.cpp:450
bool intersects(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false, VECTOR2I *aPt=nullptr) const
Definition: seg.cpp:305
VECTOR2I::extended_type ecoord
Definition: seg.h:44
VECTOR2I B
Definition: seg.h:50
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:606
bool Intersects(const SEG &aSeg) const
Definition: seg.cpp:433
bool checkCollinearOverlap(const SEG &aSeg, bool useXAxis, bool aIgnoreEndpoints, VECTOR2I *aPt) const
Definition: seg.cpp:213
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:439
static SEG::ecoord Square(int a)
Definition: seg.h:123
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:538
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:780
SEG()
Create an empty (0, 0) segment.
Definition: seg.h:55
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:529
ecoord SquaredLength() const
Definition: seg.h:348
bool ApproxPerpendicular(const SEG &aSeg) const
Definition: seg.cpp:792
bool ApproxCollinear(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:768
bool mutualDistanceSquared(const SEG &aSeg, ecoord &aD1, ecoord &aD2) const
Definition: seg.cpp:739
bool NearestPoints(const SEG &aSeg, VECTOR2I &aPtA, VECTOR2I &aPtB, int64_t &aDistSq) const
Compute closest points between this segment and aSeg.
Definition: seg.cpp:155
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:675
bool Contains(const SEG &aSeg) const
Definition: seg.h:324
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:658
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition: seg.cpp:520
EDA_ANGLE Angle(const SEG &aOther) const
Determine the smallest angle between two segments.
Definition: seg.cpp:102
constexpr extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:546
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:307
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:76
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:73
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
constexpr extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:554
static coord2_t cross_product(const VECTOR2I &O, const VECTOR2I &A, const VECTOR2I &B)
Definition: convex_hull.cpp:79
static constexpr EDA_ANGLE ANGLE_180
Definition: eda_angle.h:415
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:400
constexpr T ct_sqrt(T x)
Definition: seg.cpp:52
constexpr T sqrt_helper(T x, T lo, T hi)
Definition: seg.cpp:39
static constexpr T sqrt_max_typed
Definition: seg.cpp:58
int sgn(T aVal)
Definition: seg.cpp:33
T isqrt(T x)
Definition: seg.cpp:61
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:139
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695
VECTOR2< int64_t > VECTOR2L
Definition: vector2d.h:696