KiCad PCB EDA Suite
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 
39 namespace GEOM_TEST
40 {
41 
51 enum class QUADRANT {
52  Q1, Q2, Q3, Q4
53 };
54 
55 /*
56  * @brief Check value in Quadrant 1 (x and y both >= 0)
57  */
58 template<typename T>
59 bool 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  */
85 inline 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  */
94 inline 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  */
103 inline 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 
119 template <typename T>
120 bool 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 
143 template <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 
171 template<typename T>
172 bool ArePerpendicular( const VECTOR2<T>& a, const VECTOR2<T>& b, double aTolerance )
173 {
174  auto angle = std::abs( a.Angle() - b.Angle() );
175 
176  // Normalise: angles of 3*pi/2 are also perpendicular
177  if (angle > M_PI)
178  {
179  angle -= M_PI;
180  }
181 
182  return KI_TEST::IsWithin( angle, M_PI / 2.0, aTolerance );
183 }
184 
191 inline SHAPE_LINE_CHAIN MakeSquarePolyLine( int aSize, const VECTOR2I& aCentre )
192 {
193  SHAPE_LINE_CHAIN polyLine;
194 
195  const VECTOR2I corner = aCentre + aSize / 2;
196 
197  polyLine.Append( VECTOR2I( corner.x, corner.y ) );
198  polyLine.Append( VECTOR2I( -corner.x, corner.y ) ) ;
199  polyLine.Append( VECTOR2I( -corner.x, -corner.y ) );
200  polyLine.Append( VECTOR2I( corner.x, -corner.y ) );
201 
202  polyLine.SetClosed( true );
203 
204  return polyLine;
205 }
206 
207 /*
208  * @brief Fillet every polygon in a set and return a new set
209  */
210 inline SHAPE_POLY_SET FilletPolySet( SHAPE_POLY_SET& aPolySet, int aRadius, int aError )
211 {
212  SHAPE_POLY_SET filletedPolySet;
213 
214  for ( int i = 0; i < aPolySet.OutlineCount(); ++i )
215  {
216  const auto filleted = aPolySet.FilletPolygon( aRadius, aError, i );
217 
218  filletedPolySet.AddOutline( filleted[0] );
219  }
220 
221  return filletedPolySet;
222 }
223 
232 inline bool IsOutlineValid( const SHAPE_LINE_CHAIN& aChain )
233 {
234  ssize_t prevArcIdx = -1;
235  std::set<size_t> testedArcs;
236 
237  for( int i = 0; i < aChain.PointCount(); i++ )
238  {
239  ssize_t arcIdx = aChain.ArcIndex( i );
240 
241  if( arcIdx >= 0 )
242  {
243  // Point on arc, lets make sure it collides with the arc shape and we haven't
244  // previously seen the same arc index
245 
246  if( prevArcIdx != arcIdx && testedArcs.count( arcIdx ) )
247  return false; // we've already seen this arc before, not contiguous
248 
249  if( !aChain.Arc( arcIdx ).Collide( aChain.CPoint( i ),
251  {
252  return false;
253  }
254 
255  testedArcs.insert( arcIdx );
256  }
257 
258  if( prevArcIdx != arcIdx )
259  {
260  // we have changed arc shapes, run a few extra tests
261 
262  if( prevArcIdx >= 0 )
263  {
264  // prev point on arc, test that the last arc point on the chain
265  // matches the end point of the arc
266  VECTOR2I pointToTest = aChain.CPoint( i );
267 
268  if( !aChain.IsSharedPt( i ) )
269  pointToTest = aChain.CPoint( i - 1 );
270 
271  SHAPE_ARC lastArc = aChain.Arc( prevArcIdx );
272 
273  if( lastArc.GetP1() != pointToTest )
274  return false;
275  }
276 
277  if( arcIdx >= 0 )
278  {
279  // new arc, test that the start point of the arc matches the point on the chain
280  VECTOR2I pointToTest = aChain.CPoint( i );
281  SHAPE_ARC currentArc = aChain.Arc( arcIdx );
282 
283  if( currentArc.GetP0() != pointToTest )
284  return false;
285  }
286  }
287 
288  prevArcIdx = arcIdx;
289  }
290 
291  return true;
292 }
293 
301 inline bool IsPolySetValid( const SHAPE_POLY_SET& aSet )
302 {
303  for( int i = 0; i < aSet.OutlineCount(); i++ )
304  {
305  if( !IsOutlineValid( aSet.Outline( i ) ) )
306  return false;
307 
308  for( int j = 0; j < aSet.HoleCount( i ); j++ )
309  {
310  if( !IsOutlineValid( aSet.CHole( i, j ) ) )
311  return false;
312  }
313  }
314 
315  return true;
316 }
317 
318 } // namespace GEOM_TEST
319 
321 {
322 template <>
323 struct print_log_value<SHAPE_LINE_CHAIN>
324 {
325  inline void operator()( std::ostream& os, const SHAPE_LINE_CHAIN& c )
326  {
327  os << "SHAPE_LINE_CHAIN: " << c.PointCount() << " points: [\n";
328 
329  for( int i = 0; i < c.PointCount(); ++i )
330  {
331  os << " " << i << ": " << c.CPoint( i ) << "\n";
332  }
333 
334  os << "]";
335  }
336 };
337 }
339 
340 
341 #endif // GEOM_TEST_UTILS_H
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
Before Boost 1.64, nullptr_t wasn't handled.
const SHAPE_ARC & Arc(size_t aArc) const
bool IsWithin(T aValue, T aNominal, T aError)
Check if a value is within a tolerance of a nominal value.
Definition: numeric.h:57
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
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 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:229
SHAPE_POLY_SET FilletPolySet(SHAPE_POLY_SET &aPolySet, int aRadius, int aError)
Define a general 2D-vector/point.
Definition: vector2d.h:61
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:220
QUADRANT
Geometric quadrants, from top-right, anti-clockwise.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Return the number of points (vertices) in this line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
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...
#define BOOST_TEST_PRINT_NAMESPACE_CLOSE
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
bool SegmentCompletelyWithinRadius(const SEG &aSeg, const VECTOR2I &aPt, const int aRadius)
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
SHAPE_LINE_CHAIN MakeSquarePolyLine(int aSize, const VECTOR2I &aCentre)
construct a square polygon of given size width and centre
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
void operator()(std::ostream &os, const SHAPE_LINE_CHAIN &c)
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 SegmentEndsInQuadrant(const SEG &aSeg, QUADRANT aQuadrant)
double Angle() const
Compute the angle of the vector.
Definition: vector2d.h:307
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
Utility functions for testing geometry functions.
Definition: seg.h:40
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
VECTOR2I A
Definition: seg.h:48
bool IsInQuadrant(const VECTOR2< T > &aPoint, QUADRANT aQuadrant)
Numerical test predicates.
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 SegmentCompletelyInQuadrant(const SEG &aSeg, QUADRANT aQuadrant)
const VECTOR2I & GetP1() const
Definition: shape_arc.h:112
#define BOOST_TEST_INFO(A)
If HAVE_EXPECTED_FAILURES is defined, this means that boost::unit_test::expected_failures is availabl...
bool ArePerpendicular(const VECTOR2< T > &a, const VECTOR2< T > &b, double aTolerance)
VECTOR2I B
Definition: seg.h:49