shape_poly_set.h

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2015-2019 CERN
 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
 *
 * @author Tomasz Wlostowski <[email protected]>
 * @author Alejandro García Montoro <[email protected]>
 *
 * 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_POLY_SET_H
#define __SHAPE_POLY_SET_H
 
#include <atomic>
#include <cstdio>
#include <deque>                        // for deque
#include <functional>
#include <iosfwd>                       // for string, stringstream
#include <memory>
#include <mutex>
#include <set>                          // for set
#include <stdexcept>                    // for out_of_range
#include <stdlib.h>                     // for abs
#include <vector>
 
#include <clipper2/clipper.h>
#include <core/mirror.h>                // for FLIP_DIRECTION
#include <geometry/corner_strategy.h>
#include <geometry/seg.h>               // for SEG
#include <geometry/shape.h>
#include <geometry/shape_line_chain.h>
#include <math/box2.h>                  // for BOX2I
#include <math/vector2d.h>              // for VECTOR2I
#include <hash_128.h>
 

class SHAPE_POLY_SET : public SHAPE
{
public:
    typedef std::function<void( std::function<void()> )> TASK_SUBMITTER;

    typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
 
    class TRIANGULATED_POLYGON
    {
    public:
        struct TRI : public SHAPE_LINE_CHAIN_BASE
        {
            TRI( int _a = 0, int _b = 0, int _c = 0, TRIANGULATED_POLYGON* aParent = nullptr ) :
                SHAPE_LINE_CHAIN_BASE( SH_POLY_SET_TRIANGLE ),
                a( _a ),
                b( _b ),
                c( _c ),
                parent( aParent )
            {
            }
 
            virtual void Rotate( const EDA_ANGLE& aAngle,
                                 const VECTOR2I& aCenter = { 0, 0 } ) override {};
 
            virtual void Move( const VECTOR2I& aVector ) override {};
 
            virtual bool IsSolid() const override { return true; }
 
            virtual bool IsClosed() const override { return true; }
 
            virtual const BOX2I BBox( int aClearance = 0 ) const override;
 
            virtual const VECTOR2I GetPoint( int aIndex ) const override
            {
                switch(aIndex)
                {
                    case 0: return parent->m_vertices[a];
                    case 1: return parent->m_vertices[b];
                    case 2: return parent->m_vertices[c];
                    default: wxCHECK( false, VECTOR2I() );
                }
            }
 
            virtual const SEG GetSegment( int aIndex ) const override
            {
                switch(aIndex)
                {
                    case 0: return SEG( parent->m_vertices[a], parent->m_vertices[b] );
                    case 1: return SEG( parent->m_vertices[b], parent->m_vertices[c] );
                    case 2: return SEG( parent->m_vertices[c], parent->m_vertices[a] );
                    default: wxCHECK( false, SEG() );
                }
            }
 
            virtual size_t GetPointCount() const override { return 3; }
            virtual size_t GetSegmentCount() const override { return 3; }
 
            double Area() const
            {
                VECTOR2I& aa = parent->m_vertices[a];
                VECTOR2I& bb = parent->m_vertices[b];
                VECTOR2I& cc = parent->m_vertices[c];
 
                VECTOR2D ba = bb - aa;
                VECTOR2D cb = cc - bb;
 
                return std::abs( cb.Cross( ba ) * 0.5 );
            }
 
            int                   a;
            int                   b;
            int                   c;
            TRIANGULATED_POLYGON* parent;
        };
 
        TRIANGULATED_POLYGON( int aSourceOutline );
        TRIANGULATED_POLYGON( const TRIANGULATED_POLYGON& aOther );
        ~TRIANGULATED_POLYGON();
 
        void Clear()
        {
            m_vertices.clear();
            m_triangles.clear();
        }
 
        void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
        {
            auto& tri = m_triangles[ index ];
            a = m_vertices[ tri.a ];
            b = m_vertices[ tri.b ];
            c = m_vertices[ tri.c ];
        }
 
        TRIANGULATED_POLYGON& operator=( const TRIANGULATED_POLYGON& aOther );
 
