KiCad PCB EDA Suite
SHAPE_POLY_SET Class Reference

Class SHAPE_POLY_SET. More...

#include <shape_poly_set.h>

Inheritance diagram for SHAPE_POLY_SET:
SHAPE

Classes

class  ITERATOR_TEMPLATE
 Class ITERATOR_TEMPLATE. More...
 
class  SEGMENT_ITERATOR_TEMPLATE
 Class SEGMENT_ITERATOR_TEMPLATE. More...
 
class  TRIANGULATED_POLYGON
 
class  TRIANGULATION_CONTEXT
 
struct  VERTEX_INDEX
 Struct VERTEX_INDEX. More...
 

Public Types

enum  POLYGON_MODE { PM_FAST = true, PM_STRICTLY_SIMPLE = false }
 operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak polygon if aFastMode is PM_STRICTLY_SIMPLE (false) (default) the result is (theorically) a strictly simple polygon, but calculations can be really significantly time consuming Most of time PM_FAST is preferable. More...
 
typedef std::vector< SHAPE_LINE_CHAINPOLYGON
 

represents a single polygon outline with holes.

More...
 
typedef struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
 Struct VERTEX_INDEX. More...
 
typedef ITERATOR_TEMPLATE< VECTOR2IITERATOR
 
typedef ITERATOR_TEMPLATE< const VECTOR2ICONST_ITERATOR
 
typedef SEGMENT_ITERATOR_TEMPLATE< SEGSEGMENT_ITERATOR
 
typedef SEGMENT_ITERATOR_TEMPLATE< const SEGCONST_SEGMENT_ITERATOR
 

Public Member Functions

 SHAPE_POLY_SET ()
 
 SHAPE_POLY_SET (const SHAPE_POLY_SET &aOther)
 Copy constructor SHAPE_POLY_SET Performs a deep copy of aOther into this. More...
 
 ~SHAPE_POLY_SET ()
 
