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 <[email protected]> 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 <[email protected]> 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
_______________________________________________ Mailing list: https://launchpad.net/~kicad-developers Post to : [email protected] Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
