kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #39253
[PATCH] QA common: SEG tests
Hi,
Some tests of the SEG class. Distance and Collide are essential
foundations of nearly all the other SHAPE collision tests (and
therefore DRC and routing). So a good thing to have tested.
Cheers,
John
From 526ce7a636c24645aed6baf7c2d1015b0ffbbebb Mon Sep 17 00:00:00 2001
From: John Beard <john.j.beard@gmail.com>
Date: Fri, 1 Feb 2019 14:54:02 +0000
Subject: [PATCH] QA: Add Distance, Collide, Collinear tests on SEG
SEG collisions and distances are a fundamental part of SHAPE collision testing
and are therefore critical for DRC correctness.
Also a few Collinear tests.
---
qa/common/geometry/test_segment.cpp | 370 ++++++++++++++++++++++++++++
1 file changed, 370 insertions(+)
diff --git a/qa/common/geometry/test_segment.cpp b/qa/common/geometry/test_segment.cpp
index 679b1f4b7..db13bec6d 100644
--- a/qa/common/geometry/test_segment.cpp
+++ b/qa/common/geometry/test_segment.cpp
@@ -27,6 +27,127 @@
#include <geometry/seg.h>
+/**
+ * Predicate to check expected collision between two segments
+ * @param aSegA the first #SEG
+ * @param aSegB the second #SEG
+ * @param aClearance the collision clearance
+ * @param aExp expected collision
+ * @return does the distance calculated agree?
+ */
+bool SegCollideCorrect( const SEG& aSegA, const SEG& aSegB, int aClearance, bool aExp )
+{
+ const bool AtoB = aSegA.Collide( aSegB, aClearance );
+ const bool BtoA = aSegB.Collide( aSegA, aClearance );
+
+ const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
+
+ if( AtoB != BtoA )
+ {
+ std::stringstream ss;
+ ss << "Segment collision is not the same in both directions: expected " << aExp << ", got "
+ << AtoB << " & " << BtoA;
+ BOOST_TEST_INFO( ss.str() );
+ }
+ else if( !ok )
+ {
+ std::stringstream ss;
+ ss << "Collision incorrect: expected " << aExp << ", got " << AtoB;
+ BOOST_TEST_INFO( ss.str() );
+ }
+
+ return ok;
+}
+
+
+/**
+ * Predicate to check expected distance between two segments
+ * @param aSegA the first #SEG
+ * @param aSegB the second #SEG
+ * @param aExp expected distance
+ * @return does the distance calculated agree?
+ */
+bool SegDistanceCorrect( const SEG& aSegA, const SEG& aSegB, int aExp )
+{
+ const int AtoB = aSegA.Distance( aSegB );
+ const int BtoA = aSegB.Distance( aSegA );
+
+ bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
+
+ if( AtoB != BtoA )
+ {
+ std::stringstream ss;
+ ss << "Segment distance is not the same in both directions: expected " << aExp << ", got "
+ << AtoB << " & " << BtoA;
+ BOOST_TEST_INFO( ss.str() );
+ }
+ else if( !ok )
+ {
+ std::stringstream ss;
+ ss << "Distance incorrect: expected " << aExp << ", got " << AtoB;
+ BOOST_TEST_INFO( ss.str() );
+ }
+
+ // Sanity check: the collision should be consistent with the distance
+ ok = ok && SegCollideCorrect( aSegA, aSegB, 0, aExp == 0 );
+
+ return ok;
+}
+
+/**
+ * Predicate to check expected distance between a segment and a point
+ * @param aSegA the segment
+ * @param aVec the vector (point)
+ * @param aExp expected distance
+ * @return does the distance calculated agree?
+ */
+bool SegVecDistanceCorrect( const SEG& aSeg, const VECTOR2I& aVec, int aExp )
+{
+ const int dist = aSeg.Distance( aVec );
+
+ bool ok = ( dist == aExp );
+
+ if( !ok )
+ {
+ std::stringstream ss;
+ ss << "Distance incorrect: expected " << aExp << ", got " << dist;
+ BOOST_TEST_INFO( ss.str() );
+ }
+
+ return ok;
+}
+
+/**
+ * Predicate to check expected collision between two segments
+ * @param aSegA the first #SEG
+ * @param sSegB the second #SEG
+ * @param aExp expected collinearity
+ * @return does the collinearity calculated agree?
+ */
+bool SegCollinearCorrect( const SEG& aSegA, const SEG& aSegB, bool aExp )
+{
+ const bool AtoB = aSegA.Collinear( aSegB );
+ const bool BtoA = aSegB.Collinear( aSegA );
+
+ const bool ok = ( AtoB == aExp ) && ( BtoA == aExp );
+
+ if( AtoB != BtoA )
+ {
+ std::stringstream ss;
+ ss << "Segment collinearity is not the same in both directions: expected " << aExp
+ << ", got " << AtoB << " & " << BtoA;
+ BOOST_TEST_INFO( ss.str() );
+ }
+ else if( !ok )
+ {
+ std::stringstream ss;
+ ss << "Collinearity incorrect: expected " << aExp << ", got " << AtoB;
+ BOOST_TEST_INFO( ss.str() );
+ }
+
+ return ok;
+}
+
BOOST_AUTO_TEST_SUITE( Segment )
@@ -54,4 +175,253 @@ BOOST_AUTO_TEST_CASE( EndpointCtorMod )
BOOST_CHECK_EQUAL( segment.B, VECTOR2I( 200, 300 ) );
}
+struct SEG_SEG_DISTANCE_CASE
+{
+ std::string m_case_name;
+ SEG m_seg_a;
+ SEG m_seg_b;
+ int m_exp_dist;
+};
+
+
+// clang-format off
+static const std::vector<SEG_SEG_DISTANCE_CASE> seg_seg_dist_cases = {
+ {
+ "Parallel, 10 apart",
+ { { 0, 0 }, { 10, 0 } },
+ { { 0, 10 }, { 10, 10 } },
+ 10,
+ },
+ {
+ "Non-parallel, 10 apart",
+ { { 0, -5 }, { 10, 0 } },
+ { { 0, 10 }, { 10, 10 } },
+ 10,
+ },
+ {
+ "Co-incident",
+ { { 0, 0 }, { 30, 0 } },
+ { { 10, 0 }, { 20, 0 } },
+ 0,
+ },
+ {
+ "Crossing",
+ { { 0, -10 }, { 0, 10 } },
+ { { -20, 0 }, { 20, 0 } },
+ 0,
+ },
+ {
+ "T-junction",
+ { { 0, -10 }, { 0, 10 } },
+ { { -20, 0 }, { 0, 0 } },
+ 0,
+ },
+ {
+ "T-junction (no touch)",
+ { { 0, -10 }, { 0, 10 } },
+ { { -20, 0 }, { -2, 0 } },
+ 2,
+ },
+};
+// clang-format on
+
+
+BOOST_AUTO_TEST_CASE( SegSegDistance )
+{
+ for( const auto& c : seg_seg_dist_cases )
+ {
+ BOOST_TEST_CONTEXT( c.m_case_name )
+ {
+ BOOST_CHECK_PREDICATE( SegDistanceCorrect, ( c.m_seg_a )( c.m_seg_b )( c.m_exp_dist ) );
+ }
+ }
+}
+
+
+struct SEG_VECTOR_DISTANCE_CASE
+{
+ std::string m_case_name;
+ SEG m_seg;
+ VECTOR2I m_vec;
+ int m_exp_dist;
+};
+
+
+// clang-format off
+static const std::vector<SEG_VECTOR_DISTANCE_CASE> seg_vec_dist_cases = {
+ {
+ "On endpoint",
+ { { 0, 0 }, { 10, 0 } },
+ { 0, 0 },
+ 0,
+ },
+ {
+ "On segment",
+ { { 0, 0 }, { 10, 0 } },
+ { 3, 0 },
+ 0,
+ },
+ {
+ "At side",
+ { { 0, 0 }, { 10, 0 } },
+ { 3, 2 },
+ 2,
+ },
+ {
+ "At end (collinear)",
+ { { 0, 0 }, { 10, 0 } },
+ { 12, 0 },
+ 2,
+ },
+ {
+ "At end (not collinear)",
+ { { 0, 0 }, { 1000, 0 } },
+ { 1000 + 200, 200 },
+ 282, // sqrt(200^2 + 200^2), rounded down
+ },
+};
+// clang-format on
+
+
+BOOST_AUTO_TEST_CASE( SegVecDistance )
+{
+ for( const auto& c : seg_vec_dist_cases )
+ {
+ BOOST_TEST_CONTEXT( c.m_case_name )
+ {
+ BOOST_CHECK_PREDICATE( SegVecDistanceCorrect, ( c.m_seg )( c.m_vec )( c.m_exp_dist ) );
+ }
+ }
+}
+
+
+/**
+ * Test cases for collisions (with clearance, for no clearance,
+ * it's just a SEG_SEG_DISTANCE_CASE of 0)
+ */
+struct SEG_SEG_COLLIDE_CASE
+{
+ std::string m_case_name;
+ SEG m_seg_a;
+ SEG m_seg_b;
+ int m_clearance;
+ bool m_exp_coll;
+};
+
+
+// clang-format off
+static const std::vector<SEG_SEG_COLLIDE_CASE> seg_seg_coll_cases = {
+ {
+ "Parallel, 10 apart, 5 clear",
+ { { 0, 0 }, { 10, 0 } },
+ { { 0, 10 }, { 10, 10 } },
+ 5,
+ false,
+ },
+ {
+ "Parallel, 10 apart, 10 clear",
+ { { 0, 0 }, { 10, 0 } },
+ { { 0, 10 }, { 10, 10 } },
+ 10,
+ false,
+ },
+ {
+ "Parallel, 10 apart, 11 clear",
+ { { 0, 0 }, { 10, 0 } },
+ { { 0, 10 }, { 10, 10 } },
+ 11,
+ true,
+ },
+ {
+ "T-junction, 2 apart, 2 clear",
+ { { 0, -10 }, { 0, 0 } },
+ { { -20, 0 }, { -2, 0 } },
+ 2,
+ false,
+ },
+ {
+ "T-junction, 2 apart, 3 clear",
+ { { 0, -10 }, { 0, 0 } },
+ { { -20, 0 }, { -2, 0 } },
+ 3,
+ true,
+ },
+};
+// clang-format on
+
+
+BOOST_AUTO_TEST_CASE( SegSegCollision )
+{
+ for( const auto& c : seg_seg_coll_cases )
+ {
+ BOOST_TEST_CONTEXT( c.m_case_name )
+ {
+ BOOST_CHECK_PREDICATE( SegCollideCorrect,
+ ( c.m_seg_a )( c.m_seg_b )( c.m_clearance )( c.m_exp_coll ) );
+ }
+ }
+}
+
+
+/**
+ * Test cases for collinearity
+ */
+struct SEG_VEC_COLLINEAR_CASE
+{
+ std::string m_case_name;
+ SEG m_seg_a;
+ SEG m_seg_b;
+ bool m_exp_coll;
+};
+
+
+// clang-format off
+static const std::vector<SEG_VEC_COLLINEAR_CASE> seg_vec_collinear_cases = {
+ {
+ "coincident",
+ { { 0, 0 }, { 10, 0 } },
+ { { 0, 0 }, { 10, 0 } },
+ true,
+ },
+ {
+ "end-to-end",
+ { { 0, 0 }, { 10, 0 } },
+ { { 10, 0 }, { 20, 0 } },
+ true,
+ },
+ {
+ "In segment",
+ { { 0, 0 }, { 10, 0 } },
+ { { 4, 0 }, { 7, 0 } },
+ true,
+ },
+ {
+ "At side, parallel",
+ { { 0, 0 }, { 10, 0 } },
+ { { 4, 1 }, { 7, 1 } },
+ false,
+ },
+ {
+ "crossing",
+ { { 0, 0 }, { 10, 0 } },
+ { { 5, -5 }, { 5, 5 } },
+ false,
+ },
+};
+// clang-format on
+
+
+BOOST_AUTO_TEST_CASE( SegVecCollinear )
+{
+ for( const auto& c : seg_vec_collinear_cases )
+ {
+ BOOST_TEST_CONTEXT( c.m_case_name )
+ {
+ BOOST_CHECK_PREDICATE(
+ SegCollinearCorrect, ( c.m_seg_a )( c.m_seg_b )( c.m_exp_coll ) );
+ }
+ }
+}
+
+
BOOST_AUTO_TEST_SUITE_END()
--
2.20.1
Follow ups