bool GetRelativeIndices (int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
 Function GetRelativeIndices. More...
 
bool GetGlobalIndex (VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
 Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon, contour and vertex. More...
 
SHAPEClone () const override
 Function Clone() More...
 
int NewOutline ()
 

Creates a new empty polygon in the set and returns its index

More...
 
int NewHole (int aOutline=-1)
 

Creates a new hole in a given outline

More...
 
int AddOutline (const SHAPE_LINE_CHAIN &aOutline)
 

Adds a new outline to the set and returns its index

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

Adds a new hole to the given outline (default: last) and returns its index

More...
 
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)

More...
 
void Append (const SHAPE_POLY_SET &aSet)
 

Merges polygons from two sets.

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

Appends a vertex at the end of the given outline/hole (default: the last outline)

More...
 
void InsertVertex (int aGlobalIndex, VECTOR2I aNewVertex)
 Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex. More...
 
VECTOR2IVertex (int aIndex, int aOutline, int aHole)
 

Returns the index-th vertex in a given hole outline within a given outline

More...
 
const VECTOR2ICVertex (int aIndex, int aOutline, int aHole) const
 

Returns the index-th vertex in a given hole outline within a given outline

More...
 
VECTOR2IVertex (int aGlobalIndex)
 

Returns the aGlobalIndex-th vertex in the poly set

More...
 
const VECTOR2ICVertex (int aGlobalIndex) const
 

Returns the aGlobalIndex-th vertex in the poly set

More...
 
VECTOR2IVertex (VERTEX_INDEX aIndex)
 

Returns the index-th vertex in a given hole outline within a given outline

More...
 
const VECTOR2ICVertex (VERTEX_INDEX aIndex) const
 

Returns the index-th vertex in a given hole outline within a given outline

More...
 
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 contour in the polygon set. More...
 
bool IsPolygonSelfIntersecting (int aPolygonIndex)
 Function IsPolygonSelfIntersecting. More...
 
bool IsSelfIntersecting ()
 Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting. More...
 
int OutlineCount () const
 

Returns the number of outlines in the set

More...
 
int VertexCount (int aOutline=-1, int aHole=-1) const
 

Returns the number of vertices in a given outline/hole

More...
 
int HoleCount (int aOutline) const
 

Returns the number of holes in a given outline

More...
 
SHAPE_LINE_CHAINOutline (int aIndex)
 

Returns the reference to aIndex-th outline in the set

More...
 
SHAPE_POLY_SET Subset (int aFirstPolygon, int aLastPolygon)
 Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon. More...
 
SHAPE_POLY_SET UnitSet (int aPolygonIndex)
 
SHAPE_LINE_CHAINHole (int aOutline, int aHole)
 

Returns the reference to aHole-th hole in the aIndex-th outline

More...
 
POLYGONPolygon (int aIndex)
 

Returns the aIndex-th subpolygon in the set

More...
 
const POLYGONPolygon (int aIndex) const
 
const TRIANGULATED_POLYGONTriangulatedPolygon (int aIndex) const
 
const SHAPE_LINE_CHAINCOutline (int aIndex) const
 
const SHAPE_LINE_CHAINCHole (int aOutline, int aHole) const
 
const POLYGONCPolygon (int aIndex) const
 
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 aLast. More...
 
ITERATOR Iterate (int aOutline)
 Function Iterate. More...
 
ITERATOR IterateWithHoles (int aOutline)
 Function IterateWithHoles. More...
 
ITERATOR Iterate ()
 Function Iterate. More...
 
ITERATOR IterateWithHoles ()
 Function IterateWithHoles. More...
 
CONST_ITERATOR CIterate (int aFirst, int aLast, bool aIterateHoles=false) const
 
CONST_ITERATOR CIterate (int aOutline) const
 
CONST_ITERATOR CIterateWithHoles (int aOutline) const
 
CONST_ITERATOR CIterate () const
 
CONST_ITERATOR CIterateWithHoles () const
 
ITERATOR IterateFromVertexWithHoles (int aGlobalIdx)
 
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 (default: without) More...

 
SEGMENT_ITERATOR IterateSegments (int aPolygonIdx)
 

Returns an iterator object, for iterating aPolygonIdx-th polygon edges

More...
 
SEGMENT_ITERATOR IterateSegments ()
 

Returns an iterator object, for all outlines in the set (no holes)

More...
 
SEGMENT_ITERATOR IterateSegmentsWithHoles ()
 

Returns an iterator object, for all outlines in the set (with holes)

More...
 
SEGMENT_ITERATOR IterateSegmentsWithHoles (int aOutline)
 

Returns an iterator object, for the aOutline-th outline in the set (with holes)

More...
 
void BooleanAdd (const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
 

Performs boolean polyset union For aFastMode meaning, see function booleanOp

More...
 
void BooleanSubtract (const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
 

Performs boolean polyset difference For aFastMode meaning, see function booleanOp

More...
 
void BooleanIntersection (const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
 

Performs boolean polyset intersection For aFastMode meaning, see function booleanOp

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

Performs boolean polyset union between a and b, store the result in it self For aFastMode meaning, see function booleanOp

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

Performs boolean polyset difference between a and b, store the result in it self For aFastMode meaning, see function booleanOp

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

Performs boolean polyset intersection between a and b, store the result in it self For aFastMode meaning, see function booleanOp

More...
 
void Inflate (int aFactor, int aCircleSegmentsCount)
 

Performs outline inflation/deflation, using round corners.

More...
 
void Fracture (POLYGON_MODE aFastMode)
 

Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the outer ring to the inner holes For aFastMode meaning, see function booleanOp

More...
 
void Unfracture (POLYGON_MODE aFastMode)
 

Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.

More...
 
bool HasHoles () const
 

Returns true if the polygon set has any holes.

More...
 
bool HasTouchingHoles () const
 

Returns true if the polygon set has any holes tha share a vertex.

More...
 
void Simplify (POLYGON_MODE aFastMode)
 

Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMode meaning, see function booleanOp

More...
 
int NormalizeAreaOutlines ()
 Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s) Removes null segments. More...
 
const std::string Format () const override
 
bool Parse (std::stringstream &aStream) override
 
void Move (const VECTOR2I &aVector) override
 
void Rotate (double aAngle, const VECTOR2I &aCenter)
 Function Rotate rotates all vertices by a given angle. More...
 
bool IsSolid () const override
 
const BOX2I BBox (int aClearance=0) const override
 Function BBox() More...
 
bool PointOnEdge (const VECTOR2I &aP) const
 Function PointOnEdge() More...
 
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 point lies on an edge or on a corner of any of the polygons, there is no collision: the edges does not belong to the polygon itself. More...
 
bool Collide (const SEG &aSeg, int aClearance=0) const override
 Function Collide() More...
 
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 polygon. More...
 
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 polygon. More...
 
bool Contains (const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
 Returns true if a given subpolygon contains the point aP. More...
 
bool IsEmpty () const
 

Returns true if the set is empty (no polygons at all)

More...
 
void RemoveVertex (int aGlobalIndex)
 Function RemoveVertex deletes the aGlobalIndex-th vertex. More...
 
void RemoveVertex (VERTEX_INDEX aRelativeIndices)
 Function RemoveVertex deletes the vertex indexed by aIndex (index of polygon, contour and vertex). More...
 
void RemoveAllContours ()
 

Removes all outlines & holes (clears) the polygon set.

More...
 
void RemoveContour (int aContourIdx, int aPolygonIdx=-1)
 Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set. More...
 
int RemoveNullSegments ()
 Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and deletes them. More...
 
int TotalVertices () const
 

Returns total number of vertices stored in the set.

More...
 
void DeletePolygon (int aIdx)
 

Deletes aIdx-th polygon from the set

More...
 
POLYGON ChamferPolygon (unsigned int aDistance, int aIndex=0)
 Function Chamfer returns a chamfered version of the aIndex-th polygon. More...
 
POLYGON FilletPolygon (unsigned int aRadius, unsigned int aSegments, int aIndex=0)
 Function Fillet returns a filleted version of the aIndex-th polygon. More...
 
SHAPE_POLY_SET Chamfer (int aDistance)
 Function Chamfer returns a chamfered version of the polygon set. More...
 
SHAPE_POLY_SET Fillet (int aRadius, int aSegments)
 Function Fillet returns a filleted version of the polygon set. More...
 
int DistanceToPolygon (VECTOR2I aPoint, int aIndex)
 Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint. More...
 
int DistanceToPolygon (SEG aSegment, int aIndex, int aSegmentWidth=0)
 Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aSegment with a possible width. More...
 
int Distance (VECTOR2I aPoint)
 Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the set. More...
 
int Distance (const SEG &aSegment, int aSegmentWidth=0)
 Function DistanceToPolygon computes the minimum distance between aSegment and all the polygons in the set. More...
 
bool IsVertexInHole (int aGlobalIdx)
 Function IsVertexInHole. More...
 
SHAPE_POLY_SEToperator= (const SHAPE_POLY_SET &)
 
void CacheTriangulation ()
 
bool IsTriangulationUpToDate () const
 
SHAPE_TYPE Type () const
 Function Type() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance, VECTOR2I &aMTV) const
 Function Collide() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance=0) const
 
virtual VECTOR2I Centre () const
 Function Centre() More...
 

Protected Types

typedef VECTOR2I::extended_type ecoord
 

Protected Attributes

SHAPE_TYPE m_type
 

type of our shape

More...
 

Private Types

enum  CORNER_MODE { CHAMFERED, FILLETED }
 Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this enum is defined to make the necessary distinction when calling this method from the public ChamferPolygon and FilletPolygon methods. More...
 
typedef std::vector< POLYGONPOLYSET
 

Private Member Functions

SHAPE_LINE_CHAINgetContourForCorner (int aCornerId, int &aIndexWithinContour)
 
VECTOR2Ivertex (int aCornerId)
 
const VECTOR2Icvertex (int aCornerId) const
 
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)
 Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ... More...
 
void booleanOp (ClipperLib::ClipType aType, const SHAPE_POLY_SET &aShape, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
 
bool pointInPolygon (const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath) const
 
const ClipperLib::Path convertToClipper (const SHAPE_LINE_CHAIN &aPath, bool aRequiredOrientation)
 
const SHAPE_LINE_CHAIN convertFromClipper (const ClipperLib::Path &aPath)
 
bool containsSingle (const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
 containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the polyset. More...
 
POLYGON chamferFilletPolygon (CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aSegments=-1)
 Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in the set, depending on the aMode selected. More...
 
bool hasTouchingHoles (const POLYGON &aPoly) const
 

Returns true if the polygon set has any holes that touch share a vertex.

More...
 
void triangulateSingle (const POLYGON &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)
 
MD5_HASH checksum () const
 

Private Attributes

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

Detailed Description

Class SHAPE_POLY_SET.

Represents a set of closed polygons. Polygons may be nonconvex, self-intersecting and have holes. Provides boolean operations (using Clipper library as the backend).

Let us define the terms used on this class to clarify methods names and comments:

  • Polygon: each polygon in the set.
  • Outline: first polyline in each polygon; represents its outer contour.
  • Hole: second and following polylines in the polygon.
  • Contour: each polyline of each polygon in the set, whether or not it is an outline or a hole.
  • Vertex (or corner): each one of the points that define a contour.

TODO: add convex partitioning & spatial index

Definition at line 56 of file shape_poly_set.h.

Member Typedef Documentation

typedef VECTOR2I::extended_type SHAPE::ecoord
protectedinherited

Definition at line 61 of file shape.h.

represents a single polygon outline with holes.

The first entry is the outline,

the remaining (if any), are the holes

Definition at line 61 of file shape_poly_set.h.

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

Definition at line 1160 of file shape_poly_set.h.

Struct VERTEX_INDEX.

Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: the polygon index, the contour index relative to the polygon and the vertex index relative the contour.

Member Enumeration Documentation

Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this enum is defined to make the necessary distinction when calling this method from the public ChamferPolygon and FilletPolygon methods.

Enumerator
CHAMFERED 
FILLETED 

Definition at line 1132 of file shape_poly_set.h.

operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak polygon if aFastMode is PM_STRICTLY_SIMPLE (false) (default) the result is (theorically) a strictly simple polygon, but calculations can be really significantly time consuming Most of time PM_FAST is preferable.

PM_STRICTLY_SIMPLE can be used in critical cases (Gerber output for instance)

Enumerator
PM_FAST 
PM_STRICTLY_SIMPLE 

Definition at line 795 of file shape_poly_set.h.

Constructor & Destructor Documentation

SHAPE_POLY_SET::SHAPE_POLY_SET ( )

Definition at line 49 of file shape_poly_set.cpp.

Referenced by Clone(), and Collide().

49  :
51 {
52 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:70
convex polygon
Definition: shape.h:48
SHAPE_POLY_SET::SHAPE_POLY_SET ( const SHAPE_POLY_SET aOther)

Copy constructor SHAPE_POLY_SET Performs a deep copy of aOther into this.

Parameters
aOtheris the SHAPE_POLY_SET object that will be copied.

Definition at line 55 of file shape_poly_set.cpp.

55  :
56  SHAPE( SH_POLY_SET ), m_polys( aOther.m_polys )
57 {
58 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:70
convex polygon
Definition: shape.h:48
SHAPE_POLY_SET::~SHAPE_POLY_SET ( )

Definition at line 61 of file shape_poly_set.cpp.

62 {
63 }

Member Function Documentation

int SHAPE_POLY_SET::AddHole ( const SHAPE_LINE_CHAIN aHole,
int  aOutline = -1 
)

Adds a new hole to the given outline (default: last) and returns its index

Definition at line 441 of file shape_poly_set.cpp.

References m_polys.

Referenced by ZONE_CONTAINER::AddPolygon(), and PCB_EDIT_FRAME::End_Zone().

442 {
443  assert( m_polys.size() );
444 
445  if( aOutline < 0 )
446  aOutline += m_polys.size();
447 
448  POLYGON& poly = m_polys[aOutline];
449 
450  assert( poly.size() );
451 
452  poly.push_back( aHole );
453 
454  return poly.size() - 1;
455 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
int SHAPE_POLY_SET::AddOutline ( const SHAPE_LINE_CHAIN aOutline)

Adds a new outline to the set and returns its index

Definition at line 427 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::IsClosed(), and m_polys.

Referenced by ZONE_CONTAINER::AddPolygon(), CINFO3D_VISU::buildPadShapePolygon(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), D_PAD::MergePrimitivesAsPolygon(), CPolyLine::NormalizeAreaOutlines(), and NormalizeAreaOutlines().

428 {
429  assert( aOutline.IsClosed() );
430 
431  POLYGON poly;
432 
433  poly.push_back( aOutline );
434 
435  m_polys.push_back( poly );
436 
437  return m_polys.size() - 1;
438 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
bool IsClosed() const
Function IsClosed()
int SHAPE_POLY_SET::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)

Function Append adds a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last polygon).

Parameters
xis the x coordinate of the new vertex.
yis the y coordinate of the new vertex.
aOutlineis the index of the polygon.
aHoleis the index of the hole (-1 for the main outline),
aAllowDuplicationis a flag to indicate whether it is allowed to add this corner even if it is duplicated.
Returns
int - the number of corners of the selected contour after the addition.

Definition at line 184 of file shape_poly_set.cpp.

References m_polys.

Referenced by addHoleToPolygon(), addRect(), Append(), ZONE_CONTAINER::AppendCorner(), BuildBoardPolygonOutlines(), D_PAD::buildCustomPadPolygon(), CINFO3D_VISU::buildPadShapePolygon(), D_PAD::BuildPadShapePolygon(), ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), ZONE_FILLER::buildZoneFeatureHoleList(), DRC::checkClearancePadToPad(), DRC::checkClearanceSegmToPad(), ConvertOutlineToPolygon(), ConvertPolyListToPolySet(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CINFO3D_VISU::createNewPadWithClearance(), CreateThermalReliefPadPolygon(), DRC::doFootprintOverlappingDrc(), KIGFX::PCB_PAINTER::draw(), D_PAD::DrawShape(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), fillArcPOLY(), MODULE::GetBoundingPoly(), getRectangleAlongCentreLine(), InsertVertex(), LEGACY_PLUGIN::loadZONE_CONTAINER(), ZONE_CONTAINER::operator=(), PCB_PARSER::parseZONE_CONTAINER(), ZONE_CREATE_HELPER::performZoneCutout(), DXF_PLOTTER::PlotPoly(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), DRAWSEGMENT::SetPolyPoints(), PNS_KICAD_IFACE::syncPad(), TEXTE_PCB::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon(), TransformOvalClearanceToPolygon(), TransformRingToPolygon(), TransformRoundedEndsSegmentToPolygon(), TransformRoundRectToPolygon(), DRAWSEGMENT::TransformShapeWithClearanceToPolygon(), D_PAD::TransformShapeWithClearanceToPolygon(), ZONE_CONTAINER::TransformSolidAreasShapesToPolygonSet(), and ZONE_CONTAINER::ZONE_CONTAINER().

185 {
186  if( aOutline < 0 )
187  aOutline += m_polys.size();
188 
189  int idx;
190 
191  if( aHole < 0 )
192  idx = 0;
193  else
194  idx = aHole + 1;
195 
196  assert( aOutline < (int) m_polys.size() );
197  assert( idx < (int) m_polys[aOutline].size() );
198 
199  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
200 
201  return m_polys[aOutline][idx].PointCount();
202 }
void SHAPE_POLY_SET::Append ( const SHAPE_POLY_SET aSet)

Merges polygons from two sets.

Definition at line 1322 of file shape_poly_set.cpp.

References m_polys.

1323 {
1324  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1325 }
void SHAPE_POLY_SET::Append ( const VECTOR2I aP,
int  aOutline = -1,
int  aHole = -1 
)

Appends a vertex at the end of the given outline/hole (default: the last outline)

Definition at line 1328 of file shape_poly_set.cpp.

References Append(), VECTOR2< T >::x, and VECTOR2< T >::y.

1329 {
1330  Append( aP.x, aP.y, aOutline, aHole );
1331 }
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) ...
const BOX2I SHAPE_POLY_SET::BBox ( int  aClearance = 0) const
overridevirtual

Function BBox()

Computes a bounding box of the shape, with a margin of aClearance a collision.

Parameters
aClearancehow much the bounding box is expanded wrs to the minimum enclosing rectangle for the shape.
Returns
the bounding box.

Implements SHAPE.

Definition at line 1197 of file shape_poly_set.cpp.

References BOX2< Vec >::Inflate(), m_polys, and BOX2< Vec >::Merge().

Referenced by ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), BOARD::CombineAllAreasInNet(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), D_PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::GetBoundingBox(), IsSolid(), BOARD::TestAreaIntersection(), KIGFX::PREVIEW::POLYGON_ITEM::ViewBBox(), and KIGFX::PREVIEW::CENTRELINE_RECT_ITEM::ViewBBox().

1198 {
1199  BOX2I bb;
1200 
1201  for( unsigned i = 0; i < m_polys.size(); i++ )
1202  {
1203  if( i == 0 )
1204  bb = m_polys[i][0].BBox();
1205  else
1206  bb.Merge( m_polys[i][0].BBox() );
1207  }
1208 
1209  bb.Inflate( aClearance );
1210  return bb;
1211 }
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect...
Definition: box2.h:350
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:266
const BOX2I BBox(int aClearance=0) const override
Function BBox()
void SHAPE_POLY_SET::BooleanAdd ( const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

Performs boolean polyset union For aFastMode meaning, see function booleanOp

Definition at line 547 of file shape_poly_set.cpp.

References booleanOp().

Referenced by D_PAD::buildCustomPadPolygon(), BOARD::CombineAreas(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), and C3D_RENDER_OGL_LEGACY::reload().

548 {
549  booleanOp( ctUnion, b, aFastMode );
550 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
void SHAPE_POLY_SET::BooleanAdd ( const SHAPE_POLY_SET a,
const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

Performs boolean polyset union between a and b, store the result in it self For aFastMode meaning, see function booleanOp

Definition at line 565 of file shape_poly_set.cpp.

References booleanOp().

568 {
569  booleanOp( ctUnion, a, b, aFastMode );
570 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
void SHAPE_POLY_SET::BooleanIntersection ( const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

Performs boolean polyset intersection For aFastMode meaning, see function booleanOp

Definition at line 559 of file shape_poly_set.cpp.

References booleanOp().

Referenced by Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), DRC::doFootprintOverlappingDrc(), and TransformOvalClearanceToPolygon().

560 {
561  booleanOp( ctIntersection, b, aFastMode );
562 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
void SHAPE_POLY_SET::BooleanIntersection ( const SHAPE_POLY_SET a,
const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

Performs boolean polyset intersection between a and b, store the result in it self For aFastMode meaning, see function booleanOp

Definition at line 581 of file shape_poly_set.cpp.

References booleanOp().

584 {
585  booleanOp( ctIntersection, a, b, aFastMode );
586 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
void SHAPE_POLY_SET::booleanOp ( ClipperLib::ClipType  aType,
const SHAPE_POLY_SET aOtherShape,
POLYGON_MODE  aFastMode 
)
private

Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...

and polygon simplification (merging overlaping polygons)

Parameters
aTypeis the transform type ( see ClipperLib::ClipType )
aOtherShapeis the SHAPE_LINE_CHAIN to combine with me.
aFastModeis an option to choose if the result can be a weak polygon or a stricty simple polygon. if aFastMode is PM_FAST the result can be a weak polygon if aFastMode is PM_STRICTLY_SIMPLE (default) the result is (theorically) a strictly simple polygon, but calculations can be really significantly time consuming

Definition at line 489 of file shape_poly_set.cpp.

References convertToClipper(), importTree(), m_polys, and PM_STRICTLY_SIMPLE.

Referenced by BooleanAdd(), BooleanIntersection(), BooleanSubtract(), IsEmpty(), and Simplify().

491 {
492  Clipper c;
493 
494  if( aFastMode == PM_STRICTLY_SIMPLE )
495  c.StrictlySimple( true );
496 
497  for( const POLYGON& poly : m_polys )
498  {
499  for( unsigned int i = 0; i < poly.size(); i++ )
500  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
501  }
502 
503  for( const POLYGON& poly : aOtherShape.m_polys )
504  {
505  for( unsigned int i = 0; i < poly.size(); i++ )
506  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
507  }
508 
509  PolyTree solution;
510 
511  c.Execute( aType, solution, pftNonZero, pftNonZero );
512 
513  importTree( &solution );
514 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
const ClipperLib::Path convertToClipper(const SHAPE_LINE_CHAIN &aPath, bool aRequiredOrientation)
void importTree(ClipperLib::PolyTree *tree)
void SHAPE_POLY_SET::booleanOp ( ClipperLib::ClipType  aType,
const SHAPE_POLY_SET aShape,
const SHAPE_POLY_SET aOtherShape,
POLYGON_MODE  aFastMode 
)
private

Definition at line 517 of file shape_poly_set.cpp.

References convertToClipper(), importTree(), m_polys, and PM_STRICTLY_SIMPLE.

521 {
522  Clipper c;
523 
524  if( aFastMode == PM_STRICTLY_SIMPLE )
525  c.StrictlySimple( true );
526 
527  for( const POLYGON& poly : aShape.m_polys )
528  {
529  for( unsigned int i = 0; i < poly.size(); i++ )
530  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
531  }
532 
533  for( const POLYGON& poly : aOtherShape.m_polys )
534  {
535  for( unsigned int i = 0; i < poly.size(); i++ )
536  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
537  }
538 
539  PolyTree solution;
540 
541  c.Execute( aType, solution, pftNonZero, pftNonZero );
542 
543  importTree( &solution );
544 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
const ClipperLib::Path convertToClipper(const SHAPE_LINE_CHAIN &aPath, bool aRequiredOrientation)
void importTree(ClipperLib::PolyTree *tree)
void SHAPE_POLY_SET::BooleanSubtract ( const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

Performs boolean polyset difference For aFastMode meaning, see function booleanOp

Definition at line 553 of file shape_poly_set.cpp.

References booleanOp().

Referenced by addHoleToPolygon(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), CreateThermalReliefPadPolygon(), C3D_RENDER_OGL_LEGACY::generate_3D_Vias_and_Pads(), CPolyLine::NormalizeAreaOutlines(), and NormalizeAreaOutlines().

554 {
555  booleanOp( ctDifference, b, aFastMode );
556 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
void SHAPE_POLY_SET::BooleanSubtract ( const SHAPE_POLY_SET a,
const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

Performs boolean polyset difference between a and b, store the result in it self For aFastMode meaning, see function booleanOp

Definition at line 573 of file shape_poly_set.cpp.

References booleanOp().

576 {
577  booleanOp( ctDifference, a, b, aFastMode );
578 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
void SHAPE_POLY_SET::CacheTriangulation ( )

Definition at line 2068 of file shape_poly_set.cpp.

References checksum(), HasHoles(), HasTouchingHoles(), MD5_HASH::IsValid(), m_hash, m_triangulatedPolys, m_triangulationValid, OutlineCount(), PM_FAST, Polygon(), triangulateSingle(), and Unfracture().

Referenced by ZONE_CONTAINER::CacheTriangulation(), and PNS_KICAD_IFACE::syncZone().

2069 {
2070  bool recalculate = !m_hash.IsValid();
2071  MD5_HASH hash;
2072 
2073  if( !m_triangulationValid )
2074  recalculate = true;
2075 
2076  if( !recalculate )
2077  {
2078  hash = checksum();
2079 
2080  if( m_hash != hash )
2081  {
2082  m_hash = hash;
2083  recalculate = true;
2084  }
2085  }
2086 
2087  if( !recalculate )
2088  return;
2089 
2090  SHAPE_POLY_SET tmpSet = *this;
2091 
2092  if( !tmpSet.HasHoles() )
2093  tmpSet.Unfracture( PM_FAST );
2094 
2095  m_triangulatedPolys.clear();
2096 
2097  if( tmpSet.HasTouchingHoles() )
2098  {
2099  // temporary workaround for overlapping hole vertices that poly2tri doesn't handle
2100  m_triangulationValid = false;
2101  return;
2102  }
2103 
2104  for( int i = 0; i < tmpSet.OutlineCount(); i++ )
2105  {
2106  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2107  triangulateSingle( tmpSet.Polygon( i ), *m_triangulatedPolys.back() );
2108  }
2109 
2110  m_triangulationValid = true;
2111  m_hash = checksum();
2112 }
bool HasHoles() const
Returns true if the polygon set has any holes.
MD5_HASH checksum() const
int OutlineCount() const
Returns the number of outlines in the set
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
Class SHAPE_POLY_SET.
void triangulateSingle(const POLYGON &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)
bool IsValid() const
Definition: md5_hash.h:23
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes...
virtual VECTOR2I SHAPE::Centre ( ) const
inlinevirtualinherited

Function Centre()

Computes a center-of-mass of the shape

Returns
the center-of-mass point

Definition at line 151 of file shape.h.

References SHAPE::BBox(), BOX2< Vec >::Centre(), SHAPE::Format(), SHAPE::IsSolid(), SHAPE::Move(), and SHAPE::Parse().

152  {
153  return BBox( 0 ).Centre(); // if nothing better is available....
154  }
virtual const BOX2I BBox(int aClearance=0) const =0
Function BBox()
Vec Centre() const
Definition: box2.h:67
SHAPE_POLY_SET SHAPE_POLY_SET::Chamfer ( int  aDistance)

Function Chamfer returns a chamfered version of the polygon set.

Parameters
aDistanceis the chamfering distance.
Returns
SHAPE_POLY_SET - A set containing the chamfered version of this set.

Definition at line 1695 of file shape_poly_set.cpp.

References ChamferPolygon(), and m_polys.

Referenced by ZONE_CONTAINER::BuildSmoothedPoly(), and IsEmpty().

1696 {
1697  SHAPE_POLY_SET chamfered;
1698 
1699  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1700  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1701 
1702  return chamfered;
1703 }
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
Class SHAPE_POLY_SET.
SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::chamferFilletPolygon ( CORNER_MODE  aMode,
unsigned int  aDistance,
int  aIndex,
int  aSegments = -1 
)
private

Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in the set, depending on the aMode selected.

Parameters
aModerepresent which action will be taken: CORNER_MODE::CHAMFERED will return a chamfered version of the polygon, CORNER_MODE::FILLETED will return a filleted version of the polygon.
aDistanceis the chamfering distance if aMode = CHAMFERED; if aMode = FILLETED, is the filleting radius.
aIndexis the index of the polygon that will be chamfered/filleted.
aSegmentsis the number of filleting segments if aMode = FILLETED. If aMode = CHAMFERED, it is unused.
Returns
POLYGON - the chamfered/filleted version of the polygon.

Definition at line 1717 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::Append(), KiROUND(), SHAPE_LINE_CHAIN::Point(), Polygon(), RemoveNullSegments(), SHAPE_LINE_CHAIN::SetClosed(), and VECTOR2< T >::x.

Referenced by ChamferPolygon(), and FilletPolygon().

1721 {
1722  // Null segments create serious issues in calculations. Remove them:
1724 
1725  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1726  SHAPE_POLY_SET::POLYGON newPoly;
1727 
1728  // If the chamfering distance is zero, then the polygon remain intact.
1729  if( aDistance == 0 )
1730  {
1731  return currentPoly;
1732  }
1733 
1734  // Iterate through all the contours (outline and holes) of the polygon.
1735  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1736  {
1737  // Generate a new contour in the new polygon
1738  SHAPE_LINE_CHAIN newContour;
1739 
1740  // Iterate through the vertices of the contour
1741  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1742  {
1743  // Current vertex
1744  int x1 = currContour.Point( currVertex ).x;
1745  int y1 = currContour.Point( currVertex ).y;
1746 
1747  // Indices for previous and next vertices.
1748  int prevVertex;
1749  int nextVertex;
1750 
1751  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1752 
1753  // Previous vertex is the last one if the current vertex is the first one
1754  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1755 
1756  // next vertex is the first one if the current vertex is the last one.
1757  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1758 
1759  // Previous vertex computation
1760  double xa = currContour.Point( prevVertex ).x - x1;
1761  double ya = currContour.Point( prevVertex ).y - y1;
1762 
1763  // Next vertex computation
1764  double xb = currContour.Point( nextVertex ).x - x1;
1765  double yb = currContour.Point( nextVertex ).y - y1;
1766 
1767  // Compute the new distances
1768  double lena = hypot( xa, ya );
1769  double lenb = hypot( xb, yb );
1770 
1771  // Make the final computations depending on the mode selected, chamfered or filleted.
1772  if( aMode == CORNER_MODE::CHAMFERED )
1773  {
1774  double distance = aDistance;
1775 
1776  // Chamfer one half of an edge at most
1777  if( 0.5 * lena < distance )
1778  distance = 0.5 * lena;
1779 
1780  if( 0.5 * lenb < distance )
1781  distance = 0.5 * lenb;
1782 
1783  int nx1 = KiROUND( distance * xa / lena );
1784  int ny1 = KiROUND( distance * ya / lena );
1785 
1786  newContour.Append( x1 + nx1, y1 + ny1 );
1787 
1788  int nx2 = KiROUND( distance * xb / lenb );
1789  int ny2 = KiROUND( distance * yb / lenb );
1790 
1791  newContour.Append( x1 + nx2, y1 + ny2 );
1792  }
1793  else // CORNER_MODE = FILLETED
1794  {
1795  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1796 
1797  double radius = aDistance;
1798  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1799 
1800  // Do nothing in case of parallel edges
1801  if( std::isinf( denom ) )
1802  continue;
1803 
1804  // Limit rounding distance to one half of an edge
1805  if( 0.5 * lena * denom < radius )
1806  radius = 0.5 * lena * denom;
1807 
1808  if( 0.5 * lenb * denom < radius )
1809  radius = 0.5 * lenb * denom;
1810 
1811  // Calculate fillet arc absolute center point (xc, yx)
1812  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1813  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1814  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1815  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1816  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1817 
1818  // Calculate arc start and end vectors
1819  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1820  double xs = x1 + k * xa / lena - xc;
1821  double ys = y1 + k * ya / lena - yc;
1822  double xe = x1 + k * xb / lenb - xc;
1823  double ye = y1 + k * yb / lenb - yc;
1824 
1825  // Cosine of arc angle
1826  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1827 
1828  // Make sure the argument is in [-1,1], interval in which the acos function is
1829  // defined
1830  if( argument < -1 )
1831  argument = -1;
1832  else if( argument > 1 )
1833  argument = 1;
1834 
1835  double arcAngle = acos( argument );
1836 
1837  // Calculate the number of segments
1838  unsigned int segments = ceil( (double) aSegments * ( arcAngle / ( 2 * M_PI ) ) );
1839 
1840  double deltaAngle = arcAngle / segments;
1841  double startAngle = atan2( -ys, xs );
1842 
1843  // Flip arc for inner corners
1844  if( xa * yb - ya * xb <= 0 )
1845  deltaAngle *= -1;
1846 
1847  double nx = xc + xs;
1848  double ny = yc + ys;
1849 
1850  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1851 
1852  // Store the previous added corner to make a sanity check
1853  int prevX = KiROUND( nx );
1854  int prevY = KiROUND( ny );
1855 
1856  for( unsigned int j = 0; j < segments; j++ )
1857  {
1858  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1859  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1860 
1861  // Sanity check: the rounding can produce repeated corners; do not add them.
1862  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1863  {
1864  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1865  prevX = KiROUND( nx );
1866  prevY = KiROUND( ny );
1867  }
1868  }
1869  }
1870  }
1871 
1872  // Close the current contour and add it the new polygon
1873  newContour.SetClosed( true );
1874  newPoly.push_back( newContour );
1875  }
1876 
1877  return newPoly;
1878 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
static int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:107
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
Class SHAPE_LINE_CHAIN.
VECTOR2I & Point(int aIndex)
Function Point()
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon ( unsigned int  aDistance,
int  aIndex = 0 
)

Function Chamfer returns a chamfered version of the aIndex-th polygon.

Parameters
aDistanceis the chamfering distance.
aIndexis the index of the polygon to be chamfered.
Returns
POLYGON - A polygon containing the chamfered version of the aIndex-th polygon.

Definition at line 1571 of file shape_poly_set.cpp.

References chamferFilletPolygon().

Referenced by Chamfer(), and IsEmpty().

1572 {
1573  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1574 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aSegments=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
MD5_HASH SHAPE_POLY_SET::checksum ( ) const
private

Definition at line 2115 of file shape_poly_set.cpp.

References MD5_HASH::Finalize(), MD5_HASH::Hash(), and m_polys.

Referenced by CacheTriangulation(), and IsTriangulationUpToDate().

2116 {
2117  MD5_HASH hash;
2118 
2119  hash.Hash( m_polys.size() );
2120 
2121  for( const auto& outline : m_polys )
2122  {
2123  hash.Hash( outline.size() );
2124 
2125  for( const auto& lc : outline )
2126  {
2127  hash.Hash( lc.PointCount() );
2128 
2129  for( int i = 0; i < lc.PointCount(); i++ )
2130  {
2131  hash.Hash( lc.CPoint( i ).x );
2132  hash.Hash( lc.CPoint( i ).y );
2133  }
2134  }
2135  }
2136 
2137  hash.Finalize();
2138 
2139  return hash;
2140 }
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66
void Finalize()
Definition: md5_hash.cpp:76
const SHAPE_LINE_CHAIN& SHAPE_POLY_SET::CHole ( int  aOutline,
int  aHole 
) const
inline
CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aFirst,
int  aLast,
bool  aIterateHoles = false 
) const
inline

Definition at line 695 of file shape_poly_set.h.

References SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentContour, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentPolygon, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentVertex, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_iterateHoles, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_lastPolygon, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_poly, and OutlineCount().

Referenced by D_PAD::AddPrimitive(), DRAWSEGMENT::BuildPolyPointsList(), EDGE_MODULE::Draw(), PCB_IO::format(), DRAWSEGMENT::GetBoundingBox(), and BRDITEMS_PLOTTER::PlotFilledAreas().

696  {
697  CONST_ITERATOR iter;
698 
699  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
700  iter.m_currentPolygon = aFirst;
701  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
702  iter.m_currentContour = 0;
703  iter.m_currentVertex = 0;
704  iter.m_iterateHoles = aIterateHoles;
705 
706  return iter;
707  }
int OutlineCount() const
Returns the number of outlines in the set
Class SHAPE_POLY_SET.
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aOutline) const
inline

Definition at line 709 of file shape_poly_set.h.

References CIterate().

710  {
711  return CIterate( aOutline, aOutline );
712  }
CONST_ITERATOR CIterate() const
CONST_ITERATOR SHAPE_POLY_SET::CIterate ( ) const
inline

Definition at line 719 of file shape_poly_set.h.

References OutlineCount().

Referenced by CIterate(), and CIterateWithHoles().

720  {
721  return CIterate( 0, OutlineCount() - 1 );
722  }
CONST_ITERATOR CIterate() const
int OutlineCount() const
Returns the number of outlines in the set
CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( int  aOutline) const
inline

Definition at line 714 of file shape_poly_set.h.

References CIterate().

Referenced by EDIT_POINTS_FACTORY::buildForPolyOutline(), ZONE_CONTAINER::CIterateWithHoles(), and GRID_HELPER::computeAnchors().

715  {
716  return CIterate( aOutline, aOutline, true );
717  }
CONST_ITERATOR CIterate() const
CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( ) const
inline

Definition at line 724 of file shape_poly_set.h.

References CIterate(), and OutlineCount().

725  {
726  return CIterate( 0, OutlineCount() - 1, true );
727  }
CONST_ITERATOR CIterate() const
int OutlineCount() const
Returns the number of outlines in the set
SHAPE * SHAPE_POLY_SET::Clone ( ) const
overridevirtual

Function Clone()

Returns a dynamically allocated copy of the shape

Return values
copyof the shape

Reimplemented from SHAPE.

Definition at line 66 of file shape_poly_set.cpp.

References SHAPE_POLY_SET().

67 {
68  return new SHAPE_POLY_SET( *this );
69 }
bool SHAPE::Collide ( const SHAPE aShape,
int  aClearance,
VECTOR2I aMTV 
) const
virtualinherited

Function Collide()

Checks if the boundary of shape (this) lies closer to the shape aShape than aClearance, indicating a collision.

Parameters
aShapeshape to check collision against
aClearanceminimum clearance
aMTVminimum translation vector
Returns
true, if there is a collision.

Definition at line 456 of file shape_collisions.cpp.

References CollideShapes().

457 {
458  return CollideShapes( this, aShape, aClerance, true, aMTV );
459 }
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)
bool SHAPE::Collide ( const SHAPE aShape,
int  aClearance = 0 
) const
virtualinherited

Definition at line 462 of file shape_collisions.cpp.

References CollideShapes(), and dummy().

463 {
464  VECTOR2I dummy;
465 
466  return CollideShapes( this, aShape, aClerance, false, dummy );
467 }
static LIB_PART * dummy()
Used when a LIB_PART is not found in library to draw a dummy shape This component is a 400 mils squar...
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)
bool SHAPE_POLY_SET::Collide ( const VECTOR2I aP,
int  aClearance = 0 
) const
overridevirtual

Function Collide Checks whether the point aP collides with the inside of the polygon set; if the point lies on an edge or on a corner of any of the polygons, there is no collision: the edges does not belong to the polygon itself.

Parameters
aPis the VECTOR2I point whose collision with respect to the poly set will be tested.
aClearanceis the security distance; if the point lies closer to the polygon than aClearance distance, then there is a collision.
Returns
bool - true if the point aP collides with the polygon; false in any other case.

Reimplemented from SHAPE.

Definition at line 1231 of file shape_poly_set.cpp.

References Contains(), Inflate(), and SHAPE_POLY_SET().

Referenced by IsSolid().

1232 {
1233  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1234 
1235  // Inflate the polygon if necessary.
1236  if( aClearance > 0 )
1237  {
1238  // fixme: the number of arc segments should not be hardcoded
1239  polySet.Inflate( aClearance, 8 );
1240  }
1241 
1242  // There is a collision if and only if the point is inside of the polygon.
1243  return polySet.Contains( aP );
1244 }
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
Class SHAPE_POLY_SET.
bool SHAPE_POLY_SET::Collide ( const SEG aSeg,
int  aClearance = 0 
) const
inlineoverridevirtual

Function Collide()

Checks if the boundary of shape (this) lies closer to the segment aSeg than aClearance, indicating a collision.

Returns
true, if there is a collision.

Implements SHAPE.

Definition at line 908 of file shape_poly_set.h.

References CollideEdge(), CollideVertex(), and Contains().

908 { return false; }
bool SHAPE_POLY_SET::CollideEdge ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex,
int  aClearance = 0 
)

Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polygon.

Parameters
aPointis the VECTOR2I point whose collision with respect to the polygon will be tested.
aClearanceis the security distance; if aPoint lies closer to a vertex than aClearance distance, then there is a collision.
aClosestVertexis the index of the closes vertex to aPoint.
Returns
bool - true if there is a collision, false in any other case.

Definition at line 1372 of file shape_poly_set.cpp.

References SEG::Distance(), SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::GetIndex(), and IterateSegmentsWithHoles().

Referenced by Collide(), and ZONE_CONTAINER::HitTestForEdge().

1374 {
1375  // Shows whether there was a collision
1376  bool collision = false;
1377 
1378  SEGMENT_ITERATOR iterator;
1379 
1380  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1381  {
1382  SEG currentSegment = *iterator;
1383  int distance = currentSegment.Distance( aPoint );
1384 
1385  // Check for collisions
1386  if( distance <= aClearance )
1387  {
1388  collision = true;
1389 
1390  // Update aClearance to look for closer edges
1391  aClearance = distance;
1392 
1393  // Store the indices that identify the vertex
1394  aClosestVertex = iterator.GetIndex();
1395  }
1396  }
1397 
1398  return collision;
1399 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
Definition: seg.h:36
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
bool SHAPE_POLY_SET::CollideVertex ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex,
int  aClearance = 0 
)

Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the polygon.

Parameters
aPointis the VECTOR2I point whose collision with respect to the polygon will be tested.
aClearanceis the security distance; if aPoint lies closer to a vertex than aClearance distance, then there is a collision.
aClosestVertexis the index of the closes vertex to aPoint.
Returns
bool - true if there is a collision, false in any other case.

Definition at line 1334 of file shape_poly_set.cpp.

References delta, VECTOR2< T >::EuclideanNorm(), and IterateWithHoles().

Referenced by Collide(), and ZONE_CONTAINER::HitTestForCorner().

1336 {
1337  // Shows whether there was a collision
1338  bool collision = false;
1339 
1340  // Difference vector between each vertex and aPoint.
1341  VECTOR2D delta;
1342  double distance, clearance;
1343 
1344  // Convert clearance to double for precission when comparing distances
1345  clearance = aClearance;
1346 
1347  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1348  {
1349  // Get the difference vector between current vertex and aPoint
1350  delta = *iterator - aPoint;
1351 
1352  // Compute distance
1353  distance = delta.EuclideanNorm();
1354 
1355  // Check for collisions
1356  if( distance <= clearance )
1357  {
1358  collision = true;
1359 
1360  // Update aClearance to look for closer vertices
1361  clearance = distance;
1362 
1363  // Store the indices that identify the vertex
1364  aClosestVertex = iterator.GetIndex();
1365  }
1366  }
1367 
1368  return collision;
1369 }
static const int delta[8][2]
Definition: solve.cpp:112
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:294
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR IterateWithHoles()
Function IterateWithHoles.
bool SHAPE_POLY_SET::Contains ( const VECTOR2I aP,
int  aSubpolyIndex = -1,
bool  aIgnoreHoles = false 
) const

Returns true if a given subpolygon contains the point aP.

Parameters
aPis the point to check
aSubpolyIndexis the subpolygon to check, or -1 to check all
aIgnoreHolescontrols whether or not internal holes are considered
Returns
true if the polygon contains the point

Definition at line 1402 of file shape_poly_set.cpp.

References containsSingle(), m_polys, and OutlineCount().

Referenced by ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), Collide(), DRC::doEdgeZoneDrc(), D_PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::HitTest(), ZONE_CONTAINER::HitTestFilledArea(), ZONE_CONTAINER::HitTestInsideZone(), BOARD::TestAreaIntersection(), and DRC::TestZoneToZoneOutline().

1403 {
1404  if( m_polys.size() == 0 ) // empty set?
1405  return false;
1406 
1407  // If there is a polygon specified, check the condition against that polygon
1408  if( aSubpolyIndex >= 0 )
1409  return containsSingle( aP, aSubpolyIndex, aIgnoreHoles );
1410 
1411  // In any other case, check it against all polygons in the set
1412  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1413  {
1414  if( containsSingle( aP, polygonIdx, aIgnoreHoles ) )
1415  return true;
1416  }
1417 
1418  return false;
1419 }
int OutlineCount() const
Returns the number of outlines in the set
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
bool SHAPE_POLY_SET::containsSingle ( const VECTOR2I aP,
int  aSubpolyIndex,
bool  aIgnoreHoles = false 
) const
private

containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.

If the points lies on an edge, the polygon is considered to contain it.

Parameters
aPis the VECTOR2I point whose position with respect to the inside of the aSubpolyIndex-th polygon will be tested.
aSubpolyIndexis an integer specifying which polygon in the set has to be checked.
aIgnoreHolescan be set to true to ignore internal holes in the polygon
Returns
bool - true if aP is inside aSubpolyIndex-th polygon; false in any other case.

Definition at line 1440 of file shape_poly_set.cpp.

References CHole(), HoleCount(), m_polys, pointInPolygon(), and SHAPE_LINE_CHAIN::PointOnEdge().

Referenced by Contains(), DistanceToPolygon(), and IsEmpty().

1441 {
1442  // Check that the point is inside the outline
1443  if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
1444  {
1445  if( !aIgnoreHoles )
1446  {
1447  // Check that the point is not in any of the holes
1448  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1449  {
1450  const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
1451 
1452  // If the point is inside a hole (and not on its edge),
1453  // it is outside of the polygon
1454  if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
1455  return false;
1456  }
1457  }
1458 
1459  return true;
1460  }
1461 
1462  return false;
1463 }
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool pointInPolygon(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath) const
Class SHAPE_LINE_CHAIN.
const SHAPE_LINE_CHAIN SHAPE_POLY_SET::convertFromClipper ( const ClipperLib::Path &  aPath)
private

Definition at line 476 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::Append(), and SHAPE_LINE_CHAIN::SetClosed().

Referenced by importTree(), and IsEmpty().

477 {
478  SHAPE_LINE_CHAIN lc;
479 
480  for( unsigned int i = 0; i < aPath.size(); i++ )
481  lc.Append( aPath[i].X, aPath[i].Y );
482 
483  lc.SetClosed( true );
484 
485  return lc;
486 }
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
Class SHAPE_LINE_CHAIN.
const Path SHAPE_POLY_SET::convertToClipper ( const SHAPE_LINE_CHAIN aPath,
bool  aRequiredOrientation 
)
private

Definition at line 458 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::PointCount(), vertex(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by booleanOp(), Inflate(), and IsEmpty().

460 {
461  Path c_path;
462 
463  for( int i = 0; i < aPath.PointCount(); i++ )
464  {
465  const VECTOR2I& vertex = aPath.CPoint( i );
466  c_path.push_back( IntPoint( vertex.x, vertex.y ) );
467  }
468 
469  if( Orientation( c_path ) != aRequiredOrientation )
470  ReversePath( c_path );
471 
472  return c_path;
473 }
int PointCount() const
Function PointCount()
VECTOR2I & vertex(int aCornerId)
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
const POLYGON& SHAPE_POLY_SET::CPolygon ( int  aIndex) const
inline
const VECTOR2I & SHAPE_POLY_SET::CVertex ( int  aIndex,
int  aOutline,
int  aHole 
) const

Returns the index-th vertex in a given hole outline within a given outline

Definition at line 286 of file shape_poly_set.cpp.

References m_polys.

Referenced by CVertex(), ZONE_CONTAINER::GetCornerPosition(), DRAWSEGMENT::GetPosition(), DRAWSEGMENT::HitTest(), and POINT_EDITOR::updatePoints().

287 {
288  if( aOutline < 0 )
289  aOutline += m_polys.size();
290 
291  int idx;
292 
293  if( aHole < 0 )
294  idx = 0;
295  else
296  idx = aHole + 1;
297 
298  assert( aOutline < (int) m_polys.size() );
299  assert( idx < (int) m_polys[aOutline].size() );
300 
301  return m_polys[aOutline][idx].CPoint( aIndex );
302 }
const VECTOR2I & SHAPE_POLY_SET::CVertex ( int  aGlobalIndex) const

Returns the aGlobalIndex-th vertex in the poly set

Definition at line 317 of file shape_poly_set.cpp.

References GetRelativeIndices(), SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, m_polys, and SHAPE_POLY_SET::VERTEX_INDEX::m_vertex.

318 {
320 
321  // Assure the passed index references a legal position; abort otherwise
322  if( !GetRelativeIndices( aGlobalIndex, &index ) )
323  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
324 
325  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
326 }
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
const VECTOR2I & SHAPE_POLY_SET::CVertex ( SHAPE_POLY_SET::VERTEX_INDEX  index) const

Returns the index-th vertex in a given hole outline within a given outline

Definition at line 335 of file shape_poly_set.cpp.

References CVertex(), SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, and SHAPE_POLY_SET::VERTEX_INDEX::m_vertex.

336 {
337  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
338 }
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
const VECTOR2I& SHAPE_POLY_SET::cvertex ( int  aCornerId) const
private

Referenced by IsEmpty().

void SHAPE_POLY_SET::DeletePolygon ( int  aIdx)

Deletes aIdx-th polygon from the set

Definition at line 1316 of file shape_poly_set.cpp.

References m_polys.

Referenced by ZONE_FILLER::Fill(), and IsEmpty().

1317 {
1318  m_polys.erase( m_polys.begin() + aIdx );
1319 }
int SHAPE_POLY_SET::Distance ( VECTOR2I  aPoint)

Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the set.

Parameters
aPointis the point whose distance to the set has to be measured.
Returns
int - The minimum distance between aPoint and all the polygons in the set. If the point is contained in any of the polygons, the distance is zero.

Definition at line 1646 of file shape_poly_set.cpp.

References DistanceToPolygon(), and m_polys.

Referenced by DRC::doTrackKeepoutDrc(), IsEmpty(), and DRC::testKeepoutAreas().

1647 {
1648  int currentDistance;
1649  int minDistance = DistanceToPolygon( aPoint, 0 );
1650 
1651  // Iterate through all the polygons and get the minimum distance.
1652  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1653  {
1654  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1655 
1656  if( currentDistance < minDistance )
1657  minDistance = currentDistance;
1658  }
1659 
1660  return minDistance;
1661 }
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint...
int SHAPE_POLY_SET::Distance ( const SEG aSegment,
int  aSegmentWidth = 0 
)

Function DistanceToPolygon computes the minimum distance between aSegment and all the polygons in the set.

Parameters
aSegmentis the segment whose distance to the polygon set has to be measured.
aSegmentWidthis the width of the segment; defaults to zero.
Returns
int - The minimum distance between aSegment and all the polygons in the set. If the point is contained in the polygon, the distance is zero.

Definition at line 1664 of file shape_poly_set.cpp.

References DistanceToPolygon(), and m_polys.

1665 {
1666  int currentDistance;
1667  int minDistance = DistanceToPolygon( aSegment, 0 );
1668 
1669  // Iterate through all the polygons and get the minimum distance.
1670  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1671  {
1672  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1673 
1674  if( currentDistance < minDistance )
1675  minDistance = currentDistance;
1676  }
1677 
1678  return minDistance;
1679 }
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint...
int SHAPE_POLY_SET::DistanceToPolygon ( VECTOR2I  aPoint,
int  aIndex 
)

Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.

Parameters
aPointis the point whose distance to the aIndex-th polygon has to be measured.
aIndexis the index of the polygon whose distace to aPoint has to be measured.
Returns
int - The minimum distance between aPoint and all the segments of the aIndex-th polygon. If the point is contained in the polygon, the distance is zero.

Definition at line 1585 of file shape_poly_set.cpp.

References containsSingle(), SEG::Distance(), and IterateSegmentsWithHoles().

Referenced by Distance(), and IsEmpty().

1586 {
1587  // We calculate the min dist between the segment and each outline segment
1588  // However, if the segment to test is inside the outline, and does not cross
1589  // any edge, it can be seen outside the polygon.
1590  // Therefore test if a segment end is inside ( testing only one end is enough )
1591  if( containsSingle( aPoint, aPolygonIndex ) )
1592  return 0;
1593 
1594  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1595 
1596  SEG polygonEdge = *iterator;
1597  int minDistance = polygonEdge.Distance( aPoint );
1598 
1599  for( iterator++; iterator && minDistance > 0; iterator++ )
1600  {
1601  polygonEdge = *iterator;
1602 
1603  int currentDistance = polygonEdge.Distance( aPoint );
1604 
1605  if( currentDistance < minDistance )
1606  minDistance = currentDistance;
1607  }
1608 
1609  return minDistance;
1610 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
Definition: seg.h:36
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
int SHAPE_POLY_SET::DistanceToPolygon ( SEG  aSegment,
int  aIndex,
int  aSegmentWidth = 0 
)

Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aSegment with a possible width.

Parameters
aSegmentis the segment whose distance to the aIndex-th polygon has to be measured.
aIndexis the index of the polygon whose distace to aPoint has to be measured.
aSegmentWidthis the width of the segment; defaults to zero.
Returns
int - The minimum distance between aSegment and all the segments of the aIndex-th polygon. If the point is contained in the polygon, the distance is zero.

Definition at line 1613 of file shape_poly_set.cpp.

References SEG::A, containsSingle(), SEG::Distance(), and IterateSegmentsWithHoles().

1614 {
1615  // We calculate the min dist between the segment and each outline segment
1616  // However, if the segment to test is inside the outline, and does not cross
1617  // any edge, it can be seen outside the polygon.
1618  // Therefore test if a segment end is inside ( testing only one end is enough )
1619  if( containsSingle( aSegment.A, aPolygonIndex ) )
1620  return 0;
1621 
1622  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1623 
1624  SEG polygonEdge = *iterator;
1625  int minDistance = polygonEdge.Distance( aSegment );
1626 
1627  for( iterator++; iterator && minDistance > 0; iterator++ )
1628  {
1629  polygonEdge = *iterator;
1630 
1631  int currentDistance = polygonEdge.Distance( aSegment );
1632 
1633  if( currentDistance < minDistance )
1634  minDistance = currentDistance;
1635  }
1636 
1637  // Take into account the width of the segment
1638  if( aSegmentWidth > 0 )
1639  minDistance -= aSegmentWidth / 2;
1640 
1641  // Return the maximum of minDistance and zero
1642  return minDistance < 0 ? 0 : minDistance;
1643 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
Definition: seg.h:36
VECTOR2I A
Definition: seg.h:46
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
SHAPE_POLY_SET SHAPE_POLY_SET::Fillet ( int  aRadius,
int  aSegments 
)

Function Fillet returns a filleted version of the polygon set.

Parameters
aRadiusis the fillet radius.
aSegmentsis the number of segments / fillet.
Returns
SHAPE_POLY_SET - A set containing the filleted version of this set.

Definition at line 1706 of file shape_poly_set.cpp.

References FilletPolygon(), and m_polys.

Referenced by ZONE_CONTAINER::BuildSmoothedPoly(), and IsEmpty().

1707 {
1708  SHAPE_POLY_SET filleted;
1709 
1710  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1711  filleted.m_polys.push_back( FilletPolygon( aRadius, aSegments, polygonIdx ) );
1712 
1713  return filleted;
1714 }
Class SHAPE_POLY_SET.
POLYGON FilletPolygon(unsigned int aRadius, unsigned int aSegments, int aIndex=0)
Function Fillet returns a filleted version of the aIndex-th polygon.
SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon ( unsigned int  aRadius,
unsigned int  aSegments,
int  aIndex = 0 
)

Function Fillet returns a filleted version of the aIndex-th polygon.

Parameters
aRadiusis the fillet radius.
aSegmentsis the number of segments / fillet.
aIndexis the index of the polygon to be filleted
Returns
POLYGON - A polygon containing the filleted version of the aIndex-th polygon.

Definition at line 1577 of file shape_poly_set.cpp.

References chamferFilletPolygon().

Referenced by Fillet(), and IsEmpty().

1580 {
1581  return chamferFilletPolygon( CORNER_MODE::FILLETED, aRadius, aIndex, aSegments );
1582 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aSegments=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
const std::string SHAPE_POLY_SET::Format ( ) const
overridevirtual

Reimplemented from SHAPE.

Definition at line 1113 of file shape_poly_set.cpp.

References m_polys.

1114 {
1115  std::stringstream ss;
1116 
1117  ss << "polyset " << m_polys.size() << "\n";
1118 
1119  for( unsigned i = 0; i < m_polys.size(); i++ )
1120  {
1121  ss << "poly " << m_polys[i].size() << "\n";
1122 
1123  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1124  {
1125  ss << m_polys[i][j].PointCount() << "\n";
1126 
1127  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1128  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1129  }
1130 
1131  ss << "\n";
1132  }
1133 
1134  return ss.str();
1135 }
void SHAPE_POLY_SET::Fracture ( POLYGON_MODE  aFastMode)

Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the outer ring to the inner holes For aFastMode meaning, see function booleanOp

Definition at line 874 of file shape_poly_set.cpp.

References fractureSingle(), m_polys, and Simplify().

Referenced by addHoleToPolygon(), D_PAD::buildCustomPadPolygon(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), export_vrml_drawsegment(), export_vrml_edge_module(), ZONE_FILLER::fillSingleZone(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), C3D_RENDER_RAYTRACING::reload(), and ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon().

875 {
876  Simplify( aFastMode ); // remove overlapping holes/degeneracy
877 
878  for( POLYGON& paths : m_polys )
879  {
880  fractureSingle( paths );
881  }
882 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void fractureSingle(POLYGON &paths)
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
void SHAPE_POLY_SET::fractureSingle ( POLYGON paths)
private

Definition at line 772 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::Append(), FractureEdge::m_connected, FractureEdge::m_next, FractureEdge::m_p1, max, processEdge(), SHAPE_LINE_CHAIN::SetClosed(), and VECTOR2< T >::x.

Referenced by Fracture(), and IsEmpty().

773 {
774  FractureEdgeSet edges;
775  FractureEdgeSet border_edges;
776  FractureEdge* root = NULL;
777 
778  bool first = true;
779 
780  if( paths.size() == 1 )
781  return;
782 
783  int num_unconnected = 0;
784 
785  for( SHAPE_LINE_CHAIN& path : paths )
786  {
787  int index = 0;
788 
789  FractureEdge* prev = NULL, * first_edge = NULL;
790 
791  int x_min = std::numeric_limits<int>::max();
792 
793  for( int i = 0; i < path.PointCount(); i++ )
794  {
795  const VECTOR2I& p = path.CPoint( i );
796 
797  if( p.x < x_min )
798  x_min = p.x;
799  }
800 
801  for( int i = 0; i < path.PointCount(); i++ )
802  {
803  FractureEdge* fe = new FractureEdge( first, &path, index++ );
804 
805  if( !root )
806  root = fe;
807 
808  if( !first_edge )
809  first_edge = fe;
810 
811  if( prev )
812  prev->m_next = fe;
813 
814  if( i == path.PointCount() - 1 )
815  fe->m_next = first_edge;
816 
817  prev = fe;
818  edges.push_back( fe );
819 
820  if( !first )
821  {
822  if( fe->m_p1.x == x_min )
823  border_edges.push_back( fe );
824  }
825 
826  if( !fe->m_connected )
827  num_unconnected++;
828  }
829 
830  first = false; // first path is always the outline
831  }
832 
833  // keep connecting holes to the main outline, until there's no holes left...
834  while( num_unconnected > 0 )
835  {
836  int x_min = std::numeric_limits<int>::max();
837 
838  FractureEdge* smallestX = NULL;
839 
840  // find the left-most hole edge and merge with the outline
841  for( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
842  {
843  int xt = (*i)->m_p1.x;
844 
845  if( ( xt < x_min ) && !(*i)->m_connected )
846  {
847  x_min = xt;
848  smallestX = *i;
849  }
850  }
851 
852  num_unconnected -= processEdge( edges, smallestX );
853  }
854 
855  paths.clear();
856  SHAPE_LINE_CHAIN newPath;
857 
858  newPath.SetClosed( true );
859 
860  FractureEdge* e;
861 
862  for( e = root; e->m_next != root; e = e->m_next )
863  newPath.Append( e->m_p1 );
864 
865  newPath.Append( e->m_p1 );
866 
867  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
868  delete *i;
869 
870  paths.push_back( newPath );
871 }
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
#define max(a, b)
Definition: auxiliary.h:86
Class SHAPE_LINE_CHAIN.
FractureEdge * m_next
std::vector< FractureEdge * > FractureEdgeSet
SHAPE_LINE_CHAIN& SHAPE_POLY_SET::getContourForCorner ( int  aCornerId,
int &  aIndexWithinContour 
)
private

Referenced by IsEmpty().

bool SHAPE_POLY_SET::GetGlobalIndex ( SHAPE_POLY_SET::VERTEX_INDEX  aRelativeIndices,
int &  aGlobalIdx 
)

Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon, contour and vertex.

Parameters
aRelativeIndicesis the set of relative indices.
aGlobalIdx[out] is the computed global index.
Returns
bool - true if the relative indices are correct; false otherwise. The computed global index is returned in the aGlobalIdx reference.

Definition at line 112 of file shape_poly_set.cpp.

References SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, m_polys, SHAPE_POLY_SET::VERTEX_INDEX::m_vertex, and Polygon().

Referenced by GetNeighbourIndexes(), and ZONE_CONTAINER::GetSelectedCorner().

114 {
115  int selectedVertex = aRelativeIndices.m_vertex;
116  unsigned int selectedContour = aRelativeIndices.m_contour;
117  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
118 
119  // Check whether the vertex indices make sense in this poly set
120  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
121  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
122  {
123  POLYGON currentPolygon;
124 
125  aGlobalIdx = 0;
126 
127  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
128  {
129  currentPolygon = Polygon( polygonIdx );
130 
131  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
132  {
133  aGlobalIdx += currentPolygon[contourIdx].PointCount();
134  }
135  }
136 
137  currentPolygon = Polygon( selectedPolygon );
138 
139  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
140  {
141  aGlobalIdx += currentPolygon[contourIdx].PointCount();
142  }
143 
144  aGlobalIdx += selectedVertex;
145 
146  return true;
147  }
148  else
149  {
150  return false;
151  }
152 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
bool SHAPE_POLY_SET::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 contour in the polygon set.

they are often aGlobalIndex-1 and aGlobalIndex+1, but not for the first and last corner of the contour.

Parameters
aGlobalIndexis index of the corner, globally indexed between all edges in all contours
aPrevious- the globalIndex of the previous corner of the same contour.
aNext- the globalIndex of the next corner of the same contour.
Returns
true if OK, false if aGlobalIndex is out of range

Definition at line 341 of file shape_poly_set.cpp.

References GetGlobalIndex(), GetRelativeIndices(), SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, m_polys, SHAPE_POLY_SET::VERTEX_INDEX::m_vertex, and next().

Referenced by ZONE_CONTAINER::MoveEdge().

342 {
344 
345  // If the edge does not exist, throw an exception, it is an illegal access memory error
346  if( !GetRelativeIndices( aGlobalIndex, &index ) )
347  return false;
348 
349  // Calculate the previous and next index of aGlobalIndex, corresponding to
350  // the same contour;
351  VERTEX_INDEX inext = index;
352  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
353 
354  if( index.m_vertex == 0 )
355  {
356  index.m_vertex = lastpoint;
357  inext.m_vertex = 1;
358  }
359  else if( index.m_vertex == lastpoint )
360  {
361  index.m_vertex--;
362  inext.m_vertex = 0;
363  }
364  else
365  {
366  inext.m_vertex++;
367  index.m_vertex--;
368  }
369 
370  if( aPrevious )
371  {
372  int previous;
373  GetGlobalIndex( index, previous );
374  *aPrevious = previous;
375  }
376 
377  if( aNext )
378  {
379  int next;
380  GetGlobalIndex( inext, next );
381  *aNext = next;
382  }
383 
384  return true;
385 }
CITER next(CITER it)
Definition: ptree.cpp:130
Struct VERTEX_INDEX.
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon...
bool SHAPE_POLY_SET::GetRelativeIndices ( int  aGlobalIdx,
SHAPE_POLY_SET::VERTEX_INDEX aRelativeIndices 
) const

Function GetRelativeIndices.

Converts a global vertex index —i.e., a number that globally identifies a vertex in a concatenated list of all vertices in all contours— and get the index of the vertex relative to the contour relative to the polygon in which it is.

Parameters
aGlobalIdxis the global index of the corner whose structured index wants to be found
aRelativeIndicesis a pointer to the set of relative indices to store.
Returns
bool - true if the global index is correct and the information in aRelativeIndices is valid; false otherwise.

Definition at line 72 of file shape_poly_set.cpp.

References CPolygon(), SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, SHAPE_POLY_SET::VERTEX_INDEX::m_vertex, OutlineCount(), and SHAPE_LINE_CHAIN::PointCount().

Referenced by CVertex(), PCB_EDIT_FRAME::Delete_Zone_Contour(), DRC::doEdgeZoneDrc(), ZONE_CONTAINER::GetCornerPosition(), GetNeighbourIndexes(), InsertVertex(), IsVertexInHole(), IterateFromVertexWithHoles(), RemoveVertex(), ZONE_CONTAINER::SetCornerPosition(), ZONE_CONTAINER::SetSelectedCorner(), and Vertex().

74 {
75  int polygonIdx = 0;
76  unsigned int contourIdx = 0;
77  int vertexIdx = 0;
78 
79  int currentGlobalIdx = 0;
80 
81  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
82  {
83  const POLYGON currentPolygon = CPolygon( polygonIdx );
84 
85  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
86  {
87  SHAPE_LINE_CHAIN currentContour = currentPolygon[contourIdx];
88  int totalPoints = currentContour.PointCount();
89 
90  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
91  {
92  // Check if the current vertex is the globally indexed as aGlobalIdx
93  if( currentGlobalIdx == aGlobalIdx )
94  {
95  aRelativeIndices->m_polygon = polygonIdx;
96  aRelativeIndices->m_contour = contourIdx;
97  aRelativeIndices->m_vertex = vertexIdx;
98 
99  return true;
100  }
101 
102  // Advance
103  currentGlobalIdx++;
104  }
105  }
106  }
107 
108  return false;
109 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
int PointCount() const
Function PointCount()
int OutlineCount() const
Returns the number of outlines in the set
Class SHAPE_LINE_CHAIN.
const POLYGON & CPolygon(int aIndex) const
bool SHAPE_POLY_SET::HasHoles ( ) const

Returns true if the polygon set has any holes.

Definition at line 1046 of file shape_poly_set.cpp.

References m_polys.

Referenced by CacheTriangulation().

1047 {
1048  // Iterate through all the polygons on the set
1049  for( const POLYGON& paths : m_polys )
1050  {
1051  // If any of them has more than one contour, it is a hole.
1052  if( paths.size() > 1 )
1053  return true;
1054  }
1055 
1056  // Return false if and only if every polygon has just one outline, without holes.
1057  return false;
1058 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
bool SHAPE_POLY_SET::HasTouchingHoles ( ) const

Returns true if the polygon set has any holes tha share a vertex.

Definition at line 2143 of file shape_poly_set.cpp.

References CPolygon(), hasTouchingHoles(), and OutlineCount().

Referenced by CacheTriangulation().

2144 {
2145  for( int i = 0; i < OutlineCount(); i++ )
2146  {
2147  if( hasTouchingHoles( CPolygon( i ) ) )
2148  {
2149  return true;
2150  }
2151  }
2152 
2153  return false;
2154 }
int OutlineCount() const
Returns the number of outlines in the set
bool hasTouchingHoles(const POLYGON &aPoly) const
Returns true if the polygon set has any holes that touch share a vertex.
const POLYGON & CPolygon(int aIndex) const
bool SHAPE_POLY_SET::hasTouchingHoles ( const POLYGON aPoly) const
private

Returns true if the polygon set has any holes that touch share a vertex.

Definition at line 2157 of file shape_poly_set.cpp.

Referenced by HasTouchingHoles().

2158 {
2159  std::vector< VECTOR2I > pts;
2160 
2161  for( const auto& lc : aPoly )
2162  {
2163  for( int i = 0; i < lc.PointCount(); i++ )
2164  {
2165  const auto p = lc.CPoint( i );
2166 
2167  if( std::find( pts.begin(), pts.end(), p ) != pts.end() )
2168  {
2169  return true;
2170  }
2171 
2172  pts.push_back( p );
2173  }
2174  }
2175 
2176  return false;
2177 }
SHAPE_LINE_CHAIN& SHAPE_POLY_SET::Hole ( int  aOutline,
int  aHole 
)
inline

Returns the reference to aHole-th hole in the aIndex-th outline

Definition at line 591 of file shape_poly_set.h.

References m_polys.

Referenced by Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), export_vrml_board(), DSN::SPECCTRA_DB::fillBOUNDARY(), and ZONE_CREATE_HELPER::performZoneCutout().

592  {
593  return m_polys[aOutline][aHole + 1];
594  }
int SHAPE_POLY_SET::HoleCount ( int  aOutline) const
inline

Returns the number of holes in a given outline

Definition at line 558 of file shape_poly_set.h.

References m_polys.

Referenced by CINFO3D_VISU::AddSolidAreasShapesToContainer(), CLAYER_TRIANGLES::AddToMiddleContourns(), ZONE_CONTAINER::AppendCorner(), containsSingle(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), Convert_shape_line_polygon_to_triangles(), KIGFX::PCB_PAINTER::draw(), export_vrml_board(), DSN::SPECCTRA_DB::fillBOUNDARY(), and PlotLayerOutlines().

559  {
560  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
561  return 0;
562 
563  // the first polygon in m_polys[aOutline] is the main contour,
564  // only others are holes:
565  return m_polys[aOutline].size() - 1;
566  }
void SHAPE_POLY_SET::importTree ( ClipperLib::PolyTree *  tree)
private

Definition at line 636 of file shape_poly_set.cpp.

References convertFromClipper(), and m_polys.

Referenced by booleanOp(), Inflate(), and IsEmpty().

637 {
638  m_polys.clear();
639 
640  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
641  {
642  if( !n->IsHole() )
643  {
644  POLYGON paths;
645  paths.reserve( n->Childs.size() + 1 );
646  paths.push_back( convertFromClipper( n->Contour ) );
647 
648  for( unsigned int i = 0; i < n->Childs.size(); i++ )
649  paths.push_back( convertFromClipper( n->Childs[i]->Contour ) );
650 
651  m_polys.push_back( paths );
652  }
653  }
654 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
const SHAPE_LINE_CHAIN convertFromClipper(const ClipperLib::Path &aPath)
void SHAPE_POLY_SET::Inflate ( int  aFactor,
int  aCircleSegmentsCount 
)

Performs outline inflation/deflation, using round corners.

Definition at line 589 of file shape_poly_set.cpp.

References abs, convertToClipper(), importTree(), m_polys, and SEG_CNT_MAX.

Referenced by D_PAD::buildCustomPadPolygon(), ZONE_FILLER::buildZoneFeatureHoleList(), Collide(), ZONE_FILLER::computeRawFilledAreas(), CINFO3D_VISU::createNewPadWithClearance(), KIGFX::PCB_PAINTER::draw(), D_PAD::DrawShape(), export_vrml_drawsegment(), export_vrml_edge_module(), ZONE_FILLER::fillSingleZone(), MODULE::GetBoundingPoly(), PlotSolderMaskLayer(), ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon(), TransformRoundRectToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

590 {
591  // A static table to avoid repetitive calculations of the coefficient
592  // 1.0 - cos( M_PI/aCircleSegmentsCount)
593  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
594  #define SEG_CNT_MAX 64
595  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
596 
597  ClipperOffset c;
598 
599  for( const POLYGON& poly : m_polys )
600  {
601  for( unsigned int i = 0; i < poly.size(); i++ )
602  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), jtRound,
603  etClosedPolygon );
604  }
605 
606  PolyTree solution;
607 
608  // Calculate the arc tolerance (arc error) from the seg count by circle.
609  // the seg count is nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aFactor))
610  // see:
611  // www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
612 
613  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
614  aCircleSegmentsCount = 6;
615 
616  double coeff;
617 
618  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
619  {
620  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
621 
622  if( aCircleSegmentsCount <= SEG_CNT_MAX )
623  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
624  }
625  else
626  coeff = arc_tolerance_factor[aCircleSegmentsCount];
627 
628  c.ArcTolerance = std::abs( aFactor ) * coeff;
629 
630  c.Execute( solution, aFactor );
631 
632  importTree( &solution );
633 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
const ClipperLib::Path convertToClipper(const SHAPE_LINE_CHAIN &aPath, bool aRequiredOrientation)
#define abs(a)
Definition: auxiliary.h:84
#define SEG_CNT_MAX
void importTree(ClipperLib::PolyTree *tree)
void SHAPE_POLY_SET::InsertVertex ( int  aGlobalIndex,
VECTOR2I  aNewVertex 
)

Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.

Parameters
aGlobalIndexis the global index of the position in which teh new vertex will be inserted.
aNewVertexis the new inserted vertex.

Definition at line 205 of file shape_poly_set.cpp.

References Append(), GetRelativeIndices(), SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, m_polys, SHAPE_POLY_SET::VERTEX_INDEX::m_vertex, and TotalVertices().

Referenced by POINT_EDITOR::addCorner(), PCB_EDIT_FRAME::Process_Special_Functions(), and PCB_EDIT_FRAME::Start_Move_Zone_Corner().

206 {
207  VERTEX_INDEX index;
208 
209  if( aGlobalIndex < 0 )
210  aGlobalIndex = 0;
211 
212  if( aGlobalIndex >= TotalVertices() )
213  {
214  Append( aNewVertex );
215  }
216  else
217  {
218  // Assure the position to be inserted exists; throw an exception otherwise
219  if( GetRelativeIndices( aGlobalIndex, &index ) )
220  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
221  else
222  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
223  }
224 }
int TotalVertices() const
Returns total number of vertices stored in the set.
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
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) ...
bool SHAPE_POLY_SET::IsPolygonSelfIntersecting ( int  aPolygonIndex)

Function IsPolygonSelfIntersecting.

Checks whether the aPolygonIndex-th polygon in the set is self intersecting.

Parameters
aPolygonIndexindex of the polygon that wants to be checked.
Returns
bool - true if the aPolygonIndex-th polygon is self intersecting, false otherwise.

Definition at line 388 of file shape_poly_set.cpp.

References SEG::Collide(), SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::IsAdjacent(), and IterateSegmentsWithHoles().

Referenced by IsSelfIntersecting().

389 {
390  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
391  SEGMENT_ITERATOR innerIterator;
392 
393  for( iterator = IterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
394  {
395  SEG firstSegment = *iterator;
396 
397  // Iterate through all remaining segments.
398  innerIterator = iterator;
399 
400  // Start in the next segment, we don't want to check collision between a segment and itself
401  for( innerIterator++; innerIterator; innerIterator++ )
402  {
403  SEG secondSegment = *innerIterator;
404 
405  // Check whether the two segments built collide, only when they are not adjacent.
406  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
407  return true;
408  }
409  }
410 
411  return false;
412 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
Definition: seg.h:36
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
bool SHAPE_POLY_SET::IsSelfIntersecting ( )

Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.

Returns
bool - true if any of the polygons is self intersecting, false otherwise.

Definition at line 415 of file shape_poly_set.cpp.

References IsPolygonSelfIntersecting(), and m_polys.

Referenced by BOARD::NormalizeAreaPolygon(), and POINT_EDITOR::validatePolygon().

416 {
417  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
418  {
419  if( IsPolygonSelfIntersecting( polygon ) )
420  return true;
421  }
422 
423  return false;
424 }
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.
bool SHAPE_POLY_SET::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 878 of file shape_poly_set.h.

References BBox(), Collide(), and PointOnEdge().

879  {
880  return true;
881  }
bool SHAPE_POLY_SET::IsTriangulationUpToDate ( ) const

Definition at line 2054 of file shape_poly_set.cpp.

References checksum(), MD5_HASH::IsValid(), m_hash, and m_triangulationValid.

Referenced by KIGFX::OPENGL_GAL::DrawPolygon(), and PNS_KICAD_IFACE::syncZone().

2055 {
2056  if( !m_triangulationValid )
2057  return false;
2058 
2059  if( !m_hash.IsValid() )
2060  return false;
2061 
2062  auto hash = checksum();
2063 
2064  return hash == m_hash;
2065 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:23
bool SHAPE_POLY_SET::IsVertexInHole ( int  aGlobalIdx)

Function IsVertexInHole.

checks whether the aGlobalIndex-th vertex belongs to a hole.

Parameters
aGlobalIdxis the index of the vertex.
Returns
bool - true if the globally indexed aGlobalIdx-th vertex belongs to a hole.

Definition at line 1682 of file shape_poly_set.cpp.

References GetRelativeIndices(), and SHAPE_POLY_SET::VERTEX_INDEX::m_contour.

Referenced by PCB_EDIT_FRAME::createPopUpMenuForZones(), and IsEmpty().

1683 {
1684  VERTEX_INDEX index;
1685 
1686  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1687  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1688  return false;
1689 
1690  // The contour is a hole if its index is greater than zero
1691  return index.m_contour > 0;
1692 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
ITERATOR SHAPE_POLY_SET::Iterate ( int  aFirst,
int  aLast,
bool  aIterateHoles = false 
)
inline

Function Iterate returns an object to iterate through the points of the polygons between aFirst and aLast.

Parameters
aFirstis the first polygon whose points will be iterated.
aLastis the last polygon whose points will be iterated.
aIterateHolesis a flag to indicate whether the points of the holes should be iterated.
Returns
ITERATOR - the iterator object.

Definition at line 638 of file shape_poly_set.h.

References SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentContour, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentPolygon, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentVertex, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_iterateHoles, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_lastPolygon, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_poly, and OutlineCount().

Referenced by POINT_EDITOR::addCorner(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), ZONE_CONTAINER::DrawWhileCreateOutline(), EDGE_MODULE::Flip(), DRAWSEGMENT::Flip(), ZONE_CONTAINER::Iterate(), EDGE_MODULE::Mirror(), ZONE_CONTAINER::Mirror(), EDGE_MODULE::Move(), DRAWSEGMENT::Move(), GERBER_DRAW_ITEM::MoveAB(), GERBER_DRAW_ITEM::MoveXY(), DRAWSEGMENT::Rotate(), and ZONE_CONTAINER::Rotate().

639  {
640  ITERATOR iter;
641 
642  iter.m_poly = this;
643  iter.m_currentPolygon = aFirst;
644  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
645  iter.m_currentContour = 0;
646  iter.m_currentVertex = 0;
647  iter.m_iterateHoles = aIterateHoles;
648 
649  return iter;
650  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR SHAPE_POLY_SET::Iterate ( int  aOutline)
inline

Function Iterate.

Parameters
aOutlinethe index of the polygon to be iterated.
Returns
ITERATOR - an iterator object to visit all points in the main outline of the aOutline-th polygon, without visiting the points in the holes.

Definition at line 658 of file shape_poly_set.h.

References Iterate().

659  {
660  return Iterate( aOutline, aOutline );
661  }
ITERATOR Iterate()
Function Iterate.
ITERATOR SHAPE_POLY_SET::Iterate ( )
inline

Function Iterate.

Returns
ITERATOR - an iterator object to visit all points in all outlines of the set, without visiting the points in the holes.

Definition at line 679 of file shape_poly_set.h.

References OutlineCount().

Referenced by Iterate(), and IterateWithHoles().

680  {
681  return Iterate( 0, OutlineCount() - 1 );
682  }
ITERATOR Iterate()
Function Iterate.
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR SHAPE_POLY_SET::IterateFromVertexWithHoles ( int  aGlobalIdx)
inline

Definition at line 729 of file shape_poly_set.h.

References GetRelativeIndices(), IterateWithHoles(), SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentContour, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentPolygon, SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::m_currentVertex, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, and SHAPE_POLY_SET::VERTEX_INDEX::m_vertex.

730  {
731  // Build iterator
732  ITERATOR iter = IterateWithHoles();
733 
734  // Get the relative indices of the globally indexed vertex
735  VERTEX_INDEX indices;
736 
737  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
738  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
739 
740  // Adjust where the iterator is pointing
741  iter.m_currentPolygon = indices.m_polygon;
742  iter.m_currentContour = indices.m_contour;
743  iter.m_currentVertex = indices.m_vertex;
744 
745  return iter;
746  }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR IterateWithHoles()
Function IterateWithHoles.
SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aFirst,
int  aLast,
bool  aIterateHoles = false 
)
inline

Returns an iterator object, for iterating between aFirst and aLast outline, with or

without holes (default: without)

Definition at line 750 of file shape_poly_set.h.

References SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::m_currentContour, SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::m_currentPolygon, SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::m_currentSegment, SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::m_iterateHoles, SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::m_lastPolygon, SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::m_poly, and OutlineCount().

751  {
752  SEGMENT_ITERATOR iter;
753 
754  iter.m_poly = this;
755  iter.m_currentPolygon = aFirst;
756  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
757  iter.m_currentContour = 0;
758  iter.m_currentSegment = 0;
759  iter.m_iterateHoles = aIterateHoles;
760 
761  return iter;
762  }
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aPolygonIdx)
inline

Returns an iterator object, for iterating aPolygonIdx-th polygon edges

Definition at line 765 of file shape_poly_set.h.

References IterateSegments().

766  {
767  return IterateSegments( aPolygonIdx, aPolygonIdx );
768  }
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( )
inline

Returns an iterator object, for all outlines in the set (no holes)

Definition at line 771 of file shape_poly_set.h.

References OutlineCount().

Referenced by IterateSegments(), and IterateSegmentsWithHoles().

772  {
773  return IterateSegments( 0, OutlineCount() - 1 );
774  }
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( )
inline

Returns an iterator object, for all outlines in the set (with holes)

Definition at line 777 of file shape_poly_set.h.

References IterateSegments(), and OutlineCount().

Referenced by CollideEdge(), DistanceToPolygon(), DRC::doEdgeZoneDrc(), ZONE_CONTAINER::Draw(), ZONE_CONTAINER::Hatch(), IsPolygonSelfIntersecting(), BOARD::TestAreaIntersection(), and DRC::TestZoneToZoneOutline().

778  {
779  return IterateSegments( 0, OutlineCount() - 1, true );
780  }
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( int  aOutline)
inline

Returns an iterator object, for the aOutline-th outline in the set (with holes)

Definition at line 783 of file shape_poly_set.h.

References IterateSegments().

784  {
785  return IterateSegments( aOutline, aOutline, true );
786  }
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
ITERATOR SHAPE_POLY_SET::IterateWithHoles ( int  aOutline)
inline

Function IterateWithHoles.

Parameters
aOutlinethe index of the polygon to be iterated.
Returns
ITERATOR - an iterator object to visit all points in the main outline of the aOutline-th polygon, visiting also the points in the holes.

Definition at line 669 of file shape_poly_set.h.

References Iterate().

Referenced by findVertex(), ZONE_CONTAINER::Hatch(), ZONE_CONTAINER::IterateWithHoles(), ZONE_CONTAINER::Mirror(), ZONE_CONTAINER::Rotate(), BOARD::TestAreaIntersection(), and DRC::TestZoneToZoneOutline().

670  {
671  return Iterate( aOutline, aOutline, true );
672  }
ITERATOR Iterate()
Function Iterate.
ITERATOR SHAPE_POLY_SET::IterateWithHoles ( )
inline

Function IterateWithHoles.

Returns
ITERATOR - an iterator object to visit all points in all outlines of the set, visiting also the points in the holes.

Definition at line 689 of file shape_poly_set.h.

References Iterate(), and OutlineCount().

Referenced by CollideVertex(), IterateFromVertexWithHoles(), and RemoveNullSegments().

690  {
691  return Iterate( 0, OutlineCount() - 1, true );
692  }
ITERATOR Iterate()
Function Iterate.
int OutlineCount() const
Returns the number of outlines in the set
void SHAPE_POLY_SET::Move ( const VECTOR2I aVector)
overridevirtual

Implements SHAPE.

Definition at line 1531 of file shape_poly_set.cpp.

References m_polys.

Referenced by KIGFX::GERBVIEW_PAINTER::drawFlashedShape(), export_vrml_edge_module(), GERBER_DRAW_ITEM::HitTest(), ZONE_CONTAINER::Move(), and TransformOvalClearanceToPolygon().

1532 {
1533  for( POLYGON& poly : m_polys )
1534  {
1535  for( SHAPE_LINE_CHAIN& path : poly )
1536  {
1537  path.Move( aVector );
1538  }
1539  }
1540 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.
int SHAPE_POLY_SET::NewHole ( int  aOutline = -1)

Creates a new hole in a given outline

Definition at line 167 of file shape_poly_set.cpp.

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by ConvertOutlineToPolygon(), ConvertPolyListToPolySet(), ZONE_CONTAINER::NewHole(), and ZONE_CREATE_HELPER::performZoneCutout().

168 {
169  SHAPE_LINE_CHAIN empty_path;
170 
171  empty_path.SetClosed( true );
172 
173  // Default outline is the last one
174  if( aOutline < 0 )
175  aOutline += m_polys.size();
176 
177  // Add hole to the selected outline
178  m_polys[aOutline].push_back( empty_path );
179 
180  return m_polys.back().size() - 2;
181 }
void SetClosed(bool aClosed)
Function SetClosed()
Class SHAPE_LINE_CHAIN.
int SHAPE_POLY_SET::NewOutline ( )

Creates a new empty polygon in the set and returns its index

Definition at line 155 of file shape_poly_set.cpp.

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by addHoleToPolygon(), addRect(), ZONE_CONTAINER::AppendCorner(), BuildBoardPolygonOutlines(), D_PAD::buildCustomPadPolygon(), D_PAD::BuildPadShapePolygon(), ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), ZONE_FILLER::buildZoneFeatureHoleList(), ConvertOutlineToPolygon(), ConvertPolyListToPolySet(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CreateThermalReliefPadPolygon(), KIGFX::PCB_PAINTER::draw(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), fillArcPOLY(), MODULE::GetBoundingPoly(), getRectangleAlongCentreLine(), LEGACY_PLUGIN::loadZONE_CONTAINER(), CPolyLine::NormalizeAreaOutlines(), PCB_PARSER::parseZONE_CONTAINER(), DXF_PLOTTER::PlotPoly(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), DRAWSEGMENT::SetPolyPoints(), TEXTE_PCB::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalClearanceToPolygon(), TransformRingToPolygon(), TransformRoundedEndsSegmentToPolygon(), TransformRoundRectToPolygon(), DRAWSEGMENT::TransformShapeWithClearanceToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

156 {
157  SHAPE_LINE_CHAIN empty_path;
158  POLYGON poly;
159 
160  empty_path.SetClosed( true );
161  poly.push_back( empty_path );
162  m_polys.push_back( poly );
163  return m_polys.size() - 1;
164 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void SetClosed(bool aClosed)
Function SetClosed()
Class SHAPE_LINE_CHAIN.
int SHAPE_POLY_SET::NormalizeAreaOutlines ( )

Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s) Removes null segments.

Returns
int - the polygon count (always >= 1, because there is at least one polygon) There are new polygons only if the polygon count is > 1.

Definition at line 1080 of file shape_poly_set.cpp.

References AddOutline(), BooleanSubtract(), OutlineCount(), PM_FAST, PM_STRICTLY_SIMPLE, Polygon(), RemoveNullSegments(), and Simplify().

Referenced by BOARD::NormalizeAreaPolygon().

1081 {
1082  // We are expecting only one main outline, but this main outline can have holes
1083  // if holes: combine holes and remove them from the main outline.
1084  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1085  // calculations, but it is not mandatory. It is used mainly
1086  // because there is usually only very few vertices in area outlines
1087  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1088  SHAPE_POLY_SET holesBuffer;
1089 
1090  // Move holes stored in outline to holesBuffer:
1091  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1092  while( outline.size() > 1 )
1093  {
1094  holesBuffer.AddOutline( outline.back() );
1095  outline.pop_back();
1096  }
1097 
1099 
1100  // If any hole, substract it to main outline
1101  if( holesBuffer.OutlineCount() )
1102  {
1103  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1105  }
1106 
1108 
1109  return OutlineCount();
1110 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
int OutlineCount() const
Returns the number of outlines in the set
Class SHAPE_POLY_SET.
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp ...
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
SHAPE_POLY_SET & SHAPE_POLY_SET::operator= ( const SHAPE_POLY_SET aOther)

Definition at line 1881 of file shape_poly_set.cpp.

References m_hash, m_polys, m_triangulatedPolys, and m_triangulationValid.

1882 {
1883  static_cast<SHAPE&>(*this) = aOther;
1884  m_polys = aOther.m_polys;
1885 
1886  // reset poly cache:
1887  m_hash = MD5_HASH{};
1888  m_triangulationValid = false;
1889  m_triangulatedPolys.clear();
1890  return *this;
1891 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
Class SHAPE.
Definition: shape.h:58
int SHAPE_POLY_SET::OutlineCount ( ) const
inline

Returns the number of outlines in the set

Definition at line 552 of file shape_poly_set.h.

References m_polys, and VertexCount().

Referenced by POINT_EDITOR::addCorner(), ZONE_CONTAINER::AddPolygon(), CINFO3D_VISU::AddSolidAreasShapesToContainer(), CLAYER_TRIANGLES::AddToMiddleContourns(), ZONE_CONTAINER::AppendCorner(), D_PAD::boundingRadius(), BuildBoardPolygonOutlines(), BuildConvexHull(), D_PAD::buildCustomPadPolygon(), DRAWSEGMENT::BuildPolyPointsList(), CacheTriangulation(), DRC::checkClearancePadToPad(), CIterate(), CIterateWithHoles(), BOARD::CombineAreas(), Contains(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), Convert_shape_line_polygon_to_triangles(), D_PAD::CustomShapeAsPolygonToBoardPosition(), DRC::doFootprintOverlappingDrc(), KIGFX::GERBVIEW_PAINTER::draw(), DRAWSEGMENT::Draw(), KIGFX::PCB_PAINTER::draw(), GERBER_DRAW_ITEM::Draw(), KIGFX::GERBVIEW_PAINTER::drawApertureMacro(), APERTURE_MACRO::DrawApertureMacroShape(), ZONE_CONTAINER::DrawFilledArea(), D_CODE::DrawFlashedPolygon(), D_CODE::DrawFlashedShape(), KIGFX::GERBVIEW_PAINTER::drawFlashedShape(), KIGFX::CAIRO_GAL::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), D_PAD::DrawShape(), KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), export_vrml_board(), export_vrml_zones(), fillArcPOLY(), DSN::SPECCTRA_DB::fillBOUNDARY(), ZONE_FILLER::fillZoneWithSegments(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), D_PAD::FlipPrimitives(), C3D_RENDER_OGL_LEGACY::generate_3D_Vias_and_Pads(), C3D_RENDER_OGL_LEGACY::generate_holes_display_list(), APERTURE_MACRO::GetApertureMacroShape(), GERBER_DRAW_ITEM::GetBoundingBox(), D_PAD::GetBoundingBox(), GetRelativeIndices(), HasTouchingHoles(), D_PAD::HitTest(), Iterate(), IterateSegments(), IterateSegmentsWithHoles(), IterateWithHoles(), D_PAD::MergePrimitivesAsPolygon(), GERBER_DRAW_ITEM::MoveAB(), GERBER_DRAW_ITEM::MoveXY(), CPolyLine::NormalizeAreaOutlines(), NormalizeAreaOutlines(), BRDITEMS_PLOTTER::PlotDrawSegment(), PlotLayerOutlines(), BRDITEMS_PLOTTER::PlotPad(), DXF_PLOTTER::PlotPoly(), Polygon_Calc_BBox_3DU(), polygonArea(), C3D_RENDER_OGL_LEGACY::reload(), Subset(), and PNS_KICAD_IFACE::syncZone().

552 { return m_polys.size(); }
bool SHAPE_POLY_SET::Parse ( std::stringstream &  aStream)
overridevirtual

Reimplemented from SHAPE.

Definition at line 1138 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::Append(), m_polys, SHAPE_LINE_CHAIN::SetClosed(), VECTOR2< T >::x, and VECTOR2< T >::y.

1139 {
1140  std::string tmp;
1141 
1142  aStream >> tmp;
1143 
1144  if( tmp != "polyset" )
1145  return false;
1146 
1147  aStream >> tmp;
1148 
1149  int n_polys = atoi( tmp.c_str() );
1150 
1151  if( n_polys < 0 )
1152  return false;
1153 
1154  for( int i = 0; i < n_polys; i++ )
1155  {
1156  POLYGON paths;
1157 
1158  aStream >> tmp;
1159 
1160  if( tmp != "poly" )
1161  return false;
1162 
1163  aStream >> tmp;
1164  int n_outlines = atoi( tmp.c_str() );
1165 
1166  if( n_outlines < 0 )
1167  return false;
1168 
1169  for( int j = 0; j < n_outlines; j++ )
1170  {
1171  SHAPE_LINE_CHAIN outline;
1172 
1173  outline.SetClosed( true );
1174 
1175  aStream >> tmp;
1176  int n_vertices = atoi( tmp.c_str() );
1177 
1178  for( int v = 0; v < n_vertices; v++ )
1179  {
1180  VECTOR2I p;
1181 
1182  aStream >> tmp; p.x = atoi( tmp.c_str() );
1183  aStream >> tmp; p.y = atoi( tmp.c_str() );
1184  outline.Append( p );
1185  }
1186 
1187  paths.push_back( outline );
1188  }
1189 
1190  m_polys.push_back( paths );
1191  }
1192 
1193  return true;
1194 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
Class SHAPE_LINE_CHAIN.
bool SHAPE_POLY_SET::pointInPolygon ( const VECTOR2I aP,
const SHAPE_LINE_CHAIN aPath 
) const
private

Definition at line 1466 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::BBox(), BOX2< Vec >::Contains(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::PointCount(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by containsSingle(), and IsEmpty().

1467 {
1468  int result = 0;
1469  int cnt = aPath.PointCount();
1470 
1471  if( !aPath.BBox().Contains( aP ) ) // test with bounding box first
1472  return false;
1473 
1474  if( cnt < 3 )
1475  return false;
1476 
1477  VECTOR2I ip = aPath.CPoint( 0 );
1478 
1479  for( int i = 1; i <= cnt; ++i )
1480  {
1481  VECTOR2I ipNext = ( i == cnt ? aPath.CPoint( 0 ) : aPath.CPoint( i ) );
1482 
1483  if( ipNext.y == aP.y )
1484  {
1485  if( ( ipNext.x == aP.x ) || ( ip.y == aP.y
1486  && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
1487  return true;
1488  }
1489 
1490  if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
1491  {
1492  if( ip.x >= aP.x )
1493  {
1494  if( ipNext.x > aP.x )
1495  result = 1 - result;
1496  else
1497  {
1498  int64_t d = (int64_t) ( ip.x - aP.x ) * (int64_t) ( ipNext.y - aP.y ) -
1499  (int64_t) ( ipNext.x - aP.x ) * (int64_t) ( ip.y - aP.y );
1500 
1501  if( !d )
1502  return true;
1503 
1504  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1505  result = 1 - result;
1506  }
1507  }
1508  else
1509  {
1510  if( ipNext.x > aP.x )
1511  {
1512  int64_t d = (int64_t) ( ip.x - aP.x ) * (int64_t) ( ipNext.y - aP.y ) -
1513  (int64_t) ( ipNext.x - aP.x ) * (int64_t) ( ip.y - aP.y );
1514 
1515  if( !d )
1516  return true;
1517 
1518  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1519  result = 1 - result;
1520  }
1521  }
1522  }
1523 
1524  ip = ipNext;
1525  }
1526 
1527  return result ? true : false;
1528 }
int PointCount() const
Function PointCount()
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:139
const BOX2I BBox(int aClearance=0) const override
Function BBox()
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
bool SHAPE_POLY_SET::PointOnEdge ( const VECTOR2I aP) const

Function PointOnEdge()

Checks if point aP lies on an edge or vertex of some of the outlines or holes.

Parameters
aPis the point to check.
Returns
bool - true if the point lies on the edge of any polygon.

Definition at line 1214 of file shape_poly_set.cpp.

References m_polys.

Referenced by IsSolid().

1215 {
1216  // Iterate through all the polygons in the set
1217  for( const POLYGON& polygon : m_polys )
1218  {
1219  // Iterate through all the line chains in the polygon
1220  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1221  {
1222  if( lineChain.PointOnEdge( aP ) )
1223  return true;
1224  }
1225  }
1226 
1227  return false;
1228 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.
POLYGON& SHAPE_POLY_SET::Polygon ( int  aIndex)
inline
const POLYGON& SHAPE_POLY_SET::Polygon ( int  aIndex) const
inline

Definition at line 602 of file shape_poly_set.h.

References m_polys.

603  {
604  return m_polys[aIndex];
605  }
void SHAPE_POLY_SET::RemoveContour ( int  aContourIdx,
int  aPolygonIdx = -1 
)

Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.

Parameters
aContourIdxis the index of the contour in the aPolygonIdx-th polygon to be removed.
aPolygonIdxis the index of the polygon in which the to-be-removed contour is. Defaults to the last polygon in the set.

Definition at line 1253 of file shape_poly_set.cpp.

References m_polys.

Referenced by PCB_EDIT_FRAME::Delete_Zone_Contour(), IsEmpty(), and POINT_EDITOR::removeCorner().

1254 {
1255  // Default polygon is the last one
1256  if( aPolygonIdx < 0 )
1257  aPolygonIdx += m_polys.size();
1258 
1259  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1260 }
int SHAPE_POLY_SET::RemoveNullSegments ( )

Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and deletes them.

Returns
int - the number of deleted segments.

Definition at line 1263 of file shape_poly_set.cpp.

References SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::GetIndex(), SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::IsEndContour(), IterateWithHoles(), and RemoveVertex().

Referenced by chamferFilletPolygon(), PCB_EDIT_FRAME::End_Zone(), IsEmpty(), and NormalizeAreaOutlines().

1264 {
1265  int removed = 0;
1266 
1267  ITERATOR iterator = IterateWithHoles();
1268 
1269  VECTOR2I contourStart = *iterator;
1270  VECTOR2I segmentStart, segmentEnd;
1271 
1272  VERTEX_INDEX indexStart;
1273 
1274  while( iterator )
1275  {
1276  // Obtain first point and its index
1277  segmentStart = *iterator;
1278  indexStart = iterator.GetIndex();
1279 
1280  // Obtain last point
1281  if( iterator.IsEndContour() )
1282  {
1283  segmentEnd = contourStart;
1284 
1285  // Advance
1286  iterator++;
1287 
1288  if( iterator )
1289  contourStart = *iterator;
1290  }
1291  else
1292  {
1293  // Advance
1294  iterator++;
1295 
1296  if( iterator )
1297  segmentEnd = *iterator;
1298  }
1299 
1300  // Remove segment start if both points are equal
1301  if( segmentStart == segmentEnd )
1302  {
1303  RemoveVertex( indexStart );
1304  removed++;
1305 
1306  // Advance the iterator one position, as there is one vertex less.
1307  if( iterator )
1308  iterator++;
1309  }
1310  }
1311 
1312  return removed;
1313 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR IterateWithHoles()
Function IterateWithHoles.
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
void SHAPE_POLY_SET::RemoveVertex ( int  aGlobalIndex)

Function RemoveVertex deletes the aGlobalIndex-th vertex.

Parameters
aGlobalIndexis the global index of the to-be-removed vertex.

Definition at line 1422 of file shape_poly_set.cpp.

References GetRelativeIndices().

Referenced by Abort_Zone_Move_Corner_Or_Outlines(), PCB_EDIT_FRAME::Delete_LastCreatedCorner(), IsEmpty(), PCB_EDIT_FRAME::Remove_Zone_Corner(), POINT_EDITOR::removeCorner(), RemoveNullSegments(), and PCB_EDIT_FRAME::Start_Move_Zone_Corner().

1423 {
1424  VERTEX_INDEX index;
1425 
1426  // Assure the to be removed vertex exists, abort otherwise
1427  if( GetRelativeIndices( aGlobalIndex, &index ) )
1428  RemoveVertex( index );
1429  else
1430  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1431 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
void SHAPE_POLY_SET::RemoveVertex ( VERTEX_INDEX  aRelativeIndices)

Function RemoveVertex deletes the vertex indexed by aIndex (index of polygon, contour and vertex).

Parameters
aRelativeIndicesis the set of relative indices of the to-be-removed vertex.

Definition at line 1434 of file shape_poly_set.cpp.

References SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, m_polys, and SHAPE_POLY_SET::VERTEX_INDEX::m_vertex.

1435 {
1436  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1437 }
void SHAPE_POLY_SET::Rotate ( double  aAngle,
const VECTOR2I aCenter 
)

Function Rotate rotates all vertices by a given angle.

Parameters
aCenteris the rotation center
aAnglerotation angle in radians

Definition at line 1543 of file shape_poly_set.cpp.

References m_polys.

Referenced by export_vrml_edge_module(), MODULE::GetBoundingPoly(), and TransformOvalClearanceToPolygon().

1544 {
1545  for( POLYGON& poly : m_polys )
1546  {
1547  for( SHAPE_LINE_CHAIN& path : poly )
1548  {
1549  path.Rotate( aAngle, aCenter );
1550  }
1551  }
1552 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.
void SHAPE_POLY_SET::Simplify ( POLYGON_MODE  aFastMode)

Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMode meaning, see function booleanOp

Definition at line 1072 of file shape_poly_set.cpp.

References booleanOp(), and empty().

Referenced by CINFO3D_VISU::AddShapeWithClearanceToContainer(), CINFO3D_VISU::AddSolidAreasShapesToContainer(), D_PAD::buildCustomPadPolygon(), BOARD::CombineAreas(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), CINFO3D_VISU::createBoardPolygon(), CINFO3D_VISU::createLayers(), CINFO3D_VISU::createNewPadWithClearance(), CreateThermalReliefPadPolygon(), Fracture(), BOARD::GetBoardPolygonOutlines(), CPolyLine::NormalizeAreaOutlines(), NormalizeAreaOutlines(), PlotLayerOutlines(), ZONE_CONTAINER::TransformShapeWithClearanceToPolygon(), and Unfracture().

1073 {
1075 
1076  booleanOp( ctUnion, empty, aFastMode );
1077 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
Class SHAPE_POLY_SET.
static bool empty(const wxTextEntryBase *aCtrl)
SHAPE_POLY_SET SHAPE_POLY_SET::Subset ( int  aFirstPolygon,
int  aLastPolygon 
)

Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.

Parameters
aFirstPolygonis the first polygon to be included in the returned set.
aLastPolygonis the first polygon to be excluded of the returned set.
Returns
SHAPE_POLY_SET - a set containing the polygons between aFirstPolygon (included) and aLastPolygon (excluded).

Definition at line 252 of file shape_poly_set.cpp.

References m_polys, OutlineCount(), and Polygon().

Referenced by Outline(), and UnitSet().

253 {
254  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
255 
256  SHAPE_POLY_SET newPolySet;
257 
258  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
259  {
260  newPolySet.m_polys.push_back( Polygon( index ) );
261  }
262 
263  return newPolySet;
264 }
int OutlineCount() const
Returns the number of outlines in the set
Class SHAPE_POLY_SET.
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
int SHAPE_POLY_SET::TotalVertices ( ) const

Returns total number of vertices stored in the set.

Definition at line 1555 of file shape_poly_set.cpp.

References m_polys.

Referenced by EDIT_POINTS_FACTORY::buildForPolyOutline(), ZONE_CONTAINER::GetMsgPanelInfo(), ZONE_CONTAINER::GetNumCorners(), DRAWSEGMENT::HitTest(), ZONE_CONTAINER::HitTest(), InsertVertex(), IsEmpty(), PCB_EDIT_FRAME::Remove_Zone_Corner(), POINT_EDITOR::updateItem(), and POINT_EDITOR::updatePoints().

1556 {
1557  int c = 0;
1558 
1559  for( const POLYGON& poly : m_polys )
1560  {
1561  for( const SHAPE_LINE_CHAIN& path : poly )
1562  {
1563  c += path.PointCount();
1564  }
1565  }
1566 
1567  return c;
1568 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.
const TRIANGULATED_POLYGON* SHAPE_POLY_SET::TriangulatedPolygon ( int  aIndex) const
inline

Definition at line 607 of file shape_poly_set.h.

References m_triangulatedPolys.

Referenced by KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), and PNS_KICAD_IFACE::syncZone().

608  {
609  return m_triangulatedPolys[aIndex].get();
610  }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
void SHAPE_POLY_SET::triangulateSingle ( const POLYGON aPoly,
SHAPE_POLY_SET::TRIANGULATED_POLYGON aResult 
)
private

Definition at line 2035 of file shape_poly_set.cpp.

References SHAPE_POLY_SET::TRIANGULATION_CONTEXT::AddOutline(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::AllocateVertices(), totalVertexCount(), and SHAPE_POLY_SET::TRIANGULATION_CONTEXT::Triangulate().

Referenced by CacheTriangulation().

2037 {
2038  if( aPoly.size() == 0 )
2039  return;
2040 
2041  TRIANGULATION_CONTEXT ctx ( &aResult );
2042 
2043  aResult.AllocateVertices( totalVertexCount( aPoly ) );
2044  ctx.AddOutline( aPoly[0], false );
2045  for( unsigned i = 1; i < aPoly.size(); i++ )
2046  {
2047  ctx.AddOutline( aPoly[i], true ); // add holes
2048  }
2049 
2050  ctx.Triangulate();
2051 }
static int totalVertexCount(const SHAPE_POLY_SET::POLYGON &aPoly)
SHAPE_TYPE SHAPE::Type ( ) const
inlineinherited

Function Type()

Returns the type of the shape.

Return values
thetype

Definition at line 83 of file shape.h.

References SHAPE::m_type.

Referenced by PNS::DP_GATEWAYS::BuildFromPrimitivePair(), CollideShapes(), PNS::OPTIMIZER::computeBreakouts(), PNS::LOGGER::dumpShape(), PNS::SOLID::Hull(), ROUTER_PREVIEW_ITEM::ViewDraw(), and SHAPE_FILE_IO::Write().

84  {
85  return m_type;
86  }
SHAPE_TYPE m_type
type of our shape
Definition: shape.h:166
void SHAPE_POLY_SET::Unfracture ( POLYGON_MODE  aFastMode)

Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.

Definition at line 1061 of file shape_poly_set.cpp.

References m_polys, Simplify(), and unfractureSingle().

Referenced by CacheTriangulation().

1062 {
1063  for( POLYGON& path : m_polys )
1064  {
1065  unfractureSingle( path );
1066  }
1067 
1068  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1069 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void unfractureSingle(POLYGON &path)
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
void SHAPE_POLY_SET::unfractureSingle ( SHAPE_POLY_SET::POLYGON aPoly)
private

Definition at line 885 of file shape_poly_set.cpp.

References SEG::A, SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::Area(), SEG::B, SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), next(), operator!=(), operator==(), and SHAPE_LINE_CHAIN::SetClosed().

Referenced by IsEmpty(), and Unfracture().

886 {
887  assert( aPoly.size() == 1 );
888 
889  struct EDGE
890  {
891  int m_index = 0;
892  SHAPE_LINE_CHAIN* m_poly = nullptr;
893  bool m_duplicate = false;
894 
895  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
896  m_index( aIndex ),
897  m_poly( aPolygon )
898  {}
899 
900  bool compareSegs( const SEG& s1, const SEG& s2 ) const
901  {
902  return (s1.A == s2.B && s1.B == s2.A);
903  }
904 
905  bool operator==( const EDGE& aOther ) const
906  {
907  return compareSegs( m_poly->CSegment( m_index ),
908  aOther.m_poly->CSegment( aOther.m_index ) );
909  }
910 
911  bool operator!=( const EDGE& aOther ) const
912  {
913  return !compareSegs( m_poly->CSegment( m_index ),
914  aOther.m_poly->CSegment( aOther.m_index ) );
915  }
916 
917  struct HASH
918  {
919  std::size_t operator()( const EDGE& aEdge ) const
920  {
921  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
922 
923  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
924  }
925  };
926  };
927 
928  struct EDGE_LIST_ENTRY
929  {
930  int index;
931  EDGE_LIST_ENTRY* next;
932  };
933 
934  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
935 
936  auto lc = aPoly[0];
937  lc.Simplify();
938 
939  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
940 
941  for( int i = 0; i < lc.SegmentCount(); i++ )
942  {
943  edgeList[i].index = i;
944  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
945  }
946 
947  std::unordered_set<EDGE_LIST_ENTRY*> queue;
948 
949  for( int i = 0; i < lc.SegmentCount(); i++ )
950  {
951  EDGE e( &lc, i );
952  uniqueEdges.insert( e );
953  }
954 
955  for( int i = 0; i < lc.SegmentCount(); i++ )
956  {
957  EDGE e( &lc, i );
958  auto it = uniqueEdges.find( e );
959 
960  if( it != uniqueEdges.end() && it->m_index != i )
961  {
962  int e1 = it->m_index;
963  int e2 = i;
964 
965  if( e1 > e2 )
966  std::swap( e1, e2 );
967 
968  int e1_prev = e1 - 1;
969 
970  if( e1_prev < 0 )
971  e1_prev = lc.SegmentCount() - 1;
972 
973  int e2_prev = e2 - 1;
974 
975  if( e2_prev < 0 )
976  e2_prev = lc.SegmentCount() - 1;
977 
978  int e1_next = e1 + 1;
979 
980  if( e1_next == lc.SegmentCount() )
981  e1_next = 0;
982 
983  int e2_next = e2 + 1;
984 
985  if( e2_next == lc.SegmentCount() )
986  e2_next = 0;
987 
988  edgeList[e1_prev].next = &edgeList[ e2_next ];
989  edgeList[e2_prev].next = &edgeList[ e1_next ];
990  edgeList[i].next = nullptr;
991  edgeList[it->m_index].next = nullptr;
992  }
993  }
994 
995  for( int i = 0; i < lc.SegmentCount(); i++ )
996  {
997  if( edgeList[i].next )
998  queue.insert( &edgeList[i] );
999  }
1000 
1001  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
1002 
1003  int n = 0;
1004  int outline = -1;
1005 
1006  POLYGON result;
1007 
1008  while( queue.size() )
1009  {
1010  auto e_first = (*queue.begin() );
1011  auto e = e_first;
1012  int cnt = 0;
1013 
1014  do {
1015  edgeBuf[cnt++] = e;
1016  e = e->next;
1017  } while( e && e != e_first );
1018 
1019  SHAPE_LINE_CHAIN outl;
1020 
1021  for( int i = 0; i < cnt; i++ )
1022  {
1023  auto p = lc.CPoint( edgeBuf[i]->index );
1024  outl.Append( p );
1025  queue.erase( edgeBuf[i] );
1026  }
1027 
1028  outl.SetClosed( true );
1029 
1030  bool cw = outl.Area() > 0.0;
1031 
1032  if( cw )
1033  outline = n;
1034 
1035  result.push_back( outl );
1036  n++;
1037  }
1038 
1039  if( outline > 0 )
1040  std::swap( result[0], result[outline] );
1041 
1042  aPoly = result;
1043 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
CITER next(CITER it)
Definition: ptree.cpp:130
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const SEG CSegment(int aIndex) const
Function CSegment()
void SetClosed(bool aClosed)
Function SetClosed()
Definition: seg.h:36
Class SHAPE_LINE_CHAIN.
double Area() const
VECTOR2I A
Definition: seg.h:46
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
VECTOR2I B
Definition: seg.h:47
SHAPE_POLY_SET SHAPE_POLY_SET::UnitSet ( int  aPolygonIndex)
inline

Definition at line 585 of file shape_poly_set.h.

References Subset().

Referenced by BOARD::NormalizeAreaPolygon().

586  {
587  return Subset( aPolygonIndex, aPolygonIndex + 1 );
588  }
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...
VECTOR2I & SHAPE_POLY_SET::Vertex ( int  aIndex,
int  aOutline,
int  aHole 
)

Returns the index-th vertex in a given hole outline within a given outline

Definition at line 267 of file shape_poly_set.cpp.

References m_polys.

Referenced by Abort_Zone_Move_Corner_Or_Outlines(), POINT_EDITOR::addCorner(), DRC::doFootprintOverlappingDrc(), D_CODE::DrawFlashedPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), findVertex(), ZONE_CONTAINER::Hatch(), ZONE_CONTAINER::HitTest(), ZONE_CONTAINER::MoveEdge(), ZONE_CONTAINER::SetCornerPosition(), Show_Zone_Corner_Or_Outline_While_Move_Mouse(), PCB_EDIT_FRAME::Start_Move_Zone_Corner(), POINT_EDITOR::updateItem(), and Vertex().

268 {
269  if( aOutline < 0 )
270  aOutline += m_polys.size();
271 
272  int idx;
273 
274  if( aHole < 0 )
275  idx = 0;
276  else
277  idx = aHole + 1;
278 
279  assert( aOutline < (int) m_polys.size() );
280  assert( idx < (int) m_polys[aOutline].size() );
281 
282  return m_polys[aOutline][idx].Point( aIndex );
283 }
VECTOR2I & SHAPE_POLY_SET::Vertex ( int  aGlobalIndex)

Returns the aGlobalIndex-th vertex in the poly set

Definition at line 305 of file shape_poly_set.cpp.

References GetRelativeIndices(), SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, m_polys, and SHAPE_POLY_SET::VERTEX_INDEX::m_vertex.

306 {
308 
309  // Assure the passed index references a legal position; abort otherwise
310  if( !GetRelativeIndices( aGlobalIndex, &index ) )
311  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
312 
313  return m_polys[index.m_polygon][index.m_contour].Point( index.m_vertex );
314 }
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
VECTOR2I & SHAPE_POLY_SET::Vertex ( SHAPE_POLY_SET::VERTEX_INDEX  index)

Returns the index-th vertex in a given hole outline within a given outline

Definition at line 329 of file shape_poly_set.cpp.

References SHAPE_POLY_SET::VERTEX_INDEX::m_contour, SHAPE_POLY_SET::VERTEX_INDEX::m_polygon, SHAPE_POLY_SET::VERTEX_INDEX::m_vertex, and Vertex().

330 {
331  return Vertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
332 }
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline
VECTOR2I& SHAPE_POLY_SET::vertex ( int  aCornerId)
private

Referenced by convertToClipper(), and IsEmpty().

int SHAPE_POLY_SET::VertexCount ( int  aOutline = -1,
int  aHole = -1 
) const

Returns the number of vertices in a given outline/hole

Definition at line 227 of file shape_poly_set.cpp.

References m_polys.

Referenced by D_CODE::DrawFlashedPolygon(), DRAWSEGMENT::GetPointCount(), and OutlineCount().

228 {
229  if( m_polys.size() == 0 ) // Empty poly set
230  return 0;
231 
232  if( aOutline < 0 ) // Use last outline
233  aOutline += m_polys.size();
234 
235  int idx;
236 
237  if( aHole < 0 )
238  idx = 0;
239  else
240  idx = aHole + 1;
241 
242  if( aOutline >= (int) m_polys.size() ) // not existing outline
243  return 0;
244 
245  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
246  return 0;
247 
248  return m_polys[aOutline][idx].PointCount();
249 }

Member Data Documentation

MD5_HASH SHAPE_POLY_SET::m_hash
private

Definition at line 1178 of file shape_poly_set.h.

Referenced by CacheTriangulation(), IsTriangulationUpToDate(), and operator=().

std::vector<std::unique_ptr<TRIANGULATED_POLYGON> > SHAPE_POLY_SET::m_triangulatedPolys
private

Definition at line 1176 of file shape_poly_set.h.

Referenced by CacheTriangulation(), operator=(), and TriangulatedPolygon().

bool SHAPE_POLY_SET::m_triangulationValid = false
private

Definition at line 1177 of file shape_poly_set.h.

Referenced by CacheTriangulation(), IsTriangulationUpToDate(), and operator=().

SHAPE_TYPE SHAPE::m_type
protectedinherited

type of our shape

Definition at line 166 of file shape.h.

Referenced by SHAPE::Type().


The documentation for this class was generated from the following files: