KiCad PCB EDA Suite
SHAPE_POLY_SET Class Reference

SHAPE_POLY_SET. More...

#include <shape_poly_set.h>

Inheritance diagram for SHAPE_POLY_SET:
SHAPE SHAPE_BASE

Classes

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

Public Types

enum  POLYGON_MODE { PM_FAST = true, PM_STRICTLY_SIMPLE = false }
 operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak polygon if aFastMode is PM_STRICTLY_SIMPLE (false) (default) the result is (theorically) a strictly simple polygon, but calculations can be really significantly time consuming Most of time PM_FAST is preferable. More...
 
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
 Struct VERTEX_INDEX. More...
 
typedef ITERATOR_TEMPLATE< VECTOR2IITERATOR
 
typedef ITERATOR_TEMPLATE< const VECTOR2ICONST_ITERATOR
 
typedef SEGMENT_ITERATOR_TEMPLATE< SEGSEGMENT_ITERATOR
 
typedef SEGMENT_ITERATOR_TEMPLATE< const SEGCONST_SEGMENT_ITERATOR
 

Public Member Functions

 SHAPE_POLY_SET ()
 
 SHAPE_POLY_SET (const SHAPE_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 &)
 
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
 Function GetRelativeIndices. More...
 
bool GetGlobalIndex (VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
 Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon, contour and vertex. More...
 
SHAPEClone () const override
 Function Clone() More...
 
int NewOutline ()
 

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

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

Creates a new hole in a given outline

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

Adds a new outline to the set and returns its index

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

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

More...
 
int Append (int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
 

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

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

Merges polygons from two sets.

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

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

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

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

More...
 
const VECTOR2ICVertex (int aGlobalIndex) const
 

Returns the aGlobalIndex-th vertex in the poly set

More...
 
const VECTOR2ICVertex (VERTEX_INDEX aIndex) const
 

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

More...
 
bool GetNeighbourIndexes (int aGlobalIndex, int *aPrevious, int *aNext)
 Returns the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a contour in the polygon set. More...
 
bool IsPolygonSelfIntersecting (int aPolygonIndex) const
 Function IsPolygonSelfIntersecting. More...
 
bool IsSelfIntersecting () const
 Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting. More...
 
unsigned int TriangulatedPolyCount () const
 

Returns the number of triangulated polygons

More...
 
int OutlineCount () const
 

Returns the number of outlines in the set

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

Returns the number of vertices in a given outline/hole

More...
 
int HoleCount (int aOutline) const
 

Returns the number of holes in a given outline

More...
 
SHAPE_LINE_CHAINOutline (int aIndex)
 

Returns the reference to aIndex-th outline in the set

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

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

More...
 
POLYGONPolygon (int aIndex)
 

Returns the aIndex-th subpolygon in the set

More...
 
const POLYGONPolygon (int aIndex) const
 
const TRIANGULATED_POLYGONTriangulatedPolygon (int aIndex) const
 
const SHAPE_LINE_CHAINCOutline (int aIndex) const
 
const SHAPE_LINE_CHAINCHole (int aOutline, int aHole) const
 
const POLYGONCPolygon (int aIndex) const
 
ITERATOR Iterate (int aFirst, int aLast, bool aIterateHoles=false)
 Function Iterate returns an object to iterate through the points of the polygons between aFirst and aLast. More...
 
ITERATOR Iterate (int aOutline)
 Function Iterate. More...
 
ITERATOR IterateWithHoles (int aOutline)
 Function IterateWithHoles. More...
 
ITERATOR Iterate ()
 Function Iterate. More...
 
ITERATOR IterateWithHoles ()
 Function IterateWithHoles. More...
 
CONST_ITERATOR CIterate (int aFirst, int aLast, bool aIterateHoles=false) const
 
CONST_ITERATOR CIterate (int aOutline) const
 
CONST_ITERATOR CIterateWithHoles (int aOutline) const
 
CONST_ITERATOR CIterate () const
 
CONST_ITERATOR CIterateWithHoles () const
 
ITERATOR IterateFromVertexWithHoles (int aGlobalIdx)
 
SEGMENT_ITERATOR IterateSegments (int aFirst, int aLast, bool aIterateHoles=false)
 

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

without holes (default: without) More...

 
CONST_SEGMENT_ITERATOR CIterateSegments (int aFirst, int aLast, bool aIterateHoles=false) const
 

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

without holes (default: without) More...

 
SEGMENT_ITERATOR IterateSegments (int aPolygonIdx)
 

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

More...
 
CONST_SEGMENT_ITERATOR CIterateSegments (int aPolygonIdx) const
 

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

More...
 
SEGMENT_ITERATOR IterateSegments ()
 

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

More...
 
SEGMENT_ITERATOR IterateSegmentsWithHoles ()
 

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

More...
 
SEGMENT_ITERATOR IterateSegmentsWithHoles (int aOutline)
 

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

More...
 
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles () const
 

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

More...
 
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles (int aOutline) const
 

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

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

Performs boolean polyset union For aFastMode meaning, see function booleanOp

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

Performs boolean polyset difference For aFastMode meaning, see function booleanOp

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

Performs boolean polyset intersection For aFastMode meaning, see function booleanOp

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

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

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

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

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

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

More...
 
void Inflate (int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
 Performs 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)
 Performs outline inflation/deflation, using round corners. More...
 
void Fracture (POLYGON_MODE aFastMode)
 

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

More...
 
void Unfracture (POLYGON_MODE aFastMode)
 

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

More...
 
bool HasHoles () const
 

Returns true if the polygon set has any holes.

More...
 
bool HasTouchingHoles () const
 

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

More...
 
void Simplify (POLYGON_MODE aFastMode)
 

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

More...
 
int NormalizeAreaOutlines ()
 Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s) Removes null segments. More...
 
const std::string Format () const override
 
bool Parse (std::stringstream &aStream) override
 
void Move (const VECTOR2I &aVector) override
 
void Mirror (bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
 Mirrors the line points about y or x (or both) More...
 
void Rotate (double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
 Function Rotate rotates all vertices by a given angle. More...
 
bool IsSolid () const override
 
const BOX2I BBox (int aClearance=0) const override
 Function BBox() More...
 
bool PointOnEdge (const VECTOR2I &aP) const
 Function PointOnEdge() More...
 
bool Collide (const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Function Collide() More...
 
bool Collide (const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Function Collide Checks 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
 Function Collide Checks 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
 Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the polygon. More...
 
bool CollideEdge (const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
 Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polygon. More...
 
void BuildBBoxCaches ()
 Constructs BBoxCaches for Contains(), below. More...
 
const BOX2I BBoxFromCaches () const
 
bool Contains (const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
 Returns true if a given subpolygon contains the point aP. More...
 
bool IsEmpty () const
 

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

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

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

More...
 
void RemoveContour (int aContourIdx, int aPolygonIdx=-1)
 Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set. More...
 
int RemoveNullSegments ()
 Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and deletes them. More...
 
void SetVertex (const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
 Function SetVertex Accessor function to set the position of a specific point. More...
 
void SetVertex (int aGlobalIndex, const VECTOR2I &aPos)
 Sets the vertex based on the global index. More...
 
int TotalVertices () const
 

Returns total number of vertices stored in the set.

More...
 
void DeletePolygon (int aIdx)
 

Deletes aIdx-th polygon from the set

More...
 
POLYGON ChamferPolygon (unsigned int aDistance, int aIndex)
 Function Chamfer returns a chamfered version of the aIndex-th polygon. More...
 
POLYGON FilletPolygon (unsigned int aRadius, int aErrorMax, int aIndex)
 Function Fillet returns a filleted version of the aIndex-th polygon. More...
 
SHAPE_POLY_SET Chamfer (int aDistance)
 Function Chamfer returns a chamfered version of the polygon set. More...
 
SHAPE_POLY_SET Fillet (int aRadius, int aErrorMax)
 Function Fillet returns a filleted version of the polygon set. More...
 
SEG::ecoord SquaredDistanceToPolygon (VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
 Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint. More...
 
SEG::ecoord SquaredDistanceToPolygon (const SEG &aSegment, int aIndex, VECTOR2I *aNearest) const
 Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aSegment with a possible width. More...
 
SEG::ecoord SquaredDistance (VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
 Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in the set. More...
 
SEG::ecoord SquaredDistance (const SEG &aSegment, VECTOR2I *aNearest=nullptr) const
 Function SquaredDistance computes the minimum distance squared between aSegment and all the polygons in the set. More...
 
bool IsVertexInHole (int aGlobalIdx)
 Function IsVertexInHole. More...
 
bool IsNull () const
 Function IsNull() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const
 Function Collide() More...
 
virtual VECTOR2I Centre () const
 Function Centre() More...
 
FACETNewFacet ()
 
SGNODECalcShape (SGNODE *aParent, SGNODE *aColor, WRL1_ORDER aVertexOrder, float aCreaseLimit=0.74317, bool isVRML2=false)
 
SHAPE_TYPE Type () const
 Function Type() More...
 

Protected Types

typedef VECTOR2I::extended_type ecoord
 

Protected Attributes

SHAPE_TYPE m_type
 

type of our shape

More...
 

Private Types

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

Private Member Functions

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

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

More...
 
MD5_HASH checksum () const
 

Private Attributes

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

Detailed Description

SHAPE_POLY_SET.

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

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

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

TODO: add convex partitioning & spatial index

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

◆ SEGMENT_ITERATOR

◆ VERTEX_INDEX

Struct VERTEX_INDEX.

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

Member Enumeration Documentation

◆ CORNER_MODE

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

Enumerator
CHAMFERED 
FILLETED 

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

953  {
961  };
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 (theorically) a strictly simple polygon, but calculations can be really significantly time consuming Most of time PM_FAST is preferable.

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

Enumerator
PM_FAST 
PM_STRICTLY_SIMPLE 

Definition at line 919 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)
Constructor.
Definition: shape.h:131
simple polygon
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)
Constructor.
Definition: shape.h:131
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
simple polygon
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)
Constructor.
Definition: shape.h:131
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool IsTriangulationUpToDate() const
MD5_HASH GetHash() const
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
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 
)

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

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::loadPolygon(), and FABMASTER::loadZone().

◆ AddOutline()

int SHAPE_POLY_SET::AddOutline ( const SHAPE_LINE_CHAIN aOutline)

Adds a new outline to the set and returns its index

Definition at line 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 
)

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

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

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

Definition at line 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::loadPolygon(), FABMASTER::loadZone(), LEGACY_PLUGIN::loadZONE_CONTAINER(), PCB_PARSER::parseZONE(), DXF_PLOTTER::PlotPoly(), RENDER_3D_LEGACY::reload(), PCB_SHAPE::Rotate(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), PCB_SHAPE::SetPolyPoints(), WS_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)

Merges polygons from two sets.

Definition at line 1432 of file shape_poly_set.cpp.

1433 {
1434  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1435 }

References m_polys.

◆ Append() [3/3]

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

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

Definition at line 1438 of file shape_poly_set.cpp.

1439 {
1440  Append( aP.x, aP.y, aOutline, aHole );
1441 }
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)

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

◆ BBox()

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

Function BBox()

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

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

Implements SHAPE.

Definition at line 1187 of file shape_poly_set.cpp.

1188 {
1189  BOX2I bb;
1190 
1191  for( unsigned i = 0; i < m_polys.size(); i++ )
1192  {
1193  if( i == 0 )
1194  bb = m_polys[i][0].BBox();
1195  else
1196  bb.Merge( m_polys[i][0].BBox() );
1197  }
1198 
1199  bb.Inflate( aClearance );
1200  return bb;
1201 }
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
Function BBox()

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

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), BOARD::CombineAllZonesInNet(), APERTURE_MACRO::GetApertureMacroShape(), PAD::GetBestAnchorPosition(), ZONE::GetBoundingBox(), WS_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 1204 of file shape_poly_set.cpp.

1205 {
1206  BOX2I bb;
1207 
1208  for( unsigned i = 0; i < m_polys.size(); i++ )
1209  {
1210  if( i == 0 )
1211  bb = m_polys[i][0].BBoxFromCache();
1212  else
1213  bb.Merge( m_polys[i][0].BBoxFromCache() );
1214  }
1215 
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

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 
)

Performs boolean polyset union For aFastMode meaning, see function booleanOp

Definition at line 494 of file shape_poly_set.cpp.

495 {
496  booleanOp( ctUnion, b, aFastMode );
497 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...

References booleanOp().

Referenced by PAD::addPadPrimitivesToPolygon(), ZONE::BuildSmoothedPoly(), BOARD::CombineZones(), 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 
)

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

Definition at line 512 of file shape_poly_set.cpp.

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

References booleanOp().

◆ BooleanIntersection() [1/2]

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

Performs boolean polyset intersection For aFastMode meaning, see function booleanOp

Definition at line 506 of file shape_poly_set.cpp.

507 {
508  booleanOp( ctIntersection, b, aFastMode );
509 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...

References booleanOp().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE::BuildSmoothedPoly(), 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 
)

Performs boolean polyset intersection 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( ctIntersection, a, b, aFastMode );
533 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...

References booleanOp().

◆ booleanOp() [1/2]

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

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

and polygon simplification (merging overlaping polygons)

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

Definition at line 458 of file shape_poly_set.cpp.

460 {
461  booleanOp( aType, *this, aOtherShape, aFastMode );
462 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...

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

◆ booleanOp() [2/2]

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

Definition at line 465 of file shape_poly_set.cpp.

469 {
470  Clipper c;
471 
472  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
473 
474  for( auto poly : aShape.m_polys )
475  {
476  for( size_t i = 0 ; i < poly.size(); i++ )
477  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
478  }
479 
480  for( auto poly : aOtherShape.m_polys )
481  {
482  for( size_t i = 0; i < poly.size(); i++ )
483  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
484  }
485 
486  PolyTree solution;
487 
488  c.Execute( aType, solution, pftNonZero, pftNonZero );
489 
490  importTree( &solution );
491 }
void importTree(ClipperLib::PolyTree *tree)

References importTree(), m_polys, and PM_STRICTLY_SIMPLE.

◆ BooleanSubtract() [1/2]

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

◆ BooleanSubtract() [2/2]

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

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

Definition at line 520 of file shape_poly_set.cpp.

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

References booleanOp().

◆ BuildBBoxCaches()

void SHAPE_POLY_SET::BuildBBoxCaches ( )

Constructs BBoxCaches for Contains(), below.

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

1513 {
1514  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1515  {
1516  Outline( polygonIdx ).GenerateBBoxCache();
1517 
1518  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1519  Hole( polygonIdx, holeIdx ).GenerateBBoxCache();
1520  }
1521 }
int OutlineCount() const
Returns the number of outlines in the set
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
int HoleCount(int aOutline) const
Returns the number of holes in a given outline

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

Referenced by ZONE_FILLER::computeRawFilledArea().

◆ CacheTriangulation()

void SHAPE_POLY_SET::CacheTriangulation ( bool  aPartition = true)

Definition at line 2106 of file shape_poly_set.cpp.

2107 {
2108  bool recalculate = !m_hash.IsValid();
2109  MD5_HASH hash;
2110 
2111  if( !m_triangulationValid )
2112  recalculate = true;
2113 
2114  if( !recalculate )
2115  {
2116  hash = checksum();
2117 
2118  if( m_hash != hash )
2119  {
2120  m_hash = hash;
2121  recalculate = true;
2122  }
2123  }
2124 
2125  if( !recalculate )
2126  return;
2127 
2128  SHAPE_POLY_SET tmpSet;
2129 
2130  if( aPartition )
2131  {
2132  // This partitions into regularly-sized grids (1cm in pcbnew)
2133  partitionPolyIntoRegularCellGrid( *this, 1e7, tmpSet );
2134  }
2135  else
2136  {
2137  tmpSet = *this;
2138 
2139  if( tmpSet.HasHoles() )
2140  tmpSet.Fracture( PM_FAST );
2141  }
2142 
2143  m_triangulatedPolys.clear();
2144  m_triangulationValid = true;
2145 
2146  while( tmpSet.OutlineCount() > 0 )
2147  {
2148  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2149  PolygonTriangulation tess( *m_triangulatedPolys.back() );
2150 
2151  // If the tesselation fails, we re-fracture the polygon, which will
2152  // first simplify the system before fracturing and removing the holes
2153  // This may result in multiple, disjoint polygons.
2154  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
2155  {
2156  tmpSet.Fracture( PM_FAST );
2157  m_triangulationValid = false;
2158  continue;
2159  }
2160 
2161  tmpSet.DeletePolygon( 0 );
2162  m_triangulationValid = true;
2163  }
2164 
2165  if( m_triangulationValid )
2166  m_hash = checksum();
2167 }
int OutlineCount() const
Returns the number of outlines in the set
bool HasHoles() const
Returns true if the polygon set has any holes.
MD5_HASH checksum() const
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
static void partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize, SHAPE_POLY_SET &aOut)
SHAPE_POLY_SET.
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
bool IsValid() const
Definition: md5_hash.h:24

References checksum(), DeletePolygon(), Fracture(), HasHoles(), MD5_HASH::IsValid(), m_hash, m_triangulatedPolys, m_triangulationValid, OutlineCount(), 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:500
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
static VRML_COLOR colors[VRML_COLOR_LAST]
IFSG_SHAPE is the wrapper for the SGSHAPE class.
Definition: ifsg_shape.h:40

References IFSG_NODE::AddChildNode(), IFSG_INDEX::AddIndex(), IFSG_NODE::AddRefNode(), colors, SHAPE::facets, IFSG_NODE::GetRawPtr(), S3D::GetSGNodeParent(), IFSG_FACESET::NewNode(), IFSG_SHAPE::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

Function Centre()

Computes a center-of-mass of the shape

Returns
the center-of-mass point

Definition at line 229 of file shape.h.

230  {
231  return BBox( 0 ).Centre(); // if nothing better is available....
232  }
virtual const BOX2I BBox(int aClearance=0) const =0
Function BBox()
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)

Function Chamfer returns a chamfered version of the polygon set.

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

Definition at line 1808 of file shape_poly_set.cpp.

1809 {
1810  SHAPE_POLY_SET chamfered;
1811 
1812  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1813  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
1814 
1815  return chamfered;
1816 }
SHAPE_POLY_SET.
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Function Chamfer returns 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

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

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

Definition at line 1830 of file shape_poly_set.cpp.

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

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

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

Definition at line 1660 of file shape_poly_set.cpp.

1661 {
1662  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
1663 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...

References CHAMFERED, and chamferFilletPolygon().

Referenced by Chamfer().

◆ checksum()

MD5_HASH SHAPE_POLY_SET::checksum ( ) const
private

Definition at line 2170 of file shape_poly_set.cpp.

2171 {
2172  MD5_HASH hash;
2173 
2174  hash.Hash( m_polys.size() );
2175 
2176  for( const auto& outline : m_polys )
2177  {
2178  hash.Hash( outline.size() );
2179 
2180  for( const auto& lc : outline )
2181  {
2182  hash.Hash( lc.PointCount() );
2183 
2184  for( int i = 0; i < lc.PointCount(); i++ )
2185  {
2186  hash.Hash( lc.CPoint( i ).x );
2187  hash.Hash( lc.CPoint( i ).y );
2188  }
2189  }
2190  }
2191 
2192  hash.Finalize();
2193 
2194  return hash;
2195 }
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 784 of file shape_poly_set.h.

785  {
786  CONST_ITERATOR iter;
787 
788  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
789  iter.m_currentPolygon = aFirst;
790  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
791  iter.m_currentContour = 0;
792  iter.m_currentVertex = 0;
793  iter.m_iterateHoles = aIterateHoles;
794 
795  return iter;
796  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR

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

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

◆ CIterate() [2/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aOutline) const
inline

Definition at line 798 of file shape_poly_set.h.

799  {
800  return CIterate( aOutline, aOutline );
801  }
CONST_ITERATOR CIterate() const

References CIterate().

◆ CIterate() [3/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( ) const
inline

Definition at line 808 of file shape_poly_set.h.

809  {
810  return CIterate( 0, OutlineCount() - 1 );
811  }
int OutlineCount() const
Returns the number of outlines in the set
CONST_ITERATOR CIterate() const

References OutlineCount().

Referenced by CIterate(), and CIterateWithHoles().

◆ CIterateSegments() [1/2]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegments ( int  aFirst,
int  aLast,
bool  aIterateHoles = false 
) const
inline

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

without holes (default: without)

Definition at line 855 of file shape_poly_set.h.

857  {
859 
860  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
861  iter.m_currentPolygon = aFirst;
862  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
863  iter.m_currentContour = 0;
864  iter.m_currentSegment = 0;
865  iter.m_iterateHoles = aIterateHoles;
866 
867  return iter;
868  }
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR

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

Referenced by CIterateSegments(), CIterateSegmentsWithHoles(), BRDITEMS_PLOTTER::PlotPcbShape(), and projectPointOnSegment().

◆ CIterateSegments() [2/2]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegments ( int  aPolygonIdx) const
inline

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

Definition at line 877 of file shape_poly_set.h.

878  {
879  return CIterateSegments( aPolygonIdx, aPolygonIdx );
880  }
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Returns an iterator object, for iterating between aFirst and aLast outline, with or without holes (de...

References CIterateSegments().

◆ CIterateSegmentsWithHoles() [1/2]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegmentsWithHoles ( ) const
inline

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

Definition at line 901 of file shape_poly_set.h.

902  {
903  return CIterateSegments( 0, OutlineCount() - 1, true );
904  }
int OutlineCount() const
Returns the number of outlines in the set
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Returns an iterator object, for iterating between aFirst and aLast outline, with or without holes (de...

References CIterateSegments(), and OutlineCount().

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

◆ CIterateSegmentsWithHoles() [2/2]

CONST_SEGMENT_ITERATOR SHAPE_POLY_SET::CIterateSegmentsWithHoles ( int  aOutline) const
inline

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

Definition at line 907 of file shape_poly_set.h.

908  {
909  return CIterateSegments( aOutline, aOutline, true );
910  }
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Returns an iterator object, for iterating between aFirst and aLast outline, with or without holes (de...

References CIterateSegments().

◆ CIterateWithHoles() [1/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( int  aOutline) const
inline

Definition at line 803 of file shape_poly_set.h.

804  {
805  return CIterate( aOutline, aOutline, true );
806  }
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 813 of file shape_poly_set.h.

814  {
815  return CIterate( 0, OutlineCount() - 1, true );
816  }
int OutlineCount() const
Returns the number of outlines in the set
CONST_ITERATOR CIterate() const

References CIterate(), and OutlineCount().

Referenced by CollideVertex().

◆ Clone()

SHAPE * SHAPE_POLY_SET::Clone ( ) const
overridevirtual

Function Clone()

Returns a dynamically allocated copy of the shape

Return values
copyof the shape

Reimplemented from SHAPE.

Definition at line 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

Function Collide()

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

Parameters
aShapeshape to check collision against
aClearanceminimum clearance
aMTVminimum translation vector
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 852 of file shape_collisions.cpp.

853 {
854  return collideShapes( this, aShape, aClearance, nullptr, nullptr, aMTV );
855 }
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

Function Collide()

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

Parameters
aShapeshape to check collision against
aClearanceminimum clearance
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 1279 of file shape_poly_set.cpp.

1281 {
1282  // A couple of simple cases are worth trying before we fall back on triangulation.
1283 
1284  if( aShape->Type() == SH_SEGMENT )
1285  {
1286  const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
1287  int extra = segment->GetWidth() / 2;
1288 
1289  if( Collide( segment->GetSeg(), aClearance + extra, aActual, aLocation ) )
1290  {
1291  if( aActual )
1292  *aActual = std::max( 0, *aActual - extra );
1293 
1294  return true;
1295  }
1296 
1297  return false;
1298  }
1299 
1300  if( aShape->Type() == SH_CIRCLE )
1301  {
1302  const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
1303  int extra = circle->GetRadius();
1304 
1305  if( Collide( circle->GetCenter(), 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  const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( true );
1317 
1318  int actual = INT_MAX;
1319  VECTOR2I location;
1320 
1321  for( auto& tpoly : m_triangulatedPolys )
1322  {
1323  for ( auto& tri : tpoly->Triangles() )
1324  {
1325  int triActual;
1326  VECTOR2I triLocation;
1327 
1328  if( aShape->Collide( &tri, aClearance, &triActual, &triLocation ) )
1329  {
1330  if( !aActual && !aLocation )
1331  return true;
1332 
1333  if( triActual < actual )
1334  {
1335  actual = triActual;
1336  location = triLocation;
1337  }
1338  }
1339  }
1340  }
1341 
1342  if( actual < INT_MAX )
1343  {
1344  if( aActual )
1345  *aActual = std::max( 0, actual );
1346 
1347  if( aLocation )
1348  *aLocation = location;
1349 
1350  return true;
1351  }
1352 
1353  return false;
1354 }
int GetRadius() const
Definition: shape_circle.h:102
const VECTOR2I GetCenter() const
Definition: shape_circle.h:107
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
Function Collide()
Definition: shape.h:173
const SEG & GetSeg() const
line chain (polyline)
Definition: shape.h:46
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
int GetWidth() const
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:99
axis-aligned rectangle
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 WS_DRAW_ITEM_POLYPOLYGONS::HitTest(), PCB_SHAPE::HitTest(), FOOTPRINT::HitTestAccurate(), PCB_SELECTION_TOOL::hitTestDistance(), insideCourtyard(), 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

Function Collide Checks 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
bool - true if the point aP collides with the polygon; false in any other case.

Reimplemented from SHAPE.

Definition at line 1258 of file shape_poly_set.cpp.

1260 {
1261  VECTOR2I nearest;
1262  ecoord dist_sq = SquaredDistance( aP, aLocation ? &nearest : nullptr );
1263 
1264  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1265  {
1266  if( aLocation )
1267  *aLocation = nearest;
1268 
1269  if( aActual )
1270  *aActual = sqrt( dist_sq );
1271 
1272  return true;
1273  }
1274 
1275  return false;
1276 }
static SEG::ecoord Square(int a)
Definition: seg.h:123
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in...
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

Function Collide Checks 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
bool - true if the segment aSeg collides with the polygon; false in any other case.

Implements SHAPE.

Definition at line 1237 of file shape_poly_set.cpp.

1239 {
1240  VECTOR2I nearest;
1241  ecoord dist_sq = SquaredDistance( aSeg, aLocation ? &nearest : nullptr );
1242 
1243  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1244  {
1245  if( aLocation )
1246  *aLocation = nearest;
1247 
1248  if( aActual )
1249  *aActual = sqrt( dist_sq );
1250 
1251  return true;
1252  }
1253 
1254  return false;
1255 }
static SEG::ecoord Square(int a)
Definition: seg.h:123
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in...
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

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

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

Definition at line 1483 of file shape_poly_set.cpp.

1486 {
1487  // Shows whether there was a collision
1488  bool collision = false;
1489 
1490  for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
1491  {
1492  const SEG currentSegment = *iterator;
1493  int distance = currentSegment.Distance( aPoint );
1494 
1495  // Check for collisions
1496  if( distance <= aClearance )
1497  {
1498  collision = true;
1499 
1500  // Update aClearance to look for closer edges
1501  aClearance = distance;
1502 
1503  // Store the indices that identify the vertex
1504  aClosestVertex = iterator.GetIndex();
1505  }
1506  }
1507 
1508  return collision;
1509 }
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:214
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Returns 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:39

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

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

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

Definition at line 1444 of file shape_poly_set.cpp.

1447 {
1448  // Shows whether there was a collision
1449  bool collision = false;
1450 
1451  // Difference vector between each vertex and aPoint.
1452  VECTOR2D delta;
1453  double distance, clearance;
1454 
1455  // Convert clearance to double for precission when comparing distances
1456  clearance = aClearance;
1457 
1458  for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
1459  {
1460  // Get the difference vector between current vertex and aPoint
1461  delta = *iterator - aPoint;
1462 
1463  // Compute distance
1464  distance = delta.EuclideanNorm();
1465 
1466  // Check for collisions
1467  if( distance <= clearance )
1468  {
1469  collision = true;
1470 
1471  // Update aClearance to look for closer vertices
1472  clearance = distance;
1473 
1474  // Store the indices that identify the vertex
1475  aClosestVertex = iterator.GetIndex();
1476  }
1477  }
1478 
1479  return collision;
1480 }
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:300
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

Returns true if a given subpolygon contains the point aP.

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

Definition at line 1524 of file shape_poly_set.cpp.

1526 {
1527  if( m_polys.empty() )
1528  return false;
1529 
1530  // If there is a polygon specified, check the condition against that polygon
1531  if( aSubpolyIndex >= 0 )
1532  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1533 
1534  // In any other case, check it against all polygons in the set
1535  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1536  {
1537  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1538  return true;
1539  }
1540 
1541  return false;
1542 }
int OutlineCount() const
Returns the number of outlines in the set
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...

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

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

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

Parameters
aPis the VECTOR2I point whose position with respect to the inside of the aSubpolyIndex-th polygon will be tested.
aSubpolyIndexis an integer specifying which polygon in the set has to be checked.
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
bool - true if aP is inside aSubpolyIndex-th polygon; false in any other case.

Definition at line 1580 of file shape_poly_set.cpp.

1582 {
1583  // Check that the point is inside the outline
1584  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1585  {
1586  // Check that the point is not in any of the holes
1587  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1588  {
1589  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1590 
1591  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1592  // here as it's meaning would be inverted.
1593  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1594  return false;
1595  }
1596 
1597  return true;
1598  }
1599 
1600  return false;
1601 }
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
SHAPE_LINE_CHAIN.

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

Referenced by Contains(), and SquaredDistanceToPolygon().

◆ COutline()

◆ CPolygon()

◆ CVertex() [1/3]

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

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

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

Returns the aGlobalIndex-th vertex in the poly set

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 }
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.

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

◆ CVertex() [3/3]

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

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

Definition at line 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
Returns the index-th vertex in a given hole outline within a given outline

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

◆ Deflate()

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

Definition at line 979 of file shape_poly_set.h.

981  {
982  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
983  }
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.

References Inflate().

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

◆ DeletePolygon()

void SHAPE_POLY_SET::DeletePolygon ( int  aIdx)

Deletes aIdx-th polygon from the set

Definition at line 1426 of file shape_poly_set.cpp.

1427 {
1428  m_polys.erase( m_polys.begin() + aIdx );
1429 }

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 
)

Function Fillet returns a filleted version of the polygon set.

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

Definition at line 1819 of file shape_poly_set.cpp.

1820 {
1821  SHAPE_POLY_SET filleted;
1822 
1823  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1824  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
1825 
1826  return filleted;
1827 }
SHAPE_POLY_SET.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Function Fillet returns 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 
)

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

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

Definition at line 1666 of file shape_poly_set.cpp.

1668 {
1669  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
1670 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...

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

1098 {
1099  std::stringstream ss;
1100 
1101  ss << "SHAPE_LINE_CHAIN poly; \n";
1102 
1103  for( unsigned i = 0; i < m_polys.size(); i++ )
1104  {
1105  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1106  {
1107 
1108  ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
1109 
1110  SHAPE_POLY_SET poly;
1111 
1112  if( j == 0 )
1113  {
1114  ss << " poly.AddOutline(tmp); } \n";
1115  }
1116  else
1117  {
1118  ss << " poly.AddHole(tmp); } \n";
1119  }
1120 
1121  }
1122  }
1123 
1124  return ss.str();
1125 }
SHAPE_POLY_SET.

References m_polys.

◆ Fracture()

void SHAPE_POLY_SET::Fracture ( POLYGON_MODE  aFastMode)

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

Definition at line 858 of file shape_poly_set.cpp.

859 {
860  Simplify( aFastMode ); // remove overlapping holes/degeneracy
861 
862  for( POLYGON& paths : m_polys )
863  {
864  fractureSingle( paths );
865  }
866 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void fractureSingle(POLYGON &paths)
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...

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

Referenced by addHoleToPolygon(), PAD::addPadPrimitivesToPolygon(), PAD::AddPrimitivePoly(), CacheTriangulation(), ZONE_FILLER::computeRawFilledArea(), FOOTPRINT::CoverageRatio(), BITMAPCONV_INFO::createOutputData(), AR_AUTOPLACER::drawPlacementRoutingMatrix(), export_vrml_polygon(), AR_AUTOPLACER::fillMatrix(), ZONE_FILLER::fillSingleZone(), APERTURE_MACRO::GetApertureMacroShape(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), InflateWithLinkedHoles(), FABMASTER::loadFootprints(), EAGLE_PLUGIN::loadPolygon(), FABMASTER::loadPolygon(), 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 754 of file shape_poly_set.cpp.

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

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

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

Definition at line 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)
Returns the aIndex-th subpolygon in the set

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

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

◆ GetHash()

MD5_HASH SHAPE_POLY_SET::GetHash ( ) const

Definition at line 2013 of file shape_poly_set.cpp.

2014 {
2015  if( !m_hash.IsValid() )
2016  return checksum();
2017 
2018  return m_hash;
2019 }
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 2241 of file shape_poly_set.cpp.

2242 {
2243  size_t n = 0;
2244 
2245  for( auto& t : m_triangulatedPolys )
2246  n += t->GetTriangleCount();
2247 
2248  return n;
2249 }
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 2252 of file shape_poly_set.cpp.

2253 {
2254  aSubshapes.reserve( GetIndexableSubshapeCount() );
2255 
2256  for( auto& tpoly : m_triangulatedPolys )
2257  {
2258  for ( auto& tri : tpoly->Triangles() )
2259  {
2260  aSubshapes.push_back( &tri );
2261  }
2262  }
2263 }
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 
)

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

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

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

Definition at line 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
Struct VERTEX_INDEX.
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon,...

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

Referenced by ZONE::MoveEdge().

◆ GetRelativeIndices()

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

Function GetRelativeIndices.

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

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

Definition at line 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
Returns the number of outlines in the set
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

Returns true if the polygon set has any holes.

Definition at line 1030 of file shape_poly_set.cpp.

1031 {
1032  // Iterate through all the polygons on the set
1033  for( const POLYGON& paths : m_polys )
1034  {
1035  // If any of them has more than one contour, it is a hole.
1036  if( paths.size() > 1 )
1037  return true;
1038  }
1039 
1040  // Return false if and only if every polygon has just one outline, without holes.
1041  return false;
1042 }
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 2235 of file shape_poly_set.cpp.

2236 {
2237  return IsTriangulationUpToDate();
2238 }
bool IsTriangulationUpToDate() const

References IsTriangulationUpToDate().

◆ HasTouchingHoles()

bool SHAPE_POLY_SET::HasTouchingHoles ( ) const

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

Definition at line 2198 of file shape_poly_set.cpp.

2199 {
2200  for( int i = 0; i < OutlineCount(); i++ )
2201  {
2202  if( hasTouchingHoles( CPolygon( i ) ) )
2203  {
2204  return true;
2205  }
2206  }
2207 
2208  return false;
2209 }
const POLYGON & CPolygon(int aIndex) const
int OutlineCount() const
Returns the number of outlines in the set
bool hasTouchingHoles(const POLYGON &aPoly) const
Returns true if the polygon set has any holes that touch share a vertex.

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

◆ hasTouchingHoles()

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

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

Definition at line 2212 of file shape_poly_set.cpp.

2213 {
2214  std::set< long long > ptHashes;
2215 
2216  for( const auto& lc : aPoly )
2217  {
2218  for( const VECTOR2I& pt : lc.CPoints() )
2219  {
2220  const long long ptHash = (long long) pt.x << 32 | pt.y;
2221 
2222  if( ptHashes.count( ptHash ) > 0 )
2223  {
2224  return true;
2225  }
2226 
2227  ptHashes.insert( ptHash );
2228  }
2229  }
2230 
2231  return false;
2232 }

Referenced by HasTouchingHoles().

◆ Hole()

◆ HoleCount()

int SHAPE_POLY_SET::HoleCount ( int  aOutline) const
inline

Returns the number of holes in a given outline

Definition at line 643 of file shape_poly_set.h.

644  {
645  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
646  return 0;
647 
648  // the first polygon in m_polys[aOutline] is the main contour,
649  // only others are holes:
650  return m_polys[aOutline].size() - 1;
651  }

References m_polys.

Referenced by BOARD_ADAPTER::addSolidAreasShapes(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), ZONE::AppendCorner(), BuildBBoxCaches(), BuildFootprintPolygonOutlines(), ZONE::CalculateFilledArea(), containsSingle(), CovertPolygonToBlocks(), KIGFX::PCB_PAINTER::draw(), export_vrml_board(), DSN::SPECCTRA_DB::fillBOUNDARY(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), CADSTAR_PCB_ARCHIVE_LOADER::getZoneFromCadstarShape(), ZONE::HitTestCutout(), PlotLayerOutlines(), ZONE::RemoveCutout(), and HYPERLYNX_EXPORTER::writeNetObjects().

◆ importTree()

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

Definition at line 628 of file shape_poly_set.cpp.

629 {
630  m_polys.clear();
631 
632  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
633  {
634  if( !n->IsHole() )
635  {
636  POLYGON paths;
637  paths.reserve( n->Childs.size() + 1 );
638  paths.push_back( n->Contour );
639 
640  for( unsigned int i = 0; i < n->Childs.size(); i++ )
641  paths.push_back( n->Childs[i]->Contour );
642 
643  m_polys.push_back( paths );
644  }
645  }
646 }
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 
)

Performs 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
aAmount- number of units to offset edges
aCircleSegmentsCount- number of segments per 360 degrees to use in curve approx
aCornerStrategy- ALLOW_ACUTE_CORNERS to preserve all angles, CHOP_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 545 of file shape_poly_set.cpp.

547 {
548  // A static table to avoid repetitive calculations of the coefficient
549  // 1.0 - cos( M_PI / aCircleSegmentsCount )
550  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
551  #define SEG_CNT_MAX 64
552  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
553 
554  ClipperOffset c;
555 
556  // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
557  // and are not what you'd think they are.
558  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
559  JoinType joinType = jtRound; // The way corners are offsetted
560  double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
561  JoinType miterFallback = jtSquare;
562 
563  switch( aCornerStrategy )
564  {
565  case ALLOW_ACUTE_CORNERS:
566  joinType = jtMiter;
567  miterLimit = 10; // Allows large spikes
568  miterFallback = jtSquare;
569  break;
570 
571  case CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
572  joinType = jtMiter;
573  miterFallback = jtRound;
574  break;
575 
576  case ROUND_ACUTE_CORNERS: // Acute angles are rounded
577  joinType = jtMiter;
578  miterFallback = jtSquare;
579  break;
580 
581  case CHAMFER_ALL_CORNERS: // All angles are chamfered.
582  joinType = jtSquare;
583  miterFallback = jtSquare;
584  break;
585 
586  case ROUND_ALL_CORNERS: // All angles are rounded.
587  joinType = jtRound;
588  miterFallback = jtSquare;
589  break;
590  }
591 
592  for( const POLYGON& poly : m_polys )
593  {
594  for( size_t i = 0; i < poly.size(); i++ )
595  c.AddPath( poly[i].convertToClipper( i == 0 ), joinType, etClosedPolygon );
596  }
597 
598  PolyTree solution;
599 
600  // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
601  // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
602  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
603 
604  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
605  aCircleSegmentsCount = 6;
606 
607  double coeff;
608 
609  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
610  {
611  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
612 
613  if( aCircleSegmentsCount <= SEG_CNT_MAX )
614  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
615  }
616  else
617  coeff = arc_tolerance_factor[aCircleSegmentsCount];
618 
619  c.ArcTolerance = std::abs( aAmount ) * coeff;
620  c.MiterLimit = miterLimit;
621  c.MiterFallback = miterFallback;
622  c.Execute( solution, aAmount );
623 
624  importTree( &solution );
625 }
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 ZONE::BuildSmoothedPoly(), ZONE_FILLER::computeRawFilledArea(), BOARD_ADAPTER::createPadWithClearance(), Deflate(), export_vrml_polygon(), GERBER_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadRoundRect(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), InflateWithLinkedHoles(), 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 
)

Performs outline inflation/deflation, using round corners.

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

Definition at line 536 of file shape_poly_set.cpp.

538 {
539  Simplify( aFastMode );
540  Inflate( aFactor, aCircleSegmentsCount );
541  Fracture( aFastMode );
542 }
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...

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

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

◆ InsertVertex()

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

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

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

Definition at line 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
Returns total number of vertices stored in the set.
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)

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

Referenced by PCB_POINT_EDITOR::addCorner().

◆ IsEmpty()

◆ IsNull()

bool SHAPE::IsNull ( ) const
inlineinherited

Function IsNull()

Returns true if the shape is a null shape.

Return values
trueif null :-)

Definition at line 157 of file shape.h.

158  {
159  return m_type == SH_NULL;
160  }
SHAPE_TYPE m_type
type of our shape
Definition: shape.h:115
circular arc
Definition: shape.h:51

References SHAPE_BASE::m_type, and SH_NULL.

◆ IsPolygonSelfIntersecting()

bool SHAPE_POLY_SET::IsPolygonSelfIntersecting ( int  aPolygonIndex) const

Function IsPolygonSelfIntersecting.

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

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

Definition at line 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:139
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
Definition: seg.h:39

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

Referenced by IsSelfIntersecting().

◆ IsSelfIntersecting()

bool SHAPE_POLY_SET::IsSelfIntersecting ( ) const

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

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

Definition at line 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
Function IsPolygonSelfIntersecting.

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

1048  {
1049  return true;
1050  }

◆ IsTriangulationUpToDate()

bool SHAPE_POLY_SET::IsTriangulationUpToDate ( ) const

Definition at line 2022 of file shape_poly_set.cpp.

2023 {
2024  if( !m_triangulationValid )
2025  return false;
2026 
2027  if( !m_hash.IsValid() )
2028  return false;
2029 
2030  MD5_HASH hash = checksum();
2031 
2032  return hash == m_hash;
2033 }
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)

Function IsVertexInHole.

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

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

Definition at line 1795 of file shape_poly_set.cpp.

1796 {
1797  VERTEX_INDEX index;
1798 
1799  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1800  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1801  return false;
1802 
1803  // The contour is a hole if its index is greater than zero
1804  return index.m_contour > 0;
1805 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.

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

◆ Iterate() [1/3]

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

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

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

Definition at line 727 of file shape_poly_set.h.

728  {
729  ITERATOR iter;
730 
731  iter.m_poly = this;
732  iter.m_currentPolygon = aFirst;
733  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
734  iter.m_currentContour = 0;
735  iter.m_currentVertex = 0;
736  iter.m_iterateHoles = aIterateHoles;
737 
738  return iter;
739  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR

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

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

◆ Iterate() [2/3]

ITERATOR SHAPE_POLY_SET::Iterate ( int  aOutline)
inline

Function Iterate.

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

Definition at line 747 of file shape_poly_set.h.

748  {
749  return Iterate( aOutline, aOutline );
750  }
ITERATOR Iterate()
Function Iterate.

References Iterate().

◆ Iterate() [3/3]

ITERATOR SHAPE_POLY_SET::Iterate ( )
inline

Function Iterate.

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

Definition at line 768 of file shape_poly_set.h.

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

References OutlineCount().

Referenced by Iterate(), and IterateWithHoles().

◆ IterateFromVertexWithHoles()

ITERATOR SHAPE_POLY_SET::IterateFromVertexWithHoles ( int  aGlobalIdx)
inline

Definition at line 818 of file shape_poly_set.h.

819  {
820  // Build iterator
821  ITERATOR iter = IterateWithHoles();
822 
823  // Get the relative indices of the globally indexed vertex
824  VERTEX_INDEX indices;
825 
826  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
827  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
828 
829  // Adjust where the iterator is pointing
830  iter.m_currentPolygon = indices.m_polygon;
831  iter.m_currentContour = indices.m_contour;
832  iter.m_currentVertex = indices.m_vertex;
833 
834  return iter;
835  }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR IterateWithHoles()
Function IterateWithHoles.

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

◆ IterateSegments() [1/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aFirst,
int  aLast,
bool  aIterateHoles = false 
)
inline

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

without holes (default: without)

Definition at line 839 of file shape_poly_set.h.

840  {
841  SEGMENT_ITERATOR iter;
842 
843  iter.m_poly = this;
844  iter.m_currentPolygon = aFirst;
845  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
846  iter.m_currentContour = 0;
847  iter.m_currentSegment = 0;
848  iter.m_iterateHoles = aIterateHoles;
849 
850  return iter;
851  }
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR

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

Referenced by DIMENSION_BASE::segPolyIntersection(), TestConcaveSquareFillet(), TestSquareFillet(), and LEADER::updateGeometry().

◆ IterateSegments() [2/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aPolygonIdx)
inline

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

Definition at line 871 of file shape_poly_set.h.

872  {
873  return IterateSegments( aPolygonIdx, aPolygonIdx );
874  }
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)

References IterateSegments().

◆ IterateSegments() [3/3]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( )
inline

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

Definition at line 883 of file shape_poly_set.h.

884  {
885  return IterateSegments( 0, OutlineCount() - 1 );
886  }
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)

References OutlineCount().

Referenced by IterateSegments(), and IterateSegmentsWithHoles().

◆ IterateSegmentsWithHoles() [1/2]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( )
inline

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

Definition at line 889 of file shape_poly_set.h.

890  {
891  return IterateSegments( 0, OutlineCount() - 1, true );
892  }
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)

References IterateSegments(), and OutlineCount().

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

◆ IterateSegmentsWithHoles() [2/2]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( int  aOutline)
inline

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

Definition at line 895 of file shape_poly_set.h.

896  {
897  return IterateSegments( aOutline, aOutline, true );
898  }
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)

References IterateSegments().

◆ IterateWithHoles() [1/2]

ITERATOR SHAPE_POLY_SET::IterateWithHoles ( int  aOutline)
inline

Function IterateWithHoles.

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

Definition at line 758 of file shape_poly_set.h.

759  {
760  return Iterate( aOutline, aOutline, true );
761  }
ITERATOR Iterate()
Function Iterate.

References Iterate().

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

◆ IterateWithHoles() [2/2]

ITERATOR SHAPE_POLY_SET::IterateWithHoles ( )
inline

Function IterateWithHoles.

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

Definition at line 778 of file shape_poly_set.h.

779  {
780  return Iterate( 0, OutlineCount() - 1, true );
781  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR Iterate()
Function 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 } 
)

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

