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

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

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

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

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

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

 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, int aCircleSegCount,
 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;

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

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

 MD5_HASH checksum() const;

private:
 typedef std::vector<POLYGON> POLYSET;

 POLYSET m_polys;

 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;

 bool m_triangulationValid = false;
 MD5_HASH m_hash;
};

#endif // __SHAPE_POLY_SET_H