shape_line_chain.h

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2013 CERN
 * @author Tomasz Wlostowski <[email protected]>
 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#ifndef __SHAPE_LINE_CHAIN
#define __SHAPE_LINE_CHAIN
 
 
#include <clipper2/clipper.h>
#include <geometry/seg.h>
#include <geometry/shape.h>
#include <geometry/shape_arc.h>
#include <geometry/corner_strategy.h>
#include <math/vector2d.h>

struct CLIPPER_Z_VALUE
{
    CLIPPER_Z_VALUE()
    {
        m_FirstArcIdx = -1;
        m_SecondArcIdx = -1;
    }
 
    CLIPPER_Z_VALUE( const std::pair<ssize_t, ssize_t> aShapeIndices, ssize_t aOffset = 0 )
    {
        m_FirstArcIdx = aShapeIndices.first;
        m_SecondArcIdx = aShapeIndices.second;
 
        auto offsetVal = [&]( ssize_t& aVal )
                         {
                             if( aVal >= 0 )
                                 aVal += aOffset;
                         };
 
        offsetVal( m_FirstArcIdx );
        offsetVal( m_SecondArcIdx );
    }
 
    ssize_t m_FirstArcIdx;
    ssize_t m_SecondArcIdx;
};
 

class SHAPE_LINE_CHAIN : public SHAPE_LINE_CHAIN_BASE
{
public:
    typedef std::vector<VECTOR2I>::iterator point_iter;
    typedef std::vector<VECTOR2I>::const_iterator point_citer;

    struct INTERSECTION
    {
        VECTOR2I p;

        int index_our;

        int index_their;

        bool is_corner_our;

        bool is_corner_their;

        bool valid;
 
        INTERSECTION() :
            index_our( -1 ),
            index_their( -1 ),
            is_corner_our( false ),
            is_corner_their( false ),
            valid( false )
        {
        }
    };
 

    class POINT_INSIDE_TRACKER
    {
    public:
        POINT_INSIDE_TRACKER( const VECTOR2I& aPoint );
 
        void AddPolyline( const SHAPE_LINE_CHAIN& aPolyline );
        bool IsInside();
 
    private:
 
        bool processVertex ( const VECTOR2I& ip, const VECTOR2I& ipNext );
 
        VECTOR2I m_point;
        VECTOR2I m_lastPoint;
        VECTOR2I m_firstPoint;
        bool m_finished;
        int m_state;
        int m_count;
    };
 
    typedef std::vector<INTERSECTION> INTERSECTIONS;
 

