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 if( aChain.PointCount() > 0 && !aChain.IsClosed() && aChain.IsSharedPt( 0 ) )
236 return false; //can't have first point being shared on an open chain
237
238 for( int i = 0; i < aChain.PointCount(); i++ )
239 {
240 ssize_t arcIdx = aChain.ArcIndex( i );
241
242 if( arcIdx >= 0 )
243 {
244 // Point on arc, lets make sure it collides with the arc shape and we haven't
245 // previously seen the same arc index
246
247 if( prevArcIdx != arcIdx && testedArcs.count( arcIdx ) )
248 return false; // we've already seen this arc before, not contiguous
249
250 if( !aChain.Arc( arcIdx ).Collide( aChain.CPoint( i ),
252 {
253 return false;
254 }
255
256 testedArcs.insert( arcIdx );
257 }
258
259 if( prevArcIdx != arcIdx )
260 {
261 // we have changed arc shapes, run a few extra tests
262
263 if( prevArcIdx >= 0 )
264 {
265 // prev point on arc, test that the last arc point on the chain
266 // matches the end point of the arc
267 VECTOR2I pointToTest = aChain.CPoint( i );
268
269 if( !aChain.IsSharedPt( i ) )
270 pointToTest = aChain.CPoint( i - 1 );
271
272 SHAPE_ARC lastArc = aChain.Arc( prevArcIdx );
273
274 if( lastArc.GetP1() != pointToTest )
275 return false;
276 }
277
278 if( arcIdx >= 0 )
279 {
280 // new arc, test that the start point of the arc matches the point on the chain
281 VECTOR2I pointToTest = aChain.CPoint( i );
282 SHAPE_ARC currentArc = aChain.Arc( arcIdx );
283
284 if( currentArc.GetP0() != pointToTest )
285 return false;
286 }
287 }
288
289 prevArcIdx = arcIdx;
290 }
291
292 // Make sure last arc point matches the end of the arc
293 if( prevArcIdx >= 0 )
294 {
295 if( aChain.IsClosed() && aChain.IsSharedPt( 0 ) )
296 {
297 if( aChain.CShapes()[0].first != prevArcIdx )
298 return false;
299
300 if( aChain.Arc( prevArcIdx ).GetP1() != aChain.CPoint( 0 ) )
301 return false;
302 }
303 else
304 {
305 if( aChain.Arc( prevArcIdx ).GetP1() != aChain.CPoint( -1 ) )
306 return false;
307 }
308 }
309
310 return true;
311}
312
320inline bool IsPolySetValid( const SHAPE_POLY_SET& aSet )
321{
322 for( int i = 0; i < aSet.OutlineCount(); i++ )
323 {
324 if( !IsOutlineValid( aSet.Outline( i ) ) )
325 return false;
326
327 for( int j = 0; j < aSet.HoleCount( i ); j++ )
328 {
329 if( !IsOutlineValid( aSet.CHole( i, j ) ) )
330 return false;
331 }
332 }
333
334 return true;
335}
336
342inline bool SegmentsHaveSameEndPoints( const SEG& aSeg1, const SEG& aSeg2 )
343{
344 return ( aSeg1.A == aSeg2.A && aSeg1.B == aSeg2.B )
345 || ( aSeg1.A == aSeg2.B && aSeg1.B == aSeg2.A );
346}
347
348} // namespace GEOM_TEST
349
351{
352template <>
353struct print_log_value<SHAPE_LINE_CHAIN>
354{
355 inline void operator()( std::ostream& os, const SHAPE_LINE_CHAIN& c )
356 {
357 os << "SHAPE_LINE_CHAIN: " << c.PointCount() << " points: [\n";
358
359 for( int i = 0; i < c.PointCount(); ++i )
360 {
361 os << " " << i << ": " << c.CPoint( i ) << "\n";
362 }
363
364 os << "]";
365 }
366};
367
368}
370
371
372#endif // GEOM_TEST_UTILS_H
double AsRadians() const
Definition: eda_angle.h:159
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:223
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
bool IsClosed() const override
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.
const std::vector< std::pair< ssize_t, ssize_t > > & CShapes() const
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_90
Definition: eda_angle.h:437
static constexpr EDA_ANGLE ANGLE_180
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:424
Numerical test predicates.
void operator()(std::ostream &os, const SHAPE_LINE_CHAIN &c)
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:128
#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