KiCad PCB EDA Suite
SHAPE_LINE_CHAIN Class Reference

Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc segments. More...

#include <shape_line_chain.h>

Inheritance diagram for SHAPE_LINE_CHAIN:
SHAPE_LINE_CHAIN_BASE SHAPE SHAPE_BASE

Classes

struct  compareOriginDistance
 
struct  INTERSECTION
 Represent an intersection between two line segments. More...
 
class  POINT_INSIDE_TRACKER
 A dynamic state checking if a point lies within polygon with a dynamically built outline ( with each piece of the outline added by AddPolyline () More...
 

Public Types

typedef std::vector< INTERSECTIONINTERSECTIONS
 

Public Member Functions

 SHAPE_LINE_CHAIN ()
 Initialize an empty line chain. More...
 
 SHAPE_LINE_CHAIN (const SHAPE_LINE_CHAIN &aShape)
 
 SHAPE_LINE_CHAIN (const std::vector< int > &aV)
 
 SHAPE_LINE_CHAIN (const std::vector< VECTOR2I > &aV, bool aClosed=false)
 
 SHAPE_LINE_CHAIN (const SHAPE_ARC &aArc, bool aClosed=false)
 
 SHAPE_LINE_CHAIN (const ClipperLib::Path &aPath, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffer)
 
 SHAPE_LINE_CHAIN (const Clipper2Lib::Path64 &aPath, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffer)
 
virtual ~SHAPE_LINE_CHAIN ()
 
virtual bool Collide (const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Check if point aP lies closer to us than aClearance. More...
 
virtual bool Collide (const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
 Check if segment aSeg lies closer to us than aClearance. More...
 
SHAPE_LINE_CHAINoperator= (const SHAPE_LINE_CHAIN &)=default
 
SHAPEClone () const override
 Return a dynamically allocated copy of the shape. More...
 
void Clear ()
 Remove all points from the line chain. More...
 
void SetClosed (bool aClosed)
 Mark the line chain as closed (i.e. More...
 
bool IsClosed () const override
 
void SetWidth (int aWidth)
 Set the width of all segments in the chain. More...
 
int Width () const
 Get the current width of the segments in the chain. More...
 
int SegmentCount () const
 Return the number of segments in this line chain. More...
 
int ShapeCount () const
 Return the number of shapes (line segments or arcs) in this line chain. More...
 
int PointCount () const
 Return the number of points (vertices) in this line chain. More...
 
SEG Segment (int aIndex)
 Return a copy of the aIndex-th segment in the line chain. More...
 
const SEG CSegment (int aIndex) const
 Return a constant copy of the aIndex segment in the line chain. More...
 
int NextShape (int aPointIndex, bool aForwards=true) const
 Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape. More...
 
int PrevShape (int aPointIndex) const
 
void SetPoint (int aIndex, const VECTOR2I &aPos)
 Move a point to a specific location. More...
 
const VECTOR2ICPoint (int aIndex) const
 Return a reference to a given point in the line chain. More...
 
const std::vector< VECTOR2I > & CPoints () const
 
const VECTOR2ICLastPoint () const
 Return the last point in the line chain. More...
 
const std::vector< SHAPE_ARC > & CArcs () const
 
const std::vector< std::pair< ssize_t, ssize_t > > & CShapes () const
 
const BOX2I BBox (int aClearance=0) const override
 Compute a bounding box of the shape, with a margin of aClearance a collision. More...
 
void GenerateBBoxCache () const
 
BOX2IGetCachedBBox () const override
 
int Distance (const VECTOR2I &aP, bool aOutlineOnly=false) const
 Compute the minimum distance between the line chain and a point aP. More...
 
const SHAPE_LINE_CHAIN Reverse () const
 Reverse point order in the line chain. More...
 
void ClearArcs ()
 Remove all arc references in the line chain, resulting in a chain formed only of straight segments. More...
 
long long int Length () const
 Return length of the line chain in Euclidean metric. More...
 
void Append (int aX, int aY, bool aAllowDuplication=false)
 Append a new point at the end of the line chain. More...
 
void Append (const VECTOR2I &aP, bool aAllowDuplication=false)
 Append a new point at the end of the line chain. More...
 
void Append (const SHAPE_LINE_CHAIN &aOtherLine)
 Append another line chain at the end. More...
 
void Append (const SHAPE_ARC &aArc)
 
void Append (const SHAPE_ARC &aArc, double aAccuracy)
 
void Insert (size_t aVertex, const VECTOR2I &aP)
 
void Insert (size_t aVertex, const SHAPE_ARC &aArc)
 
void Replace (int aStartIndex, int aEndIndex, const VECTOR2I &aP)
 Replace points with indices in range [start_index, end_index] with a single point aP. More...
 
void Replace (int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN &aLine)
 Replace points with indices in range [start_index, end_index] with the points from line chain aLine. More...
 
void Remove (int aStartIndex, int aEndIndex)
 Remove the range of points [start_index, end_index] from the line chain. More...
 
void Remove (int aIndex)
 Remove the aIndex-th point from the line chain. More...
 
void RemoveShape (int aPointIndex)
 Remove the shape at the given index from the line chain. More...
 
int Split (const VECTOR2I &aP)
 Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two. More...
 
int Find (const VECTOR2I &aP, int aThreshold=0) const
 Search for point aP. More...
 
int FindSegment (const VECTOR2I &aP, int aThreshold=1) const
 Search for segment containing point aP. More...
 
const SHAPE_LINE_CHAIN Slice (int aStartIndex, int aEndIndex=-1) const
 Return a subset of this line chain containing the [start_index, end_index] range of points. More...
 
bool Intersects (const SHAPE_LINE_CHAIN &aChain) const
 
int Intersect (const SEG &aSeg, INTERSECTIONS &aIp) const
 Find all intersection points between our line chain and the segment aSeg. More...
 
int Intersect (const SHAPE_LINE_CHAIN &aChain, INTERSECTIONS &aIp, bool aExcludeColinearAndTouching=false, BOX2I *aChainBBox=nullptr) const
 Find all intersection points between our line chain and the line chain aChain. More...
 
int PathLength (const VECTOR2I &aP, int aIndex=-1) const
 Compute the walk path length from the beginning of the line chain and the point aP belonging to our line. More...
 
bool CheckClearance (const VECTOR2I &aP, const int aDist) const
 Check if point aP is closer to (or on) an edge or vertex of the line chain. More...
 
const std::optional< INTERSECTIONSelfIntersecting () const
 Check if the line chain is self-intersecting. More...
 
SHAPE_LINE_CHAINSimplify (bool aRemoveColinear=true)
 Simplify the line chain by removing colinear adjacent segments and duplicate vertices. More...
 
int NearestSegment (const VECTOR2I &aP) const
 Find the segment nearest the given point. More...
 
const VECTOR2I NearestPoint (const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
 Find a point on the line chain that is closest to point aP. More...
 
const VECTOR2I NearestPoint (const SEG &aSeg, int &dist) const
 Find a point on the line chain that is closest to the line defined by the points of segment aSeg, also returns the distance. More...
 
const std::string Format (bool aCplusPlus=true) const override
 
bool Parse (std::stringstream &aStream) override
 
bool operator!= (const SHAPE_LINE_CHAIN &aRhs) const
 
bool CompareGeometry (const SHAPE_LINE_CHAIN &aOther) const
 
void Move (const VECTOR2I &aVector) override
 
void Mirror (bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
 Mirror the line points about y or x (or both). More...
 
void Mirror (const SEG &axis)
 Mirror the line points using an given axis. More...
 
void Rotate (const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
 Rotate all vertices by a given angle. More...
 
bool IsSolid () const override
 
const VECTOR2I PointAlong (int aPathLength) const
 
double Area (bool aAbsolute=true) const
 Return the area of this chain. More...
 
size_t ArcCount () const
 
ssize_t ArcIndex (size_t aSegment) const
 Return the arc index for the given segment index. More...
 
const SHAPE_ARCArc (size_t aArc) const
 
bool IsSharedPt (size_t aIndex) const
 Test if a point is shared between multiple shapes. More...
 
bool IsPtOnArc (size_t aPtIndex) const
 
bool IsArcSegment (size_t aSegment) const
 
bool IsArcStart (size_t aIndex) const
 
bool IsArcEnd (size_t aIndex) const
 
virtual const VECTOR2I GetPoint (int aIndex) const override
 
virtual const SEG GetSegment (int aIndex) const override
 
virtual size_t GetPointCount () const override
 
virtual size_t GetSegmentCount () const override
 
virtual bool Collide (const SHAPE *aShape, int aClearance, VECTOR2I *aMTV) const
 Check if the boundary of shape (this) lies closer to the shape aShape than aClearance, indicating a collision. More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
 
SEG::ecoord SquaredDistance (const VECTOR2I &aP, bool aOutlineOnly=false) const
 
bool PointInside (const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
 Check if point aP lies inside a polygon (any type) defined by the line chain. More...
 
bool PointOnEdge (const VECTOR2I &aP, int aAccuracy=0) const
 Check if point aP lies on an edge or vertex of the line chain. More...
 
int EdgeContainingPoint (const VECTOR2I &aP, int aAccuracy=0) const
 Check if point aP lies on an edge or vertex of the line chain. More...
 
int GetClearance (const SHAPE *aOther) const
 Return the actual minimum distance between two shapes. More...
 
bool IsNull () const
 Return true if the shape is a null shape. More...
 
virtual VECTOR2I Centre () const
 Compute a center-of-mass of the shape. More...
 
FACETNewFacet ()
 
SGNODECalcShape (SGNODE *aParent, SGNODE *aColor, WRL1_ORDER aVertexOrder, float aCreaseLimit=0.74317, bool isVRML2=false)
 
SHAPE_TYPE Type () const
 Return the type of the shape. More...
 
wxString TypeName () const
 
virtual bool HasIndexableSubshapes () const
 
virtual size_t GetIndexableSubshapeCount () const
 
virtual void GetIndexableSubshapes (std::vector< const SHAPE * > &aSubshapes) const
 

Static Public Attributes

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

Protected Types

typedef VECTOR2I::extended_type ecoord
 

Protected Member Functions

void convertArc (ssize_t aArcIndex)
 Convert an arc to only a point chain by removing the arc and references. More...
 
void splitArc (ssize_t aPtIndex, bool aCoincident=false)
 Splits an arc into two arcs at aPtIndex. More...
 
void amendArc (size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)
 
void amendArcStart (size_t aArcIndex, const VECTOR2I &aNewStart)
 
void amendArcEnd (size_t aArcIndex, const VECTOR2I &aNewEnd)
 
ssize_t reversedArcIndex (size_t aSegment) const
 Return the arc index for the given segment index, looking backwards. More...
 
ClipperLib::Path convertToClipper (bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
 Create a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation. More...
 
Clipper2Lib::Path64 convertToClipper2 (bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
 Create a new Clipper2 path from the SHAPE_LINE_CHAIN in a given orientation. More...
 
void fixIndicesRotation ()
 Fix indices of this chain to ensure arcs are not split between the end and start indices. More...
 
void mergeFirstLastPointIfNeeded ()
 Merge the first and last point if they are the same and this chain is closed. More...
 

Protected Attributes

SHAPE_TYPE m_type
 < type of our shape More...
 

Private Types

typedef std::vector< VECTOR2I >::iterator point_iter
 
typedef std::vector< VECTOR2I >::const_iterator point_citer
 

Private Attributes

std::vector< VECTOR2Im_points
 array of vertices More...
 
std::vector< std::pair< ssize_t, ssize_t > > m_shapes
 Array of indices that refer to the index of the shape if the point is part of a larger shape, e.g. More...
 
std::vector< SHAPE_ARCm_arcs
 
bool m_closed
 is the line chain closed? More...
 
int m_width
 Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to account for where we need a width and where not Alternatively, we could split the class into a LINE_CHAIN (no width) and SHAPE_LINE_CHAIN that derives from SHAPE as well that does have a width. More...
 
BOX2I m_bbox
 cached bounding box More...
 
std::list< FACET * > facets
 

Static Private Attributes

static const ssize_t SHAPE_IS_PT = -1
 
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT = { SHAPE_IS_PT, SHAPE_IS_PT }
 

Friends

class SHAPE_POLY_SET
 

Detailed Description

Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc segments.

The arc shapes are piecewise approximated for the purpose of boolean operations but are used as arcs when doing collision checks.

It is purposely not named "polyline" to avoid confusion with the existing CPolyLine in Pcbnew.

Note
The SHAPE_LINE_CHAIN class shall not be used for polygons!

Definition at line 81 of file shape_line_chain.h.

Member Typedef Documentation

◆ ecoord

typedef VECTOR2I::extended_type SHAPE::ecoord
protectedinherited

Definition at line 249 of file shape.h.

◆ INTERSECTIONS

Definition at line 151 of file shape_line_chain.h.

◆ point_citer

typedef std::vector<VECTOR2I>::const_iterator SHAPE_LINE_CHAIN::point_citer
private

Definition at line 85 of file shape_line_chain.h.

◆ point_iter

typedef std::vector<VECTOR2I>::iterator SHAPE_LINE_CHAIN::point_iter
private

Definition at line 84 of file shape_line_chain.h.

Constructor & Destructor Documentation

◆ SHAPE_LINE_CHAIN() [1/7]

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( )
inline

Initialize an empty line chain.

Definition at line 157 of file shape_line_chain.h.

157 :
159 m_closed( false ),
160 m_width( 0 )
161 {}
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:256
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
bool m_closed
is the line chain closed?
@ SH_LINE_CHAIN
line chain (polyline)
Definition: shape.h:46

Referenced by Clone().

◆ SHAPE_LINE_CHAIN() [2/7]

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const SHAPE_LINE_CHAIN aShape)
inline

Definition at line 163 of file shape_line_chain.h.

163 :
165 m_points( aShape.m_points ),
166 m_shapes( aShape.m_shapes ),
167 m_arcs( aShape.m_arcs ),
168 m_closed( aShape.m_closed ),
169 m_width( aShape.m_width ),
170 m_bbox( aShape.m_bbox )
171 {}
std::vector< std::pair< ssize_t, ssize_t > > m_shapes
Array of indices that refer to the index of the shape if the point is part of a larger shape,...
std::vector< SHAPE_ARC > m_arcs
std::vector< VECTOR2I > m_points
array of vertices
BOX2I m_bbox
cached bounding box

◆ SHAPE_LINE_CHAIN() [3/7]

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const std::vector< int > &  aV)

Definition at line 47 of file shape_line_chain.cpp.

49{
50 for(size_t i = 0; i < aV.size(); i+= 2 )
51 {
52 Append( aV[i], aV[i+1] );
53 }
54}
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.

References Append().

◆ SHAPE_LINE_CHAIN() [4/7]

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const std::vector< VECTOR2I > &  aV,
bool  aClosed = false 
)
inline

Definition at line 175 of file shape_line_chain.h.

175 :
177 m_closed( aClosed ),
178 m_width( 0 )
179 {
180 m_points = aV;
181 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
182 }
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

References m_points, m_shapes, and SHAPES_ARE_PT.

◆ SHAPE_LINE_CHAIN() [5/7]

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const SHAPE_ARC aArc,
bool  aClosed = false 
)
inline

Definition at line 184 of file shape_line_chain.h.

184 :
186 m_closed( aClosed ),
187 m_width( 0 )
188 {
190 m_arcs.emplace_back( aArc );
191 m_arcs.back().SetWidth( 0 );
192 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( m_points.size(), { 0, SHAPE_IS_PT } );
193 }
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=DefaultAccuracyForPCB(), double *aEffectiveAccuracy=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:470
const std::vector< VECTOR2I > & CPoints() const
static const ssize_t SHAPE_IS_PT

References SHAPE_ARC::ConvertToPolyline(), CPoints(), m_arcs, m_points, m_shapes, and SHAPE_IS_PT.

◆ SHAPE_LINE_CHAIN() [6/7]

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const ClipperLib::Path &  aPath,
const std::vector< CLIPPER_Z_VALUE > &  aZValueBuffer,
const std::vector< SHAPE_ARC > &  aArcBuffer 
)

Definition at line 57 of file shape_line_chain.cpp.

59 :
61 m_closed( true ), m_width( 0 )
62{
63 std::map<ssize_t, ssize_t> loadedArcs;
64 m_points.reserve( aPath.size() );
65 m_shapes.reserve( aPath.size() );
66
67 auto loadArc =
68 [&]( ssize_t aArcIndex ) -> ssize_t
69 {
70 if( aArcIndex == SHAPE_IS_PT )
71 {
72 return SHAPE_IS_PT;
73 }
74 else if( loadedArcs.count( aArcIndex ) == 0 )
75 {
76 loadedArcs.insert( { aArcIndex, m_arcs.size() } );
77 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
78 }
79
80 return loadedArcs.at( aArcIndex );
81 };
82
83 for( size_t ii = 0; ii < aPath.size(); ++ii )
84 {
85 Append( aPath[ii].X, aPath[ii].Y );
86
87 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
88 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
89 }
90
91 // Clipper shouldn't return duplicate contiguous points. if it did, these would be
92 // removed during Append() and we would have different number of shapes to points
93 wxASSERT( m_shapes.size() == m_points.size() );
94
95 // Clipper might mess up the rotation of the indices such that an arc can be split between
96 // the end point and wrap around to the start point. Lets fix the indices up now
98}
void fixIndicesRotation()
Fix indices of this chain to ensure arcs are not split between the end and start indices.
#define Z()
#define X()

References Append(), fixIndicesRotation(), m_arcs, m_points, m_shapes, SHAPE_IS_PT, X, and Z.

◆ SHAPE_LINE_CHAIN() [7/7]

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const Clipper2Lib::Path64 &  aPath,
const std::vector< CLIPPER_Z_VALUE > &  aZValueBuffer,
const std::vector< SHAPE_ARC > &  aArcBuffer 
)

Definition at line 101 of file shape_line_chain.cpp.

103 :
105 m_closed( true ), m_width( 0 )
106{
107 std::map<ssize_t, ssize_t> loadedArcs;
108 m_points.reserve( aPath.size() );
109 m_shapes.reserve( aPath.size() );
110
111 auto loadArc =
112 [&]( ssize_t aArcIndex ) -> ssize_t
113 {
114 if( aArcIndex == SHAPE_IS_PT )
115 {
116 return SHAPE_IS_PT;
117 }
118 else if( loadedArcs.count( aArcIndex ) == 0 )
119 {
120 loadedArcs.insert( { aArcIndex, m_arcs.size() } );
121 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
122 }
123
124 return loadedArcs.at( aArcIndex );
125 };
126
127 for( size_t ii = 0; ii < aPath.size(); ++ii )
128 {
129 Append( aPath[ii].x, aPath[ii].y );
130
131 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].z].m_FirstArcIdx );
132 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].z].m_SecondArcIdx );
133 }
134
135 // Clipper shouldn't return duplicate contiguous points. if it did, these would be
136 // removed during Append() and we would have different number of shapes to points
137 wxASSERT( m_shapes.size() == m_points.size() );
138
139 // Clipper might mess up the rotation of the indices such that an arc can be split between
140 // the end point and wrap around to the start point. Lets fix the indices up now
142}