1620 {
1621  for( POLYGON& poly : m_polys )
1622  {
1623  for( SHAPE_LINE_CHAIN& path : poly )
1624  path.Mirror( aX, aY, aRef );
1625  }
1626 
1627  if( m_triangulationValid )
1629 }
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, and m_triangulationValid.

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

◆ Move()

void SHAPE_POLY_SET::Move ( const VECTOR2I aVector)
overridevirtual

Implements SHAPE.

Definition at line 1604 of file shape_poly_set.cpp.

1605 {
1606  for( POLYGON& poly : m_polys )
1607  {
1608  for( SHAPE_LINE_CHAIN& path : poly )
1609  path.Move( aVector );
1610  }
1611 
1612  for( std::unique_ptr<TRIANGULATED_POLYGON>& tri : m_triangulatedPolys )
1613  tri->Move( aVector );
1614 
1615  m_hash = checksum();
1616 }
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, and m_triangulatedPolys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), export_vrml_polygon(), ALTIUM_PCB::HelperDrawsegmentSetLocalCoord(), GERBER_DRAW_ITEM::HitTest(), FP_SHAPE::Move(), PCB_SHAPE::Move(), ZONE::Move(), GERBER_DRAW_ITEM::MoveAB(), GERBER_DRAW_ITEM::MoveXY(), WS_DRAW_ITEM_POLYPOLYGONS::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)

