KiCad PCB EDA Suite
test_circle.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) 2021 Roberto Fernandez Bautista <[email protected]>
5 * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * This program is free software: you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation, either version 3 of the License, or (at your
10 * option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License along
18 * with this program. If not, see <http://www.gnu.org/licenses/>.
19 */
20
22#include <geometry/circle.h>
23#include <geometry/seg.h> // for SEG
24#include <geometry/shape.h> // for MIN_PRECISION_IU
25
26const int MIN_PRECISION_45DEG = KiROUND( (double) SHAPE::MIN_PRECISION_IU * 0.7071 );
27
28bool CompareLength( int aLengthA, int aLengthB )
29{
30 if( aLengthA > ( aLengthB + SHAPE::MIN_PRECISION_IU ) )
31 return false;
32 else if( aLengthA < ( aLengthB - SHAPE::MIN_PRECISION_IU ) )
33 return false;
34 else
35 return true;
36}
37
38bool CompareVector2I( const VECTOR2I& aVecA, const VECTOR2I& aVecB )
39{
40 if( !CompareLength(aVecA.x, aVecB.x) )
41 return false;
42 else if( !CompareLength( aVecA.y, aVecB.y ) )
43 return false;
44 else
45 return true;
46}
47
48
49BOOST_AUTO_TEST_SUITE( Circle )
50
51
55BOOST_AUTO_TEST_CASE( ParameterCtorMod )
56{
57 const VECTOR2I center( 10, 20 );
58 const int radius = 10;
59
60 // Build a circle referencing the previous values
61 CIRCLE circle( center, radius );
62
63 BOOST_CHECK_EQUAL( circle.Center, VECTOR2I( 10, 20 ) );
64 BOOST_CHECK_EQUAL( circle.Radius, 10 );
65
66 // Modify the parameters
67 circle.Center += VECTOR2I( 10, 10 );
68 circle.Radius += 20;
69
70 // Check the parameters were modified
71 BOOST_CHECK_EQUAL( circle.Center, VECTOR2I( 20, 30 ) );
72 BOOST_CHECK_EQUAL( circle.Radius, 30 );
73}
74
75
80{
81 std::string m_case_name;
85};
86
87// clang-format off
91static const std::vector<CIR_PT_BOOL_CASE> contains_cases = {
92 {
93 "on center",
94 { { 100, 100 }, 200 },
95 { 100, 100 },
96 false,
97 },
98 {
99 "0 deg",
100 { { 100, 100 }, 200 },
101 { 300, 100 },
102 true,
103 },
104 {
105 "0 deg, allowed tolerance pos",
106 { { 100, 100 }, 200 },
107 { 100, 300 + SHAPE::MIN_PRECISION_IU },
108 true,
109 },
110 {
111 "0 deg, allowed tolerance neg",
112 { { 100, 100 }, 200 },
113 { 100, 300 - SHAPE::MIN_PRECISION_IU },
114 true,
115 },
116 {
117 "0 deg, allowed tolerance pos + 1",
118 { { 100, 100 }, 200 },
119 { 100, 300 + SHAPE::MIN_PRECISION_IU + 1 },
120 false,
121 },
122 {
123 "0 deg, allowed tolerance neg - 1",
124 { { 100, 100 }, 200 },
125 { 100, 300 - SHAPE::MIN_PRECISION_IU - 1 },
126 false,
127 },
128 {
129 "45 deg",
130 { { 100, 100 }, 200 },
131 { 241, 241 },
132 true,
133 },
134 {
135 "45 deg, allowed tolerance pos",
136 { { 100, 100 }, 200 },
138 true,
139 },
140 {
141 "45 deg, allowed tolerance pos + 1",
142 { { 100, 100 }, 200 },
143 { 241 + MIN_PRECISION_45DEG + 1, 241 + MIN_PRECISION_45DEG + 1 },
144 false,
145 },
146 {
147 "90 deg",
148 { { 100, 100 }, 200 },
149 { 100, 300 },
150 true,
151 },
152 {
153 "180 deg",
154 { { 100, 100 }, 200 },
155 { -100, 100 },
156 true,
157 },
158 {
159 "270 deg",
160 { { 100, 100 }, 200 },
161 { 100, -100 },
162 true,
163 },
164};
165// clang-format on
166
167
169{
170 for( const auto& c : contains_cases )
171 {
172 BOOST_TEST_CONTEXT( c.m_case_name )
173 {
174 bool ret = c.m_circle.Contains( c.m_point );
175 BOOST_CHECK_EQUAL( ret, c.m_exp_result );
176 }
177 }
178}
179
180
181
186{
187 std::string m_case_name;
191};
192
193// clang-format off
197static const std::vector<CIR_PT_PT_CASE> nearest_point_cases = {
198 {
199 "on center",
200 { { 10, 10 }, 20 },
201 { 10, 10 },
202 { 30, 10 }, // special case: when at the circle return a point on the x axis
203 },
204 {
205 "inside",
206 { { 10, 10 }, 20 },
207 { 10, 20 },
208 { 10, 30 },
209 },
210 {
211 "outside",
212 { { 10, 10 }, 20 },
213 { 10, 50 },
214 { 10, 30 },
215 },
216 {
217 "angled",
218 { { 10, 10 }, 20 },
219 { 50, 50 },
220 { 24, 24 },
221 },
222};
223// clang-format on
224
225
226BOOST_AUTO_TEST_CASE( NearestPoint )
227{
228 for( const auto& c : nearest_point_cases )
229 {
230 BOOST_TEST_CONTEXT( c.m_case_name )
231 {
232 VECTOR2I ret = c.m_circle.NearestPoint( c.m_point );
233 BOOST_CHECK_EQUAL( ret, c.m_exp_result );
234 }
235 }
236}
237
238
243{
244 std::string m_case_name;
247 std::vector<VECTOR2I> m_exp_result;
248};
249
250// clang-format off
254static const std::vector<CIR_CIR_VECPT_CASE> intersect_circle_cases = {
255 {
256 "two point aligned",
257 { { 10, 10 }, 20 },
258 { { 10, 45 }, 20 },
259 {
260 { 0, 27 },
261 { 21, 27 },
262 },
263 },
264 {
265 "two point angled",
266 { { 10, 10 }, 20 },
267 { { 20, 20 }, 20 },
268 {
269 { 2, 28 },
270 { 28, 2 },
271 },
272 },
273 {
274 "tangent aligned, external",
275 { { 10, 10 }, 20 },
276 { { 10, 50 }, 20 },
277 {
278 { 10, 30 },
279 },
280 },
281 {
282 "tangent aligned, internal",
283 { { 10, 10 }, 40 },
284 { { 10, 30 }, 20 },
285 {
286 { 10, 50 },
287 },
288 },
289 {
290 "no intersection",
291 { { 10, 10 }, 20 },
292 { { 10, 51 }, 20 },
293 {
294 //no points
295 },
296 },
297 {
298 "KiROUND overflow 1",
299 { { 44798001, -94001999 }, 200001 },
300 { { 44797999, -94001999 }, 650001 },
301 {
302 //no points
303 },
304 },
305 {
306 "KiROUND overflow 2",
307 { { 50747999, -92402001 }, 650001 },
308 { { 50748001, -92402001 }, 200001 },
309 {
310 //no points
311 },
312 },
313 {
314 "KiROUND overflow 3",
315 { { 43947999, -92402001 }, 650001 },
316 { { 43948001, -92402001 }, 200001 },
317 {
318 //no points
319 },
320 },
321 {
322 "KiROUND overflow 4",
323 { { 46497999, -94001999 }, 200001 },
324 { { 46498001, -94001999 }, 650001 },
325 {
326 //no points
327 },
328 },
329 {
330 "Co-centered, same radius", // Exercise d=0
331 { { 205999999, 136367974 }, 3742026 },
332 { { 205999999, 136367974 }, 3742026 },
333 {
334 //no points
335 },
336 },
337};
338// clang-format on
339
340
341BOOST_AUTO_TEST_CASE( IntersectCircle )
342{
343 for( const auto& c : intersect_circle_cases )
344 {
345 BOOST_TEST_CONTEXT( c.m_case_name + " Case 1" )
346 {
347 std::vector<VECTOR2I> ret1 = c.m_circle1.Intersect( c.m_circle2 );
348 BOOST_CHECK_EQUAL( c.m_exp_result.size(), ret1.size() );
349 KI_TEST::CheckUnorderedMatches( c.m_exp_result, ret1, CompareVector2I );
350 }
351
352 BOOST_TEST_CONTEXT( c.m_case_name + " Case 2" )
353 {
354 // Test the other direction
355 std::vector<VECTOR2I> ret2 = c.m_circle2.Intersect( c.m_circle1 );
356 BOOST_CHECK_EQUAL( c.m_exp_result.size(), ret2.size() );
357 KI_TEST::CheckUnorderedMatches( c.m_exp_result, ret2, CompareVector2I );
358 }
359 }
360}
361
362
367{
368 std::string m_case_name;
371 std::vector<VECTOR2I> m_exp_result;
372};
373
374// clang-format off
378static const std::vector<SEG_SEG_VECPT_CASE> intersect_seg_cases = {
379 {
380 "two point aligned",
381 { { 0, 0 }, 20 },
382 { { 10, -40 }, {10, 40} },
383 {
384 { 10, -17 },
385 { 10, 17 },
386 },
387 },
388 {
389 "two point angled",
390 { { 0, 0 }, 20 },
391 { { -20, -40 }, {20, 40} },
392 {
393 { 8, 17 },
394 { -8, -17 },
395 },
396 },
397 {
398 "tangent",
399 { { 0, 0 }, 20 },
400 { { 20, 0 }, {20, 40} },
401 {
402 { 20, 0 }
403 },
404 },
405 {
406 "no intersection",
407 { { 0, 0 }, 20 },
408 { { 25, 0 }, {25, 40} },
409 {
410 //no points
411 },
412 },
413 {
414 "no intersection: seg end points inside circle",
415 { { 0, 0 }, 20 },
416 { { 0, 10 }, {0, -10} },
417 {
418 //no points
419 },
420 },
421};
422// clang-format on
423
424
426{
427 for( const auto& c : intersect_seg_cases )
428 {
429 BOOST_TEST_CONTEXT( c.m_case_name )
430 {
431 std::vector<VECTOR2I> ret = c.m_circle.Intersect( c.m_seg );
432 BOOST_CHECK_EQUAL( c.m_exp_result.size(), ret.size() );
433 KI_TEST::CheckUnorderedMatches( c.m_exp_result, ret, CompareVector2I );
434 }
435 }
436}
437
438
439// clang-format off
443static const std::vector<SEG_SEG_VECPT_CASE> intersect_line_cases = {
444 {
445 "two point aligned",
446 { { 0, 0 }, 20 },
447 { { 10, 45 }, {10, 40} },
448 {
449 { 10, -17 },
450 { 10, 17 },
451 },
452 },
453 {
454 "two point angled",
455 { { 0, 0 }, 20 },
456 { { -20, -40 }, {20, 40} },
457 {
458 { 8, 17 },
459 { -8, -17 },
460 },
461 },
462 {
463 "tangent",
464 { { 0, 0 }, 20 },
465 { { 20, 0 }, {20, 40} },
466 {
467 { 20, 0 }
468 },
469 },
470 {
471 "no intersection",
472 { { 0, 0 }, 20 },
473 { { 25, 0 }, {25, 40} },
474 {
475 //no points
476 },
477 },
478 {
479 "intersection, seg end points inside circle",
480 { { 0, 0 }, 20 },
481 { { 0, 10 }, {0, -10} },
482 {
483 { 0, 20 },
484 { 0, -20 }
485 },
486 },
487};
488// clang-format on
489
490
491BOOST_AUTO_TEST_CASE( IntersectLine )
492{
493 for( const auto& c : intersect_line_cases )
494 {
495 BOOST_TEST_CONTEXT( c.m_case_name )
496 {
497 std::vector<VECTOR2I> ret = c.m_circle.IntersectLine( c.m_seg );
498 BOOST_CHECK_EQUAL( c.m_exp_result.size(), ret.size() );
499 KI_TEST::CheckUnorderedMatches( c.m_exp_result, ret, CompareVector2I );
500 }
501 }
502}
503
504
505
510{
511 std::string m_case_name;
516};
517
518// clang-format off
522static const std::vector<CIR_SEG_VECPT_CASE> construct_tan_tan_pt_cases = {
523 {
524 "90 degree segs, point on seg",
525 { { 0, 0 }, { 0, 1000 } },
526 { { 0, 0 }, { 1000, 0 } },
527 { 0, 400 },
528 { { 400, 400} , 400 }, // result from simple geometric inference
529 },
530 {
531 "90 degree segs, point floating",
532 { { 0, 0 }, { 0, 1000 } },
533 { { 0, 0 }, { 1000, 0 } },
534 { 200, 100 },
535 { { 500, 500} , 500 }, // result from LibreCAD 2.2.0-rc2
536 },
537 {
538 "45 degree segs, point on seg",
539 { { 0, 0 }, { 1000, 0 } },
540 { { 0, 0 }, { 1000, 1000 } },
541 { 400, 0 },
542 { { 400, 166} , 166 },// result from LibreCAD 2.2.0-rc2
543 },
544 {
545 "45 degree segs, point floating",
546 { { 0, 0 }, { 1000000, 0 } },
547 { { 0, 0 }, { 1000000, 1000000 } },
548 { 200000, 100000 },
549 { { 332439, 137701} , 137701 }, // result from LibreCAD 2.2.0-rc2
550 },
551 {
552 "135 degree segs, point on seg",
553 { { 0, 0 }, { 1000000, 0 } },
554 { { 0, 0 }, { -1000000, 1000000 } },
555 { 400000, 0 },
556 { { 400009, 965709 } , 965709 }, // amended to get the test to pass
557 //{ { 400000, 965686 } , 965686 }, // result from LibreCAD 2.2.0-rc2
558 },
559 {
560 "135 degree segs, point floating",
561 { { 0, 0 }, { 1000, 0 } },
562 { { 0, 0 }, { -1000, 1000 } },
563 { 200, 100 },
564 { { 814, 1964} , 1964 }, // amended to get the test to pass
565 //{ { 822, 1985} , 1985 }, // result from LibreCAD 2.2.0-rc2
566 },
567 {
568 "point on intersection",
569 { { 10, 0 }, { 1000, 0 } },
570 { { 10, 0 }, { -1000, 1000 } },
571 { 10, 0 },
572 { { 10, 0} , 0 }, // special case: radius=0
573 },
574};
575// clang-format on
576
577
578BOOST_AUTO_TEST_CASE( ConstructFromTanTanPt )
579{
580 for( const auto& c : construct_tan_tan_pt_cases )
581 {
582 BOOST_TEST_CONTEXT( c.m_case_name )
583 {
584 CIRCLE circle;
585 circle.ConstructFromTanTanPt( c.m_segA, c.m_segB, c.m_pt );
586 BOOST_CHECK_MESSAGE( CompareVector2I( c.m_exp_result.Center, circle.Center ),
587 "\nCenter point mismatch: "
588 << "\n Got: " << circle.Center
589 << "\n Expected: " << c.m_exp_result.Center );
590
591 BOOST_CHECK_MESSAGE( CompareLength( c.m_exp_result.Radius, circle.Radius ),
592 "\nRadius mismatch: "
593 << "\n Got: " << circle.Radius
594 << "\n Expected: " << c.m_exp_result.Radius );
595 }
596 }
597}
598
599BOOST_AUTO_TEST_SUITE_END()
Represent basic circle geometry with utility geometry functions.
Definition: circle.h:33
VECTOR2I Center
Public to make access simpler.
Definition: circle.h:116
int Radius
Public to make access simpler.
Definition: circle.h:115
CIRCLE & ConstructFromTanTanPt(const SEG &aLineA, const SEG &aLineB, const VECTOR2I &aP)
Construct this circle such that it is tangent to the given segments and passes through the given poin...
Definition: circle.cpp:51
Definition: seg.h:42
static const int MIN_PRECISION_IU
This is the minimum precision for all the points in a shape.
Definition: shape.h:128
void CheckUnorderedMatches(const EXP_CONT &aExpected, const FOUND_CONT &aFound, MATCH_PRED aMatchPredicate)
Check that a container of "found" objects matches a container of "expected" objects.
Struct to hold test cases for two circles, and an vector of points.
std::string m_case_name
std::vector< VECTOR2I > m_exp_result
Struct to hold test cases for a given circle, a point and an expected return boolean.
Definition: test_circle.cpp:80
std::string m_case_name
Definition: test_circle.cpp:81
Struct to hold test cases for a given circle, a point and an expected return point.
std::string m_case_name
VECTOR2I m_point
VECTOR2I m_exp_result
Struct to hold test cases for two lines, a point and an expected returned circle.
std::string m_case_name
Struct to hold test cases for a circle, a line and an expected vector of points.
std::vector< VECTOR2I > m_exp_result
std::string m_case_name
bool CompareLength(int aLengthA, int aLengthB)
Definition: test_circle.cpp:28
static const std::vector< CIR_SEG_VECPT_CASE > construct_tan_tan_pt_cases
Test cases for #CIRCLE::Intersect( const SEG& aSeg )
BOOST_AUTO_TEST_CASE(ParameterCtorMod)
Checks whether the construction of a circle referencing external parameters works and that the parame...
Definition: test_circle.cpp:55
bool CompareVector2I(const VECTOR2I &aVecA, const VECTOR2I &aVecB)
Definition: test_circle.cpp:38
static const std::vector< CIR_PT_PT_CASE > nearest_point_cases
Test cases for CIRCLE::NearestPoint.
static const std::vector< CIR_CIR_VECPT_CASE > intersect_circle_cases
Test cases for #CIRCLE::Intersect( const CIRCLE& aCircle )
static const std::vector< SEG_SEG_VECPT_CASE > intersect_line_cases
Test cases for #CIRCLE::IntersectLine( const SEG& aSeg )
static const std::vector< SEG_SEG_VECPT_CASE > intersect_seg_cases
Test cases for #CIRCLE::Intersect( const SEG& aSeg )
const int MIN_PRECISION_45DEG
Definition: test_circle.cpp:26
static const std::vector< CIR_PT_BOOL_CASE > contains_cases
Test cases for CIRCLE::Contains.
Definition: test_circle.cpp:91
#define BOOST_TEST_CONTEXT(A)
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:80
VECTOR2< int > VECTOR2I
Definition: vector2d.h:607