        // Move assignment operator.
        TRIANGULATED_POLYGON& operator=( TRIANGULATED_POLYGON&& aOther ) noexcept
        {
            if( this != &aOther )
            {
                m_sourceOutline = aOther.m_sourceOutline;
                m_triangles = std::move( aOther.m_triangles );
                m_vertices = std::move( aOther.m_vertices );
 
                for( TRI& tri : m_triangles )
                    tri.parent = this;
            }
 
            return *this;
        }
 
        void AddTriangle( int a, int b, int c );
 
        void AddVertex( const VECTOR2I& aP )
        {
            m_vertices.push_back( aP );
        }
 
        size_t GetTriangleCount() const { return m_triangles.size(); }
 
        int GetSourceOutlineIndex() const { return m_sourceOutline; }
        void SetSourceOutlineIndex( int aIndex ) { m_sourceOutline = aIndex; }
 
        const std::deque<TRI>& Triangles() const { return m_triangles; }
        void SetTriangles( const std::deque<TRI>& aTriangles )
        {
            m_triangles.resize( aTriangles.size() );
 
            for( size_t ii = 0; ii < aTriangles.size(); ii++ )
            {
                m_triangles[ii] = aTriangles[ii];
                m_triangles[ii].parent = this;
            }
        }
 
        const std::deque<VECTOR2I>& Vertices() const { return m_vertices; }
        void SetVertices( const std::deque<VECTOR2I>& aVertices )
        {
            m_vertices = aVertices;
        }
 
        size_t GetVertexCount() const
        {
            return m_vertices.size();
        }
 
        void Move( const VECTOR2I& aVec )
        {
            for( VECTOR2I& vertex : m_vertices )
                vertex += aVec;
        }
 
    private:
        int                  m_sourceOutline;
        std::deque<TRI>      m_triangles;
        std::deque<VECTOR2I> m_vertices;
    };

    struct VERTEX_INDEX
    {
        int m_polygon;   
        int m_contour;   
        int m_vertex;    
 
        VERTEX_INDEX() :
            m_polygon(-1),
            m_contour(-1),
            m_vertex(-1)
        {
        }
    };

    template <class T>
    class ITERATOR_TEMPLATE
    {
    public:

        bool IsEndContour() const
        {
            return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
        }

        bool IsLastPolygon() const
        {
            return m_currentPolygon == m_lastPolygon;
        }
 
        operator bool() const
        {
            if( m_currentPolygon < m_lastPolygon )
                return true;
 
            if( m_currentPolygon != m_poly->OutlineCount() - 1 )
                return false;
 
            const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
 
            return m_currentContour < (int) currentPolygon.size() - 1
                       || m_currentVertex < currentPolygon[m_currentContour].PointCount();
        }

        void Advance()
        {
            // Advance vertex index
            m_currentVertex ++;
 
            // Check whether the user wants to iterate through the vertices of the holes
            // and behave accordingly
            if( m_iterateHoles )
            {
                // If the last vertex of the contour was reached, advance the contour index
                if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount() )
                {
                    m_currentVertex = 0;
                    m_currentContour++;
 
                    // If the last contour of the current polygon was reached, advance the
                    // outline index
                    int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
 
                    if( m_currentContour >= totalContours )
                    {
                        m_currentContour = 0;
                        m_currentPolygon++;
                    }
                }
            }
            else
            {
                // If the last vertex of the outline was reached, advance to the following polygon
                if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
                {
                    m_currentVertex = 0;
                    m_currentPolygon++;
                }
            }
        }
 
        void operator++( int dummy )
        {
            Advance();
        }
 
        void operator++()
        {
            Advance();
        }
 
        const T& Get()
        {
            return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint( m_currentVertex );
        }
 
        const T& operator*()
        {
            return Get();
        }
 
        const T* operator->()
        {
            return &Get();
        }

        VERTEX_INDEX GetIndex()
        {
            VERTEX_INDEX index;
 
            index.m_polygon = m_currentPolygon;
            index.m_contour = m_currentContour;
            index.m_vertex = m_currentVertex;
 
            return index;
        }
 
    private:
        friend class SHAPE_POLY_SET;
 
        SHAPE_POLY_SET* m_poly;
        int             m_currentPolygon;
        int             m_currentContour;
        int             m_currentVertex;
        int             m_lastPolygon;
        bool            m_iterateHoles;
    };

    template <class T>
    class SEGMENT_ITERATOR_TEMPLATE
    {
    public:
        bool IsLastPolygon() const
        {
            return m_currentPolygon == m_lastPolygon;
        }
 
        operator bool() const
        {
            return m_currentPolygon <= m_lastPolygon;
        }

        void Advance()
        {
            // Advance vertex index
            m_currentSegment++;
            int last;
 
            // Check whether the user wants to iterate through the vertices of the holes
            // and behave accordingly.
            if( m_iterateHoles )
            {
                last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
 
                // If the last vertex of the contour was reached, advance the contour index.
                if( m_currentSegment >= last )
                {
                    m_currentSegment = 0;
                    m_currentContour++;
 
                    // If the last contour of the current polygon was reached, advance the
                    // outline index.
                    int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
 
                    if( m_currentContour >= totalContours )
                    {
                        m_currentContour = 0;
                        m_currentPolygon++;
                    }
                }
            }
            else
            {
                last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
                // If the last vertex of the outline was reached, advance to the following
                // polygon
                if( m_currentSegment >= last )
                {
                    m_currentSegment = 0;
                    m_currentPolygon++;
                }
            }
        }
 
        void operator++( int dummy )
        {
            Advance();
        }
 
        void operator++()
        {
            Advance();
        }
 
        T Get()
        {
            return m_poly->Polygon( m_currentPolygon )[m_currentContour].Segment( m_currentSegment );
        }
 
        T operator*()
        {
            return Get();
        }

        VERTEX_INDEX GetIndex() const
        {
            VERTEX_INDEX index;
 
            index.m_polygon = m_currentPolygon;
            index.m_contour = m_currentContour;
            index.m_vertex = m_currentSegment;
 
            return index;
        }

        bool IsAdjacent( SEGMENT_ITERATOR_TEMPLATE<T> aOther ) const
        {
            // Check that both iterators point to the same contour of the same polygon of the
            // same polygon set.
            if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
                m_currentContour == aOther.m_currentContour )
            {
                // Compute the total number of segments.
                int numSeg;
                numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
 
                // Compute the difference of the segment indices. If it is exactly one, they
                // are adjacent. The only missing case where they also are adjacent is when
                // the segments are the first and last one, in which case the difference
                // always equals the total number of segments minus one.
                int indexDiff = std::abs( m_currentSegment - aOther.m_currentSegment );
 
                return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
            }
 
            return false;
        }
 
    private:
        friend class SHAPE_POLY_SET;
 
        SHAPE_POLY_SET* m_poly;
        int             m_currentPolygon;
        int             m_currentContour;
        int             m_currentSegment;
        int             m_lastPolygon;
        bool            m_iterateHoles;
    };
 
    // Iterator and const iterator types to visit polygon's points.
    typedef ITERATOR_TEMPLATE<VECTOR2I> ITERATOR;
    typedef ITERATOR_TEMPLATE<const VECTOR2I> CONST_ITERATOR;
 
    // Iterator and const iterator types to visit polygon's edges.
    typedef SEGMENT_ITERATOR_TEMPLATE<SEG> SEGMENT_ITERATOR;
    typedef SEGMENT_ITERATOR_TEMPLATE<const SEG> CONST_SEGMENT_ITERATOR;
 
    SHAPE_POLY_SET();
 
    SHAPE_POLY_SET( const BOX2D& aRect );

    SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );

    SHAPE_POLY_SET( const POLYGON& aPolygon );

    SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
 
    ~SHAPE_POLY_SET();
 
    SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
 
    // Move assignment operator
    SHAPE_POLY_SET& operator=( SHAPE_POLY_SET&& aOther ) noexcept
    {
        if (this != &aOther)
        {
            SHAPE::operator=( aOther );
 
            m_polys = std::move( aOther.m_polys );
            m_triangulatedPolys = std::move( aOther.m_triangulatedPolys );
 
            m_hash = aOther.m_hash;
            m_hashValid.store( aOther.m_hashValid.load() );
            m_triangulationValid.store( aOther.m_triangulationValid );
        }
 
        return *this;
    }

    virtual void CacheTriangulation( bool aSimplify = false,
                                     const TASK_SUBMITTER& aSubmitter = {} )
    {
        cacheTriangulation( aSimplify, nullptr, aSubmitter );
    }
    bool IsTriangulationUpToDate() const;
 
    HASH_128 GetHash() const;
 
    virtual bool HasIndexableSubshapes() const override;
 
    virtual size_t GetIndexableSubshapeCount() const override;
 
    virtual void GetIndexableSubshapes( std::vector<const SHAPE*>& aSubshapes ) const override;

    bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;

    bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;

    SHAPE* Clone() const override;
 
    SHAPE_POLY_SET CloneDropTriangulation() const;

    int NewOutline();

    int NewHole( int aOutline = -1 );

    int AddOutline( const SHAPE_LINE_CHAIN& aOutline );

    int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );

    int AddPolygon( const POLYGON& apolygon );

    double Area();

    int ArcCount() const;

    void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;

    void ClearArcs();


    int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );

    void Append( const SHAPE_POLY_SET& aSet );

    void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );

    int Append( const SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1,
                std::optional<int> aMaxError = {} );

    void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );

    const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;

    const VECTOR2I& CVertex( int aGlobalIndex ) const;

    const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;

    bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext ) const;

    bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;

    bool IsSelfIntersecting() const;

    unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }

    int OutlineCount() const { return m_polys.size(); }

    int VertexCount( int aOutline = -1, int aHole = -1 ) const;

    int FullPointCount() const;

    int HoleCount( int aOutline ) const
    {
        if( aOutline < 0 || aOutline >= (int) m_polys.size() || m_polys[aOutline].size() < 2 )
            return 0;
 
        // the first polygon in m_polys[aOutline] is the main contour,
        // only others are holes:
        return m_polys[aOutline].size() - 1;
    }

    SHAPE_LINE_CHAIN& Outline( int aIndex )
    {
        return m_polys[aIndex][0];
    }
 
    const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
    {
        return m_polys[aIndex][0];
    }

    SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
 
    SHAPE_POLY_SET UnitSet( int aPolygonIndex )
    {
        return Subset( aPolygonIndex, aPolygonIndex + 1 );
    }

    SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
    {
        return m_polys[aOutline][aHole + 1];
    }

    POLYGON& Polygon( int aIndex )
    {
        return m_polys[aIndex];
    }
 
    const POLYGON& Polygon( int aIndex ) const
    {
        return m_polys[aIndex];
    }
 
    const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
    {
        return m_triangulatedPolys[aIndex].get();
    }
 
    const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
    {
        return m_polys[aIndex][0];
    }
 
    const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
    {
        return m_polys[aOutline][aHole + 1];
    }
 
    const POLYGON& CPolygon( int aIndex ) const
    {
        return m_polys[aIndex];
    }
 
    const std::vector<POLYGON>& CPolygons() const { return m_polys; }

    ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
    {
        ITERATOR iter;
 
        iter.m_poly = this;
        iter.m_currentPolygon = aFirst;
        iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
        iter.m_currentContour = 0;
        iter.m_currentVertex = 0;
        iter.m_iterateHoles = aIterateHoles;
 
        return iter;
    }

    ITERATOR Iterate( int aOutline )
    {
        return Iterate( aOutline, aOutline );
    }

    ITERATOR IterateWithHoles( int aOutline )
    {
        return Iterate( aOutline, aOutline, true );
    }

    ITERATOR Iterate()
    {
        return Iterate( 0, OutlineCount() - 1 );
    }

    ITERATOR IterateWithHoles()
    {
        return Iterate( 0, OutlineCount() - 1, true );
    }
 
 
    CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
    {
        CONST_ITERATOR iter;
 
        iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
        iter.m_currentPolygon = aFirst;
        iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
        iter.m_currentContour = 0;
        iter.m_currentVertex = 0;
        iter.m_iterateHoles = aIterateHoles;
 
        return iter;
    }
 
    CONST_ITERATOR CIterate( int aOutline ) const
    {
        return CIterate( aOutline, aOutline );
    }
 
    CONST_ITERATOR CIterateWithHoles( int aOutline ) const
    {
        return CIterate( aOutline, aOutline, true );
    }
 
    CONST_ITERATOR CIterate() const
    {
        return CIterate( 0, OutlineCount() - 1 );
    }
 
    CONST_ITERATOR CIterateWithHoles() const
    {
        return CIterate( 0, OutlineCount() - 1, true );
    }
 
    ITERATOR IterateFromVertexWithHoles( int aGlobalIdx )
    {
        // Build iterator
        ITERATOR iter = IterateWithHoles();
 
        // Get the relative indices of the globally indexed vertex
        VERTEX_INDEX indices;
 
        if( !GetRelativeIndices( aGlobalIdx, &indices ) )
            throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
 
        // Adjust where the iterator is pointing
        iter.m_currentPolygon = indices.m_polygon;
        iter.m_currentContour = indices.m_contour;
        iter.m_currentVertex = indices.m_vertex;
 
        return iter;
    }

    SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
    {
        SEGMENT_ITERATOR iter;
 
        iter.m_poly = this;
        iter.m_currentPolygon = aFirst;
        iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
        iter.m_currentContour = 0;
        iter.m_currentSegment = 0;
        iter.m_iterateHoles = aIterateHoles;
 
        return iter;
    }

    CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
                                             bool aIterateHoles = false ) const
    {
        CONST_SEGMENT_ITERATOR iter;
 
        iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
        iter.m_currentPolygon = aFirst;
        iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
        iter.m_currentContour = 0;
        iter.m_currentSegment = 0;
        iter.m_iterateHoles = aIterateHoles;
 
        return iter;
    }

    SEGMENT_ITERATOR IterateSegments( int aPolygonIdx )
    {
        return IterateSegments( aPolygonIdx, aPolygonIdx );
    }

    CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
    {
        return CIterateSegments( aPolygonIdx, aPolygonIdx );
    }

    SEGMENT_ITERATOR IterateSegments()
    {
        return IterateSegments( 0, OutlineCount() - 1 );
    }

    CONST_SEGMENT_ITERATOR CIterateSegments() const
    {
        return CIterateSegments( 0, OutlineCount() - 1 );
    }

    SEGMENT_ITERATOR IterateSegmentsWithHoles()
    {
        return IterateSegments( 0, OutlineCount() - 1, true );
    }

    SEGMENT_ITERATOR IterateSegmentsWithHoles( int aOutline )
    {
        return IterateSegments( aOutline, aOutline, true );
    }

    CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
    {
        return CIterateSegments( 0, OutlineCount() - 1, true );
    }

    CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles( int aOutline ) const
    {
        return CIterateSegments( aOutline, aOutline, true );
    }
 

    void BooleanAdd( const SHAPE_POLY_SET& b );

    void BooleanSubtract( const SHAPE_POLY_SET& b );

    void BooleanIntersection( const SHAPE_POLY_SET& b );

    void BooleanXor( const SHAPE_POLY_SET& b );

    void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );

    void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );

    void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );

    void BooleanXor( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );

    void RebuildHolesFromContours();

    void Inflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
                  bool aSimplify = false );
 
    void Deflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError )
    {
        Inflate( -aAmount, aCornerStrategy, aMaxError );
    }

    void OffsetLineChain( const SHAPE_LINE_CHAIN& aLine, int aAmount,
                          CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify );

    void InflateWithLinkedHoles( int aFactor, CORNER_STRATEGY aCornerStrategy, int aMaxError );

    void Fracture( bool aSimplify = true );

    void Unfracture();

    bool HasHoles() const;

    bool HasTouchingHoles() const;
 

    void Simplify();

    void SimplifyOutlines( int aMaxError = 0 );

    int NormalizeAreaOutlines();

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

    bool Parse( std::stringstream& aStream ) override;

    void Move( const VECTOR2I& aVector ) override;

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

    void Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;

    bool IsSolid() const override
    {
        return true;
    }
 
    const BOX2I BBox( int aClearance = 0 ) const override;

    bool PointOnEdge( const VECTOR2I& aP, int aAccuracy = 0 ) const;

    bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
                  VECTOR2I* aLocation = nullptr ) const override;

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

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

    bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
                        int aClearance = 0 ) const;

    bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
                      int aClearance = 0 ) const;
 
    bool PointInside( const VECTOR2I& aPt, int aAccuracy = 0,
                      bool aUseBBoxCache = false ) const override;

    void BuildBBoxCaches() const;
 
    const BOX2I BBoxFromCaches() const;

    bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
                   bool aUseBBoxCaches = false ) const;

    bool IsEmpty() const
    {
        return m_polys.empty();
    }

    void RemoveVertex( int aGlobalIndex );

    void RemoveVertex( VERTEX_INDEX aRelativeIndices );

    void RemoveAllContours();

    void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
 

    void RemoveOutline( int aOutlineIdx );

    int RemoveNullSegments();

    void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );

    void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );

    int TotalVertices() const;

    void DeletePolygon( int aIdx );

    void DeletePolygonAndTriangulationData( int aIdx, bool aUpdateHash = true );
 
    void UpdateTriangulationDataHash();

    POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );

    POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );

    SHAPE_POLY_SET Chamfer( int aDistance );

    SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );

    SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
                                          VECTOR2I* aNearest ) const;

    SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
                                          VECTOR2I* aNearest) const;

    SEG::ecoord SquaredDistance( const VECTOR2I& aPoint, bool aOutlineOnly,
                                 VECTOR2I* aNearest ) const;
 
    SEG::ecoord SquaredDistance( const VECTOR2I& aPoint, bool aOutlineOnly = false ) const override
    {
        return SquaredDistance( aPoint, aOutlineOnly, nullptr );
    }

    SEG::ecoord SquaredDistanceToSeg( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;

    bool IsVertexInHole( int aGlobalIdx );

    void BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths,
                                        bool aEvenOdd = false );
 
    void TransformToPolygon( SHAPE_POLY_SET& aBuffer, int aError,
                             ERROR_LOC aErrorLoc ) const override
    {
        aBuffer.Append( *this );
    }
 
    const std::vector<SEG> GenerateHatchLines( const std::vector<double>& aSlopes, int aSpacing,
                                               int aLineLength ) const;
 
    void Scale( double aScaleFactorX, double aScaleFactorY, const VECTOR2I& aCenter );
 
protected:
    void cacheTriangulation( bool aSimplify,
                             std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData,
                             const TASK_SUBMITTER& aSubmitter = {} );
 
private:
    enum DROP_TRIANGULATION_FLAG { SINGLETON };
 
    SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther, DROP_TRIANGULATION_FLAG );
 
    void fractureSingle( POLYGON& paths );
    void unfractureSingle ( POLYGON& path );
    void importTree( Clipper2Lib::PolyTree64&            tree,
                     const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
                     const std::vector<SHAPE_ARC>&       aArcBuffe );
    void importPaths( Clipper2Lib::Paths64&               paths,
                     const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
                     const std::vector<SHAPE_ARC>&       aArcBuffe );
    void importPolyPath( const std::unique_ptr<Clipper2Lib::PolyPath64>& aPolyPath,
                     const std::vector<CLIPPER_Z_VALUE>&                 aZValueBuffer,
                     const std::vector<SHAPE_ARC>&                       aArcBuffer );
 
    void inflate2( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify = false );
 
    void inflateLine2( const SHAPE_LINE_CHAIN& aLine, int aAmount, int aCircleSegCount,
                       CORNER_STRATEGY aCornerStrategy, bool aSimplify = false );
 
    void splitCollinearOutlines();

    void splitSelfTouchingOutlines();

    bool isExteriorWaist( const SEG& aSegA, const SEG& aSegB ) const;

    void booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aOtherShape );
 
    void booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aShape,
                    const SHAPE_POLY_SET& aOtherShape );

    bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
                         bool aUseBBoxCaches = false ) const;

    enum CORNER_MODE
    {
        CHAMFERED,
        FILLETED
    };

    POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
                                  int aIndex, int aErrorMax );

    bool hasTouchingHoles( const POLYGON& aPoly ) const;
 
    HASH_128 checksum() const;
 
protected:
    std::vector<POLYGON>                               m_polys;
    std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
 
    std::atomic<bool> m_triangulationValid = false;
    std::mutex  m_triangulationMutex;
 
private:
    HASH_128 m_hash;
    std::atomic<bool> m_hashValid = false;
 
    HASH_128 m_failedHash;
    std::atomic<bool> m_failedHashValid = false;
};
 
#endif // __SHAPE_POLY_SET_H