KiCad PCB EDA Suite
SHAPE_POLY_SET Class Reference

Represent a set of closed polygons. More...

#include <shape_poly_set.h>

Inheritance diagram for SHAPE_POLY_SET:
SHAPE SHAPE_BASE

Classes

class  ITERATOR_TEMPLATE
 Base class for iterating over all vertices in a given SHAPE_POLY_SET. More...
 
class  SEGMENT_ITERATOR_TEMPLATE
 Base class for iterating over all segments in a given SHAPE_POLY_SET. More...
 
class  TRIANGULATED_POLYGON
 
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. 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 (theoretically) a strictly simple polygon, but calculations can be really significantly time consuming Most of time PM_FAST is preferable. More...
 
enum  CORNER_STRATEGY {
  ALLOW_ACUTE_CORNERS, CHAMFER_ACUTE_CORNERS, ROUND_ACUTE_CORNERS, CHAMFER_ALL_CORNERS,
  ROUND_ALL_CORNERS
}
 < define how inflate transform build inflated polygon More...
 
typedef std::vector< SHAPE_LINE_CHAINPOLYGON
 < represents a single polygon outline with holes. 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 BOX2D &aRect)
 
 SHAPE_POLY_SET (const SHAPE_LINE_CHAIN &aOutline)
 Construct a SHAPE_POLY_SET with the first outline given by aOutline. More...
 
 SHAPE_POLY_SET (const SHAPE_POLY_SET &aOther)
 Copy constructor SHAPE_POLY_SET Performs a deep copy of aOther into this. More...
 
 ~SHAPE_POLY_SET ()
 
SHAPE_POLY_SEToperator= (const SHAPE_POLY_SET &aOther)
 
void CacheTriangulation (bool aPartition=true)
 Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations. More...
 
bool IsTriangulationUpToDate () const
 
MD5_HASH GetHash () const
 
virtual bool HasIndexableSubshapes () const override
 
virtual size_t GetIndexableSubshapeCount () const override
 
virtual void GetIndexableSubshapes (std::vector< SHAPE * > &aSubshapes) override
 
bool GetRelativeIndices (int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
 Convert 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. More...
 
bool GetGlobalIndex (VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
 Compute the global index of a vertex from the relative indices of polygon, contour and vertex. More...
 
SHAPEClone () const override
 Return a dynamically allocated copy of the shape. More...
 
int NewOutline ()
 Creates a new hole in a given outline. More...
 
int NewHole (int aOutline=-1)
 Adds a new outline to the set and returns its index. More...
 
int AddOutline (const SHAPE_LINE_CHAIN &aOutline)
 Adds a new hole to the given outline (default: last) and returns its index. More...
 
int AddHole (const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
 Return the area of this poly set. More...
 
double Area ()
 Count the number of arc shapes present. More...
 
int ArcCount () const
 Appends all the arcs in this polyset to aArcBuffer. More...
 
void GetArcs (std::vector< SHAPE_ARC > &aArcBuffer) const
 Removes all arc references from all the outlines and holes in the polyset. More...
 
void ClearArcs ()
 Appends a vertex at the end of the given outline/hole (default: the last outline) More...
 
int Append (int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
 Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last polygon). More...
 
void Append (const SHAPE_POLY_SET &aSet)
 Append a vertex at the end of the given outline/hole (default: the last outline) More...
 
void Append (const VECTOR2I &aP, int aOutline=-1, int aHole=-1)
 
int Append (SHAPE_ARC &aArc, int aOutline=-1, int aHole=-1)
 Append a new arc to the contour indexed by aOutline and aHole (defaults to the outline of the last polygon). More...
 
void InsertVertex (int aGlobalIndex, const VECTOR2I &aNewVertex)
 Adds a vertex in the globally indexed position aGlobalIndex. More...
 
const VECTOR2ICVertex (int aIndex, int aOutline, int aHole) const
 Return the aGlobalIndex-th vertex in the poly set. More...
 
const VECTOR2ICVertex (int aGlobalIndex) const
 Return the index-th vertex in a given hole outline within a given outline. More...
 
const VECTOR2ICVertex (VERTEX_INDEX aIndex) const
 
bool GetNeighbourIndexes (int aGlobalIndex, int *aPrevious, int *aNext)
 Return 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) const
 Check whether the aPolygonIndex-th polygon in the set is self intersecting. More...
 
bool IsSelfIntersecting () const
 Check whether any of the polygons in the set is self intersecting. More...
 
unsigned int TriangulatedPolyCount () const
 Return the number of outlines in the set. More...
 
int OutlineCount () const
 Return the number of vertices in a given outline/hole. More...
 
int VertexCount (int aOutline=-1, int aHole=-1) const
 Return the number of points in the shape poly set. More...
 
int FullPointCount () const
 Returns the number of holes in a given outline. More...
 
int HoleCount (int aOutline) const
 Return the reference to aIndex-th outline in the set. More...
 
SHAPE_LINE_CHAINOutline (int aIndex)
 
const SHAPE_LINE_CHAINOutline (int aIndex) const
 
SHAPE_POLY_SET Subset (int aFirstPolygon, int aLastPolygon)
 Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon. More...
 
SHAPE_POLY_SET UnitSet (int aPolygonIndex)
 Return the reference to aHole-th hole in the aIndex-th outline. More...
 
SHAPE_LINE_CHAINHole (int aOutline, int aHole)
 Return the aIndex-th subpolygon in the set. More...
 
POLYGONPolygon (int aIndex)
 
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)
 Return an object to iterate through the points of the polygons between aFirst and aLast. More...
 
ITERATOR Iterate (int aOutline)
 
ITERATOR IterateWithHoles (int aOutline)
 
ITERATOR Iterate ()
 
ITERATOR IterateWithHoles ()
 
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)
 Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (default: without) More...
 
SEGMENT_ITERATOR IterateSegments (int aFirst, int aLast, bool aIterateHoles=false)
 Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (default: without) More...
 
CONST_SEGMENT_ITERATOR CIterateSegments (int aFirst, int aLast, bool aIterateHoles=false) const
 Return an iterator object, for iterating aPolygonIdx-th polygon edges. More...
 
SEGMENT_ITERATOR IterateSegments (int aPolygonIdx)
 Return an iterator object, for iterating aPolygonIdx-th polygon edges. More...
 
CONST_SEGMENT_ITERATOR CIterateSegments (int aPolygonIdx) const
 Return an iterator object, for all outlines in the set (no holes). More...
 
SEGMENT_ITERATOR IterateSegments ()
 Returns an iterator object, for all outlines in the set (no holes) More...
 
CONST_SEGMENT_ITERATOR CIterateSegments () const
 Returns an iterator object, for all outlines in the set (with holes) More...
 
SEGMENT_ITERATOR IterateSegmentsWithHoles ()
 Return an iterator object, for the aOutline-th outline in the set (with holes). More...
 
SEGMENT_ITERATOR IterateSegmentsWithHoles (int aOutline)
 Return an iterator object, for the aOutline-th outline in the set (with holes). More...
 
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles () const
 Return an iterator object, for the aOutline-th outline in the set (with holes). More...
 
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles (int aOutline) const
 
