drc_creepage_utils.cpp

Go to the documentation of this file.

/*
    * Copyright The KiCad Developers.
    * Copyright (C) 2024 Fabien Corona f.corona<at>laposte.net
    *
    * 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/>.
    */
 
#include "drc/drc_creepage_utils.h"
 
#include <geometry/intersection.h>
#include <geometry/shape_simple.h>
#include <pcb_track.h>
#include <thread_pool.h>
 
 
void BuildCreepageBoardEdges( BOARD& aBoard, std::vector<BOARD_ITEM*>& aVector,
                              std::vector<std::unique_ptr<PCB_SHAPE>>&  aOwned,
                              const std::set<const BOARD_ITEM*>*        aExclude )
{
    const int errorMax = aBoard.GetDesignSettings().m_MaxError;
 
    auto excluded = [&]( const BOARD_ITEM* aItem ) -> bool
    {
        if( !aExclude || !aItem )
            return false;
 
        if( aExclude->count( aItem ) )
            return true;
 
        const BOARD_ITEM* parent = dynamic_cast<const BOARD_ITEM*>( aItem->GetParent() );
 
        return parent && aExclude->count( parent );
    };
 
    // The creepage graph only handles SEGMENT/ARC/CIRCLE/RECTANGLE/POLY, so Bezier curves must be
    // flattened to segments or they are silently ignored and creepage paths pass through them
    auto addEdgeDrawing = [&]( BOARD_ITEM* aDrawing )
    {
        if( !aDrawing || !aDrawing->IsOnLayer( Edge_Cuts ) )
            return;
 
        if( excluded( aDrawing ) )
            return;
 
        // Downstream code static_casts every item in m_boardEdge to PCB_SHAPE, so non-shape items
        // (text, dimensions, ...) on Edge.Cuts must not enter the graph
        PCB_SHAPE* shape = dynamic_cast<PCB_SHAPE*>( aDrawing );
 
        if( !shape )
            return;
 
        if( shape->GetShape() != SHAPE_T::BEZIER )
        {
            aVector.push_back( shape );
            return;
        }
 
        shape->RebuildBezierToSegmentsPointsList( errorMax );
        const std::vector<VECTOR2I>& pts = shape->GetBezierPoints();
 
        for( size_t i = 1; i < pts.size(); ++i )
        {
            if( pts[i - 1] == pts[i] )
                continue;
 
            auto seg = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::SEGMENT );
            seg->SetStart( pts[i - 1] );
            seg->SetEnd( pts[i] );
            aVector.push_back( seg.get() );
            aOwned.push_back( std::move( seg ) );
        }
    };
 
    for( BOARD_ITEM* drawing : aBoard.Drawings() )
        addEdgeDrawing( drawing );
 
    for( FOOTPRINT* fp : aBoard.Footprints() )
    {
        if( !fp )
            continue;
 
        for( BOARD_ITEM* drawing : fp->GraphicalItems() )
            addEdgeDrawing( drawing );
    }
 
    for( const PAD* p : aBoard.GetPads() )
    {
        if( !p || p->GetAttribute() != PAD_ATTRIB::NPTH )
            continue;
 
        if( excluded( p ) )
            continue;
 
        std::shared_ptr<SHAPE_SEGMENT> hole = p->GetEffectiveHoleShape();
 
        if( !hole )
            continue;
 
        VECTOR2I ptA = hole->GetSeg().A;
        VECTOR2I ptB = hole->GetSeg().B;
        int      radius = hole->GetWidth() / 2;
 
        if( ptA == ptB )
        {
            auto s = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::CIRCLE );
            s->SetRadius( radius );
            s->SetPosition( ptA );
            aVector.push_back( s.get() );
            aOwned.push_back( std::move( s ) );
        }
        else
        {
            // Oblong slot outline as two straight sides and two semicircular end caps
            VECTOR2I axis = ptB - ptA;
            VECTOR2I perp = axis.Perpendicular().Resize( radius );
 
            auto seg1 = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::SEGMENT );
            seg1->SetStart( ptA + perp );
            seg1->SetEnd( ptB + perp );
            aVector.push_back( seg1.get() );
            aOwned.push_back( std::move( seg1 ) );
 
            auto seg2 = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::SEGMENT );
            seg2->SetStart( ptA - perp );
            seg2->SetEnd( ptB - perp );
            aVector.push_back( seg2.get() );
            aOwned.push_back( std::move( seg2 ) );
 
            VECTOR2I midA = ptA - axis.Resize( radius );
            auto     arcA = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::ARC );
            arcA->SetArcGeometry( ptA + perp, midA, ptA - perp );
            aVector.push_back( arcA.get() );
            aOwned.push_back( std::move( arcA ) );
 
            VECTOR2I midB = ptB + axis.Resize( radius );
            auto     arcB = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::ARC );
            arcB->SetArcGeometry( ptB - perp, midB, ptB + perp );
            aVector.push_back( arcB.get() );
            aOwned.push_back( std::move( arcB ) );
        }
    }
}
 
 
bool segmentIntersectsArc( const VECTOR2I& p1, const VECTOR2I& p2, const VECTOR2I& center,
                           double radius, EDA_ANGLE startAngle, EDA_ANGLE endAngle,
                           std::vector<VECTOR2I>* aIntersectionPoints = nullptr )
{
    SEG       segment( p1, p2 );
    VECTOR2I  startPoint( radius * cos( startAngle.AsRadians() ), radius * sin( startAngle.AsRadians() ) );
    SHAPE_ARC arc( center, startPoint + center, endAngle - startAngle );
 
    VECTOR2I arcStart = arc.GetP0();
    VECTOR2I arcEnd = arc.GetP1();
 
    INTERSECTABLE_GEOM geom1 = segment;
    INTERSECTABLE_GEOM geom2 = arc;
 
    std::vector<VECTOR2I> rawPoints;
    INTERSECTION_VISITOR  visitor( geom2, rawPoints );
    std::visit( visitor, geom1 );
 
    // Filter out intersections where a segment endpoint coincides with an
    // arc endpoint, matching the endpoint exclusion in segments_intersect.
    std::vector<VECTOR2I> filtered;
 
    // arcStart and arcEnd are reconstructed from the arc angles via cos/sin and
    // truncated to integer, so they land a couple of IU away from the stored
    // corner coordinates of an adjoining edge. The intersection solver rounds
    // similarly. An exact equality test therefore misses the shared corner where
    // a segment endpoint meets the arc endpoint and reports a phantom crossing,
    // which rejects legitimate creepage paths threading the gap between two
    // adjacent slot end caps. Compare with a small rounding-scale tolerance.
    const VECTOR2I::extended_type tolerance = 50;
    const VECTOR2I::extended_type toleranceSq = tolerance * tolerance;
 
    auto coincident = [&]( const VECTOR2I& a, const VECTOR2I& b )
    {
        return ( a - b ).SquaredEuclideanNorm() <= toleranceSq;
    };
 
    for( const VECTOR2I& ip : rawPoints )
    {
        bool atSharedEndpoint = ( coincident( ip, arcStart ) || coincident( ip, arcEnd ) )
                                && ( coincident( ip, p1 ) || coincident( ip, p2 ) );
 
        if( !atSharedEndpoint )
            filtered.push_back( ip );
    }
 
    if( aIntersectionPoints )
    {
        for( const VECTOR2I& ip : filtered )
            aIntersectionPoints->push_back( ip );
    }
 
    return !filtered.empty();
}
 
 
//Check if line segments 'p1q1' and 'p2q2' intersect, excluding endpoint overlap
 
bool segments_intersect( const VECTOR2I& p1, const VECTOR2I& q1, const VECTOR2I& p2, const VECTOR2I& q2,
                         std::vector<VECTOR2I>& aIntersectionPoints )
{
    if( p1 == p2 || p1 == q2 || q1 == p2 || q1 == q2 )
        return false;
 
    SEG segment1( p1, q1 );
    SEG segment2( p2, q2 );
 
    INTERSECTABLE_GEOM geom1 = segment1;
    INTERSECTABLE_GEOM geom2 = segment2;
 
    size_t startCount = aIntersectionPoints.size();
 
    INTERSECTION_VISITOR visitor( geom2, aIntersectionPoints );
    std::visit( visitor, geom1 );
 
    return aIntersectionPoints.size() > startCount;
}
 
 
bool compareShapes( const CREEP_SHAPE* a, const CREEP_SHAPE* b )
{
    if( !a )
        return true;
 
    if( !b )
        return false;
 
    if( a->GetType() != b->GetType() )
        return a->GetType() < b->GetType();
 
    if( a->GetType() == CREEP_SHAPE::TYPE::UNDEFINED )
        return true;
 
    if( a->GetPos() != b->GetPos() )
        return a->GetPos() < b->GetPos();
 
    if( a->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
        return a->GetRadius() < b->GetRadius();
 
    return false;
}
 
 
bool areEquivalent( const CREEP_SHAPE* a, const CREEP_SHAPE* b )
{
    if( !a && !b )
        return true;
 
    if( !a || !b )
        return false;
 
    if( a->GetType() != b->GetType() )
        return false;
 
    if( a->GetType() == CREEP_SHAPE::TYPE::POINT )
        return a->GetPos() == b->GetPos();
 
    if( a->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
        return a->GetPos() == b->GetPos() && ( a->GetRadius() == b->GetRadius() );
 
    return false;
}
 
 
std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                                    double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    double weight = ( this->GetPos() - aS2.GetPos() ).SquaredEuclideanNorm();
 
    if( weight > aMaxSquaredWeight )
        return result;
 
    PATH_CONNECTION pc;
    pc.a1 = this->GetPos();
    pc.a2 = aS2.GetPos();
    pc.weight = sqrt( weight );
 
    result.push_back( pc );
    return result;
}
 
 
std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                    double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    int                          radius = aS2.GetRadius();
    VECTOR2I                     pointPos = this->GetPos();
    VECTOR2I                     circleCenter = aS2.GetPos();
 
    if( radius <= 0 )
        return result;
 
    double pointToCenterDistanceSquared = ( pointPos - circleCenter ).SquaredEuclideanNorm();
    double weightSquared = pointToCenterDistanceSquared - (float) radius * (float) radius;
 
    if( weightSquared > aMaxSquaredWeight )
        return result;
 
    VECTOR2D direction1 = VECTOR2D( pointPos.x - circleCenter.x, pointPos.y - circleCenter.y );
    direction1 = direction1.Resize( 1 );
 
    VECTOR2D direction2 = direction1.Perpendicular();
 
    double radiusSquared = double( radius ) * double( radius );
 
    double distance = sqrt( pointToCenterDistanceSquared );
    double value1 = radiusSquared / distance;
    double value2 = sqrt( radiusSquared - value1 * value1 );
 
    VECTOR2D resultPoint;
 
    PATH_CONNECTION pc;
    pc.a1 = pointPos;
    pc.weight = sqrt( weightSquared );
 
    resultPoint = direction1 * value1 + direction2 * value2 + circleCenter;
    pc.a2.x = int( resultPoint.x );
    pc.a2.y = int( resultPoint.y );
    result.push_back( pc );
 
    resultPoint = direction1 * value1 - direction2 * value2 + circleCenter;
    pc.a2.x = int( resultPoint.x );
    pc.a2.y = int( resultPoint.y );
    result.push_back( pc );
 
    return result;
}
 
 
std::pair<bool, bool> BE_SHAPE_ARC::IsThereATangentPassingThroughPoint( const BE_SHAPE_POINT aPoint ) const
{
    std::pair<bool, bool> result;
    double                R = m_radius;
 
    VECTOR2I newPoint = aPoint.GetPos() - m_pos;
 
    if( newPoint.SquaredEuclideanNorm() <= R * R )
    {
        // If the point is inside the arc
        result.first = false;
        result.second = false;
        return result;
    }
 
    EDA_ANGLE testAngle = AngleBetweenStartAndEnd( aPoint.GetPos() );
 
    double startAngle = m_startAngle.AsRadians();
    double endAngle = m_endAngle.AsRadians();
    double pointAngle = testAngle.AsRadians();
 
    bool greaterThan180 = ( m_endAngle - m_startAngle ) > EDA_ANGLE( 180 );
    bool connectToEndPoint;
 
    connectToEndPoint = ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y >= R );
 
    if( greaterThan180 )
        connectToEndPoint &= ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y <= R );
 
    connectToEndPoint |= ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y <= R )
                         && ( pointAngle >= endAngle || pointAngle <= startAngle );
 
    result.first = !connectToEndPoint;
 
    connectToEndPoint = ( cos( endAngle ) * newPoint.x + sin( endAngle ) * newPoint.y >= R );
 
    if( greaterThan180 )
        connectToEndPoint &= ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y <= R );
 
    connectToEndPoint |= ( cos( startAngle ) * newPoint.x + sin( startAngle ) * newPoint.y <= R )
                         && ( pointAngle >= endAngle || pointAngle <= startAngle );
 
    result.second = !connectToEndPoint;
    return result;
}
 
 
std::vector<PATH_CONNECTION> BE_SHAPE_POINT::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                                    double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    VECTOR2I                     center = aS2.GetPos();
    double                       radius = aS2.GetRadius();
 
    // First path tries to connect to start point
    // Second path tries to connect to end point
    std::pair<bool, bool> behavesLikeCircle;
    behavesLikeCircle = aS2.IsThereATangentPassingThroughPoint( *this );
 
    if( behavesLikeCircle.first && behavesLikeCircle.second )
    {
        BE_SHAPE_CIRCLE csc( center, radius );
        return this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
    }
 
    if( behavesLikeCircle.first )
    {
        BE_SHAPE_CIRCLE              csc( center, radius );
        std::vector<PATH_CONNECTION> paths = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
 
        if( paths.size() > 1 ) // Point to circle creates either 0 or 2 connections
            result.push_back( paths[1] );
    }
    else
    {
        BE_SHAPE_POINT csp1( aS2.GetStartPoint() );
 
        for( const PATH_CONNECTION& pc : this->Paths( csp1, aMaxWeight, aMaxSquaredWeight ) )
            result.push_back( pc );
    }
 
    if( behavesLikeCircle.second )
    {
        BE_SHAPE_CIRCLE              csc( center, radius );
        std::vector<PATH_CONNECTION> paths = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
 
        if( paths.size() > 1 ) // Point to circle creates either 0 or 2 connections
            result.push_back( paths[0] );
    }
    else
    {
        BE_SHAPE_POINT csp1( aS2.GetEndPoint() );
 
        for( const PATH_CONNECTION& pc : this->Paths( csp1, aMaxWeight, aMaxSquaredWeight ) )
            result.push_back( pc );
    }
 
    return result;
}
 
