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 (C) 2021-2022 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, 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 <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 <clipper2/clipper.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 <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( 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; }
 
 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 );
 
 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; }
 
 std::deque<TRI>& Triangles() { return m_triangles; }
 const std::deque<TRI>& Triangles() const { return m_triangles; }
 
 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 SHAPE_POLY_SET& aOther );
 
 ~SHAPE_POLY_SET();
 
 SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
 
 void CacheTriangulation( bool aPartition = true, bool aSimplify = false );
 bool IsTriangulationUpToDate() const;
 
 MD5_HASH 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 );
 
 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( SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1,
 double aAccuracy = SHAPE_ARC::DefaultAccuracyForPCB() );
 
 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 );
 
 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];
 }
 
 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 );
 }
 
 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, CORNER_STRATEGY aCornerStrategy, int aMaxError,
 bool aSimplify = false );
 
 void Deflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError )
 {
 Inflate( -aAmount, aCornerStrategy, aMaxError );
 }
 
 void InflateWithLinkedHoles( int aFactor, CORNER_STRATEGY aCornerStrategy, int aMaxError,
 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( bool aCplusPlus = true ) 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( 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 ) 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;
 
 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 );
 
 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( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
 
 SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
 
 bool IsVertexInHole( int aGlobalIdx );
 
 static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths, bool aReverseOrientation = false, bool aEvenOdd = false );
 
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( ClipperLib::PolyTree* tree,
 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
 const std::vector<SHAPE_ARC>& aArcBuffe );
 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 inflate1( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy );
 void inflate2( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify = false );
 
 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 );
 
 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;
 
 MD5_HASH checksum() const;
 
private:
 std::vector<POLYGON> m_polys;
 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
 
 bool m_triangulationValid = false;
 MD5_HASH m_hash;
};
 
#endif // __SHAPE_POLY_SET_H