References Append(), fixIndicesRotation(), m_arcs, m_points, m_shapes, and SHAPE_IS_PT.

◆ ~SHAPE_LINE_CHAIN()

virtual SHAPE_LINE_CHAIN::~SHAPE_LINE_CHAIN ( )
inlinevirtual

Definition at line 203 of file shape_line_chain.h.

204 {}

Member Function Documentation

◆ amendArc()

void SHAPE_LINE_CHAIN::amendArc ( size_t  aArcIndex,
const VECTOR2I aNewStart,
const VECTOR2I aNewEnd 
)
protected

Definition at line 287 of file shape_line_chain.cpp.

289{
290 wxCHECK_MSG( aArcIndex < m_arcs.size(), /* void */,
291 wxT( "Invalid arc index requested." ) );
292
293 SHAPE_ARC& theArc = m_arcs[aArcIndex];
294
295 // Try to preseve the centre of the original arc
296 SHAPE_ARC newArc;
297 newArc.ConstructFromStartEndCenter( aNewStart, aNewEnd, theArc.GetCenter(),
298 theArc.IsClockwise() );
299
300 m_arcs[aArcIndex] = newArc;
301}
bool IsClockwise() const
Definition: shape_arc.cpp:366
SHAPE_ARC & ConstructFromStartEndCenter(const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aClockwise=false, double aWidth=0)
Constructs this arc from the given start, end and center.
Definition: shape_arc.cpp:209
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:433

References SHAPE_ARC::ConstructFromStartEndCenter(), SHAPE_ARC::GetCenter(), SHAPE_ARC::IsClockwise(), and m_arcs.

Referenced by amendArcEnd(), amendArcStart(), and splitArc().

◆ amendArcEnd()

void SHAPE_LINE_CHAIN::amendArcEnd ( size_t  aArcIndex,
const VECTOR2I aNewEnd 
)
inlineprotected

Definition at line 901 of file shape_line_chain.h.

902 {
903 amendArc( aArcIndex, m_arcs[aArcIndex].GetP0(), aNewEnd );
904 }
void amendArc(size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)

References amendArc(), and m_arcs.

◆ amendArcStart()

void SHAPE_LINE_CHAIN::amendArcStart ( size_t  aArcIndex,
const VECTOR2I aNewStart 
)
inlineprotected

Definition at line 896 of file shape_line_chain.h.

897 {
898 amendArc( aArcIndex, aNewStart, m_arcs[aArcIndex].GetP1() );
899 }

References amendArc(), and m_arcs.

◆ Append() [1/5]

void SHAPE_LINE_CHAIN::Append ( const SHAPE_ARC aArc)

Definition at line 1326 of file shape_line_chain.cpp.

1327{
1329}
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:221

References Append(), and SHAPE_ARC::DefaultAccuracyForPCB().

◆ Append() [2/5]

void SHAPE_LINE_CHAIN::Append ( const SHAPE_ARC aArc,
double  aAccuracy 
)

Definition at line 1332 of file shape_line_chain.cpp.

1333{
1334 SEG startToEnd( aArc.GetP0(), aArc.GetP1() );
1335
1336 if( startToEnd.Distance( aArc.GetArcMid() ) < 1 )
1337 {
1338 // Not really a valid arc. Add as a straight line segment instead
1339 Append( aArc.GetP0() );
1340 Append( aArc.GetP1() );
1341 }
1342 else
1343 {
1344 SHAPE_LINE_CHAIN chain = aArc.ConvertToPolyline( aAccuracy );
1345
1346 // @todo should the below 4 LOC be moved to SHAPE_ARC::ConvertToPolyline ?
1347 chain.m_arcs.push_back( aArc );
1348 chain.m_arcs.back().SetWidth( 0 );
1349
1350 for( auto& sh : chain.m_shapes )
1351 sh.first = 0;
1352
1353 Append( chain );
1354 }
1355
1356 assert( m_shapes.size() == m_points.size() );
1357}
Definition: seg.h:42
const VECTOR2I & GetArcMid() const
Definition: shape_arc.h:114
const VECTOR2I & GetP1() const
Definition: shape_arc.h:113
const VECTOR2I & GetP0() const
Definition: shape_arc.h:112
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

References Append(), SHAPE_ARC::ConvertToPolyline(), SEG::Distance(), SHAPE_ARC::GetArcMid(), SHAPE_ARC::GetP0(), SHAPE_ARC::GetP1(), m_arcs, m_points, and m_shapes.

◆ Append() [3/5]

void SHAPE_LINE_CHAIN::Append ( const SHAPE_LINE_CHAIN aOtherLine)

Append another line chain at the end.

Parameters
aOtherLineis the line chain to be appended.

Definition at line 1260 of file shape_line_chain.cpp.

1261{
1262 assert( m_shapes.size() == m_points.size() );
1263
1264 if( aOtherLine.PointCount() == 0 )
1265 {
1266 return;
1267 }
1268
1269 size_t num_arcs = m_arcs.size();
1270 m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
1271
1272 auto fixShapeIndices =
1273 [&]( const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1274 {
1275 std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1276
1277 alg::run_on_pair( retval, [&]( ssize_t& aIndex )
1278 {
1279 if( aIndex != SHAPE_IS_PT )
1280 aIndex = aIndex + num_arcs;
1281 } );
1282
1283 return retval;
1284 };
1285
1286 if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
1287 {
1288 const VECTOR2I p = aOtherLine.CPoint( 0 );
1289 m_points.push_back( p );
1290 m_shapes.push_back( fixShapeIndices( aOtherLine.CShapes()[0] ) );
1291 m_bbox.Merge( p );
1292 }
1293 else if( aOtherLine.IsArcSegment( 0 ) )
1294 {
1295 // Associate the new arc shape with the last point of this chain
1296 if( m_shapes.back() == SHAPES_ARE_PT )
1297 m_shapes.back().first = aOtherLine.CShapes()[0].first + num_arcs;
1298 else
1299 m_shapes.back().second = aOtherLine.CShapes()[0].first + num_arcs;
1300 }
1301
1302
1303 for( int i = 1; i < aOtherLine.PointCount(); i++ )
1304 {
1305 const VECTOR2I p = aOtherLine.CPoint( i );
1306 m_points.push_back( p );
1307
1308 ssize_t arcIndex = aOtherLine.ArcIndex( i );
1309
1310 if( arcIndex != ssize_t( SHAPE_IS_PT ) )
1311 {
1312 m_shapes.push_back( fixShapeIndices( aOtherLine.m_shapes[i] ) );
1313 }
1314 else
1315 m_shapes.push_back( SHAPES_ARE_PT );
1316
1317 m_bbox.Merge( p );
1318 }
1319
1321
1322 assert( m_shapes.size() == m_points.size() );
1323}
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:588
int PointCount() const
Return the number of points (vertices) in this line chain.
void mergeFirstLastPointIfNeeded()
Merge the first and last point if they are the same and this chain is closed.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const std::vector< std::pair< ssize_t, ssize_t > > & CShapes() const
bool IsArcSegment(size_t aSegment) const
void run_on_pair(std::pair< _Type, _Type > &__pair, _Function __f)
Apply a function to the first and second element of a std::pair.
Definition: kicad_algo.h:44

References ArcIndex(), CPoint(), CShapes(), IsArcSegment(), m_arcs, m_bbox, m_points, m_shapes, BOX2< Vec >::Merge(), mergeFirstLastPointIfNeeded(), PointCount(), alg::run_on_pair(), SHAPE_IS_PT, and SHAPES_ARE_PT.

◆ Append() [4/5]

void SHAPE_LINE_CHAIN::Append ( const VECTOR2I aP,
bool  aAllowDuplication = false 
)
inline

Append a new point at the end of the line chain.

Parameters
aPis the new point.
aAllowDuplicationset to true to append the new point even it is the same as the last entered point or false (default) to skip it if it is the same as the last entered point.

Definition at line 511 of file shape_line_chain.h.

512 {
513 if( m_points.size() == 0 )
514 m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
515
516 if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
517 {
518 m_points.push_back( aP );
519 m_shapes.push_back( SHAPES_ARE_PT );
520 m_bbox.Merge( aP );
521 }
522 }
BOX2< VECTOR2I > BOX2I
Definition: box2.h:847
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

References CPoint(), m_bbox, m_points, m_shapes, BOX2< Vec >::Merge(), and SHAPES_ARE_PT.

◆ Append() [5/5]

void SHAPE_LINE_CHAIN::Append ( int  aX,
int  aY,
bool  aAllowDuplication = false 
)
inline

Append a new point at the end of the line chain.

Parameters
aXis X coordinate of the new point.
aYis Y coordinate of the new point.
aAllowDuplicationset to true to append the new point even if it is the same as the last entered point, false (default) to skip it if it is the same as the last entered point.

Definition at line 497 of file shape_line_chain.h.

498 {
499 VECTOR2I v( aX, aY );
500 Append( v, aAllowDuplication );
501 }

References Append().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), PNS_PCBNEW_DEBUG_DECORATOR::AddPoint(), PNS_TEST_DEBUG_DECORATOR::AddPoint(), LIB_SHAPE::AddPoint(), SCH_SHAPE::AddPoint(), POLYGON_GEOM_MANAGER::AddPoint(), ZONE::AddPolygon(), PNS_PCBNEW_DEBUG_DECORATOR::AddShape(), PNS::DEBUG_DECORATOR::AddShape(), PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::DIFF_PAIR::Append(), SHAPE_SIMPLE::Append(), Append(), CADSTAR_ARCHIVE_PARSER::VERTEX::AppendToChain(), PNS::ArcHull(), PNS::NODE::AssembleLine(), EDA_SHAPE::beginEdit(), BOOST_AUTO_TEST_CASE(), buildBoardBoundingBoxPoly(), PAD::BuildEffectiveShapes(), BuildFootprintPolygonOutlines(), PNS::DIFF_PAIR::BuildInitial(), DIRECTION_45::BuildInitialTrace(), SHAPE_POLY_SET::BuildPolysetFromOrientedPaths(), ZONE_FILLER::buildThermalSpokes(), SHAPE_POLY_SET::chamferFilletPolygon(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), PNS::OPTIMIZER::circleBreakouts(), KI_TEST::CommonTestData::CommonTestData(), PCB_GRID_HELPER::computeAnchors(), SCH_SHEET_PIN::ConstrainOnEdge(), EDA_SHAPE::continueEdit(), ConvertArcToPolyline(), ConvertOutlineToPolygon(), convertPolygon(), SHAPE_ARC::ConvertToPolyline(), PNS::ConvexHull(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), PNS::OPTIMIZER::customBreakouts(), PNS::MEANDER_PLACER::doMove(), PNS::LINE::dragSegment45(), PNS::MEANDER_SHAPE::forward(), SHAPE_POLY_SET::fractureSingle(), PNS::MEANDER_SHAPE::genMeanderShape(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), KIFONT::OUTLINE_FONT::getTextAsGlyphs(), HelperShapeLineChainFromAltiumVertices(), Insert(), POLYGON_GEOM_MANAGER::IsSelfIntersecting(), PNS::ROUTER::isStartingPointRoutable(), IteratorFixture::IteratorFixture(), PNS::TOPOLOGY::LeadingRatLine(), CADSTAR_SCH_ARCHIVE_LOADER::loadBusses(), FABMASTER::loadFootprints(), CADSTAR_SCH_ARCHIVE_LOADER::loadNets(), FABMASTER::loadShapePolySet(), FABMASTER::loadZone(), PNS::MEANDER_SHAPE::MakeArc(), PNS::MEANDER_SHAPE::MakeCorner(), PNS::MEANDER_SHAPE::makeMiterShape(), CONVERT_TOOL::makePolysFromChainedSegs(), GEOM_TEST::MakeSquarePolyLine(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeObtuse(), PNS::MEANDER_SHAPE::miter(), PNS::DP_MEANDER_PLACER::Move(), PNS::OctagonalHull(), ZONE_CREATE_HELPER::OnComplete(), PNS::LINE_PLACER::optimizeTailHeadTransition(), SHAPE_RECT::Outline(), SHAPE_POLY_SET::Parse(), PCB_PARSER::parseOutlinePoints(), ALTIUM_PCB::ParseRegions6Data(), partitionPolyIntoRegularCellGrid(), BRDITEMS_PLOTTER::PlotFootprintShape(), BRDITEMS_PLOTTER::PlotPcbShape(), PNS::VIA::PushoutForce(), PNS::LINE_PLACER::rhWalkBase(), PNS::SegmentHull(), SHAPE_LINE_CHAIN(), MARKER_BASE::ShapeToPolygon(), Slice(), PNS::OPTIMIZER::smartPadsSingle(), PNS::MEANDER_SHAPE::start(), TestConcaveSquareFillet(), PNS::tightenSegment(), PNS::LINE_PLACER::Trace(), TransformCircleToPolygon(), unfracture(), SHAPE_POLY_SET::unfractureSingle(), and PNS::LINE::Walkaround().

◆ Arc()

◆ ArcCount()

size_t SHAPE_LINE_CHAIN::ArcCount ( ) const
inline

◆ ArcIndex()

ssize_t SHAPE_LINE_CHAIN::ArcIndex ( size_t  aSegment) const
inline

Return the arc index for the given segment index.

Definition at line 796 of file shape_line_chain.h.

797 {
798 if( IsSharedPt( aSegment ) )
799 return m_shapes[aSegment].second;
800 else
801 return m_shapes[aSegment].first;
802 }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.

References IsSharedPt(), and m_shapes.

Referenced by Append(), PNS::NODE::AssembleLine(), PNS::MEANDER_PLACER::doMove(), fixIndicesRotation(), PNS::LINE_PLACER::FixRoute(), PCB_PLUGIN::formatPolyPts(), PNS::LINE_PLACER::handlePullback(), ALTIUM_PCB::HelperCreateBoardOutline(), GEOM_TEST::IsOutlineValid(), PNS::LINE_PLACER::mergeHead(), PNS::DP_MEANDER_PLACER::Move(), NearestPoint(), NextShape(), GERBER_PLOTTER::PlotPoly(), RemoveShape(), Slice(), Split(), and splitArc().

◆ Area()

double SHAPE_LINE_CHAIN::Area ( bool  aAbsolute = true) const

Return the area of this chain.

Parameters
aAbsoluteIf true, returns a positive value. Otherwise the value depends on the orientation of the chain

Definition at line 2117 of file shape_line_chain.cpp.

2118{
2119 // see https://www.mathopenref.com/coordpolygonarea2.html
2120
2121 if( !m_closed )
2122 return 0.0;
2123
2124 double area = 0.0;
2125 int size = m_points.size();
2126
2127 for( int i = 0, j = size - 1; i < size; ++i )
2128 {
2129 area += ( (double) m_points[j].x + m_points[i].x ) *
2130 ( (double) m_points[j].y - m_points[i].y );
2131 j = i;
2132 }
2133
2134 if( aAbsolute )
2135 return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
2136 else
2137 return -area * 0.5; // The result would be negative if points are anti-clockwise
2138}

References m_closed, and m_points.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), SHAPE_POLY_SET::Area(), TEARDROP_MANAGER::ComputePointsOnPadVia(), convertToClipper(), convertToClipper2(), ZONE_FILLER::Fill(), FOOTPRINT::GetCoverageArea(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), unfracture(), and SHAPE_POLY_SET::unfractureSingle().

◆ BBox()

const BOX2I SHAPE_LINE_CHAIN::BBox ( int  aClearance = 0) const
inlineoverridevirtual

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

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

Implements SHAPE.

Definition at line 435 of file shape_line_chain.h.

436 {
437 BOX2I bbox;
438 bbox.Compute( m_points );
439
440 if( aClearance != 0 || m_width != 0 )
441 bbox.Inflate( aClearance + m_width );
442
443 return bbox;
444 }
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:82

References BOX2< Vec >::Compute(), BOX2< Vec >::Inflate(), m_points, and m_width.

Referenced by SHAPE_SIMPLE::BBox(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), AR_AUTOPLACER::fillMatrix(), POLYGON_TEST::FindPairs(), DIALOG_BOARD_STATISTICS::getDataFromPCB(), Intersect(), FABMASTER::loadZones(), PNS::COMPONENT_DRAGGER::Start(), and PolygonTriangulation::TesselatePolygon().

◆ CalcShape()

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

Definition at line 703 of file wrlfacet.cpp.

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

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

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

◆ CArcs()

const std::vector< SHAPE_ARC > & SHAPE_LINE_CHAIN::CArcs ( ) const
inline
Returns
the vector of stored arcs.

Definition at line 421 of file shape_line_chain.h.

422 {
423 return m_arcs;
424 }

References m_arcs.

Referenced by ROUTER_PREVIEW_ITEM::drawLineChain(), PNS::LINE_PLACER::handlePullback(), Length(), and PNS::LINE_PLACER::mergeHead().

◆ Centre()

virtual VECTOR2I SHAPE::Centre ( ) const
inlinevirtualinherited

Compute a center-of-mass of the shape.

Returns
the center-of-mass point

Definition at line 229 of file shape.h.

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

References SHAPE::BBox(), and BOX2< Vec >::Centre().

Referenced by Collide().

◆ CheckClearance()

bool SHAPE_LINE_CHAIN::CheckClearance ( const VECTOR2I aP,
const int  aDist 
) const

Check if point aP is closer to (or on) an edge or vertex of the line chain.

Parameters
aPis the point to check.
aDistis the distance in internal units.
Returns
true if the point is equal to or closer than aDist to the line chain.

Definition at line 1706 of file shape_line_chain.cpp.

1707{
1708 if( !PointCount() )
1709 return false;
1710 else if( PointCount() == 1 )
1711 return m_points[0] == aP;
1712
1713 for( int i = 0; i < SegmentCount(); i++ )
1714 {
1715 const SEG s = CSegment( i );
1716
1717 if( s.A == aP || s.B == aP )
1718 return true;
1719
1720 if( s.Distance( aP ) <= aDist )
1721 return true;
1722 }
1723
1724 return false;
1725}
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:319
int SegmentCount() const
Return the number of segments in this line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.

References SEG::A, SEG::B, CSegment(), SEG::Distance(), m_points, PointCount(), and SegmentCount().

◆ CLastPoint()

const VECTOR2I & SHAPE_LINE_CHAIN::CLastPoint ( ) const
inline

Return the last point in the line chain.

Definition at line 413 of file shape_line_chain.h.

414 {
415 return m_points[static_cast<size_t>( PointCount() ) - 1];
416 }

References m_points, and PointCount().

Referenced by BOOST_AUTO_TEST_CASE(), EDA_SHAPE::continueEdit(), POLYGON_GEOM_MANAGER::DeleteLastCorner(), EDA_SHAPE::endEdit(), and POLYGON_GEOM_MANAGER::updateTemporaryLines().

◆ Clear()

◆ ClearArcs()

void SHAPE_LINE_CHAIN::ClearArcs ( )

Remove all arc references in the line chain, resulting in a chain formed only of straight segments.

Any arcs in the chain are removed and only the piecewise linear approximation remains.

Definition at line 680 of file shape_line_chain.cpp.

681{
682 for( ssize_t arcIndex = m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
683 convertArc( arcIndex );
684}
void convertArc(ssize_t aArcIndex)
Convert an arc to only a point chain by removing the arc and references.

References convertArc(), and m_arcs.

◆ Clone()

SHAPE * SHAPE_LINE_CHAIN::Clone ( ) const
overridevirtual

Return a dynamically allocated copy of the shape.

Return values
copyof the shape

Reimplemented from SHAPE.

Definition at line 2038 of file shape_line_chain.cpp.

2039{
2040 return new SHAPE_LINE_CHAIN( *this );
2041}
SHAPE_LINE_CHAIN()
Initialize an empty line chain.

References SHAPE_LINE_CHAIN().

◆ Collide() [1/4]

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

Check if segment aSeg lies closer to us than aClearance.

Note: This is overridden as we want to ensure we test collisions with the arcs in this chain as true arcs rather than segment approximations.

Parameters
aSegthe segment to check for collisions with
aClearanceminimum distance that does not qualify as a collision.
aActualan optional pointer to an int to store the actual distance in the event of a collision.
Returns
true, when a collision has been found

Reimplemented from SHAPE_LINE_CHAIN_BASE.

Definition at line 571 of file shape_line_chain.cpp.

573{
574 if( IsClosed() && PointInside( aSeg.A ) )
575 {
576 if( aLocation )
577 *aLocation = aSeg.A;
578
579 if( aActual )
580 *aActual = 0;
581
582 return true;
583 }
584
585 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
586 SEG::ecoord clearance_sq = SEG::Square( aClearance );
587 VECTOR2I nearest;
588
589 // Collide line segments
590 for( size_t i = 0; i < GetSegmentCount(); i++ )
591 {
592 if( IsArcSegment( i ) )
593 continue;
594
595 const SEG& s = GetSegment( i );
596 SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
597
598 if( dist_sq < closest_dist_sq )
599 {
600 if( aLocation )
601 nearest = s.NearestPoint( aSeg );
602
603 closest_dist_sq = dist_sq;
604
605 if( closest_dist_sq == 0 )
606 break;
607
608 // If we're not looking for aActual then any collision will do
609 if( closest_dist_sq < clearance_sq && !aActual )
610 break;
611 }
612 }
613
614 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
615 {
616 if( aLocation )
617 *aLocation = nearest;
618
619 if( aActual )
620 *aActual = sqrt( closest_dist_sq );
621
622 return true;
623 }
624
625 // Collide arc segments
626 for( size_t i = 0; i < ArcCount(); i++ )
627 {
628 const SHAPE_ARC& arc = Arc( i );
629
630 // The arcs in the chain should have zero width
631 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
632
633 if( arc.Collide( aSeg, aClearance, aActual, aLocation ) )
634 return true;
635 }
636
637 return false;
638}
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
VECTOR2I::extended_type ecoord
Definition: seg.h:44
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:261
static SEG::ecoord Square(int a)
Definition: seg.h:123
int GetWidth() const
Definition: shape_arc.h:157
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the segment aSeg than aClearance,...
Definition: shape_arc.cpp:241
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
const SHAPE_ARC & Arc(size_t aArc) const
bool IsClosed() const override
virtual const SEG GetSegment(int aIndex) const override
virtual size_t GetSegmentCount() const override
size_t ArcCount() const
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79

References SEG::A, Arc(), ArcCount(), SHAPE_ARC::Collide(), VECTOR2< int >::ECOORD_MAX, GetSegment(), GetSegmentCount(), SHAPE_ARC::GetWidth(), IsArcSegment(), IsClosed(), SEG::NearestPoint(), SHAPE_LINE_CHAIN_BASE::PointInside(), SEG::Square(), and SEG::SquaredDistance().

◆ Collide() [2/4]

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

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

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

Reimplemented in SHAPE_COMPOUND, SHAPE_RECT, and SHAPE_SEGMENT.

Definition at line 1109 of file shape_collisions.cpp.

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

References collideShapes().

◆ Collide() [3/4]

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

Reimplemented in SHAPE_ARC, SHAPE_COMPOUND, SHAPE_POLY_SET, SHAPE_RECT, and SHAPE_SEGMENT.

Definition at line 1115 of file shape_collisions.cpp.

1116{
1117 return collideShapes( this, aShape, aClearance, aActual, aLocation, nullptr );
1118}

References collideShapes().

◆ Collide() [4/4]

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

Check if point aP lies closer to us than aClearance.

Note: This is overridden as we want to ensure we test collisions with the arcs in this chain as true arcs rather than segment approximations.

Parameters
aPthe point to check for collisions with
aClearanceminimum distance that does not qualify as a collision.
aActualan optional pointer to an int to store the actual distance in the event of a collision.
Returns
true, when a collision has been found

Reimplemented from SHAPE_LINE_CHAIN_BASE.

Definition at line 438 of file shape_line_chain.cpp.

440{
441 if( IsClosed() && PointInside( aP, aClearance ) )
442 {
443 if( aLocation )
444 *aLocation = aP;
445
446 if( aActual )
447 *aActual = 0;
448
449 return true;
450 }
451
452 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
453 SEG::ecoord clearance_sq = SEG::Square( aClearance );
454 VECTOR2I nearest;
455
456 // Collide line segments
457 for( size_t i = 0; i < GetSegmentCount(); i++ )
458 {
459 if( IsArcSegment( i ) )
460 continue;
461
462 const SEG& s = GetSegment( i );
463 VECTOR2I pn = s.NearestPoint( aP );
464 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
465
466 if( dist_sq < closest_dist_sq )
467 {
468 nearest = pn;
469 closest_dist_sq = dist_sq;
470
471 if( closest_dist_sq == 0 )
472 break;
473
474 // If we're not looking for aActual then any collision will do
475 if( closest_dist_sq < clearance_sq && !aActual )
476 break;
477 }
478 }
479
480 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
481 {
482 if( aLocation )
483 *aLocation = nearest;
484
485 if( aActual )
486 *aActual = sqrt( closest_dist_sq );
487
488 return true;
489 }
490
491 // Collide arc segments
492 for( size_t i = 0; i < ArcCount(); i++ )
493 {
494 const SHAPE_ARC& arc = Arc( i );
495
496 // The arcs in the chain should have zero width
497 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
498
499 if( arc.Collide( aP, aClearance, aActual, aLocation ) )
500 return true;
501 }
502
503 return false;
504}

References Arc(), ArcCount(), SHAPE_ARC::Collide(), VECTOR2< int >::ECOORD_MAX, GetSegment(), GetSegmentCount(), SHAPE_ARC::GetWidth(), IsArcSegment(), IsClosed(), SEG::NearestPoint(), SHAPE_LINE_CHAIN_BASE::PointInside(), and SEG::Square().

Referenced by PNS::MEANDERED_LINE::CheckSelfIntersections(), SHAPE_SIMPLE::Collide(), PCB_SELECTION_TOOL::hitTestDistance(), and DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::testZoneLayer().

◆ CompareGeometry()

bool SHAPE_LINE_CHAIN::CompareGeometry ( const SHAPE_LINE_CHAIN aOther) const

Definition at line 2012 of file shape_line_chain.cpp.

2013{
2014 SHAPE_LINE_CHAIN a(*this), b( aOther );
2015 a.Simplify();
2016 b.Simplify();
2017
2018 if( a.m_points.size() != b.m_points.size() )
2019 return false;
2020
2021 for( int i = 0; i < a.PointCount(); i++ )
2022 {
2023 if( a.CPoint( i ) != b.CPoint( i ) )
2024 return false;
2025 }
2026
2027 return true;
2028}

References CPoint(), m_points, and Simplify().

Referenced by PNS::LINE::CompareGeometry().

◆ convertArc()

void SHAPE_LINE_CHAIN::convertArc ( ssize_t  aArcIndex)
protected

Convert an arc to only a point chain by removing the arc and references.

Parameters
aArcIndexindex of the arc to convert to points

Definition at line 258 of file shape_line_chain.cpp.

259{
260 if( aArcIndex < 0 )
261 aArcIndex += m_arcs.size();
262
263 if( aArcIndex >= static_cast<ssize_t>( m_arcs.size() ) )
264 return;
265
266 // Clear the shapes references
267 for( auto& sh : m_shapes )
268 {
270 [&]( ssize_t& aShapeIndex )
271 {
272 if( aShapeIndex == aArcIndex )
273 aShapeIndex = SHAPE_IS_PT;
274
275 if( aShapeIndex > aArcIndex )
276 --aShapeIndex;
277 } );
278
279 if( sh.second != SHAPE_IS_PT && sh.first == SHAPE_IS_PT )
280 std::swap( sh.first, sh.second );
281 }
282
283 m_arcs.erase( m_arcs.begin() + aArcIndex );
284}

References m_arcs, m_shapes, alg::run_on_pair(), and SHAPE_IS_PT.

Referenced by ClearArcs(), Remove(), and SetPoint().

◆ convertToClipper()

ClipperLib::Path SHAPE_LINE_CHAIN::convertToClipper ( bool  aRequiredOrientation,
std::vector< CLIPPER_Z_VALUE > &  aZValueBuffer,
std::vector< SHAPE_ARC > &  aArcBuffer 
) const
protected

Create a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.

Definition at line 145 of file shape_line_chain.cpp.

148{
149 ClipperLib::Path c_path;
150 SHAPE_LINE_CHAIN input;
151 bool orientation = Area( false ) >= 0;
152 ssize_t shape_offset = aArcBuffer.size();
153
154 if( orientation != aRequiredOrientation )
155 input = Reverse();
156 else
157 input = *this;
158
159 int pointCount = input.PointCount();
160 c_path.reserve( pointCount );
161
162 for( int i = 0; i < pointCount; i++ )
163 {
164 const VECTOR2I& vertex = input.CPoint( i );
165
166 CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
167 size_t z_value_ptr = aZValueBuffer.size();
168 aZValueBuffer.push_back( z_value );
169
170 c_path.emplace_back( vertex.x, vertex.y, z_value_ptr );
171 }
172
173 aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
174
175 return c_path;
176}
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
double Area(bool aAbsolute=true) const
Return the area of this chain.
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...

References Area(), CPoint(), m_arcs, m_shapes, PointCount(), Reverse(), VECTOR2< T >::x, and VECTOR2< T >::y.

◆ convertToClipper2()

Clipper2Lib::Path64 SHAPE_LINE_CHAIN::convertToClipper2 ( bool  aRequiredOrientation,
std::vector< CLIPPER_Z_VALUE > &  aZValueBuffer,
std::vector< SHAPE_ARC > &  aArcBuffer 
) const
protected

Create a new Clipper2 path from the SHAPE_LINE_CHAIN in a given orientation.

Definition at line 179 of file shape_line_chain.cpp.

182{
183 Clipper2Lib::Path64 c_path;
184 SHAPE_LINE_CHAIN input;
185 bool orientation = Area( false ) >= 0;
186 ssize_t shape_offset = aArcBuffer.size();
187
188 if( orientation != aRequiredOrientation )
189 input = Reverse();
190 else
191 input = *this;
192
193 int pointCount = input.PointCount();
194 c_path.reserve( pointCount );
195
196 for( int i = 0; i < pointCount; i++ )
197 {
198 const VECTOR2I& vertex = input.CPoint( i );
199
200 CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
201 size_t z_value_ptr = aZValueBuffer.size();
202 aZValueBuffer.push_back( z_value );
203
204 c_path.emplace_back( vertex.x, vertex.y, z_value_ptr );
205 }
206
207 aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
208
209 return c_path;
210}

References Area(), CPoint(), m_arcs, m_shapes, PointCount(), Reverse(), VECTOR2< T >::x, and VECTOR2< T >::y.

◆ CPoint()

const VECTOR2I & SHAPE_LINE_CHAIN::CPoint ( int  aIndex) const
inline

Return a reference to a given point in the line chain.

Parameters
aIndexis the index of the point.
Returns
a const reference to the point.

Definition at line 395 of file shape_line_chain.h.

396 {
397 if( aIndex < 0 )
398 aIndex += PointCount();
399 else if( aIndex >= PointCount() )
400 aIndex -= PointCount();
401
402 return m_points[aIndex];
403 }

References m_points, and PointCount().

Referenced by LABEL_MANAGER::Add(), EE_POINT_EDITOR::addCorner(), POLYGON_GEOM_MANAGER::AddPoint(), SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::AddPolyline(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS_LOG_VIEWER_OVERLAY::AnnotatedPolyline(), Append(), PNS::LINE::AppendVia(), ArePolylineEndPointsNearCircle(), ArePolylineMidPointsNearCircle(), PNS::NODE::AssembleLine(), PNS::TOPOLOGY::AssembleTuningPath(), BOOST_AUTO_TEST_CASE(), build45DegLeader(), BuildBoardPolygonOutlines(), BuildConvexHull(), PAD::BuildEffectivePolygon(), PAD::BuildEffectiveShapes(), PNS::LINE_PLACER::buildInitialLine(), SHAPE_POLY_SET::chamferFilletPolygon(), PNS::LINE::ChangedArea(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), CN_VISITOR::checkZoneZoneConnection(), CompareGeometry(), EDA_SHAPE::continueEdit(), convertPolygon(), convertToClipper(), convertToClipper2(), PNS::coupledBypass(), PNS::LINE::CPoint(), SHAPE_SIMPLE::CPoint(), PolygonTriangulation::createList(), POLYGON_TEST::createList(), CreatePadsShapesSection(), PNS::LINE_PLACER::cursorDistMinimum(), PNS::LINE::dragCorner45(), PNS::dragCornerInternal(), KIGFX::PCB_PAINTER::draw(), KIGFX::CAIRO_GAL_BASE::drawPoly(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolyline(), KIGFX::CAIRO_GAL_BASE::DrawSegmentChain(), KIGFX::OPENGL_GAL::DrawSegmentChain(), EDA_SHAPE::endEdit(), EXPORTER_PCB_VRML::ExportVrmlBoard(), EXPORTER_PCB_VRML::ExportVrmlPolygonSet(), DSN::SPECCTRA_DB::fillBOUNDARY(), AR_AUTOPLACER::fillMatrix(), Find(), PNS::LINE_PLACER::FixRoute(), CADSTAR_SCH_ARCHIVE_LOADER::fixUpLibraryPins(), GERBER_PLOTTER::FlashPadChamferRoundRect(), DXF_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), HPGL_PLOTTER::FlashPadRoundRect(), PSLIKE_PLOTTER::FlashPadRoundRect(), PNS::TOPOLOGY::followTrivialPath(), PCB_PLUGIN::formatPolyPts(), PCB_SHAPE::GetFocusPosition(), GetPoint(), SHAPE_SIMPLE::GetPoint(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), CADSTAR_SCH_ARCHIVE_LOADER::getScaledLibPart(), PNS::MOUSE_TRAIL_TRACER::GetTrailLeadVector(), PNS::LINE_PLACER::handleSelfIntersections(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), GEOM_TEST::IsOutlineValid(), POLYGON_GEOM_MANAGER::IsSelfIntersecting(), DSN::SPECCTRA_DB::makeIMAGE(), DSN::SPECCTRA_DB::makePADSTACK(), STEP_PCB_MODEL::MakeShape(), PNS::LINE_PLACER::mergeHead(), PNS::MEANDER_SHAPE::miter(), PNS::DP_MEANDER_PLACER::Move(), PNS::LINE_PLACER::Move(), NearestPoint(), POLYGON_GEOM_MANAGER::NewPointClosesOutline(), ZONE_CREATE_HELPER::OnComplete(), operator!=(), BOOST_TEST_PRINT_NAMESPACE_OPEN::print_log_value< SHAPE_LINE_CHAIN >::operator()(), BITMAPCONV_INFO::outputOnePolygon(), SCH_SEXPR_PARSER::ParseSchematic(), PlotDrawingSheet(), PLOTTER::PlotPoly(), GERBER_PLOTTER::PlotPoly(), PointAlong(), PNS::pointInside2(), polygon_Convert(), SCH_SHAPE::Print(), LIB_SHAPE::print(), SCH_SHAPE::PrintBackground(), GERBER_DRAW_ITEM::PrintGerberPoly(), DS_DRAW_ITEM_POLYPOLYGONS::PrintWsItem(), DRC_RTREE::QueryColliding(), PNS::LINE_PLACER::removeLoops(), PNS::LINE_PLACER::rhWalkBase(), PNS::DIFF_PAIR_PLACER::routeHead(), DRC_TEST_PROVIDER_CONNECTION_WIDTH::Run(), PNS::OPTIMIZER::runSmartPads(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), PNS::LINE::SetShape(), PNS::shovedArea(), PNS::SHOVE::shoveLineFromLoneVia(), PNS::SHOVE::shoveLineToHullSet(), Simplify(), PNS::OPTIMIZER::smartPadsSingle(), PNS::COMPONENT_DRAGGER::Start(), PNS_KICAD_IFACE_BASE::syncTextItem(), unfracture(), SHAPE_POLY_SET::unfractureSingle(), PNS::MEANDER_SHAPE::updateBaseSegment(), PNS::LINE_PLACER::updatePStart(), PNS::LINE::Walkaround(), HYPERLYNX_EXPORTER::writeNetObjects(), GBR_TO_PCB_EXPORTER::writePcbPolygon(), and GBR_TO_PCB_EXPORTER::writePcbZoneItem().

◆ CPoints()

◆ CSegment()

const SEG SHAPE_LINE_CHAIN::CSegment ( int  aIndex) const
inline

Return a constant copy of the aIndex segment in the line chain.

Parameters
aIndexis the index of the segment in the line chain. Negative values are counted from the end (i.e. -1 means the last segment in the line chain).
Returns
a segment at aIndex in the line chain.

Definition at line 350 of file shape_line_chain.h.

351 {
352 if( aIndex < 0 )
353 aIndex += SegmentCount();
354
355 if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
356 return SEG( m_points[aIndex], m_points[0], aIndex );
357 else
358 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
359 }

References m_closed, m_points, and SegmentCount().

Referenced by PNS::NODE::Add(), PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::ArcHull(), PNS::LINE_PLACER::buildInitialLine(), PNS::LINE::ChangedArea(), PNS::PRESERVE_VERTEX_CONSTRAINT::Check(), CheckClearance(), PNS::NODE::CheckColliding(), PNS::DIFF_PAIR::CheckConnectionAngle(), PNS::checkGap(), PNS::MEANDERED_LINE::CheckSelfIntersections(), PNS::LINE::ClipToNearestObstacle(), PNS::closestProjectedPoint(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), PNS::coupledBypass(), PNS::DIFF_PAIR::CoupledLength(), PNS::LINE::CSegment(), PNS::LINE_PLACER::cursorDistMinimum(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::MEANDER_PLACER::doMove(), PNS::dragCornerInternal(), PNS::findCoupledVertices(), FindSegment(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), EDA_SHAPE::GetLength(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), GetSegment(), SHAPE_SIMPLE::GetSegment(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), PNS::HullIntersection(), Intersect(), isLine45Degree(), Length(), PNS::OPTIMIZER::mergeColinear(), PNS::OPTIMIZER::mergeDpStep(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeObtuse(), PNS::OPTIMIZER::mergeStep(), PNS::NODE::NearestObstacle(), NearestPoint(), NearestSegment(), PathLength(), PointAlong(), KIGFX::VIEW_OVERLAY::Polyline(), PNS::LINE_PLACER::reduceTail(), DRC_TEST_PROVIDER_EDGE_CLEARANCE::Run(), PNS::SegmentHull(), SelfIntersecting(), PNS::OPTIMIZER::smartPadsSingle(), PNS::LINE::snapDraggedCorner(), PNS::LINE::snapToNeighbourSegments(), Split(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::testShapeLineChain(), PNS::tightenSegment(), SHAPE_POLY_SET::unfractureSingle(), and HYPERLYNX_EXPORTER::writeBoardInfo().

◆ CShapes()

const std::vector< std::pair< ssize_t, ssize_t > > & SHAPE_LINE_CHAIN::CShapes ( ) const
inline
Returns
the vector of values indicating shape type and location.

Definition at line 429 of file shape_line_chain.h.

430 {
431 return m_shapes;
432 }

References m_shapes.

Referenced by Append(), and BOOST_AUTO_TEST_CASE().

◆ Distance()

int SHAPE_LINE_CHAIN::Distance ( const VECTOR2I aP,
bool  aOutlineOnly = false 
) const

Compute the minimum distance between the line chain and a point aP.

Parameters
aPthe point.
Returns
minimum distance.

Definition at line 878 of file shape_line_chain.cpp.

879{
880 return sqrt( SquaredDistance( aP, aOutlineOnly ) );
881}
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const

References SHAPE_LINE_CHAIN_BASE::SquaredDistance().

Referenced by PAD::GetBestAnchorPosition().

◆ EdgeContainingPoint()

int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint ( const VECTOR2I aP,
int  aAccuracy = 0 
) const
inherited

Check if point aP lies on an edge or vertex of the line chain.

Parameters
aPpoint to check
Returns
index of the first edge containing the point, otherwise negative

Definition at line 1679 of file shape_line_chain.cpp.

1680{
1681 if( !GetPointCount() )
1682 {
1683 return -1;
1684 }
1685 else if( GetPointCount() == 1 )
1686 {
1687 VECTOR2I dist = GetPoint(0) - aPt;
1688 return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
1689 }
1690
1691 for( size_t i = 0; i < GetSegmentCount(); i++ )
1692 {
1693 const SEG s = GetSegment( i );
1694
1695 if( s.A == aPt || s.B == aPt )
1696 return i;
1697
1698 if( s.Distance( aPt ) <= aAccuracy + 1 )
1699 return i;
1700 }
1701
1702 return -1;
1703}
virtual size_t GetPointCount() const =0
virtual size_t GetSegmentCount() const =0
virtual const VECTOR2I GetPoint(int aIndex) const =0
virtual const SEG GetSegment(int aIndex) const =0

References SEG::A, SEG::B, SEG::Distance(), SHAPE_LINE_CHAIN_BASE::GetPoint(), SHAPE_LINE_CHAIN_BASE::GetPointCount(), SHAPE_LINE_CHAIN_BASE::GetSegment(), SHAPE_LINE_CHAIN_BASE::GetSegmentCount(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by SHAPE_LINE_CHAIN_BASE::PointOnEdge().

◆ Find()

int SHAPE_LINE_CHAIN::Find ( const VECTOR2I aP,
int  aThreshold = 0 
) const

Search for point aP.

Parameters
aPis the point to be looked for.
Returns
the index of the corresponding point in the line chain or negative when not found.

Definition at line 951 of file shape_line_chain.cpp.

952{
953 for( int s = 0; s < PointCount(); s++ )
954 {
955 if( aThreshold == 0 )
956 {
957 if( CPoint( s ) == aP )
958 return s;
959 }
960 else
961 {
962 if( (CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
963 return s;
964 }
965 }
966
967 return -1;
968}

References CPoint(), and PointCount().

Referenced by PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::DRAGGER::dragViaMarkObstacles(), PNS::DRAGGER::dragViaWalkaround(), PNS::NODE::FindLinesBetweenJoints(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), Split(), PNS::LINE_PLACER::splitHeadTail(), and PNS::LINE::Walkaround().

◆ FindSegment()

int SHAPE_LINE_CHAIN::FindSegment ( const VECTOR2I aP,
int  aThreshold = 1 
) const

Search for segment containing point aP.

Parameters
aPis the point to be looked for.
Returns
index of the corresponding segment in the line chain or negative when not found.

Definition at line 971 of file shape_line_chain.cpp.

972{
973 for( int s = 0; s < SegmentCount(); s++ )
974 {
975 if( CSegment( s ).Distance( aP ) <= aThreshold )
976 return s;
977 }
978
979 return -1;
980}

References CSegment(), SEG::Distance(), and SegmentCount().

Referenced by PNS::MEANDER_PLACER_BASE::cutTunedLine(), and CADSTAR_SCH_ARCHIVE_LOADER::loadNets().

◆ fixIndicesRotation()

void SHAPE_LINE_CHAIN::fixIndicesRotation ( )
protected

Fix indices of this chain to ensure arcs are not split between the end and start indices.

Definition at line 213 of file shape_line_chain.cpp.

214{
215 wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
216
217 if( m_shapes.size() <= 1 || m_arcs.size() <= 1 )
218 return;
219
220 size_t rotations = 0;
221 size_t numPoints = m_points.size();
222
223 while( ArcIndex( 0 ) != SHAPE_IS_PT
224 && ArcIndex( 0 ) == ArcIndex( numPoints - 1 ) )
225 {
226 // Rotate right
227 std::rotate( m_points.rbegin(), m_points.rbegin() + 1, m_points.rend() );
228 std::rotate( m_shapes.rbegin(), m_shapes.rbegin() + 1, m_shapes.rend() );
229
230 // Sanity check - avoid infinite loops (NB: wxCHECK is not thread-safe)
231 if( rotations++ > m_shapes.size() )
232 return;
233 }
234}

References ArcIndex(), m_arcs, m_points, m_shapes, and SHAPE_IS_PT.

Referenced by mergeFirstLastPointIfNeeded(), and SHAPE_LINE_CHAIN().

◆ Format()

const std::string SHAPE_LINE_CHAIN::Format ( bool  aCplusPlus = true) const
overridevirtual

Reimplemented from SHAPE.

Definition at line 1983 of file shape_line_chain.cpp.

1984{
1985 std::stringstream ss;
1986
1987 ss << "SHAPE_LINE_CHAIN( { ";
1988
1989 for( int i = 0; i < PointCount(); i++ )
1990 {
1991 ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
1992
1993 if( i != PointCount() -1 )
1994 ss << ", ";
1995 }
1996
1997 ss << "}, " << ( m_closed ? "true" : "false" );
1998 ss << " );";
1999
2000 return ss.str();
2001
2002 /* fixme: arcs
2003 for( size_t i = 0; i < m_arcs.size(); i++ )
2004 ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
2005 << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
2006 << m_arcs[i].GetCentralAngle().AsDegrees();
2007
2008 return ss.str();*/
2009}

References m_closed, m_points, and PointCount().

Referenced by PNS::SHOVE::shoveLineToHullSet().

◆ GenerateBBoxCache()

void SHAPE_LINE_CHAIN::GenerateBBoxCache ( ) const
inline

Definition at line 446 of file shape_line_chain.h.

447 {
449
450 if( m_width != 0 )
452 }

References BOX2< Vec >::Compute(), BOX2< Vec >::Inflate(), m_bbox, m_points, and m_width.

Referenced by SHAPE_POLY_SET::BuildBBoxCaches().

◆ GetCachedBBox()

BOX2I * SHAPE_LINE_CHAIN::GetCachedBBox ( ) const
inlineoverridevirtual

Reimplemented from SHAPE_LINE_CHAIN_BASE.

Definition at line 454 of file shape_line_chain.h.

455 {
456 return &m_bbox;
457 }

References m_bbox.

◆ GetClearance()

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

Return the actual minimum distance between two shapes.

Return values
distancein IU

Definition at line 49 of file shape.cpp.

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

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

◆ GetIndexableSubshapeCount()

virtual size_t SHAPE_BASE::GetIndexableSubshapeCount ( ) const
inlinevirtualinherited

Reimplemented in SHAPE_COMPOUND, and SHAPE_POLY_SET.

Definition at line 110 of file shape.h.

110{ return 0; }

Referenced by SHAPE::GetClearance().

◆ GetIndexableSubshapes()

virtual void SHAPE_BASE::GetIndexableSubshapes ( std::vector< const SHAPE * > &  aSubshapes) const
inlinevirtualinherited

Reimplemented in SHAPE_COMPOUND, and SHAPE_POLY_SET.

Definition at line 112 of file shape.h.

112{ }

Referenced by SHAPE_COMPOUND::AddShape(), SHAPE::GetClearance(), and ROUTER_PREVIEW_ITEM::ViewDraw().

◆ GetPoint()

◆ GetPointCount()

◆ GetSegment()

virtual const SEG SHAPE_LINE_CHAIN::GetSegment ( int  aIndex) const
inlineoverridevirtual

Implements SHAPE_LINE_CHAIN_BASE.

Definition at line 866 of file shape_line_chain.h.

866{ return CSegment(aIndex); }

References CSegment().

Referenced by Collide(), Collide(), PCB_GRID_HELPER::computeAnchors(), and ConvertOutlineToPolygon().

◆ GetSegmentCount()

virtual size_t SHAPE_LINE_CHAIN::GetSegmentCount ( ) const
inlineoverridevirtual

◆ HasIndexableSubshapes()

virtual bool SHAPE_BASE::HasIndexableSubshapes ( ) const
inlinevirtualinherited

Reimplemented in SHAPE_COMPOUND, and SHAPE_POLY_SET.

Definition at line 105 of file shape.h.

106 {
107 return false;
108 }

Referenced by SHAPE_COMPOUND::AddShape(), and ROUTER_PREVIEW_ITEM::ViewDraw().

◆ Insert() [1/2]

void SHAPE_LINE_CHAIN::Insert ( size_t  aVertex,
const SHAPE_ARC aArc 
)

Step 1: Find the position for the new arc in the existing arc vector

Step 2: Add the arc polyline points to the chain

Step 3: Add the vector of indices to the shape vector

Definition at line 1381 of file shape_line_chain.cpp.

1382{
1383 wxCHECK( aVertex < m_points.size(), /* void */ );
1384
1385 if( aVertex > 0 && IsPtOnArc( aVertex ) )
1386 splitArc( aVertex );
1387
1389 ssize_t arc_pos = m_arcs.size();
1390
1391 for( auto arc_it = m_shapes.rbegin() ;
1392 arc_it != m_shapes.rend() + aVertex;
1393 arc_it++ )
1394 {
1395 if( *arc_it != SHAPES_ARE_PT )
1396 {
1397 arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1398 arc_pos++;
1399 }
1400 }
1401
1402 //Increment all arc indices before inserting the new arc
1403 for( auto& sh : m_shapes )
1404 {
1405 alg::run_on_pair( sh,
1406 [&]( ssize_t& aIndex )
1407 {
1408 if( aIndex >= arc_pos )
1409 aIndex++;
1410 } );
1411 }
1412
1413 SHAPE_ARC arcCopy( aArc );
1414 arcCopy.SetWidth( 0 );
1415 m_arcs.insert( m_arcs.begin() + arc_pos, arcCopy );
1416
1418 //@todo need to check we aren't creating duplicate points at start or end
1419 auto& chain = aArc.ConvertToPolyline();
1420 m_points.insert( m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1421
1423 //@todo need to check we aren't creating duplicate points at start or end
1424 std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1425 { arc_pos, SHAPE_IS_PT } );
1426
1427 m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1428 assert( m_shapes.size() == m_points.size() );
1429}
bool IsPtOnArc(size_t aPtIndex) const
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.

References SHAPE_ARC::ConvertToPolyline(), IsPtOnArc(), m_arcs, m_points, m_shapes, alg::run_on_pair(), SHAPE_ARC::SetWidth(), SHAPES_ARE_PT, and splitArc().

◆ Insert() [2/2]

void SHAPE_LINE_CHAIN::Insert ( size_t  aVertex,
const VECTOR2I aP 
)

Definition at line 1360 of file shape_line_chain.cpp.

1361{
1362 if( aVertex == m_points.size() )
1363 {
1364 Append( aP );
1365 return;
1366 }
1367
1368 wxCHECK( aVertex < m_points.size(), /* void */ );
1369
1370 if( aVertex > 0 && IsPtOnArc( aVertex ) )
1371 splitArc( aVertex );
1372
1373 //@todo need to check we aren't creating duplicate points
1374 m_points.insert( m_points.begin() + aVertex, aP );
1375 m_shapes.insert( m_shapes.begin() + aVertex, SHAPES_ARE_PT );
1376
1377 assert( m_shapes.size() == m_points.size() );
1378}

References Append(), IsPtOnArc(), m_points, m_shapes, SHAPES_ARE_PT, and splitArc().

Referenced by EE_POINT_EDITOR::addCorner(), PNS::TOPOLOGY::AssembleTuningPath(), PNS::LINE::dragCorner45(), PNS::LINE::dragCornerFree(), CONVERT_TOOL::makePolysFromChainedSegs(), Replace(), and Split().

◆ Intersect() [1/2]

int SHAPE_LINE_CHAIN::Intersect ( const SEG aSeg,
INTERSECTIONS aIp 
) const

Find all intersection points between our line chain and the segment aSeg.

Parameters
aSegis the segment chain to find intersections with.
aIpis the reference to a vector to store found intersections. Intersection points are sorted with increasing distances from point aSeg.a.
Returns
the number of intersections found.

Definition at line 1447 of file shape_line_chain.cpp.

1448{
1449 for( int s = 0; s < SegmentCount(); s++ )
1450 {
1451 OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
1452
1453 if( p )
1454 {
1455 INTERSECTION is;
1456 is.valid = true;
1457 is.index_our = s;
1458 is.index_their = -1;
1459 is.is_corner_our = is.is_corner_their = false;
1460 is.p = *p;
1461 aIp.push_back( is );
1462 }
1463 }
1464
1465 compareOriginDistance comp( aSeg.A );
1466 sort( aIp.begin(), aIp.end(), comp );
1467
1468 return aIp.size();
1469}
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
Definition: seg.cpp:188
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39

References SEG::A, CSegment(), SHAPE_LINE_CHAIN::INTERSECTION::index_our, SHAPE_LINE_CHAIN::INTERSECTION::index_their, SEG::Intersect(), SHAPE_LINE_CHAIN::INTERSECTION::is_corner_our, SHAPE_LINE_CHAIN::INTERSECTION::is_corner_their, SHAPE_LINE_CHAIN::INTERSECTION::p, SegmentCount(), and SHAPE_LINE_CHAIN::INTERSECTION::valid.

Referenced by PNS::OPTIMIZER::customBreakouts(), TEARDROP_MANAGER::findAnchorPointsOnTrack(), PNS::LINE_PLACER::handleSelfIntersections(), PNS::HullIntersection(), Intersects(), and CADSTAR_SCH_ARCHIVE_LOADER::loadNets().

◆ Intersect() [2/2]

int SHAPE_LINE_CHAIN::Intersect ( const SHAPE_LINE_CHAIN aChain,
INTERSECTIONS aIp,
bool  aExcludeColinearAndTouching = false,
BOX2I aChainBBox = nullptr 
) const

Find all intersection points between our line chain and the line chain aChain.

Parameters
aChainis the line chain to find intersections with.
aIpis reference to a vector to store found intersections. Intersection points are sorted with increasing path lengths from the starting point of aChain.
Returns
the number of intersections found.

Definition at line 1487 of file shape_line_chain.cpp.

1489{
1490 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.BBox();
1491
1492 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1493 {
1494 const SEG& a = CSegment( s1 );
1495 const BOX2I bb_cur( a.A, a.B - a.A );
1496
1497 if( !bb_other.Intersects( bb_cur ) )
1498 continue;
1499
1500 for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
1501 {
1502 const SEG& b = aChain.CSegment( s2 );
1503 INTERSECTION is;
1504
1505 is.index_our = s1;
1506 is.index_their = s2;
1507 is.is_corner_our = false;
1508 is.is_corner_their = false;
1509 is.valid = true;
1510
1511 OPT_VECTOR2I p = a.Intersect( b );
1512
1513 bool coll = a.Collinear( b );
1514
1515 if( coll && ! aExcludeColinearAndTouching )
1516 {
1517 if( a.Contains( b.A ) )
1518 {
1519 is.p = b.A;
1520 is.is_corner_their = true;
1521 addIntersection(aIp, PointCount(), is);
1522 }
1523
1524 if( a.Contains( b.B ) )
1525 {
1526 is.p = b.B;
1527 is.index_their++;
1528 is.is_corner_their = true;
1529 addIntersection( aIp, PointCount(), is );
1530 }
1531
1532 if( b.Contains( a.A ) )
1533 {
1534 is.p = a.A;
1535 is.is_corner_our = true;
1536 addIntersection( aIp, PointCount(), is );
1537 }
1538
1539 if( b.Contains( a.B ) )
1540 {
1541 is.p = a.B;
1542 is.index_our++;
1543 is.is_corner_our = true;
1544 addIntersection( aIp, PointCount(), is );
1545 }
1546 }
1547 else if( p )
1548 {
1549 is.p = *p;
1550 is.is_corner_our = false;
1551 is.is_corner_their = false;
1552
1553 int distA = ( b.A - *p ).EuclideanNorm();
1554 int distB = ( b.B - *p ).EuclideanNorm();
1555
1556 if( p == a.A )
1557 {
1558 is.is_corner_our = true;
1559 }
1560
1561 if( p == a.B )
1562 {
1563 is.is_corner_our = true;
1564 is.index_our++;
1565 }
1566
1567 if( p == b.A )
1568 {
1569 is.is_corner_their = true;
1570 }
1571
1572 if( p == b.B )
1573 {
1574 is.is_corner_their = true;
1575 is.index_their++;
1576 }
1577
1578 addIntersection( aIp, PointCount(), is );
1579 }
1580 }
1581 }
1582
1583 return aIp.size();
1584}
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:269
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:269
bool Contains(const SEG &aSeg) const
Definition: seg.h:307
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
static void addIntersection(SHAPE_LINE_CHAIN::INTERSECTIONS &aIps, int aPc, const SHAPE_LINE_CHAIN::INTERSECTION &aP)
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129

References SEG::A, addIntersection(), SEG::B, BBox(), SEG::Collinear(), SEG::Contains(), CSegment(), EuclideanNorm(), SHAPE_LINE_CHAIN::INTERSECTION::index_our, SHAPE_LINE_CHAIN::INTERSECTION::index_their, SEG::Intersect(), BOX2< Vec >::Intersects(), SHAPE_LINE_CHAIN::INTERSECTION::is_corner_our, SHAPE_LINE_CHAIN::INTERSECTION::is_corner_their, SHAPE_LINE_CHAIN::INTERSECTION::p, PointCount(), SegmentCount(), and SHAPE_LINE_CHAIN::INTERSECTION::valid.

◆ Intersects()

bool SHAPE_LINE_CHAIN::Intersects ( const SHAPE_LINE_CHAIN aChain) const

Definition at line 2031 of file shape_line_chain.cpp.

2032{
2034 return Intersect( aChain, dummy ) != 0;
2035}
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
std::vector< INTERSECTION > INTERSECTIONS
std::vector< FAB_LAYER_COLOR > dummy

References dummy, and Intersect().

Referenced by PNS::DIFF_PAIR::BuildInitial().

◆ IsArcEnd()

bool SHAPE_LINE_CHAIN::IsArcEnd ( size_t  aIndex) const
inline

Definition at line 860 of file shape_line_chain.h.

861 {
862 return ( IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex ) ) );
863 }

References IsArcSegment(), IsPtOnArc(), and IsSharedPt().

Referenced by BOOST_AUTO_TEST_CASE(), NearestPoint(), and splitArc().

◆ IsArcSegment()

bool SHAPE_LINE_CHAIN::IsArcSegment ( size_t  aSegment) const
inline

Definition at line 828 of file shape_line_chain.h.

829 {
830 /*
831 * A segment is part of an arc except in the special case of two arcs next to each other
832 * but without a shared vertex. Here there is a segment between the end of the first arc
833 * and the start of the second arc.
834 */
835 size_t nextIdx = aSegment + 1;
836
837 if( nextIdx > m_shapes.size() - 1 )
838 {
839 if( nextIdx == m_shapes.size() && m_closed )
840 nextIdx = 0; // segment between end point and first point
841 else
842 return false;
843 }
844
845 return ( IsPtOnArc( aSegment )
846 && ( IsSharedPt( aSegment )
847 || m_shapes[aSegment].first == m_shapes[nextIdx].first ) );
848 }

References IsPtOnArc(), IsSharedPt(), m_closed, and m_shapes.

Referenced by PNS::NODE::Add(), Append(), PNS::LINE::ClipToNearestObstacle(), Collide(), Collide(), PNS::MEANDER_PLACER::doMove(), PNS::LINE::dragCornerFree(), IsArcEnd(), IsArcStart(), isLine45Degree(), Length(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeStep(), PNS::DP_MEANDER_PLACER::Move(), NearestPoint(), PNS::SHOVE::ShoveObstacleLine(), Slice(), and Split().

◆ IsArcStart()

bool SHAPE_LINE_CHAIN::IsArcStart ( size_t  aIndex) const
inline

Definition at line 851 of file shape_line_chain.h.

852 {
853 if( aIndex == 0 )
854 return IsPtOnArc( aIndex );
855
856 return ( IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex - 1 ) ) );
857 }

References IsArcSegment(), IsPtOnArc(), and IsSharedPt().

Referenced by BOOST_AUTO_TEST_CASE(), ALTIUM_PCB::HelperCreateBoardOutline(), NearestPoint(), Slice(), and splitArc().

◆ IsClosed()

◆ IsNull()

bool SHAPE::IsNull ( ) const
inlineinherited

Return true if the shape is a null shape.

Return values
trueif null :-)

Definition at line 163 of file shape.h.

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

References SHAPE_BASE::m_type, and SH_NULL.

◆ IsPtOnArc()

◆ IsSharedPt()

bool SHAPE_LINE_CHAIN::IsSharedPt ( size_t  aIndex) const
inline

Test if a point is shared between multiple shapes.

Parameters
aIndex
Returns

Definition at line 814 of file shape_line_chain.h.

815 {
816 return aIndex < m_shapes.size()
817 && m_shapes[aIndex].first != SHAPE_IS_PT
818 && m_shapes[aIndex].second != SHAPE_IS_PT;
819 }

References m_shapes, and SHAPE_IS_PT.

Referenced by ArcIndex(), BOOST_AUTO_TEST_CASE(), IsArcEnd(), IsArcSegment(), IsArcStart(), GEOM_TEST::IsOutlineValid(), Remove(), RemoveShape(), reversedArcIndex(), and splitArc().

◆ IsSolid()

bool SHAPE_LINE_CHAIN::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 774 of file shape_line_chain.h.

775 {
776 return false;
777 }

◆ Length()

long long int SHAPE_LINE_CHAIN::Length ( ) const

Return length of the line chain in Euclidean metric.

Returns
the length of the line chain.

Definition at line 687 of file shape_line_chain.cpp.

688{
689 long long int l = 0;
690
691 for( int i = 0; i < SegmentCount(); i++ )
692 {
693 // Only include segments that aren't part of arc shapes
694 if( !IsArcSegment(i) )
695 l += CSegment( i ).Length();
696 }
697
698 for( int i = 0; i < ArcCount(); i++ )
699 l += CArcs()[i].GetLength();
700
701 return l;
702}
int Length() const
Return the length (this).
Definition: seg.h:326
const std::vector< SHAPE_ARC > & CArcs() const

References ArcCount(), CArcs(), CSegment(), IsArcSegment(), SEG::Length(), and SegmentCount().

Referenced by PNS::COST_ESTIMATOR::Add(), PNS::LINE_PLACER::clipAndCheckCollisions(), PNS::MEANDER_SHAPE::CurrentLength(), PNS::MEANDER_PLACER::doMove(), PNS::LINE::dragSegment45(), PNS::OPTIMIZER::fanoutCleanup(), PNS::DP_MEANDER_PLACER::Move(), PNS::SHOVE::onCollidingArc(), PNS::SHOVE::onCollidingSegment(), PNS::COST_ESTIMATOR::Remove(), PNS::COST_ESTIMATOR::Replace(), PNS::LINE_PLACER::rhWalkBase(), PNS::WALKAROUND::Route(), PNS::SHOVE::shoveLineFromLoneVia(), PNS::DIFF_PAIR::Skew(), PNS::OPTIMIZER::smartPadsSingle(), PNS::DIFF_PAIR::TotalLength(), and PNS::DRAGGER::tryWalkaround().

◆ mergeFirstLastPointIfNeeded()

void SHAPE_LINE_CHAIN::mergeFirstLastPointIfNeeded ( )
protected

Merge the first and last point if they are the same and this chain is closed.

Definition at line 237 of file shape_line_chain.cpp.

238{
239 if( m_closed )
240 {
241 if( m_points.size() > 1 && m_points.front() == m_points.back() )
242 {
243 if( m_shapes.back() != SHAPES_ARE_PT )
244 {
245 m_shapes.front().second = m_shapes.front().first;
246 m_shapes.front().first = m_shapes.back().first;
247 }
248
249 m_points.pop_back();
250 m_shapes.pop_back();
251
253 }
254 }
255}

References fixIndicesRotation(), m_closed, m_points, m_shapes, and SHAPES_ARE_PT.

Referenced by Append(), and SetClosed().

◆ Mirror() [1/2]

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

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

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

Definition at line 705 of file shape_line_chain.cpp.

706{
707 for( auto& pt : m_points )
708 {
709 if( aX )
710 pt.x = -pt.x + 2 * aRef.x;
711
712 if( aY )
713 pt.y = -pt.y + 2 * aRef.y;
714 }
715
716 for( auto& arc : m_arcs )
717 arc.Mirror( aX, aY, aRef );
718}

References m_arcs, m_points, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by GBR_TO_PCB_EXPORTER::export_flashed_copper_item(), and PNS::MEANDER_SHAPE::genMeanderShape().

◆ Mirror() [2/2]

void SHAPE_LINE_CHAIN::Mirror ( const SEG axis)

Mirror the line points using an given axis.

Parameters
axisis the axis on which to mirror.

Definition at line 721 of file shape_line_chain.cpp.

722{
723 for( auto& pt : m_points )
724 pt = axis.ReflectPoint( pt );
725
726 for( auto& arc : m_arcs )
727 arc.Mirror( axis );
728}
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:283

References m_arcs, m_points, and SEG::ReflectPoint().

◆ Move()

void SHAPE_LINE_CHAIN::Move ( const VECTOR2I aVector)
inlineoverridevirtual

Implements SHAPE.

Definition at line 739 of file shape_line_chain.h.

740 {
741 for( auto& pt : m_points )
742 pt += aVector;
743
744 for( auto& arc : m_arcs )
745 arc.Move( aVector );
746
747 m_bbox.Move( aVector );
748 }
void Move(const Vec &aMoveVector)
Move the rectangle by the aMoveVector.
Definition: box2.h:111

References m_arcs, m_bbox, m_points, and BOX2< Vec >::Move().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), PAD::BuildEffectiveShapes(), PCB_GRID_HELPER::computeAnchors(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), EDA_SHAPE::hitTest(), PCB_SELECTION_TOOL::hitTestDistance(), EDA_SHAPE::makeEffectiveShapes(), and SHAPE_SIMPLE::Move().

◆ NearestPoint() [1/2]

const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint ( const SEG aSeg,
int &  dist 
) const

Find a point on the line chain that is closest to the line defined by the points of segment aSeg, also returns the distance.

Parameters
aSegis the segment defining the line.
distis the reference receiving the distance to the nearest point.
Returns
the nearest point.

Definition at line 1936 of file shape_line_chain.cpp.

1937{
1938 if( PointCount() == 0 )
1939 {
1940 // The only right answer here is "don't crash".
1941 return { 0, 0 };
1942 }
1943
1944 int nearest = 0;
1945
1946 dist = INT_MAX;
1947
1948 for( int i = 0; i < PointCount(); i++ )
1949 {
1950 int d = aSeg.LineDistance( CPoint( i ) );
1951
1952 if( d < dist )
1953 {
1954 dist = d;
1955 nearest = i;
1956 }
1957 }
1958
1959 return CPoint( nearest );
1960}
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.cpp:331

References CPoint(), SEG::LineDistance(), and PointCount().

◆ NearestPoint() [2/2]

const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint ( const VECTOR2I aP,
bool  aAllowInternalShapePoints = true 
) const

Find a point on the line chain that is closest to point aP.

Parameters
aPis the point to find.
aAllowInternalShapePointsif false will not return points internal to an arc (i.e. only the arc endpoints are possible candidates)
Returns
the nearest point.

Definition at line 1878 of file shape_line_chain.cpp.

1880{
1881 if( PointCount() == 0 )
1882 {
1883 // The only right answer here is "don't crash".
1884 return { 0, 0 };
1885 }
1886
1887 int min_d = INT_MAX;
1888 int nearest = 0;
1889
1890 for( int i = 0; i < SegmentCount(); i++ )
1891 {
1892 int d = CSegment( i ).Distance( aP );
1893
1894 if( d < min_d )
1895 {
1896 min_d = d;
1897 nearest = i;
1898 }
1899 }
1900
1901 if( !aAllowInternalShapePoints )
1902 {
1903 //Snap to arc end points if the closest found segment is part of an arc segment
1904 if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
1905 {
1906 VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
1907 VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
1908
1909 if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
1910 nearest++;
1911
1912 // Is this the start or end of an arc? If so, return it directly
1913 if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
1914 {
1915 return m_points[nearest];
1916 }
1917 else
1918 {
1919 const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
1920 VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
1921 VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
1922
1923 if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
1924 return nearestArc.GetP1();
1925 else
1926 return nearestArc.GetP0();
1927 }
1928
1929 }
1930 }
1931
1932 return CSegment( nearest ).NearestPoint( aP );
1933}
bool IsArcEnd(size_t aIndex) const
bool IsArcStart(size_t aIndex) const
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293

References SEG::A, Arc(), ArcIndex(), SEG::B, CSegment(), SEG::Distance(), VECTOR2< T >::EuclideanNorm(), SHAPE_ARC::GetP0(), SHAPE_ARC::GetP1(), IsArcEnd(), IsArcSegment(), IsArcStart(), m_points, SEG::NearestPoint(), PointCount(), and SegmentCount().

Referenced by FOOTPRINT::CheckNetTies(), PCB_GRID_HELPER::computeAnchors(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), CADSTAR_SCH_ARCHIVE_LOADER::loadBusses(), PNS::MoveDiagonal(), and PNS::DRAGGER::optimizeAndUpdateDraggedLine().

◆ NearestSegment()

int SHAPE_LINE_CHAIN::NearestSegment ( const VECTOR2I aP) const

Find the segment nearest the given point.

Parameters
aPis the point to compare with.
Returns
the index of the segment closest to the point.

Definition at line 1963 of file shape_line_chain.cpp.

1964{
1965 int min_d = INT_MAX;
1966 int nearest = 0;
1967
1968 for( int i = 0; i < SegmentCount(); i++ )
1969 {
1970 int d = CSegment( i ).Distance( aP );
1971
1972 if( d < min_d )
1973 {
1974 min_d = d;
1975 nearest = i;
1976 }
1977 }
1978
1979 return nearest;
1980}

References CSegment(), SEG::Distance(), and SegmentCount().

Referenced by PNS::LINE::ClipToNearestObstacle(), and SCH_SHEET_PIN::ConstrainOnEdge().

◆ NewFacet()

FACET * SHAPE::NewFacet ( )
inherited

Definition at line 695 of file wrlfacet.cpp.

696{
697 FACET* fp = new FACET;
698 facets.push_back( fp );
699 return fp;
700}
Definition: wrlfacet.h:43

References SHAPE::facets.

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

◆ NextShape()

int SHAPE_LINE_CHAIN::NextShape ( int  aPointIndex,
bool  aForwards = true 
) const

Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.

If aPointIndex is the start of a segment, this will be ( aPointIndex + 1 ). If aPointIndex is part of an arc, this will be the index of the start of the next shape after the arc, in other words, the last point of the arc.

Parameters
aPointIndexis a vertex in the chain.
aForwardsis true if the next shape is desired, false for previous shape.
Returns
the vertex index of the start of the next shape after aPoint's shape or -1 if the end was reached.

Definition at line 1033 of file shape_line_chain.cpp.

1034{
1035 if( aPointIndex < 0 )
1036 aPointIndex += PointCount();
1037
1038 int lastIndex = PointCount() - 1;
1039
1040 // First or last point?
1041 if( ( aForwards && aPointIndex == lastIndex ) ||
1042 ( !aForwards && aPointIndex == 0 ) )
1043 {
1044 return -1; // we don't want to wrap around
1045 }
1046
1047 int delta = aForwards ? 1 : -1;
1048
1049 if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
1050 return aPointIndex + delta;
1051
1052 int arcStart = aPointIndex;
1053
1054 // The second element should only get populated when the point is shared between two shapes.
1055 // If not a shared point, then the index should always go on the first element.
1056 assert( m_shapes[aPointIndex].first != SHAPE_IS_PT );
1057
1058 // Start with the assumption the point is shared
1059 auto arcIndex = [&]( int aIndex ) -> ssize_t
1060 {
1061 if( aForwards )
1062 return ArcIndex( aIndex );
1063 else
1064 return reversedArcIndex( aIndex );
1065 };
1066
1067 ssize_t currentArcIdx = arcIndex( aPointIndex );
1068
1069 // Now skip the rest of the arc
1070 while( aPointIndex < lastIndex && aPointIndex >= 0 && arcIndex( aPointIndex ) == currentArcIdx )
1071 aPointIndex += delta;
1072
1073 if( aPointIndex == lastIndex )
1074 {
1075 if( !m_closed && arcIndex( aPointIndex ) == currentArcIdx )
1076 return -1;
1077 else
1078 return lastIndex; // Segment between last point and the start
1079 }
1080
1081 bool indexStillOnArc = alg::pair_contains( m_shapes[aPointIndex], currentArcIdx );
1082
1083 // We want the last vertex of the arc if the initial point was the start of one
1084 // Well-formed arcs should generate more than one point to travel above
1085 if( aPointIndex - arcStart > 1 && !indexStillOnArc )
1086 aPointIndex -= delta;
1087
1088 return aPointIndex;
1089}
ssize_t reversedArcIndex(size_t aSegment) const
Return the arc index for the given segment index, looking backwards.
bool pair_contains(const std::pair< _Type, _Type > __pair, _Value __value)
Returns true if either of the elements in an std::pair contains the given value.
Definition: kicad_algo.h:112
constexpr int delta

References ArcIndex(), delta, m_closed, m_shapes, alg::pair_contains(), PointCount(), reversedArcIndex(), SHAPE_IS_PT, and SHAPES_ARE_PT.

Referenced by PNS::LINE::ClipVertexRange(), PNS::MEANDER_PLACER::doMove(), ALTIUM_PCB::HelperCreateBoardOutline(), PNS::DP_MEANDER_PLACER::Move(), PrevShape(), and Slice().

◆ operator!=()

bool SHAPE_LINE_CHAIN::operator!= ( const SHAPE_LINE_CHAIN aRhs) const
inline

Definition at line 723 of file shape_line_chain.h.

724 {
725 if( PointCount() != aRhs.PointCount() )
726 return true;
727
728 for( int i = 0; i < PointCount(); i++ )
729 {
730 if( CPoint( i ) != aRhs.CPoint( i ) )
731 return true;
732 }
733
734 return false;
735 }

References CPoint(), and PointCount().

◆ operator=()

SHAPE_LINE_CHAIN & SHAPE_LINE_CHAIN::operator= ( const SHAPE_LINE_CHAIN )
default

◆ Parse()

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

Reimplemented from SHAPE.

Definition at line 2044 of file shape_line_chain.cpp.

2045{
2046 size_t n_pts;
2047 size_t n_arcs;
2048
2049 m_points.clear();
2050 aStream >> n_pts;
2051
2052 // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
2053 if( n_pts > aStream.str().size() )
2054 return false;
2055
2056 aStream >> m_closed;
2057 aStream >> n_arcs;
2058
2059 if( n_arcs > aStream.str().size() )
2060 return false;
2061
2062 for( size_t i = 0; i < n_pts; i++ )
2063 {
2064 int x, y;
2065 ssize_t ind;
2066 aStream >> x;
2067 aStream >> y;
2068 m_points.emplace_back( x, y );
2069
2070 aStream >> ind;
2071 m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
2072 }
2073
2074 for( size_t i = 0; i < n_arcs; i++ )
2075 {
2076 VECTOR2I p0, pc;
2077 double angle;
2078
2079 aStream >> pc.x;
2080 aStream >> pc.y;
2081 aStream >> p0.x;
2082 aStream >> p0.y;
2083 aStream >> angle;
2084
2085 m_arcs.emplace_back( pc, p0, EDA_ANGLE( angle, DEGREES_T ) );
2086 }
2087
2088 return true;
2089}
@ DEGREES_T
Definition: eda_angle.h:31
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)

References PNS::angle(), DEGREES_T, m_arcs, m_closed, m_points, m_shapes, SHAPE_IS_PT, VECTOR2< T >::x, and VECTOR2< T >::y.

◆ PathLength()

int SHAPE_LINE_CHAIN::PathLength ( const VECTOR2I aP,
int  aIndex = -1 
) const

Compute the walk path length from the beginning of the line chain and the point aP belonging to our line.

Returns
the path length in Euclidean metric or -1 if aP does not belong to the line chain.

Definition at line 1587 of file shape_line_chain.cpp.

1588{
1589 int sum = 0;
1590
1591 for( int i = 0; i < SegmentCount(); i++ )
1592 {
1593 const SEG seg = CSegment( i );
1594 bool indexMatch = true;
1595
1596 if( aIndex >= 0 )
1597 {
1598 if( aIndex == SegmentCount() )
1599 {
1600 indexMatch = ( i == SegmentCount() - 1 );
1601 }
1602 else
1603 {
1604 indexMatch = ( i == aIndex );
1605 }
1606 }
1607
1608 if( indexMatch )
1609 {
1610 sum += ( aP - seg.A ).EuclideanNorm();
1611 return sum;
1612 }
1613 else
1614 sum += seg.Length();
1615 }
1616
1617 return -1;
1618}

References SEG::A, CSegment(), EuclideanNorm(), SEG::Length(), and SegmentCount().

Referenced by PNS::NODE::NearestObstacle().

◆ PointAlong()

const VECTOR2I SHAPE_LINE_CHAIN::PointAlong ( int  aPathLength) const

Definition at line 2092 of file shape_line_chain.cpp.

2093{
2094 int total = 0;
2095
2096 if( aPathLength == 0 )
2097 return CPoint( 0 );
2098
2099 for( int i = 0; i < SegmentCount(); i++ )
2100 {
2101 const SEG& s = CSegment( i );
2102 int l = s.Length();
2103
2104 if( total + l >= aPathLength )
2105 {
2106 VECTOR2I d( s.B - s.A );
2107 return s.A + d.Resize( aPathLength - total );
2108 }
2109
2110 total += l;
2111 }
2112
2113 return CPoint( -1 );
2114}
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:378

References SEG::A, SEG::B, CPoint(), CSegment(), SEG::Length(), VECTOR2< T >::Resize(), and SegmentCount().

◆ PointCount()

int SHAPE_LINE_CHAIN::PointCount ( ) const
inline

Return the number of points (vertices) in this line chain.

Returns
the number of points.

Definition at line 320 of file shape_line_chain.h.

321 {
322 return m_points.size();
323 }

References m_points.

Referenced by LABEL_MANAGER::Add(), POLYGON_GEOM_MANAGER::AddPoint(), SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::AddPolyline(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), PNS_LOG_VIEWER_OVERLAY::AnnotatedPolyline(), Append(), CADSTAR_ARCHIVE_PARSER::VERTEX::AppendToChain(), PNS::LINE::AppendVia(), ArePolylineEndPointsNearCircle(), ArePolylineMidPointsNearCircle(), PNS::NODE::AssembleLine(), PNS::TOPOLOGY::AssembleTuningPath(), BOOST_AUTO_TEST_CASE(), build45DegLeader(), BuildConvexHull(), PAD::BuildEffectivePolygon(), PAD::BuildEffectiveShapes(), PNS_LOG_VIEWER_FRAME::buildListTree(), PNS::LINE::ChangedArea(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), CheckClearance(), CN_VISITOR::checkZoneZoneConnection(), CLastPoint(), PNS::LINE::ClipVertexRange(), convertPolygon(), ALTIUM_PCB::ConvertShapeBasedRegions6ToBoardItem(), ALTIUM_PCB::ConvertShapeBasedRegions6ToBoardItemOnLayer(), ALTIUM_PCB::ConvertShapeBasedRegions6ToFootprintItem(), ALTIUM_PCB::ConvertShapeBasedRegions6ToFootprintItemOnLayer(), convertToClipper(), convertToClipper2(), PNS::coupledBypass(), CPoint(), PolygonTriangulation::createList(), POLYGON_TEST::createList(), CreatePadsShapesSection(), STEP_PCB_MODEL::CreatePCB(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), PNS::LINE_PLACER::cursorDistMinimum(), POLYGON_GEOM_MANAGER::DeleteLastCorner(), DIALOG_PAD_PRIMITIVE_POLY_PROPS::doValidate(), PNS::LINE::dragCornerFree(), PNS::dragCornerInternal(), PNS::LINE::dragSegment45(), PNS::DRAGGER::dragWalkaround(), KIGFX::PCB_PAINTER::draw(), KIGFX::GERBVIEW_PAINTER::draw(), KIGFX::CAIRO_GAL_BASE::drawPoly(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolyline(), KIGFX::PREVIEW::POLYGON_ITEM::drawPreviewShape(), KIGFX::CAIRO_GAL_BASE::DrawSegmentChain(), KIGFX::OPENGL_GAL::DrawSegmentChain(), EDA_SHAPE::DupPolyPointsList(), EXPORTER_PCB_VRML::ExportVrmlBoard(), EXPORTER_PCB_VRML::ExportVrmlPolygonSet(), DSN::SPECCTRA_DB::fillBOUNDARY(), AR_AUTOPLACER::fillMatrix(), Find(), PNS::LINE_PLACER::FixRoute(), GERBER_PLOTTER::FlashPadChamferRoundRect(), DXF_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), HPGL_PLOTTER::FlashPadRoundRect(), PSLIKE_PLOTTER::FlashPadRoundRect(), Format(), PCB_PLUGIN::formatPolyPts(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), GetPointCount(), SHAPE_SIMPLE::GetPointCount(), CADSTAR_PCB_ARCHIVE_LOADER::getPolySetFromCadstarShape(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), SHAPE_POLY_SET::GetRelativeIndices(), PNS::MOUSE_TRAIL_TRACER::GetTrailLeadVector(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), ALTIUM_PCB::HelperCreateBoardOutline(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), PNS::HullIntersection(), Intersect(), GEOM_TEST::IsOutlineValid(), POLYGON_GEOM_MANAGER::IsPolygonInProgress(), EDA_SHAPE::IsPolyShapeValid(), POLYGON_GEOM_MANAGER::IsSelfIntersecting(), FABMASTER::loadFootprints(), FABMASTER::loadGraphics(), FABMASTER::loadPolygon(), FABMASTER::loadZone(), DSN::SPECCTRA_DB::makeIMAGE(), DSN::SPECCTRA_DB::makePADSTACK(), CONVERT_TOOL::makePolysFromChainedSegs(), STEP_PCB_MODEL::MakeShape(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeObtuse(), PNS::DP_MEANDER_PLACER::Move(), NearestPoint(), POLYGON_GEOM_MANAGER::NewPointClosesOutline(), NextShape(), ZONE_CREATE_HELPER::OnComplete(), operator!=(), BOOST_TEST_PRINT_NAMESPACE_OPEN::print_log_value< SHAPE_LINE_CHAIN >::operator()(), PNS::LINE_PLACER::optimizeTailHeadTransition(), BITMAPCONV_INFO::outputOnePolygon(), ALTIUM_PCB::ParsePolygons6Data(), PlotDrawingSheet(), GERBER_PLOTTER::PlotGerberRegion(), PLOTTER::PlotPoly(), GERBER_PLOTTER::PlotPoly(), SHAPE_SIMPLE::PointCount(), PNS::LINE::PointCount(), PNS::pointInside2(), polygon_Convert(), GERBER_DRAW_ITEM::PrintGerberPoly(), DS_DRAW_ITEM_POLYPOLYGONS::PrintWsItem(), Remove(), RemoveShape(), Replace(), PNS::OPTIMIZER::runSmartPads(), SetPoint(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), PNS::LINE::SetShape(), PNS::shovedArea(), PNS::SHOVE::shoveLineFromLoneVia(), PNS::SHOVE::shoveLineToHullSet(), Simplify(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), Slice(), PNS::OPTIMIZER::smartPadsSingle(), splitArc(), PNS::DRAGGER::tryWalkaround(), PNS::LINE_PLACER::updatePStart(), POLYGON_GEOM_MANAGER::updateTemporaryLines(), PNS::LINE::Walkaround(), HYPERLYNX_EXPORTER::writeNetObjects(), GBR_TO_PCB_EXPORTER::writePcbPolygon(), and GBR_TO_PCB_EXPORTER::writePcbZoneItem().

◆ PointInside()

bool SHAPE_LINE_CHAIN_BASE::PointInside ( const VECTOR2I aPt,
int  aAccuracy = 0,
bool  aUseBBoxCache = false 
) const
inherited

Check if point aP lies inside a polygon (any type) defined by the line chain.

For closed shapes only.

Parameters
aPtpoint to check
aUseBBoxCachegives better performance if the bounding box caches have been generated.
Returns
true if the point is inside the shape (edge is not treated as being inside).

Definition at line 1621 of file shape_line_chain.cpp.

1623{
1624 /*
1625 * Don't check the bounding box unless it's cached. Building it is about the same speed as
1626 * the rigorous test below and so just slows things down by doing potentially two tests.
1627 */
1628 if( aUseBBoxCache && GetCachedBBox() && !GetCachedBBox()->Contains( aPt ) )
1629 return false;
1630
1631 if( !IsClosed() || GetPointCount() < 3 )
1632 return false;
1633
1634 bool inside = false;
1635
1636 /*
1637 * To check for interior points, we draw a line in the positive x direction from
1638 * the point. If it intersects an even number of segments, the point is outside the
1639 * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
1640 *
1641 * Note: slope might be denormal here in the case of a horizontal line but we require our
1642 * y to move from above to below the point (or vice versa)
1643 *
1644 * Note: we open-code CPoint() here so that we don't end up calculating the size of the
1645 * vector number-of-points times. This has a non-trivial impact on zone fill times.
1646 */
1647 int pointCount = GetPointCount();
1648
1649 for( int i = 0; i < pointCount; )
1650 {
1651 const auto p1 = GetPoint( i++ );
1652 const auto p2 = GetPoint( i == pointCount ? 0 : i );
1653 const auto diff = p2 - p1;
1654
1655 if( diff.y != 0 )
1656 {
1657 const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
1658
1659 if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
1660 inside = !inside;
1661 }
1662 }
1663
1664 // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
1665 // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
1666 if( aAccuracy <= 1 )
1667 return inside;
1668 else
1669 return inside || PointOnEdge( aPt, aAccuracy );
1670}
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
virtual BOX2I * GetCachedBBox() const
Definition: shape.h:325
virtual bool IsClosed() const =0
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:118

References SHAPE_LINE_CHAIN_BASE::GetCachedBBox(), SHAPE_LINE_CHAIN_BASE::GetPoint(), SHAPE_LINE_CHAIN_BASE::GetPointCount(), SHAPE_LINE_CHAIN_BASE::IsClosed(), SHAPE_LINE_CHAIN_BASE::PointOnEdge(), rescale(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by BuildBoardPolygonOutlines(), Collide(), SHAPE_LINE_CHAIN_BASE::Collide(), Collide(), SHAPE_POLY_SET::containsSingle(), ConvertOutlineToPolygon(), ZONE::HitTestCutout(), MARKER_BASE::HitTestMarker(), CONNECTIVITY_DATA::IsConnectedOnLayer(), DRC_RTREE::QueryColliding(), SHAPE_LINE_CHAIN_BASE::SquaredDistance(), DRC_TEST_PROVIDER_ZONE_CONNECTIONS::testZoneLayer(), and PNS::LINE::Walkaround().

◆ PointOnEdge()

bool SHAPE_LINE_CHAIN_BASE::PointOnEdge ( const VECTOR2I aP,
int  aAccuracy = 0 
) const
inherited

Check if point aP lies on an edge or vertex of the line chain.

Parameters
aPpoint to check
Returns
true if the point lies on the edge.

Definition at line 1673 of file shape_line_chain.cpp.

1674{
1675 return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
1676}
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.

References SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint().

Referenced by FABMASTER::loadZones(), SHAPE_LINE_CHAIN_BASE::PointInside(), PNS::LINE_PLACER::splitHeadTail(), and PNS::LINE::Walkaround().

◆ PrevShape()

int SHAPE_LINE_CHAIN::PrevShape ( int  aPointIndex) const
inline

Definition at line 376 of file shape_line_chain.h.

377 {
378 return NextShape( aPointIndex, false );
379 }
int NextShape(int aPointIndex, bool aForwards=true) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.

References NextShape().

Referenced by PNS::LINE_PLACER::handlePullback().

◆ Remove() [1/2]

void SHAPE_LINE_CHAIN::Remove ( int  aIndex)
inline

Remove the aIndex-th point from the line chain.

Parameters
aIndexis the index of the point to be removed.

Definition at line 570 of file shape_line_chain.h.

571 {
572 Remove( aIndex, aIndex );
573 }
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.

References Remove().

◆ Remove() [2/2]

void SHAPE_LINE_CHAIN::Remove ( int  aStartIndex,
int  aEndIndex 
)

Remove the range of points [start_index, end_index] from the line chain.

Parameters
aStartIndexis the start of the point range to be replaced (inclusive).
aEndIndexis the end of the point range to be replaced (inclusive).

Definition at line 809 of file shape_line_chain.cpp.

810{
811 assert( m_shapes.size() == m_points.size() );
812
813 if( aEndIndex < 0 )
814 aEndIndex += PointCount();
815
816 if( aStartIndex < 0 )
817 aStartIndex += PointCount();
818
819 if( aStartIndex >= PointCount() )
820 return;
821
822 aEndIndex = std::min( aEndIndex, PointCount() - 1 );
823
824 // Split arcs at start index and end just after the end index
825 if( IsPtOnArc( aStartIndex ) )
826 splitArc( aStartIndex );
827
828 size_t nextIndex = static_cast<size_t>( aEndIndex ) + 1;
829
830 if( IsPtOnArc( nextIndex ) )
831 splitArc( nextIndex );
832
833 std::set<size_t> extra_arcs;
834 auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
835 {
836 if( aShapeIndex != SHAPE_IS_PT )
837 extra_arcs.insert( aShapeIndex );
838 };
839
840 // Remove any overlapping arcs in the point range
841 for( int i = aStartIndex; i <= aEndIndex; i++ )
842 {
843 if( IsSharedPt( i ) )
844 {
845 if( i == aStartIndex )
846 {
847 logArcIdxRemoval( m_shapes[i].second ); // Only remove the arc on the second index
848
849 // Ensure that m_shapes has been built correctly.
850 assert( i < aEndIndex || m_shapes[i + 1].first == m_shapes[i].second );
851
852 continue;
853 }
854 else if( i == aEndIndex )
855 {
856 logArcIdxRemoval( m_shapes[i].first ); // Only remove the arc on the first index
857
858 // Ensure that m_shapes has been built correctly.
859 assert( i > aStartIndex || IsSharedPt( i - 1 )
860 ? m_shapes[i - 1].second == m_shapes[i].first
861 : m_shapes[i - 1].first == m_shapes[i].first );
862 continue;
863 }
864 }
865
866 alg::run_on_pair( m_shapes[i], logArcIdxRemoval );
867 }
868
869 for( auto arc : extra_arcs )
870 convertArc( arc );
871
872 m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
873 m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
874 assert( m_shapes.size() == m_points.size() );
875}

References convertArc(), IsPtOnArc(), IsSharedPt(), m_points, m_shapes, PointCount(), alg::run_on_pair(), SHAPE_IS_PT, and splitArc().

Referenced by POLYGON_GEOM_MANAGER::AddPoint(), PNS::TOPOLOGY::AssembleTuningPath(), PNS::LINE_PLACER::buildInitialLine(), PNS::LINE::ClipToNearestObstacle(), POLYGON_GEOM_MANAGER::DeleteLastCorner(), EDA_SHAPE::endEdit(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::handleSelfIntersections(), PNS::OPTIMIZER::mergeColinear(), PNS::LINE_PLACER::mergeHead(), ZONE_CREATE_HELPER::OnComplete(), PNS::LINE_PLACER::reduceTail(), Remove(), EE_POINT_EDITOR::removeCorner(), RemoveShape(), Replace(), and Simplify().

◆ RemoveShape()

void SHAPE_LINE_CHAIN::RemoveShape ( int  aPointIndex)

Remove the shape at the given index from the line chain.

If the given index is inside an arc, the entire arc will be removed. Otherwise this is equivalent to Remove( aPointIndex ).

Parameters
aPointIndexis the index of the point to remove.

Definition at line 1110 of file shape_line_chain.cpp.

1111{
1112 if( aPointIndex < 0 )
1113 aPointIndex += PointCount();
1114
1115 if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
1116 {
1117 Remove( aPointIndex );
1118 return;
1119 }
1120
1121 //@todo should this be replaced to use NextShape() / PrevShape()?
1122 int start = aPointIndex;
1123 int end = aPointIndex;
1124 int arcIdx = ArcIndex( aPointIndex );
1125
1126 if( !IsSharedPt( aPointIndex ) )
1127 {
1128 // aPointIndex is not a shared point, so iterate backwards to find the start of the arc
1129 while( start >= 0 && m_shapes[start].first == arcIdx )
1130 start--;
1131
1132 // Check if the previous point might be a shared point and decrement 'start' if so
1133 if( start >= 1 && m_shapes[static_cast<ssize_t>( start ) - 1].second == arcIdx )
1134 start--;
1135 }
1136
1137 // For the end point we only need to check the first element in m_shapes (the second one is only
1138 // populated if there is an arc after the current one sharing the same point).
1139 while( end < static_cast<int>( m_shapes.size() ) - 1 && m_shapes[end].first == arcIdx )
1140 end++;
1141
1142 Remove( start, end );
1143}

References ArcIndex(), IsSharedPt(), m_shapes, PointCount(), Remove(), and SHAPES_ARE_PT.

Referenced by PNS::LINE_PLACER::handlePullback().

◆ Replace() [1/2]

void SHAPE_LINE_CHAIN::Replace ( int  aStartIndex,
int  aEndIndex,
const SHAPE_LINE_CHAIN aLine 
)

Replace points with indices in range [start_index, end_index] with the points from line chain aLine.

Parameters
aStartIndexis the start of the point range to be replaced (inclusive).
aEndIndexis the end of the point range to be replaced (inclusive).
aLineis the replacement line chain.

Definition at line 739 of file shape_line_chain.cpp.

740{
741 if( aEndIndex < 0 )
742 aEndIndex += PointCount();
743
744 if( aStartIndex < 0 )
745 aStartIndex += PointCount();
746
747 // We only process lines in order in this house
748 wxASSERT( aStartIndex <= aEndIndex );
749 wxASSERT( aEndIndex < m_points.size() );
750
751 SHAPE_LINE_CHAIN newLine = aLine;
752
753 // Zero points to add?
754 if( newLine.PointCount() == 0 )
755 {
756 Remove( aStartIndex, aEndIndex );
757 return;
758 }
759
760 // Remove coincident points in the new line
761 if( newLine.m_points.front() == m_points[aStartIndex] )
762 {
763 aStartIndex++;
764 newLine.Remove( 0 );
765
766 // Zero points to add?
767 if( newLine.PointCount() == 0 )
768 {
769 Remove( aStartIndex, aEndIndex );
770 return;
771 }
772 }
773
774 if( newLine.m_points.back() == m_points[aEndIndex] && aEndIndex > 0 )
775 {
776 aEndIndex--;
777 newLine.Remove( -1 );
778 }
779
780 Remove( aStartIndex, aEndIndex );
781
782 // Zero points to add?
783 if( newLine.PointCount() == 0 )
784 return;
785
786 // The total new arcs index is added to the new arc indices
787 size_t prev_arc_count = m_arcs.size();
788 std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.m_shapes;
789
790 for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
791 {
792 alg::run_on_pair( shape_pair,
793 [&]( ssize_t& aShape )
794 {
795 if( aShape != SHAPE_IS_PT )
796 aShape += prev_arc_count;
797 } );
798 }
799
800 m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
801 m_points.insert( m_points.begin() + aStartIndex, newLine.m_points.begin(),
802 newLine.m_points.end() );
803 m_arcs.insert( m_arcs.end(), newLine.m_arcs.begin(), newLine.m_arcs.end() );
804
805 assert( m_shapes.size() == m_points.size() );
806}

References m_arcs, m_points, m_shapes, PointCount(), Remove(), alg::run_on_pair(), and SHAPE_IS_PT.

◆ Replace() [2/2]

void SHAPE_LINE_CHAIN::Replace ( int  aStartIndex,
int  aEndIndex,
const VECTOR2I aP 
)

Replace points with indices in range [start_index, end_index] with a single point aP.

Parameters
aStartIndexis the start of the point range to be replaced (inclusive).
aEndIndexis the end of the point range to be replaced (inclusive).
aPis the replacement point.

Definition at line 731 of file shape_line_chain.cpp.

732{
733 Remove( aStartIndex, aEndIndex );
734 Insert( aStartIndex, aP );
735 assert( m_shapes.size() == m_points.size() );
736}
void Insert(size_t aVertex, const VECTOR2I &aP)

References Insert(), m_points, m_shapes, and Remove().

Referenced by PNS::TOPOLOGY::AssembleTuningPath(), BOOST_AUTO_TEST_CASE(), PNS::CORNER_COUNT_LIMIT_CONSTRAINT::Check(), PNS::coupledBypass(), PNS::LINE::dragSegment45(), CADSTAR_SCH_ARCHIVE_LOADER::loadNets(), PNS::OPTIMIZER::mergeDpStep(), PNS::OPTIMIZER::mergeObtuse(), PNS::LINE_PLACER::optimizeTailHeadTransition(), and PNS::Tighten().

◆ Reverse()

const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Reverse ( ) const

Reverse point order in the line chain.

Returns
line chain with reversed point order (original A-B-C-D: returned D-C-B-A).

Definition at line 641 of file shape_line_chain.cpp.

642{
643 SHAPE_LINE_CHAIN a( *this );
644
645 reverse( a.m_points.begin(), a.m_points.end() );
646 reverse( a.m_shapes.begin(), a.m_shapes.end() );
647 reverse( a.m_arcs.begin(), a.m_arcs.end() );
648
649 for( auto& sh : a.m_shapes )
650 {
651 if( sh != SHAPES_ARE_PT )
652 {
654 [&]( ssize_t& aShapeIndex )
655 {
656 if( aShapeIndex != SHAPE_IS_PT )
657 aShapeIndex = a.m_arcs.size() - aShapeIndex - 1;
658 } );
659
660 if( sh.second != SHAPE_IS_PT )
661 {
662 // If the second element is populated, the first one should be too!
663 assert( sh.first != SHAPE_IS_PT );
664
665 // Switch round first and second in shared points, as part of reversing the chain
666 std::swap( sh.first, sh.second );
667 }
668 }
669 }
670
671 for( SHAPE_ARC& arc : a.m_arcs )
672 arc.Reverse();
673
674 a.m_closed = m_closed;
675
676 return a;
677}
void Reverse()
Definition: shape_arc.cpp:581

References m_arcs, m_closed, m_points, m_shapes, SHAPE_ARC::Reverse(), alg::run_on_pair(), SHAPE_IS_PT, and SHAPES_ARE_PT.

Referenced by PNS::ArcHull(), PNS::DP_GATEWAYS::buildEntries(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), PNS::SHOVE::checkShoveDirection(), convertToClipper(), convertToClipper2(), PNS::coupledBypass(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::LINE::dragCorner45(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), CADSTAR_SCH_ARCHIVE_LOADER::loadNets(), PNS::DP_GATEWAY::Reverse(), PNS::LINE::Reverse(), PNS::SegmentHull(), PNS::OPTIMIZER::smartPadsSingle(), POLYGON_GEOM_MANAGER::updateTemporaryLines(), and PNS::LINE::Walkaround().

◆ reversedArcIndex()

ssize_t SHAPE_LINE_CHAIN::reversedArcIndex ( size_t  aSegment) const
inlineprotected

Return the arc index for the given segment index, looking backwards.

Definition at line 909 of file shape_line_chain.h.

910 {
911 if( IsSharedPt( aSegment ) )
912 return m_shapes[aSegment].first;
913 else
914 return m_shapes[aSegment].second;
915 }

References IsSharedPt(), and m_shapes.

Referenced by NextShape().

◆ Rotate()

void SHAPE_LINE_CHAIN::Rotate ( const EDA_ANGLE aAngle,
const VECTOR2I aCenter = { 0, 0 } 
)
overridevirtual

Rotate all vertices by a given angle.

Parameters
aCenteris the rotation center.
aAngleis the rotation angle.

Implements SHAPE.

Definition at line 507 of file shape_line_chain.cpp.

508{
509 for( VECTOR2I& pt : m_points )
510 RotatePoint( pt, aCenter, aAngle );
511
512 for( SHAPE_ARC& arc : m_arcs )
513 arc.Rotate( aAngle, aCenter );
514}
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:183

References m_arcs, m_points, and RotatePoint().

Referenced by PAD::BuildEffectiveShapes(), PCB_GRID_HELPER::computeAnchors(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), EDA_SHAPE::hitTest(), and EDA_SHAPE::makeEffectiveShapes().

◆ Segment()

SEG SHAPE_LINE_CHAIN::Segment ( int  aIndex)
inline

Return a copy of the aIndex-th segment in the line chain.

Parameters
aIndexis the index of the segment in the line chain. Negative values are counted from the end (i.e. -1 means the last segment in the line chain).
Returns
a segment at the aIndex in the line chain.

Definition at line 332 of file shape_line_chain.h.

333 {
334 if( aIndex < 0 )
335 aIndex += SegmentCount();
336
337 if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
338 return SEG( m_points[aIndex], m_points[0], aIndex );
339 else
340 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
341 }

References m_closed, m_points, and SegmentCount().

Referenced by BuildFootprintPolygonOutlines(), PNS::DIFF_PAIR::CoupledSegmentPairs(), BOARD_ADAPTER::createPadWithMargin(), findEndSegments(), ALTIUM_PCB::HelperCreateBoardOutline(), CADSTAR_SCH_ARCHIVE_LOADER::loadShapeVertices(), EDA_SHAPE::makeEffectiveShapes(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::testZoneLayer(), and unfracture().

◆ SegmentCount()

int SHAPE_LINE_CHAIN::SegmentCount ( ) const
inline

Return the number of segments in this line chain.

Returns
the number of segments.

Definition at line 296 of file shape_line_chain.h.

297 {
298 int c = m_points.size() - 1;
299
300 if( m_closed )
301 c++;
302
303 return std::max( 0, c );
304 }

References m_closed, and m_points.

Referenced by PNS::NODE::Add(), PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::NODE::AssembleLine(), build45DegLeader(), BuildFootprintPolygonOutlines(), PNS::LINE_PLACER::buildInitialLine(), PNS::PRESERVE_VERTEX_CONSTRAINT::Check(), CheckClearance(), PNS::NODE::CheckColliding(), PNS::DIFF_PAIR::CheckConnectionAngle(), PNS::checkGap(), PNS::MEANDERED_LINE::CheckSelfIntersections(), PNS::closestProjectedPoint(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), PNS::DIFF_PAIR::CoupledLength(), PNS::DIFF_PAIR::CoupledSegmentPairs(), BOARD_ADAPTER::createPadWithMargin(), CSegment(), PNS::LINE_PLACER::cursorDistMinimum(), PNS::MEANDER_PLACER::doMove(), PNS::LINE::dragCorner45(), PNS::dragCornerInternal(), PNS::LINE::dragSegment45(), KIGFX::OPENGL_GAL::DrawPolygon(), PNS::DIFF_PAIR::Empty(), PNS::findCoupledVertices(), findEndSegments(), FindSegment(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), GetSegmentCount(), SHAPE_SIMPLE::GetSegmentCount(), PNS::LINE_PLACER::handlePullback(), PNS::DIFF_PAIR_PLACER::HasPlacedAnything(), PNS::DP_MEANDER_PLACER::HasPlacedAnything(), PNS::HullIntersection(), Intersect(), isLine45Degree(), Length(), CADSTAR_SCH_ARCHIVE_LOADER::loadShapeVertices(), EDA_SHAPE::makeEffectiveShapes(), PNS::OPTIMIZER::mergeColinear(), PNS::OPTIMIZER::mergeDpSegments(), PNS::OPTIMIZER::mergeDpStep(), PNS::OPTIMIZER::mergeFull(), PNS::OPTIMIZER::mergeObtuse(), PNS::OPTIMIZER::mergeStep(), NearestPoint(), NearestSegment(), PathLength(), PointAlong(), PNS::pointInside2(), KIGFX::VIEW_OVERLAY::Polyline(), PNS::LINE_PLACER::reduceTail(), Segment(), PNS::LINE::SegmentCount(), SelfIntersecting(), PNS::OPTIMIZER::smartPadsSingle(), PNS::LINE::snapDraggedCorner(), PNS::LINE::snapToNeighbourSegments(), Split(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::testShapeLineChain(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::testZoneLayer(), PNS::Tighten(), SHAPE_POLY_SET::unfractureSingle(), PNS::LINE::Walkaround(), and HYPERLYNX_EXPORTER::writeBoardInfo().

◆ SelfIntersecting()

const std::optional< SHAPE_LINE_CHAIN::INTERSECTION > SHAPE_LINE_CHAIN::SelfIntersecting ( ) const

Check if the line chain is self-intersecting.

Returns
(optional) first found self-intersection point.

Definition at line 1728 of file shape_line_chain.cpp.

1729{
1730 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1731 {
1732 for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
1733 {
1734 const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
1735
1736 if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
1737 {
1738 INTERSECTION is;
1739 is.index_our = s1;
1740 is.index_their = s2;
1741 is.p = s2a;
1742 return is;
1743 }
1744 else if( CSegment( s1 ).Contains( s2b ) &&
1745 // for closed polylines, the ending point of the
1746 // last segment == starting point of the first segment
1747 // this is a normal case, not self intersecting case
1748 !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
1749 {
1750 INTERSECTION is;
1751 is.index_our = s1;
1752 is.index_their = s2;
1753 is.p = s2b;
1754 return is;
1755 }
1756 else
1757 {
1758 OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
1759
1760 if( p )
1761 {
1762 INTERSECTION is;
1763 is.index_our = s1;
1764 is.index_their = s2;
1765 is.p = *p;
1766 return is;
1767 }
1768 }
1769 }
1770 }
1771
1772 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
1773}

References SEG::A, SEG::B, CSegment(), SHAPE_LINE_CHAIN::INTERSECTION::index_our, SHAPE_LINE_CHAIN::INTERSECTION::index_their, SEG::Intersect(), IsClosed(), SHAPE_LINE_CHAIN::INTERSECTION::p, and SegmentCount().

Referenced by PNS::DIFF_PAIR::BuildInitial(), DIALOG_PAD_PRIMITIVE_POLY_PROPS::doValidate(), and POLYGON_GEOM_MANAGER::IsSelfIntersecting().

◆ SetClosed()

void SHAPE_LINE_CHAIN::SetClosed ( bool  aClosed)
inline

Mark the line chain as closed (i.e.

with a segment connecting the last point with the first point).

Parameters
aClosedwhether the line chain is to be closed or not.

Definition at line 257 of file shape_line_chain.h.

258 {
259 m_closed = aClosed;
261 }

References m_closed, and mergeFirstLastPointIfNeeded().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE::AddPolygon(), PNS::ArcHull(), EDA_SHAPE::beginEdit(), BOOST_AUTO_TEST_CASE(), buildBoardBoundingBoxPoly(), BuildFootprintPolygonOutlines(), KI_TEST::BuildRectChain(), ZONE_FILLER::buildThermalSpokes(), SHAPE_POLY_SET::chamferFilletPolygon(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), KI_TEST::CommonTestData::CommonTestData(), PCB_GRID_HELPER::computeAnchors(), ConvertOutlineToPolygon(), convertPolygon(), ConvertPolygonToBlocks(), CADSTAR_ARCHIVE_PARSER::SHAPE::ConvertToPolySet(), PNS::ConvexHull(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), KIGFX::GERBVIEW_PAINTER::draw(), EDA_SHAPE::endEdit(), TEARDROP_MANAGER::findAnchorPointsOnTrack(), SHAPE_POLY_SET::fractureSingle(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), KIFONT::OUTLINE_FONT::getTextAsGlyphs(), HelperShapeLineChainFromAltiumVertices(), POLYGON_GEOM_MANAGER::IsSelfIntersecting(), IteratorFixture::IteratorFixture(), EDA_SHAPE::makeEffectiveShapes(), CONVERT_TOOL::makePolysFromChainedSegs(), GEOM_TEST::MakeSquarePolyLine(), SHAPE_POLY_SET::NewHole(), SHAPE_POLY_SET::NewOutline(), PNS::OctagonalHull(), ZONE_CREATE_HELPER::OnComplete(), SHAPE_RECT::Outline(), CADSTAR_ARCHIVE_PARSER::SHAPE::OutlineAsChain(), EAGLE_PLUGIN::packagePolygon(), SHAPE_POLY_SET::Parse(), ALTIUM_PCB::ParseRegions6Data(), PCB_PARSER::parseRenderCache(), PCB_PARSER::parseZONE(), BRDITEMS_PLOTTER::PlotFootprintShape(), BRDITEMS_PLOTTER::PlotPcbShape(), polygonArea(), RENDER_3D_OPENGL::reload(), DRC_TEST_PROVIDER_ANNULAR_WIDTH::Run(), PNS::SegmentHull(), SHAPE_POLY_SET::SHAPE_POLY_SET(), SHAPE_SIMPLE::SHAPE_SIMPLE(), MARKER_BASE::ShapeToPolygon(), TestConcaveSquareFillet(), TransformCircleToPolygon(), unfracture(), and SHAPE_POLY_SET::unfractureSingle().

◆ SetPoint()

void SHAPE_LINE_CHAIN::SetPoint ( int  aIndex,
const VECTOR2I aPos 
)

Move a point to a specific location.

Parameters
aIndexis the index of the point to move.
aPosis the new absolute location of the point.

Definition at line 1092 of file shape_line_chain.cpp.

1093{
1094 if( aIndex < 0 )
1095 aIndex += PointCount();
1096 else if( aIndex >= PointCount() )
1097 aIndex -= PointCount();
1098
1099 m_points[aIndex] = aPos;
1100
1101 alg::run_on_pair( m_shapes[aIndex],
1102 [&]( ssize_t& aIdx )
1103 {
1104 if( aIdx != SHAPE_IS_PT )
1105 convertArc( aIdx );
1106 } );
1107}

References convertArc(), m_points, m_shapes, PointCount(), alg::run_on_pair(), and SHAPE_IS_PT.

Referenced by PNS::LINE_PLACER::buildInitialLine(), EDA_SHAPE::calcEdit(), PNS::LINE::dragCornerFree(), and CADSTAR_SCH_ARCHIVE_LOADER::getScaledLibPart().

◆ SetWidth()

void SHAPE_LINE_CHAIN::SetWidth ( int  aWidth)
inline

Set the width of all segments in the chain.

Parameters
aWidthis the width in internal units.

Definition at line 276 of file shape_line_chain.h.

277 {
278 m_width = aWidth;
279 }

References m_width.

Referenced by PNS_PCBNEW_DEBUG_DECORATOR::AddPoint(), PNS_PCBNEW_DEBUG_DECORATOR::AddShape(), BOOST_AUTO_TEST_CASE(), PNS::LINE::SetShape(), PNS::DIFF_PAIR::SetWidth(), and PNS::LINE::SetWidth().

◆ ShapeCount()

int SHAPE_LINE_CHAIN::ShapeCount ( ) const

Return the number of shapes (line segments or arcs) in this line chain.

This is kind of like SegmentCount() but will only count arcs as 1 segment.

Returns
ArcCount() + the number of non-arc segments.

Definition at line 983 of file shape_line_chain.cpp.

984{
985 if( m_points.empty() )
986 return 0;
987
988 int numPoints = static_cast<int>( m_shapes.size() );
989 int numShapes = 0;
990 int arcIdx = -1;
991
992 for( int i = 0; i < m_points.size() - 1; i++ )
993 {
994 if( m_shapes[i] == SHAPES_ARE_PT )
995 {
996 numShapes++;
997 }
998 else
999 {
1000 // Expect that the second index only gets populated when the point is shared between
1001 // two shapes. Otherwise, the shape index should always go on the first element of
1002 // the pair.
1003 assert( m_shapes[i].first != SHAPE_IS_PT );
1004
1005 // Start assuming the point is shared with the previous arc
1006 // If so, the new/next arc index should be located at the second
1007 // element in the pair
1008 arcIdx = m_shapes[i].second;
1009
1010 if( arcIdx == SHAPE_IS_PT )
1011 arcIdx = m_shapes[i].first; // Not a shared point
1012
1013 numShapes++;
1014
1015 // Now skip the rest of the arc
1016 while( i < numPoints && m_shapes[i].first == arcIdx )
1017 i++;
1018
1019 // Add the "hidden" segment at the end of the arc, if it exists
1020 if( i < numPoints && m_points[i] != m_points[i - 1] )
1021 {
1022 numShapes++;
1023 }
1024
1025 i--;
1026 }
1027 }
1028
1029 return numShapes;
1030}

References m_points, m_shapes, SHAPE_IS_PT, and SHAPES_ARE_PT.

Referenced by PNS::LINE_PLACER::mergeHead(), PNS::LINE_PLACER::optimizeTailHeadTransition(), and PNS::LINE::ShapeCount().

◆ Simplify()

SHAPE_LINE_CHAIN & SHAPE_LINE_CHAIN::Simplify ( bool  aRemoveColinear = true)

Simplify the line chain by removing colinear adjacent segments and duplicate vertices.

Parameters
aRemoveColinearcontrols the removal of colinear adjacent segments.
Returns
reference to this line chain.

Definition at line 1776 of file shape_line_chain.cpp.

1777{
1778 std::vector<VECTOR2I> pts_unique;
1779 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
1780
1781 // Always try to keep at least 2 points otherwise, we're not really a line
1782 if( PointCount() < 3 )
1783 {
1784 return *this;
1785 }
1786 else if( PointCount() == 3 )
1787 {
1788 if( m_points[0] == m_points[1] )
1789 Remove( 1 );
1790
1791 return *this;
1792 }
1793
1794 int i = 0;
1795 int np = PointCount();
1796
1797 // stage 1: eliminate duplicate vertices
1798 while( i < np )
1799 {
1800 int j = i + 1;
1801
1802 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
1803 // one of them is part of a shape and one is not.
1804 while( j < np && m_points[i] == m_points[j] &&
1805 ( m_shapes[i] == m_shapes[j] ||
1806 m_shapes[i] == SHAPES_ARE_PT ||
1807 m_shapes[j] == SHAPES_ARE_PT ) )
1808 {
1809 j++;
1810 }
1811
1812 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
1813
1814 if( shapeToKeep == SHAPES_ARE_PT )
1815 shapeToKeep = m_shapes[j - 1];
1816
1817 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
1818 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
1819
1820 pts_unique.push_back( CPoint( i ) );
1821 shapes_unique.push_back( shapeToKeep );
1822
1823 i = j;
1824 }
1825
1826 m_points.clear();
1827 m_shapes.clear();
1828 np = pts_unique.size();
1829
1830 i = 0;
1831
1832 // stage 2: eliminate colinear segments
1833 while( i < np - 2 )
1834 {
1835 const VECTOR2I p0 = pts_unique[i];
1836 int n = i;
1837
1838 if( aRemoveColinear && shapes_unique[i] == SHAPES_ARE_PT
1839 && shapes_unique[i + 1] == SHAPES_ARE_PT )
1840 {
1841 while( n < np - 2
1842 && ( SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
1843 || SEG( p0, pts_unique[n + 2] ).Collinear( SEG( p0, pts_unique[n + 1] ) ) ) )
1844 n++;
1845 }
1846
1847 m_points.push_back( p0 );
1848 m_shapes.push_back( shapes_unique[i] );
1849
1850 if( n > i )
1851 i = n;
1852
1853 if( n == np - 2 )
1854 {
1855 m_points.push_back( pts_unique[np - 1] );
1856 m_shapes.push_back( shapes_unique[np - 1] );
1857 return *this;
1858 }
1859
1860 i++;
1861 }
1862
1863 if( np > 1 )
1864 {
1865 m_points.push_back( pts_unique[np - 2] );
1866 m_shapes.push_back( shapes_unique[np - 2] );
1867 }
1868
1869 m_points.push_back( pts_unique[np - 1] );
1870 m_shapes.push_back( shapes_unique[np - 1] );
1871
1872 assert( m_points.size() == m_shapes.size() );
1873
1874 return *this;
1875}

References CPoint(), m_arcs, m_points, m_shapes, PointCount(), Remove(), and SHAPES_ARE_PT.

Referenced by PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::NODE::AssembleLine(), PNS::DIFF_PAIR_PLACER::attemptWalk(), BOOST_AUTO_TEST_CASE(), DIRECTION_45::BuildInitialTrace(), PNS_LOG_VIEWER_FRAME::buildListTree(), PNS::LINE::ChangedArea(), PNS::CORNER_COUNT_LIMIT_CONSTRAINT::Check(), CompareGeometry(), PNS::DIFF_PAIR::CoupledSegmentPairs(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::MEANDER_PLACER::doMove(), DIALOG_PAD_PRIMITIVE_POLY_PROPS::doValidate(), PNS::LINE::dragCornerFree(), PNS::LINE::dragSegment45(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), PNS::OPTIMIZER::mergeDpStep(), PNS::OPTIMIZER::mergeFull(), PNS::LINE_PLACER::mergeHead(), PNS::DP_MEANDER_PLACER::Move(), PNS::SHOVE::onCollidingSolid(), ZONE_CREATE_HELPER::OnComplete(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::LINE_PLACER::rhWalkBase(), PNS::WALKAROUND::Route(), PNS::OPTIMIZER::runSmartPads(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), PNS::WALKAROUND::singleStep(), PNS::OPTIMIZER::smartPadsSingle(), PNS::Tighten(), PNS::LINE_PLACER::Trace(), and SHAPE_POLY_SET::unfractureSingle().

◆ Slice()

const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice ( int  aStartIndex,
int  aEndIndex = -1 
) const

Return a subset of this line chain containing the [start_index, end_index] range of points.

Parameters
aStartIndexis the start of the point range to be returned (inclusive).
aEndIndexis the end of the point range to be returned (inclusive).
Returns
the cut line chain.

Definition at line 1146 of file shape_line_chain.cpp.

1147{
1149
1150 if( aEndIndex < 0 )
1151 aEndIndex += PointCount();
1152
1153 if( aStartIndex < 0 )
1154 aStartIndex += PointCount();
1155
1156 int numPoints = static_cast<int>( m_points.size() );
1157
1158
1159 if( IsArcSegment( aStartIndex ) && !IsArcStart( aStartIndex ) )
1160 {
1161 // Cutting in middle of an arc, lets split it
1162 ssize_t arcIndex = ArcIndex( aStartIndex );
1163 const SHAPE_ARC& currentArc = Arc( arcIndex );
1164
1165 // Copy the points as arc points
1166 for( size_t i = aStartIndex; arcIndex == ArcIndex( i ); i++ )
1167 {
1168 rv.m_points.push_back( m_points[i] );
1169 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1170 rv.m_bbox.Merge( m_points[i] );
1171 }
1172
1173 // Create a new arc from the existing one, with different start point.
1174 SHAPE_ARC newArc;
1175
1176 VECTOR2I newArcStart = m_points[aStartIndex];
1177
1178 newArc.ConstructFromStartEndCenter( newArcStart, currentArc.GetP1(),
1179 currentArc.GetCenter(),
1180 currentArc.IsClockwise() );
1181
1182
1183 rv.m_arcs.push_back( newArc );
1184
1185 aStartIndex += rv.PointCount();
1186 }
1187
1188 for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i = NextShape( i ) )
1189 {
1190 if( i == -1 )
1191 return rv; // NextShape reached the end
1192
1193 if( IsArcStart( i ) )
1194 {
1195 const SHAPE_ARC &currentArc = Arc( ArcIndex( i ) );
1196 int nextShape = NextShape( i );
1197 bool isLastShape = nextShape < 0;
1198
1199 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1200 || ( nextShape > aEndIndex ) )
1201 {
1202 if( i == aEndIndex )
1203 {
1204 // Single point on an arc, just append the single point
1205 rv.Append( m_points[i] );
1206 return rv;
1207 }
1208
1209 // Cutting in middle of an arc, lets split it
1210 ssize_t arcIndex = ArcIndex( i );
1211 const SHAPE_ARC& currentArc = Arc( arcIndex );
1212
1213 // Copy the points as arc points
1214 for( ; i <= aEndIndex && i < numPoints; i++ )
1215 {
1216 if( arcIndex != ArcIndex( i ) )
1217 break;
1218
1219 rv.m_points.push_back( m_points[i] );
1220 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1221 rv.m_bbox.Merge( m_points[i] );
1222 }
1223
1224 // Create a new arc from the existing one, with different end point.
1225 SHAPE_ARC newArc;
1226
1227 VECTOR2I newArcEnd = m_points[aEndIndex];
1228
1229 newArc.ConstructFromStartEndCenter( currentArc.GetP0(), newArcEnd,
1230 currentArc.GetCenter(),
1231 currentArc.IsClockwise() );
1232
1233
1234 rv.m_arcs.push_back( newArc );
1235
1236 return rv;
1237 }
1238 else
1239 {
1240 // append the whole arc
1241 rv.Append( currentArc );
1242 }
1243
1244 if( isLastShape )
1245 return rv;
1246 }
1247 else
1248 {
1249 wxASSERT_MSG( !IsArcSegment( i ),
1250 wxT( "Still on an arc segment, we missed something..." ) );
1251
1252 rv.Append( m_points[i] );
1253 }
1254 }
1255
1256 return rv;
1257}

References Append(), Arc(), ArcIndex(), SHAPE_ARC::ConstructFromStartEndCenter(), SHAPE_ARC::GetCenter(), SHAPE_ARC::GetP0(), SHAPE_ARC::GetP1(), IsArcSegment(), IsArcStart(), SHAPE_ARC::IsClockwise(), m_arcs, m_bbox, m_points, m_shapes, BOX2< Vec >::Merge(), NextShape(), PointCount(), and SHAPE_IS_PT.

Referenced by PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), BOOST_AUTO_TEST_CASE(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), PNS::LINE_PLACER::clipAndCheckCollisions(), PNS::LINE::ClipVertexRange(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::LINE::dragCorner45(), PNS::dragCornerInternal(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::LINE_PLACER::splitHeadTail(), and PNS::Tighten().

◆ Split()

int SHAPE_LINE_CHAIN::Split ( const VECTOR2I aP)

Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.

Parameters
aPis the point to be inserted.
Returns
index of the newly inserted point (or a negative value if aP does not lie on our line).

Definition at line 898 of file shape_line_chain.cpp.

899{
900 int ii = -1;
901 int min_dist = 2;
902
903 int found_index = Find( aP );
904
905 for( int s = 0; s < SegmentCount(); s++ )
906 {
907 const SEG seg = CSegment( s );
908 int dist = seg.Distance( aP );
909
910 // make sure we are not producing a 'slightly concave' primitive. This might happen
911 // if aP lies very close to one of already existing points.
912 if( dist < min_dist && seg.A != aP && seg.B != aP )
913 {
914 min_dist = dist;
915 if( found_index < 0 )
916 ii = s;
917 else if( s < found_index )
918 ii = s;
919 }
920 }
921
922 if( ii < 0 )
923 ii = found_index;
924
925 if( ii >= 0 )
926 {
927 // Don't create duplicate points
928 if( GetPoint( ii ) == aP )
929 return ii;
930
931 size_t newIndex = static_cast<size_t>( ii ) + 1;
932
933 if( IsArcSegment( ii ) )
934 {
935 m_points.insert( m_points.begin() + newIndex, aP );
936 m_shapes.insert( m_shapes.begin() + newIndex, { ArcIndex( ii ), SHAPE_IS_PT } );
937 splitArc( newIndex, true ); // Make the inserted point a shared point
938 }
939 else
940 {
941 Insert( newIndex, aP );
942 }
943
944 return newIndex;
945 }
946
947 return -1;
948}
virtual const VECTOR2I GetPoint(int aIndex) const override
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.

References SEG::A, ArcIndex(), SEG::B, CSegment(), SEG::Distance(), Find(), GetPoint(), Insert(), IsArcSegment(), m_points, m_shapes, SegmentCount(), SHAPE_IS_PT, and splitArc().

Referenced by BOOST_AUTO_TEST_CASE(), PNS::LINE_PLACER::clipAndCheckCollisions(), PNS::LINE::ClipToNearestObstacle(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::LINE_PLACER::splitHeadTail(), and PNS::LINE::Walkaround().

◆ splitArc()

void SHAPE_LINE_CHAIN::splitArc ( ssize_t  aPtIndex,
bool  aCoincident = false 
)
protected

Splits an arc into two arcs at aPtIndex.

Parameter aCoincident controls whether the two arcs are to be coincident at aPtIndex or whether a short straight segment should be created instead

Parameters
aPtIndexindex of the point in the chain in which to split the arc
aCoincidentIf true, the end point of the first arc will be coincident with the start point of the second arc at aPtIndex. If false, the end point of the first arc will be at aPtIndex-1 and the start point of the second arc will be at aPtIndex, resulting in a short straight line segment between aPtIndex-1 and aPtIndex.

Definition at line 304 of file shape_line_chain.cpp.

305{
306 if( aPtIndex < 0 )
307 aPtIndex += m_shapes.size();
308
309 if( !IsSharedPt( aPtIndex ) && IsArcStart( aPtIndex ) )
310 return; // Nothing to do
311
312 if( !IsPtOnArc( aPtIndex ) )
313 return; // Nothing to do
314
315 wxCHECK_MSG( aPtIndex < static_cast<ssize_t>( m_shapes.size() ), /* void */,
316 wxT( "Invalid point index requested." ) );
317
318 if( IsSharedPt( aPtIndex ) || IsArcEnd( aPtIndex ) )
319 {
320 if( aCoincident || aPtIndex == 0 )
321 return; // nothing to do
322
323 ssize_t firstArcIndex = m_shapes[aPtIndex].first;
324
325 const VECTOR2I& newStart = m_arcs[firstArcIndex].GetP0(); // don't amend the start
326 const VECTOR2I& newEnd = m_points[aPtIndex - 1];
327 amendArc( firstArcIndex, newStart, newEnd );
328
329 if( IsSharedPt( aPtIndex ) )
330 {
331 m_shapes[aPtIndex].first = m_shapes[aPtIndex].second;
332 m_shapes[aPtIndex].second = SHAPE_IS_PT;
333 }
334 else
335 {
336 m_shapes[aPtIndex] = SHAPES_ARE_PT;
337 }
338
339 return;
340 }
341
342 ssize_t currArcIdx = ArcIndex( aPtIndex );
343 SHAPE_ARC& currentArc = m_arcs[currArcIdx];
344
345 SHAPE_ARC newArc1;
346 SHAPE_ARC newArc2;
347
348 VECTOR2I arc1End = ( aCoincident ) ? m_points[aPtIndex] : m_points[aPtIndex - 1];
349 VECTOR2I arc2Start = m_points[aPtIndex];
350
351 newArc1.ConstructFromStartEndCenter( currentArc.GetP0(), arc1End, currentArc.GetCenter(),
352 currentArc.IsClockwise() );
353
354 newArc2.ConstructFromStartEndCenter( arc2Start, currentArc.GetP1(), currentArc.GetCenter(),
355 currentArc.IsClockwise() );
356
357 if( !aCoincident && ArcIndex( aPtIndex - 1 ) != currArcIdx )
358 {
359 //Ignore newArc1 as it has zero points
360 m_arcs[currArcIdx] = newArc2;
361 }
362 else
363 {
364 m_arcs[currArcIdx] = newArc1;
365 m_arcs.insert( m_arcs.begin() + currArcIdx + 1, newArc2 );
366
367 if( aCoincident )
368 {
369 m_shapes[aPtIndex].second = currArcIdx + 1;
370 aPtIndex++;
371 }
372
373 // Only change the arc indices for the second half of the point range
374 for( int i = aPtIndex; i < PointCount(); i++ )
375 {
376 alg::run_on_pair( m_shapes[i], [&]( ssize_t& aIndex ) {
377 if( aIndex != SHAPE_IS_PT )
378 aIndex++;
379 } );
380 }
381 }
382}

References amendArc(), ArcIndex(), SHAPE_ARC::ConstructFromStartEndCenter(), SHAPE_ARC::GetCenter(), SHAPE_ARC::GetP0(), SHAPE_ARC::GetP1(), IsArcEnd(), IsArcStart(), SHAPE_ARC::IsClockwise(), IsPtOnArc(), IsSharedPt(), m_arcs, m_points, m_shapes, PointCount(), alg::run_on_pair(), SHAPE_IS_PT, and SHAPES_ARE_PT.

Referenced by Insert(), Remove(), and Split().

◆ SquaredDistance()

SEG::ecoord SHAPE_LINE_CHAIN_BASE::SquaredDistance ( const VECTOR2I aP,
bool  aOutlineOnly = false 
) const
inherited

Definition at line 884 of file shape_line_chain.cpp.

885{
887
888 if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
889 return 0;
890
891 for( size_t s = 0; s < GetSegmentCount(); s++ )
892 d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
893
894 return d;
895}
VECTOR2I::extended_type ecoord

References VECTOR2< int >::ECOORD_MAX, SHAPE_LINE_CHAIN_BASE::GetSegment(), SHAPE_LINE_CHAIN_BASE::GetSegmentCount(), SHAPE_LINE_CHAIN_BASE::IsClosed(), SHAPE_LINE_CHAIN_BASE::PointInside(), and SEG::SquaredDistance().

Referenced by Distance().

◆ Type()

◆ TypeName()

wxString SHAPE_BASE::TypeName ( ) const
inlineinherited

Definition at line 100 of file shape.h.

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

References SHAPE_BASE::m_type, and SHAPE_TYPE_asString().

Referenced by Collide().

◆ Width()

int SHAPE_LINE_CHAIN::Width ( ) const
inline

Get the current width of the segments in the chain.

Returns
the width in internal units.

Definition at line 286 of file shape_line_chain.h.

287 {
288 return m_width;
289 }

References m_width.

Referenced by PNS_PCBNEW_DEBUG_DECORATOR::AddPoint(), and PNS::LINE::dragCorner45().

Friends And Related Function Documentation

◆ SHAPE_POLY_SET

friend class SHAPE_POLY_SET
friend

Definition at line 871 of file shape_line_chain.h.

Member Data Documentation

◆ facets

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

Definition at line 143 of file wrlfacet.h.

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

◆ m_arcs

◆ m_bbox

BOX2I SHAPE_LINE_CHAIN::m_bbox
mutableprivate

cached bounding box

Definition at line 979 of file shape_line_chain.h.

Referenced by Append(), GenerateBBoxCache(), GetCachedBBox(), Move(), and Slice().

◆ m_closed

bool SHAPE_LINE_CHAIN::m_closed
private

◆ m_points

◆ m_shapes

std::vector<std::pair<ssize_t, ssize_t> > SHAPE_LINE_CHAIN::m_shapes
private

Array of indices that refer to the index of the shape if the point is part of a larger shape, e.g.

arc or spline. If the value is -1, the point is just a point.

There can be up to two shapes associated with a single point (e.g. the end point of one arc might be the start point of another).

Generally speaking only the first element of the pair will be populated (i.e. with a value not equal to SHAPE_IS_PT), unless the point is shared between two arc shapes. If the point is shared, then both the first and second element of the pair should be populated.

The second element must always be SHAPE_IS_PT if the first element is SHAPE_IS_PT.

Definition at line 964 of file shape_line_chain.h.

Referenced by Append(), ArcIndex(), Clear(), convertArc(), convertToClipper(), convertToClipper2(), CShapes(), fixIndicesRotation(), Insert(), IsArcSegment(), IsPtOnArc(), IsSharedPt(), mergeFirstLastPointIfNeeded(), NextShape(), Parse(), Remove(), RemoveShape(), Replace(), Reverse(), reversedArcIndex(), SetPoint(), SHAPE_LINE_CHAIN(), ShapeCount(), Simplify(), Slice(), Split(), and splitArc().

◆ m_type

SHAPE_TYPE SHAPE_BASE::m_type
protectedinherited

< type of our shape

Definition at line 116 of file shape.h.

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

◆ m_width

int SHAPE_LINE_CHAIN::m_width
private

Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to account for where we need a width and where not Alternatively, we could split the class into a LINE_CHAIN (no width) and SHAPE_LINE_CHAIN that derives from SHAPE as well that does have a width.

Not sure yet on the correct path. TODO Note that we also have SHAPE_SIMPLE which is a closed, filled SHAPE_LINE_CHAIN.

Definition at line 976 of file shape_line_chain.h.

Referenced by BBox(), GenerateBBoxCache(), SetWidth(), and Width().

◆ MIN_PRECISION_IU

const int SHAPE::MIN_PRECISION_IU = 4
staticinherited

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

Definition at line 128 of file shape.h.

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

◆ SHAPE_IS_PT

const ssize_t SHAPE_LINE_CHAIN::SHAPE_IS_PT = -1
staticprivate

◆ SHAPES_ARE_PT

const std::pair< ssize_t, ssize_t > SHAPE_LINE_CHAIN::SHAPES_ARE_PT = { SHAPE_IS_PT, SHAPE_IS_PT }
staticprivate

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