std::vector<PATH_CONNECTION> BE_SHAPE_CIRCLE::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                                     double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    VECTOR2I                     circleCenter = this->GetPos();
    double                       circleRadius = this->GetRadius();
    VECTOR2I                     arcCenter = aS2.GetPos();
    double                       arcRadius = aS2.GetRadius();
    EDA_ANGLE                    arcStartAngle = aS2.GetStartAngle();
    EDA_ANGLE                    arcEndAngle = aS2.GetEndAngle();
 
    double centerDistance = ( circleCenter - arcCenter ).EuclideanNorm();
 
    if( centerDistance + arcRadius < circleRadius )
    {
        // The arc is inside the circle
        return result;
    }
 
    BE_SHAPE_POINT  csp1( aS2.GetStartPoint() );
    BE_SHAPE_POINT  csp2( aS2.GetEndPoint() );
    BE_SHAPE_CIRCLE csc( arcCenter, arcRadius );
 
    for( const PATH_CONNECTION& pc : this->Paths( csc, aMaxWeight, aMaxSquaredWeight ) )
    {
        EDA_ANGLE pointAngle = aS2.AngleBetweenStartAndEnd( pc.a2 - arcCenter );
 
        if( pointAngle <= aS2.GetEndAngle() )
            result.push_back( pc );
    }
 
    if( result.size() == 4 )
    {
        // It behaved as a circle
        return result;
    }
 
    for( const BE_SHAPE_POINT& csp : { csp1, csp2 } )
    {
        for( const PATH_CONNECTION& pc : this->Paths( csp, aMaxWeight, aMaxSquaredWeight ) )
        {
            if( !segmentIntersectsArc( pc.a1, pc.a2, arcCenter, arcRadius, arcStartAngle, arcEndAngle ) )
                result.push_back( pc );
        }
    }
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> BE_SHAPE_ARC::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                                  double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    VECTOR2I                     circleCenter = this->GetPos();
    double                       circleRadius = this->GetRadius();
    VECTOR2I                     arcCenter = aS2.GetPos();
    double                       arcRadius = aS2.GetRadius();
 
    double centerDistance = ( circleCenter - arcCenter ).EuclideanNorm();
 
    if( centerDistance + arcRadius < circleRadius )
    {
        // The arc is inside the circle
        return result;
    }
 
    BE_SHAPE_POINT  csp1( aS2.GetStartPoint() );
    BE_SHAPE_POINT  csp2( aS2.GetEndPoint() );
    BE_SHAPE_CIRCLE csc( arcCenter, arcRadius );
 
 
    for( const PATH_CONNECTION& pc : this->Paths( BE_SHAPE_CIRCLE( aS2.GetPos(), aS2.GetRadius() ),
                                                  aMaxWeight, aMaxSquaredWeight ) )
    {
        EDA_ANGLE pointAngle = aS2.AngleBetweenStartAndEnd( pc.a2 - arcCenter );
 
        if( pointAngle <= aS2.GetEndAngle() )
            result.push_back( pc );
    }
 
    for( const PATH_CONNECTION& pc : BE_SHAPE_CIRCLE( this->GetPos(), this->GetRadius() )
                                          .Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
    {
        EDA_ANGLE pointAngle = this->AngleBetweenStartAndEnd( pc.a2 - arcCenter );
 
        if( pointAngle <= this->GetEndAngle() )
            result.push_back( pc );
    }
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> BE_SHAPE_CIRCLE::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                     double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    VECTOR2I p1 = this->GetPos();
    VECTOR2I p2 = aS2.GetPos();
 
    VECTOR2D distSquared( double( ( p2 - p1 ).x ), double( ( p2 - p1 ).y ) );
    double   weightSquared = distSquared.SquaredEuclideanNorm();
 
    double R1 = this->GetRadius();
    double R2 = aS2.GetRadius();
 
    double Rdiff = abs( R1 - R2 );
    double Rsum = R1 + R2;
 
    // "Straight" paths
    double weightSquared1 = weightSquared - Rdiff * Rdiff;
    // "Crossed" paths
    double weightSquared2 = weightSquared - Rsum * Rsum;
 
    if( weightSquared1 <= aMaxSquaredWeight )
    {
        VECTOR2D direction1 = VECTOR2D( p2.x - p1.x, p2.y - p1.y );
        direction1 = direction1.Resize( 1 );
        VECTOR2D direction2 = direction1.Perpendicular();
 
        double D = sqrt( weightSquared );
        double ratio1 = ( R1 - R2 ) / D;
        double ratio2 = sqrt( 1 - ratio1 * ratio1 );
 
 
        PATH_CONNECTION pc;
        pc.weight = sqrt( weightSquared1 );
 
        pc.a1 = p1 + direction1 * R1 * ratio1 + direction2 * R1 * ratio2;
        pc.a2 = p2 + direction1 * R2 * ratio1 + direction2 * R2 * ratio2;
 
        result.push_back( pc );
 
        pc.a1 = p1 + direction1 * R1 * ratio1 - direction2 * R1 * ratio2;
        pc.a2 = p2 + direction1 * R2 * ratio1 - direction2 * R2 * ratio2;
 
        result.push_back( pc );
    }
    if( weightSquared2 <= aMaxSquaredWeight )
    {
        VECTOR2D direction1 = VECTOR2D( p2.x - p1.x, p2.y - p1.y );
        direction1 = direction1.Resize( 1 );
        VECTOR2D direction2 = direction1.Perpendicular();
 
        double D = sqrt( weightSquared );
        double ratio1 = ( R1 + R2 ) / D;
        double ratio2 = sqrt( 1 - ratio1 * ratio1 );
 
 
        PATH_CONNECTION pc;
        pc.weight = sqrt( weightSquared2 );
 
        pc.a1 = p1 + direction1 * R1 * ratio1 + direction2 * R1 * ratio2;
        pc.a2 = p2 - direction1 * R2 * ratio1 - direction2 * R2 * ratio2;
 
        result.push_back( pc );
 
        pc.a1 = p1 + direction1 * R1 * ratio1 - direction2 * R1 * ratio2;
        pc.a2 = p2 - direction1 * R2 * ratio1 + direction2 * R2 * ratio2;
 
        result.push_back( pc );
    }
 
    return result;
}
 
 
void CREEPAGE_GRAPH::TransformCreepShapesToNodes( std::vector<CREEP_SHAPE*>& aShapes )
{
    for( CREEP_SHAPE* p1 : aShapes )
    {
        if( !p1 )
            continue;
 
        switch( p1->GetType() )
        {
        case CREEP_SHAPE::TYPE::POINT:  AddNode( GRAPH_NODE::TYPE::POINT, p1, p1->GetPos() );  break;
        case CREEP_SHAPE::TYPE::CIRCLE: AddNode( GRAPH_NODE::TYPE::CIRCLE, p1, p1->GetPos() ); break;
        case CREEP_SHAPE::TYPE::ARC:    AddNode( GRAPH_NODE::TYPE::ARC, p1, p1->GetPos() );    break;
        default:                                                                               break;
        }
    }
}
 
void CREEPAGE_GRAPH::RemoveDuplicatedShapes()
{
    // Sort the vector
    sort( m_shapeCollection.begin(), m_shapeCollection.end(), compareShapes );
    std::vector<CREEP_SHAPE*> newVector;
 
    size_t i = 0;
 
    for( i = 0; i < m_shapeCollection.size() - 1; i++ )
    {
        if( m_shapeCollection[i] == nullptr )
            continue;
 
        if( areEquivalent( m_shapeCollection[i], m_shapeCollection[i + 1] ) )
        {
            delete m_shapeCollection[i];
            m_shapeCollection[i] = nullptr;
        }
        else
        {
            newVector.push_back( m_shapeCollection[i] );
        }
    }
 
    if( m_shapeCollection[i] )
        newVector.push_back( m_shapeCollection[i] );
 
    std::swap( m_shapeCollection, newVector );
}
 
void CREEPAGE_GRAPH::TransformEdgeToCreepShapes()
{
    for( BOARD_ITEM* drawing : m_boardEdge )
    {
        PCB_SHAPE* d = dynamic_cast<PCB_SHAPE*>( drawing );
 
        if( !d )
            continue;
 
        switch( d->GetShape() )
        {
        case SHAPE_T::SEGMENT:
        {
            BE_SHAPE_POINT* a = new BE_SHAPE_POINT( d->GetStart() );
            a->SetParent( d );
            m_shapeCollection.push_back( a );
            a = new BE_SHAPE_POINT( d->GetEnd() );
            a->SetParent( d );
            m_shapeCollection.push_back( a );
            break;
        }
 
        case SHAPE_T::RECTANGLE:
        {
            int r = d->GetCornerRadius();
 
            if( r > 0 )
            {
                // Rounded rectangle: decompose into arcs.
                // Normalize coordinates so x1 < x2 and y1 < y2.
                int x1 = std::min( d->GetStart().x, d->GetEnd().x );
                int y1 = std::min( d->GetStart().y, d->GetEnd().y );
                int x2 = std::max( d->GetStart().x, d->GetEnd().x );
                int y2 = std::max( d->GetStart().y, d->GetEnd().y );
 
                int w = x2 - x1;
                int h = y2 - y1;
 
                auto addArc = [&]( const VECTOR2I& center, const VECTOR2I& startPt,
                                   const VECTOR2I& endPt )
                {
                    EDA_ANGLE startAngle( VECTOR2D( startPt - center ) );
                    EDA_ANGLE endAngle( VECTOR2D( endPt - center ) );
 
                    while( endAngle < startAngle )
                        endAngle += ANGLE_360;
 
                    BE_SHAPE_ARC* arc = new BE_SHAPE_ARC( center, r, startAngle, endAngle,
                                                         startPt, endPt );
                    arc->SetParent( d );
                    m_shapeCollection.push_back( arc );
                };
 
                if( h == 2 * r )
                {
                    // Horizontal stadium: left and right semicircles. The endpoint order
                    // makes addArc sweep the outer half of each circle so the caps bulge
                    // away from the slot.
                    addArc( { x1 + r, y1 + r }, { x1 + r, y2 }, { x1 + r, y1 } );
                    addArc( { x2 - r, y1 + r }, { x2 - r, y1 }, { x2 - r, y2 } );
                }
                else if( w == 2 * r )
                {
                    // Vertical stadium: top and bottom semicircles
                    addArc( { x1 + r, y1 + r }, { x1, y1 + r }, { x2, y1 + r } );
                    addArc( { x1 + r, y2 - r }, { x2, y2 - r }, { x1, y2 - r } );
                }
                else
                {
                    // General rounded rectangle: four quarter-circle arcs
                    addArc( { x1 + r, y1 + r }, { x1,     y1 + r }, { x1 + r, y1     } );
                    addArc( { x2 - r, y1 + r }, { x2 - r, y1     }, { x2,     y1 + r } );
                    addArc( { x2 - r, y2 - r }, { x2,     y2 - r }, { x2 - r, y2     } );
                    addArc( { x1 + r, y2 - r }, { x1 + r, y2     }, { x1,     y2 - r } );
                }
            }
            else
            {
                BE_SHAPE_POINT* a = new BE_SHAPE_POINT( d->GetStart() );
                a->SetParent( d );
                m_shapeCollection.push_back( a );
                a = new BE_SHAPE_POINT( d->GetEnd() );
                a->SetParent( d );
                m_shapeCollection.push_back( a );
                a = new BE_SHAPE_POINT( VECTOR2I( d->GetEnd().x, d->GetStart().y ) );
                a->SetParent( d );
                m_shapeCollection.push_back( a );
                a = new BE_SHAPE_POINT( VECTOR2I( d->GetStart().x, d->GetEnd().y ) );
                a->SetParent( d );
                m_shapeCollection.push_back( a );
            }
 
            break;
        }
 
        case SHAPE_T::POLY:
            for( const VECTOR2I& p : d->GetPolyPoints() )
            {
                BE_SHAPE_POINT* a = new BE_SHAPE_POINT( p );
                a->SetParent( d );
                m_shapeCollection.push_back( a );
            }
 
            break;
 
        case SHAPE_T::CIRCLE:
        {
            BE_SHAPE_CIRCLE* a = new BE_SHAPE_CIRCLE( d->GetCenter(), d->GetRadius() );
            a->SetParent( d );
            m_shapeCollection.push_back( a );
            break;
        }
 
        case SHAPE_T::ARC:
        {
            // If the arc is not locally convex, only use the endpoints
            double   tolerance = 10;
            VECTOR2D center( double( d->GetCenter().x ), double( d->GetCenter().y ) );
            VECTOR2D mid( double( d->GetArcMid().x ), double( d->GetArcMid().y ) );
            VECTOR2D dir( mid - center );
            dir = dir / d->GetRadius() * ( d->GetRadius() - tolerance );
 
            EDA_ANGLE alpha, beta;
            d->CalcArcAngles( alpha, beta );
            BE_SHAPE_ARC* a = new BE_SHAPE_ARC( d->GetCenter(), d->GetRadius(), alpha, beta,
                                                d->GetStart(), d->GetEnd() );
            a->SetParent( d );
 
            m_shapeCollection.push_back( a );
            break;
        }
 
        default:
            break;
        }
    }
}
 
 
void GRAPH_CONNECTION::GetShapes( std::vector<PCB_SHAPE>& aShapes )
{
    if( !m_path.m_show )
        return;
 
    if( !n1 || !n2 )
        return;
 
    if( n1->m_type == GRAPH_NODE::TYPE::VIRTUAL || n2->m_type == GRAPH_NODE::TYPE::VIRTUAL )
        return;
 
    if( !m_forceStraightLine && n1->m_parent
            && n1->m_parent == n2->m_parent
            && n1->m_parent->GetType() == CREEP_SHAPE::TYPE::CIRCLE )
    {
        VECTOR2I  center = n1->m_parent->GetPos();
        VECTOR2I  R1 = n1->m_pos - center;
        VECTOR2I  R2 = n2->m_pos - center;
        PCB_SHAPE s( nullptr, SHAPE_T::ARC );
 
        if( R1.Cross( R2 ) > 0 )
        {
            s.SetStart( n1->m_pos );
            s.SetEnd( n2->m_pos );
        }
        else
        {
            s.SetStart( n2->m_pos );
            s.SetEnd( n1->m_pos );
        }
 
        s.SetCenter( center );
        aShapes.push_back( s );
        return;
    }
 
    if( !m_forceStraightLine && n1->m_parent
            && n1->m_parent == n2->m_parent
            && n1->m_parent->GetType() == CREEP_SHAPE::TYPE::ARC )
    {
        if( BE_SHAPE_ARC* arc = dynamic_cast<BE_SHAPE_ARC*>( n1->m_parent ) )
        {
            VECTOR2I  center = arc->GetPos();
            VECTOR2I  R1 = n1->m_pos - center;
            VECTOR2I  R2 = n2->m_pos - center;
            PCB_SHAPE s( nullptr, SHAPE_T::ARC );
 
            if( R1.Cross( R2 ) > 0 )
            {
                s.SetStart( n1->m_pos );
                s.SetEnd( n2->m_pos );
            }
            else
            {
                s.SetStart( n2->m_pos );
                s.SetEnd( n1->m_pos );
            }
 
            s.SetCenter( center );
 
            //Check that we are on the correct side of the arc.
            VECTOR2I  mid = s.GetArcMid();
            EDA_ANGLE midAngle = arc->AngleBetweenStartAndEnd( mid );
 
            if( midAngle > arc->GetEndAngle() )
            {
                VECTOR2I tmp;
                tmp = s.GetStart();
                s.SetStart( s.GetEnd() );
                s.SetEnd( tmp );
                s.SetCenter( center );
            }
 
            aShapes.push_back( s );
            return;
        }
    }
 
    PCB_SHAPE s( nullptr, SHAPE_T::SEGMENT );
    s.SetStart( m_path.a1 );
    s.SetEnd( m_path.a2 );
    aShapes.push_back( s );
}
 
 
void CREEP_SHAPE::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>&,
                                   CREEPAGE_GRAPH&              aG ) const
{
}
 
 
void BE_SHAPE_POINT::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>&,
                                      CREEPAGE_GRAPH&              aG ) const
{
}
 
 
void BE_SHAPE_CIRCLE::ShortenChildDueToGV( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>& a2,
                                           CREEPAGE_GRAPH& aG, double aNormalWeight ) const
{
    EDA_ANGLE angle1 = EDA_ANGLE( a1->m_pos - m_pos );
    EDA_ANGLE angle2 = EDA_ANGLE( a2->m_pos - m_pos );
 
    while( angle1 < ANGLE_0 )
        angle1 += ANGLE_360;
    while( angle2 < ANGLE_0 )
        angle2 += ANGLE_360;
    while( angle1 > ANGLE_360 )
        angle1 -= ANGLE_360;
    while( angle2 > ANGLE_360 )
        angle2 -= ANGLE_360;
 
    EDA_ANGLE maxAngle = angle1 > angle2 ? angle1 : angle2;
    EDA_ANGLE skipAngle =
            EDA_ANGLE( asin( float( aG.m_minGrooveWidth ) / ( 2 * m_radius ) ), RADIANS_T );
    skipAngle += skipAngle; // Cannot multiply EDA_ANGLE by scalar, but this really is angle *2
    EDA_ANGLE pointAngle = maxAngle - skipAngle;
 
    VECTOR2I skipPoint = m_pos;
    skipPoint.x += m_radius * cos( pointAngle.AsRadians() );
    skipPoint.y += m_radius * sin( pointAngle.AsRadians() );
 
    std::shared_ptr<GRAPH_NODE> gnt = aG.AddNode( GRAPH_NODE::POINT, a1->m_parent, skipPoint );
 
    PATH_CONNECTION pc;
 
    pc.a1 = maxAngle == angle2 ? a1->m_pos : a2->m_pos;
    pc.a2 = skipPoint;
    pc.weight = aNormalWeight - aG.m_minGrooveWidth;
    aG.AddConnection( maxAngle == angle2 ? a1 : a2, gnt, pc );
 
    pc.a1 = skipPoint;
    pc.a2 = maxAngle == angle2 ? a2->m_pos : a1->m_pos;
    pc.weight = aG.m_minGrooveWidth;
 
    std::shared_ptr<GRAPH_CONNECTION> gc = aG.AddConnection( gnt, maxAngle == angle2 ? a2 : a1, pc );
 
    if( gc )
        gc->m_forceStraightLine = true;
}
 
 
void BE_SHAPE_CIRCLE::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>& a2,
                                       CREEPAGE_GRAPH& aG ) const
{
    if( !a1 || !a2 )
        return;
 
    if( m_radius == 0 )
        return;
 
    VECTOR2D distI( a1->m_pos - a2->m_pos );
    VECTOR2D distD( double( distI.x ), double( distI.y ) );
 
    double weight = m_radius * 2 * asin( distD.EuclideanNorm() / ( 2.0 * m_radius ) );
 
    if( weight > aG.GetTarget() )
        return;
 
    if( aG.m_minGrooveWidth <= 0 )
    {
        PATH_CONNECTION pc;
        pc.a1 = a1->m_pos;
        pc.a2 = a2->m_pos;
        pc.weight = std::max( weight, 0.0 );
 
        aG.AddConnection( a1, a2, pc );
        return;
    }
 
    if( weight > aG.m_minGrooveWidth )
        ShortenChildDueToGV( a1, a2, aG, weight );
    // Else well.. this paths will be "shorted" by another one
}
 
 
void BE_SHAPE_ARC::ConnectChildren( std::shared_ptr<GRAPH_NODE>& a1, std::shared_ptr<GRAPH_NODE>& a2,
                                    CREEPAGE_GRAPH& aG ) const
{
    if( !a1 || !a2 )
        return;
 
    EDA_ANGLE angle1 = AngleBetweenStartAndEnd( a1->m_pos );
    EDA_ANGLE angle2 = AngleBetweenStartAndEnd( a2->m_pos );
 
    double weight = abs( m_radius * ( angle2 - angle1 ).AsRadians() );
 
    if( aG.m_minGrooveWidth <= 0 )
    {
        if( ( weight > aG.GetTarget() ) )
            return;
 
        PATH_CONNECTION pc;
        pc.a1 = a1->m_pos;
        pc.a2 = a2->m_pos;
        pc.weight = weight;
 
        aG.AddConnection( a1, a2, pc );
        return;
    }
 
    if( weight > aG.m_minGrooveWidth )
        ShortenChildDueToGV( a1, a2, aG, weight );
}
 
 
void CREEPAGE_GRAPH::SetTarget( double aTarget )
{
    m_creepageTarget = aTarget;
    m_creepageTargetSquared = aTarget * aTarget;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                                      double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    VECTOR2I                     start = this->GetStart();
    VECTOR2I                     end = this->GetEnd();
    double                       halfWidth = this->GetWidth() / 2;
    EDA_ANGLE                    trackAngle( end - start );
    VECTOR2I                     pointPos = aS2.GetPos();
 
    double length = ( start - end ).EuclideanNorm();
    double projectedPos = cos( trackAngle.AsRadians() ) * ( pointPos.x - start.x )
                          + sin( trackAngle.AsRadians() ) * ( pointPos.y - start.y );
 
    VECTOR2I newPoint;
 
    if( projectedPos <= 0 )
    {
        newPoint = start + ( pointPos - start ).Resize( halfWidth );
    }
    else if( projectedPos >= length )
    {
        newPoint = end + ( pointPos - end ).Resize( halfWidth );
    }
    else
    {
        double posOnSegment = ( start - pointPos ).SquaredEuclideanNorm()
                              - ( end - pointPos ).SquaredEuclideanNorm();
        posOnSegment = posOnSegment / ( 2 * length ) + length / 2;
 
        newPoint = start + ( end - start ).Resize( posOnSegment );
        newPoint += ( pointPos - newPoint ).Resize( halfWidth );
    }
 
    double weightSquared = ( pointPos - newPoint ).SquaredEuclideanNorm();
 
    if( weightSquared > aMaxSquaredWeight )
        return result;
 
    PATH_CONNECTION pc;
    pc.a1 = newPoint;
    pc.a2 = pointPos;
    pc.weight = sqrt( weightSquared );
 
    result.push_back( pc );
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                      double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    VECTOR2I                     start = this->GetStart();
    VECTOR2I                     end = this->GetEnd();
    double                       halfWidth = this->GetWidth() / 2;
 
    double    circleRadius = aS2.GetRadius();
    VECTOR2I  circleCenter = aS2.GetPos();
    double    length = ( start - end ).EuclideanNorm();
    EDA_ANGLE trackAngle( end - start );
 
    double   weightSquared = std::numeric_limits<double>::infinity();
    VECTOR2I PointOnTrack, PointOnCircle;
 
    // There are two possible paths
    // First the one on the side of the start of the track.
    double projectedPos1 = cos( trackAngle.AsRadians() ) * ( circleCenter.x - start.x )
                           + sin( trackAngle.AsRadians() ) * ( circleCenter.y - start.y );
    double projectedPos2 = projectedPos1 + circleRadius;
    projectedPos1 = projectedPos1 - circleRadius;
 
    double trackSide = ( end - start ).Cross( circleCenter - start ) > 0 ? 1 : -1;
 
    if( ( projectedPos1 < 0 && projectedPos2 < 0 ) )
    {
        CU_SHAPE_CIRCLE csc( start, halfWidth );
        for( PATH_CONNECTION pc : csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
        {
            result.push_back( pc );
        }
    }
    else if( ( projectedPos1 > length && projectedPos2 > length ) )
    {
        CU_SHAPE_CIRCLE csc( end, halfWidth );
 
        for( const PATH_CONNECTION& pc : csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
            result.push_back( pc );
    }
 
    else if( ( projectedPos1 >= 0 ) && ( projectedPos1 <= length ) && ( projectedPos2 >= 0 )
             && ( projectedPos2 <= length ) )
    {
        // Both point connects to the segment part of the track
        PointOnTrack = start;
        PointOnTrack += ( end - start ).Resize( projectedPos1 );
        PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
        PointOnCircle = circleCenter - ( end - start ).Resize( circleRadius );
        weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
 
        if( weightSquared < aMaxSquaredWeight )
        {
            PATH_CONNECTION pc;
            pc.a1 = PointOnTrack;
            pc.a2 = PointOnCircle;
            pc.weight = sqrt( weightSquared );
 
            result.push_back( pc );
 
            PointOnTrack = start;
            PointOnTrack += ( end - start ).Resize( projectedPos2 );
            PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
            PointOnCircle = circleCenter + ( end - start ).Resize( circleRadius );
 
 
            pc.a1 = PointOnTrack;
            pc.a2 = PointOnCircle;
 
            result.push_back( pc );
        }
    }
    else if( ( ( projectedPos1 >= 0 ) && ( projectedPos1 <= length ) )
             && ( ( projectedPos2 > length ) || projectedPos2 < 0 ) )
    {
        CU_SHAPE_CIRCLE              csc( end, halfWidth );
        std::vector<PATH_CONNECTION> pcs = csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
 
        if( pcs.size() < 2 )
            return result;
 
        result.push_back( pcs.at( trackSide == 1 ? 1 : 0 ) );
 
 
        PointOnTrack = start;
        PointOnTrack += ( end - start ).Resize( projectedPos1 );
        PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
        PointOnCircle = circleCenter - ( end - start ).Resize( circleRadius );
        weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
 
        if( weightSquared < aMaxSquaredWeight )
        {
            PATH_CONNECTION pc;
            pc.a1 = PointOnTrack;
            pc.a2 = PointOnCircle;
            pc.weight = sqrt( weightSquared );
 
            result.push_back( pc );
        }
    }
    else if( ( ( projectedPos2 >= 0 ) && ( projectedPos2 <= length ) )
             && ( ( projectedPos1 > length ) || projectedPos1 < 0 ) )
    {
        CU_SHAPE_CIRCLE              csc( start, halfWidth );
        std::vector<PATH_CONNECTION> pcs = csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
 
        if( pcs.size() < 2 )
            return result;
 
        result.push_back( pcs.at( trackSide == 1 ? 0 : 1 ) );
 
        PointOnTrack = start;
        PointOnTrack += ( end - start ).Resize( projectedPos2 );
        PointOnTrack += ( end - start ).Perpendicular().Resize( halfWidth ) * trackSide;
        PointOnCircle = circleCenter + ( end - start ).Resize( circleRadius );
        weightSquared = ( PointOnCircle - PointOnTrack ).SquaredEuclideanNorm();
 
        if( weightSquared < aMaxSquaredWeight )
        {
            PATH_CONNECTION pc;
            pc.a1 = PointOnTrack;
            pc.a2 = PointOnCircle;
            pc.weight = sqrt( weightSquared );
 
            result.push_back( pc );
        }
    }
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                                      double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    BE_SHAPE_CIRCLE bsc( aS2.GetPos(), aS2.GetRadius() );
 
    for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
    {
        EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
 
        if( testAngle < aS2.GetEndAngle() )
            result.push_back( pc );
    }
 
    if( result.size() < 2 )
    {
        BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
        BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
 
        VECTOR2I  beArcPos = aS2.GetPos();
        int       beArcRadius = aS2.GetRadius();
        EDA_ANGLE beArcStartAngle = aS2.GetStartAngle();
        EDA_ANGLE beArcEndAngle = aS2.GetEndAngle();
 
        for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
        {
            if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
                result.push_back( pc );
        }
 
        for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
        {
            if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
                result.push_back( pc );
        }
    }
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                                     double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    VECTOR2I                     beArcPos = aS2.GetPos();
    int                          beArcRadius = aS2.GetRadius();
    EDA_ANGLE                    beArcStartAngle = aS2.GetStartAngle();
    EDA_ANGLE                    beArcEndAngle = aS2.GetEndAngle();
 
    BE_SHAPE_CIRCLE bsc( beArcPos, beArcRadius );
 
    for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
    {
        EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
 
        if( testAngle < aS2.GetEndAngle() )
            result.push_back( pc );
    }
 
    if( result.size() < 2 )
    {
        BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
        BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
 
        for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
        {
            if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
                result.push_back( pc );
        }
 
        for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
        {
            if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
                result.push_back( pc );
        }
 
    }
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                  double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    CU_SHAPE_CIRCLE csc( this->GetPos(), this->GetRadius() + this->GetWidth() / 2 );
 
    for( const PATH_CONNECTION& pc : this->Paths( csc, aMaxWeight, aMaxSquaredWeight ) )
    {
        EDA_ANGLE testAngle = this->AngleBetweenStartAndEnd( pc.a2 );
 
        if( testAngle < this->GetEndAngle() )
            result.push_back( pc );
    }
 
    if( result.size() < 2 )
    {
        CU_SHAPE_CIRCLE csc1( this->GetStartPoint(), this->GetWidth() / 2 );
        CU_SHAPE_CIRCLE csc2( this->GetEndPoint(), this->GetWidth() / 2 );
 
        for( const PATH_CONNECTION& pc : this->Paths( csc1, aMaxWeight, aMaxSquaredWeight ) )
            result.push_back( pc );
 
        for( const PATH_CONNECTION& pc : this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ) )
            result.push_back( pc );
    }
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                                  double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    VECTOR2I                     beArcPos = aS2.GetPos();
    int                          beArcRadius = aS2.GetRadius();
    EDA_ANGLE                    beArcStartAngle = aS2.GetStartAngle();
    EDA_ANGLE                    beArcEndAngle = aS2.GetEndAngle();
 
    BE_SHAPE_CIRCLE bsc( aS2.GetPos(), aS2.GetRadius() );
 
    for( const PATH_CONNECTION& pc : this->Paths( bsc, aMaxWeight, aMaxSquaredWeight ) )
    {
        EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pc.a2 );
 
        if( testAngle < aS2.GetEndAngle() )
            result.push_back( pc );
    }
 
    if( result.size() < 2 )
    {
        BE_SHAPE_POINT bsp1( aS2.GetStartPoint() );
        BE_SHAPE_POINT bsp2( aS2.GetEndPoint() );
 
        for( const PATH_CONNECTION& pc : this->Paths( bsp1, aMaxWeight, aMaxSquaredWeight ) )
        {
            if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
                result.push_back( pc );
        }
 
        for( const PATH_CONNECTION& pc : this->Paths( bsp2, aMaxWeight, aMaxSquaredWeight ) )
        {
            if( !segmentIntersectsArc( pc.a1, pc.a2, beArcPos, beArcRadius, beArcStartAngle, beArcEndAngle ) )
                result.push_back( pc );
        }
    }
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                                     double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    double   R = this->GetRadius();
    VECTOR2I center = this->GetPos();
    VECTOR2I point = aS2.GetPos();
    double   weight = ( center - point ).EuclideanNorm() - R;
 
    if( weight > aMaxWeight )
        return result;
 
    PATH_CONNECTION pc;
    pc.weight = std::max( weight, 0.0 );
    pc.a2 = point;
    pc.a1 = center + ( point - center ).Resize( R );
 
    result.push_back( pc );
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                     double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    double   R1 = this->GetRadius();
    double   R2 = aS2.GetRadius();
    VECTOR2I C1 = this->GetPos();
    VECTOR2I C2 = aS2.GetPos();
 
    if( ( C1 - C2 ).SquaredEuclideanNorm() < ( R1 - R2 ) * ( R1 - R2 ) )
    {
        // One of the circles is inside the other
        return result;
    }
 
    double weight = ( C1 - C2 ).EuclideanNorm() - R1 - R2;
 
    if( weight > aMaxWeight || weight < 0 )
        return result;
 
    PATH_CONNECTION pc;
    pc.weight = std::max( weight, 0.0 );
    pc.a1 = ( C2 - C1 ).Resize( R1 ) + C1;
    pc.a2 = ( C1 - C2 ).Resize( R2 ) + C2;
    result.push_back( pc );
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                      double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    VECTOR2I s_start = this->GetStart();
    VECTOR2I s_end = this->GetEnd();
    double   halfWidth = this->GetWidth() / 2;
 
    EDA_ANGLE trackAngle( s_end - s_start );
    VECTOR2I  pointPos = aS2.GetPos();
 
    double length = ( s_start - s_end ).EuclideanNorm();
    double projectedPos = cos( trackAngle.AsRadians() ) * ( pointPos.x - s_start.x )
                          + sin( trackAngle.AsRadians() ) * ( pointPos.y - s_start.y );
 
    if( ( projectedPos <= 0 ) || ( s_start == s_end ) )
    {
        CU_SHAPE_CIRCLE csc( s_start, halfWidth );
        return csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
    }
 
    if( projectedPos >= length )
    {
        CU_SHAPE_CIRCLE csc( s_end, halfWidth );
        return csc.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
    }
 
    double radius = aS2.GetRadius();
    double trackSide = ( s_end - s_start ).Cross( pointPos - s_start ) > 0 ? 1 : -1;
 
    PATH_CONNECTION pc;
    pc.a1 = s_start + ( s_end - s_start ).Resize( projectedPos )
            + ( s_end - s_start ).Perpendicular().Resize( halfWidth ) * trackSide;
    pc.a2 = ( pc.a1 - pointPos ).Resize( radius ) + pointPos;
    pc.weight = ( pc.a2 - pc.a1 ).SquaredEuclideanNorm();
 
    if( pc.weight <= aMaxSquaredWeight )
    {
        pc.weight = sqrt( pc.weight );
        result.push_back( pc );
    }
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                                     double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    VECTOR2I circlePos = this->GetPos();
    VECTOR2I arcPos = aS2.GetPos();
 
    double circleRadius = this->GetRadius();
    double arcRadius = aS2.GetRadius();
 
    VECTOR2I startPoint = aS2.GetStartPoint();
    VECTOR2I endPoint = aS2.GetEndPoint();
 
    CU_SHAPE_CIRCLE csc( arcPos, arcRadius + aS2.GetWidth() / 2 );
 
    if( ( circlePos - arcPos ).EuclideanNorm() > arcRadius + circleRadius )
    {
        const std::vector<PATH_CONNECTION>& pcs = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
 
        if( pcs.size() == 1 )
        {
            EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( pcs[0].a2 );
 
            if( testAngle < aS2.GetEndAngle() )
            {
                result.push_back( pcs[0] );
                return result;
            }
        }
    }
 
    CU_SHAPE_CIRCLE csc1( startPoint, aS2.GetWidth() / 2 );
    CU_SHAPE_CIRCLE csc2( endPoint, aS2.GetWidth() / 2 );
 
    PATH_CONNECTION* bestPath = nullptr;
 
 
    std::vector<PATH_CONNECTION> pcs1 = this->Paths( csc1, aMaxWeight, aMaxSquaredWeight );
    std::vector<PATH_CONNECTION> pcs2 = this->Paths( csc2, aMaxWeight, aMaxSquaredWeight );
 
    for( PATH_CONNECTION& pc : pcs1 )
    {
        if( !bestPath || ( ( bestPath->weight > pc.weight ) && ( pc.weight > 0 ) ) )
            bestPath = &pc;
    }
 
    for( PATH_CONNECTION& pc : pcs2 )
    {
        if( !bestPath || ( ( bestPath->weight > pc.weight ) && ( pc.weight > 0 ) ) )
            bestPath = &pc;
    }
 
    // If the circle center is insde the arc ring
 
    PATH_CONNECTION pc3;
 
    if( ( circlePos - arcPos ).SquaredEuclideanNorm() < arcRadius * arcRadius )
    {
        if( circlePos != arcPos ) // The best path is already found otherwise
        {
            EDA_ANGLE testAngle = aS2.AngleBetweenStartAndEnd( circlePos );
 
            if( testAngle < aS2.GetEndAngle() )
            {
                pc3.weight = std::max( arcRadius - ( circlePos - arcPos ).EuclideanNorm() - circleRadius, 0.0 );
                pc3.a1 = circlePos + ( circlePos - arcPos ).Resize( circleRadius );
                pc3.a2 = arcPos + ( circlePos - arcPos ).Resize( arcRadius - aS2.GetWidth() / 2 );
 
                if( !bestPath || ( ( bestPath->weight > pc3.weight ) && ( pc3.weight > 0 ) ) )
                    bestPath = &pc3;
            }
        }
    }
 
    if( bestPath && bestPath->weight > 0 )
    {
        result.push_back( *bestPath );
    }
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                                      double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    VECTOR2I s_start = this->GetStart();
    VECTOR2I s_end = this->GetEnd();
    double   halfWidth1 = this->GetWidth() / 2;
 
    VECTOR2I arcPos = aS2.GetPos();
    double   arcRadius = aS2.GetRadius();
    double   halfWidth2 = aS2.GetWidth() / 2;
 
 
    CU_SHAPE_CIRCLE csc( arcPos, arcRadius + halfWidth2 );
 
    std::vector<PATH_CONNECTION> pcs;
    pcs = this->Paths( csc, aMaxWeight, aMaxSquaredWeight );
 
    if( pcs.size() < 1 )
        return result;
 
    VECTOR2I  circlePoint;
    EDA_ANGLE testAngle;
 
    if( pcs.size() > 0 )
    {
        circlePoint = pcs[0].a1;
        testAngle = ( aS2.AngleBetweenStartAndEnd( pcs[0].a1 ) );
    }
 
    if( testAngle < aS2.GetEndAngle() && pcs.size() > 0 )
    {
        result.push_back( pcs[0] );
        return result;
    }
 
    CU_SHAPE_CIRCLE  csc1( aS2.GetStartPoint(), halfWidth2 );
    CU_SHAPE_CIRCLE  csc2( aS2.GetEndPoint(), halfWidth2 );
    PATH_CONNECTION* bestPath = nullptr;
 
    for( PATH_CONNECTION& pc : this->Paths( csc1, aMaxWeight, aMaxSquaredWeight ) )
    {
        if( !bestPath || ( bestPath->weight > pc.weight ) )
            bestPath = &pc;
    }
 
    for( PATH_CONNECTION& pc : this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ) )
    {
        if( !bestPath || ( bestPath->weight > pc.weight ) )
            bestPath = &pc;
    }
 
    CU_SHAPE_CIRCLE csc3( s_start, halfWidth1 );
    CU_SHAPE_CIRCLE csc4( s_end, halfWidth1 );
 
    for( PATH_CONNECTION& pc : csc3.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
    {
        if( !bestPath || ( bestPath->weight > pc.weight ) )
            bestPath = &pc;
    }
 
 
    for( PATH_CONNECTION& pc : csc4.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) )
    {
        if( !bestPath || ( bestPath->weight > pc.weight ) )
            bestPath = &pc;
    }
 
    if( bestPath )
        result.push_back( *bestPath );
 
    return result;
}
 
