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 KIFONT::OUTLINE_GLYPH

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< const SHAPE * > &aSubshapes) const 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...
 
SHAPE_POLY_SET CloneDropTriangulation () const
 Creates a new empty polygon in the set and returns its index. 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 (const EDA_ANGLE &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=nullptr, 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=nullptr, 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)
 Delete aIdx-th polygon and its triangulation data from the set. More...
 
void DeletePolygonAndTriangulationData (int aIdx, bool aUpdateHash=true)
 
void UpdateTriangulationDataHash ()
 
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...
 
int GetClearance (const SHAPE *aOther) const
 Return the actual minimum distance between two shapes. 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...
 
wxString TypeName () const
 

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  DROP_TRIANGULATION_FLAG { SINGLETON }
 
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...
 

Private Member Functions

 SHAPE_POLY_SET (const SHAPE_POLY_SET &aOther, DROP_TRIANGULATION_FLAG)
 
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, ... and polygon simplification (merging overlapping polygons). 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

std::vector< POLYGONm_polys
 
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
 
bool m_triangulationValid = false
 
MD5_HASH m_hash
 
std::list< FACET * > facets
 

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 249 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.

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

1432 {
1433 CHAMFERED,
1434 FILLETED
1435 };

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

982 {
991 };
@ 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.
@ ROUND_ALL_CORNERS
All angles are rounded.

◆ DROP_TRIANGULATION_FLAG

Enumerator
SINGLETON 

Definition at line 1381 of file shape_poly_set.h.

◆ POLYGON_MODE

Operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak polygon if aFastMode is PM_STRICTLY_SIMPLE (false) (default) the result is (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 948 of file shape_poly_set.h.

949 {
950 PM_FAST = true,
951 PM_STRICTLY_SIMPLE = false
952 };

Constructor & Destructor Documentation

◆ SHAPE_POLY_SET() [1/5]

SHAPE_POLY_SET::SHAPE_POLY_SET ( )

Definition at line 63 of file shape_poly_set.cpp.

63 :
65{
66}
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition: shape.h:133
@ SH_POLY_SET
set of polygons (with holes, etc.)
Definition: shape.h:49

Referenced by Clone(), and CloneDropTriangulation().

◆ SHAPE_POLY_SET() [2/5]

SHAPE_POLY_SET::SHAPE_POLY_SET ( const BOX2D aRect)

Definition at line 69 of file shape_poly_set.cpp.

69 :
71{
72 NewOutline();
73 Append( VECTOR2I( aRect.GetLeft(), aRect.GetTop() ) );
74 Append( VECTOR2I( aRect.GetRight(), aRect.GetTop() ) );
75 Append( VECTOR2I( aRect.GetRight(), aRect.GetBottom() ) );
76 Append( VECTOR2I( aRect.GetLeft(), aRect.GetBottom() ) );
77 Outline( 0 ).SetClosed( true );
78}
coord_type GetTop() const
Definition: box2.h:194
coord_type GetRight() const
Definition: box2.h:189
coord_type GetLeft() const
Definition: box2.h:193
coord_type GetBottom() const
Definition: box2.h:190
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
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...
SHAPE_LINE_CHAIN & Outline(int aIndex)
int NewOutline()
Creates a new hole in a given outline.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

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/5]

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

81 :
83{
84 AddOutline( aOutline );
85}
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.

References AddOutline().

◆ SHAPE_POLY_SET() [4/5]

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

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

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

◆ ~SHAPE_POLY_SET()

SHAPE_POLY_SET::~SHAPE_POLY_SET ( )

Definition at line 122 of file shape_poly_set.cpp.

123{
124}

◆ SHAPE_POLY_SET() [5/5]

SHAPE_POLY_SET::SHAPE_POLY_SET ( const SHAPE_POLY_SET aOther,
DROP_TRIANGULATION_FLAG   
)
private

Definition at line 112 of file shape_poly_set.cpp.

112 :
113 SHAPE( aOther ),
114 m_polys( aOther.m_polys )
115{
116 m_triangulationValid = false;
117 m_hash = MD5_HASH();
118 m_triangulatedPolys.clear();
119}

References m_hash, m_triangulatedPolys, and m_triangulationValid.

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

512{
513 assert( m_polys.size() );
514
515 if( aOutline < 0 )
516 aOutline += m_polys.size();
517
518 assert( aOutline < (int)m_polys.size() );
519
520 POLYGON& poly = m_polys[aOutline];
521
522 assert( poly.size() );
523
524 poly.push_back( aHole );
525
526 return poly.size() - 2;
527}
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(), ALTIUM_PCB::ParseRegions6Data(), and PCB_PARSER::parseRenderCache().

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

498{
499 assert( aOutline.IsClosed() );
500
501 POLYGON poly;
502
503 poly.push_back( aOutline );
504
505 m_polys.push_back( poly );
506
507 return m_polys.size() - 1;
508}
bool IsClosed() const override

