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 (C) 2013-2022 KiCad Developers, see AUTHORS.txt for contributors.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
#ifndef __SHAPE_LINE_CHAIN
#define __SHAPE_LINE_CHAIN
 
 
#include <clipper.hpp>
#include <clipper2/clipper.h>
#include <geometry/seg.h>
#include <geometry/shape.h>
#include <geometry/shape_arc.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
{
private:
 typedef std::vector<VECTOR2I>::iterator point_iter;
 typedef std::vector<VECTOR2I>::const_iterator point_citer;
 
public:
 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_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_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_BASE( SH_LINE_CHAIN ),
 m_closed( aClosed ),
 m_width( 0 )
 {
 m_points = aV;
 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
 }
 
 SHAPE_LINE_CHAIN( const SHAPE_ARC& aArc, bool aClosed = false ) :
 SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ),
 m_closed( aClosed ),
 m_width( 0 )
 {
 m_points = aArc.ConvertToPolyline().CPoints();
 m_arcs.emplace_back( aArc );
 m_arcs.back().SetWidth( 0 );
 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( m_points.size(), { 0, SHAPE_IS_PT } );
 }
 
 SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath,
 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
 const std::vector<SHAPE_ARC>& aArcBuffer );
 
 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;
 
 SHAPE_LINE_CHAIN& operator=( const SHAPE_LINE_CHAIN& ) = default;
 
 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 )
 {
 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;
 
 int PointCount() const
 {
 return m_points.size();
 }
 
 SEG Segment( int aIndex )
 {
 if( aIndex < 0 )
 aIndex += SegmentCount();
 
 if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
 return SEG( m_points[aIndex], m_points[0], aIndex );
 else
 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
 }
 
 const SEG CSegment( int aIndex ) const
 {
 if( aIndex < 0 )
 aIndex += SegmentCount();
 
 if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
 return SEG( m_points[aIndex], m_points[0], aIndex );
 else
 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
 }
 
 int NextShape( int aPointIndex, bool aForwards = true ) const;
 
 int PrevShape( int aPointIndex ) const
 {
 return NextShape( aPointIndex, false );
 }
 
 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;
 }
 
 int Distance( const VECTOR2I& aP, bool aOutlineOnly = false ) const;
 
 const SHAPE_LINE_CHAIN Reverse() const;
 
 void ClearArcs();
 
 long long int Length() const;
 
 void ReservePoints( size_t aSize )
 {
 m_points.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 || CPoint( -1 ) != 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, double aAccuracy );
 
 void Insert( size_t aVertex, const VECTOR2I& aP );
 
 void Insert( size_t aVertex, const SHAPE_ARC& aArc );
 
 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 );
 
 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 = -1 ) 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 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;
 
 SHAPE_LINE_CHAIN& Simplify( bool aRemoveColinear = true );
 
 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 ) 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( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
 
 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;
 
 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
 {
 return aIndex < m_shapes.size()
 && m_shapes[aIndex].first != SHAPE_IS_PT
 && m_shapes[aIndex].second != SHAPE_IS_PT;
 }
 
 
 bool IsPtOnArc( size_t aPtIndex ) const
 {
 return aPtIndex < m_shapes.size() && m_shapes[aPtIndex] != SHAPES_ARE_PT;
 }
 
 
 bool IsArcSegment( size_t aSegment ) const
 {
 /*
 * A segment is part of an arc except in the special case of two arcs next to each other
 * but without a shared vertex. Here there is a segment between the end of the first arc
 * and the start of the second arc.
 */
 size_t nextIdx = aSegment + 1;
 
 if( nextIdx > m_shapes.size() - 1 )
 {
 if( nextIdx == m_shapes.size() && m_closed )
 nextIdx = 0; // segment between end point and first point
 else
 return false;
 }
 
 return ( IsPtOnArc( aSegment )
 && ( IsSharedPt( aSegment )
 || m_shapes[aSegment].first == m_shapes[nextIdx].first ) );
 }
 
 
 bool IsArcStart( size_t aIndex ) const
 {
 if( aIndex == 0 )
 return IsPtOnArc( aIndex );
 
 return ( IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex - 1 ) ) );
 }
 
 
 bool IsArcEnd( size_t aIndex ) const
 {
 return ( IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex ) ) );
 }
 
 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(); }
 
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;
 }
 
 ClipperLib::Path convertToClipper( bool aRequiredOrientation,
 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
 std::vector<SHAPE_ARC>& aArcBuffer ) const;
 
 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;
 
 bool m_closed;
 
 int m_width;
 
 mutable BOX2I m_bbox;
};
 
 
#endif // __SHAPE_LINE_CHAIN