Creates a new hole in a given outline

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 empty polygon in the set and returns its index

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::loadPolygon(), FABMASTER::loadZone(), LEGACY_PLUGIN::loadZONE_CONTAINER(), PCB_PARSER::parseZONE(), DXF_PLOTTER::PlotPoly(), RENDER_3D_LEGACY::reload(), PCB_SHAPE::Rotate(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), PCB_SHAPE::SetPolyPoints(), WS_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 ( )

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

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

Definition at line 1064 of file shape_poly_set.cpp.

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

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

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

◆ operator=()

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

Definition at line 1991 of file shape_poly_set.cpp.

1992 {
1993  static_cast<SHAPE&>(*this) = aOther;
1994  m_polys = aOther.m_polys;
1995  m_triangulatedPolys.clear();
1996  m_triangulationValid = false;
1997 
1998  if( aOther.IsTriangulationUpToDate() )
1999  {
2000  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
2001  {
2002  const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
2003  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
2004  }
2005 
2006  m_hash = aOther.GetHash();
2007  m_triangulationValid = true;
2008  }
2009 
2010  return *this;
2011 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool IsTriangulationUpToDate() const
MD5_HASH GetHash() const
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
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

Returns the reference to aIndex-th outline in the set

Definition at line 654 of file shape_poly_set.h.

655  {
656  return m_polys[aIndex][0];
657  }

References m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), BuildBBoxCaches(), 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::WS_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), APERTURE_MACRO::DrawApertureMacroShape(), export_vrml_padshape(), 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::loadZone(), DSN::SPECCTRA_DB::makePADSTACK(), BOARD::NormalizeAreaPolygon(), BRDITEMS_PLOTTER::PlotFilledAreas(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), PlotWorkSheet(), polygonArea(), CONVERT_TOOL::PolyToLines(), GERBER_DRAW_ITEM::PrintGerberPoly(), WS_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 659 of file shape_poly_set.h.

660  {
661  return m_polys[aIndex][0];
662  }

References m_polys.

◆ OutlineCount()

int SHAPE_POLY_SET::OutlineCount ( ) const
inline

Returns the number of outlines in the set

Definition at line 637 of file shape_poly_set.h.

637 { return m_polys.size(); }

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(), BuildBBoxCaches(), BuildBoardPolygonOutlines(), BuildConvexHull(), BuildFootprintPolygonOutlines(), PCB_SHAPE::BuildPolyPointsList(), CacheTriangulation(), ZONE::CalculateFilledArea(), CIterate(), CIterateSegments(), CIterateSegmentsWithHoles(), CIterateWithHoles(), BOARD::CombineZones(), Contains(), CovertPolygonToBlocks(), RENDER_3D_LEGACY::createBoard(), BITMAPCONV_INFO::createOutputData(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), KIGFX::WS_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(), export_vrml_board(), export_vrml_padshape(), export_vrml_zones(), 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(), WS_DRAW_ITEM_POLYPOLYGONS::HitTest(), ZONE::HitTestCutout(), insideArea(), isCopperOutside(), Iterate(), IterateSegments(), IterateSegmentsWithHoles(), IterateWithHoles(), CONVERT_TOOL::LinesToPoly(), NormalizeAreaOutlines(), SHAPE_POLY_SET::ITERATOR_TEMPLATE< T >::operator bool(), DIALOG_PAD_PROPERTIES::padValuesOK(), partitionPolyIntoRegularCellGrid(), BRDITEMS_PLOTTER::PlotFilledAreas(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), PlotLayerOutlines(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), PlotStandardLayer(), PlotWorkSheet(), polygon_triangulation_main(), polygonArea(), GERBER_DRAW_ITEM::Print(), WS_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 1128 of file shape_poly_set.cpp.

