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 ()
 
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...
 
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 VECTOR2I &aP, int aClearance=0, int *aActual=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) 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) const
 Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint. More...
 
SEG::ecoord SquaredDistanceToPolygon (const SEG &aSegment, int aIndex) const
 Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aSegment with a possible width. More...
 
SEG::ecoord SquaredDistance (VECTOR2I aPoint) const
 Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in the set. More...
 
SEG::ecoord SquaredDistance (const SEG &aSegment) 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...
 
SHAPE_POLY_SEToperator= (const SHAPE_POLY_SET &)
 
void CacheTriangulation (bool aPartition=true)
 
bool IsTriangulationUpToDate () const
 
MD5_HASH GetHash () const
 
bool IsNull () const
 Function IsNull() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const
 Function Collide() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance=0, int *aActual=nullptr) const
 
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...
 
virtual bool HasIndexableSubshapes () const
 
virtual size_t GetIndexableSubshapeCount ()
 
virtual void GetIndexableSubshape (SHAPE_BASE &aSubshape) const
 

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 63 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 123 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 69 of file shape_poly_set.h.

◆ POLYSET

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

Definition at line 1360 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 1334 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 937 of file shape_poly_set.h.

938  {
946  };
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 904 of file shape_poly_set.h.

Constructor & Destructor Documentation

◆ SHAPE_POLY_SET() [1/3]

SHAPE_POLY_SET::SHAPE_POLY_SET ( )

Definition at line 57 of file shape_poly_set.cpp.

