KiCad PCB EDA Suite
Loading...
Searching...
No Matches
test_segment.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) 2017 CERN
5 * @author Alejandro García Montoro <[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
27#include <boost/test/data/test_case.hpp>
28
29#include <geometry/seg.h>
30
31namespace
32{
33
42bool SegCollideCorrect( const SEG& aSegA, const SEG& aSegB, int aClearance, bool aExp )
43{
44 const bool AtoB = aSegA.Collide( aSegB, aClearance );
45 const bool BtoA = aSegB.Collide( aSegA, aClearance );
46
47 const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
48
49 if( AtoB != BtoA )
50 {
51 std::stringstream ss;
52 ss << "Segment collision is not the same in both directions: expected " << aExp << ", got "
53 << AtoB << " & " << BtoA;
54 BOOST_TEST_INFO( ss.str() );
55 }
56 else if( !ok )
57 {
58 std::stringstream ss;
59 ss << "Collision incorrect: expected " << aExp << ", got " << AtoB;
60 BOOST_TEST_INFO( ss.str() );
61 }
62
63 return ok;
64}
65
66
74bool SegDistanceCorrect( const SEG& aSegA, const SEG& aSegB, int aExp )
75{
76 const int AtoB = aSegA.Distance( aSegB );
77 const int BtoA = aSegB.Distance( aSegA );
78
79 bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
80
81 if( AtoB != BtoA )
82 {
83 std::stringstream ss;
84 ss << "Segment distance is not the same in both directions: expected " << aExp << ", got "
85 << AtoB << " & " << BtoA;
86 BOOST_TEST_INFO( ss.str() );
87 }
88 else if( !ok )
89 {
90 std::stringstream ss;
91 ss << "Distance incorrect: expected " << aExp << ", got " << AtoB;
92 BOOST_TEST_INFO( ss.str() );
93 }
94
95 // Sanity check: the collision should be consistent with the distance
96 ok = ok && SegCollideCorrect( aSegA, aSegB, 0, aExp == 0 );
97
98 return ok;
99}
100
108bool SegVecDistanceCorrect( const SEG& aSeg, const VECTOR2I& aVec, int aExp )
109{
110 const SEG::ecoord squaredDistance = aSeg.SquaredDistance( aVec );
111 BOOST_REQUIRE( squaredDistance >= 0 );
112
113 const int dist = aSeg.Distance( aVec );
114
115 bool ok = ( dist == aExp );
116
117 if( !ok )
118 {
119 std::stringstream ss;
120 ss << "Distance incorrect: expected " << aExp << ", got " << dist;
121 BOOST_TEST_INFO( ss.str() );
122 }
123
124 return ok;
125}
126
134bool SegCollinearCorrect( const SEG& aSegA, const SEG& aSegB, bool aExp )
135{
136 const bool AtoB = aSegA.Collinear( aSegB );
137 const bool BtoA = aSegB.Collinear( aSegA );
138
139 const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
140
141 if( AtoB != BtoA )
142 {
143 std::stringstream ss;
144 ss << "Segment collinearity is not the same in both directions: expected " << aExp
145 << ", got " << AtoB << " & " << BtoA;
146 BOOST_TEST_INFO( ss.str() );
147 }
148 else if( !ok )
149 {
150 std::stringstream ss;
151 ss << "Collinearity incorrect: expected " << aExp << ", got " << AtoB;
152 BOOST_TEST_INFO( ss.str() );
153 }
154
155 return ok;
156}
157
166bool SegParallelCorrect( const SEG& aSegA, const SEG& aSegB, bool aExp )
167{
168 const bool AtoB = aSegA.ApproxParallel( aSegB );
169 const bool BtoA = aSegB.ApproxParallel( aSegA );
170
171 const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
172
173 if( AtoB != BtoA )
174 {
175 std::stringstream ss;
176 ss << "Segment parallelism is not the same in both directions: expected " << aExp
177 << ", got AtoB: " << AtoB << " BtoA:" << BtoA;
178 BOOST_TEST_INFO( ss.str() );
179 }
180 else if( !ok )
181 {
182 std::stringstream ss;
183 ss << "Parallelism incorrect: expected " << aExp << ", got " << AtoB;
184 BOOST_TEST_INFO( ss.str() );
185 }
186
187 return ok;
188}
189
198bool SegPerpendicularCorrect( const SEG& aSegA, const SEG& aSegB, bool aExp )
199{
200 const bool AtoB = aSegA.ApproxPerpendicular( aSegB );
201 const bool BtoA = aSegB.ApproxPerpendicular( aSegA );
202
203 const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
204
205 if( AtoB != BtoA )
206 {
207 std::stringstream ss;
208 ss << "Segment perpendicularity is not the same in both directions: expected " << aExp
209 << ", got AtoB: " << AtoB << " BtoA:" << BtoA;
210 BOOST_TEST_INFO( ss.str() );
211 }
212 else if( !ok )
213 {
214 std::stringstream ss;
215 ss << "Perpendicularity incorrect: expected " << aExp << ", got " << AtoB;
216 BOOST_TEST_INFO( ss.str() );
217 }
218
219 return ok;
220}
221
222} // namespace
223
224BOOST_AUTO_TEST_SUITE( Segment )
225
226
230BOOST_AUTO_TEST_CASE( EndpointCtorMod )
231{
232 const VECTOR2I pointA{ 10, 20 };
233 const VECTOR2I pointB{ 100, 200 };
234
235 // Build a segment referencing the previous points
236 SEG segment( pointA, pointB );
237
238 BOOST_CHECK_EQUAL( pointA, VECTOR2I( 10, 20 ) );
239 BOOST_CHECK_EQUAL( pointB, VECTOR2I( 100, 200 ) );
240
241 // Modify the ends of the segments
242 segment.A += VECTOR2I( 10, 10 );
243 segment.B += VECTOR2I( 100, 100 );
244
245 // Check that the ends in segment are modified
246 BOOST_CHECK_EQUAL( segment.A, VECTOR2I( 20, 30 ) );
247 BOOST_CHECK_EQUAL( segment.B, VECTOR2I( 200, 300 ) );
248}
249
251{
255};
256
257
258// clang-format off
259static const std::vector<SEG_SEG_DISTANCE_CASE> seg_seg_dist_cases = {
260 {
261 "Parallel, 10 apart",
262 { { 0, 0 }, { 10, 0 } },
263 { { 0, 10 }, { 10, 10 } },
264 10,
265 },
266 {
267 "Non-parallel, 10 apart",
268 { { 0, -5 }, { 10, 0 } },
269 { { 0, 10 }, { 10, 10 } },
270 10,
271 },
272 {
273 "Co-incident",
274 { { 0, 0 }, { 30, 0 } },
275 { { 10, 0 }, { 20, 0 } },
276 0,
277 },
278 {
279 "Crossing",
280 { { 0, -10 }, { 0, 10 } },
281 { { -20, 0 }, { 20, 0 } },
282 0,
283 },
284 {
285 "T-junction",
286 { { 0, -10 }, { 0, 10 } },
287 { { -20, 0 }, { 0, 0 } },
288 0,
289 },
290 {
291 "T-junction (no touch)",
292 { { 0, -10 }, { 0, 10 } },
293 { { -20, 0 }, { -2, 0 } },
294 2,
295 },
296};
297// clang-format on
298
299
300BOOST_DATA_TEST_CASE( SegSegDistance, boost::unit_test::data::make( seg_seg_dist_cases ), c )
301{
302 BOOST_CHECK_PREDICATE( SegDistanceCorrect, ( c.m_seg_a )( c.m_seg_b )( c.m_exp_dist ) );
303}
304
305
307{
311};
312
313
314// clang-format off
315static const std::vector<SEG_VECTOR_DISTANCE_CASE> seg_vec_dist_cases = {
316 {
317 "On endpoint",
318 { { 0, 0 }, { 10, 0 } },
319 { 0, 0 },
320 0,
321 },
322 {
323 "On segment",
324 { { 0, 0 }, { 10, 0 } },
325 { 3, 0 },
326 0,
327 },
328 {
329 "At side",
330 { { 0, 0 }, { 10, 0 } },
331 { 3, 2 },
332 2,
333 },
334 {
335 "At end (collinear)",
336 { { 0, 0 }, { 10, 0 } },
337 { 12, 0 },
338 2,
339 },
340 {
341 "At end (not collinear)",
342 { { 0, 0 }, { 1000, 0 } },
343 { 1000 + 200, 200 },
344 282, // sqrt(200^2 + 200^2) = 282.8, rounded to nearest
345 },
346 {
347 "Issue 18473 (inside hit with rounding error)",
348 { { 187360000, 42510000 }, { 105796472, 42510000 } },
349 { 106645000, 42510000 },
350 0,
351 },
352 {
353 "Straight line x distance",
354 { { 187360000, 42510000 }, { 105796472, 42510000 } },
355 { 197360000, 42510000 },
356 10000000,
357 },
358 {
359 "Straight line -x distance",
360 { { 187360000, 42510000 }, { 105796472, 42510000 } },
361 { 104796472, 42510000 },
362 1000000,
363 },
364};
365// clang-format on
366
367
368BOOST_DATA_TEST_CASE( SegVecDistance, boost::unit_test::data::make( seg_vec_dist_cases ), c )
369{
370 BOOST_CHECK_PREDICATE( SegVecDistanceCorrect, ( c.m_seg )( c.m_vec )( c.m_exp_dist ) );
371}
372
373
379{
384};
385
386
387// clang-format off
388static const std::vector<SEG_SEG_COLLIDE_CASE> seg_seg_coll_cases = {
389 {
390 "Parallel, 10 apart, 5 clear",
391 { { 0, 0 }, { 10, 0 } },
392 { { 0, 10 }, { 10, 10 } },
393 5,
394 false,
395 },
396 {
397 "Parallel, 10 apart, 10 clear",
398 { { 0, 0 }, { 10, 0 } },
399 { { 0, 10 }, { 10, 10 } },
400 10,
401 false,
402 },
403 {
404 "Parallel, 10 apart, 11 clear",
405 { { 0, 0 }, { 10, 0 } },
406 { { 0, 10 }, { 10, 10 } },
407 11,
408 true,
409 },
410 {
411 "T-junction, 2 apart, 2 clear",
412 { { 0, -10 }, { 0, 0 } },
413 { { -20, 0 }, { -2, 0 } },
414 2,
415 false,
416 },
417 {
418 "T-junction, 2 apart, 3 clear",
419 { { 0, -10 }, { 0, 0 } },
420 { { -20, 0 }, { -2, 0 } },
421 3,
422 true,
423 },
424};
425// clang-format on
426
427
428BOOST_DATA_TEST_CASE( SegSegCollision, boost::unit_test::data::make( seg_seg_coll_cases ), c )
429{
430 BOOST_CHECK_PREDICATE( SegCollideCorrect,
431 ( c.m_seg_a )( c.m_seg_b )( c.m_clearance )( c.m_exp_coll ) );
432}
433
434
439{
443};
444
445// clang-format off
449static const std::vector<SEG_SEG_BOOLEAN_CASE> seg_vec_collinear_cases = {
450 {
451 "coincident",
452 { { 0, 0 }, { 10, 0 } },
453 { { 0, 0 }, { 10, 0 } },
454 true,
455 },
456 {
457 "end-to-end",
458 { { 0, 0 }, { 10, 0 } },
459 { { 10, 0 }, { 20, 0 } },
460 true,
461 },
462 {
463 "In segment",
464 { { 0, 0 }, { 10, 0 } },
465 { { 4, 0 }, { 7, 0 } },
466 true,
467 },
468 {
469 "At side, parallel",
470 { { 0, 0 }, { 10, 0 } },
471 { { 4, 1 }, { 7, 1 } },
472 false,
473 },
474 {
475 "crossing",
476 { { 0, 0 }, { 10, 0 } },
477 { { 5, -5 }, { 5, 5 } },
478 false,
479 },
480};
481// clang-format on
482
483
484BOOST_DATA_TEST_CASE( SegSegCollinear, boost::unit_test::data::make( seg_vec_collinear_cases ), c )
485{
486 BOOST_CHECK_PREDICATE( SegCollinearCorrect, ( c.m_seg_a )( c.m_seg_b )( c.m_exp_result ) );
487}
488
489
490// clang-format off
494static const std::vector<SEG_SEG_BOOLEAN_CASE> seg_vec_parallel_cases = {
495 {
496 "coincident",
497 { { 0, 0 }, { 10, 0 } },
498 { { 0, 0 }, { 10, 0 } },
499 true,
500 },
501 {
502 "end-to-end",
503 { { 0, 0 }, { 10, 0 } },
504 { { 10, 0 }, { 20, 0 } },
505 true,
506 },
507 {
508 "In segment",
509 { { 0, 0 }, { 10, 0 } },
510 { { 4, 0 }, { 7, 0 } },
511 true,
512 },
513 {
514 "At side, parallel",
515 { { 0, 0 }, { 10, 0 } },
516 { { 4, 1 }, { 7, 1 } },
517 true,
518 },
519 {
520 "crossing",
521 { { 0, 0 }, { 10, 0 } },
522 { { 5, -5 }, { 5, 5 } },
523 false,
524 },
525};
526// clang-format on
527
528
529BOOST_DATA_TEST_CASE( SegSegParallel, boost::unit_test::data::make( seg_vec_parallel_cases ), c )
530{
531 BOOST_CHECK_PREDICATE( SegParallelCorrect, ( c.m_seg_a )( c.m_seg_b )( c.m_exp_result ) );
532}
533
534
535// clang-format off
539static const std::vector<SEG_SEG_BOOLEAN_CASE> seg_vec_perpendicular_cases = {
540 {
541 "coincident",
542 { { 0, 0 }, { 10, 0 } },
543 { { 0, 0 }, { 10, 0 } },
544 false,
545 },
546 {
547 "end-to-end",
548 { { 0, 0 }, { 10, 0 } },
549 { { 10, 0 }, { 20, 0 } },
550 false,
551 },
552 {
553 "In segment",
554 { { 0, 0 }, { 10, 0 } },
555 { { 4, 0 }, { 7, 0 } },
556 false,
557 },
558 {
559 "At side, parallel",
560 { { 0, 0 }, { 10, 0 } },
561 { { 4, 1 }, { 7, 1 } },
562 false,
563 },
564 {
565 "crossing 45 deg",
566 { { 0, 0 }, { 10, 0 } },
567 { { 0, 0 }, { 5, 5 } },
568 false,
569 },
570 {
571 "very nearly perpendicular",
572 { { 0, 0 }, { 10, 0 } },
573 { { 0, 0 }, { 1, 10 } },
574 true, //allow error margin of 1 IU
575 },
576 {
577 "not really perpendicular",
578 { { 0, 0 }, { 10, 0 } },
579 { { 0, 0 }, { 3, 10 } },
580 false,
581 },
582 {
583 "perpendicular",
584 { { 0, 0 }, { 10, 0 } },
585 { { 0, 0 }, { 0, 10 } },
586 true,
587 },
588 {
589 "perpendicular not intersecting",
590 { { 0, 0 }, { 10, 0 } },
591 { { 15, 5 }, { 15, 10 } },
592 true,
593 },
594};
595// clang-format on
596
597
598BOOST_DATA_TEST_CASE( SegSegPerpendicular,
599 boost::unit_test::data::make( seg_vec_perpendicular_cases ), c )
600{
601 BOOST_CHECK_PREDICATE( SegPerpendicularCorrect, ( c.m_seg_a )( c.m_seg_b )( c.m_exp_result ) );
602}
603
604
609{
612};
613
614
615// clang-format off
619static const std::vector<SEG_VEC_CASE> segment_and_point_cases = {
620 {
621 "Horizontal: point on edge of seg",
622 { { 0, 0 }, { 10, 0 } },
623 { 0, 0 },
624 },
625 {
626 "Horizontal: point in middle of seg",
627 { { 0, 0 }, { 10, 0 } },
628 { 5, 0 },
629 },
630 {
631 "Horizontal: point outside seg",
632 { { 0, 0 }, { 10, 0 } },
633 { 20, 20 },
634 },
635 {
636 "Vertical: point on edge of seg",
637 { { 0, 0 }, { 0, 10 } },
638 { 0, 0 },
639 },
640 {
641 "Vertical: point in middle of seg",
642 { { 0, 0 }, { 0, 10 } },
643 { 0, 5 },
644 },
645 {
646 "Vertical: point outside seg",
647 { { 0, 0 }, { 0, 10 } },
648 { 20, 20 },
649 },
650};
651// clang-format on
652
653
654BOOST_DATA_TEST_CASE( SegCreateParallel, boost::unit_test::data::make( segment_and_point_cases ),
655 c )
656{
657 const SEG perpendicular = c.m_seg.ParallelSeg( c.m_vec );
658
659 BOOST_CHECK_PREDICATE( SegParallelCorrect, (perpendicular) ( c.m_seg )( true ) );
660 BOOST_CHECK_PREDICATE( SegVecDistanceCorrect, (perpendicular) ( c.m_vec )( 0 ) );
661}
662
663BOOST_DATA_TEST_CASE( SegCreatePerpendicular,
664 boost::unit_test::data::make( segment_and_point_cases ), c )
665{
666 const SEG perpendicular = c.m_seg.PerpendicularSeg( c.m_vec );
667
668 BOOST_CHECK_PREDICATE( SegPerpendicularCorrect, (perpendicular) ( c.m_seg )( true ) );
669 BOOST_CHECK_PREDICATE( SegVecDistanceCorrect, (perpendicular) ( c.m_vec )( 0 ) );
670}
671
672BOOST_AUTO_TEST_CASE( LineDistance )
673{
674 SEG seg( { 0, 0 }, { 10, 0 } );
675
676 BOOST_TEST( seg.LineDistance( { 5, 0 } ) == 0 );
677 BOOST_TEST( seg.LineDistance( { 5, 8 } ) == 8 );
678}
679
680BOOST_AUTO_TEST_CASE( LineDistanceSided )
681{
682 SEG seg( { 0, 0 }, { 10, 0 } );
683
684 BOOST_TEST( seg.LineDistance( { 5, 8 }, true ) == 8 );
685 BOOST_TEST( seg.LineDistance( { 5, -8 }, true ) == -8 );
686}
687
692{
699};
700
701// clang-format off
702static const std::vector<SEG_SEG_INTERSECT_CASE> seg_intersect_cases = {
703 // Basic crossing cases
704 {
705 "Crossing at origin",
706 { { -10, 0 }, { 10, 0 } },
707 { { 0, -10 }, { 0, 10 } },
708 false, false, true,
709 { 0, 0 }
710 },
711 {
712 "Crossing at (5,5)",
713 { { 0, 5 }, { 10, 5 } },
714 { { 5, 0 }, { 5, 10 } },
715 false, false, true,
716 { 5, 5 }
717 },
718 {
719 "T-junction intersection",
720 { { 0, 0 }, { 10, 0 } },
721 { { 5, -5 }, { 5, 0 } },
722 false, false, true,
723 { 5, 0 }
724 },
725
726 // Non-intersecting cases
727 {
728 "Parallel segments",
729 { { 0, 0 }, { 10, 0 } },
730 { { 0, 5 }, { 10, 5 } },
731 false, false, false,
732 { 0, 0 }
733 },
734 {
735 "Separated segments",
736 { { 0, 0 }, { 5, 0 } },
737 { { 10, 0 }, { 15, 0 } },
738 false, false, false,
739 { 0, 0 }
740 },
741 {
742 "Lines would intersect, but segments don't",
743 { { 0, 0 }, { 2, 0 } },
744 { { 5, -5 }, { 5, 5 } },
745 false, false, false,
746 { 0, 0 }
747 },
748
749 // Endpoint intersection cases
750 {
751 "Endpoint touching - should intersect",
752 { { 0, 0 }, { 10, 0 } },
753 { { 10, 0 }, { 20, 0 } },
754 false, false, true,
755 { 10, 0 }
756 },
757 {
758 "Endpoint touching - ignore endpoints",
759 { { 0, 0 }, { 10, 0 } },
760 { { 10, 0 }, { 20, 0 } },
761 true, false, false,
762 { 0, 0 }
763 },
764 {
765 "Endpoint touching at angle",
766 { { 0, 0 }, { 10, 0 } },
767 { { 10, 0 }, { 15, 5 } },
768 false, false, true,
769 { 10, 0 }
770 },
771
772 // Collinear cases
773 {
774 "Collinear overlapping segments",
775 { { 0, 0 }, { 10, 0 } },
776 { { 5, 0 }, { 15, 0 } },
777 false, false, true,
778 { 7, 0 } // Midpoint of overlap [5,10]
779 },
780 {
781 "Collinear non-overlapping segments",
782 { { 0, 0 }, { 5, 0 } },
783 { { 10, 0 }, { 15, 0 } },
784 false, false, false,
785 { 0, 0 }
786 },
787 {
788 "Collinear touching at endpoint",
789 { { 0, 0 }, { 10, 0 } },
790 { { 10, 0 }, { 20, 0 } },
791 false, false, true,
792 { 10, 0 }
793 },
794 {
795 "Collinear contained segment",
796 { { 0, 0 }, { 20, 0 } },
797 { { 5, 0 }, { 15, 0 } },
798 false, false, true,
799 { 10, 0 } // Midpoint of contained segment
800 },
801 {
802 "Collinear vertical overlapping",
803 { { 5, 0 }, { 5, 10 } },
804 { { 5, 5 }, { 5, 15 } },
805 false, false, true,
806 { 5, 7 } // Midpoint of overlap [5,10]
807 },
808
809 // Line mode cases (infinite lines)
810 {
811 "Lines intersect, segments don't",
812 { { 0, 0 }, { 2, 0 } },
813 { { 5, -5 }, { 5, 5 } },
814 false, true, true,
815 { 5, 0 }
816 },
817 {
818 "Parallel lines (infinite)",
819 { { 0, 0 }, { 10, 0 } },
820 { { 0, 5 }, { 10, 5 } },
821 false, true, false,
822 { 0, 0 }
823 },
824 {
825 "Collinear lines (infinite)",
826 { { 0, 0 }, { 10, 0 } },
827 { { 20, 0 }, { 30, 0 } },
828 false, true, true,
829 { 10, 0 } // Midpoint between segment starts
830 },
831
832 // Edge cases
833 {
834 "Zero-length segment intersection",
835 { { 5, 5 }, { 5, 5 } },
836 { { 0, 5 }, { 10, 5 } },
837 false, false, true,
838 { 5, 5 }
839 },
840 {
841 "Both zero-length, same point",
842 { { 5, 5 }, { 5, 5 } },
843 { { 5, 5 }, { 5, 5 } },
844 false, false, true,
845 { 5, 5 }
846 },
847 {
848 "Both zero-length, different points",
849 { { 5, 5 }, { 5, 5 } },
850 { { 10, 10 }, { 10, 10 } },
851 false, false, false,
852 { 0, 0 }
853 },
854
855 // Diagonal intersection cases
856 {
857 "45-degree crossing",
858 { { 0, 0 }, { 10, 10 } },
859 { { 0, 10 }, { 10, 0 } },
860 false, false, true,
861 { 5, 5 }
862 },
863 {
864 "Arbitrary angle crossing",
865 { { 0, 0 }, { 6, 8 } },
866 { { 0, 8 }, { 6, 0 } },
867 false, false, true,
868 { 3, 4 }
869 },
870
871 // Bounding box optimization test cases
872 {
873 "Far apart horizontal segments",
874 { { 0, 0 }, { 10, 0 } },
875 { { 100, 0 }, { 110, 0 } },
876 false, false, false,
877 { 0, 0 }
878 },
879 {
880 "Far apart vertical segments",
881 { { 0, 0 }, { 0, 10 } },
882 { { 0, 100 }, { 0, 110 } },
883 false, false, false,
884 { 0, 0 }
885 },
886 {
887 "Far apart diagonal segments",
888 { { 0, 0 }, { 10, 10 } },
889 { { 100, 100 }, { 110, 110 } },
890 false, false, false,
891 { 0, 0 }
892 },
893};
894// clang-format on
895
896
903{
904 const auto resultA = aCase.m_seg_a.Intersect( aCase.m_seg_b, aCase.m_ignore_endpoints, aCase.m_lines );
905 const auto resultB = aCase.m_seg_b.Intersect( aCase.m_seg_a, aCase.m_ignore_endpoints, aCase.m_lines );
906
907 const bool intersectsA = resultA.has_value();
908 const bool intersectsB = resultB.has_value();
909
910 bool ok = ( intersectsA == aCase.m_exp_intersect ) && ( intersectsB == aCase.m_exp_intersect );
911
912 if( intersectsA != intersectsB )
913 {
914 std::stringstream ss;
915 ss << "Segment intersection is not the same in both directions: expected " << aCase.m_exp_intersect
916 << ", got " << intersectsA << " & " << intersectsB;
917 BOOST_TEST_INFO( ss.str() );
918 ok = false;
919 }
920 else if( !ok )
921 {
922 std::stringstream ss;
923 ss << "Intersection incorrect: expected " << aCase.m_exp_intersect << ", got " << intersectsA;
924 BOOST_TEST_INFO( ss.str() );
925 }
926
927 // Check intersection point if intersection was expected
928 if( ok && aCase.m_exp_intersect && aCase.m_exp_point != VECTOR2I() )
929 {
930 // Allow some tolerance for intersection point calculation
931 const int tolerance = 1;
932
933 if( !resultA || !resultB )
934 {
935 std::stringstream ss;
936 ss << "Expected intersection but got nullopt";
937 BOOST_TEST_INFO( ss.str() );
938 ok = false;
939 }
940 else
941 {
942 const VECTOR2I pointA = *resultA;
943 const VECTOR2I pointB = *resultB;
944
945 bool pointOk = ( std::abs( pointA.x - aCase.m_exp_point.x ) <= tolerance &&
946 std::abs( pointA.y - aCase.m_exp_point.y ) <= tolerance &&
947 std::abs( pointB.x - aCase.m_exp_point.x ) <= tolerance &&
948 std::abs( pointB.y - aCase.m_exp_point.y ) <= tolerance );
949
950 if( !pointOk )
951 {
952 std::stringstream ss;
953 ss << "Intersection point incorrect: expected " << aCase.m_exp_point.Format()
954 << ", got " << pointA.Format() << " & " << pointB.Format();
955 BOOST_TEST_INFO( ss.str() );
956 ok = false;
957 }
958 }
959 }
960
961 return ok;
962}
963
964BOOST_DATA_TEST_CASE( SegSegIntersection, boost::unit_test::data::make( seg_intersect_cases ), c )
965{
967}
968
969
970// Additional focused test cases for specific scenarios
971BOOST_AUTO_TEST_CASE( IntersectLargeCoordinates )
972{
973 // Test with large coordinates to verify overflow protection
974 SEG segA( { 1000000000, 0 }, { -1000000000, 0 } );
975 SEG segB( { 0, 1000000000 }, { 0, -1000000000 } );
976
977 auto intersection = segA.Intersect( segB, false, false );
978
979 BOOST_CHECK( intersection.has_value() );
980 BOOST_CHECK_EQUAL( intersection->x, 0 );
981 BOOST_CHECK_EQUAL( intersection->y, 0 );
982}
983
984BOOST_AUTO_TEST_CASE( IntersectOverflowDetection )
985{
986 // Test intersection that would overflow coordinate range
987 constexpr int max_coord = std::numeric_limits<int>::max();
988
989 SEG segA( { 0, 0 }, { max_coord, max_coord } );
990 SEG segB( { max_coord, 0 }, { 0, max_coord } );
991
992 // This should either work or return nullopt due to overflow protection
993 auto intersection = segA.Intersect( segB, false, false );
994
995 // The test passes if it doesn't crash - the exact result depends on overflow handling
996 BOOST_TEST_MESSAGE( "Overflow test completed without crash. Has intersection: " << intersection.has_value() );
997 if( intersection.has_value() )
998 {
999 BOOST_TEST_MESSAGE( "Intersection point: " << intersection->Format() );
1000 }
1001}
1002
1003BOOST_AUTO_TEST_CASE( IntersectPrecisionEdgeCases )
1004{
1005 // Test cases that might have precision issues
1006 SEG segA( { 0, 0 }, { 1000000, 1 } );
1007 SEG segB( { 500000, -1 }, { 500000, 2 } );
1008
1009 auto intersection = segA.Intersect( segB, false, false );
1010
1011 BOOST_CHECK( intersection.has_value() );
1012 // The intersection should be very close to (500000, 0.5), rounded to (500000, 1) or (500000, 0)
1013 BOOST_CHECK_EQUAL( intersection->x, 500000 );
1014 BOOST_CHECK( intersection->y >= 0 && intersection->y <= 1 );
1015}
1016
1017BOOST_AUTO_TEST_CASE( IntersectIgnoreEndpointsEdgeCases )
1018{
1019 // Test edge cases with ignore endpoints
1020 SEG segA( { 0, 0 }, { 10, 0 } );
1021 SEG segB( { 5, -5 }, { 5, 5 } );
1022
1023 // Normal intersection should work
1024 auto intersection1 = segA.Intersect( segB, false, false );
1025 BOOST_CHECK( intersection1.has_value() );
1026 BOOST_CHECK_EQUAL( *intersection1, VECTOR2I( 5, 0 ) );
1027
1028 // Should still work when ignoring endpoints (this is a middle intersection)
1029 auto intersection2 = segA.Intersect( segB, true, false );
1030 BOOST_CHECK( intersection2.has_value() );
1031 BOOST_CHECK_EQUAL( *intersection2, VECTOR2I( 5, 0 ) );
1032
1033 // Test actual endpoint intersection
1034 SEG segC( { 10, 0 }, { 20, 0 } );
1035 auto intersection3 = segA.Intersect( segC, false, false );
1036 BOOST_CHECK( intersection3.has_value() );
1037 BOOST_CHECK_EQUAL( *intersection3, VECTOR2I( 10, 0 ) );
1038
1039 // Should not intersect when ignoring endpoints
1040 auto intersection4 = segA.Intersect( segC, true, false );
1041 BOOST_CHECK( !intersection4.has_value() );
1042}
1043
1044BOOST_AUTO_TEST_CASE( IntersectCollinearRegressionTests )
1045{
1046 // Regression tests for collinear segment handling
1047
1048 // Test case: horizontal segments with partial overlap
1049 SEG seg1( { 0, 5 }, { 10, 5 } );
1050 SEG seg2( { 5, 5 }, { 15, 5 } );
1051
1052 auto intersection = seg1.Intersect( seg2, false, false );
1053
1054 BOOST_CHECK( intersection.has_value() );
1055 BOOST_CHECK_EQUAL( intersection->y, 5 );
1056 BOOST_CHECK( intersection->x >= 5 && intersection->x <= 10 ); // Should be in overlap region
1057
1058 // Test case: vertical segments with complete overlap (one contained in other)
1059 SEG seg3( { 3, 0 }, { 3, 20 } );
1060 SEG seg4( { 3, 5 }, { 3, 15 } );
1061
1062 auto intersection2 = seg3.Intersect( seg4, false, false );
1063
1064 BOOST_CHECK( intersection2.has_value() );
1065 BOOST_CHECK_EQUAL( intersection2->x, 3 );
1066 BOOST_CHECK( intersection2->y >= 5 && intersection2->y <= 15 ); // Should be in contained segment
1067
1068 // Test case: diagonal collinear segments
1069 SEG seg5( { 0, 0 }, { 10, 10 } );
1070 SEG seg6( { 5, 5 }, { 15, 15 } );
1071
1072 auto intersection3 = seg5.Intersect( seg6, false, false );
1073
1074 BOOST_CHECK( intersection3.has_value() );
1075 BOOST_CHECK( intersection3->x >= 5 && intersection3->x <= 10 );
1076 BOOST_CHECK( intersection3->y >= 5 && intersection3->y <= 10 );
1077 BOOST_CHECK_EQUAL( intersection3->x, intersection3->y ); // Should maintain diagonal relationship
1078
1079 // Test case: collinear segments that touch only at endpoints
1080 SEG seg7( { 0, 0 }, { 5, 0 } );
1081 SEG seg8( { 5, 0 }, { 10, 0 } );
1082
1083 auto intersection4 = seg7.Intersect( seg8, false, false );
1084 BOOST_CHECK( intersection4.has_value() );
1085 BOOST_CHECK_EQUAL( *intersection4, VECTOR2I( 5, 0 ) );
1086
1087 // Same test but ignoring endpoints
1088 auto intersection5 = seg7.Intersect( seg8, true, false );
1089 BOOST_CHECK( !intersection5.has_value() );
1090
1091 // Test case: collinear segments that don't overlap
1092 SEG seg9( { 0, 0 }, { 5, 0 } );
1093 SEG seg10( { 10, 0 }, { 15, 0 } );
1094
1095 auto intersection6 = seg9.Intersect( seg10, false, false );
1096 BOOST_CHECK( !intersection6.has_value() );
1097}
1098
1099BOOST_AUTO_TEST_CASE( IntersectBoundingBoxOptimization )
1100{
1101 // Test that bounding box optimization works correctly
1102
1103 // Segments that are clearly separated - should be rejected quickly
1104 SEG seg1( { 0, 0 }, { 10, 10 } );
1105 SEG seg2( { 100, 100 }, { 110, 110 } );
1106
1107 auto intersection = seg1.Intersect( seg2, false, false );
1108 BOOST_CHECK( !intersection.has_value() );
1109
1110 // Segments with overlapping bounding boxes but no intersection
1111 SEG seg3( { 0, 0 }, { 10, 0 } );
1112 SEG seg4( { 5, 5 }, { 15, 5 } );
1113
1114 auto intersection2 = seg3.Intersect( seg4, false, false );
1115 BOOST_CHECK( !intersection2.has_value() );
1116
1117 // Segments with touching bounding boxes and actual intersection
1118 SEG seg5( { 0, 0 }, { 10, 10 } );
1119 SEG seg6( { 10, 0 }, { 0, 10 } );
1120
1121 auto intersection3 = seg5.Intersect( seg6, false, false );
1122 BOOST_CHECK( intersection3.has_value() );
1123 BOOST_CHECK_EQUAL( *intersection3, VECTOR2I( 5, 5 ) );
1124}
1125
1126BOOST_AUTO_TEST_CASE( IntersectLineVsSegmentMode )
1127{
1128 // Test the difference between line mode and segment mode
1129
1130 SEG seg1( { 0, 0 }, { 5, 0 } );
1131 SEG seg2( { 10, -5 }, { 10, 5 } );
1132
1133 // In segment mode, these don't intersect
1134 auto segmentIntersect = seg1.Intersect( seg2, false, false );
1135 BOOST_CHECK( !segmentIntersect.has_value() );
1136
1137 // In line mode, they should intersect
1138 auto lineIntersect = seg1.Intersect( seg2, false, true );
1139 BOOST_CHECK( lineIntersect.has_value() );
1140 BOOST_CHECK_EQUAL( *lineIntersect, VECTOR2I( 10, 0 ) );
1141
1142 // Test collinear case in line mode
1143 SEG seg3( { 0, 0 }, { 10, 0 } );
1144 SEG seg4( { 20, 0 }, { 30, 0 } );
1145
1146 // Segments don't intersect
1147 auto segmentIntersect2 = seg3.Intersect( seg4, false, false );
1148 BOOST_CHECK( !segmentIntersect2.has_value() );
1149
1150 // Lines (infinite) do intersect (collinear)
1151 auto lineIntersect2 = seg3.Intersect( seg4, false, true );
1152 BOOST_CHECK( lineIntersect2.has_value() );
1153}
1154
1155BOOST_AUTO_TEST_CASE( IntersectNumericalStability )
1156{
1157 // Test cases designed to stress numerical precision
1158
1159 // Very small segments
1160 SEG seg1( { 0, 0 }, { 1, 1 } );
1161 SEG seg2( { 0, 1 }, { 1, 0 } );
1162
1163 auto intersection = seg1.Intersect( seg2, false, false );
1164
1165 BOOST_CHECK( intersection.has_value() );
1166 // Intersection should be very close to (0.5, 0.5), rounded to (0,0), (0,1), (1,0), or (1,1)
1167 BOOST_CHECK( intersection->x >= 0 && intersection->x <= 1 );
1168 BOOST_CHECK( intersection->y >= 0 && intersection->y <= 1 );
1169
1170 // Nearly parallel segments
1171 SEG seg3( { 0, 0 }, { 1000, 1 } );
1172 SEG seg4( { 0, 1 }, { 1000, 2 } );
1173
1174 auto intersection2 = seg3.Intersect( seg4, false, false );
1175 BOOST_CHECK( !intersection2.has_value() ); // Should be detected as parallel/non-intersecting
1176
1177 // Segments that intersect at a very acute angle
1178 SEG seg5( { 0, 0 }, { 1000000, 1 } );
1179 SEG seg6( { 500000, -1 }, { 500000, 2 } );
1180
1181 auto intersection3 = seg5.Intersect( seg6, false, false );
1182 BOOST_CHECK( intersection3.has_value() );
1183 BOOST_CHECK_EQUAL( intersection3->x, 500000 );
1184}
1185
1186BOOST_AUTO_TEST_CASE( IntersectZeroLengthSegments )
1187{
1188 // Comprehensive tests for zero-length segments (points)
1189
1190 VECTOR2I point1( 5, 5 );
1191 VECTOR2I point2( 10, 10 );
1192
1193 SEG pointSeg1( point1, point1 ); // Zero-length segment (point)
1194 SEG pointSeg2( point2, point2 ); // Another zero-length segment
1195 SEG normalSeg( { 0, 5 }, { 10, 5 } ); // Normal segment
1196
1197 // Point intersecting with normal segment
1198 auto intersection1 = pointSeg1.Intersect( normalSeg, false, false );
1199 BOOST_CHECK( intersection1.has_value() );
1200 BOOST_CHECK_EQUAL( *intersection1, point1 );
1201
1202 // Point not intersecting with normal segment
1203 auto intersection2 = pointSeg2.Intersect( normalSeg, false, false );
1204 BOOST_CHECK( !intersection2.has_value() );
1205
1206 // Two points at same location
1207 SEG pointSeg3( point1, point1 );
1208 auto intersection3 = pointSeg1.Intersect( pointSeg3, false, false );
1209 BOOST_CHECK( intersection3.has_value() );
1210 BOOST_CHECK_EQUAL( *intersection3, point1 );
1211
1212 // Two points at different locations
1213 auto intersection4 = pointSeg1.Intersect( pointSeg2, false, false );
1214 BOOST_CHECK( !intersection4.has_value() );
1215
1216 // Point on line (infinite mode)
1217 SEG lineSeg( { 0, 0 }, { 1, 1 } ); // Diagonal line segment
1218 SEG pointOnLine( { 100, 100 }, { 100, 100 } ); // Point on extended line
1219
1220 auto intersection5 = pointOnLine.Intersect( lineSeg, false, false );
1221 BOOST_CHECK( !intersection5.has_value() ); // Point not on segment
1222
1223 auto intersection6 = pointOnLine.Intersect( lineSeg, false, true );
1224 BOOST_CHECK( intersection6.has_value() ); // Point on infinite line
1225 BOOST_CHECK_EQUAL( *intersection6, VECTOR2I( 100, 100 ) );
1226}
1227
1228
1233{
1235 double m_slope;
1236 double m_offset;
1239};
1240
1250bool SegLineIntersectCorrect( const SEG& aSeg, double aSlope, double aOffset,
1251 bool aExpIntersect, const VECTOR2I& aExpPoint = VECTOR2I() )
1252{
1253 VECTOR2I intersection;
1254 const bool intersects = aSeg.IntersectsLine( aSlope, aOffset, intersection );
1255
1256 bool ok = ( intersects == aExpIntersect );
1257
1258 if( !ok )
1259 {
1260 std::stringstream ss;
1261 ss << "Line intersection incorrect: expected " << aExpIntersect << ", got " << intersects;
1262 BOOST_TEST_INFO( ss.str() );
1263 }
1264
1265 // Check intersection point if intersection was expected
1266 if( ok && aExpIntersect && aExpPoint != VECTOR2I() )
1267 {
1268 // Allow some tolerance for intersection point calculation
1269 const int tolerance = 1;
1270
1271 bool pointOk = ( std::abs( intersection.x - aExpPoint.x ) <= tolerance &&
1272 std::abs( intersection.y - aExpPoint.y ) <= tolerance );
1273
1274 if( !pointOk )
1275 {
1276 std::stringstream ss;
1277 ss << "Intersection point incorrect: expected " << aExpPoint.Format()
1278 << ", got " << intersection.Format();
1279 BOOST_TEST_INFO( ss.str() );
1280 ok = false;
1281 }
1282 }
1283
1284 return ok;
1285}
1286
1287// clang-format off
1288static const std::vector<SEG_LINE_INTERSECT_CASE> seg_line_intersect_cases = {
1289 // Basic intersection cases
1290 {
1291 "Horizontal segment, diagonal line",
1292 { { 0, 5 }, { 10, 5 } },
1293 1.0, 0.0, // y = x
1294 true,
1295 { 5, 5 }
1296 },
1297 {
1298 "Vertical segment, horizontal line",
1299 { { 5, 0 }, { 5, 10 } },
1300 0.0, 3.0, // y = 3
1301 true,
1302 { 5, 3 }
1303 },
1304 {
1305 "Diagonal segment, horizontal line crossing",
1306 { { 0, 0 }, { 10, 10 } },
1307 0.0, 5.0, // y = 5
1308 true,
1309 { 5, 5 }
1310 },
1311 {
1312 "Diagonal segment, vertical line (steep slope)",
1313 { { 0, 0 }, { 10, 10 } },
1314 1000.0, -5000.0, // Very steep line: y = 1000x - 5000, crosses at x=5
1315 true,
1316 { 5, 5 }
1317 },
1318
1319 // Non-intersecting cases
1320 {
1321 "Horizontal segment, parallel horizontal line",
1322 { { 0, 5 }, { 10, 5 } },
1323 0.0, 10.0, // y = 10 (parallel to y = 5)
1324 false,
1325 { 0, 0 }
1326 },
1327 {
1328 "Diagonal segment, parallel line",
1329 { { 0, 0 }, { 10, 10 } },
1330 1.0, 5.0, // y = x + 5 (parallel to y = x)
1331 false,
1332 { 0, 0 }
1333 },
1334 {
1335 "Segment above line",
1336 { { 0, 10 }, { 10, 10 } },
1337 0.0, 5.0, // y = 5
1338 false,
1339 { 0, 0 }
1340 },
1341 {
1342 "Segment to left of steep line",
1343 { { 0, 0 }, { 2, 2 } },
1344 1.0, 10.0, // y = x + 10
1345 false,
1346 { 0, 0 }
1347 },
1348
1349 // Collinear cases (segment lies on line)
1350 {
1351 "Horizontal segment on horizontal line",
1352 { { 0, 5 }, { 10, 5 } },
1353 0.0, 5.0, // y = 5
1354 true,
1355 { 5, 5 } // Midpoint
1356 },
1357 {
1358 "Diagonal segment on diagonal line",
1359 { { 0, 0 }, { 10, 10 } },
1360 1.0, 0.0, // y = x
1361 true,
1362 { 5, 5 } // Midpoint
1363 },
1364 {
1365 "Vertical segment, any line slope (collinear impossible)",
1366 { { 5, 0 }, { 5, 10 } },
1367 2.0, -5.0, // y = 2x - 5, passes through (5, 5)
1368 true,
1369 { 5, 5 }
1370 },
1371
1372 // Edge cases
1373 {
1374 "Zero-length segment (point) on line",
1375 { { 3, 7 }, { 3, 7 } },
1376 2.0, 1.0, // y = 2x + 1, point (3,7) should be on this line
1377 true,
1378 { 3, 7 }
1379 },
1380 {
1381 "Zero-length segment (point) not on line",
1382 { { 3, 5 }, { 3, 5 } },
1383 2.0, 1.0, // y = 2x + 1, point (3,5) not on line (should be y=7)
1384 false,
1385 { 0, 0 }
1386 },
1387 {
1388 "Line with zero slope (horizontal)",
1389 { { 0, 0 }, { 10, 5 } },
1390 0.0, 2.5, // y = 2.5
1391 true,
1392 { 5, 2 } // Intersection at x=5, y=2.5 rounded to y=2 or 3
1393 },
1394 {
1395 "Very steep positive slope",
1396 { { 0, 0 }, { 10, 1 } },
1397 100.0, -250.0, // y = 100x - 250, intersects at x=2.5
1398 true,
1399 { 2, 0 } // Approximately (2.5, 0)
1400 },
1401 {
1402 "Very steep negative slope",
1403 { { 0, 0 }, { 10, 10 } },
1404 -100.0, 505.0, // y = -100x + 505, intersects at x=5.05, y≈0
1405 true,
1406 { 5, 5 } // Approximately (5.05, 0) but segment has y=5 at x=5
1407 },
1408 {
1409 "Fractional slope",
1410 { { 0, 0 }, { 12, 8 } },
1411 0.5, 1.0, // y = 0.5x + 1
1412 true,
1413 { 6, 4 } // Intersection where segment y = 2x/3 meets line y = 0.5x + 1
1414 },
1415
1416 // Endpoint intersections
1417 {
1418 "Line passes through segment start point",
1419 { { 2, 3 }, { 80, 90 } },
1420 1.0, 1.0, // y = x + 1, passes through (2,3)
1421 true,
1422 { 2, 3 }
1423 },
1424 {
1425 "Line passes through segment end point",
1426 { { 20, 30 }, { 8, 9 } },
1427 1.0, 1.0, // y = x + 1, passes through (8,9)
1428 true,
1429 { 8, 9 }
1430 },
1431 {
1432 "Line intersects near endpoint",
1433 { { 0, 0 }, { 10, 0 } },
1434 0.0, 0.0, // y = 0, same as segment
1435 true,
1436 { 5, 0 } // Collinear, returns midpoint
1437 },
1438
1439 // Precision edge cases
1440 {
1441 "Nearly parallel lines",
1442 { { 0, 0 }, { 1000, 1 } },
1443 0.0011, -0.05, // Very slightly different slope
1444 true,
1445 { 500, 1 } // At 500, y will round up to 1 in both cases
1446 },
1447 {
1448 "Line intersection outside segment bounds",
1449 { { 5, 5 }, { 10, 10 } },
1450 1.0, -10.0, // y = x - 10, would intersect extended line at (15, 5)
1451 false,
1452 { 0, 0 }
1453 },
1454};
1455// clang-format on
1456
1457BOOST_DATA_TEST_CASE( SegLineIntersection, boost::unit_test::data::make( seg_line_intersect_cases ), c )
1458{
1459 BOOST_CHECK_PREDICATE( SegLineIntersectCorrect, ( c.m_seg )( c.m_slope )( c.m_offset )( c.m_exp_intersect )( c.m_exp_point ) );
1460}
1461
1462// Additional focused test cases for specific scenarios
1463BOOST_AUTO_TEST_CASE( IntersectLineVerticalSegments )
1464{
1465 // Test vertical segments with various line slopes
1466 SEG verticalSeg( { 5, 0 }, { 5, 10 } );
1467 VECTOR2I intersection;
1468
1469 // Horizontal line intersecting vertical segment
1470 bool intersects1 = verticalSeg.IntersectsLine( 0.0, 7.0, intersection );
1471 BOOST_CHECK( intersects1 );
1472 BOOST_CHECK_EQUAL( intersection, VECTOR2I( 5, 7 ) );
1473
1474 // Diagonal line intersecting vertical segment
1475 bool intersects2 = verticalSeg.IntersectsLine( 2.0, -5.0, intersection ); // y = 2x - 5
1476 BOOST_CHECK( intersects2 );
1477 BOOST_CHECK_EQUAL( intersection, VECTOR2I( 5, 5 ) ); // At x=5: y = 2*5 - 5 = 5
1478
1479 // Line that misses vertical segment
1480 bool intersects3 = verticalSeg.IntersectsLine( 1.0, 20.0, intersection ); // y = x + 20
1481 BOOST_CHECK( !intersects3 );
1482}
1483
1484BOOST_AUTO_TEST_CASE( IntersectLineVerticalSegmentsCorrection )
1485{
1486 // Corrected test for vertical segments
1487 SEG verticalSeg( { 5, 0 }, { 5, 10 } );
1488 VECTOR2I intersection;
1489
1490 // Line that misses vertical segment (intersection outside y-range)
1491 bool intersects1 = verticalSeg.IntersectsLine( 1.0, 20.0, intersection ); // y = x + 20
1492 BOOST_CHECK( !intersects1 ); // At x=5: y = 25, which is outside [0,10]
1493
1494 // Line that intersects within segment bounds
1495 bool intersects2 = verticalSeg.IntersectsLine( 0.5, 2.0, intersection ); // y = 0.5x + 2
1496 BOOST_CHECK( intersects2 );
1497 BOOST_CHECK_EQUAL( intersection, VECTOR2I( 5, 5 ) ); // At x=5: y = 0.5*5 + 2 = 4.5 ≈ 5 (round up)
1498}
1499
1500BOOST_AUTO_TEST_CASE( IntersectLineParallelDetection )
1501{
1502 // Test parallel line detection using cross products
1503
1504 // Horizontal segment with horizontal line
1505 SEG horizontalSeg( { 0, 5 }, { 10, 5 } );
1506 VECTOR2I intersection;
1507
1508 // Parallel but not collinear
1509 bool intersects1 = horizontalSeg.IntersectsLine( 0.0, 8.0, intersection ); // y = 8
1510 BOOST_CHECK( !intersects1 );
1511
1512 // Collinear (segment lies on line)
1513 bool intersects2 = horizontalSeg.IntersectsLine( 0.0, 5.0, intersection ); // y = 5
1514 BOOST_CHECK( intersects2 );
1515 BOOST_CHECK_EQUAL( intersection, VECTOR2I( 5, 5 ) ); // Midpoint
1516
1517 // Diagonal segment with parallel line
1518 SEG diagonalSeg( { 0, 0 }, { 10, 10 } );
1519
1520 // Parallel but offset
1521 bool intersects3 = diagonalSeg.IntersectsLine( 1.0, 3.0, intersection ); // y = x + 3
1522 BOOST_CHECK( !intersects3 );
1523
1524 // Collinear
1525 bool intersects4 = diagonalSeg.IntersectsLine( 1.0, 0.0, intersection ); // y = x
1526 BOOST_CHECK( intersects4 );
1527 BOOST_CHECK_EQUAL( intersection, VECTOR2I( 5, 5 ) ); // Midpoint
1528}
1529
1530BOOST_AUTO_TEST_CASE( IntersectLinePrecisionEdgeCases )
1531{
1532 // Test precision-sensitive cases
1533
1534 // Very shallow segment with steep line
1535 SEG shallowSeg( { 0, 100 }, { 1000000, 101 } ); // Almost horizontal
1536 VECTOR2I intersection;
1537
1538 bool intersects = shallowSeg.IntersectsLine( 1000.0, -499900.0, intersection );
1539 // Line: y = 1000x - 499900
1540 // This should intersect around x = 500, y ≈ 100.001
1541
1542 if( intersects )
1543 {
1544 BOOST_CHECK( intersection.x >= 0 && intersection.x <= 1000000 );
1545 BOOST_CHECK( intersection.y >= 100 && intersection.y <= 101 );
1546 }
1547
1548 // Test with very large coordinates
1549 SEG largeSeg( { 1000000, 1000000 }, { 2000000, 2000000 } );
1550 bool intersects2 = largeSeg.IntersectsLine( 1.0, 0.0, intersection ); // y = x
1551 BOOST_CHECK( intersects2 );
1552 BOOST_CHECK_EQUAL( intersection, VECTOR2I( 1500000, 1500000 ) ); // Midpoint
1553}
1554
1555BOOST_AUTO_TEST_CASE( IntersectLineZeroLengthSegments )
1556{
1557 // Test with zero-length segments (points)
1558
1559 VECTOR2I point( 10, 20 );
1560 SEG pointSeg( point, point );
1561 VECTOR2I intersection;
1562
1563 // Point lies on line
1564 bool intersects1 = pointSeg.IntersectsLine( 2.0, 0.0, intersection ); // y = 2x
1565 BOOST_CHECK( intersects1 ); // Point (10, 20) is on line y = 2x
1566 BOOST_CHECK_EQUAL( intersection, point );
1567
1568 // Point does not lie on line
1569 bool intersects2 = pointSeg.IntersectsLine( 3.0, 0.0, intersection ); // y = 3x
1570 BOOST_CHECK( !intersects2 ); // Point (10, 20) not on line y = 3x (would be y = 30)
1571
1572 // Point on horizontal line
1573 bool intersects3 = pointSeg.IntersectsLine( 0.0, 20.0, intersection ); // y = 20
1574 BOOST_CHECK( intersects3 );
1575 BOOST_CHECK_EQUAL( intersection, point );
1576}
1577
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
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
VECTOR2I::extended_type ecoord
Definition: seg.h:44
VECTOR2I B
Definition: seg.h:50
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
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
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:286
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:529
bool ApproxPerpendicular(const SEG &aSeg) const
Definition: seg.cpp:792
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:675
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition: seg.cpp:520
const std::string Format() const
Return the vector formatted as a string.
Definition: vector2d.h:423
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:400
A named data-driven test case.
Test cases for segment-line intersection.
Struct to hold general cases for collinearity, parallelism and perpendicularity.
Test cases for collisions (with clearance, for no clearance, it's just a SEG_SEG_DISTANCE_CASE of 0)
Test cases for segment intersection.
Struct to hold cases for operations with a SEG, and a VECTOR2I.
VECTOR2I m_vec
BOOST_AUTO_TEST_SUITE(CadstarPartParser)
BOOST_CHECK_EQUAL(ret, c.m_exp_result)
BOOST_TEST(contains==c.ExpectedContains)
BOOST_REQUIRE(intersection.has_value()==c.ExpectedIntersection.has_value())
BOOST_AUTO_TEST_SUITE_END()
static const std::vector< SEG_SEG_BOOLEAN_CASE > seg_vec_perpendicular_cases
Test cases for perpendicularity.
BOOST_AUTO_TEST_CASE(EndpointCtorMod)
Checks whether the construction of a segment referencing external points works and that the endpoints...
static const std::vector< SEG_SEG_BOOLEAN_CASE > seg_vec_collinear_cases
Test cases for collinearity.
static const std::vector< SEG_VEC_CASE > segment_and_point_cases
Test cases to create segments passing through a point.
BOOST_DATA_TEST_CASE(SegSegPerpendicular, boost::unit_test::data::make(seg_vec_perpendicular_cases), c)
static const std::vector< SEG_SEG_DISTANCE_CASE > seg_seg_dist_cases
static const std::vector< SEG_VECTOR_DISTANCE_CASE > seg_vec_dist_cases
static const std::vector< SEG_LINE_INTERSECT_CASE > seg_line_intersect_cases
static const std::vector< SEG_SEG_INTERSECT_CASE > seg_intersect_cases
bool SegIntersectCorrect(const SEG_SEG_INTERSECT_CASE &aCase)
Predicate to check expected intersection between two segments.
static const std::vector< SEG_SEG_COLLIDE_CASE > seg_seg_coll_cases
bool SegLineIntersectCorrect(const SEG &aSeg, double aSlope, double aOffset, bool aExpIntersect, const VECTOR2I &aExpPoint=VECTOR2I())
Predicate to check expected intersection between a segment and an infinite line.
static const std::vector< SEG_SEG_BOOLEAN_CASE > seg_vec_parallel_cases
Test cases for parallelism.
BOOST_CHECK_PREDICATE(ArePolylineEndPointsNearCircle,(chain)(c.m_geom.m_center_point)(radius)(accuracy+epsilon))
BOOST_TEST_MESSAGE("Polyline has "<< chain.PointCount()<< " points")
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695