KiCad PCB EDA Suite
SHAPE_POLY_SET Class Reference

Represent a set of closed polygons. More...

#include <shape_poly_set.h>

Inheritance diagram for SHAPE_POLY_SET:
SHAPE SHAPE_BASE

Classes

class  ITERATOR_TEMPLATE
 Base class for iterating over all vertices in a given SHAPE_POLY_SET. More...
 
class  SEGMENT_ITERATOR_TEMPLATE
 Base class for iterating over all segments in a given SHAPE_POLY_SET. More...
 
class  TRIANGULATED_POLYGON
 
struct  VERTEX_INDEX
 Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: the polygon index, the contour index relative to the polygon and the vertex index relative the contour. More...
 

Public Types

enum  POLYGON_MODE { PM_FAST = true, PM_STRICTLY_SIMPLE = false }
 Operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak polygon if aFastMode is PM_STRICTLY_SIMPLE (false) (default) the result is (theoretically) a strictly simple polygon, but calculations can be really significantly time consuming Most of time PM_FAST is preferable. More...
 
enum  CORNER_STRATEGY {
  ALLOW_ACUTE_CORNERS, CHAMFER_ACUTE_CORNERS, ROUND_ACUTE_CORNERS, CHAMFER_ALL_CORNERS,
  ROUND_ALL_CORNERS
}
 < define how inflate transform build inflated polygon More...
 
typedef std::vector< SHAPE_LINE_CHAINPOLYGON
 < represents a single polygon outline with holes. More...
 
typedef struct SHAPE_POLY_SET::VERTEX_INDEX 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...
 
typedef ITERATOR_TEMPLATE< VECTOR2IITERATOR
 
typedef ITERATOR_TEMPLATE< const VECTOR2ICONST_ITERATOR
 
typedef SEGMENT_ITERATOR_TEMPLATE< SEGSEGMENT_ITERATOR
 
typedef SEGMENT_ITERATOR_TEMPLATE< const SEGCONST_SEGMENT_ITERATOR
 

Public Member Functions

 SHAPE_POLY_SET ()
 
 SHAPE_POLY_SET (const SHAPE_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)
 
bool IsTriangulationUpToDate () const
 
MD5_HASH GetHash () const
 
virtual bool HasIndexableSubshapes () const override
 
virtual size_t GetIndexableSubshapeCount () const override
 
virtual void GetIndexableSubshapes (std::vector< SHAPE * > &aSubshapes) override
 
