KiCad PCB EDA Suite
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 <alejandro.garciamontoro@gmail.com>
6  * Copyright (C) 2019-2021 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 
28 #include <geometry/seg.h>
29 
38 bool SegCollideCorrect( const SEG& aSegA, const SEG& aSegB, int aClearance, bool aExp )
39 {
40  const bool AtoB = aSegA.Collide( aSegB, aClearance );
41  const bool BtoA = aSegB.Collide( aSegA, aClearance );
42 
43  const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
44 
45  if( AtoB != BtoA )
46  {
47  std::stringstream ss;
48  ss << "Segment collision is not the same in both directions: expected " << aExp << ", got "
49  << AtoB << " & " << BtoA;
50  BOOST_TEST_INFO( ss.str() );
51  }
52  else if( !ok )
53  {
54  std::stringstream ss;
55  ss << "Collision incorrect: expected " << aExp << ", got " << AtoB;
56  BOOST_TEST_INFO( ss.str() );
57  }
58 
59  return ok;
60 }
61 
62 
70 bool SegDistanceCorrect( const SEG& aSegA, const SEG& aSegB, int aExp )
71 {
72  const int AtoB = aSegA.Distance( aSegB );
73  const int BtoA = aSegB.Distance( aSegA );
74 
75  bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
76 
77  if( AtoB != BtoA )
78  {
79  std::stringstream ss;
80  ss << "Segment distance is not the same in both directions: expected " << aExp << ", got "
81  << AtoB << " & " << BtoA;
82  BOOST_TEST_INFO( ss.str() );
83  }
84  else if( !ok )
85  {
86  std::stringstream ss;
87  ss << "Distance incorrect: expected " << aExp << ", got " << AtoB;
88  BOOST_TEST_INFO( ss.str() );
89  }
90 
91  // Sanity check: the collision should be consistent with the distance
92  ok = ok && SegCollideCorrect( aSegA, aSegB, 0, aExp == 0 );
93 
94  return ok;
95 }
96 
104 bool SegVecDistanceCorrect( const SEG& aSeg, const VECTOR2I& aVec, int aExp )
105 {
106  const int dist = aSeg.Distance( aVec );
107 
108  bool ok = ( dist == aExp );
109 
110  if( !ok )
111  {
112  std::stringstream ss;
113  ss << "Distance incorrect: expected " << aExp << ", got " << dist;
114  BOOST_TEST_INFO( ss.str() );
115  }
116 
117  return ok;
118 }
119 
127 bool SegCollinearCorrect( const SEG& aSegA, const SEG& aSegB, bool aExp )
128 {
129  const bool AtoB = aSegA.Collinear( aSegB );
130  const bool BtoA = aSegB.Collinear( aSegA );
131 
132  const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
133 
134  if( AtoB != BtoA )
135  {
136  std::stringstream ss;
137  ss << "Segment collinearity is not the same in both directions: expected " << aExp
138  << ", got " << AtoB << " & " << BtoA;
139  BOOST_TEST_INFO( ss.str() );
140  }
141  else if( !ok )
142  {
143  std::stringstream ss;
144  ss << "Collinearity incorrect: expected " << aExp << ", got " << AtoB;
145  BOOST_TEST_INFO( ss.str() );
146  }
147 
148  return ok;
149 }
150 
159 bool SegParallelCorrect( const SEG& aSegA, const SEG& aSegB, bool aExp )
160 {
161  const bool AtoB = aSegA.ApproxParallel( aSegB );
162  const bool BtoA = aSegB.ApproxParallel( aSegA );
163 
164  const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
165 
166  if( AtoB != BtoA )
167  {
168  std::stringstream ss;
169  ss << "Segment parallelism is not the same in both directions: expected " << aExp
170  << ", got AtoB: " << AtoB << " BtoA:" << BtoA;
171  BOOST_TEST_INFO( ss.str() );
172  }
173  else if( !ok )
174  {
175  std::stringstream ss;
176  ss << "Parallelism incorrect: expected " << aExp << ", got " << AtoB;
177  BOOST_TEST_INFO( ss.str() );
178  }
179 
180  return ok;
181 }
182 
191 bool SegPerpendicularCorrect( const SEG& aSegA, const SEG& aSegB, bool aExp )
192 {
193  const bool AtoB = aSegA.ApproxPerpendicular( aSegB );
194  const bool BtoA = aSegB.ApproxPerpendicular( aSegA );
195 
196  const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
197 
198  if( AtoB != BtoA )
199  {
200  std::stringstream ss;
201  ss << "Segment perpendicularity is not the same in both directions: expected " << aExp
202  << ", got AtoB: " << AtoB << " BtoA:" << BtoA;
203  BOOST_TEST_INFO( ss.str() );
204  }
205  else if( !ok )
206  {
207  std::stringstream ss;
208  ss << "Perpendicularity incorrect: expected " << aExp << ", got " << AtoB;
209  BOOST_TEST_INFO( ss.str() );
210  }
211 
212  return ok;
213 }
214 
215 BOOST_AUTO_TEST_SUITE( Segment )
216 
217 
221 BOOST_AUTO_TEST_CASE( EndpointCtorMod )
222 {
223  const VECTOR2I pointA{ 10, 20 };
224  const VECTOR2I pointB{ 100, 200 };
225 
226  // Build a segment referencing the previous points
227  SEG segment( pointA, pointB );
228 
229  BOOST_CHECK_EQUAL( pointA, VECTOR2I( 10, 20 ) );
230  BOOST_CHECK_EQUAL( pointB, VECTOR2I( 100, 200 ) );
231 
232  // Modify the ends of the segments
233  segment.A += VECTOR2I( 10, 10 );
234  segment.B += VECTOR2I( 100, 100 );
235 
236  // Check that the ends in segment are modified
237  BOOST_CHECK_EQUAL( segment.A, VECTOR2I( 20, 30 ) );
238  BOOST_CHECK_EQUAL( segment.B, VECTOR2I( 200, 300 ) );
239 }
240 
242 {
243  std::string m_case_name;
247 };
248 
249 
250 // clang-format off
251 static const std::vector<SEG_SEG_DISTANCE_CASE> seg_seg_dist_cases = {
252  {
253  "Parallel, 10 apart",
254  { { 0, 0 }, { 10, 0 } },
255  { { 0, 10 }, { 10, 10 } },
256  10,
257  },
258  {
259  "Non-parallel, 10 apart",
260  { { 0, -5 }, { 10, 0 } },
261  { { 0, 10 }, { 10, 10 } },
262  10,
263  },
264  {
265  "Co-incident",
266  { { 0, 0 }, { 30, 0 } },
267  { { 10, 0 }, { 20, 0 } },
268  0,
269  },
270  {
271  "Crossing",
272  { { 0, -10 }, { 0, 10 } },
273  { { -20, 0 }, { 20, 0 } },
274  0,
275  },
276  {
277  "T-junction",
278  { { 0, -10 }, { 0, 10 } },
279  { { -20, 0 }, { 0, 0 } },
280  0,
281  },
282  {
283  "T-junction (no touch)",
284  { { 0, -10 }, { 0, 10 } },
285  { { -20, 0 }, { -2, 0 } },
286  2,
287  },
288 };
289 // clang-format on
290 
291 
292 BOOST_AUTO_TEST_CASE( SegSegDistance )
293 {
294  for( const auto& c : seg_seg_dist_cases )
295  {
296  BOOST_TEST_CONTEXT( c.m_case_name )
297  {
298  BOOST_CHECK_PREDICATE( SegDistanceCorrect, ( c.m_seg_a )( c.m_seg_b )( c.m_exp_dist ) );
299  }
300  }
301 }
302 
303 
305 {
306  std::string m_case_name;
310 };
311 
312 
313 // clang-format off
314 static const std::vector<SEG_VECTOR_DISTANCE_CASE> seg_vec_dist_cases = {
315  {
316  "On endpoint",
317  { { 0, 0 }, { 10, 0 } },
318  { 0, 0 },
319  0,
320  },
321  {
322  "On segment",
323  { { 0, 0 }, { 10, 0 } },
324  { 3, 0 },
325  0,
326  },
327  {
328  "At side",
329  { { 0, 0 }, { 10, 0 } },
330  { 3, 2 },
331  2,
332  },
333  {
334  "At end (collinear)",
335  { { 0, 0 }, { 10, 0 } },
336  { 12, 0 },
337  2,
338  },
339  {
340  "At end (not collinear)",
341  { { 0, 0 }, { 1000, 0 } },
342  { 1000 + 200, 200 },
343  282, // sqrt(200^2 + 200^2), rounded down
344  },
345 };
346 // clang-format on
347 
348 
349 BOOST_AUTO_TEST_CASE( SegVecDistance )
350 {
351  for( const auto& c : seg_vec_dist_cases )
352  {
353  BOOST_TEST_CONTEXT( c.m_case_name )
354  {
355  BOOST_CHECK_PREDICATE( SegVecDistanceCorrect, ( c.m_seg )( c.m_vec )( c.m_exp_dist ) );
356  }
357  }
358 }
359 
360 
366 {
367  std::string m_case_name;
372 };
373 
374 
375 // clang-format off
376 static const std::vector<SEG_SEG_COLLIDE_CASE> seg_seg_coll_cases = {
377  {
378  "Parallel, 10 apart, 5 clear",
379  { { 0, 0 }, { 10, 0 } },
380  { { 0, 10 }, { 10, 10 } },
381  5,
382  false,
383  },
384  {
385  "Parallel, 10 apart, 10 clear",
386  { { 0, 0 }, { 10, 0 } },
387  { { 0, 10 }, { 10, 10 } },
388  10,
389  false,
390  },
391  {
392  "Parallel, 10 apart, 11 clear",
393  { { 0, 0 }, { 10, 0 } },
394  { { 0, 10 }, { 10, 10 } },
395  11,
396  true,
397  },
398  {
399  "T-junction, 2 apart, 2 clear",
400  { { 0, -10 }, { 0, 0 } },
401  { { -20, 0 }, { -2, 0 } },
402  2,
403  false,
404  },
405  {
406  "T-junction, 2 apart, 3 clear",
407  { { 0, -10 }, { 0, 0 } },
408  { { -20, 0 }, { -2, 0 } },
409  3,
410  true,
411  },
412 };
413 // clang-format on
414 
415 
416 BOOST_AUTO_TEST_CASE( SegSegCollision )
417 {
418  for( const auto& c : seg_seg_coll_cases )
419  {
420  BOOST_TEST_CONTEXT( c.m_case_name )
421  {
422  BOOST_CHECK_PREDICATE( SegCollideCorrect,
423  ( c.m_seg_a )( c.m_seg_b )( c.m_clearance )( c.m_exp_coll ) );
424  }
425  }
426 }
427 
428 
433 {
434  std::string m_case_name;
438 };
439 
440 // clang-format off
444 static const std::vector<SEG_SEG_BOOLEAN_CASE> seg_vec_collinear_cases = {
445  {
446  "coincident",
447  { { 0, 0 }, { 10, 0 } },
448  { { 0, 0 }, { 10, 0 } },
449  true,
450  },
451  {
452  "end-to-end",
453  { { 0, 0 }, { 10, 0 } },
454  { { 10, 0 }, { 20, 0 } },
455  true,
456  },
457  {
458  "In segment",
459  { { 0, 0 }, { 10, 0 } },
460  { { 4, 0 }, { 7, 0 } },
461  true,
462  },
463  {
464  "At side, parallel",
465  { { 0, 0 }, { 10, 0 } },
466  { { 4, 1 }, { 7, 1 } },
467  false,
468  },
469  {
470  "crossing",
471  { { 0, 0 }, { 10, 0 } },
472  { { 5, -5 }, { 5, 5 } },
473  false,
474  },
475 };
476 // clang-format on
477 
478 
479 BOOST_AUTO_TEST_CASE( SegSegCollinear )
480 {
481  for( const auto& c : seg_vec_collinear_cases )
482  {
483  BOOST_TEST_CONTEXT( c.m_case_name )
484  {
485  BOOST_CHECK_PREDICATE( SegCollinearCorrect,
486  ( c.m_seg_a )( c.m_seg_b )( c.m_exp_result ) );
487  }
488  }
489 }
490 
491 
492 // clang-format off
496 static const std::vector<SEG_SEG_BOOLEAN_CASE> seg_vec_parallel_cases = {
497  {
498  "coincident",
499  { { 0, 0 }, { 10, 0 } },
500  { { 0, 0 }, { 10, 0 } },
501  true,
502  },
503  {
504  "end-to-end",
505  { { 0, 0 }, { 10, 0 } },
506  { { 10, 0 }, { 20, 0 } },
507  true,
508  },
509  {
510  "In segment",
511  { { 0, 0 }, { 10, 0 } },
512  { { 4, 0 }, { 7, 0 } },
513  true,
514  },
515  {
516  "At side, parallel",
517  { { 0, 0 }, { 10, 0 } },
518  { { 4, 1 }, { 7, 1 } },
519  true,
520  },
521  {
522  "crossing",
523  { { 0, 0 }, { 10, 0 } },
524  { { 5, -5 }, { 5, 5 } },
525  false,
526  },
527 };
528 // clang-format on
529 
530 
531 BOOST_AUTO_TEST_CASE( SegSegParallel )
532 {
533  for( const auto& c : seg_vec_parallel_cases )
534  {
535  BOOST_TEST_CONTEXT( c.m_case_name )
536  {
537  BOOST_CHECK_PREDICATE( SegParallelCorrect,
538  ( c.m_seg_a )( c.m_seg_b )( c.m_exp_result ) );
539  }
540  }
541 }
542 
543 
544 // clang-format off
548 static const std::vector<SEG_SEG_BOOLEAN_CASE> seg_vec_perpendicular_cases = {
549  {
550  "coincident",
551  { { 0, 0 }, { 10, 0 } },
552  { { 0, 0 }, { 10, 0 } },
553  false,
554  },
555  {
556  "end-to-end",
557  { { 0, 0 }, { 10, 0 } },
558  { { 10, 0 }, { 20, 0 } },
559  false,
560  },
561  {
562  "In segment",
563  { { 0, 0 }, { 10, 0 } },
564  { { 4, 0 }, { 7, 0 } },
565  false,
566  },
567  {
568  "At side, parallel",
569  { { 0, 0 }, { 10, 0 } },
570  { { 4, 1 }, { 7, 1 } },
571  false,
572  },
573  {
574  "crossing 45 deg",
575  { { 0, 0 }, { 10, 0 } },
576  { { 0, 0 }, { 5, 5 } },
577  false,
578  },
579  {
580  "very nearly perpendicular",
581  { { 0, 0 }, { 10, 0 } },
582  { { 0, 0 }, { 1, 10 } },
583  true, //allow error margin of 1 IU
584  },
585  {
586  "not really perpendicular",
587  { { 0, 0 }, { 10, 0 } },
588  { { 0, 0 }, { 3, 10 } },
589  false,
590  },
591  {
592  "perpendicular",
593  { { 0, 0 }, { 10, 0 } },
594  { { 0, 0 }, { 0, 10 } },
595  true,
596  },
597  {
598  "perpendicular not intersecting",
599  { { 0, 0 }, { 10, 0 } },
600  { { 15, 5 }, { 15, 10 } },
601  true,
602  },
603 };
604 // clang-format on
605 
606 
607 BOOST_AUTO_TEST_CASE( SegSegPerpendicular )
608 {
609  for( const auto& c : seg_vec_perpendicular_cases )
610  {
611  BOOST_TEST_CONTEXT( c.m_case_name )
612  {
613  BOOST_CHECK_PREDICATE( SegPerpendicularCorrect,
614  ( c.m_seg_a )( c.m_seg_b )( c.m_exp_result ) );
615  }
616  }
617 }
618 
619 
624 {
625  std::string m_case_name;
628 };
629 
630 
631 // clang-format off
635 static const std::vector<SEG_VEC_CASE> segment_and_point_cases = {
636  {
637  "Horizontal: point on edge of seg",
638  { { 0, 0 }, { 10, 0 } },
639  { 0, 0 },
640  },
641  {
642  "Horizontal: point in middle of seg",
643  { { 0, 0 }, { 10, 0 } },
644  { 5, 0 },
645  },
646  {
647  "Horizontal: point outside seg",
648  { { 0, 0 }, { 10, 0 } },
649  { 20, 20 },
650  },
651  {
652  "Vertical: point on edge of seg",
653  { { 0, 0 }, { 0, 10 } },
654  { 0, 0 },
655  },
656  {
657  "Vertical: point in middle of seg",
658  { { 0, 0 }, { 0, 10 } },
659  { 0, 5 },
660  },
661  {
662  "Vertical: point outside seg",
663  { { 0, 0 }, { 0, 10 } },
664  { 20, 20 },
665  },
666 };
667 // clang-format on
668 
669 
670 BOOST_AUTO_TEST_CASE( SegCreateParallel )
671 {
672  for( const auto& c : segment_and_point_cases )
673  {
674  BOOST_TEST_CONTEXT( c.m_case_name )
675  {
676  SEG perpendicular = c.m_seg.ParallelSeg( c.m_vec );
677 
678  BOOST_CHECK_PREDICATE( SegParallelCorrect, ( perpendicular )( c.m_seg )( true ) );
679  BOOST_CHECK_PREDICATE( SegVecDistanceCorrect, ( perpendicular )( c.m_vec )( 0 ) );
680  }
681  }
682 }
683 
684 BOOST_AUTO_TEST_CASE( SegCreatePerpendicular )
685 {
686  for( const auto& c : segment_and_point_cases )
687  {
688  BOOST_TEST_CONTEXT( c.m_case_name )
689  {
690  SEG perpendicular = c.m_seg.PerpendicularSeg( c.m_vec );
691 
692  BOOST_CHECK_PREDICATE( SegPerpendicularCorrect, ( perpendicular )( c.m_seg )( true ) );
693  BOOST_CHECK_PREDICATE( SegVecDistanceCorrect, ( perpendicular )( c.m_vec )( 0 ) );
694  }
695  }
696 }
697 
698 BOOST_AUTO_TEST_SUITE_END()
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.h:239
static const std::vector< SEG_SEG_BOOLEAN_CASE > seg_vec_parallel_cases
Test cases for paralellism.
bool ApproxPerpendicular(const SEG &aSeg) const
Definition: seg.h:306
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition: seg.cpp:148
Test cases for collisions (with clearance, for no clearance, it's just a SEG_SEG_DISTANCE_CASE of 0)
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:172
Define a general 2D-vector/point.
Definition: vector2d.h:61
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:157
VECTOR2I m_vec
BOOST_AUTO_TEST_CASE(EndpointCtorMod)
Checks whether the construction of a segment referencing external points works and that the endpoints...
bool SegVecDistanceCorrect(const SEG &aSeg, const VECTOR2I &aVec, int aExp)
Predicate to check expected distance between a segment and a point.
std::string m_case_name
static const std::vector< SEG_SEG_BOOLEAN_CASE > seg_vec_collinear_cases
Test cases for collinearity.
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:295
static const std::vector< SEG_VEC_CASE > segment_and_point_cases
Test cases to create segments passing through a point.
static const std::vector< SEG_SEG_BOOLEAN_CASE > seg_vec_perpendicular_cases
Test cases for perpendicularity.
bool SegPerpendicularCorrect(const SEG &aSegA, const SEG &aSegB, bool aExp)
Predicate to check expected perpendicularity between two segments.
bool SegCollideCorrect(const SEG &aSegA, const SEG &aSegB, int aClearance, bool aExp)
Predicate to check expected collision between two segments.
#define BOOST_TEST_CONTEXT(A)
static const std::vector< SEG_SEG_COLLIDE_CASE > seg_seg_coll_cases
static const std::vector< SEG_SEG_DISTANCE_CASE > seg_seg_dist_cases
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:273
Definition: seg.h:41
static const std::vector< SEG_VECTOR_DISTANCE_CASE > seg_vec_dist_cases
bool SegParallelCorrect(const SEG &aSegA, const SEG &aSegB, bool aExp)
Predicate to check expected parallelism between two segments.
bool SegDistanceCorrect(const SEG &aSegA, const SEG &aSegB, int aExp)
Predicate to check expected distance between two segments.
Struct to hold cases for operations with a SEG, and a VECTOR2I.
VECTOR2I A
Definition: seg.h:49
bool SegCollinearCorrect(const SEG &aSegA, const SEG &aSegB, bool aExp)
Predicate to check expected collision between two segments.
#define BOOST_TEST_INFO(A)
If HAVE_EXPECTED_FAILURES is defined, this means that boost::unit_test::expected_failures is availabl...
Struct to hold general cases for collinearity, paralellism and perpendicularity.
VECTOR2I B
Definition: seg.h:50