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
 
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, bool aDeepCopy=false)
 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...
 
unsigned int TriangulatedPolyCount () const
 

Returns the number of triangulated polygons

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 InflateWithLinkedHoles (int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
 

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 Checks whether the segment aSeg collides with the inside of the polygon set; if the segment touches an edge or a corner of any of the polygons, there is no collision: the edges do not belong to the polygon itself. 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, int aErrorMax, 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 aErrorMax)
 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
 
MD5_HASH GetHash () 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
 
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 aErrorMax=-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...
 
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 54 of file shape_poly_set.h.

Member Typedef Documentation

◆ CONST_ITERATOR

◆ CONST_SEGMENT_ITERATOR

◆ ecoord

typedef VECTOR2I::extended_type SHAPE::ecoord
protectedinherited

Definition at line 61 of file shape.h.

◆ ITERATOR

◆ POLYGON

represents a single polygon outline with holes.

The first entry is the outline, the remaining (if any), are the holes N.B. SWIG only supports typedef, so avoid c++ 'using' keyword

Definition at line 60 of file shape_poly_set.h.

◆ POLYSET

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

Definition at line 1185 of file shape_poly_set.h.

◆ SEGMENT_ITERATOR

◆ VERTEX_INDEX

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

◆ CORNER_MODE

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 1157 of file shape_poly_set.h.

◆ POLYGON_MODE

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 800 of file shape_poly_set.h.

Constructor & Destructor Documentation

◆ SHAPE_POLY_SET() [1/2]

SHAPE_POLY_SET::SHAPE_POLY_SET ( )

Definition at line 51 of file shape_poly_set.cpp.