1129 {
1130  std::string tmp;
1131 
1132  aStream >> tmp;
1133 
1134  if( tmp != "polyset" )
1135  return false;
1136 
1137  aStream >> tmp;
1138 
1139  int n_polys = atoi( tmp.c_str() );
1140 
1141  if( n_polys < 0 )
1142  return false;
1143 
1144  for( int i = 0; i < n_polys; i++ )
1145  {
1146  POLYGON paths;
1147 
1148  aStream >> tmp;
1149 
1150  if( tmp != "poly" )
1151  return false;
1152 
1153  aStream >> tmp;
1154  int n_outlines = atoi( tmp.c_str() );
1155 
1156  if( n_outlines < 0 )
1157  return false;
1158 
1159  for( int j = 0; j < n_outlines; j++ )
1160  {
1161  SHAPE_LINE_CHAIN outline;
1162 
1163  outline.SetClosed( true );
1164 
1165  aStream >> tmp;
1166  int n_vertices = atoi( tmp.c_str() );
1167 
1168  for( int v = 0; v < n_vertices; v++ )
1169  {
1170  VECTOR2I p;
1171 
1172  aStream >> tmp; p.x = atoi( tmp.c_str() );
1173  aStream >> tmp; p.y = atoi( tmp.c_str() );
1174  outline.Append( p );
1175  }
1176 
1177  paths.push_back( outline );
1178  }
1179 
1180  m_polys.push_back( paths );
1181  }
1182 
1183  return true;
1184 }
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

