intersection.cpp

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 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/intersection.h"
 
#include <core/type_helpers.h>
 
#include <geometry/shape_utils.h>
 
/*
 * Helper functions that dispatch to the correct intersection function
 * in one of the geometry classes.
 */
namespace
{
 
void findIntersections( const SEG& aSegA, const SEG& aSegB, std::vector<VECTOR2I>& aIntersections )
{
    const OPT_VECTOR2I intersection = aSegA.Intersect( aSegB );
 
    if( intersection )
    {
        aIntersections.push_back( *intersection );
    }
}
 
void findIntersections( const SEG& aSeg, const LINE& aLine, std::vector<VECTOR2I>& aIntersections )
{
    OPT_VECTOR2I intersection = aLine.Intersect( aSeg );
 
    if( intersection )
    {
        aIntersections.push_back( *intersection );
    }
}
 
void findIntersections( const SEG& aSeg, const HALF_LINE& aHalfLine,
                        std::vector<VECTOR2I>& aIntersections )
{
    OPT_VECTOR2I intersection = aHalfLine.Intersect( aSeg );
 
    if( intersection )
    {
        aIntersections.push_back( *intersection );
    }
}
 
void findIntersections( const SEG& aSeg, const CIRCLE& aCircle,
                        std::vector<VECTOR2I>& aIntersections )
{
    std::vector<VECTOR2I> intersections = aCircle.Intersect( aSeg );
 
    aIntersections.insert( aIntersections.end(), intersections.begin(), intersections.end() );
}
 
void findIntersections( const SEG& aSeg, const SHAPE_ARC& aArc,
                        std::vector<VECTOR2I>& aIntersections )
{
    std::vector<VECTOR2I> intersections;
    aArc.IntersectLine( aSeg, &intersections );
 
    // Find only the intersections that are within the segment
    for( const VECTOR2I& intersection : intersections )
    {
        if( aSeg.Contains( intersection ) )
        {
            aIntersections.emplace_back( intersection );
        }
    }
}
 
void findIntersections( const LINE& aLineA, const LINE& aLineB,
                        std::vector<VECTOR2I>& aIntersections )
{
    OPT_VECTOR2I intersection = aLineA.Intersect( aLineB );
 
    if( intersection )
    {
        aIntersections.push_back( *intersection );
    }
}
 
void findIntersections( const LINE& aLine, const HALF_LINE& aHalfLine,
                        std::vector<VECTOR2I>& aIntersections )
{
    // Intersect as two infinite lines
    OPT_VECTOR2I intersection =
            aHalfLine.GetContainedSeg().Intersect( aLine.GetContainedSeg(), false, true );
 
    // No intersection at all (parallel, or passes on the other side of the start point)
    if( !intersection )
    {
        return;
    }
 
    if( aHalfLine.Contains( *intersection ) )
    {
        aIntersections.push_back( *intersection );
    }
}
 
void findIntersections( const HALF_LINE& aHalfLineA, const HALF_LINE& aHalfLineB,
                        std::vector<VECTOR2I>& aIntersections )
{
    OPT_VECTOR2I intersection = aHalfLineA.Intersect( aHalfLineB );
 
    if( intersection )
    {
        aIntersections.push_back( *intersection );
    }
}
 
void findIntersections( const CIRCLE& aCircle, const LINE& aLine,
                        std::vector<VECTOR2I>& aIntersections )
{
    std::vector<VECTOR2I> intersections = aCircle.IntersectLine( aLine.GetContainedSeg() );
 
    aIntersections.insert( aIntersections.end(), intersections.begin(), intersections.end() );
}
 
void findIntersections( const CIRCLE& aCircle, const HALF_LINE& aHalfLine,
                        std::vector<VECTOR2I>& aIntersections )
{
    std::vector<VECTOR2I> intersections = aCircle.IntersectLine( aHalfLine.GetContainedSeg() );
 
    for( const VECTOR2I& intersection : intersections )
    {
        if( aHalfLine.Contains( intersection ) )
        {
            aIntersections.push_back( intersection );
        }
    }
}
 
void findIntersections( const CIRCLE& aCircleA, const CIRCLE& aCircleB,
                        std::vector<VECTOR2I>& aIntersections )
{
    std::vector<VECTOR2I> intersections = aCircleA.Intersect( aCircleB );
    aIntersections.insert( aIntersections.end(), intersections.begin(), intersections.end() );
}
 
void findIntersections( const CIRCLE& aCircle, const SHAPE_ARC& aArc,
                        std::vector<VECTOR2I>& aIntersections )
{
    aArc.Intersect( aCircle, &aIntersections );
}
 
void findIntersections( const SHAPE_ARC& aArcA, const SHAPE_ARC& aArcB,
                        std::vector<VECTOR2I>& aIntersections )
{
    aArcA.Intersect( aArcB, &aIntersections );
}
 
void findIntersections( const SHAPE_ARC& aArc, const LINE& aLine,
                        std::vector<VECTOR2I>& aIntersections )
{
    std::vector<VECTOR2I> intersections;
    aArc.IntersectLine( aLine.GetContainedSeg(), &intersections );
 
    aIntersections.insert( aIntersections.end(), intersections.begin(), intersections.end() );
}
 
void findIntersections( const SHAPE_ARC& aArc, const HALF_LINE& aHalfLine,
                        std::vector<VECTOR2I>& aIntersections )
{
    std::vector<VECTOR2I> intersections;
    aArc.IntersectLine( aHalfLine.GetContainedSeg(), &intersections );
 
    for( const VECTOR2I& intersection : intersections )
    {
        if( aHalfLine.Contains( intersection ) )
        {
            aIntersections.push_back( intersection );
        }
    }
}
 
} // namespace
 
 
INTERSECTION_VISITOR::INTERSECTION_VISITOR( const INTERSECTABLE_GEOM& aOtherGeometry,
                                            std::vector<VECTOR2I>&    aIntersections ) :
        m_otherGeometry( aOtherGeometry ), m_intersections( aIntersections )
{
}
 
/*
 * The operator() functions are the entry points for the visitor.
 *
 * Dispatch to the correct function based on the type of the "otherGeometry"
 * which is held as state. This is also where the order of the parameters is
 * determined, which avoids having to define a 'reverse' function for each
 * intersection type.
 */
 
void INTERSECTION_VISITOR::operator()( const SEG& aSeg ) const
{
    // Dispatch to the correct function
    return std::visit(
            [&]( const auto& otherGeom )
            {
                using OtherGeomType = std::decay_t<decltype( otherGeom )>;
 
                if constexpr( std::is_same_v<OtherGeomType, BOX2I> )
                {
                    // Seg-Rect via decomposition into segments
                    for( const SEG& aRectSeg : KIGEOM::BoxToSegs( otherGeom ) )
                    {
                        findIntersections( aSeg, aRectSeg, m_intersections );
                    }
                }
                else
                {
                    // In all other segment comparisons, the SEG is the first argument
                    findIntersections( aSeg, otherGeom, m_intersections );
                }
            },
            m_otherGeometry );
}
 
void INTERSECTION_VISITOR::operator()( const LINE& aLine ) const
{
    // Dispatch to the correct function
    return std::visit(
            [&]( const auto& otherGeom )
            {
                using OtherGeomType = std::decay_t<decltype( otherGeom )>;
                // Dispatch in the correct order
                if constexpr( std::is_same_v<OtherGeomType, SEG>
                              || std::is_same_v<OtherGeomType, LINE>
                              || std::is_same_v<OtherGeomType, CIRCLE>
                              || std::is_same_v<OtherGeomType, SHAPE_ARC> )
                {
                    // Seg-Line, Line-Line, Circle-Line, Arc-Line
                    findIntersections( otherGeom, aLine, m_intersections );
                }
                else if constexpr( std::is_same_v<OtherGeomType, HALF_LINE> )
                {
                    // Line-HalfLine
                    findIntersections( aLine, otherGeom, m_intersections );
                }
                else if constexpr( std::is_same_v<OtherGeomType, BOX2I> )
                {
                    // Line-Rect via decomposition into segments
                    for( const SEG& aRectSeg : KIGEOM::BoxToSegs( otherGeom ) )
                    {
                        findIntersections( aRectSeg, aLine, m_intersections );
                    }
                }
                else
                {
                    static_assert( always_false<OtherGeomType>::value,
                                   "Unhandled other geometry type" );
                }
            },
            m_otherGeometry );
};
 