51  :
53 {
54 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:70
simple polygon
Definition: shape.h:48

Referenced by Clone(), and Collide().

◆ SHAPE_POLY_SET() [2/2]

SHAPE_POLY_SET::SHAPE_POLY_SET ( const SHAPE_POLY_SET aOther,
bool  aDeepCopy = false 
)

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

Parameters
aOtheris the SHAPE_POLY_SET object that will be copied.
aDeepCopyif true, make new copies of the triangulated unique_ptr vector

Definition at line 57 of file shape_poly_set.cpp.

57  :
58  SHAPE( SH_POLY_SET ), m_polys( aOther.m_polys )
59 {
60  if( aOther.IsTriangulationUpToDate() )
61  {
62  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
63  m_triangulatedPolys.push_back(
64  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
65 
66  m_hash = aOther.GetHash();
67  m_triangulationValid = true;
68  }
69 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:70
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool IsTriangulationUpToDate() const
MD5_HASH GetHash() const
simple polygon
Definition: shape.h:48
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
size_t i
Definition: json11.cpp:597
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const

References GetHash(), i, IsTriangulationUpToDate(), m_hash, m_triangulatedPolys, m_triangulationValid, TriangulatedPolyCount(), and TriangulatedPolygon().

◆ ~SHAPE_POLY_SET()

SHAPE_POLY_SET::~SHAPE_POLY_SET ( )

Definition at line 72 of file shape_poly_set.cpp.

73 {
74 }

Member Function Documentation

◆ AddHole()

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 452 of file shape_poly_set.cpp.

453 {
454  assert( m_polys.size() );
455 
456  if( aOutline < 0 )
457  aOutline += m_polys.size();
458 
459  POLYGON& poly = m_polys[aOutline];
460 
461  assert( poly.size() );
462 
463  poly.push_back( aHole );
464 
465  return poly.size() - 1;
466 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.

References m_polys.

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

◆ AddOutline()

int SHAPE_POLY_SET::AddOutline ( const SHAPE_LINE_CHAIN aOutline)

Adds a new outline to the set and returns its index

Definition at line 438 of file shape_poly_set.cpp.

439 {
440  assert( aOutline.IsClosed() );
441 
442  POLYGON poly;
443 
444  poly.push_back( aOutline );
445 
446  m_polys.push_back( poly );
447 
448  return m_polys.size() - 1;
449 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
bool IsClosed() const
Function IsClosed()

References SHAPE_LINE_CHAIN::IsClosed(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE_CONTAINER::AddPolygon(), CINFO3D_VISU::buildPadShapePolygon(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), D_PAD::MergePrimitivesAsPolygon(), NormalizeAreaOutlines(), and ZONE_CREATE_HELPER::performZoneCutout().

◆ Append() [1/3]

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 195 of file shape_poly_set.cpp.

196 {
197  if( aOutline < 0 )
198  aOutline += m_polys.size();
199 
200  int idx;
201 
202  if( aHole < 0 )
203  idx = 0;
204  else
205  idx = aHole + 1;
206 
207  assert( aOutline < (int) m_polys.size() );
208  assert( idx < (int) m_polys[aOutline].size() );
209 
210  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
211 
212  return m_polys[aOutline][idx].PointCount();
213 }

References m_polys.

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), AR_AUTOPLACER::addPad(), D_PAD::AddPrimitive(), 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(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CINFO3D_VISU::createNewPadWithClearance(), CreateThermalReliefPadPolygon(), 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(), DXF_PLOTTER::PlotPoly(), DRC_COURTYARD_OVERLAP::RunDRC(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), DRAWSEGMENT::SetPolyPoints(), PNS_KICAD_IFACE::syncPad(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon(), TransformOvalClearanceToPolygon(), TransformRingToPolygon(), TransformRoundChamferedRectToPolygon(), TransformRoundedEndsSegmentToPolygon(), DRAWSEGMENT::TransformShapeWithClearanceToPolygon(), D_PAD::TransformShapeWithClearanceToPolygon(), ZONE_CONTAINER::TransformSolidAreasShapesToPolygonSet(), and ZONE_CONTAINER::ZONE_CONTAINER().

◆ Append() [2/3]

void SHAPE_POLY_SET::Append ( const SHAPE_POLY_SET aSet)

Merges polygons from two sets.

Definition at line 1318 of file shape_poly_set.cpp.

1319 {
1320  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1321 }

References m_polys.

◆ Append() [3/3]

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 1324 of file shape_poly_set.cpp.

1325 {
1326  Append( aP.x, aP.y, aOutline, aHole );
1327 }
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)

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

◆ BBox()

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 1162 of file shape_poly_set.cpp.

1163 {
1164  BOX2I bb;
1165 
1166  for( unsigned i = 0; i < m_polys.size(); i++ )
1167  {
1168  if( i == 0 )
1169  bb = m_polys[i][0].BBox();
1170  else
1171  bb.Merge( m_polys[i][0].BBox() );
1172  }
1173 
1174  bb.Inflate( aClearance );
1175  return bb;
1176 }
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:384
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:300
size_t i
Definition: json11.cpp:597
const BOX2I BBox(int aClearance=0) const override
Function BBox()

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

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

◆ BooleanAdd() [1/2]

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 505 of file shape_poly_set.cpp.

506 {
507  booleanOp( ctUnion, b, aFastMode );
508 }
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,...

References booleanOp().

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

◆ BooleanAdd() [2/2]

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 523 of file shape_poly_set.cpp.

526 {
527  booleanOp( ctUnion, a, b, aFastMode );
528 }
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,...

References booleanOp().

◆ BooleanIntersection() [1/2]

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 517 of file shape_poly_set.cpp.

518 {
519  booleanOp( ctIntersection, b, aFastMode );
520 }
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,...

References booleanOp().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), DRC_COURTYARD_OVERLAP::RunDRC(), and TransformOvalClearanceToPolygon().

◆ BooleanIntersection() [2/2]

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 539 of file shape_poly_set.cpp.

542 {
543  booleanOp( ctIntersection, a, b, aFastMode );
544 }
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,...

References booleanOp().

◆ booleanOp() [1/2]

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 469 of file shape_poly_set.cpp.

471 {
472  booleanOp( aType, *this, aOtherShape, aFastMode );
473 }
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,...

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

◆ booleanOp() [2/2]

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 476 of file shape_poly_set.cpp.

480 {
481  Clipper c;
482 
483  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
484 
485  for( auto poly : aShape.m_polys )
486  {
487  for( size_t i = 0 ; i < poly.size(); i++ )
488  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
489  }
490 
491  for( auto poly : aOtherShape.m_polys )
492  {
493  for( size_t i = 0; i < poly.size(); i++ )
494  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
495  }
496 
497  PolyTree solution;
498 
499  c.Execute( aType, solution, pftNonZero, pftNonZero );
500 
501  importTree( &solution );
502 }
size_t i
Definition: json11.cpp:597
void importTree(ClipperLib::PolyTree *tree)

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

◆ BooleanSubtract() [1/2]

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 511 of file shape_poly_set.cpp.

512 {
513  booleanOp( ctDifference, b, aFastMode );
514 }
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,...

References booleanOp().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), addHoleToPolygon(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), CreateThermalReliefPadPolygon(), C3D_RENDER_OGL_LEGACY::generate_3D_Vias_and_Pads(), AR_AUTOPLACER::genModuleOnRoutingMatrix(), APERTURE_MACRO::GetApertureMacroShape(), NormalizeAreaOutlines(), ZONE_CREATE_HELPER::performZoneCutout(), AR_AUTOPLACER::testModuleByPolygon(), and TransformRoundChamferedRectToPolygon().

◆ BooleanSubtract() [2/2]

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 531 of file shape_poly_set.cpp.

534 {
535  booleanOp( ctDifference, a, b, aFastMode );
536 }
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,...

References booleanOp().

◆ CacheTriangulation()

void SHAPE_POLY_SET::CacheTriangulation ( )

Definition at line 1852 of file shape_poly_set.cpp.

1853 {
1854  bool recalculate = !m_hash.IsValid();
1855  MD5_HASH hash;
1856 
1857  if( !m_triangulationValid )
1858  recalculate = true;
1859 
1860  if( !recalculate )
1861  {
1862  hash = checksum();
1863 
1864  if( m_hash != hash )
1865  {
1866  m_hash = hash;
1867  recalculate = true;
1868  }
1869  }
1870 
1871  if( !recalculate )
1872  return;
1873 
1874  SHAPE_POLY_SET tmpSet = *this;
1875 
1876  if( tmpSet.HasHoles() )
1877  tmpSet.Fracture( PM_FAST );
1878 
1879  m_triangulatedPolys.clear();
1880  m_triangulationValid = true;
1881 
1882  while( tmpSet.OutlineCount() > 0 )
1883  {
1884  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
1885  PolygonTriangulation tess( *m_triangulatedPolys.back() );
1886 
1887  // If the tesselation fails, we re-fracture the polygon, which will
1888  // first simplify the system before fracturing and removing the holes
1889  // This may result in multiple, disjoint polygons.
1890  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
1891  {
1892  tmpSet.Fracture( PM_FAST );
1893  m_triangulationValid = false;
1894  continue;
1895  }
1896 
1897  tmpSet.DeletePolygon( 0 );
1898  m_triangulationValid = true;
1899  }
1900 
1901  if( m_triangulationValid )
1902  m_hash = checksum();
1903 }
int OutlineCount() const
Returns the number of outlines in the set
bool HasHoles() const
Returns true if the polygon set has any holes.
MD5_HASH checksum() const
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
Class SHAPE_POLY_SET.
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
bool IsValid() const
Definition: md5_hash.h:24

References checksum(), DeletePolygon(), Fracture(), HasHoles(), MD5_HASH::IsValid(), m_hash, m_triangulatedPolys, m_triangulationValid, OutlineCount(), PM_FAST, and Polygon().

Referenced by ZONE_CONTAINER::CacheTriangulation(), Convert_shape_line_polygon_to_triangles(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), and PNS_KICAD_IFACE::syncZone().

◆ Centre()

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.

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

References SHAPE::BBox(), and BOX2< Vec >::Centre().

◆ Chamfer()

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 1632 of file shape_poly_set.cpp.

1633 {
1634  SHAPE_POLY_SET chamfered;
1635 
1636  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1637  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1638 
1639  return chamfered;
1640 }
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
Class SHAPE_POLY_SET.

References ChamferPolygon(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), and ZONE_CONTAINER::BuildSmoothedPoly().

◆ chamferFilletPolygon()

SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::chamferFilletPolygon ( CORNER_MODE  aMode,
unsigned int  aDistance,
int  aIndex,
int  aErrorMax = -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.
aErrorMaxis the maximum allowable deviation of the polygon from the circle if aMode = FILLETED. If aMode = CHAMFERED, it is unused.
Returns
POLYGON - the chamfered/filleted version of the polygon.

Definition at line 1654 of file shape_poly_set.cpp.

1658 {
1659  // Null segments create serious issues in calculations. Remove them:
1661 
1662  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1663  SHAPE_POLY_SET::POLYGON newPoly;
1664 
1665  // If the chamfering distance is zero, then the polygon remain intact.
1666  if( aDistance == 0 )
1667  {
1668  return currentPoly;
1669  }
1670 
1671  // Iterate through all the contours (outline and holes) of the polygon.
1672  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1673  {
1674  // Generate a new contour in the new polygon
1675  SHAPE_LINE_CHAIN newContour;
1676 
1677  // Iterate through the vertices of the contour
1678  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1679  {
1680  // Current vertex
1681  int x1 = currContour.Point( currVertex ).x;
1682  int y1 = currContour.Point( currVertex ).y;
1683 
1684  // Indices for previous and next vertices.
1685  int prevVertex;
1686  int nextVertex;
1687 
1688  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1689 
1690  // Previous vertex is the last one if the current vertex is the first one
1691  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1692 
1693  // next vertex is the first one if the current vertex is the last one.
1694  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1695 
1696  // Previous vertex computation
1697  double xa = currContour.Point( prevVertex ).x - x1;
1698  double ya = currContour.Point( prevVertex ).y - y1;
1699 
1700  // Next vertex computation
1701  double xb = currContour.Point( nextVertex ).x - x1;
1702  double yb = currContour.Point( nextVertex ).y - y1;
1703 
1704  // Compute the new distances
1705  double lena = hypot( xa, ya );
1706  double lenb = hypot( xb, yb );
1707 
1708  // Make the final computations depending on the mode selected, chamfered or filleted.
1709  if( aMode == CORNER_MODE::CHAMFERED )
1710  {
1711  double distance = aDistance;
1712 
1713  // Chamfer one half of an edge at most
1714  if( 0.5 * lena < distance )
1715  distance = 0.5 * lena;
1716 
1717  if( 0.5 * lenb < distance )
1718  distance = 0.5 * lenb;
1719 
1720  int nx1 = round_nearest( distance * xa / lena );
1721  int ny1 = round_nearest( distance * ya / lena );
1722 
1723  newContour.Append( x1 + nx1, y1 + ny1 );
1724 
1725  int nx2 = round_nearest( distance * xb / lenb );
1726  int ny2 = round_nearest( distance * yb / lenb );
1727 
1728  newContour.Append( x1 + nx2, y1 + ny2 );
1729  }
1730  else // CORNER_MODE = FILLETED
1731  {
1732  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1733 
1734  double radius = aDistance;
1735  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1736 
1737  // Do nothing in case of parallel edges
1738  if( std::isinf( denom ) )
1739  continue;
1740 
1741  // Limit rounding distance to one half of an edge
1742  if( 0.5 * lena * denom < radius )
1743  radius = 0.5 * lena * denom;
1744 
1745  if( 0.5 * lenb * denom < radius )
1746  radius = 0.5 * lenb * denom;
1747 
1748  // Calculate fillet arc absolute center point (xc, yx)
1749  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1750  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1751  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1752  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1753  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1754 
1755  // Calculate arc start and end vectors
1756  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1757  double xs = x1 + k * xa / lena - xc;
1758  double ys = y1 + k * ya / lena - yc;
1759  double xe = x1 + k * xb / lenb - xc;
1760  double ye = y1 + k * yb / lenb - yc;
1761 
1762  // Cosine of arc angle
1763  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1764 
1765  // Make sure the argument is in [-1,1], interval in which the acos function is
1766  // defined
1767  if( argument < -1 )
1768  argument = -1;
1769  else if( argument > 1 )
1770  argument = 1;
1771 
1772  double arcAngle = acos( argument );
1773  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1774  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1775 
1776  double deltaAngle = arcAngle / segments;
1777  double startAngle = atan2( -ys, xs );
1778 
1779  // Flip arc for inner corners
1780  if( xa * yb - ya * xb <= 0 )
1781  deltaAngle *= -1;
1782 
1783  double nx = xc + xs;
1784  double ny = yc + ys;
1785 
1786  newContour.Append( round_nearest( nx ), round_nearest( ny ) );
1787 
1788  // Store the previous added corner to make a sanity check
1789  int prevX = round_nearest( nx );
1790  int prevY = round_nearest( ny );
1791 
1792  for( int j = 0; j < segments; j++ )
1793  {
1794  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1795  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1796 
1797  // Sanity check: the rounding can produce repeated corners; do not add them.
1798  if( round_nearest( nx ) != prevX || round_nearest( ny ) != prevY )
1799  {
1800  newContour.Append( round_nearest( nx ), round_nearest( ny ) );
1801  prevX = round_nearest( nx );
1802  prevY = round_nearest( ny );
1803  }
1804  }
1805  }
1806  }
1807 
1808  // Close the current contour and add it the new polygon
1809  newContour.SetClosed( true );
1810  newPoly.push_back( newContour );
1811  }
1812 
1813  return newPoly;
1814 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
static int round_nearest(double v)
Definition: math_util.h:56
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.
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
VECTOR2I & Point(int aIndex)
Function Point()
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set

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

Referenced by ChamferPolygon(), and FilletPolygon().

◆ ChamferPolygon()

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 1508 of file shape_poly_set.cpp.

1509 {
1510  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1511 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...

References chamferFilletPolygon().

Referenced by Chamfer().

◆ checksum()

MD5_HASH SHAPE_POLY_SET::checksum ( ) const
private

Definition at line 1906 of file shape_poly_set.cpp.

1907 {
1908  MD5_HASH hash;
1909 
1910  hash.Hash( m_polys.size() );
1911 
1912  for( const auto& outline : m_polys )
1913  {
1914  hash.Hash( outline.size() );
1915 
1916  for( const auto& lc : outline )
1917  {
1918  hash.Hash( lc.PointCount() );
1919 
1920  for( int i = 0; i < lc.PointCount(); i++ )
1921  {
1922  hash.Hash( lc.CPoint( i ).x );
1923  hash.Hash( lc.CPoint( i ).y );
1924  }
1925  }
1926  }
1927 
1928  hash.Finalize();
1929 
1930  return hash;
1931 }
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66
size_t i
Definition: json11.cpp:597
void Finalize()
Definition: md5_hash.cpp:76

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

Referenced by CacheTriangulation(), GetHash(), and IsTriangulationUpToDate().

◆ CHole()

const SHAPE_LINE_CHAIN& SHAPE_POLY_SET::CHole ( int  aOutline,
int  aHole 
) const
inline

◆ CIterate() [1/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aFirst,
int  aLast,
bool  aIterateHoles = false 
) const
inline

Definition at line 700 of file shape_poly_set.h.

701  {
702  CONST_ITERATOR iter;
703 
704  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
705  iter.m_currentPolygon = aFirst;
706  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
707  iter.m_currentContour = 0;
708  iter.m_currentVertex = 0;
709  iter.m_iterateHoles = aIterateHoles;
710 
711  return iter;
712  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR

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(), ConvertOutlineToPolygon(), EDGE_MODULE::Draw(), PCB_IO::format(), DRAWSEGMENT::GetBoundingBox(), BRDITEMS_PLOTTER::PlotFilledAreas(), and PNS_KICAD_IFACE::syncPad().

◆ CIterate() [2/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aOutline) const
inline

Definition at line 714 of file shape_poly_set.h.

715  {
716  return CIterate( aOutline, aOutline );
717  }
CONST_ITERATOR CIterate() const

References CIterate().

◆ CIterate() [3/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( ) const
inline

Definition at line 724 of file shape_poly_set.h.

725  {
726  return CIterate( 0, OutlineCount() - 1 );
727  }
int OutlineCount() const
Returns the number of outlines in the set
CONST_ITERATOR CIterate() const

References OutlineCount().

Referenced by CIterate(), and CIterateWithHoles().

◆ CIterateWithHoles() [1/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( int  aOutline) const
inline

Definition at line 719 of file shape_poly_set.h.

720  {
721  return CIterate( aOutline, aOutline, true );
722  }
CONST_ITERATOR CIterate() const

References CIterate().

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

◆ CIterateWithHoles() [2/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( ) const
inline

Definition at line 729 of file shape_poly_set.h.

730  {
731  return CIterate( 0, OutlineCount() - 1, true );
732  }
int OutlineCount() const
Returns the number of outlines in the set
CONST_ITERATOR CIterate() const

References CIterate(), and OutlineCount().

◆ Clone()

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 77 of file shape_poly_set.cpp.

78 {
79  return new SHAPE_POLY_SET( *this );
80 }

References SHAPE_POLY_SET().

◆ Collide() [1/4]

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 545 of file shape_collisions.cpp.

546 {
547  return CollideShapes( this, aShape, aClearance, true, aMTV );
548 }
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)

References CollideShapes().

◆ Collide() [2/4]

bool SHAPE::Collide ( const SHAPE aShape,
int  aClearance = 0 
) const
virtualinherited

Definition at line 551 of file shape_collisions.cpp.

552 {
553  VECTOR2I dummy;
554 
555  return CollideShapes( this, aShape, aClearance, false, dummy );
556 }
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)

References CollideShapes(), and dummy().

◆ Collide() [3/4]

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 1227 of file shape_poly_set.cpp.

1228 {
1229  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1230 
1231  // Inflate the polygon if necessary.
1232  if( aClearance > 0 )
1233  {
1234  // fixme: the number of arc segments should not be hardcoded
1235  polySet.Inflate( aClearance, 8 );
1236  }
1237 
1238  // There is a collision if and only if the point is inside of the polygon.
1239  return polySet.Contains( aP );
1240 }
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.

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

Referenced by DRAWSEGMENT::HitTest().

◆ Collide() [4/4]

bool SHAPE_POLY_SET::Collide ( const SEG aSeg,
int  aClearance = 0 
) const
overridevirtual

Function Collide Checks whether the segment aSeg collides with the inside of the polygon set; if the segment touches an edge or a corner of any of the polygons, there is no collision: the edges do not belong to the polygon itself.

Parameters
aSegis the SEG segment whose collision with respect to the poly set will be tested.
aClearanceis the security distance; if the segment passes closer to the polygon than aClearance distance, then there is a collision.
Returns
bool - true if the segment aSeg collides with the polygon; false in any other case.

Implements SHAPE.

Definition at line 1196 of file shape_poly_set.cpp.

1197 {
1198 
1199  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1200 
1201  // Inflate the polygon if necessary.
1202  if( aClearance > 0 )
1203  {
1204  // fixme: the number of arc segments should not be hardcoded
1205  polySet.Inflate( aClearance, 8 );
1206  }
1207 
1208  // We are going to check to see if the segment crosses an external
1209  // boundary. However, if the full segment is inside the polyset, this
1210  // will not be true. So we first test to see if one of the points is
1211  // inside. If true, then we collide
1212  if( polySet.Contains( aSeg.A ) )
1213  return true;
1214 
1215  for( SEGMENT_ITERATOR iterator = polySet.IterateSegmentsWithHoles(); iterator; iterator++ )
1216  {
1217  SEG polygonEdge = *iterator;
1218 
1219  if( polygonEdge.Intersect( aSeg, true ) )
1220  return true;
1221  }
1222 
1223  return false;
1224 }
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:132
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
Class SHAPE_POLY_SET.
Definition: seg.h:36
VECTOR2I A
Definition: seg.h:44

References SEG::A, Contains(), Inflate(), SEG::Intersect(), IterateSegmentsWithHoles(), and SHAPE_POLY_SET().

◆ CollideEdge()

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 1368 of file shape_poly_set.cpp.

1370 {
1371  // Shows whether there was a collision
1372  bool collision = false;
1373 
1374  SEGMENT_ITERATOR iterator;
1375 
1376  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1377  {
1378  SEG currentSegment = *iterator;
1379  int distance = currentSegment.Distance( aPoint );
1380 
1381  // Check for collisions
1382  if( distance <= aClearance )
1383  {
1384  collision = true;
1385 
1386  // Update aClearance to look for closer edges
1387  aClearance = distance;
1388 
1389  // Store the indices that identify the vertex
1390  aClosestVertex = iterator.GetIndex();
1391  }
1392  }
1393 
1394  return collision;
1395 }
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:199
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
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)

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

Referenced by DRAWSEGMENT::HitTest(), and ZONE_CONTAINER::HitTestForEdge().

◆ CollideVertex()

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 1330 of file shape_poly_set.cpp.

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

References delta, distance(), and IterateWithHoles().

Referenced by ZONE_CONTAINER::HitTestForCorner().

◆ Contains()

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 1398 of file shape_poly_set.cpp.

1399 {
1400  if( m_polys.size() == 0 ) // empty set?
1401  return false;
1402 
1403  // If there is a polygon specified, check the condition against that polygon
1404  if( aSubpolyIndex >= 0 )
1405  return containsSingle( aP, aSubpolyIndex, aIgnoreHoles );
1406 
1407  // In any other case, check it against all polygons in the set
1408  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1409  {
1410  if( containsSingle( aP, polygonIdx, aIgnoreHoles ) )
1411  return true;
1412  }
1413 
1414  return false;
1415 }
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 OutlineCount() const
Returns the number of outlines in the set

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

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

◆ containsSingle()

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 1436 of file shape_poly_set.cpp.

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

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

Referenced by Contains(), and DistanceToPolygon().

◆ COutline()

◆ CPolygon()

◆ CVertex() [1/3]

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 297 of file shape_poly_set.cpp.

298 {
299  if( aOutline < 0 )
300  aOutline += m_polys.size();
301 
302  int idx;
303 
304  if( aHole < 0 )
305  idx = 0;
306  else
307  idx = aHole + 1;
308 
309  assert( aOutline < (int) m_polys.size() );
310  assert( idx < (int) m_polys[aOutline].size() );
311 
312  return m_polys[aOutline][idx].CPoint( aIndex );
313 }

References m_polys.

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

◆ CVertex() [2/3]

const VECTOR2I & SHAPE_POLY_SET::CVertex ( int  aGlobalIndex) const

Returns the aGlobalIndex-th vertex in the poly set

Definition at line 328 of file shape_poly_set.cpp.

329 {
331 
332  // Assure the passed index references a legal position; abort otherwise
333  if( !GetRelativeIndices( aGlobalIndex, &index ) )
334  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
335 
336  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
337 }
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.

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.

◆ CVertex() [3/3]

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 346 of file shape_poly_set.cpp.

347 {
348  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
349 }
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline

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

◆ cvertex()

const VECTOR2I& SHAPE_POLY_SET::cvertex ( int  aCornerId) const
private

◆ DeletePolygon()

void SHAPE_POLY_SET::DeletePolygon ( int  aIdx)

Deletes aIdx-th polygon from the set

Definition at line 1312 of file shape_poly_set.cpp.

1313 {
1314  m_polys.erase( m_polys.begin() + aIdx );
1315 }

References m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), CacheTriangulation(), and ZONE_FILLER::Fill().

◆ Distance() [1/2]

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 1583 of file shape_poly_set.cpp.

1584 {
1585  int currentDistance;
1586  int minDistance = DistanceToPolygon( aPoint, 0 );
1587 
1588  // Iterate through all the polygons and get the minimum distance.
1589  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1590  {
1591  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1592 
1593  if( currentDistance < minDistance )
1594  minDistance = currentDistance;
1595  }
1596 
1597  return minDistance;
1598 }
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.

References DistanceToPolygon(), and m_polys.

Referenced by DRC::doTrackDrc(), DRC::doTrackKeepoutDrc(), DRC_MARKER_FACTORY::NewMarker(), DRC::testCopperDrawItem(), DRC::testCopperTextItem(), and DRC::testKeepoutAreas().

◆ Distance() [2/2]

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 1601 of file shape_poly_set.cpp.

1602 {
1603  int currentDistance;
1604  int minDistance = DistanceToPolygon( aSegment, 0, aSegmentWidth );
1605 
1606  // Iterate through all the polygons and get the minimum distance.
1607  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1608  {
1609  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1610 
1611  if( currentDistance < minDistance )
1612  minDistance = currentDistance;
1613  }
1614 
1615  return minDistance;
1616 }
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.

References DistanceToPolygon(), and m_polys.

◆ DistanceToPolygon() [1/2]

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 1522 of file shape_poly_set.cpp.

1523 {
1524  // We calculate the min dist between the segment and each outline segment
1525  // However, if the segment to test is inside the outline, and does not cross
1526  // any edge, it can be seen outside the polygon.
1527  // Therefore test if a segment end is inside ( testing only one end is enough )
1528  if( containsSingle( aPoint, aPolygonIndex ) )
1529  return 0;
1530 
1531  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1532 
1533  SEG polygonEdge = *iterator;
1534  int minDistance = polygonEdge.Distance( aPoint );
1535 
1536  for( iterator++; iterator && minDistance > 0; iterator++ )
1537  {
1538  polygonEdge = *iterator;
1539 
1540  int currentDistance = polygonEdge.Distance( aPoint );
1541 
1542  if( currentDistance < minDistance )
1543  minDistance = currentDistance;
1544  }
1545 
1546  return minDistance;
1547 }
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:199
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

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

Referenced by Distance().

◆ DistanceToPolygon() [2/2]

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 1550 of file shape_poly_set.cpp.

1551 {
1552  // We calculate the min dist between the segment and each outline segment
1553  // However, if the segment to test is inside the outline, and does not cross
1554  // any edge, it can be seen outside the polygon.
1555  // Therefore test if a segment end is inside ( testing only one end is enough )
1556  if( containsSingle( aSegment.A, aPolygonIndex ) )
1557  return 0;
1558 
1559  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1560 
1561  SEG polygonEdge = *iterator;
1562  int minDistance = polygonEdge.Distance( aSegment );
1563 
1564  for( iterator++; iterator && minDistance > 0; iterator++ )
1565  {
1566  polygonEdge = *iterator;
1567 
1568  int currentDistance = polygonEdge.Distance( aSegment );
1569 
1570  if( currentDistance < minDistance )
1571  minDistance = currentDistance;
1572  }
1573 
1574  // Take into account the width of the segment
1575  if( aSegmentWidth > 0 )
1576  minDistance -= aSegmentWidth / 2;
1577 
1578  // Return the maximum of minDistance and zero
1579  return minDistance < 0 ? 0 : minDistance;
1580 }
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:199
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:44

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

◆ Fillet()

SHAPE_POLY_SET SHAPE_POLY_SET::Fillet ( int  aRadius,
int  aErrorMax 
)

Function Fillet returns a filleted version of the polygon set.

Parameters
aRadiusis the fillet radius.
aErrorMaxis the maximum allowable deviation of the polygon from the circle
Returns
SHAPE_POLY_SET - A set containing the filleted version of this set.

Definition at line 1643 of file shape_poly_set.cpp.

1644 {
1645  SHAPE_POLY_SET filleted;
1646 
1647  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1648  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, polygonIdx ) );
1649 
1650  return filleted;
1651 }
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex=0)
Function Fillet returns a filleted version of the aIndex-th polygon.
Class SHAPE_POLY_SET.

References FilletPolygon(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), and ZONE_CONTAINER::BuildSmoothedPoly().

◆ FilletPolygon()

SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon ( unsigned int  aRadius,
int  aErrorMax,
int  aIndex = 0 
)

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

Parameters
aRadiusis the fillet radius.
aErrorMaxis the maximum allowable deviation of the polygon from the circle
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 1514 of file shape_poly_set.cpp.

1517 {
1518  return chamferFilletPolygon( CORNER_MODE::FILLETED, aRadius, aIndex, aErrorMax );
1519 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...

References chamferFilletPolygon().

Referenced by Fillet().

◆ Format()

const std::string SHAPE_POLY_SET::Format ( ) const
overridevirtual

Reimplemented from SHAPE.

Definition at line 1078 of file shape_poly_set.cpp.

1079 {
1080  std::stringstream ss;
1081 
1082  ss << "polyset " << m_polys.size() << "\n";
1083 
1084  for( unsigned i = 0; i < m_polys.size(); i++ )
1085  {
1086  ss << "poly " << m_polys[i].size() << "\n";
1087 
1088  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1089  {
1090  ss << m_polys[i][j].PointCount() << "\n";
1091 
1092  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1093  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1094  }
1095 
1096  ss << "\n";
1097  }
1098 
1099  return ss.str();
1100 }
size_t i
Definition: json11.cpp:597

References i, and m_polys.

◆ Fracture()

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 839 of file shape_poly_set.cpp.

840 {
841  Simplify( aFastMode ); // remove overlapping holes/degeneracy
842 
843  for( POLYGON& paths : m_polys )
844  {
845  fractureSingle( paths );
846  }
847 }
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...

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

Referenced by addHoleToPolygon(), D_PAD::AddPrimitive(), D_PAD::buildCustomPadPolygon(), CacheTriangulation(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), AR_AUTOPLACER::drawPlacementRoutingMatrix(), export_vrml_polygon(), AR_AUTOPLACER::fillMatrix(), ZONE_FILLER::fillSingleZone(), APERTURE_MACRO::GetApertureMacroShape(), InflateWithLinkedHoles(), BRDITEMS_PLOTTER::PlotDrawSegment(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), C3D_RENDER_RAYTRACING::reload(), ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon(), TransformRingToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

◆ fractureSingle()

void SHAPE_POLY_SET::fractureSingle ( POLYGON paths)
private

Definition at line 737 of file shape_poly_set.cpp.

738 {
739  FractureEdgeSet edges;
740  FractureEdgeSet border_edges;
741  FractureEdge* root = NULL;
742 
743  bool first = true;
744 
745  if( paths.size() == 1 )
746  return;
747 
748  int num_unconnected = 0;
749 
750  for( SHAPE_LINE_CHAIN& path : paths )
751  {
752  int index = 0;
753 
754  FractureEdge* prev = NULL, * first_edge = NULL;
755 
756  int x_min = std::numeric_limits<int>::max();
757 
758  for( int i = 0; i < path.PointCount(); i++ )
759  {
760  const VECTOR2I& p = path.CPoint( i );
761 
762  if( p.x < x_min )
763  x_min = p.x;
764  }
765 
766  for( int i = 0; i < path.PointCount(); i++ )
767  {
768  FractureEdge* fe = new FractureEdge( first, &path, index++ );
769 
770  if( !root )
771  root = fe;
772 
773  if( !first_edge )
774  first_edge = fe;
775 
776  if( prev )
777  prev->m_next = fe;
778 
779  if( i == path.PointCount() - 1 )
780  fe->m_next = first_edge;
781 
782  prev = fe;
783  edges.push_back( fe );
784 
785  if( !first )
786  {
787  if( fe->m_p1.x == x_min )
788  border_edges.push_back( fe );
789  }
790 
791  if( !fe->m_connected )
792  num_unconnected++;
793  }
794 
795  first = false; // first path is always the outline
796  }
797 
798  // keep connecting holes to the main outline, until there's no holes left...
799  while( num_unconnected > 0 )
800  {
801  int x_min = std::numeric_limits<int>::max();
802 
803  FractureEdge* smallestX = NULL;
804 
805  // find the left-most hole edge and merge with the outline
806  for( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
807  {
808  int xt = (*i)->m_p1.x;
809 
810  if( ( xt < x_min ) && !(*i)->m_connected )
811  {
812  x_min = xt;
813  smallestX = *i;
814  }
815  }
816 
817  num_unconnected -= processEdge( edges, smallestX );
818  }
819 
820  paths.clear();
821  SHAPE_LINE_CHAIN newPath;
822 
823  newPath.SetClosed( true );
824 
825  FractureEdge* e;
826 
827  for( e = root; e->m_next != root; e = e->m_next )
828  newPath.Append( e->m_p1 );
829 
830  newPath.Append( e->m_p1 );
831 
832  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
833  delete *i;
834 
835  paths.push_back( newPath );
836 }
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
size_t i
Definition: json11.cpp:597
std::vector< FractureEdge * > FractureEdgeSet

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

Referenced by Fracture().

◆ getContourForCorner()

SHAPE_LINE_CHAIN& SHAPE_POLY_SET::getContourForCorner ( int  aCornerId,
int &  aIndexWithinContour 
)
private

◆ GetGlobalIndex()

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 123 of file shape_poly_set.cpp.

125 {
126  int selectedVertex = aRelativeIndices.m_vertex;
127  unsigned int selectedContour = aRelativeIndices.m_contour;
128  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
129 
130  // Check whether the vertex indices make sense in this poly set
131  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
132  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
133  {
134  POLYGON currentPolygon;
135 
136  aGlobalIdx = 0;
137 
138  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
139  {
140  currentPolygon = Polygon( polygonIdx );
141 
142  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
143  {
144  aGlobalIdx += currentPolygon[contourIdx].PointCount();
145  }
146  }
147 
148  currentPolygon = Polygon( selectedPolygon );
149 
150  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
151  {
152  aGlobalIdx += currentPolygon[contourIdx].PointCount();
153  }
154 
155  aGlobalIdx += selectedVertex;
156 
157  return true;
158  }
159  else
160  {
161  return false;
162  }
163 }
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

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

◆ GetHash()

MD5_HASH SHAPE_POLY_SET::GetHash ( ) const

Definition at line 1829 of file shape_poly_set.cpp.

1830 {
1831  if( !m_hash.IsValid() )
1832  return checksum();
1833 
1834  return m_hash;
1835 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:24

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

Referenced by ZONE_CONTAINER::BuildHashValue(), and SHAPE_POLY_SET().

◆ GetNeighbourIndexes()

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 352 of file shape_poly_set.cpp.

353 {
355 
356  // If the edge does not exist, throw an exception, it is an illegal access memory error
357  if( !GetRelativeIndices( aGlobalIndex, &index ) )
358  return false;
359 
360  // Calculate the previous and next index of aGlobalIndex, corresponding to
361  // the same contour;
362  VERTEX_INDEX inext = index;
363  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
364 
365  if( index.m_vertex == 0 )
366  {
367  index.m_vertex = lastpoint;
368  inext.m_vertex = 1;
369  }
370  else if( index.m_vertex == lastpoint )
371  {
372  index.m_vertex--;
373  inext.m_vertex = 0;
374  }
375  else
376  {
377  inext.m_vertex++;
378  index.m_vertex--;
379  }
380 
381  if( aPrevious )
382  {
383  int previous;
384  GetGlobalIndex( index, previous );
385  *aPrevious = previous;
386  }
387 
388  if( aNext )
389  {
390  int next;
391  GetGlobalIndex( inext, next );
392  *aNext = next;
393  }
394 
395  return true;
396 }
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,...

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

◆ GetRelativeIndices()

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 83 of file shape_poly_set.cpp.

85 {
86  int polygonIdx = 0;
87  unsigned int contourIdx = 0;
88  int vertexIdx = 0;
89 
90  int currentGlobalIdx = 0;
91 
92  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
93  {
94  const POLYGON currentPolygon = CPolygon( polygonIdx );
95 
96  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
97  {
98  SHAPE_LINE_CHAIN currentContour = currentPolygon[contourIdx];
99  int totalPoints = currentContour.PointCount();
100 
101  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
102  {
103  // Check if the current vertex is the globally indexed as aGlobalIdx
104  if( currentGlobalIdx == aGlobalIdx )
105  {
106  aRelativeIndices->m_polygon = polygonIdx;
107  aRelativeIndices->m_contour = contourIdx;
108  aRelativeIndices->m_vertex = vertexIdx;
109 
110  return true;
111  }
112 
113  // Advance
114  currentGlobalIdx++;
115  }
116  }
117  }
118 
119  return false;
120 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
const POLYGON & CPolygon(int aIndex) const
int OutlineCount() const
Returns the number of outlines in the set
int PointCount() const
Function PointCount()
Class SHAPE_LINE_CHAIN.

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

◆ HasHoles()

bool SHAPE_POLY_SET::HasHoles ( ) const

Returns true if the polygon set has any holes.

Definition at line 1011 of file shape_poly_set.cpp.

1012 {
1013  // Iterate through all the polygons on the set
1014  for( const POLYGON& paths : m_polys )
1015  {
1016  // If any of them has more than one contour, it is a hole.
1017  if( paths.size() > 1 )
1018  return true;
1019  }
1020 
1021  // Return false if and only if every polygon has just one outline, without holes.
1022  return false;
1023 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.

References m_polys.

Referenced by CacheTriangulation().

◆ HasTouchingHoles()

bool SHAPE_POLY_SET::HasTouchingHoles ( ) const

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

Definition at line 1934 of file shape_poly_set.cpp.

1935 {
1936  for( int i = 0; i < OutlineCount(); i++ )
1937  {
1938  if( hasTouchingHoles( CPolygon( i ) ) )
1939  {
1940  return true;
1941  }
1942  }
1943 
1944  return false;
1945 }
const POLYGON & CPolygon(int aIndex) const
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.
size_t i
Definition: json11.cpp:597

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

◆ hasTouchingHoles()

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 1948 of file shape_poly_set.cpp.

1949 {
1950  std::set< long long > ptHashes;
1951 
1952  for( const auto& lc : aPoly )
1953  {
1954  for( const VECTOR2I& pt : lc.CPoints() )
1955  {
1956  const long long ptHash = (long long) pt.x << 32 | pt.y;
1957 
1958  if( ptHashes.count( ptHash ) > 0 )
1959  {
1960  return true;
1961  }
1962 
1963  ptHashes.insert( ptHash );
1964  }
1965  }
1966 
1967  return false;
1968 }

Referenced by HasTouchingHoles().

◆ Hole()

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 597 of file shape_poly_set.h.

598  {
599  return m_polys[aOutline][aHole + 1];
600  }

References m_polys.

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

◆ HoleCount()

int SHAPE_POLY_SET::HoleCount ( int  aOutline) const
inline

Returns the number of holes in a given outline

Definition at line 564 of file shape_poly_set.h.

565  {
566  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
567  return 0;
568 
569  // the first polygon in m_polys[aOutline] is the main contour,
570  // only others are holes:
571  return m_polys[aOutline].size() - 1;
572  }

References m_polys.

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

◆ importTree()

void SHAPE_POLY_SET::importTree ( ClipperLib::PolyTree *  tree)
private

Definition at line 601 of file shape_poly_set.cpp.

602 {
603  m_polys.clear();
604 
605  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
606  {
607  if( !n->IsHole() )
608  {
609  POLYGON paths;
610  paths.reserve( n->Childs.size() + 1 );
611  paths.push_back( n->Contour );
612 
613  for( unsigned int i = 0; i < n->Childs.size(); i++ )
614  paths.push_back( n->Childs[i]->Contour );
615 
616  m_polys.push_back( paths );
617  }
618  }
619 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
size_t i
Definition: json11.cpp:597

References i, and m_polys.

Referenced by booleanOp(), and Inflate().

◆ Inflate()

void SHAPE_POLY_SET::Inflate ( int  aFactor,
int  aCircleSegmentsCount 
)

Performs outline inflation/deflation, using round corners.

Polygons cna have holes, but not linked holes with main outlines, if aFactor < 0. When aFactor is < 0 a bad shape can result from these extra-segments used to link holes to main outlines Use InflateWithLinkedHoles for these polygons, especially if aFactor < 0

Definition at line 555 of file shape_poly_set.cpp.

556 {
557  // A static table to avoid repetitive calculations of the coefficient
558  // 1.0 - cos( M_PI/aCircleSegmentsCount)
559  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
560  #define SEG_CNT_MAX 64
561  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
562 
563  ClipperOffset c;
564 
565  for( const POLYGON& poly : m_polys )
566  {
567  for( size_t i = 0; i < poly.size(); i++ )
568  c.AddPath( poly[i].convertToClipper( i == 0 ), jtRound, etClosedPolygon );
569  }
570 
571  PolyTree solution;
572 
573  // Calculate the arc tolerance (arc error) from the seg count by circle.
574  // the seg count is nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aFactor))
575  // see:
576  // www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
577 
578  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
579  aCircleSegmentsCount = 6;
580 
581  double coeff;
582 
583  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
584  {
585  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
586 
587  if( aCircleSegmentsCount <= SEG_CNT_MAX )
588  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
589  }
590  else
591  coeff = arc_tolerance_factor[aCircleSegmentsCount];
592 
593  c.ArcTolerance = std::abs( aFactor ) * coeff;
594 
595  c.Execute( solution, aFactor );
596 
597  importTree( &solution );
598 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
#define abs(a)
Definition: auxiliary.h:84
#define SEG_CNT_MAX
size_t i
Definition: json11.cpp:597
void importTree(ClipperLib::PolyTree *tree)

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

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), D_PAD::buildCustomPadPolygon(), ZONE_FILLER::buildZoneFeatureHoleList(), Collide(), ZONE_FILLER::computeRawFilledAreas(), CINFO3D_VISU::createNewPadWithClearance(), export_vrml_polygon(), ZONE_FILLER::fillSingleZone(), GERBER_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadRoundRect(), MODULE::GetBoundingPoly(), MODULE::HitTestAccurate(), InflateWithLinkedHoles(), PlotSolderMaskLayer(), ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon(), TransformRoundChamferedRectToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

◆ InflateWithLinkedHoles()

void SHAPE_POLY_SET::InflateWithLinkedHoles ( int  aFactor,
int  aCircleSegmentsCount,
POLYGON_MODE  aFastMode 
)

Performs outline inflation/deflation, using round corners.

Polygons can have holes, and/or linked holes with main outlines. The resulting polygons are laso polygons with linked holes to main outlines For aFastMode meaning, see function booleanOp

Definition at line 547 of file shape_poly_set.cpp.

548 {
549  Simplify( aFastMode );
550  Inflate( aFactor, aCircleSegmentsCount );
551  Fracture( aFastMode );
552 }
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...

References Fracture(), Inflate(), and Simplify().

Referenced by KIGFX::PCB_PAINTER::draw(), D_PAD::DrawShape(), and PlotStandardLayer().

◆ InsertVertex()

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 216 of file shape_poly_set.cpp.

217 {
218  VERTEX_INDEX index;
219 
220  if( aGlobalIndex < 0 )
221  aGlobalIndex = 0;
222 
223  if( aGlobalIndex >= TotalVertices() )
224  {
225  Append( aNewVertex );
226  }
227  else
228  {
229  // Assure the position to be inserted exists; throw an exception otherwise
230  if( GetRelativeIndices( aGlobalIndex, &index ) )
231  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
232  else
233  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
234  }
235 }
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)

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

◆ IsEmpty()

◆ IsPolygonSelfIntersecting()

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 399 of file shape_poly_set.cpp.

400 {
401  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
402  SEGMENT_ITERATOR innerIterator;
403 
404  for( iterator = IterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
405  {
406  SEG firstSegment = *iterator;
407 
408  // Iterate through all remaining segments.
409  innerIterator = iterator;
410 
411  // Start in the next segment, we don't want to check collision between a segment and itself
412  for( innerIterator++; innerIterator; innerIterator++ )
413  {
414  SEG secondSegment = *innerIterator;
415 
416  // Check whether the two segments built collide, only when they are not adjacent.
417  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
418  return true;
419  }
420  }
421 
422  return false;
423 }
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:167

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

Referenced by IsSelfIntersecting().

◆ IsSelfIntersecting()

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 426 of file shape_poly_set.cpp.

427 {
428  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
429  {
430  if( IsPolygonSelfIntersecting( polygon ) )
431  return true;
432  }
433 
434  return false;
435 }
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.

References IsPolygonSelfIntersecting(), and m_polys.

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

◆ IsSolid()

bool SHAPE_POLY_SET::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 895 of file shape_poly_set.h.

896  {
897  return true;
898  }

◆ IsTriangulationUpToDate()

bool SHAPE_POLY_SET::IsTriangulationUpToDate ( ) const

Definition at line 1838 of file shape_poly_set.cpp.

1839 {
1840  if( !m_triangulationValid )
1841  return false;
1842 
1843  if( !m_hash.IsValid() )
1844  return false;
1845 
1846  auto hash = checksum();
1847 
1848  return hash == m_hash;
1849 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:24

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

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

◆ IsVertexInHole()

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 1619 of file shape_poly_set.cpp.

1620 {
1621  VERTEX_INDEX index;
1622 
1623  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1624  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1625  return false;
1626 
1627  // The contour is a hole if its index is greater than zero
1628  return index.m_contour > 0;
1629 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.

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

Referenced by PCB_EDIT_FRAME::createPopUpMenuForZones().

◆ Iterate() [1/3]

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 643 of file shape_poly_set.h.

644  {
645  ITERATOR iter;
646 
647  iter.m_poly = this;
648  iter.m_currentPolygon = aFirst;
649  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
650  iter.m_currentContour = 0;
651  iter.m_currentVertex = 0;
652  iter.m_iterateHoles = aIterateHoles;
653 
654  return iter;
655  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR

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

◆ Iterate() [2/3]

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 663 of file shape_poly_set.h.

664  {
665  return Iterate( aOutline, aOutline );
666  }
ITERATOR Iterate()
Function Iterate.

References Iterate().

◆ Iterate() [3/3]

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 684 of file shape_poly_set.h.

685  {
686  return Iterate( 0, OutlineCount() - 1 );
687  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR Iterate()
Function Iterate.

References OutlineCount().

Referenced by Iterate(), and IterateWithHoles().

◆ IterateFromVertexWithHoles()

ITERATOR SHAPE_POLY_SET::IterateFromVertexWithHoles ( int  aGlobalIdx)
inline

Definition at line 734 of file shape_poly_set.h.

735  {
736  // Build iterator
737  ITERATOR iter = IterateWithHoles();
738 
739  // Get the relative indices of the globally indexed vertex
740  VERTEX_INDEX indices;
741 
742  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
743  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
744 
745  // Adjust where the iterator is pointing
746  iter.m_currentPolygon = indices.m_polygon;
747  iter.m_currentContour = indices.m_contour;
748  iter.m_currentVertex = indices.m_vertex;
749 
750  return iter;
751  }
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.

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.

◆ IterateSegments() [1/3]

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 755 of file shape_poly_set.h.

756  {
757  SEGMENT_ITERATOR iter;
758 
759  iter.m_poly = this;
760  iter.m_currentPolygon = aFirst;
761  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
762  iter.m_currentContour = 0;
763  iter.m_currentSegment = 0;
764  iter.m_iterateHoles = aIterateHoles;
765 
766  return iter;
767  }
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR

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

Referenced by BRDITEMS_PLOTTER::PlotDrawSegment().

◆ IterateSegments() [2/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aPolygonIdx)
inline

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

Definition at line 770 of file shape_poly_set.h.

771  {
772  return IterateSegments( aPolygonIdx, aPolygonIdx );
773  }
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)

References IterateSegments().

◆ IterateSegments() [3/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( )
inline

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

Definition at line 776 of file shape_poly_set.h.

777  {
778  return IterateSegments( 0, OutlineCount() - 1 );
779  }
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)

References OutlineCount().

Referenced by IterateSegments(), and IterateSegmentsWithHoles().

◆ IterateSegmentsWithHoles() [1/2]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( )
inline

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

Definition at line 782 of file shape_poly_set.h.

783  {
784  return IterateSegments( 0, OutlineCount() - 1, true );
785  }
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)

References IterateSegments(), and OutlineCount().

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

◆ IterateSegmentsWithHoles() [2/2]

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 788 of file shape_poly_set.h.

789  {
790  return IterateSegments( aOutline, aOutline, true );
791  }
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)

References IterateSegments().

◆ IterateWithHoles() [1/2]

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 674 of file shape_poly_set.h.

675  {
676  return Iterate( aOutline, aOutline, true );
677  }
ITERATOR Iterate()
Function Iterate.

References Iterate().

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

◆ IterateWithHoles() [2/2]

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 694 of file shape_poly_set.h.

695  {
696  return Iterate( 0, OutlineCount() - 1, true );
697  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR Iterate()
Function Iterate.

References Iterate(), and OutlineCount().

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

◆ Move()

void SHAPE_POLY_SET::Move ( const VECTOR2I aVector)
overridevirtual

Implements SHAPE.

Definition at line 1468 of file shape_poly_set.cpp.

1469 {
1470  for( POLYGON& poly : m_polys )
1471  {
1472  for( SHAPE_LINE_CHAIN& path : poly )
1473  {
1474  path.Move( aVector );
1475  }
1476  }
1477 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.

References m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), KIGFX::GERBVIEW_PAINTER::drawFlashedShape(), export_vrml_polygon(), GERBER_DRAW_ITEM::HitTest(), ZONE_CONTAINER::Move(), AR_AUTOPLACER::testModuleByPolygon(), TransformOvalClearanceToPolygon(), and TransformRoundChamferedRectToPolygon().

◆ NewHole()

int SHAPE_POLY_SET::NewHole ( int  aOutline = -1)

Creates a new hole in a given outline

Definition at line 178 of file shape_poly_set.cpp.

179 {
180  SHAPE_LINE_CHAIN empty_path;
181 
182  empty_path.SetClosed( true );
183 
184  // Default outline is the last one
185  if( aOutline < 0 )
186  aOutline += m_polys.size();
187 
188  // Add hole to the selected outline
189  m_polys[aOutline].push_back( empty_path );
190 
191  return m_polys.back().size() - 2;
192 }
void SetClosed(bool aClosed)
Function SetClosed()
Class SHAPE_LINE_CHAIN.

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by ConvertOutlineToPolygon(), ZONE_CONTAINER::NewHole(), and TransformRingToPolygon().

◆ NewOutline()

int SHAPE_POLY_SET::NewOutline ( )

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

Definition at line 166 of file shape_poly_set.cpp.

167 {
168  SHAPE_LINE_CHAIN empty_path;
169  POLYGON poly;
170 
171  empty_path.SetClosed( true );
172  poly.push_back( empty_path );
173  m_polys.push_back( poly );
174  return m_polys.size() - 1;
175 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void SetClosed(bool aClosed)
Function SetClosed()
Class SHAPE_LINE_CHAIN.

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), AR_AUTOPLACER::addPad(), addRect(), ZONE_CONTAINER::AppendCorner(), BuildBoardPolygonOutlines(), D_PAD::buildCustomPadPolygon(), D_PAD::BuildPadShapePolygon(), ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), ZONE_FILLER::buildZoneFeatureHoleList(), ConvertOutlineToPolygon(), 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(), PCB_PARSER::parseZONE_CONTAINER(), DXF_PLOTTER::PlotPoly(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), DRAWSEGMENT::SetPolyPoints(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalClearanceToPolygon(), TransformRoundChamferedRectToPolygon(), TransformRoundedEndsSegmentToPolygon(), DRAWSEGMENT::TransformShapeWithClearanceToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

◆ NormalizeAreaOutlines()

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 1045 of file shape_poly_set.cpp.

1046 {
1047  // We are expecting only one main outline, but this main outline can have holes
1048  // if holes: combine holes and remove them from the main outline.
1049  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1050  // calculations, but it is not mandatory. It is used mainly
1051  // because there is usually only very few vertices in area outlines
1052  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1053  SHAPE_POLY_SET holesBuffer;
1054 
1055  // Move holes stored in outline to holesBuffer:
1056  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1057  while( outline.size() > 1 )
1058  {
1059  holesBuffer.AddOutline( outline.back() );
1060  outline.pop_back();
1061  }
1062 
1064 
1065  // If any hole, substract it to main outline
1066  if( holesBuffer.OutlineCount() )
1067  {
1068  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1070  }
1071 
1073 
1074  return OutlineCount();
1075 }
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

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

Referenced by BOARD::NormalizeAreaPolygon().

◆ operator=()

SHAPE_POLY_SET & SHAPE_POLY_SET::operator= ( const SHAPE_POLY_SET aOther)

Definition at line 1817 of file shape_poly_set.cpp.

1818 {
1819  static_cast<SHAPE&>(*this) = aOther;
1820  m_polys = aOther.m_polys;
1821 
1822  // reset poly cache:
1823  m_hash = MD5_HASH{};
1824  m_triangulationValid = false;
1825  m_triangulatedPolys.clear();
1826  return *this;
1827 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys

References m_hash, m_polys, m_triangulatedPolys, and m_triangulationValid.

◆ Outline()

◆ OutlineCount()

int SHAPE_POLY_SET::OutlineCount ( ) const
inline

Returns the number of outlines in the set

Definition at line 558 of file shape_poly_set.h.

558 { return m_polys.size(); }

References m_polys.

Referenced by POINT_EDITOR::addCorner(), ZONE_FILLER::addHatchFillTypeOnZone(), 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(), D_PAD::CustomShapeAsPolygonToBoardPosition(), KIGFX::GERBVIEW_PAINTER::draw(), DRAWSEGMENT::Draw(), GERBER_DRAW_ITEM::Draw(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawApertureMacro(), APERTURE_MACRO::DrawApertureMacroShape(), ZONE_CONTAINER::DrawFilledArea(), D_CODE::DrawFlashedPolygon(), D_CODE::DrawFlashedShape(), KIGFX::GERBVIEW_PAINTER::drawFlashedShape(), AR_AUTOPLACER::drawPlacementRoutingMatrix(), KIGFX::CAIRO_GAL_BASE::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_padshape(), export_vrml_zones(), fillArcPOLY(), DSN::SPECCTRA_DB::fillBOUNDARY(), 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(), D_PAD::MirrorXPrimitives(), GERBER_DRAW_ITEM::MoveAB(), GERBER_DRAW_ITEM::MoveXY(), NormalizeAreaOutlines(), SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::operator bool(), PlotLayerOutlines(), BRDITEMS_PLOTTER::PlotPad(), DXF_PLOTTER::PlotPoly(), Polygon_Calc_BBox_3DU(), polygonArea(), C3D_RENDER_OGL_LEGACY::reload(), DRC_COURTYARD_OVERLAP::RunDRC(), Subset(), PNS_KICAD_IFACE::syncZone(), AR_AUTOPLACER::testModuleByPolygon(), ZONE_CONTAINER::TransformSolidAreasShapesToPolygonSet(), HYPERLYNX_EXPORTER::writeBoardInfo(), and HYPERLYNX_EXPORTER::writeNetObjects().

◆ Parse()

bool SHAPE_POLY_SET::Parse ( std::stringstream &  aStream)
overridevirtual

Reimplemented from SHAPE.

Definition at line 1103 of file shape_poly_set.cpp.

1104 {
1105  std::string tmp;
1106 
1107  aStream >> tmp;
1108 
1109  if( tmp != "polyset" )
1110  return false;
1111 
1112  aStream >> tmp;
1113 
1114  int n_polys = atoi( tmp.c_str() );
1115 
1116  if( n_polys < 0 )
1117  return false;
1118 
1119  for( int i = 0; i < n_polys; i++ )
1120  {
1121  POLYGON paths;
1122 
1123  aStream >> tmp;
1124 
1125  if( tmp != "poly" )
1126  return false;
1127 
1128  aStream >> tmp;
1129  int n_outlines = atoi( tmp.c_str() );
1130 
1131  if( n_outlines < 0 )
1132  return false;
1133 
1134  for( int j = 0; j < n_outlines; j++ )
1135  {
1136  SHAPE_LINE_CHAIN outline;
1137 
1138  outline.SetClosed( true );
1139 
1140  aStream >> tmp;
1141  int n_vertices = atoi( tmp.c_str() );
1142 
1143  for( int v = 0; v < n_vertices; v++ )
1144  {
1145  VECTOR2I p;
1146 
1147  aStream >> tmp; p.x = atoi( tmp.c_str() );
1148  aStream >> tmp; p.y = atoi( tmp.c_str() );
1149  outline.Append( p );
1150  }
1151 
1152  paths.push_back( outline );
1153  }
1154 
1155  m_polys.push_back( paths );
1156  }
1157 
1158  return true;
1159 }
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.
size_t i
Definition: json11.cpp:597

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

◆ pointInPolygon()

bool SHAPE_POLY_SET::pointInPolygon ( const VECTOR2I aP,
const SHAPE_LINE_CHAIN aPath 
) const
private

Definition at line 1462 of file shape_poly_set.cpp.

1463 {
1464  return aPath.PointInside( aP );
1465 }
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0) const
Function PointInside()

References SHAPE_LINE_CHAIN::PointInside().

Referenced by containsSingle().

◆ PointOnEdge()

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 1179 of file shape_poly_set.cpp.

1180 {
1181  // Iterate through all the polygons in the set
1182  for( const POLYGON& polygon : m_polys )
1183  {
1184  // Iterate through all the line chains in the polygon
1185  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1186  {
1187  if( lineChain.PointOnEdge( aP ) )
1188  return true;
1189  }
1190  }
1191 
1192  return false;
1193 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.

References m_polys.

◆ Polygon() [1/2]

◆ Polygon() [2/2]

const POLYGON& SHAPE_POLY_SET::Polygon ( int  aIndex) const
inline

Definition at line 608 of file shape_poly_set.h.

609  {
610  return m_polys[aIndex];
611  }

References m_polys.

◆ RemoveAllContours()

◆ RemoveContour()

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 1249 of file shape_poly_set.cpp.

1250 {
1251  // Default polygon is the last one
1252  if( aPolygonIdx < 0 )
1253  aPolygonIdx += m_polys.size();
1254 
1255  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1256 }

References m_polys.

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

◆ RemoveNullSegments()

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 1259 of file shape_poly_set.cpp.

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

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(), and NormalizeAreaOutlines().

◆ RemoveVertex() [1/2]

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 1418 of file shape_poly_set.cpp.

1419 {
1420  VERTEX_INDEX index;
1421 
1422  // Assure the to be removed vertex exists, abort otherwise
1423  if( GetRelativeIndices( aGlobalIndex, &index ) )
1424  RemoveVertex( index );
1425  else
1426  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1427 }
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.

References GetRelativeIndices().

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

◆ RemoveVertex() [2/2]

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 1430 of file shape_poly_set.cpp.

1431 {
1432  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1433 }

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.

◆ Rotate()

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 1480 of file shape_poly_set.cpp.

1481 {
1482  for( POLYGON& poly : m_polys )
1483  {
1484  for( SHAPE_LINE_CHAIN& path : poly )
1485  {
1486  path.Rotate( aAngle, aCenter );
1487  }
1488  }
1489 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.

References m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), DRC::checkClearanceSegmToPad(), D_CODE::ConvertShapeToPolygon(), export_vrml_polygon(), MODULE::GetBoundingPoly(), TransformOvalClearanceToPolygon(), and TransformRoundChamferedRectToPolygon().

◆ Simplify()

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 1037 of file shape_poly_set.cpp.

1038 {
1040 
1041  booleanOp( ctUnion, empty, aFastMode );
1042 }
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,...
Class SHAPE_POLY_SET.
static bool empty(const wxTextEntryBase *aCtrl)

References booleanOp(), and empty().

Referenced by CINFO3D_VISU::AddShapeWithClearanceToContainer(), D_PAD::buildCustomPadPolygon(), BOARD::CombineAreas(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), CINFO3D_VISU::createLayers(), CreateThermalReliefPadPolygon(), Fracture(), BOARD::GetBoardPolygonOutlines(), InflateWithLinkedHoles(), NormalizeAreaOutlines(), PlotLayerOutlines(), ZONE_CONTAINER::TransformShapeWithClearanceToPolygon(), D_PAD::TransformShapeWithClearanceToPolygon(), Unfracture(), and HYPERLYNX_EXPORTER::writeNetObjects().

◆ Subset()

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 263 of file shape_poly_set.cpp.

264 {
265  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
266 
267  SHAPE_POLY_SET newPolySet;
268 
269  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
270  {
271  newPolySet.m_polys.push_back( Polygon( index ) );
272  }
273 
274  return newPolySet;
275 }
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

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

Referenced by UnitSet().

◆ TotalVertices()

int SHAPE_POLY_SET::TotalVertices ( ) const

Returns total number of vertices stored in the set.

Definition at line 1492 of file shape_poly_set.cpp.

1493 {
1494  int c = 0;
1495 
1496  for( const POLYGON& poly : m_polys )
1497  {
1498  for( const SHAPE_LINE_CHAIN& path : poly )
1499  {
1500  c += path.PointCount();
1501  }
1502  }
1503 
1504  return c;
1505 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.

References m_polys.

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

◆ TriangulatedPolyCount()

unsigned int SHAPE_POLY_SET::TriangulatedPolyCount ( ) const
inline

Returns the number of triangulated polygons

Definition at line 555 of file shape_poly_set.h.

555 { return m_triangulatedPolys.size(); }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys

References m_triangulatedPolys.

Referenced by Convert_shape_line_polygon_to_triangles(), KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), and SHAPE_POLY_SET().

◆ TriangulatedPolygon()

const TRIANGULATED_POLYGON* SHAPE_POLY_SET::TriangulatedPolygon ( int  aIndex) const
inline

Definition at line 613 of file shape_poly_set.h.

614  {
615  return m_triangulatedPolys[aIndex].get();
616  }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys

References m_triangulatedPolys.

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

◆ Type()

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.

84  {
85  return m_type;
86  }
SHAPE_TYPE m_type
type of our shape
Definition: shape.h:166

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

◆ Unfracture()

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 1026 of file shape_poly_set.cpp.

1027 {
1028  for( POLYGON& path : m_polys )
1029  {
1030  unfractureSingle( path );
1031  }
1032 
1033  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1034 }
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...

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

◆ unfractureSingle()

void SHAPE_POLY_SET::unfractureSingle ( SHAPE_POLY_SET::POLYGON aPoly)
private

Definition at line 850 of file shape_poly_set.cpp.

851 {
852  assert( aPoly.size() == 1 );
853 
854  struct EDGE
855  {
856  int m_index = 0;
857  SHAPE_LINE_CHAIN* m_poly = nullptr;
858  bool m_duplicate = false;
859 
860  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
861  m_index( aIndex ),
862  m_poly( aPolygon )
863  {}
864 
865  bool compareSegs( const SEG& s1, const SEG& s2 ) const
866  {
867  return (s1.A == s2.B && s1.B == s2.A);
868  }
869 
870  bool operator==( const EDGE& aOther ) const
871  {
872  return compareSegs( m_poly->CSegment( m_index ),
873  aOther.m_poly->CSegment( aOther.m_index ) );
874  }
875 
876  bool operator!=( const EDGE& aOther ) const
877  {
878  return !compareSegs( m_poly->CSegment( m_index ),
879  aOther.m_poly->CSegment( aOther.m_index ) );
880  }
881 
882  struct HASH
883  {
884  std::size_t operator()( const EDGE& aEdge ) const
885  {
886  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
887 
888  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
889  }
890  };
891  };
892 
893  struct EDGE_LIST_ENTRY
894  {
895  int index;
896  EDGE_LIST_ENTRY* next;
897  };
898 
899  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
900 
901  auto lc = aPoly[0];
902  lc.Simplify();
903 
904  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
905 
906  for( int i = 0; i < lc.SegmentCount(); i++ )
907  {
908  edgeList[i].index = i;
909  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
910  }
911 
912  std::unordered_set<EDGE_LIST_ENTRY*> queue;
913 
914  for( int i = 0; i < lc.SegmentCount(); i++ )
915  {
916  EDGE e( &lc, i );
917  uniqueEdges.insert( e );
918  }
919 
920  for( int i = 0; i < lc.SegmentCount(); i++ )
921  {
922  EDGE e( &lc, i );
923  auto it = uniqueEdges.find( e );
924 
925  if( it != uniqueEdges.end() && it->m_index != i )
926  {
927  int e1 = it->m_index;
928  int e2 = i;
929 
930  if( e1 > e2 )
931  std::swap( e1, e2 );
932 
933  int e1_prev = e1 - 1;
934 
935  if( e1_prev < 0 )
936  e1_prev = lc.SegmentCount() - 1;
937 
938  int e2_prev = e2 - 1;
939 
940  if( e2_prev < 0 )
941  e2_prev = lc.SegmentCount() - 1;
942 
943  int e1_next = e1 + 1;
944 
945  if( e1_next == lc.SegmentCount() )
946  e1_next = 0;
947 
948  int e2_next = e2 + 1;
949 
950  if( e2_next == lc.SegmentCount() )
951  e2_next = 0;
952 
953  edgeList[e1_prev].next = &edgeList[ e2_next ];
954  edgeList[e2_prev].next = &edgeList[ e1_next ];
955  edgeList[i].next = nullptr;
956  edgeList[it->m_index].next = nullptr;
957  }
958  }
959 
960  for( int i = 0; i < lc.SegmentCount(); i++ )
961  {
962  if( edgeList[i].next )
963  queue.insert( &edgeList[i] );
964  }
965 
966  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
967 
968  int n = 0;
969  int outline = -1;
970 
971  POLYGON result;
972 
973  while( queue.size() )
974  {
975  auto e_first = (*queue.begin() );
976  auto e = e_first;
977  int cnt = 0;
978 
979  do {
980  edgeBuf[cnt++] = e;
981  e = e->next;
982  } while( e && e != e_first );
983 
984  SHAPE_LINE_CHAIN outl;
985 
986  for( int i = 0; i < cnt; i++ )
987  {
988  auto p = lc.CPoint( edgeBuf[i]->index );
989  outl.Append( p );
990  queue.erase( edgeBuf[i] );
991  }
992 
993  outl.SetClosed( true );
994 
995  bool cw = outl.Area() > 0.0;
996 
997  if( cw )
998  outline = n;
999 
1000  result.push_back( outl );
1001  n++;
1002  }
1003 
1004  if( outline > 0 )
1005  std::swap( result[0], result[outline] );
1006 
1007  aPoly = result;
1008 }
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 VECTOR2I & CPoint(int aIndex) const
Function CPoint()
void SetClosed(bool aClosed)
Function SetClosed()
double Area() const
Definition: seg.h:36
const SEG CSegment(int aIndex) const
Function CSegment()
Class SHAPE_LINE_CHAIN.
size_t i
Definition: json11.cpp:597
VECTOR2I A
Definition: seg.h:44
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
VECTOR2I B
Definition: seg.h:45

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

Referenced by Unfracture().

◆ UnitSet()

SHAPE_POLY_SET SHAPE_POLY_SET::UnitSet ( int  aPolygonIndex)
inline

Definition at line 591 of file shape_poly_set.h.

592  {
593  return Subset( aPolygonIndex, aPolygonIndex + 1 );
594  }
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...

References Subset().

Referenced by BOARD::NormalizeAreaPolygon().

◆ Vertex() [1/3]

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 278 of file shape_poly_set.cpp.

279 {
280  if( aOutline < 0 )
281  aOutline += m_polys.size();
282 
283  int idx;
284 
285  if( aHole < 0 )
286  idx = 0;
287  else
288  idx = aHole + 1;
289 
290  assert( aOutline < (int) m_polys.size() );
291  assert( idx < (int) m_polys[aOutline].size() );
292 
293  return m_polys[aOutline][idx].Point( aIndex );
294 }

References m_polys.

Referenced by Abort_Zone_Move_Corner_Or_Outlines(), POINT_EDITOR::addCorner(), 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(), DRC_COURTYARD_OVERLAP::RunDRC(), ZONE_CONTAINER::SetCornerPosition(), Show_Zone_Corner_Or_Outline_While_Move_Mouse(), PCB_EDIT_FRAME::Start_Move_Zone_Corner(), POINT_EDITOR::updateItem(), and Vertex().

◆ Vertex() [2/3]

VECTOR2I & SHAPE_POLY_SET::Vertex ( int  aGlobalIndex)

Returns the aGlobalIndex-th vertex in the poly set

Definition at line 316 of file shape_poly_set.cpp.

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

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.

◆ Vertex() [3/3]

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 340 of file shape_poly_set.cpp.

341 {
342  return Vertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
343 }
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline

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

◆ vertex()

VECTOR2I& SHAPE_POLY_SET::vertex ( int  aCornerId)
private

◆ VertexCount()

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 238 of file shape_poly_set.cpp.

239 {
240  if( m_polys.size() == 0 ) // Empty poly set
241  return 0;
242 
243  if( aOutline < 0 ) // Use last outline
244  aOutline += m_polys.size();
245 
246  int idx;
247 
248  if( aHole < 0 )
249  idx = 0;
250  else
251  idx = aHole + 1;
252 
253  if( aOutline >= (int) m_polys.size() ) // not existing outline
254  return 0;
255 
256  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
257  return 0;
258 
259  return m_polys[aOutline][idx].PointCount();
260 }

References m_polys.

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

Member Data Documentation

◆ m_hash

MD5_HASH SHAPE_POLY_SET::m_hash
private

◆ m_polys

◆ m_triangulatedPolys

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

◆ m_triangulationValid

bool SHAPE_POLY_SET::m_triangulationValid = false
private

◆ m_type

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: