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< wxPoint > &aV, bool aClosed=false)
 
 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)
 
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 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) 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 OPT< 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 () 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 (double aAngle, const VECTOR2I &aCenter=VECTOR2I(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...
 
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...
 
virtual bool HasIndexableSubshapes () const
 
virtual size_t GetIndexableSubshapeCount () const
 
virtual void GetIndexableSubshapes (std::vector< SHAPE * > &aSubshapes)
 

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

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 80 of file shape_line_chain.h.

Member Typedef Documentation

◆ ecoord

typedef VECTOR2I::extended_type SHAPE::ecoord
protectedinherited

Definition at line 236 of file shape.h.

◆ INTERSECTIONS

Definition at line 141 of file shape_line_chain.h.

◆ point_citer

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

Definition at line 84 of file shape_line_chain.h.

◆ point_iter

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

Definition at line 83 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 147 of file shape_line_chain.h.

147  :
149  m_closed( false ),
150  m_width( 0 )
151  {}
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
bool m_closed
is the line chain closed?
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
line chain (polyline)
Definition: shape.h:45

Referenced by Clone().

◆ SHAPE_LINE_CHAIN() [2/7]

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const SHAPE_LINE_CHAIN aShape)
inline

Definition at line 153 of file shape_line_chain.h.

153  :
155  m_points( aShape.m_points ),
156  m_shapes( aShape.m_shapes ),
157  m_arcs( aShape.m_arcs ),
158  m_closed( aShape.m_closed ),
159  m_width( aShape.m_width ),
160  m_bbox( aShape.m_bbox )
161  {}
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
BOX2I m_bbox
cached bounding box
std::vector< SHAPE_ARC > m_arcs
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
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,...
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
line chain (polyline)
Definition: shape.h:45

◆ 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 }
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
bool m_closed
is the line chain closed?
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
line chain (polyline)
Definition: shape.h:45

References Append().

◆ SHAPE_LINE_CHAIN() [4/7]

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

Definition at line 165 of file shape_line_chain.h.

165  :
167  m_closed( aClosed ),
168  m_width( 0 )
169  {
170  m_points.reserve( aV.size() );
171 
172  for( auto pt : aV )
173  m_points.emplace_back( pt.x, pt.y );
174 
175  m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
176  }
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
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,...
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
line chain (polyline)
Definition: shape.h:45
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 std::vector< VECTOR2I > &  aV,
bool  aClosed = false 
)
inline

Definition at line 178 of file shape_line_chain.h.

178  :
180  m_closed( aClosed ),
181  m_width( 0 )
182  {
183  m_points = aV;
184  m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
185  }
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
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,...
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
line chain (polyline)
Definition: shape.h:45
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

References m_points, m_shapes, and SHAPES_ARE_PT.

◆ SHAPE_LINE_CHAIN() [6/7]

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

Definition at line 187 of file shape_line_chain.h.

187  :
189  m_closed( aClosed ),
190  m_width( 0 )
191  {
193  m_arcs.emplace_back( aArc );
194  m_arcs.back().SetWidth( 0 );
195  m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( m_points.size(), { 0, SHAPE_IS_PT } );
196  }
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
static const ssize_t SHAPE_IS_PT
std::vector< SHAPE_ARC > m_arcs
bool m_closed
is the line chain closed?
const std::vector< VECTOR2I > & CPoints() const
std::vector< VECTOR2I > m_points
array of vertices
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,...
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:458
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
line chain (polyline)
Definition: shape.h:45

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

◆ SHAPE_LINE_CHAIN() [7/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 56 of file shape_line_chain.cpp.

58  :
60  m_closed( true ), m_width( 0 )
61 {
62  std::map<ssize_t, ssize_t> loadedArcs;
63  m_points.reserve( aPath.size() );
64  m_shapes.reserve( aPath.size() );
65 
66  auto loadArc =
67  [&]( ssize_t aArcIndex ) -> ssize_t
68  {
69  if( aArcIndex == SHAPE_IS_PT )
70  {
71  return SHAPE_IS_PT;
72  }
73  else if( loadedArcs.count( aArcIndex ) == 0 )
74  {
75  loadedArcs.insert( { aArcIndex, m_arcs.size() } );
76  m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
77  }
78 
79  return loadedArcs.at( aArcIndex );
80  };
81 
82  for( size_t ii = 0; ii < aPath.size(); ++ii )
83  {
84  Append( aPath[ii].X, aPath[ii].Y );
85 
86  m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
87  m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
88  }
89 
90  // Clipper shouldn't return duplicate contiguous points. if it did, these would be
91  // removed during Append() and we would have different number of shapes to points
92  wxASSERT( m_shapes.size() == m_points.size() );
93 
94  // Clipper might mess up the rotation of the indices such that an arc can be split between
95  // the end point and wrap around to the start point. Lets fix the indices up now
97 }
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
void fixIndicesRotation()
Fix indices of this chain to ensure arcs are not split between the end and start indices.
static const ssize_t SHAPE_IS_PT
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
std::vector< SHAPE_ARC > m_arcs
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
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,...
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
line chain (polyline)
Definition: shape.h:45

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 202 of file shape_line_chain.h.

203  {}

Member Function Documentation

◆ amendArc()

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

Definition at line 203 of file shape_line_chain.cpp.

205 {
206  wxCHECK_MSG( aArcIndex < m_arcs.size(), /* void */,
207  wxT( "Invalid arc index requested." ) );
208 
209  SHAPE_ARC& theArc = m_arcs[aArcIndex];
210 
211  // Try to preseve the centre of the original arc
212  SHAPE_ARC newArc;
213  newArc.ConstructFromStartEndCenter( aNewStart, aNewEnd, theArc.GetCenter(),
214  theArc.IsClockwise() );
215 
216  m_arcs[aArcIndex] = newArc;
217 }
std::vector< SHAPE_ARC > m_arcs
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:201

References SHAPE_ARC::ConstructFromStartEndCenter(), 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 895 of file shape_line_chain.h.

896  {
897  amendArc( aArcIndex, m_arcs[aArcIndex].GetP0(), aNewEnd );
898  }
std::vector< SHAPE_ARC > m_arcs
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 890 of file shape_line_chain.h.

891  {
892  amendArc( aArcIndex, aNewStart, m_arcs[aArcIndex].GetP1() );
893  }
std::vector< SHAPE_ARC > m_arcs
void amendArc(size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)

References amendArc(), and m_arcs.

◆ Append() [1/4]

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 495 of file shape_line_chain.h.

496  {
497  VECTOR2I v( aX, aY );
498  Append( v, aAllowDuplication );
499  }
Define a general 2D-vector/point.
Definition: vector2d.h:61
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.

Referenced by PNS_PCBNEW_DEBUG_DECORATOR::AddBox(), ZONE_FILLER::addHatchFillTypeOnZone(), LIB_SHAPE::AddPoint(), POLYGON_GEOM_MANAGER::AddPoint(), PNS_TEST_DEBUG_DECORATOR::AddPoint(), PNS_PCBNEW_DEBUG_DECORATOR::AddPoint(), ZONE::AddPolygon(), PNS_PCBNEW_DEBUG_DECORATOR::AddSegment(), PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), SHAPE_SIMPLE::Append(), PNS::DIFF_PAIR::Append(), Append(), 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(), convertPolygon(), SHAPE_ARC::ConvertToPolyline(), PNS::ConvexHull(), CONVERT_TOOL::CreateLines(), 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(), 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::makePolysFromRects(), CONVERT_TOOL::makePolysFromSegs(), 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::PlotFootprintGraphicItem(), BRDITEMS_PLOTTER::PlotPcbShape(), PNS::LINE_PLACER::rhShoveOnly(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::Run(), 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(), POLYGON_GEOM_MANAGER::updateLeaderPoints(), and PNS::LINE::Walkaround().

◆ Append() [2/4]

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 509 of file shape_line_chain.h.

510  {
511  if( m_points.size() == 0 )
512  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
513 
514  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
515  {
516  m_points.push_back( aP );
517  m_shapes.push_back( SHAPES_ARE_PT );
518  m_bbox.Merge( aP );
519  }
520  }
BOX2I m_bbox
cached bounding box
BOX2< VECTOR2I > BOX2I
Definition: box2.h:506
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
std::vector< VECTOR2I > m_points
array of vertices
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363
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,...
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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

◆ Append() [3/4]

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 1180 of file shape_line_chain.cpp.

1181 {
1182  assert( m_shapes.size() == m_points.size() );
1183 
1184  if( aOtherLine.PointCount() == 0 )
1185  {
1186  return;
1187  }
1188 
1189  size_t num_arcs = m_arcs.size();
1190  m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
1191 
1192  auto fixShapeIndices =
1193  [&]( const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1194  {
1195  std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1196 
1197  alg::run_on_pair( retval, [&]( ssize_t& aIndex )
1198  {
1199  if( aIndex != SHAPE_IS_PT )
1200  aIndex = aIndex + num_arcs;
1201  } );
1202 
1203  return retval;
1204  };
1205 
1206  if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
1207  {
1208  const VECTOR2I p = aOtherLine.CPoint( 0 );
1209  m_points.push_back( p );
1210  m_shapes.push_back( fixShapeIndices( aOtherLine.CShapes()[0] ) );
1211  m_bbox.Merge( p );
1212  }
1213  else if( aOtherLine.IsArcSegment( 0 ) )
1214  {
1215  // Associate the new arc shape with the last point of this chain
1216  if( m_shapes.back() == SHAPES_ARE_PT )
1217  m_shapes.back().first = aOtherLine.CShapes()[0].first + num_arcs;
1218  else
1219  m_shapes.back().second = aOtherLine.CShapes()[0].first + num_arcs;
1220  }
1221 
1222 
1223  for( int i = 1; i < aOtherLine.PointCount(); i++ )
1224  {
1225  const VECTOR2I p = aOtherLine.CPoint( i );
1226  m_points.push_back( p );
1227 
1228  ssize_t arcIndex = aOtherLine.ArcIndex( i );
1229 
1230  if( arcIndex != ssize_t( SHAPE_IS_PT ) )
1231  {
1232  m_shapes.push_back( fixShapeIndices( aOtherLine.m_shapes[i] ) );
1233  }
1234  else
1235  m_shapes.push_back( SHAPES_ARE_PT );
1236 
1237  m_bbox.Merge( p );
1238  }
1239 
1241 
1242  assert( m_shapes.size() == m_points.size() );
1243 }
const std::vector< std::pair< ssize_t, ssize_t > > & CShapes() const
BOX2I m_bbox
cached bounding box
static const ssize_t SHAPE_IS_PT
Define a general 2D-vector/point.
Definition: vector2d.h:61
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< SHAPE_ARC > m_arcs
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.
bool IsArcSegment(size_t aSegment) const
std::vector< VECTOR2I > m_points
array of vertices
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
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363
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,...
void mergeFirstLastPointIfNeeded()
Merge the first and last point if they are the same and this chain is closed.
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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/4]

void SHAPE_LINE_CHAIN::Append ( const SHAPE_ARC aArc)

Definition at line 1246 of file shape_line_chain.cpp.

1247 {
1248  SEG startToEnd( aArc.GetP0(), aArc.GetP1() );
1249 
1250  if( startToEnd.Distance( aArc.GetArcMid() ) < 1 )
1251  {
1252  // Not really a valid arc. Add as a straight line segment instead
1253  Append( aArc.GetP0() );
1254  Append( aArc.GetP1() );
1255  }
1256  else
1257  {
1258  SHAPE_LINE_CHAIN chain = aArc.ConvertToPolyline();
1259 
1260  // @todo should the below 4 LOC be moved to SHAPE_ARC::ConvertToPolyline ?
1261  chain.m_arcs.push_back( aArc );
1262  chain.m_arcs.back().SetWidth( 0 );
1263 
1264  for( auto& sh : chain.m_shapes )
1265  sh.first = 0;
1266 
1267  Append( chain );
1268  }
1269 
1270  assert( m_shapes.size() == m_points.size() );
1271 }
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
std::vector< SHAPE_ARC > m_arcs
std::vector< VECTOR2I > m_points
array of vertices
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
const VECTOR2I & GetArcMid() const
Definition: shape_arc.h:113
Definition: seg.h:40
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,...
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:458
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const VECTOR2I & GetP1() const
Definition: shape_arc.h:112

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

◆ Arc()

const SHAPE_ARC& SHAPE_LINE_CHAIN::Arc ( size_t  aArc) const
inline

◆ ArcCount()

size_t SHAPE_LINE_CHAIN::ArcCount ( ) const
inline

Definition at line 782 of file shape_line_chain.h.

783  {
784  return m_arcs.size();
785  }
std::vector< SHAPE_ARC > m_arcs

References m_arcs.

Referenced by PNS::LINE::ArcCount(), BOOST_AUTO_TEST_CASE(), Collide(), Collide(), ROUTER_PREVIEW_ITEM::drawLineChain(), PNS::LINE_PLACER::FixRoute(), and Length().

◆ ArcIndex()

ssize_t SHAPE_LINE_CHAIN::ArcIndex ( size_t  aSegment) const
inline

Return the arc index for the given segment index.

Definition at line 790 of file shape_line_chain.h.

791  {
792  if( IsSharedPt( aSegment ) )
793  return m_shapes[aSegment].second;
794  else
795  return m_shapes[aSegment].first;
796  }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
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,...

References IsSharedPt(), and m_shapes.

Referenced by Append(), PNS::NODE::AssembleLine(), fixIndicesRotation(), PNS::LINE_PLACER::FixRoute(), PCB_PLUGIN::format(), PNS::LINE_PLACER::handlePullback(), ALTIUM_PCB::HelperCreateBoardOutline(), GEOM_TEST::IsOutlineValid(), PNS::LINE_PLACER::mergeHead(), 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 2009 of file shape_line_chain.cpp.

2010 {
2011  // see https://www.mathopenref.com/coordpolygonarea2.html
2012 
2013  if( !m_closed )
2014  return 0.0;
2015 
2016  double area = 0.0;
2017  int size = m_points.size();
2018 
2019  for( int i = 0, j = size - 1; i < size; ++i )
2020  {
2021  area += ( (double) m_points[j].x + m_points[i].x ) *
2022  ( (double) m_points[j].y - m_points[i].y );
2023  j = i;
2024  }
2025 
2026  if( aAbsolute )
2027  return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
2028  else
2029  return -area * 0.5; // The result would be negative if points are anti-clockwise
2030 }
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices

References m_closed, and m_points.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), SHAPE_POLY_SET::Area(), ZONE::CalculateFilledArea(), convertToClipper(), 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 433 of file shape_line_chain.h.

434  {
435  BOX2I bbox;
436  bbox.Compute( m_points );
437 
438  if( aClearance != 0 || m_width != 0 )
439  bbox.Inflate( aClearance + m_width );
440 
441  return bbox;
442  }
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:75
A 2D bounding box built on top of an origin point and size vector.
Definition: box2.h:41
std::vector< VECTOR2I > m_points
array of vertices
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:281
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...

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

Referenced by SHAPE_SIMPLE::BBox(), POLY_GRID_PARTITION::build(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), AR_AUTOPLACER::fillMatrix(), 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 }
double x
Definition: sg_base.h:70
IFSG_COORDS is the wrapper for SGCOORDS.
Definition: ifsg_coords.h:40
IFSG_COORDINDEX is the wrapper for SGCOORDINDEX.
IFSG_COLORS is the wrapper for SGCOLORS.
Definition: ifsg_colors.h:41
SGLIB_API SGNODE * GetSGNodeParent(SGNODE *aNode)
Definition: ifsg_api.cpp:494
double y
Definition: sg_base.h:71
IFSG_NORMALS is the wrapper for the SGNORMALS class.
Definition: ifsg_normals.h:40
std::list< FACET * > facets
Definition: wrlfacet.h:143
IFSG_FACESET is the wrapper for the SGFACESET class.
Definition: ifsg_faceset.h:40
double z
Definition: sg_base.h:72
IFSG_SHAPE is the wrapper for the SGSHAPE class.
Definition: ifsg_shape.h:40

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

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

◆ CArcs()

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

Definition at line 419 of file shape_line_chain.h.

420  {
421  return m_arcs;
422  }
std::vector< SHAPE_ARC > m_arcs

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

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

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 1620 of file shape_line_chain.cpp.