void INTERSECTION_VISITOR::operator()( const HALF_LINE& aHalfLine ) const
{
    // Dispatch to the correct function
    return std::visit(
            [&]( const auto& otherGeom )
            {
                using OtherGeomType = std::decay_t<decltype( otherGeom )>;
                // Dispatch in the correct order
                if constexpr( std::is_same_v<OtherGeomType, SEG>
                              || std::is_same_v<OtherGeomType, HALF_LINE>
                              || std::is_same_v<OtherGeomType, CIRCLE>
                              || std::is_same_v<OtherGeomType, SHAPE_ARC> )
                {
                    // Seg-HalfLine, HalfLine-HalfLine, Circle-HalfLine, Arc-HalfLine
                    findIntersections( otherGeom, aHalfLine, m_intersections );
                }
                else if constexpr( std::is_same_v<OtherGeomType, LINE> )
                {
                    // Line-HalfLine
                    findIntersections( otherGeom, aHalfLine, m_intersections );
                }
                else if constexpr( std::is_same_v<OtherGeomType, BOX2I> )
                {
                    // HalfLine-Rect via decomposition into segments
                    for( const SEG& aRectSeg : KIGEOM::BoxToSegs( otherGeom ) )
                    {
                        findIntersections( aRectSeg, aHalfLine, m_intersections );
                    }
                }
                else
                {
                    static_assert( always_false<OtherGeomType>::value,
                                   "Unhandled other geometry type" );
                }
            },
            m_otherGeometry );
};
 
void INTERSECTION_VISITOR::operator()( const CIRCLE& aCircle ) const
{
    // Dispatch to the correct function
    return std::visit(
            [&]( const auto& otherGeom )
            {
                using OtherGeomType = std::decay_t<decltype( otherGeom )>;
                // Dispatch in the correct order
                if constexpr( std::is_same_v<OtherGeomType, SEG>
                              || std::is_same_v<OtherGeomType, CIRCLE> )
                {
                    // Seg-Circle, Circle-Circle
                    findIntersections( otherGeom, aCircle, m_intersections );
                }
                else if constexpr( std::is_same_v<OtherGeomType, SHAPE_ARC>
                                   || std::is_same_v<OtherGeomType, LINE>
                                   || std::is_same_v<OtherGeomType, HALF_LINE> )
                {
                    // Circle-Arc, Circle-Line, Circle-HalfLine
                    findIntersections( aCircle, otherGeom, m_intersections );
                }
                else if constexpr( std::is_same_v<OtherGeomType, BOX2I> )
                {
                    // Circle-Rect via decomposition into segments
                    for( const SEG& aRectSeg : KIGEOM::BoxToSegs( otherGeom ) )
                    {
                        findIntersections( aRectSeg, aCircle, m_intersections );
                    }
                }
                else
                {
                    static_assert( always_false<OtherGeomType>::value,
                                   "Unhandled other geometry type" );
                }
            },
            m_otherGeometry );
}
 
void INTERSECTION_VISITOR::operator()( const SHAPE_ARC& aArc ) const
{
    // Dispatch to the correct function
    return std::visit(
            [&]( const auto& otherGeom )
            {
                using OtherGeomType = std::decay_t<decltype( otherGeom )>;
                // Dispatch in the correct order
                if constexpr( std::is_same_v<OtherGeomType, SEG>
                              || std::is_same_v<OtherGeomType, CIRCLE>
                              || std::is_same_v<OtherGeomType, SHAPE_ARC> )
                {
                    // Seg-Arc, Circle-Arc, Arc-Arc
                    findIntersections( otherGeom, aArc, m_intersections );
                }
                else if constexpr( std::is_same_v<OtherGeomType, LINE>
                                   || std::is_same_v<OtherGeomType, HALF_LINE> )
                {
                    // Arc-Line, Arc-HalfLine
                    findIntersections( aArc, otherGeom, m_intersections );
                }
                else if constexpr( std::is_same_v<OtherGeomType, BOX2I> )
                {
                    // Arc-Rect via decomposition into segments
                    for( const SEG& aRectSeg : KIGEOM::BoxToSegs( otherGeom ) )
                    {
                        findIntersections( aRectSeg, aArc, m_intersections );
                    }
                }
                else
                {
                    static_assert( always_false<OtherGeomType>::value,
                                   "Unhandled other geometry type" );
                }
            },
            m_otherGeometry );
};
 
 
void INTERSECTION_VISITOR::operator()( const BOX2I& aRect ) const
{
    // Defer to the SEG visitor repeatedly
    // Note - in some cases, points can be repeated in the intersection list
    // if that's an issue, both directions of the visitor can be implemented
    // to take care of that.
    const std::array<SEG, 4> segs = KIGEOM::BoxToSegs( aRect );
 
    for( const SEG& seg : segs )
    {
        ( *this )( seg );
    }
};