Function PointOnEdge()

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

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

Definition at line 1220 of file shape_poly_set.cpp.

1221 {
1222  // Iterate through all the polygons in the set
1223  for( const POLYGON& polygon : m_polys )
1224  {
1225  // Iterate through all the line chains in the polygon
1226  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1227  {
1228  if( lineChain.PointOnEdge( aP ) )
1229  return true;
1230  }
1231  }
1232 
1233  return false;
1234 }
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 692 of file shape_poly_set.h.

693  {
694  return m_polys[aIndex];
695  }

References m_polys.

◆ RemoveAllContours()

◆ RemoveContour()

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

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

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

Definition at line 1363 of file shape_poly_set.cpp.

1364 {
1365  // Default polygon is the last one
1366  if( aPolygonIdx < 0 )
1367  aPolygonIdx += m_polys.size();
1368 
1369  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1370 }

References m_polys.

Referenced by PCB_POINT_EDITOR::removeCorner().

◆ RemoveNullSegments()

int SHAPE_POLY_SET::RemoveNullSegments ( )

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

Returns
int - the number of deleted segments.

Definition at line 1373 of file shape_poly_set.cpp.

1374 {
1375  int removed = 0;
1376 
1377  ITERATOR iterator = IterateWithHoles();
1378 
1379  VECTOR2I contourStart = *iterator;
1380  VECTOR2I segmentStart, segmentEnd;
1381 
1382  VERTEX_INDEX indexStart;
1383 
1384  while( iterator )
1385  {
1386  // Obtain first point and its index
1387  segmentStart = *iterator;
1388  indexStart = iterator.GetIndex();
1389 
1390  // Obtain last point
1391  if( iterator.IsEndContour() )
1392  {
1393  segmentEnd = contourStart;
1394 
1395  // Advance
1396  iterator++;
1397 
1398  if( iterator )
1399  contourStart = *iterator;
1400  }
1401  else
1402  {
1403  // Advance
1404  iterator++;
1405 
1406  if( iterator )
1407  segmentEnd = *iterator;
1408  }
1409 
1410  // Remove segment start if both points are equal
1411  if( segmentStart == segmentEnd )
1412  {
1413  RemoveVertex( indexStart );
1414  removed++;
1415 
1416  // Advance the iterator one position, as there is one vertex less.
1417  if( iterator )
1418  iterator++;
1419  }
1420  }
1421 
1422  return removed;
1423 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR IterateWithHoles()
Function IterateWithHoles.
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.

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

Referenced by chamferFilletPolygon(), and NormalizeAreaOutlines().

◆ RemoveVertex() [1/2]

void SHAPE_POLY_SET::RemoveVertex ( int  aGlobalIndex)

Function RemoveVertex deletes the aGlobalIndex-th vertex.

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

Definition at line 1545 of file shape_poly_set.cpp.

1546 {
1547  VERTEX_INDEX index;
1548 
1549  // Assure the to be removed vertex exists, abort otherwise
1550  if( GetRelativeIndices( aGlobalIndex, &index ) )
1551  RemoveVertex( index );
1552  else
1553  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1554 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.

References GetRelativeIndices().

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

◆ RemoveVertex() [2/2]

void SHAPE_POLY_SET::RemoveVertex ( VERTEX_INDEX  aRelativeIndices)

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

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

Definition at line 1557 of file shape_poly_set.cpp.

1558 {
1559  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1560 }

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

Function Rotate rotates all vertices by a given angle.

Parameters
aCenteris the rotation center
aAnglerotation angle in radians

Implements SHAPE.

Definition at line 1632 of file shape_poly_set.cpp.

1633 {
1634  for( POLYGON& poly : m_polys )
1635  {
1636  for( SHAPE_LINE_CHAIN& path : poly )
1637  path.Rotate( aAngle, aCenter );
1638  }
1639 
1640  // Don't re-cache if the triangulation is already invalid
1641  if( m_triangulationValid )
1643 }
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, and m_triangulationValid.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), D_CODE::ConvertShapeToPolygon(), export_vrml_polygon(), ALTIUM_PCB::HelperDrawsegmentSetLocalCoord(), PCB_SHAPE::Rotate(), ZONE::Rotate(), 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 
)