References SHAPE_LINE_CHAIN::IsClosed(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE::AddPolygon(), BOARD_ADAPTER::addText(), BOOST_AUTO_TEST_CASE(), buildBoardBoundingBoxPoly(), KI_TEST::BuildHollowSquare(), KI_TEST::BuildPolyset(), KI_TEST::CommonTestData::CommonTestData(), ConvertPolygonToBlocks(), ALTIUM_PCB::ConvertShapeBasedRegions6ToBoardItem(), ALTIUM_PCB::ConvertShapeBasedRegions6ToFootprintItem(), FOOTPRINT::CoverageRatio(), BOARD_ADAPTER::createPadWithMargin(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::draw(), ZONE_FILLER::fillCopperZone(), GEOM_TEST::FilletPolySet(), FOOTPRINT::GetBoundingHull(), PNS::SOLID::HoleHull(), PNS::SOLID::Hull(), IteratorFixture::IteratorFixture(), DSN::SPECCTRA_DB::makeIMAGE(), CONVERT_TOOL::makePolysFromChainedSegs(), PAD::MergePrimitivesAsPolygon(), NormalizeAreaOutlines(), EAGLE_PLUGIN::packagePolygon(), ALTIUM_PCB::ParsePolygons6Data(), ALTIUM_PCB::ParseRegions6Data(), PCB_PARSER::parseRenderCache(), partitionPolyIntoRegularCellGrid(), ZONE_CREATE_HELPER::performZoneCutout(), BRDITEMS_PLOTTER::PlotFootprintShape(), BRDITEMS_PLOTTER::PlotPcbText(), PlotStandardLayer(), DRC_TEST_PROVIDER_SLIVER_CHECKER::Run(), SHAPE_POLY_SET(), TestConcaveSquareFillet(), and TestSquareFillet().

◆ Append() [1/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 1700 of file shape_poly_set.cpp.

1701{
1702 m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1703}

References m_polys.

◆ Append() [2/4]

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

Definition at line 1706 of file shape_poly_set.cpp.

1707{
1708 Append( aP.x, aP.y, aOutline, aHole );
1709}

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

◆ Append() [3/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 247 of file shape_poly_set.cpp.

248{
249 assert( m_polys.size() );
250
251 if( aOutline < 0 )
252 aOutline += m_polys.size();
253
254 int idx;
255
256 if( aHole < 0 )
257 idx = 0;
258 else
259 idx = aHole + 1;
260
261 assert( aOutline < (int) m_polys.size() );
262 assert( idx < (int) m_polys[aOutline].size() );
263
264 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
265
266 return m_polys[aOutline][idx].PointCount();
267}

References m_polys.

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), ZONE_FILLER::addKnockout(), AR_AUTOPLACER::addPad(), PAD::AddPrimitivePoly(), Append(), ZONE::AppendCorner(), BOARD::BOARD(), BOOST_AUTO_TEST_CASE(), BuildBoardPolygonOutlines(), ZONE_FILLER::buildCopperItemClearances(), BuildFootprintPolygonOutlines(), TEARDROP_MANAGER::ComputePointsOnPadVia(), ConvertOutlineToPolygon(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CornerListToPolygon(), BITMAPCONV_INFO::createOutputData(), BOARD_ADAPTER::createPadWithMargin(), CONVERT_TOOL::CreatePolys(), TEARDROP_MANAGER::createTeardrop(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), 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(), CONVERT_TOOL::makePolysFromGraphics(), 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(), EDA_SHAPE::TransformShapeWithClearanceToPolygon(), FP_TEXT::TransformShapeWithClearanceToPolygon(), FP_TEXTBOX::TransformShapeWithClearanceToPolygon(), PCB_TEXTBOX::TransformShapeWithClearanceToPolygon(), ZONE::TransformShapeWithClearanceToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), ZONE::TransformSmoothedOutlineToPolygon(), ZONE::TransformSolidAreasShapesToPolygon(), FP_TEXT::TransformTextShapeWithClearanceToPolygon(), FP_TEXTBOX::TransformTextShapeWithClearanceToPolygon(), PCB_TEXT::TransformTextShapeWithClearanceToPolygon(), PCB_TEXTBOX::TransformTextShapeWithClearanceToPolygon(), TransformTrapezoidToPolygon(), PCB_DIM_ALIGNED::updateGeometry(), PCB_DIM_ORTHOGONAL::updateGeometry(), PCB_DIM_RADIAL::updateGeometry(), PCB_DIM_LEADER::updateGeometry(), and EE_POINT_EDITOR::updateParentItem().

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

271{
272 assert( m_polys.size() );
273
274 if( aOutline < 0 )
275 aOutline += m_polys.size();
276
277 int idx;
278
279 if( aHole < 0 )
280 idx = 0;
281 else
282 idx = aHole + 1;
283
284 assert( aOutline < (int) m_polys.size() );
285 assert( idx < (int) m_polys[aOutline].size() );
286
287 m_polys[aOutline][idx].Append( aArc );
288
289 return m_polys[aOutline][idx].PointCount();
290}

References m_polys.

◆ ArcCount()

int SHAPE_POLY_SET::ArcCount ( ) const

Appends all the arcs in this polyset to aArcBuffer.

Definition at line 546 of file shape_poly_set.cpp.

547{
548 int retval = 0;
549
550 for( const POLYGON& poly : m_polys )
551 {
552 for( size_t i = 0; i < poly.size(); i++ )
553 retval += poly[i].ArcCount();
554 }
555
556 return retval;
557}
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.

References ArcCount(), and m_polys.

Referenced by ArcCount(), and booleanOp().

◆ Area()

double SHAPE_POLY_SET::Area ( )

Count the number of arc shapes present.

Definition at line 530 of file shape_poly_set.cpp.

531{
532 double area = 0.0;
533
534 for( int i = 0; i < OutlineCount(); i++ )
535 {
536 area += Outline( i ).Area();
537
538 for( int j = 0; j < HoleCount( i ); j++ )
539 area -= Hole( i, j ).Area();
540 }
541
542 return area;
543}
double Area(bool aAbsolute=true) const
Return the area of this chain.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
int OutlineCount() const
Return the number of vertices in a given outline/hole.

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

Referenced by BOOST_AUTO_TEST_CASE(), ZONE::CalculateOutlineArea(), CADSTAR_PCB_ARCHIVE_LOADER::calculateZonePriorities(), polygonArea(), and DRC_TEST_PROVIDER_TEXT_DIMS::Run().

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

1414{
1415 BOX2I bb;
1416
1417 for( unsigned i = 0; i < m_polys.size(); i++ )
1418 {
1419 if( i == 0 )
1420 bb = m_polys[i][0].BBox();
1421 else
1422 bb.Merge( m_polys[i][0].BBox() );
1423 }
1424
1425 bb.Inflate( aClearance );
1426 return bb;
1427}
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:588
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.

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

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), BBox(), KIFONT::OUTLINE_GLYPH::BoundingBox(), DRAWING_TOOL::DrawBoardCharacteristics(), PCB_BASE_FRAME::FocusOnItems(), APERTURE_MACRO::GetApertureMacroShape(), PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::GetBoundingBox(), DS_DRAW_ITEM_POLYPOLYGONS::GetBoundingBox(), ZONE::GetBoundingBox(), partitionPolyIntoRegularCellGrid(), KIGFX::VIEW::SetCenter(), BOARD::TestZoneIntersection(), KIGFX::PREVIEW::CENTRELINE_RECT_ITEM::ViewBBox(), and KIGFX::PREVIEW::POLYGON_ITEM::ViewBBox().

◆ BBoxFromCaches()

const BOX2I SHAPE_POLY_SET::BBoxFromCaches ( ) const

Definition at line 1430 of file shape_poly_set.cpp.

1431{
1432 BOX2I bb;
1433
1434 for( unsigned i = 0; i < m_polys.size(); i++ )
1435 {
1436 if( i == 0 )
1437 bb = *m_polys[i][0].GetCachedBBox();
1438 else
1439 bb.Merge( *m_polys[i][0].GetCachedBBox() );
1440 }
1441
1442 return bb;
1443}

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

Referenced by DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances(), and DRC_TEST_PROVIDER_COURTYARD_CLEARANCE_ON_MOVE::testCourtyardClearances().

◆ BooleanAdd() [1/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 713 of file shape_poly_set.cpp.

715{
716 booleanOp( ClipperLib::ctUnion, a, b, aFastMode );
717}
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, ... and polygon simplification...

References booleanOp().

◆ BooleanAdd() [2/2]

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

◆ BooleanIntersection() [1/2]

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

Definition at line 727 of file shape_poly_set.cpp.

729{
730 booleanOp( ClipperLib::ctIntersection, a, b, aFastMode );
731}

References booleanOp().

◆ BooleanIntersection() [2/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 707 of file shape_poly_set.cpp.

708{
709 booleanOp( ClipperLib::ctIntersection, b, aFastMode );
710}

References booleanOp().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), BOOST_AUTO_TEST_CASE(), ZONE::BuildSmoothedPoly(), CADSTAR_PCB_ARCHIVE_LOADER::calculateZonePriorities(), TEARDROP_MANAGER::ComputePointsOnPadVia(), ConvertPolygonToBlocks(), ZONE_FILLER::fillCopperZone(), PCB_BASE_FRAME::FocusOnItems(), isCopperOutside(), PAD_TOOL::RecombinePad(), RENDER_3D_OPENGL::reload(), and TransformOvalToPolygon().

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

585{
586 booleanOp( aType, *this, aOtherShape, aFastMode );
587}

References booleanOp().

Referenced by BooleanAdd(), BooleanIntersection(), booleanOp(), 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 590 of file shape_poly_set.cpp.

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

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

◆ BooleanSubtract() [1/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 720 of file shape_poly_set.cpp.

722{
723 booleanOp( ClipperLib::ctDifference, a, b, aFastMode );
724}

References booleanOp().

◆ BooleanSubtract() [2/2]

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

1786{
1787 for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1788 {
1789 COutline( polygonIdx ).GenerateBBoxCache();
1790
1791 for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1792 CHole( polygonIdx, holeIdx ).GenerateBBoxCache();
1793 }
1794}
void GenerateBBoxCache() const
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
const SHAPE_LINE_CHAIN & COutline(int aIndex) const

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

Referenced by ZONE_FILLER::fillCopperZone().

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

2608{
2609 ClipperLib::Clipper clipper;
2610 ClipperLib::PolyTree tree;
2611
2612 // fixme: do we need aReverseOrientation?
2613
2614 for( const SHAPE_LINE_CHAIN& path : aPaths )
2615 {
2616 ClipperLib::Path lc;
2617
2618 for( int i = 0; i < path.PointCount(); i++ )
2619 {
2620 lc.emplace_back( path.CPoint( i ).x, path.CPoint( i ).y );
2621 }
2622
2623 clipper.AddPath( lc, ClipperLib::ptSubject, true );
2624 }
2625
2626 clipper.StrictlySimple( true );
2627 clipper.Execute( ClipperLib::ctUnion, tree,
2628 aEvenOdd ? ClipperLib::pftEvenOdd : ClipperLib::pftNonZero,
2629 ClipperLib::pftNonZero );
2630 SHAPE_POLY_SET result;
2631
2632 for( ClipperLib::PolyNode* n = tree.GetFirst(); n; n = n->GetNext() )
2633 {
2634 if( !n->IsHole() )
2635 {
2636 int outl = result.NewOutline();
2637
2638 for( unsigned int i = 0; i < n->Contour.size(); i++ )
2639 result.Outline( outl ).Append( n->Contour[i].X, n->Contour[i].Y );
2640
2641 for( unsigned int i = 0; i < n->Childs.size(); i++ )
2642 {
2643 int outh = result.NewHole( outl );
2644 for( unsigned int j = 0; j < n->Childs[i]->Contour.size(); j++ )
2645 {
2646 result.Hole( outl, outh )
2647 .Append( n->Childs[i]->Contour[j].X, n->Childs[i]->Contour[j].Y );
2648 }
2649 }
2650 }
2651 }
2652
2653 return result;
2654}
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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.
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.

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

2379{
2380 bool recalculate = !m_hash.IsValid();
2381 MD5_HASH hash;
2382
2384 recalculate = true;
2385
2386 if( !recalculate )
2387 {
2388 hash = checksum();
2389
2390 if( m_hash != hash )
2391 {
2392 m_hash = hash;
2393 recalculate = true;
2394 }
2395 }
2396
2397 if( !recalculate )
2398 return;
2399
2400 auto triangulate =
2401 []( SHAPE_POLY_SET& polySet, int forOutline,
2402 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest )
2403 {
2404 bool triangulationValid = false;
2405
2406 while( polySet.OutlineCount() > 0 )
2407 {
2408 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
2409 dest.erase( dest.end() - 1 );
2410
2411 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
2412 PolygonTriangulation tess( *dest.back() );
2413
2414 // If the tessellation fails, we re-fracture the polygon, which will
2415 // first simplify the system before fracturing and removing the holes
2416 // This may result in multiple, disjoint polygons.
2417 if( !tess.TesselatePolygon( polySet.Polygon( 0 ).front() ) )
2418 {
2419 polySet.Fracture( PM_FAST );
2420 triangulationValid = false;
2421 continue;
2422 }
2423
2424 polySet.DeletePolygon( 0 );
2425 triangulationValid = true;
2426 }
2427
2428 return triangulationValid;
2429 };
2430
2431 m_triangulatedPolys.clear();
2432 m_triangulationValid = true;
2433
2434 if( aPartition )
2435 {
2436 for( int ii = 0; ii < OutlineCount(); ++ii )
2437 {
2438 // This partitions into regularly-sized grids (1cm in Pcbnew)
2439 SHAPE_POLY_SET flattened( Outline( ii ) );
2440 flattened.ClearArcs();
2441 SHAPE_POLY_SET partitions = partitionPolyIntoRegularCellGrid( flattened, 1e7 );
2442
2443 m_triangulationValid &= triangulate( partitions, ii, m_triangulatedPolys );
2444 }
2445 }
2446 else
2447 {
2448 SHAPE_POLY_SET tmpSet( *this );
2449
2450 if( tmpSet.HasHoles() )
2451 tmpSet.Fracture( PM_FAST );
2452
2453 m_triangulationValid = triangulate( tmpSet, -1, m_triangulatedPolys );
2454 }
2455
2457 m_hash = checksum();
2458}
bool IsValid() const
Definition: md5_hash.h:24
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
void DeletePolygon(int aIdx)
Delete aIdx-th polygon and its triangulation data from the set.
POLYGON & Polygon(int aIndex)
MD5_HASH checksum() const
static SHAPE_POLY_SET partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize)

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

Referenced by FOOTPRINT::BuildCourtyardCaches(), ZONE::CacheTriangulation(), Collide(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::draw(), Mirror(), Rotate(), PNS_KICAD_IFACE_BASE::syncZone(), and KIFONT::OUTLINE_GLYPH::Triangulate().

◆ 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}
IFSG_COLORS is the wrapper for SGCOLORS.
Definition: ifsg_colors.h:42
IFSG_COORDINDEX is the wrapper for SGCOORDINDEX.
IFSG_COORDS is the wrapper for SGCOORDS.
Definition: ifsg_coords.h:41
IFSG_FACESET is the wrapper for the SGFACESET class.
Definition: ifsg_faceset.h:41
IFSG_NORMALS is the wrapper for the SGNORMALS class.
Definition: ifsg_normals.h:41
IFSG_SHAPE is the wrapper for the SGSHAPE class.
Definition: ifsg_shape.h:41
double z
Definition: sg_base.h:72
double x
Definition: sg_base.h:70
double y
Definition: sg_base.h:71
std::list< FACET * > facets
Definition: wrlfacet.h:143
SGLIB_API SGNODE * GetSGNodeParent(SGNODE *aNode)
Definition: ifsg_api.cpp:494

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 WRL2FACESET::TranslateToSG(), X3DIFACESET::TranslateToSG(), and WRL1FACESET::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 229 of file shape.h.

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

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

2083{
2084 SHAPE_POLY_SET chamfered;
2085
2086 for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
2087 chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
2088
2089 return chamfered;
2090}
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 2104 of file shape_poly_set.cpp.

2107{
2108 // Null segments create serious issues in calculations. Remove them:
2110
2111 SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
2113
2114 // If the chamfering distance is zero, then the polygon remain intact.
2115 if( aDistance == 0 )
2116 {
2117 return currentPoly;
2118 }
2119
2120 // Iterate through all the contours (outline and holes) of the polygon.
2121 for( SHAPE_LINE_CHAIN& currContour : currentPoly )
2122 {
2123 // Generate a new contour in the new polygon
2124 SHAPE_LINE_CHAIN newContour;
2125
2126 // Iterate through the vertices of the contour
2127 for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2128 {
2129 // Current vertex
2130 int x1 = currContour.CPoint( currVertex ).x;
2131 int y1 = currContour.CPoint( currVertex ).y;
2132
2133 // Indices for previous and next vertices.
2134 int prevVertex;
2135 int nextVertex;
2136
2137 // Previous and next vertices indices computation. Necessary to manage the edge cases.
2138
2139 // Previous vertex is the last one if the current vertex is the first one
2140 prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2141
2142 // next vertex is the first one if the current vertex is the last one.
2143 nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
2144
2145 // Previous vertex computation
2146 double xa = currContour.CPoint( prevVertex ).x - x1;
2147 double ya = currContour.CPoint( prevVertex ).y - y1;
2148
2149 // Next vertex computation
2150 double xb = currContour.CPoint( nextVertex ).x - x1;
2151 double yb = currContour.CPoint( nextVertex ).y - y1;
2152
2153 // Compute the new distances
2154 double lena = hypot( xa, ya );
2155 double lenb = hypot( xb, yb );
2156
2157 // Make the final computations depending on the mode selected, chamfered or filleted.
2158 if( aMode == CORNER_MODE::CHAMFERED )
2159 {
2160 double distance = aDistance;
2161
2162 // Chamfer one half of an edge at most
2163 if( 0.5 * lena < distance )
2164 distance = 0.5 * lena;
2165
2166 if( 0.5 * lenb < distance )
2167 distance = 0.5 * lenb;
2168
2169 int nx1 = KiROUND( distance * xa / lena );
2170 int ny1 = KiROUND( distance * ya / lena );
2171
2172 newContour.Append( x1 + nx1, y1 + ny1 );
2173
2174 int nx2 = KiROUND( distance * xb / lenb );
2175 int ny2 = KiROUND( distance * yb / lenb );
2176
2177 newContour.Append( x1 + nx2, y1 + ny2 );
2178 }
2179 else // CORNER_MODE = FILLETED
2180 {
2181 double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
2182
2183 double radius = aDistance;
2184 double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
2185
2186 // Do nothing in case of parallel edges
2187 if( std::isinf( denom ) )
2188 continue;
2189
2190 // Limit rounding distance to one half of an edge
2191 if( 0.5 * lena * denom < radius )
2192 radius = 0.5 * lena * denom;
2193
2194 if( 0.5 * lenb * denom < radius )
2195 radius = 0.5 * lenb * denom;
2196
2197 // Calculate fillet arc absolute center point (xc, yx)
2198 double k = radius / sqrt( .5 * ( 1 - cosine ) );
2199 double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
2200 ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
2201 double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
2202 double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
2203
2204 // Calculate arc start and end vectors
2205 k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
2206 double xs = x1 + k * xa / lena - xc;
2207 double ys = y1 + k * ya / lena - yc;
2208 double xe = x1 + k * xb / lenb - xc;
2209 double ye = y1 + k * yb / lenb - yc;
2210
2211 // Cosine of arc angle
2212 double argument = ( xs * xe + ys * ye ) / ( radius * radius );
2213
2214 // Make sure the argument is in [-1,1], interval in which the acos function is
2215 // defined
2216 if( argument < -1 )
2217 argument = -1;
2218 else if( argument > 1 )
2219 argument = 1;
2220
2221 double arcAngle = acos( argument );
2222 int segments = GetArcToSegmentCount( radius, aErrorMax,
2223 EDA_ANGLE( arcAngle, RADIANS_T ) );
2224
2225 double deltaAngle = arcAngle / segments;
2226 double startAngle = atan2( -ys, xs );
2227
2228 // Flip arc for inner corners
2229 if( xa * yb - ya * xb <= 0 )
2230 deltaAngle *= -1;
2231
2232 double nx = xc + xs;
2233 double ny = yc + ys;
2234
2235 newContour.Append( KiROUND( nx ), KiROUND( ny ) );
2236
2237 // Store the previous added corner to make a sanity check
2238 int prevX = KiROUND( nx );
2239 int prevY = KiROUND( ny );
2240
2241 for( int j = 0; j < segments; j++ )
2242 {
2243 nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2244 ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2245
2246 // Sanity check: the rounding can produce repeated corners; do not add them.
2247 if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
2248 {
2249 newContour.Append( KiROUND( nx ), KiROUND( ny ) );
2250 prevX = KiROUND( nx );
2251 prevY = KiROUND( ny );
2252 }
2253 }
2254 }
2255 }
2256
2257 // Close the current contour and add it the new polygon
2258 newContour.SetClosed( true );
2259 newPoly.push_back( newContour );
2260 }
2261
2262 return newPoly;
2263}
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
@ RADIANS_T
Definition: eda_angle.h:32
int GetArcToSegmentCount(int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
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:80

References SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::CPoint(), distance(), GetArcToSegmentCount(), KiROUND(), Polygon(), RADIANS_T, 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 1933 of file shape_poly_set.cpp.

1934{
1935 return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
1936}
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 2461 of file shape_poly_set.cpp.

2462{
2463 MD5_HASH hash;
2464
2465 hash.Hash( m_polys.size() );
2466
2467 for( const POLYGON& outline : m_polys )
2468 {
2469 hash.Hash( outline.size() );
2470
2471 for( const SHAPE_LINE_CHAIN& lc : outline )
2472 {
2473 hash.Hash( lc.PointCount() );
2474
2475 for( int i = 0; i < lc.PointCount(); i++ )
2476 {
2477 hash.Hash( lc.CPoint( i ).x );
2478 hash.Hash( lc.CPoint( i ).y );
2479 }
2480 }
2481 }
2482
2483 hash.Finalize();
2484
2485 return hash;
2486}
void Finalize()
Definition: md5_hash.cpp:78
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66

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

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

◆ CHole()

◆ CIterate() [1/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( ) const
inline

Definition at line 830 of file shape_poly_set.h.

831 {
832 return CIterate( 0, OutlineCount() - 1 );
833 }
CONST_ITERATOR CIterate() const

References CIterate(), and OutlineCount().

Referenced by CIterate(), and CIterateWithHoles().

◆ CIterate() [2/3]

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

Definition at line 806 of file shape_poly_set.h.

807 {
808 CONST_ITERATOR iter;
809
810 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
811 iter.m_currentPolygon = aFirst;
812 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
813 iter.m_currentContour = 0;
814 iter.m_currentVertex = 0;
815 iter.m_iterateHoles = aIterateHoles;
816
817 return iter;
818 }
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() [3/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aOutline) const
inline

Definition at line 820 of file shape_poly_set.h.

821 {
822 return CIterate( aOutline, aOutline );
823 }

References CIterate().

◆ CIterateSegments() [1/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 911 of file shape_poly_set.h.

References CIterateSegments(), and OutlineCount().

Referenced by CIterateSegments(), and CIterateSegmentsWithHoles().

◆ CIterateSegments() [2/3]

◆ CIterateSegments() [3/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 899 of file shape_poly_set.h.

References CIterateSegments().

◆ 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 929 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 935 of file shape_poly_set.h.

936 {
937 return CIterateSegments( aOutline, aOutline, true );
938 }
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 ( ) const
inline

Definition at line 835 of file shape_poly_set.h.

836 {
837 return CIterate( 0, OutlineCount() - 1, true );
838 }

References CIterate(), and OutlineCount().

Referenced by CollideVertex().

◆ CIterateWithHoles() [2/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( int  aOutline) const
inline

Definition at line 825 of file shape_poly_set.h.

826 {
827 return CIterate( aOutline, aOutline, true );
828 }

References CIterate().

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

◆ ClearArcs()

void SHAPE_POLY_SET::ClearArcs ( )

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

Definition at line 573 of file shape_poly_set.cpp.

574{
575 for( POLYGON& poly : m_polys )
576 {
577 for( size_t i = 0; i < poly.size(); i++ )
578 poly[i].ClearArcs();
579 }
580}
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)

References ClearArcs(), and m_polys.

Referenced by BOOST_AUTO_TEST_CASE(), ZONE::BuildSmoothedPoly(), CacheTriangulation(), ClearArcs(), 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

Reimplemented from SHAPE.

Definition at line 127 of file shape_poly_set.cpp.

128{
129 return new SHAPE_POLY_SET( *this );
130}

References SHAPE_POLY_SET().

◆ CloneDropTriangulation()

◆ Collide() [1/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 1463 of file shape_poly_set.cpp.

1465{
1466 VECTOR2I nearest;
1467 ecoord dist_sq = SquaredDistance( aSeg, 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}
static SEG::ecoord Square(int a)
Definition: seg.h:123
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().

◆ Collide() [2/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_COMPOUND, SHAPE_RECT, and SHAPE_SEGMENT.

Definition at line 1109 of file shape_collisions.cpp.

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

References collideShapes().

◆ Collide() [3/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 1508 of file shape_poly_set.cpp.

1510{
1511 // A couple of simple cases are worth trying before we fall back on triangulation.
1512
1513 if( aShape->Type() == SH_SEGMENT )
1514 {
1515 const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
1516 int extra = segment->GetWidth() / 2;
1517
1518 if( Collide( segment->GetSeg(), aClearance + extra, aActual, aLocation ) )
1519 {
1520 if( aActual )
1521 *aActual = std::max( 0, *aActual - extra );
1522
1523 return true;
1524 }
1525
1526 return false;
1527 }
1528
1529 if( aShape->Type() == SH_CIRCLE )
1530 {
1531 const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
1532 int extra = circle->GetRadius();
1533
1534 if( Collide( circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
1535 {
1536 if( aActual )
1537 *aActual = std::max( 0, *aActual - extra );
1538
1539 return true;
1540 }
1541
1542 return false;
1543 }
1544
1545 const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( false );
1546
1547 int actual = INT_MAX;
1548 VECTOR2I location;
1549
1550 for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
1551 {
1552 for( const TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
1553 {
1554 if( aActual || aLocation )
1555 {
1556 int triActual;
1557 VECTOR2I triLocation;
1558
1559 if( aShape->Collide( &tri, aClearance, &triActual, &triLocation ) )
1560 {
1561 if( triActual < actual )
1562 {
1563 actual = triActual;
1564 location = triLocation;
1565 }
1566 }
1567 }
1568 else // A much faster version of above
1569 {
1570 if( aShape->Collide( &tri, aClearance ) )
1571 return true;
1572 }
1573 }
1574 }
1575
1576 if( actual < INT_MAX )
1577 {
1578 if( aActual )
1579 *aActual = std::max( 0, actual );
1580
1581 if( aLocation )
1582 *aLocation = location;
1583
1584 return true;
1585 }
1586
1587 return false;
1588}
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:95
int GetRadius() const
Definition: shape_circle.h:108
const VECTOR2I GetCenter() const
Definition: shape_circle.h:113
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,...
void CacheTriangulation(bool aPartition=true)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
const SEG & GetSeg() const
int GetWidth() const
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:178
@ SH_CIRCLE
circle
Definition: shape.h:47
@ SH_SEGMENT
line segment
Definition: shape.h:45

References CacheTriangulation(), Collide(), 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 Collide(), collidesWithArea(), collidesWithCourtyard(), DRAWING_TOOL::DrawVia(), ZONE_FILLER::Fill(), EDA_SHAPE::hitTest(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), FOOTPRINT::HitTestAccurate(), PCB_SELECTION_TOOL::hitTestDistance(), DIALOG_PAD_PROPERTIES::padValuesOK(), DRC_TEST_PROVIDER_ANNULAR_WIDTH::Run(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE_ON_MOVE::testCourtyardClearances(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::testItemAgainstZones(), and PCB_TEXT::TextHitTest().

◆ Collide() [4/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 1484 of file shape_poly_set.cpp.

1486{
1487 if( IsEmpty() || VertexCount() == 0 )
1488 return false;
1489
1490 VECTOR2I nearest;
1491 ecoord dist_sq = SquaredDistance( aP, aLocation ? &nearest : nullptr );
1492
1493 if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1494 {
1495 if( aLocation )
1496 *aLocation = nearest;
1497
1498 if( aActual )
1499 *aActual = sqrt( dist_sq );
1500
1501 return true;
1502 }
1503
1504 return false;
1505}
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of points in the shape poly set.
bool IsEmpty() const

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

◆ CollideEdge()

bool SHAPE_POLY_SET::CollideEdge ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex = nullptr,
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 1752 of file shape_poly_set.cpp.

1755{
1756 // Shows whether there was a collision
1757 bool collision = false;
1758 ecoord clearance_squared = SEG::Square( aClearance );
1759
1760 for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
1761 {
1762 const SEG currentSegment = *iterator;
1763 ecoord distance_squared = currentSegment.SquaredDistance( aPoint );
1764
1765 // Check for collisions
1766 if( distance_squared <= clearance_squared )
1767 {
1768 if( !aClosestVertex )
1769 return true;
1770
1771 collision = true;
1772
1773 // Update clearance to look for closer edges
1774 clearance_squared = distance_squared;
1775
1776 // Store the indices that identify the vertex
1777 *aClosestVertex = iterator.GetIndex();
1778 }
1779 }
1780
1781 return collision;
1782}
Definition: seg.h:42
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR

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

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

◆ CollideVertex()

bool SHAPE_POLY_SET::CollideVertex ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex = nullptr,
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 1712 of file shape_poly_set.cpp.

1715{
1716 // Shows whether there was a collision
1717 bool collision = false;
1718
1719 // Difference vector between each vertex and aPoint.
1721 ecoord distance_squared;
1722 ecoord clearance_squared = SEG::Square( aClearance );
1723
1724 for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
1725 {
1726 // Get the difference vector between current vertex and aPoint
1727 delta = *iterator - aPoint;
1728
1729 // Compute distance
1730 distance_squared = delta.SquaredEuclideanNorm();
1731
1732 // Check for collisions
1733 if( distance_squared <= clearance_squared )
1734 {
1735 if( !aClosestVertex )
1736 return true;
1737
1738 collision = true;
1739
1740 // Update clearance to look for closer vertices
1741 clearance_squared = distance_squared;
1742
1743 // Store the indices that identify the vertex
1744 *aClosestVertex = iterator.GetIndex();
1745 }
1746 }
1747
1748 return collision;
1749}
CONST_ITERATOR CIterateWithHoles() const
constexpr int delta

References CIterateWithHoles(), delta, and SEG::Square().

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 point Return true if the set is empty (no polygons at all)

Definition at line 1797 of file shape_poly_set.cpp.

1799{
1800 if( m_polys.empty() )
1801 return false;
1802
1803 // If there is a polygon specified, check the condition against that polygon
1804 if( aSubpolyIndex >= 0 )
1805 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1806
1807 // In any other case, check it against all polygons in the set
1808 for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1809 {
1810 if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1811 return true;
1812 }
1813
1814 return false;
1815}
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 ZONE_FILLER::Fill(), ZONE_FILLER::fillCopperZone(), 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 1853 of file shape_poly_set.cpp.

1855{
1856 // Check that the point is inside the outline
1857 if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1858 {
1859 // Check that the point is not in any of the holes
1860 for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1861 {
1862 const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1863
1864 // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1865 // here as it's meaning would be inverted.
1866 if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1867 return false;
1868 }
1869
1870 return true;
1871 }
1872
1873 return false;
1874}
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.

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

Referenced by Contains(), and SquaredDistanceToPolygon().

◆ COutline()

◆ CPolygon()

◆ CVertex() [1/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 393 of file shape_poly_set.cpp.

394{
396
397 // Assure the passed index references a legal position; abort otherwise
398 if( !GetRelativeIndices( aGlobalIndex, &index ) )
399 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
400
401 return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
402}
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...
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...

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() [2/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 374 of file shape_poly_set.cpp.

375{
376 if( aOutline < 0 )
377 aOutline += m_polys.size();
378
379 int idx;
380
381 if( aHole < 0 )
382 idx = 0;
383 else
384 idx = aHole + 1;
385
386 assert( aOutline < (int) m_polys.size() );
387 assert( idx < (int) m_polys[aOutline].size() );
388
389 return m_polys[aOutline][idx].CPoint( aIndex );
390}

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(), FOOTPRINT::cmp_drawings::operator()(), FOOTPRINT::cmp_zones::operator()(), ZONE::SetCornerPosition(), shapesNeedUpdate(), PCB_POINT_EDITOR::updateItem(), PCB_POINT_EDITOR::updatePoints(), and zonesNeedUpdate().

◆ CVertex() [3/3]

const VECTOR2I & SHAPE_POLY_SET::CVertex ( SHAPE_POLY_SET::VERTEX_INDEX  index) const

Definition at line 405 of file shape_poly_set.cpp.

406{
407 return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
408}
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

◆ DeletePolygon()

void SHAPE_POLY_SET::DeletePolygon ( int  aIdx)

Delete aIdx-th polygon and its triangulation data from the set.

If called with aUpdateHash false, caller must call UpdateTriangulationDataHash().

Definition at line 1666 of file shape_poly_set.cpp.

1667{
1668 m_polys.erase( m_polys.begin() + aIdx );
1669}

References m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), BOOST_AUTO_TEST_CASE(), CacheTriangulation(), ZONE_FILLER::fillCopperZone(), and PlotStandardLayer().

◆ DeletePolygonAndTriangulationData()

void SHAPE_POLY_SET::DeletePolygonAndTriangulationData ( int  aIdx,
bool  aUpdateHash = true 
)

Definition at line 1672 of file shape_poly_set.cpp.

1673{
1674 m_polys.erase( m_polys.begin() + aIdx );
1675
1677 {
1678 for( int ii = m_triangulatedPolys.size() - 1; ii >= 0; --ii )
1679 {
1680 std::unique_ptr<TRIANGULATED_POLYGON>& triangleSet = m_triangulatedPolys[ii];
1681
1682 if( triangleSet->GetSourceOutlineIndex() == aIdx )
1683 m_triangulatedPolys.erase( m_triangulatedPolys.begin() + ii );
1684 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
1685 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
1686 }
1687
1688 if( aUpdateHash )
1689 m_hash = checksum();
1690 }
1691}

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

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

2094{
2095 SHAPE_POLY_SET filleted;
2096
2097 for( size_t idx = 0; idx < m_polys.size(); idx++ )
2098 filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
2099
2100 return filleted;
2101}
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 1939 of file shape_poly_set.cpp.

1941{
1942 return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
1943}

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

1324{
1325 std::stringstream ss;
1326
1327 ss << "SHAPE_LINE_CHAIN poly; \n";
1328
1329 for( unsigned i = 0; i < m_polys.size(); i++ )
1330 {
1331 for( unsigned j = 0; j < m_polys[i].size(); j++ )
1332 {
1333
1334 ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
1335
1336 SHAPE_POLY_SET poly;
1337
1338 if( j == 0 )
1339 {
1340 ss << " poly.AddOutline(tmp); } \n";
1341 }
1342 else
1343 {
1344 ss << " poly.AddHole(tmp); } \n";
1345 }
1346
1347 }
1348 }
1349
1350 return ss.str();
1351}

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

1081{
1082 Simplify( aFastMode ); // remove overlapping holes/degeneracy
1083
1084 for( POLYGON& paths : m_polys )
1085 fractureSingle( paths );
1086}
void fractureSingle(POLYGON &paths)
void Simplify(POLYGON_MODE aFastMode)

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

Referenced by addHoleToPolygon(), PAD::addPadPrimitivesToPolygon(), PAD::AddPrimitivePoly(), BOARD_ADAPTER::addText(), CacheTriangulation(), convertPolygon(), BITMAPCONV_INFO::createOutputData(), KIGFX::PCB_PAINTER::draw(), CADSTAR_PCB_ARCHIVE_LOADER::drawCadstarShape(), CALLBACK_GAL::DrawGlyph(), AR_AUTOPLACER::drawPlacementRoutingMatrix(), EXPORTER_PCB_VRML::ExportStandardLayers(), EXPORTER_PCB_VRML::ExportVrmlSolderMask(), ZONE_FILLER::fillCopperZone(), AR_AUTOPLACER::fillMatrix(), ZONE_FILLER::fillNonCopperZone(), APERTURE_MACRO::GetApertureMacroShape(), InflateWithLinkedHoles(), CADSTAR_PCB_ARCHIVE_LOADER::loadCoppers(), FABMASTER::loadFootprints(), EAGLE_PLUGIN::loadPolygon(), FABMASTER::loadShapePolySet(), ALTIUM_PCB::ParseRegions6Data(), BRDITEMS_PLOTTER::PlotFootprintShape(), BRDITEMS_PLOTTER::PlotPcbShape(), BRDITEMS_PLOTTER::PlotPcbText(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), RENDER_3D_RAYTRACE::Reload(), EDA_SHAPE::SetPolyShape(), TransformRingToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), and ZONE::TransformSmoothedOutlineToPolygon().

◆ fractureSingle()

void SHAPE_POLY_SET::fractureSingle ( POLYGON paths)
private

Definition at line 964 of file shape_poly_set.cpp.

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

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

341{
342 int full_count = 0;
343
344 if( m_polys.size() == 0 ) // Empty poly set
345 return full_count;
346
347 for( int ii = 0; ii < OutlineCount(); ii++ )
348 {
349 // the first polygon in m_polys[ii] is the main contour,
350 // only others are holes:
351 for( int idx = 0; idx <= HoleCount( ii ); idx++ )
352 {
353 full_count += m_polys[ii][idx].PointCount();
354 }
355 }
356
357 return full_count;
358}

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

561{
562 for( const POLYGON& poly : m_polys )
563 {
564 for( size_t i = 0; i < poly.size(); i++ )
565 {
566 for( SHAPE_ARC arc : poly[i].m_arcs )
567 aArcBuffer.push_back( arc );
568 }
569 }
570}

References m_polys.

Referenced by BOOST_AUTO_TEST_CASE().

◆ GetClearance()

int SHAPE::GetClearance ( const SHAPE aOther) const
inherited

Return the actual minimum distance between two shapes.

Return values
distancein IU

Definition at line 48 of file shape.cpp.

49{
50 int actual_clearance = std::numeric_limits<int>::max();
51 std::vector<const SHAPE*> a_shapes;
52 std::vector<const SHAPE*> b_shapes;
53
54 GetIndexableSubshapes( a_shapes );
55 aOther->GetIndexableSubshapes( b_shapes );
56
57 if( GetIndexableSubshapeCount() == 0 )
58 a_shapes.push_back( this );
59
60 if( aOther->GetIndexableSubshapeCount() == 0 )
61 b_shapes.push_back( aOther );
62
63 for( const SHAPE* a : a_shapes )
64 {
65 for( const SHAPE* b : b_shapes )
66 {
67 int temp_dist = 0;
68 a->Collide( b, std::numeric_limits<int>::max() / 2, &temp_dist );
69
70 if( temp_dist < actual_clearance )
71 actual_clearance = temp_dist;
72 }
73 }
74
75 return actual_clearance;
76}
virtual size_t GetIndexableSubshapeCount() const
Definition: shape.h:110
virtual void GetIndexableSubshapes(std::vector< const SHAPE * > &aSubshapes) const
Definition: shape.h:112
An abstract shape on 2D plane.
Definition: shape.h:123

References SHAPE_BASE::GetIndexableSubshapeCount(), and SHAPE_BASE::GetIndexableSubshapes().

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

181{
182 int selectedVertex = aRelativeIndices.m_vertex;
183 unsigned int selectedContour = aRelativeIndices.m_contour;
184 unsigned int selectedPolygon = aRelativeIndices.m_polygon;
185
186 // Check whether the vertex indices make sense in this poly set
187 if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
188 && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
189 {
190 POLYGON currentPolygon;
191
192 aGlobalIdx = 0;
193
194 for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
195 {
196 currentPolygon = Polygon( polygonIdx );
197
198 for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
199 aGlobalIdx += currentPolygon[contourIdx].PointCount();
200 }
201
202 currentPolygon = Polygon( selectedPolygon );
203
204 for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
205 aGlobalIdx += currentPolygon[contourIdx].PointCount();
206
207 aGlobalIdx += selectedVertex;
208
209 return true;
210 }
211 else
212 {
213 return false;
214 }
215}

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

2287{
2288 if( !m_hash.IsValid() )
2289 return checksum();
2290
2291 return m_hash;
2292}

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

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

◆ GetIndexableSubshapeCount()

size_t SHAPE_POLY_SET::GetIndexableSubshapeCount ( ) const
overridevirtual

Reimplemented from SHAPE_BASE.

Definition at line 2528 of file shape_poly_set.cpp.

2529{
2530 size_t n = 0;
2531
2532 for( const std::unique_ptr<TRIANGULATED_POLYGON>& t : m_triangulatedPolys )
2533 n += t->GetTriangleCount();
2534
2535 return n;
2536}

References m_triangulatedPolys.

Referenced by GetIndexableSubshapes().

◆ GetIndexableSubshapes()

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

Reimplemented from SHAPE_BASE.

Definition at line 2539 of file shape_poly_set.cpp.

2540{
2541 aSubshapes.reserve( GetIndexableSubshapeCount() );
2542
2543 for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
2544 {
2545 for( TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
2546 aSubshapes.push_back( &tri );
2547 }
2548}
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 411 of file shape_poly_set.cpp.

412{
414
415 // If the edge does not exist, throw an exception, it is an illegal access memory error
416 if( !GetRelativeIndices( aGlobalIndex, &index ) )
417 return false;
418
419 // Calculate the previous and next index of aGlobalIndex, corresponding to
420 // the same contour;
421 VERTEX_INDEX inext = index;
422 int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
423
424 if( index.m_vertex == 0 )
425 {
426 index.m_vertex = lastpoint;
427 inext.m_vertex = 1;
428 }
429 else if( index.m_vertex == lastpoint )
430 {
431 index.m_vertex--;
432 inext.m_vertex = 0;
433 }
434 else
435 {
436 inext.m_vertex++;
437 index.m_vertex--;
438 }
439
440 if( aPrevious )
441 {
442 int previous;
443 GetGlobalIndex( index, previous );
444 *aPrevious = previous;
445 }
446
447 if( aNext )
448 {
449 int next;
450 GetGlobalIndex( inext, next );
451 *aNext = next;
452 }
453
454 return true;
455}
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
CITER next(CITER it)
Definition: ptree.cpp:126

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

141{
142 int polygonIdx = 0;
143 unsigned int contourIdx = 0;
144 int vertexIdx = 0;
145
146 int currentGlobalIdx = 0;
147
148 for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
149 {
150 const POLYGON& currentPolygon = CPolygon( polygonIdx );
151
152 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
153 {
154 const SHAPE_LINE_CHAIN& currentContour = currentPolygon[contourIdx];
155 int totalPoints = currentContour.PointCount();
156
157 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
158 {
159 // Check if the current vertex is the globally indexed as aGlobalIdx
160 if( currentGlobalIdx == aGlobalIdx )
161 {
162 aRelativeIndices->m_polygon = polygonIdx;
163 aRelativeIndices->m_contour = contourIdx;
164 aRelativeIndices->m_vertex = vertexIdx;
165
166 return true;
167 }
168
169 // Advance
170 currentGlobalIdx++;
171 }
172 }
173 }
174
175 return false;
176}
int PointCount() const
Return the number of points (vertices) in this line chain.
const POLYGON & CPolygon(int aIndex) const

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

1257{
1258 // Iterate through all the polygons on the set
1259 for( const POLYGON& paths : m_polys )
1260 {
1261 // If any of them has more than one contour, it is a hole.
1262 if( paths.size() > 1 )
1263 return true;
1264 }
1265
1266 // Return false if and only if every polygon has just one outline, without holes.
1267 return false;
1268}

References m_polys.

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

◆ HasIndexableSubshapes()

bool SHAPE_POLY_SET::HasIndexableSubshapes ( ) const
overridevirtual

Reimplemented from SHAPE_BASE.

Definition at line 2522 of file shape_poly_set.cpp.

2523{
2524 return IsTriangulationUpToDate();
2525}

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

2490{
2491 for( int i = 0; i < OutlineCount(); i++ )
2492 {
2493 if( hasTouchingHoles( CPolygon( i ) ) )
2494 return true;
2495 }
2496
2497 return false;
2498}
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 2501 of file shape_poly_set.cpp.

2502{
2503 std::set<long long> ptHashes;
2504
2505 for( const SHAPE_LINE_CHAIN& lc : aPoly )
2506 {
2507 for( const VECTOR2I& pt : lc.CPoints() )
2508 {
2509 const long long ptHash = (long long) pt.x << 32 | pt.y;
2510
2511 if( ptHashes.count( ptHash ) > 0 )
2512 return true;
2513
2514 ptHashes.insert( ptHash );
2515 }
2516 }
2517
2518 return false;
2519}

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

837{
838 m_polys.clear();
839
840 for( ClipperLib::PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
841 {
842 if( !n->IsHole() )
843 {
844 POLYGON paths;
845 paths.reserve( n->Childs.size() + 1 );
846
847 paths.emplace_back( n->Contour, aZValueBuffer, aArcBuffer );
848
849 for( unsigned int i = 0; i < n->Childs.size(); i++ )
850 paths.emplace_back( n->Childs[i]->Contour, aZValueBuffer, aArcBuffer );
851
852 m_polys.push_back( paths );
853 }
854 }
855}

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

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

References std::abs(), 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::BuildCourtyardCaches(), ZONE::BuildSmoothedPoly(), CADSTAR_PCB_ARCHIVE_LOADER::calculateZonePriorities(), BOARD_ADAPTER::createPadWithMargin(), Deflate(), ZONE_FILLER::fillCopperZone(), ZONE_FILLER::fillNonCopperZone(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), InflateWithLinkedHoles(), CADSTAR_PCB_ARCHIVE_LOADER::loadCoppers(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::packagePolygon(), PlotSolderMaskLayer(), DRC_TEST_PROVIDER_TEXT_DIMS::Run(), TEARDROP_MANAGER::SetTeardrops(), 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 734 of file shape_poly_set.cpp.

736{
737 Unfracture( aFastMode );
738 Inflate( aFactor, aCircleSegmentsCount );
739 Fracture( aFastMode );
740}
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.

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

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

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

294{
295 VERTEX_INDEX index;
296
297 if( aGlobalIndex < 0 )
298 aGlobalIndex = 0;
299
300 if( aGlobalIndex >= TotalVertices() )
301 {
302 Append( aNewVertex );
303 }
304 else
305 {
306 // Assure the position to be inserted exists; throw an exception otherwise
307 if( GetRelativeIndices( aGlobalIndex, &index ) )
308 m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
309 else
310 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
311 }
312}
int TotalVertices() const
Delete aIdx-th polygon from the set.

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 163 of file shape.h.

164 {
165 return m_type == SH_NULL;
166 }
SHAPE_TYPE m_type
< type of our shape
Definition: shape.h:116
@ SH_NULL
empty shape (no shape...),
Definition: shape.h:52

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

459{
460 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
461 CONST_SEGMENT_ITERATOR innerIterator;
462
463 for( iterator = CIterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
464 {
465 SEG firstSegment = *iterator;
466
467 // Iterate through all remaining segments.
468 innerIterator = iterator;
469
470 // Start in the next segment, we don't want to check collision between a segment and itself
471 for( innerIterator++; innerIterator; innerIterator++ )
472 {
473 SEG secondSegment = *innerIterator;
474
475 // Check whether the two segments built collide, only when they are not adjacent.
476 if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
477 return true;
478 }
479 }
480
481 return false;
482}
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:223

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

486{
487 for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
488 {
489 if( IsPolygonSelfIntersecting( polygon ) )
490 return true;
491 }
492
493 return false;
494}
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 1082 of file shape_poly_set.h.

1083 {
1084 return true;
1085 }

◆ IsTriangulationUpToDate()

bool SHAPE_POLY_SET::IsTriangulationUpToDate ( ) const

Definition at line 2295 of file shape_poly_set.cpp.

2296{
2298 return false;
2299
2300 if( !m_hash.IsValid() )
2301 return false;
2302
2303 MD5_HASH hash = checksum();
2304
2305 return hash == m_hash;
2306}

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

Referenced by KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::OPENGL_GAL::DrawPolygon(), HasIndexableSubshapes(), 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 2069 of file shape_poly_set.cpp.

2070{
2071 VERTEX_INDEX index;
2072
2073 // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
2074 if( !GetRelativeIndices( aGlobalIdx, &index ) )
2075 return false;
2076
2077 // The contour is a hole if its index is greater than zero
2078 return index.m_contour > 0;
2079}

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

◆ Iterate() [1/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 791 of file shape_poly_set.h.

792 {
793 return Iterate( 0, OutlineCount() - 1 );
794 }
ITERATOR Iterate()

References Iterate(), and OutlineCount().

Referenced by Iterate(), and IterateWithHoles().

◆ Iterate() [2/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 753 of file shape_poly_set.h.

754 {
755 ITERATOR iter;
756
757 iter.m_poly = this;
758 iter.m_currentPolygon = aFirst;
759 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
760 iter.m_currentContour = 0;
761 iter.m_currentVertex = 0;
762 iter.m_iterateHoles = aIterateHoles;
763
764 return iter;
765 }
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() [3/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 772 of file shape_poly_set.h.

773 {
774 return Iterate( aOutline, aOutline );
775 }

References Iterate().

◆ IterateFromVertexWithHoles()

ITERATOR SHAPE_POLY_SET::IterateFromVertexWithHoles ( int  aGlobalIdx)
inline

◆ IterateSegments() [1/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( )
inline

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

Definition at line 905 of file shape_poly_set.h.

References IterateSegments(), and OutlineCount().

Referenced by IterateSegments(), and IterateSegmentsWithHoles().

◆ IterateSegments() [2/3]

◆ IterateSegments() [3/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aPolygonIdx)
inline

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

Definition at line 893 of file shape_poly_set.h.

References IterateSegments().

◆ 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 917 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 923 of file shape_poly_set.h.

References IterateSegments().

◆ IterateWithHoles() [1/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 800 of file shape_poly_set.h.

801 {
802 return Iterate( 0, OutlineCount() - 1, true );
803 }

References Iterate(), and OutlineCount().

Referenced by IterateFromVertexWithHoles(), and RemoveNullSegments().

◆ IterateWithHoles() [2/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 782 of file shape_poly_set.h.

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

References Iterate().

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

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

1893{
1894 for( POLYGON& poly : m_polys )
1895 {
1896 for( SHAPE_LINE_CHAIN& path : poly )
1897 path.Mirror( aX, aY, aRef );
1898 }
1899
1902}

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

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

◆ Move()

◆ 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:43

References SHAPE::facets.

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

◆ NewHole()

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

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

Definition at line 230 of file shape_poly_set.cpp.

231{
232 SHAPE_LINE_CHAIN empty_path;
233
234 empty_path.SetClosed( true );
235
236 // Default outline is the last one
237 if( aOutline < 0 )
238 aOutline += m_polys.size();
239
240 // Add hole to the selected outline
241 m_polys[aOutline].push_back( empty_path );
242
243 return m_polys.back().size() - 2;
244}

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

219{
220 SHAPE_LINE_CHAIN empty_path;
221 POLYGON poly;
222
223 empty_path.SetClosed( true );
224 poly.push_back( empty_path );
225 m_polys.push_back( poly );
226 return m_polys.size() - 1;
227}

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), ZONE_FILLER::addKnockout(), AR_AUTOPLACER::addPad(), LIB_SHAPE::AddPoint(), SCH_SHAPE::AddPoint(), ZONE::AppendCorner(), EDA_SHAPE::beginEdit(), BOARD::BOARD(), BOOST_AUTO_TEST_CASE(), BuildBoardPolygonOutlines(), BuildFootprintPolygonOutlines(), BuildPolysetFromOrientedPaths(), KI_TEST::CommonTestData::CommonTestData(), TEARDROP_MANAGER::ComputePointsOnPadVia(), ConvertOutlineToPolygon(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CornerListToPolygon(), BITMAPCONV_INFO::createOutputData(), BOARD_ADAPTER::createPadWithMargin(), TEARDROP_MANAGER::createTeardrop(), 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(), FP_TEXTBOX::TransformShapeWithClearanceToPolygon(), PCB_TEXTBOX::TransformShapeWithClearanceToPolygon(), FP_TEXT::TransformTextShapeWithClearanceToPolygon(), FP_TEXTBOX::TransformTextShapeWithClearanceToPolygon(), PCB_TEXT::TransformTextShapeWithClearanceToPolygon(), PCB_TEXTBOX::TransformTextShapeWithClearanceToPolygon(), PCB_DIM_ALIGNED::updateGeometry(), PCB_DIM_ORTHOGONAL::updateGeometry(), PCB_DIM_RADIAL::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 1288 of file shape_poly_set.cpp.

1289{
1290 // We are expecting only one main outline, but this main outline can have holes
1291 // if holes: combine holes and remove them from the main outline.
1292 // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1293 // calculations, but it is not mandatory. It is used mainly
1294 // because there is usually only very few vertices in area outlines
1295 SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1296 SHAPE_POLY_SET holesBuffer;
1297
1298 // Move holes stored in outline to holesBuffer:
1299 // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1300 while( outline.size() > 1 )
1301 {
1302 holesBuffer.AddOutline( outline.back() );
1303 outline.pop_back();
1304 }
1305
1307
1308 // If any hole, subtract it to main outline
1309 if( holesBuffer.OutlineCount() )
1310 {
1311 holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1313 }
1314
1315 // In degenerate cases, simplify might return no outlines
1316 if( OutlineCount() > 0 )
1318
1319 return OutlineCount();
1320}
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.

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

2267{
2268 static_cast<SHAPE&>(*this) = aOther;
2269 m_polys = aOther.m_polys;
2270
2271 m_triangulatedPolys.clear();
2272
2273 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
2274 {
2275 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
2276 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
2277 }
2278
2279 m_hash = aOther.m_hash;
2281
2282 return *this;
2283}

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

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

References m_polys.

Referenced by EE_POINT_EDITOR::addCorner(), ZONE_FILLER::addHatchFillTypeOnZone(), LIB_SHAPE::AddPoint(), SCH_SHAPE::AddPoint(), Area(), EDA_SHAPE::beginEdit(), BOOST_AUTO_TEST_CASE(), BuildFootprintPolygonOutlines(), BuildPolysetFromOrientedPaths(), ZONE::BuildSmoothedPoly(), CacheTriangulation(), EDA_SHAPE::calcEdit(), FOOTPRINT::CheckNetTies(), collidesWithArea(), TEARDROP_MANAGER::ComputePointsOnPadVia(), EDA_SHAPE::continueEdit(), ConvertPolygonToBlocks(), FOOTPRINT::CoverageRatio(), BITMAPCONV_INFO::createOutputData(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), DIALOG_PAD_PRIMITIVE_POLY_PROPS::DIALOG_PAD_PRIMITIVE_POLY_PROPS(), KIGFX::DS_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), APERTURE_MACRO::DrawApertureMacroShape(), CALLBACK_GAL::DrawGlyph(), EDA_SHAPE::endEdit(), DSN::SPECCTRA_DB::fillBOUNDARY(), AR_AUTOPLACER::fillMatrix(), TEARDROP_MANAGER::findAnchorPointsOnTrack(), CADSTAR_SCH_ARCHIVE_LOADER::fixUpLibraryPins(), GERBER_PLOTTER::FlashPadChamferRoundRect(), DXF_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), HPGL_PLOTTER::FlashPadRoundRect(), PSLIKE_PLOTTER::FlashPadRoundRect(), PCB_PLUGIN::format(), formatPoly(), PCB_PLUGIN::formatRenderCache(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), PCB_SHAPE::GetFocusPosition(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), CADSTAR_SCH_ARCHIVE_LOADER::getScaledLibPart(), LIB_SHAPE::GetSelectMenuText(), SCH_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(), SCH_SEXPR_PARSER::ParseSchematic(), PCB_PARSER::parseZONE(), ZONE_CREATE_HELPER::performZoneCutout(), SCH_SHAPE::Plot(), LIB_SHAPE::Plot(), PlotDrawingSheet(), BRDITEMS_PLOTTER::PlotFilledAreas(), BRDITEMS_PLOTTER::PlotFootprintShape(), BRDITEMS_PLOTTER::PlotPcbShape(), BRDITEMS_PLOTTER::PlotPcbText(), polygonArea(), SCH_SHAPE::Print(), 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(), DRC_TEST_PROVIDER_ANNULAR_WIDTH::Run(), DRC_TEST_PROVIDER_EDGE_CLEARANCE::Run(), DRC_TEST_PROVIDER_SLIVER_CHECKER::Run(), SCH_LEGACY_PLUGIN_CACHE::savePolyLine(), EDA_SHAPE::scale(), TEARDROP_MANAGER::SetTeardrops(), SHAPE_POLY_SET(), ZONE_FILLER::subtractHigherPriorityZones(), DRC_TEST_PROVIDER_ZONE_CONNECTIONS::testZoneLayer(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::testZoneLayer(), 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 685 of file shape_poly_set.h.

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

References m_polys.

◆ OutlineCount()

int SHAPE_POLY_SET::OutlineCount ( ) const
inline

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

Definition at line 658 of file shape_poly_set.h.

References m_polys.

Referenced by PCB_POINT_EDITOR::addCorner(), ZONE_FILLER::addHatchFillTypeOnZone(), PAD::addPadPrimitivesToPolygon(), ZONE::AddPolygon(), PAD::AddPrimitivePoly(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), ZONE::AppendCorner(), Area(), booleanOp(), BOOST_AUTO_TEST_CASE(), BOOST_FIXTURE_TEST_CASE(), BuildBBoxCaches(), BuildBoardPolygonOutlines(), BuildConvexHull(), BuildFootprintPolygonOutlines(), CacheTriangulation(), FOOTPRINT::CheckNetTies(), KI_TEST::CheckShapePolySet(), CIterate(), CIterateSegments(), CIterateSegmentsWithHoles(), CIterateWithHoles(), collidesWithArea(), Contains(), convertPolygon(), ConvertPolygonToBlocks(), RENDER_3D_OPENGL::createBoard(), BITMAPCONV_INFO::createOutputData(), CreatePadsShapesSection(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), CONVERT_TOOL::CreatePolys(), KIGFX::DS_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawApertureMacro(), APERTURE_MACRO::DrawApertureMacroShape(), D_CODE::DrawFlashedPolygon(), D_CODE::DrawFlashedShape(), KIGFX::GERBVIEW_PAINTER::drawFlashedShape(), CALLBACK_GAL::DrawGlyph(), 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(), fillArcPOLY(), DSN::SPECCTRA_DB::fillBOUNDARY(), ZONE_FILLER::fillCopperZone(), GEOM_TEST::FilletPolySet(), DXF_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), PCB_PLUGIN::formatRenderCache(), 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(), FOOTPRINT::GetEffectiveShape(), 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(), PCB_PARSER::parseRenderCache(), ZONE_CREATE_HELPER::performZoneCutout(), BRDITEMS_PLOTTER::PlotFilledAreas(), BRDITEMS_PLOTTER::PlotFootprintShape(), PlotLayerOutlines(), BRDITEMS_PLOTTER::PlotPcbShape(), BRDITEMS_PLOTTER::PlotPcbText(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), PlotStandardLayer(), polygonArea(), GERBER_DRAW_ITEM::Print(), DS_DRAW_ITEM_POLYPOLYGONS::PrintWsItem(), DRC_RTREE::QueryColliding(), RENDER_3D_RAYTRACE::Reload(), ZONE::RemoveCutout(), DRC_TEST_PROVIDER_SLIVER_CHECKER::Run(), DRC_TEST_PROVIDER_TEXT_DIMS::Run(), EDA_SHAPE::SetPolyShape(), Subset(), PNS_KICAD_IFACE_BASE::syncZone(), TestConcaveSquareFillet(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE_ON_MOVE::testCourtyardClearances(), TestSquareFillet(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::testZoneLayer(), 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 1354 of file shape_poly_set.cpp.

1355{
1356 std::string tmp;
1357
1358 aStream >> tmp;
1359
1360 if( tmp != "polyset" )
1361 return false;
1362
1363 aStream >> tmp;
1364
1365 int n_polys = atoi( tmp.c_str() );
1366
1367 if( n_polys < 0 )
1368 return false;
1369
1370 for( int i = 0; i < n_polys; i++ )
1371 {
1372 POLYGON paths;
1373
1374 aStream >> tmp;
1375
1376 if( tmp != "poly" )
1377 return false;
1378
1379 aStream >> tmp;
1380 int n_outlines = atoi( tmp.c_str() );
1381
1382 if( n_outlines < 0 )
1383 return false;
1384
1385 for( int j = 0; j < n_outlines; j++ )
1386 {
1387 SHAPE_LINE_CHAIN outline;
1388
1389 outline.SetClosed( true );
1390
1391 aStream >> tmp;
1392 int n_vertices = atoi( tmp.c_str() );
1393
1394 for( int v = 0; v < n_vertices; v++ )
1395 {
1396 VECTOR2I p;
1397
1398 aStream >> tmp; p.x = atoi( tmp.c_str() );
1399 aStream >> tmp; p.y = atoi( tmp.c_str() );
1400 outline.Append( p );
1401 }
1402
1403 paths.push_back( outline );
1404 }
1405
1406 m_polys.push_back( paths );
1407 }
1408
1409 return true;
1410}

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

1447{
1448 // Iterate through all the polygons in the set
1449 for( const POLYGON& polygon : m_polys )
1450 {
1451 // Iterate through all the line chains in the polygon
1452 for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1453 {
1454 if( lineChain.PointOnEdge( aP ) )
1455 return true;
1456 }
1457 }
1458
1459 return false;
1460}

References m_polys.

◆ Polygon() [1/2]

◆ Polygon() [2/2]

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

Definition at line 718 of file shape_poly_set.h.

719 {
720 return m_polys[aIndex];
721 }

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

1598{
1599 // Default polygon is the last one
1600 if( aPolygonIdx < 0 )
1601 aPolygonIdx += m_polys.size();
1602
1603 m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1604}

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

1608{
1609 int removed = 0;
1610
1611 ITERATOR iterator = IterateWithHoles();
1612
1613 VECTOR2I contourStart = *iterator;
1614 VECTOR2I segmentStart, segmentEnd;
1615
1616 VERTEX_INDEX indexStart;
1617 std::vector<VERTEX_INDEX> indices_to_remove;
1618
1619 while( iterator )
1620 {
1621 // Obtain first point and its index
1622 segmentStart = *iterator;
1623 indexStart = iterator.GetIndex();
1624
1625 // Obtain last point
1626 if( iterator.IsEndContour() )
1627 {
1628 segmentEnd = contourStart;
1629
1630 // Advance
1631 iterator++;
1632
1633 // If we have rolled into the next contour, remember its position
1634 // segmentStart and segmentEnd remain valid for comparison here
1635 if( iterator )
1636 contourStart = *iterator;
1637 }
1638 else
1639 {
1640 // Advance
1641 iterator++;
1642
1643 // If we have reached the end of the SHAPE_POLY_SET, something is broken here
1644 wxCHECK_MSG( iterator, removed, wxT( "Invalid polygon. Reached end without noticing. Please report this error" ) );
1645
1646 segmentEnd = *iterator;
1647 }
1648
1649 // Remove segment start if both points are equal
1650 if( segmentStart == segmentEnd )
1651 {
1652 indices_to_remove.push_back( indexStart );
1653 removed++;
1654 }
1655 }
1656
1657 // Proceed in reverse direction to remove the vertices because they are stored as absolute indices in a vector
1658 // Removing in reverse order preserves the remaining index values
1659 for( auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
1660 RemoveVertex( *it );
1661
1662 return removed;
1663}
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 BOOST_AUTO_TEST_CASE(), 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 1818 of file shape_poly_set.cpp.

1819{
1820 VERTEX_INDEX index;
1821
1822 // Assure the to be removed vertex exists, abort otherwise
1823 if( GetRelativeIndices( aGlobalIndex, &index ) )
1824 RemoveVertex( index );
1825 else
1826 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1827}

References GetRelativeIndices(), and RemoveVertex().

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

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

1831{
1832 m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1833}

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 ( const EDA_ANGLE aAngle,
const VECTOR2I aCenter = { 0, 0 } 
)
overridevirtual

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

1848{
1849 m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1850}

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 vertex Return total number of vertices stored in the set.

Definition at line 1836 of file shape_poly_set.cpp.

1837{
1838 VERTEX_INDEX index;
1839
1840 if( GetRelativeIndices( aGlobalIndex, &index ) )
1841 SetVertex( index, aPos );
1842 else
1843 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1844}
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.

References GetRelativeIndices(), and SetVertex().

◆ Simplify()

◆ SquaredDistance() [1/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 2044 of file shape_poly_set.cpp.

2045{
2046 SEG::ecoord currentDistance_sq;
2047 SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
2048 VECTOR2I nearest;
2049
2050 // Iterate through all the polygons and get the minimum distance.
2051 for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
2052 {
2053 currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
2054 aNearest ? &nearest : nullptr );
2055
2056 if( currentDistance_sq < minDistance_sq )
2057 {
2058 if( aNearest )
2059 *aNearest = nearest;
2060
2061 minDistance_sq = currentDistance_sq;
2062 }
2063 }
2064
2065 return minDistance_sq;
2066}
VECTOR2I::extended_type ecoord
Definition: seg.h:44
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79

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

◆ SquaredDistance() [2/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 2019 of file shape_poly_set.cpp.

2020{
2021 SEG::ecoord currentDistance_sq;
2022 SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
2023 VECTOR2I nearest;
2024
2025 // Iterate through all the polygons and get the minimum distance.
2026 for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
2027 {
2028 currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
2029 aNearest ? &nearest : nullptr );
2030
2031 if( currentDistance_sq < minDistance_sq )
2032 {
2033 if( aNearest )
2034 *aNearest = nearest;
2035
2036 minDistance_sq = currentDistance_sq;
2037 }
2038 }
2039
2040 return minDistance_sq;
2041}

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

Referenced by BOOST_AUTO_TEST_CASE(), Collide(), and DRC_TEST_PROVIDER_ANNULAR_WIDTH::Run().

◆ SquaredDistanceToPolygon() [1/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 1982 of file shape_poly_set.cpp.

1984{
1985 // Check if the segment is fully-contained. If so, its midpoint is a good-enough nearest point.
1986 if( containsSingle( aSegment.A, aPolygonIndex, 1 ) &&
1987 containsSingle( aSegment.B, aPolygonIndex, 1 ) )
1988 {
1989 if( aNearest )
1990 *aNearest = ( aSegment.A + aSegment.B ) / 2;
1991
1992 return 0;
1993 }
1994
1995 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1996 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1997
1998 if( aNearest && minDistance == 0 )
1999 *aNearest = ( *iterator ).NearestPoint( aSegment );
2000
2001 for( iterator++; iterator && minDistance > 0; iterator++ )
2002 {
2003 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
2004
2005 if( currentDistance < minDistance )
2006 {
2007 if( aNearest )
2008 *aNearest = (*iterator).NearestPoint( aSegment );
2009
2010 minDistance = currentDistance;
2011 }
2012 }
2013
2014 // Return the maximum of minDistance and zero
2015 return minDistance < 0 ? 0 : minDistance;
2016}
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50

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

◆ SquaredDistanceToPolygon() [2/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 1946 of file shape_poly_set.cpp.

1948{
1949 // We calculate the min dist between the segment and each outline segment. However, if the
1950 // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1951 // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1952 // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1953 if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1954 {
1955 if( aNearest )
1956 *aNearest = aPoint;
1957
1958 return 0;
1959 }
1960
1961 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1962
1963 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1964
1965 for( iterator++; iterator && minDistance > 0; iterator++ )
1966 {
1967 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1968
1969 if( currentDistance < minDistance )
1970 {
1971 if( aNearest )
1972 *aNearest = (*iterator).NearestPoint( aPoint );
1973
1974 minDistance = currentDistance;
1975 }
1976 }
1977
1978 return minDistance;
1979}

References CIterateSegmentsWithHoles(), and containsSingle().

Referenced by SquaredDistance().

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

362{
363 assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
364
365 SHAPE_POLY_SET newPolySet;
366
367 for( int index = aFirstPolygon; index < aLastPolygon; index++ )
368 newPolySet.m_polys.push_back( Polygon( index ) );
369
370 return newPolySet;
371}

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

1920{
1921 int c = 0;
1922
1923 for( const POLYGON& poly : m_polys )
1924 {
1925 for( const SHAPE_LINE_CHAIN& path : poly )
1926 c += path.PointCount();
1927 }
1928
1929 return c;
1930}

References m_polys, and path.

Referenced by PCB_POINT_EDITOR::buildForPolyOutline(), KI_TEST::CheckShapePolySet(), EDA_SHAPE::Compare(), ZONE::GetNumCorners(), ZONE::HitTest(), InsertVertex(), FOOTPRINT::cmp_drawings::operator()(), FOOTPRINT::cmp_zones::operator()(), shapesNeedUpdate(), PCB_POINT_EDITOR::updateItem(), PCB_POINT_EDITOR::updatePoints(), and zonesNeedUpdate().

◆ TriangulatedPolyCount()

unsigned int SHAPE_POLY_SET::TriangulatedPolyCount ( ) const
inline

◆ TriangulatedPolygon()

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

◆ Type()

◆ TypeName()

wxString SHAPE_BASE::TypeName ( ) const
inlineinherited

Definition at line 100 of file shape.h.

101 {
102 return SHAPE_TYPE_asString( m_type );
103 }
static wxString SHAPE_TYPE_asString(SHAPE_TYPE a)
Definition: shape.h:56

References SHAPE_BASE::m_type, and SHAPE_TYPE_asString().

Referenced by Collide().

◆ Unfracture()

void SHAPE_POLY_SET::Unfracture ( POLYGON_MODE  aFastMode)

Return true if the polygon set has any holes.

Definition at line 1271 of file shape_poly_set.cpp.

1272{
1273 for( POLYGON& path : m_polys )
1275
1276 Simplify( aFastMode ); // remove overlapping holes/degeneracy
1277}
void unfractureSingle(POLYGON &path)

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

Referenced by InflateWithLinkedHoles(), and DRC_TEST_PROVIDER_SLIVER_CHECKER::Run().

◆ unfractureSingle()

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

Definition at line 1089 of file shape_poly_set.cpp.

1090{
1091 assert( aPoly.size() == 1 );
1092
1093 struct EDGE
1094 {
1095 int m_index = 0;
1096 SHAPE_LINE_CHAIN* m_poly = nullptr;
1097 bool m_duplicate = false;
1098
1099 EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
1100 m_index( aIndex ),
1101 m_poly( aPolygon )
1102 {}
1103
1104 bool compareSegs( const SEG& s1, const SEG& s2 ) const
1105 {
1106 return (s1.A == s2.B && s1.B == s2.A);
1107 }
1108
1109 bool operator==( const EDGE& aOther ) const
1110 {
1111 return compareSegs( m_poly->CSegment( m_index ),
1112 aOther.m_poly->CSegment( aOther.m_index ) );
1113 }
1114
1115 bool operator!=( const EDGE& aOther ) const
1116 {
1117 return !compareSegs( m_poly->CSegment( m_index ),
1118 aOther.m_poly->CSegment( aOther.m_index ) );
1119 }
1120
1121 struct HASH
1122 {
1123 std::size_t operator()( const EDGE& aEdge ) const
1124 {
1125 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1126 std::size_t seed = 0xa82de1c0;
1127 hash_combine( seed, a.A.x, a.B.x, a.A.y, a.B.y );
1128 return seed;
1129 }
1130 };
1131 };
1132
1133 struct EDGE_LIST_ENTRY
1134 {
1135 int index;
1136 EDGE_LIST_ENTRY* next;
1137 };
1138
1139 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1140
1141 SHAPE_LINE_CHAIN lc = aPoly[0];
1142 lc.Simplify();
1143
1144 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.SegmentCount() );
1145
1146 for( int i = 0; i < lc.SegmentCount(); i++ )
1147 {
1148 edgeList[i].index = i;
1149 edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
1150 }
1151
1152 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1153
1154 for( int i = 0; i < lc.SegmentCount(); i++ )
1155 {
1156 EDGE e( &lc, i );
1157 uniqueEdges.insert( e );
1158 }
1159
1160 for( int i = 0; i < lc.SegmentCount(); i++ )
1161 {
1162 EDGE e( &lc, i );
1163 auto it = uniqueEdges.find( e );
1164
1165 if( it != uniqueEdges.end() && it->m_index != i )
1166 {
1167 int e1 = it->m_index;
1168 int e2 = i;
1169
1170 if( e1 > e2 )
1171 std::swap( e1, e2 );
1172
1173 int e1_prev = e1 - 1;
1174
1175 if( e1_prev < 0 )
1176 e1_prev = lc.SegmentCount() - 1;
1177
1178 int e2_prev = e2 - 1;
1179
1180 if( e2_prev < 0 )
1181 e2_prev = lc.SegmentCount() - 1;
1182
1183 int e1_next = e1 + 1;
1184
1185 if( e1_next == lc.SegmentCount() )
1186 e1_next = 0;
1187
1188 int e2_next = e2 + 1;
1189
1190 if( e2_next == lc.SegmentCount() )
1191 e2_next = 0;
1192
1193 edgeList[e1_prev].next = &edgeList[ e2_next ];
1194 edgeList[e2_prev].next = &edgeList[ e1_next ];
1195 edgeList[i].next = nullptr;
1196 edgeList[it->m_index].next = nullptr;
1197 }
1198 }
1199
1200 for( int i = 0; i < lc.SegmentCount(); i++ )
1201 {
1202 if( edgeList[i].next )
1203 queue.insert( &edgeList[i] );
1204 }
1205
1206 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
1207
1208 int n = 0;
1209 int outline = -1;
1210
1211 POLYGON result;
1212 double max_poly = 0.0;
1213
1214 while( queue.size() )
1215 {
1216 EDGE_LIST_ENTRY* e_first = *queue.begin();
1217 EDGE_LIST_ENTRY* e = e_first;
1218 int cnt = 0;
1219
1220 do
1221 {
1222 edgeBuf[cnt++] = e;
1223 e = e->next;
1224 } while( e && e != e_first );
1225
1226 SHAPE_LINE_CHAIN outl;
1227
1228 for( int i = 0; i < cnt; i++ )
1229 {
1230 VECTOR2I p = lc.CPoint( edgeBuf[i]->index );
1231 outl.Append( p );
1232 queue.erase( edgeBuf[i] );
1233 }
1234
1235 outl.SetClosed( true );
1236
1237 double area = std::fabs( outl.Area() );
1238
1239 if( area > max_poly )
1240 {
1241 outline = n;
1242 max_poly = area;
1243 }
1244
1245 result.push_back( outl );
1246 n++;
1247 }
1248
1249 if( outline > 0 )
1250 std::swap( result[0], result[outline] );
1251
1252 aPoly = result;
1253}
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int SegmentCount() const
Return the number of segments in this line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
static void hash_combine(std::size_t &seed)
This is a dummy function to take the final case of hash_combine below.
Definition: hash.h:34
const bool operator==(const COLOR4D &lhs, const COLOR4D &rhs)
Equality operator, are two colors equal.
Definition: color4d.cpp:268
const bool operator!=(const COLOR4D &lhs, const COLOR4D &rhs)
Not equality operator, are two colors not equal.
Definition: color4d.cpp:274

References SEG::A, SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::Area(), SEG::B, SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::CSegment(), hash_combine(), next(), KIGFX::operator!=(), KIGFX::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 701 of file shape_poly_set.h.

References Subset().

◆ UpdateTriangulationDataHash()

void SHAPE_POLY_SET::UpdateTriangulationDataHash ( )

Definition at line 1694 of file shape_poly_set.cpp.

1695{
1696 m_hash = checksum();
1697}

References checksum(), and m_hash.

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

316{
317 if( m_polys.size() == 0 ) // Empty poly set
318 return 0;
319
320 if( aOutline < 0 ) // Use last outline
321 aOutline += m_polys.size();
322
323 int idx;
324
325 if( aHole < 0 )
326 idx = 0;
327 else
328 idx = aHole + 1;
329
330 if( aOutline >= (int) m_polys.size() ) // not existing outline
331 return 0;
332
333 if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
334 return 0;
335
336 return m_polys[aOutline][idx].PointCount();
337}

References m_polys.

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

Member Data Documentation

◆ facets

std::list< FACET* > SHAPE::facets
privateinherited

Definition at line 143 of file wrlfacet.h.

Referenced by SHAPE::CalcShape(), and SHAPE::NewFacet().

◆ m_hash

◆ m_polys

◆ m_triangulatedPolys

◆ 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 116 of file shape.h.

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

◆ 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 128 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: