kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #38934
[PATCH] SHAPE_ARC tests
Hi,
Couple of patches for the SHAPE_ARC geometry class.
Notably, a bug in the bounding box code is exposed: the bbox is
currently computed to be a box that contains the start, end and
centre. This does not work if the arc passes a "quadrant point". This
is not an issue for 90-deg arcs, but it means, for example, the bbox
for a 180 degree arc is zero-area, as the centre and both endpoints
are collinear. This could be related to occasional rumours of pads
disappearing when at high zoom (?)
The second patch contains a computation for it and removes the
expected failures. It would be good to get a review to check I've done
it correctly! Specifically: have I missed an important case in the
tests?
Also includes a couple of handy geometry test predicates for vectors and boxes.
Cheers,
John
From 89bbe29e721a2059a69f7205449dd51c8e5a2257 Mon Sep 17 00:00:00 2001
From: John Beard <john.j.beard@xxxxxxxxx>
Date: Tue, 8 Jan 2019 17:10:14 +0000
Subject: [PATCH 1/2] QA: Add unit test of SHAPE_ARC
Test a few "centre-point-angle" cases and add some
generic geom code for testing vectors and boxes are within
tolerance (since rounding often creeps in).
Much of the arc-checking code will be useful to other
construction methods (e.g. point-point-point).
There are expected failures for the bbox code when
the arc passes though, but does not end on, a quadrant point
(0, 90, 180, 270). This is due to a defective
implementation of SHAPE_ARC::BBox() that does not take
into account the quadrant points. This will be fixed
as a follow-up.
---
qa/common/CMakeLists.txt | 1 +
qa/common/geometry/test_shape_arc.cpp | 289 ++++++++++++++++++
.../include/unit_test_utils/geometry.h | 49 +++
3 files changed, 339 insertions(+)
create mode 100644 qa/common/geometry/test_shape_arc.cpp
create mode 100644 qa/unit_test_utils/include/unit_test_utils/geometry.h
diff --git a/qa/common/CMakeLists.txt b/qa/common/CMakeLists.txt
index 8e409f411..ab5bdcd26 100644
--- a/qa/common/CMakeLists.txt
+++ b/qa/common/CMakeLists.txt
@@ -46,6 +46,7 @@ set( common_srcs
libeval/test_numeric_evaluator.cpp
geometry/test_fillet.cpp
+ geometry/test_shape_arc.cpp
view/test_zoom_controller.cpp
)
diff --git a/qa/common/geometry/test_shape_arc.cpp b/qa/common/geometry/test_shape_arc.cpp
new file mode 100644
index 000000000..26b82234a
--- /dev/null
+++ b/qa/common/geometry/test_shape_arc.cpp
@@ -0,0 +1,289 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2018 KiCad Developers, see CHANGELOG.TXT for contributors.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+#include <geometry/shape_arc.h>
+
+#include <unit_test_utils/geometry.h>
+#include <unit_test_utils/numeric.h>
+#include <unit_test_utils/unit_test_utils.h>
+
+
+BOOST_AUTO_TEST_SUITE( ShapeArc )
+
+/**
+ * All properties of an arc (depending on how it's constructed, some of these
+ * might be the same as the constructor params)
+ */
+struct ARC_PROPERTIES
+{
+ VECTOR2I m_center_point;
+ VECTOR2I m_start_point;
+ VECTOR2I m_end_point;
+ double m_center_angle;
+ double m_start_angle;
+ double m_end_angle;
+ int m_radius;
+ BOX2I m_bbox;
+};
+
+/**
+ * Check a #SHAPE_ARC against a given set of geometric properties
+ */
+static void CheckArcGeom( const SHAPE_ARC& aArc, const ARC_PROPERTIES& aProps )
+{
+ // Angular error - not this can get quite large for very small arcs,
+ // as the integral position rounding has a relatively greater effect
+ const double angle_tol_deg = 0.01;
+
+ // Position error - rounding to nearest integer
+ const int pos_tol = 1;
+
+ BOOST_CHECK_PREDICATE( KI_TEST::IsVecWithinTol<VECTOR2I>,
+ ( aProps.m_start_point )( aProps.m_start_point )( pos_tol ) );
+ BOOST_CHECK_PREDICATE(
+ KI_TEST::IsVecWithinTol<VECTOR2I>, ( aArc.GetP1() )( aProps.m_end_point )( pos_tol ) );
+ BOOST_CHECK_PREDICATE( KI_TEST::IsVecWithinTol<VECTOR2I>,
+ ( aArc.GetCenter() )( aProps.m_center_point )( pos_tol ) );
+ BOOST_CHECK_PREDICATE( KI_TEST::IsWithin<double>,
+ ( aArc.GetCentralAngle() )( aProps.m_center_angle )( angle_tol_deg ) );
+ BOOST_CHECK_PREDICATE( KI_TEST::IsWithin<double>,
+ ( aArc.GetStartAngle() )( aProps.m_start_angle )( angle_tol_deg ) );
+ BOOST_CHECK_PREDICATE( KI_TEST::IsWithin<double>,
+ ( aArc.GetEndAngle() )( aProps.m_end_angle )( angle_tol_deg ) );
+ BOOST_CHECK_PREDICATE(
+ KI_TEST::IsWithin<double>, ( aArc.GetRadius() )( aProps.m_radius )( pos_tol ) );
+
+ /// Check the chord agrees
+ const auto chord = aArc.GetChord();
+
+ BOOST_CHECK_PREDICATE(
+ KI_TEST::IsVecWithinTol<VECTOR2I>, ( chord.A )( aProps.m_start_point )( pos_tol ) );
+ BOOST_CHECK_PREDICATE(
+ KI_TEST::IsVecWithinTol<VECTOR2I>, ( chord.B )( aProps.m_end_point )( pos_tol ) );
+
+ /// All arcs are solid
+ BOOST_CHECK_EQUAL( aArc.IsSolid(), true );
+
+ BOOST_CHECK_PREDICATE(
+ KI_TEST::IsBoxWithinTol<BOX2I>, ( aArc.BBox() )( aProps.m_bbox )( pos_tol ) );
+
+ /// Collisions will be checked elsewhere.
+}
+
+/**
+ * Check an arcs geometry and other class functions
+ */
+static void CheckArc( const SHAPE_ARC& aArc, const ARC_PROPERTIES& aProps )
+{
+ // Check the original arc
+ CheckArcGeom( aArc, aProps );
+
+ // Test the Clone function (also tests copy-ctor)
+ std::unique_ptr<SHAPE> new_shape{ aArc.Clone() };
+
+ BOOST_CHECK_EQUAL( new_shape->Type(), SH_ARC );
+
+ SHAPE_ARC* new_arc = dynamic_cast<SHAPE_ARC*>( new_shape.get() );
+
+ BOOST_REQUIRE( new_arc != nullptr );
+
+ /// Should have identical geom props
+ CheckArcGeom( *new_arc, aProps );
+}
+
+/**
+ * Check correct handling of filter strings (as used by WX)
+ */
+BOOST_AUTO_TEST_CASE( NullCtor )
+{
+ auto arc = SHAPE_ARC();
+
+ BOOST_CHECK_EQUAL( arc.GetWidth(), 0 );
+
+ static ARC_PROPERTIES null_props{
+ { 0, 0 },
+ { 0, 0 },
+ { 0, 0 },
+ 0,
+ 0,
+ 0,
+ 0,
+ };
+
+ CheckArc( arc, null_props );
+}
+
+/**
+ * Info to set up an arc by centre, start point and angle
+ *
+ * In future there may be more ways to set this up, so keep it separate
+ */
+struct ARC_CENTRE_PT_ANGLE
+{
+ VECTOR2I m_center_point;
+ VECTOR2I m_start_point;
+ double m_center_angle;
+};
+
+struct ARC_CPA_CASE
+{
+ /// The text context name
+ std::string m_ctx_name;
+
+ /// Geom of the arc
+ ARC_CENTRE_PT_ANGLE m_geom;
+
+ /// Arc line width
+ int m_width;
+
+ /// Expected properties
+ ARC_PROPERTIES m_properties;
+};
+
+static const std::vector<ARC_CPA_CASE> arc_cases = {
+ {
+ "C(0,0) 180 + 90 degree",
+ {
+ { 0, 0 },
+ { -100, 0 },
+ 90,
+ },
+ 0,
+ {
+ { 0, 0 },
+ { -100, 0 },
+ { 0, -100 },
+ 90,
+ 180,
+ 270,
+ 100,
+ { { -100, -100 }, { 100, 100 } },
+ },
+ },
+ {
+ "C(100,200) 0 - 30 degree",
+ {
+ { 100, 200 },
+ { 300, 200 },
+ -30,
+ },
+ 0,
+ {
+ { 100, 200 },
+ { 300, 200 },
+ { 273, 100 }, // 200 * sin(30) = 100, 200* cos(30) = 173
+ -30,
+ 0,
+ 330,
+ 200,
+ { { 100, 100 }, { 200, 100 } },
+ },
+ },
+ {
+ // This is a "fan shape" which includes the top quadrant point,
+ // so it exercises the bounding box code (centre and end points
+ // do not contain the top quadrant)
+ "C(0,0) 30 + 120 degree",
+ {
+ { 0, 0 },
+ { 17320, 10000 },
+ 120,
+ },
+ 0,
+ {
+ { 0, 0 },
+ { 17320, 10000 },
+ { -17320, 10000 }, // 200 * sin(30) = 100, 200* cos(30) = 173
+ 120,
+ 30,
+ 150,
+ 20000,
+ // bbox defined by: centre, top quadrant point, two endpoints
+ { { -17320, 0 }, { 17320 * 2, 20000 } },
+ },
+ },
+ {
+ // An arc that covers three quadrant points (L/R, bottom)
+ "C(0,0) 150 + 240 degree",
+ {
+ { 0, 0 },
+ { -17320, 10000 },
+ 240,
+ },
+ 0,
+ {
+ { 0, 0 },
+ { -17320, 10000 },
+ { 17320, 10000 },
+ 240,
+ 150,
+ 30,
+ 20000,
+ // bbox defined by: L/R quads, bottom quad and start/end
+ { { -20000, -20000 }, { 40000, 30000 } },
+ },
+ },
+ {
+ // Same as above but reverse direction
+ "C(0,0) 30 - 300 degree",
+ {
+ { 0, 0 },
+ { 17320, 10000 },
+ -240,
+ },
+ 0,
+ {
+ { 0, 0 },
+ { 17320, 10000 },
+ { -17320, 10000 },
+ -240,
+ 30,
+ 150,
+ 20000,
+ // bbox defined by: L/R quads, bottom quad and start/end
+ { { -20000, -20000 }, { 40000, 30000 } },
+ },
+ },
+};
+
+#ifdef HAVE_EXPECTED_FAILURES
+// One of the bbox tests fails
+
+BOOST_AUTO_TEST_CASE( BasicCPAGeom, *boost::unit_test::expected_failures( 6 ) )
+{
+ for( const auto& c : arc_cases )
+ {
+ BOOST_TEST_CONTEXT( c.m_ctx_name )
+ {
+
+ const auto this_arc = SHAPE_ARC{ c.m_geom.m_center_point, c.m_geom.m_start_point,
+ c.m_geom.m_center_angle, c.m_width };
+
+ CheckArc( this_arc, c.m_properties );
+ }
+ }
+}
+
+#endif // HAVE_EXPECTED_FAILURES
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/qa/unit_test_utils/include/unit_test_utils/geometry.h b/qa/unit_test_utils/include/unit_test_utils/geometry.h
new file mode 100644
index 000000000..cc10cd381
--- /dev/null
+++ b/qa/unit_test_utils/include/unit_test_utils/geometry.h
@@ -0,0 +1,49 @@
+
+#ifndef QA_UNIT_TEST_UTILS_GEOM__H
+#define QA_UNIT_TEST_UTILS_GEOM__H
+
+#include <unit_test_utils/numeric.h>
+#include <unit_test_utils/unit_test_utils.h>
+
+#include <math/box2.h>
+#include <math/vector2d.h>
+
+/**
+ * Printer for BOX2I type
+ */
+template <> struct BOOST_PRINT::print_log_value<BOX2I>
+{
+ void operator()( std::ostream& os, const BOX2I& aBox )
+ {
+ os << "BOX[ " << aBox.GetOrigin() << " + " << aBox.GetSize() << " ]";
+ }
+};
+
+
+namespace KI_TEST
+{
+
+/**
+ * Check that both x and y of a vector are within expected error
+ */
+template <typename VEC>
+bool IsVecWithinTol( const VEC& aVec, const VEC& aExp, typename VEC::coord_type aTol )
+{
+ return IsWithin<typename VEC::coord_type>( aVec.x, aExp.x, aTol )
+ && IsWithin<typename VEC::coord_type>( aVec.y, aExp.y, aTol );
+}
+
+/**
+ * Check that a box is close enough to another box
+ */
+template <typename BOX>
+bool IsBoxWithinTol( const BOX& aBox, const BOX& aExp, typename BOX::coord_type aTol )
+{
+ using VEC = VECTOR2<typename BOX::coord_type>;
+ return IsVecWithinTol<VEC>( aBox.GetPosition(), aExp.GetPosition(), aTol )
+ && IsVecWithinTol<VEC>( aBox.GetSize(), aExp.GetSize(), aTol * 2 );
+}
+
+} // namespace KI_TEST
+
+#endif // QA_UNIT_TEST_UTILS_GEOM__H
\ No newline at end of file
--
2.20.1
From c7ff4e2606348b3b0b37c759c85e2ce8094ce1b2 Mon Sep 17 00:00:00 2001
From: John Beard <john.j.beard@xxxxxxxxx>
Date: Wed, 9 Jan 2019 12:01:00 +0000
Subject: [PATCH 2/2] Geom: Account for quadrant points in arc bbox calc
This means arcs that pass though quadrant points (multiple of
0, 90, 180, 270 degrees) include these points in the bbox.
---
common/geometry/shape_arc.cpp | 32 +++++++++++++++++++++++++++
qa/common/geometry/test_shape_arc.cpp | 7 +-----
2 files changed, 33 insertions(+), 6 deletions(-)
diff --git a/common/geometry/shape_arc.cpp b/common/geometry/shape_arc.cpp
index 2a596b9b9..136223d58 100644
--- a/common/geometry/shape_arc.cpp
+++ b/common/geometry/shape_arc.cpp
@@ -22,6 +22,7 @@
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
*/
+#include <algorithm>
#include <vector>
#include <geometry/geometry_utils.h>
@@ -158,6 +159,37 @@ const BOX2I SHAPE_ARC::BBox( int aClearance ) const
points.push_back( m_p0 );
points.push_back( GetP1() );
+ double start_angle = GetStartAngle();
+ double end_angle = start_angle + GetCentralAngle();
+
+ // we always count quadrants clockwise (increasing angle)
+ if( start_angle > end_angle )
+ std::swap( start_angle, end_angle );
+
+ int quad_angle_start = std::ceil( start_angle / 90.0 );
+ int quad_angle_end = std::floor( end_angle / 90.0 );
+
+ // count through quadrants included in arc
+ for( int quad_angle = quad_angle_start; quad_angle <= quad_angle_end; ++quad_angle )
+ {
+ const int radius = GetRadius();
+ VECTOR2I quad_pt = m_pc;
+
+ switch( quad_angle % 4 )
+ {
+ case 0: quad_pt += { radius, 0 }; break;
+ case 1:
+ case -3: quad_pt += { 0, radius }; break;
+ case 2:
+ case -2: quad_pt += { -radius, 0 }; break;
+ case 3:
+ case -1: quad_pt += { 0, -radius }; break;
+ default: assert( false );
+ }
+
+ points.push_back( quad_pt );
+ }
+
bbox.Compute( points );
if( aClearance != 0 )
diff --git a/qa/common/geometry/test_shape_arc.cpp b/qa/common/geometry/test_shape_arc.cpp
index 26b82234a..9bcd5bd79 100644
--- a/qa/common/geometry/test_shape_arc.cpp
+++ b/qa/common/geometry/test_shape_arc.cpp
@@ -266,10 +266,7 @@ static const std::vector<ARC_CPA_CASE> arc_cases = {
},
};
-#ifdef HAVE_EXPECTED_FAILURES
-// One of the bbox tests fails
-
-BOOST_AUTO_TEST_CASE( BasicCPAGeom, *boost::unit_test::expected_failures( 6 ) )
+BOOST_AUTO_TEST_CASE( BasicCPAGeom )
{
for( const auto& c : arc_cases )
{
@@ -284,6 +281,4 @@ BOOST_AUTO_TEST_CASE( BasicCPAGeom, *boost::unit_test::expected_failures( 6 ) )
}
}
-#endif // HAVE_EXPECTED_FAILURES
-
BOOST_AUTO_TEST_SUITE_END()
--
2.20.1
Follow ups
