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

50 {
51  for(size_t i = 0; i < aV.size(); i+= 2 )
52  {
53  Append( aV[i], aV[i+1] );
54  }
55 }
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 57 of file shape_line_chain.cpp.

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

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

2020 {
2021  // see https://www.mathopenref.com/coordpolygonarea2.html
2022 
2023  if( !m_closed )
2024  return 0.0;
2025 
2026  double area = 0.0;
2027  int size = m_points.size();
2028 
2029  for( int i = 0, j = size - 1; i < size; ++i )
2030  {
2031  area += ( (double) m_points[j].x + m_points[i].x ) *
2032  ( (double) m_points[j].y - m_points[i].y );
2033  j = i;
2034  }
2035 
2036  if( aAbsolute )
2037  return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
2038  else
2039  return -area * 0.5; // The result would be negative if points are anti-clockwise
2040 }
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:492
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:285
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 601 of file shape_line_chain.cpp.

602 {
603  for( ssize_t arcIndex = m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
604  convertArc( arcIndex );
605 }
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 1940 of file shape_line_chain.cpp.

1941 {
1942  return new SHAPE_LINE_CHAIN( *this );
1943 }
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 355 of file shape_line_chain.cpp.

357 {
358  if( IsClosed() && PointInside( aP, aClearance ) )
359  {
360  if( aLocation )
361  *aLocation = aP;
362 
363  if( aActual )
364  *aActual = 0;
365 
366  return true;
367  }
368 
369  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
370  SEG::ecoord clearance_sq = SEG::Square( aClearance );
371  VECTOR2I nearest;
372 
373  // Collide line segments
374  for( size_t i = 0; i < GetSegmentCount(); i++ )
375  {
376  if( IsArcSegment( i ) )
377  continue;
378 
379  const SEG& s = GetSegment( i );
380  VECTOR2I pn = s.NearestPoint( aP );
381  SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
382 
383  if( dist_sq < closest_dist_sq )
384  {
385  nearest = pn;
386  closest_dist_sq = dist_sq;
387 
388  if( closest_dist_sq == 0 )
389  break;
390 
391  // If we're not looking for aActual then any collision will do
392  if( closest_dist_sq < clearance_sq && !aActual )
393  break;
394  }
395  }
396 
397  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
398  {
399  if( aLocation )
400  *aLocation = nearest;
401 
402  if( aActual )
403  *aActual = sqrt( closest_dist_sq );
404 
405  return true;
406  }
407 
408  // Collide arc segments
409  for( size_t i = 0; i < ArcCount(); i++ )
410  {
411  const SHAPE_ARC& arc = Arc( i );
412 
413  // The arcs in the chain should have zero width
414  wxASSERT_MSG( arc.GetWidth() == 0, "Invalid arc width - should be zero" );
415 
416  if( arc.Collide( aP, aClearance, aActual, aLocation ) )
417  return true;
418  }
419 
420  return false;
421 }
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:227
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(), and PCB_SELECTION_TOOL::hitTestDistance().

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

494 {
495  if( IsClosed() && PointInside( aSeg.A ) )
496  {
497  if( aLocation )
498  *aLocation = aSeg.A;
499 
500  if( aActual )
501  *aActual = 0;
502 
503  return true;
504  }
505 
506  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
507  SEG::ecoord clearance_sq = SEG::Square( aClearance );
508  VECTOR2I nearest;
509 
510  // Collide line segments
511  for( size_t i = 0; i < GetSegmentCount(); i++ )
512  {
513  if( IsArcSegment( i ) )
514  continue;
515 
516  const SEG& s = GetSegment( i );
517  SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
518 
519  if( dist_sq < closest_dist_sq )
520  {
521  if( aLocation )
522  nearest = s.NearestPoint( aSeg );
523 
524  closest_dist_sq = dist_sq;
525 
526  if( closest_dist_sq == 0 )
527  break;
528 
529  // If we're not looking for aActual then any collision will do
530  if( closest_dist_sq < clearance_sq && !aActual )
531  break;
532  }
533  }
534 
535  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
536  {
537  if( aLocation )
538  *aLocation = nearest;
539 
540  if( aActual )
541  *aActual = sqrt( closest_dist_sq );
542 
543  return true;
544  }
545 
546  // Collide arc segments
547  for( size_t i = 0; i < ArcCount(); i++ )
548  {
549  const SHAPE_ARC& arc = Arc( i );
550 
551  // The arcs in the chain should have zero width
552  wxASSERT_MSG( arc.GetWidth() == 0, "Invalid arc width - should be zero" );
553 
554  if( arc.Collide( aSeg, aClearance, aActual, aLocation ) )
555  return true;
556  }
557 
558  return false;
559 }
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:39
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:227
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 1914 of file shape_line_chain.cpp.

1915 {
1916  SHAPE_LINE_CHAIN a(*this), b( aOther );
1917  a.Simplify();
1918  b.Simplify();
1919 
1920  if( a.m_points.size() != b.m_points.size() )
1921  return false;
1922 
1923  for( int i = 0; i < a.PointCount(); i++ )
1924  {
1925  if( a.CPoint( i ) != b.CPoint( i ) )
1926  return false;
1927  }
1928 
1929  return true;
1930 }
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 175 of file shape_line_chain.cpp.

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

103 {
104  ClipperLib::Path c_path;
105  SHAPE_LINE_CHAIN input;
106  bool orientation = Area( false ) >= 0;
107  ssize_t shape_offset = aArcBuffer.size();
108 
109  if( orientation != aRequiredOrientation )
110  input = Reverse();
111  else
112  input = *this;
113 
114  for( int i = 0; i < input.PointCount(); i++ )
115  {
116  const VECTOR2I& vertex = input.CPoint( i );
117 
118  CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
119  size_t z_value_ptr = aZValueBuffer.size();
120  aZValueBuffer.push_back( z_value );
121 
122  c_path.push_back( ClipperLib::IntPoint( vertex.x, vertex.y, z_value_ptr ) );
123  }
124 
125  aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
126 
127  return c_path;
128 }
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(), 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(), 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(), 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 799 of file shape_line_chain.cpp.

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

873 {
874  for( int s = 0; s < PointCount(); s++ )
875  {
876  if( aThreshold == 0 )
877  {
878  if( CPoint( s ) == aP )
879  return s;
880  }
881  else
882  {
883  if( (CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
884  return s;
885  }
886  }
887 
888  return -1;
889 }
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 892 of file shape_line_chain.cpp.

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

132 {
133  wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
134 
135  if( m_shapes.size() <= 1 || m_arcs.size() <= 1 )
136  return;
137 
138  size_t rotations = 0;
139  size_t numPoints = m_points.size();
140 
141  while( ArcIndex( 0 ) != SHAPE_IS_PT
142  && ArcIndex( 0 ) == ArcIndex( numPoints - 1 ) )
143  {
144  // Rotate right
145  std::rotate( m_points.rbegin(), m_points.rbegin() + 1, m_points.rend() );
146  std::rotate( m_shapes.rbegin(), m_shapes.rbegin() + 1, m_shapes.rend() );
147 
148  // Sanity check - avoid infinite loops
149  wxCHECK( rotations++ <= m_shapes.size(), /* void */ );
150  }
151 }
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 1885 of file shape_line_chain.cpp.

1886 {
1887  std::stringstream ss;
1888 
1889  ss << "SHAPE_LINE_CHAIN( { ";
1890 
1891  for( int i = 0; i < PointCount(); i++ )
1892  {
1893  ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
1894 
1895  if( i != PointCount() -1 )
1896  ss << ", ";
1897  }
1898 
1899  ss << "}, " << ( m_closed ? "true" : "false" );
1900  ss << " );";
1901 
1902  return ss.str();
1903 
1904  /* fixme: arcs
1905  for( size_t i = 0; i < m_arcs.size(); i++ )
1906  ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
1907  << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
1908  << m_arcs[i].GetCentralAngle();
1909 
1910  return ss.str();*/
1911 }
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:154
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(), 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:154
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 1933 of file shape_line_chain.cpp.

1934 {
1936  return Intersect( aChain, dummy ) != 0;
1937 }
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()

bool SHAPE_LINE_CHAIN::IsClosed ( ) const
inlineoverridevirtual

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

609 {
610  long long int l = 0;
611 
612  for( int i = 0; i < SegmentCount(); i++ )
613  {
614  // Only include segments that aren't part of arc shapes
615  if( !IsArcSegment(i) )
616  l += CSegment( i ).Length();
617  }
618 
619  for( int i = 0; i < ArcCount(); i++ )
620  l += CArcs()[i].GetLength();
621 
622  return l;
623 }
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 154 of file shape_line_chain.cpp.

155 {
156  if( m_closed )
157  {
158  if( m_points.size() > 1 && m_points.front() == m_points.back() )
159  {
160  if( m_shapes.back() != SHAPES_ARE_PT )
161  {
162  m_shapes.front().second = m_shapes.front().first;
163  m_shapes.front().first = m_shapes.back().first;
164  }
165 
166  m_points.pop_back();
167  m_shapes.pop_back();
168 
170  }
171  }
172 }
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 626 of file shape_line_chain.cpp.

627 {
628  for( auto& pt : m_points )
629  {
630  if( aX )
631  pt.x = -pt.x + 2 * aRef.x;
632 
633  if( aY )
634  pt.y = -pt.y + 2 * aRef.y;
635  }
636 
637  for( auto& arc : m_arcs )
638  arc.Mirror( aX, aY, aRef );
639 }
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 642 of file shape_line_chain.cpp.

643 {
644  for( auto& pt : m_points )
645  pt = axis.ReflectPoint( pt );
646 
647  for( auto& arc : m_arcs )
648  arc.Mirror( axis );
649 }
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:249
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 1792 of file shape_line_chain.cpp.

1794 {
1795  int min_d = INT_MAX;
1796  int nearest = 0;
1797 
1798  for( int i = 0; i < SegmentCount(); i++ )
1799  {
1800  int d = CSegment( i ).Distance( aP );
1801 
1802  if( d < min_d )
1803  {
1804  min_d = d;
1805  nearest = i;
1806  }
1807  }
1808 
1809  if( !aAllowInternalShapePoints )
1810  {
1811  //Snap to arc end points if the closest found segment is part of an arc segment
1812  if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
1813  {
1814  VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
1815  VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
1816 
1817  if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
1818  nearest++;
1819 
1820  // Is this the start or end of an arc? If so, return it directly
1821  if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
1822  {
1823  return m_points[nearest];
1824  }
1825  else
1826  {
1827  const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
1828  VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
1829  VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
1830 
1831  if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
1832  return nearestArc.GetP1();
1833  else
1834  return nearestArc.GetP0();
1835  }
1836 
1837  }
1838  }
1839 
1840  return CSegment( nearest ).NearestPoint( aP );
1841 }
const SHAPE_ARC & Arc(size_t aArc) const
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
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:227
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 1844 of file shape_line_chain.cpp.

1845 {
1846  int nearest = 0;
1847 
1848  dist = INT_MAX;
1849 
1850  for( int i = 0; i < PointCount(); i++ )
1851  {
1852  int d = aSeg.LineDistance( CPoint( i ) );
1853 
1854  if( d < dist )
1855  {
1856  dist = d;
1857  nearest = i;
1858  }
1859  }
1860 
1861  return CPoint( nearest );
1862 }
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:297
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 1865 of file shape_line_chain.cpp.

1866 {
1867  int min_d = INT_MAX;
1868  int nearest = 0;
1869 
1870  for( int i = 0; i < SegmentCount(); i++ )
1871  {
1872  int d = CSegment( i ).Distance( aP );
1873 
1874  if( d < min_d )
1875  {
1876  min_d = d;
1877  nearest = i;
1878  }
1879  }
1880 
1881  return nearest;
1882 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
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 954 of file shape_line_chain.cpp.

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

1947 {
1948  size_t n_pts;
1949  size_t n_arcs;
1950 
1951  m_points.clear();
1952  aStream >> n_pts;
1953 
1954  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
1955  if( n_pts > aStream.str().size() )
1956  return false;
1957 
1958  aStream >> m_closed;
1959  aStream >> n_arcs;
1960 
1961  if( n_arcs > aStream.str().size() )
1962  return false;
1963 
1964  for( size_t i = 0; i < n_pts; i++ )
1965  {
1966  int x, y;
1967  ssize_t ind;
1968  aStream >> x;
1969  aStream >> y;
1970  m_points.emplace_back( x, y );
1971 
1972  aStream >> ind;
1973  m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
1974  }
1975 
1976  for( size_t i = 0; i < n_arcs; i++ )
1977  {
1978  VECTOR2I p0, pc;
1979  double angle;
1980 
1981  aStream >> pc.x;
1982  aStream >> pc.y;
1983  aStream >> p0.x;
1984  aStream >> p0.y;
1985  aStream >> angle;
1986 
1987  m_arcs.emplace_back( pc, p0, angle );
1988  }
1989 
1990  return true;
1991 }
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 1994 of file shape_line_chain.cpp.

1995 {
1996  int total = 0;
1997 
1998  if( aPathLength == 0 )
1999  return CPoint( 0 );
2000 
2001  for( int i = 0; i < SegmentCount(); i++ )
2002  {
2003  const SEG& s = CSegment( i );
2004  int l = s.Length();
2005 
2006  if( total + l >= aPathLength )
2007  {
2008  VECTOR2I d( s.B - s.A );
2009  return s.A + d.Resize( aPathLength - total );
2010  }
2011 
2012  total += l;
2013  }
2014 
2015  return CPoint( -1 );
2016 }
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(), 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(), 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(), 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(), 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 730 of file shape_line_chain.cpp.

731 {
732  assert( m_shapes.size() == m_points.size() );
733 
734  if( aEndIndex < 0 )
735  aEndIndex += PointCount();
736 
737  if( aStartIndex < 0 )
738  aStartIndex += PointCount();
739 
740  if( aStartIndex >= PointCount() )
741  return;
742 
743  aEndIndex = std::min( aEndIndex, PointCount() - 1 );
744 
745  // Split arcs at start index and end just after the end index
746  if( IsPtOnArc( aStartIndex ) )
747  splitArc( aStartIndex );
748 
749  size_t nextIndex = static_cast<size_t>( aEndIndex ) + 1;
750 
751  if( IsPtOnArc( nextIndex ) )
752  splitArc( nextIndex );
753 
754  std::set<size_t> extra_arcs;
755  auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
756  {
757  if( aShapeIndex != SHAPE_IS_PT )
758  extra_arcs.insert( aShapeIndex );
759  };
760 
761  // Remove any overlapping arcs in the point range
762  for( int i = aStartIndex; i <= aEndIndex; i++ )
763  {
764  if( IsSharedPt( i ) )
765  {
766  if( i == aStartIndex )
767  {
768  logArcIdxRemoval( m_shapes[i].second ); // Only remove the arc on the second index
769 
770  // Ensure that m_shapes has been built correctly.
771  assert( i < aEndIndex || m_shapes[i + 1].first == m_shapes[i].second );
772 
773  continue;
774  }
775  else if( i == aEndIndex )
776  {
777  logArcIdxRemoval( m_shapes[i].first ); // Only remove the arc on the first index
778 
779  // Ensure that m_shapes has been built correctly.
780  assert( i > aStartIndex || IsSharedPt( i - 1 )
781  ? m_shapes[i - 1].second == m_shapes[i].first
782  : m_shapes[i - 1].first == m_shapes[i].first );
783  continue;
784  }
785  }
786 
787  alg::run_on_pair( m_shapes[i], logArcIdxRemoval );
788  }
789 
790  for( auto arc : extra_arcs )
791  convertArc( arc );
792 
793  m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
794  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
795  assert( m_shapes.size() == m_points.size() );
796 }
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 1031 of file shape_line_chain.cpp.

1032 {
1033  if( aPointIndex < 0 )
1034  aPointIndex += PointCount();
1035 
1036  if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
1037  {
1038  Remove( aPointIndex );
1039  return;
1040  }
1041 
1042  //@todo should this be replaced to use NextShape() / PrevShape()?
1043  int start = aPointIndex;
1044  int end = aPointIndex;
1045  int arcIdx = ArcIndex( aPointIndex );
1046 
1047  if( !IsSharedPt( aPointIndex ) )
1048  {
1049  // aPointIndex is not a shared point, so iterate backwards to find the start of the arc
1050  while( start >= 0 && m_shapes[start].first == arcIdx )
1051  start--;
1052 
1053  // Check if the previous point might be a shared point and decrement 'start' if so
1054  if( start >= 1 && m_shapes[static_cast<ssize_t>( start ) - 1].second == arcIdx )
1055  start--;
1056  }
1057 
1058  // For the end point we only need to check the first element in m_shapes (the second one is only
1059  // populated if there is an arc after the current one sharing the same point).
1060  while( end < static_cast<int>( m_shapes.size() ) - 1 && m_shapes[end].first == arcIdx )
1061  end++;
1062 
1063  Remove( start, end );
1064 }
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 652 of file shape_line_chain.cpp.

653 {
654  Remove( aStartIndex, aEndIndex );
655  Insert( aStartIndex, aP );
656  assert( m_shapes.size() == m_points.size() );
657 }
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 660 of file shape_line_chain.cpp.

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

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

425 {
426  for( auto& pt : m_points )
427  {
428  pt -= aCenter;
429  pt = pt.Rotate( aAngle );
430  pt += aCenter;
431  }
432 
433  for( auto& arc : m_arcs )
434  arc.Rotate( aAngle, aCenter );
435 }
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(), 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(), 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:154
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(), and DIALOG_PAD_PRIMITIVE_POLY_PROPS::doValidate().

◆ 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(), 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(), 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(), polygonArea(), RENDER_3D_OPENGL::reload(), 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 1013 of file shape_line_chain.cpp.

1014 {
1015  if( aIndex < 0 )
1016  aIndex += PointCount();
1017  else if( aIndex >= PointCount() )
1018  aIndex -= PointCount();
1019 
1020  m_points[aIndex] = aPos;
1021 
1022  alg::run_on_pair( m_shapes[aIndex],
1023  [&]( ssize_t& aIdx )
1024  {
1025  if( aIdx != SHAPE_IS_PT )
1026  convertArc( aIdx );
1027  } );
1028 }
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 904 of file shape_line_chain.cpp.

905 {
906  if( m_points.empty() )
907  return 0;
908 
909  int numPoints = static_cast<int>( m_shapes.size() );
910  int numShapes = 0;
911  int arcIdx = -1;
912 
913  for( int i = 0; i < m_points.size() - 1; i++ )
914  {
915  if( m_shapes[i] == SHAPES_ARE_PT )
916  {
917  numShapes++;
918  }
919  else
920  {
921  // Expect that the second index only gets populated when the point is shared between
922  // two shapes. Otherwise, the shape index should always go on the first element of
923  // the pair.
924  assert( m_shapes[i].first != SHAPE_IS_PT );
925 
926  // Start assuming the point is shared with the previous arc
927  // If so, the new/next arc index should be located at the second
928  // element in the pair
929  arcIdx = m_shapes[i].second;
930 
931  if( arcIdx == SHAPE_IS_PT )
932  arcIdx = m_shapes[i].first; // Not a shared point
933 
934  numShapes++;
935 
936  // Now skip the rest of the arc
937  while( i < numPoints && m_shapes[i].first == arcIdx )
938  i++;
939 
940  // Add the "hidden" segment at the end of the arc, if it exists
941  if( i < numPoints && m_points[i] != m_points[i - 1] )
942  {
943  numShapes++;
944  }
945 
946  i--;
947  }
948  }
949 
950  return numShapes;
951 }
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  while( i < np - 2 )
1747  {
1748  const VECTOR2I p0 = pts_unique[i];
1749  const VECTOR2I p1 = pts_unique[i + 1];
1750  int n = i;
1751 
1752  if( aRemoveColinear && shapes_unique[i] == SHAPES_ARE_PT
1753  && shapes_unique[i + 1] == SHAPES_ARE_PT )
1754  {
1755  while( n < np - 2
1756  && ( SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1
1757  || SEG( p0, p1 ).Collinear( SEG( p1, pts_unique[n + 2] ) ) ) )
1758  n++;
1759  }
1760 
1761  m_points.push_back( p0 );
1762  m_shapes.push_back( shapes_unique[i] );
1763 
1764  if( n > i )
1765  i = n;
1766 
1767  if( n == np - 2 )
1768  {
1769  m_points.push_back( pts_unique[np - 1] );
1770  m_shapes.push_back( shapes_unique[np - 1] );
1771  return *this;
1772  }
1773 
1774  i++;
1775  }
1776 
1777  if( np > 1 )
1778  {
1779  m_points.push_back( pts_unique[np - 2] );
1780  m_shapes.push_back( shapes_unique[np - 2] );
1781  }
1782 
1783  m_points.push_back( pts_unique[np - 1] );
1784  m_shapes.push_back( shapes_unique[np - 1] );
1785 
1786  assert( m_points.size() == m_shapes.size() );
1787 
1788  return *this;
1789 }
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
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
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 CPoint(), 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 1067 of file shape_line_chain.cpp.

1068 {
1069  SHAPE_LINE_CHAIN rv;
1070 
1071  if( aEndIndex < 0 )
1072  aEndIndex += PointCount();
1073 
1074  if( aStartIndex < 0 )
1075  aStartIndex += PointCount();
1076 
1077  int numPoints = static_cast<int>( m_points.size() );
1078 
1079 
1080  if( IsArcSegment( aStartIndex ) && !IsArcStart( aStartIndex ) )
1081  {
1082  // Cutting in middle of an arc, lets split it
1083  ssize_t arcIndex = ArcIndex( aStartIndex );
1084  const SHAPE_ARC& currentArc = Arc( arcIndex );
1085 
1086  // Copy the points as arc points
1087  for( size_t i = aStartIndex; arcIndex == ArcIndex( i ); i++ )
1088  {
1089  rv.m_points.push_back( m_points[i] );
1090  rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1091  rv.m_bbox.Merge( m_points[i] );
1092  }
1093 
1094  // Create a new arc from the existing one, with different start point.
1095  SHAPE_ARC newArc;
1096 
1097  VECTOR2I newArcStart = m_points[aStartIndex];
1098 
1099  newArc.ConstructFromStartEndCenter( newArcStart, currentArc.GetP1(),
1100  currentArc.GetCenter(),
1101  currentArc.IsClockwise() );
1102 
1103 
1104  rv.m_arcs.push_back( newArc );
1105 
1106  aStartIndex += rv.PointCount();
1107  }
1108 
1109  for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i = NextShape( i ) )
1110  {
1111  if( i == -1 )
1112  return rv; // NextShape reached the end
1113 
1114  if( IsArcStart( i ) )
1115  {
1116  const SHAPE_ARC &currentArc = Arc( ArcIndex( i ) );
1117  int nextShape = NextShape( i );
1118  bool isLastShape = nextShape < 0;
1119 
1120  if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1121  || ( nextShape > aEndIndex ) )
1122  {
1123  if( i == aEndIndex )
1124  {
1125  // Single point on an arc, just append the single point
1126  rv.Append( m_points[i] );
1127  return rv;
1128  }
1129 
1130  // Cutting in middle of an arc, lets split it
1131  ssize_t arcIndex = ArcIndex( i );
1132  const SHAPE_ARC& currentArc = Arc( arcIndex );
1133 
1134  // Copy the points as arc points
1135  for( ; i <= aEndIndex && i < numPoints; i++ )
1136  {
1137  if( arcIndex != ArcIndex( i ) )
1138  break;
1139 
1140  rv.m_points.push_back( m_points[i] );
1141  rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1142  rv.m_bbox.Merge( m_points[i] );
1143  }
1144 
1145  // Create a new arc from the existing one, with different end point.
1146  SHAPE_ARC newArc;
1147 
1148  VECTOR2I newArcEnd = m_points[aEndIndex];
1149 
1150  newArc.ConstructFromStartEndCenter( currentArc.GetP0(), newArcEnd,
1151  currentArc.GetCenter(),
1152  currentArc.IsClockwise() );
1153 
1154 
1155  rv.m_arcs.push_back( newArc );
1156 
1157  return rv;
1158  }
1159  else
1160  {
1161  // append the whole arc
1162  rv.Append( currentArc );
1163  }
1164 
1165  if( isLastShape )
1166  return rv;
1167  }
1168  else
1169  {
1170  wxASSERT_MSG( !IsArcSegment( i ), "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 819 of file shape_line_chain.cpp.

820 {
821  int ii = -1;
822  int min_dist = 2;
823 
824  int found_index = Find( aP );
825 
826  for( int s = 0; s < SegmentCount(); s++ )
827  {
828  const SEG seg = CSegment( s );
829  int dist = seg.Distance( aP );
830 
831  // make sure we are not producing a 'slightly concave' primitive. This might happen
832  // if aP lies very close to one of already existing points.
833  if( dist < min_dist && seg.A != aP && seg.B != aP )
834  {
835  min_dist = dist;
836  if( found_index < 0 )
837  ii = s;
838  else if( s < found_index )
839  ii = s;
840  }
841  }
842 
843  if( ii < 0 )
844  ii = found_index;
845 
846  if( ii >= 0 )
847  {
848  // Don't create duplicate points
849  if( GetPoint( ii ) == aP )
850  return ii;
851 
852  size_t newIndex = static_cast<size_t>( ii ) + 1;
853 
854  if( IsArcSegment( ii ) )
855  {
856  m_points.insert( m_points.begin() + newIndex, aP );
857  m_shapes.insert( m_shapes.begin() + newIndex, { ArcIndex( ii ), SHAPE_IS_PT } );
858  splitArc( newIndex, true ); // Make the inserted point a shared point
859  }
860  else
861  {
862  Insert( newIndex, aP );
863  }
864 
865  return newIndex;
866  }
867 
868  return -1;
869 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
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 221 of file shape_line_chain.cpp.

222 {
223  if( aPtIndex < 0 )
224  aPtIndex += m_shapes.size();
225 
226  if( !IsSharedPt( aPtIndex ) && IsArcStart( aPtIndex ) )
227  return; // Nothing to do
228 
229  if( !IsPtOnArc( aPtIndex ) )
230  return; // Nothing to do
231 
232  wxCHECK_MSG( aPtIndex < static_cast<ssize_t>( m_shapes.size() ), /* void */,
233  "Invalid point index requested." );
234 
235  if( IsSharedPt( aPtIndex ) || IsArcEnd( aPtIndex ) )
236  {
237  if( aCoincident || aPtIndex == 0 )
238  return; // nothing to do
239 
240  ssize_t firstArcIndex = m_shapes[aPtIndex].first;
241 
242  const VECTOR2I& newStart = m_arcs[firstArcIndex].GetP0(); // don't amend the start
243  const VECTOR2I& newEnd = m_points[aPtIndex - 1];
244  amendArc( firstArcIndex, newStart, newEnd );
245 
246  if( IsSharedPt( aPtIndex ) )
247  {
248  m_shapes[aPtIndex].first = m_shapes[aPtIndex].second;
249  m_shapes[aPtIndex].second = SHAPE_IS_PT;
250  }
251  else
252  {
253  m_shapes[aPtIndex] = SHAPES_ARE_PT;
254  }
255 
256  return;
257  }
258 
259  ssize_t currArcIdx = ArcIndex( aPtIndex );
260  SHAPE_ARC& currentArc = m_arcs[currArcIdx];
261 
262  SHAPE_ARC newArc1;
263  SHAPE_ARC newArc2;
264 
265  VECTOR2I arc1End = ( aCoincident ) ? m_points[aPtIndex] : m_points[aPtIndex - 1];
266  VECTOR2I arc2Start = m_points[aPtIndex];
267 
268  newArc1.ConstructFromStartEndCenter( currentArc.GetP0(), arc1End, currentArc.GetCenter(),
269  currentArc.IsClockwise() );
270 
271  newArc2.ConstructFromStartEndCenter( arc2Start, currentArc.GetP1(), currentArc.GetCenter(),
272  currentArc.IsClockwise() );
273 
274  if( !aCoincident && ArcIndex( aPtIndex - 1 ) != currArcIdx )
275  {
276  //Ignore newArc1 as it has zero points
277  m_arcs[currArcIdx] = newArc2;
278  }
279  else
280  {
281  m_arcs[currArcIdx] = newArc1;
282  m_arcs.insert( m_arcs.begin() + currArcIdx + 1, newArc2 );
283 
284  if( aCoincident )
285  {
286  m_shapes[aPtIndex].second = currArcIdx + 1;
287  aPtIndex++;
288  }
289 
290  // Only change the arc indices for the second half of the point range
291  for( int i = aPtIndex; i < PointCount(); i++ )
292  {
293  alg::run_on_pair( m_shapes[i], [&]( ssize_t& aIndex ) {
294  if( aIndex != SHAPE_IS_PT )
295  aIndex++;
296  } );
297  }
298  }
299 }
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 805 of file shape_line_chain.cpp.

806 {
808 
809  if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
810  return 0;
811 
812  for( size_t s = 0; s < GetSegmentCount(); s++ )
813  d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
814 
815  return d;
816 }
virtual bool IsClosed() const =0
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:39
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: