KiCad PCB EDA Suite
SHAPE_POLY_SET Class Reference

Class SHAPE_POLY_SET. More...

#include <shape_poly_set.h>

Inheritance diagram for SHAPE_POLY_SET:
SHAPE

Classes

class  ITERATOR_TEMPLATE
 Class ITERATOR_TEMPLATE. More...
 
class  SEGMENT_ITERATOR_TEMPLATE
 Class 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...
 
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_POLY_SET &aOther, bool aDeepCopy=false)
 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...
 
VECTOR2IVertex (int aIndex, int aOutline, int aHole)
 

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

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...
 
VECTOR2IVertex (int aGlobalIndex)
 

Returns the aGlobalIndex-th vertex in the poly set

More...
 
const VECTOR2ICVertex (int aGlobalIndex) const
 

Returns the aGlobalIndex-th vertex in the poly set

More...
 
VECTOR2IVertex (VERTEX_INDEX aIndex)
 

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

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)
 Function IsPolygonSelfIntersecting. More...
 
bool IsSelfIntersecting ()
 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...

 
SEGMENT_ITERATOR IterateSegments (int aPolygonIdx)
 

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...
 
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 aFactor, int aCircleSegmentsCount)
 

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 Rotate (double aAngle, const VECTOR2I &aCenter)
 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) const override
 Function Collide Checks whether the point aP collides with the inside of the polygon set; if the point lies on an edge or on a corner of any of the polygons, there is no collision: the edges does not belong to the polygon itself. More...
 
bool Collide (const SEG &aSeg, int aClearance=0) const override
 Function Collide Checks whether the segment aSeg collides with the inside of the polygon set; if the segment touches an edge or a corner of any of the polygons, there is no collision: the edges do not belong to the polygon itself. More...
 
bool CollideVertex (const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
 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)
 Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polygon. More...
 
bool Contains (const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=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...
 
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=0)
 Function Chamfer returns a chamfered version of the aIndex-th polygon. More...
 
POLYGON FilletPolygon (unsigned int aRadius, int aErrorMax, int aIndex=0)
 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...
 
int DistanceToPolygon (VECTOR2I aPoint, int aIndex)
 Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint. More...
 
int DistanceToPolygon (SEG aSegment, int aIndex, int aSegmentWidth=0)
 Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aSegment with a possible width. More...
 
int Distance (VECTOR2I aPoint)
 Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the set. More...
 
int Distance (const SEG &aSegment, int aSegmentWidth=0)
 Function DistanceToPolygon computes the minimum distance 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 IsTriangulationUpToDate () const
 
MD5_HASH GetHash () const
 
SHAPE_TYPE Type () const
 Function Type() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance, VECTOR2I &aMTV) const
 Function Collide() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance=0) const
 
virtual VECTOR2I Centre () const
 Function Centre() More...
 

Protected Types

typedef VECTOR2I::extended_type ecoord
 

Protected Attributes

SHAPE_TYPE m_type
 

type of our shape

More...
 

Private Types

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

Private Member Functions

SHAPE_LINE_CHAINgetContourForCorner (int aCornerId, int &aIndexWithinContour)
 
VECTOR2Ivertex (int aCornerId)
 
const VECTOR2Icvertex (int aCornerId) const
 
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 pointInPolygon (const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath) const
 
bool containsSingle (const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=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=-1)
 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

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

Member Typedef Documentation

typedef VECTOR2I::extended_type SHAPE::ecoord
protectedinherited

Definition at line 61 of file shape.h.

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

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

Definition at line 1171 of file shape_poly_set.h.

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

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

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

Constructor & Destructor Documentation

SHAPE_POLY_SET::SHAPE_POLY_SET ( )

Definition at line 49 of file shape_poly_set.cpp.

Referenced by Clone(), and Collide().

49  :
51 {
52 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:70
simple polygon
Definition: shape.h:48
SHAPE_POLY_SET::SHAPE_POLY_SET ( const SHAPE_POLY_SET aOther,
bool  aDeepCopy = false 
)

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

Parameters
aOtheris the SHAPE_POLY_SET object that will be copied.
aDeepCopyif true, make new copies of the triangulated unique_ptr vector

Definition at line 55 of file shape_poly_set.cpp.

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

55  :
56  SHAPE( SH_POLY_SET ), m_polys( aOther.m_polys )
57 {
58  if( aOther.IsTriangulationUpToDate() )
59  {
60  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
61  m_triangulatedPolys.push_back(
62  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
63 
64  m_hash = aOther.GetHash();
65  m_triangulationValid = true;
66  }
67 }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:70
MD5_HASH GetHash() const
bool IsTriangulationUpToDate() const
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
simple polygon
Definition: shape.h:48
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
size_t i
Definition: json11.cpp:597
SHAPE_POLY_SET::~SHAPE_POLY_SET ( )

Definition at line 70 of file shape_poly_set.cpp.

71 {
72 }

Member Function Documentation

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

References m_polys.

Referenced by ZONE_CONTAINER::AddPolygon(), and PCB_EDIT_FRAME::End_Zone().

451 {
452  assert( m_polys.size() );
453 
454  if( aOutline < 0 )
455  aOutline += m_polys.size();
456 
457  POLYGON& poly = m_polys[aOutline];
458 
459  assert( poly.size() );
460 
461  poly.push_back( aHole );
462 
463  return poly.size() - 1;
464 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
int SHAPE_POLY_SET::AddOutline ( const SHAPE_LINE_CHAIN aOutline)

Adds a new outline to the set and returns its index

Definition at line 436 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::IsClosed(), and m_polys.

Referenced by ZONE_CONTAINER::AddPolygon(), CINFO3D_VISU::buildPadShapePolygon(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), D_PAD::MergePrimitivesAsPolygon(), CPolyLine::NormalizeAreaOutlines(), NormalizeAreaOutlines(), and ZONE_CREATE_HELPER::performZoneCutout().

437 {
438  assert( aOutline.IsClosed() );
439 
440  POLYGON poly;
441 
442  poly.push_back( aOutline );
443 
444  m_polys.push_back( poly );
445 
446  return m_polys.size() - 1;
447 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
bool IsClosed() const
Function IsClosed()
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 193 of file shape_poly_set.cpp.

References m_polys.

Referenced by addHoleToPolygon(), D_PAD::AddPrimitive(), addRect(), Append(), ZONE_CONTAINER::AppendCorner(), BuildBoardPolygonOutlines(), D_PAD::buildCustomPadPolygon(), CINFO3D_VISU::buildPadShapePolygon(), D_PAD::BuildPadShapePolygon(), ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), ZONE_FILLER::buildZoneFeatureHoleList(), DRC::checkClearancePadToPad(), DRC::checkClearanceSegmToPad(), ConvertOutlineToPolygon(), ConvertPolyListToPolySet(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CINFO3D_VISU::createNewPadWithClearance(), CreateThermalReliefPadPolygon(), DRC::doFootprintOverlappingDrc(), KIGFX::PCB_PAINTER::draw(), D_PAD::DrawShape(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), fillArcPOLY(), MODULE::GetBoundingPoly(), getRectangleAlongCentreLine(), InsertVertex(), LEGACY_PLUGIN::loadZONE_CONTAINER(), ZONE_CONTAINER::operator=(), PCB_PARSER::parseZONE_CONTAINER(), DXF_PLOTTER::PlotPoly(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), DRAWSEGMENT::SetPolyPoints(), PNS_KICAD_IFACE::syncPad(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon(), TransformOvalClearanceToPolygon(), TransformRingToPolygon(), TransformRoundedEndsSegmentToPolygon(), TransformRoundRectToPolygon(), DRAWSEGMENT::TransformShapeWithClearanceToPolygon(), D_PAD::TransformShapeWithClearanceToPolygon(), ZONE_CONTAINER::TransformSolidAreasShapesToPolygonSet(), and ZONE_CONTAINER::ZONE_CONTAINER().

194 {
195  if( aOutline < 0 )
196  aOutline += m_polys.size();
197 
198  int idx;
199 
200  if( aHole < 0 )
201  idx = 0;
202  else
203  idx = aHole + 1;
204 
205  assert( aOutline < (int) m_polys.size() );
206  assert( idx < (int) m_polys[aOutline].size() );
207 
208  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
209 
210  return m_polys[aOutline][idx].PointCount();
211 }
void SHAPE_POLY_SET::Append ( const SHAPE_POLY_SET aSet)

Merges polygons from two sets.

Definition at line 1308 of file shape_poly_set.cpp.

References m_polys.

1309 {
1310  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1311 }
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 1314 of file shape_poly_set.cpp.

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

1315 {
1316  Append( aP.x, aP.y, aOutline, aHole );
1317 }
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) ...
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 1152 of file shape_poly_set.cpp.

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

Referenced by ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), BOARD::CombineAllAreasInNet(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), D_PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::GetBoundingBox(), IsSolid(), BOARD::TestAreaIntersection(), KIGFX::PREVIEW::POLYGON_ITEM::ViewBBox(), and KIGFX::PREVIEW::CENTRELINE_RECT_ITEM::ViewBBox().

1153 {
1154  BOX2I bb;
1155 
1156  for( unsigned i = 0; i < m_polys.size(); i++ )
1157  {
1158  if( i == 0 )
1159  bb = m_polys[i][0].BBox();
1160  else
1161  bb.Merge( m_polys[i][0].BBox() );
1162  }
1163 
1164  bb.Inflate( aClearance );
1165  return bb;
1166 }
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:384
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:300
size_t i
Definition: json11.cpp:597
const BOX2I BBox(int aClearance=0) const override
Function BBox()
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 503 of file shape_poly_set.cpp.

References booleanOp().

Referenced by D_PAD::buildCustomPadPolygon(), BOARD::CombineAreas(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), and C3D_RENDER_OGL_LEGACY::reload().

504 {
505  booleanOp( ctUnion, 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, OR, ...
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 521 of file shape_poly_set.cpp.

References booleanOp().

524 {
525  booleanOp( ctUnion, a, b, aFastMode );
526 }
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, ...
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 515 of file shape_poly_set.cpp.

References booleanOp().

Referenced by Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), DRC::doFootprintOverlappingDrc(), and TransformOvalClearanceToPolygon().

516 {
517  booleanOp( ctIntersection, b, aFastMode );
518 }
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, ...
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 537 of file shape_poly_set.cpp.

References booleanOp().

540 {
541  booleanOp( ctIntersection, a, b, aFastMode );
542 }
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, ...
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 467 of file shape_poly_set.cpp.

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

469 {
470  booleanOp( aType, *this, aOtherShape, aFastMode );
471 }
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, ...
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 474 of file shape_poly_set.cpp.

References i, importTree(), m_polys, and PM_STRICTLY_SIMPLE.

478 {
479  Clipper c;
480 
481  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
482 
483  for( auto poly : aShape.m_polys )
484  {
485  for( size_t i = 0 ; i < poly.size(); i++ )
486  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
487  }
488 
489  for( auto poly : aOtherShape.m_polys )
490  {
491  for( size_t i = 0; i < poly.size(); i++ )
492  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
493  }
494 
495  PolyTree solution;
496 
497  c.Execute( aType, solution, pftNonZero, pftNonZero );
498 
499  importTree( &solution );
500 }
size_t i
Definition: json11.cpp:597
void importTree(ClipperLib::PolyTree *tree)
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 509 of file shape_poly_set.cpp.

References booleanOp().

Referenced by addHoleToPolygon(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), CreateThermalReliefPadPolygon(), C3D_RENDER_OGL_LEGACY::generate_3D_Vias_and_Pads(), CPolyLine::NormalizeAreaOutlines(), NormalizeAreaOutlines(), and ZONE_CREATE_HELPER::performZoneCutout().

510 {
511  booleanOp( ctDifference, b, aFastMode );
512 }
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, ...
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 529 of file shape_poly_set.cpp.

References booleanOp().

532 {
533  booleanOp( ctDifference, a, b, aFastMode );
534 }
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, ...
void SHAPE_POLY_SET::CacheTriangulation ( )

Definition at line 1842 of file shape_poly_set.cpp.

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

Referenced by ZONE_CONTAINER::CacheTriangulation(), Convert_shape_line_polygon_to_triangles(), and PNS_KICAD_IFACE::syncZone().

1843 {
1844  bool recalculate = !m_hash.IsValid();
1845  MD5_HASH hash;
1846 
1847  if( !m_triangulationValid )
1848  recalculate = true;
1849 
1850  if( !recalculate )
1851  {
1852  hash = checksum();
1853 
1854  if( m_hash != hash )
1855  {
1856  m_hash = hash;
1857  recalculate = true;
1858  }
1859  }
1860 
1861  if( !recalculate )
1862  return;
1863 
1864  SHAPE_POLY_SET tmpSet = *this;
1865 
1866  if( tmpSet.HasHoles() )
1867  tmpSet.Fracture( PM_FAST );
1868 
1869  m_triangulatedPolys.clear();
1870 
1871  for( int i = 0; i < tmpSet.OutlineCount(); i++ )
1872  {
1873  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
1874  PolygonTriangulation tess( *m_triangulatedPolys.back() );
1875 
1876  tess.TesselatePolygon( tmpSet.Polygon( i ).front() );
1877  }
1878 
1879  m_triangulationValid = true;
1880  m_hash = checksum();
1881 }
bool HasHoles() const
Returns true if the polygon set has any holes.
MD5_HASH checksum() const
void TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly)
int OutlineCount() const
Returns the number of outlines in the set
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
Class 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...
bool IsValid() const
Definition: md5_hash.h:23
size_t i
Definition: json11.cpp:597
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
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 151 of file shape.h.

References SHAPE::BBox(), BOX2< Vec >::Centre(), SHAPE::Format(), SHAPE::IsSolid(), SHAPE::Move(), and SHAPE::Parse().

152  {
153  return BBox( 0 ).Centre(); // if nothing better is available....
154  }
virtual const BOX2I BBox(int aClearance=0) const =0
Function BBox()
Vec Centre() const
Definition: box2.h:77
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 1622 of file shape_poly_set.cpp.

References ChamferPolygon(), and m_polys.

Referenced by ZONE_CONTAINER::BuildSmoothedPoly(), and IsEmpty().

1623 {
1624  SHAPE_POLY_SET chamfered;
1625 
1626  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1627  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1628 
1629  return chamfered;
1630 }
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
Class SHAPE_POLY_SET.
SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::chamferFilletPolygon ( CORNER_MODE  aMode,
unsigned int  aDistance,
int  aIndex,
int  aErrorMax = -1 
)
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 1644 of file shape_poly_set.cpp.

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

Referenced by ChamferPolygon(), and FilletPolygon().

1648 {
1649  // Null segments create serious issues in calculations. Remove them:
1651 
1652  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1653  SHAPE_POLY_SET::POLYGON newPoly;
1654 
1655  // If the chamfering distance is zero, then the polygon remain intact.
1656  if( aDistance == 0 )
1657  {
1658  return currentPoly;
1659  }
1660 
1661  // Iterate through all the contours (outline and holes) of the polygon.
1662  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1663  {
1664  // Generate a new contour in the new polygon
1665  SHAPE_LINE_CHAIN newContour;
1666 
1667  // Iterate through the vertices of the contour
1668  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1669  {
1670  // Current vertex
1671  int x1 = currContour.Point( currVertex ).x;
1672  int y1 = currContour.Point( currVertex ).y;
1673 
1674  // Indices for previous and next vertices.
1675  int prevVertex;
1676  int nextVertex;
1677 
1678  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1679 
1680  // Previous vertex is the last one if the current vertex is the first one
1681  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1682 
1683  // next vertex is the first one if the current vertex is the last one.
1684  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1685 
1686  // Previous vertex computation
1687  double xa = currContour.Point( prevVertex ).x - x1;
1688  double ya = currContour.Point( prevVertex ).y - y1;
1689 
1690  // Next vertex computation
1691  double xb = currContour.Point( nextVertex ).x - x1;
1692  double yb = currContour.Point( nextVertex ).y - y1;
1693 
1694  // Compute the new distances
1695  double lena = hypot( xa, ya );
1696  double lenb = hypot( xb, yb );
1697 
1698  // Make the final computations depending on the mode selected, chamfered or filleted.
1699  if( aMode == CORNER_MODE::CHAMFERED )
1700  {
1701  double distance = aDistance;
1702 
1703  // Chamfer one half of an edge at most
1704  if( 0.5 * lena < distance )
1705  distance = 0.5 * lena;
1706 
1707  if( 0.5 * lenb < distance )
1708  distance = 0.5 * lenb;
1709 
1710  int nx1 = KiROUND( distance * xa / lena );
1711  int ny1 = KiROUND( distance * ya / lena );
1712 
1713  newContour.Append( x1 + nx1, y1 + ny1 );
1714 
1715  int nx2 = KiROUND( distance * xb / lenb );
1716  int ny2 = KiROUND( distance * yb / lenb );
1717 
1718  newContour.Append( x1 + nx2, y1 + ny2 );
1719  }
1720  else // CORNER_MODE = FILLETED
1721  {
1722  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1723 
1724  double radius = aDistance;
1725  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1726 
1727  // Do nothing in case of parallel edges
1728  if( std::isinf( denom ) )
1729  continue;
1730 
1731  // Limit rounding distance to one half of an edge
1732  if( 0.5 * lena * denom < radius )
1733  radius = 0.5 * lena * denom;
1734 
1735  if( 0.5 * lenb * denom < radius )
1736  radius = 0.5 * lenb * denom;
1737 
1738  // Calculate fillet arc absolute center point (xc, yx)
1739  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1740  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1741  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1742  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1743  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1744 
1745  // Calculate arc start and end vectors
1746  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1747  double xs = x1 + k * xa / lena - xc;
1748  double ys = y1 + k * ya / lena - yc;
1749  double xe = x1 + k * xb / lenb - xc;
1750  double ye = y1 + k * yb / lenb - yc;
1751 
1752  // Cosine of arc angle
1753  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1754 
1755  // Make sure the argument is in [-1,1], interval in which the acos function is
1756  // defined
1757  if( argument < -1 )
1758  argument = -1;
1759  else if( argument > 1 )
1760  argument = 1;
1761 
1762  double arcAngle = acos( argument );
1763  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1764  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1765 
1766  double deltaAngle = arcAngle / segments;
1767  double startAngle = atan2( -ys, xs );
1768 
1769  // Flip arc for inner corners
1770  if( xa * yb - ya * xb <= 0 )
1771  deltaAngle *= -1;
1772 
1773  double nx = xc + xs;
1774  double ny = yc + ys;
1775 
1776  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1777 
1778  // Store the previous added corner to make a sanity check
1779  int prevX = KiROUND( nx );
1780  int prevY = KiROUND( ny );
1781 
1782  for( int j = 0; j < segments; j++ )
1783  {
1784  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1785  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1786 
1787  // Sanity check: the rounding can produce repeated corners; do not add them.
1788  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1789  {
1790  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1791  prevX = KiROUND( nx );
1792  prevY = KiROUND( ny );
1793  }
1794  }
1795  }
1796  }
1797 
1798  // Close the current contour and add it the new polygon
1799  newContour.SetClosed( true );
1800  newPoly.push_back( newContour );
1801  }
1802 
1803  return newPoly;
1804 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
static int KiROUND(double v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: common.h:120
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
Class SHAPE_LINE_CHAIN.
VECTOR2I & Point(int aIndex)
Function Point()
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon ( unsigned int  aDistance,
int  aIndex = 0 
)

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

References chamferFilletPolygon().

Referenced by Chamfer(), and IsEmpty().

1499 {
1500  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1501 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
MD5_HASH SHAPE_POLY_SET::checksum ( ) const
private

Definition at line 1884 of file shape_poly_set.cpp.

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

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

1885 {
1886  MD5_HASH hash;
1887 
1888  hash.Hash( m_polys.size() );
1889 
1890  for( const auto& outline : m_polys )
1891  {
1892  hash.Hash( outline.size() );
1893 
1894  for( const auto& lc : outline )
1895  {
1896  hash.Hash( lc.PointCount() );
1897 
1898  for( int i = 0; i < lc.PointCount(); i++ )
1899  {
1900  hash.Hash( lc.CPoint( i ).x );
1901  hash.Hash( lc.CPoint( i ).y );
1902  }
1903  }
1904  }
1905 
1906  hash.Finalize();
1907 
1908  return hash;
1909 }
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66
size_t i
Definition: json11.cpp:597
void Finalize()
Definition: md5_hash.cpp:76
const SHAPE_LINE_CHAIN& SHAPE_POLY_SET::CHole ( int  aOutline,
int  aHole 
) const
inline

Definition at line 621 of file shape_poly_set.h.

References m_polys.

Referenced by CINFO3D_VISU::AddSolidAreasShapesToContainer(), CLAYER_TRIANGLES::AddToMiddleContourns(), containsSingle(), KIGFX::PCB_PAINTER::draw(), and PlotLayerOutlines().

622  {
623  return m_polys[aOutline][aHole + 1];
624  }
CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aFirst,
int  aLast,
bool  aIterateHoles = false 
) const
inline

Definition at line 698 of file shape_poly_set.h.

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::AddPrimitive(), DRAWSEGMENT::BuildPolyPointsList(), EDGE_MODULE::Draw(), PCB_IO::format(), DRAWSEGMENT::GetBoundingBox(), BRDITEMS_PLOTTER::PlotFilledAreas(), and PNS_KICAD_IFACE::syncPad().

699  {
700  CONST_ITERATOR iter;
701 
702  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
703  iter.m_currentPolygon = aFirst;
704  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
705  iter.m_currentContour = 0;
706  iter.m_currentVertex = 0;
707  iter.m_iterateHoles = aIterateHoles;
708 
709  return iter;
710  }
int OutlineCount() const
Returns the number of outlines in the set
Class SHAPE_POLY_SET.
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
CONST_ITERATOR SHAPE_POLY_SET::CIterate ( int  aOutline) const
inline

Definition at line 712 of file shape_poly_set.h.

References CIterate().

713  {
714  return CIterate( aOutline, aOutline );
715  }
CONST_ITERATOR CIterate() const
CONST_ITERATOR SHAPE_POLY_SET::CIterate ( ) const
inline

Definition at line 722 of file shape_poly_set.h.

References OutlineCount().

Referenced by CIterate(), and CIterateWithHoles().

723  {
724  return CIterate( 0, OutlineCount() - 1 );
725  }
CONST_ITERATOR CIterate() const
int OutlineCount() const
Returns the number of outlines in the set
CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( int  aOutline) const
inline

Definition at line 717 of file shape_poly_set.h.

References CIterate().

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

718  {
719  return CIterate( aOutline, aOutline, true );
720  }
CONST_ITERATOR CIterate() const
CONST_ITERATOR SHAPE_POLY_SET::CIterateWithHoles ( ) const
inline

Definition at line 727 of file shape_poly_set.h.

References CIterate(), and OutlineCount().

728  {
729  return CIterate( 0, OutlineCount() - 1, true );
730  }
CONST_ITERATOR CIterate() const
int OutlineCount() const
Returns the number of outlines in the set
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 75 of file shape_poly_set.cpp.

References SHAPE_POLY_SET().

76 {
77  return new SHAPE_POLY_SET( *this );
78 }
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
Returns
true, if there is a collision.

Definition at line 545 of file shape_collisions.cpp.

References CollideShapes().

546 {
547  return CollideShapes( this, aShape, aClearance, true, aMTV );
548 }
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)
bool SHAPE::Collide ( const SHAPE aShape,
int  aClearance = 0 
) const
virtualinherited

Definition at line 551 of file shape_collisions.cpp.

References CollideShapes(), and dummy().

552 {
553  VECTOR2I dummy;
554 
555  return CollideShapes( this, aShape, aClearance, false, dummy );
556 }
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
static LIB_PART * dummy()
Used when a LIB_PART is not found in library to draw a dummy shape This component is a 400 mils squar...
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)
bool SHAPE_POLY_SET::Collide ( const VECTOR2I aP,
int  aClearance = 0 
) const
overridevirtual

Function Collide Checks whether the point aP collides with the inside of the polygon set; if the point lies on an edge or on a corner of any of the polygons, there is no collision: the edges does not belong to the polygon itself.

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

Reimplemented from SHAPE.

Definition at line 1217 of file shape_poly_set.cpp.

References Contains(), Inflate(), and SHAPE_POLY_SET().

Referenced by IsSolid().

1218 {
1219  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1220 
1221  // Inflate the polygon if necessary.
1222  if( aClearance > 0 )
1223  {
1224  // fixme: the number of arc segments should not be hardcoded
1225  polySet.Inflate( aClearance, 8 );
1226  }
1227 
1228  // There is a collision if and only if the point is inside of the polygon.
1229  return polySet.Contains( aP );
1230 }
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
Class SHAPE_POLY_SET.
bool SHAPE_POLY_SET::Collide ( const SEG aSeg,
int  aClearance = 0 
) const
overridevirtual

Function Collide Checks whether the segment aSeg collides with the inside of the polygon set; if the segment touches an edge or a corner of any of the polygons, there is no collision: the edges do not belong to the polygon itself.

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

Implements SHAPE.

Definition at line 1186 of file shape_poly_set.cpp.

References SEG::A, Contains(), Inflate(), SEG::Intersect(), IterateSegmentsWithHoles(), and SHAPE_POLY_SET().

1187 {
1188 
1189  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1190 
1191  // Inflate the polygon if necessary.
1192  if( aClearance > 0 )
1193  {
1194  // fixme: the number of arc segments should not be hardcoded
1195  polySet.Inflate( aClearance, 8 );
1196  }
1197 
1198  // We are going to check to see if the segment crosses an external
1199  // boundary. However, if the full segment is inside the polyset, this
1200  // will not be true. So we first test to see if one of the points is
1201  // inside. If true, then we collide
1202  if( polySet.Contains( aSeg.A ) )
1203  return true;
1204 
1205  for( SEGMENT_ITERATOR iterator = polySet.IterateSegmentsWithHoles(); iterator; iterator++ )
1206  {
1207  SEG polygonEdge = *iterator;
1208 
1209  if( polygonEdge.Intersect( aSeg, true ) )
1210  return true;
1211  }
1212 
1213  return false;
1214 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
Class SHAPE_POLY_SET.
Definition: seg.h:36
VECTOR2I A
Definition: seg.h:46
bool SHAPE_POLY_SET::CollideEdge ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex,
int  aClearance = 0 
)

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

References SEG::Distance(), SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE< T >::GetIndex(), and IterateSegmentsWithHoles().

Referenced by ZONE_CONTAINER::HitTestForEdge(), and IsSolid().

1360 {
1361  // Shows whether there was a collision
1362  bool collision = false;
1363 
1364  SEGMENT_ITERATOR iterator;
1365 
1366  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1367  {
1368  SEG currentSegment = *iterator;
1369  int distance = currentSegment.Distance( aPoint );
1370 
1371  // Check for collisions
1372  if( distance <= aClearance )
1373  {
1374  collision = true;
1375 
1376  // Update aClearance to look for closer edges
1377  aClearance = distance;
1378 
1379  // Store the indices that identify the vertex
1380  aClosestVertex = iterator.GetIndex();
1381  }
1382  }
1383 
1384  return collision;
1385 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
Definition: seg.h:36
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
bool SHAPE_POLY_SET::CollideVertex ( const VECTOR2I aPoint,
SHAPE_POLY_SET::VERTEX_INDEX aClosestVertex,
int  aClearance = 0 
)

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

References delta, VECTOR2< T >::EuclideanNorm(), and IterateWithHoles().

Referenced by ZONE_CONTAINER::HitTestForCorner(), and IsSolid().

1322 {
1323  // Shows whether there was a collision
1324  bool collision = false;
1325 
1326  // Difference vector between each vertex and aPoint.
1327  VECTOR2D delta;
1328  double distance, clearance;
1329 
1330  // Convert clearance to double for precission when comparing distances
1331  clearance = aClearance;
1332 
1333  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1334  {
1335  // Get the difference vector between current vertex and aPoint
1336  delta = *iterator - aPoint;
1337 
1338  // Compute distance
1339  distance = delta.EuclideanNorm();
1340 
1341  // Check for collisions
1342  if( distance <= clearance )
1343  {
1344  collision = true;
1345 
1346  // Update aClearance to look for closer vertices
1347  clearance = distance;
1348 
1349  // Store the indices that identify the vertex
1350  aClosestVertex = iterator.GetIndex();
1351  }
1352  }
1353 
1354  return collision;
1355 }
static const int delta[8][2]
Definition: solve.cpp:112
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:292
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
ITERATOR IterateWithHoles()
Function IterateWithHoles.
bool SHAPE_POLY_SET::Contains ( const VECTOR2I aP,
int  aSubpolyIndex = -1,
bool  aIgnoreHoles = 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
aIgnoreHolescontrols whether or not internal holes are considered
Returns
true if the polygon contains the point

Definition at line 1388 of file shape_poly_set.cpp.

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

Referenced by ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), Collide(), DRC::doEdgeZoneDrc(), D_PAD::GetBestAnchorPosition(), GERBER_DRAW_ITEM::HitTest(), ZONE_CONTAINER::HitTestFilledArea(), ZONE_CONTAINER::HitTestInsideZone(), IsSolid(), BOARD::TestAreaIntersection(), and DRC::TestZoneToZoneOutline().

1389 {
1390  if( m_polys.size() == 0 ) // empty set?
1391  return false;
1392 
1393  // If there is a polygon specified, check the condition against that polygon
1394  if( aSubpolyIndex >= 0 )
1395  return containsSingle( aP, aSubpolyIndex, aIgnoreHoles );
1396 
1397  // In any other case, check it against all polygons in the set
1398  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1399  {
1400  if( containsSingle( aP, polygonIdx, aIgnoreHoles ) )
1401  return true;
1402  }
1403 
1404  return false;
1405 }
int OutlineCount() const
Returns the number of outlines in the set
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
bool SHAPE_POLY_SET::containsSingle ( const VECTOR2I aP,
int  aSubpolyIndex,
bool  aIgnoreHoles = 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.
aIgnoreHolescan be set to true to ignore internal holes in the polygon
Returns
bool - true if aP is inside aSubpolyIndex-th polygon; false in any other case.

Definition at line 1426 of file shape_poly_set.cpp.

References CHole(), HoleCount(), m_polys, pointInPolygon(), and SHAPE_LINE_CHAIN::PointOnEdge().

Referenced by Contains(), DistanceToPolygon(), and IsEmpty().

1427 {
1428  // Check that the point is inside the outline
1429  if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
1430  {
1431  if( !aIgnoreHoles )
1432  {
1433  // Check that the point is not in any of the holes
1434  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1435  {
1436  const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
1437 
1438  // If the point is inside a hole (and not on its edge),
1439  // it is outside of the polygon
1440  if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
1441  return false;
1442  }
1443  }
1444 
1445  return true;
1446  }
1447 
1448  return false;
1449 }
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool pointInPolygon(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath) const
Class SHAPE_LINE_CHAIN.
const POLYGON& SHAPE_POLY_SET::CPolygon ( int  aIndex) const
inline
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 295 of file shape_poly_set.cpp.

References m_polys.

Referenced by CVertex(), ZONE_CONTAINER::GetCornerPosition(), DRAWSEGMENT::GetPosition(), DRAWSEGMENT::HitTest(), and POINT_EDITOR::updatePoints().

296 {
297  if( aOutline < 0 )
298  aOutline += m_polys.size();
299 
300  int idx;
301 
302  if( aHole < 0 )
303  idx = 0;
304  else
305  idx = aHole + 1;
306 
307  assert( aOutline < (int) m_polys.size() );
308  assert( idx < (int) m_polys[aOutline].size() );
309 
310  return m_polys[aOutline][idx].CPoint( aIndex );
311 }
const VECTOR2I & SHAPE_POLY_SET::CVertex ( int  aGlobalIndex) const

Returns the aGlobalIndex-th vertex in the poly set

Definition at line 326 of file shape_poly_set.cpp.

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.

327 {
329 
330  // Assure the passed index references a legal position; abort otherwise
331  if( !GetRelativeIndices( aGlobalIndex, &index ) )
332  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
333 
334  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
335 }
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
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 344 of file shape_poly_set.cpp.

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

345 {
346  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
347 }
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
const VECTOR2I& SHAPE_POLY_SET::cvertex ( int  aCornerId) const
private

Referenced by IsEmpty().

void SHAPE_POLY_SET::DeletePolygon ( int  aIdx)

Deletes aIdx-th polygon from the set

Definition at line 1302 of file shape_poly_set.cpp.

References m_polys.

Referenced by ZONE_FILLER::Fill(), and IsEmpty().

1303 {
1304  m_polys.erase( m_polys.begin() + aIdx );
1305 }
int SHAPE_POLY_SET::Distance ( VECTOR2I  aPoint)

Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the set.

Parameters
aPointis the point whose distance to the set has to be measured.
Returns
int - The minimum distance 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 1573 of file shape_poly_set.cpp.

References DistanceToPolygon(), and m_polys.

Referenced by DRC::doTrackDrc(), DRC::doTrackKeepoutDrc(), IsEmpty(), DRC::newMarker(), DRC::testCopperDrawItem(), DRC::testCopperTextItem(), and DRC::testKeepoutAreas().

1574 {
1575  int currentDistance;
1576  int minDistance = DistanceToPolygon( aPoint, 0 );
1577 
1578  // Iterate through all the polygons and get the minimum distance.
1579  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1580  {
1581  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1582 
1583  if( currentDistance < minDistance )
1584  minDistance = currentDistance;
1585  }
1586 
1587  return minDistance;
1588 }
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint...
int SHAPE_POLY_SET::Distance ( const SEG aSegment,
int  aSegmentWidth = 0 
)

Function DistanceToPolygon computes the minimum distance between aSegment and all the polygons in the set.

Parameters
aSegmentis the segment whose distance to the polygon set has to be measured.
aSegmentWidthis the width of the segment; defaults to zero.
Returns
int - The minimum distance between aSegment and all the polygons in the set. If the point is contained in the polygon, the distance is zero.

Definition at line 1591 of file shape_poly_set.cpp.

References DistanceToPolygon(), and m_polys.

1592 {
1593  int currentDistance;
1594  int minDistance = DistanceToPolygon( aSegment, 0 );
1595 
1596  // Iterate through all the polygons and get the minimum distance.
1597  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1598  {
1599  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1600 
1601  if( currentDistance < minDistance )
1602  minDistance = currentDistance;
1603  }
1604 
1605  return minDistance;
1606 }
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint...
int SHAPE_POLY_SET::DistanceToPolygon ( VECTOR2I  aPoint,
int  aIndex 
)

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

References containsSingle(), SEG::Distance(), and IterateSegmentsWithHoles().

Referenced by Distance(), and IsEmpty().

1513 {
1514  // We calculate the min dist between the segment and each outline segment
1515  // However, if the segment to test is inside the outline, and does not cross
1516  // any edge, it can be seen outside the polygon.
1517  // Therefore test if a segment end is inside ( testing only one end is enough )
1518  if( containsSingle( aPoint, aPolygonIndex ) )
1519  return 0;
1520 
1521  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1522 
1523  SEG polygonEdge = *iterator;
1524  int minDistance = polygonEdge.Distance( aPoint );
1525 
1526  for( iterator++; iterator && minDistance > 0; iterator++ )
1527  {
1528  polygonEdge = *iterator;
1529 
1530  int currentDistance = polygonEdge.Distance( aPoint );
1531 
1532  if( currentDistance < minDistance )
1533  minDistance = currentDistance;
1534  }
1535 
1536  return minDistance;
1537 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
Definition: seg.h:36
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
int SHAPE_POLY_SET::DistanceToPolygon ( SEG  aSegment,
int  aIndex,
int  aSegmentWidth = 0 
)

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

References SEG::A, containsSingle(), SEG::Distance(), and IterateSegmentsWithHoles().

1541 {
1542  // We calculate the min dist between the segment and each outline segment
1543  // However, if the segment to test is inside the outline, and does not cross
1544  // any edge, it can be seen outside the polygon.
1545  // Therefore test if a segment end is inside ( testing only one end is enough )
1546  if( containsSingle( aSegment.A, aPolygonIndex ) )
1547  return 0;
1548 
1549  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1550 
1551  SEG polygonEdge = *iterator;
1552  int minDistance = polygonEdge.Distance( aSegment );
1553 
1554  for( iterator++; iterator && minDistance > 0; iterator++ )
1555  {
1556  polygonEdge = *iterator;
1557 
1558  int currentDistance = polygonEdge.Distance( aSegment );
1559 
1560  if( currentDistance < minDistance )
1561  minDistance = currentDistance;
1562  }
1563 
1564  // Take into account the width of the segment
1565  if( aSegmentWidth > 0 )
1566  minDistance -= aSegmentWidth / 2;
1567 
1568  // Return the maximum of minDistance and zero
1569  return minDistance < 0 ? 0 : minDistance;
1570 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
Definition: seg.h:36
VECTOR2I A
Definition: seg.h:46
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
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 1633 of file shape_poly_set.cpp.

References FilletPolygon(), and m_polys.

Referenced by ZONE_CONTAINER::BuildSmoothedPoly(), and IsEmpty().

1634 {
1635  SHAPE_POLY_SET filleted;
1636 
1637  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1638  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, polygonIdx ) );
1639 
1640  return filleted;
1641 }
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex=0)
Function Fillet returns a filleted version of the aIndex-th polygon.
Class SHAPE_POLY_SET.
SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon ( unsigned int  aRadius,
int  aErrorMax,
int  aIndex = 0 
)

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

References chamferFilletPolygon().

Referenced by Fillet(), and IsEmpty().

1507 {
1508  return chamferFilletPolygon( CORNER_MODE::FILLETED, aRadius, aIndex, aErrorMax );
1509 }
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
const std::string SHAPE_POLY_SET::Format ( ) const
overridevirtual

Reimplemented from SHAPE.

Definition at line 1068 of file shape_poly_set.cpp.

References i, and m_polys.

1069 {
1070  std::stringstream ss;
1071 
1072  ss << "polyset " << m_polys.size() << "\n";
1073 
1074  for( unsigned i = 0; i < m_polys.size(); i++ )
1075  {
1076  ss << "poly " << m_polys[i].size() << "\n";
1077 
1078  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1079  {
1080  ss << m_polys[i][j].PointCount() << "\n";
1081 
1082  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1083  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1084  }
1085 
1086  ss << "\n";
1087  }
1088 
1089  return ss.str();
1090 }
size_t i
Definition: json11.cpp:597
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 829 of file shape_poly_set.cpp.

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

Referenced by addHoleToPolygon(), D_PAD::AddPrimitive(), D_PAD::buildCustomPadPolygon(), CacheTriangulation(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), export_vrml_polygon(), ZONE_FILLER::fillSingleZone(), DXF_PLOTTER::PlotPoly(), PlotSolderMaskLayer(), C3D_RENDER_RAYTRACING::reload(), and ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon().

830 {
831  Simplify( aFastMode ); // remove overlapping holes/degeneracy
832 
833  for( POLYGON& paths : m_polys )
834  {
835  fractureSingle( paths );
836  }
837 }
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...
void SHAPE_POLY_SET::fractureSingle ( POLYGON paths)
private

Definition at line 727 of file shape_poly_set.cpp.

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

Referenced by Fracture(), and IsEmpty().

728 {
729  FractureEdgeSet edges;
730  FractureEdgeSet border_edges;
731  FractureEdge* root = NULL;
732 
733  bool first = true;
734 
735  if( paths.size() == 1 )
736  return;
737 
738  int num_unconnected = 0;
739 
740  for( SHAPE_LINE_CHAIN& path : paths )
741  {
742  int index = 0;
743 
744  FractureEdge* prev = NULL, * first_edge = NULL;
745 
746  int x_min = std::numeric_limits<int>::max();
747 
748  for( int i = 0; i < path.PointCount(); i++ )
749  {
750  const VECTOR2I& p = path.CPoint( i );
751 
752  if( p.x < x_min )
753  x_min = p.x;
754  }
755 
756  for( int i = 0; i < path.PointCount(); i++ )
757  {
758  FractureEdge* fe = new FractureEdge( first, &path, index++ );
759 
760  if( !root )
761  root = fe;
762 
763  if( !first_edge )
764  first_edge = fe;
765 
766  if( prev )
767  prev->m_next = fe;
768 
769  if( i == path.PointCount() - 1 )
770  fe->m_next = first_edge;
771 
772  prev = fe;
773  edges.push_back( fe );
774 
775  if( !first )
776  {
777  if( fe->m_p1.x == x_min )
778  border_edges.push_back( fe );
779  }
780 
781  if( !fe->m_connected )
782  num_unconnected++;
783  }
784 
785  first = false; // first path is always the outline
786  }
787 
788  // keep connecting holes to the main outline, until there's no holes left...
789  while( num_unconnected > 0 )
790  {
791  int x_min = std::numeric_limits<int>::max();
792 
793  FractureEdge* smallestX = NULL;
794 
795  // find the left-most hole edge and merge with the outline
796  for( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
797  {
798  int xt = (*i)->m_p1.x;
799 
800  if( ( xt < x_min ) && !(*i)->m_connected )
801  {
802  x_min = xt;
803  smallestX = *i;
804  }
805  }
806 
807  num_unconnected -= processEdge( edges, smallestX );
808  }
809 
810  paths.clear();
811  SHAPE_LINE_CHAIN newPath;
812 
813  newPath.SetClosed( true );
814 
815  FractureEdge* e;
816 
817  for( e = root; e->m_next != root; e = e->m_next )
818  newPath.Append( e->m_p1 );
819 
820  newPath.Append( e->m_p1 );
821 
822  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
823  delete *i;
824 
825  paths.push_back( newPath );
826 }
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 max(a, b)
Definition: auxiliary.h:86
Class SHAPE_LINE_CHAIN.
FractureEdge * m_next
size_t i
Definition: json11.cpp:597
std::vector< FractureEdge * > FractureEdgeSet
SHAPE_LINE_CHAIN& SHAPE_POLY_SET::getContourForCorner ( int  aCornerId,
int &  aIndexWithinContour 
)
private

Referenced by IsEmpty().

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

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

123 {
124  int selectedVertex = aRelativeIndices.m_vertex;
125  unsigned int selectedContour = aRelativeIndices.m_contour;
126  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
127 
128  // Check whether the vertex indices make sense in this poly set
129  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
130  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
131  {
132  POLYGON currentPolygon;
133 
134  aGlobalIdx = 0;
135 
136  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
137  {
138  currentPolygon = Polygon( polygonIdx );
139 
140  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
141  {
142  aGlobalIdx += currentPolygon[contourIdx].PointCount();
143  }
144  }
145 
146  currentPolygon = Polygon( selectedPolygon );
147 
148  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
149  {
150  aGlobalIdx += currentPolygon[contourIdx].PointCount();
151  }
152 
153  aGlobalIdx += selectedVertex;
154 
155  return true;
156  }
157  else
158  {
159  return false;
160  }
161 }
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
MD5_HASH SHAPE_POLY_SET::GetHash ( ) const

Definition at line 1819 of file shape_poly_set.cpp.

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

Referenced by ZONE_FILLER::Fill(), and SHAPE_POLY_SET().

1820 {
1821  if( !m_hash.IsValid() )
1822  return checksum();
1823 
1824  return m_hash;
1825 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:23
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 350 of file shape_poly_set.cpp.

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

351 {
353 
354  // If the edge does not exist, throw an exception, it is an illegal access memory error
355  if( !GetRelativeIndices( aGlobalIndex, &index ) )
356  return false;
357 
358  // Calculate the previous and next index of aGlobalIndex, corresponding to
359  // the same contour;
360  VERTEX_INDEX inext = index;
361  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
362 
363  if( index.m_vertex == 0 )
364  {
365  index.m_vertex = lastpoint;
366  inext.m_vertex = 1;
367  }
368  else if( index.m_vertex == lastpoint )
369  {
370  index.m_vertex--;
371  inext.m_vertex = 0;
372  }
373  else
374  {
375  inext.m_vertex++;
376  index.m_vertex--;
377  }
378 
379  if( aPrevious )
380  {
381  int previous;
382  GetGlobalIndex( index, previous );
383  *aPrevious = previous;
384  }
385 
386  if( aNext )
387  {
388  int next;
389  GetGlobalIndex( inext, next );
390  *aNext = next;
391  }
392 
393  return true;
394 }
CITER next(CITER it)
Definition: ptree.cpp:130
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...
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 81 of file shape_poly_set.cpp.

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(), PCB_EDIT_FRAME::Delete_Zone_Contour(), DRC::doEdgeZoneDrc(), ZONE_CONTAINER::GetCornerPosition(), GetNeighbourIndexes(), InsertVertex(), IsVertexInHole(), IterateFromVertexWithHoles(), RemoveVertex(), ZONE_CONTAINER::SetCornerPosition(), ZONE_CONTAINER::SetSelectedCorner(), and Vertex().

83 {
84  int polygonIdx = 0;
85  unsigned int contourIdx = 0;
86  int vertexIdx = 0;
87 
88  int currentGlobalIdx = 0;
89 
90  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
91  {
92  const POLYGON currentPolygon = CPolygon( polygonIdx );
93 
94  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
95  {
96  SHAPE_LINE_CHAIN currentContour = currentPolygon[contourIdx];
97  int totalPoints = currentContour.PointCount();
98 
99  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
100  {
101  // Check if the current vertex is the globally indexed as aGlobalIdx
102  if( currentGlobalIdx == aGlobalIdx )
103  {
104  aRelativeIndices->m_polygon = polygonIdx;
105  aRelativeIndices->m_contour = contourIdx;
106  aRelativeIndices->m_vertex = vertexIdx;
107 
108  return true;
109  }
110 
111  // Advance
112  currentGlobalIdx++;
113  }
114  }
115  }
116 
117  return false;
118 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
int PointCount() const
Function PointCount()
int OutlineCount() const
Returns the number of outlines in the set
Class SHAPE_LINE_CHAIN.
const POLYGON & CPolygon(int aIndex) const
bool SHAPE_POLY_SET::HasHoles ( ) const

Returns true if the polygon set has any holes.

Definition at line 1001 of file shape_poly_set.cpp.

References m_polys.

Referenced by CacheTriangulation().

1002 {
1003  // Iterate through all the polygons on the set
1004  for( const POLYGON& paths : m_polys )
1005  {
1006  // If any of them has more than one contour, it is a hole.
1007  if( paths.size() > 1 )
1008  return true;
1009  }
1010 
1011  // Return false if and only if every polygon has just one outline, without holes.
1012  return false;
1013 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
bool SHAPE_POLY_SET::HasTouchingHoles ( ) const

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

Definition at line 1912 of file shape_poly_set.cpp.

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

1913 {
1914  for( int i = 0; i < OutlineCount(); i++ )
1915  {
1916  if( hasTouchingHoles( CPolygon( i ) ) )
1917  {
1918  return true;
1919  }
1920  }
1921 
1922  return false;
1923 }
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.
size_t i
Definition: json11.cpp:597
const POLYGON & CPolygon(int aIndex) const
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 1926 of file shape_poly_set.cpp.

Referenced by HasTouchingHoles().

1927 {
1928  std::set< long long > ptHashes;
1929 
1930  for( const auto& lc : aPoly )
1931  {
1932  for( const VECTOR2I& pt : lc.CPoints() )
1933  {
1934  const long long ptHash = (long long) pt.x << 32 | pt.y;
1935 
1936  if( ptHashes.count( ptHash ) > 0 )
1937  {
1938  return true;
1939  }
1940 
1941  ptHashes.insert( ptHash );
1942  }
1943  }
1944 
1945  return false;
1946 }
SHAPE_LINE_CHAIN& SHAPE_POLY_SET::Hole ( int  aOutline,
int  aHole 
)
inline

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

Definition at line 595 of file shape_poly_set.h.

References m_polys.

Referenced by Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), export_vrml_board(), and DSN::SPECCTRA_DB::fillBOUNDARY().

596  {
597  return m_polys[aOutline][aHole + 1];
598  }
int SHAPE_POLY_SET::HoleCount ( int  aOutline) const
inline

Returns the number of holes in a given outline

Definition at line 562 of file shape_poly_set.h.

References m_polys.

Referenced by CINFO3D_VISU::AddSolidAreasShapesToContainer(), CLAYER_TRIANGLES::AddToMiddleContourns(), ZONE_CONTAINER::AppendCorner(), containsSingle(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), KIGFX::PCB_PAINTER::draw(), export_vrml_board(), DSN::SPECCTRA_DB::fillBOUNDARY(), and PlotLayerOutlines().

563  {
564  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
565  return 0;
566 
567  // the first polygon in m_polys[aOutline] is the main contour,
568  // only others are holes:
569  return m_polys[aOutline].size() - 1;
570  }
void SHAPE_POLY_SET::importTree ( ClipperLib::PolyTree *  tree)
private

Definition at line 591 of file shape_poly_set.cpp.

References i, and m_polys.

Referenced by booleanOp(), Inflate(), and IsEmpty().

592 {
593  m_polys.clear();
594 
595  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
596  {
597  if( !n->IsHole() )
598  {
599  POLYGON paths;
600  paths.reserve( n->Childs.size() + 1 );
601  paths.push_back( n->Contour );
602 
603  for( unsigned int i = 0; i < n->Childs.size(); i++ )
604  paths.push_back( n->Childs[i]->Contour );
605 
606  m_polys.push_back( paths );
607  }
608  }
609 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
size_t i
Definition: json11.cpp:597
void SHAPE_POLY_SET::Inflate ( int  aFactor,
int  aCircleSegmentsCount 
)

Performs outline inflation/deflation, using round corners.

Definition at line 545 of file shape_poly_set.cpp.

References abs, i, importTree(), m_polys, and SEG_CNT_MAX.

Referenced by D_PAD::buildCustomPadPolygon(), ZONE_FILLER::buildZoneFeatureHoleList(), Collide(), ZONE_FILLER::computeRawFilledAreas(), CINFO3D_VISU::createNewPadWithClearance(), KIGFX::PCB_PAINTER::draw(), D_PAD::DrawShape(), export_vrml_polygon(), ZONE_FILLER::fillSingleZone(), GERBER_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadRoundRect(), MODULE::GetBoundingPoly(), PlotSolderMaskLayer(), PlotStandardLayer(), ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon(), TransformRoundRectToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

546 {
547  // A static table to avoid repetitive calculations of the coefficient
548  // 1.0 - cos( M_PI/aCircleSegmentsCount)
549  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
550  #define SEG_CNT_MAX 64
551  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
552 
553  ClipperOffset c;
554 
555  for( const POLYGON& poly : m_polys )
556  {
557  for( size_t i = 0; i < poly.size(); i++ )
558  c.AddPath( poly[i].convertToClipper( i == 0 ), jtRound, etClosedPolygon );
559  }
560 
561  PolyTree solution;
562 
563  // Calculate the arc tolerance (arc error) from the seg count by circle.
564  // the seg count is nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aFactor))
565  // see:
566  // www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
567 
568  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
569  aCircleSegmentsCount = 6;
570 
571  double coeff;
572 
573  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
574  {
575  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
576 
577  if( aCircleSegmentsCount <= SEG_CNT_MAX )
578  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
579  }
580  else
581  coeff = arc_tolerance_factor[aCircleSegmentsCount];
582 
583  c.ArcTolerance = std::abs( aFactor ) * coeff;
584 
585  c.Execute( solution, aFactor );
586 
587  importTree( &solution );
588 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
#define abs(a)
Definition: auxiliary.h:84
#define SEG_CNT_MAX
size_t i
Definition: json11.cpp:597
void importTree(ClipperLib::PolyTree *tree)
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 214 of file shape_poly_set.cpp.

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(), PCB_EDIT_FRAME::Process_Special_Functions(), and PCB_EDIT_FRAME::Start_Move_Zone_Corner().

215 {
216  VERTEX_INDEX index;
217 
218  if( aGlobalIndex < 0 )
219  aGlobalIndex = 0;
220 
221  if( aGlobalIndex >= TotalVertices() )
222  {
223  Append( aNewVertex );
224  }
225  else
226  {
227  // Assure the position to be inserted exists; throw an exception otherwise
228  if( GetRelativeIndices( aGlobalIndex, &index ) )
229  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
230  else
231  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
232  }
233 }
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) ...
bool SHAPE_POLY_SET::IsPolygonSelfIntersecting ( int  aPolygonIndex)

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

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

Referenced by IsSelfIntersecting().

398 {
399  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
400  SEGMENT_ITERATOR innerIterator;
401 
402  for( iterator = IterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
403  {
404  SEG firstSegment = *iterator;
405 
406  // Iterate through all remaining segments.
407  innerIterator = iterator;
408 
409  // Start in the next segment, we don't want to check collision between a segment and itself
410  for( innerIterator++; innerIterator; innerIterator++ )
411  {
412  SEG secondSegment = *innerIterator;
413 
414  // Check whether the two segments built collide, only when they are not adjacent.
415  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
416  return true;
417  }
418  }
419 
420  return false;
421 }
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
Definition: seg.h:36
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
bool SHAPE_POLY_SET::IsSelfIntersecting ( )

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

References IsPolygonSelfIntersecting(), and m_polys.

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

425 {
426  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
427  {
428  if( IsPolygonSelfIntersecting( polygon ) )
429  return true;
430  }
431 
432  return false;
433 }
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.
bool SHAPE_POLY_SET::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 881 of file shape_poly_set.h.

References BBox(), Collide(), CollideEdge(), CollideVertex(), Contains(), and PointOnEdge().

882  {
883  return true;
884  }
bool SHAPE_POLY_SET::IsTriangulationUpToDate ( ) const

Definition at line 1828 of file shape_poly_set.cpp.

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

Referenced by KIGFX::OPENGL_GAL::DrawPolygon(), SHAPE_POLY_SET(), and PNS_KICAD_IFACE::syncZone().

1829 {
1830  if( !m_triangulationValid )
1831  return false;
1832 
1833  if( !m_hash.IsValid() )
1834  return false;
1835 
1836  auto hash = checksum();
1837 
1838  return hash == m_hash;
1839 }
MD5_HASH checksum() const
bool IsValid() const
Definition: md5_hash.h:23
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 1609 of file shape_poly_set.cpp.

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

Referenced by PCB_EDIT_FRAME::createPopUpMenuForZones(), and IsEmpty().

1610 {
1611  VERTEX_INDEX index;
1612 
1613  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1614  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1615  return false;
1616 
1617  // The contour is a hole if its index is greater than zero
1618  return index.m_contour > 0;
1619 }
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
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 641 of file shape_poly_set.h.

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(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), ZONE_CONTAINER::DrawWhileCreateOutline(), EDGE_MODULE::Flip(), DRAWSEGMENT::Flip(), ZONE_CONTAINER::Iterate(), EDGE_MODULE::Mirror(), ZONE_CONTAINER::Mirror(), EDGE_MODULE::Move(), DRAWSEGMENT::Move(), GERBER_DRAW_ITEM::MoveAB(), GERBER_DRAW_ITEM::MoveXY(), DRAWSEGMENT::Rotate(), and ZONE_CONTAINER::Rotate().

642  {
643  ITERATOR iter;
644 
645  iter.m_poly = this;
646  iter.m_currentPolygon = aFirst;
647  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
648  iter.m_currentContour = 0;
649  iter.m_currentVertex = 0;
650  iter.m_iterateHoles = aIterateHoles;
651 
652  return iter;
653  }
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
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 661 of file shape_poly_set.h.

References Iterate().

662  {
663  return Iterate( aOutline, aOutline );
664  }
ITERATOR Iterate()
Function Iterate.
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 682 of file shape_poly_set.h.

References OutlineCount().

Referenced by Iterate(), and IterateWithHoles().

683  {
684  return Iterate( 0, OutlineCount() - 1 );
685  }
ITERATOR Iterate()
Function Iterate.
int OutlineCount() const
Returns the number of outlines in the set
ITERATOR SHAPE_POLY_SET::IterateFromVertexWithHoles ( int  aGlobalIdx)
inline

Definition at line 732 of file shape_poly_set.h.

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.

733  {
734  // Build iterator
735  ITERATOR iter = IterateWithHoles();
736 
737  // Get the relative indices of the globally indexed vertex
738  VERTEX_INDEX indices;
739 
740  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
741  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
742 
743  // Adjust where the iterator is pointing
744  iter.m_currentPolygon = indices.m_polygon;
745  iter.m_currentContour = indices.m_contour;
746  iter.m_currentVertex = indices.m_vertex;
747 
748  return iter;
749  }
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.
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 753 of file shape_poly_set.h.

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

754  {
755  SEGMENT_ITERATOR iter;
756 
757  iter.m_poly = this;
758  iter.m_currentPolygon = aFirst;
759  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
760  iter.m_currentContour = 0;
761  iter.m_currentSegment = 0;
762  iter.m_iterateHoles = aIterateHoles;
763 
764  return iter;
765  }
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
int OutlineCount() const
Returns the number of outlines in the set
SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( int  aPolygonIdx)
inline

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

Definition at line 768 of file shape_poly_set.h.

References IterateSegments().

769  {
770  return IterateSegments( aPolygonIdx, aPolygonIdx );
771  }
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegments ( )
inline

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

Definition at line 774 of file shape_poly_set.h.

References OutlineCount().

Referenced by IterateSegments(), and IterateSegmentsWithHoles().

775  {
776  return IterateSegments( 0, OutlineCount() - 1 );
777  }
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)
SEGMENT_ITERATOR SHAPE_POLY_SET::IterateSegmentsWithHoles ( )
inline

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

Definition at line 780 of file shape_poly_set.h.

References IterateSegments(), and OutlineCount().

Referenced by Collide(), CollideEdge(), DistanceToPolygon(), DRC::doEdgeZoneDrc(), ZONE_CONTAINER::Draw(), ZONE_CONTAINER::Hatch(), IsPolygonSelfIntersecting(), BOARD::TestAreaIntersection(), and DRC::TestZoneToZoneOutline().

781  {
782  return IterateSegments( 0, OutlineCount() - 1, true );
783  }
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)
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 786 of file shape_poly_set.h.

References IterateSegments().

787  {
788  return IterateSegments( aOutline, aOutline, true );
789  }
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
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 672 of file shape_poly_set.h.

References Iterate().

Referenced by findVertex(), ZONE_CONTAINER::Hatch(), ZONE_CONTAINER::IterateWithHoles(), ZONE_CONTAINER::Mirror(), ZONE_CONTAINER::Rotate(), BOARD::TestAreaIntersection(), and DRC::TestZoneToZoneOutline().

673  {
674  return Iterate( aOutline, aOutline, true );
675  }
ITERATOR Iterate()
Function Iterate.
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 692 of file shape_poly_set.h.

References Iterate(), and OutlineCount().

Referenced by CollideVertex(), IterateFromVertexWithHoles(), and RemoveNullSegments().

693  {
694  return Iterate( 0, OutlineCount() - 1, true );
695  }
ITERATOR Iterate()
Function Iterate.
int OutlineCount() const
Returns the number of outlines in the set
void SHAPE_POLY_SET::Move ( const VECTOR2I aVector)
overridevirtual

Implements SHAPE.

Definition at line 1458 of file shape_poly_set.cpp.

References m_polys.

Referenced by KIGFX::GERBVIEW_PAINTER::drawFlashedShape(), export_vrml_polygon(), GERBER_DRAW_ITEM::HitTest(), ZONE_CONTAINER::Move(), and TransformOvalClearanceToPolygon().

1459 {
1460  for( POLYGON& poly : m_polys )
1461  {
1462  for( SHAPE_LINE_CHAIN& path : poly )
1463  {
1464  path.Move( aVector );
1465  }
1466  }
1467 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.
int SHAPE_POLY_SET::NewHole ( int  aOutline = -1)

Creates a new hole in a given outline

Definition at line 176 of file shape_poly_set.cpp.

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

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

177 {
178  SHAPE_LINE_CHAIN empty_path;
179 
180  empty_path.SetClosed( true );
181 
182  // Default outline is the last one
183  if( aOutline < 0 )
184  aOutline += m_polys.size();
185 
186  // Add hole to the selected outline
187  m_polys[aOutline].push_back( empty_path );
188 
189  return m_polys.back().size() - 2;
190 }
void SetClosed(bool aClosed)
Function SetClosed()
Class SHAPE_LINE_CHAIN.
int SHAPE_POLY_SET::NewOutline ( )

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

Definition at line 164 of file shape_poly_set.cpp.

References m_polys, and SHAPE_LINE_CHAIN::SetClosed().

Referenced by addHoleToPolygon(), addRect(), ZONE_CONTAINER::AppendCorner(), BuildBoardPolygonOutlines(), D_PAD::buildCustomPadPolygon(), D_PAD::BuildPadShapePolygon(), ZONE_FILLER::buildUnconnectedThermalStubsPolygonList(), ZONE_FILLER::buildZoneFeatureHoleList(), ConvertOutlineToPolygon(), ConvertPolyListToPolySet(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), D_CODE::ConvertShapeToPolygon(), CreateThermalReliefPadPolygon(), KIGFX::PCB_PAINTER::draw(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), fillArcPOLY(), MODULE::GetBoundingPoly(), getRectangleAlongCentreLine(), LEGACY_PLUGIN::loadZONE_CONTAINER(), CPolyLine::NormalizeAreaOutlines(), PCB_PARSER::parseZONE_CONTAINER(), DXF_PLOTTER::PlotPoly(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), DRAWSEGMENT::SetPolyPoints(), EDA_TEXT::TransformBoundingBoxWithClearanceToPolygon(), TransformCircleToPolygon(), TransformOvalClearanceToPolygon(), TransformRingToPolygon(), TransformRoundedEndsSegmentToPolygon(), TransformRoundRectToPolygon(), DRAWSEGMENT::TransformShapeWithClearanceToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

165 {
166  SHAPE_LINE_CHAIN empty_path;
167  POLYGON poly;
168 
169  empty_path.SetClosed( true );
170  poly.push_back( empty_path );
171  m_polys.push_back( poly );
172  return m_polys.size() - 1;
173 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void SetClosed(bool aClosed)
Function SetClosed()
Class SHAPE_LINE_CHAIN.
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 1035 of file shape_poly_set.cpp.

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

Referenced by BOARD::NormalizeAreaPolygon().

1036 {
1037  // We are expecting only one main outline, but this main outline can have holes
1038  // if holes: combine holes and remove them from the main outline.
1039  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1040  // calculations, but it is not mandatory. It is used mainly
1041  // because there is usually only very few vertices in area outlines
1042  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1043  SHAPE_POLY_SET holesBuffer;
1044 
1045  // Move holes stored in outline to holesBuffer:
1046  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1047  while( outline.size() > 1 )
1048  {
1049  holesBuffer.AddOutline( outline.back() );
1050  outline.pop_back();
1051  }
1052 
1054 
1055  // If any hole, substract it to main outline
1056  if( holesBuffer.OutlineCount() )
1057  {
1058  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1060  }
1061 
1063 
1064  return OutlineCount();
1065 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
int OutlineCount() const
Returns the number of outlines in the set
Class 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
SHAPE_POLY_SET & SHAPE_POLY_SET::operator= ( const SHAPE_POLY_SET aOther)

Definition at line 1807 of file shape_poly_set.cpp.

References m_hash, m_polys, m_triangulatedPolys, and m_triangulationValid.

1808 {
1809  static_cast<SHAPE&>(*this) = aOther;
1810  m_polys = aOther.m_polys;
1811 
1812  // reset poly cache:
1813  m_hash = MD5_HASH{};
1814  m_triangulationValid = false;
1815  m_triangulatedPolys.clear();
1816  return *this;
1817 }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
Class SHAPE.
Definition: shape.h:58
int SHAPE_POLY_SET::OutlineCount ( ) const
inline

Returns the number of outlines in the set

Definition at line 556 of file shape_poly_set.h.

References m_polys, and VertexCount().

Referenced by POINT_EDITOR::addCorner(), ZONE_CONTAINER::AddPolygon(), CINFO3D_VISU::AddSolidAreasShapesToContainer(), CLAYER_TRIANGLES::AddToMiddleContourns(), ZONE_CONTAINER::AppendCorner(), D_PAD::boundingRadius(), BuildBoardPolygonOutlines(), BuildConvexHull(), D_PAD::buildCustomPadPolygon(), DRAWSEGMENT::BuildPolyPointsList(), CacheTriangulation(), DRC::checkClearancePadToPad(), CIterate(), CIterateWithHoles(), BOARD::CombineAreas(), Contains(), Convert_path_polygon_to_polygon_blocks_and_dummy_blocks(), D_PAD::CustomShapeAsPolygonToBoardPosition(), DRC::doFootprintOverlappingDrc(), KIGFX::GERBVIEW_PAINTER::draw(), DRAWSEGMENT::Draw(), KIGFX::PCB_PAINTER::draw(), GERBER_DRAW_ITEM::Draw(), KIGFX::GERBVIEW_PAINTER::drawApertureMacro(), APERTURE_MACRO::DrawApertureMacroShape(), ZONE_CONTAINER::DrawFilledArea(), D_CODE::DrawFlashedPolygon(), D_CODE::DrawFlashedShape(), KIGFX::GERBVIEW_PAINTER::drawFlashedShape(), KIGFX::CAIRO_GAL::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::GERBVIEW_PAINTER::drawPolygon(), D_PAD::DrawShape(), KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), export_vrml_board(), export_vrml_padshape(), export_vrml_zones(), fillArcPOLY(), DSN::SPECCTRA_DB::fillBOUNDARY(), ZONE_FILLER::fillZoneWithSegments(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), D_PAD::FlipPrimitives(), C3D_RENDER_OGL_LEGACY::generate_3D_Vias_and_Pads(), C3D_RENDER_OGL_LEGACY::generate_holes_display_list(), APERTURE_MACRO::GetApertureMacroShape(), GERBER_DRAW_ITEM::GetBoundingBox(), D_PAD::GetBoundingBox(), GetRelativeIndices(), HasTouchingHoles(), D_PAD::HitTest(), Iterate(), IterateSegments(), IterateSegmentsWithHoles(), IterateWithHoles(), D_PAD::MergePrimitivesAsPolygon(), GERBER_DRAW_ITEM::MoveAB(), GERBER_DRAW_ITEM::MoveXY(), CPolyLine::NormalizeAreaOutlines(), NormalizeAreaOutlines(), BRDITEMS_PLOTTER::PlotDrawSegment(), PlotLayerOutlines(), BRDITEMS_PLOTTER::PlotPad(), DXF_PLOTTER::PlotPoly(), Polygon_Calc_BBox_3DU(), polygonArea(), C3D_RENDER_OGL_LEGACY::reload(), Subset(), and PNS_KICAD_IFACE::syncZone().

556 { return m_polys.size(); }
bool SHAPE_POLY_SET::Parse ( std::stringstream &  aStream)
overridevirtual

Reimplemented from SHAPE.

Definition at line 1093 of file shape_poly_set.cpp.

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

1094 {
1095  std::string tmp;
1096 
1097  aStream >> tmp;
1098 
1099  if( tmp != "polyset" )
1100  return false;
1101 
1102  aStream >> tmp;
1103 
1104  int n_polys = atoi( tmp.c_str() );
1105 
1106  if( n_polys < 0 )
1107  return false;
1108 
1109  for( int i = 0; i < n_polys; i++ )
1110  {
1111  POLYGON paths;
1112 
1113  aStream >> tmp;
1114 
1115  if( tmp != "poly" )
1116  return false;
1117 
1118  aStream >> tmp;
1119  int n_outlines = atoi( tmp.c_str() );
1120 
1121  if( n_outlines < 0 )
1122  return false;
1123 
1124  for( int j = 0; j < n_outlines; j++ )
1125  {
1126  SHAPE_LINE_CHAIN outline;
1127 
1128  outline.SetClosed( true );
1129 
1130  aStream >> tmp;
1131  int n_vertices = atoi( tmp.c_str() );
1132 
1133  for( int v = 0; v < n_vertices; v++ )
1134  {
1135  VECTOR2I p;
1136 
1137  aStream >> tmp; p.x = atoi( tmp.c_str() );
1138  aStream >> tmp; p.y = atoi( tmp.c_str() );
1139  outline.Append( p );
1140  }
1141 
1142  paths.push_back( outline );
1143  }
1144 
1145  m_polys.push_back( paths );
1146  }
1147 
1148  return true;
1149 }
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()
Class SHAPE_LINE_CHAIN.
size_t i
Definition: json11.cpp:597
bool SHAPE_POLY_SET::pointInPolygon ( const VECTOR2I aP,
const SHAPE_LINE_CHAIN aPath 
) const
private

Definition at line 1452 of file shape_poly_set.cpp.

References SHAPE_LINE_CHAIN::PointInside().

Referenced by containsSingle(), and IsEmpty().

1453 {
1454  return aPath.PointInside( aP );
1455 }
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
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 1169 of file shape_poly_set.cpp.

References m_polys.

Referenced by IsSolid().

1170 {
1171  // Iterate through all the polygons in the set
1172  for( const POLYGON& polygon : m_polys )
1173  {
1174  // Iterate through all the line chains in the polygon
1175  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1176  {
1177  if( lineChain.PointOnEdge( aP ) )
1178  return true;
1179  }
1180  }
1181 
1182  return false;
1183 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.
POLYGON& SHAPE_POLY_SET::Polygon ( int  aIndex)
inline
const POLYGON& SHAPE_POLY_SET::Polygon ( int  aIndex) const
inline

Definition at line 606 of file shape_poly_set.h.

References m_polys.

607  {
608  return m_polys[aIndex];
609  }
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 1239 of file shape_poly_set.cpp.

References m_polys.

Referenced by PCB_EDIT_FRAME::Delete_Zone_Contour(), IsEmpty(), and POINT_EDITOR::removeCorner().

1240 {
1241  // Default polygon is the last one
1242  if( aPolygonIdx < 0 )
1243  aPolygonIdx += m_polys.size();
1244 
1245  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1246 }
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 1249 of file shape_poly_set.cpp.

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

Referenced by chamferFilletPolygon(), PCB_EDIT_FRAME::End_Zone(), IsEmpty(), and NormalizeAreaOutlines().

1250 {
1251  int removed = 0;
1252 
1253  ITERATOR iterator = IterateWithHoles();
1254 
1255  VECTOR2I contourStart = *iterator;
1256  VECTOR2I segmentStart, segmentEnd;
1257 
1258  VERTEX_INDEX indexStart;
1259 
1260  while( iterator )
1261  {
1262  // Obtain first point and its index
1263  segmentStart = *iterator;
1264  indexStart = iterator.GetIndex();
1265 
1266  // Obtain last point
1267  if( iterator.IsEndContour() )
1268  {
1269  segmentEnd = contourStart;
1270 
1271  // Advance
1272  iterator++;
1273 
1274  if( iterator )
1275  contourStart = *iterator;
1276  }
1277  else
1278  {
1279  // Advance
1280  iterator++;
1281 
1282  if( iterator )
1283  segmentEnd = *iterator;
1284  }
1285 
1286  // Remove segment start if both points are equal
1287  if( segmentStart == segmentEnd )
1288  {
1289  RemoveVertex( indexStart );
1290  removed++;
1291 
1292  // Advance the iterator one position, as there is one vertex less.
1293  if( iterator )
1294  iterator++;
1295  }
1296  }
1297 
1298  return removed;
1299 }
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.
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 1408 of file shape_poly_set.cpp.

References GetRelativeIndices().

Referenced by Abort_Zone_Move_Corner_Or_Outlines(), PCB_EDIT_FRAME::Delete_LastCreatedCorner(), IsEmpty(), PCB_EDIT_FRAME::Remove_Zone_Corner(), POINT_EDITOR::removeCorner(), RemoveNullSegments(), and PCB_EDIT_FRAME::Start_Move_Zone_Corner().

1409 {
1410  VERTEX_INDEX index;
1411 
1412  // Assure the to be removed vertex exists, abort otherwise
1413  if( GetRelativeIndices( aGlobalIndex, &index ) )
1414  RemoveVertex( index );
1415  else
1416  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1417 }
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.
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 1420 of file shape_poly_set.cpp.

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.

1421 {
1422  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1423 }
void SHAPE_POLY_SET::Rotate ( double  aAngle,
const VECTOR2I aCenter 
)

Function Rotate rotates all vertices by a given angle.

Parameters
aCenteris the rotation center
aAnglerotation angle in radians

Definition at line 1470 of file shape_poly_set.cpp.

References m_polys.

Referenced by D_CODE::ConvertShapeToPolygon(), export_vrml_polygon(), MODULE::GetBoundingPoly(), and TransformOvalClearanceToPolygon().

1471 {
1472  for( POLYGON& poly : m_polys )
1473  {
1474  for( SHAPE_LINE_CHAIN& path : poly )
1475  {
1476  path.Rotate( aAngle, aCenter );
1477  }
1478  }
1479 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.
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 1027 of file shape_poly_set.cpp.

References booleanOp(), and empty().

Referenced by CINFO3D_VISU::AddShapeWithClearanceToContainer(), D_PAD::buildCustomPadPolygon(), BOARD::CombineAreas(), ZONE_FILLER::computeRawFilledAreas(), MODULE::CoverageRatio(), CINFO3D_VISU::createBoardPolygon(), CINFO3D_VISU::createLayers(), CreateThermalReliefPadPolygon(), Fracture(), BOARD::GetBoardPolygonOutlines(), CPolyLine::NormalizeAreaOutlines(), NormalizeAreaOutlines(), PlotLayerOutlines(), ZONE_CONTAINER::TransformShapeWithClearanceToPolygon(), and Unfracture().

1028 {
1030 
1031  booleanOp( ctUnion, empty, aFastMode );
1032 }
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, ...
Class SHAPE_POLY_SET.
static bool empty(const wxTextEntryBase *aCtrl)
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 261 of file shape_poly_set.cpp.

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

Referenced by Outline(), and UnitSet().

262 {
263  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
264 
265  SHAPE_POLY_SET newPolySet;
266 
267  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
268  {
269  newPolySet.m_polys.push_back( Polygon( index ) );
270  }
271 
272  return newPolySet;
273 }
int OutlineCount() const
Returns the number of outlines in the set
Class SHAPE_POLY_SET.
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
int SHAPE_POLY_SET::TotalVertices ( ) const

Returns total number of vertices stored in the set.

Definition at line 1482 of file shape_poly_set.cpp.

References m_polys.

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

1483 {
1484  int c = 0;
1485 
1486  for( const POLYGON& poly : m_polys )
1487  {
1488  for( const SHAPE_LINE_CHAIN& path : poly )
1489  {
1490  c += path.PointCount();
1491  }
1492  }
1493 
1494  return c;
1495 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Class SHAPE_LINE_CHAIN.
unsigned int SHAPE_POLY_SET::TriangulatedPolyCount ( ) const
inline

Returns the number of triangulated polygons

Definition at line 553 of file shape_poly_set.h.

References m_triangulatedPolys.

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

553 { return m_triangulatedPolys.size(); }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
const TRIANGULATED_POLYGON* SHAPE_POLY_SET::TriangulatedPolygon ( int  aIndex) const
inline

Definition at line 611 of file shape_poly_set.h.

References m_triangulatedPolys.

Referenced by Convert_shape_line_polygon_to_triangles(), KIGFX::OPENGL_GAL::drawTriangulatedPolyset(), SHAPE_POLY_SET(), and PNS_KICAD_IFACE::syncZone().

612  {
613  return m_triangulatedPolys[aIndex].get();
614  }
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
SHAPE_TYPE SHAPE::Type ( ) const
inlineinherited

Function Type()

Returns the type of the shape.

Return values
thetype

Definition at line 83 of file shape.h.

References SHAPE::m_type.

Referenced by PNS::DP_GATEWAYS::BuildFromPrimitivePair(), CollideShapes(), PNS::OPTIMIZER::computeBreakouts(), PNS::LOGGER::dumpShape(), PNS::SOLID::Hull(), ROUTER_PREVIEW_ITEM::ViewDraw(), and SHAPE_FILE_IO::Write().

84  {
85  return m_type;
86  }
SHAPE_TYPE m_type
type of our shape
Definition: shape.h:166
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 1016 of file shape_poly_set.cpp.

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

1017 {
1018  for( POLYGON& path : m_polys )
1019  {
1020  unfractureSingle( path );
1021  }
1022 
1023  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1024 }
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...
void SHAPE_POLY_SET::unfractureSingle ( SHAPE_POLY_SET::POLYGON aPoly)
private

Definition at line 840 of file shape_poly_set.cpp.

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

Referenced by IsEmpty(), and Unfracture().

841 {
842  assert( aPoly.size() == 1 );
843 
844  struct EDGE
845  {
846  int m_index = 0;
847  SHAPE_LINE_CHAIN* m_poly = nullptr;
848  bool m_duplicate = false;
849 
850  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
851  m_index( aIndex ),
852  m_poly( aPolygon )
853  {}
854 
855  bool compareSegs( const SEG& s1, const SEG& s2 ) const
856  {
857  return (s1.A == s2.B && s1.B == s2.A);
858  }
859 
860  bool operator==( const EDGE& aOther ) const
861  {
862  return compareSegs( m_poly->CSegment( m_index ),
863  aOther.m_poly->CSegment( aOther.m_index ) );
864  }
865 
866  bool operator!=( const EDGE& aOther ) const
867  {
868  return !compareSegs( m_poly->CSegment( m_index ),
869  aOther.m_poly->CSegment( aOther.m_index ) );
870  }
871 
872  struct HASH
873  {
874  std::size_t operator()( const EDGE& aEdge ) const
875  {
876  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
877 
878  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
879  }
880  };
881  };
882 
883  struct EDGE_LIST_ENTRY
884  {
885  int index;
886  EDGE_LIST_ENTRY* next;
887  };
888 
889  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
890 
891  auto lc = aPoly[0];
892  lc.Simplify();
893 
894  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
895 
896  for( int i = 0; i < lc.SegmentCount(); i++ )
897  {
898  edgeList[i].index = i;
899  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
900  }
901 
902  std::unordered_set<EDGE_LIST_ENTRY*> queue;
903 
904  for( int i = 0; i < lc.SegmentCount(); i++ )
905  {
906  EDGE e( &lc, i );
907  uniqueEdges.insert( e );
908  }
909 
910  for( int i = 0; i < lc.SegmentCount(); i++ )
911  {
912  EDGE e( &lc, i );
913  auto it = uniqueEdges.find( e );
914 
915  if( it != uniqueEdges.end() && it->m_index != i )
916  {
917  int e1 = it->m_index;
918  int e2 = i;
919 
920  if( e1 > e2 )
921  std::swap( e1, e2 );
922 
923  int e1_prev = e1 - 1;
924 
925  if( e1_prev < 0 )
926  e1_prev = lc.SegmentCount() - 1;
927 
928  int e2_prev = e2 - 1;
929 
930  if( e2_prev < 0 )
931  e2_prev = lc.SegmentCount() - 1;
932 
933  int e1_next = e1 + 1;
934 
935  if( e1_next == lc.SegmentCount() )
936  e1_next = 0;
937 
938  int e2_next = e2 + 1;
939 
940  if( e2_next == lc.SegmentCount() )
941  e2_next = 0;
942 
943  edgeList[e1_prev].next = &edgeList[ e2_next ];
944  edgeList[e2_prev].next = &edgeList[ e1_next ];
945  edgeList[i].next = nullptr;
946  edgeList[it->m_index].next = nullptr;
947  }
948  }
949 
950  for( int i = 0; i < lc.SegmentCount(); i++ )
951  {
952  if( edgeList[i].next )
953  queue.insert( &edgeList[i] );
954  }
955 
956  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
957 
958  int n = 0;
959  int outline = -1;
960 
961  POLYGON result;
962 
963  while( queue.size() )
964  {
965  auto e_first = (*queue.begin() );
966  auto e = e_first;
967  int cnt = 0;
968 
969  do {
970  edgeBuf[cnt++] = e;
971  e = e->next;
972  } while( e && e != e_first );
973 
974  SHAPE_LINE_CHAIN outl;
975 
976  for( int i = 0; i < cnt; i++ )
977  {
978  auto p = lc.CPoint( edgeBuf[i]->index );
979  outl.Append( p );
980  queue.erase( edgeBuf[i] );
981  }
982 
983  outl.SetClosed( true );
984 
985  bool cw = outl.Area() > 0.0;
986 
987  if( cw )
988  outline = n;
989 
990  result.push_back( outl );
991  n++;
992  }
993 
994  if( outline > 0 )
995  std::swap( result[0], result[outline] );
996 
997  aPoly = result;
998 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
CITER next(CITER it)
Definition: ptree.cpp:130
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 SEG CSegment(int aIndex) const
Function CSegment()
void SetClosed(bool aClosed)
Function SetClosed()
Definition: seg.h:36
Class SHAPE_LINE_CHAIN.
double Area() const
size_t i
Definition: json11.cpp:597
VECTOR2I A
Definition: seg.h:46
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
VECTOR2I B
Definition: seg.h:47
SHAPE_POLY_SET SHAPE_POLY_SET::UnitSet ( int  aPolygonIndex)
inline

Definition at line 589 of file shape_poly_set.h.

References Subset().

Referenced by BOARD::NormalizeAreaPolygon().

590  {
591  return Subset( aPolygonIndex, aPolygonIndex + 1 );
592  }
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...
VECTOR2I & SHAPE_POLY_SET::Vertex ( int  aIndex,
int  aOutline,
int  aHole 
)

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

Definition at line 276 of file shape_poly_set.cpp.

References m_polys.

Referenced by Abort_Zone_Move_Corner_Or_Outlines(), POINT_EDITOR::addCorner(), DRC::doFootprintOverlappingDrc(), D_CODE::DrawFlashedPolygon(), GERBER_FILE_IMAGE::Execute_DCODE_Command(), GERBER_FILE_IMAGE::Execute_G_Command(), findVertex(), ZONE_CONTAINER::Hatch(), ZONE_CONTAINER::HitTest(), ZONE_CONTAINER::MoveEdge(), ZONE_CONTAINER::SetCornerPosition(), Show_Zone_Corner_Or_Outline_While_Move_Mouse(), PCB_EDIT_FRAME::Start_Move_Zone_Corner(), POINT_EDITOR::updateItem(), and Vertex().

277 {
278  if( aOutline < 0 )
279  aOutline += m_polys.size();
280 
281  int idx;
282 
283  if( aHole < 0 )
284  idx = 0;
285  else
286  idx = aHole + 1;
287 
288  assert( aOutline < (int) m_polys.size() );
289  assert( idx < (int) m_polys[aOutline].size() );
290 
291  return m_polys[aOutline][idx].Point( aIndex );
292 }
VECTOR2I & SHAPE_POLY_SET::Vertex ( int  aGlobalIndex)

Returns the aGlobalIndex-th vertex in the poly set

Definition at line 314 of file shape_poly_set.cpp.

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.

315 {
317 
318  // Assure the passed index references a legal position; abort otherwise
319  if( !GetRelativeIndices( aGlobalIndex, &index ) )
320  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
321 
322  return m_polys[index.m_polygon][index.m_contour].Point( index.m_vertex );
323 }
Struct VERTEX_INDEX.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
VECTOR2I & SHAPE_POLY_SET::Vertex ( SHAPE_POLY_SET::VERTEX_INDEX  index)

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

Definition at line 338 of file shape_poly_set.cpp.

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

339 {
340  return Vertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
341 }
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline
VECTOR2I& SHAPE_POLY_SET::vertex ( int  aCornerId)
private

Referenced by IsEmpty().

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

References m_polys.

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

237 {
238  if( m_polys.size() == 0 ) // Empty poly set
239  return 0;
240 
241  if( aOutline < 0 ) // Use last outline
242  aOutline += m_polys.size();
243 
244  int idx;
245 
246  if( aHole < 0 )
247  idx = 0;
248  else
249  idx = aHole + 1;
250 
251  if( aOutline >= (int) m_polys.size() ) // not existing outline
252  return 0;
253 
254  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
255  return 0;
256 
257  return m_polys[aOutline][idx].PointCount();
258 }

Member Data Documentation

MD5_HASH SHAPE_POLY_SET::m_hash
private
std::vector<std::unique_ptr<TRIANGULATED_POLYGON> > SHAPE_POLY_SET::m_triangulatedPolys
private
bool SHAPE_POLY_SET::m_triangulationValid = false
private
SHAPE_TYPE SHAPE::m_type
protectedinherited

type of our shape

Definition at line 166 of file shape.h.

Referenced by SHAPE::Type().


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