corner_operations.cpp

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2023-2024 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, 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 "geometry/corner_operations.h"
 
#include <geometry/circle.h>
#include <geometry/half_line.h>
#include <geometry/shape_arc.h>
#include <geometry/shape_utils.h>
#include <geometry/vector_utils.h>
#include <trigo.h>
 
namespace
{
 
SEG GetBisectorOfCornerSegments( const SEG& aSegA, const SEG& aSegB, int aLength )
{
    // Use the "parallelogram" method to find the bisector
 
    // The intersection point of the two lines is the one that is shared by both segments
    const std::optional<VECTOR2I> corner = KIGEOM::GetSharedEndpoint( aSegA, aSegB );
 
    // Get the vector of a segment pointing away from a point
    const auto getSegVectorPointingAwayFrom = []( const SEG&      aSeg,
                                                  const VECTOR2I& aPoint ) -> VECTOR2I
    {
        const int distA = ( aSeg.A - aPoint ).EuclideanNorm();
        const int distB = ( aSeg.B - aPoint ).EuclideanNorm();
 
        // If A is closer the segment is already pointing away from the corner
        // If B is closer, we need to reverse the segment
        return ( distA < distB ) ? ( aSeg.B - aSeg.A ) : ( aSeg.A - aSeg.B );
    };
 
    // The vectors have to be the same length
    const int      maxLen = std::max( aSegA.Length(), aSegB.Length() );
    const VECTOR2I aVecOutward = getSegVectorPointingAwayFrom( aSegA, *corner ).Resize( maxLen );
    const VECTOR2I bVecOutward = getSegVectorPointingAwayFrom( aSegB, *corner ).Resize( maxLen );
    const VECTOR2I bisectorOutward = aVecOutward + bVecOutward;
 
    return SEG( *corner, *corner + bisectorOutward.Resize( aLength ) );
}
 
} // namespace
 