Function SetVertex 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 1574 of file shape_poly_set.cpp.

1575 {
1576  m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1577 }

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 
)

Sets the vertex based on the global index.

Throws if the index doesn't exist

Parameters
aGlobalIndexglobal index of the to-be-moved vertex
aPosNew position on the vertex

Definition at line 1563 of file shape_poly_set.cpp.

1564 {
1565  VERTEX_INDEX index;
1566 
1567  if( GetRelativeIndices( aGlobalIndex, &index ) )
1568  SetVertex( index, aPos );
1569  else
1570  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1571 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Function SetVertex Accessor function to set the position of a specific point.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.

References GetRelativeIndices(), and SetVertex().

◆ Simplify()

void SHAPE_POLY_SET::Simplify ( POLYGON_MODE  aFastMode)

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

Definition at line 1056 of file shape_poly_set.cpp.

1057 {
1059 
1060  booleanOp( ctUnion, empty, aFastMode );
1061 }
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...
SHAPE_POLY_SET.
static bool empty(const wxTextEntryBase *aCtrl)

References booleanOp(), and empty().

Referenced by PAD::addPadPrimitivesToPolygon(), BOARD_ADAPTER::addShapeWithClearance(), ZONE_FILLER::buildCopperItemClearances(), BOARD::CombineZones(), FOOTPRINT::CoverageRatio(), BOARD_ADAPTER::createBoardPolygon(), BOARD_ADAPTER::createLayers(), BITMAPCONV_INFO::createOutputData(), Fracture(), BOARD::GetBoardPolygonOutlines(), InflateWithLinkedHoles(), NormalizeAreaOutlines(), ALTIUM_PCB::ParseArcs6Data(), PlotLayerOutlines(), PlotSolderMaskLayer(), PAD::TransformShapeWithClearanceToPolygon(), ZONE::TransformShapeWithClearanceToPolygon(), Unfracture(), HYPERLYNX_EXPORTER::writeNetObjects(), GBR_TO_PCB_EXPORTER::writePcbPolygon(), and GBR_TO_PCB_EXPORTER::writePcbZoneItem().

◆ SquaredDistance() [1/2]

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

Function SquaredDistance computes 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 1745 of file shape_poly_set.cpp.

1746 {
1747  SEG::ecoord currentDistance_sq;
1748  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1749  VECTOR2I nearest;
1750 
1751  // Iterate through all the polygons and get the minimum distance.
1752  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1753  {
1754  currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
1755  aNearest ? &nearest : nullptr );
1756 
1757  if( currentDistance_sq < minDistance_sq )
1758  {
1759  if( aNearest )
1760  *aNearest = nearest;
1761 
1762  minDistance_sq = currentDistance_sq;
1763  }
1764  }
1765 
1766  return minDistance_sq;
1767 }
VECTOR2I::extended_type ecoord
Definition: seg.h:42
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:81
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Function DistanceToPolygon computes 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

Function SquaredDistance computes 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 1770 of file shape_poly_set.cpp.

1771 {
1772  SEG::ecoord currentDistance_sq;
1773  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1774  VECTOR2I nearest;
1775 
1776  // Iterate through all the polygons and get the minimum distance.
1777  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1778  {
1779  currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
1780  aNearest ? &nearest : nullptr );
1781 
1782  if( currentDistance_sq < minDistance_sq )
1783  {
1784  if( aNearest )
1785  *aNearest = nearest;
1786 
1787  minDistance_sq = currentDistance_sq;
1788  }
1789  }
1790 
1791  return minDistance_sq;
1792 }
VECTOR2I::extended_type ecoord
Definition: seg.h:42
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:81
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Function DistanceToPolygon computes 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

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

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

Definition at line 1673 of file shape_poly_set.cpp.

1675 {
1676  // We calculate the min dist between the segment and each outline segment. However, if the
1677  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1678  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1679  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1680  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1681  {
1682  if( aNearest )
1683  *aNearest = aPoint;
1684 
1685  return 0;
1686  }
1687 
1688  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1689 
1690  SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1691 
1692  for( iterator++; iterator && minDistance > 0; iterator++ )
1693  {
1694  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1695 
1696  if( currentDistance < minDistance )
1697  {
1698  if( aNearest )
1699  *aNearest = (*iterator).NearestPoint( aPoint );
1700 
1701  minDistance = currentDistance;
1702  }
1703  }
1704 
1705  return minDistance;
1706 }
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
VECTOR2I::extended_type ecoord
Definition: seg.h:42
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Returns 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
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...

References CIterateSegmentsWithHoles(), and containsSingle().

Referenced by SquaredDistance().

◆ SquaredDistanceToPolygon() [2/2]

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

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

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

Definition at line 1709 of file shape_poly_set.cpp.

1711 {
1712  // We calculate the min dist between the segment and each outline segment. However, if the
1713  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1714  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1715  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1716  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) )
1717  {
1718  if( aNearest )
1719  *aNearest = ( aSegment.A + aSegment.B ) / 2;
1720 
1721  return 0;
1722  }
1723 
1724  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1725  SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1726 
1727  for( iterator++; iterator && minDistance > 0; iterator++ )
1728  {
1729  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
1730 
1731  if( currentDistance < minDistance )
1732  {
1733  if( aNearest )
1734  *aNearest = (*iterator).NearestPoint( aSegment );
1735 
1736  minDistance = currentDistance;
1737  }
1738  }
1739 
1740  // Return the maximum of minDistance and zero
1741  return minDistance < 0 ? 0 : minDistance;
1742 }
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
VECTOR2I::extended_type ecoord
Definition: seg.h:42
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
VECTOR2I A
Definition: seg.h:47
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
VECTOR2I B
Definition: seg.h:48

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

◆ Subset()

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

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

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

Definition at line 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
Returns the number of outlines in the set
SHAPE_POLY_SET.
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set

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

Referenced by UnitSet().

◆ TotalVertices()

int SHAPE_POLY_SET::TotalVertices ( ) const

Returns total number of vertices stored in the set.

Definition at line 1646 of file shape_poly_set.cpp.

1647 {
1648  int c = 0;
1649 
1650  for( const POLYGON& poly : m_polys )
1651  {
1652  for( const SHAPE_LINE_CHAIN& path : poly )
1653  c += path.PointCount();
1654  }
1655 
1656  return c;
1657 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
SHAPE_LINE_CHAIN.

References m_polys.

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

Returns the number of triangulated polygons

Definition at line 634 of file shape_poly_set.h.

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

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

698  {
699  return m_triangulatedPolys[aIndex].get();
700  }
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

Function Type()

Returns the type of the shape.

Return values
thetype

Definition at line 99 of file shape.h.

100  {
101  return m_type;
102  }
SHAPE_TYPE m_type
type of our shape
Definition: shape.h:115

References SHAPE_BASE::m_type.

Referenced by PNS::DP_GATEWAYS::BuildFromPrimitivePair(), PNS::buildHullForPrimitiveShape(), Collide(), Collide(), collideShapes(), collideSingleShapes(), PNS::OPTIMIZER::computeBreakouts(), ROUTER_PREVIEW_ITEM::drawShape(), PNS::SOLID::HoleHull(), PNS::SOLID::Hull(), and SHAPE_FILE_IO::Write().

◆ Unfracture()

void SHAPE_POLY_SET::Unfracture ( POLYGON_MODE  aFastMode)

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

Definition at line 1045 of file shape_poly_set.cpp.

1046 {
1047  for( POLYGON& path : m_polys )
1048  {
1049  unfractureSingle( path );
1050  }
1051 
1052  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1053 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void unfractureSingle(POLYGON &path)
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...

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

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

◆ unfractureSingle()

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

Definition at line 869 of file shape_poly_set.cpp.

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

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

Definition at line 675 of file shape_poly_set.h.

676  {
677  return Subset( aPolygonIndex, aPolygonIndex + 1 );
678  }
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLas...

References Subset().

Referenced by BOARD::NormalizeAreaPolygon().

◆ VertexCount()

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

Returns the number of vertices in a given outline/hole

Definition at line 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::loadPolygon(), 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 115 of file shape.h.

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


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