57  :
59 {
60 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:132
simple polygon
Definition: shape.h:47

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

63  :
65 {
66  AddOutline( aOutline );
67 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:132
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
simple polygon
Definition: shape.h:47

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

70  :
71  SHAPE( aOther ), m_polys( aOther.m_polys )
72 {
73  if( aOther.IsTriangulationUpToDate() )
74  {
75  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
76  m_triangulatedPolys.push_back(
77  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
78 
79  m_hash = aOther.GetHash();
80  m_triangulationValid = true;
81  }
82  else
83  {
84  m_triangulationValid = false;
85  m_hash = MD5_HASH();
86  m_triangulatedPolys.clear();
87  }
88 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:132
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 91 of file shape_poly_set.cpp.

92 {
93 }

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

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

References m_polys.

Referenced by ZONE_CONTAINER::AddPolygon(), KI_TEST::BuildHollowSquare(), KI_TEST::CommonTestData::CommonTestData(), and CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape().

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

423 {
424  assert( aOutline.IsClosed() );
425 
426  POLYGON poly;
427 
428  poly.push_back( aOutline );
429 
430  m_polys.push_back( poly );
431 
432  return m_polys.size() - 1;
433 }
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_CONTAINER::AddPolygon(), KI_TEST::BuildHollowSquare(), KI_TEST::BuildPolyset(), KI_TEST::CommonTestData::CommonTestData(), ZONE_FILLER::computeRawFilledArea(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), BOARD_ADAPTER::createNewPadWithClearance(), KIGFX::GERBVIEW_PAINTER::draw(), GEOM_TEST::FilletPolySet(), IteratorFixture::IteratorFixture(), CONVERT_TOOL::makePolysFromRects(), CONVERT_TOOL::makePolysFromSegs(), D_PAD::MergePrimitivesAsPolygon(), NormalizeAreaOutlines(), EAGLE_PLUGIN::packagePolygon(), ALTIUM_PCB::ParseRegions6Data(), partitionPolyIntoRegularCellGrid(), ZONE_CREATE_HELPER::performZoneCutout(), 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 214 of file shape_poly_set.cpp.

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

References m_polys.

Referenced by AR_AUTOPLACER::addFpBody(), addHoleToPolygon(), ZONE_FILLER::addKnockout(), AR_AUTOPLACER::addPad(), D_PAD::AddPrimitivePoly(), addRect(), Append(), ZONE_CONTAINER::AppendCorner(), BuildBoardPolygonOutlines(), ZONE_FILLER::buildCopperItemClearances(), ConvertOutlineToPolygon(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), BOARD_ADAPTER::createNewPadWithClearance(), BITMAPCONV_INFO::createOutputData(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), fillArcPOLY(), MODULE::GetBoundingPoly(), getRectangleAlongCentreLine(), DRAWSEGMENT::HitTest(), D_PAD::HitTest(), InsertVertex(), CONVERT_TOOL::LinesToPoly(), EAGLE_PLUGIN::loadPolygon(), LEGACY_PLUGIN::loadZONE_CONTAINER(), PCB_PARSER::parseZONE_CONTAINER(), DXF_PLOTTER::PlotPoly(), PlotStandardLayer(), DRAWSEGMENT::Rotate(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), DRAWSEGMENT::SetPolyPoints(), WS_DATA_ITEM_POLYGONS::SyncDrawItems(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testOverlappingComponentCourtyards(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRingToPolygon(), TransformRoundChamferedRectToPolygon(), DRAWSEGMENT::TransformShapeWithClearanceToPolygon(), D_PAD::TransformShapeWithClearanceToPolygon(), ZONE_CONTAINER::TransformSmoothedOutlineWithClearanceToPolygon(), ZONE_CONTAINER::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 1334 of file shape_poly_set.cpp.

1335 {
1336  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1337 }

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

1341 {
1342  Append( aP.x, aP.y, aOutline, aHole );
1343 }
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 1177 of file shape_poly_set.cpp.

1178 {
1179  BOX2I bb;
1180 
1181  for( unsigned i = 0; i < m_polys.size(); i++ )
1182  {
1183  if( i == 0 )
1184  bb = m_polys[i][0].BBox();
1185  else
1186  bb.Merge( m_polys[i][0].BBox() );
1187  }
1188 
1189  bb.Inflate( aClearance );
1190  return bb;
1191 }
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::CombineAllAreasInNet(), APERTURE_MACRO::GetApertureMacroShape(), D_PAD::GetBestAnchorPosition(), ZONE_CONTAINER::GetBoundingBox(), WS_DRAW_ITEM_POLYPOLYGONS::GetBoundingBox(), GERBER_DRAW_ITEM::GetBoundingBox(), partitionPolyIntoRegularCellGrid(), BOARD::TestAreaIntersection(), KIGFX::PREVIEW::POLYGON_ITEM::ViewBBox(), and KIGFX::PREVIEW::CENTRELINE_RECT_ITEM::ViewBBox().

◆ BBoxFromCaches()

const BOX2I SHAPE_POLY_SET::BBoxFromCaches ( ) const

Definition at line 1194 of file shape_poly_set.cpp.

1195 {
1196  BOX2I bb;
1197 
1198  for( unsigned i = 0; i < m_polys.size(); i++ )
1199  {
1200  if( i == 0 )
1201  bb = m_polys[i][0].BBoxFromCache();
1202  else
1203  bb.Merge( m_polys[i][0].BBoxFromCache() );
1204  }
1205 
1206  return bb;
1207 }
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::testOverlappingComponentCourtyards().

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

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

References booleanOp().

Referenced by D_PAD::addPadPrimitivesToPolygon(), ZONE_CONTAINER::BuildSmoothedPoly(), BOARD::CombineAreas(), ALTIUM_PCB::ParseRegions6Data(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), C3D_RENDER_OGL_LEGACY::reload(), ZONE_CONTAINER::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 509 of file shape_poly_set.cpp.

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

References booleanOp().

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

504 {
505  booleanOp( ctIntersection, b, aFastMode );
506 }
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_CONTAINER::BuildSmoothedPoly(), CN_VISITOR::checkZoneZoneConnection(), ZONE_FILLER::computeRawFilledArea(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), ZONE_FILLER::fillSingleZone(), D_PAD::HitTest(), insideArea(), insideCourtyard(), PAD_TOOL::recombinePad(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testOverlappingComponentCourtyards(), TransformOvalToPolygon(), and TransformRoundChamferedRectToPolygon().

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

528 {
529  booleanOp( ctIntersection, a, b, aFastMode );
530 }
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 455 of file shape_poly_set.cpp.

457 {
458  booleanOp( aType, *this, aOtherShape, aFastMode );
459 }
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 462 of file shape_poly_set.cpp.

466 {
467  Clipper c;
468 
469  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
470 
471  for( auto poly : aShape.m_polys )
472  {
473  for( size_t i = 0 ; i < poly.size(); i++ )
474  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
475  }
476 
477  for( auto poly : aOtherShape.m_polys )
478  {
479  for( size_t i = 0; i < poly.size(); i++ )
480  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
481  }
482 
483  PolyTree solution;
484 
485  c.Execute( aType, solution, pftNonZero, pftNonZero );
486 
487  importTree( &solution );
488 }
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 
)

Performs boolean polyset difference For aFastMode meaning, see function booleanOp

Definition at line 497 of file shape_poly_set.cpp.

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

References booleanOp().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), addHoleToPolygon(), ZONE_FILLER::computeRawFilledArea(), MODULE::CoverageRatio(), BOARD_ADAPTER::createLayers(), BITMAPCONV_INFO::createOutputData(), TRACKS_CLEANER::deleteTracksInPads(), C3D_RENDER_OGL_LEGACY::generate_3D_Vias_and_Pads(), AR_AUTOPLACER::genModuleOnRoutingMatrix(), APERTURE_MACRO::GetApertureMacroShape(), ZONE_FILLER::knockoutThermalReliefs(), NormalizeAreaOutlines(), ZONE_CREATE_HELPER::performZoneCutout(), PlotSolderMaskLayer(), and TransformRoundChamferedRectToPolygon().

◆ BooleanSubtract() [2/2]

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

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

Definition at line 517 of file shape_poly_set.cpp.

520 {
521  booleanOp( ctDifference, a, b, aFastMode );
522 }
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 1414 of file shape_poly_set.cpp.

1415 {
1416  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1417  {
1418  Outline( polygonIdx ).GenerateBBoxCache();
1419 
1420  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1421  Hole( polygonIdx, holeIdx ).GenerateBBoxCache();
1422  }
1423 }
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 1968 of file shape_poly_set.cpp.

1969 {
1970  bool recalculate = !m_hash.IsValid();
1971  MD5_HASH hash;
1972 
1973  if( !m_triangulationValid )
1974  recalculate = true;
1975 
1976  if( !recalculate )
1977  {
1978  hash = checksum();
1979 
1980  if( m_hash != hash )
1981  {
1982  m_hash = hash;
1983  recalculate = true;
1984  }
1985  }
1986 
1987  if( !recalculate )
1988  return;
1989 
1990  SHAPE_POLY_SET tmpSet;
1991 
1992  if( aPartition )
1993  // This partitions into regularly-sized grids (1cm in pcbnew)
1994  partitionPolyIntoRegularCellGrid( *this, 1e7, tmpSet );
1995  else
1996  {
1997  tmpSet = *this;
1998 
1999  if( tmpSet.HasHoles() )
2000  tmpSet.Fracture( PM_FAST );
2001  }
2002 
2003  m_triangulatedPolys.clear();
2004  m_triangulationValid = true;
2005 
2006  while( tmpSet.OutlineCount() > 0 )
2007  {
2008  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2009  PolygonTriangulation tess( *m_triangulatedPolys.back() );
2010 
2011  // If the tesselation fails, we re-fracture the polygon, which will
2012  // first simplify the system before fracturing and removing the holes
2013  // This may result in multiple, disjoint polygons.
2014  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
2015  {
2016  tmpSet.Fracture( PM_FAST );
2017  m_triangulationValid = false;
2018  continue;
2019  }
2020 
2021  tmpSet.DeletePolygon( 0 );
2022  m_triangulationValid = true;
2023  }
2024 
2025  if( m_triangulationValid )
2026  m_hash = checksum();
2027 }
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 Convert_shape_line_polygon_to_triangles(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::PCB_PAINTER::draw(), 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( 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:636
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 220 of file shape.h.

221  {
222  return BBox( 0 ).Centre(); // if nothing better is available....
223  }
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 PNS_PCBNEW_RULE_RESOLVER::CollideHoles().

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

1674 {
1675  SHAPE_POLY_SET chamfered;
1676 
1677  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1678  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
1679 
1680  return chamfered;
1681 }
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 1695 of file shape_poly_set.cpp.

1697 {
1698  // Null segments create serious issues in calculations. Remove them:
1700 
1701  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1702  SHAPE_POLY_SET::POLYGON newPoly;
1703 
1704  // If the chamfering distance is zero, then the polygon remain intact.
1705  if( aDistance == 0 )
1706  {
1707  return currentPoly;
1708  }
1709 
1710  // Iterate through all the contours (outline and holes) of the polygon.
1711  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1712  {
1713  // Generate a new contour in the new polygon
1714  SHAPE_LINE_CHAIN newContour;
1715 
1716  // Iterate through the vertices of the contour
1717  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1718  {
1719  // Current vertex
1720  int x1 = currContour.CPoint( currVertex ).x;
1721  int y1 = currContour.CPoint( currVertex ).y;
1722 
1723  // Indices for previous and next vertices.
1724  int prevVertex;
1725  int nextVertex;
1726 
1727  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1728 
1729  // Previous vertex is the last one if the current vertex is the first one
1730  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1731 
1732  // next vertex is the first one if the current vertex is the last one.
1733  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1734 
1735  // Previous vertex computation
1736  double xa = currContour.CPoint( prevVertex ).x - x1;
1737  double ya = currContour.CPoint( prevVertex ).y - y1;
1738 
1739  // Next vertex computation
1740  double xb = currContour.CPoint( nextVertex ).x - x1;
1741  double yb = currContour.CPoint( nextVertex ).y - y1;
1742 
1743  // Compute the new distances
1744  double lena = hypot( xa, ya );
1745  double lenb = hypot( xb, yb );
1746 
1747  // Make the final computations depending on the mode selected, chamfered or filleted.
1748  if( aMode == CORNER_MODE::CHAMFERED )
1749  {
1750  double distance = aDistance;
1751 
1752  // Chamfer one half of an edge at most
1753  if( 0.5 * lena < distance )
1754  distance = 0.5 * lena;
1755 
1756  if( 0.5 * lenb < distance )
1757  distance = 0.5 * lenb;
1758 
1759  int nx1 = KiROUND( distance * xa / lena );
1760  int ny1 = KiROUND( distance * ya / lena );
1761 
1762  newContour.Append( x1 + nx1, y1 + ny1 );
1763 
1764  int nx2 = KiROUND( distance * xb / lenb );
1765  int ny2 = KiROUND( distance * yb / lenb );
1766 
1767  newContour.Append( x1 + nx2, y1 + ny2 );
1768  }
1769  else // CORNER_MODE = FILLETED
1770  {
1771  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1772 
1773  double radius = aDistance;
1774  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1775 
1776  // Do nothing in case of parallel edges
1777  if( std::isinf( denom ) )
1778  continue;
1779 
1780  // Limit rounding distance to one half of an edge
1781  if( 0.5 * lena * denom < radius )
1782  radius = 0.5 * lena * denom;
1783 
1784  if( 0.5 * lenb * denom < radius )
1785  radius = 0.5 * lenb * denom;
1786 
1787  // Calculate fillet arc absolute center point (xc, yx)
1788  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1789  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1790  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1791  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1792  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1793 
1794  // Calculate arc start and end vectors
1795  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1796  double xs = x1 + k * xa / lena - xc;
1797  double ys = y1 + k * ya / lena - yc;
1798  double xe = x1 + k * xb / lenb - xc;
1799  double ye = y1 + k * yb / lenb - yc;
1800 
1801  // Cosine of arc angle
1802  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1803 
1804  // Make sure the argument is in [-1,1], interval in which the acos function is
1805  // defined
1806  if( argument < -1 )
1807  argument = -1;
1808  else if( argument > 1 )
1809  argument = 1;
1810 
1811  double arcAngle = acos( argument );
1812  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1813  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1814 
1815  double deltaAngle = arcAngle / segments;
1816  double startAngle = atan2( -ys, xs );
1817 
1818  // Flip arc for inner corners
1819  if( xa * yb - ya * xb <= 0 )
1820  deltaAngle *= -1;
1821 
1822  double nx = xc + xs;
1823  double ny = yc + ys;
1824 
1825  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1826 
1827  // Store the previous added corner to make a sanity check
1828  int prevX = KiROUND( nx );
1829  int prevY = KiROUND( ny );
1830 
1831  for( int j = 0; j < segments; j++ )
1832  {
1833  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1834  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1835 
1836  // Sanity check: the rounding can produce repeated corners; do not add them.
1837  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1838  {
1839  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1840  prevX = KiROUND( nx );
1841  prevY = KiROUND( ny );
1842  }
1843  }
1844  }
1845  }
1846 
1847  // Close the current contour and add it the new polygon
1848  newContour.SetClosed( true );
1849  newPoly.push_back( newContour );
1850  }
1851 
1852  return newPoly;
1853 }
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()
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
SHAPE_LINE_CHAIN.
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h: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 1561 of file shape_poly_set.cpp.

1562 {
1563  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
1564 }
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 2030 of file shape_poly_set.cpp.

2031 {
2032  MD5_HASH hash;
2033 
2034  hash.Hash( m_polys.size() );
2035 
2036  for( const auto& outline : m_polys )
2037  {
2038  hash.Hash( outline.size() );
2039 
2040  for( const auto& lc : outline )
2041  {
2042  hash.Hash( lc.PointCount() );
2043 
2044  for( int i = 0; i < lc.PointCount(); i++ )
2045  {
2046  hash.Hash( lc.CPoint( i ).x );
2047  hash.Hash( lc.CPoint( i ).y );
2048  }
2049  }
2050  }
2051 
2052  hash.Finalize();
2053 
2054  return hash;
2055 }
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 769 of file shape_poly_set.h.

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

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

Referenced by D_PAD::AddPrimitivePoly(), DRAWSEGMENT::BuildPolyPointsList(), ConvertOutlineToPolygon(), PCB_IO::format(), DRAWSEGMENT::GetBoundingBox(), and ZONE_CONTAINER::GetInteractingZones().

◆ CIterate() [2/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aOutline) const
inline

Definition at line 783 of file shape_poly_set.h.

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

References CIterate().

◆ CIterate() [3/3]

CONST_ITERATOR SHAPE_POLY_SET::CIterate ( ) const
inline

Definition at line 793 of file shape_poly_set.h.

794  {
795  return CIterate( 0, OutlineCount() - 1 );
796  }
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 840 of file shape_poly_set.h.

842  {
844 
845  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
846  iter.m_currentPolygon = aFirst;
847  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
848  iter.m_currentContour = 0;
849  iter.m_currentSegment = 0;
850  iter.m_iterateHoles = aIterateHoles;
851 
852  return iter;
853  }
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(), DRC_TEST_PROVIDER_CLEARANCE_BASE::getLocation(), and BRDITEMS_PLOTTER::PlotDrawSegment().

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

863  {
864  return CIterateSegments( aPolygonIdx, aPolygonIdx );
865  }
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 886 of file shape_poly_set.h.

887  {
888  return CIterateSegments( 0, OutlineCount() - 1, true );
889  }
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 892 of file shape_poly_set.h.

893  {
894  return CIterateSegments( aOutline, aOutline, true );
895  }
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 788 of file shape_poly_set.h.

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

References CIterate().

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

◆ CIterateWithHoles() [2/2]

CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( ) const
inline

Definition at line 798 of file shape_poly_set.h.

799  {
800  return CIterate( 0, OutlineCount() - 1, true );
801  }
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 96 of file shape_poly_set.cpp.

97 {
98  return new SHAPE_POLY_SET( *this );
99 }

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
aActualan optional pointer to an int to store the actual distance 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 719 of file shape_collisions.cpp.

720 {
721  return collideShapes( this, aShape, aClearance, nullptr, aMTV );
722 }
static bool collideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)

References collideShapes().

◆ Collide() [2/4]

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

Reimplemented in SHAPE_RECT, SHAPE_SEGMENT, and SHAPE_COMPOUND.

Definition at line 725 of file shape_collisions.cpp.

726 {
727  return collideShapes( this, aShape, aClearance, aActual, nullptr );
728 }
static bool collideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, int *aActual, VECTOR2I *aMTV)

References collideShapes().

◆ Collide() [3/4]

bool SHAPE_POLY_SET::Collide ( const VECTOR2I aP,
int  aClearance = 0,
int *  aActual = 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 1243 of file shape_poly_set.cpp.

1244 {
1245  ecoord dist_sq = SquaredDistance( aP );
1246 
1247  if( dist_sq == 0 || dist_sq < (ecoord) aClearance * aClearance )
1248  {
1249  if( aActual )
1250  *aActual = sqrt( dist_sq );
1251 
1252  return true;
1253  }
1254 
1255  return false;
1256 }
SEG::ecoord SquaredDistance(VECTOR2I aPoint) const
Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in...
VECTOR2I::extended_type ecoord

References SquaredDistance().

Referenced by WS_DRAW_ITEM_POLYPOLYGONS::HitTest(), DRAWSEGMENT::HitTest(), and MODULE::HitTestAccurate().

◆ Collide() [4/4]

bool SHAPE_POLY_SET::Collide ( const SEG aSeg,
int  aClearance = 0,
int *  aActual = 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 1227 of file shape_poly_set.cpp.

1228 {
1229  ecoord dist_sq = SquaredDistance( aSeg );
1230 
1231  if( dist_sq == 0 || dist_sq < (ecoord) aClearance * aClearance )
1232  {
1233  if( aActual )
1234  *aActual = sqrt( dist_sq );
1235 
1236  return true;
1237  }
1238 
1239  return false;
1240 }
SEG::ecoord SquaredDistance(VECTOR2I aPoint) const
Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in...
VECTOR2I::extended_type ecoord

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

1388 {
1389  // Shows whether there was a collision
1390  bool collision = false;
1391 
1392  for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
1393  {
1394  const SEG currentSegment = *iterator;
1395  int distance = currentSegment.Distance( aPoint );
1396 
1397  // Check for collisions
1398  if( distance <= aClearance )
1399  {
1400  collision = true;
1401 
1402  // Update aClearance to look for closer edges
1403  aClearance = distance;
1404 
1405  // Store the indices that identify the vertex
1406  aClosestVertex = iterator.GetIndex();
1407  }
1408  }
1409 
1410  return collision;
1411 }
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
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
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)

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

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

◆ CollideVertex()

bool SHAPE_POLY_SET::CollideVertex ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex,
int  aClearance = 0 
) 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 1346 of file shape_poly_set.cpp.

1349 {
1350  // Shows whether there was a collision
1351  bool collision = false;
1352 
1353  // Difference vector between each vertex and aPoint.
1354  VECTOR2D delta;
1355  double distance, clearance;
1356 
1357  // Convert clearance to double for precission when comparing distances
1358  clearance = aClearance;
1359 
1360  for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
1361  {
1362  // Get the difference vector between current vertex and aPoint
1363  delta = *iterator - aPoint;
1364 
1365  // Compute distance
1366  distance = delta.EuclideanNorm();
1367 
1368  // Check for collisions
1369  if( distance <= clearance )
1370  {
1371  collision = true;
1372 
1373  // Update aClearance to look for closer vertices
1374  clearance = distance;
1375 
1376  // Store the indices that identify the vertex
1377  aClosestVertex = iterator.GetIndex();
1378  }
1379  }
1380 
1381  return collision;
1382 }
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:299
CONST_ITERATOR CIterateWithHoles() const

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

Referenced by ZONE_CONTAINER::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 1426 of file shape_poly_set.cpp.

1428 {
1429  if( m_polys.empty() )
1430  return false;
1431 
1432  // If there is a polygon specified, check the condition against that polygon
1433  if( aSubpolyIndex >= 0 )
1434  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1435 
1436  // In any other case, check it against all polygons in the set
1437  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1438  {
1439  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1440  return true;
1441  }
1442 
1443  return false;
1444 }
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(), D_PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::HitTest(), ZONE_CONTAINER::HitTestFilledArea(), DIMENSION::segPolyIntersection(), BOARD::TestAreaIntersection(), 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 1482 of file shape_poly_set.cpp.

1484 {
1485  // Check that the point is inside the outline
1486  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1487  {
1488  // Check that the point is not in any of the holes
1489  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1490  {
1491  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1492 
1493  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1494  // here as it's meaning would be inverted.
1495  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1496  return false;
1497  }
1498 
1499  return true;
1500  }
1501 
1502  return false;
1503 }
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 299 of file shape_poly_set.cpp.

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

References m_polys.

Referenced by POINT_EDITOR::addCorner(), CVertex(), D_CODE::DrawFlashedPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), findVertex(), ZONE_CONTAINER::GetCornerPosition(), DRAWSEGMENT::GetPosition(), ZONE_CONTAINER::HatchBorder(), DRAWSEGMENT::HitTest(), ZONE_CONTAINER::HitTest(), ZONE_CONTAINER::MoveEdge(), ZONE_CONTAINER::SetCornerPosition(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testOverlappingComponentCourtyards(), POINT_EDITOR::updateItem(), and POINT_EDITOR::updatePoints().

◆ CVertex() [2/3]

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

Returns the aGlobalIndex-th vertex in the poly set

Definition at line 318 of file shape_poly_set.cpp.

319 {
321 
322  // Assure the passed index references a legal position; abort otherwise
323  if( !GetRelativeIndices( aGlobalIndex, &index ) )
324  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
325 
326  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
327 }
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 330 of file shape_poly_set.cpp.

331 {
332  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
333 }
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 964 of file shape_poly_set.h.

966  {
967  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
968  }
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.

References Inflate().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), 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 1328 of file shape_poly_set.cpp.

1329 {
1330  m_polys.erase( m_polys.begin() + aIdx );
1331 }

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

1685 {
1686  SHAPE_POLY_SET filleted;
1687 
1688  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1689  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
1690 
1691  return filleted;
1692 }
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 1567 of file shape_poly_set.cpp.

1569 {
1570  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
1571 }
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 1093 of file shape_poly_set.cpp.

1094 {
1095  std::stringstream ss;
1096 
1097  ss << "polyset " << m_polys.size() << "\n";
1098 
1099  for( unsigned i = 0; i < m_polys.size(); i++ )
1100  {
1101  ss << "poly " << m_polys[i].size() << "\n";
1102 
1103  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1104  {
1105  ss << m_polys[i][j].PointCount() << "\n";
1106 
1107  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1108  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1109  }
1110 
1111  ss << "\n";
1112  }
1113 
1114  return ss.str();
1115 }

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

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

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

Referenced by addHoleToPolygon(), D_PAD::addPadPrimitivesToPolygon(), D_PAD::AddPrimitivePoly(), CacheTriangulation(), ZONE_FILLER::computeRawFilledArea(), MODULE::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(), EAGLE_PLUGIN::loadPolygon(), BRDITEMS_PLOTTER::PlotDrawSegment(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), PlotStandardLayer(), C3D_RENDER_RAYTRACING::reload(), TransformRingToPolygon(), D_PAD::TransformShapeWithClearanceToPolygon(), ZONE_CONTAINER::TransformSmoothedOutlineWithClearanceToPolygon(), and GBR_TO_PCB_EXPORTER::writePcbPolygon().

◆ fractureSingle()

void SHAPE_POLY_SET::fractureSingle ( POLYGON paths)
private

Definition at line 750 of file shape_poly_set.cpp.

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

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

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

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

◆ GetHash()

MD5_HASH SHAPE_POLY_SET::GetHash ( ) const

Definition at line 1876 of file shape_poly_set.cpp.

1877 {
1878  if( !m_hash.IsValid() )
1879  return checksum();
1880 
1881  return m_hash;
1882 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:24

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

Referenced by operator=(), and SHAPE_POLY_SET().

◆ GetIndexableSubshape()

virtual void SHAPE_BASE::GetIndexableSubshape ( SHAPE_BASE aSubshape) const
inlinevirtualinherited

Definition at line 108 of file shape.h.

108 {};

◆ GetIndexableSubshapeCount()

virtual size_t SHAPE_BASE::GetIndexableSubshapeCount ( )
inlinevirtualinherited

Definition at line 106 of file shape.h.

106 { return 0; }

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

337 {
339 
340  // If the edge does not exist, throw an exception, it is an illegal access memory error
341  if( !GetRelativeIndices( aGlobalIndex, &index ) )
342  return false;
343 
344  // Calculate the previous and next index of aGlobalIndex, corresponding to
345  // the same contour;
346  VERTEX_INDEX inext = index;
347  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
348 
349  if( index.m_vertex == 0 )
350  {
351  index.m_vertex = lastpoint;
352  inext.m_vertex = 1;
353  }
354  else if( index.m_vertex == lastpoint )
355  {
356  index.m_vertex--;
357  inext.m_vertex = 0;
358  }
359  else
360  {
361  inext.m_vertex++;
362  index.m_vertex--;
363  }
364 
365  if( aPrevious )
366  {
367  int previous;
368  GetGlobalIndex( index, previous );
369  *aPrevious = previous;
370  }
371 
372  if( aNext )
373  {
374  int next;
375  GetGlobalIndex( inext, next );
376  *aNext = next;
377  }
378 
379  return true;
380 }
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_CONTAINER::MoveEdge().

◆ GetRelativeIndices()

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

Function GetRelativeIndices.

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

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

Definition at line 102 of file shape_poly_set.cpp.

104 {
105  int polygonIdx = 0;
106  unsigned int contourIdx = 0;
107  int vertexIdx = 0;
108 
109  int currentGlobalIdx = 0;
110 
111  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
112  {
113  const POLYGON& currentPolygon = CPolygon( polygonIdx );
114 
115  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
116  {
117  const SHAPE_LINE_CHAIN& currentContour = currentPolygon[contourIdx];
118  int totalPoints = currentContour.PointCount();
119 
120  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
121  {
122  // Check if the current vertex is the globally indexed as aGlobalIdx
123  if( currentGlobalIdx == aGlobalIdx )
124  {
125  aRelativeIndices->m_polygon = polygonIdx;
126  aRelativeIndices->m_contour = contourIdx;
127  aRelativeIndices->m_vertex = vertexIdx;
128 
129  return true;
130  }
131 
132  // Advance
133  currentGlobalIdx++;
134  }
135  }
136  }
137 
138  return false;
139 }
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_CONTAINER::GetCornerPosition(), GetNeighbourIndexes(), InsertVertex(), IsVertexInHole(), IterateFromVertexWithHoles(), RemoveVertex(), ZONE_CONTAINER::SetCornerPosition(), ZONE_CONTAINER::SetSelectedCorner(), and SetVertex().

◆ HasHoles()

bool SHAPE_POLY_SET::HasHoles ( ) const

Returns true if the polygon set has any holes.

Definition at line 1026 of file shape_poly_set.cpp.

1027 {
1028  // Iterate through all the polygons on the set
1029  for( const POLYGON& paths : m_polys )
1030  {
1031  // If any of them has more than one contour, it is a hole.
1032  if( paths.size() > 1 )
1033  return true;
1034  }
1035 
1036  // Return false if and only if every polygon has just one outline, without holes.
1037  return false;
1038 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.

References m_polys.

Referenced by CacheTriangulation().

◆ HasIndexableSubshapes()

virtual bool SHAPE_BASE::HasIndexableSubshapes ( ) const
inlinevirtualinherited

Definition at line 101 of file shape.h.

102  {
103  return false;
104  }

◆ HasTouchingHoles()

bool SHAPE_POLY_SET::HasTouchingHoles ( ) const

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

Definition at line 2058 of file shape_poly_set.cpp.

2059 {
2060  for( int i = 0; i < OutlineCount(); i++ )
2061  {
2062  if( hasTouchingHoles( CPolygon( i ) ) )
2063  {
2064  return true;
2065  }
2066  }
2067 
2068  return false;
2069 }
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 2072 of file shape_poly_set.cpp.

2073 {
2074  std::set< long long > ptHashes;
2075 
2076  for( const auto& lc : aPoly )
2077  {
2078  for( const VECTOR2I& pt : lc.CPoints() )
2079  {
2080  const long long ptHash = (long long) pt.x << 32 | pt.y;
2081 
2082  if( ptHashes.count( ptHash ) > 0 )
2083  {
2084  return true;
2085  }
2086 
2087  ptHashes.insert( ptHash );
2088  }
2089  }
2090 
2091  return false;
2092 }

Referenced by HasTouchingHoles().

◆ Hole()

◆ HoleCount()

int SHAPE_POLY_SET::HoleCount ( int  aOutline) const
inline

◆ importTree()

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

Definition at line 625 of file shape_poly_set.cpp.

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

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

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

535 {
536  Simplify( aFastMode );
537  Inflate( aFactor, aCircleSegmentsCount );
538  Fracture( aFastMode );
539 }
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_CONTAINER::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 237 of file shape_poly_set.cpp.

238 {
239  VERTEX_INDEX index;
240 
241  if( aGlobalIndex < 0 )
242  aGlobalIndex = 0;
243 
244  if( aGlobalIndex >= TotalVertices() )
245  {
246  Append( aNewVertex );
247  }
248  else
249  {
250  // Assure the position to be inserted exists; throw an exception otherwise
251  if( GetRelativeIndices( aGlobalIndex, &index ) )
252  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
253  else
254  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
255  }
256 }
int TotalVertices() const
Returns total number of vertices stored in the set.
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)

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

Referenced by POINT_EDITOR::addCorner().

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

159  {
160  return m_type == SH_NULL;
161  }
SHAPE_TYPE m_type
type of our shape
Definition: shape.h:108
circular arc
Definition: shape.h:50

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

384 {
385  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
386  CONST_SEGMENT_ITERATOR innerIterator;
387 
388  for( iterator = CIterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
389  {
390  SEG firstSegment = *iterator;
391 
392  // Iterate through all remaining segments.
393  innerIterator = iterator;
394 
395  // Start in the next segment, we don't want to check collision between a segment and itself
396  for( innerIterator++; innerIterator; innerIterator++ )
397  {
398  SEG secondSegment = *innerIterator;
399 
400  // Check whether the two segments built collide, only when they are not adjacent.
401  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
402  return true;
403  }
404  }
405 
406  return false;
407 }
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:128
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 410 of file shape_poly_set.cpp.

411 {
412  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
413  {
414  if( IsPolygonSelfIntersecting( polygon ) )
415  return true;
416  }
417 
418  return false;
419 }
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Function IsPolygonSelfIntersecting.

References IsPolygonSelfIntersecting(), and m_polys.

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

◆ IsSolid()

bool SHAPE_POLY_SET::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 1032 of file shape_poly_set.h.

1033  {
1034  return true;
1035  }

◆ IsTriangulationUpToDate()

bool SHAPE_POLY_SET::IsTriangulationUpToDate ( ) const

Definition at line 1885 of file shape_poly_set.cpp.

1886 {
1887  if( !m_triangulationValid )
1888  return false;
1889 
1890  if( !m_hash.IsValid() )
1891  return false;
1892 
1893  auto hash = checksum();
1894 
1895  return hash == m_hash;
1896 }
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(), 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 1660 of file shape_poly_set.cpp.

1661 {
1662  VERTEX_INDEX index;
1663 
1664  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1665  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1666  return false;
1667 
1668  // The contour is a hole if its index is greater than zero
1669  return index.m_contour > 0;
1670 }
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 712 of file shape_poly_set.h.

713  {
714  ITERATOR iter;
715 
716  iter.m_poly = this;
717  iter.m_currentPolygon = aFirst;
718  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
719  iter.m_currentContour = 0;
720  iter.m_currentVertex = 0;
721  iter.m_iterateHoles = aIterateHoles;
722 
723  return iter;
724  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR

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

Referenced by POINT_EDITOR::addCorner(), and ZONE_CONTAINER::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 732 of file shape_poly_set.h.

733  {
734  return Iterate( aOutline, aOutline );
735  }
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 753 of file shape_poly_set.h.

754  {
755  return Iterate( 0, OutlineCount() - 1 );
756  }
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 803 of file shape_poly_set.h.

804  {
805  // Build iterator
806  ITERATOR iter = IterateWithHoles();
807 
808  // Get the relative indices of the globally indexed vertex
809  VERTEX_INDEX indices;
810 
811  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
812  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
813 
814  // Adjust where the iterator is pointing
815  iter.m_currentPolygon = indices.m_polygon;
816  iter.m_currentContour = indices.m_contour;
817  iter.m_currentVertex = indices.m_vertex;
818 
819  return iter;
820  }
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 824 of file shape_poly_set.h.

825  {
826  SEGMENT_ITERATOR iter;
827 
828  iter.m_poly = this;
829  iter.m_currentPolygon = aFirst;
830  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
831  iter.m_currentContour = 0;
832  iter.m_currentSegment = 0;
833  iter.m_iterateHoles = aIterateHoles;
834 
835  return iter;
836  }
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::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 856 of file shape_poly_set.h.

857  {
858  return IterateSegments( aPolygonIdx, aPolygonIdx );
859  }
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 868 of file shape_poly_set.h.

869  {
870  return IterateSegments( 0, OutlineCount() - 1 );
871  }
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 874 of file shape_poly_set.h.

875  {
876  return IterateSegments( 0, OutlineCount() - 1, true );
877  }
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_CONTAINER::HatchBorder(), and BOARD::TestAreaIntersection().

◆ IterateSegmentsWithHoles() [2/2]

SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( int  aOutline)
inline

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

Definition at line 880 of file shape_poly_set.h.

881  {
882  return IterateSegments( aOutline, aOutline, true );
883  }
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 743 of file shape_poly_set.h.

744  {
745  return Iterate( aOutline, aOutline, true );
746  }
ITERATOR Iterate()
Function Iterate.

References Iterate().

Referenced by findVertex(), ZONE_CONTAINER::HatchBorder(), ZONE_CONTAINER::IterateWithHoles(), and BOARD::TestAreaIntersection().

◆ IterateWithHoles() [2/2]

ITERATOR SHAPE_POLY_SET::IterateWithHoles ( )
inline

Function IterateWithHoles.

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

Definition at line 763 of file shape_poly_set.h.

764  {
765  return Iterate( 0, OutlineCount() - 1, true );
766  }
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 1521 of file shape_poly_set.cpp.

1522 {
1523  for( POLYGON& poly : m_polys )
1524  {
1525  for( SHAPE_LINE_CHAIN& path : poly )
1526  {
1527  path.Mirror( aX, aY, aRef );
1528  }
1529  }
1530 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
SHAPE_LINE_CHAIN.

References m_polys.

Referenced by GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), EDGE_MODULE::Flip(), DRAWSEGMENT::Flip(), EDGE_MODULE::Mirror(), and ZONE_CONTAINER::Mirror().

◆ Move()

void SHAPE_POLY_SET::Move ( const VECTOR2I aVector)
overridevirtual

Implements SHAPE.

Definition at line 1506 of file shape_poly_set.cpp.

1507 {
1508  for( POLYGON& poly : m_polys )
1509  {
1510  for( SHAPE_LINE_CHAIN& path : poly )
1511  path.Move( aVector );
1512  }
1513 
1514  for( auto& tri : m_triangulatedPolys )
1515  tri->Move( aVector );
1516 
1517  m_hash = checksum();
1518 }
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(), GERBER_DRAW_ITEM::HitTest(), EDGE_MODULE::Move(), DRAWSEGMENT::Move(), ZONE_CONTAINER::Move(), GERBER_DRAW_ITEM::MoveAB(), GERBER_DRAW_ITEM::MoveXY(), WS_DRAW_ITEM_POLYPOLYGONS::SetPosition(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), and D_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 197 of file shape_poly_set.cpp.

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

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

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

◆ NewOutline()

int SHAPE_POLY_SET::NewOutline ( )

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

Definition at line 185 of file shape_poly_set.cpp.

186 {
187  SHAPE_LINE_CHAIN empty_path;
188  POLYGON poly;
189 
190  empty_path.SetClosed( true );
191  poly.push_back( empty_path );
192  m_polys.push_back( poly );
193  return m_polys.size() - 1;
194 }
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(), addRect(), ZONE_CONTAINER::AppendCorner(), BuildBoardPolygonOutlines(), KI_TEST::CommonTestData::CommonTestData(), ConvertOutlineToPolygon(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), BOARD_ADAPTER::createNewPadWithClearance(), BITMAPCONV_INFO::createOutputData(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), fillArcPOLY(), MODULE::GetBoundingPoly(), getRectangleAlongCentreLine(), DRAWSEGMENT::HitTest(), D_PAD::HitTest(), EAGLE_PLUGIN::loadPolygon(), LEGACY_PLUGIN::loadZONE_CONTAINER(), PCB_PARSER::parseZONE_CONTAINER(), DXF_PLOTTER::PlotPoly(), DRAWSEGMENT::Rotate(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), DRAWSEGMENT::SetPolyPoints(), WS_DATA_ITEM_POLYGONS::SyncDrawItems(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), DRAWSEGMENT::TransformShapeWithClearanceToPolygon(), D_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 1060 of file shape_poly_set.cpp.

1061 {
1062  // We are expecting only one main outline, but this main outline can have holes
1063  // if holes: combine holes and remove them from the main outline.
1064  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1065  // calculations, but it is not mandatory. It is used mainly
1066  // because there is usually only very few vertices in area outlines
1067  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1068  SHAPE_POLY_SET holesBuffer;
1069 
1070  // Move holes stored in outline to holesBuffer:
1071  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1072  while( outline.size() > 1 )
1073  {
1074  holesBuffer.AddOutline( outline.back() );
1075  outline.pop_back();
1076  }
1077 
1079 
1080  // If any hole, substract it to main outline
1081  if( holesBuffer.OutlineCount() )
1082  {
1083  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1085  }
1086 
1088 
1089  return OutlineCount();
1090 }
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 1856 of file shape_poly_set.cpp.

1857 {
1858  static_cast<SHAPE&>(*this) = aOther;
1859  m_polys = aOther.m_polys;
1860  m_triangulatedPolys.clear();
1861  m_triangulationValid = false;
1862 
1863  if( aOther.IsTriangulationUpToDate() )
1864  {
1865  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
1866  m_triangulatedPolys.push_back(
1867  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
1868 
1869  m_hash = aOther.GetHash();
1870  m_triangulationValid = true;
1871  }
1872 
1873  return *this;
1874 }
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()

SHAPE_LINE_CHAIN& SHAPE_POLY_SET::Outline ( int  aIndex)
inline

Returns the reference to aIndex-th outline in the set

Definition at line 644 of file shape_poly_set.h.

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

References m_polys.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), BuildBBoxCaches(), ZONE_CONTAINER::CalculateFilledArea(), GRID_HELPER::computeAnchors(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), BITMAPCONV_INFO::createOutputData(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), DIALOG_PAD_PRIMITIVE_POLY_PROPS::DIALOG_PAD_PRIMITIVE_POLY_PROPS(), KIGFX::WS_PAINTER::draw(), APERTURE_MACRO::DrawApertureMacroShape(), export_vrml_padshape(), DSN::SPECCTRA_DB::fillBOUNDARY(), AR_AUTOPLACER::fillMatrix(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadRoundRect(), PSLIKE_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), DXF_PLOTTER::FlashPadRoundRect(), PCB_IO::format(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), DRAWSEGMENT::GetMsgPanelInfo(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), 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(), POINT_EDITOR::removeCorner(), POINT_EDITOR::removeCornerCondition(), DRAWSEGMENT::Scale(), GBR_TO_PCB_EXPORTER::writePcbPolygon(), and GBR_TO_PCB_EXPORTER::writePcbZoneItem().

◆ OutlineCount()

int SHAPE_POLY_SET::OutlineCount ( ) const
inline

Returns the number of outlines in the set

Definition at line 627 of file shape_poly_set.h.

627 { return m_polys.size(); }

References m_polys.

Referenced by POINT_EDITOR::addCorner(), ZONE_FILLER::addHatchFillTypeOnZone(), D_PAD::addPadPrimitivesToPolygon(), ZONE_CONTAINER::AddPolygon(), BOARD_ADAPTER::AddSolidAreasShapesToContainer(), CLAYER_TRIANGLES::AddToMiddleContourns(), ZONE_CONTAINER::AppendCorner(), BuildBBoxCaches(), BuildBoardPolygonOutlines(), BuildConvexHull(), DRAWSEGMENT::BuildPolyPointsList(), CacheTriangulation(), ZONE_CONTAINER::CalculateFilledArea(), CIterate(), CIterateSegments(), CIterateSegmentsWithHoles(), CIterateWithHoles(), BOARD::CombineAreas(), Contains(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), 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(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), C3D_RENDER_OGL_LEGACY::generate_3D_Vias_and_Pads(), C3D_RENDER_OGL_LEGACY::generate_holes_display_list(), C3D_RENDER_OGL_LEGACY::generateLayerListFromContainer(), APERTURE_MACRO::GetApertureMacroShape(), D_PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::GetBoundingBox(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), GetRelativeIndices(), HasTouchingHoles(), WS_DRAW_ITEM_POLYPOLYGONS::HitTest(), ZONE_CONTAINER::HitTestCutout(), insideArea(), insideCourtyard(), 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(), C3D_RENDER_OGL_LEGACY::reload(), C3D_RENDER_RAYTRACING::reload(), ZONE_CONTAINER::RemoveCutout(), Subset(), PNS_KICAD_IFACE_BASE::syncZone(), TestConcaveSquareFillet(), DRC_TEST_PROVIDER_COURTYARD_CLEARANCE::testOverlappingComponentCourtyards(), 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 1118 of file shape_poly_set.cpp.

1119 {
1120  std::string tmp;
1121 
1122  aStream >> tmp;
1123 
1124  if( tmp != "polyset" )
1125  return false;
1126 
1127  aStream >> tmp;
1128 
1129  int n_polys = atoi( tmp.c_str() );
1130 
1131  if( n_polys < 0 )
1132  return false;
1133 
1134  for( int i = 0; i < n_polys; i++ )
1135  {
1136  POLYGON paths;
1137 
1138  aStream >> tmp;
1139 
1140  if( tmp != "poly" )
1141  return false;
1142 
1143  aStream >> tmp;
1144  int n_outlines = atoi( tmp.c_str() );
1145 
1146  if( n_outlines < 0 )
1147  return false;
1148 
1149  for( int j = 0; j < n_outlines; j++ )
1150  {
1151  SHAPE_LINE_CHAIN outline;
1152 
1153  outline.SetClosed( true );
1154 
1155  aStream >> tmp;
1156  int n_vertices = atoi( tmp.c_str() );
1157 
1158  for( int v = 0; v < n_vertices; v++ )
1159  {
1160  VECTOR2I p;
1161 
1162  aStream >> tmp; p.x = atoi( tmp.c_str() );
1163  aStream >> tmp; p.y = atoi( tmp.c_str() );
1164  outline.Append( p );
1165  }
1166 
1167  paths.push_back( outline );
1168  }
1169 
1170  m_polys.push_back( paths );
1171  }
1172 
1173  return true;
1174 }
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 1210 of file shape_poly_set.cpp.

1211 {
1212  // Iterate through all the polygons in the set
1213  for( const POLYGON& polygon : m_polys )
1214  {
1215  // Iterate through all the line chains in the polygon
1216  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1217  {
1218  if( lineChain.PointOnEdge( aP ) )
1219  return true;
1220  }
1221  }
1222 
1223  return false;
1224 }
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 677 of file shape_poly_set.h.

678  {
679  return m_polys[aIndex];
680  }

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

1266 {
1267  // Default polygon is the last one
1268  if( aPolygonIdx < 0 )
1269  aPolygonIdx += m_polys.size();
1270 
1271  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1272 }

References m_polys.

Referenced by 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 1275 of file shape_poly_set.cpp.

1276 {
1277  int removed = 0;
1278 
1279  ITERATOR iterator = IterateWithHoles();
1280 
1281  VECTOR2I contourStart = *iterator;
1282  VECTOR2I segmentStart, segmentEnd;
1283 
1284  VERTEX_INDEX indexStart;
1285 
1286  while( iterator )
1287  {
1288  // Obtain first point and its index
1289  segmentStart = *iterator;
1290  indexStart = iterator.GetIndex();
1291 
1292  // Obtain last point
1293  if( iterator.IsEndContour() )
1294  {
1295  segmentEnd = contourStart;
1296 
1297  // Advance
1298  iterator++;
1299 
1300  if( iterator )
1301  contourStart = *iterator;
1302  }
1303  else
1304  {
1305  // Advance
1306  iterator++;
1307 
1308  if( iterator )
1309  segmentEnd = *iterator;
1310  }
1311 
1312  // Remove segment start if both points are equal
1313  if( segmentStart == segmentEnd )
1314  {
1315  RemoveVertex( indexStart );
1316  removed++;
1317 
1318  // Advance the iterator one position, as there is one vertex less.
1319  if( iterator )
1320  iterator++;
1321  }
1322  }
1323 
1324  return removed;
1325 }
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 1447 of file shape_poly_set.cpp.

1448 {
1449  VERTEX_INDEX index;
1450 
1451  // Assure the to be removed vertex exists, abort otherwise
1452  if( GetRelativeIndices( aGlobalIndex, &index ) )
1453  RemoveVertex( index );
1454  else
1455  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1456 }
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 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 1459 of file shape_poly_set.cpp.

1460 {
1461  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1462 }

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

1534 {
1535  for( POLYGON& poly : m_polys )
1536  {
1537  for( SHAPE_LINE_CHAIN& path : poly )
1538  path.Rotate( aAngle, aCenter );
1539  }
1540 
1541  // Don't re-cache if the triangulation is already invalid
1542  if( m_triangulationValid )
1544 }
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(), MODULE::GetBoundingPoly(), DRAWSEGMENT::Rotate(), ZONE_CONTAINER::Rotate(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), D_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 1476 of file shape_poly_set.cpp.

1477 {
1478  m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1479 }

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_CONTAINER::MoveEdge(), ZONE_CONTAINER::SetCornerPosition(), SetVertex(), and 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 1465 of file shape_poly_set.cpp.

1466 {
1467  VERTEX_INDEX index;
1468 
1469  if( GetRelativeIndices( aGlobalIndex, &index ) )
1470  SetVertex( index, aPos );
1471  else
1472  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1473 }
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 1052 of file shape_poly_set.cpp.

1053 {
1055 
1056  booleanOp( ctUnion, empty, aFastMode );
1057 }
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 D_PAD::addPadPrimitivesToPolygon(), BOARD_ADAPTER::AddShapeWithClearanceToContainer(), ZONE_FILLER::buildCopperItemClearances(), BOARD::CombineAreas(), MODULE::CoverageRatio(), BOARD_ADAPTER::createLayers(), BITMAPCONV_INFO::createOutputData(), Fracture(), BOARD::GetBoardPolygonOutlines(), InflateWithLinkedHoles(), NormalizeAreaOutlines(), ALTIUM_PCB::ParseArcs6Data(), PlotLayerOutlines(), PlotSolderMaskLayer(), D_PAD::TransformShapeWithClearanceToPolygon(), ZONE_CONTAINER::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) 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.
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 1624 of file shape_poly_set.cpp.

1625 {
1626  SEG::ecoord currentDistance;
1627  SEG::ecoord minDistance = SquaredDistanceToPolygon( aPoint, 0 );
1628 
1629  // Iterate through all the polygons and get the minimum distance.
1630  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1631  {
1632  currentDistance = SquaredDistanceToPolygon( aPoint, polygonIdx );
1633 
1634  if( currentDistance < minDistance )
1635  minDistance = currentDistance;
1636  }
1637 
1638  return minDistance;
1639 }
VECTOR2I::extended_type ecoord
Definition: seg.h:42
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex) const
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.

References m_polys, and SquaredDistanceToPolygon().

Referenced by BOOST_AUTO_TEST_CASE(), and Collide().

◆ SquaredDistance() [2/2]

SEG::ecoord SHAPE_POLY_SET::SquaredDistance ( const SEG aSegment) 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.
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 1642 of file shape_poly_set.cpp.

1643 {
1644  SEG::ecoord currentDistance;
1645  SEG::ecoord minDistance = SquaredDistanceToPolygon( aSegment, 0 );
1646 
1647  // Iterate through all the polygons and get the minimum distance.
1648  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1649  {
1650  currentDistance = SquaredDistanceToPolygon( aSegment, polygonIdx );
1651 
1652  if( currentDistance < minDistance )
1653  minDistance = currentDistance;
1654  }
1655 
1656  return minDistance;
1657 }
VECTOR2I::extended_type ecoord
Definition: seg.h:42
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex) const
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.

References m_polys, and SquaredDistanceToPolygon().

◆ SquaredDistanceToPolygon() [1/2]

SEG::ecoord SHAPE_POLY_SET::SquaredDistanceToPolygon ( VECTOR2I  aPoint,
int  aIndex 
) 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.
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 1574 of file shape_poly_set.cpp.

1575 {
1576  // We calculate the min dist between the segment and each outline segment. However, if the
1577  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1578  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1579  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1580  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1581  return 0;
1582 
1583  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1584 
1585  SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1586 
1587  for( iterator++; iterator && minDistance > 0; iterator++ )
1588  {
1589  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1590 
1591  if( currentDistance < minDistance )
1592  minDistance = currentDistance;
1593  }
1594 
1595  return minDistance;
1596 }
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 
) 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.
aSegmentWidthis the width of the segment; defaults to zero.
Returns
int - The minimum distance between aSegment and all the segments of the aIndex-th polygon. If the point is contained in the polygon, the distance is zero.

Definition at line 1599 of file shape_poly_set.cpp.

1600 {
1601  // We calculate the min dist between the segment and each outline segment. However, if the
1602  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1603  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1604  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1605  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) )
1606  return 0;
1607 
1608  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1609  SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1610 
1611  for( iterator++; iterator && minDistance > 0; iterator++ )
1612  {
1613  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
1614 
1615  if( currentDistance < minDistance )
1616  minDistance = currentDistance;
1617  }
1618 
1619  // Return the maximum of minDistance and zero
1620  return minDistance < 0 ? 0 : minDistance;
1621 }
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...

References SEG::A, 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 284 of file shape_poly_set.cpp.

285 {
286  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
287 
288  SHAPE_POLY_SET newPolySet;
289 
290  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
291  {
292  newPolySet.m_polys.push_back( Polygon( index ) );
293  }
294 
295  return newPolySet;
296 }
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 1547 of file shape_poly_set.cpp.

1548 {
1549  int c = 0;
1550 
1551  for( const POLYGON& poly : m_polys )
1552  {
1553  for( const SHAPE_LINE_CHAIN& path : poly )
1554  c += path.PointCount();
1555  }
1556 
1557  return c;
1558 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
SHAPE_LINE_CHAIN.

References m_polys.

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

◆ TriangulatedPolyCount()

unsigned int SHAPE_POLY_SET::TriangulatedPolyCount ( ) const
inline

Returns the number of triangulated polygons

Definition at line 624 of file shape_poly_set.h.

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

References m_triangulatedPolys.

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

◆ TriangulatedPolygon()

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

Definition at line 682 of file shape_poly_set.h.

683  {
684  return m_triangulatedPolys[aIndex].get();
685  }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys

References m_triangulatedPolys.

Referenced by Convert_shape_line_polygon_to_triangles(), 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 96 of file shape.h.

97  {
98  return m_type;
99  }
SHAPE_TYPE m_type
type of our shape
Definition: shape.h:108

References SHAPE_BASE::m_type.

Referenced by PNS::DP_GATEWAYS::BuildFromPrimitivePair(), collideShapes(), collideSingleShapes(), PNS::OPTIMIZER::computeBreakouts(), ROUTER_PREVIEW_ITEM::ViewDraw(), and SHAPE_FILE_IO::Write().

◆ Unfracture()

void SHAPE_POLY_SET::Unfracture ( POLYGON_MODE  aFastMode)

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

Definition at line 1041 of file shape_poly_set.cpp.

1042 {
1043  for( POLYGON& path : m_polys )
1044  {
1045  unfractureSingle( path );
1046  }
1047 
1048  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1049 }
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 PlotStandardLayer(), and polygon_triangulation_main().

◆ unfractureSingle()

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

Definition at line 865 of file shape_poly_set.cpp.

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

661  {
662  return Subset( aPolygonIndex, aPolygonIndex + 1 );
663  }
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 259 of file shape_poly_set.cpp.

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

References m_polys.

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

Member Data Documentation

◆ m_hash

MD5_HASH SHAPE_POLY_SET::m_hash
private

◆ m_polys

◆ m_triangulatedPolys

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

◆ m_triangulationValid

bool SHAPE_POLY_SET::m_triangulationValid = false
private

◆ m_type

SHAPE_TYPE SHAPE_BASE::m_type
protectedinherited

type of our shape

Definition at line 108 of file shape.h.

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


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