kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #36439
Re: [PATCH] qa_geometry tests
Hi Wayne,
(Feel free to tell me to come back to this later if busy with v5!)
On closer inspection, qa_geometry is NOT a general test of geometry
code, but rather a few tests to ensure that some refactored code
(SHAPE_POLY_SET) matches the original CPolyLine-based code.
As for the fillet code testing, I had a go at making some actual tests
for the SHAPE_POLY_SET. It basically does the following for a few
combinations of radius/error:
1) Make a square shape
2) Fillet it
3) Check there's a single resulting polygon
4) Look at the segments generated by the code and ensure that:
a) The end points are the right distance from the radius centre
b) The mid point error from the ideal arc is within tolerance
c) The line is (roughly, due to rounding) perpendicular to the
line joining midpoint and radius centre
5) Check the fillet is at least one segment
These tests do appear to pass for the SHAPE_POLY_SET code.
You could also do testing against expected co-ordinate results, but
that requires that the Fillet code contracts to return exact,
reproducible result, not just "good enough to fit the given error, but
with latitude within that brief".
Attached are some patches to illustrate what I am talking about. I'm
not asking to merge before v5, though I believe the first three are
generally harmless in that respect, as they just enable ctest, add the
working qa_geometry tests (renamed to qa_shape_poly_set_refactor) and
add the Python tests.
The fourth is the new fillet tests, which are still just a concept,
though feedback is welcome.
Cheers,
John
On Tue, Jul 10, 2018 at 4:12 PM, Wayne Stambaugh <stambaughw@xxxxxxxxx> wrote:
> I'm not sure what bothers me more, the fact the test fails or the fact
> that the test used different fillet code as the pass/fail criteria
> rather than a hard coded known correct test. Which fillet code was/is
> correct? We really do need to start doing a better job with our
> geometry tests and testing in general. Is the fillet code we use to
> generate polygons and other geometry actually correct?
>
> As far as fixing qa tests, I don't think that will impact the v5 release
> but pushing it off to 5.0.1 or 5.1 probably makes more sense at this
> point. I do agree that there should be an easier way to run tests.
>
> Cheers,
>
> Wayne
>
> On 7/9/2018 5:35 AM, John Beard wrote:
>> Note to Wayne: Nothing here concerns v5 release, I was just trying to
>> get a geom test working for future.
>>
>> On Mon, Jul 9, 2018 at 9:12 AM, John Beard <john.j.beard@xxxxxxxxx> wrote:
>>> Hi,
>>>
>>> Let's come back to the make test behaviour after v5, I think we'll
>>> need to discuss that separately. However, I think this does illustrate
>>> why we need the tests to be runnable easily, otherwise they suffer
>>> bit-rot, and then the tests are useless.
>>>
>>> Looking at that change, the test is now iterating the second parameter
>>> which is now "max error", not "number of segments". Does this test
>>> still make any sense? It's now comparing:
>>>
>>> SHAPE_POLY_SET::Fillet( radius, error );
>>>
>>> with
>>>
>>> CPolyLine::Fillet( radius, segments );
>>>
>>> The original test was designed to ensure SHAPE_POLY_SET::Fillet and
>>> CPolyLine::Fillet were the same, but they now have different
>>> interfaces and semantics. Wouldn't it be better to check
>>> SHAPE_POLY_SET::Fillet (and Chamfer) against some ground truth?
>>>
>>> Cheers,
>>>
>>> John
>>>
>>> On Fri, Jul 6, 2018 at 8:40 PM, Nick Østergaard <oe.nick@xxxxxxxxx> wrote:
>>>> Hi
>>>>
>>>> I guess we could add it to the qa target somehow? What I don't particularyly
>>>> like with this patch is that executing "make test" does not check for
>>>> dependency changes.
>>>>
>>>> Back to the status about qa_geometry... it did pass a long time ago, doing a
>>>> bit of git bisect points at this commit as the one breaking the test.
>>>>
>>>> fbf10e941bdf26bb3618aba0a1b7c44fd0bafed2 is the first bad commit
>>>> commit fbf10e941bdf26bb3618aba0a1b7c44fd0bafed2
>>>> Author: Jeff Young
>>>> Date: Thu Mar 22 18:02:45 2018 +0000
>>>>
>>>> Switch zone fillets to absolute-error algorithm.
>>>>
>>>> And some general cleanup to related constants, etc.
>>>>
>>>> :040000 040000 8b6ad8d44a7b38e0355ce5c8897f823d6255f811
>>>> 8d54d43a9bd6e5062d6b804890a779e785e430cc M common
>>>> :040000 040000 5a90dc20fe7cb3f74ae1768a5b5024a902c9354d
>>>> a2be92ebd64fd46ad17427e8e3c12da7f10df699 M include
>>>> :040000 040000 af9f333c0f56dca3a90fb7b04f385dbf39425e8d
>>>> 99b5f9757c78216a08220b7eb056f343658b961d M pcbnew
>>>>
>>>>
>>>> Den tor. 5. jul. 2018 kl. 12.13 skrev John Beard <john.j.beard@xxxxxxxxx>:
>>>>>
>>>>> Hi,
>>>>>
>>>>> Are the qa_geometry test supposed to all work?
>>>>>
>>>>> When I run `qa_geometry`, I get 1160 errors like this:
>>>>>
>>>>> error: in "ChamferFillet/Fillet": check { chainPoints.begin(),
>>>>> chainPoints.end() } == { polyPoints.begin(), polyPoints.end() } has
>>>>> failed.
>>>>>
>>>>> Mismatch at position 0: [ 40 | 14 ] != [ 40 | 12 ]
>>>>> Mismatch at position 1: [ 40 | 15 ] != [ 40 | 13 ]
>>>>> Mismatch at position 2: [ 44 | 10 ] != [ 40 | 14 ]
>>>>> Mismatch at position 3: [ 44 | 18 ] != [ 40 | 15 ]
>>>>> Mismatch at position 4: [ 50 | 10 ] != [ 40 | 16 ]
>>>>> Mismatch at position 5: [ 51 | 14 ] != [ 40 | 17 ]
>>>>> Collections size mismatch: 6 != 25
>>>>>
>>>>> Attached is a patch that enabled CTest tests and adds qa_geometry as a
>>>>> test. Then you can run `make test` or `ctest` to run all tests. I
>>>>> think it would be good to have a single unambigous and easily
>>>>> understood command to be able to run unit tests?
>>>>>
>>>>> This patch explicitly excludes the "ChamferFillet/Fillet" tests as
>>>>> they are failing, but if those tests can be fixed, it would be good to
>>>>> run them too.
>>>>>
>>>>> Cheers,
>>>>>
>>>>> John
>>>>> _______________________________________________
>>>>> Mailing list: https://launchpad.net/~kicad-developers
>>>>> Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
>>>>> Unsubscribe : https://launchpad.net/~kicad-developers
>>>>> More help : https://help.launchpad.net/ListHelp
>>
>> _______________________________________________
>> Mailing list: https://launchpad.net/~kicad-developers
>> Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
>> Unsubscribe : https://launchpad.net/~kicad-developers
>> More help : https://help.launchpad.net/ListHelp
>>
>
> _______________________________________________
> Mailing list: https://launchpad.net/~kicad-developers
> Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~kicad-developers
> More help : https://help.launchpad.net/ListHelp
From a6b98ecfd06529d7722a2834083d67a011741e63 Mon Sep 17 00:00:00 2001
From: John Beard <john.j.beard@xxxxxxxxx>
Date: Thu, 5 Jul 2018 11:11:57 +0100
Subject: [PATCH 1/4] Enable CTest tests and add qa_geometry as a test
This allows the use of `make test` or `ctest` to run all registered
tests.
The ChamferFillet/Fillet test is disabled for now as it fails.
---
CMakeLists.txt | 1 +
qa/geometry/CMakeLists.txt | 4 ++++
2 files changed, 5 insertions(+)
diff --git a/CMakeLists.txt b/CMakeLists.txt
index f2ea761f9..60c22c2f4 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -912,6 +912,7 @@ if( UNIX AND NOT APPLE )
endif()
#include( CTest )
+enable_testing()
if( UNIX AND NOT APPLE )
diff --git a/qa/geometry/CMakeLists.txt b/qa/geometry/CMakeLists.txt
index b932bfb74..19ca8b91b 100644
--- a/qa/geometry/CMakeLists.txt
+++ b/qa/geometry/CMakeLists.txt
@@ -54,3 +54,7 @@ target_link_libraries(qa_geometry
)
add_dependencies( qa_geometry pcbnew )
+
+add_test( NAME geometry
+ COMMAND qa_geometry --run_test=!ChamferFillet/Fillet
+)
\ No newline at end of file
--
2.17.1
From c70a40198310961d15c90a83a0a67d2480062928 Mon Sep 17 00:00:00 2001
From: John Beard <john.j.beard@xxxxxxxxx>
Date: Mon, 9 Jul 2018 15:03:02 +0100
Subject: [PATCH 2/4] QA: Add python test as a Ctest test rather than build
target
---
qa/CMakeLists.txt | 14 ++++++++------
1 file changed, 8 insertions(+), 6 deletions(-)
diff --git a/qa/CMakeLists.txt b/qa/CMakeLists.txt
index 7bbfcbee5..9ee379acc 100644
--- a/qa/CMakeLists.txt
+++ b/qa/CMakeLists.txt
@@ -1,12 +1,14 @@
if( KICAD_SCRIPTING_MODULES )
- # build target that runs the QA tests through scripting
- add_custom_target( qa
- COMMAND PYTHONPATH=${CMAKE_BINARY_DIR}/pcbnew${PYTHON_QA_PATH} ${PYTHON_EXECUTABLE} test.py
-
- COMMENT "running qa"
+ # Test that runs the QA tests through scripting
+ add_test( NAME qa_python
+ COMMAND ${PYTHON_EXECUTABLE} test.py
WORKING_DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR}
- )
+ )
+
+ set_property( TEST qa_python
+ PROPERTY ENVIRONMENT "PYTHONPATH=${CMAKE_BINARY_DIR}/pcbnew${PYTHON_QA_PATH}"
+ )
endif()
--
2.17.1
From b00c2dd84de7e602d8037d28c0818039fe1bb414 Mon Sep 17 00:00:00 2001
From: John Beard <john.j.beard@xxxxxxxxx>
Date: Mon, 9 Jul 2018 14:28:40 +0100
Subject: [PATCH 3/4] QA: Rename geometry to shape_poly_set_refactor
This test is not really concerned with generic geometric code testing,
but rather the correctness of a refactoring effort.
Rename it make this clearer, and also to make way for generic geometry tests.
---
qa/CMakeLists.txt | 2 +-
.../CMakeLists.txt | 12 ++++++------
.../test_chamfer_fillet.cpp | 0
.../test_collision.cpp | 0
.../test_iterator.cpp | 0
.../test_module.cpp | 0
.../test_segment.cpp | 0
7 files changed, 7 insertions(+), 7 deletions(-)
rename qa/{geometry => shape_poly_set_refactor}/CMakeLists.txt (86%)
rename qa/{geometry => shape_poly_set_refactor}/test_chamfer_fillet.cpp (100%)
rename qa/{geometry => shape_poly_set_refactor}/test_collision.cpp (100%)
rename qa/{geometry => shape_poly_set_refactor}/test_iterator.cpp (100%)
rename qa/{geometry => shape_poly_set_refactor}/test_module.cpp (100%)
rename qa/{geometry => shape_poly_set_refactor}/test_segment.cpp (100%)
diff --git a/qa/CMakeLists.txt b/qa/CMakeLists.txt
index 9ee379acc..e8cd8846b 100644
--- a/qa/CMakeLists.txt
+++ b/qa/CMakeLists.txt
@@ -12,7 +12,7 @@ if( KICAD_SCRIPTING_MODULES )
endif()
-add_subdirectory( geometry )
+add_subdirectory( shape_poly_set_refactor )
add_subdirectory( pcb_test_window )
add_subdirectory( polygon_triangulation )
add_subdirectory( polygon_generator )
\ No newline at end of file
diff --git a/qa/geometry/CMakeLists.txt b/qa/shape_poly_set_refactor/CMakeLists.txt
similarity index 86%
rename from qa/geometry/CMakeLists.txt
rename to qa/shape_poly_set_refactor/CMakeLists.txt
index 19ca8b91b..3100328b5 100644
--- a/qa/geometry/CMakeLists.txt
+++ b/qa/shape_poly_set_refactor/CMakeLists.txt
@@ -26,7 +26,7 @@ find_package( wxWidgets 3.0.0 COMPONENTS gl aui adv html core net base xml stc R
add_definitions(-DBOOST_TEST_DYN_LINK)
-add_executable(qa_geometry
+add_executable( qa_shape_poly_set_refactor
test_module.cpp
test_chamfer_fillet.cpp
test_collision.cpp
@@ -42,7 +42,7 @@ include_directories(
${Boost_INCLUDE_DIR}
)
-target_link_libraries(qa_geometry
+target_link_libraries( qa_shape_poly_set_refactor
polygon
common
polygon
@@ -53,8 +53,8 @@ target_link_libraries(qa_geometry
${wxWidgets_LIBRARIES}
)
-add_dependencies( qa_geometry pcbnew )
+add_dependencies( qa_shape_poly_set_refactor pcbnew )
-add_test( NAME geometry
- COMMAND qa_geometry --run_test=!ChamferFillet/Fillet
-)
\ No newline at end of file
+add_test( NAME shape_poly_set_refactor
+ COMMAND qa_shape_poly_set_refactor --run_test=!ChamferFillet/Fillet
+)
diff --git a/qa/geometry/test_chamfer_fillet.cpp b/qa/shape_poly_set_refactor/test_chamfer_fillet.cpp
similarity index 100%
rename from qa/geometry/test_chamfer_fillet.cpp
rename to qa/shape_poly_set_refactor/test_chamfer_fillet.cpp
diff --git a/qa/geometry/test_collision.cpp b/qa/shape_poly_set_refactor/test_collision.cpp
similarity index 100%
rename from qa/geometry/test_collision.cpp
rename to qa/shape_poly_set_refactor/test_collision.cpp
diff --git a/qa/geometry/test_iterator.cpp b/qa/shape_poly_set_refactor/test_iterator.cpp
similarity index 100%
rename from qa/geometry/test_iterator.cpp
rename to qa/shape_poly_set_refactor/test_iterator.cpp
diff --git a/qa/geometry/test_module.cpp b/qa/shape_poly_set_refactor/test_module.cpp
similarity index 100%
rename from qa/geometry/test_module.cpp
rename to qa/shape_poly_set_refactor/test_module.cpp
diff --git a/qa/geometry/test_segment.cpp b/qa/shape_poly_set_refactor/test_segment.cpp
similarity index 100%
rename from qa/geometry/test_segment.cpp
rename to qa/shape_poly_set_refactor/test_segment.cpp
--
2.17.1
From d2f12d49378070484908981161966e210008e38f Mon Sep 17 00:00:00 2001
From: John Beard <john.j.beard@xxxxxxxxx>
Date: Mon, 9 Jul 2018 12:54:39 +0100
Subject: [PATCH 4/4] QA Geometry: New test suite for generic geometric tests
This is the first test for a generic test suite for geometric functions.
The tests run are for fillet corners of SHAPE_POLY_SETS.
Previously, SHAPE_POLY_SET::Fillet was tested against CPolyLine::Fillet
to ensure compatibility. However, thse two functions now have different
interfaces and are not directly comparable. Also, this depended on
CPolyLine::Fillet being correct, which was not tested.
Instead, test SHAPE_POLY_SET::Fillet using tests against geometric
constraints, independent of any other fillet implementation.
---
qa/CMakeLists.txt | 1 +
qa/geometry/CMakeLists.txt | 49 ++++++++
qa/geometry/geom_test_utils.h | 212 ++++++++++++++++++++++++++++++++++
qa/geometry/test_fillet.cpp | 210 +++++++++++++++++++++++++++++++++
qa/geometry/test_module.cpp | 32 +++++
5 files changed, 504 insertions(+)
create mode 100644 qa/geometry/CMakeLists.txt
create mode 100644 qa/geometry/geom_test_utils.h
create mode 100644 qa/geometry/test_fillet.cpp
create mode 100644 qa/geometry/test_module.cpp
diff --git a/qa/CMakeLists.txt b/qa/CMakeLists.txt
index e8cd8846b..e82afcd73 100644
--- a/qa/CMakeLists.txt
+++ b/qa/CMakeLists.txt
@@ -12,6 +12,7 @@ if( KICAD_SCRIPTING_MODULES )
endif()
+add_subdirectory( geometry )
add_subdirectory( shape_poly_set_refactor )
add_subdirectory( pcb_test_window )
add_subdirectory( polygon_triangulation )
diff --git a/qa/geometry/CMakeLists.txt b/qa/geometry/CMakeLists.txt
new file mode 100644
index 000000000..031c02b3a
--- /dev/null
+++ b/qa/geometry/CMakeLists.txt
@@ -0,0 +1,49 @@
+# 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
+
+find_package(Boost COMPONENTS unit_test_framework REQUIRED)
+find_package( wxWidgets 3.0.0 COMPONENTS gl aui adv html core net base xml stc REQUIRED )
+
+
+add_definitions(-DBOOST_TEST_DYN_LINK)
+
+add_executable( qa_geometry
+ test_module.cpp
+ test_fillet.cpp
+)
+
+include_directories(
+ ${CMAKE_SOURCE_DIR}
+ ${CMAKE_SOURCE_DIR}/include
+ ${CMAKE_SOURCE_DIR}/polygon
+ ${Boost_INCLUDE_DIR}
+)
+
+target_link_libraries( qa_geometry
+ common
+ polygon
+ ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}
+ ${wxWidgets_LIBRARIES}
+)
+
+add_test( NAME geometry
+ COMMAND qa_geometry
+)
\ No newline at end of file
diff --git a/qa/geometry/geom_test_utils.h b/qa/geometry/geom_test_utils.h
new file mode 100644
index 000000000..cb4e9721f
--- /dev/null
+++ b/qa/geometry/geom_test_utils.h
@@ -0,0 +1,212 @@
+/*
+ * 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
+ */
+
+#ifndef GEOM_TEST_UTILS_H
+#define GEOM_TEST_UTILS_H
+
+/**
+ * @brief Utility functions for testing geometry functions.
+ */
+namespace GEOM_TEST
+{
+
+constexpr double PI = atan(1.0) * 4.0;
+constexpr double PI_2 = atan(1.0) * 2.0;
+
+/**
+ * @brief Check if a value is within a tolerance of a nominal value
+ *
+* @return value is in [aNominal - aError, aNominal + aError]
+ */
+template<typename T>
+bool IsWithin( T aValue, T aNominal, T aError )
+{
+ return ( aValue >= aNominal - aError )
+ && ( aValue <= aNominal + aError );
+}
+
+/**
+ * @brief Check if a value is within a tolerance of a nominal value,
+ * with different allowances for errors above and below.
+ *
+ * @return value is in [aNominal - aErrorBelow, aNominal + aErrorAbove]
+ */
+template<typename T>
+bool IsWithin( T aValue, T aNominal, T aErrorAbove, T aErrorBelow )
+{
+ return ( aValue >= aNominal - aErrorBelow )
+ && ( aValue <= aNominal + aErrorAbove );
+}
+
+/**
+ * @brief value is in range [aNominal - aErrorBelow, aNominal]
+ */
+template<typename T>
+bool IsWithinAndBelow( T aValue, T aNominal, T aErrorBelow )
+{
+ return IsWithin( aValue, aNominal, 0, aErrorBelow );
+}
+
+/**
+ * @brief value is in range [aNominal, aNominal + aErrorAbove]
+ */
+template<typename T>
+bool IsWithinAndAbove( T aValue, T aNominal, T aErrorAbove )
+{
+ return IsWithin( aValue, aNominal, aErrorAbove, 0 );
+}
+
+/**
+ * @brief Geometric quadrants, from top-right, anti-clockwise
+ *
+ * ^ y
+ * |
+ * Q2 | Q1
+ * -------> x
+ * Q3 | Q4
+ */
+enum class QUADRANT {
+ Q1, Q2, Q3, Q4
+};
+
+/*
+ * @brief Check value in Quadrant 1 (x and y both >= 0)
+ */
+template<typename T>
+bool IsInQuadrant( const VECTOR2<T>& aPoint, QUADRANT aQuadrant )
+{
+ bool isInQuad = false;
+
+ switch( aQuadrant )
+ {
+ case QUADRANT::Q1:
+ isInQuad = aPoint.x >= 0 && aPoint.y >= 0;
+ break;
+ case QUADRANT::Q2:
+ isInQuad = aPoint.x <= 0 && aPoint.y >= 0;
+ break;
+ case QUADRANT::Q3:
+ isInQuad = aPoint.x <= 0 && aPoint.y <= 0;
+ break;
+ case QUADRANT::Q4:
+ isInQuad = aPoint.x >= 0 && aPoint.y <= 0;
+ break;
+ }
+
+ return isInQuad;
+}
+
+/*
+ * @Brief Check if both ends of a segment are in Quadrant 1
+ */
+bool SegmentCompletelyInQuadrant( const SEG& aSeg, QUADRANT aQuadrant )
+{
+ return IsInQuadrant( aSeg.A, aQuadrant)
+ && IsInQuadrant( aSeg.B, aQuadrant );
+}
+
+/*
+ * @brief Check if at least one end of the segment is in Quadrant 1
+ */
+bool SegmentEndsInQuadrant( const SEG& aSeg, QUADRANT aQuadrant )
+{
+ return IsInQuadrant( aSeg.A, aQuadrant )
+ || IsInQuadrant( aSeg.B, aQuadrant );
+}
+
+/*
+ * @brief Check if a segment is entirely within a certain radius of a point.
+ */
+bool SegmentCompletelyWithinRadius( const SEG& aSeg, const VECTOR2I& aPt,
+ const int aRadius )
+{
+ // This is true iff both ends of the segment are within the radius
+ return ( ( aSeg.A - aPt ).EuclideanNorm() < aRadius )
+ && ( ( aSeg.B - aPt ).EuclideanNorm() < aRadius );
+}
+
+/*
+ * @brief Check if two vectors are perpendicular
+ *
+ * @param a: vector A
+ * @param b: vector B
+ * @param aTolerance: the allowed deviation from PI/2 (e.g. when rounding)
+ */
+
+template<typename T>
+bool ArePerpendicular( const VECTOR2<T>& a, const VECTOR2<T>& b, double aTolerance )
+{
+ auto angle = std::abs( a.Angle() - b.Angle() );
+
+ // Normalise: angles of 3*pi/2 are also perpendicular
+ if (angle > PI)
+ {
+ angle -= PI;
+ }
+
+ return IsWithin( angle, PI_2, aTolerance );
+}
+
+/**
+ * @brief construct a square polygon of given size width and centre
+ *
+ * @param aSize: the side width (must be divisible by 2 if want to avoid rounding)
+ * @param aCentre: the centre of the square
+ */
+SHAPE_LINE_CHAIN MakeSquarePolyLine( int aSize, const VECTOR2I& aCentre )
+{
+ SHAPE_LINE_CHAIN polyLine;
+
+ const VECTOR2I corner = aCentre + aSize / 2;
+
+ polyLine.Append( VECTOR2I( corner.x, corner.y ) );
+ polyLine.Append( VECTOR2I( -corner.x, corner.y ) ) ;
+ polyLine.Append( VECTOR2I( -corner.x, -corner.y ) );
+ polyLine.Append( VECTOR2I( corner.x, -corner.y ) );
+
+ polyLine.SetClosed( true );
+
+ return polyLine;
+}
+
+/*
+ * @brief Fillet every polygon in a set and return a new set
+ */
+SHAPE_POLY_SET FilletPolySet( SHAPE_POLY_SET& aPolySet, int aRadius,
+ int aError )
+{
+ SHAPE_POLY_SET filletedPolySet;
+
+ for ( int i = 0; i < aPolySet.OutlineCount(); ++i )
+ {
+ const auto filleted = aPolySet.FilletPolygon( aRadius, aError, i );
+
+ filletedPolySet.AddOutline( filleted[0] );
+ }
+
+ return filletedPolySet;
+}
+
+}
+
+#endif // GEOM_TEST_UTILS_H
\ No newline at end of file
diff --git a/qa/geometry/test_fillet.cpp b/qa/geometry/test_fillet.cpp
new file mode 100644
index 000000000..10a7fe725
--- /dev/null
+++ b/qa/geometry/test_fillet.cpp
@@ -0,0 +1,210 @@
+/*
+ * 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 <boost/test/unit_test.hpp>
+#include <boost/test/test_case_template.hpp>
+
+#include <geometry/shape_poly_set.h>
+#include <geometry/shape_line_chain.h>
+
+#include <algorithm>
+
+#include <qa/geometry/geom_test_utils.h>
+
+struct FilletFixture
+{
+};
+
+/**
+ * Declares the FilletFixture struct as the boost test fixture.
+ */
+BOOST_FIXTURE_TEST_SUITE( Fillet, FilletFixture )
+
+/*
+ * @brief check that a single segment of a fillet complies with the geometric
+ * constraint:
+ *
+ * 1: The end points are radius from the centre point
+ * 2: The mid point error is acceptable
+ * 3: The segment midpoints are perpendicular to the radius
+ */
+void TestFilletSegmentConstraints( const SEG& aSeg, VECTOR2I aRadCentre,
+ int aRadius, int aError )
+{
+ using namespace GEOM_TEST;
+
+ const auto diffA = aRadCentre - aSeg.A;
+ const auto diffB = aRadCentre - aSeg.B;
+ const auto diffC = aRadCentre - aSeg.Center();
+
+ // Check 1: radii (error of 1 for rounding)
+ BOOST_CHECK_PREDICATE( IsWithinAndBelow<int>,
+ ( diffA.EuclideanNorm() )( aRadius )( 1 ) );
+ BOOST_CHECK_PREDICATE( IsWithinAndBelow<int>,
+ ( diffB.EuclideanNorm() )( aRadius )( 1 ) );
+
+ // Check 2: Mid-point error
+ BOOST_CHECK_PREDICATE( IsWithinAndBelow<int>,
+ ( diffC.EuclideanNorm() )( aRadius )( aError + 1 ) );
+
+ // Check 3: Mid-point -> radius centre perpendicular
+ BOOST_CHECK_PREDICATE( ArePerpendicular<int>,
+ ( diffC )( aSeg.A - aSeg.B )( PI_2 / 10 ) );
+}
+
+
+/**
+ * @brief: Create a square, fillet it, and check a corner for correctness
+ */
+void TestSquareFillet( int aSquareSize, int aRadius, int aError )
+{
+ using namespace GEOM_TEST;
+
+ SHAPE_POLY_SET squarePolySet;
+
+ squarePolySet.AddOutline( MakeSquarePolyLine(aSquareSize, VECTOR2I(0, 0) ) );
+
+ SHAPE_POLY_SET filleted = FilletPolySet(squarePolySet, aRadius, aError);
+
+ // expect a single filleted polygon
+ BOOST_CHECK_EQUAL( filleted.OutlineCount(), 1 );
+
+ auto segIter = filleted.IterateSegments();
+
+ const VECTOR2I radCentre { aSquareSize / 2 - aRadius,
+ aSquareSize / 2 - aRadius };
+
+ int checked = 0;
+
+ for( ; segIter; segIter++ )
+ {
+ // Only check the first Quadrant
+ if ( SegmentCompletelyInQuadrant( *segIter, QUADRANT::Q1 ) )
+ {
+ TestFilletSegmentConstraints( *segIter, radCentre, aRadius, aError );
+ checked++;
+ }
+ }
+
+ // we expect there to be at least one segment in the fillet
+ BOOST_CHECK( checked > 0 );
+}
+
+
+/**
+ * @brief: Create a square concave corner, fillet and check correctness
+ */
+void TestConcaveSquareFillet( int aSquareSize, int aRadius, int aError )
+{
+ using namespace GEOM_TEST;
+
+ SHAPE_POLY_SET polySet;
+ SHAPE_LINE_CHAIN polyLine;
+
+ /*
+ * L-shape:
+ * ----
+ * | |
+ * ---- |
+ * | |
+ * --------
+ */
+
+ polyLine.Append( VECTOR2I{ 0, 0 } );
+ polyLine.Append( VECTOR2I{ 0, aSquareSize / 2 } );
+ polyLine.Append( VECTOR2I{ aSquareSize / 2 , aSquareSize / 2 } );
+ polyLine.Append( VECTOR2I{ aSquareSize / 2 , aSquareSize } );
+ polyLine.Append( VECTOR2I{ aSquareSize, aSquareSize } );
+ polyLine.Append( VECTOR2I{ aSquareSize, 0 } );
+
+ polyLine.SetClosed( true );
+
+ polySet.AddOutline( polyLine );
+
+ SHAPE_POLY_SET filleted = FilletPolySet(polySet, aRadius, aError);
+
+ // expect a single filleted polygon
+ BOOST_CHECK_EQUAL( filleted.OutlineCount(), 1 );
+
+ auto segIter = filleted.IterateSegments();
+
+ const VECTOR2I radCentre { aSquareSize / 2 - aRadius,
+ aSquareSize / 2 + aRadius };
+
+ int checked = 0;
+
+ for( ; segIter; segIter++ )
+ {
+ // Only check segments around the concave corner
+ if ( SegmentCompletelyWithinRadius( *segIter, radCentre, aRadius + 1) )
+ {
+ TestFilletSegmentConstraints( *segIter, radCentre, aRadius, aError );
+ checked++;
+ }
+ }
+
+ // we expect there to be at least one segment in the fillet
+ BOOST_CHECK( checked > 0 );
+}
+
+
+struct SquareFilletTestCase
+{
+ int squareSize;
+ int radius;
+ int error;
+};
+
+const std::vector<SquareFilletTestCase> squareFilletCases {
+ { 1000, 120, 10 },
+ { 1000, 10, 1 },
+
+ /* Large error relative to fillet */
+ { 1000, 10, 5 },
+
+ /* Very small error relative to fillet(many segments in interpolation) */
+ { 70000, 1000, 1 },
+};
+
+/**
+ * Tests the SHAPE_POLY_SET::FilletPolygon method against certain geometric
+ * constraints.
+ */
+BOOST_AUTO_TEST_CASE( SquareFillet )
+{
+ for ( const auto& testCase : squareFilletCases )
+ {
+ TestSquareFillet( testCase.squareSize, testCase.radius, testCase.error );
+ }
+}
+
+BOOST_AUTO_TEST_CASE( SquareConcaveFillet )
+{
+ for ( const auto& testCase : squareFilletCases )
+ {
+ TestConcaveSquareFillet( testCase.squareSize, testCase.radius, testCase.error );
+ }
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/qa/geometry/test_module.cpp b/qa/geometry/test_module.cpp
new file mode 100644
index 000000000..6fb45de1f
--- /dev/null
+++ b/qa/geometry/test_module.cpp
@@ -0,0 +1,32 @@
+/*
+ * 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
+ */
+
+/**
+ * Main file for the geometry tests to be compiled
+ */
+
+#define BOOST_TEST_MAIN
+#define BOOST_TEST_MODULE "Geometry module tests"
+
+
+#include <boost/test/unit_test.hpp>
--
2.17.1
Follow ups
References
