drc_creepage_utils.h

Go to the documentation of this file.

 
/*
    * Copyright (C) 2024 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, you may find one here:
    * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
    * or you may search the http://www.gnu.org website for the version 2 license,
    * or you may write to the Free Software Foundation, Inc.,
    * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
    */
 
 
#ifndef _DRC_CREEPAGE_UTILS_H
#define _DRC_CREEPAGE_UTILS_H
 
#include <common.h>
#include <macros.h>
#include <board_design_settings.h>
#include <footprint.h>
#include <pad.h>
#include <pcb_track.h>
#include <pcb_shape.h>
#include <zone.h>
#include <advanced_config.h>
#include <geometry/shape_rect.h>
#include <geometry/seg.h>
#include <geometry/shape_segment.h>
#include <drc/drc_item.h>
#include <drc/drc_rule.h>
#include <board.h>
 
 
#include <geometry/shape_circle.h>
 
 
extern bool SegmentIntersectsBoard( const VECTOR2I& aP1, const VECTOR2I& aP2,
                                    const std::vector<BOARD_ITEM*>&       aBe,
                                    const std::vector<const BOARD_ITEM*>& aDontTestAgainst,
                                    int                                   aMinGrooveWidth );
 
struct PATH_CONNECTION
{
    VECTOR2D a1;
    VECTOR2D a2;
    double   weight = -1;
    bool     m_show = true;
 
    bool m_forceA1concavityCheck = false;
    bool m_forceA2concavityCheck = false;
 
 
    bool isValid( const BOARD& aBoard, PCB_LAYER_ID aLayer,
                  const std::vector<BOARD_ITEM*>&       aBoardEdges,
                  const std::vector<const BOARD_ITEM*>& aIgnoreForTest, SHAPE_POLY_SET* aOutline,
                  const std::pair<bool, bool>& aTestLocalConcavity, int aMinGrooveWidth )
    {
        if( !aOutline )
            return true; // We keep the segment if there is a problem
 
        if( !SegmentIntersectsBoard( a1, a2, aBoardEdges, aIgnoreForTest, aMinGrooveWidth ) )
            return false;
 
        // The mid point should be inside the board.
        // Tolerance of 100nm.
 
        VECTOR2I midPoint = ( a1 + a2 ) / 2;
        int      tolerance = 100;
 
        if( !( aOutline->Contains( midPoint, -1, tolerance )
               || aOutline->PointOnEdge( midPoint, tolerance ) ) )
            return false;
 
        if( false && ( aTestLocalConcavity.first || aTestLocalConcavity.second ) )
        {
            // Test for local concavity. If it is localy convex, then it will not be a path of interest.
 
            double extendLine = 1000; // extend line by 1000nm
            // In some cases, the projected point could be on the board edge
            // In such cases, we wan to keep the line.
            // We inflate the polygon to get a small margin for computation/rounding error.
            // We might keep some unnecessary lines, but it's better than loosing the important ones.
            double extendPoly = 100; // extend polygon by 10 nm
 
            VECTOR2D a( double( a1.x ), double( a1.y ) );
            VECTOR2D b( double( a2.x ), double( a2.y ) );
 
            VECTOR2D dir( b - a );
            dir = dir * ( extendLine / dir.SquaredEuclideanNorm() );
 
            SHAPE_POLY_SET outline2 = *aOutline;
            outline2.Inflate( extendPoly, CORNER_STRATEGY::ROUND_ALL_CORNERS, 3 );
 
            if( aTestLocalConcavity.first && !aOutline->Contains( a - dir, -1, 0 ) )
                return false;
 
            if( aTestLocalConcavity.second && !aOutline->Contains( b + dir, -1, 0 ) )
                return false;
        }
 
        SEG segPath( a1, a2 );
 
        if( aLayer != Edge_Cuts )
        {
            for( PCB_TRACK* track : aBoard.Tracks() )
            {
                if( !track )
                    continue;
 
                if( 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 )
                    {
                        SEG segTrack( track->GetStart(), track->GetEnd() );
 
                        if( segPath.Intersects( segTrack ) )
                            return false;
                    }
                }
            }
        }
        return true;
    }
};
 
 
class GraphConnection;
class GraphNode;
class CreepageGraph;
class CREEP_SHAPE;
class BE_SHAPE;
class BE_SHAPE_POINT;
class BE_SHAPE_ARC;
class BE_SHAPE_CIRCLE;
class CU_SHAPE;
class CU_SHAPE_SEGMENT;
class CU_SHAPE_CIRCLE;
class CU_SHAPE_ARC;
 
