KiCad PCB EDA Suite
Loading...
Searching...
No Matches
geom_test_utils.h
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) 2018 KiCad Developers, see AUTHORS.TXT for contributors.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, you may find one here:
18 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
19 * or you may search the http://www.gnu.org website for the version 2 license,
20 * or you may write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22 */
23
24#ifndef GEOM_TEST_UTILS_H
25#define GEOM_TEST_UTILS_H
26
27#include <cmath>
28
29#include <geometry/seg.h>
32
33#include <qa_utils/numeric.h>
35
39namespace GEOM_TEST
40{
41
51enum class QUADRANT {
52 Q1, Q2, Q3, Q4
53};
54
55/*
56 * @brief Check value in Quadrant 1 (x and y both >= 0)
57 */
58template<typename T>
59bool IsInQuadrant( const VECTOR2<T>& aPoint, QUADRANT aQuadrant )
60{
61 bool isInQuad = false;
62
63 switch( aQuadrant )
64 {
65 case QUADRANT::Q1:
66 isInQuad = aPoint.x >= 0 && aPoint.y >= 0;
67 break;
68 case QUADRANT::Q2:
69 isInQuad = aPoint.x <= 0 && aPoint.y >= 0;
70 break;
71 case QUADRANT::Q3:
72 isInQuad = aPoint.x <= 0 && aPoint.y <= 0;
73 break;
74 case QUADRANT::Q4:
75 isInQuad = aPoint.x >= 0 && aPoint.y <= 0;
76 break;
77 }
78
79 return isInQuad;
80}
81
82/*
83 * @Brief Check if both ends of a segment are in Quadrant 1
84 */
85inline bool SegmentCompletelyInQuadrant( const SEG& aSeg, QUADRANT aQuadrant )
86{
87 return IsInQuadrant( aSeg.A, aQuadrant)
88 && IsInQuadrant( aSeg.B, aQuadrant );
89}
90
91/*
92 * @brief Check if at least one end of the segment is in Quadrant 1
93 */
94inline bool SegmentEndsInQuadrant( const SEG& aSeg, QUADRANT aQuadrant )
95{
96 return IsInQuadrant( aSeg.A, aQuadrant )
97 || IsInQuadrant( aSeg.B, aQuadrant );
98}
99
100/*
101 * @brief Check if a segment is entirely within a certain radius of a point.
102 */
103inline bool SegmentCompletelyWithinRadius( const SEG& aSeg, const VECTOR2I& aPt, const int aRadius )
104{
105 // This is true iff both ends of the segment are within the radius
106 return ( ( aSeg.A - aPt ).EuclideanNorm() < aRadius )
107 && ( ( aSeg.B - aPt ).EuclideanNorm() < aRadius );
108}
109
119template <typename T>
120bool IsPointAtDistance( const VECTOR2<T>& aPtA, const VECTOR2<T>& aPtB, T aExpDist, T aTol )
121{
122 const int dist = ( aPtB - aPtA ).EuclideanNorm();
123 const bool ok = KI_TEST::IsWithin( dist, aExpDist, aTol );
124
125 if( !ok )
126 {
127 BOOST_TEST_INFO( "Points not at expected distance: distance is " << dist << ", expected "
128 << aExpDist );
129 }
130
131 return ok;
132}
133
143template <typename T>
145 const std::vector<VECTOR2<T>>& aPoints, const VECTOR2<T>& aCentre, T aRad, T aTol )
146{
147 bool ok = true;
148
149 for( unsigned i = 0; i < aPoints.size(); ++i )
150 {
151 if( !IsPointAtDistance( aPoints[i], aCentre, aRad, aTol ) )
152 {
153 BOOST_TEST_INFO( "Point " << i << " " << aPoints[i] << " is not within tolerance ("
154 << aTol << ") of radius (" << aRad << ") from centre point "
155 << aCentre );
156 ok = false;
157 }
158 }
159
160 return ok;
161}
162
163/*
164 * @brief Check if two vectors are perpendicular
165 *
166 * @param a: vector A
167 * @param b: vector B
168 * @param aTolerance: the allowed deviation from PI/2 (e.g. when rounding)
169 */
170
171template<typename T>
172bool ArePerpendicular( const VECTOR2<T>& a, const VECTOR2<T>& b, const EDA_ANGLE& aTolerance )
173{
174 EDA_ANGLE angle = std::abs( EDA_ANGLE( a ) - EDA_ANGLE( b ) );
175
176 // Normalise: angles of 3*pi/2 are also perpendicular
177 if (angle > ANGLE_180)
178 angle -= ANGLE_180;
179
180 return KI_TEST::IsWithin( angle.AsRadians(), ANGLE_90.AsRadians(), aTolerance.AsRadians() );
181}
182
189inline SHAPE_LINE_CHAIN MakeSquarePolyLine( int aSize, const VECTOR2I& aCentre )
190{
191 SHAPE_LINE_CHAIN polyLine;
192
193 const VECTOR2I corner = aCentre + aSize / 2;
194
195 polyLine.Append( VECTOR2I( corner.x, corner.y ) );
196 polyLine.Append( VECTOR2I( -corner.x, corner.y ) ) ;
197 polyLine.Append( VECTOR2I( -corner.x, -corner.y ) );
198 polyLine.Append( VECTOR2I( corner.x, -corner.y ) );
199
200 polyLine.SetClosed( true );
201
202 return polyLine;
203}
204
205/*
206 * @brief Fillet every polygon in a set and return a new set
207 */
208inline SHAPE_POLY_SET FilletPolySet( SHAPE_POLY_SET& aPolySet, int aRadius, int aError )
209{
210 SHAPE_POLY_SET filletedPolySet;
211
212 for ( int i = 0; i < aPolySet.OutlineCount(); ++i )
213 {
214 const auto filleted = aPolySet.FilletPolygon( aRadius, aError, i );
215
216 filletedPolySet.AddOutline( filleted[0] );
217 }
218
219 return filletedPolySet;
220}
221
230inline bool IsOutlineValid( const SHAPE_LINE_CHAIN& aChain )
231{
232 ssize_t prevArcIdx = -1;
233 std::set<size_t> testedArcs;
234
235 for( int i = 0; i < aChain.PointCount(); i++ )
236 {
237 ssize_t arcIdx = aChain.ArcIndex( i );
238
239 if( arcIdx >= 0 )
240 {
241 // Point on arc, lets make sure it collides with the arc shape and we haven't
242 // previously seen the same arc index
243
244 if( prevArcIdx != arcIdx && testedArcs.count( arcIdx ) )
245 return false; // we've already seen this arc before, not contiguous
246
247 if( !aChain.Arc( arcIdx ).Collide( aChain.CPoint( i ),
249 {
250 return false;
251 }
252
253 testedArcs.insert( arcIdx );
254 }
255
256 if( prevArcIdx != arcIdx )
257 {
258 // we have changed arc shapes, run a few extra tests
259
260 if( prevArcIdx >= 0 )
261 {
262 // prev point on arc, test that the last arc point on the chain
263 // matches the end point of the arc
264 VECTOR2I pointToTest = aChain.CPoint( i );
265
266 if( !aChain.IsSharedPt( i ) )
267 pointToTest = aChain.CPoint( i - 1 );
268
269 SHAPE_ARC lastArc = aChain.Arc( prevArcIdx );
270
271 if( lastArc.GetP1() != pointToTest )
272 return false;
273 }
274
275 if( arcIdx >= 0 )
276 {
277 // new arc, test that the start point of the arc matches the point on the chain
278 VECTOR2I pointToTest = aChain.CPoint( i );
279 SHAPE_ARC currentArc = aChain.Arc( arcIdx );
280
281 if( currentArc.GetP0() != pointToTest )
282 return false;
283 }
284 }
285
286 prevArcIdx = arcIdx;
287 }
288
289 return true;
290}
291
299inline bool IsPolySetValid( const SHAPE_POLY_SET& aSet )
300{
301 for( int i = 0; i < aSet.OutlineCount(); i++ )
302 {
303 if( !IsOutlineValid( aSet.Outline( i ) ) )
304 return false;
305
306 for( int j = 0; j < aSet.HoleCount( i ); j++ )
307 {
308 if( !IsOutlineValid( aSet.CHole( i, j ) ) )
309 return false;
310 }
311 }
312
313 return true;
314}
315
321inline bool SegmentsHaveSameEndPoints( const SEG& aSeg1, const SEG& aSeg2 )
322{
323 return ( aSeg1.A == aSeg2.A && aSeg1.B == aSeg2.B )
324 || ( aSeg1.A == aSeg2.B && aSeg1.B == aSeg2.A );
325}
326
327} // namespace GEOM_TEST
328
330{
331template <>
332struct print_log_value<SHAPE_LINE_CHAIN>
333{
334 inline void operator()( std::ostream& os, const SHAPE_LINE_CHAIN& c )
335 {
336 os << "SHAPE_LINE_CHAIN: " << c.PointCount() << " points: [\n";
337
338 for( int i = 0; i < c.PointCount(); ++i )
339 {
340 os << " " << i << ": " << c.CPoint( i ) << "\n";
341 }
342
343 os << "]";
344 }
345};
346
347}
349
350
351#endif // GEOM_TEST_UTILS_H
double AsRadians() const
Definition: eda_angle.h:153
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
const VECTOR2I & GetP1() const
Definition: shape_arc.h:113
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the segment aSeg than aClearance,...
Definition: shape_arc.cpp:242
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:221
const VECTOR2I & GetP0() const
Definition: shape_arc.h:112
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_ARC & Arc(size_t aArc) const
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
Represent a set of closed polygons.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
int HoleCount(int aOutline) const
Returns the number of holes in a given outline.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Return the reference to aIndex-th outline in the set.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
int OutlineCount() const
Return the number of outlines in the set.
Define a general 2D-vector/point.
Definition: vector2d.h:70
static constexpr EDA_ANGLE & ANGLE_180
Definition: eda_angle.h:441
static constexpr EDA_ANGLE & ANGLE_90
Definition: eda_angle.h:439
Before Boost 1.64, nullptr_t wasn't handled.
Utility functions for testing geometry functions.
bool ArePointsNearCircle(const std::vector< VECTOR2< T > > &aPoints, const VECTOR2< T > &aCentre, T aRad, T aTol)
Predicate for checking a set of points is within a certain tolerance of a circle.
bool IsOutlineValid(const SHAPE_LINE_CHAIN &aChain)
Verify that a SHAPE_LINE_CHAIN has been assembled correctly by ensuring that the arc start and end po...
bool SegmentCompletelyWithinRadius(const SEG &aSeg, const VECTOR2I &aPt, const int aRadius)
bool IsPointAtDistance(const VECTOR2< T > &aPtA, const VECTOR2< T > &aPtB, T aExpDist, T aTol)
Check that two points are the given distance apart, within the given tolerance.
bool SegmentEndsInQuadrant(const SEG &aSeg, QUADRANT aQuadrant)
SHAPE_POLY_SET FilletPolySet(SHAPE_POLY_SET &aPolySet, int aRadius, int aError)
SHAPE_LINE_CHAIN MakeSquarePolyLine(int aSize, const VECTOR2I &aCentre)
construct a square polygon of given size width and centre
bool IsInQuadrant(const VECTOR2< T > &aPoint, QUADRANT aQuadrant)
bool SegmentCompletelyInQuadrant(const SEG &aSeg, QUADRANT aQuadrant)
bool ArePerpendicular(const VECTOR2< T > &a, const VECTOR2< T > &b, const EDA_ANGLE &aTolerance)
QUADRANT
Geometric quadrants, from top-right, anti-clockwise.
bool SegmentsHaveSameEndPoints(const SEG &aSeg1, const SEG &aSeg2)
Check that two SEGs have the same end points, in either order.
bool IsPolySetValid(const SHAPE_POLY_SET &aSet)
Verify that a SHAPE_POLY_SET has been assembled correctly by verifying each of the outlines and holes...
bool IsWithin(T aValue, T aNominal, T aError)
Check if a value is within a tolerance of a nominal value.
Definition: numeric.h:57
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:426
Numerical test predicates.
void operator()(std::ostream &os, const SHAPE_LINE_CHAIN &c)
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129
#define BOOST_TEST_PRINT_NAMESPACE_CLOSE
#define BOOST_TEST_INFO(A)
If HAVE_EXPECTED_FAILURES is defined, this means that boost::unit_test::expected_failures is availabl...
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588