// Function to compute the projection of point P onto the line segment AB
VECTOR2I closestPointOnSegment( const VECTOR2I& A, const VECTOR2I& B, const VECTOR2I& P )
{
    if( A == B )
        return A;
    if( A == P )
        return A;
 
    VECTOR2I AB = B - A;
    VECTOR2I AP = P - A;
 
    double t = float( AB.Dot( AP ) ) / float( AB.SquaredEuclideanNorm() );
 
    // Clamp t to the range [0, 1] to restrict the projection to the segment
    t = std::max( 0.0, std::min( 1.0, t ) );
 
    return A + ( AB * t );
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_SEGMENT::Paths( const CU_SHAPE_SEGMENT& aS2,
                                                      double                  aMaxWeight,
                                                      double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    VECTOR2I A( this->GetStart() );
    VECTOR2I B( this->GetEnd() );
    double   halfWidth1 = this->GetWidth() / 2;
 
 
    VECTOR2I C( aS2.GetStart() );
    VECTOR2I D( aS2.GetEnd() );
    double   halfWidth2 = aS2.GetWidth() / 2;
 
    VECTOR2I P1 = closestPointOnSegment( A, B, C );
    VECTOR2I P2 = closestPointOnSegment( A, B, D );
    VECTOR2I P3 = closestPointOnSegment( C, D, A );
    VECTOR2I P4 = closestPointOnSegment( C, D, B );
 
    // Calculate all possible squared distances between the segments
    double dist1 = ( P1 - C ).SquaredEuclideanNorm();
    double dist2 = ( P2 - D ).SquaredEuclideanNorm();
    double dist3 = ( P3 - A ).SquaredEuclideanNorm();
    double dist4 = ( P4 - B ).SquaredEuclideanNorm();
 
    // Find the minimum squared distance and update closest points
    double   min_dist = dist1;
    VECTOR2I closest1 = P1;
    VECTOR2I closest2 = C;
 
    if( dist2 < min_dist )
    {
        min_dist = dist2;
        closest1 = P2;
        closest2 = D;
    }
 
    if( dist3 < min_dist )
    {
        min_dist = dist3;
        closest1 = A;
        closest2 = P3;
    }
 
    if( dist4 < min_dist )
    {
        min_dist = dist4;
        closest1 = B;
        closest2 = P4;
    }
 
 
    PATH_CONNECTION pc;
    pc.a1 = closest1 + ( closest2 - closest1 ).Resize( halfWidth1 );
    pc.a2 = closest2 + ( closest1 - closest2 ).Resize( halfWidth2 );
    pc.weight = std::max( sqrt( min_dist ) - halfWidth1 - halfWidth2, 0.0 );
 
    if( pc.weight <= aMaxWeight )
        result.push_back( pc );
 
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_CIRCLE::Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                     double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    double   R1 = this->GetRadius();
    double   R2 = aS2.GetRadius();
    VECTOR2I center1 = this->GetPos();
    VECTOR2I center2 = aS2.GetPos();
    double   dist = ( center1 - center2 ).EuclideanNorm();
 
    if( dist > aMaxWeight || dist == 0 )
        return result;
 
    double circleAngle = EDA_ANGLE( center2 - center1 ).AsRadians();
 
    if( dist <= R2 )
    {
        // Copper circle center is inside the board-edge circle so external tangent lines
        // don't exist. The nearest gap is the radial distance between circle boundaries.
        double weight = std::max( R2 - dist - R1, 0.0 );
 
        if( weight > aMaxWeight )
            return result;
 
        double radialAngle = circleAngle + M_PI;
        double cx = cos( radialAngle );
        double cy = sin( radialAngle );
        VECTOR2I pEnd = center2 + VECTOR2I( R2 * cx, R2 * cy );
        VECTOR2I pStart = center1 + VECTOR2I( R1 * cx, R1 * cy );
 
        PATH_CONNECTION pc;
        pc.a1 = pStart;
        pc.a2 = pEnd;
        pc.weight = weight;
 
        // Callers expect two entries (one per tangent side) and select by index.
        result.push_back( pc );
        result.push_back( pc );
 
        return result;
    }
 
    double weight = sqrt( dist * dist - R2 * R2 ) - R1;
    double theta = asin( R2 / dist );
    double psi = acos( R2 / dist );
 
    if( weight > aMaxWeight )
        return result;
 
    PATH_CONNECTION pc;
    pc.weight = std::max( weight, 0.0 );
 
    VECTOR2I pStart;
    VECTOR2I pEnd;
 
    pStart = VECTOR2I( R1 * cos( theta + circleAngle ), R1 * sin( theta + circleAngle ) );
    pStart += center1;
    pEnd = VECTOR2I( -R2 * cos( psi - circleAngle ), R2 * sin( psi - circleAngle ) );
    pEnd += center2;
 
    pc.a1 = pStart;
    pc.a2 = pEnd;
    result.push_back( pc );
 
    pStart = VECTOR2I( R1 * cos( -theta + circleAngle ), R1 * sin( -theta + circleAngle ) );
    pStart += center1;
    pEnd = VECTOR2I( -R2 * cos( -psi - circleAngle ), R2 * sin( -psi - circleAngle ) );
    pEnd += center2;
 
    pc.a1 = pStart;
    pc.a2 = pEnd;
 
    result.push_back( pc );
    return result;
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                                  double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
    VECTOR2I                     point = aS2.GetPos();
    VECTOR2I                     arcCenter = this->GetPos();
 
    double radius = this->GetRadius();
    double width = this->GetWidth();
 
    EDA_ANGLE angle( point - arcCenter );
 
    while( angle < this->GetStartAngle() )
        angle += ANGLE_360;
    while( angle > this->GetEndAngle() + ANGLE_360 )
        angle -= ANGLE_360;
 
    if( angle < this->GetEndAngle() )
    {
        if( ( point - arcCenter ).SquaredEuclideanNorm() > radius * radius )
        {
            CU_SHAPE_CIRCLE circle( arcCenter, radius + width / 2 );
            return circle.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
        }
        else
        {
            PATH_CONNECTION pc;
            pc.weight = std::max( ( radius - width / 2 ) - ( point - arcCenter ).EuclideanNorm(), 0.0 );
            pc.a1 = ( point - arcCenter ).Resize( radius - width / 2 ) + arcCenter;
            pc.a2 = point;
 
            if( pc.weight > 0 && pc.weight < aMaxWeight )
                result.push_back( pc );
 
            return result;
        }
    }
    else
    {
        VECTOR2I nearestPoint;
 
        if( ( point - this->GetStartPoint() ).SquaredEuclideanNorm()
                > ( point - this->GetEndPoint() ).SquaredEuclideanNorm() )
        {
            nearestPoint = this->GetEndPoint();
        }
        else
        {
            nearestPoint = this->GetStartPoint();
        }
 
        CU_SHAPE_CIRCLE circle( nearestPoint, width / 2 );
        return circle.Paths( aS2, aMaxWeight, aMaxSquaredWeight );
    }
}
 
 
std::vector<PATH_CONNECTION> CU_SHAPE_ARC::Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                                  double aMaxSquaredWeight ) const
{
    std::vector<PATH_CONNECTION> result;
 
    double R1 = this->GetRadius();
    double R2 = aS2.GetRadius();
 
    VECTOR2I C1 = this->GetPos();
    VECTOR2I C2 = aS2.GetPos();
 
    PATH_CONNECTION bestPath;
    bestPath.weight = std::numeric_limits<double>::infinity();
    CU_SHAPE_CIRCLE csc1( C1, R1 + this->GetWidth() / 2 );
    CU_SHAPE_CIRCLE csc2( C2, R2 + aS2.GetWidth() / 2 );
 
    CU_SHAPE_CIRCLE csc3( this->GetStartPoint(), this->GetWidth() / 2 );
    CU_SHAPE_CIRCLE csc4( this->GetEndPoint(), this->GetWidth() / 2 );
    CU_SHAPE_CIRCLE csc5( aS2.GetStartPoint(), aS2.GetWidth() / 2 );
    CU_SHAPE_CIRCLE csc6( aS2.GetEndPoint(), aS2.GetWidth() / 2 );
 
    for( const std::vector<PATH_CONNECTION>& pcs : { csc1.Paths( csc2, aMaxWeight, aMaxSquaredWeight ),
                                                     this->Paths( csc2, aMaxWeight, aMaxSquaredWeight ),
                                                     csc1.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) } )
    {
        for( const PATH_CONNECTION& pc : pcs )
        {
            EDA_ANGLE testAngle1 = this->AngleBetweenStartAndEnd( pc.a1 );
            EDA_ANGLE testAngle2 = aS2.AngleBetweenStartAndEnd( pc.a2 );
 
            if( testAngle1 < this->GetEndAngle() && testAngle2 < aS2.GetEndAngle() && bestPath.weight > pc.weight )
                bestPath = pc;
        }
    }
 
    for( const std::vector<PATH_CONNECTION>& pcs : { this->Paths( csc5, aMaxWeight, aMaxSquaredWeight ),
                                                     this->Paths( csc6, aMaxWeight, aMaxSquaredWeight ),
                                                     csc3.Paths( aS2, aMaxWeight, aMaxSquaredWeight ),
                                                     csc4.Paths( aS2, aMaxWeight, aMaxSquaredWeight ) } )
    {
        for( const PATH_CONNECTION& pc : pcs )
        {
            if( bestPath.weight > pc.weight )
                bestPath = pc;
        }
    }
 
    if( bestPath.weight != std::numeric_limits<double>::infinity() )
        result.push_back( bestPath );
 
    return result;
}
 
 
bool segmentIntersectsCircle( const VECTOR2I& p1, const VECTOR2I& p2, const VECTOR2I& center, double radius,
                              std::vector<VECTOR2I>* aIntersectPoints )
{
    SEG    segment( p1, p2 );
    CIRCLE circle( center, radius );
 
    std::vector<VECTOR2I> intersectionPoints;
    INTERSECTABLE_GEOM    geom1 = segment;
    INTERSECTABLE_GEOM    geom2 = circle;
 
    INTERSECTION_VISITOR visitor( geom2, intersectionPoints );
    std::visit( visitor, geom1 );
 
    if( aIntersectPoints )
    {
        for( VECTOR2I& point : intersectionPoints )
            aIntersectPoints->push_back( point );
    }
 
    return intersectionPoints.size() > 0;
}
 
bool SegmentIntersectsBoard( const VECTOR2I& aP1, const VECTOR2I& aP2,
                             const std::vector<BOARD_ITEM*>&       aBe,
                             const std::vector<const BOARD_ITEM*>& aDontTestAgainst,
                             int                                   aMinGrooveWidth )
{
    std::vector<VECTOR2I> intersectionPoints;
    bool TestGrooveWidth = aMinGrooveWidth > 0;
 
    for( BOARD_ITEM* be : aBe )
    {
        if( count( aDontTestAgainst.begin(), aDontTestAgainst.end(), be ) > 0 )
            continue;
 
        PCB_SHAPE* d = static_cast<PCB_SHAPE*>( be );
        if( !d )
            continue;
 
        switch( d->GetShape() )
        {
        case SHAPE_T::SEGMENT:
        {
            bool intersects = segments_intersect( aP1, aP2, d->GetStart(), d->GetEnd(), intersectionPoints );
 
            if( intersects && !TestGrooveWidth )
                return false;
 
            break;
        }
 
        case SHAPE_T::RECTANGLE:
        {
            int r = d->GetCornerRadius();
 
            if( r > 0 )
            {
                // Rounded rectangle: four shortened straight sides + four quarter-circle arcs.
                int x1 = std::min( d->GetStart().x, d->GetEnd().x );
                int y1 = std::min( d->GetStart().y, d->GetEnd().y );
                int x2 = std::max( d->GetStart().x, d->GetEnd().x );
                int y2 = std::max( d->GetStart().y, d->GetEnd().y );
 
                // Straight sides (between arc endpoints). Skip zero-length
                // sides that occur when one dimension equals 2*r (stadium).
                int w = x2 - x1;
                int h = y2 - y1;
                bool intersects = false;
 
                if( w > 2 * r )
                {
                    intersects |= segments_intersect( aP1, aP2, { x1 + r, y1 }, { x2 - r, y1 },
                                                      intersectionPoints );
                    intersects |= segments_intersect( aP1, aP2, { x2 - r, y2 }, { x1 + r, y2 },
                                                      intersectionPoints );
                }
 
                if( h > 2 * r )
                {
                    intersects |= segments_intersect( aP1, aP2, { x2, y1 + r }, { x2, y2 - r },
                                                      intersectionPoints );
                    intersects |= segments_intersect( aP1, aP2, { x1, y2 - r }, { x1, y1 + r },
                                                      intersectionPoints );
                }
 
                if( intersects && !TestGrooveWidth )
                    return false;
 
                // Corner arcs, matching the decomposition in TransformEdgeToCreepShapes.
                // Stadium shapes get semicircles instead of four quarter-arcs to
                // avoid duplicate centers that cause division by zero in Paths().
                struct CornerArcRange
                {
                    VECTOR2I  center;
                    EDA_ANGLE startAngle;
                    EDA_ANGLE endAngle;
                };
 
                std::vector<CornerArcRange> arcs;
 
                if( h == 2 * r )
                {
                    // Horizontal stadium: left and right semicircles. Each cap spans
                    // the outer half of its circle so the modeled boundary matches the
                    // decomposition in TransformEdgeToCreepShapes.
                    arcs.push_back( { { x1 + r, y1 + r },
                                      EDA_ANGLE( 90.0, DEGREES_T ),
                                      EDA_ANGLE( 270.0, DEGREES_T ) } );
                    arcs.push_back( { { x2 - r, y1 + r },
                                      EDA_ANGLE( -90.0, DEGREES_T ),
                                      EDA_ANGLE( 90.0, DEGREES_T ) } );
                }
                else if( w == 2 * r )
                {
                    // Vertical stadium: top and bottom semicircles
                    arcs.push_back( { { x1 + r, y1 + r },
                                      EDA_ANGLE( -180.0, DEGREES_T ),
                                      EDA_ANGLE( 0.0, DEGREES_T ) } );
                    arcs.push_back( { { x1 + r, y2 - r },
                                      EDA_ANGLE( 0.0, DEGREES_T ),
                                      EDA_ANGLE( 180.0, DEGREES_T ) } );
                }
                else
                {
                    arcs = {
                        { { x1 + r, y1 + r }, EDA_ANGLE( -180.0, DEGREES_T ),
                          EDA_ANGLE( -90.0, DEGREES_T ) },
                        { { x2 - r, y1 + r }, EDA_ANGLE( -90.0, DEGREES_T ),
                          EDA_ANGLE( 0.0, DEGREES_T ) },
                        { { x2 - r, y2 - r }, EDA_ANGLE( 0.0, DEGREES_T ),
                          EDA_ANGLE( 90.0, DEGREES_T ) },
                        { { x1 + r, y2 - r }, EDA_ANGLE( 90.0, DEGREES_T ),
                          EDA_ANGLE( 180.0, DEGREES_T ) },
                    };
                }
 
                for( const CornerArcRange& ca : arcs )
                {
                    bool arcIntersects = segmentIntersectsArc( aP1, aP2, ca.center, r,
                                                               ca.startAngle, ca.endAngle,
                                                               &intersectionPoints );
 
                    if( arcIntersects && !TestGrooveWidth )
                        return false;
                }
            }
            else
            {
                VECTOR2I c1 = d->GetStart();
                VECTOR2I c2( d->GetStart().x, d->GetEnd().y );
                VECTOR2I c3 = d->GetEnd();
                VECTOR2I c4( d->GetEnd().x, d->GetStart().y );
 
                bool intersects = false;
                intersects |= segments_intersect( aP1, aP2, c1, c2, intersectionPoints );
                intersects |= segments_intersect( aP1, aP2, c2, c3, intersectionPoints );
                intersects |= segments_intersect( aP1, aP2, c3, c4, intersectionPoints );
                intersects |= segments_intersect( aP1, aP2, c4, c1, intersectionPoints );
 
                if( intersects && !TestGrooveWidth )
                    return false;
            }
 
            break;
        }
 
        case SHAPE_T::POLY:
        {
            std::vector<VECTOR2I> points = d->GetPolyPoints();
 
            if( points.size() < 2 )
                break;
 
            VECTOR2I prevPoint = points.back();
 
            bool intersects = false;
 
            for( const VECTOR2I& p : points )
            {
                intersects |= segments_intersect( aP1, aP2, prevPoint, p, intersectionPoints );
                prevPoint = p;
            }
 
            if( intersects && !TestGrooveWidth )
                return false;
 
            break;
        }
 
        case SHAPE_T::CIRCLE:
        {
            VECTOR2I center = d->GetCenter();
            double   radius = d->GetRadius();
 
            bool intersects = segmentIntersectsCircle( aP1, aP2, center, radius, &intersectionPoints );
 
            if( intersects && !TestGrooveWidth )
                return false;
 
            break;
        }
 
        case SHAPE_T::ARC:
        {
            VECTOR2I center = d->GetCenter();
            double   radius = d->GetRadius();
 
            EDA_ANGLE A, B;
            d->CalcArcAngles( A, B );
 
            bool intersects = segmentIntersectsArc( aP1, aP2, center, radius, A, B, &intersectionPoints );
 
            if( intersects && !TestGrooveWidth )
                return false;
 
            break;
        }
 
        default:
            break;
        }
    }
 
    if( intersectionPoints.size() <= 0 )
        return true;
 
    if( intersectionPoints.size() % 2 != 0 )
        return false; // Should not happen if the start and end are both on the board
 
    int minx = intersectionPoints[0].x;
    int maxx = intersectionPoints[0].x;
    int miny = intersectionPoints[0].y;
    int maxy = intersectionPoints[0].y;
 
    for( const VECTOR2I& v : intersectionPoints )
    {
        minx = v.x < minx ? v.x : minx;
        maxx = v.x > maxx ? v.x : maxx;
        miny = v.x < miny ? v.x : miny;
        maxy = v.x > maxy ? v.x : maxy;
    }
 
    if( abs( maxx - minx ) > abs( maxy - miny ) )
    {
        std::sort( intersectionPoints.begin(), intersectionPoints.end(),
                   []( const VECTOR2I& a, const VECTOR2I& b )
                   {
                       return a.x > b.x;
                   } );
    }
    else
    {
        std::sort( intersectionPoints.begin(), intersectionPoints.end(),
                   []( const VECTOR2I& a, const VECTOR2I& b )
                   {
                       return a.y > b.y;
                   } );
    }
 
    int GVSquared = aMinGrooveWidth * aMinGrooveWidth;
 
    for( size_t i = 0; i < intersectionPoints.size(); i += 2 )
    {
        if( intersectionPoints[i].SquaredDistance( intersectionPoints[i + 1] ) > GVSquared )
            return false;
    }
 
    return true;
}
 
 
std::vector<PATH_CONNECTION> GetPaths( CREEP_SHAPE* aS1, CREEP_SHAPE* aS2, double aMaxWeight )
{
    double                       maxWeight = aMaxWeight;
    double                       maxWeightSquared = maxWeight * maxWeight;
    std::vector<PATH_CONNECTION> result;
 
    CU_SHAPE_SEGMENT* cusegment1 = dynamic_cast<CU_SHAPE_SEGMENT*>( aS1 );
    CU_SHAPE_SEGMENT* cusegment2 = dynamic_cast<CU_SHAPE_SEGMENT*>( aS2 );
    CU_SHAPE_CIRCLE*  cucircle1 = dynamic_cast<CU_SHAPE_CIRCLE*>( aS1 );
    CU_SHAPE_CIRCLE*  cucircle2 = dynamic_cast<CU_SHAPE_CIRCLE*>( aS2 );
    CU_SHAPE_ARC*     cuarc1 = dynamic_cast<CU_SHAPE_ARC*>( aS1 );
    CU_SHAPE_ARC*     cuarc2 = dynamic_cast<CU_SHAPE_ARC*>( aS2 );
 
 
    BE_SHAPE_POINT*  bepoint1 = dynamic_cast<BE_SHAPE_POINT*>( aS1 );
    BE_SHAPE_POINT*  bepoint2 = dynamic_cast<BE_SHAPE_POINT*>( aS2 );
    BE_SHAPE_CIRCLE* becircle1 = dynamic_cast<BE_SHAPE_CIRCLE*>( aS1 );
    BE_SHAPE_CIRCLE* becircle2 = dynamic_cast<BE_SHAPE_CIRCLE*>( aS2 );
    BE_SHAPE_ARC*    bearc1 = dynamic_cast<BE_SHAPE_ARC*>( aS1 );
    BE_SHAPE_ARC*    bearc2 = dynamic_cast<BE_SHAPE_ARC*>( aS2 );
 
    // Cu to Cu
 
    if( cuarc1 && cuarc2 )
        return cuarc1->Paths( *cuarc2, maxWeight, maxWeightSquared );
    if( cuarc1 && cucircle2 )
        return cuarc1->Paths( *cucircle2, maxWeight, maxWeightSquared );
    if( cuarc1 && cusegment2 )
        return cuarc1->Paths( *cusegment2, maxWeight, maxWeightSquared );
    if( cucircle1 && cuarc2 )
        return cucircle1->Paths( *cuarc2, maxWeight, maxWeightSquared );
    if( cucircle1 && cucircle2 )
        return cucircle1->Paths( *cucircle2, maxWeight, maxWeightSquared );
    if( cucircle1 && cusegment2 )
        return cucircle1->Paths( *cusegment2, maxWeight, maxWeightSquared );
    if( cusegment1 && cuarc2 )
        return cusegment1->Paths( *cuarc2, maxWeight, maxWeightSquared );
    if( cusegment1 && cucircle2 )
        return cusegment1->Paths( *cucircle2, maxWeight, maxWeightSquared );
    if( cusegment1 && cusegment2 )
        return cusegment1->Paths( *cusegment2, maxWeight, maxWeightSquared );
 
 
    // Cu to Be
 
    if( cuarc1 && bearc2 )
        return cuarc1->Paths( *bearc2, maxWeight, maxWeightSquared );
    if( cuarc1 && becircle2 )
        return cuarc1->Paths( *becircle2, maxWeight, maxWeightSquared );
    if( cuarc1 && bepoint2 )
        return cuarc1->Paths( *bepoint2, maxWeight, maxWeightSquared );
    if( cucircle1 && bearc2 )
        return cucircle1->Paths( *bearc2, maxWeight, maxWeightSquared );
    if( cucircle1 && becircle2 )
        return cucircle1->Paths( *becircle2, maxWeight, maxWeightSquared );
    if( cucircle1 && bepoint2 )
        return cucircle1->Paths( *bepoint2, maxWeight, maxWeightSquared );
    if( cusegment1 && bearc2 )
        return cusegment1->Paths( *bearc2, maxWeight, maxWeightSquared );
    if( cusegment1 && becircle2 )
        return cusegment1->Paths( *becircle2, maxWeight, maxWeightSquared );
    if( cusegment1 && bepoint2 )
        return cusegment1->Paths( *bepoint2, maxWeight, maxWeightSquared );
 
    // Reversed
 
    if( cuarc2 && bearc1 )
        return bearc1->Paths( *cuarc2, maxWeight, maxWeightSquared );
    if( cuarc2 && becircle1 )
        return becircle1->Paths( *cuarc2, maxWeight, maxWeightSquared );
    if( cuarc2 && bepoint1 )
        return bepoint1->Paths( *cuarc2, maxWeight, maxWeightSquared );
    if( cucircle2 && bearc1 )
        return bearc1->Paths( *cucircle2, maxWeight, maxWeightSquared );
    if( cucircle2 && becircle1 )
        return becircle1->Paths( *cucircle2, maxWeight, maxWeightSquared );
    if( cucircle2 && bepoint1 )
        return bepoint1->Paths( *cucircle2, maxWeight, maxWeightSquared );
    if( cusegment2 && bearc1 )
        return bearc1->Paths( *cusegment2, maxWeight, maxWeightSquared );
    if( cusegment2 && becircle1 )
        return becircle1->Paths( *cusegment2, maxWeight, maxWeightSquared );
    if( cusegment2 && bepoint1 )
        return bepoint1->Paths( *cusegment2, maxWeight, maxWeightSquared );
 
 
    // Be to Be
 
    if( bearc1 && bearc2 )
        return bearc1->Paths( *bearc2, maxWeight, maxWeightSquared );
    if( bearc1 && becircle2 )
        return bearc1->Paths( *becircle2, maxWeight, maxWeightSquared );
    if( bearc1 && bepoint2 )
        return bearc1->Paths( *bepoint2, maxWeight, maxWeightSquared );
    if( becircle1 && bearc2 )
        return becircle1->Paths( *bearc2, maxWeight, maxWeightSquared );
    if( becircle1 && becircle2 )
        return becircle1->Paths( *becircle2, maxWeight, maxWeightSquared );
    if( becircle1 && bepoint2 )
        return becircle1->Paths( *bepoint2, maxWeight, maxWeightSquared );
    if( bepoint1 && bearc2 )
        return bepoint1->Paths( *bearc2, maxWeight, maxWeightSquared );
    if( bepoint1 && becircle2 )
        return bepoint1->Paths( *becircle2, maxWeight, maxWeightSquared );
    if( bepoint1 && bepoint2 )
        return bepoint1->Paths( *bepoint2, maxWeight, maxWeightSquared );
 
    return result;
}
 