1621 {
1622  if( !PointCount() )
1623  return false;
1624  else if( PointCount() == 1 )
1625  return m_points[0] == aP;
1626 
1627  for( int i = 0; i < SegmentCount(); i++ )
1628  {
1629  const SEG s = CSegment( i );
1630 
1631  if( s.A == aP || s.B == aP )
1632  return true;
1633 
1634  if( s.Distance( aP ) <= aDist )
1635  return true;
1636  }
1637 
1638  return false;
1639 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:318
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< VECTOR2I > m_points
array of vertices
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
VECTOR2I A
Definition: seg.h:48
VECTOR2I B
Definition: seg.h:49

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 411 of file shape_line_chain.h.

412  {
413  return m_points[static_cast<size_t>( PointCount() ) - 1];
414  }
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< VECTOR2I > m_points
array of vertices

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

◆ Clear()

void SHAPE_LINE_CHAIN::Clear ( )
inline

Remove all points from the line chain.

Definition at line 242 of file shape_line_chain.h.

243  {
244  m_points.clear();
245  m_arcs.clear();
246  m_shapes.clear();
247  m_closed = false;
248  }
std::vector< SHAPE_ARC > m_arcs
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
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,...

References m_arcs, m_closed, m_points, and m_shapes.

Referenced by PNS_PCBNEW_DEBUG_DECORATOR::AddPoint(), PNS::LINE_PLACER::buildInitialLine(), PNS::MOUSE_TRAIL_TRACER::Clear(), SHAPE_SIMPLE::Clear(), PNS::LINE::Clear(), PNS::DIFF_PAIR::Clear(), PNS::LINE::ClipToNearestObstacle(), KI_TEST::CommonTestData::CommonTestData(), PNS::MEANDER_PLACER::doMove(), PNS::LINE_PLACER::FixRoute(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), PNS::LINE_PLACER::initPlacement(), IteratorFixture::IteratorFixture(), PNS::TOPOLOGY::LeadingRatLine(), PNS::MEANDER_SHAPE::MakeArc(), PNS::MEANDER_SHAPE::MakeCorner(), DSN::SPECCTRA_DB::makeIMAGE(), PNS::DP_MEANDER_PLACER::Move(), PNS::SHOVE::onReverseCollidingVia(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::LINE_PLACER::reduceTail(), POLYGON_GEOM_MANAGER::Reset(), PNS::LINE_PLACER::SetLayer(), PNS::MEANDER_SHAPE::start(), PNS::tightenSegment(), and PNS::LINE_PLACER::UnfixRoute().

◆ 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 600 of file shape_line_chain.cpp.

601 {
602  for( ssize_t arcIndex = m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
603  convertArc( arcIndex );
604 }
void convertArc(ssize_t aArcIndex)
Convert an arc to only a point chain by removing the arc and references.
std::vector< SHAPE_ARC > m_arcs

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 1930 of file shape_line_chain.cpp.

1931 {
1932  return new SHAPE_LINE_CHAIN( *this );
1933 }
SHAPE_LINE_CHAIN()
Initialize an empty line chain.

References SHAPE_LINE_CHAIN().

Referenced by ROUTER_PREVIEW_ITEM::Line().

◆ Collide() [1/4]

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

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

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

Reimplemented in SHAPE_RECT, SHAPE_SEGMENT, and SHAPE_COMPOUND.

Definition at line 1103 of file shape_collisions.cpp.

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

References collideShapes().

◆ Collide() [2/4]

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

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

Definition at line 1109 of file shape_collisions.cpp.

1110 {
1111  return collideShapes( this, aShape, aClearance, aActual, aLocation, nullptr );
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_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 354 of file shape_line_chain.cpp.

356 {
357  if( IsClosed() && PointInside( aP, aClearance ) )
358  {
359  if( aLocation )
360  *aLocation = aP;
361 
362  if( aActual )
363  *aActual = 0;
364 
365  return true;
366  }
367 
368  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
369  SEG::ecoord clearance_sq = SEG::Square( aClearance );
370  VECTOR2I nearest;
371 
372  // Collide line segments
373  for( size_t i = 0; i < GetSegmentCount(); i++ )
374  {
375  if( IsArcSegment( i ) )
376  continue;
377 
378  const SEG& s = GetSegment( i );
379  VECTOR2I pn = s.NearestPoint( aP );
380  SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
381 
382  if( dist_sq < closest_dist_sq )
383  {
384  nearest = pn;
385  closest_dist_sq = dist_sq;
386 
387  if( closest_dist_sq == 0 )
388  break;
389 
390  // If we're not looking for aActual then any collision will do
391  if( closest_dist_sq < clearance_sq && !aActual )
392  break;
393  }
394  }
395 
396  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
397  {
398  if( aLocation )
399  *aLocation = nearest;
400 
401  if( aActual )
402  *aActual = sqrt( closest_dist_sq );
403 
404  return true;
405  }
406 
407  // Collide arc segments
408  for( size_t i = 0; i < ArcCount(); i++ )
409  {
410  const SHAPE_ARC& arc = Arc( i );
411 
412  // The arcs in the chain should have zero width
413  wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
414 
415  if( arc.Collide( aP, aClearance, aActual, aLocation ) )
416  return true;
417  }
418 
419  return false;
420 }
const SHAPE_ARC & Arc(size_t aArc) const
virtual size_t GetSegmentCount() const override
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:229
VECTOR2I::extended_type ecoord
Definition: seg.h:43
Define a general 2D-vector/point.
Definition: vector2d.h:61
size_t ArcCount() const
static SEG::ecoord Square(int a)
Definition: seg.h:122
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
bool IsArcSegment(size_t aSegment) const
bool IsClosed() const override
virtual const SEG GetSegment(int aIndex) const override
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 VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:260
Definition: seg.h:40
int GetWidth() const
Definition: shape_arc.h:156

References Arc(), ArcCount(), SHAPE_ARC::Collide(), VECTOR2< T >::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().

◆ Collide() [4/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 491 of file shape_line_chain.cpp.

493 {
494  if( IsClosed() && PointInside( aSeg.A ) )
495  {
496  if( aLocation )
497  *aLocation = aSeg.A;
498 
499  if( aActual )
500  *aActual = 0;
501 
502  return true;
503  }
504 
505  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
506  SEG::ecoord clearance_sq = SEG::Square( aClearance );
507  VECTOR2I nearest;
508 
509  // Collide line segments
510  for( size_t i = 0; i < GetSegmentCount(); i++ )
511  {
512  if( IsArcSegment( i ) )
513  continue;
514 
515  const SEG& s = GetSegment( i );
516  SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
517 
518  if( dist_sq < closest_dist_sq )
519  {
520  if( aLocation )
521  nearest = s.NearestPoint( aSeg );
522 
523  closest_dist_sq = dist_sq;
524 
525  if( closest_dist_sq == 0 )
526  break;
527 
528  // If we're not looking for aActual then any collision will do
529  if( closest_dist_sq < clearance_sq && !aActual )
530  break;
531  }
532  }
533 
534  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
535  {
536  if( aLocation )
537  *aLocation = nearest;
538 
539  if( aActual )
540  *aActual = sqrt( closest_dist_sq );
541 
542  return true;
543  }
544 
545  // Collide arc segments
546  for( size_t i = 0; i < ArcCount(); i++ )
547  {
548  const SHAPE_ARC& arc = Arc( i );
549 
550  // The arcs in the chain should have zero width
551  wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
552 
553  if( arc.Collide( aSeg, aClearance, aActual, aLocation ) )
554  return true;
555  }
556 
557  return false;
558 }
const SHAPE_ARC & Arc(size_t aArc) const
virtual size_t GetSegmentCount() const override
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:229
VECTOR2I::extended_type ecoord
Definition: seg.h:43
Define a general 2D-vector/point.
Definition: vector2d.h:61
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:72
size_t ArcCount() const
static SEG::ecoord Square(int a)
Definition: seg.h:122
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
bool IsArcSegment(size_t aSegment) const
bool IsClosed() const override
virtual const SEG GetSegment(int aIndex) const override
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 VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:260
Definition: seg.h:40
int GetWidth() const
Definition: shape_arc.h:156
VECTOR2I A
Definition: seg.h:48

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

◆ CompareGeometry()

bool SHAPE_LINE_CHAIN::CompareGeometry ( const SHAPE_LINE_CHAIN aOther) const

Definition at line 1904 of file shape_line_chain.cpp.

1905 {
1906  SHAPE_LINE_CHAIN a(*this), b( aOther );
1907  a.Simplify();
1908  b.Simplify();
1909 
1910  if( a.m_points.size() != b.m_points.size() )
1911  return false;
1912 
1913  for( int i = 0; i < a.PointCount(); i++ )
1914  {
1915  if( a.CPoint( i ) != b.CPoint( i ) )
1916  return false;
1917  }
1918 
1919  return true;
1920 }
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

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 174 of file shape_line_chain.cpp.

175 {
176  if( aArcIndex < 0 )
177  aArcIndex += m_arcs.size();
178 
179  if( aArcIndex >= static_cast<ssize_t>( m_arcs.size() ) )
180  return;
181 
182  // Clear the shapes references
183  for( auto& sh : m_shapes )
184  {
185  alg::run_on_pair( sh,
186  [&]( ssize_t& aShapeIndex )
187  {
188  if( aShapeIndex == aArcIndex )
189  aShapeIndex = SHAPE_IS_PT;
190 
191  if( aShapeIndex > aArcIndex )
192  --aShapeIndex;
193  } );
194 
195  if( sh.second != SHAPE_IS_PT && sh.first == SHAPE_IS_PT )
196  std::swap( sh.first, sh.second );
197  }
198 
199  m_arcs.erase( m_arcs.begin() + aArcIndex );
200 }
static const ssize_t SHAPE_IS_PT
std::vector< SHAPE_ARC > m_arcs
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
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,...

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 99 of file shape_line_chain.cpp.

102 {
103  ClipperLib::Path c_path;
104  SHAPE_LINE_CHAIN input;
105  bool orientation = Area( false ) >= 0;
106  ssize_t shape_offset = aArcBuffer.size();
107 
108  if( orientation != aRequiredOrientation )
109  input = Reverse();
110  else
111  input = *this;
112 
113  for( int i = 0; i < input.PointCount(); i++ )
114  {
115  const VECTOR2I& vertex = input.CPoint( i );
116 
117  CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
118  size_t z_value_ptr = aZValueBuffer.size();
119  aZValueBuffer.push_back( z_value );
120 
121  c_path.push_back( ClipperLib::IntPoint( vertex.x, vertex.y, z_value_ptr ) );
122  }
123 
124  aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
125 
126  return c_path;
127 }
Define a general 2D-vector/point.
Definition: vector2d.h:61
double Area(bool aAbsolute=true) const
Return the area of this chain.
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< SHAPE_ARC > m_arcs
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
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,...
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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.

◆ 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 393 of file shape_line_chain.h.

394  {
395  if( aIndex < 0 )
396  aIndex += PointCount();
397  else if( aIndex >= PointCount() )
398  aIndex -= PointCount();
399 
400  return m_points[aIndex];
401  }
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< VECTOR2I > m_points
array of vertices

References m_points, and PointCount().

Referenced by LABEL_MANAGER::Add(), POLYGON_GEOM_MANAGER::AddPoint(), SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::AddPolyline(), BOARD_ADAPTER::addSolidAreasShapes(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), Append(), PNS::LINE::AppendVia(), ArePolylineEndPointsNearCircle(), ArePolylineMidPointsNearCircle(), PNS::NODE::AssembleLine(), PNS::TOPOLOGY::AssembleTuningPath(), BOOST_AUTO_TEST_CASE(), 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(), PNS::coupledBypass(), SHAPE_SIMPLE::CPoint(), PNS::LINE::CPoint(), PolygonTriangulation::createList(), CreatePadsShapesSection(), PNS::cursorDistMinimum(), PNS::LINE::dragCorner45(), PNS::dragCornerInternal(), APERTURE_MACRO::DrawApertureMacroShape(), KIGFX::CAIRO_GAL_BASE::drawPoly(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolyline(), 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(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), HPGL_PLOTTER::FlashPadRoundRect(), DXF_PLOTTER::FlashPadRoundRect(), PNS::TOPOLOGY::followTrivialPath(), PCB_PLUGIN::format(), CN_ZONE_LAYER::GetAnchor(), PCB_SHAPE::GetFocusPosition(), SHAPE_SIMPLE::GetPoint(), GetPoint(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), CADSTAR_SCH_ARCHIVE_LOADER::getScaledLibPart(), PNS::MOUSE_TRAIL_TRACER::GetTrailLeadVector(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), GEOM_TEST::IsOutlineValid(), POLYGON_GEOM_MANAGER::IsSelfIntersecting(), DSN::SPECCTRA_DB::makeIMAGE(), DSN::SPECCTRA_DB::makePADSTACK(), PNS::LINE_PLACER::mergeHead(), PNS::MEANDER_SHAPE::miter(), PNS::LINE_PLACER::Move(), NearestPoint(), POLYGON_GEOM_MANAGER::NewPointClosesOutline(), operator!=(), BOOST_TEST_PRINT_NAMESPACE_OPEN::print_log_value< SHAPE_LINE_CHAIN >::operator()(), PNS::LINE_PLACER::optimizeTailHeadTransition(), BITMAPCONV_INFO::outputOnePolygon(), PlotDrawingSheet(), BRDITEMS_PLOTTER::PlotFilledAreas(), GERBER_PLOTTER::PlotPoly(), PLOTTER::PlotPoly(), PointAlong(), PNS::pointInside2(), polygon_Convert(), LIB_SHAPE::print(), GERBER_DRAW_ITEM::PrintGerberPoly(), DS_DRAW_ITEM_POLYPOLYGONS::PrintWsItem(), DRC_RTREE::QueryColliding(), PNS::LINE_PLACER::removeLoops(), PNS::DIFF_PAIR_PLACER::routeHead(), PNS::OPTIMIZER::runSmartPads(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), PNS::shovedArea(), PNS::SHOVE::shoveLineFromLoneVia(), PNS::SHOVE::shoveLineToHullSet(), Simplify(), PNS::COMPONENT_DRAGGER::Start(), unfracture(), SHAPE_POLY_SET::unfractureSingle(), PNS::MEANDER_SHAPE::updateBaseSegment(), POLYGON_GEOM_MANAGER::updateLeaderPoints(), 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 348 of file shape_line_chain.h.

349  {
350  if( aIndex < 0 )
351  aIndex += SegmentCount();
352 
353  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
354  return SEG( m_points[aIndex], m_points[0], aIndex );
355  else
356  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
357  }
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40

References m_closed, m_points, and SegmentCount().

Referenced by PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::ArcHull(), PNS::LINE_PLACER::buildInitialLine(), PNS::PRESERVE_VERTEX_CONSTRAINT::Check(), CheckClearance(), PNS::NODE::CheckColliding(), PNS::DIFF_PAIR::CheckConnectionAngle(), PNS::checkGap(), PNS::MEANDERED_LINE::CheckSelfIntersections(), PNS::LINE::ClipToNearestObstacle(), PNS::closestProjectedPoint(), PCB_GRID_HELPER::computeAnchors(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), PNS::coupledBypass(), PNS::DIFF_PAIR::CoupledLength(), PNS::LINE::CSegment(), PNS::cursorDistMinimum(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::dragCornerInternal(), PNS::findCoupledVertices(), FindSegment(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), EDA_SHAPE::GetLength(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), SHAPE_SIMPLE::GetSegment(), GetSegment(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), PNS::HullIntersection(), Intersect(), PNS::LINE::Is45Degree(), 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(), POLY_GRID_PARTITION::scanCell(), 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 427 of file shape_line_chain.h.

428  {
429  return m_shapes;
430  }
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,...

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 798 of file shape_line_chain.cpp.

799 {
800  return sqrt( SquaredDistance( aP, aOutlineOnly ) );
801 }
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 1593 of file shape_line_chain.cpp.

1594 {
1595  if( !GetPointCount() )
1596  {
1597  return -1;
1598  }
1599  else if( GetPointCount() == 1 )
1600  {
1601  VECTOR2I dist = GetPoint(0) - aPt;
1602  return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
1603  }
1604 
1605  for( size_t i = 0; i < GetSegmentCount(); i++ )
1606  {
1607  const SEG s = GetSegment( i );
1608 
1609  if( s.A == aPt || s.B == aPt )
1610  return i;
1611 
1612  if( s.Distance( aPt ) <= aAccuracy + 1 )
1613  return i;
1614  }
1615 
1616  return -1;
1617 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:318
Define a general 2D-vector/point.
Definition: vector2d.h:61
virtual size_t GetPointCount() const =0
virtual size_t GetSegmentCount() const =0
Definition: seg.h:40
virtual const SEG GetSegment(int aIndex) const =0
VECTOR2I A
Definition: seg.h:48
virtual const VECTOR2I GetPoint(int aIndex) const =0
VECTOR2I B
Definition: seg.h:49

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 871 of file shape_line_chain.cpp.

872 {
873  for( int s = 0; s < PointCount(); s++ )
874  {
875  if( aThreshold == 0 )
876  {
877  if( CPoint( s ) == aP )
878  return s;
879  }
880  else
881  {
882  if( (CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
883  return s;
884  }
885  }
886 
887  return -1;
888 }
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.

References CPoint(), and PointCount().

Referenced by PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::DRAGGER::dragViaMarkObstacles(), PNS::DRAGGER::dragViaWalkaround(), PNS::NODE::FindLinesBetweenJoints(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), Split(), 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 891 of file shape_line_chain.cpp.

892 {
893  for( int s = 0; s < SegmentCount(); s++ )
894  {
895  if( CSegment( s ).Distance( aP ) <= aThreshold )
896  return s;
897  }
898 
899  return -1;
900 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:318
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 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 130 of file shape_line_chain.cpp.

131 {
132  wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
133 
134  if( m_shapes.size() <= 1 || m_arcs.size() <= 1 )
135  return;
136 
137  size_t rotations = 0;
138  size_t numPoints = m_points.size();
139 
140  while( ArcIndex( 0 ) != SHAPE_IS_PT
141  && ArcIndex( 0 ) == ArcIndex( numPoints - 1 ) )
142  {
143  // Rotate right
144  std::rotate( m_points.rbegin(), m_points.rbegin() + 1, m_points.rend() );
145  std::rotate( m_shapes.rbegin(), m_shapes.rbegin() + 1, m_shapes.rend() );
146 
147  // Sanity check - avoid infinite loops
148  wxCHECK( rotations++ <= m_shapes.size(), /* void */ );
149  }
150 }
static const ssize_t SHAPE_IS_PT
std::vector< SHAPE_ARC > m_arcs
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
std::vector< VECTOR2I > m_points
array of vertices
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,...

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 ( ) const
overridevirtual

Reimplemented from SHAPE.

Definition at line 1875 of file shape_line_chain.cpp.

1876 {
1877  std::stringstream ss;
1878 
1879  ss << "SHAPE_LINE_CHAIN( { ";
1880 
1881  for( int i = 0; i < PointCount(); i++ )
1882  {
1883  ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
1884 
1885  if( i != PointCount() -1 )
1886  ss << ", ";
1887  }
1888 
1889  ss << "}, " << ( m_closed ? "true" : "false" );
1890  ss << " );";
1891 
1892  return ss.str();
1893 
1894  /* fixme: arcs
1895  for( size_t i = 0; i < m_arcs.size(); i++ )
1896  ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
1897  << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
1898  << m_arcs[i].GetCentralAngle();
1899 
1900  return ss.str();*/
1901 }
int PointCount() const
Return the number of points (vertices) in this line chain.
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices

References m_closed, m_points, and PointCount().

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

◆ GenerateBBoxCache()

void SHAPE_LINE_CHAIN::GenerateBBoxCache ( ) const
inline

Definition at line 444 of file shape_line_chain.h.

445  {
447 
448  if( m_width != 0 )
450  }
BOX2I m_bbox
cached bounding box
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:75
std::vector< VECTOR2I > m_points
array of vertices
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:281
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...

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

Referenced by SHAPE_POLY_SET::BuildBBoxCaches(), and ZONE_FILLER::buildThermalSpokes().

◆ GetCachedBBox()

BOX2I* SHAPE_LINE_CHAIN::GetCachedBBox ( ) const
inlineoverridevirtual

Reimplemented from SHAPE_LINE_CHAIN_BASE.

Definition at line 452 of file shape_line_chain.h.

453  {
454  return &m_bbox;
455  }
BOX2I m_bbox
cached bounding box

References m_bbox.

◆ GetIndexableSubshapeCount()

virtual size_t SHAPE_BASE::GetIndexableSubshapeCount ( ) const
inlinevirtualinherited

Reimplemented in SHAPE_POLY_SET, and SHAPE_COMPOUND.

Definition at line 104 of file shape.h.

104 { return 0; }

◆ GetIndexableSubshapes()

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

Reimplemented in SHAPE_POLY_SET, and SHAPE_COMPOUND.

Definition at line 106 of file shape.h.

106 { }

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

◆ GetPoint()

virtual const VECTOR2I SHAPE_LINE_CHAIN::GetPoint ( int  aIndex) const
inlineoverridevirtual

Implements SHAPE_LINE_CHAIN_BASE.

Definition at line 859 of file shape_line_chain.h.

859 { return CPoint(aIndex); }
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.

References CPoint().

Referenced by PNS::TOPOLOGY::AssembleTuningPath(), BOOST_AUTO_TEST_CASE(), BuildFootprintPolygonOutlines(), PNS::LINE::dragCornerFree(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), EDA_SHAPE::hitTest(), Split(), and TransformArcToPolygon().

◆ GetPointCount()

◆ GetSegment()

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

Implements SHAPE_LINE_CHAIN_BASE.

Definition at line 860 of file shape_line_chain.h.

860 { return CSegment(aIndex); }
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.

References CSegment().

Referenced by Collide(), and Collide().

◆ GetSegmentCount()

virtual size_t SHAPE_LINE_CHAIN::GetSegmentCount ( ) const
inlineoverridevirtual

Implements SHAPE_LINE_CHAIN_BASE.

Definition at line 862 of file shape_line_chain.h.

862 { return SegmentCount(); }
int SegmentCount() const
Return the number of segments in this line chain.

References SegmentCount().

Referenced by Collide(), Collide(), DRC_TEST_PROVIDER_EDGE_CLEARANCE::Run(), and TransformArcToPolygon().

◆ HasIndexableSubshapes()

virtual bool SHAPE_BASE::HasIndexableSubshapes ( ) const
inlinevirtualinherited

Reimplemented in SHAPE_POLY_SET, and SHAPE_COMPOUND.

Definition at line 99 of file shape.h.

100  {
101  return false;
102  }

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

◆ Insert() [1/2]

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

Definition at line 1274 of file shape_line_chain.cpp.

1275 {
1276  if( aVertex == m_points.size() )
1277  {
1278  Append( aP );
1279  return;
1280  }
1281 
1282  wxCHECK( aVertex < m_points.size(), /* void */ );
1283 
1284  if( aVertex > 0 && IsPtOnArc( aVertex ) )
1285  splitArc( aVertex );
1286 
1287  //@todo need to check we aren't creating duplicate points
1288  m_points.insert( m_points.begin() + aVertex, aP );
1289  m_shapes.insert( m_shapes.begin() + aVertex, SHAPES_ARE_PT );
1290 
1291  assert( m_shapes.size() == m_points.size() );
1292 }
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
std::vector< VECTOR2I > m_points
array of vertices
bool IsPtOnArc(size_t aPtIndex) const
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,...
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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

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

◆ Insert() [2/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 1295 of file shape_line_chain.cpp.

1296 {
1297  wxCHECK( aVertex < m_points.size(), /* void */ );
1298 
1299  if( aVertex > 0 && IsPtOnArc( aVertex ) )
1300  splitArc( aVertex );
1301 
1303  ssize_t arc_pos = m_arcs.size();
1304 
1305  for( auto arc_it = m_shapes.rbegin() ;
1306  arc_it != m_shapes.rend() + aVertex;
1307  arc_it++ )
1308  {
1309  if( *arc_it != SHAPES_ARE_PT )
1310  {
1311  arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1312  arc_pos++;
1313  }
1314  }
1315 
1316  //Increment all arc indices before inserting the new arc
1317  for( auto& sh : m_shapes )
1318  {
1319  alg::run_on_pair( sh,
1320  [&]( ssize_t& aIndex )
1321  {
1322  if( aIndex >= arc_pos )
1323  aIndex++;
1324  } );
1325  }
1326 
1327  SHAPE_ARC arcCopy( aArc );
1328  arcCopy.SetWidth( 0 );
1329  m_arcs.insert( m_arcs.begin() + arc_pos, arcCopy );
1330 
1332  //@todo need to check we aren't creating duplicate points at start or end
1333  auto& chain = aArc.ConvertToPolyline();
1334  m_points.insert( m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1335 
1337  //@todo need to check we aren't creating duplicate points at start or end
1338  std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1339  { arc_pos, SHAPE_IS_PT } );
1340 
1341  m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1342  assert( m_shapes.size() == m_points.size() );
1343 }
static const ssize_t SHAPE_IS_PT
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
std::vector< SHAPE_ARC > m_arcs
std::vector< VECTOR2I > m_points
array of vertices
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
bool IsPtOnArc(size_t aPtIndex) const
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,...
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:458
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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

◆ 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 1361 of file shape_line_chain.cpp.

1362 {
1363  for( int s = 0; s < SegmentCount(); s++ )
1364  {
1365  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
1366 
1367  if( p )
1368  {
1369  INTERSECTION is;
1370  is.valid = true;
1371  is.index_our = s;
1372  is.index_their = -1;
1373  is.is_corner_our = is.is_corner_their = false;
1374  is.p = *p;
1375  aIp.push_back( is );
1376  }
1377  }
1378 
1379  compareOriginDistance comp( aSeg.A );
1380  sort( aIp.begin(), aIp.end(), comp );
1381 
1382  return aIp.size();
1383 }
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:187
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38
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.
VECTOR2I A
Definition: seg.h:48

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(), CN_ITEM::GetAnchor(), PNS::LINE_PLACER::handleSelfIntersections(), PNS::HullIntersection(), Intersects(), CADSTAR_SCH_ARCHIVE_LOADER::loadNets(), DRC_TEST_PROVIDER_ZONE_CONNECTIONS::Run(), and POLYGON_GEOM_MANAGER::updateLeaderPoints().

◆ Intersect() [2/2]

int SHAPE_LINE_CHAIN::Intersect ( const SHAPE_LINE_CHAIN aChain,
INTERSECTIONS aIp,
bool  aExcludeColinearAndTouching = false 
) 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 1401 of file shape_line_chain.cpp.

1403 {
1404  BOX2I bb_other = aChain.BBox();
1405 
1406  for( int s1 = 0; s1 < SegmentCount(); s1++ )
1407  {
1408  const SEG& a = CSegment( s1 );
1409  const BOX2I bb_cur( a.A, a.B - a.A );
1410 
1411  if( !bb_other.Intersects( bb_cur ) )
1412  continue;
1413 
1414  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
1415  {
1416  const SEG& b = aChain.CSegment( s2 );
1417  INTERSECTION is;
1418 
1419  is.index_our = s1;
1420  is.index_their = s2;
1421  is.is_corner_our = false;
1422  is.is_corner_their = false;
1423  is.valid = true;
1424 
1425  OPT_VECTOR2I p = a.Intersect( b );
1426 
1427  bool coll = a.Collinear( b );
1428 
1429  if( coll && ! aExcludeColinearAndTouching )
1430  {
1431  if( a.Contains( b.A ) )
1432  {
1433  is.p = b.A;
1434  is.is_corner_their = true;
1435  addIntersection(aIp, PointCount(), is);
1436  }
1437 
1438  if( a.Contains( b.B ) )
1439  {
1440  is.p = b.B;
1441  is.index_their++;
1442  is.is_corner_their = true;
1443  addIntersection( aIp, PointCount(), is );
1444  }
1445 
1446  if( b.Contains( a.A ) )
1447  {
1448  is.p = a.A;
1449  is.is_corner_our = true;
1450  addIntersection( aIp, PointCount(), is );
1451  }
1452 
1453  if( b.Contains( a.B ) )
1454  {
1455  is.p = a.B;
1456  is.index_our++;
1457  is.is_corner_our = true;
1458  addIntersection( aIp, PointCount(), is );
1459  }
1460  }
1461  else if( p )
1462  {
1463  is.p = *p;
1464  is.is_corner_our = false;
1465  is.is_corner_their = false;
1466 
1467  int distA = ( b.A - *p ).EuclideanNorm();
1468  int distB = ( b.B - *p ).EuclideanNorm();
1469 
1470  if( p == a.A )
1471  {
1472  is.is_corner_our = true;
1473  }
1474 
1475  if( p == a.B )
1476  {
1477  is.is_corner_our = true;
1478  is.index_our++;
1479  }
1480 
1481  if( p == b.A )
1482  {
1483  is.is_corner_their = true;
1484  }
1485 
1486  if( p == b.B )
1487  {
1488  is.is_corner_their = true;
1489  is.index_their++;
1490  }
1491 
1492  addIntersection( aIp, PointCount(), is );
1493  }
1494  }
1495  }
1496 
1497  return aIp.size();
1498 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
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:187
int PointCount() const
Return the number of points (vertices) in this line chain.
A 2D bounding box built on top of an origin point and size vector.
Definition: box2.h:41
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:217
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38
int SegmentCount() const
Return the number of segments in this line chain.
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:268
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
VECTOR2I A
Definition: seg.h:48
static void addIntersection(SHAPE_LINE_CHAIN::INTERSECTIONS &aIps, int aPc, const SHAPE_LINE_CHAIN::INTERSECTION &aP)
bool Contains(const SEG &aSeg) const
Definition: seg.h:331
VECTOR2I B
Definition: seg.h:49

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 1923 of file shape_line_chain.cpp.

1924 {
1926  return Intersect( aChain, dummy ) != 0;
1927 }
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
std::vector< INTERSECTION > INTERSECTIONS
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
Definition: sch_symbol.cpp:72

References dummy(), and Intersect().

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

◆ IsArcEnd()

bool SHAPE_LINE_CHAIN::IsArcEnd ( size_t  aIndex) const
inline

Definition at line 854 of file shape_line_chain.h.

855  {
856  return ( IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex ) ) );
857  }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
bool IsArcSegment(size_t aSegment) const
bool IsPtOnArc(size_t aPtIndex) const

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 822 of file shape_line_chain.h.

823  {
824  /*
825  * A segment is part of an arc except in the special case of two arcs next to each other
826  * but without a shared vertex. Here there is a segment between the end of the first arc
827  * and the start of the second arc.
828  */
829  size_t nextIdx = aSegment + 1;
830 
831  if( nextIdx > m_shapes.size() - 1 )
832  {
833  if( nextIdx == m_shapes.size() && m_closed )
834  nextIdx = 0; // segment between end point and first point
835  else
836  return false;
837  }
838 
839  return ( IsPtOnArc( aSegment )
840  && ( IsSharedPt( aSegment )
841  || m_shapes[aSegment].first == m_shapes[nextIdx].first ) );
842  }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
bool m_closed
is the line chain closed?
bool IsPtOnArc(size_t aPtIndex) const
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,...

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

Referenced by Append(), PNS::LINE::ClipToNearestObstacle(), Collide(), Collide(), PNS::LINE::dragCornerFree(), PNS::LINE::Is45Degree(), IsArcEnd(), IsArcStart(), Length(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeStep(), NearestPoint(), PNS::SHOVE::ShoveObstacleLine(), Slice(), and Split().

◆ IsArcStart()

bool SHAPE_LINE_CHAIN::IsArcStart ( size_t  aIndex) const
inline

Definition at line 845 of file shape_line_chain.h.

846  {
847  if( aIndex == 0 )
848  return IsPtOnArc( aIndex );
849 
850  return ( IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex - 1 ) ) );
851  }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
bool IsArcSegment(size_t aSegment) const
bool IsPtOnArc(size_t aPtIndex) const

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

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

References SHAPE_BASE::m_type, and SH_NULL.

◆ IsPtOnArc()

bool SHAPE_LINE_CHAIN::IsPtOnArc ( size_t  aPtIndex) const
inline

Definition at line 816 of file shape_line_chain.h.

817  {
818  return aPtIndex < m_shapes.size() && m_shapes[aPtIndex] != SHAPES_ARE_PT;
819  }
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,...
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

References m_shapes, and SHAPES_ARE_PT.

Referenced by BOOST_AUTO_TEST_CASE(), PNS::LINE::dragCorner45(), PNS::LINE::dragCornerFree(), PNS::LINE_PLACER::FixRoute(), PNS::LINE_PLACER::handlePullback(), Insert(), IsArcEnd(), IsArcSegment(), IsArcStart(), PNS::OPTIMIZER::mergeColinear(), PNS::LINE_PLACER::mergeHead(), Remove(), splitArc(), and PNS::DRAGGER::startDragSegment().

◆ 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 808 of file shape_line_chain.h.

809  {
810  return aIndex < m_shapes.size()
811  && m_shapes[aIndex].first != SHAPE_IS_PT
812  && m_shapes[aIndex].second != SHAPE_IS_PT;
813  }
static const ssize_t SHAPE_IS_PT
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,...

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 768 of file shape_line_chain.h.

769  {
770  return false;
771  }

◆ 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 607 of file shape_line_chain.cpp.

608 {
609  long long int l = 0;
610 
611  for( int i = 0; i < SegmentCount(); i++ )
612  {
613  // Only include segments that aren't part of arc shapes
614  if( !IsArcSegment(i) )
615  l += CSegment( i ).Length();
616  }
617 
618  for( int i = 0; i < ArcCount(); i++ )
619  l += CArcs()[i].GetLength();
620 
621  return l;
622 }
int Length() const
Return the length (this).
Definition: seg.h:350
size_t ArcCount() const
const std::vector< SHAPE_ARC > & CArcs() const
bool IsArcSegment(size_t aSegment) const
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 ArcCount(), CArcs(), CSegment(), IsArcSegment(), SEG::Length(), and SegmentCount().

Referenced by PNS::COST_ESTIMATOR::Add(), PNS::LINE::dragSegment45(), PNS::OPTIMIZER::fanoutCleanup(), PNS::MEANDER_SHAPE::MaxTunableLength(), PNS::SHOVE::onCollidingArc(), PNS::SHOVE::onCollidingSegment(), PNS::COST_ESTIMATOR::Remove(), PNS::COST_ESTIMATOR::Replace(), PNS::LINE_PLACER::rhWalkOnly(), PNS::WALKAROUND::Route(), PNS::SHOVE::shoveLineFromLoneVia(), PNS::DIFF_PAIR::Skew(), 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 153 of file shape_line_chain.cpp.

154 {
155  if( m_closed )
156  {
157  if( m_points.size() > 1 && m_points.front() == m_points.back() )
158  {
159  if( m_shapes.back() != SHAPES_ARE_PT )
160  {
161  m_shapes.front().second = m_shapes.front().first;
162  m_shapes.front().first = m_shapes.back().first;
163  }
164 
165  m_points.pop_back();
166  m_shapes.pop_back();
167 
169  }
170  }
171 }
void fixIndicesRotation()
Fix indices of this chain to ensure arcs are not split between the end and start indices.
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
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,...
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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 625 of file shape_line_chain.cpp.

626 {
627  for( auto& pt : m_points )
628  {
629  if( aX )
630  pt.x = -pt.x + 2 * aRef.x;
631 
632  if( aY )
633  pt.y = -pt.y + 2 * aRef.y;
634  }
635 
636  for( auto& arc : m_arcs )
637  arc.Mirror( aX, aY, aRef );
638 }
std::vector< SHAPE_ARC > m_arcs
std::vector< VECTOR2I > m_points
array of vertices

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

Referenced by 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 641 of file shape_line_chain.cpp.

642 {
643  for( auto& pt : m_points )
644  pt = axis.ReflectPoint( pt );
645 
646  for( auto& arc : m_arcs )
647  arc.Mirror( axis );
648 }
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:282
std::vector< SHAPE_ARC > m_arcs
std::vector< VECTOR2I > m_points
array of vertices

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

◆ Move()

void SHAPE_LINE_CHAIN::Move ( const VECTOR2I aVector)
inlineoverridevirtual

Implements SHAPE.

Definition at line 735 of file shape_line_chain.h.

736  {
737  for( auto& pt : m_points )
738  pt += aVector;
739 
740  for( auto& arc : m_arcs )
741  arc.Move( aVector );
742  }
std::vector< SHAPE_ARC > m_arcs
std::vector< VECTOR2I > m_points
array of vertices

References m_arcs, and m_points.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), PAD::BuildEffectiveShapes(), ZONE_FILLER::buildThermalSpokes(), 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 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 1782 of file shape_line_chain.cpp.

1784 {
1785  int min_d = INT_MAX;
1786  int nearest = 0;
1787 
1788  for( int i = 0; i < SegmentCount(); i++ )
1789  {
1790  int d = CSegment( i ).Distance( aP );
1791 
1792  if( d < min_d )
1793  {
1794  min_d = d;
1795  nearest = i;
1796  }
1797  }
1798 
1799  if( !aAllowInternalShapePoints )
1800  {
1801  //Snap to arc end points if the closest found segment is part of an arc segment
1802  if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
1803  {
1804  VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
1805  VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
1806 
1807  if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
1808  nearest++;
1809 
1810  // Is this the start or end of an arc? If so, return it directly
1811  if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
1812  {
1813  return m_points[nearest];
1814  }
1815  else
1816  {
1817  const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
1818  VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
1819  VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
1820 
1821  if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
1822  return nearestArc.GetP1();
1823  else
1824  return nearestArc.GetP0();
1825  }
1826 
1827  }
1828  }
1829 
1830  return CSegment( nearest ).NearestPoint( aP );
1831 }
const SHAPE_ARC & Arc(size_t aArc) const
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:318
Define a general 2D-vector/point.
Definition: vector2d.h:61
int PointCount() const
Return the number of points (vertices) in this line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
bool IsArcStart(size_t aIndex) const
bool IsArcSegment(size_t aSegment) const
std::vector< VECTOR2I > m_points
array of vertices
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:260
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.
VECTOR2I A
Definition: seg.h:48
bool IsArcEnd(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
const VECTOR2I & GetP1() const
Definition: shape_arc.h:112
VECTOR2I B
Definition: seg.h:49

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 PCB_GRID_HELPER::computeAnchors(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), CADSTAR_SCH_ARCHIVE_LOADER::loadBusses(), PNS::MoveDiagonal(), and PNS::DRAGGER::optimizeAndUpdateDraggedLine().

◆ NearestPoint() [2/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 1834 of file shape_line_chain.cpp.

1835 {
1836  int nearest = 0;
1837 
1838  dist = INT_MAX;
1839 
1840  for( int i = 0; i < PointCount(); i++ )
1841  {
1842  int d = aSeg.LineDistance( CPoint( i ) );
1843 
1844  if( d < dist )
1845  {
1846  dist = d;
1847  nearest = i;
1848  }
1849  }
1850 
1851  return CPoint( nearest );
1852 }
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:330
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.

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

◆ 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 1855 of file shape_line_chain.cpp.

1856 {
1857  int min_d = INT_MAX;
1858  int nearest = 0;
1859 
1860  for( int i = 0; i < SegmentCount(); i++ )
1861  {
1862  int d = CSegment( i ).Distance( aP );
1863 
1864  if( d < min_d )
1865  {
1866  min_d = d;
1867  nearest = i;
1868  }
1869  }
1870 
1871  return nearest;
1872 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:318
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 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:42
std::list< FACET * > facets
Definition: wrlfacet.h:143

References SHAPE::facets.

Referenced by WRL1FACESET::TranslateToSG(), X3DIFACESET::TranslateToSG(), and WRL2FACESET::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 953 of file shape_line_chain.cpp.

954 {
955  if( aPointIndex < 0 )
956  aPointIndex += PointCount();
957 
958  int lastIndex = PointCount() - 1;
959 
960  // First or last point?
961  if( ( aForwards && aPointIndex == lastIndex ) ||
962  ( !aForwards && aPointIndex == 0 ) )
963  {
964  return -1; // we don't want to wrap around
965  }
966 
967  int delta = aForwards ? 1 : -1;
968 
969  if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
970  return aPointIndex + delta;
971 
972  int arcStart = aPointIndex;
973 
974  // The second element should only get populated when the point is shared between two shapes.
975  // If not a shared point, then the index should always go on the first element.
976  assert( m_shapes[aPointIndex].first != SHAPE_IS_PT );
977 
978  // Start with the assumption the point is shared
979  auto arcIndex = [&]( int aIndex ) -> ssize_t
980  {
981  if( aForwards )
982  return ArcIndex( aIndex );
983  else
984  return reversedArcIndex( aIndex );
985  };
986 
987  ssize_t currentArcIdx = arcIndex( aPointIndex );
988 
989  // Now skip the rest of the arc
990  while( aPointIndex < lastIndex && aPointIndex >= 0 && arcIndex( aPointIndex ) == currentArcIdx )
991  aPointIndex += delta;
992 
993  if( aPointIndex == lastIndex )
994  {
995  if( !m_closed && arcIndex( aPointIndex ) == currentArcIdx )
996  return -1;
997  else
998  return lastIndex; // Segment between last point and the start
999  }
1000 
1001  bool indexStillOnArc = alg::pair_contains( m_shapes[aPointIndex], currentArcIdx );
1002 
1003  // We want the last vertex of the arc if the initial point was the start of one
1004  // Well-formed arcs should generate more than one point to travel above
1005  if( aPointIndex - arcStart > 1 && !indexStillOnArc )
1006  aPointIndex -= delta;
1007 
1008  return aPointIndex;
1009 }
static const ssize_t SHAPE_IS_PT
int PointCount() const
Return the number of points (vertices) in this line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
bool m_closed
is the line chain closed?
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,...
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
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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

Referenced by PNS::LINE::ClipVertexRange(), ALTIUM_PCB::HelperCreateBoardOutline(), PrevShape(), and Slice().

◆ operator!=()

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

Definition at line 719 of file shape_line_chain.h.

720  {
721  if( PointCount() != aRhs.PointCount() )
722  return true;
723 
724  for( int i = 0; i < PointCount(); i++ )
725  {
726  if( CPoint( i ) != aRhs.CPoint( i ) )
727  return true;
728  }
729 
730  return false;
731  }
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.

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 1936 of file shape_line_chain.cpp.

1937 {
1938  size_t n_pts;
1939  size_t n_arcs;
1940 
1941  m_points.clear();
1942  aStream >> n_pts;
1943 
1944  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
1945  if( n_pts > aStream.str().size() )
1946  return false;
1947 
1948  aStream >> m_closed;
1949  aStream >> n_arcs;
1950 
1951  if( n_arcs > aStream.str().size() )
1952  return false;
1953 
1954  for( size_t i = 0; i < n_pts; i++ )
1955  {
1956  int x, y;
1957  ssize_t ind;
1958  aStream >> x;
1959  aStream >> y;
1960  m_points.emplace_back( x, y );
1961 
1962  aStream >> ind;
1963  m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
1964  }
1965 
1966  for( size_t i = 0; i < n_arcs; i++ )
1967  {
1968  VECTOR2I p0, pc;
1969  double angle;
1970 
1971  aStream >> pc.x;
1972  aStream >> pc.y;
1973  aStream >> p0.x;
1974  aStream >> p0.y;
1975  aStream >> angle;
1976 
1977  m_arcs.emplace_back( pc, p0, angle );
1978  }
1979 
1980  return true;
1981 }
static const ssize_t SHAPE_IS_PT
Define a general 2D-vector/point.
Definition: vector2d.h:61
std::vector< SHAPE_ARC > m_arcs
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
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,...
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)

References PNS::angle(), 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 1501 of file shape_line_chain.cpp.

1502 {
1503  int sum = 0;
1504 
1505  for( int i = 0; i < SegmentCount(); i++ )
1506  {
1507  const SEG seg = CSegment( i );
1508  bool indexMatch = true;
1509 
1510  if( aIndex >= 0 )
1511  {
1512  if( aIndex == SegmentCount() )
1513  {
1514  indexMatch = ( i == SegmentCount() - 1 );
1515  }
1516  else
1517  {
1518  indexMatch = ( i == aIndex );
1519  }
1520  }
1521 
1522  if( indexMatch )
1523  {
1524  sum += ( aP - seg.A ).EuclideanNorm();
1525  return sum;
1526  }
1527  else
1528  sum += seg.Length();
1529  }
1530 
1531  return -1;
1532 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
int Length() const
Return the length (this).
Definition: seg.h:350
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
VECTOR2I A
Definition: seg.h:48

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 1984 of file shape_line_chain.cpp.

1985 {
1986  int total = 0;
1987 
1988  if( aPathLength == 0 )
1989  return CPoint( 0 );
1990 
1991  for( int i = 0; i < SegmentCount(); i++ )
1992  {
1993  const SEG& s = CSegment( i );
1994  int l = s.Length();
1995 
1996  if( total + l >= aPathLength )
1997  {
1998  VECTOR2I d( s.B - s.A );
1999  return s.A + d.Resize( aPathLength - total );
2000  }
2001 
2002  total += l;
2003  }
2004 
2005  return CPoint( -1 );
2006 }
int Length() const
Return the length (this).
Definition: seg.h:350
Define a general 2D-vector/point.
Definition: vector2d.h:61
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
VECTOR2I A
Definition: seg.h:48
VECTOR2I B
Definition: seg.h:49

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 318 of file shape_line_chain.h.

319  {
320  return m_points.size();
321  }
std::vector< VECTOR2I > m_points
array of vertices

References m_points.

Referenced by LABEL_MANAGER::Add(), POLYGON_GEOM_MANAGER::AddPoint(), SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::AddPolyline(), BOARD_ADAPTER::addSolidAreasShapes(), TRIANGLE_DISPLAY_LIST::AddToMiddleContourns(), CN_ZONE_LAYER::AnchorCount(), Append(), PNS::LINE::AppendVia(), ArePolylineEndPointsNearCircle(), ArePolylineMidPointsNearCircle(), PNS::NODE::AssembleLine(), PNS::TOPOLOGY::AssembleTuningPath(), BOOST_AUTO_TEST_CASE(), BuildConvexHull(), PAD::BuildEffectivePolygon(), PAD::BuildEffectiveShapes(), PNS::LINE::ChangedArea(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), CheckClearance(), CN_VISITOR::checkZoneZoneConnection(), CLastPoint(), PNS::LINE::ClipVertexRange(), convertPolygon(), convertToClipper(), PNS::coupledBypass(), CPoint(), PolygonTriangulation::createList(), CreatePadsShapesSection(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), PNS::cursorDistMinimum(), POLYGON_GEOM_MANAGER::DeleteLastCorner(), DIALOG_PAD_PRIMITIVE_POLY_PROPS::doValidate(), PNS::LINE::dragCornerFree(), PNS::dragCornerInternal(), PNS::LINE::dragSegment45(), PNS::DRAGGER::dragWalkaround(), KIGFX::GERBVIEW_PAINTER::draw(), APERTURE_MACRO::DrawApertureMacroShape(), KIGFX::CAIRO_GAL_BASE::drawPoly(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolyline(), KIGFX::PREVIEW::POLYGON_ITEM::drawPreviewShape(), 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(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), HPGL_PLOTTER::FlashPadRoundRect(), DXF_PLOTTER::FlashPadRoundRect(), PCB_PLUGIN::format(), Format(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), SHAPE_SIMPLE::GetPointCount(), 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::makePolysFromSegs(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeObtuse(), NearestPoint(), POLYGON_GEOM_MANAGER::NewPointClosesOutline(), NextShape(), operator!=(), BOOST_TEST_PRINT_NAMESPACE_OPEN::print_log_value< SHAPE_LINE_CHAIN >::operator()(), PNS::LINE_PLACER::optimizeTailHeadTransition(), BITMAPCONV_INFO::outputOnePolygon(), ALTIUM_PCB::ParsePolygons6Data(), ALTIUM_PCB::ParseShapeBasedRegions6Data(), PlotDrawingSheet(), BRDITEMS_PLOTTER::PlotFilledAreas(), GERBER_PLOTTER::PlotGerberRegion(), GERBER_PLOTTER::PlotPoly(), 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::shovedArea(), PNS::SHOVE::shoveLineFromLoneVia(), PNS::SHOVE::shoveLineToHullSet(), Simplify(), Slice(), splitArc(), PNS::DRAGGER::tryWalkaround(), POLYGON_GEOM_MANAGER::updateLeaderPoints(), 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 1535 of file shape_line_chain.cpp.

1537 {
1538  /*
1539  * Don't check the bounding box unless it's cached. Building it is about the same speed as
1540  * the rigorous test below and so just slows things down by doing potentially two tests.
1541  */
1542  if( aUseBBoxCache && GetCachedBBox() && !GetCachedBBox()->Contains( aPt ) )
1543  return false;
1544 
1545  if( !IsClosed() || GetPointCount() < 3 )
1546  return false;
1547 
1548  bool inside = false;
1549 
1550  /*
1551  * To check for interior points, we draw a line in the positive x direction from
1552  * the point. If it intersects an even number of segments, the point is outside the
1553  * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
1554  *
1555  * Note: slope might be denormal here in the case of a horizontal line but we require our
1556  * y to move from above to below the point (or vice versa)
1557  *
1558  * Note: we open-code CPoint() here so that we don't end up calculating the size of the
1559  * vector number-of-points times. This has a non-trivial impact on zone fill times.
1560  */
1561  int pointCount = GetPointCount();
1562 
1563  for( int i = 0; i < pointCount; )
1564  {
1565  const auto p1 = GetPoint( i++ );
1566  const auto p2 = GetPoint( i == pointCount ? 0 : i );
1567  const auto diff = p2 - p1;
1568 
1569  if( diff.y != 0 )
1570  {
1571  const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
1572 
1573  if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
1574  inside = !inside;
1575  }
1576  }
1577 
1578  // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
1579  // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
1580  if( aAccuracy <= 1 )
1581  return inside;
1582  else
1583  return inside || PointOnEdge( aPt, aAccuracy );
1584 }
virtual BOX2I * GetCachedBBox() const
Definition: shape.h:312
virtual bool IsClosed() const =0
virtual size_t GetPointCount() const =0
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:98
virtual const VECTOR2I GetPoint(int aIndex) const =0

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 Collide(), Collide(), SHAPE_LINE_CHAIN_BASE::Collide(), POLY_GRID_PARTITION::containsPoint(), SHAPE_POLY_SET::containsSingle(), ZONE::HitTestCutout(), MARKER_BASE::HitTestMarker(), DRC_RTREE::QueryColliding(), DRC_TEST_PROVIDER_ZONE_CONNECTIONS::Run(), SHAPE_LINE_CHAIN_BASE::SquaredDistance(), 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 1587 of file shape_line_chain.cpp.

1588 {
1589  return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
1590 }
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(), and PNS::LINE::Walkaround().

◆ PrevShape()

int SHAPE_LINE_CHAIN::PrevShape ( int  aPointIndex) const
inline

Definition at line 374 of file shape_line_chain.h.

375  {
376  return NextShape( aPointIndex, false );
377  }
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  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 729 of file shape_line_chain.cpp.

730 {
731  assert( m_shapes.size() == m_points.size() );
732 
733  if( aEndIndex < 0 )
734  aEndIndex += PointCount();
735 
736  if( aStartIndex < 0 )
737  aStartIndex += PointCount();
738 
739  if( aStartIndex >= PointCount() )
740  return;
741 
742  aEndIndex = std::min( aEndIndex, PointCount() - 1 );
743 
744  // Split arcs at start index and end just after the end index
745  if( IsPtOnArc( aStartIndex ) )
746  splitArc( aStartIndex );
747 
748  size_t nextIndex = static_cast<size_t>( aEndIndex ) + 1;
749 
750  if( IsPtOnArc( nextIndex ) )
751  splitArc( nextIndex );
752 
753  std::set<size_t> extra_arcs;
754  auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
755  {
756  if( aShapeIndex != SHAPE_IS_PT )
757  extra_arcs.insert( aShapeIndex );
758  };
759 
760  // Remove any overlapping arcs in the point range
761  for( int i = aStartIndex; i <= aEndIndex; i++ )
762  {
763  if( IsSharedPt( i ) )
764  {
765  if( i == aStartIndex )
766  {
767  logArcIdxRemoval( m_shapes[i].second ); // Only remove the arc on the second index
768 
769  // Ensure that m_shapes has been built correctly.
770  assert( i < aEndIndex || m_shapes[i + 1].first == m_shapes[i].second );
771 
772  continue;
773  }
774  else if( i == aEndIndex )
775  {
776  logArcIdxRemoval( m_shapes[i].first ); // Only remove the arc on the first index
777 
778  // Ensure that m_shapes has been built correctly.
779  assert( i > aStartIndex || IsSharedPt( i - 1 )
780  ? m_shapes[i - 1].second == m_shapes[i].first
781  : m_shapes[i - 1].first == m_shapes[i].first );
782  continue;
783  }
784  }
785 
786  alg::run_on_pair( m_shapes[i], logArcIdxRemoval );
787  }
788 
789  for( auto arc : extra_arcs )
790  convertArc( arc );
791 
792  m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
793  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
794  assert( m_shapes.size() == m_points.size() );
795 }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
static const ssize_t SHAPE_IS_PT
void convertArc(ssize_t aArcIndex)
Convert an arc to only a point chain by removing the arc and references.
int PointCount() const
Return the number of points (vertices) in this line chain.
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
std::vector< VECTOR2I > m_points
array of vertices
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
bool IsPtOnArc(size_t aPtIndex) const
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,...

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(), PNS::LINE_PLACER::reduceTail(), Remove(), RemoveShape(), and Replace().

◆ Remove() [2/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 567 of file shape_line_chain.h.

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

References Remove().

◆ 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 1030 of file shape_line_chain.cpp.

1031 {
1032  if( aPointIndex < 0 )
1033  aPointIndex += PointCount();
1034 
1035  if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
1036  {
1037  Remove( aPointIndex );
1038  return;
1039  }
1040 
1041  //@todo should this be replaced to use NextShape() / PrevShape()?
1042  int start = aPointIndex;
1043  int end = aPointIndex;
1044  int arcIdx = ArcIndex( aPointIndex );
1045 
1046  if( !IsSharedPt( aPointIndex ) )
1047  {
1048  // aPointIndex is not a shared point, so iterate backwards to find the start of the arc
1049  while( start >= 0 && m_shapes[start].first == arcIdx )
1050  start--;
1051 
1052  // Check if the previous point might be a shared point and decrement 'start' if so
1053  if( start >= 1 && m_shapes[static_cast<ssize_t>( start ) - 1].second == arcIdx )
1054  start--;
1055  }
1056 
1057  // For the end point we only need to check the first element in m_shapes (the second one is only
1058  // populated if there is an arc after the current one sharing the same point).
1059  while( end < static_cast<int>( m_shapes.size() ) - 1 && m_shapes[end].first == arcIdx )
1060  end++;
1061 
1062  Remove( start, end );
1063 }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
int PointCount() const
Return the number of points (vertices) in this line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
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,...
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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 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 651 of file shape_line_chain.cpp.

652 {
653  Remove( aStartIndex, aEndIndex );
654  Insert( aStartIndex, aP );
655  assert( m_shapes.size() == m_points.size() );
656 }
void Insert(size_t aVertex, const VECTOR2I &aP)
std::vector< VECTOR2I > m_points
array of vertices
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
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,...

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

◆ Replace() [2/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 659 of file shape_line_chain.cpp.

660 {
661  if( aEndIndex < 0 )
662  aEndIndex += PointCount();
663 
664  if( aStartIndex < 0 )
665  aStartIndex += PointCount();
666 
667  // We only process lines in order in this house
668  wxASSERT( aStartIndex <= aEndIndex );
669  wxASSERT( aEndIndex < m_points.size() );
670 
671  SHAPE_LINE_CHAIN newLine = aLine;
672 
673  // Zero points to add?
674  if( newLine.PointCount() == 0 )
675  {
676  Remove( aStartIndex, aEndIndex );
677  return;
678  }
679 
680  // Remove coincident points in the new line
681  if( newLine.m_points.front() == m_points[aStartIndex] )
682  {
683  aStartIndex++;
684  newLine.Remove( 0 );
685 
686  // Zero points to add?
687  if( newLine.PointCount() == 0 )
688  {
689  Remove( aStartIndex, aEndIndex );
690  return;
691  }
692  }
693 
694  if( newLine.m_points.back() == m_points[aEndIndex] && aEndIndex > 0 )
695  {
696  aEndIndex--;
697  newLine.Remove( -1 );
698  }
699 
700  Remove( aStartIndex, aEndIndex );
701 
702  // Zero points to add?
703  if( newLine.PointCount() == 0 )
704  return;
705 
706  // The total new arcs index is added to the new arc indices
707  size_t prev_arc_count = m_arcs.size();
708  std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.m_shapes;
709 
710  for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
711  {
712  alg::run_on_pair( shape_pair,
713  [&]( ssize_t& aShape )
714  {
715  if( aShape != SHAPE_IS_PT )
716  aShape += prev_arc_count;
717  } );
718  }
719 
720  m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
721  m_points.insert( m_points.begin() + aStartIndex, newLine.m_points.begin(),
722  newLine.m_points.end() );
723  m_arcs.insert( m_arcs.end(), newLine.m_arcs.begin(), newLine.m_arcs.end() );
724 
725  assert( m_shapes.size() == m_points.size() );
726 }
static const ssize_t SHAPE_IS_PT
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< SHAPE_ARC > m_arcs
std::vector< VECTOR2I > m_points
array of vertices
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
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
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,...
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...

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

◆ 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 561 of file shape_line_chain.cpp.

562 {
563  SHAPE_LINE_CHAIN a( *this );
564 
565  reverse( a.m_points.begin(), a.m_points.end() );
566  reverse( a.m_shapes.begin(), a.m_shapes.end() );
567  reverse( a.m_arcs.begin(), a.m_arcs.end() );
568 
569  for( auto& sh : a.m_shapes )
570  {
571  if( sh != SHAPES_ARE_PT )
572  {
573  alg::run_on_pair( sh,
574  [&]( ssize_t& aShapeIndex )
575  {
576  if( aShapeIndex != SHAPE_IS_PT )
577  aShapeIndex = a.m_arcs.size() - aShapeIndex - 1;
578  } );
579 
580  if( sh.second != SHAPE_IS_PT )
581  {
582  // If the second element is populated, the first one should be too!
583  assert( sh.first != SHAPE_IS_PT );
584 
585  // Switch round first and second in shared points, as part of reversing the chain
586  std::swap( sh.first, sh.second );
587  }
588  }
589  }
590 
591  for( SHAPE_ARC& arc : a.m_arcs )
592  arc.Reverse();
593 
594  a.m_closed = m_closed;
595 
596  return a;
597 }
static const ssize_t SHAPE_IS_PT
bool m_closed
is the line chain closed?
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
void Reverse()
Definition: shape_arc.cpp:578
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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::KEEP_TOPOLOGY_CONSTRAINT::Check(), PNS::SHOVE::checkShoveDirection(), convertToClipper(), 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(), 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 903 of file shape_line_chain.h.

904  {
905  if( IsSharedPt( aSegment ) )
906  return m_shapes[aSegment].first;
907  else
908  return m_shapes[aSegment].second;
909  }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
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,...

References IsSharedPt(), and m_shapes.

Referenced by NextShape().

◆ Rotate()

void SHAPE_LINE_CHAIN::Rotate ( double  aAngle,
const VECTOR2I aCenter = VECTOR2I( 0, 0 ) 
)
overridevirtual

Rotate all vertices by a given angle.

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

Implements SHAPE.

Definition at line 423 of file shape_line_chain.cpp.

424 {
425  for( auto& pt : m_points )
426  {
427  pt -= aCenter;
428  pt = pt.Rotate( aAngle );
429  pt += aCenter;
430  }
431 
432  for( auto& arc : m_arcs )
433  arc.Rotate( aAngle, aCenter );
434 }
std::vector< SHAPE_ARC > m_arcs
std::vector< VECTOR2I > m_points
array of vertices
VECTOR2< T > Rotate(double aAngle) const
Rotate the vector by a given angle.
Definition: vector2d.h:371

References m_arcs, m_points, and VECTOR2< T >::Rotate().

Referenced by PAD::BuildEffectiveShapes(), ZONE_FILLER::buildThermalSpokes(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), EDA_SHAPE::hitTest(), EDA_SHAPE::MakeEffectiveShapes(), and TransformArcToPolygon().

◆ 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 330 of file shape_line_chain.h.

331  {
332  if( aIndex < 0 )
333  aIndex += SegmentCount();
334 
335  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
336  return SEG( m_points[aIndex], m_points[0], aIndex );
337  else
338  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
339  }
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40

References m_closed, m_points, and SegmentCount().

Referenced by POLY_GRID_PARTITION::build(), BuildFootprintPolygonOutlines(), POLY_GRID_PARTITION::checkClearance(), PNS::DIFF_PAIR::CoupledSegmentPairs(), BOARD_ADAPTER::createPadWithClearance(), KIGFX::PCB_PAINTER::draw(), 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 295 of file shape_line_chain.h.

296  {
297  int c = m_points.size() - 1;
298  if( m_closed )
299  c++;
300 
301  return std::max( 0, c );
302  }
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices

References m_closed, and m_points.

Referenced by PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::NODE::AssembleLine(), POLY_GRID_PARTITION::build(), 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(), PCB_GRID_HELPER::computeAnchors(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), PNS::DIFF_PAIR::CoupledLength(), PNS::DIFF_PAIR::CoupledSegmentPairs(), BOARD_ADAPTER::createPadWithClearance(), CSegment(), PNS::cursorDistMinimum(), PNS::LINE::dragCorner45(), PNS::dragCornerInternal(), PNS::LINE::dragSegment45(), KIGFX::PCB_PAINTER::draw(), KIGFX::OPENGL_GAL::DrawPolygon(), PNS::DIFF_PAIR::Empty(), PNS::findCoupledVertices(), findEndSegments(), FindSegment(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), EDA_SHAPE::GetLength(), SHAPE_SIMPLE::GetSegmentCount(), GetSegmentCount(), PNS::LINE_PLACER::handlePullback(), PNS::DP_MEANDER_PLACER::HasPlacedAnything(), PNS::DIFF_PAIR_PLACER::HasPlacedAnything(), PNS::HullIntersection(), Intersect(), PNS::LINE::Is45Degree(), 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(), PNS::NODE::NearestObstacle(), 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(), SHAPE_POLY_SET::unfractureSingle(), POLYGON_GEOM_MANAGER::updateLeaderPoints(), PNS::LINE::Walkaround(), and HYPERLYNX_EXPORTER::writeBoardInfo().

◆ SelfIntersecting()

const OPT< 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 1642 of file shape_line_chain.cpp.

1643 {
1644  for( int s1 = 0; s1 < SegmentCount(); s1++ )
1645  {
1646  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
1647  {
1648  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
1649 
1650  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
1651  {
1652  INTERSECTION is;
1653  is.index_our = s1;
1654  is.index_their = s2;
1655  is.p = s2a;
1656  return is;
1657  }
1658  else if( CSegment( s1 ).Contains( s2b ) &&
1659  // for closed polylines, the ending point of the
1660  // last segment == starting point of the first segment
1661  // this is a normal case, not self intersecting case
1662  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
1663  {
1664  INTERSECTION is;
1665  is.index_our = s1;
1666  is.index_their = s2;
1667  is.p = s2b;
1668  return is;
1669  }
1670  else
1671  {
1672  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
1673 
1674  if( p )
1675  {
1676  INTERSECTION is;
1677  is.index_our = s1;
1678  is.index_their = s2;
1679  is.p = *p;
1680  return is;
1681  }
1682  }
1683  }
1684  }
1685 
1687 }
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:187
Define a general 2D-vector/point.
Definition: vector2d.h:61
bool IsClosed() const override
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38
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.
VECTOR2I A
Definition: seg.h:48
boost::optional< T > OPT
Definition: optional.h:7
VECTOR2I B
Definition: seg.h:49

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 256 of file shape_line_chain.h.

257  {
258  m_closed = aClosed;
260  }
bool m_closed
is the line chain closed?
void mergeFirstLastPointIfNeeded()
Merge the first and last point if they are the same and this chain is closed.

References m_closed, and mergeFirstLastPointIfNeeded().

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE::AddPolygon(), PNS::ArcHull(), EDA_SHAPE::beginEdit(), BOOST_AUTO_TEST_CASE(), POLY_GRID_PARTITION::build(), buildBoardBoundingBoxPoly(), BuildFootprintPolygonOutlines(), KI_TEST::BuildRectChain(), ZONE_FILLER::buildThermalSpokes(), SHAPE_POLY_SET::chamferFilletPolygon(), PNS::KEEP_TOPOLOGY_CONSTRAINT::Check(), CN_ZONE_LAYER::CN_ZONE_LAYER(), KI_TEST::CommonTestData::CommonTestData(), PCB_GRID_HELPER::computeAnchors(), convertPolygon(), ConvertPolygonToBlocks(), PNS::ConvexHull(), CONVERT_TOOL::CreateLines(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), KIGFX::GERBVIEW_PAINTER::draw(), EDA_SHAPE::endEdit(), SHAPE_POLY_SET::fractureSingle(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), HelperShapeLineChainFromAltiumVertices(), POLYGON_GEOM_MANAGER::IsSelfIntersecting(), IteratorFixture::IteratorFixture(), CONVERT_TOOL::makePolysFromRects(), CONVERT_TOOL::makePolysFromSegs(), GEOM_TEST::MakeSquarePolyLine(), SHAPE_POLY_SET::NewHole(), SHAPE_POLY_SET::NewOutline(), PNS::OctagonalHull(), SHAPE_RECT::Outline(), EAGLE_PLUGIN::packagePolygon(), SHAPE_POLY_SET::Parse(), ALTIUM_PCB::ParseRegions6Data(), PCB_PARSER::parseZONE(), BRDITEMS_PLOTTER::PlotFootprintGraphicItem(), BRDITEMS_PLOTTER::PlotPcbShape(), polygonArea(), RENDER_3D_OPENGL::reload(), DRC_TEST_PROVIDER_PHYSICAL_CLEARANCE::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 1012 of file shape_line_chain.cpp.

1013 {
1014  if( aIndex < 0 )
1015  aIndex += PointCount();
1016  else if( aIndex >= PointCount() )
1017  aIndex -= PointCount();
1018 
1019  m_points[aIndex] = aPos;
1020 
1021  alg::run_on_pair( m_shapes[aIndex],
1022  [&]( ssize_t& aIdx )
1023  {
1024  if( aIdx != SHAPE_IS_PT )
1025  convertArc( aIdx );
1026  } );
1027 }
static const ssize_t SHAPE_IS_PT
void convertArc(ssize_t aArcIndex)
Convert an arc to only a point chain by removing the arc and references.
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< VECTOR2I > m_points
array of vertices
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
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,...

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 275 of file shape_line_chain.h.

276  {
277  m_width = aWidth;
278  }
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...

References m_width.

Referenced by BOOST_AUTO_TEST_CASE(), ROUTER_PREVIEW_ITEM::Line(), CONVERT_TOOL::makePolysFromRects(), CONVERT_TOOL::makePolysFromSegs(), PNS::LINE::SetShape(), PNS::LINE::SetWidth(), and PNS::DIFF_PAIR::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 903 of file shape_line_chain.cpp.

904 {
905  if( m_points.empty() )
906  return 0;
907 
908  int numPoints = static_cast<int>( m_shapes.size() );
909  int numShapes = 0;
910  int arcIdx = -1;
911 
912  for( int i = 0; i < m_points.size() - 1; i++ )
913  {
914  if( m_shapes[i] == SHAPES_ARE_PT )
915  {
916  numShapes++;
917  }
918  else
919  {
920  // Expect that the second index only gets populated when the point is shared between
921  // two shapes. Otherwise, the shape index should always go on the first element of
922  // the pair.
923  assert( m_shapes[i].first != SHAPE_IS_PT );
924 
925  // Start assuming the point is shared with the previous arc
926  // If so, the new/next arc index should be located at the second
927  // element in the pair
928  arcIdx = m_shapes[i].second;
929 
930  if( arcIdx == SHAPE_IS_PT )
931  arcIdx = m_shapes[i].first; // Not a shared point
932 
933  numShapes++;
934 
935  // Now skip the rest of the arc
936  while( i < numPoints && m_shapes[i].first == arcIdx )
937  i++;
938 
939  // Add the "hidden" segment at the end of the arc, if it exists
940  if( i < numPoints && m_points[i] != m_points[i - 1] )
941  {
942  numShapes++;
943  }
944 
945  i--;
946  }
947  }
948 
949  return numShapes;
950 }
static const ssize_t SHAPE_IS_PT
std::vector< VECTOR2I > m_points
array of vertices
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,...
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

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 1690 of file shape_line_chain.cpp.

1691 {
1692  std::vector<VECTOR2I> pts_unique;
1693  std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
1694 
1695  if( PointCount() < 2 )
1696  {
1697  return *this;
1698  }
1699  else if( PointCount() == 2 )
1700  {
1701  if( m_points[0] == m_points[1] )
1702  m_points.pop_back();
1703 
1704  return *this;
1705  }
1706 
1707  int i = 0;
1708  int np = PointCount();
1709 
1710  // stage 1: eliminate duplicate vertices
1711  while( i < np )
1712  {
1713  int j = i + 1;
1714 
1715  // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
1716  // one of them is part of a shape and one is not.
1717  while( j < np && m_points[i] == m_points[j] &&
1718  ( m_shapes[i] == m_shapes[j] ||
1719  m_shapes[i] == SHAPES_ARE_PT ||
1720  m_shapes[j] == SHAPES_ARE_PT ) )
1721  {
1722  j++;
1723  }
1724 
1725  std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
1726 
1727  if( shapeToKeep == SHAPES_ARE_PT )
1728  shapeToKeep = m_shapes[j - 1];
1729 
1730  assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
1731  assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
1732 
1733  pts_unique.push_back( CPoint( i ) );
1734  shapes_unique.push_back( shapeToKeep );
1735 
1736  i = j;
1737  }
1738 
1739  m_points.clear();
1740  m_shapes.clear();
1741  np = pts_unique.size();
1742 
1743  i = 0;
1744 
1745  // stage 2: eliminate colinear segments
1746  for( i = 1 ; i < np - 1 ; i ++ )
1747  {
1748  const VECTOR2I p_prev = pts_unique[i - 1];
1749  const VECTOR2I midpoint = pts_unique[i];
1750  const VECTOR2I p_next = pts_unique[i + 1];
1751 
1752 
1753  if( aRemoveColinear && shapes_unique[i - 1] == SHAPES_ARE_PT
1754  && shapes_unique[i] == SHAPES_ARE_PT )
1755  {
1756  const auto distToMidpoint = SEG( p_prev, p_next ).LineDistance( midpoint );
1757  const auto isMidpointColinear = SEG( p_prev, p_next ).Collinear( SEG( p_prev, midpoint ) );
1758 
1759  if( distToMidpoint <= 1 || isMidpointColinear )
1760  {
1761  pts_unique.erase( pts_unique.begin() + i );
1762  shapes_unique.erase( shapes_unique.begin() + i );
1763  i--;
1764  np--;
1765  continue;
1766  }
1767  }
1768  }
1769 
1770  for( i = 0 ; i < np; i ++ )
1771  {
1772  m_points.push_back( pts_unique[i] );
1773  m_shapes.push_back( shapes_unique[i] );
1774  }
1775 
1776  assert( m_points.size() == m_shapes.size() );
1777 
1778  return *this;
1779 }
Define a general 2D-vector/point.
Definition: vector2d.h:61
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:330
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< SHAPE_ARC > m_arcs
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
std::vector< VECTOR2I > m_points
array of vertices
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:268
Definition: seg.h:40
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,...
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

References SEG::Collinear(), CPoint(), SEG::LineDistance(), m_arcs, m_points, m_shapes, PointCount(), and SHAPES_ARE_PT.

Referenced by PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), PNS::NODE::AssembleLine(), PNS::DIFF_PAIR_PLACER::attemptWalk(), DIRECTION_45::BuildInitialTrace(), PNS::LINE::ChangedArea(), PNS::CORNER_COUNT_LIMIT_CONSTRAINT::Check(), CN_ZONE_LAYER::CN_ZONE_LAYER(), 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(), CONVERT_TOOL::makePolysFromSegs(), PNS::OPTIMIZER::mergeDpStep(), PNS::OPTIMIZER::mergeFull(), PNS::LINE_PLACER::mergeHead(), PNS::DP_MEANDER_PLACER::Move(), PNS::SHOVE::onCollidingSolid(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::LINE_PLACER::rhShoveOnly(), 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 1066 of file shape_line_chain.cpp.

1067 {
1068  SHAPE_LINE_CHAIN rv;
1069 
1070  if( aEndIndex < 0 )
1071  aEndIndex += PointCount();
1072 
1073  if( aStartIndex < 0 )
1074  aStartIndex += PointCount();
1075 
1076  int numPoints = static_cast<int>( m_points.size() );
1077 
1078 
1079  if( IsArcSegment( aStartIndex ) && !IsArcStart( aStartIndex ) )
1080  {
1081  // Cutting in middle of an arc, lets split it
1082  ssize_t arcIndex = ArcIndex( aStartIndex );
1083  const SHAPE_ARC& currentArc = Arc( arcIndex );
1084 
1085  // Copy the points as arc points
1086  for( size_t i = aStartIndex; arcIndex == ArcIndex( i ); i++ )
1087  {
1088  rv.m_points.push_back( m_points[i] );
1089  rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1090  rv.m_bbox.Merge( m_points[i] );
1091  }
1092 
1093  // Create a new arc from the existing one, with different start point.
1094  SHAPE_ARC newArc;
1095 
1096  VECTOR2I newArcStart = m_points[aStartIndex];
1097 
1098  newArc.ConstructFromStartEndCenter( newArcStart, currentArc.GetP1(),
1099  currentArc.GetCenter(),
1100  currentArc.IsClockwise() );
1101 
1102 
1103  rv.m_arcs.push_back( newArc );
1104 
1105  aStartIndex += rv.PointCount();
1106  }
1107 
1108  for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i = NextShape( i ) )
1109  {
1110  if( i == -1 )
1111  return rv; // NextShape reached the end
1112 
1113  if( IsArcStart( i ) )
1114  {
1115  const SHAPE_ARC &currentArc = Arc( ArcIndex( i ) );
1116  int nextShape = NextShape( i );
1117  bool isLastShape = nextShape < 0;
1118 
1119  if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1120  || ( nextShape > aEndIndex ) )
1121  {
1122  if( i == aEndIndex )
1123  {
1124  // Single point on an arc, just append the single point
1125  rv.Append( m_points[i] );
1126  return rv;
1127  }
1128 
1129  // Cutting in middle of an arc, lets split it
1130  ssize_t arcIndex = ArcIndex( i );
1131  const SHAPE_ARC& currentArc = Arc( arcIndex );
1132 
1133  // Copy the points as arc points
1134  for( ; i <= aEndIndex && i < numPoints; i++ )
1135  {
1136  if( arcIndex != ArcIndex( i ) )
1137  break;
1138 
1139  rv.m_points.push_back( m_points[i] );
1140  rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1141  rv.m_bbox.Merge( m_points[i] );
1142  }
1143 
1144  // Create a new arc from the existing one, with different end point.
1145  SHAPE_ARC newArc;
1146 
1147  VECTOR2I newArcEnd = m_points[aEndIndex];
1148 
1149  newArc.ConstructFromStartEndCenter( currentArc.GetP0(), newArcEnd,
1150  currentArc.GetCenter(),
1151  currentArc.IsClockwise() );
1152 
1153 
1154  rv.m_arcs.push_back( newArc );
1155 
1156  return rv;
1157  }
1158  else
1159  {
1160  // append the whole arc
1161  rv.Append( currentArc );
1162  }
1163 
1164  if( isLastShape )
1165  return rv;
1166  }
1167  else
1168  {
1169  wxASSERT_MSG( !IsArcSegment( i ),
1170  wxT( "Still on an arc segment, we missed something..." ) );
1171 
1172  rv.Append( m_points[i] );
1173  }
1174  }
1175 
1176  return rv;
1177 }
BOX2I m_bbox
cached bounding box
const SHAPE_ARC & Arc(size_t aArc) const
bool IsClockwise() const
Definition: shape_arc.cpp:351
static const ssize_t SHAPE_IS_PT
Define a general 2D-vector/point.
Definition: vector2d.h:61
int PointCount() const
Return the number of points (vertices) in this line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
std::vector< SHAPE_ARC > m_arcs
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
bool IsArcStart(size_t aIndex) const
bool IsArcSegment(size_t aSegment) const
std::vector< VECTOR2I > m_points
array of vertices
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363
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,...
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:201
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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.
const VECTOR2I & GetP1() const
Definition: shape_arc.h:112
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:424

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::ClipVertexRange(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::LINE::dragCorner45(), PNS::dragCornerInternal(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::LINE_PLACER::rhWalkOnly(), 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 818 of file shape_line_chain.cpp.

819 {
820  int ii = -1;
821  int min_dist = 2;
822 
823  int found_index = Find( aP );
824 
825  for( int s = 0; s < SegmentCount(); s++ )
826  {
827  const SEG seg = CSegment( s );
828  int dist = seg.Distance( aP );
829 
830  // make sure we are not producing a 'slightly concave' primitive. This might happen
831  // if aP lies very close to one of already existing points.
832  if( dist < min_dist && seg.A != aP && seg.B != aP )
833  {
834  min_dist = dist;
835  if( found_index < 0 )
836  ii = s;
837  else if( s < found_index )
838  ii = s;
839  }
840  }
841 
842  if( ii < 0 )
843  ii = found_index;
844 
845  if( ii >= 0 )
846  {
847  // Don't create duplicate points
848  if( GetPoint( ii ) == aP )
849  return ii;
850 
851  size_t newIndex = static_cast<size_t>( ii ) + 1;
852 
853  if( IsArcSegment( ii ) )
854  {
855  m_points.insert( m_points.begin() + newIndex, aP );
856  m_shapes.insert( m_shapes.begin() + newIndex, { ArcIndex( ii ), SHAPE_IS_PT } );
857  splitArc( newIndex, true ); // Make the inserted point a shared point
858  }
859  else
860  {
861  Insert( newIndex, aP );
862  }
863 
864  return newIndex;
865  }
866 
867  return -1;
868 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:318
static const ssize_t SHAPE_IS_PT
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
void Insert(size_t aVertex, const VECTOR2I &aP)
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
bool IsArcSegment(size_t aSegment) const
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
std::vector< VECTOR2I > m_points
array of vertices
int SegmentCount() const
Return the number of segments in this line chain.
virtual const VECTOR2I GetPoint(int aIndex) const override
Definition: seg.h:40
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,...
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
VECTOR2I A
Definition: seg.h:48
VECTOR2I B
Definition: seg.h:49

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::ClipToNearestObstacle(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::LINE_PLACER::rhWalkOnly(), 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 220 of file shape_line_chain.cpp.

221 {
222  if( aPtIndex < 0 )
223  aPtIndex += m_shapes.size();
224 
225  if( !IsSharedPt( aPtIndex ) && IsArcStart( aPtIndex ) )
226  return; // Nothing to do
227 
228  if( !IsPtOnArc( aPtIndex ) )
229  return; // Nothing to do
230 
231  wxCHECK_MSG( aPtIndex < static_cast<ssize_t>( m_shapes.size() ), /* void */,
232  wxT( "Invalid point index requested." ) );
233 
234  if( IsSharedPt( aPtIndex ) || IsArcEnd( aPtIndex ) )
235  {
236  if( aCoincident || aPtIndex == 0 )
237  return; // nothing to do
238 
239  ssize_t firstArcIndex = m_shapes[aPtIndex].first;
240 
241  const VECTOR2I& newStart = m_arcs[firstArcIndex].GetP0(); // don't amend the start
242  const VECTOR2I& newEnd = m_points[aPtIndex - 1];
243  amendArc( firstArcIndex, newStart, newEnd );
244 
245  if( IsSharedPt( aPtIndex ) )
246  {
247  m_shapes[aPtIndex].first = m_shapes[aPtIndex].second;
248  m_shapes[aPtIndex].second = SHAPE_IS_PT;
249  }
250  else
251  {
252  m_shapes[aPtIndex] = SHAPES_ARE_PT;
253  }
254 
255  return;
256  }
257 
258  ssize_t currArcIdx = ArcIndex( aPtIndex );
259  SHAPE_ARC& currentArc = m_arcs[currArcIdx];
260 
261  SHAPE_ARC newArc1;
262  SHAPE_ARC newArc2;
263 
264  VECTOR2I arc1End = ( aCoincident ) ? m_points[aPtIndex] : m_points[aPtIndex - 1];
265  VECTOR2I arc2Start = m_points[aPtIndex];
266 
267  newArc1.ConstructFromStartEndCenter( currentArc.GetP0(), arc1End, currentArc.GetCenter(),
268  currentArc.IsClockwise() );
269 
270  newArc2.ConstructFromStartEndCenter( arc2Start, currentArc.GetP1(), currentArc.GetCenter(),
271  currentArc.IsClockwise() );
272 
273  if( !aCoincident && ArcIndex( aPtIndex - 1 ) != currArcIdx )
274  {
275  //Ignore newArc1 as it has zero points
276  m_arcs[currArcIdx] = newArc2;
277  }
278  else
279  {
280  m_arcs[currArcIdx] = newArc1;
281  m_arcs.insert( m_arcs.begin() + currArcIdx + 1, newArc2 );
282 
283  if( aCoincident )
284  {
285  m_shapes[aPtIndex].second = currArcIdx + 1;
286  aPtIndex++;
287  }
288 
289  // Only change the arc indices for the second half of the point range
290  for( int i = aPtIndex; i < PointCount(); i++ )
291  {
292  alg::run_on_pair( m_shapes[i], [&]( ssize_t& aIndex ) {
293  if( aIndex != SHAPE_IS_PT )
294  aIndex++;
295  } );
296  }
297  }
298 }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
bool IsClockwise() const
Definition: shape_arc.cpp:351
static const ssize_t SHAPE_IS_PT
Define a general 2D-vector/point.
Definition: vector2d.h:61
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< SHAPE_ARC > m_arcs
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
bool IsArcStart(size_t aIndex) const
std::vector< VECTOR2I > m_points
array of vertices
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
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
void amendArc(size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)
bool IsPtOnArc(size_t aPtIndex) const
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,...
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:201
bool IsArcEnd(size_t aIndex) const
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT
const VECTOR2I & GetP1() const
Definition: shape_arc.h:112
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:424

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 804 of file shape_line_chain.cpp.

805 {
807 
808  if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
809  return 0;
810 
811  for( size_t s = 0; s < GetSegmentCount(); s++ )
812  d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
813 
814  return d;
815 }
virtual bool IsClosed() const =0
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:72
virtual size_t GetSegmentCount() const =0
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
VECTOR2I::extended_type ecoord
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.
virtual const SEG GetSegment(int aIndex) const =0

References VECTOR2< T >::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()

SHAPE_TYPE SHAPE_BASE::Type ( ) const
inlineinherited

◆ 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 285 of file shape_line_chain.h.

286  {
287  return m_width;
288  }
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...

References m_width.

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

Friends And Related Function Documentation

◆ SHAPE_POLY_SET

friend class SHAPE_POLY_SET
friend

Definition at line 865 of file shape_line_chain.h.

Member Data Documentation

◆ m_arcs

◆ m_bbox

BOX2I SHAPE_LINE_CHAIN::m_bbox
mutableprivate

cached bounding box

Definition at line 966 of file shape_line_chain.h.

Referenced by Append(), GenerateBBoxCache(), GetCachedBBox(), 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 951 of file shape_line_chain.h.

Referenced by Append(), ArcIndex(), Clear(), convertArc(), convertToClipper(), 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 110 of file shape.h.

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

◆ 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 963 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 122 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: