const SHAPE_LINE_CHAIN SHAPE_ARC::ConvertToPolyline( double aAccuracy ) const
{
    SHAPE_LINE_CHAIN rv;
    double r = GetRadius();
    double sa = GetStartAngle();
    auto c = GetCenter();
    int n;

    if( r == 0.0 )
    {
        n = 0;
    }
    else
    {
        n = GetArcToSegmentCount( r, From_User_Unit( MILLIMETRES, aAccuracy ), m_centralAngle );
    }

    for( int i = 0; i <= n ; i++ )
    {
        double a = sa + m_centralAngle * (double) i / (double) n;
        double x = c.x + r * cos( a * M_PI / 180.0 );
        double y = c.y + r * sin( a * M_PI / 180.0 );

        rv.Append( (int) x, (int) y );
    }

    return rv;
}

static void polygon_Convert( const SHAPE_LINE_CHAIN &aPath,
                             SEGMENTS &aOutSegment,
                             float aBiuTo3DunitsScale )
{
    aOutSegment.resize( aPath.PointCount() );

    for( int j = 0; j < aPath.PointCount(); j++ )
    {
        const VECTOR2I &a = aPath.CPoint( j );

        aOutSegment[j].m_Start = SFVEC2F( (float) a.x * aBiuTo3DunitsScale,
                                          (float)-a.y * aBiuTo3DunitsScale );
    }

    unsigned int i;
    unsigned int j = aOutSegment.size () - 1;

    for( i = 0; i < aOutSegment.size (); j = i++ )
    {
        // Calculate constants for each segment
        aOutSegment[i].m_inv_JY_minus_IY = 1.0f / ( aOutSegment[j].m_Start.y -
                                                    aOutSegment[i].m_Start.y );

        aOutSegment[i].m_JX_minus_IX = (aOutSegment[j].m_Start.x -
                                        aOutSegment[i].m_Start.x);
    }
}

bool PNS_LINE_PLACER::reduceTail( const VECTOR2I& aEnd )
{
    SHAPE_LINE_CHAIN& head = m_head.Line();
    SHAPE_LINE_CHAIN& tail = m_tail.Line();

    int n = tail.SegmentCount();

    if( head.SegmentCount() < 1 )
        return false;

    // Don't attempt this for too short tails
    if( n < 2 )
        return false;

    // Start from the segment farthest from the end of the tail
    // int start_index = std::max(n - 1 - ReductionDepth, 0);

    DIRECTION_45 new_direction;
    VECTOR2I new_start;
    int reduce_index = -1;

    for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
    {
        const SEG s = tail.CSegment( i );
        DIRECTION_45 dir( s );

        // calculate a replacement route and check if it matches
        // the direction of the segment to be replaced
        SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );

        PNS_LINE tmp( m_tail, replacement );

        if( m_currentNode->CheckColliding( &tmp, PNS_ITEM::ANY ) )
            break;

        if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
        {
            new_start = s.A;
            new_direction = dir;
            reduce_index = i;
        }
    }

    if( reduce_index >= 0 )
    {
        TRACE( 0, "Placer: reducing tail: %d", reduce_index );
        SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );

        m_p_start = new_start;
        m_direction = new_direction;
        tail.Remove( reduce_index + 1, -1 );
        head.Clear();
        return true;
    }

    if( !tail.SegmentCount() )
        m_direction = m_initial_direction;

    return false;
}

/**
 * Function TestLineChainEqualCPolyLine
 * tests the equality between a SHAPE_LINE_CHAIN polygon and a polygon inside a
 * CPolyLine object using Boost test suite.
 * @param lineChain is a SHAPE_LINE_CHAIN polygon object.
 * @param polyLine  is a CPolyLine polygon object.
 * @param contourIdx is the index of the contour inside polyLine that has to be tested
 *                   against lineChain.
 */
void TestLineChainEqualCPolyLine(SHAPE_LINE_CHAIN& lineChain, CPolyLine& polyLine,
                                 int contourIdx = 0)
{
    // Arrays to store the polygon points lexicographically ordered
    std::vector<VECTOR2I> chainPoints;
    std::vector<VECTOR2I> polyPoints;

    // Populate the array storing the new data with the lineChain corners
    for (int pointIdx = 0; pointIdx < lineChain.PointCount(); pointIdx++) {
        chainPoints.push_back(lineChain.Point(pointIdx));
    }

    int start = polyLine.GetContourStart(contourIdx);
    int end = polyLine.GetContourEnd(contourIdx);

    // Populate the array storing the legacy data with the polyLine corners
    for (int pointIdx = start; pointIdx <= end; pointIdx++) {
        polyPoints.push_back( VECTOR2I(polyLine.GetX(pointIdx), polyLine.GetY(pointIdx)) );
    }

    // Order the vectors in a lexicographic way
    std::sort(chainPoints.begin(), chainPoints.end(), lexicographicOrder);
    std::sort(polyPoints.begin(), polyPoints.end(), lexicographicOrder);

    // Compare every point coordinate to check the equality
    BOOST_CHECK_EQUAL_COLLECTIONS(chainPoints.begin(), chainPoints.end(),
                                  polyPoints.begin(), polyPoints.end());
}

SHAPE_LINE_CHAIN PNS_MEANDER_SHAPE::circleQuad( VECTOR2D aP, VECTOR2D aDir, bool aSide )
{
    SHAPE_LINE_CHAIN lc;

    if( aDir.EuclideanNorm( ) == 0.0f )
    {
        lc.Append( aP );
        return lc;
    }

    VECTOR2D dir_u( aDir );
    VECTOR2D dir_v( aDir.Perpendicular( ) );

    const int ArcSegments = Settings().m_cornerArcSegments;

    for( int i = ArcSegments - 1; i >= 0; i-- )
    {
        VECTOR2D p;
        double alpha = (double) i / (double) ( ArcSegments - 1 ) * M_PI / 2.0;
        p = aP + dir_u * cos( alpha ) + dir_v * ( aSide ? -1.0 : 1.0 ) * ( 1.0 - sin( alpha ) );
        lc.Append( ( int ) p.x, ( int ) p.y );
    }

    return lc;
}

static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
                            bool aNeedMTV, VECTOR2I& aMTV )
{
    bool found = false;

    for( int s = 0; s < aB.SegmentCount(); s++ )
    {
        if( aA.Collide( aB.CSegment( s ), aClearance ) )
        {
            found = true;
            break;
        }
    }

    if( !aNeedMTV || !found )
        return found;

    SHAPE_CIRCLE cmoved( aA );
    VECTOR2I f_total( 0, 0 );

    for( int s = 0; s < aB.SegmentCount(); s++ )
    {
        VECTOR2I f = pushoutForce( cmoved, aB.CSegment( s ), aClearance );
        cmoved.SetCenter( cmoved.GetCenter() + f );
        f_total += f;
    }

    aMTV = f_total;
    return found;
}

void POLYGON_GEOM_MANAGER::updateLeaderPoints( const VECTOR2I& aEndPoint )
{
    SHAPE_LINE_CHAIN newChain;

    if( m_leaderMode == LEADER_MODE::DEG45 )
    {
        // get a restricted 45/H/V line from the last fixed point to the cursor
        DIRECTION_45 direction( m_lockedPoints.back() - aEndPoint );
        newChain = direction.BuildInitialTrace( m_lockedPoints.back(), aEndPoint );

        // Can also add chain back to start, but this rearely produces
        // usable result
        //DIRECTION_45 directionToStart( aEndPoint - m_lockedPoints.front() );
        //newChain.Append( directionToStart.BuildInitialTrace( aEndPoint, m_lockedPoints.front() ) );
    }
    else
    {
        // direct segment
        newChain = SHAPE_LINE_CHAIN( m_lockedPoints.back(), aEndPoint );
    }

    // rebuild leader point list from the chain
    m_leaderPts.clear();

    for( int i = 0; i < newChain.PointCount(); ++i )
    {
        m_leaderPts.push_back( newChain.Point( i ) );
    }

    m_client.OnGeometryChange( *this );
}

bool PNS_DIFF_PAIR::BuildInitial( PNS_DP_GATEWAY& aEntry, PNS_DP_GATEWAY &aTarget, bool aPrefDiagonal )
{
    SHAPE_LINE_CHAIN p = DIRECTION_45().BuildInitialTrace ( aEntry.AnchorP(), aTarget.AnchorP(), aPrefDiagonal );
    SHAPE_LINE_CHAIN n = DIRECTION_45().BuildInitialTrace ( aEntry.AnchorN(), aTarget.AnchorN(), aPrefDiagonal );

    int mask = aEntry.AllowedAngles() | DIRECTION_45::ANG_STRAIGHT | DIRECTION_45::ANG_OBTUSE;

    SHAPE_LINE_CHAIN sum_n, sum_p;
    m_p = p;
    m_n = n;

    if( aEntry.HasEntryLines() )
    {
        if( !aEntry.Entry().CheckConnectionAngle( *this, mask ) )
            return false;

        sum_p = aEntry.Entry().CP();
        sum_n = aEntry.Entry().CN();
        sum_p.Append( p );
        sum_n.Append( n );
    }
    else
    {
        sum_p = p;
        sum_n = n;
    }

    mask = aTarget.AllowedAngles() | DIRECTION_45::ANG_STRAIGHT | DIRECTION_45::ANG_OBTUSE;

    m_p = sum_p;
    m_n = sum_n;

    if( aTarget.HasEntryLines() )
    {
        PNS_DP_GATEWAY t(aTarget) ;
        t.Reverse();

        if( !CheckConnectionAngle( t.Entry(), mask ) )
            return false;

        sum_p.Append( t.Entry().CP() );
        sum_n.Append( t.Entry().CN() );
    }

    m_p = sum_p;
    m_n = sum_n;

    if( !checkGap ( p, n, m_gapConstraint ) )
        return false;

    if( p.SelfIntersecting() || n.SelfIntersecting() )
        return false;

    if( p.Intersects( n ) )
        return false;

    return true;
}

const SHAPE_LINE_CHAIN SHAPE_POLY_SET::convertFromClipper( const Path& aPath )
{
    SHAPE_LINE_CHAIN lc;

    for( unsigned int i = 0; i < aPath.size(); i++ )
        lc.Append( aPath[i].X, aPath[i].Y );

    return lc;
}

    void AddSegment( SEG aS, int aColor )
    {
        SHAPE_LINE_CHAIN l;

        l.Append( aS.A );
        l.Append( aS.B );

        AddLine( l, aColor, 10000 );
    }

void DrawDebugSeg( SEG aS, int aColor )
{
    SHAPE_LINE_CHAIN l;

    l.Append( aS.A );
    l.Append( aS.B );

    ROUTER::GetInstance()->DisplayDebugLine( l, aColor, 10000 );
}

bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
{
    std::string tmp;

    aStream >> tmp;

    if( tmp != "polyset" )
        return false;

    aStream >> tmp;

    int n_polys = atoi( tmp.c_str() );

    if( n_polys < 0 )
        return false;

    for( int i = 0; i < n_polys; i++ )
    {
        POLYGON paths;

        aStream >> tmp;

        if( tmp != "poly" )
            return false;

        aStream >> tmp;
        int n_outlines = atoi( tmp.c_str() );

        if( n_outlines < 0 )
            return false;

        for( int j = 0; j < n_outlines; j++ )
        {
            SHAPE_LINE_CHAIN outline;

            outline.SetClosed( true );

            aStream >> tmp;
            int n_vertices = atoi( tmp.c_str() );
            for( int v = 0; v < n_vertices; v++ )
            {
                VECTOR2I p;

                aStream >> tmp; p.x = atoi( tmp.c_str() );
                aStream >> tmp; p.y = atoi( tmp.c_str() );
                outline.Append( p );
            }

            paths.push_back( outline );
        }

        m_polys.push_back( paths );
    }
    return true;
}

const SHAPE_LINE_CHAIN ConvexHull( const SHAPE_CONVEX& aConvex, int aClearance )
{
    // this defines the horizontal and vertical lines in the hull octagon
    BOX2I box = aConvex.BBox( aClearance + HULL_MARGIN );
    box.Normalize();

    SEG topline = SEG( VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ),
                       VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ) );
    SEG rightline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() + box.GetHeight() ),
                         VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ) );
    SEG bottomline = SEG( VECTOR2I( box.GetX() + box.GetWidth(), box.GetY() ),
             box.GetOrigin() );
    SEG leftline = SEG( box.GetOrigin(), VECTOR2I( box.GetX(), box.GetY() + box.GetHeight() ) );

    const SHAPE_LINE_CHAIN& vertices = aConvex.Vertices();

    // top right diagonal
    VECTOR2I corner = box.GetOrigin() + box.GetSize();
    SEG toprightline = SEG( corner,
                            corner + VECTOR2I( box.GetHeight(), -box.GetHeight() ) );
    MoveDiagonal( toprightline, vertices, aClearance );

    // bottom right diagonal
    corner = box.GetOrigin() + VECTOR2I( box.GetWidth(), 0 );
    SEG bottomrightline = SEG( corner + VECTOR2I( box.GetHeight(), box.GetHeight() ),
                               corner );
    MoveDiagonal( bottomrightline, vertices, aClearance );

    // bottom left diagonal
    corner = box.GetOrigin();
    SEG bottomleftline = SEG( corner,
                              corner + VECTOR2I( -box.GetHeight(), box.GetHeight() ) );
    MoveDiagonal( bottomleftline, vertices, aClearance );

    // top left diagonal
    corner = box.GetOrigin() + VECTOR2I( 0, box.GetHeight() );
    SEG topleftline = SEG( corner + VECTOR2I( -box.GetHeight(), -box.GetHeight() ),
                           corner );
    MoveDiagonal( topleftline, vertices, aClearance );

    SHAPE_LINE_CHAIN octagon;
    octagon.SetClosed( true );

    octagon.Append( *leftline.IntersectLines( bottomleftline ) );
    octagon.Append( *bottomline.IntersectLines( bottomleftline ) );
    octagon.Append( *bottomline.IntersectLines( bottomrightline ) );
    octagon.Append( *rightline.IntersectLines( bottomrightline ) );
    octagon.Append( *rightline.IntersectLines( toprightline ) );
    octagon.Append( *topline.IntersectLines( toprightline ) );
    octagon.Append( *topline.IntersectLines( topleftline ) );
    octagon.Append( *leftline.IntersectLines( topleftline ) );

    return octagon;
}

static inline bool Collide( const SHAPE_CIRCLE& aA, const SHAPE_LINE_CHAIN& aB, int aClearance,
                            bool aNeedMTV, VECTOR2I& aMTV )
{
    for( int s = 0; s < aB.SegmentCount(); s++ )
    {
        if( aA.Collide( aB.CSegment( s ), aClearance ) )
            return true;
    }

    return false;
}

void PNS_LINE::Walkaround( const SHAPE_LINE_CHAIN& aObstacle,
        SHAPE_LINE_CHAIN& aPath,
        bool aCw ) const
{
    SHAPE_LINE_CHAIN walk, post;

    Walkaround( aObstacle, aPath, walk, post, aCw );
    aPath.Append( walk );
    aPath.Append( post );
    aPath.Simplify();
}

static void drawGw( VECTOR2I p, int color )
{
    SHAPE_LINE_CHAIN l;

    l.Append( p - VECTOR2I( -50000, -50000 ) );
    l.Append( p + VECTOR2I( -50000, -50000 ) );

    l.Clear();
    l.Append( p - VECTOR2I( 50000, -50000 ) );
    l.Append( p + VECTOR2I( 50000, -50000 ) );
}

SHAPE_LINE_CHAIN dragCornerInternal( const SHAPE_LINE_CHAIN& aOrigin, const VECTOR2I& aP )
{
    optional<SHAPE_LINE_CHAIN> picked;
    int i;

    int d = 2;

    if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
        d = 1;

    for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
    {
        DIRECTION_45 d_start ( aOrigin.CSegment( i ) );
        VECTOR2I p_start = aOrigin.CPoint( i );
        SHAPE_LINE_CHAIN paths[2];
        DIRECTION_45 dirs[2];
        DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i - 1 ) ) : DIRECTION_45() );

        for( int j = 0; j < 2; j++ )
        {
            paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
            dirs[j] = DIRECTION_45( paths[j].CSegment( 0 ) );
        }

        for( int j = 0; j < 2; j++ )
        {
            if( dirs[j] == d_start )
            {
                picked = paths[j];
                break;
            }
        }

        if( picked )
            break;

        for( int j = 0; j < 2; j++ )
        {
            if( dirs[j].IsObtuse( d_prev ) )
            {
                picked = paths[j];
                break;
            }
        }

        if( picked )
            break;
    }

    if( picked )
    {
        SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
        path.Append( *picked );

        return path;
    }

    return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, true );
}

const ClipperLib::Path SHAPE_POLY_SET::convert( const SHAPE_LINE_CHAIN& aPath )
{
    Path c_path;

    for(int i = 0; i < aPath.PointCount(); i++)
    {
        const VECTOR2I& vertex = aPath.CPoint(i);
        c_path.push_back(ClipperLib::IntPoint ( vertex.x, vertex.y ) );
    }

    return c_path;
}

const SHAPE_LINE_CHAIN SegmentHull ( const SHAPE_SEGMENT& aSeg, int aClearance,
                                     int aWalkaroundThickness )
{
    int d = aSeg.GetWidth() / 2 + aClearance + aWalkaroundThickness / 2 + HULL_MARGIN;
    int x = (int)( 2.0 / ( 1.0 + M_SQRT2 ) * d );

    const VECTOR2I a = aSeg.GetSeg().A;
    const VECTOR2I b = aSeg.GetSeg().B;

    VECTOR2I dir = b - a;
    VECTOR2I p0 = dir.Perpendicular().Resize( d );
    VECTOR2I ds = dir.Perpendicular().Resize( x / 2 );
    VECTOR2I pd = dir.Resize( x / 2 );
    VECTOR2I dp = dir.Resize( d );

    SHAPE_LINE_CHAIN s;

    s.SetClosed( true );

    s.Append( b + p0 + pd );
    s.Append( b + dp + ds );
    s.Append( b + dp - ds );
    s.Append( b - p0 + pd );
    s.Append( a - p0 - pd );
    s.Append( a - dp - ds );
    s.Append( a - dp + ds );
    s.Append( a + p0 - pd );

    // make sure the hull outline is always clockwise
    if( s.CSegment( 0 ).Side( a ) < 0 )
        return s.Reverse();
    else
        return s;
}

void DrawDebugPoint( VECTOR2I aP, int aColor )
{
    SHAPE_LINE_CHAIN l;

    l.Append( aP - VECTOR2I( -50000, -50000 ) );
    l.Append( aP + VECTOR2I( -50000, -50000 ) );

    ROUTER::GetInstance()->DisplayDebugLine ( l, aColor, 10000 );

    l.Clear();
    l.Append( aP - VECTOR2I( 50000, -50000 ) );
    l.Append( aP + VECTOR2I( 50000, -50000 ) );

    ROUTER::GetInstance()->DisplayDebugLine( l, aColor, 10000 );
}