double CREEPAGE_GRAPH::Solve( std::shared_ptr<GRAPH_NODE>& aFrom, std::shared_ptr<GRAPH_NODE>& aTo,
                              std::vector<std::shared_ptr<GRAPH_CONNECTION>>& aResult ) // Change to vector of pointers
{
    if( !aFrom || !aTo )
        return 0;
 
    if( aFrom == aTo )
        return 0;
 
    // Dijkstra's algorithm for shortest path
    std::unordered_map<GRAPH_NODE*, double>     distances;
    std::unordered_map<GRAPH_NODE*, GRAPH_NODE*> previous;
 
    // Each heap entry carries the tentative distance captured at push time. A comparator that read
    // the live distances map instead would let a decrease-key reinsertion silently corrupt the heap
    // ordering, so aTo could be popped on a non-shortest path and the early break would return it.
    using QUEUE_ITEM = std::pair<double, GRAPH_NODE*>;
 
    auto cmp = []( const QUEUE_ITEM& aLeft, const QUEUE_ITEM& aRight )
    {
        if( aLeft.first == aRight.first )
            return aLeft.second > aRight.second; // Compare addresses to avoid ties.
        return aLeft.first > aRight.first;
    };
    std::priority_queue<QUEUE_ITEM, std::vector<QUEUE_ITEM>, decltype( cmp )> pq( cmp );
 
    // Initialize distances to infinity for all nodes except the starting node
    for( const std::shared_ptr<GRAPH_NODE>& node : m_nodes )
    {
        if( node != nullptr )
            distances[node.get()] = std::numeric_limits<double>::infinity(); // Set to infinity
    }
 
    distances[aFrom.get()] = 0.0;
    distances[aTo.get()] = std::numeric_limits<double>::infinity();
    pq.push( { 0.0, aFrom.get() } );
 
    // Dijkstra's main loop
    while( !pq.empty() )
    {
        auto [dist, current] = pq.top();
        pq.pop();
 
        // A stale entry left behind by a decrease-key reinsertion; its shorter copy was already
        // processed
        if( dist > distances[current] )
            continue;
 
        if( current == aTo.get() )
        {
            break; // Shortest path found
        }
 
        // Traverse neighbors
        for( const std::shared_ptr<GRAPH_CONNECTION>& connection : current->m_node_conns )
        {
            GRAPH_NODE* neighbor = ( connection->n1 ).get() == current ? ( connection->n2 ).get()
                                                                       : ( connection->n1 ).get();
 
            if( !neighbor )
                continue;
 
            // Ignore connections with negative weights as Dijkstra doesn't support them.
            if( connection->m_path.weight < 0.0 )
            {
                wxLogTrace( "CREEPAGE", "Negative weight connection found. Ignoring connection." );
                continue;
            }
 
            double alt = distances[current] + connection->m_path.weight; // Calculate alternative path cost
 
            if( alt < distances[neighbor] )
            {
                distances[neighbor] = alt;
                previous[neighbor] = current;
                pq.push( { alt, neighbor } );
            }
        }
    }
 
    double pathWeight = distances[aTo.get()];
 
    // If aTo is unreachable, return infinity
    if( pathWeight == std::numeric_limits<double>::infinity() )
        return std::numeric_limits<double>::infinity();
 
    // Trace back the path from aTo to aFrom
    GRAPH_NODE* step = aTo.get();
 
    while( step != aFrom.get() )
    {
        GRAPH_NODE* prevNode = previous[step];
 
        for( const std::shared_ptr<GRAPH_CONNECTION>& node_conn : step->m_node_conns )
        {
            if( ( ( node_conn->n1 ).get() == prevNode && ( node_conn->n2 ).get() == step )
                || ( ( node_conn->n1 ).get() == step && ( node_conn->n2 ).get() == prevNode ) )
            {
                aResult.push_back( node_conn );
                break;
            }
        }
        step = prevNode;
    }
 
    return pathWeight;
}
 