void BooleanAdd (const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
 Perform boolean polyset difference For aFastMode meaning, see function booleanOp. More...
 
void BooleanSubtract (const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
 Perform boolean polyset intersection For aFastMode meaning, see function booleanOp. More...
 
void BooleanIntersection (const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
 Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning, see function booleanOp. More...
 
void BooleanAdd (const SHAPE_POLY_SET &a, const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
 Perform boolean polyset difference 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)
 Perform boolean polyset intersection 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)
 
void Inflate (int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
 Perform outline inflation/deflation. More...
 
void Deflate (int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
 
void InflateWithLinkedHoles (int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
 Perform outline inflation/deflation, using round corners. More...
 
void Fracture (POLYGON_MODE aFastMode)
 Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes. More...
 
void Unfracture (POLYGON_MODE aFastMode)
 Return true if the polygon set has any holes. More...
 
bool HasHoles () const
 Return true if the polygon set has any holes that share a vertex. More...
 
bool HasTouchingHoles () const
 Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMode meaning, see function booleanOp. More...
 
void Simplify (POLYGON_MODE aFastMode)
 
int NormalizeAreaOutlines ()
 Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s). More...
 
const std::string Format () const override
 
bool Parse (std::stringstream &aStream) override
 
void Move (const VECTOR2I &aVector) override
 
void Mirror (bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
 Mirror the line points about y or x (or both) More...
 
void Rotate (double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
 Rotate all vertices by a given angle. More...
 
bool IsSolid () const override
 
const BOX2I BBox (int aClearance=0) const override
 Compute a bounding box of the shape, with a margin of aClearance a collision. More...
 
bool PointOnEdge (const VECTOR2I &aP) const
 Check if point aP lies on an edge or vertex of some of the outlines or holes. More...
 
bool Collide (const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Check if the boundary of shape (this) lies closer to the shape aShape than aClearance, indicating a collision. More...
 
bool Collide (const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Check whether the point aP is either inside or on the edge of the polygon set. More...
 
bool Collide (const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Check whether the segment aSeg collides with the polygon set (or its edge). More...
 
bool CollideVertex (const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
 Check 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) const
 Check whether aPoint collides with any edge of any of the contours of the polygon. More...
 
void BuildBBoxCaches () const
 Construct BBoxCaches for Contains(), below. More...
 
const BOX2I BBoxFromCaches () const
 
bool Contains (const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
 Return true if a given subpolygon contains the point aP. More...
 
bool IsEmpty () const
 
void RemoveVertex (int aGlobalIndex)
 Delete the aGlobalIndex-th vertex. More...
 
void RemoveVertex (VERTEX_INDEX aRelativeIndices)
 Delete the vertex indexed by aRelativeIndex (index of polygon, contour and vertex). More...
 
void RemoveAllContours ()
 
void RemoveContour (int aContourIdx, int aPolygonIdx=-1)
 Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set. More...
 
int RemoveNullSegments ()
 Look for null segments; ie, segments whose ends are exactly the same and deletes them. More...
 
void SetVertex (const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
 Accessor function to set the position of a specific point. More...
 
void SetVertex (int aGlobalIndex, const VECTOR2I &aPos)
 Set the vertex based on the global index. More...
 
int TotalVertices () const
 Delete aIdx-th polygon from the set. More...
 
void DeletePolygon (int aIdx)
 
POLYGON ChamferPolygon (unsigned int aDistance, int aIndex)
 Return a chamfered version of the aIndex-th polygon. More...
 
POLYGON FilletPolygon (unsigned int aRadius, int aErrorMax, int aIndex)
 Return a filleted version of the aIndex-th polygon. More...
 
SHAPE_POLY_SET Chamfer (int aDistance)
 Return a chamfered version of the polygon set. More...
 
SHAPE_POLY_SET Fillet (int aRadius, int aErrorMax)
 Return a filleted version of the polygon set. More...
 
SEG::ecoord SquaredDistanceToPolygon (VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
 Compute the minimum distance between the aIndex-th polygon and aPoint. More...
 
SEG::ecoord SquaredDistanceToPolygon (const SEG &aSegment, int aIndex, VECTOR2I *aNearest) const
 Compute the minimum distance between the aIndex-th polygon and aSegment with a possible width. More...
 
SEG::ecoord SquaredDistance (VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
 Compute the minimum distance squared between aPoint and all the polygons in the set. More...
 
SEG::ecoord SquaredDistance (const SEG &aSegment, VECTOR2I *aNearest=nullptr) const
 Compute the minimum distance squared between aSegment and all the polygons in the set. More...
 
bool IsVertexInHole (int aGlobalIdx)
 Check whether the aGlobalIndex-th vertex belongs to a hole. More...
 
bool IsNull () const
 Return true if the shape is a null shape. More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const
 Check if the boundary of shape (this) lies closer to the shape aShape than aClearance, indicating a collision. More...
 
virtual VECTOR2I Centre () const
 Compute a center-of-mass of the shape. More...
 
FACETNewFacet ()
 
SGNODECalcShape (SGNODE *aParent, SGNODE *aColor, WRL1_ORDER aVertexOrder, float aCreaseLimit=0.74317, bool isVRML2=false)
 
SHAPE_TYPE Type () const
 Return the type of the shape. More...
 

Static Public Member Functions

static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths (const std::vector< SHAPE_LINE_CHAIN > &aPaths, bool aReverseOrientation=false, bool aEvenOdd=false)
 Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order. More...
 

Static Public Attributes

static const int MIN_PRECISION_IU = 4
 This is the minimum precision for all the points in a shape. 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 }
 Operation 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

void fractureSingle (POLYGON &paths)
 
void unfractureSingle (POLYGON &path)
 
void importTree (ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
 
void booleanOp (ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
 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 containsSingle (const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
 Check 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)
 Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode selected. More...
 
bool hasTouchingHoles (const POLYGON &aPoly) const
 
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

Represent 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 64 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 236 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 70 of file shape_poly_set.h.

◆ POLYSET

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

Definition at line 1448 of file shape_poly_set.h.

◆ SEGMENT_ITERATOR

Member Enumeration Documentation

◆ CORNER_MODE

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

◆ CORNER_STRATEGY

< define how inflate transform build inflated polygon

Enumerator
ALLOW_ACUTE_CORNERS 

just inflate the polygon. Acute angles create spikes

CHAMFER_ACUTE_CORNERS 

Acute angles are chamfered.

ROUND_ACUTE_CORNERS 

Acute angles are rounded.

CHAMFER_ALL_CORNERS 

All angles are chamfered.

The distance between new and old polygon edges is not constant, but do not change a lot

ROUND_ALL_CORNERS 

All angles are rounded.

The distance between new and old polygon edges is constant

Definition at line 980 of file shape_poly_set.h.

981  {
989  };
All angles are chamfered.
Acute angles are rounded.
Acute angles are chamfered.
just inflate the polygon. Acute angles create spikes

◆ 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 (theoretically) 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 947 of file shape_poly_set.h.

Constructor & Destructor Documentation

◆ SHAPE_POLY_SET() [1/4]

SHAPE_POLY_SET::SHAPE_POLY_SET ( )

Definition at line 62 of file shape_poly_set.cpp.

62  :
64 {
65 }
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition: shape.h:127
set of polygons (with holes, etc.)
Definition: shape.h:48

Referenced by Clone().

◆ SHAPE_POLY_SET() [2/4]

SHAPE_POLY_SET::SHAPE_POLY_SET ( const BOX2D aRect)

Definition at line 68 of file shape_poly_set.cpp.

68  :
70 {
71  NewOutline();
72  Append( VECTOR2I( aRect.GetLeft(), aRect.GetTop() ) );
73  Append( VECTOR2I( aRect.GetRight(), aRect.GetTop() ) );
74  Append( VECTOR2I( aRect.GetRight(), aRect.GetBottom() ) );
75  Append( VECTOR2I( aRect.GetLeft(), aRect.GetBottom() ) );
76  Outline( 0 ).SetClosed( true );
77 }
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition: shape.h:127
coord_type GetTop() const
Definition: box2.h:187
coord_type GetRight() const
Definition: box2.h:182
coord_type GetBottom() const
Definition: box2.h:183
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
SHAPE_LINE_CHAIN & Outline(int aIndex)
int NewOutline()
Creates a new hole in a given outline.
set of polygons (with holes, etc.)
Definition: shape.h:48
coord_type GetLeft() const
Definition: box2.h:186
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...

References Append(), BOX2< Vec >::GetBottom(), BOX2< Vec >::GetLeft(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetTop(), NewOutline(), Outline(), and SHAPE_LINE_CHAIN::SetClosed().

◆ SHAPE_POLY_SET() [3/4]

SHAPE_POLY_SET::SHAPE_POLY_SET ( const SHAPE_LINE_CHAIN aOutline)

Construct a SHAPE_POLY_SET with the first outline given by aOutline.

Parameters
aOutlineis a closed outline

Definition at line 80 of file shape_poly_set.cpp.

80  :
82 {
83  AddOutline( aOutline );
84 }
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition: shape.h:127
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
set of polygons (with holes, etc.)
Definition: shape.h:48

References AddOutline().

◆ SHAPE_POLY_SET() [4/4]

SHAPE_POLY_SET::SHAPE_POLY_SET ( const SHAPE_POLY_SET aOther)

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

Parameters
aOtheris the SHAPE_POLY_SET object that will be copied.

Definition at line 87 of file shape_poly_set.cpp.

87  :
88  SHAPE( aOther ),
89  m_polys( aOther.m_polys )
90 {
91  if( aOther.IsTriangulationUpToDate() )
92  {
93  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
94  {
95  const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
96  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
97  }
98 
99  m_hash = aOther.GetHash();
100  m_triangulationValid = true;
101  }
102  else
103  {
104  m_triangulationValid = false;
105  m_hash = MD5_HASH();
106  m_triangulatedPolys.clear();
107  }
108 }
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition: shape.h:127
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool IsTriangulationUpToDate() const
MD5_HASH GetHash() const
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const

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

◆ ~SHAPE_POLY_SET()

SHAPE_POLY_SET::~SHAPE_POLY_SET ( )

Definition at line 111 of file shape_poly_set.cpp.

112 {
113 }

Member Function Documentation

◆ AddHole()

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

Return the area of this poly set.

Definition at line 494 of file shape_poly_set.cpp.

495 {
496  assert( m_polys.size() );
497 
498  if( aOutline < 0 )
499  aOutline += m_polys.size();
500 
501  assert( aOutline < (int)m_polys.size() );
502 
503  POLYGON& poly = m_polys[aOutline];
504 
505  assert( poly.size() );
506 
507  poly.push_back( aHole );
508 
509  return poly.size() - 2;
510 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.

References m_polys.

Referenced by ZONE::AddPolygon(), BuildFootprintPolygonOutlines(), KI_TEST::BuildHollowSquare(), KI_TEST::CommonTestData::CommonTestData(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), FABMASTER::loadFootprints(), FABMASTER::loadShapePolySet(), FABMASTER::loadZone(), and ALTIUM_PCB::ParseRegions6Data().

◆ AddOutline()

int SHAPE_POLY_SET::AddOutline ( const SHAPE_LINE_CHAIN aOutline)

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

Definition at line 480 of file shape_poly_set.cpp.

481 {
482  assert( aOutline.IsClosed() );
483 
484  POLYGON poly;
485 
486  poly.push_back( aOutline );
487 
488  m_polys.push_back( poly );
489 
490  return m_polys.size() - 1;
491 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
bool IsClosed() const override

References SHAPE_LINE_CHAIN::IsClosed(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE::AddPolygon(), BOOST_AUTO_TEST_CASE(), buildBoardBoundingBoxPoly(), KI_TEST::BuildHollowSquare(), KI_TEST::BuildPolyset(), KI_TEST::CommonTestData::CommonTestData(), ZONE_FILLER::computeRawFilledArea(), ConvertPolygonToBlocks(), FOOTPRINT::CoverageRatio(), CONVERT_TOOL::CreateLines(), BOARD_ADAPTER::createPadWithClearance(), KIGFX::GERBVIEW_PAINTER::draw(), GEOM_TEST::FilletPolySet(), FOOTPRINT::GetBoundingHull(), PNS::SOLID::HoleHull(), PNS::SOLID::Hull(), IteratorFixture::IteratorFixture(), DSN::SPECCTRA_DB::makeIMAGE(), CONVERT_TOOL::makePolysFromCircles(), CONVERT_TOOL::makePolysFromRects(), CONVERT_TOOL::makePolysFromSegs(), PAD::MergePrimitivesAsPolygon(), NormalizeAreaOutlines(), EAGLE_PLUGIN::packagePolygon(), ALTIUM_PCB::ParsePolygons6Data(), ALTIUM_PCB::ParseRegions6Data(), ALTIUM_PCB::ParseShapeBasedRegions6Data(), partitionPolyIntoRegularCellGrid(), ZONE_CREATE_HELPER::performZoneCutout(), PGPartitionFixture::PGPartitionFixture(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), PlotStandardLayer(), SHAPE_POLY_SET(), TestConcaveSquareFillet(), and TestSquareFillet().

◆ Append() [1/4]

int SHAPE_POLY_SET::Append ( int  x,
int  y,
int  aOutline = -1,
int  aHole = -1,
bool  aAllowDuplication = false 
)

Add 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
the number of corners of the selected contour after the addition.Merge polygons from two sets.

Definition at line 230 of file shape_poly_set.cpp.

231 {
232  assert( m_polys.size() );
233 
234  if( aOutline < 0 )
235  aOutline += m_polys.size();
236 
237  int idx;
238 
239  if( aHole < 0 )
240  idx = 0;
241  else
242  idx = aHole + 1;
243 
244  assert( aOutline < (int) m_polys.size() );
245  assert( idx < (int) m_polys[aOutline].size() );
246 
247  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
248 
249  return m_polys[aOutline][idx].PointCount();
250 }

References m_polys.

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), ZONE_FILLER::addKnockout(), AR_AUTOPLACER::addPad(), PAD::AddPrimitivePoly(), Append(), ZONE::AppendCorner(), BuildBoardPolygonOutlines(), ZONE_FILLER::buildCopperItemClearances(), BuildFootprintPolygonOutlines(), ConvertOutlineToPolygon(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CornerListToPolygon(), BITMAPCONV_INFO::createOutputData(), BOARD_ADAPTER::createPadWithClearance(), CONVERT_TOOL::CreatePolys(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), CONVERT_TOOL::extractPolygons(), fillArcPOLY(), PCB_BASE_FRAME::FocusOnItems(), FOOTPRINT::GetBoundingHull(), getRectangleAlongCentreLine(), EDA_SHAPE::hitTest(), InsertVertex(), FABMASTER::loadFootprints(), EAGLE_PLUGIN::loadPolygon(), FABMASTER::loadShapePolySet(), FABMASTER::loadZone(), LEGACY_PLUGIN::loadZONE_CONTAINER(), DSN::SPECCTRA_DB::makeIMAGE(), DXF_PLOTTER::PlotPoly(), PlotStandardLayer(), RENDER_3D_OPENGL::reload(), EDA_SHAPE::rotate(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), EDA_SHAPE::SetPolyPoints(), SHAPE_POLY_SET(), DS_DATA_ITEM_POLYGONS::SyncDrawItems(), TransformArcToPolygon(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRingToPolygon(), TransformRoundChamferedRectToPolygon(), FP_TEXT::TransformShapeWithClearanceToPolygon(), EDA_SHAPE::TransformShapeWithClearanceToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), ZONE::TransformSmoothedOutlineToPolygon(), ZONE::TransformSolidAreasShapesToPolygon(), TransformTrapezoidToPolygon(), PCB_DIM_ALIGNED::updateGeometry(), PCB_DIM_ORTHOGONAL::updateGeometry(), PCB_DIM_LEADER::updateGeometry(), and EE_POINT_EDITOR::updateParentItem().

◆ Append() [2/4]

void SHAPE_POLY_SET::Append ( const SHAPE_POLY_SET aSet)

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

Definition at line 1642 of file shape_poly_set.cpp.

1643 {
1644  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1645 }

References m_polys.

◆ Append() [3/4]

void SHAPE_POLY_SET::Append ( const VECTOR2I aP,
int  aOutline = -1,
int  aHole = -1 
)

Definition at line 1648 of file shape_poly_set.cpp.

1649 {
1650  Append( aP.x, aP.y, aOutline, aHole );
1651 }
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...

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

◆ Append() [4/4]

int SHAPE_POLY_SET::Append ( SHAPE_ARC aArc,
int  aOutline = -1,
int  aHole = -1 
)

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

Parameters
aArcThe arc to be inserted
aOutlineIndex of the polygon
aHoleIndex of the hole (-1 for the main outline)
Returns
the number of points in the arc (including the interpolated points from the arc)

Definition at line 253 of file shape_poly_set.cpp.

254 {
255  assert( m_polys.size() );
256 
257  if( aOutline < 0 )
258  aOutline += m_polys.size();
259 
260  int idx;
261 
262  if( aHole < 0 )
263  idx = 0;
264  else
265  idx = aHole + 1;
266 
267  assert( aOutline < (int) m_polys.size() );
268  assert( idx < (int) m_polys[aOutline].size() );
269 
270  m_polys[aOutline][idx].Append( aArc );
271 
272  return m_polys[aOutline][idx].PointCount();
273 }

References m_polys.

◆ ArcCount()

int SHAPE_POLY_SET::ArcCount ( ) const

Appends all the arcs in this polyset to aArcBuffer.

Definition at line 529 of file shape_poly_set.cpp.

530 {
531  int retval = 0;
532 
533  for( const POLYGON& poly : m_polys )
534  {
535  for( size_t i = 0; i < poly.size(); i++ )
536  retval += poly[i].ArcCount();
537  }
538 
539  return retval;
540 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.

References m_polys.

Referenced by booleanOp().

◆ Area()

double SHAPE_POLY_SET::Area ( )

Count the number of arc shapes present.

Definition at line 513 of file shape_poly_set.cpp.

514 {
515  double area = 0.0;
516 
517  for( int i = 0; i < OutlineCount(); i++ )
518  {
519  area += Outline( i ).Area();
520 
521  for( int j = 0; j < HoleCount( i ); j++ )
522  area -= Hole( i, j ).Area();
523  }
524 
525  return area;
526 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
double Area(bool aAbsolute=true) const
Return the area of this chain.
SHAPE_LINE_CHAIN & Outline(int aIndex)
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.

References SHAPE_LINE_CHAIN::Area(), Hole(), HoleCount(), Outline(), and OutlineCount().

Referenced by BOOST_AUTO_TEST_CASE(), CADSTAR_PCB_ARCHIVE_LOADER::calculateZonePriorities(), and polygonArea().

◆ BBox()

const BOX2I SHAPE_POLY_SET::BBox ( int  aClearance = 0) const
overridevirtual

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

1390 {
1391  BOX2I bb;
1392 
1393  for( unsigned i = 0; i < m_polys.size(); i++ )
1394  {
1395  if( i == 0 )
1396  bb = m_polys[i][0].BBox();
1397  else
1398  bb.Merge( m_polys[i][0].BBox() );
1399  }
1400 
1401  bb.Inflate( aClearance );
1402  return bb;
1403 }
A 2D bounding box built on top of an origin point and size vector.
Definition: box2.h:41
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:281
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.

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

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), DRAWING_TOOL::DrawBoardCharacteristics(), PCB_BASE_FRAME::FocusOnItems(), APERTURE_MACRO::GetApertureMacroShape(), PAD::GetBestAnchorPosition(), ZONE::GetBoundingBox(), DS_DRAW_ITEM_POLYPOLYGONS::GetBoundingBox(), GERBER_DRAW_ITEM::GetBoundingBox(), DIALOG_PAD_PROPERTIES::padValuesOK(), partitionPolyIntoRegularCellGrid(), BOARD::TestZoneIntersection(), KIGFX::PREVIEW::POLYGON_ITEM::ViewBBox(), and KIGFX::PREVIEW::CENTRELINE_RECT_ITEM::ViewBBox().

◆ BBoxFromCaches()

const BOX2I SHAPE_POLY_SET::BBoxFromCaches ( ) const

Definition at line 1406 of file shape_poly_set.cpp.

1407 {
1408  BOX2I bb;
1409 
1410  for( unsigned i = 0; i < m_polys.size(); i++ )
1411  {
1412  if( i == 0 )
1413  bb = *m_polys[i][0].GetCachedBBox();
1414  else
1415  bb.Merge( *m_polys[i][0].GetCachedBBox() );
1416  }
1417 
1418  return bb;
1419 }
A 2D bounding box built on top of an origin point and size vector.
Definition: box2.h:41
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363

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

Referenced by DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances().

◆ BooleanAdd() [1/2]

void SHAPE_POLY_SET::BooleanAdd ( const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

Perform boolean polyset difference For aFastMode meaning, see function booleanOp.

Definition at line 678 of file shape_poly_set.cpp.

679 {
680  booleanOp( ClipperLib::ctUnion, b, aFastMode );
681 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
This is the engine to execute all polygon boolean transforms (AND, OR, ...

References booleanOp().

Referenced by PAD::addPadPrimitivesToPolygon(), BOOST_AUTO_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), ZONE::BuildSmoothedPoly(), CADSTAR_PCB_ARCHIVE_LOADER::loadCoppers(), ALTIUM_PCB::ParseRegions6Data(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), and ZONE::RemoveCutout().

◆ BooleanAdd() [2/2]

void SHAPE_POLY_SET::BooleanAdd ( const SHAPE_POLY_SET a,
const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

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

Definition at line 696 of file shape_poly_set.cpp.

698 {
699  booleanOp( ClipperLib::ctUnion, a, b, aFastMode );
700 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
This is the engine to execute all polygon boolean transforms (AND, OR, ...

References booleanOp().

◆ BooleanIntersection() [1/2]

void SHAPE_POLY_SET::BooleanIntersection ( const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

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

Definition at line 690 of file shape_poly_set.cpp.

691 {
692  booleanOp( ClipperLib::ctIntersection, b, aFastMode );
693 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
This is the engine to execute all polygon boolean transforms (AND, OR, ...

References booleanOp().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), BOOST_AUTO_TEST_CASE(), ZONE::BuildSmoothedPoly(), ZONE_FILLER::computeRawFilledArea(), ConvertPolygonToBlocks(), PCB_BASE_FRAME::FocusOnItems(), isCopperOutside(), PAD_TOOL::recombinePad(), RENDER_3D_OPENGL::reload(), and TransformOvalToPolygon().

◆ BooleanIntersection() [2/2]

void SHAPE_POLY_SET::BooleanIntersection ( const SHAPE_POLY_SET a,
const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

Definition at line 710 of file shape_poly_set.cpp.

712 {
713  booleanOp( ClipperLib::ctIntersection, a, b, aFastMode );
714 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
This is the engine to execute all polygon boolean transforms (AND, OR, ...

References booleanOp().

◆ booleanOp() [1/2]

void SHAPE_POLY_SET::booleanOp ( ClipperLib::ClipType  aType,
const SHAPE_POLY_SET aOtherShape,
POLYGON_MODE  aFastMode 
)
private

This is the engine to execute all polygon boolean transforms (AND, OR, ...

and polygon simplification (merging overlapping 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 strictly simple polygon. if aFastMode is PM_FAST the result can be a weak polygon if aFastMode is PM_STRICTLY_SIMPLE (default) the result is (theoretically) a strictly simple polygon, but calculations can be really significantly time consuming

Definition at line 566 of file shape_poly_set.cpp.

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

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

575 {
576  if( ( aShape.OutlineCount() > 1 || aOtherShape.OutlineCount() > 0 )
577  && ( aShape.ArcCount() > 0 || aOtherShape.ArcCount() > 0 ) )
578  {
579  wxFAIL_MSG( wxT( "Boolean ops on curved polygons are not supported. You should call "
580  "ClearArcs() before carrying out the boolean operation." ) );
581  }
582 
583  ClipperLib::Clipper c;
584 
585  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
586 
587  std::vector<CLIPPER_Z_VALUE> zValues;
588  std::vector<SHAPE_ARC> arcBuffer;
589  std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
590 
591  for( const POLYGON& poly : aShape.m_polys )
592  {
593  for( size_t i = 0; i < poly.size(); i++ )
594  {
595  c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
596  ClipperLib::ptSubject, true );
597  }
598  }
599 
600  for( const POLYGON& poly : aOtherShape.m_polys )
601  {
602  for( size_t i = 0; i < poly.size(); i++ )
603  {
604  c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
605  ClipperLib::ptClip, true );
606  }
607  }
608 
609  ClipperLib::PolyTree solution;
610 
611  ClipperLib::ZFillCallback callback =
612  [&]( ClipperLib::IntPoint & e1bot, ClipperLib::IntPoint & e1top,
613  ClipperLib::IntPoint & e2bot, ClipperLib::IntPoint & e2top,
614  ClipperLib::IntPoint & pt )
615  {
616  auto arcIndex =
617  [&]( const ssize_t& aZvalue, const ssize_t& aCompareVal = -1 ) -> ssize_t
618  {
619  ssize_t retval;
620 
621  retval = zValues.at( aZvalue ).m_SecondArcIdx;
622 
623  if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
624  retval = zValues.at( aZvalue ).m_FirstArcIdx;
625 
626  return retval;
627  };
628 
629  auto arcSegment =
630  [&]( const ssize_t& aBottomZ, const ssize_t aTopZ ) -> ssize_t
631  {
632  ssize_t retval = arcIndex( aBottomZ );
633 
634  if( retval != -1 )
635  {
636  if( retval != arcIndex( aTopZ, retval ) )
637  retval = -1; // Not an arc segment as the two indices do not match
638  }
639 
640  return retval;
641  };
642 
643  ssize_t e1ArcSegmentIndex = arcSegment( e1bot.Z, e1top.Z );
644  ssize_t e2ArcSegmentIndex = arcSegment( e2bot.Z, e2top.Z );
645 
646  CLIPPER_Z_VALUE newZval;
647 
648  if( e1ArcSegmentIndex != -1 )
649  {
650  newZval.m_FirstArcIdx = e1ArcSegmentIndex;
651  newZval.m_SecondArcIdx = e2ArcSegmentIndex;
652  }
653  else
654  {
655  newZval.m_FirstArcIdx = e2ArcSegmentIndex;
656  newZval.m_SecondArcIdx = -1;
657  }
658 
659  size_t z_value_ptr = zValues.size();
660  zValues.push_back( newZval );
661 
662  // Only worry about arc segments for later processing
663  if( newZval.m_FirstArcIdx != -1 )
664  newIntersectPoints.insert( { VECTOR2I( pt.X, pt.Y ), newZval } );
665 
666  pt.Z = z_value_ptr;
667  //@todo amend X,Y values to true intersection between arcs or arc and segment
668  };
669 
670  c.ZFillFunction( callback ); // register callback
671 
672  c.Execute( aType, solution, ClipperLib::pftNonZero, ClipperLib::pftNonZero );
673 
674  importTree( &solution, zValues, arcBuffer );
675 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
void importTree(ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)

References ArcCount(), importTree(), CLIPPER_Z_VALUE::m_FirstArcIdx, m_polys, CLIPPER_Z_VALUE::m_SecondArcIdx, OutlineCount(), and PM_STRICTLY_SIMPLE.

◆ BooleanSubtract() [1/2]

◆ BooleanSubtract() [2/2]

void SHAPE_POLY_SET::BooleanSubtract ( const SHAPE_POLY_SET a,
const SHAPE_POLY_SET b,
POLYGON_MODE  aFastMode 
)

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

Definition at line 703 of file shape_poly_set.cpp.

705 {
706  booleanOp( ClipperLib::ctDifference, a, b, aFastMode );
707 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
This is the engine to execute all polygon boolean transforms (AND, OR, ...

References booleanOp().

◆ BuildBBoxCaches()

void SHAPE_POLY_SET::BuildBBoxCaches ( ) const

Construct BBoxCaches for Contains(), below.

Note
These caches must be built before a group of calls to Contains(). They are not kept up-to-date by editing actions.

Definition at line 1722 of file shape_poly_set.cpp.

1723 {
1724  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1725  {
1726  COutline( polygonIdx ).GenerateBBoxCache();
1727 
1728  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1729  CHole( polygonIdx, holeIdx ).GenerateBBoxCache();
1730  }
1731 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void GenerateBBoxCache() const

References CHole(), COutline(), SHAPE_LINE_CHAIN::GenerateBBoxCache(), HoleCount(), and OutlineCount().

Referenced by ZONE_FILLER::computeRawFilledArea().

◆ BuildPolysetFromOrientedPaths()

const SHAPE_POLY_SET SHAPE_POLY_SET::BuildPolysetFromOrientedPaths ( const std::vector< SHAPE_LINE_CHAIN > &  aPaths,
bool  aReverseOrientation = false,
bool  aEvenOdd = false 
)
static

Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order.

Parameters
aPathset of closed outlines forming the polygon. Positive orientation = outline, negative = hole
aReverseOrientationinverts the sign of the orientation of aPaths (so negative = outline)
aEvenOddforces the even-off fill rule (default is non zero)
Returns
the constructed poly set

Definition at line 2531 of file shape_poly_set.cpp.

2533 {
2534  ClipperLib::Clipper clipper;
2535  ClipperLib::PolyTree tree;
2536 
2537  // fixme: do we need aReverseOrientation?
2538 
2539  for( const SHAPE_LINE_CHAIN& path : aPaths )
2540  {
2541  ClipperLib::Path lc;
2542 
2543  for( int i = 0; i < path.PointCount(); i++ )
2544  {
2545  lc.emplace_back( path.CPoint( i ).x, path.CPoint( i ).y );
2546  }
2547 
2548  clipper.AddPath( lc, ClipperLib::ptSubject, true );
2549  }
2550 
2551  clipper.StrictlySimple( true );
2552  clipper.Execute( ClipperLib::ctUnion, tree,
2553  aEvenOdd ? ClipperLib::pftEvenOdd : ClipperLib::pftNonZero,
2554  ClipperLib::pftNonZero );
2555  SHAPE_POLY_SET result;
2556 
2557  for( ClipperLib::PolyNode* n = tree.GetFirst(); n; n = n->GetNext() )
2558  {
2559  if( !n->IsHole() )
2560  {
2561  int outl = result.NewOutline();
2562 
2563  for( unsigned int i = 0; i < n->Contour.size(); i++ )
2564  result.Outline( outl ).Append( n->Contour[i].X, n->Contour[i].Y );
2565 
2566  for( unsigned int i = 0; i < n->Childs.size(); i++ )
2567  {
2568  int outh = result.NewHole( outl );
2569  for( unsigned int j = 0; j < n->Childs[i]->Contour.size(); j++ )
2570  {
2571  result.Hole( outl, outh )
2572  .Append( n->Childs[i]->Contour[j].X, n->Childs[i]->Contour[j].Y );
2573  }
2574  }
2575  }
2576  }
2577 
2578  return result;
2579 }
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
int NewOutline()
Creates a new hole in a given outline.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

References SHAPE_LINE_CHAIN::Append(), Hole(), NewHole(), NewOutline(), Outline(), and path.

Referenced by convertPolygon().

◆ CacheTriangulation()

void SHAPE_POLY_SET::CacheTriangulation ( bool  aPartition = true)

Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.

Parameters
aPartition= true to created a trinagulation in a partition on a grid false to create a more basic triangulation of the polygons Note in partition calculations the grid size is hard coded to 1e7. This is a good value for Pcbnew: 1cm, in internal units. But not good for Gerbview (1e7 = 10cm), however using a partition is not useful.

Definition at line 2319 of file shape_poly_set.cpp.

2320 {
2321  bool recalculate = !m_hash.IsValid();
2322  MD5_HASH hash;
2323 
2324  if( !m_triangulationValid )
2325  recalculate = true;
2326 
2327  if( !recalculate )
2328  {
2329  hash = checksum();
2330 
2331  if( m_hash != hash )
2332  {
2333  m_hash = hash;
2334  recalculate = true;
2335  }
2336  }
2337 
2338  if( !recalculate )
2339  return;
2340 
2341  SHAPE_POLY_SET tmpSet;
2342 
2343  if( aPartition )
2344  {
2345  // This partitions into regularly-sized grids (1cm in Pcbnew)
2346  SHAPE_POLY_SET flattened( *this );
2347  flattened.ClearArcs();
2348  partitionPolyIntoRegularCellGrid( flattened, 1e7, tmpSet );
2349  }
2350  else
2351  {
2352  tmpSet = *this;
2353 
2354  if( tmpSet.HasHoles() )
2355  tmpSet.Fracture( PM_FAST );
2356  }
2357 
2358  m_triangulatedPolys.clear();
2359  m_triangulationValid = false;
2360 
2361  while( tmpSet.OutlineCount() > 0 )
2362  {
2363 
2364  if( !m_triangulatedPolys.empty() && m_triangulatedPolys.back()->GetTriangleCount() == 0 )
2365  m_triangulatedPolys.erase( m_triangulatedPolys.end() - 1 );
2366 
2367  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2368  PolygonTriangulation tess( *m_triangulatedPolys.back() );
2369 
2370  // If the tessellation fails, we re-fracture the polygon, which will
2371  // first simplify the system before fracturing and removing the holes
2372  // This may result in multiple, disjoint polygons.
2373  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
2374  {
2375  tmpSet.Fracture( PM_FAST );
2376  m_triangulationValid = false;
2377  continue;
2378  }
2379 
2380  tmpSet.DeletePolygon( 0 );
2381  m_triangulationValid = true;
2382  }
2383 
2384  if( m_triangulationValid )
2385  m_hash = checksum();
2386 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
MD5_HASH checksum() const
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
void DeletePolygon(int aIdx)
static void partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize, SHAPE_POLY_SET &aOut)
Represent a set of closed polygons.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
POLYGON & Polygon(int aIndex)
bool IsValid() const
Definition: md5_hash.h:24

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

Referenced by FOOTPRINT::BuildPolyCourtyards(), ZONE::CacheTriangulation(), ConvertPolygonToTriangles(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), Mirror(), polygon_triangulation_main(), Rotate(), and PNS_KICAD_IFACE_BASE::syncZone().

◆ CalcShape()

SGNODE * SHAPE::CalcShape ( SGNODE aParent,
SGNODE aColor,
WRL1_ORDER  aVertexOrder,
float  aCreaseLimit = 0.74317,
bool  isVRML2 = false 
)
inherited

Definition at line 703 of file wrlfacet.cpp.

705 {
706  if( facets.empty() || !facets.front()->HasMinPoints() )
707  return nullptr;
708 
709  std::vector< std::list< FACET* > > flist;
710 
711  // determine the max. index and size flist as appropriate
712  std::list< FACET* >::iterator sF = facets.begin();
713  std::list< FACET* >::iterator eF = facets.end();
714 
715  int maxIdx = 0;
716  int tmi;
717  float maxV = 0.0;
718  float tV = 0.0;
719 
720  while( sF != eF )
721  {
722  tV = ( *sF )->CalcFaceNormal();
723  tmi = ( *sF )->GetMaxIndex();
724 
725  if( tmi > maxIdx )
726  maxIdx = tmi;
727 
728  if( tV > maxV )
729  maxV = tV;
730 
731  ++sF;
732  }
733 
734  ++maxIdx;
735 
736  if( maxIdx < 3 )
737  return nullptr;
738 
739  flist.resize( maxIdx );
740 
741  // create the lists of facets common to indices
742  sF = facets.begin();
743 
744  while( sF != eF )
745  {
746  ( *sF )->Renormalize( tV );
747  ( *sF )->CollectVertices( flist );
748  ++sF;
749  }
750 
751  // calculate the normals
752  size_t vs = flist.size();
753 
754  for( size_t i = 0; i < vs; ++i )
755  {
756  sF = flist[i].begin();
757  eF = flist[i].end();
758 
759  while( sF != eF )
760  {
761  ( *sF )->CalcVertexNormal( static_cast<int>( i ), flist[i], aCreaseLimit );
762  ++sF;
763  }
764  }
765 
766  std::vector< WRLVEC3F > vertices;
767  std::vector< WRLVEC3F > normals;
768  std::vector< SGCOLOR > colors;
769 
770  // push the facet data to the final output list
771  sF = facets.begin();
772  eF = facets.end();
773 
774  while( sF != eF )
775  {
776  ( *sF )->GetData( vertices, normals, colors, aVertexOrder );
777  ++sF;
778  }
779 
780  flist.clear();
781 
782  if( vertices.size() < 3 )
783  return nullptr;
784 
785  IFSG_SHAPE shapeNode( false );
786 
787  if( !isVRML2 )
788  {
789  shapeNode.NewNode( aParent );
790 
791  if( aColor )
792  {
793  if( nullptr == S3D::GetSGNodeParent( aColor ) )
794  shapeNode.AddChildNode( aColor );
795  else
796  shapeNode.AddRefNode( aColor );
797  }
798  }
799 
800  std::vector< SGPOINT > lCPts; // vertex points in SGPOINT (double) format
801  std::vector< SGVECTOR > lCNorm; // per-vertex normals
802  vs = vertices.size();
803 
804  for( size_t i = 0; i < vs; ++i )
805  {
806  SGPOINT pt;
807  pt.x = vertices[i].x;
808  pt.y = vertices[i].y;
809  pt.z = vertices[i].z;
810  lCPts.push_back( pt );
811  lCNorm.emplace_back( normals[i].x, normals[i].y, normals[i].z );
812  }
813 
814  vertices.clear();
815  normals.clear();
816 
817  IFSG_FACESET fsNode( false );
818 
819  if( !isVRML2 )
820  fsNode.NewNode( shapeNode );
821  else
822  fsNode.NewNode( aParent );
823 
824  IFSG_COORDS cpNode( fsNode );
825  cpNode.SetCoordsList( lCPts.size(), &lCPts[0] );
826  IFSG_COORDINDEX ciNode( fsNode );
827 
828  for( int i = 0; i < (int)lCPts.size(); ++i )
829  ciNode.AddIndex( i );
830 
831  IFSG_NORMALS nmNode( fsNode );
832  nmNode.SetNormalList( lCNorm.size(), &lCNorm[0] );
833 
834  if( !colors.empty() )
835  {
836  IFSG_COLORS nmColor( fsNode );
837  nmColor.SetColorList( colors.size(), &colors[0] );
838  colors.clear();
839  }
840 
841  if( !isVRML2 )
842  return shapeNode.GetRawPtr();
843 
844  return fsNode.GetRawPtr();
845 }
double x
Definition: sg_base.h:70
IFSG_COORDS is the wrapper for SGCOORDS.
Definition: ifsg_coords.h:40
IFSG_COORDINDEX is the wrapper for SGCOORDINDEX.
IFSG_COLORS is the wrapper for SGCOLORS.
Definition: ifsg_colors.h:41
SGLIB_API SGNODE * GetSGNodeParent(SGNODE *aNode)
Definition: ifsg_api.cpp:494
double y
Definition: sg_base.h:71
IFSG_NORMALS is the wrapper for the SGNORMALS class.
Definition: ifsg_normals.h:40
std::list< FACET * > facets
Definition: wrlfacet.h:143
IFSG_FACESET is the wrapper for the SGFACESET class.
Definition: ifsg_faceset.h:40
double z
Definition: sg_base.h:72
IFSG_SHAPE is the wrapper for the SGSHAPE class.
Definition: ifsg_shape.h:40

References IFSG_NODE::AddChildNode(), IFSG_INDEX::AddIndex(), IFSG_NODE::AddRefNode(), SHAPE::facets, IFSG_NODE::GetRawPtr(), S3D::GetSGNodeParent(), IFSG_FACESET::NewNode(), IFSG_SHAPE::NewNode(), IFSG_COLORS::SetColorList(), IFSG_COORDS::SetCoordsList(), IFSG_NORMALS::SetNormalList(), SGPOINT::x, SGPOINT::y, and SGPOINT::z.

Referenced by WRL1FACESET::TranslateToSG(), WRL2FACESET::TranslateToSG(), and X3DIFACESET::TranslateToSG().

◆ Centre()

virtual VECTOR2I SHAPE::Centre ( ) const
inlinevirtualinherited

Compute a center-of-mass of the shape.

Returns
the center-of-mass point

Definition at line 216 of file shape.h.

217  {
218  return BBox( 0 ).Centre(); // if nothing better is available....
219  }
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
Vec Centre() const
Definition: box2.h:63

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

Referenced by Collide().

◆ Chamfer()

SHAPE_POLY_SET SHAPE_POLY_SET::Chamfer ( int  aDistance)

Return a chamfered version of the polygon set.

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

Definition at line 2019 of file shape_poly_set.cpp.

2020 {
2021  SHAPE_POLY_SET chamfered;
2022 
2023  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
2024  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
2025 
2026  return chamfered;
2027 }
Represent a set of closed polygons.
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.

References ChamferPolygon(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone().

◆ chamferFilletPolygon()

SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::chamferFilletPolygon ( CORNER_MODE  aMode,
unsigned int  aDistance,
int  aIndex,
int  aErrorMax 
)
private

Return the chamfered 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
the chamfered/filleted version of the polygon.Return true if the polygon set has any holes that touch share a vertex.

Definition at line 2041 of file shape_poly_set.cpp.

2044 {
2045  // Null segments create serious issues in calculations. Remove them:
2047 
2048  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
2049  SHAPE_POLY_SET::POLYGON newPoly;
2050 
2051  // If the chamfering distance is zero, then the polygon remain intact.
2052  if( aDistance == 0 )
2053  {
2054  return currentPoly;
2055  }
2056 
2057  // Iterate through all the contours (outline and holes) of the polygon.
2058  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
2059  {
2060  // Generate a new contour in the new polygon
2061  SHAPE_LINE_CHAIN newContour;
2062 
2063  // Iterate through the vertices of the contour
2064  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2065  {
2066  // Current vertex
2067  int x1 = currContour.CPoint( currVertex ).x;
2068  int y1 = currContour.CPoint( currVertex ).y;
2069 
2070  // Indices for previous and next vertices.
2071  int prevVertex;
2072  int nextVertex;
2073 
2074  // Previous and next vertices indices computation. Necessary to manage the edge cases.
2075 
2076  // Previous vertex is the last one if the current vertex is the first one
2077  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2078 
2079  // next vertex is the first one if the current vertex is the last one.
2080  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
2081 
2082  // Previous vertex computation
2083  double xa = currContour.CPoint( prevVertex ).x - x1;
2084  double ya = currContour.CPoint( prevVertex ).y - y1;
2085 
2086  // Next vertex computation
2087  double xb = currContour.CPoint( nextVertex ).x - x1;
2088  double yb = currContour.CPoint( nextVertex ).y - y1;
2089 
2090  // Compute the new distances
2091  double lena = hypot( xa, ya );
2092  double lenb = hypot( xb, yb );
2093 
2094  // Make the final computations depending on the mode selected, chamfered or filleted.
2095  if( aMode == CORNER_MODE::CHAMFERED )
2096  {
2097  double distance = aDistance;
2098 
2099  // Chamfer one half of an edge at most
2100  if( 0.5 * lena < distance )
2101  distance = 0.5 * lena;
2102 
2103  if( 0.5 * lenb < distance )
2104  distance = 0.5 * lenb;
2105 
2106  int nx1 = KiROUND( distance * xa / lena );
2107  int ny1 = KiROUND( distance * ya / lena );
2108 
2109  newContour.Append( x1 + nx1, y1 + ny1 );
2110 
2111  int nx2 = KiROUND( distance * xb / lenb );
2112  int ny2 = KiROUND( distance * yb / lenb );
2113 
2114  newContour.Append( x1 + nx2, y1 + ny2 );
2115  }
2116  else // CORNER_MODE = FILLETED
2117  {
2118  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
2119 
2120  double radius = aDistance;
2121  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
2122 
2123  // Do nothing in case of parallel edges
2124  if( std::isinf( denom ) )
2125  continue;
2126 
2127  // Limit rounding distance to one half of an edge
2128  if( 0.5 * lena * denom < radius )
2129  radius = 0.5 * lena * denom;
2130 
2131  if( 0.5 * lenb * denom < radius )
2132  radius = 0.5 * lenb * denom;
2133 
2134  // Calculate fillet arc absolute center point (xc, yx)
2135  double k = radius / sqrt( .5 * ( 1 - cosine ) );
2136  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
2137  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
2138  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
2139  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
2140 
2141  // Calculate arc start and end vectors
2142  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
2143  double xs = x1 + k * xa / lena - xc;
2144  double ys = y1 + k * ya / lena - yc;
2145  double xe = x1 + k * xb / lenb - xc;
2146  double ye = y1 + k * yb / lenb - yc;
2147 
2148  // Cosine of arc angle
2149  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
2150 
2151  // Make sure the argument is in [-1,1], interval in which the acos function is
2152  // defined
2153  if( argument < -1 )
2154  argument = -1;
2155  else if( argument > 1 )
2156  argument = 1;
2157 
2158  double arcAngle = acos( argument );
2159  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
2160  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
2161 
2162  double deltaAngle = arcAngle / segments;
2163  double startAngle = atan2( -ys, xs );
2164 
2165  // Flip arc for inner corners
2166  if( xa * yb - ya * xb <= 0 )
2167  deltaAngle *= -1;
2168 
2169  double nx = xc + xs;
2170  double ny = yc + ys;
2171 
2172  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
2173 
2174  // Store the previous added corner to make a sanity check
2175  int prevX = KiROUND( nx );
2176  int prevY = KiROUND( ny );
2177 
2178  for( int j = 0; j < segments; j++ )
2179  {
2180  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2181  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2182 
2183  // Sanity check: the rounding can produce repeated corners; do not add them.
2184  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
2185  {
2186  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
2187  prevX = KiROUND( nx );
2188  prevY = KiROUND( ny );
2189  }
2190  }
2191  }
2192  }
2193 
2194  // Close the current contour and add it the new polygon
2195  newContour.SetClosed( true );
2196  newPoly.push_back( newContour );
2197  }
2198 
2199  return newPoly;
2200 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:73
POLYGON & Polygon(int aIndex)
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)

References SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::CPoint(), distance(), GetArcToSegmentCount(), KiROUND(), Polygon(), RemoveNullSegments(), 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 
)

Return a chamfered version of the aIndex-th polygon.

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

Definition at line 1870 of file shape_poly_set.cpp.

1871 {
1872  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
1873 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode ...

References CHAMFERED, and chamferFilletPolygon().

Referenced by Chamfer().

◆ checksum()

MD5_HASH SHAPE_POLY_SET::checksum ( ) const
private

Definition at line 2389 of file shape_poly_set.cpp.

2390 {
2391  MD5_HASH hash;
2392 
2393  hash.Hash( m_polys.size() );
2394 
2395  for( const POLYGON& outline : m_polys )
2396  {
2397  hash.Hash( outline.size() );
2398 
2399  for( const SHAPE_LINE_CHAIN& lc : outline )
2400  {
2401  hash.Hash( lc.PointCount() );
2402 
2403  for( int i = 0; i < lc.PointCount(); i++ )
2404  {
2405  hash.Hash( lc.CPoint( i ).x );
2406  hash.Hash( lc.CPoint( i ).y );
2407  }
2408  }
2409  }
2410 
2411  hash.Finalize();
2412 
2413  return hash;
2414 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void Finalize()
Definition: md5_hash.cpp:78

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

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

◆ CHole()

◆ CIterate() [1/3]

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

Definition at line 805 of file shape_poly_set.h.

806  {
807  CONST_ITERATOR iter;
808 
809  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
810  iter.m_currentPolygon = aFirst;
811  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
812  iter.m_currentContour = 0;
813  iter.m_currentVertex = 0;
814  iter.m_iterateHoles = aIterateHoles;
815 
816  return iter;
817  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
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 ConvertOutlineToPolygon(), EDA_SHAPE::DupPolyPointsList(), EDA_SHAPE::getBoundingBox(), and ZONE::GetInteractingZones().

◆ CIterate() [2/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aOutline) const
inline

Definition at line 819 of file shape_poly_set.h.

820  {
821  return CIterate( aOutline, aOutline );
822  }
CONST_ITERATOR CIterate() const

References CIterate().

◆ CIterate() [3/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( ) const
inline

Definition at line 829 of file shape_poly_set.h.

830  {
831  return CIterate( 0, OutlineCount() - 1 );
832  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
CONST_ITERATOR CIterate() const

References OutlineCount().

Referenced by CIterate(), and CIterateWithHoles().

◆ CIterateSegments() [1/3]

◆ CIterateSegments() [2/3]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegments ( int  aPolygonIdx) const
inline

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

Definition at line 898 of file shape_poly_set.h.

References CIterateSegments().

◆ CIterateSegments() [3/3]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegments ( ) const
inline

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

Definition at line 910 of file shape_poly_set.h.

References OutlineCount().

Referenced by CIterateSegments(), and CIterateSegmentsWithHoles().

◆ CIterateSegmentsWithHoles() [1/2]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegmentsWithHoles ( ) const
inline

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

Definition at line 928 of file shape_poly_set.h.

References CIterateSegments(), and OutlineCount().

Referenced by CollideEdge(), IsPolygonSelfIntersecting(), and SquaredDistanceToPolygon().

◆ CIterateSegmentsWithHoles() [2/2]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegmentsWithHoles ( int  aOutline) const
inline

Definition at line 934 of file shape_poly_set.h.

935  {
936  return CIterateSegments( aOutline, aOutline, true );
937  }
CONST_SEGMENT_ITERATOR CIterateSegments() const
Returns an iterator object, for all outlines in the set (with holes)

References CIterateSegments().

◆ CIterateWithHoles() [1/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( int  aOutline) const
inline

Definition at line 824 of file shape_poly_set.h.

825  {
826  return CIterate( aOutline, aOutline, true );
827  }
CONST_ITERATOR CIterate() const

References CIterate().

Referenced by PCB_POINT_EDITOR::buildForPolyOutline(), ZONE::CIterateWithHoles(), and PCB_GRID_HELPER::computeAnchors().

◆ CIterateWithHoles() [2/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( ) const
inline

Definition at line 834 of file shape_poly_set.h.

835  {
836  return CIterate( 0, OutlineCount() - 1, true );
837  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
CONST_ITERATOR CIterate() const

References CIterate(), and OutlineCount().

Referenced by CollideVertex().

◆ ClearArcs()

void SHAPE_POLY_SET::ClearArcs ( )

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

Definition at line 556 of file shape_poly_set.cpp.

557 {
558  for( POLYGON& poly : m_polys )
559  {
560  for( size_t i = 0; i < poly.size(); i++ )
561  poly[i].ClearArcs();
562  }
563 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)

References m_polys.

Referenced by BOOST_AUTO_TEST_CASE(), ZONE::BuildSmoothedPoly(), CacheTriangulation(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), CADSTAR_PCB_ARCHIVE_LOADER::loadCoppers(), and ZONE_FILLER::subtractHigherPriorityZones().

◆ Clone()

SHAPE * SHAPE_POLY_SET::Clone ( ) const
overridevirtual

Return a dynamically allocated copy of the shape.

Return values
copyof the shape Creates a new empty polygon in the set and returns its index

Reimplemented from SHAPE.

Definition at line 116 of file shape_poly_set.cpp.

117 {
118  return new SHAPE_POLY_SET( *this );
119 }

References SHAPE_POLY_SET().

◆ Collide() [1/4]

bool SHAPE::Collide ( const SHAPE aShape,
int  aClearance,
VECTOR2I aMTV 
) const
virtualinherited

Check 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
aActual[out] an optional pointer to an int to store the actual distance in the event of a collision.
aLocation[out] an option pointer to a point to store a nearby location in the event of a collision.
Returns
true, if there is a collision.

Reimplemented in SHAPE_RECT, SHAPE_SEGMENT, and SHAPE_COMPOUND.

Definition at line 1103 of file shape_collisions.cpp.

1104 {
1105  return collideShapes( this, aShape, aClearance, nullptr, nullptr, aMTV );
1106 }
static bool collideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aLocation, VECTOR2I *aMTV)

References collideShapes().

◆ Collide() [2/4]

bool SHAPE_POLY_SET::Collide ( const SHAPE aShape,
int  aClearance = 0,
int *  aActual = nullptr,
VECTOR2I aLocation = nullptr 
) const
overridevirtual

Check 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
aActual[out] an optional pointer to an int to store the actual distance in the event of a collision.
aLocation[out] an option pointer to a point to store a nearby location in the event of a collision.
Returns
true if there is a collision.

Reimplemented from SHAPE.

Definition at line 1484 of file shape_poly_set.cpp.

1486 {
1487  // A couple of simple cases are worth trying before we fall back on triangulation.
1488 
1489  if( aShape->Type() == SH_SEGMENT )
1490  {
1491  const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
1492  int extra = segment->GetWidth() / 2;
1493 
1494  if( Collide( segment->GetSeg(), aClearance + extra, aActual, aLocation ) )
1495  {
1496  if( aActual )
1497  *aActual = std::max( 0, *aActual - extra );
1498 
1499  return true;
1500  }
1501 
1502  return false;
1503  }
1504 
1505  if( aShape->Type() == SH_CIRCLE )
1506  {
1507  const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
1508  int extra = circle->GetRadius();
1509 
1510  if( Collide( circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
1511  {
1512  if( aActual )
1513  *aActual = std::max( 0, *aActual - extra );
1514 
1515  return true;
1516  }
1517 
1518  return false;
1519  }
1520 
1521  const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( false );
1522 
1523  int actual = INT_MAX;
1524  VECTOR2I location;
1525 
1526  for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
1527  {
1528  for( const TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
1529  {
1530  if( aActual || aLocation )
1531  {
1532  int triActual;
1533  VECTOR2I triLocation;
1534 
1535  if( aShape->Collide( &tri, aClearance, &triActual, &triLocation ) )
1536  {
1537  if( triActual < actual )
1538  {
1539  actual = triActual;
1540  location = triLocation;
1541  }
1542  }
1543  }
1544  else // A much faster version of above
1545  {
1546  if( aShape->Collide( &tri, aClearance ) )
1547  return true;
1548  }
1549  }
1550  }
1551 
1552  if( actual < INT_MAX )
1553  {
1554  if( aActual )
1555  *aActual = std::max( 0, actual );
1556 
1557  if( aLocation )
1558  *aLocation = location;
1559 
1560  return true;
1561  }
1562 
1563  return false;
1564 }
int GetRadius() const
Definition: shape_circle.h:107
Define a general 2D-vector/point.
Definition: vector2d.h:61
const VECTOR2I GetCenter() const
Definition: shape_circle.h:112
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:165
const SEG & GetSeg() const
circle
Definition: shape.h:46
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
int GetWidth() const
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:94
line segment
Definition: shape.h:44

References SHAPE::Collide(), SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), SHAPE_SEGMENT::GetSeg(), SHAPE_SEGMENT::GetWidth(), m_triangulatedPolys, SH_CIRCLE, SH_SEGMENT, and SHAPE_BASE::Type().

Referenced by calcIsInsideArea(), calcIsInsideCourtyard(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), EDA_SHAPE::hitTest(), FOOTPRINT::HitTestAccurate(), PCB_SELECTION_TOOL::hitTestDistance(), and DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances().

◆ Collide() [3/4]

bool SHAPE_POLY_SET::Collide ( const VECTOR2I aP,
int  aClearance = 0,
int *  aActual = nullptr,
VECTOR2I aLocation = nullptr 
) const
overridevirtual

Check whether the point aP is either inside or on the edge of the polygon set.

Note that prior to Jul 2020 we considered the edge to not be part of the polygon. However, most other shapes (rects, circles, segments, etc.) include their edges and the difference was causing issues when used for DRC.

(FWIW, SHAPE_LINE_CHAIN was a split personality, with Collide() including its edges but PointInside() not. That has also been corrected.)

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.
aActualan optional pointer to an int to store the actual distance in the event of a collision.
Returns
true if the point aP collides with the polygon; false in any other case.

Reimplemented from SHAPE.

Definition at line 1460 of file shape_poly_set.cpp.

1462 {
1463  if( IsEmpty() || VertexCount() == 0 )
1464  return false;
1465 
1466  VECTOR2I nearest;
1467  ecoord dist_sq = SquaredDistance( aP, aLocation ? &nearest : nullptr );
1468 
1469  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1470  {
1471  if( aLocation )
1472  *aLocation = nearest;
1473 
1474  if( aActual )
1475  *aActual = sqrt( dist_sq );
1476 
1477  return true;
1478  }
1479 
1480  return false;
1481 }
bool IsEmpty() const
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of points in the shape poly set.
Define a general 2D-vector/point.
Definition: vector2d.h:61
static SEG::ecoord Square(int a)
Definition: seg.h:122
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
VECTOR2I::extended_type ecoord

References IsEmpty(), SEG::Square(), SquaredDistance(), and VertexCount().

◆ Collide() [4/4]

bool SHAPE_POLY_SET::Collide ( const SEG aSeg,
int  aClearance = 0,
int *  aActual = nullptr,
VECTOR2I aLocation = nullptr 
) const
overridevirtual

Check whether the segment aSeg collides with the polygon set (or its edge).

Note that prior to Jul 2020 we considered the edge to not be part of the polygon. However, most other shapes (rects, circles, segments, etc.) include their edges and the difference was causing issues when used for DRC.

(FWIW, SHAPE_LINE_CHAIN was a split personality, with Collide() including its edges but PointInside() not. That has also been corrected.)

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.
aActualan optional pointer to an int to store the actual distance in the event of a collision.
Returns
true if the segment aSeg collides with the polygon, false in any other case.

Implements SHAPE.

Definition at line 1439 of file shape_poly_set.cpp.

1441 {
1442  VECTOR2I nearest;
1443  ecoord dist_sq = SquaredDistance( aSeg, aLocation ? &nearest : nullptr );
1444 
1445  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1446  {
1447  if( aLocation )
1448  *aLocation = nearest;
1449 
1450  if( aActual )
1451  *aActual = sqrt( dist_sq );
1452 
1453  return true;
1454  }
1455 
1456  return false;
1457 }
Define a general 2D-vector/point.
Definition: vector2d.h:61
static SEG::ecoord Square(int a)
Definition: seg.h:122
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
VECTOR2I::extended_type ecoord

References SEG::Square(), and SquaredDistance().

◆ CollideEdge()

bool SHAPE_POLY_SET::CollideEdge ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex,
int  aClearance = 0 
) const

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

1696 {
1697  // Shows whether there was a collision
1698  bool collision = false;
1699 
1700  for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
1701  {
1702  const SEG currentSegment = *iterator;
1703  int distance = currentSegment.Distance( aPoint );
1704 
1705  // Check for collisions
1706  if( distance <= aClearance )
1707  {
1708  collision = true;
1709 
1710  // Update aClearance to look for closer edges
1711  aClearance = distance;
1712 
1713  // Store the indices that identify the vertex
1714  aClosestVertex = iterator.GetIndex();
1715  }
1716  }
1717 
1718  return collision;
1719 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
Definition: seg.h:40

References CIterateSegmentsWithHoles(), SEG::Distance(), and distance().

Referenced by EDA_SHAPE::hitTest(), and ZONE::HitTestForEdge().

◆ CollideVertex()

bool SHAPE_POLY_SET::CollideVertex ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex,
int  aClearance = 0 
) const

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

1657 {
1658  // Shows whether there was a collision
1659  bool collision = false;
1660 
1661  // Difference vector between each vertex and aPoint.
1662  VECTOR2D delta;
1663  double distance, clearance;
1664 
1665  // Convert clearance to double for precision when comparing distances
1666  clearance = aClearance;
1667 
1668  for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
1669  {
1670  // Get the difference vector between current vertex and aPoint
1671  delta = *iterator - aPoint;
1672 
1673  // Compute distance
1674  distance = delta.EuclideanNorm();
1675 
1676  // Check for collisions
1677  if( distance <= clearance )
1678  {
1679  collision = true;
1680 
1681  // Update aClearance to look for closer vertices
1682  clearance = distance;
1683 
1684  // Store the indices that identify the vertex
1685  aClosestVertex = iterator.GetIndex();
1686  }
1687  }
1688 
1689  return collision;
1690 }
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
constexpr int delta
CONST_ITERATOR CIterateWithHoles() const

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

Referenced by ZONE::HitTestForCorner().

◆ Contains()

bool SHAPE_POLY_SET::Contains ( const VECTOR2I aP,
int  aSubpolyIndex = -1,
int  aAccuracy = 0,
bool  aUseBBoxCaches = false 
) const

Return 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
aUseBBoxCachesgives faster performance when multiple calls are made with no editing in between, but the caller MUST cache the bbox caches before calling (via BuildBBoxCaches(), above)
Returns
true if the polygon contains the pointReturn true if the set is empty (no polygons at all)

Definition at line 1734 of file shape_poly_set.cpp.

1736 {
1737  if( m_polys.empty() )
1738  return false;
1739 
1740  // If there is a polygon specified, check the condition against that polygon
1741  if( aSubpolyIndex >= 0 )
1742  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1743 
1744  // In any other case, check it against all polygons in the set
1745  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1746  {
1747  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1748  return true;
1749  }
1750 
1751  return false;
1752 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.

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

Referenced by SHAPE_RECT::Collide(), ZONE_FILLER::computeRawFilledArea(), ZONE_FILLER::Fill(), PAD::GetBestAnchorPosition(), CADSTAR_PCB_ARCHIVE_LOADER::getKiCadPad(), GERBER_DRAW_ITEM::HitTest(), ZONE::HitTestFilledArea(), PCB_DIMENSION_BASE::segPolyIntersection(), BOARD::TestZoneIntersection(), PCB_DIM_ALIGNED::updateGeometry(), and PCB_DIM_ORTHOGONAL::updateGeometry().

◆ containsSingle()

bool SHAPE_POLY_SET::containsSingle ( const VECTOR2I aP,
int  aSubpolyIndex,
int  aAccuracy,
bool  aUseBBoxCaches = false 
) const
private

Check 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.
aAccuracyaccuracy in internal units
aUseBBoxCachesgives faster performance when multiple calls are made with no editing in between, but the caller MUST cache the bbox caches before calling (via BuildBBoxCaches(), above)
Returns
true if aP is inside aSubpolyIndex-th polygon; false in any other case.

Definition at line 1790 of file shape_poly_set.cpp.

1792 {
1793  // Check that the point is inside the outline
1794  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1795  {
1796  // Check that the point is not in any of the holes
1797  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1798  {
1799  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1800 
1801  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1802  // here as it's meaning would be inverted.
1803  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1804  return false;
1805  }
1806 
1807  return true;
1808  }
1809 
1810  return false;
1811 }
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

References CHole(), HoleCount(), m_polys, and SHAPE_LINE_CHAIN_BASE::PointInside().

Referenced by Contains(), and SquaredDistanceToPolygon().

◆ COutline()

const SHAPE_LINE_CHAIN& SHAPE_POLY_SET::COutline ( int  aIndex) const
inline

Definition at line 727 of file shape_poly_set.h.

728  {
729  return m_polys[aIndex][0];
730  }

References m_polys.

Referenced by CN_LIST::Add(), PAD::AddPrimitivePoly(), BOARD_ADAPTER::addSolidAreasShapes(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), CN_ZONE_LAYER::AnchorCount(), BuildBBoxCaches(), BuildConvexHull(), PAD::BuildEffectiveShapes(), CN_VISITOR::checkZoneZoneConnection(), CN_ZONE_LAYER::CN_ZONE_LAYER(), convertPolygon(), ConvertPolygonToBlocks(), CONVERT_TOOL::CreatePolys(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::PCB_PAINTER::Draw(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawApertureMacro(), KIGFX::CAIRO_GAL_BASE::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), KIGFX::PREVIEW::POLYGON_ITEM::drawPreviewShape(), EDA_SHAPE::DupPolyPointsList(), EXPORTER_PCB_VRML::ExportVrmlBoard(), EXPORTER_PCB_VRML::ExportVrmlPolygonSet(), PCB_PLUGIN::format(), CN_ZONE_LAYER::GetAnchor(), PAD::GetBestAnchorPosition(), FOOTPRINT::GetBoundingHull(), EDA_SHAPE::GetLength(), CADSTAR_PCB_ARCHIVE_LOADER::getZoneFromCadstarShape(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), FABMASTER::loadGraphics(), EAGLE_PLUGIN::loadPolygon(), FABMASTER::loadPolygon(), EDA_SHAPE::MakeEffectiveShapes(), DSN::SPECCTRA_DB::makePADSTACK(), PlotLayerOutlines(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), DXF_PLOTTER::ThickSegment(), HYPERLYNX_EXPORTER::writeBoardInfo(), HYPERLYNX_EXPORTER::writeNetObjects(), and GBR_TO_PCB_EXPORTER::writePcbPolygon().

◆ CPolygon()

◆ CVertex() [1/3]

const VECTOR2I & SHAPE_POLY_SET::CVertex ( int  aIndex,
int  aOutline,
int  aHole 
) const

Return the aGlobalIndex-th vertex in the poly set.

Definition at line 357 of file shape_poly_set.cpp.

358 {
359  if( aOutline < 0 )
360  aOutline += m_polys.size();
361 
362  int idx;
363 
364  if( aHole < 0 )
365  idx = 0;
366  else
367  idx = aHole + 1;
368 
369  assert( aOutline < (int) m_polys.size() );
370  assert( idx < (int) m_polys[aOutline].size() );
371 
372  return m_polys[aOutline][idx].CPoint( aIndex );
373 }

References m_polys.

Referenced by PCB_POINT_EDITOR::addCorner(), EDA_SHAPE::Compare(), CVertex(), D_CODE::DrawFlashedPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), findVertex(), ZONE::GetCornerPosition(), EDA_SHAPE::getPosition(), ZONE::HatchBorder(), ZONE::HitTest(), ZONE::MoveEdge(), ZONE::SetCornerPosition(), PCB_POINT_EDITOR::updateItem(), and PCB_POINT_EDITOR::updatePoints().

◆ CVertex() [2/3]

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

Return the index-th vertex in a given hole outline within a given outline.

Definition at line 376 of file shape_poly_set.cpp.

377 {
379 
380  // Assure the passed index references a legal position; abort otherwise
381  if( !GetRelativeIndices( aGlobalIndex, &index ) )
382  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
383 
384  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
385 }
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...

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

Definition at line 388 of file shape_poly_set.cpp.

389 {
390  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
391 }
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Return the aGlobalIndex-th vertex in the poly set.

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

◆ Deflate()

void SHAPE_POLY_SET::Deflate ( int  aAmount,
int  aCircleSegmentsCount,
CORNER_STRATEGY  aCornerStrategy = ROUND_ALL_CORNERS 
)
inline

Definition at line 1009 of file shape_poly_set.h.

1011  {
1012  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
1013  }
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.

References Inflate().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), calcIsInsideArea(), ZONE_FILLER::computeRawFilledArea(), KIGFX::PCB_PAINTER::draw(), ZONE_FILLER::fillSingleZone(), PCB_BASE_FRAME::FocusOnItems(), ALTIUM_PCB::ParseRegions6Data(), and PlotSolderMaskLayer().

◆ DeletePolygon()

void SHAPE_POLY_SET::DeletePolygon ( int  aIdx)

Definition at line 1636 of file shape_poly_set.cpp.

1637 {
1638  m_polys.erase( m_polys.begin() + aIdx );
1639 }

References m_polys.

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

◆ Fillet()

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

Return a filleted version of the polygon set.

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

Definition at line 2030 of file shape_poly_set.cpp.

2031 {
2032  SHAPE_POLY_SET filleted;
2033 
2034  for( size_t idx = 0; idx < m_polys.size(); idx++ )
2035  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
2036 
2037  return filleted;
2038 }
Represent a set of closed polygons.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.

References FilletPolygon(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone().

◆ FilletPolygon()

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

Return 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
A polygon containing the filleted version of the aIndex-th polygon.

Definition at line 1876 of file shape_poly_set.cpp.

1878 {
1879  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
1880 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode ...

References chamferFilletPolygon(), and FILLETED.

Referenced by Fillet(), and GEOM_TEST::FilletPolySet().

◆ Format()

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

Reimplemented from SHAPE.

Definition at line 1299 of file shape_poly_set.cpp.

1300 {
1301  std::stringstream ss;
1302 
1303  ss << "SHAPE_LINE_CHAIN poly; \n";
1304 
1305  for( unsigned i = 0; i < m_polys.size(); i++ )
1306  {
1307  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1308  {
1309 
1310  ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
1311 
1312  SHAPE_POLY_SET poly;
1313 
1314  if( j == 0 )
1315  {
1316  ss << " poly.AddOutline(tmp); } \n";
1317  }
1318  else
1319  {
1320  ss << " poly.AddHole(tmp); } \n";
1321  }
1322 
1323  }
1324  }
1325 
1326  return ss.str();
1327 }
Represent a set of closed polygons.

References m_polys.

◆ Fracture()

void SHAPE_POLY_SET::Fracture ( POLYGON_MODE  aFastMode)

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

Definition at line 1063 of file shape_poly_set.cpp.

1064 {
1065  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1066 
1067  for( POLYGON& paths : m_polys )
1068  fractureSingle( paths );
1069 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void fractureSingle(POLYGON &paths)
void Simplify(POLYGON_MODE aFastMode)

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

Referenced by addHoleToPolygon(), PAD::addPadPrimitivesToPolygon(), PAD::AddPrimitivePoly(), CacheTriangulation(), ZONE_FILLER::computeRawFilledArea(), convertPolygon(), BITMAPCONV_INFO::createOutputData(), CADSTAR_PCB_ARCHIVE_LOADER::drawCadstarShape(), AR_AUTOPLACER::drawPlacementRoutingMatrix(), EXPORTER_PCB_VRML::ExportStandardLayers(), EXPORTER_PCB_VRML::ExportVrmlSolderMask(), AR_AUTOPLACER::fillMatrix(), ZONE_FILLER::fillSingleZone(), APERTURE_MACRO::GetApertureMacroShape(), InflateWithLinkedHoles(), CADSTAR_PCB_ARCHIVE_LOADER::loadCoppers(), FABMASTER::loadFootprints(), EAGLE_PLUGIN::loadPolygon(), FABMASTER::loadShapePolySet(), ALTIUM_PCB::ParseRegions6Data(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), BRDITEMS_PLOTTER::PlotPcbShape(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), RENDER_3D_RAYTRACE::Reload(), TransformRingToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), and ZONE::TransformSmoothedOutlineToPolygon().

◆ fractureSingle()

void SHAPE_POLY_SET::fractureSingle ( POLYGON paths)
private

Definition at line 947 of file shape_poly_set.cpp.

948 {
949  FractureEdgeSet edges;
950  FractureEdgeSet border_edges;
951  FractureEdge* root = nullptr;
952 
953  bool first = true;
954 
955  if( paths.size() == 1 )
956  return;
957 
958  int num_unconnected = 0;
959 
960  for( const SHAPE_LINE_CHAIN& path : paths )
961  {
962  const std::vector<VECTOR2I>& points = path.CPoints();
963  int pointCount = points.size();
964 
965  FractureEdge* prev = nullptr, * first_edge = nullptr;
966 
967  int x_min = std::numeric_limits<int>::max();
968 
969  for( int i = 0; i < pointCount; i++ )
970  {
971  if( points[i].x < x_min )
972  x_min = points[i].x;
973 
974  // Do not use path.CPoint() here; open-coding it using the local variables "points"
975  // and "pointCount" gives a non-trivial performance boost to zone fill times.
976  FractureEdge* fe = new FractureEdge( first, points[ i ],
977  points[ i+1 == pointCount ? 0 : i+1 ] );
978 
979  if( !root )
980  root = fe;
981 
982  if( !first_edge )
983  first_edge = fe;
984 
985  if( prev )
986  prev->m_next = fe;
987 
988  if( i == pointCount - 1 )
989  fe->m_next = first_edge;
990 
991  prev = fe;
992  edges.push_back( fe );
993 
994  if( !first )
995  {
996  if( fe->m_p1.x == x_min )
997  border_edges.push_back( fe );
998  }
999 
1000  if( !fe->m_connected )
1001  num_unconnected++;
1002  }
1003 
1004  first = false; // first path is always the outline
1005  }
1006 
1007  // keep connecting holes to the main outline, until there's no holes left...
1008  while( num_unconnected > 0 )
1009  {
1010  int x_min = std::numeric_limits<int>::max();
1011  auto it = border_edges.begin();
1012 
1013  FractureEdge* smallestX = nullptr;
1014 
1015  // find the left-most hole edge and merge with the outline
1016  for( ; it != border_edges.end(); ++it )
1017  {
1018  FractureEdge* border_edge = *it;
1019  int xt = border_edge->m_p1.x;
1020 
1021  if( ( xt <= x_min ) && !border_edge->m_connected )
1022  {
1023  x_min = xt;
1024  smallestX = border_edge;
1025  }
1026  }
1027 
1028  int num_processed = processEdge( edges, smallestX );
1029 
1030  // If we can't handle the edge, the zone is broken (maybe)
1031  if( !num_processed )
1032  {
1033  wxLogWarning( wxT( "Broken polygon, dropping path" ) );
1034 
1035  for( FractureEdge* edge : edges )
1036  delete edge;
1037 
1038  return;
1039  }
1040 
1041  num_unconnected -= num_processed;
1042  }
1043 
1044  paths.clear();
1045  SHAPE_LINE_CHAIN newPath;
1046 
1047  newPath.SetClosed( true );
1048 
1049  FractureEdge* e;
1050 
1051  for( e = root; e->m_next != root; e = e->m_next )
1052  newPath.Append( e->m_p1 );
1053 
1054  newPath.Append( e->m_p1 );
1055 
1056  for( FractureEdge* edge : edges )
1057  delete edge;
1058 
1059  paths.push_back( std::move( newPath ) );
1060 }
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
FractureEdge * m_next
std::vector< FractureEdge * > FractureEdgeSet

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

Referenced by Fracture().

◆ FullPointCount()

int SHAPE_POLY_SET::FullPointCount ( ) const

Returns the number of holes in a given outline.

Definition at line 323 of file shape_poly_set.cpp.

324 {
325  int full_count = 0;
326 
327  if( m_polys.size() == 0 ) // Empty poly set
328  return full_count;
329 
330  for( int ii = 0; ii < OutlineCount(); ii++ )
331  {
332  // the first polygon in m_polys[ii] is the main contour,
333  // only others are holes:
334  for( int idx = 0; idx <= HoleCount( ii ); idx++ )
335  {
336  full_count += m_polys[ii][idx].PointCount();
337  }
338  }
339 
340  return full_count;
341 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.

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

◆ GetArcs()

void SHAPE_POLY_SET::GetArcs ( std::vector< SHAPE_ARC > &  aArcBuffer) const

Removes all arc references from all the outlines and holes in the polyset.

Definition at line 543 of file shape_poly_set.cpp.

544 {
545  for( const POLYGON& poly : m_polys )
546  {
547  for( size_t i = 0; i < poly.size(); i++ )
548  {
549  for( SHAPE_ARC arc : poly[i].m_arcs )
550  aArcBuffer.push_back( arc );
551  }
552  }
553 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.

References m_polys.

Referenced by BOOST_AUTO_TEST_CASE().

◆ GetGlobalIndex()

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

Compute 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
true if the relative indices are correct; false otherwise. The computed global index is returned in the aGlobalIdx reference.

Definition at line 162 of file shape_poly_set.cpp.

164 {
165  int selectedVertex = aRelativeIndices.m_vertex;
166  unsigned int selectedContour = aRelativeIndices.m_contour;
167  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
168 
169  // Check whether the vertex indices make sense in this poly set
170  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
171  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
172  {
173  POLYGON currentPolygon;
174 
175  aGlobalIdx = 0;
176 
177  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
178  {
179  currentPolygon = Polygon( polygonIdx );
180 
181  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
182  aGlobalIdx += currentPolygon[contourIdx].PointCount();
183  }
184 
185  currentPolygon = Polygon( selectedPolygon );
186 
187  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
188  aGlobalIdx += currentPolygon[contourIdx].PointCount();
189 
190  aGlobalIdx += selectedVertex;
191 
192  return true;
193  }
194  else
195  {
196  return false;
197  }
198 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
POLYGON & Polygon(int aIndex)

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

◆ GetHash()

MD5_HASH SHAPE_POLY_SET::GetHash ( ) const

Definition at line 2226 of file shape_poly_set.cpp.

2227 {
2228  if( !m_hash.IsValid() )
2229  return checksum();
2230 
2231  return m_hash;
2232 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:24

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

Referenced by ZONE::BuildHashValue(), ZONE::GetHashValue(), DSN::SPECCTRA_DB::makePADSTACK(), operator=(), and SHAPE_POLY_SET().

◆ GetIndexableSubshapeCount()

size_t SHAPE_POLY_SET::GetIndexableSubshapeCount ( ) const
overridevirtual

Reimplemented from SHAPE_BASE.

Definition at line 2456 of file shape_poly_set.cpp.

2457 {
2458  size_t n = 0;
2459 
2460  for( const std::unique_ptr<TRIANGULATED_POLYGON>& t : m_triangulatedPolys )
2461  n += t->GetTriangleCount();
2462 
2463  return n;
2464 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys

References m_triangulatedPolys.

Referenced by GetIndexableSubshapes().

◆ GetIndexableSubshapes()

void SHAPE_POLY_SET::GetIndexableSubshapes ( std::vector< SHAPE * > &  aSubshapes)
overridevirtual

Reimplemented from SHAPE_BASE.

Definition at line 2467 of file shape_poly_set.cpp.

2468 {
2469  aSubshapes.reserve( GetIndexableSubshapeCount() );
2470 
2471  for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
2472  {
2473  for( TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
2474  aSubshapes.push_back( &tri );
2475  }
2476 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
virtual size_t GetIndexableSubshapeCount() const override

References GetIndexableSubshapeCount(), and m_triangulatedPolys.

◆ GetNeighbourIndexes()

bool SHAPE_POLY_SET::GetNeighbourIndexes ( int  aGlobalIndex,
int *  aPrevious,
int *  aNext 
)

Return 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
aPreviousis the globalIndex of the previous corner of the same contour.
aNextis the globalIndex of the next corner of the same contour.
Returns
true if OK, false if aGlobalIndex is out of range

Definition at line 394 of file shape_poly_set.cpp.

395 {
397 
398  // If the edge does not exist, throw an exception, it is an illegal access memory error
399  if( !GetRelativeIndices( aGlobalIndex, &index ) )
400  return false;
401 
402  // Calculate the previous and next index of aGlobalIndex, corresponding to
403  // the same contour;
404  VERTEX_INDEX inext = index;
405  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
406 
407  if( index.m_vertex == 0 )
408  {
409  index.m_vertex = lastpoint;
410  inext.m_vertex = 1;
411  }
412  else if( index.m_vertex == lastpoint )
413  {
414  index.m_vertex--;
415  inext.m_vertex = 0;
416  }
417  else
418  {
419  inext.m_vertex++;
420  index.m_vertex--;
421  }
422 
423  if( aPrevious )
424  {
425  int previous;
426  GetGlobalIndex( index, previous );
427  *aPrevious = previous;
428  }
429 
430  if( aNext )
431  {
432  int next;
433  GetGlobalIndex( inext, next );
434  *aNext = next;
435  }
436 
437  return true;
438 }
CITER next(CITER it)
Definition: ptree.cpp:126
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.

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

◆ GetRelativeIndices()

bool SHAPE_POLY_SET::GetRelativeIndices ( int  aGlobalIdx,
SHAPE_POLY_SET::VERTEX_INDEX aRelativeIndices 
) const

Convert 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
true if the global index is correct and the information in aRelativeIndices is valid; false otherwise.

Definition at line 122 of file shape_poly_set.cpp.

124 {
125  int polygonIdx = 0;
126  unsigned int contourIdx = 0;
127  int vertexIdx = 0;
128 
129  int currentGlobalIdx = 0;
130 
131  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
132  {
133  const POLYGON& currentPolygon = CPolygon( polygonIdx );
134 
135  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
136  {
137  const SHAPE_LINE_CHAIN& currentContour = currentPolygon[contourIdx];
138  int totalPoints = currentContour.PointCount();
139 
140  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
141  {
142  // Check if the current vertex is the globally indexed as aGlobalIdx
143  if( currentGlobalIdx == aGlobalIdx )
144  {
145  aRelativeIndices->m_polygon = polygonIdx;
146  aRelativeIndices->m_contour = contourIdx;
147  aRelativeIndices->m_vertex = vertexIdx;
148 
149  return true;
150  }
151 
152  // Advance
153  currentGlobalIdx++;
154  }
155  }
156  }
157 
158  return false;
159 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
const POLYGON & CPolygon(int aIndex) const
int OutlineCount() const
Return the number of vertices in a given outline/hole.
int PointCount() const
Return the number of points (vertices) in this line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

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(), ZONE::GetCornerPosition(), GetNeighbourIndexes(), InsertVertex(), IsVertexInHole(), IterateFromVertexWithHoles(), RemoveVertex(), ZONE::SetCornerPosition(), ZONE::SetSelectedCorner(), and SetVertex().

◆ HasHoles()

bool SHAPE_POLY_SET::HasHoles ( ) const

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

Definition at line 1234 of file shape_poly_set.cpp.

1235 {
1236  // Iterate through all the polygons on the set
1237  for( const POLYGON& paths : m_polys )
1238  {
1239  // If any of them has more than one contour, it is a hole.
1240  if( paths.size() > 1 )
1241  return true;
1242  }
1243 
1244  // Return false if and only if every polygon has just one outline, without holes.
1245  return false;
1246 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.

References m_polys.

Referenced by PAD::AddPrimitivePoly(), and CacheTriangulation().

◆ HasIndexableSubshapes()

bool SHAPE_POLY_SET::HasIndexableSubshapes ( ) const
overridevirtual

Reimplemented from SHAPE_BASE.

Definition at line 2450 of file shape_poly_set.cpp.

2451 {
2452  return IsTriangulationUpToDate();
2453 }
bool IsTriangulationUpToDate() const

References IsTriangulationUpToDate().

◆ HasTouchingHoles()

bool SHAPE_POLY_SET::HasTouchingHoles ( ) const

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

Definition at line 2417 of file shape_poly_set.cpp.

2418 {
2419  for( int i = 0; i < OutlineCount(); i++ )
2420  {
2421  if( hasTouchingHoles( CPolygon( i ) ) )
2422  return true;
2423  }
2424 
2425  return false;
2426 }
const POLYGON & CPolygon(int aIndex) const
int OutlineCount() const
Return the number of vertices in a given outline/hole.
bool hasTouchingHoles(const POLYGON &aPoly) const

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

◆ hasTouchingHoles()

bool SHAPE_POLY_SET::hasTouchingHoles ( const POLYGON aPoly) const
private

Definition at line 2429 of file shape_poly_set.cpp.

2430 {
2431  std::set<long long> ptHashes;
2432 
2433  for( const SHAPE_LINE_CHAIN& lc : aPoly )
2434  {
2435  for( const VECTOR2I& pt : lc.CPoints() )
2436  {
2437  const long long ptHash = (long long) pt.x << 32 | pt.y;
2438 
2439  if( ptHashes.count( ptHash ) > 0 )
2440  return true;
2441 
2442  ptHashes.insert( ptHash );
2443  }
2444  }
2445 
2446  return false;
2447 }
Define a general 2D-vector/point.
Definition: vector2d.h:61
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

Referenced by HasTouchingHoles().

◆ Hole()

◆ HoleCount()

◆ importTree()

void SHAPE_POLY_SET::importTree ( ClipperLib::PolyTree *  tree,
const std::vector< CLIPPER_Z_VALUE > &  aZValueBuffer,
const std::vector< SHAPE_ARC > &  aArcBuffe 
)
private

Definition at line 817 of file shape_poly_set.cpp.

820 {
821  m_polys.clear();
822 
823  for( ClipperLib::PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
824  {
825  if( !n->IsHole() )
826  {
827  POLYGON paths;
828  paths.reserve( n->Childs.size() + 1 );
829 
830  paths.emplace_back( n->Contour, aZValueBuffer, aArcBuffer );
831 
832  for( unsigned int i = 0; i < n->Childs.size(); i++ )
833  paths.emplace_back( n->Childs[i]->Contour, aZValueBuffer, aArcBuffer );
834 
835  m_polys.push_back( paths );
836  }
837  }
838 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.

References m_polys.

Referenced by booleanOp(), and Inflate().

◆ Inflate()

void SHAPE_POLY_SET::Inflate ( int  aAmount,
int  aCircleSegCount,
CORNER_STRATEGY  aCornerStrategy = ROUND_ALL_CORNERS 
)

Perform outline inflation/deflation.

Polygons can have holes, but not linked holes with main outlines, if aFactor < 0. For those use InflateWithLinkedHoles() to avoid odd corners where the link segments meet the outline.

Parameters
aAmountis the number of units to offset edges.
aCircleSegCountis the number of segments per 360 degrees to use in curve approx
aCornerStrategyALLOW_ACUTE_CORNERS to preserve all angles, CHAMFER_ACUTE_CORNERS to chop angles less than 90°, ROUND_ACUTE_CORNERS to round off angles less than 90°, ROUND_ALL_CORNERS to round regardless of angles

Definition at line 726 of file shape_poly_set.cpp.

727 {
728  using namespace ClipperLib;
729  // A static table to avoid repetitive calculations of the coefficient
730  // 1.0 - cos( M_PI / aCircleSegCount )
731  // aCircleSegCount is most of time <= 64 and usually 8, 12, 16, 32
732  #define SEG_CNT_MAX 64
733  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
734 
735  ClipperOffset c;
736 
737  // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
738  // and are not what you'd think they are.
739  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
740  JoinType joinType = jtRound; // The way corners are offsetted
741  double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
742  JoinType miterFallback = jtSquare;
743 
744  switch( aCornerStrategy )
745  {
746  case ALLOW_ACUTE_CORNERS:
747  joinType = jtMiter;
748  miterLimit = 10; // Allows large spikes
749  miterFallback = jtSquare;
750  break;
751 
752  case CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
753  joinType = jtMiter;
754  miterFallback = jtRound;
755  break;
756 
757  case ROUND_ACUTE_CORNERS: // Acute angles are rounded
758  joinType = jtMiter;
759  miterFallback = jtSquare;
760  break;
761 
762  case CHAMFER_ALL_CORNERS: // All angles are chamfered.
763  joinType = jtSquare;
764  miterFallback = jtSquare;
765  break;
766 
767  case ROUND_ALL_CORNERS: // All angles are rounded.
768  joinType = jtRound;
769  miterFallback = jtSquare;
770  break;
771  }
772 
773  std::vector<CLIPPER_Z_VALUE> zValues;
774  std::vector<SHAPE_ARC> arcBuffer;
775 
776  for( const POLYGON& poly : m_polys )
777  {
778  for( size_t i = 0; i < poly.size(); i++ )
779  {
780  c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
781  joinType, etClosedPolygon );
782  }
783  }
784 
785  PolyTree solution;
786 
787  // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
788  // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
789  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
790 
791  if( aCircleSegCount < 6 ) // avoid incorrect aCircleSegCount values
792  aCircleSegCount = 6;
793 
794  double coeff;
795 
796  if( aCircleSegCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
797  {
798  coeff = 1.0 - cos( M_PI / aCircleSegCount );
799 
800  if( aCircleSegCount <= SEG_CNT_MAX )
801  arc_tolerance_factor[aCircleSegCount] = coeff;
802  }
803  else
804  {
805  coeff = arc_tolerance_factor[aCircleSegCount];
806  }
807 
808  c.ArcTolerance = std::abs( aAmount ) * coeff;
809  c.MiterLimit = miterLimit;
810  c.MiterFallback = miterFallback;
811  c.Execute( solution, aAmount );
812 
813  importTree( &solution, zValues, arcBuffer );
814 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
All angles are chamfered.
#define SEG_CNT_MAX
Acute angles are rounded.
Acute angles are chamfered.
just inflate the polygon. Acute angles create spikes
void importTree(ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)

References ALLOW_ACUTE_CORNERS, CHAMFER_ACUTE_CORNERS, CHAMFER_ALL_CORNERS, importTree(), m_polys, ROUND_ACUTE_CORNERS, ROUND_ALL_CORNERS, and SEG_CNT_MAX.

Referenced by FOOTPRINT::BuildPolyCourtyards(), ZONE::BuildSmoothedPoly(), CADSTAR_PCB_ARCHIVE_LOADER::calculateZonePriorities(), ZONE_FILLER::computeRawFilledArea(), BOARD_ADAPTER::createPadWithClearance(), Deflate(), ZONE_FILLER::fillSingleZone(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), InflateWithLinkedHoles(), CADSTAR_PCB_ARCHIVE_LOADER::loadCoppers(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::packagePolygon(), PlotSolderMaskLayer(), PAD::TransformShapeWithClearanceToPolygon(), and ZONE::TransformSmoothedOutlineToPolygon().

◆ InflateWithLinkedHoles()

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

Perform outline inflation/deflation, using round corners.

Polygons can have holes and/or linked holes with main outlines. The resulting polygons are also polygons with linked holes to main outlines. For aFastMode meaning, see function booleanOp .Convert a set of polygons with holes to a single outline with "slits"/"fractures" connecting the outer ring to the inner holes For aFastMode meaning, see function booleanOp

Definition at line 717 of file shape_poly_set.cpp.

719 {
720  Unfracture( aFastMode );
721  Inflate( aFactor, aCircleSegmentsCount );
722  Fracture( aFastMode );
723 }
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.

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

Referenced by PlotStandardLayer(), ZONE::TransformShapeWithClearanceToPolygon(), and ZONE::TransformSolidAreasShapesToPolygon().

◆ InsertVertex()

void SHAPE_POLY_SET::InsertVertex ( int  aGlobalIndex,
const VECTOR2I aNewVertex 
)

Adds a vertex in the globally indexed position aGlobalIndex.

Parameters
aGlobalIndexis the global index of the position in which the new vertex will be inserted.
aNewVertexis the new inserted vertex.Return the index-th vertex in a given hole outline within a given outline

Definition at line 276 of file shape_poly_set.cpp.

277 {
278  VERTEX_INDEX index;
279 
280  if( aGlobalIndex < 0 )
281  aGlobalIndex = 0;
282 
283  if( aGlobalIndex >= TotalVertices() )
284  {
285  Append( aNewVertex );
286  }
287  else
288  {
289  // Assure the position to be inserted exists; throw an exception otherwise
290  if( GetRelativeIndices( aGlobalIndex, &index ) )
291  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
292  else
293  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
294  }
295 }
int TotalVertices() const
Delete aIdx-th polygon from the set.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...

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 PCB_POINT_EDITOR::addCorner().

◆ IsEmpty()

◆ IsNull()

bool SHAPE::IsNull ( ) const
inlineinherited

Return true if the shape is a null shape.

Return values
trueif null :-)

Definition at line 150 of file shape.h.

151  {
152  return m_type == SH_NULL;
153  }
SHAPE_TYPE m_type
< type of our shape
Definition: shape.h:110
empty shape (no shape...),
Definition: shape.h:51

References SHAPE_BASE::m_type, and SH_NULL.

◆ IsPolygonSelfIntersecting()

bool SHAPE_POLY_SET::IsPolygonSelfIntersecting ( int  aPolygonIndex) const

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

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

Definition at line 441 of file shape_poly_set.cpp.

442 {
443  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
444  CONST_SEGMENT_ITERATOR innerIterator;
445 
446  for( iterator = CIterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
447  {
448  SEG firstSegment = *iterator;
449 
450  // Iterate through all remaining segments.
451  innerIterator = iterator;
452 
453  // Start in the next segment, we don't want to check collision between a segment and itself
454  for( innerIterator++; innerIterator; innerIterator++ )
455  {
456  SEG secondSegment = *innerIterator;
457 
458  // Check whether the two segments built collide, only when they are not adjacent.
459  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
460  return true;
461  }
462  }
463 
464  return false;
465 }
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:189
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
Definition: seg.h:40

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

Referenced by IsSelfIntersecting().

◆ IsSelfIntersecting()

bool SHAPE_POLY_SET::IsSelfIntersecting ( ) const

Check whether any of the polygons in the set is self intersecting.

Returns
true if any of the polygons is self intersecting, false otherwise.Return the number of triangulated polygons

Definition at line 468 of file shape_poly_set.cpp.

469 {
470  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
471  {
472  if( IsPolygonSelfIntersecting( polygon ) )
473  return true;
474  }
475 
476  return false;
477 }
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.

References IsPolygonSelfIntersecting(), and m_polys.

Referenced by PCB_POINT_EDITOR::validatePolygon().

◆ IsSolid()

bool SHAPE_POLY_SET::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 1081 of file shape_poly_set.h.

1082  {
1083  return true;
1084  }

◆ IsTriangulationUpToDate()

bool SHAPE_POLY_SET::IsTriangulationUpToDate ( ) const

Definition at line 2235 of file shape_poly_set.cpp.

2236 {
2237  if( !m_triangulationValid )
2238  return false;
2239 
2240  if( !m_hash.IsValid() )
2241  return false;
2242 
2243  MD5_HASH hash = checksum();
2244 
2245  return hash == m_hash;
2246 }
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::GERBVIEW_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), KIGFX::OPENGL_GAL::DrawPolygon(), HasIndexableSubshapes(), operator=(), SHAPE_POLY_SET(), and PNS_KICAD_IFACE_BASE::syncZone().

◆ IsVertexInHole()

bool SHAPE_POLY_SET::IsVertexInHole ( int  aGlobalIdx)

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

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

Definition at line 2006 of file shape_poly_set.cpp.

2007 {
2008  VERTEX_INDEX index;
2009 
2010  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
2011  if( !GetRelativeIndices( aGlobalIdx, &index ) )
2012  return false;
2013 
2014  // The contour is a hole if its index is greater than zero
2015  return index.m_contour > 0;
2016 }
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...

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

◆ Iterate() [1/3]

ITERATOR SHAPE_POLY_SET::Iterate ( int  aFirst,
int  aLast,
bool  aIterateHoles = false 
)
inline

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

753  {
754  ITERATOR iter;
755 
756  iter.m_poly = this;
757  iter.m_currentPolygon = aFirst;
758  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
759  iter.m_currentContour = 0;
760  iter.m_currentVertex = 0;
761  iter.m_iterateHoles = aIterateHoles;
762 
763  return iter;
764  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
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 PCB_POINT_EDITOR::addCorner(), and ZONE::Iterate().

◆ Iterate() [2/3]

ITERATOR SHAPE_POLY_SET::Iterate ( int  aOutline)
inline
Parameters
aOutlineis the index of the polygon to be iterated.
Returns
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 771 of file shape_poly_set.h.

772  {
773  return Iterate( aOutline, aOutline );
774  }
ITERATOR Iterate()

References Iterate().

◆ Iterate() [3/3]

ITERATOR SHAPE_POLY_SET::Iterate ( )
inline
Returns
an iterator object to visit all points in all outlines of the set, without visiting the points in the holes.

Definition at line 790 of file shape_poly_set.h.

791  {
792  return Iterate( 0, OutlineCount() - 1 );
793  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
ITERATOR Iterate()

References OutlineCount().

Referenced by Iterate(), and IterateWithHoles().

◆ IterateFromVertexWithHoles()

ITERATOR SHAPE_POLY_SET::IterateFromVertexWithHoles ( int  aGlobalIdx)
inline

◆ IterateSegments() [1/3]

◆ IterateSegments() [2/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aPolygonIdx)
inline

Return an iterator object, for iterating aPolygonIdx-th polygon edges.

Definition at line 892 of file shape_poly_set.h.

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

References OutlineCount().

Referenced by IterateSegments(), and IterateSegmentsWithHoles().

◆ IterateSegmentsWithHoles() [1/2]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( )
inline

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

Definition at line 916 of file shape_poly_set.h.

References IterateSegments(), and OutlineCount().

Referenced by ConvertOutlineToPolygon(), ZONE::HatchBorder(), and BOARD::TestZoneIntersection().

◆ IterateSegmentsWithHoles() [2/2]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( int  aOutline)
inline

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

Definition at line 922 of file shape_poly_set.h.

References IterateSegments().

◆ IterateWithHoles() [1/2]

ITERATOR SHAPE_POLY_SET::IterateWithHoles ( int  aOutline)
inline
Parameters
aOutlinethe index of the polygon to be iterated.
Returns
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 781 of file shape_poly_set.h.

782  {
783  return Iterate( aOutline, aOutline, true );
784  }
ITERATOR Iterate()

References Iterate().

Referenced by findVertex(), ZONE::HatchBorder(), ZONE::IterateWithHoles(), and BOARD::TestZoneIntersection().

◆ IterateWithHoles() [2/2]

ITERATOR SHAPE_POLY_SET::IterateWithHoles ( )
inline
Returns
an iterator object to visit all points in all outlines of the set, visiting also the points in the holes.

Definition at line 799 of file shape_poly_set.h.

800  {
801  return Iterate( 0, OutlineCount() - 1, true );
802  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
ITERATOR Iterate()

References Iterate(), and OutlineCount().

Referenced by IterateFromVertexWithHoles(), and RemoveNullSegments().

◆ Mirror()

void SHAPE_POLY_SET::Mirror ( bool  aX = true,
bool  aY = false,
const VECTOR2I aRef = { 0, 0 } 
)

Mirror the line points about y or x (or both)

Parameters
aXIf true, mirror about the y axis (flip x coordinate)
aYIf true, mirror about the x axis
aRefsets the reference point about which to mirror

Definition at line 1829 of file shape_poly_set.cpp.

1830 {
1831  for( POLYGON& poly : m_polys )
1832  {
1833  for( SHAPE_LINE_CHAIN& path : poly )
1834  path.Mirror( aX, aY, aRef );
1835  }
1836 
1837  if( m_triangulationValid )
1839 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void CacheTriangulation(bool aPartition=true)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.

References CacheTriangulation(), m_polys, m_triangulationValid, and path.

Referenced by GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), FP_SHAPE::Flip(), FOOTPRINT::Flip(), EDA_SHAPE::flip(), FABMASTER::loadFootprints(), FP_SHAPE::Mirror(), and ZONE::Mirror().

◆ Move()

void SHAPE_POLY_SET::Move ( const VECTOR2I aVector)
overridevirtual

Implements SHAPE.

Definition at line 1814 of file shape_poly_set.cpp.

1815 {
1816  for( POLYGON& poly : m_polys )
1817  {
1818  for( SHAPE_LINE_CHAIN& path : poly )
1819  path.Move( aVector );
1820  }
1821 
1822  for( std::unique_ptr<TRIANGULATED_POLYGON>& tri : m_triangulatedPolys )
1823  tri->Move( aVector );
1824 
1825  m_hash = checksum();
1826 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
MD5_HASH checksum() const
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

References checksum(), m_hash, m_polys, m_triangulatedPolys, and path.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), ALTIUM_PCB::HelperShapeSetLocalCoord(), GERBER_DRAW_ITEM::HitTest(), FABMASTER::loadFootprints(), CADSTAR_PCB_ARCHIVE_LOADER::loadLibraryCoppers(), FP_SHAPE::Move(), EDA_SHAPE::move(), ZONE::Move(), GERBER_DRAW_ITEM::MoveAB(), FOOTPRINT::MoveAnchorPosition(), GERBER_DRAW_ITEM::MoveXY(), DS_DRAW_ITEM_POLYPOLYGONS::SetPosition(), FOOTPRINT::SetPosition(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), and TransformTrapezoidToPolygon().

◆ NewFacet()

FACET * SHAPE::NewFacet ( )
inherited

Definition at line 695 of file wrlfacet.cpp.

696 {
697  FACET* fp = new FACET;
698  facets.push_back( fp );
699  return fp;
700 }
Definition: wrlfacet.h:42
std::list< FACET * > facets
Definition: wrlfacet.h:143

References SHAPE::facets.

Referenced by WRL1FACESET::TranslateToSG(), WRL2FACESET::TranslateToSG(), and X3DIFACESET::TranslateToSG().

◆ NewHole()

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

Adds a new outline to the set and returns its index.

Definition at line 213 of file shape_poly_set.cpp.

214 {
215  SHAPE_LINE_CHAIN empty_path;
216 
217  empty_path.SetClosed( true );
218 
219  // Default outline is the last one
220  if( aOutline < 0 )
221  aOutline += m_polys.size();
222 
223  // Add hole to the selected outline
224  m_polys[aOutline].push_back( empty_path );
225 
226  return m_polys.back().size() - 2;
227 }
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by BuildPolysetFromOrientedPaths(), ConvertOutlineToPolygon(), ZONE::NewHole(), and TransformRingToPolygon().

◆ NewOutline()

int SHAPE_POLY_SET::NewOutline ( )

Creates a new hole in a given outline.

Definition at line 201 of file shape_poly_set.cpp.

202 {
203  SHAPE_LINE_CHAIN empty_path;
204  POLYGON poly;
205 
206  empty_path.SetClosed( true );
207  poly.push_back( empty_path );
208  m_polys.push_back( poly );
209  return m_polys.size() - 1;
210 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), ZONE_FILLER::addKnockout(), AR_AUTOPLACER::addPad(), LIB_SHAPE::AddPoint(), ZONE::AppendCorner(), EDA_SHAPE::beginEdit(), BuildBoardPolygonOutlines(), BuildFootprintPolygonOutlines(), BuildPolysetFromOrientedPaths(), KI_TEST::CommonTestData::CommonTestData(), ConvertOutlineToPolygon(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CornerListToPolygon(), BITMAPCONV_INFO::createOutputData(), BOARD_ADAPTER::createPadWithClearance(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), fillArcPOLY(), PCB_BASE_FRAME::FocusOnItems(), FOOTPRINT::GetBoundingHull(), getRectangleAlongCentreLine(), EDA_SHAPE::hitTest(), FABMASTER::loadFootprints(), EAGLE_PLUGIN::loadPolygon(), FABMASTER::loadShapePolySet(), FABMASTER::loadZone(), LEGACY_PLUGIN::loadZONE_CONTAINER(), PCB_PARSER::parseZONE(), DXF_PLOTTER::PlotPoly(), PlotStandardLayer(), RENDER_3D_OPENGL::reload(), EDA_SHAPE::rotate(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), EDA_SHAPE::SetPolyPoints(), SHAPE_POLY_SET(), DS_DATA_ITEM_POLYGONS::SyncDrawItems(), TransformArcToPolygon(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), EDA_SHAPE::TransformShapeWithClearanceToPolygon(), PCB_DIM_ALIGNED::updateGeometry(), PCB_DIM_ORTHOGONAL::updateGeometry(), PCB_DIM_LEADER::updateGeometry(), and EE_POINT_EDITOR::updateParentItem().

◆ NormalizeAreaOutlines()

int SHAPE_POLY_SET::NormalizeAreaOutlines ( )

Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).

Removes null segments.

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

1267 {
1268  // We are expecting only one main outline, but this main outline can have holes
1269  // if holes: combine holes and remove them from the main outline.
1270  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1271  // calculations, but it is not mandatory. It is used mainly
1272  // because there is usually only very few vertices in area outlines
1273  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1274  SHAPE_POLY_SET holesBuffer;
1275 
1276  // Move holes stored in outline to holesBuffer:
1277  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1278  while( outline.size() > 1 )
1279  {
1280  holesBuffer.AddOutline( outline.back() );
1281  outline.pop_back();
1282  }
1283 
1285 
1286  // If any hole, subtract it to main outline
1287  if( holesBuffer.OutlineCount() )
1288  {
1289  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1291  }
1292 
1294 
1295  return OutlineCount();
1296 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
Represent a set of closed polygons.
void Simplify(POLYGON_MODE aFastMode)
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
POLYGON & Polygon(int aIndex)

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

Referenced by BITMAPCONV_INFO::createOutputData().

◆ operator=()

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

Definition at line 2203 of file shape_poly_set.cpp.

2204 {
2205  static_cast<SHAPE&>(*this) = aOther;
2206  m_polys = aOther.m_polys;
2207  m_triangulatedPolys.clear();
2208  m_triangulationValid = false;
2209 
2210  if( aOther.IsTriangulationUpToDate() )
2211  {
2212  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
2213  {
2214  const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
2215  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
2216  }
2217 
2218  m_hash = aOther.GetHash();
2219  m_triangulationValid = true;
2220  }
2221 
2222  return *this;
2223 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool IsTriangulationUpToDate() const
MD5_HASH GetHash() const
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const

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

◆ Outline() [1/2]

SHAPE_LINE_CHAIN& SHAPE_POLY_SET::Outline ( int  aIndex)
inline

Definition at line 679 of file shape_poly_set.h.

680  {
681  return m_polys[aIndex][0];
682  }

References m_polys.

Referenced by EE_POINT_EDITOR::addCorner(), ZONE_FILLER::addHatchFillTypeOnZone(), LIB_SHAPE::AddPoint(), Area(), EDA_SHAPE::beginEdit(), BOOST_AUTO_TEST_CASE(), BuildFootprintPolygonOutlines(), BuildPolysetFromOrientedPaths(), ZONE::BuildSmoothedPoly(), EDA_SHAPE::calcEdit(), calcIsInsideArea(), ZONE::CalculateFilledArea(), PCB_GRID_HELPER::computeAnchors(), EDA_SHAPE::continueEdit(), ConvertPolygonToBlocks(), FOOTPRINT::CoverageRatio(), CONVERT_TOOL::CreateLines(), BITMAPCONV_INFO::createOutputData(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), DIALOG_PAD_PRIMITIVE_POLY_PROPS::DIALOG_PAD_PRIMITIVE_POLY_PROPS(), KIGFX::DS_PAINTER::draw(), KIGFX::SCH_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), APERTURE_MACRO::DrawApertureMacroShape(), EDA_SHAPE::endEdit(), DSN::SPECCTRA_DB::fillBOUNDARY(), AR_AUTOPLACER::fillMatrix(), CADSTAR_SCH_ARCHIVE_LOADER::fixUpLibraryPins(), GERBER_PLOTTER::FlashPadChamferRoundRect(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), HPGL_PLOTTER::FlashPadRoundRect(), DXF_PLOTTER::FlashPadRoundRect(), PCB_PLUGIN::format(), formatPoly(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), PCB_SHAPE::GetFocusPosition(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), CADSTAR_SCH_ARCHIVE_LOADER::getScaledLibPart(), LIB_SHAPE::GetSelectMenuText(), EDA_SHAPE::hitTest(), PNS::SOLID::HoleHull(), PNS::SOLID::Hull(), GEOM_TEST::IsPolySetValid(), FABMASTER::loadFootprints(), FABMASTER::loadZone(), EDIT_POINTS_FACTORY::Make(), DSN::SPECCTRA_DB::makeIMAGE(), DSN::SPECCTRA_DB::makePADSTACK(), PCB_PARSER::parseZONE(), LIB_SHAPE::Plot(), PlotDrawingSheet(), BRDITEMS_PLOTTER::PlotFilledAreas(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), BRDITEMS_PLOTTER::PlotPcbShape(), polygonArea(), LIB_SHAPE::print(), GERBER_DRAW_ITEM::PrintGerberPoly(), DS_DRAW_ITEM_POLYPOLYGONS::PrintWsItem(), DRC_RTREE::QueryColliding(), RENDER_3D_OPENGL::reload(), EE_POINT_EDITOR::removeCorner(), EE_POINT_EDITOR::removeCornerCondition(), PCB_POINT_EDITOR::removeCornerCondition(), DRC_TEST_PROVIDER_EDGE_CLEARANCE::Run(), SCH_LEGACY_PLUGIN_CACHE::savePolyLine(), EDA_SHAPE::scale(), SHAPE_POLY_SET(), ZONE_FILLER::subtractHigherPriorityZones(), TransformArcToPolygon(), EE_POINT_EDITOR::updatePoints(), and GBR_TO_PCB_EXPORTER::writePcbZoneItem().

◆ Outline() [2/2]

const SHAPE_LINE_CHAIN& SHAPE_POLY_SET::Outline ( int  aIndex) const
inline

Definition at line 684 of file shape_poly_set.h.

685  {
686  return m_polys[aIndex][0];
687  }

References m_polys.

◆ OutlineCount()

int SHAPE_POLY_SET::OutlineCount ( ) const
inline

Return the number of vertices in a given outline/hole.

Definition at line 657 of file shape_poly_set.h.

References m_polys.

Referenced by PCB_POINT_EDITOR::addCorner(), ZONE_FILLER::addHatchFillTypeOnZone(), PAD::addPadPrimitivesToPolygon(), ZONE::AddPolygon(), PAD::AddPrimitivePoly(), BOARD_ADAPTER::addSolidAreasShapes(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), ZONE::AppendCorner(), Area(), booleanOp(), BOOST_AUTO_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BuildBBoxCaches(), BuildBoardPolygonOutlines(), BuildConvexHull(), BuildFootprintPolygonOutlines(), CacheTriangulation(), calcIsInsideArea(), ZONE::CalculateFilledArea(), CIterate(), CIterateSegments(), CIterateSegmentsWithHoles(), CIterateWithHoles(), ZONE_FILLER::computeRawFilledArea(), Contains(), convertPolygon(), ConvertPolygonToBlocks(), RENDER_3D_OPENGL::createBoard(), BITMAPCONV_INFO::createOutputData(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), CONVERT_TOOL::CreatePolys(), KIGFX::DS_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawApertureMacro(), APERTURE_MACRO::DrawApertureMacroShape(), 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(), KIGFX::PREVIEW::POLYGON_ITEM::drawPreviewShape(), KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), EDA_SHAPE::DupPolyPointsList(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), EXPORTER_PCB_VRML::ExportVrmlBoard(), EXPORTER_PCB_VRML::ExportVrmlPolygonSet(), ZONE_FILLER::Fill(), fillArcPOLY(), DSN::SPECCTRA_DB::fillBOUNDARY(), GEOM_TEST::FilletPolySet(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), PCB_PLUGIN::format(), FullPointCount(), RENDER_3D_OPENGL::generateHoles(), RENDER_3D_OPENGL::generateLayerList(), RENDER_3D_OPENGL::generateViasAndPads(), APERTURE_MACRO::GetApertureMacroShape(), PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::GetBoundingBox(), FOOTPRINT::GetBoundingHull(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), GetRelativeIndices(), HasTouchingHoles(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), ZONE::HitTestCutout(), isCopperOutside(), GEOM_TEST::IsPolySetValid(), Iterate(), IterateSegments(), IterateSegmentsWithHoles(), IterateWithHoles(), FABMASTER::loadFootprints(), FABMASTER::loadGraphics(), FABMASTER::loadPolygon(), NormalizeAreaOutlines(), SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::operator bool(), DIALOG_PAD_PROPERTIES::padValuesOK(), partitionPolyIntoRegularCellGrid(), PlotDrawingSheet(), BRDITEMS_PLOTTER::PlotFilledAreas(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), PlotLayerOutlines(), BRDITEMS_PLOTTER::PlotPcbShape(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), PlotStandardLayer(), polygon_triangulation_main(), polygonArea(), GERBER_DRAW_ITEM::Print(), DS_DRAW_ITEM_POLYPOLYGONS::PrintWsItem(), DRC_RTREE::QueryColliding(), RENDER_3D_RAYTRACE::Reload(), ZONE::RemoveCutout(), Subset(), PNS_KICAD_IFACE_BASE::syncZone(), TestConcaveSquareFillet(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances(), TestSquareFillet(), HYPERLYNX_EXPORTER::writeBoardInfo(), HYPERLYNX_EXPORTER::writeNetObjects(), GBR_TO_PCB_EXPORTER::writePcbPolygon(), and GBR_TO_PCB_EXPORTER::writePcbZoneItem().

◆ Parse()

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

Reimplemented from SHAPE.

Definition at line 1330 of file shape_poly_set.cpp.

1331 {
1332  std::string tmp;
1333 
1334  aStream >> tmp;
1335 
1336  if( tmp != "polyset" )
1337  return false;
1338 
1339  aStream >> tmp;
1340 
1341  int n_polys = atoi( tmp.c_str() );
1342 
1343  if( n_polys < 0 )
1344  return false;
1345 
1346  for( int i = 0; i < n_polys; i++ )
1347  {
1348  POLYGON paths;
1349 
1350  aStream >> tmp;
1351 
1352  if( tmp != "poly" )
1353  return false;
1354 
1355  aStream >> tmp;
1356  int n_outlines = atoi( tmp.c_str() );
1357 
1358  if( n_outlines < 0 )
1359  return false;
1360 
1361  for( int j = 0; j < n_outlines; j++ )
1362  {
1363  SHAPE_LINE_CHAIN outline;
1364 
1365  outline.SetClosed( true );
1366 
1367  aStream >> tmp;
1368  int n_vertices = atoi( tmp.c_str() );
1369 
1370  for( int v = 0; v < n_vertices; v++ )
1371  {
1372  VECTOR2I p;
1373 
1374  aStream >> tmp; p.x = atoi( tmp.c_str() );
1375  aStream >> tmp; p.y = atoi( tmp.c_str() );
1376  outline.Append( p );
1377  }
1378 
1379  paths.push_back( outline );
1380  }
1381 
1382  m_polys.push_back( paths );
1383  }
1384 
1385  return true;
1386 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
Define a general 2D-vector/point.
Definition: vector2d.h:61
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

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

◆ PointOnEdge()

bool SHAPE_POLY_SET::PointOnEdge ( const VECTOR2I aP) const

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

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

Definition at line 1422 of file shape_poly_set.cpp.

1423 {
1424  // Iterate through all the polygons in the set
1425  for( const POLYGON& polygon : m_polys )
1426  {
1427  // Iterate through all the line chains in the polygon
1428  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1429  {
1430  if( lineChain.PointOnEdge( aP ) )
1431  return true;
1432  }
1433  }
1434 
1435  return false;
1436 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

References m_polys.

◆ Polygon() [1/2]

◆ Polygon() [2/2]

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

Definition at line 717 of file shape_poly_set.h.

718  {
719  return m_polys[aIndex];
720  }

References m_polys.

◆ RemoveAllContours()

◆ RemoveContour()

void SHAPE_POLY_SET::RemoveContour ( int  aContourIdx,
int  aPolygonIdx = -1 
)

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

1574 {
1575  // Default polygon is the last one
1576  if( aPolygonIdx < 0 )
1577  aPolygonIdx += m_polys.size();
1578 
1579  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1580 }

References m_polys.

Referenced by PCB_POINT_EDITOR::removeCorner().

◆ RemoveNullSegments()

int SHAPE_POLY_SET::RemoveNullSegments ( )

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

Returns
the number of deleted segments.

Definition at line 1583 of file shape_poly_set.cpp.

1584 {
1585  int removed = 0;
1586 
1587  ITERATOR iterator = IterateWithHoles();
1588 
1589  VECTOR2I contourStart = *iterator;
1590  VECTOR2I segmentStart, segmentEnd;
1591 
1592  VERTEX_INDEX indexStart;
1593 
1594  while( iterator )
1595  {
1596  // Obtain first point and its index
1597  segmentStart = *iterator;
1598  indexStart = iterator.GetIndex();
1599 
1600  // Obtain last point
1601  if( iterator.IsEndContour() )
1602  {
1603  segmentEnd = contourStart;
1604 
1605  // Advance
1606  iterator++;
1607 
1608  if( iterator )
1609  contourStart = *iterator;
1610  }
1611  else
1612  {
1613  // Advance
1614  iterator++;
1615 
1616  if( iterator )
1617  segmentEnd = *iterator;
1618  }
1619 
1620  // Remove segment start if both points are equal
1621  if( segmentStart == segmentEnd )
1622  {
1623  RemoveVertex( indexStart );
1624  removed++;
1625 
1626  // Advance the iterator one position, as there is one vertex less.
1627  if( iterator )
1628  iterator++;
1629  }
1630  }
1631 
1632  return removed;
1633 }
Define a general 2D-vector/point.
Definition: vector2d.h:61
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR IterateWithHoles()
void RemoveVertex(int aGlobalIndex)
Delete 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(), and NormalizeAreaOutlines().

◆ RemoveVertex() [1/2]

void SHAPE_POLY_SET::RemoveVertex ( int  aGlobalIndex)

Delete the aGlobalIndex-th vertex.

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

Definition at line 1755 of file shape_poly_set.cpp.

1756 {
1757  VERTEX_INDEX index;
1758 
1759  // Assure the to be removed vertex exists, abort otherwise
1760  if( GetRelativeIndices( aGlobalIndex, &index ) )
1761  RemoveVertex( index );
1762  else
1763  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1764 }
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.

References GetRelativeIndices().

Referenced by PCB_POINT_EDITOR::removeCorner(), and RemoveNullSegments().

◆ RemoveVertex() [2/2]

void SHAPE_POLY_SET::RemoveVertex ( VERTEX_INDEX  aRelativeIndices)

Delete the vertex indexed by aRelativeIndex (index of polygon, contour and vertex).

Parameters
aRelativeIndicesis the set of relative indices of the to-be-removed vertex.Remove all outlines & holes (clears) the polygon set.

Definition at line 1767 of file shape_poly_set.cpp.

1768 {
1769  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1770 }

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 = { 0, 0 } 
)
overridevirtual

Rotate all vertices by a given angle.

Parameters
aCenteris the rotation center.
aAngleis the rotation angle in radians.

Implements SHAPE.

Definition at line 1842 of file shape_poly_set.cpp.

1843 {
1844  for( POLYGON& poly : m_polys )
1845  {
1846  for( SHAPE_LINE_CHAIN& path : poly )
1847  path.Rotate( aAngle, aCenter );
1848  }
1849 
1850  // Don't re-cache if the triangulation is already invalid
1851  if( m_triangulationValid )
1853 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void CacheTriangulation(bool aPartition=true)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.

References CacheTriangulation(), m_polys, m_triangulationValid, and path.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), D_CODE::ConvertShapeToPolygon(), ALTIUM_PCB::HelperShapeSetLocalCoord(), FABMASTER::loadFootprints(), EDA_SHAPE::rotate(), ZONE::Rotate(), FOOTPRINT::SetOrientation(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), FP_TEXT::TransformShapeWithClearanceToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), TransformTrapezoidToPolygon(), PCB_DIM_ALIGNED::updateGeometry(), PCB_DIM_ORTHOGONAL::updateGeometry(), and PCB_DIM_LEADER::updateGeometry().

◆ SetVertex() [1/2]

void SHAPE_POLY_SET::SetVertex ( const VERTEX_INDEX aIndex,
const VECTOR2I aPos 
)

Accessor function to set the position of a specific point.

Parameters
aIndex#VERTEX_INDEX of the point to move.
aPosdestination position of the specified point.

Definition at line 1784 of file shape_poly_set.cpp.

1785 {
1786  m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1787 }

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.

Referenced by ZONE::MoveEdge(), ZONE::SetCornerPosition(), SetVertex(), and PCB_POINT_EDITOR::updateItem().

◆ SetVertex() [2/2]

void SHAPE_POLY_SET::SetVertex ( int  aGlobalIndex,
const VECTOR2I aPos 
)

Set the vertex based on the global index.

Throws if the index doesn't exist.

Parameters
aGlobalIndexglobal index of the to-be-moved vertex
aPosNew position on the vertexReturn total number of vertices stored in the set.

Definition at line 1773 of file shape_poly_set.cpp.

1774 {
1775  VERTEX_INDEX index;
1776 
1777  if( GetRelativeIndices( aGlobalIndex, &index ) )
1778  SetVertex( index, aPos );
1779  else
1780  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1781 }
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...

References GetRelativeIndices(), and SetVertex().

◆ Simplify()

◆ SquaredDistance() [1/2]

SEG::ecoord SHAPE_POLY_SET::SquaredDistance ( VECTOR2I  aPoint,
VECTOR2I aNearest = nullptr 
) const

Compute the minimum distance squared between aPoint and all the polygons in the set.

Squared distances are used because they avoid the cost of doing square-roots.

Parameters
aPointis the point whose distance to the set has to be measured.
aNearest[out] an optional pointer to be filled in with the point on the polyset which is closest to aPoint.
Returns
The minimum distance squared 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 1956 of file shape_poly_set.cpp.

1957 {
1958  SEG::ecoord currentDistance_sq;
1959  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1960  VECTOR2I nearest;
1961 
1962  // Iterate through all the polygons and get the minimum distance.
1963  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1964  {
1965  currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
1966  aNearest ? &nearest : nullptr );
1967 
1968  if( currentDistance_sq < minDistance_sq )
1969  {
1970  if( aNearest )
1971  *aNearest = nearest;
1972 
1973  minDistance_sq = currentDistance_sq;
1974  }
1975  }
1976 
1977  return minDistance_sq;
1978 }
VECTOR2I::extended_type ecoord
Definition: seg.h:43
Define a general 2D-vector/point.
Definition: vector2d.h:61
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.

References VECTOR2< T >::ECOORD_MAX, m_polys, and SquaredDistanceToPolygon().

Referenced by BOOST_AUTO_TEST_CASE(), and Collide().

◆ SquaredDistance() [2/2]

SEG::ecoord SHAPE_POLY_SET::SquaredDistance ( const SEG aSegment,
VECTOR2I aNearest = nullptr 
) const

Compute the minimum distance squared between aSegment and all the polygons in the set.

Squared distances are used because they avoid the cost of doing square-roots.

Parameters
aSegmentis the segment whose distance to the polygon set has to be measured.
aSegmentWidthis the width of the segment; defaults to zero.
aNearest[out] an optional pointer to be filled in with the point on the polyset which is closest to aSegment.
Returns
The minimum distance squared between aSegment and all the polygons in the set. If the point is contained in the polygon, the distance is zero.

Definition at line 1981 of file shape_poly_set.cpp.

1982 {
1983  SEG::ecoord currentDistance_sq;
1984  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1985  VECTOR2I nearest;
1986 
1987  // Iterate through all the polygons and get the minimum distance.
1988  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1989  {
1990  currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
1991  aNearest ? &nearest : nullptr );
1992 
1993  if( currentDistance_sq < minDistance_sq )
1994  {
1995  if( aNearest )
1996  *aNearest = nearest;
1997 
1998  minDistance_sq = currentDistance_sq;
1999  }
2000  }
2001 
2002  return minDistance_sq;
2003 }
VECTOR2I::extended_type ecoord
Definition: seg.h:43
Define a general 2D-vector/point.
Definition: vector2d.h:61
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.

References VECTOR2< T >::ECOORD_MAX, m_polys, and SquaredDistanceToPolygon().

◆ SquaredDistanceToPolygon() [1/2]

SEG::ecoord SHAPE_POLY_SET::SquaredDistanceToPolygon ( VECTOR2I  aPoint,
int  aIndex,
VECTOR2I aNearest 
) const

Compute 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 distance to aPoint has to be measured.
aNearest[out] an optional pointer to be filled in with the point on the polyset which is closest to aPoint.
Returns
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 1883 of file shape_poly_set.cpp.

1885 {
1886  // We calculate the min dist between the segment and each outline segment. However, if the
1887  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1888  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1889  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1890  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1891  {
1892  if( aNearest )
1893  *aNearest = aPoint;
1894 
1895  return 0;
1896  }
1897 
1898  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1899 
1900  SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1901 
1902  for( iterator++; iterator && minDistance > 0; iterator++ )
1903  {
1904  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1905 
1906  if( currentDistance < minDistance )
1907  {
1908  if( aNearest )
1909  *aNearest = (*iterator).NearestPoint( aPoint );
1910 
1911  minDistance = currentDistance;
1912  }
1913  }
1914 
1915  return minDistance;
1916 }
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
VECTOR2I::extended_type ecoord
Definition: seg.h:43
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.

References CIterateSegmentsWithHoles(), and containsSingle().

Referenced by SquaredDistance().

◆ SquaredDistanceToPolygon() [2/2]

SEG::ecoord SHAPE_POLY_SET::SquaredDistanceToPolygon ( const SEG aSegment,
int  aIndex,
VECTOR2I aNearest 
) const

Compute 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 distance to aPoint has to be measured.
aNearest[out] an optional pointer to be filled in with the point on the polyset which is closest to aSegment.
Returns
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 1919 of file shape_poly_set.cpp.

1921 {
1922  // Check if the segment is fully-contained. If so, its midpoint is a good-enough nearest point.
1923  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) &&
1924  containsSingle( aSegment.B, aPolygonIndex, 1 ) )
1925  {
1926  if( aNearest )
1927  *aNearest = ( aSegment.A + aSegment.B ) / 2;
1928 
1929  return 0;
1930  }
1931 
1932  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1933  SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1934 
1935  if( aNearest && minDistance == 0 )
1936  *aNearest = ( *iterator ).NearestPoint( aSegment );
1937 
1938  for( iterator++; iterator && minDistance > 0; iterator++ )
1939  {
1940  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
1941 
1942  if( currentDistance < minDistance )
1943  {
1944  if( aNearest )
1945  *aNearest = (*iterator).NearestPoint( aSegment );
1946 
1947  minDistance = currentDistance;
1948  }
1949  }
1950 
1951  // Return the maximum of minDistance and zero
1952  return minDistance < 0 ? 0 : minDistance;
1953 }
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
VECTOR2I::extended_type ecoord
Definition: seg.h:43
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
VECTOR2I A
Definition: seg.h:48
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.
VECTOR2I B
Definition: seg.h:49

References SEG::A, SEG::B, CIterateSegmentsWithHoles(), and containsSingle().

◆ Subset()

SHAPE_POLY_SET SHAPE_POLY_SET::Subset ( int  aFirstPolygon,
int  aLastPolygon 
)

Return 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 last polygon to be excluded of the returned set.
Returns
a set containing the polygons between aFirstPolygon (included) and aLastPolygon (excluded).

Definition at line 344 of file shape_poly_set.cpp.

345 {
346  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
347 
348  SHAPE_POLY_SET newPolySet;
349 
350  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
351  newPolySet.m_polys.push_back( Polygon( index ) );
352 
353  return newPolySet;
354 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
Represent a set of closed polygons.
POLYGON & Polygon(int aIndex)

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

Referenced by UnitSet().

◆ TotalVertices()

int SHAPE_POLY_SET::TotalVertices ( ) const

Delete aIdx-th polygon from the set.

Definition at line 1856 of file shape_poly_set.cpp.

1857 {
1858  int c = 0;
1859 
1860  for( const POLYGON& poly : m_polys )
1861  {
1862  for( const SHAPE_LINE_CHAIN& path : poly )
1863  c += path.PointCount();
1864  }
1865 
1866  return c;
1867 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

References m_polys, and path.

Referenced by PCB_POINT_EDITOR::buildForPolyOutline(), EDA_SHAPE::Compare(), ZONE::GetNumCorners(), ZONE::HitTest(), InsertVertex(), PCB_POINT_EDITOR::updateItem(), and PCB_POINT_EDITOR::updatePoints().

◆ TriangulatedPolyCount()

unsigned int SHAPE_POLY_SET::TriangulatedPolyCount ( ) const
inline

Return the number of outlines in the set.

Definition at line 654 of file shape_poly_set.h.

References m_triangulatedPolys.

Referenced by ConvertPolygonToTriangles(), KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), operator=(), and SHAPE_POLY_SET().

◆ TriangulatedPolygon()

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

Definition at line 722 of file shape_poly_set.h.

723  {
724  return m_triangulatedPolys[aIndex].get();
725  }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys

References m_triangulatedPolys.

Referenced by ConvertPolygonToTriangles(), KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), operator=(), SHAPE_POLY_SET(), and PNS_KICAD_IFACE_BASE::syncZone().

◆ Type()

SHAPE_TYPE SHAPE_BASE::Type ( ) const
inlineinherited

◆ Unfracture()

void SHAPE_POLY_SET::Unfracture ( POLYGON_MODE  aFastMode)

Return true if the polygon set has any holes.

Definition at line 1249 of file shape_poly_set.cpp.

1250 {
1251  for( POLYGON& path : m_polys )
1253 
1254  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1255 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void unfractureSingle(POLYGON &path)
void Simplify(POLYGON_MODE aFastMode)

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

Referenced by InflateWithLinkedHoles(), PGPartitionFixture::PGPartitionFixture(), and polygon_triangulation_main().

◆ unfractureSingle()

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

Definition at line 1072 of file shape_poly_set.cpp.

1073 {
1074  assert( aPoly.size() == 1 );
1075 
1076  struct EDGE
1077  {
1078  int m_index = 0;
1079  SHAPE_LINE_CHAIN* m_poly = nullptr;
1080  bool m_duplicate = false;
1081 
1082  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
1083  m_index( aIndex ),
1084  m_poly( aPolygon )
1085  {}
1086 
1087  bool compareSegs( const SEG& s1, const SEG& s2 ) const
1088  {
1089  return (s1.A == s2.B && s1.B == s2.A);
1090  }
1091 
1092  bool operator==( const EDGE& aOther ) const
1093  {
1094  return compareSegs( m_poly->CSegment( m_index ),
1095  aOther.m_poly->CSegment( aOther.m_index ) );
1096  }
1097 
1098  bool operator!=( const EDGE& aOther ) const
1099  {
1100  return !compareSegs( m_poly->CSegment( m_index ),
1101  aOther.m_poly->CSegment( aOther.m_index ) );
1102  }
1103 
1104  struct HASH
1105  {
1106  std::size_t operator()( const EDGE& aEdge ) const
1107  {
1108  const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1109 
1110  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
1111  }
1112  };
1113  };
1114 
1115  struct EDGE_LIST_ENTRY
1116  {
1117  int index;
1118  EDGE_LIST_ENTRY* next;
1119  };
1120 
1121  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1122 
1123  SHAPE_LINE_CHAIN lc = aPoly[0];
1124  lc.Simplify();
1125 
1126  auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.SegmentCount() );
1127 
1128  for( int i = 0; i < lc.SegmentCount(); i++ )
1129  {
1130  edgeList[i].index = i;
1131  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
1132  }
1133 
1134  std::unordered_set<EDGE_LIST_ENTRY*> queue;
1135 
1136  for( int i = 0; i < lc.SegmentCount(); i++ )
1137  {
1138  EDGE e( &lc, i );
1139  uniqueEdges.insert( e );
1140  }
1141 
1142  for( int i = 0; i < lc.SegmentCount(); i++ )
1143  {
1144  EDGE e( &lc, i );
1145  auto it = uniqueEdges.find( e );
1146 
1147  if( it != uniqueEdges.end() && it->m_index != i )
1148  {
1149  int e1 = it->m_index;
1150  int e2 = i;
1151 
1152  if( e1 > e2 )
1153  std::swap( e1, e2 );
1154 
1155  int e1_prev = e1 - 1;
1156 
1157  if( e1_prev < 0 )
1158  e1_prev = lc.SegmentCount() - 1;
1159 
1160  int e2_prev = e2 - 1;
1161 
1162  if( e2_prev < 0 )
1163  e2_prev = lc.SegmentCount() - 1;
1164 
1165  int e1_next = e1 + 1;
1166 
1167  if( e1_next == lc.SegmentCount() )
1168  e1_next = 0;
1169 
1170  int e2_next = e2 + 1;
1171 
1172  if( e2_next == lc.SegmentCount() )
1173  e2_next = 0;
1174 
1175  edgeList[e1_prev].next = &edgeList[ e2_next ];
1176  edgeList[e2_prev].next = &edgeList[ e1_next ];
1177  edgeList[i].next = nullptr;
1178  edgeList[it->m_index].next = nullptr;
1179  }
1180  }
1181 
1182  for( int i = 0; i < lc.SegmentCount(); i++ )
1183  {
1184  if( edgeList[i].next )
1185  queue.insert( &edgeList[i] );
1186  }
1187 
1188  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
1189 
1190  int n = 0;
1191  int outline = -1;
1192 
1193  POLYGON result;
1194 
1195  while( queue.size() )
1196  {
1197  EDGE_LIST_ENTRY* e_first = *queue.begin();
1198  EDGE_LIST_ENTRY* e = e_first;
1199  int cnt = 0;
1200 
1201  do
1202  {
1203  edgeBuf[cnt++] = e;
1204  e = e->next;
1205  } while( e && e != e_first );
1206 
1207  SHAPE_LINE_CHAIN outl;
1208 
1209  for( int i = 0; i < cnt; i++ )
1210  {
1211  VECTOR2I p = lc.CPoint( edgeBuf[i]->index );
1212  outl.Append( p );
1213  queue.erase( edgeBuf[i] );
1214  }
1215 
1216  outl.SetClosed( true );
1217 
1218  bool cw = outl.Area() > 0.0;
1219 
1220  if( cw )
1221  outline = n;
1222 
1223  result.push_back( outl );
1224  n++;
1225  }
1226 
1227  if( outline > 0 )
1228  std::swap( result[0], result[outline] );
1229 
1230  aPoly = result;
1231 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
CITER next(CITER it)
Definition: ptree.cpp:126
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
Define a general 2D-vector/point.
Definition: vector2d.h:61
bool operator!=(const SYMBOL_LIB &aLibrary, const wxString &aName)
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
bool operator==(const SYMBOL_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
VECTOR2I A
Definition: seg.h:48
VECTOR2I B
Definition: seg.h:49

References SEG::A, SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::Area(), SEG::B, SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), next(), operator!=(), operator==(), SHAPE_LINE_CHAIN::SegmentCount(), SHAPE_LINE_CHAIN::SetClosed(), SHAPE_LINE_CHAIN::Simplify(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by Unfracture().

◆ UnitSet()

SHAPE_POLY_SET SHAPE_POLY_SET::UnitSet ( int  aPolygonIndex)
inline

Return the reference to aHole-th hole in the aIndex-th outline.

Definition at line 700 of file shape_poly_set.h.

References Subset().

◆ VertexCount()

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

Return the number of points in the shape poly set.

mainly for reports

Definition at line 298 of file shape_poly_set.cpp.

299 {
300  if( m_polys.size() == 0 ) // Empty poly set
301  return 0;
302 
303  if( aOutline < 0 ) // Use last outline
304  aOutline += m_polys.size();
305 
306  int idx;
307 
308  if( aHole < 0 )
309  idx = 0;
310  else
311  idx = aHole + 1;
312 
313  if( aOutline >= (int) m_polys.size() ) // not existing outline
314  return 0;
315 
316  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
317  return 0;
318 
319  return m_polys[aOutline][idx].PointCount();
320 }

References m_polys.

Referenced by Collide(), D_CODE::DrawFlashedPolygon(), GERBER_FILE_IMAGE::Execute_G_Command(), EDA_SHAPE::GetPointCount(), FABMASTER::loadFootprints(), FABMASTER::loadShapePolySet(), and FABMASTER::loadZone().

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_BASE::m_type
protectedinherited

< type of our shape

Definition at line 110 of file shape.h.

Referenced by SHAPE::IsNull(), and SHAPE_BASE::Type().

◆ MIN_PRECISION_IU

const int SHAPE::MIN_PRECISION_IU = 4
staticinherited

This is the minimum precision for all the points in a shape.

Definition at line 122 of file shape.h.

Referenced by BOOST_AUTO_TEST_CASE(), DIRECTION_45::BuildInitialTrace(), CompareLength(), CIRCLE::Contains(), EDIT_TOOL::FilletTracks(), and CIRCLE::IntersectLine().


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