geom_test_utils.h

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright The KiCad Developers, see AUTHORS.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, see <https://www.gnu.org/licenses/>.
 */
 
#ifndef GEOM_TEST_UTILS_H
#define GEOM_TEST_UTILS_H
 
#include <cmath>
 
#include <geometry/point_types.h>
#include <geometry/seg.h>
#include <geometry/shape_line_chain.h>
#include <geometry/shape_poly_set.h>
 
#include <qa_utils/numeric.h>
#include <qa_utils/wx_utils/unit_test_utils.h>
#include <qa_utils/geometry/geometry.h>

namespace GEOM_TEST
{

enum class QUADRANT {
    Q1, Q2, Q3, Q4
};

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;
}

inline bool SegmentCompletelyInQuadrant( const SEG& aSeg, QUADRANT aQuadrant )
{
    return IsInQuadrant( aSeg.A, aQuadrant)
            && IsInQuadrant( aSeg.B, aQuadrant );
}

inline bool SegmentEndsInQuadrant( const SEG& aSeg, QUADRANT aQuadrant )
{
    return IsInQuadrant( aSeg.A, aQuadrant )
            || IsInQuadrant( aSeg.B, aQuadrant );
}

inline 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 );
}

template <typename T>
bool IsPointAtDistance( const VECTOR2<T>& aPtA, const VECTOR2<T>& aPtB, T aExpDist, T aTol )
{
    const int  dist = ( aPtB - aPtA ).EuclideanNorm();
    const bool ok = KI_TEST::IsWithin( dist, aExpDist, aTol );
 
    if( !ok )
    {
        BOOST_TEST_INFO( "Points not at expected distance: distance is " << dist << ", expected "
                                                                         << aExpDist );
    }
 
    return ok;
}

template <typename T>
bool ArePointsNearCircle(
        const std::vector<VECTOR2<T>>& aPoints, const VECTOR2<T>& aCentre, T aRad, T aTol )
{
    bool ok = true;
 
    for( unsigned i = 0; i < aPoints.size(); ++i )
    {
        if( !IsPointAtDistance( aPoints[i], aCentre, aRad, aTol ) )
        {
            BOOST_TEST_INFO( "Point " << i << " " << aPoints[i] << " is not within tolerance ("
                                      << aTol << ") of radius (" << aRad << ") from centre point "
                                      << aCentre );
            ok = false;
        }
    }
 
    return ok;
}

 
template<typename T>
bool ArePerpendicular( const VECTOR2<T>& a, const VECTOR2<T>& b, const EDA_ANGLE& aTolerance )
{
    EDA_ANGLE angle = std::abs( EDA_ANGLE( a ) - EDA_ANGLE( b ) );
 
    // Normalise: angles of 3*pi/2 are also perpendicular
    if (angle > ANGLE_180)
        angle -= ANGLE_180;
 
    return KI_TEST::IsWithin( angle.AsRadians(), ANGLE_90.AsRadians(), aTolerance.AsRadians() );
}

inline 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;
}

inline bool IsOutlineValid( const SHAPE_LINE_CHAIN& aChain )
{
    ssize_t           prevArcIdx = -1;
    std::set<size_t> testedArcs;
 
    if( aChain.PointCount() > 0 && !aChain.IsClosed() && aChain.IsSharedPt( 0 ) )
        return false; //can't have first point being shared on an open chain
 
    for( int i = 0; i < aChain.PointCount(); i++ )
    {
        ssize_t arcIdx = aChain.ArcIndex( i );
 
        if( arcIdx >= 0 )
        {
            // Point on arc, lets make sure it collides with the arc shape and we haven't
            // previously seen the same arc index
 
            if( prevArcIdx != arcIdx && testedArcs.count( arcIdx ) )
                return false; // we've already seen this arc before, not contiguous
 
            if( !aChain.Arc( arcIdx ).Collide( aChain.CPoint( i ),
                                               SHAPE_ARC::DefaultAccuracyForPCB() ) )
            {
                return false;
            }
 
            testedArcs.insert( arcIdx );
        }
 
        if( prevArcIdx != arcIdx )
        {
            // we have changed arc shapes, run a few extra tests
 
            if( prevArcIdx >= 0 )
            {
                // prev point on arc, test that the last arc point on the chain
                // matches the end point of the arc
                VECTOR2I pointToTest = aChain.CPoint( i );
 
                if( !aChain.IsSharedPt( i ) )
                    pointToTest = aChain.CPoint( i - 1 );
 
                SHAPE_ARC lastArc = aChain.Arc( prevArcIdx );
 
                if( lastArc.GetP1() != pointToTest )
                    return false;
            }
 
            if( arcIdx >= 0 )
            {
                // new arc, test that the start point of the arc matches the point on the chain
                VECTOR2I pointToTest = aChain.CPoint( i );
                SHAPE_ARC currentArc = aChain.Arc( arcIdx );
 
                if( currentArc.GetP0() != pointToTest )
                    return false;
            }
        }
 
        prevArcIdx = arcIdx;
    }
 
    // Make sure last arc point matches the end of the arc
    if( prevArcIdx >= 0 )
    {
        if( aChain.IsClosed() && aChain.IsSharedPt( 0 ) )
        {
            if( aChain.CShapes()[0].first != prevArcIdx )
                return false;
 
            if( aChain.Arc( prevArcIdx ).GetP1() != aChain.CPoint( 0 ) )
                return false;
        }
        else
        {
            if( aChain.Arc( prevArcIdx ).GetP1() != aChain.CLastPoint() )
                return false;
        }
    }
 
    return true;
}

inline bool IsPolySetValid( const SHAPE_POLY_SET& aSet )
{
    for( int i = 0; i < aSet.OutlineCount(); i++ )
    {
        if( !IsOutlineValid( aSet.Outline( i ) ) )
            return false;
 
        for( int j = 0; j < aSet.HoleCount( i ); j++ )
        {
            if( !IsOutlineValid( aSet.CHole( i, j ) ) )
                return false;
        }
    }
 
    return true;
}

inline bool SegmentsHaveSameEndPoints( const SEG& aSeg1, const SEG& aSeg2 )
{
    return ( aSeg1.A == aSeg2.A && aSeg1.B == aSeg2.B )
           || ( aSeg1.A == aSeg2.B && aSeg1.B == aSeg2.A );
}
 

inline double TriangleMinAngleDeg( const VECTOR2I& a, const VECTOR2I& b, const VECTOR2I& c )
{
    auto angleAt = []( const VECTOR2I& v, const VECTOR2I& p, const VECTOR2I& q )
    {
        VECTOR2D u( p.x - v.x, p.y - v.y );
        VECTOR2D w( q.x - v.x, q.y - v.y );
 
        return std::atan2( std::abs( u.x * w.y - u.y * w.x ), u.x * w.x + u.y * w.y ) * 180.0 / M_PI;
    };
 
    return std::min( { angleAt( a, b, c ), angleAt( b, c, a ), angleAt( c, a, b ) } );
}
 
} // namespace GEOM_TEST
 
 
// Not clear why boost_test_print_type doesn't work on Debian specifically for this type,
// but this works on all platforms
std::ostream& operator<<( std::ostream& os, const TYPED_POINT2I& c );
 
#endif // GEOM_TEST_UTILS_H