bool GetRelativeIndices (int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
 Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated list of all vertices in all contours— and get the index of the vertex relative to the contour relative to the polygon in which it is. More...
 
bool GetGlobalIndex (VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
 Compute the global index of a vertex from the relative indices of polygon, contour and vertex. More...
 
SHAPEClone () const override
 Return a dynamically allocated copy of the shape. More...
 
int NewOutline ()
 Creates a new hole in a given outline. More...
 
int NewHole (int aOutline=-1)
 Adds a new outline to the set and returns its index. More...
 
int AddOutline (const SHAPE_LINE_CHAIN &aOutline)
 Adds a new hole to the given outline (default: last) and returns its index. More...
 
int AddHole (const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
 Return the area of this poly set. More...
 
double Area ()
 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)
 
void InsertVertex (int aGlobalIndex, 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
 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 aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
 Perform outline inflation/deflation. More...
 
void Deflate (int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
 
void InflateWithLinkedHoles (int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
 Perform outline inflation/deflation, using round corners. More...
 
void Fracture (POLYGON_MODE aFastMode)
 Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes. More...
 
void Unfracture (POLYGON_MODE aFastMode)
 Return true if the polygon set has any holes. More...
 
bool HasHoles () const
 Return true if the polygon set has any holes that share a vertex. More...
 
bool HasTouchingHoles () const
 Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMode meaning, see function booleanOp. More...
 
void Simplify (POLYGON_MODE aFastMode)
 
int NormalizeAreaOutlines ()
 Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s). More...
 
const std::string Format () const override
 
bool Parse (std::stringstream &aStream) override
 
void Move (const VECTOR2I &aVector) override
 
void Mirror (bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
 Mirror the line points about y or x (or both) More...
 
void Rotate (double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
 Rotate all vertices by a given angle. More...
 
bool IsSolid () const override
 
const BOX2I BBox (int aClearance=0) const override
 Compute a bounding box of the shape, with a margin of aClearance a collision. More...
 
bool PointOnEdge (const VECTOR2I &aP) const
 Check if point aP lies on an edge or vertex of some of the outlines or holes. More...
 
bool Collide (const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Check if the boundary of shape (this) lies closer to the shape aShape than aClearance, indicating a collision. More...
 
bool Collide (const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Check whether the point aP is either inside or on the edge of the polygon set. More...
 
bool Collide (const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Check whether the segment aSeg collides with the polygon set (or its edge). More...
 
bool CollideVertex (const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
 Check whether aPoint collides with any vertex of any of the contours of the polygon. More...
 
bool CollideEdge (const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
 Check whether aPoint collides with any edge of any of the contours of the polygon. More...
 
void BuildBBoxCaches () const
 Construct BBoxCaches for Contains(), below. More...
 
const BOX2I BBoxFromCaches () const
 
bool Contains (const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
 Return true if a given subpolygon contains the point aP. More...
 
bool IsEmpty () const
 
void RemoveVertex (int aGlobalIndex)
 Delete the aGlobalIndex-th vertex. More...
 
void RemoveVertex (VERTEX_INDEX aRelativeIndices)
 Delete the vertex indexed by aRelativeIndex (index of polygon, contour and vertex). More...
 
void RemoveAllContours ()
 
void RemoveContour (int aContourIdx, int aPolygonIdx=-1)
 Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set. More...
 
int RemoveNullSegments ()
 Look for null segments; ie, segments whose ends are exactly the same and deletes them. More...
 
void SetVertex (const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
 Accessor function to set the position of a specific point. More...
 
void SetVertex (int aGlobalIndex, const VECTOR2I &aPos)
 Set the vertex based on the global index. More...
 
int TotalVertices () const
 Delete aIdx-th polygon from the set. More...
 
void DeletePolygon (int aIdx)
 
POLYGON ChamferPolygon (unsigned int aDistance, int aIndex)
 Return a chamfered version of the aIndex-th polygon. More...
 
POLYGON FilletPolygon (unsigned int aRadius, int aErrorMax, int aIndex)
 Return a filleted version of the aIndex-th polygon. More...
 
SHAPE_POLY_SET Chamfer (int aDistance)
 Return a chamfered version of the polygon set. More...
 
SHAPE_POLY_SET Fillet (int aRadius, int aErrorMax)
 Return a filleted version of the polygon set. More...
 
SEG::ecoord SquaredDistanceToPolygon (VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
 Compute the minimum distance between the aIndex-th polygon and aPoint. More...
 
SEG::ecoord SquaredDistanceToPolygon (const SEG &aSegment, int aIndex, VECTOR2I *aNearest) const
 Compute the minimum distance between the aIndex-th polygon and aSegment with a possible width. More...
 
SEG::ecoord SquaredDistance (VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
 Compute the minimum distance squared between aPoint and all the polygons in the set. More...
 
SEG::ecoord SquaredDistance (const SEG &aSegment, VECTOR2I *aNearest=nullptr) const
 Compute the minimum distance squared between aSegment and all the polygons in the set. More...
 
bool IsVertexInHole (int aGlobalIdx)
 Check whether the aGlobalIndex-th vertex belongs to a hole. More...
 
bool IsNull () const
 Return true if the shape is a null shape. More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const
 Check if the boundary of shape (this) lies closer to the shape aShape than aClearance, indicating a collision. More...
 
virtual VECTOR2I Centre () const
 Compute a center-of-mass of the shape. More...
 
FACETNewFacet ()
 
SGNODECalcShape (SGNODE *aParent, SGNODE *aColor, WRL1_ORDER aVertexOrder, float aCreaseLimit=0.74317, bool isVRML2=false)
 
SHAPE_TYPE Type () const
 Return the type of the shape. More...
 

Static Public Attributes

static const int MIN_PRECISION_IU = 4
 This is the minimum precision for all the points in a shape. More...
 

Protected Types

typedef VECTOR2I::extended_type ecoord
 

Protected Attributes

SHAPE_TYPE m_type
 < type of our shape More...
 

Private Types

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

Private Member Functions

void fractureSingle (POLYGON &paths)
 
void unfractureSingle (POLYGON &path)
 
void importTree (ClipperLib::PolyTree *tree)
 
void booleanOp (ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
 This is the engine to execute all polygon boolean transforms (AND, OR, ... More...
 
void booleanOp (ClipperLib::ClipType aType, const SHAPE_POLY_SET &aShape, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
 
bool containsSingle (const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
 Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset. More...
 
POLYGON chamferFilletPolygon (CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
 Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode selected. More...
 
bool hasTouchingHoles (const POLYGON &aPoly) const
 
MD5_HASH checksum () const
 

Private Attributes

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

Detailed Description

Represent a set of closed polygons.

Polygons may be nonconvex, self-intersecting and have holes. Provides boolean operations (using Clipper library as the backend).

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

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

TODO: add convex partitioning & spatial index

Definition at line 64 of file shape_poly_set.h.

Member Typedef Documentation

◆ CONST_ITERATOR

◆ CONST_SEGMENT_ITERATOR

◆ ecoord

typedef VECTOR2I::extended_type SHAPE::ecoord
protectedinherited

Definition at line 236 of file shape.h.

◆ ITERATOR

◆ POLYGON

< represents a single polygon outline with holes.

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

Definition at line 70 of file shape_poly_set.h.

◆ POLYSET

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

Definition at line 1401 of file shape_poly_set.h.

◆ SEGMENT_ITERATOR

◆ VERTEX_INDEX

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

Member Enumeration Documentation

◆ CORNER_MODE

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

◆ CORNER_STRATEGY

< define how inflate transform build inflated polygon

Enumerator
ALLOW_ACUTE_CORNERS 

just inflate the polygon. Acute angles create spikes

CHAMFER_ACUTE_CORNERS 

Acute angles are chamfered.

ROUND_ACUTE_CORNERS 

Acute angles are rounded.

CHAMFER_ALL_CORNERS 

All angles are chamfered.

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

ROUND_ALL_CORNERS 

All angles are rounded.

The distance between new and old polygon edges is constant

Definition at line 945 of file shape_poly_set.h.

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

◆ POLYGON_MODE

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

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

Enumerator
PM_FAST 
PM_STRICTLY_SIMPLE 

Definition at line 912 of file shape_poly_set.h.

Constructor & Destructor Documentation

◆ SHAPE_POLY_SET() [1/3]

SHAPE_POLY_SET::SHAPE_POLY_SET ( )

Definition at line 60 of file shape_poly_set.cpp.

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

Referenced by Clone().

◆ SHAPE_POLY_SET() [2/3]

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

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

References AddOutline().

◆ SHAPE_POLY_SET() [3/3]

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

73  :
74  SHAPE( aOther ), m_polys( aOther.m_polys )
75 {
76  if( aOther.IsTriangulationUpToDate() )
77  {
78  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
79  m_triangulatedPolys.push_back(
80  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
81 
82  m_hash = aOther.GetHash();
83  m_triangulationValid = true;
84  }
85  else
86  {
87  m_triangulationValid = false;
88  m_hash = MD5_HASH();
89  m_triangulatedPolys.clear();
90  }
91 }
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition: shape.h:127
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool IsTriangulationUpToDate() const
MD5_HASH GetHash() const
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const

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

◆ ~SHAPE_POLY_SET()

SHAPE_POLY_SET::~SHAPE_POLY_SET ( )

Definition at line 94 of file shape_poly_set.cpp.

95 {
96 }

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

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

References m_polys.

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

◆ AddOutline()

int SHAPE_POLY_SET::AddOutline ( const SHAPE_LINE_CHAIN aOutline)

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

Definition at line 425 of file shape_poly_set.cpp.

426 {
427  assert( aOutline.IsClosed() );
428 
429  POLYGON poly;
430 
431  poly.push_back( aOutline );
432 
433  m_polys.push_back( poly );
434 
435  return m_polys.size() - 1;
436 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
bool IsClosed() const override
Function IsClosed()

References SHAPE_LINE_CHAIN::IsClosed(), and m_polys.

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

◆ Append() [1/3]

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

218 {
219  assert( m_polys.size() );
220 
221  if( aOutline < 0 )
222  aOutline += m_polys.size();
223 
224  int idx;
225 
226  if( aHole < 0 )
227  idx = 0;
228  else
229  idx = aHole + 1;
230 
231  assert( aOutline < (int) m_polys.size() );
232  assert( idx < (int) m_polys[aOutline].size() );
233 
234  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
235 
236  return m_polys[aOutline][idx].PointCount();
237 }

References m_polys.

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), ZONE_FILLER::addKnockout(), AR_AUTOPLACER::addPad(), PAD::AddPrimitivePoly(), Append(), ZONE::AppendCorner(), BuildBoardPolygonOutlines(), ZONE_FILLER::buildCopperItemClearances(), BuildFootprintPolygonOutlines(), ConvertOutlineToPolygon(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), BITMAPCONV_INFO::createOutputData(), BOARD_ADAPTER::createPadWithClearance(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), fillArcPOLY(), FOOTPRINT::GetBoundingHull(), getRectangleAlongCentreLine(), PCB_SHAPE::HitTest(), PAD::HitTest(), InsertVertex(), CONVERT_TOOL::LinesToPoly(), FABMASTER::loadFootprints(), EAGLE_PLUGIN::loadPolygon(), FABMASTER::loadShapePolySet(), FABMASTER::loadZone(), LEGACY_PLUGIN::loadZONE_CONTAINER(), PCB_PARSER::parseZONE(), DXF_PLOTTER::PlotPoly(), PlotStandardLayer(), RENDER_3D_LEGACY::reload(), PCB_SHAPE::Rotate(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), PCB_SHAPE::SetPolyPoints(), DS_DATA_ITEM_POLYGONS::SyncDrawItems(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRingToPolygon(), TransformRoundChamferedRectToPolygon(), TransformRoundRectToPolygon(), PCB_SHAPE::TransformShapeWithClearanceToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), ZONE::TransformSmoothedOutlineToPolygon(), ZONE::TransformSolidAreasShapesToPolygon(), ALIGNED_DIMENSION::updateGeometry(), ORTHOGONAL_DIMENSION::updateGeometry(), and LEADER::updateGeometry().

◆ Append() [2/3]

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

1449 {
1450  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1451 }

References m_polys.

◆ Append() [3/3]

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

Definition at line 1454 of file shape_poly_set.cpp.

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

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

◆ Area()

double SHAPE_POLY_SET::Area ( )

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

Definition at line 458 of file shape_poly_set.cpp.

459 {
460  double area = 0.0;
461 
462  for( int i = 0; i < OutlineCount(); i++ )
463  {
464  area += Outline( i ).Area();
465 
466  for( int j = 0; j < HoleCount( i ); j++ )
467  area -= Hole( i, j ).Area();
468  }
469 
470  return area;
471 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
SHAPE_LINE_CHAIN & Outline(int aIndex)
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.

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

Referenced by CADSTAR_PCB_ARCHIVE_LOADER::calculateZonePriorities().

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

1204 {
1205  BOX2I bb;
1206 
1207  for( unsigned i = 0; i < m_polys.size(); i++ )
1208  {
1209  if( i == 0 )
1210  bb = m_polys[i][0].BBox();
1211  else
1212  bb.Merge( m_polys[i][0].BBox() );
1213  }
1214 
1215  bb.Inflate( aClearance );
1216  return bb;
1217 }
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect.
Definition: box2.h:386
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.

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

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

◆ BBoxFromCaches()

const BOX2I SHAPE_POLY_SET::BBoxFromCaches ( ) const

Definition at line 1220 of file shape_poly_set.cpp.

1221 {
1222  BOX2I bb;
1223 
1224  for( unsigned i = 0; i < m_polys.size(); i++ )
1225  {
1226  if( i == 0 )
1227  bb = m_polys[i][0].BBoxFromCache();
1228  else
1229  bb.Merge( m_polys[i][0].BBoxFromCache() );
1230  }
1231 
1232  return bb;
1233 }
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect.
Definition: box2.h:386

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

Referenced by DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances().

◆ BooleanAdd() [1/2]

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

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

Definition at line 510 of file shape_poly_set.cpp.

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

References booleanOp().

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

◆ BooleanAdd() [2/2]

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

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

Definition at line 528 of file shape_poly_set.cpp.

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

References booleanOp().

◆ BooleanIntersection() [1/2]

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

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

Definition at line 522 of file shape_poly_set.cpp.

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

References booleanOp().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE::BuildSmoothedPoly(), CADSTAR_PCB_ARCHIVE_LOADER::calculateZonePriorities(), ZONE_FILLER::computeRawFilledArea(), CovertPolygonToBlocks(), PAD::HitTest(), isCopperOutside(), PAD_TOOL::recombinePad(), RENDER_3D_LEGACY::reload(), TransformOvalToPolygon(), and TransformRoundRectToPolygon().

◆ BooleanIntersection() [2/2]

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

Definition at line 544 of file shape_poly_set.cpp.

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

References booleanOp().

◆ booleanOp() [1/2]

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

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

and polygon simplification (merging overlapping polygons).

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

Definition at line 474 of file shape_poly_set.cpp.

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

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

◆ booleanOp() [2/2]

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

Definition at line 481 of file shape_poly_set.cpp.

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

References importTree(), m_polys, and PM_STRICTLY_SIMPLE.

◆ BooleanSubtract() [1/2]

◆ BooleanSubtract() [2/2]

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

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

Definition at line 536 of file shape_poly_set.cpp.

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

References booleanOp().

◆ BuildBBoxCaches()

void SHAPE_POLY_SET::BuildBBoxCaches ( ) const

Construct BBoxCaches for Contains(), below.

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

Definition at line 1528 of file shape_poly_set.cpp.

1529 {
1530  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1531  {
1532  COutline( polygonIdx ).GenerateBBoxCache();
1533 
1534  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1535  CHole( polygonIdx, holeIdx ).GenerateBBoxCache();
1536  }
1537 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void GenerateBBoxCache() const

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

Referenced by ZONE_FILLER::computeRawFilledArea().

◆ CacheTriangulation()

void SHAPE_POLY_SET::CacheTriangulation ( bool  aPartition = true)

Definition at line 2123 of file shape_poly_set.cpp.

2124 {
2125  bool recalculate = !m_hash.IsValid();
2126  MD5_HASH hash;
2127 
2128  if( !m_triangulationValid )
2129  recalculate = true;
2130 
2131  if( !recalculate )
2132  {
2133  hash = checksum();
2134 
2135  if( m_hash != hash )
2136  {
2137  m_hash = hash;
2138  recalculate = true;
2139  }
2140  }
2141 
2142  if( !recalculate )
2143  return;
2144 
2145  SHAPE_POLY_SET tmpSet;
2146 
2147  if( aPartition )
2148  {
2149  // This partitions into regularly-sized grids (1cm in pcbnew)
2150  partitionPolyIntoRegularCellGrid( *this, 1e7, tmpSet );
2151  }
2152  else
2153  {
2154  tmpSet = *this;
2155 
2156  if( tmpSet.HasHoles() )
2157  tmpSet.Fracture( PM_FAST );
2158  }
2159 
2160  m_triangulatedPolys.clear();
2161  m_triangulationValid = false;
2162 
2163  while( tmpSet.OutlineCount() > 0 )
2164  {
2165  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2166  PolygonTriangulation tess( *m_triangulatedPolys.back() );
2167 
2168  // If the tesselation fails, we re-fracture the polygon, which will
2169  // first simplify the system before fracturing and removing the holes
2170  // This may result in multiple, disjoint polygons.
2171  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
2172  {
2173  tmpSet.Fracture( PM_FAST );
2174  m_triangulationValid = false;
2175  continue;
2176  }
2177 
2178  tmpSet.DeletePolygon( 0 );
2179  m_triangulationValid = true;
2180  }
2181 
2182  if( m_triangulationValid )
2183  m_hash = checksum();
2184 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
MD5_HASH checksum() const
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
void DeletePolygon(int aIdx)
static void partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize, SHAPE_POLY_SET &aOut)
Represent a set of closed polygons.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
POLYGON & Polygon(int aIndex)
bool IsValid() const
Definition: md5_hash.h:24

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

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

◆ CalcShape()

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

Definition at line 713 of file wrlfacet.cpp.

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

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

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

◆ Centre()

virtual VECTOR2I SHAPE::Centre ( ) const
inlinevirtualinherited

Compute a center-of-mass of the shape.

Returns
the center-of-mass point

Definition at line 216 of file shape.h.

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

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

1826 {
1827  SHAPE_POLY_SET chamfered;
1828 
1829  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1830  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
1831 
1832  return chamfered;
1833 }
Represent a set of closed polygons.
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.

References ChamferPolygon(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone().

◆ chamferFilletPolygon()

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

Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode selected.

Parameters
aModerepresent which action will be taken: CORNER_MODE::CHAMFERED will return a chamfered version of the polygon, CORNER_MODE::FILLETED will return a filleted version of the polygon.
aDistanceis the chamfering distance if aMode = CHAMFERED; if aMode = FILLETED, is the filleting radius.
aIndexis the index of the polygon that will be chamfered/filleted.
aErrorMaxis the maximum allowable deviation of the polygon from the circle if aMode = FILLETED. If aMode = CHAMFERED, it is unused.
Returns
the chamfered/filleted version of the polygon.Return true if the polygon set has any holes that touch share a vertex.

Definition at line 1847 of file shape_poly_set.cpp.

1849 {
1850  // Null segments create serious issues in calculations. Remove them:
1852 
1853  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1854  SHAPE_POLY_SET::POLYGON newPoly;
1855 
1856  // If the chamfering distance is zero, then the polygon remain intact.
1857  if( aDistance == 0 )
1858  {
1859  return currentPoly;
1860  }
1861 
1862  // Iterate through all the contours (outline and holes) of the polygon.
1863  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1864  {
1865  // Generate a new contour in the new polygon
1866  SHAPE_LINE_CHAIN newContour;
1867 
1868  // Iterate through the vertices of the contour
1869  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1870  {
1871  // Current vertex
1872  int x1 = currContour.CPoint( currVertex ).x;
1873  int y1 = currContour.CPoint( currVertex ).y;
1874 
1875  // Indices for previous and next vertices.
1876  int prevVertex;
1877  int nextVertex;
1878 
1879  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1880 
1881  // Previous vertex is the last one if the current vertex is the first one
1882  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1883 
1884  // next vertex is the first one if the current vertex is the last one.
1885  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1886 
1887  // Previous vertex computation
1888  double xa = currContour.CPoint( prevVertex ).x - x1;
1889  double ya = currContour.CPoint( prevVertex ).y - y1;
1890 
1891  // Next vertex computation
1892  double xb = currContour.CPoint( nextVertex ).x - x1;
1893  double yb = currContour.CPoint( nextVertex ).y - y1;
1894 
1895  // Compute the new distances
1896  double lena = hypot( xa, ya );
1897  double lenb = hypot( xb, yb );
1898 
1899  // Make the final computations depending on the mode selected, chamfered or filleted.
1900  if( aMode == CORNER_MODE::CHAMFERED )
1901  {
1902  double distance = aDistance;
1903 
1904  // Chamfer one half of an edge at most
1905  if( 0.5 * lena < distance )
1906  distance = 0.5 * lena;
1907 
1908  if( 0.5 * lenb < distance )
1909  distance = 0.5 * lenb;
1910 
1911  int nx1 = KiROUND( distance * xa / lena );
1912  int ny1 = KiROUND( distance * ya / lena );
1913 
1914  newContour.Append( x1 + nx1, y1 + ny1 );
1915 
1916  int nx2 = KiROUND( distance * xb / lenb );
1917  int ny2 = KiROUND( distance * yb / lenb );
1918 
1919  newContour.Append( x1 + nx2, y1 + ny2 );
1920  }
1921  else // CORNER_MODE = FILLETED
1922  {
1923  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1924 
1925  double radius = aDistance;
1926  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1927 
1928  // Do nothing in case of parallel edges
1929  if( std::isinf( denom ) )
1930  continue;
1931 
1932  // Limit rounding distance to one half of an edge
1933  if( 0.5 * lena * denom < radius )
1934  radius = 0.5 * lena * denom;
1935 
1936  if( 0.5 * lenb * denom < radius )
1937  radius = 0.5 * lenb * denom;
1938 
1939  // Calculate fillet arc absolute center point (xc, yx)
1940  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1941  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1942  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1943  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1944  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1945 
1946  // Calculate arc start and end vectors
1947  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1948  double xs = x1 + k * xa / lena - xc;
1949  double ys = y1 + k * ya / lena - yc;
1950  double xe = x1 + k * xb / lenb - xc;
1951  double ye = y1 + k * yb / lenb - yc;
1952 
1953  // Cosine of arc angle
1954  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1955 
1956  // Make sure the argument is in [-1,1], interval in which the acos function is
1957  // defined
1958  if( argument < -1 )
1959  argument = -1;
1960  else if( argument > 1 )
1961  argument = 1;
1962 
1963  double arcAngle = acos( argument );
1964  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1965  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1966 
1967  double deltaAngle = arcAngle / segments;
1968  double startAngle = atan2( -ys, xs );
1969 
1970  // Flip arc for inner corners
1971  if( xa * yb - ya * xb <= 0 )
1972  deltaAngle *= -1;
1973 
1974  double nx = xc + xs;
1975  double ny = yc + ys;
1976 
1977  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1978 
1979  // Store the previous added corner to make a sanity check
1980  int prevX = KiROUND( nx );
1981  int prevY = KiROUND( ny );
1982 
1983  for( int j = 0; j < segments; j++ )
1984  {
1985  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1986  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1987 
1988  // Sanity check: the rounding can produce repeated corners; do not add them.
1989  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1990  {
1991  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1992  prevX = KiROUND( nx );
1993  prevY = KiROUND( ny );
1994  }
1995  }
1996  }
1997  }
1998 
1999  // Close the current contour and add it the new polygon
2000  newContour.SetClosed( true );
2001  newPoly.push_back( newContour );
2002  }
2003 
2004  return newPoly;
2005 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetClosed(bool aClosed)
Function SetClosed()
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
SHAPE_LINE_CHAIN.
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:68
POLYGON & Polygon(int aIndex)
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)

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

Referenced by ChamferPolygon(), and FilletPolygon().

◆ ChamferPolygon()

SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon ( unsigned int  aDistance,
int  aIndex 
)

Return a chamfered version of the aIndex-th polygon.

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

Definition at line 1676 of file shape_poly_set.cpp.

1677 {
1678  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
1679 }
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 2187 of file shape_poly_set.cpp.

2188 {
2189  MD5_HASH hash;
2190 
2191  hash.Hash( m_polys.size() );
2192 
2193  for( const auto& outline : m_polys )
2194  {
2195  hash.Hash( outline.size() );
2196 
2197  for( const auto& lc : outline )
2198  {
2199  hash.Hash( lc.PointCount() );
2200 
2201  for( int i = 0; i < lc.PointCount(); i++ )
2202  {
2203  hash.Hash( lc.CPoint( i ).x );
2204  hash.Hash( lc.CPoint( i ).y );
2205  }
2206  }
2207  }
2208 
2209  hash.Finalize();
2210 
2211  return hash;
2212 }
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:65
void Finalize()
Definition: md5_hash.cpp:75

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

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

◆ CHole()

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

◆ CIterate() [1/3]

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

Definition at line 770 of file shape_poly_set.h.

771  {
772  CONST_ITERATOR iter;
773 
774  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
775  iter.m_currentPolygon = aFirst;
776  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
777  iter.m_currentContour = 0;
778  iter.m_currentVertex = 0;
779  iter.m_iterateHoles = aIterateHoles;
780 
781  return iter;
782  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR

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

Referenced by PAD::AddPrimitivePoly(), PCB_SHAPE::BuildPolyPointsList(), ConvertOutlineToPolygon(), PCB_IO::format(), PCB_SHAPE::GetBoundingBox(), ZONE::GetInteractingZones(), and PNS_KICAD_IFACE_BASE::syncPad().

◆ CIterate() [2/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aOutline) const
inline

Definition at line 784 of file shape_poly_set.h.

785  {
786  return CIterate( aOutline, aOutline );
787  }
CONST_ITERATOR CIterate() const

References CIterate().

◆ CIterate() [3/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( ) const
inline

Definition at line 794 of file shape_poly_set.h.

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

References OutlineCount().

Referenced by CIterate(), and CIterateWithHoles().

◆ CIterateSegments() [1/3]

◆ CIterateSegments() [2/3]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegments ( int  aPolygonIdx) const
inline

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

Definition at line 863 of file shape_poly_set.h.

References CIterateSegments().

◆ CIterateSegments() [3/3]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegments ( ) const
inline

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

Definition at line 875 of file shape_poly_set.h.

References OutlineCount().

Referenced by CIterateSegments(), and CIterateSegmentsWithHoles().

◆ CIterateSegmentsWithHoles() [1/2]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegmentsWithHoles ( ) const
inline

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

Definition at line 893 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 899 of file shape_poly_set.h.

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

References CIterateSegments().

◆ CIterateWithHoles() [1/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( int  aOutline) const
inline

Definition at line 789 of file shape_poly_set.h.

790  {
791  return CIterate( aOutline, aOutline, true );
792  }
CONST_ITERATOR CIterate() const

References CIterate().

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

◆ CIterateWithHoles() [2/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( ) const
inline

Definition at line 799 of file shape_poly_set.h.

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

References CIterate(), and OutlineCount().

Referenced by CollideVertex().

◆ Clone()

SHAPE * SHAPE_POLY_SET::Clone ( ) const
overridevirtual

Return a dynamically allocated copy of the shape.

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

Reimplemented from SHAPE.

Definition at line 99 of file shape_poly_set.cpp.

100 {
101  return new SHAPE_POLY_SET( *this );
102 }

References SHAPE_POLY_SET().

◆ Collide() [1/4]

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

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

Parameters
aShapeshape to check collision against
aClearanceminimum clearance
aMTVminimum translation vector
aActual[out] an optional pointer to an int to store the actual distance in the event of a collision.
aLocation[out] an option pointer to a point to store a nearby location in the event of a collision.
Returns
true, if there is a collision.

Reimplemented in SHAPE_RECT, SHAPE_SEGMENT, and SHAPE_COMPOUND.

Definition at line 881 of file shape_collisions.cpp.

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

References collideShapes().

◆ Collide() [2/4]

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

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

Parameters
aShapeshape to check collision against
aClearanceminimum clearance
aActual[out] an optional pointer to an int to store the actual distance in the event of a collision.
aLocation[out] an option pointer to a point to store a nearby location in the event of a collision.
Returns
true if there is a collision.

Reimplemented from SHAPE.

Definition at line 1295 of file shape_poly_set.cpp.

1297 {
1298  // A couple of simple cases are worth trying before we fall back on triangulation.
1299 
1300  if( aShape->Type() == SH_SEGMENT )
1301  {
1302  const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
1303  int extra = segment->GetWidth() / 2;
1304 
1305  if( Collide( segment->GetSeg(), aClearance + extra, aActual, aLocation ) )
1306  {
1307  if( aActual )
1308  *aActual = std::max( 0, *aActual - extra );
1309 
1310  return true;
1311  }
1312 
1313  return false;
1314  }
1315 
1316  if( aShape->Type() == SH_CIRCLE )
1317  {
1318  const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
1319  int extra = circle->GetRadius();
1320 
1321  if( Collide( circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
1322  {
1323  if( aActual )
1324  *aActual = std::max( 0, *aActual - extra );
1325 
1326  return true;
1327  }
1328 
1329  return false;
1330  }
1331 
1332  const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( true );
1333 
1334  int actual = INT_MAX;
1335  VECTOR2I location;
1336 
1337  for( const auto& tpoly : m_triangulatedPolys )
1338  {
1339  for ( const auto& tri : tpoly->Triangles() )
1340  {
1341  int triActual;
1342  VECTOR2I triLocation;
1343 
1344  if( aShape->Collide( &tri, aClearance, &triActual, &triLocation ) )
1345  {
1346  if( !aActual && !aLocation )
1347  return true;
1348 
1349  if( triActual < actual )
1350  {
1351  actual = triActual;
1352  location = triLocation;
1353  }
1354  }
1355  }
1356  }
1357 
1358  if( actual < INT_MAX )
1359  {
1360  if( aActual )
1361  *aActual = std::max( 0, actual );
1362 
1363  if( aLocation )
1364  *aLocation = location;
1365 
1366  return true;
1367  }
1368 
1369  return false;
1370 }
int GetRadius() const
Definition: shape_circle.h:107
const VECTOR2I GetCenter() const
Definition: shape_circle.h:112
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:165
const SEG & GetSeg() const
circle
Definition: shape.h:46
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
int GetWidth() const
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:94
line segment
Definition: shape.h:44

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

Referenced by DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), PCB_SHAPE::HitTest(), FOOTPRINT::HitTestAccurate(), PCB_SELECTION_TOOL::hitTestDistance(), insideArea(), insideFootprintCourtyard(), and DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances().

◆ Collide() [3/4]

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

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

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

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

Parameters
aPis the VECTOR2I point whose collision with respect to the poly set will be tested.
aClearanceis the security distance; if the point lies closer to the polygon than aClearance distance, then there is a collision.
aActualan optional pointer to an int to store the actual distance in the event of a collision.
Returns
true if the point aP collides with the polygon; false in any other case.

Reimplemented from SHAPE.

Definition at line 1274 of file shape_poly_set.cpp.

1276 {
1277  VECTOR2I nearest;
1278  ecoord dist_sq = SquaredDistance( aP, aLocation ? &nearest : nullptr );
1279 
1280  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1281  {
1282  if( aLocation )
1283  *aLocation = nearest;
1284 
1285  if( aActual )
1286  *aActual = sqrt( dist_sq );
1287 
1288  return true;
1289  }
1290 
1291  return false;
1292 }
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() [4/4]

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

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

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

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

Parameters
aSegis the SEG segment whose collision with respect to the poly set will be tested.
aClearanceis the security distance; if the segment passes closer to the polygon than aClearance distance, then there is a collision.
aActualan optional pointer to an int to store the actual distance in the event of a collision.
Returns
true if the segment aSeg collides with the polygon, false in any other case.

Implements SHAPE.

Definition at line 1253 of file shape_poly_set.cpp.

1255 {
1256  VECTOR2I nearest;
1257  ecoord dist_sq = SquaredDistance( aSeg, aLocation ? &nearest : nullptr );
1258 
1259  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1260  {
1261  if( aLocation )
1262  *aLocation = nearest;
1263 
1264  if( aActual )
1265  *aActual = sqrt( dist_sq );
1266 
1267  return true;
1268  }
1269 
1270  return false;
1271 }
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().

◆ CollideEdge()

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

Check whether aPoint collides with any edge of any of the contours of the polygon.

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

Definition at line 1499 of file shape_poly_set.cpp.

1502 {
1503  // Shows whether there was a collision
1504  bool collision = false;
1505 
1506  for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
1507  {
1508  const SEG currentSegment = *iterator;
1509  int distance = currentSegment.Distance( aPoint );
1510 
1511  // Check for collisions
1512  if( distance <= aClearance )
1513  {
1514  collision = true;
1515 
1516  // Update aClearance to look for closer edges
1517  aClearance = distance;
1518 
1519  // Store the indices that identify the vertex
1520  aClosestVertex = iterator.GetIndex();
1521  }
1522  }
1523 
1524  return collision;
1525 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.h:239
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
Definition: seg.h:41

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

Referenced by PCB_SHAPE::HitTest(), and ZONE::HitTestForEdge().

◆ CollideVertex()

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

Check whether aPoint collides with any vertex of any of the contours of the polygon.

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

Definition at line 1460 of file shape_poly_set.cpp.

1463 {
1464  // Shows whether there was a collision
1465  bool collision = false;
1466 
1467  // Difference vector between each vertex and aPoint.
1468  VECTOR2D delta;
1469  double distance, clearance;
1470 
1471  // Convert clearance to double for precission when comparing distances
1472  clearance = aClearance;
1473 
1474  for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
1475  {
1476  // Get the difference vector between current vertex and aPoint
1477  delta = *iterator - aPoint;
1478 
1479  // Compute distance
1480  distance = delta.EuclideanNorm();
1481 
1482  // Check for collisions
1483  if( distance <= clearance )
1484  {
1485  collision = true;
1486 
1487  // Update aClearance to look for closer vertices
1488  clearance = distance;
1489 
1490  // Store the indices that identify the vertex
1491  aClosestVertex = iterator.GetIndex();
1492  }
1493  }
1494 
1495  return collision;
1496 }
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
CONST_ITERATOR CIterateWithHoles() const

References CIterateWithHoles(), distance(), and VECTOR2< T >::EuclideanNorm().

Referenced by ZONE::HitTestForCorner().

◆ Contains()

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

Return true if a given subpolygon contains the point aP.

Parameters
aPis the point to check
aSubpolyIndexis the subpolygon to check, or -1 to check all
aUseBBoxCachesgives faster performance when multiple calls are made with no editing in between, but the caller MUST cache the bbox caches before calling (via BuildBBoxCaches(), above)
Returns
true if the polygon contains the pointReturn true if the set is empty (no polygons at all)

Definition at line 1540 of file shape_poly_set.cpp.

1542 {
1543  if( m_polys.empty() )
1544  return false;
1545 
1546  // If there is a polygon specified, check the condition against that polygon
1547  if( aSubpolyIndex >= 0 )
1548  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1549 
1550  // In any other case, check it against all polygons in the set
1551  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1552  {
1553  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1554  return true;
1555  }
1556 
1557  return false;
1558 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.

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

Referenced by SHAPE_RECT::Collide(), ZONE_FILLER::computeRawFilledArea(), ZONE_FILLER::Fill(), PAD::GetBestAnchorPosition(), CADSTAR_PCB_ARCHIVE_LOADER::getKiCadPad(), GERBER_DRAW_ITEM::HitTest(), ZONE::HitTestFilledArea(), DIMENSION_BASE::segPolyIntersection(), BOARD::TestZoneIntersection(), ALIGNED_DIMENSION::updateGeometry(), and ORTHOGONAL_DIMENSION::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 1596 of file shape_poly_set.cpp.

1598 {
1599  // Check that the point is inside the outline
1600  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1601  {
1602  // Check that the point is not in any of the holes
1603  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1604  {
1605  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1606 
1607  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1608  // here as it's meaning would be inverted.
1609  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1610  return false;
1611  }
1612 
1613  return true;
1614  }
1615 
1616  return false;
1617 }
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
SHAPE_LINE_CHAIN.

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

Referenced by Contains(), and SquaredDistanceToPolygon().

◆ COutline()

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

◆ CPolygon()

◆ CVertex() [1/3]

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

Return the aGlobalIndex-th vertex in the poly set.

Definition at line 302 of file shape_poly_set.cpp.

303 {
304  if( aOutline < 0 )
305  aOutline += m_polys.size();
306 
307  int idx;
308 
309  if( aHole < 0 )
310  idx = 0;
311  else
312  idx = aHole + 1;
313 
314  assert( aOutline < (int) m_polys.size() );
315  assert( idx < (int) m_polys[aOutline].size() );
316 
317  return m_polys[aOutline][idx].CPoint( aIndex );
318 }

References m_polys.

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

◆ CVertex() [2/3]

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

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

Definition at line 321 of file shape_poly_set.cpp.

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

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

◆ CVertex() [3/3]

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

Definition at line 333 of file shape_poly_set.cpp.

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

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

◆ Deflate()

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

Definition at line 974 of file shape_poly_set.h.

976  {
977  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
978  }
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.

References Inflate().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE::BuildSmoothedPoly(), ZONE_FILLER::computeRawFilledArea(), ZONE_FILLER::fillSingleZone(), insideArea(), ALTIUM_PCB::ParseRegions6Data(), and PlotSolderMaskLayer().

◆ DeletePolygon()

void SHAPE_POLY_SET::DeletePolygon ( int  aIdx)

Definition at line 1442 of file shape_poly_set.cpp.

1443 {
1444  m_polys.erase( m_polys.begin() + aIdx );
1445 }

References m_polys.

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

◆ Fillet()

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

Return a filleted version of the polygon set.

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

Definition at line 1836 of file shape_poly_set.cpp.

1837 {
1838  SHAPE_POLY_SET filleted;
1839 
1840  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1841  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
1842 
1843  return filleted;
1844 }
Represent a set of closed polygons.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.

References FilletPolygon(), and m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone().

◆ FilletPolygon()

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

Return a filleted version of the aIndex-th polygon.

Parameters
aRadiusis the fillet radius.
aErrorMaxis the maximum allowable deviation of the polygon from the circle
aIndexis the index of the polygon to be filleted
Returns
A polygon containing the filleted version of the aIndex-th polygon.

Definition at line 1682 of file shape_poly_set.cpp.

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

References chamferFilletPolygon(), and FILLETED.

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

◆ Format()

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

Reimplemented from SHAPE.

Definition at line 1113 of file shape_poly_set.cpp.

1114 {
1115  std::stringstream ss;
1116 
1117  ss << "SHAPE_LINE_CHAIN poly; \n";
1118 
1119  for( unsigned i = 0; i < m_polys.size(); i++ )
1120  {
1121  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1122  {
1123 
1124  ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
1125 
1126  SHAPE_POLY_SET poly;
1127 
1128  if( j == 0 )
1129  {
1130  ss << " poly.AddOutline(tmp); } \n";
1131  }
1132  else
1133  {
1134  ss << " poly.AddHole(tmp); } \n";
1135  }
1136 
1137  }
1138  }
1139 
1140  return ss.str();
1141 }
Represent a set of closed polygons.

References m_polys.

◆ Fracture()

void SHAPE_POLY_SET::Fracture ( POLYGON_MODE  aFastMode)

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

Definition at line 874 of file shape_poly_set.cpp.

875 {
876  Simplify( aFastMode ); // remove overlapping holes/degeneracy
877 
878  for( POLYGON& paths : m_polys )
879  {
880  fractureSingle( paths );
881  }
882 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void fractureSingle(POLYGON &paths)
void Simplify(POLYGON_MODE aFastMode)

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

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

◆ fractureSingle()

void SHAPE_POLY_SET::fractureSingle ( POLYGON paths)
private

Definition at line 770 of file shape_poly_set.cpp.

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

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

Referenced by Fracture().

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

147 {
148  int selectedVertex = aRelativeIndices.m_vertex;
149  unsigned int selectedContour = aRelativeIndices.m_contour;
150  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
151 
152  // Check whether the vertex indices make sense in this poly set
153  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
154  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
155  {
156  POLYGON currentPolygon;
157 
158  aGlobalIdx = 0;
159 
160  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
161  {
162  currentPolygon = Polygon( polygonIdx );
163 
164  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
165  {
166  aGlobalIdx += currentPolygon[contourIdx].PointCount();
167  }
168  }
169 
170  currentPolygon = Polygon( selectedPolygon );
171 
172  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
173  {
174  aGlobalIdx += currentPolygon[contourIdx].PointCount();
175  }
176 
177  aGlobalIdx += selectedVertex;
178 
179  return true;
180  }
181  else
182  {
183  return false;
184  }
185 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
POLYGON & Polygon(int aIndex)

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

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

◆ GetHash()

MD5_HASH SHAPE_POLY_SET::GetHash ( ) const

Definition at line 2030 of file shape_poly_set.cpp.

2031 {
2032  if( !m_hash.IsValid() )
2033  return checksum();
2034 
2035  return m_hash;
2036 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:24

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

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

◆ GetIndexableSubshapeCount()

size_t SHAPE_POLY_SET::GetIndexableSubshapeCount ( ) const
overridevirtual

Reimplemented from SHAPE_BASE.

Definition at line 2258 of file shape_poly_set.cpp.

2259 {
2260  size_t n = 0;
2261 
2262  for( auto& t : m_triangulatedPolys )
2263  n += t->GetTriangleCount();
2264 
2265  return n;
2266 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys

References m_triangulatedPolys.

Referenced by GetIndexableSubshapes().

◆ GetIndexableSubshapes()

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

Reimplemented from SHAPE_BASE.

Definition at line 2269 of file shape_poly_set.cpp.

2270 {
2271  aSubshapes.reserve( GetIndexableSubshapeCount() );
2272 
2273  for( auto& tpoly : m_triangulatedPolys )
2274  {
2275  for ( auto& tri : tpoly->Triangles() )
2276  {
2277  aSubshapes.push_back( &tri );
2278  }
2279  }
2280 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
virtual size_t GetIndexableSubshapeCount() const override

References GetIndexableSubshapeCount(), and m_triangulatedPolys.

◆ GetNeighbourIndexes()

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

Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a contour in the polygon set.

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

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

Definition at line 339 of file shape_poly_set.cpp.

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

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

Referenced by ZONE::MoveEdge().

◆ GetRelativeIndices()

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

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

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

Definition at line 105 of file shape_poly_set.cpp.

107 {
108  int polygonIdx = 0;
109  unsigned int contourIdx = 0;
110  int vertexIdx = 0;
111 
112  int currentGlobalIdx = 0;
113 
114  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
115  {
116  const POLYGON& currentPolygon = CPolygon( polygonIdx );
117 
118  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
119  {
120  const SHAPE_LINE_CHAIN& currentContour = currentPolygon[contourIdx];
121  int totalPoints = currentContour.PointCount();
122 
123  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
124  {
125  // Check if the current vertex is the globally indexed as aGlobalIdx
126  if( currentGlobalIdx == aGlobalIdx )
127  {
128  aRelativeIndices->m_polygon = polygonIdx;
129  aRelativeIndices->m_contour = contourIdx;
130  aRelativeIndices->m_vertex = vertexIdx;
131 
132  return true;
133  }
134 
135  // Advance
136  currentGlobalIdx++;
137  }
138  }
139  }
140 
141  return false;
142 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
const POLYGON & CPolygon(int aIndex) const
int OutlineCount() const
Return the number of vertices in a given outline/hole.
int PointCount() const
Function PointCount()
SHAPE_LINE_CHAIN.

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

Referenced by CVertex(), 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 1046 of file shape_poly_set.cpp.

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

References m_polys.

Referenced by CacheTriangulation().

◆ HasIndexableSubshapes()

bool SHAPE_POLY_SET::HasIndexableSubshapes ( ) const
overridevirtual

Reimplemented from SHAPE_BASE.

Definition at line 2252 of file shape_poly_set.cpp.

2253 {
2254  return IsTriangulationUpToDate();
2255 }
bool IsTriangulationUpToDate() const

References IsTriangulationUpToDate().

◆ HasTouchingHoles()

bool SHAPE_POLY_SET::HasTouchingHoles ( ) const

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

Definition at line 2215 of file shape_poly_set.cpp.

2216 {
2217  for( int i = 0; i < OutlineCount(); i++ )
2218  {
2219  if( hasTouchingHoles( CPolygon( i ) ) )
2220  {
2221  return true;
2222  }
2223  }
2224 
2225  return false;
2226 }
const POLYGON & CPolygon(int aIndex) const
int OutlineCount() const
Return the number of vertices in a given outline/hole.
bool hasTouchingHoles(const POLYGON &aPoly) const

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

◆ hasTouchingHoles()

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

Definition at line 2229 of file shape_poly_set.cpp.

2230 {
2231  std::set< long long > ptHashes;
2232 
2233  for( const auto& lc : aPoly )
2234  {
2235  for( const VECTOR2I& pt : lc.CPoints() )
2236  {
2237  const long long ptHash = (long long) pt.x << 32 | pt.y;
2238 
2239  if( ptHashes.count( ptHash ) > 0 )
2240  {
2241  return true;
2242  }
2243 
2244  ptHashes.insert( ptHash );
2245  }
2246  }
2247 
2248  return false;
2249 }

Referenced by HasTouchingHoles().

◆ Hole()

◆ HoleCount()

◆ importTree()

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

Definition at line 644 of file shape_poly_set.cpp.

645 {
646  m_polys.clear();
647 
648  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
649  {
650  if( !n->IsHole() )
651  {
652  POLYGON paths;
653  paths.reserve( n->Childs.size() + 1 );
654  paths.push_back( n->Contour );
655 
656  for( unsigned int i = 0; i < n->Childs.size(); i++ )
657  paths.push_back( n->Childs[i]->Contour );
658 
659  m_polys.push_back( paths );
660  }
661  }
662 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.

References m_polys.

Referenced by booleanOp(), and Inflate().

◆ Inflate()

void SHAPE_POLY_SET::Inflate ( int  aAmount,
int  aCircleSegmentsCount,
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.
aCircleSegmentsCountis 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 561 of file shape_poly_set.cpp.

563 {
564  // A static table to avoid repetitive calculations of the coefficient
565  // 1.0 - cos( M_PI / aCircleSegmentsCount )
566  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
567  #define SEG_CNT_MAX 64
568  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
569 
570  ClipperOffset c;
571 
572  // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
573  // and are not what you'd think they are.
574  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
575  JoinType joinType = jtRound; // The way corners are offsetted
576  double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
577  JoinType miterFallback = jtSquare;
578 
579  switch( aCornerStrategy )
580  {
581  case ALLOW_ACUTE_CORNERS:
582  joinType = jtMiter;
583  miterLimit = 10; // Allows large spikes
584  miterFallback = jtSquare;
585  break;
586 
587  case CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
588  joinType = jtMiter;
589  miterFallback = jtRound;
590  break;
591 
592  case ROUND_ACUTE_CORNERS: // Acute angles are rounded
593  joinType = jtMiter;
594  miterFallback = jtSquare;
595  break;
596 
597  case CHAMFER_ALL_CORNERS: // All angles are chamfered.
598  joinType = jtSquare;
599  miterFallback = jtSquare;
600  break;
601 
602  case ROUND_ALL_CORNERS: // All angles are rounded.
603  joinType = jtRound;
604  miterFallback = jtSquare;
605  break;
606  }
607 
608  for( const POLYGON& poly : m_polys )
609  {
610  for( size_t i = 0; i < poly.size(); i++ )
611  c.AddPath( poly[i].convertToClipper( i == 0 ), joinType, etClosedPolygon );
612  }
613 
614  PolyTree solution;
615 
616  // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
617  // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
618  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
619 
620  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
621  aCircleSegmentsCount = 6;
622 
623  double coeff;
624 
625  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
626  {
627  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
628 
629  if( aCircleSegmentsCount <= SEG_CNT_MAX )
630  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
631  }
632  else
633  coeff = arc_tolerance_factor[aCircleSegmentsCount];
634 
635  c.ArcTolerance = std::abs( aAmount ) * coeff;
636  c.MiterLimit = miterLimit;
637  c.MiterFallback = miterFallback;
638  c.Execute( solution, aAmount );
639 
640  importTree( &solution );
641 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
All angles are chamfered.
#define SEG_CNT_MAX
Acute angles are rounded.
Acute angles are chamfered.
just inflate the polygon. Acute angles create spikes
void importTree(ClipperLib::PolyTree *tree)

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

Referenced by FOOTPRINT::BuildPolyCourtyards(), ZONE::BuildSmoothedPoly(), ZONE_FILLER::computeRawFilledArea(), BOARD_ADAPTER::createPadWithClearance(), Deflate(), ZONE_FILLER::fillSingleZone(), GERBER_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadRoundRect(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), InflateWithLinkedHoles(), CADSTAR_PCB_ARCHIVE_LOADER::loadCoppers(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::packagePolygon(), PlotSolderMaskLayer(), PAD::TransformShapeWithClearanceToPolygon(), ZONE::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 singe outline with "slits"/"fractures" connecting the outer ring to the inner holes For aFastMode meaning, see function booleanOp

Definition at line 552 of file shape_poly_set.cpp.

554 {
555  Simplify( aFastMode );
556  Inflate( aFactor, aCircleSegmentsCount );
557  Fracture( aFastMode );
558 }
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
void Simplify(POLYGON_MODE aFastMode)
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.

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

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

◆ InsertVertex()

void SHAPE_POLY_SET::InsertVertex ( int  aGlobalIndex,
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 240 of file shape_poly_set.cpp.

241 {
242  VERTEX_INDEX index;
243 
244  if( aGlobalIndex < 0 )
245  aGlobalIndex = 0;
246 
247  if( aGlobalIndex >= TotalVertices() )
248  {
249  Append( aNewVertex );
250  }
251  else
252  {
253  // Assure the position to be inserted exists; throw an exception otherwise
254  if( GetRelativeIndices( aGlobalIndex, &index ) )
255  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
256  else
257  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
258  }
259 }
int TotalVertices() const
Delete aIdx-th polygon from the set.
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...

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

Referenced by PCB_POINT_EDITOR::addCorner().

◆ IsEmpty()

◆ IsNull()

bool SHAPE::IsNull ( ) const
inlineinherited

Return true if the shape is a null shape.

Return values
trueif null :-)

Definition at line 150 of file shape.h.

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

References SHAPE_BASE::m_type, and SH_NULL.

◆ IsPolygonSelfIntersecting()

bool SHAPE_POLY_SET::IsPolygonSelfIntersecting ( int  aPolygonIndex) const

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

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

Definition at line 386 of file shape_poly_set.cpp.

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

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

414 {
415  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
416  {
417  if( IsPolygonSelfIntersecting( polygon ) )
418  return true;
419  }
420 
421  return false;
422 }
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.

References IsPolygonSelfIntersecting(), and m_polys.

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

◆ IsSolid()

bool SHAPE_POLY_SET::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 1046 of file shape_poly_set.h.

1047  {
1048  return true;
1049  }

◆ IsTriangulationUpToDate()

bool SHAPE_POLY_SET::IsTriangulationUpToDate ( ) const

Definition at line 2039 of file shape_poly_set.cpp.

2040 {
2041  if( !m_triangulationValid )
2042  return false;
2043 
2044  if( !m_hash.IsValid() )
2045  return false;
2046 
2047  MD5_HASH hash = checksum();
2048 
2049  return hash == m_hash;
2050 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:24

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

Referenced by KIGFX::PCB_PAINTER::draw(), KIGFX::OPENGL_GAL::DrawPolygon(), HasIndexableSubshapes(), operator=(), SHAPE_POLY_SET(), and PNS_KICAD_IFACE_BASE::syncZone().

◆ IsVertexInHole()

bool SHAPE_POLY_SET::IsVertexInHole ( int  aGlobalIdx)

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

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

Definition at line 1812 of file shape_poly_set.cpp.

1813 {
1814  VERTEX_INDEX index;
1815 
1816  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1817  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1818  return false;
1819 
1820  // The contour is a hole if its index is greater than zero
1821  return index.m_contour > 0;
1822 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...

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

◆ Iterate() [1/3]

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

Return an object to iterate through the points of the polygons between aFirst and aLast.

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

Definition at line 717 of file shape_poly_set.h.

718  {
719  ITERATOR iter;
720 
721  iter.m_poly = this;
722  iter.m_currentPolygon = aFirst;
723  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
724  iter.m_currentContour = 0;
725  iter.m_currentVertex = 0;
726  iter.m_iterateHoles = aIterateHoles;
727 
728  return iter;
729  }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR

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

Referenced by PCB_POINT_EDITOR::addCorner(), and ZONE::Iterate().

◆ Iterate() [2/3]

ITERATOR SHAPE_POLY_SET::Iterate ( int  aOutline)
inline
Parameters
aOutlineis the index of the polygon to be iterated.
Returns
an iterator object to visit all points in the main outline of the aOutline-th polygon, without visiting the points in the holes.

Definition at line 736 of file shape_poly_set.h.

737  {
738  return Iterate( aOutline, aOutline );
739  }
ITERATOR Iterate()

References Iterate().

◆ Iterate() [3/3]

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

Definition at line 755 of file shape_poly_set.h.

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

References OutlineCount().

Referenced by Iterate(), and IterateWithHoles().

◆ IterateFromVertexWithHoles()

ITERATOR SHAPE_POLY_SET::IterateFromVertexWithHoles ( int  aGlobalIdx)
inline

◆ IterateSegments() [1/3]

◆ IterateSegments() [2/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aPolygonIdx)
inline

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

Definition at line 857 of file shape_poly_set.h.

References IterateSegments().

◆ IterateSegments() [3/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( )
inline

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

Definition at line 869 of file shape_poly_set.h.

References OutlineCount().

Referenced by IterateSegments(), and IterateSegmentsWithHoles().

◆ IterateSegmentsWithHoles() [1/2]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( )
inline

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

Definition at line 881 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 887 of file shape_poly_set.h.

References IterateSegments().

◆ IterateWithHoles() [1/2]

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

Definition at line 746 of file shape_poly_set.h.

747  {
748  return Iterate( aOutline, aOutline, true );
749  }
ITERATOR Iterate()

References Iterate().

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

◆ IterateWithHoles() [2/2]

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

Definition at line 764 of file shape_poly_set.h.

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

References Iterate(), and OutlineCount().

Referenced by IterateFromVertexWithHoles(), and RemoveNullSegments().

◆ Mirror()

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

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

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

Definition at line 1635 of file shape_poly_set.cpp.

1636 {
1637  for( POLYGON& poly : m_polys )
1638  {
1639  for( SHAPE_LINE_CHAIN& path : poly )
1640  path.Mirror( aX, aY, aRef );
1641  }
1642 
1643  if( m_triangulationValid )
1645 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
SHAPE_LINE_CHAIN.
void CacheTriangulation(bool aPartition=true)

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

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

◆ Move()

void SHAPE_POLY_SET::Move ( const VECTOR2I aVector)
overridevirtual

Implements SHAPE.

Definition at line 1620 of file shape_poly_set.cpp.

1621 {
1622  for( POLYGON& poly : m_polys )
1623  {
1624  for( SHAPE_LINE_CHAIN& path : poly )
1625  path.Move( aVector );
1626  }
1627 
1628  for( std::unique_ptr<TRIANGULATED_POLYGON>& tri : m_triangulatedPolys )
1629  tri->Move( aVector );
1630 
1631  m_hash = checksum();
1632 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
MD5_HASH checksum() const
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
SHAPE_LINE_CHAIN.

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

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

◆ NewFacet()

FACET * SHAPE::NewFacet ( )
inherited

Definition at line 705 of file wrlfacet.cpp.

706 {
707  FACET* fp = new FACET;
708  facets.push_back( fp );
709  return fp;
710 }
Definition: wrlfacet.h:41
std::list< FACET * > facets
Definition: wrlfacet.h:143

References SHAPE::facets.

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

◆ NewHole()

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

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

Definition at line 200 of file shape_poly_set.cpp.

201 {
202  SHAPE_LINE_CHAIN empty_path;
203 
204  empty_path.SetClosed( true );
205 
206  // Default outline is the last one
207  if( aOutline < 0 )
208  aOutline += m_polys.size();
209 
210  // Add hole to the selected outline
211  m_polys[aOutline].push_back( empty_path );
212 
213  return m_polys.back().size() - 2;
214 }
void SetClosed(bool aClosed)
Function SetClosed()
SHAPE_LINE_CHAIN.

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

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

◆ NewOutline()

int SHAPE_POLY_SET::NewOutline ( )

Creates a new hole in a given outline.

Definition at line 188 of file shape_poly_set.cpp.

189 {
190  SHAPE_LINE_CHAIN empty_path;
191  POLYGON poly;
192 
193  empty_path.SetClosed( true );
194  poly.push_back( empty_path );
195  m_polys.push_back( poly );
196  return m_polys.size() - 1;
197 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
void SetClosed(bool aClosed)
Function SetClosed()
SHAPE_LINE_CHAIN.

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), ZONE_FILLER::addKnockout(), AR_AUTOPLACER::addPad(), ZONE::AppendCorner(), BuildBoardPolygonOutlines(), BuildFootprintPolygonOutlines(), KI_TEST::CommonTestData::CommonTestData(), ConvertOutlineToPolygon(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), BITMAPCONV_INFO::createOutputData(), BOARD_ADAPTER::createPadWithClearance(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), fillArcPOLY(), FOOTPRINT::GetBoundingHull(), getRectangleAlongCentreLine(), PCB_SHAPE::HitTest(), PAD::HitTest(), FABMASTER::loadFootprints(), EAGLE_PLUGIN::loadPolygon(), FABMASTER::loadShapePolySet(), FABMASTER::loadZone(), LEGACY_PLUGIN::loadZONE_CONTAINER(), PCB_PARSER::parseZONE(), DXF_PLOTTER::PlotPoly(), PlotStandardLayer(), RENDER_3D_LEGACY::reload(), PCB_SHAPE::Rotate(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), PCB_SHAPE::SetPolyPoints(), DS_DATA_ITEM_POLYGONS::SyncDrawItems(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), TransformRoundRectToPolygon(), PCB_SHAPE::TransformShapeWithClearanceToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), ALIGNED_DIMENSION::updateGeometry(), ORTHOGONAL_DIMENSION::updateGeometry(), and LEADER::updateGeometry().

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

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

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

Referenced by BITMAPCONV_INFO::createOutputData(), and BOARD::NormalizeAreaPolygon().

◆ operator=()

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

Definition at line 2008 of file shape_poly_set.cpp.

2009 {
2010  static_cast<SHAPE&>(*this) = aOther;
2011  m_polys = aOther.m_polys;
2012  m_triangulatedPolys.clear();
2013  m_triangulationValid = false;
2014 
2015  if( aOther.IsTriangulationUpToDate() )
2016  {
2017  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
2018  {
2019  const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
2020  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
2021  }
2022 
2023  m_hash = aOther.GetHash();
2024  m_triangulationValid = true;
2025  }
2026 
2027  return *this;
2028 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool IsTriangulationUpToDate() const
MD5_HASH GetHash() const
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const

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

◆ Outline() [1/2]

SHAPE_LINE_CHAIN& SHAPE_POLY_SET::Outline ( int  aIndex)
inline

Definition at line 644 of file shape_poly_set.h.

645  {
646  return m_polys[aIndex][0];
647  }

References m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), Area(), BuildFootprintPolygonOutlines(), ZONE::CalculateFilledArea(), PCB_GRID_HELPER::computeAnchors(), FOOTPRINT::CoverageRatio(), CovertPolygonToBlocks(), 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(), DSN::SPECCTRA_DB::fillBOUNDARY(), AR_AUTOPLACER::fillMatrix(), GERBER_PLOTTER::FlashPadChamferRoundRect(), PSLIKE_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadRoundRect(), DXF_PLOTTER::FlashPadRoundRect(), HPGL_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), PCB_IO::format(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), insideArea(), FABMASTER::loadFootprints(), FABMASTER::loadZone(), DSN::SPECCTRA_DB::makePADSTACK(), BOARD::NormalizeAreaPolygon(), PlotDrawingSheet(), BRDITEMS_PLOTTER::PlotFilledAreas(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), polygonArea(), CONVERT_TOOL::PolyToLines(), GERBER_DRAW_ITEM::PrintGerberPoly(), DS_DRAW_ITEM_POLYPOLYGONS::PrintWsItem(), RENDER_3D_LEGACY::reload(), PCB_POINT_EDITOR::removeCornerCondition(), DRC_TEST_PROVIDER_EDGE_CLEARANCE::Run(), PCB_SHAPE::Scale(), TransformRoundRectToPolygon(), GBR_TO_PCB_EXPORTER::writePcbPolygon(), and GBR_TO_PCB_EXPORTER::writePcbZoneItem().

◆ Outline() [2/2]

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

Definition at line 649 of file shape_poly_set.h.

650  {
651  return m_polys[aIndex][0];
652  }

References m_polys.

◆ OutlineCount()

int SHAPE_POLY_SET::OutlineCount ( ) const
inline

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

Definition at line 626 of file shape_poly_set.h.

References m_polys.

Referenced by PCB_POINT_EDITOR::addCorner(), ZONE_FILLER::addHatchFillTypeOnZone(), PAD::addPadPrimitivesToPolygon(), ZONE::AddPolygon(), BOARD_ADAPTER::addSolidAreasShapes(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), ZONE::AppendCorner(), Area(), BuildBBoxCaches(), BuildBoardPolygonOutlines(), BuildConvexHull(), BuildFootprintPolygonOutlines(), PCB_SHAPE::BuildPolyPointsList(), CacheTriangulation(), ZONE::CalculateFilledArea(), CIterate(), CIterateSegments(), CIterateSegmentsWithHoles(), CIterateWithHoles(), Contains(), CovertPolygonToBlocks(), RENDER_3D_LEGACY::createBoard(), BITMAPCONV_INFO::createOutputData(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), KIGFX::DS_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawApertureMacro(), APERTURE_MACRO::DrawApertureMacroShape(), D_CODE::DrawFlashedPolygon(), D_CODE::DrawFlashedShape(), KIGFX::GERBVIEW_PAINTER::drawFlashedShape(), AR_AUTOPLACER::drawPlacementRoutingMatrix(), KIGFX::CAIRO_GAL_BASE::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), KIGFX::PREVIEW::POLYGON_ITEM::drawPreviewShape(), KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), EXPORTER_PCB_VRML::ExportVrmlBoard(), EXPORTER_PCB_VRML::ExportVrmlPolygonSet(), ZONE_FILLER::Fill(), fillArcPOLY(), DSN::SPECCTRA_DB::fillBOUNDARY(), GEOM_TEST::FilletPolySet(), PSLIKE_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), RENDER_3D_LEGACY::generateHoles(), RENDER_3D_LEGACY::generateLayerList(), RENDER_3D_LEGACY::generateViasAndPads(), APERTURE_MACRO::GetApertureMacroShape(), PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::GetBoundingBox(), FOOTPRINT::GetBoundingHull(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), GetRelativeIndices(), HasTouchingHoles(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), ZONE::HitTestCutout(), insideArea(), isCopperOutside(), Iterate(), IterateSegments(), IterateSegmentsWithHoles(), IterateWithHoles(), CONVERT_TOOL::LinesToPoly(), FABMASTER::loadFootprints(), FABMASTER::loadGraphics(), FABMASTER::loadPolygon(), NormalizeAreaOutlines(), SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::operator bool(), DIALOG_PAD_PROPERTIES::padValuesOK(), partitionPolyIntoRegularCellGrid(), PlotDrawingSheet(), BRDITEMS_PLOTTER::PlotFilledAreas(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), PlotLayerOutlines(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), PlotStandardLayer(), polygon_triangulation_main(), polygonArea(), GERBER_DRAW_ITEM::Print(), DS_DRAW_ITEM_POLYPOLYGONS::PrintWsItem(), RENDER_3D_RAYTRACE::Reload(), ZONE::RemoveCutout(), Subset(), PNS_KICAD_IFACE_BASE::syncZone(), TestConcaveSquareFillet(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testCourtyardClearances(), TestSquareFillet(), HYPERLYNX_EXPORTER::writeBoardInfo(), HYPERLYNX_EXPORTER::writeNetObjects(), GBR_TO_PCB_EXPORTER::writePcbPolygon(), and GBR_TO_PCB_EXPORTER::writePcbZoneItem().

◆ Parse()

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

Reimplemented from SHAPE.

Definition at line 1144 of file shape_poly_set.cpp.

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

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

1237 {
1238  // Iterate through all the polygons in the set
1239  for( const POLYGON& polygon : m_polys )
1240  {
1241  // Iterate through all the line chains in the polygon
1242  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1243  {
1244  if( lineChain.PointOnEdge( aP ) )
1245  return true;
1246  }
1247  }
1248 
1249  return false;
1250 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
SHAPE_LINE_CHAIN.

References m_polys.

◆ Polygon() [1/2]

◆ Polygon() [2/2]

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

Definition at line 682 of file shape_poly_set.h.

683  {
684  return m_polys[aIndex];
685  }

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

1380 {
1381  // Default polygon is the last one
1382  if( aPolygonIdx < 0 )
1383  aPolygonIdx += m_polys.size();
1384 
1385  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1386 }

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

1390 {
1391  int removed = 0;
1392 
1393  ITERATOR iterator = IterateWithHoles();
1394 
1395  VECTOR2I contourStart = *iterator;
1396  VECTOR2I segmentStart, segmentEnd;
1397 
1398  VERTEX_INDEX indexStart;
1399 
1400  while( iterator )
1401  {
1402  // Obtain first point and its index
1403  segmentStart = *iterator;
1404  indexStart = iterator.GetIndex();
1405 
1406  // Obtain last point
1407  if( iterator.IsEndContour() )
1408  {
1409  segmentEnd = contourStart;
1410 
1411  // Advance
1412  iterator++;
1413 
1414  if( iterator )
1415  contourStart = *iterator;
1416  }
1417  else
1418  {
1419  // Advance
1420  iterator++;
1421 
1422  if( iterator )
1423  segmentEnd = *iterator;
1424  }
1425 
1426  // Remove segment start if both points are equal
1427  if( segmentStart == segmentEnd )
1428  {
1429  RemoveVertex( indexStart );
1430  removed++;
1431 
1432  // Advance the iterator one position, as there is one vertex less.
1433  if( iterator )
1434  iterator++;
1435  }
1436  }
1437 
1438  return removed;
1439 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR IterateWithHoles()
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.

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

Referenced by chamferFilletPolygon(), and NormalizeAreaOutlines().

◆ RemoveVertex() [1/2]

void SHAPE_POLY_SET::RemoveVertex ( int  aGlobalIndex)

Delete the aGlobalIndex-th vertex.

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

Definition at line 1561 of file shape_poly_set.cpp.

1562 {
1563  VERTEX_INDEX index;
1564 
1565  // Assure the to be removed vertex exists, abort otherwise
1566  if( GetRelativeIndices( aGlobalIndex, &index ) )
1567  RemoveVertex( index );
1568  else
1569  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1570 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.

References GetRelativeIndices().

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

◆ RemoveVertex() [2/2]

void SHAPE_POLY_SET::RemoveVertex ( VERTEX_INDEX  aRelativeIndices)

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

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

Definition at line 1573 of file shape_poly_set.cpp.

1574 {
1575  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1576 }

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

◆ Rotate()

void SHAPE_POLY_SET::Rotate ( double  aAngle,
const VECTOR2I aCenter = { 0, 0 } 
)
overridevirtual

Rotate all vertices by a given angle.

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

Implements SHAPE.

Definition at line 1648 of file shape_poly_set.cpp.

1649 {
1650  for( POLYGON& poly : m_polys )
1651  {
1652  for( SHAPE_LINE_CHAIN& path : poly )
1653  path.Rotate( aAngle, aCenter );
1654  }
1655 
1656  // Don't re-cache if the triangulation is already invalid
1657  if( m_triangulationValid )
1659 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
SHAPE_LINE_CHAIN.
void CacheTriangulation(bool aPartition=true)

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

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), D_CODE::ConvertShapeToPolygon(), ALTIUM_PCB::HelperDrawsegmentSetLocalCoord(), FABMASTER::loadFootprints(), PCB_SHAPE::Rotate(), ZONE::Rotate(), FOOTPRINT::SetOrientation(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), ALIGNED_DIMENSION::updateGeometry(), ORTHOGONAL_DIMENSION::updateGeometry(), and LEADER::updateGeometry().

◆ SetVertex() [1/2]

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

Accessor function to set the position of a specific point.

Parameters
aIndexVERTEX_INDEX of the point to move.
aPosdestination position of the specified point.

Definition at line 1590 of file shape_poly_set.cpp.

1591 {
1592  m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1593 }

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

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

◆ SetVertex() [2/2]

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

Set the vertex based on the global index.

Throws if the index doesn't exist.

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

Definition at line 1579 of file shape_poly_set.cpp.

1580 {
1581  VERTEX_INDEX index;
1582 
1583  if( GetRelativeIndices( aGlobalIndex, &index ) )
1584  SetVertex( index, aPos );
1585  else
1586  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1587 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...

References GetRelativeIndices(), and SetVertex().

◆ Simplify()

◆ SquaredDistance() [1/2]

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

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

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

Parameters
aPointis the point whose distance to the set has to be measured.
aNearest[out] an optional pointer to be filled in with the point on the polyset which is closest to aPoint.
Returns
The minimum distance squared between aPoint and all the polygons in the set. If the point is contained in any of the polygons, the distance is zero.

Definition at line 1762 of file shape_poly_set.cpp.

1763 {
1764  SEG::ecoord currentDistance_sq;
1765  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1766  VECTOR2I nearest;
1767 
1768  // Iterate through all the polygons and get the minimum distance.
1769  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1770  {
1771  currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
1772  aNearest ? &nearest : nullptr );
1773 
1774  if( currentDistance_sq < minDistance_sq )
1775  {
1776  if( aNearest )
1777  *aNearest = nearest;
1778 
1779  minDistance_sq = currentDistance_sq;
1780  }
1781  }
1782 
1783  return minDistance_sq;
1784 }
VECTOR2I::extended_type ecoord
Definition: seg.h:44
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.

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

Referenced by BOOST_AUTO_TEST_CASE(), and Collide().

◆ SquaredDistance() [2/2]

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

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

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

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

Definition at line 1787 of file shape_poly_set.cpp.

1788 {
1789  SEG::ecoord currentDistance_sq;
1790  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1791  VECTOR2I nearest;
1792 
1793  // Iterate through all the polygons and get the minimum distance.
1794  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1795  {
1796  currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
1797  aNearest ? &nearest : nullptr );
1798 
1799  if( currentDistance_sq < minDistance_sq )
1800  {
1801  if( aNearest )
1802  *aNearest = nearest;
1803 
1804  minDistance_sq = currentDistance_sq;
1805  }
1806  }
1807 
1808  return minDistance_sq;
1809 }
VECTOR2I::extended_type ecoord
Definition: seg.h:44
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.

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

◆ SquaredDistanceToPolygon() [1/2]

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

Compute the minimum distance between the aIndex-th polygon and aPoint.

Parameters
aPointis the point whose distance to the aIndex-th polygon has to be measured.
aIndexis the index of the polygon whose distance to aPoint has to be measured.
aNearest[out] an optional pointer to be filled in with the point on the polyset which is closest to aPoint.
Returns
The minimum distance between aPoint and all the segments of the aIndex-th polygon. If the point is contained in the polygon, the distance is zero.

Definition at line 1689 of file shape_poly_set.cpp.

1691 {
1692  // We calculate the min dist between the segment and each outline segment. However, if the
1693  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1694  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1695  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1696  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1697  {
1698  if( aNearest )
1699  *aNearest = aPoint;
1700 
1701  return 0;
1702  }
1703 
1704  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1705 
1706  SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1707 
1708  for( iterator++; iterator && minDistance > 0; iterator++ )
1709  {
1710  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1711 
1712  if( currentDistance < minDistance )
1713  {
1714  if( aNearest )
1715  *aNearest = (*iterator).NearestPoint( aPoint );
1716 
1717  minDistance = currentDistance;
1718  }
1719  }
1720 
1721  return minDistance;
1722 }
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
VECTOR2I::extended_type ecoord
Definition: seg.h:44
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.

References CIterateSegmentsWithHoles(), and containsSingle().

Referenced by SquaredDistance().

◆ SquaredDistanceToPolygon() [2/2]

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

Compute the minimum distance between the aIndex-th polygon and aSegment with a possible width.

Parameters
aSegmentis the segment whose distance to the aIndex-th polygon has to be measured.
aIndexis the index of the polygon whose distance to aPoint has to be measured.
aNearest[out] an optional pointer to be filled in with the point on the polyset which is closest to aSegment.
Returns
The minimum distance between aSegment and all the segments of the aIndex-th polygon. If the point is contained in the polygon, the distance is zero.

Definition at line 1725 of file shape_poly_set.cpp.

1727 {
1728  // Check if the segment is fully-contained. If so, its midpoint is a good-enough nearest point.
1729  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) &&
1730  containsSingle( aSegment.B, aPolygonIndex, 1 ) )
1731  {
1732  if( aNearest )
1733  *aNearest = ( aSegment.A + aSegment.B ) / 2;
1734 
1735  return 0;
1736  }
1737 
1738  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1739  SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1740 
1741  if( aNearest && minDistance == 0 )
1742  *aNearest = ( *iterator ).NearestPoint( aSegment );
1743 
1744  for( iterator++; iterator && minDistance > 0; iterator++ )
1745  {
1746  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
1747 
1748  if( currentDistance < minDistance )
1749  {
1750  if( aNearest )
1751  *aNearest = (*iterator).NearestPoint( aSegment );
1752 
1753  minDistance = currentDistance;
1754  }
1755  }
1756 
1757  // Return the maximum of minDistance and zero
1758  return minDistance < 0 ? 0 : minDistance;
1759 }
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
VECTOR2I::extended_type ecoord
Definition: seg.h:44
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
VECTOR2I A
Definition: seg.h:49
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.
VECTOR2I B
Definition: seg.h:50

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

◆ Subset()

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

Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.

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

Definition at line 287 of file shape_poly_set.cpp.

288 {
289  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
290 
291  SHAPE_POLY_SET newPolySet;
292 
293  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
294  {
295  newPolySet.m_polys.push_back( Polygon( index ) );
296  }
297 
298  return newPolySet;
299 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
Represent a set of closed polygons.
POLYGON & Polygon(int aIndex)

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

Referenced by UnitSet().

◆ TotalVertices()

int SHAPE_POLY_SET::TotalVertices ( ) const

Delete aIdx-th polygon from the set.

Definition at line 1662 of file shape_poly_set.cpp.

1663 {
1664  int c = 0;
1665 
1666  for( const POLYGON& poly : m_polys )
1667  {
1668  for( const SHAPE_LINE_CHAIN& path : poly )
1669  c += path.PointCount();
1670  }
1671 
1672  return c;
1673 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
SHAPE_LINE_CHAIN.

References m_polys, and path.

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

◆ TriangulatedPolyCount()

unsigned int SHAPE_POLY_SET::TriangulatedPolyCount ( ) const
inline

Return the number of outlines in the set.

Definition at line 623 of file shape_poly_set.h.

References m_triangulatedPolys.

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

◆ TriangulatedPolygon()

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

Definition at line 687 of file shape_poly_set.h.

688  {
689  return m_triangulatedPolys[aIndex].get();
690  }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys

References m_triangulatedPolys.

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

◆ Type()

SHAPE_TYPE SHAPE_BASE::Type ( ) const
inlineinherited

◆ Unfracture()

void SHAPE_POLY_SET::Unfracture ( POLYGON_MODE  aFastMode)

Return true if the polygon set has any holes.

Definition at line 1061 of file shape_poly_set.cpp.

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

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

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

◆ unfractureSingle()

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

Definition at line 885 of file shape_poly_set.cpp.

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

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

Referenced by 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 665 of file shape_poly_set.h.

References Subset().

Referenced by BOARD::NormalizeAreaPolygon().

◆ VertexCount()

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

Returns the number of holes in a given outline.

Definition at line 262 of file shape_poly_set.cpp.

263 {
264  if( m_polys.size() == 0 ) // Empty poly set
265  return 0;
266 
267  if( aOutline < 0 ) // Use last outline
268  aOutline += m_polys.size();
269 
270  int idx;
271 
272  if( aHole < 0 )
273  idx = 0;
274  else
275  idx = aHole + 1;
276 
277  if( aOutline >= (int) m_polys.size() ) // not existing outline
278  return 0;
279 
280  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
281  return 0;
282 
283  return m_polys[aOutline][idx].PointCount();
284 }

References m_polys.

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

Member Data Documentation

◆ m_hash

MD5_HASH SHAPE_POLY_SET::m_hash
private

◆ m_polys

◆ m_triangulatedPolys

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

◆ m_triangulationValid

bool SHAPE_POLY_SET::m_triangulationValid = false
private

◆ m_type

SHAPE_TYPE SHAPE_BASE::m_type
protectedinherited

< type of our shape

Definition at line 110 of file shape.h.

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

◆ MIN_PRECISION_IU

const int SHAPE::MIN_PRECISION_IU = 4
staticinherited

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

Definition at line 122 of file shape.h.

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


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