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
 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
 * @author Alejandro García Montoro <alejandro.garciamontoro@gmail.com>
 *
 * 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_POLY_SET_H
#define __SHAPE_POLY_SET_H

#include <cstdio>
#include <deque>                        // for deque
#include <vector>                       // for vector
#include <iosfwd>                       // for string, stringstream
#include <memory>
#include <set>                          // for set
#include <stdexcept>                    // for out_of_range
#include <stdlib.h>                     // for abs
#include <vector>

#include <clipper.hpp>                  // for ClipType, PolyTree (ptr only)
#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 <md5_hash.h>


class SHAPE_POLY_SET : public SHAPE
{
    public:
        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( double 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: assert(false);
                    }
                    return VECTOR2I(0, 0);
                }

                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: assert(false);
                    }
                    return SEG();
                }

                virtual size_t GetPointCount() const override { return 3; }
                virtual size_t GetSegmentCount() const override { return 3; }


                int a, b, c;
                TRIANGULATED_POLYGON* parent;
            };

            TRIANGULATED_POLYGON();
            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 );

            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();
            }

            std::deque<TRI>& Triangles()
            {
                return m_triangles;
            }

            size_t GetVertexCount() const
            {
                return m_vertices.size();
            }

            void Move( const VECTOR2I& aVec )
            {
                for( auto& vertex : m_vertices )
                    vertex += aVec;
            }

        private:

            std::deque<TRI> m_triangles;
            std::deque<VECTOR2I> m_vertices;
        };

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

        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()
            {
                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 )
            {
                // 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 = 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 SHAPE_LINE_CHAIN& aOutline );

        SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );

        ~SHAPE_POLY_SET();

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

        bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );

        SHAPE* Clone() const override;

        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 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 );

        void InsertVertex( int aGlobalIndex, 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 );


        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 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];
        }

        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];
        }

        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 );
        }

        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 );
        }

        enum POLYGON_MODE
        {
            PM_FAST = true,
            PM_STRICTLY_SIMPLE = false
        };

        void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );

        void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );

        void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );

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

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

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

        enum CORNER_STRATEGY    
        {
            ALLOW_ACUTE_CORNERS,    
            CHAMFER_ACUTE_CORNERS,  
            ROUND_ACUTE_CORNERS,    
            CHAMFER_ALL_CORNERS,    
            ROUND_ALL_CORNERS       
        };

        void Inflate( int aAmount, int aCircleSegmentsCount,
                      CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );

        void Deflate( int aAmount, int aCircleSegmentsCount,
                      CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
        {
            Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
        }

        void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );

        void Fracture( POLYGON_MODE aFastMode );

        void Unfracture( POLYGON_MODE aFastMode );

        bool HasHoles() const;

        bool HasTouchingHoles() const;


        void Simplify( POLYGON_MODE aFastMode );

        int NormalizeAreaOutlines();

        const std::string Format() const override;

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

        void Move( const VECTOR2I& aVector ) override;

        void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );

        void Rotate( double 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 ) 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,
                            int aClearance = 0 ) const;

        bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
                          int aClearance = 0 ) const;

        void BuildBBoxCaches();

        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.size() == 0;
        }

        void RemoveVertex( int aGlobalIndex );

        void RemoveVertex( VERTEX_INDEX aRelativeIndices );

        void RemoveAllContours();

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

        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 );

        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( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;

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

        bool IsVertexInHole( int aGlobalIdx );

    private:
        void fractureSingle( POLYGON& paths );
        void unfractureSingle ( POLYGON& path );
        void importTree( ClipperLib::PolyTree* tree );

        void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
                        POLYGON_MODE aFastMode );

        void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
                        const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );

        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;

        typedef std::vector<POLYGON> POLYSET;

        POLYSET m_polys;

    public:

        SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& );

        void CacheTriangulation( bool aPartition = true );
        bool IsTriangulationUpToDate() const;

        MD5_HASH GetHash() const;

        virtual bool HasIndexableSubshapes() const override;

        virtual size_t GetIndexableSubshapeCount() const override;

        virtual void GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes ) override;

    private:

        MD5_HASH checksum() const;

        std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
        bool m_triangulationValid = false;
        MD5_HASH m_hash;

};

#endif