26 #ifndef __SHAPE_POLY_SET_H
27 #define __SHAPE_POLY_SET_H
32 #include <geometry/shape.h>
33 #include <geometry/shape_line_chain.h>
35 #include "clipper.hpp"
61 typedef std::vector<SHAPE_LINE_CHAIN>
POLYGON;
70 TRI() : a(0), b(0), c(0)
81 void AllocateVertices(
int aSize );
82 void AllocateTriangles (
int aSize );
86 auto tri = &m_triangles[ index ];
87 a = m_vertices[ tri->a ];
88 b = m_vertices[ tri->b ];
89 c = m_vertices[ tri->c ];
92 void SetTriangle(
int aIndex,
const TRI& aTri )
94 m_triangles[aIndex] = aTri;
99 m_vertices[ m_vertexCount ] = aP;
100 return (m_vertexCount++);
103 int GetTriangleCount()
const
105 return m_triangleCount;
108 int GetVertexCount()
const
110 return m_vertexCount;
115 TRI* m_triangles =
nullptr;
117 int m_vertexCount = 0;
118 int m_triangleCount = 0;
156 return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
165 return m_currentPolygon == m_lastPolygon;
168 operator bool()
const
170 return m_currentPolygon <= m_lastPolygon;
188 if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount() )
195 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
197 if( m_currentContour >= totalContours )
199 m_currentContour = 0;
207 if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
215 void operator++(
int dummy )
227 return m_poly->
Polygon( m_currentPolygon )[m_currentContour].Point( m_currentVertex );
260 int m_currentPolygon;
261 int m_currentContour;
282 return m_currentPolygon == m_lastPolygon;
285 operator bool()
const
287 return m_currentPolygon <= m_lastPolygon;
305 last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
308 if( m_currentSegment >= last )
310 m_currentSegment = 0;
315 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
317 if( m_currentContour >= totalContours )
319 m_currentContour = 0;
326 last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
329 if( m_currentSegment >= last )
331 m_currentSegment = 0;
337 void operator++(
int dummy )
349 return m_poly->
Polygon( m_currentPolygon )[m_currentContour].Segment( m_currentSegment );
383 if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
384 m_currentContour == aOther.m_currentContour )
388 numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
394 int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
396 return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
406 int m_currentPolygon;
407 int m_currentContour;
408 int m_currentSegment;
414 typedef ITERATOR_TEMPLATE<VECTOR2I> ITERATOR;
415 typedef ITERATOR_TEMPLATE<const VECTOR2I> CONST_ITERATOR;
418 typedef SEGMENT_ITERATOR_TEMPLATE<SEG> SEGMENT_ITERATOR;
419 typedef SEGMENT_ITERATOR_TEMPLATE<const SEG> CONST_SEGMENT_ITERATOR;
464 int NewHole(
int aOutline = -1 );
485 int Append(
int x,
int y,
int aOutline = -1,
int aHole = -1,
486 bool aAllowDuplication =
false );
492 void Append(
const VECTOR2I& aP,
int aOutline = -1,
int aHole = -1 );
558 int VertexCount(
int aOutline = -1,
int aHole = -1 )
const;
563 if( ( aOutline < 0 ) || (aOutline >= (
int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
568 return m_polys[aOutline].size() - 1;
574 return m_polys[aIndex][0];
590 return Subset( aPolygonIndex, aPolygonIndex + 1 );
596 return m_polys[aOutline][aHole + 1];
602 return m_polys[aIndex];
607 return m_polys[aIndex];
610 const TRIANGULATED_POLYGON* TriangulatedPolygon(
int aIndex )
const
612 return m_triangulatedPolys[aIndex].get();
617 return m_polys[aIndex][0];
622 return m_polys[aOutline][aHole + 1];
625 const POLYGON& CPolygon(
int aIndex )
const
627 return m_polys[aIndex];
645 iter.m_currentPolygon = aFirst;
646 iter.m_lastPolygon = aLast < 0 ?
OutlineCount() - 1 : aLast;
647 iter.m_currentContour = 0;
648 iter.m_currentVertex = 0;
649 iter.m_iterateHoles = aIterateHoles;
662 return Iterate( aOutline, aOutline );
673 return Iterate( aOutline, aOutline,
true );
697 CONST_ITERATOR CIterate(
int aFirst,
int aLast,
bool aIterateHoles =
false )
const
701 iter.m_poly = const_cast<SHAPE_POLY_SET*>(
this );
702 iter.m_currentPolygon = aFirst;
703 iter.m_lastPolygon = aLast < 0 ?
OutlineCount() - 1 : aLast;
704 iter.m_currentContour = 0;
705 iter.m_currentVertex = 0;
706 iter.m_iterateHoles = aIterateHoles;
711 CONST_ITERATOR CIterate(
int aOutline )
const
713 return CIterate( aOutline, aOutline );
716 CONST_ITERATOR CIterateWithHoles(
int aOutline )
const
718 return CIterate( aOutline, aOutline,
true );
721 CONST_ITERATOR CIterate()
const
726 CONST_ITERATOR CIterateWithHoles()
const
731 ITERATOR IterateFromVertexWithHoles(
int aGlobalIdx )
740 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
743 iter.m_currentPolygon = indices.
m_polygon;
744 iter.m_currentContour = indices.m_contour;
745 iter.m_currentVertex = indices.m_vertex;
757 iter.m_currentPolygon = aFirst;
758 iter.m_lastPolygon = aLast < 0 ?
OutlineCount() - 1 : aLast;
759 iter.m_currentContour = 0;
760 iter.m_currentSegment = 0;
761 iter.m_iterateHoles = aIterateHoles;
800 PM_STRICTLY_SIMPLE =
false
831 void Inflate(
int aFactor,
int aCircleSegmentsCount );
863 const std::string
Format()
const override;
866 bool Parse( std::stringstream& aStream )
override;
885 const BOX2I BBox(
int aClearance = 0 )
const override;
921 bool Collide(
const SEG& aSeg,
int aClearance = 0 )
const override;
934 int aClearance = 0 );
947 int aClearance = 0 );
957 bool Contains(
const VECTOR2I& aP,
int aSubpolyIndex = -1,
bool aIgnoreHoles =
false )
const;
962 return m_polys.size() == 0;
1082 int Distance(
const SEG& aSegment,
int aSegmentWidth = 0 );
1094 SHAPE_LINE_CHAIN& getContourForCorner(
int aCornerId,
int& aIndexWithinContour );
1096 const VECTOR2I& cvertex(
int aCornerId )
const;
1099 void fractureSingle(
POLYGON& paths );
1100 void unfractureSingle (
POLYGON& path );
1114 void booleanOp( ClipperLib::ClipType aType,
1117 void booleanOp( ClipperLib::ClipType aType,
1123 const ClipperLib::Path convertToClipper(
const SHAPE_LINE_CHAIN& aPath,
bool aRequiredOrientation );
1124 const SHAPE_LINE_CHAIN convertFromClipper(
const ClipperLib::Path& aPath );
1138 bool containsSingle(
const VECTOR2I& aP,
int aSubpolyIndex,
bool aIgnoreHoles =
false )
const;
1167 POLYGON chamferFilletPolygon( CORNER_MODE aMode,
unsigned int aDistance,
1168 int aIndex,
int aErrorMax = -1 );
1171 bool hasTouchingHoles(
const POLYGON& aPoly )
const;
1173 typedef std::vector<POLYGON> POLYSET;
1181 void CacheTriangulation();
1182 bool IsTriangulationUpToDate()
const;
1184 MD5_HASH GetHash()
const;
1189 MD5_HASH checksum()
const;
1191 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1192 bool m_triangulationValid =
false;
bool IsEndContour() const
Function IsEndContour.
Definition: shape_poly_set.h:154
ITERATOR IterateWithHoles()
Function IterateWithHoles.
Definition: shape_poly_set.h:691
int Distance(VECTOR2I aPoint)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
Definition: shape_poly_set.cpp:1619
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
Definition: shape_poly_set.h:379
bool IsSelfIntersecting()
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.
Definition: shape_poly_set.cpp:416
void Move(const VECTOR2I &aVector) override
Definition: shape_poly_set.cpp:1504
bool IsSolid() const override
Definition: shape_poly_set.h:880
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
Definition: shape_poly_set.cpp:1295
Definition: clipper.hpp:158
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_poly_set.cpp:1198
int m_polygon
Definition: shape_poly_set.h:130
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
Definition: shape_poly_set.cpp:206
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
Definition: shape_poly_set.cpp:554
Definition: shape_poly_set.h:65
SEGMENT_ITERATOR IterateSegments(int aFirst, int aLast, bool aIterateHoles=false)
Returns an iterator object, for iterating between aFirst and aLast outline, with or without holes (de...
Definition: shape_poly_set.h:752
Class ITERATOR_TEMPLATE.
Definition: shape_poly_set.h:145
VERTEX_INDEX GetIndex()
Function GetIndex.
Definition: shape_poly_set.h:361
VERTEX_INDEX GetIndex()
Function GetIndex.
Definition: shape_poly_set.h:244
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
Definition: shape_poly_set.cpp:1655
void Advance()
Function Advance advances the indices of the current vertex/outline/contour, checking whether the ver...
Definition: shape_poly_set.h:178
Definition: shape_poly_set.cpp:1866
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
Definition: shape_poly_set.cpp:73
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
Definition: shape_poly_set.cpp:875
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
Definition: shape_poly_set.cpp:1454
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
Definition: shape_poly_set.cpp:590
void Advance()
Function Advance advances the indices of the current vertex/outline/contour, checking whether the ver...
Definition: shape_poly_set.h:295
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Returns the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a con...
Definition: shape_poly_set.cpp:342
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline
Definition: shape_poly_set.cpp:268
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
Definition: shape_poly_set.cpp:168
Class SEGMENT_ITERATOR_TEMPLATE.
Definition: shape_poly_set.h:273
Struct VERTEX_INDEX.
Definition: shape_poly_set.h:128
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
Definition: shape_poly_set.cpp:1516
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
Definition: shape_poly_set.cpp:1434
SEGMENT_ITERATOR IterateSegmentsWithHoles(int aOutline)
Returns an iterator object, for the aOutline-th outline in the set (with holes)
Definition: shape_poly_set.h:785
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
Definition: shape_poly_set.cpp:1279
int m_contour
Definition: shape_poly_set.h:131
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
Definition: shape_poly_set.cpp:185
int TotalVertices() const
Returns total number of vertices stored in the set.
Definition: shape_poly_set.cpp:1528
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
Definition: shape_poly_set.h:773
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
Definition: shape_poly_set.cpp:1544
ITERATOR Iterate(int aOutline)
Function Iterate.
Definition: shape_poly_set.h:660
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
Definition: shape_poly_set.cpp:1062
POLYGON_MODE
operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
Definition: shape_poly_set.h:797
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide Checks whether the point aP collides with the inside of the polygon set; if the poin...
Definition: shape_poly_set.cpp:1263
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
Definition: shape_poly_set.cpp:228
int NewOutline()
Creates a new empty polygon in the set and returns its index
Definition: shape_poly_set.cpp:156
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLas...
Definition: shape_poly_set.cpp:253
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
Definition: shape_poly_set.h:561
int OutlineCount() const
Returns the number of outlines in the set
Definition: shape_poly_set.h:555
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
Definition: shape_poly_set.cpp:1285
bool IsLastPolygon() const
Function IsLastOutline.
Definition: shape_poly_set.h:163
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
Definition: shape_poly_set.cpp:1348
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
Definition: shape_poly_set.cpp:1215
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
Definition: shape_poly_set.h:960
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
Definition: shape_poly_set.h:600
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex=0)
Function Fillet returns a filleted version of the aIndex-th polygon.
Definition: shape_poly_set.cpp:1550
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
Definition: shape_poly_set.cpp:2121
Definition: shape_poly_set.h:68
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
Definition: shape_poly_set.cpp:548
SHAPE * Clone() const override
Function Clone()
Definition: shape_poly_set.cpp:67
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Definition: shape_poly_set.h:61
ITERATOR Iterate(int aFirst, int aLast, bool aIterateHoles=false)
Function Iterate returns an object to iterate through the points of the polygons between aFirst and a...
Definition: shape_poly_set.h:640
ITERATOR IterateWithHoles(int aOutline)
Function IterateWithHoles.
Definition: shape_poly_set.h:671
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp
Definition: shape_poly_set.cpp:560
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
Definition: shape_poly_set.cpp:1073
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Returns an iterator object, for iterating aPolygonIdx-th polygon edges
Definition: shape_poly_set.h:767
bool Parse(std::stringstream &aStream) override
Definition: shape_poly_set.cpp:1139
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
Definition: shape_poly_set.h:779
int m_vertex
Definition: shape_poly_set.h:132
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.
Definition: shape_poly_set.cpp:389
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
Definition: shape_poly_set.cpp:287
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Function Fillet returns a filleted version of the polygon set.
Definition: shape_poly_set.cpp:1679
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
Definition: shape_poly_set.cpp:1558
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
Definition: shape_poly_set.cpp:1404
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
Definition: shape_poly_set.cpp:428
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
Definition: shape_poly_set.cpp:1366
Class SHAPE_LINE_CHAIN.
Definition: shape_line_chain.h:47
ITERATOR Iterate()
Function Iterate.
Definition: shape_poly_set.h:681
Class SHAPE.
Definition: shape.h:58
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
Definition: shape_poly_set.h:572
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
Definition: shape_poly_set.cpp:1668
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon,...
Definition: shape_poly_set.cpp:113
const std::string Format() const override
Definition: shape_poly_set.cpp:1114
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
Definition: shape_poly_set.h:594
bool HasHoles() const
Returns true if the polygon set has any holes.
Definition: shape_poly_set.cpp:1047
bool IsLastPolygon() const
Function IsLastOutline.
Definition: shape_poly_set.h:280
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
Definition: shape_poly_set.cpp:1081
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index
Definition: shape_poly_set.cpp:442
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
Definition: shape_poly_set.h:552
Class SHAPE_POLY_SET.
Definition: shape_poly_set.h:56