std::optional<CHAMFER_RESULT> ComputeChamferPoints( const SEG& aSegA, const SEG& aSegB,
                                                    const CHAMFER_PARAMS& aChamferParams )
{
    const int line_a_setback = aChamferParams.m_chamfer_setback_a;
    const int line_b_setback = aChamferParams.m_chamfer_setback_b;
 
    if( line_a_setback == 0 && line_b_setback == 0 )
    {
        // No chamfer to do
        // In theory a chamfer of 0 on one side is kind-of valid (adds a collinear point)
        // so allow it (using an and above, not an or)
        return std::nullopt;
    }
 
    if( aSegA.Length() < line_a_setback || aSegB.Length() < line_b_setback )
    {
        // Chamfer is too big for the line segments
        return std::nullopt;
    }
 
    // We only support the case where the lines intersect at the end points
    // otherwise we would need to decide which inside corner to chamfer
 
    // Figure out which end points are the ones at the intersection
    const std::optional<VECTOR2I> corner = KIGEOM::GetSharedEndpoint( aSegA, aSegB );
 
    if( !corner )
    {
        // The lines are not coterminous
        return std::nullopt;
    }
 
    // These are the other existing line points (the ones that are not the intersection)
    const VECTOR2I& a_end_pt = KIGEOM::GetOtherEnd( aSegA, *corner );
    const VECTOR2I& b_end_pt = KIGEOM::GetOtherEnd( aSegB, *corner );
 
    // Now, construct segment of the set-back lengths, that begins
    // at the intersection point and is parallel to each line segments
    SEG setback_a( *corner, *corner + VECTOR2I( a_end_pt - *corner ).Resize( line_a_setback ) );
    SEG setback_b( *corner, *corner + VECTOR2I( b_end_pt - *corner ).Resize( line_b_setback ) );
 
    // The chamfer segment then goes between the end points of the set-back segments
    SEG chamfer( setback_a.B, setback_b.B );
 
    // The adjusted segments go from the old end points to the chamfer ends
 
    std::optional<SEG> new_a;
 
    if( a_end_pt != chamfer.A )
        new_a = SEG{ a_end_pt, chamfer.A };
 
    std::optional<SEG> new_b;
 
    if( b_end_pt != chamfer.B )
        new_b = SEG{ b_end_pt, chamfer.B };
 
    return CHAMFER_RESULT{ chamfer, new_a, new_b };
}
 
 
std::optional<DOGBONE_RESULT> ComputeDogbone( const SEG& aSegA, const SEG& aSegB,
                                              int aDogboneRadius, bool aAddSlots )
{
    const std::optional<VECTOR2I> corner = KIGEOM::GetSharedEndpoint( aSegA, aSegB );
 
    // Cannot handle parallel lines
    if( !corner || aSegA.Angle( aSegB ).IsHorizontal() )
    {
        return std::nullopt;
    }
 
    const SEG bisector = GetBisectorOfCornerSegments( aSegA, aSegB, aDogboneRadius );
 
    // The dogbone center is the end of the bisector
    const VECTOR2I dogboneCenter = bisector.B;
 
    // We can find the ends of the arc by considering the corner angle,
    // but it's easier to just intersect the circle with the original segments.
 
    const CIRCLE circle( dogboneCenter, aDogboneRadius );
 
    const std::vector<VECTOR2I> segAIntersections = circle.Intersect( aSegA );
    const std::vector<VECTOR2I> segBIntersections = circle.Intersect( aSegB );
 
    // There can be a little bit of error in the intersection calculation
    static int s_epsilon = 8;
 
    const auto getPointNotOnCorner =
            [&]( const std::vector<VECTOR2I>& aIntersections, const VECTOR2I& aCorner )
    {
        std::optional<VECTOR2I> result;
        for( const VECTOR2I& pt : aIntersections )
        {
            if( aCorner.Distance( pt ) > s_epsilon )
            {
                result = pt;
                break;
            }
        }
        return result;
    };
 
    const std::optional<VECTOR2I> ptOnSegA = getPointNotOnCorner( segAIntersections, *corner );
    const std::optional<VECTOR2I> ptOnSegB = getPointNotOnCorner( segBIntersections, *corner );
 
    // The arc doesn't cross one or both of the segments
    if( !ptOnSegA || !ptOnSegB )
    {
        return std::nullopt;
    }
 
    SHAPE_ARC arc( *ptOnSegA, *corner, *ptOnSegB, 0 );
 
    const VECTOR2I& aOtherPtA = KIGEOM::GetOtherEnd( aSegA, *corner );
    const VECTOR2I& aOtherPtB = KIGEOM::GetOtherEnd( aSegB, *corner );
 
    const EDA_ANGLE angle_epsilon( 1e-3, EDA_ANGLE_T::DEGREES_T );
    const bool small_arc_mouth = std::abs( arc.GetCentralAngle() ) > ( ANGLE_180 + angle_epsilon );
 
    {
        // See if we need to update the original segments
        // or if the dogbone consumed them
        std::optional<SEG> new_a, new_b;
        if( aOtherPtA != *ptOnSegA )
            new_a = SEG{ aOtherPtA, *ptOnSegA };
 
        if( aOtherPtB != *ptOnSegB )
            new_b = SEG{ aOtherPtB, *ptOnSegB };
 
        // Nice and easy
        if( !small_arc_mouth || !aAddSlots )
        {
            return DOGBONE_RESULT{
                arc,
                new_a,
                new_b,
                small_arc_mouth,
            };
        }
    }
 
    // If it's a small mouth, we can try to work out the minimal slot to allow
 
    // First the arc will be pulled back to 180 degrees
    SHAPE_ARC slotArc = SHAPE_ARC( GetRotated( *corner, dogboneCenter, ANGLE_90 ), *corner,
                                   GetRotated( *corner, dogboneCenter, -ANGLE_90 ), 0 );
 
    // Make sure P0 is still the 'A' end
    if( !KIGEOM::PointsAreInSameDirection( slotArc.GetP0(), arc.GetP0(), dogboneCenter ) )
    {
        slotArc.Reverse();
    }
 
    // Take the bisector and glue it to the arc ends
    const HALF_LINE arc_extension_a{
        slotArc.GetP0(),
        slotArc.GetP0() + ( dogboneCenter - *corner ),
    };
    const HALF_LINE arc_extension_b{
        slotArc.GetP1(),
        slotArc.GetP1() + ( dogboneCenter - *corner ),
    };
 
    const OPT_VECTOR2I ext_a_intersect = arc_extension_a.Intersect( aSegA );
    const OPT_VECTOR2I ext_b_intersect = arc_extension_b.Intersect( aSegB );
 
    if( !ext_a_intersect || !ext_b_intersect )
    {
        // The arc extensions don't intersect the original segments
        return std::nullopt;
    }
 
    {
        // See if we need to update the original segments
        // or if the dogbone consumed them
        std::optional<SEG> new_a, new_b;
        if( aOtherPtA != *ext_a_intersect )
            new_a = SEG{ aOtherPtA, *ext_a_intersect };
 
        if( aOtherPtB != *ext_b_intersect )
            new_b = SEG{ aOtherPtB, *ext_b_intersect };
 
        return DOGBONE_RESULT{
            slotArc,
            new_a,
            new_b,
            small_arc_mouth,
        };
    }
}