void CREEPAGE_GRAPH::Addshape( const SHAPE& aShape, std::shared_ptr<GRAPH_NODE>& aConnectTo,
                               BOARD_ITEM* aParent )
{
    CREEP_SHAPE* newshape = nullptr;
 
    if( !aConnectTo )
        return;
 
    switch( aShape.Type() )
    {
    case SH_SEGMENT:
    {
        const SHAPE_SEGMENT& segment = dynamic_cast<const SHAPE_SEGMENT&>( aShape );
        CU_SHAPE_SEGMENT*    cuseg = new CU_SHAPE_SEGMENT( segment.GetSeg().A, segment.GetSeg().B,
                                                           segment.GetWidth() );
        newshape = dynamic_cast<CREEP_SHAPE*>( cuseg );
        break;
    }
 
    case SH_CIRCLE:
    {
        const SHAPE_CIRCLE& circle = dynamic_cast<const SHAPE_CIRCLE&>( aShape );
        CU_SHAPE_CIRCLE* cucircle = new CU_SHAPE_CIRCLE( circle.GetCenter(), circle.GetRadius() );
        newshape = dynamic_cast<CREEP_SHAPE*>( cucircle );
        break;
    }
 
    case SH_ARC:
    {
        const SHAPE_ARC& arc = dynamic_cast<const SHAPE_ARC&>( aShape );
        EDA_ANGLE        alpha, beta;
        VECTOR2I         start, end;
 
        EDA_SHAPE edaArc( SHAPE_T::ARC, 0, FILL_T::NO_FILL );
 
        if( arc.IsClockwise() )
        {
            edaArc.SetArcGeometry( arc.GetP0(), arc.GetArcMid(), arc.GetP1() );
            start = arc.GetP0();
            end = arc.GetP1();
        }
        else
        {
            edaArc.SetArcGeometry( arc.GetP1(), arc.GetArcMid(), arc.GetP0() );
            start = arc.GetP1();
            end = arc.GetP0();
        }
 
        edaArc.CalcArcAngles( alpha, beta );
 
        CU_SHAPE_ARC* cuarc = new CU_SHAPE_ARC( edaArc.getCenter(), edaArc.GetRadius(), alpha, beta,
                                                arc.GetP0(), arc.GetP1() );
        cuarc->SetWidth( arc.GetWidth() );
        newshape = dynamic_cast<CREEP_SHAPE*>( cuarc );
        break;
    }
 
    case SH_COMPOUND:
    {
        int nbShapes = static_cast<const SHAPE_COMPOUND*>( &aShape )->Shapes().size();
        for( const SHAPE* subshape : ( static_cast<const SHAPE_COMPOUND*>( &aShape )->Shapes() ) )
        {
            if( subshape )
            {
                // We don't want to add shape for the inner rectangle of rounded rectangles
                if( !( ( subshape->Type() == SH_RECT ) && ( nbShapes == 5 ) ) )
                    Addshape( *subshape, aConnectTo, aParent );
            }
        }
        break;
    }
 
    case SH_POLY_SET:
    {
        const SHAPE_POLY_SET& polySet = dynamic_cast<const SHAPE_POLY_SET&>( aShape );
 
        for( auto it = polySet.CIterateSegmentsWithHoles(); it; it++ )
        {
            const SEG     object = *it;
            SHAPE_SEGMENT segment( object.A, object.B );
            Addshape( segment, aConnectTo, aParent );
        }
        break;
    }
 
    case SH_LINE_CHAIN:
    {
        const SHAPE_LINE_CHAIN& lineChain = dynamic_cast<const SHAPE_LINE_CHAIN&>( aShape );
 
        VECTOR2I prevPoint = lineChain.CLastPoint();
 
        for( const VECTOR2I& point : lineChain.CPoints() )
        {
            SHAPE_SEGMENT segment( point, prevPoint );
            prevPoint = point;
            Addshape( segment, aConnectTo, aParent );
        }
 
        break;
    }
 
    case SH_SIMPLE:
    {
        // SHAPE_SIMPLE is the arbitrary-polygon form used for rectangular, trapezoidal and
        // chamfered pads when they are not axis-aligned (orthogonal rotations collapse to
        // SH_RECT instead). Decompose its closed outline into segments so the copper edge
        // is added to the graph, otherwise the pad contributes no creepage anchor and the
        // path snaps to the pad hole instead of the copper (issue #24543).
        const SHAPE_SIMPLE&     simple = dynamic_cast<const SHAPE_SIMPLE&>( aShape );
        const SHAPE_LINE_CHAIN& vertices = simple.Vertices();
 
        if( vertices.PointCount() < 3 )
            break;
 
        VECTOR2I prevPoint = vertices.CLastPoint();
 
        for( const VECTOR2I& point : vertices.CPoints() )
        {
            if( point != prevPoint )
                Addshape( SHAPE_SEGMENT( prevPoint, point ), aConnectTo, aParent );
 
            prevPoint = point;
        }
 
        break;
    }
 
    case SH_RECT:
    {
        const SHAPE_RECT& rect = dynamic_cast<const SHAPE_RECT&>( aShape );
 
        VECTOR2I point0 = rect.GetPosition();
        VECTOR2I point1 = rect.GetPosition() + VECTOR2I( rect.GetSize().x, 0 );
        VECTOR2I point2 = rect.GetPosition() + rect.GetSize();
        VECTOR2I point3 = rect.GetPosition() + VECTOR2I( 0, rect.GetSize().y );
 
        Addshape( SHAPE_SEGMENT( point0, point1 ), aConnectTo, aParent );
        Addshape( SHAPE_SEGMENT( point1, point2 ), aConnectTo, aParent );
        Addshape( SHAPE_SEGMENT( point2, point3 ), aConnectTo, aParent );
        Addshape( SHAPE_SEGMENT( point3, point0 ), aConnectTo, aParent );
        break;
    }
 
    default:
        break;
    }
 
    if( !newshape )
        return;
 
    std::shared_ptr<GRAPH_NODE> gnShape = nullptr;
 
    newshape->SetParent( aParent );
 
    switch( aShape.Type() )
    {
    case SH_SEGMENT: gnShape = AddNode( GRAPH_NODE::SEGMENT, newshape, newshape->GetPos() ); break;
    case SH_CIRCLE:  gnShape = AddNode( GRAPH_NODE::CIRCLE, newshape, newshape->GetPos() );  break;
    case SH_ARC:     gnShape = AddNode( GRAPH_NODE::ARC, newshape, newshape->GetPos() );     break;
    default:                                                                                 break;
    }
 
    if( gnShape )
    {
        m_shapeCollection.push_back( newshape );
        gnShape->m_net = aConnectTo->m_net;
        std::shared_ptr<GRAPH_CONNECTION> gc = AddConnection( gnShape, aConnectTo );
 
        if( gc )
            gc->m_path.m_show = false;
    }
    else
    {
        delete newshape;
        newshape = nullptr;
    }
}
 
void CREEPAGE_GRAPH::GeneratePaths( double aMaxWeight, PCB_LAYER_ID aLayer,
                                   const std::set<int>* aRelevantNets )
{
    auto irrelevantPair = [&]( const std::shared_ptr<GRAPH_NODE>& gn1,
                               const std::shared_ptr<GRAPH_NODE>& gn2 ) -> bool
    {
        return aRelevantNets && gn1->m_parent && gn2->m_parent && gn1->m_parent->IsConductive()
               && gn2->m_parent->IsConductive() && !aRelevantNets->count( gn1->m_net )
               && !aRelevantNets->count( gn2->m_net );
    };
 
    std::vector<std::shared_ptr<GRAPH_NODE>> nodes;
    std::mutex                               nodes_lock;
    thread_pool&                             tp = GetKiCadThreadPool();
 
    std::vector<CREEPAGE_TRACK_ENTRY*> trackEntries;
    TRACK_RTREE::Builder              trackBuilder;
 
    if( aLayer != Edge_Cuts )
    {
        for( PCB_TRACK* track : m_board.Tracks() )
        {
            if( track && track->Type() == KICAD_T::PCB_TRACE_T && track->IsOnLayer( aLayer ) )
            {
                std::shared_ptr<SHAPE> sh = track->GetEffectiveShape();
 
                if( sh && sh->Type() == SHAPE_TYPE::SH_SEGMENT )
                {
                    CREEPAGE_TRACK_ENTRY* entry = new CREEPAGE_TRACK_ENTRY();
                    entry->segment = SEG( track->GetStart(), track->GetEnd() );
                    entry->layer = aLayer;
                    entry->halfWidth = track->GetWidth() / 2;
                    entry->track = track;
 
                    BOX2I bbox = track->GetBoundingBox();
                    int   minCoords[2] = { bbox.GetX(), bbox.GetY() };
                    int   maxCoords[2] = { bbox.GetRight(), bbox.GetBottom() };
                    trackBuilder.Add( minCoords, maxCoords, entry );
                    trackEntries.push_back( entry );
                }
            }
        }
    }
 
    TRACK_RTREE trackIndex = trackBuilder.Build();
 
    std::copy_if( m_nodes.begin(), m_nodes.end(), std::back_inserter( nodes ),
            [&]( const std::shared_ptr<GRAPH_NODE>& gn )
            {
                return gn && gn->m_parent && gn->m_connectDirectly && ( gn->m_type != GRAPH_NODE::TYPE::VIRTUAL );
            } );
 
    std::sort( nodes.begin(), nodes.end(),
            []( const std::shared_ptr<GRAPH_NODE>& gn1, const std::shared_ptr<GRAPH_NODE>& gn2 )
            {
                return gn1->m_parent < gn2->m_parent
                        || ( gn1->m_parent == gn2->m_parent && gn1->m_net < gn2->m_net );
            } );
 
    // Build parent -> net -> nodes mapping for efficient filtering
    // Also cache bounding boxes for early spatial filtering
    std::unordered_map<const BOARD_ITEM*, std::unordered_map<int, std::vector<std::shared_ptr<GRAPH_NODE>>>> parent_net_groups;
    std::unordered_map<const BOARD_ITEM*, BOX2I> parent_bboxes;
    std::vector<const BOARD_ITEM*> parent_keys;
 
    for( const auto& gn : nodes )
    {
        const BOARD_ITEM* parent = gn->m_parent->GetParent();
 
        if( parent_net_groups[parent].empty() )
        {
            parent_keys.push_back( parent );
            if( parent )
                parent_bboxes[parent] = parent->GetBoundingBox();
        }
 
        parent_net_groups[parent][gn->m_net].push_back( gn );
    }
 
    // Generate work items using parent-level spatial indexing
    std::vector<std::pair<std::shared_ptr<GRAPH_NODE>, std::shared_ptr<GRAPH_NODE>>> work_items;
 
    // Use RTree for spatial indexing of parent bounding boxes
    // Expand each bbox by maxWeight to find potentially overlapping parents
 
    int64_t maxDist = static_cast<int64_t>( aMaxWeight );
 
    struct ParentEntry
    {
        const BOARD_ITEM* parent;
        BOX2I             bbox;
    };
 
    std::vector<ParentEntry> parentEntries;
 
    for( const auto* parent : parent_keys )
    {
        if( parent )
        {
            ParentEntry entry;
            entry.parent = parent;
            entry.bbox = parent_bboxes[parent];
            parentEntries.push_back( entry );
        }
    }
 
    KIRTREE::PACKED_RTREE<ParentEntry*, int, 2>::Builder parentBuilder;
 
    for( ParentEntry& entry : parentEntries )
    {
        int minCoords[2] = { entry.bbox.GetLeft(), entry.bbox.GetTop() };
        int maxCoords[2] = { entry.bbox.GetRight(), entry.bbox.GetBottom() };
        parentBuilder.Add( minCoords, maxCoords, &entry );
    }
 
    auto parentIndex = parentBuilder.Build();
 
    // Parallelize parent pair search using thread pool
    std::mutex work_items_lock;
 
    auto searchParent = [&]( size_t i ) -> bool
    {
        const ParentEntry& entry1 = parentEntries[i];
        const BOARD_ITEM*  parent1 = entry1.parent;
        BOX2I              bbox1 = entry1.bbox;
 
        std::vector<std::pair<std::shared_ptr<GRAPH_NODE>, std::shared_ptr<GRAPH_NODE>>> localWorkItems;
 
        // Search for parents within maxDist of bbox1
        int searchMin[2] = { bbox1.GetLeft() - (int) maxDist, bbox1.GetTop() - (int) maxDist };
        int searchMax[2] = { bbox1.GetRight() + (int) maxDist, bbox1.GetBottom() + (int) maxDist };
 
        auto parentVisitor = [&]( ParentEntry* entry2 ) -> bool
        {
            const BOARD_ITEM* parent2 = entry2->parent;
 
            // Only process if parent1 < parent2 to avoid duplicates
            if( parent1 >= parent2 )
                return true;
 
            // Precise bbox distance check
            BOX2I bbox2 = entry2->bbox;
 
            int64_t bboxDistX = 0;
 
            if( bbox2.GetLeft() > bbox1.GetRight() )
                bboxDistX = bbox2.GetLeft() - bbox1.GetRight();
            else if( bbox1.GetLeft() > bbox2.GetRight() )
                bboxDistX = bbox1.GetLeft() - bbox2.GetRight();
 
            int64_t bboxDistY = 0;
 
            if( bbox2.GetTop() > bbox1.GetBottom() )
                bboxDistY = bbox2.GetTop() - bbox1.GetBottom();
            else if( bbox1.GetTop() > bbox2.GetBottom() )
                bboxDistY = bbox1.GetTop() - bbox2.GetBottom();
 
            int64_t bboxDistSq = bboxDistX * bboxDistX + bboxDistY * bboxDistY;
 
            if( bboxDistSq > maxDist * maxDist )
                return true;
 
            // Get nodes for both parents (thread-safe reads from const map)
            auto it1 = parent_net_groups.find( parent1 );
            auto it2 = parent_net_groups.find( parent2 );
 
            if( it1 == parent_net_groups.end() || it2 == parent_net_groups.end() )
                return true;
 
            for( const auto& [net1, nodes1] : it1->second )
            {
                for( const auto& [net2, nodes2] : it2->second )
                {
                    // Skip same net if both are conductive
                    if( net1 == net2 && !nodes1.empty() && !nodes2.empty() )
                    {
                        if( nodes1[0]->m_parent->IsConductive()
                            && nodes2[0]->m_parent->IsConductive() )
                            continue;
                    }
 
                    for( const auto& gn1 : nodes1 )
                    {
                        for( const auto& gn2 : nodes2 )
                        {
                            VECTOR2I pos1 = gn1->m_parent->GetPos();
                            VECTOR2I pos2 = gn2->m_parent->GetPos();
                            int      r1 = gn1->m_parent->GetRadius();
                            int      r2 = gn2->m_parent->GetRadius();
 
                            int64_t centerDistSq = ( pos1 - pos2 ).SquaredEuclideanNorm();
                            double  threshold = aMaxWeight + r1 + r2;
                            double  thresholdSq = threshold * threshold;
 
                            if( (double) centerDistSq > thresholdSq )
                                continue;
 
                            if( irrelevantPair( gn1, gn2 ) )
                                continue;
 
                            localWorkItems.push_back( { gn1, gn2 } );
                        }
                    }
                }
            }
 
            return true;
        };
 
        parentIndex.Search( searchMin, searchMax, parentVisitor );
 
        // Merge local results into global
        if( !localWorkItems.empty() )
        {
            std::lock_guard<std::mutex> lock( work_items_lock );
            work_items.insert( work_items.end(), localWorkItems.begin(), localWorkItems.end() );
        }
 
        return true;
    };
 
    // Use thread pool if there are enough parents
    if( parentEntries.size() > 100 && tp.get_tasks_total() < tp.get_thread_count() - 4 )
    {
        auto ret = tp.submit_loop( 0, parentEntries.size(), searchParent );
 
        for( auto& r : ret )
        {
            if( r.valid() )
                r.wait();
        }
    }
    else
    {
        for( size_t i = 0; i < parentEntries.size(); ++i )
            searchParent( i );
    }
 
    // Generate work items for same-parent node pairs. The cross-parent search above
    // skips pairs where parent1 == parent2, but creepage paths between different edge
    // segments of the same slot (which share a footprint grandparent) are needed for
    // the path to navigate around the slot geometry. Also handles null-parent nodes
    // (e.g. NPTH pad shapes) which were excluded from the RTree search entirely.
    for( const auto& [parent, net_groups] : parent_net_groups )
    {
        std::vector<std::shared_ptr<GRAPH_NODE>> sameParentNodes;
 
        for( const auto& [net, nodeList] : net_groups )
            sameParentNodes.insert( sameParentNodes.end(), nodeList.begin(), nodeList.end() );
 
        for( size_t i = 0; i < sameParentNodes.size(); i++ )
        {
            for( size_t j = i + 1; j < sameParentNodes.size(); j++ )
            {
                auto& gn1 = sameParentNodes[i];
                auto& gn2 = sameParentNodes[j];
 
                // ConnectChildren already handles nodes on the same CREEP_SHAPE
                if( gn1->m_parent == gn2->m_parent )
                    continue;
 
                // Skip same-net conductive pairs
                if( gn1->m_parent->IsConductive() && gn2->m_parent->IsConductive()
                    && gn1->m_net == gn2->m_net )
                {
                    continue;
                }
 
                VECTOR2I pos1 = gn1->m_parent->GetPos();
                VECTOR2I pos2 = gn2->m_parent->GetPos();
                int      r1 = gn1->m_parent->GetRadius();
                int      r2 = gn2->m_parent->GetRadius();
 
                int64_t centerDistSq = ( pos1 - pos2 ).SquaredEuclideanNorm();
                double  threshold = aMaxWeight + r1 + r2;
                double  thresholdSq = threshold * threshold;
 
                if( (double) centerDistSq > thresholdSq )
                    continue;
 
                if( irrelevantPair( gn1, gn2 ) )
                    continue;
 
                work_items.push_back( { gn1, gn2 } );
            }
        }
    }
 
    auto processWorkItems =
            [&]( size_t idx ) -> bool
            {
                auto& [gn1, gn2] = work_items[idx];
 
                // Distance filtering already done during work item creation
                CREEP_SHAPE* shape1 = gn1->m_parent;
                CREEP_SHAPE* shape2 = gn2->m_parent;
 
                for( const PATH_CONNECTION& pc : GetPaths( shape1, shape2, aMaxWeight ) )
                {
                    std::vector<const BOARD_ITEM*> IgnoreForTest;
 
                    // For CIRCLE and ARC shapes the candidate path ends ON the shape's
                    // boundary at a tangent point. segmentIntersectsCircle has no
                    // endpoint exclusion, and segmentIntersectsArc only excludes when
                    // the shared point is also an arc endpoint, so a tangent point
                    // lying mid-arc registers as an intersection. Without suppressing
                    // the parent here, the tangent path is wrongly rejected and
                    // Dijkstra is forced onto a longer route around the obstacle
                    // (issue #24286).
                    //
                    // POINT shapes don't need suppression because segments_intersect
                    // excludes shared segment endpoints, so paths ending at a POINT
                    // already get correct exclusion from its parent's other edges.
                    if( shape1->GetType() == CREEP_SHAPE::TYPE::CIRCLE
                        || shape1->GetType() == CREEP_SHAPE::TYPE::ARC )
                    {
                        IgnoreForTest.push_back( shape1->GetParent() );
                    }
 
                    if( shape2->GetType() == CREEP_SHAPE::TYPE::CIRCLE
                        || shape2->GetType() == CREEP_SHAPE::TYPE::ARC )
                    {
                        IgnoreForTest.push_back( shape2->GetParent() );
                    }
 
                    // Also ignore each CU shape's own parent for the endpoint-inside-track
                    // test so we don't reject paths that touch the track's own edge.
                    if( shape1->IsConductive() )
                        IgnoreForTest.push_back( shape1->GetParent() );
 
                    if( shape2->IsConductive() )
                        IgnoreForTest.push_back( shape2->GetParent() );
 
                    bool valid = pc.isValid( m_board, aLayer, m_boardEdge, IgnoreForTest, m_boardOutline,
                                     { false, true }, m_minGrooveWidth, &trackIndex );
 
                    if( !valid )
                    {
                        continue;
                    }
 
                    std::shared_ptr<GRAPH_NODE> connect1 = gn1, connect2 = gn2;
                    std::lock_guard<std::mutex> lock( nodes_lock );
 
                    // Handle non-point node1
                    if( gn1->m_parent->GetType() != CREEP_SHAPE::TYPE::POINT )
                    {
                        auto gnt1 = AddNode( GRAPH_NODE::POINT, gn1->m_parent, pc.a1 );
                        gnt1->m_connectDirectly = false;
                        connect1 = gnt1;
 
                        if( gn1->m_parent->IsConductive() )
                        {
                            if( std::shared_ptr<GRAPH_CONNECTION> gc = AddConnection( gn1, gnt1 ) )
                                gc->m_path.m_show = false;
                        }
                    }
 
                    // Handle non-point node2
                    if( gn2->m_parent->GetType() != CREEP_SHAPE::TYPE::POINT )
                    {
                        auto gnt2 = AddNode( GRAPH_NODE::POINT, gn2->m_parent, pc.a2 );
                        gnt2->m_connectDirectly = false;
                        connect2 = gnt2;
 
                        if( gn2->m_parent->IsConductive() )
                        {
                            if( std::shared_ptr<GRAPH_CONNECTION> gc = AddConnection( gn2, gnt2 ) )
                                gc->m_path.m_show = false;
                        }
                    }
 
                    AddConnection( connect1, connect2, pc );
                }
 
                return true;
            };
 
    // If the number of tasks is high enough, this indicates that the calling process
    // has already parallelized the work, so we can process all items in one go.
    if( tp.get_tasks_total() >= tp.get_thread_count() - 4 )
    {
        for( size_t ii = 0; ii < work_items.size(); ii++ )
            processWorkItems( ii );
    }
    else
    {
        auto ret = tp.submit_loop( 0, work_items.size(), processWorkItems );
 
        for( size_t ii = 0; ii < ret.size(); ii++ )
        {
            auto& r = ret[ii];
 
            if( !r.valid() )
                continue;
 
            while( r.wait_for( std::chrono::milliseconds( 100 ) ) != std::future_status::ready ){}
        }
    }
 
    // Clean up track entries
    for( CREEPAGE_TRACK_ENTRY* entry : trackEntries )
        delete entry;
}
 
 
void CREEPAGE_GRAPH::Trim( double aWeightLimit )
{
    std::vector<std::shared_ptr<GRAPH_CONNECTION>> toRemove;
 
    // Collect connections to remove
    for( std::shared_ptr<GRAPH_CONNECTION>& gc : m_connections )
    {
        if( gc && ( gc->m_path.weight > aWeightLimit ) )
            toRemove.push_back( gc );
    }
 
    // Remove collected connections
    for( const std::shared_ptr<GRAPH_CONNECTION>& gc : toRemove )
        RemoveConnection( gc );
}
 
 
void CREEPAGE_GRAPH::RemoveConnection( const std::shared_ptr<GRAPH_CONNECTION>& aGc, bool aDelete )
{
    if( !aGc )
        return;
 
    for( std::shared_ptr<GRAPH_NODE> gn : { aGc->n1, aGc->n2 } )
    {
        if( gn )
        {
            gn->m_node_conns.erase( aGc );
 
            if( gn->m_node_conns.empty() && aDelete )
            {
                auto it = std::find_if( m_nodes.begin(), m_nodes.end(),
                                        [&gn]( const std::shared_ptr<GRAPH_NODE>& node )
                                        {
                                            return node.get() == gn.get();
                                        } );
 
                if( it != m_nodes.end() )
                    m_nodes.erase( it );
 
                m_nodeset.erase( gn );
            }
        }
    }
 
    if( aDelete )
    {
        // Remove the connection from the graph's connections
        m_connections.erase( std::remove( m_connections.begin(), m_connections.end(), aGc ),
                             m_connections.end() );
    }
}
 
 
void CREEPAGE_GRAPH::TruncateToPrefix( size_t aNodeCount, size_t aConnectionCount )
{
    size_t vectorSize = m_connections.size();
 
    // Detach each connection from its endpoints' lists; the bulk resize drops them in one shot
    for( size_t i = aConnectionCount; i < vectorSize; i++ )
        RemoveConnection( m_connections[i], false );
 
    m_connections.resize( aConnectionCount, nullptr );
    m_nodes.resize( aNodeCount, nullptr );
 
    // Without this, stale per-solve nodes corrupt subsequent FindNode/AddNode lookups
    m_nodeset.clear();
 
    for( size_t i = 0; i < aNodeCount; ++i )
    {
        if( m_nodes[i] )
            m_nodeset.insert( m_nodes[i] );
    }
}
 
 
std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNode( GRAPH_NODE::TYPE aType, CREEP_SHAPE* parent,
                                                     const VECTOR2I& pos )
{
    std::shared_ptr<GRAPH_NODE> gn = FindNode( aType, parent, pos );
 
    if( gn )
        return gn;
 
    gn = std::make_shared<GRAPH_NODE>( aType, parent, pos );
    m_nodes.push_back( gn );
    m_nodeset.insert( gn );
    return gn;
}
 
 
std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNodeVirtual()
{
    //Virtual nodes are always unique, do not try to find them
    std::shared_ptr<GRAPH_NODE> gn = std::make_shared<GRAPH_NODE>( GRAPH_NODE::TYPE::VIRTUAL, nullptr );
    m_nodes.push_back( gn );
    m_nodeset.insert( gn );
    return gn;
}
 
 
std::shared_ptr<GRAPH_CONNECTION> CREEPAGE_GRAPH::AddConnection( std::shared_ptr<GRAPH_NODE>& aN1,
                                                                 std::shared_ptr<GRAPH_NODE>& aN2,
                                                                 const PATH_CONNECTION&       aPc )
{
    if( !aN1 || !aN2 )
        return nullptr;
 
    wxASSERT_MSG( ( aN1 != aN2 ), "Creepage: a connection connects a node to itself" );
 
    std::shared_ptr<GRAPH_CONNECTION> gc = std::make_shared<GRAPH_CONNECTION>( aN1, aN2, aPc );
    m_connections.push_back( gc );
    aN1->m_node_conns.insert( gc );
    aN2->m_node_conns.insert( gc );
 
    return gc;
}
 
 
std::shared_ptr<GRAPH_CONNECTION> CREEPAGE_GRAPH::AddConnection( std::shared_ptr<GRAPH_NODE>& aN1,
                                                                 std::shared_ptr<GRAPH_NODE>& aN2 )
{
    if( !aN1 || !aN2 )
        return nullptr;
 
    PATH_CONNECTION pc;
    pc.a1 = aN1->m_pos;
    pc.a2 = aN2->m_pos;
    pc.weight = 0;
 
    return AddConnection( aN1, aN2, pc );
}
 
 
std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::FindNode( GRAPH_NODE::TYPE aType, CREEP_SHAPE* aParent,
                                                      const VECTOR2I& aPos )
{
    auto it = m_nodeset.find( std::make_shared<GRAPH_NODE>( aType, aParent, aPos ) );
 
    if( it != m_nodeset.end() )
        return *it;
 
    return nullptr;
}
 
 
std::shared_ptr<GRAPH_NODE> CREEPAGE_GRAPH::AddNetElements( int aNetCode, PCB_LAYER_ID aLayer,
                                                            int aMaxCreepage )
{
    std::shared_ptr<GRAPH_NODE> virtualNode = AddNodeVirtual();
    virtualNode->m_net = aNetCode;
 
    for( FOOTPRINT* footprint : m_board.Footprints() )
    {
        for( PAD* pad : footprint->Pads() )
        {
            if( pad->GetNetCode() != aNetCode || !pad->IsOnLayer( aLayer ) )
                continue;
 
            if( std::shared_ptr<SHAPE> padShape = pad->GetEffectiveShape( aLayer ) )
                Addshape( *padShape, virtualNode, pad );
        }
    }
 
    for( PCB_TRACK* track : m_board.Tracks() )
    {
        if( track->GetNetCode() != aNetCode || !track->IsOnLayer( aLayer ) )
            continue;
 
        if( std::shared_ptr<SHAPE> shape = track->GetEffectiveShape() )
            Addshape( *shape, virtualNode, track );
    }
 
 
    for( ZONE* zone : m_board.Zones() )
    {
        if( zone->GetNetCode() != aNetCode || !zone->IsOnLayer( aLayer ) )
            continue;
 
        if( std::shared_ptr<SHAPE> shape = zone->GetEffectiveShape( aLayer ) )
            Addshape( *shape, virtualNode, zone );
    }
 
    const DRAWINGS drawings = m_board.Drawings();
 
    for( BOARD_ITEM* drawing : drawings )
    {
        if( drawing->IsConnected() )
        {
            BOARD_CONNECTED_ITEM* bci = static_cast<BOARD_CONNECTED_ITEM*>( drawing );
 
            if( bci->GetNetCode() != aNetCode || !bci->IsOnLayer( aLayer ) )
                continue;
 
            if( std::shared_ptr<SHAPE> shape = bci->GetEffectiveShape() )
                Addshape( *shape, virtualNode, bci );
        }
    }
 
 
    return virtualNode;
}