    SHAPE_LINE_CHAIN() :
            SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ),
            m_accuracy( 0 ),
            m_closed( false ),
            m_width( 0 )
    {}
 
    SHAPE_LINE_CHAIN( const SHAPE_LINE_CHAIN& aShape ) :
            SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ),
            m_points( aShape.m_points ),
            m_shapes( aShape.m_shapes ),
            m_arcs( aShape.m_arcs ),
            m_accuracy( aShape.m_accuracy ),
            m_closed( aShape.m_closed ),
            m_width( aShape.m_width ),
            m_bbox( aShape.m_bbox )
    {}
 
    SHAPE_LINE_CHAIN( const std::vector<int>& aV );
 
    SHAPE_LINE_CHAIN( const std::vector<VECTOR2I>& aV, bool aClosed = false );
 
    SHAPE_LINE_CHAIN( const SHAPE_ARC& aArc, bool aClosed = false, std::optional<int> aMaxError = {} );
 
    SHAPE_LINE_CHAIN( const Clipper2Lib::Path64& aPath,
                      const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
                      const std::vector<SHAPE_ARC>& aArcBuffer );
 
    virtual ~SHAPE_LINE_CHAIN()
    {}

    virtual bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
                          VECTOR2I* aLocation = nullptr ) const override;

    virtual bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
                          VECTOR2I* aLocation = nullptr ) const override;

    bool ClosestPoints( const SHAPE_LINE_CHAIN& aOther, VECTOR2I& aPt0, VECTOR2I& aPt1 ) const;
 
    static bool ClosestPoints( const point_citer& aMyStart, const point_citer& aMyEnd,
                               const point_citer& aOtherStart, const point_citer& aOtherEnd,
                               VECTOR2I& aPt0, VECTOR2I& aPt1, int64_t& aDistSq );
 
    static bool ClosestSegments( const VECTOR2I& aMyPrevPt, const point_citer& aMyStart,
                                 const point_citer& aMyEnd, const VECTOR2I& aOtherPrevPt,
                                 const point_citer& aOtherStart, const point_citer& aOtherEnd,
                                 VECTOR2I& aPt0, VECTOR2I& aPt1, int64_t& aDistSq );

    bool ClosestSegmentsFast( const SHAPE_LINE_CHAIN& aOther, VECTOR2I& aPt0,
                              VECTOR2I& aPt1 ) const;
 
    SHAPE_LINE_CHAIN& operator=( const SHAPE_LINE_CHAIN& ) = default;
 
    // Move assignment operator
    SHAPE_LINE_CHAIN& operator=( SHAPE_LINE_CHAIN&& aOther ) noexcept
    {
        if (this != &aOther)
        {
            SHAPE_LINE_CHAIN_BASE::operator=( aOther );
 
            m_points = std::move( aOther.m_points );
            m_shapes = std::move( aOther.m_shapes );
            m_arcs = std::move( aOther.m_arcs );
 
            m_accuracy = aOther.m_accuracy;
            m_closed = aOther.m_closed;
            m_width = aOther.m_width;
            m_bbox = aOther.m_bbox;
        }
 
        return *this;
    }
 
    SHAPE* Clone() const override;

    void Clear()
    {
        m_points.clear();
        m_arcs.clear();
        m_shapes.clear();
        m_closed = false;
    }

    void SetClosed( bool aClosed )
    {
        m_closed = aClosed;
        mergeFirstLastPointIfNeeded();
    }

    bool IsClosed() const override
    {
        return m_closed;
    }

    void SetWidth( int aWidth ) override
    {
        m_width = aWidth;
    }

    int Width() const
    {
        return m_width;
    }

    int SegmentCount() const
    {
        int c = m_points.size() - 1;
 
        if( m_closed )
            c++;
 
        return std::max( 0, c );
    }

    int ShapeCount() const;
 

    void RemoveDuplicatePoints();

    void Simplify( int aTolerance = 0 );
 
    // legacy function, used by the router. Please do not remove until I'll figure out
    // the root cause of rounding errors - Tom
    SHAPE_LINE_CHAIN& Simplify2( bool aRemoveColinear = true );

    int PointCount() const
    {
        return m_points.size();
    }

    SEG Segment( int aIndex ) const;

    const SEG CSegment( int aIndex ) const { return Segment( aIndex ); }

    int NextShape( int aPointIndex ) const;

    void SetPoint( int aIndex, const VECTOR2I& aPos );

    const VECTOR2I& CPoint( int aIndex ) const
    {
        if( aIndex < 0 )
            aIndex += PointCount();
        else if( aIndex >= PointCount() )
            aIndex -= PointCount();
 
        return m_points[aIndex];
    }
 
    const std::vector<VECTOR2I>& CPoints() const { return m_points; }

    const VECTOR2I& CLastPoint() const
    {
        return m_points[static_cast<size_t>( PointCount() ) - 1];
    }

    const std::vector<SHAPE_ARC>& CArcs() const
    {
        return m_arcs;
    }

    const std::vector<std::pair<ssize_t, ssize_t>>& CShapes() const
    {
        return m_shapes;
    }

    const BOX2I BBox( int aClearance = 0 ) const override
    {
        BOX2I bbox;
        bbox.Compute( m_points );
 
        if( aClearance != 0 || m_width != 0 )
            bbox.Inflate( aClearance + m_width );
 
        return bbox;
    }
 
    void GenerateBBoxCache() const
    {
        m_bbox.Compute( m_points );
 
        if( m_width != 0 )
            m_bbox.Inflate( m_width );
    }
 
    BOX2I* GetCachedBBox() const override
    {
        return &m_bbox;
    }

    const SHAPE_LINE_CHAIN Reverse() const;

    void ClearArcs();

    long long int Length() const;

    void ReservePoints( size_t aSize )
    {
        m_points.reserve( aSize );
        m_shapes.reserve( aSize );
    }

    void Append( int aX, int aY, bool aAllowDuplication = false )
    {
        VECTOR2I v( aX, aY );
        Append( v, aAllowDuplication );
    }

    void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
    {
        if( m_points.size() == 0 )
            m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
 
        if( m_points.size() == 0 || aAllowDuplication || CLastPoint() != aP )
        {
            m_points.push_back( aP );
            m_shapes.push_back( SHAPES_ARE_PT );
            m_bbox.Merge( aP );
        }
    }

    void Append( const SHAPE_LINE_CHAIN& aOtherLine );
 
    void Append( const SHAPE_ARC& aArc );
    void Append( const SHAPE_ARC& aArc, int aMaxError );
 
    void Insert( size_t aVertex, const VECTOR2I& aP );
 
    void Insert( size_t aVertex, const SHAPE_ARC& aArc );
    void Insert( size_t aVertex, const SHAPE_ARC& aArc, int aMaxError );

    void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );

    void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );

    void Remove( int aStartIndex, int aEndIndex );

    void Remove( int aIndex )
    {
        Remove( aIndex, aIndex );
    }

    void RemoveShape( int aPointIndex );

    int Split( const VECTOR2I& aP, bool aExact = false );

    int Find( const VECTOR2I& aP, int aThreshold = 0 ) const;

    int FindSegment( const VECTOR2I& aP, int aThreshold = 1 ) const;

    const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex ) const;
    const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex, int aMaxError ) const;
 
    struct compareOriginDistance
    {
        compareOriginDistance( const VECTOR2I& aOrigin ):
            m_origin( aOrigin )
        {}
 
        bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
        {
            return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
        }
 
        VECTOR2I m_origin;
    };
 
    bool Intersects( const SEG& aSeg) const;
    bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;

    int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;

    int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp,
                   bool aExcludeColinearAndTouching = false,
                   BOX2I* aChainBBox = nullptr ) const;

    int PathLength( const VECTOR2I& aP, int aIndex = -1 ) const;

    bool CheckClearance( const VECTOR2I& aP, const int aDist) const;

    const std::optional<INTERSECTION> SelfIntersecting() const;

    const std::optional<INTERSECTION> SelfIntersectingWithArcs() const;

    int NearestSegment( const VECTOR2I& aP ) const;

    const VECTOR2I NearestPoint( const VECTOR2I& aP, bool aAllowInternalShapePoints = true ) const;

    const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;

    const std::string Format( bool aCplusPlus = true ) const override;

    bool Parse( std::stringstream& aStream ) override;
 
    bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
    {
        if( PointCount() != aRhs.PointCount() )
            return true;
 
        for( int i = 0; i < PointCount(); i++ )
        {
            if( CPoint( i ) != aRhs.CPoint( i ) )
                return true;
        }
 
        return false;
    }

    bool CompareGeometry( const SHAPE_LINE_CHAIN& aOther, bool aCyclicalCompare = false, int aEpsilon = 0 ) const;
 
    void Move( const VECTOR2I& aVector ) override
    {
        for( auto& pt : m_points )
            pt += aVector;
 
        for( auto& arc : m_arcs )
            arc.Move( aVector );
 
        m_bbox.Move( aVector );
    }

    void Mirror( const VECTOR2I& aRef, FLIP_DIRECTION aFlipDirection );

    void Mirror( const SEG& axis );

    void Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
 
    bool IsSolid() const override
    {
        return false;
    }
 
    const VECTOR2I PointAlong( int aPathLength ) const;

    double Area( bool aAbsolute = true ) const;

    void Split( const VECTOR2I& aStart, const VECTOR2I& aEnd, SHAPE_LINE_CHAIN& aPre,
                SHAPE_LINE_CHAIN& aMid, SHAPE_LINE_CHAIN& aPost ) const;

    bool OffsetLine( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
                     SHAPE_LINE_CHAIN& aLeft, SHAPE_LINE_CHAIN& aRight,
                     bool aSimplify = false ) const;
 
    size_t ArcCount() const
    {
        return m_arcs.size();
    }

    ssize_t ArcIndex( size_t aSegment ) const
    {
        if( IsSharedPt( aSegment ) )
            return m_shapes[aSegment].second;
        else
            return m_shapes[aSegment].first;
    }
 
    const SHAPE_ARC& Arc( size_t aArc ) const
    {
        return m_arcs[aArc];
    }

    bool IsSharedPt( size_t aIndex ) const;
 
    bool IsPtOnArc( size_t aPtIndex ) const;
 
    bool IsArcSegment( size_t aSegment ) const;
 
    bool IsArcStart( size_t aIndex ) const;
 
    bool IsArcEnd( size_t aIndex ) const;
 
    using SHAPE::Distance;
 
    int Distance( const VECTOR2I& aP, bool aOutlineOnly ) const
    {
        return sqrt( SquaredDistance( aP, aOutlineOnly ) );
    }
 
    virtual const VECTOR2I GetPoint( int aIndex ) const override { return CPoint(aIndex); }
    virtual const SEG GetSegment( int aIndex ) const override { return CSegment(aIndex); }
    virtual size_t GetPointCount() const override { return PointCount(); }
    virtual size_t GetSegmentCount() const override { return SegmentCount(); }
 
    bool PointInside( const VECTOR2I& aPt, int aAccuracy = 0,
                      bool aUseBBoxCache = false ) const override;
 
    void TransformToPolygon( SHAPE_POLY_SET& aBuffer, int aError,
                             ERROR_LOC aErrorLoc ) const override;
 
protected:
    friend class SHAPE_POLY_SET;

    void convertArc( ssize_t aArcIndex );

    void splitArc( ssize_t aPtIndex, bool aCoincident = false );
 
    void amendArc( size_t aArcIndex, const VECTOR2I& aNewStart, const VECTOR2I& aNewEnd );
 
    void amendArcStart( size_t aArcIndex, const VECTOR2I& aNewStart )
    {
        amendArc( aArcIndex, aNewStart, m_arcs[aArcIndex].GetP1() );
    }
 
    void amendArcEnd( size_t aArcIndex, const VECTOR2I& aNewEnd )
    {
        amendArc( aArcIndex, m_arcs[aArcIndex].GetP0(), aNewEnd );
    }

    ssize_t reversedArcIndex( size_t aSegment ) const
    {
        if( IsSharedPt( aSegment ) )
            return m_shapes[aSegment].first;
        else
            return m_shapes[aSegment].second;
    }

    Clipper2Lib::Path64 convertToClipper2( bool aRequiredOrientation,
            std::vector<CLIPPER_Z_VALUE> &aZValueBuffer,
            std::vector<SHAPE_ARC> &aArcBuffer ) const;

    void fixIndicesRotation();

    void mergeFirstLastPointIfNeeded();
 
private:
 
    static const ssize_t SHAPE_IS_PT;
 
    static const std::pair<ssize_t, ssize_t> SHAPES_ARE_PT;

    std::vector<VECTOR2I> m_points;

    std::vector<std::pair<ssize_t, ssize_t>> m_shapes;
 
    std::vector<SHAPE_ARC> m_arcs;
 
    // the maxError to use when converting arcs to points
    int m_accuracy;

    bool m_closed;

    int m_width;

    mutable BOX2I m_bbox;
};
 
 
#endif // __SHAPE_LINE_CHAIN