class CREEP_SHAPE
{
public:
    enum class TYPE
    {
        UNDEFINED = 0,
        POINT,
        CIRCLE,
        ARC
    };
    CREEP_SHAPE() {};
 
    virtual ~CREEP_SHAPE() {}
 
 
    virtual int       GetRadius() const { return 0; };
    virtual EDA_ANGLE GetStartAngle() const { return EDA_ANGLE( 0 ); };
    virtual EDA_ANGLE GetEndAngle() const { return EDA_ANGLE( 0 ); };
    virtual VECTOR2I  GetStartPoint() const { return VECTOR2I( 0, 0 ); };
    virtual VECTOR2I  GetEndPoint() const { return VECTOR2I( 0, 0 ); };
    VECTOR2I          GetPos() const { return m_pos; };
    CREEP_SHAPE::TYPE GetType() const { return m_type; };
    const BOARD_ITEM* GetParent() const { return m_parent; };
    void              SetParent( BOARD_ITEM* aParent ) { m_parent = aParent; };
 
    virtual void ConnectChildren( std::shared_ptr<GraphNode>& a1, std::shared_ptr<GraphNode>& a2,
                                  CreepageGraph& aG ) const;
 
    std::vector<PATH_CONNECTION> ReversePaths( const std::vector<PATH_CONNECTION>& aV ) const
    {
        std::vector<PATH_CONNECTION> r;
        r.reserve( aV.size() );
 
        for( const auto& pc : aV )
        {
            r.emplace_back( pc );
            std::swap( r.back().a1, r.back().a2 );
        }
 
        return r;
    }
 
    std::vector<PATH_CONNECTION> Paths( const CREEP_SHAPE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const
    {
        std::vector<PATH_CONNECTION> a;
        return a;
    };
    virtual std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                                double aMaxSquaredWeight ) const
    {
        std::vector<PATH_CONNECTION> a;
        return a;
    };
    virtual std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                double aMaxSquaredWeight ) const
    {
        std::vector<PATH_CONNECTION> a;
        return a;
    };
    virtual std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                                double aMaxSquaredWeight ) const
    {
        std::vector<PATH_CONNECTION> a;
        return a;
    };
    virtual std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_SEGMENT& aS2, double aMaxWeight,
                                                double aMaxSquaredWeight ) const
    {
        std::vector<PATH_CONNECTION> a;
        return a;
    };
    virtual std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                                double aMaxSquaredWeight ) const
    {
        std::vector<PATH_CONNECTION> a;
        return a;
    };
    virtual std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                                double aMaxSquaredWeight ) const
    {
        std::vector<PATH_CONNECTION> a;
        return a;
    };
 
    //virtual std::vector<PATH_CONNECTION> GetPathsCuToBe( CREEP_SHAPE* aShape ) const{ std::vector<PATH_CONNECTION> a; return a;};
    bool IsConductive() { return m_conductive; };
 
 
protected:
    bool              m_conductive = false;
    BOARD_ITEM*       m_parent = nullptr;
    VECTOR2I          m_pos = VECTOR2I( 0, 0 );
    CREEP_SHAPE::TYPE m_type = CREEP_SHAPE::TYPE::UNDEFINED;
};
 
 
class CU_SHAPE : public CREEP_SHAPE
{
public:
    CU_SHAPE() : CREEP_SHAPE() { m_conductive = true; };
};
 
class BE_SHAPE : public CREEP_SHAPE
{
public:
    BE_SHAPE() : CREEP_SHAPE() { m_conductive = false; };
};
 
class CU_SHAPE_SEGMENT : public CU_SHAPE
{
public:
    CU_SHAPE_SEGMENT( VECTOR2I aStart, VECTOR2I aEnd, double aWidth = 0 ) : CU_SHAPE()
    {
        m_start = aStart;
        m_end = aEnd;
        m_width = aWidth;
    }
 
    VECTOR2I GetStart() const { return m_start; };
    VECTOR2I GetEnd() const { return m_end; };
    double   GetWidth() const { return m_width; };
 
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_SEGMENT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
 
 
private:
    VECTOR2I m_start = VECTOR2I( 0, 0 );
    VECTOR2I m_end = VECTOR2I( 0, 0 );
    double   m_width = 0;
};
 
class CU_SHAPE_CIRCLE : public CU_SHAPE
{
public:
    CU_SHAPE_CIRCLE( VECTOR2I aPos, double aRadius = 0 ) : CU_SHAPE()
    {
        m_pos = aPos;
        m_radius = aRadius;
    }
 
    VECTOR2I GetPos() const { return m_pos; };
    int      GetRadius() const override { return m_radius; };
 
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_SEGMENT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
 
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
 
private:
    VECTOR2I m_pos = VECTOR2I( 0, 0 );
    double   m_radius = 1;
};
 
class CU_SHAPE_ARC : public CU_SHAPE_CIRCLE
{
public:
    CU_SHAPE_ARC( VECTOR2I aPos, double aRadius, EDA_ANGLE aStartAngle, EDA_ANGLE aEndAngle,
                  VECTOR2D aStartPoint, VECTOR2D aEndPoint ) : CU_SHAPE_CIRCLE( aPos, aRadius )
    {
        m_pos = aPos;
        m_type = CREEP_SHAPE::TYPE::ARC;
        m_startAngle = aStartAngle;
        m_endAngle = aEndAngle;
        m_startPoint = aStartPoint;
        m_endPoint = aEndPoint;
        m_radius = aRadius;
    }
 
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_SEGMENT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
 
 
    EDA_ANGLE GetStartAngle() const override { return m_startAngle; }
    EDA_ANGLE GetEndAngle() const override { return m_endAngle; }
    int       GetRadius() const override { return m_radius; }
 
 
    VECTOR2I  GetStartPoint() const override { return m_startPoint; }
    VECTOR2I  GetEndPoint() const override { return m_endPoint; }
    EDA_ANGLE AngleBetweenStartAndEnd( const VECTOR2I aPoint ) const
    {
        EDA_ANGLE angle( aPoint - m_pos );
        while( angle < GetStartAngle() )
            angle += ANGLE_360;
        while( angle > GetEndAngle() + ANGLE_360 )
            angle -= ANGLE_360;
 
        return angle;
    }
    double GetWidth() const { return m_width; };
    void   SetWidth( double aW ) { m_width = aW; };
 
private:
    int       m_width = 0;
    VECTOR2I  m_pos = VECTOR2I( 0, 0 );
    double    m_radius = 1;
    EDA_ANGLE m_startAngle = EDA_ANGLE( 0 );
    EDA_ANGLE m_endAngle = EDA_ANGLE( 180 );
    VECTOR2I  m_startPoint = VECTOR2I( 1, 0 );
    VECTOR2I  m_endPoint = VECTOR2I( -1, 0 );
};
 
class GraphNode
{
public:
    enum TYPE
    {
 
        POINT = 0,
        CIRCLE,
        ARC,
        SEGMENT,
        VIRTUAL
    };
 
    GraphNode( GraphNode::TYPE aType, CREEP_SHAPE* aParent, VECTOR2I aPos = VECTOR2I() )
    {
        m_parent = aParent;
        m_pos = aPos;
        m_type = aType;
        m_connectDirectly = true;
        m_connections = {};
    };
 
    ~GraphNode() {};
 
 
    CREEP_SHAPE*                  m_parent = nullptr;
    std::vector<std::shared_ptr<GraphConnection>> m_connections = {};
    VECTOR2I                      m_pos = VECTOR2I( 0, 0 );
    // Virtual nodes are connected with a 0 weight connection to equivalent net ( same net or netclass )
    bool m_virtual = false;
    bool m_connectDirectly = true;
    int  m_net = -1;
 
    GraphNode::TYPE m_type;
};
 
class GraphConnection
{
public:
    GraphConnection( std::shared_ptr<GraphNode>& aN1, std::shared_ptr<GraphNode>& aN2,
                     const PATH_CONNECTION& aPc ) : n1( aN1 ), n2( aN2 )
    {
        m_path = aPc;
    };
 
    std::shared_ptr<GraphNode> n1 = nullptr;
    std::shared_ptr<GraphNode> n2 = nullptr;
    PATH_CONNECTION            m_path;
 
    std::vector<PCB_SHAPE> GetShapes();
    bool                   forceStraightLigne = false;
};
 
 
class BE_SHAPE_POINT : public BE_SHAPE
{
public:
    BE_SHAPE_POINT( VECTOR2I aPos ) : BE_SHAPE()
    {
        m_pos = aPos;
        m_type = CREEP_SHAPE::TYPE::POINT;
    }
 
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_SEGMENT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    }
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
 
 
    void ConnectChildren( std::shared_ptr<GraphNode>& a1, std::shared_ptr<GraphNode>& a2,
                          CreepageGraph& aG ) const override;
};
 
class BE_SHAPE_CIRCLE : public BE_SHAPE
{
public:
    BE_SHAPE_CIRCLE( VECTOR2I aPos = VECTOR2I( 0, 0 ), int aRadius = 0 ) : BE_SHAPE()
    {
        m_pos = aPos;
        m_radius = aRadius;
        m_type = CREEP_SHAPE::TYPE::CIRCLE;
    }
 
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_SEGMENT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
 
 
    int  GetRadius() const override { return m_radius; }
    void ConnectChildren( std::shared_ptr<GraphNode>& a1, std::shared_ptr<GraphNode>& a2,
                          CreepageGraph& aG ) const override;
    void ShortenChildDueToGV( std::shared_ptr<GraphNode>& a1, std::shared_ptr<GraphNode>& a2,
                              CreepageGraph& aG, double aNormalWeight ) const;
 
 
protected:
    int m_radius;
};
 
class BE_SHAPE_ARC : public BE_SHAPE_CIRCLE
{
public:
    BE_SHAPE_ARC( VECTOR2I aPos, int aRadius, EDA_ANGLE aStartAngle, EDA_ANGLE aEndAngle,
                  VECTOR2D aStartPoint, VECTOR2D aEndPoint ) : BE_SHAPE_CIRCLE( aPos, aRadius )
    {
        m_type = CREEP_SHAPE::TYPE::ARC;
        m_startAngle = aStartAngle;
        m_endAngle = aEndAngle;
        m_startPoint = aStartPoint;
        m_endPoint = aEndPoint;
        m_radius = aRadius;
    }
 
    void ConnectChildren( std::shared_ptr<GraphNode>& a1, std::shared_ptr<GraphNode>& a2,
                          CreepageGraph& aG ) const override;
 
 
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_POINT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const BE_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override;
 
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_SEGMENT& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_CIRCLE& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
    std::vector<PATH_CONNECTION> Paths( const CU_SHAPE_ARC& aS2, double aMaxWeight,
                                        double aMaxSquaredWeight ) const override
    {
        return ReversePaths( aS2.Paths( *this, aMaxWeight, aMaxSquaredWeight ) );
    };
 
 
    EDA_ANGLE GetStartAngle() const override { return m_startAngle; }
    EDA_ANGLE GetEndAngle() const override { return m_endAngle; }
    int       GetRadius() const override { return m_radius; }
 
 
    VECTOR2I  GetStartPoint() const override { return m_startPoint; }
    VECTOR2I  GetEndPoint() const override { return m_endPoint; }
    EDA_ANGLE AngleBetweenStartAndEnd( const VECTOR2I aPoint ) const
    {
        EDA_ANGLE angle( aPoint - m_pos );
 
        while( angle < m_startAngle )
            angle += ANGLE_360;
        while( angle > m_endAngle + ANGLE_360 )
            angle -= ANGLE_360;
 
        return angle;
    }
 
    std::pair<bool, bool> IsThereATangentPassingThroughPoint( const BE_SHAPE_POINT aPoint ) const;
 
protected:
    int       m_radius;
    EDA_ANGLE m_startAngle;
    EDA_ANGLE m_endAngle;
    VECTOR2I  m_startPoint;
    VECTOR2I  m_endPoint;
};
 
 
class CreepageGraph
{
public:
    CreepageGraph( BOARD& aBoard ) : m_board( aBoard )
    {
        m_boardOutline = nullptr;
        m_creepageTarget = -1;
        m_creepageTargetSquared = -1;
    };
    ~CreepageGraph()
    {
        for( CREEP_SHAPE* cs : m_shapeCollection )
            if( cs )
            {
                delete cs;
                cs = nullptr;
            }
    };
 
    BOARD&                   m_board;
    std::vector<BOARD_ITEM*> m_boardEdge;
    SHAPE_POLY_SET*          m_boardOutline;
 
    std::vector<std::shared_ptr<GraphNode>>       m_nodes;
    std::vector<std::shared_ptr<GraphConnection>> m_connections;
 
 
    void TransformEdgeToCreepShapes();
    void TransformCreepShapesToNodes( std::vector<CREEP_SHAPE*>& aShapes );
    void RemoveDuplicatedShapes();
    // Add a node to the graph. If an equivalent node exists, returns the pointer of the existing node instead
    std::shared_ptr<GraphNode>       AddNode( GraphNode::TYPE aType, CREEP_SHAPE* aParent = nullptr,
                                              VECTOR2I aPos = VECTOR2I() );
    std::shared_ptr<GraphNode>       AddNodeVirtual();
    std::shared_ptr<GraphConnection> AddConnection( std::shared_ptr<GraphNode>& aN1,
                                                    std::shared_ptr<GraphNode>& aN2,
                                                    const PATH_CONNECTION&      aPc );
    std::shared_ptr<GraphConnection> AddConnection( std::shared_ptr<GraphNode>& aN1,
                                                    std::shared_ptr<GraphNode>& aN2 );
    std::shared_ptr<GraphNode>       FindNode( GraphNode::TYPE aType, CREEP_SHAPE* aParent,
                                               VECTOR2I aPos );
 
    void RemoveConnection( std::shared_ptr<GraphConnection>, bool aDelete = false );
    void Trim( double aWeightLimit );
    void Addshape( const SHAPE& aShape, std::shared_ptr<GraphNode>& aConnectTo,
                   BOARD_ITEM* aParent = nullptr );
 
    double Solve( std::shared_ptr<GraphNode>& aFrom, std::shared_ptr<GraphNode>& aTo,
                  std::vector<std::shared_ptr<GraphConnection>>& aResult );
 
    void GeneratePaths( double aMaxWeight, PCB_LAYER_ID aLayer, bool aGenerateBoardEdges = true );
    std::shared_ptr<GraphNode> AddNetElements( int aNetCode, PCB_LAYER_ID aLayer,
                                               int aMaxCreepage );
 
    void   SetTarget( double aTarget );
    double GetTarget() { return m_creepageTarget; };
    int    m_minGrooveWidth = 0;
 
    std::vector<CREEP_SHAPE*> m_shapeCollection;
 
private:
    double m_creepageTarget;
    double m_creepageTargetSquared;
};
 
 
#endif