KiCad PCB EDA Suite
SHAPE_LINE_CHAIN Class Reference

Represent a polyline (an zero-thickness chain of connected line 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 ()
 
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 aPoint is in 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
 
const BOX2I BBoxFromCache () const
 
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 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...
 
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)
 
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...
 

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 (an zero-thickness chain of connected line segments).

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

◆ point_citer

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

Definition at line 80 of file shape_line_chain.h.

◆ point_iter

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

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

143  :
145  m_closed( false ),
146  m_width( 0 )
147  {}
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 149 of file shape_line_chain.h.

149  :
151  m_points( aShape.m_points ),
152  m_shapes( aShape.m_shapes ),
153  m_arcs( aShape.m_arcs ),
154  m_closed( aShape.m_closed ),
155  m_width( aShape.m_width ),
156  m_bbox( aShape.m_bbox )
157  {}
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 49 of file shape_line_chain.cpp.

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

161  :
163  m_closed( aClosed ),
164  m_width( 0 )
165  {
166  m_points.reserve( aV.size() );
167 
168  for( auto pt : aV )
169  m_points.emplace_back( pt.x, pt.y );
170 
171  m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
172  }
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 174 of file shape_line_chain.h.

174  :
176  m_closed( aClosed ),
177  m_width( 0 )
178  {
179  m_points = aV;
180  m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
181  }
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 183 of file shape_line_chain.h.

183  :
185  m_closed( aClosed ),
186  m_width( 0 )
187  {
189  m_arcs.emplace_back( aArc );
190  m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( m_points.size(), SHAPES_ARE_PT );
191  }
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
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:459
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 SHAPE_ARC::ConvertToPolyline(), CPoints(), m_arcs, m_points, m_shapes, and SHAPES_ARE_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 58 of file shape_line_chain.cpp.

60  :
62  m_closed( true ), m_width( 0 )
63 {
64  std::map<ssize_t, ssize_t> loadedArcs;
65  m_points.reserve( aPath.size() );
66  m_shapes.reserve( aPath.size() );
67 
68  auto loadArc =
69  [&]( ssize_t aArcIndex ) -> ssize_t
70  {
71  if( aArcIndex == SHAPE_IS_PT )
72  {
73  return SHAPE_IS_PT;
74  }
75  else if( loadedArcs.count( aArcIndex ) == 0 )
76  {
77  loadedArcs.insert( { aArcIndex, m_arcs.size() } );
78  m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
79  }
80 
81  return loadedArcs.at(aArcIndex);
82  };
83 
84  for( size_t ii = 0; ii < aPath.size(); ++ii )
85  {
86  Append( aPath[ii].X, aPath[ii].Y );
87 
88  m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
89  m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
90  }
91 }
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition: shape.h:243
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(), m_arcs, m_points, m_shapes, and SHAPE_IS_PT.

◆ ~SHAPE_LINE_CHAIN()

virtual SHAPE_LINE_CHAIN::~SHAPE_LINE_CHAIN ( )
inlinevirtual

Definition at line 197 of file shape_line_chain.h.

198  {}

Member Function Documentation

◆ amendArc()

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

Definition at line 153 of file shape_line_chain.cpp.

155 {
156  wxCHECK_MSG( aArcIndex < m_arcs.size(), /* void */,
157  "Invalid arc index requested." );
158 
159  SHAPE_ARC& theArc = m_arcs[aArcIndex];
160 
161  // Try to preseve the centre of the original arc
162  SHAPE_ARC newArc;
163  newArc.ConstructFromStartEndCenter( aNewStart, aNewEnd, theArc.GetCenter(),
164  theArc.IsClockwise() );
165 
166  m_arcs[aArcIndex] = newArc;
167 }
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:199

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

857  {
858  amendArc( aArcIndex, m_arcs[aArcIndex].GetP0(), aNewEnd );
859  }
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 851 of file shape_line_chain.h.

852  {
853  amendArc( aArcIndex, aNewStart, m_arcs[aArcIndex].GetP1() );
854  }
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 458 of file shape_line_chain.h.

459  {
460  VECTOR2I v( aX, aY );
461  Append( v, aAllowDuplication );
462  }
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(), 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(), 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(), ConvertArcToPolyline(), SHAPE_ARC::ConvertToPolyline(), PNS::ConvexHull(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), PNS::OPTIMIZER::customBreakouts(), PNS::MEANDER_PLACER::doMove(), PNS::LINE::dragSegment45(), PNS::MEANDER_SHAPE::forward(), SHAPE_POLY_SET::fractureSingle(), PNS::MEANDER_SHAPE::genMeanderShape(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), HelperShapeLineChainFromAltiumVertices(), LIB_POLYLINE::HitTest(), 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::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(), CONVERT_TOOL::PolyToLines(), 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 472 of file shape_line_chain.h.

473  {
474  if( m_points.size() == 0 )
475  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
476 
477  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
478  {
479  m_points.push_back( aP );
480  m_shapes.push_back( SHAPES_ARE_PT );
481  m_bbox.Merge( aP );
482  }
483  }
BOX2I m_bbox
cached bounding box
BOX2< VECTOR2I > BOX2I
Definition: box2.h:506
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
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 887 of file shape_line_chain.cpp.

888 {
889  assert( m_shapes.size() == m_points.size() );
890 
891  if( aOtherLine.PointCount() == 0 )
892  {
893  return;
894  }
895 
896  size_t num_arcs = m_arcs.size();
897  m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
898 
899  auto fixShapeIndices =
900  [&]( const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
901  {
902  std::pair<ssize_t, ssize_t> retval = aShapeIndices;
903 
904  alg::run_on_pair( retval, [&]( ssize_t& aIndex )
905  {
906  if( aIndex != SHAPE_IS_PT )
907  aIndex = aIndex + num_arcs;
908  } );
909 
910  return retval;
911  };
912 
913  if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
914  {
915  const VECTOR2I p = aOtherLine.CPoint( 0 );
916  m_points.push_back( p );
917  m_shapes.push_back( fixShapeIndices( aOtherLine.CShapes()[0] ) );
918  m_bbox.Merge( p );
919  }
920  else if( aOtherLine.IsArcSegment( 0 ) )
921  {
922  // Associate the new arc shape with the last point of this chain
923  if( m_shapes.back() == SHAPES_ARE_PT )
924  m_shapes.back().first = aOtherLine.CShapes()[0].first + num_arcs;
925  else
926  m_shapes.back().second = aOtherLine.CShapes()[0].first + num_arcs;
927  }
928 
929 
930  for( int i = 1; i < aOtherLine.PointCount(); i++ )
931  {
932  const VECTOR2I p = aOtherLine.CPoint( i );
933  m_points.push_back( p );
934 
935  ssize_t arcIndex = aOtherLine.ArcIndex( i );
936 
937  if( arcIndex != ssize_t( SHAPE_IS_PT ) )
938  {
939  m_shapes.push_back( fixShapeIndices( aOtherLine.m_shapes[i] ) );
940  }
941  else
942  m_shapes.push_back( SHAPES_ARE_PT );
943 
944  m_bbox.Merge( p );
945  }
946 
947  assert( m_shapes.size() == m_points.size() );
948 }
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:43
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 ArcIndex(), CPoint(), CShapes(), IsArcSegment(), m_arcs, m_bbox, m_points, m_shapes, BOX2< Vec >::Merge(), 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 951 of file shape_line_chain.cpp.

952 {
953  SHAPE_LINE_CHAIN chain = aArc.ConvertToPolyline();
954 
955  // @todo should the below 4 LOC be moved to SHAPE_ARC::ConvertToPolyline ?
956  chain.m_arcs.push_back( aArc );
957 
958  for( auto& sh : chain.m_shapes )
959  sh.first = 0;
960 
961  Append( chain );
962 
963  assert( m_shapes.size() == m_points.size() );
964 }
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
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:459
Represent a polyline (an zero-thickness chain of connected line segments).

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

◆ Arc()

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

Definition at line 761 of file shape_line_chain.h.

762  {
763  return m_arcs[aArc];
764  }
std::vector< SHAPE_ARC > m_arcs

References m_arcs.

Referenced by PNS::NODE::Add(), PNS::LINE_PLACER::FixRoute(), PCB_IO::format(), GEOM_TEST::IsOutlineValid(), and GERBER_PLOTTER::PlotPoly().

◆ ArcCount()

size_t SHAPE_LINE_CHAIN::ArcCount ( ) const
inline

Definition at line 745 of file shape_line_chain.h.

746  {
747  return m_arcs.size();
748  }
std::vector< SHAPE_ARC > m_arcs

References m_arcs.

Referenced by PNS::LINE::ArcCount(), 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 753 of file shape_line_chain.h.

754  {
755  if( IsSharedPt( aSegment ) )
756  return m_shapes[aSegment].second;
757  else
758  return m_shapes[aSegment].first;
759  }
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(), PNS::LINE_PLACER::FixRoute(), PCB_IO::format(), PNS::LINE_PLACER::handlePullback(), GEOM_TEST::IsOutlineValid(), PNS::LINE_PLACER::mergeHead(), GERBER_PLOTTER::PlotPoly(), RemoveShape(), Slice(), 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 1695 of file shape_line_chain.cpp.

1696 {
1697  // see https://www.mathopenref.com/coordpolygonarea2.html
1698 
1699  if( !m_closed )
1700  return 0.0;
1701 
1702  double area = 0.0;
1703  int size = m_points.size();
1704 
1705  for( int i = 0, j = size - 1; i < size; ++i )
1706  {
1707  area += ( (double) m_points[j].x + m_points[i].x ) *
1708  ( (double) m_points[j].y - m_points[i].y );
1709  j = i;
1710  }
1711 
1712  if( aAbsolute )
1713  return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
1714  else
1715  return -area * 0.5; // The result would be negative if points are anti-clockwise
1716 }
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(), polygonArea(), 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 396 of file shape_line_chain.h.

397  {
398  BOX2I bbox;
399  bbox.Compute( m_points );
400 
401  if( aClearance != 0 || m_width != 0 )
402  bbox.Inflate( aClearance + m_width );
403 
404  return bbox;
405  }
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(), and PolygonTriangulation::TesselatePolygon().

◆ BBoxFromCache()

const BOX2I SHAPE_LINE_CHAIN::BBoxFromCache ( ) const
inline

Definition at line 415 of file shape_line_chain.h.

416  {
417  return m_bbox;
418  }
BOX2I m_bbox
cached bounding box

References m_bbox.

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

383  {
384  return m_arcs;
385  }
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 1309 of file shape_line_chain.cpp.

1310 {
1311  if( !PointCount() )
1312  return false;
1313  else if( PointCount() == 1 )
1314  return m_points[0] == aP;
1315 
1316  for( int i = 0; i < SegmentCount(); i++ )
1317  {
1318  const SEG s = CSegment( i );
1319 
1320  if( s.A == aP || s.B == aP )
1321  return true;
1322 
1323  if( s.Distance( aP ) <= aDist )
1324  return true;
1325  }
1326 
1327  return false;
1328 }
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 374 of file shape_line_chain.h.

375  {
376  return m_points[static_cast<size_t>( PointCount() ) - 1];
377  }
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 POLYGON_GEOM_MANAGER::DeleteLastCorner(), and POLYGON_GEOM_MANAGER::updateLeaderPoints().

◆ Clear()

void SHAPE_LINE_CHAIN::Clear ( )
inline

Remove all points from the line chain.

Definition at line 207 of file shape_line_chain.h.

208  {
209  m_points.clear();
210  m_arcs.clear();
211  m_shapes.clear();
212  m_closed = false;
213  }
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::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 405 of file shape_line_chain.cpp.

406 {
407  for( ssize_t arcIndex = m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
408  convertArc( arcIndex );
409 }
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 1616 of file shape_line_chain.cpp.

1617 {
1618  return new SHAPE_LINE_CHAIN( *this );
1619 }
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 917 of file shape_collisions.cpp.

918 {
919  return collideShapes( this, aShape, aClearance, nullptr, nullptr, aMTV );
920 }
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_RECT, SHAPE_SEGMENT, and SHAPE_COMPOUND.

Definition at line 923 of file shape_collisions.cpp.

924 {
925  return collideShapes( this, aShape, aClearance, aActual, aLocation, nullptr );
926 }
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_BASE::Collide ( const VECTOR2I aP,
int  aClearance = 0,
int *  aActual = nullptr,
VECTOR2I aLocation = nullptr 
) const
overridevirtualinherited

Check if point aP lies closer to us than aClearance.

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.

Definition at line 245 of file shape_line_chain.cpp.

247 {
248  if( IsClosed() && PointInside( aP, aClearance ) )
249  {
250  if( aLocation )
251  *aLocation = aP;
252 
253  if( aActual )
254  *aActual = 0;
255 
256  return true;
257  }
258 
259  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
260  SEG::ecoord clearance_sq = SEG::Square( aClearance );
261  VECTOR2I nearest;
262 
263  for( size_t i = 0; i < GetSegmentCount(); i++ )
264  {
265  const SEG& s = GetSegment( i );
266  VECTOR2I pn = s.NearestPoint( aP );
267  SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
268 
269  if( dist_sq < closest_dist_sq )
270  {
271  nearest = pn;
272  closest_dist_sq = dist_sq;
273 
274  if( closest_dist_sq == 0 )
275  break;
276 
277  // If we're not looking for aActual then any collision will do
278  if( closest_dist_sq < clearance_sq && !aActual )
279  break;
280  }
281  }
282 
283  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
284  {
285  if( aLocation )
286  *aLocation = nearest;
287 
288  if( aActual )
289  *aActual = sqrt( closest_dist_sq );
290 
291  return true;
292  }
293 
294  return false;
295 }
virtual bool IsClosed() const =0
VECTOR2I::extended_type ecoord
Definition: seg.h:43
Define a general 2D-vector/point.
Definition: vector2d.h:61
virtual size_t GetSegmentCount() const =0
static SEG::ecoord Square(int a)
Definition: seg.h:122
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
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
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(), SEG::NearestPoint(), SHAPE_LINE_CHAIN_BASE::PointInside(), and SEG::Square().

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

◆ Collide() [4/4]

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

Check if segment aSeg lies closer to us than aClearance.

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

Implements SHAPE.

Reimplemented in SHAPE_SIMPLE.

Definition at line 312 of file shape_line_chain.cpp.

314 {
315  if( IsClosed() && PointInside( aSeg.A ) )
316  {
317  if( aLocation )
318  *aLocation = aSeg.A;
319 
320  if( aActual )
321  *aActual = 0;
322 
323  return true;
324  }
325 
326  SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
327  SEG::ecoord clearance_sq = SEG::Square( aClearance );
328  VECTOR2I nearest;
329 
330  for( size_t i = 0; i < GetSegmentCount(); i++ )
331  {
332  const SEG& s = GetSegment( i );
333  SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
334 
335  if( dist_sq < closest_dist_sq )
336  {
337  if( aLocation )
338  nearest = s.NearestPoint( aSeg );
339 
340  closest_dist_sq = dist_sq;
341 
342  if( closest_dist_sq == 0)
343  break;
344 
345  // If we're not looking for aActual then any collision will do
346  if( closest_dist_sq < clearance_sq && !aActual )
347  break;
348  }
349  }
350 
351  if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
352  {
353  if( aLocation )
354  *aLocation = nearest;
355 
356  if( aActual )
357  *aActual = sqrt( closest_dist_sq );
358 
359  return true;
360  }
361 
362  return false;
363 }
virtual bool IsClosed() const =0
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
virtual size_t GetSegmentCount() const =0
static SEG::ecoord Square(int a)
Definition: seg.h:122
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
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
virtual const SEG GetSegment(int aIndex) const =0
VECTOR2I A
Definition: seg.h:48

References SEG::A, VECTOR2< T >::ECOORD_MAX, SHAPE_LINE_CHAIN_BASE::GetSegment(), SHAPE_LINE_CHAIN_BASE::GetSegmentCount(), SHAPE_LINE_CHAIN_BASE::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 1590 of file shape_line_chain.cpp.

1591 {
1592  SHAPE_LINE_CHAIN a(*this), b( aOther );
1593  a.Simplify();
1594  b.Simplify();
1595 
1596  if( a.m_points.size() != b.m_points.size() )
1597  return false;
1598 
1599  for( int i = 0; i < a.PointCount(); i++ )
1600  {
1601  if( a.CPoint( i ) != b.CPoint( i ) )
1602  return false;
1603  }
1604 
1605  return true;
1606 }
Represent a polyline (an zero-thickness chain of connected line segments).

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

125 {
126  if( aArcIndex < 0 )
127  aArcIndex += m_arcs.size();
128 
129  if( aArcIndex >= static_cast<ssize_t>( m_arcs.size() ) )
130  return;
131 
132  // Clear the shapes references
133  for( auto& sh : m_shapes )
134  {
135  alg::run_on_pair( sh,
136  [&]( ssize_t& aShapeIndex )
137  {
138  if( aShapeIndex == aArcIndex )
139  aShapeIndex = SHAPE_IS_PT;
140 
141  if( aShapeIndex > aArcIndex )
142  --aShapeIndex;
143  } );
144 
145  if( sh.second != SHAPE_IS_PT && sh.first == SHAPE_IS_PT )
146  std::swap( sh.first, sh.second );
147  }
148 
149  m_arcs.erase( m_arcs.begin() + aArcIndex );
150 }
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:43
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 93 of file shape_line_chain.cpp.

96 {
97  ClipperLib::Path c_path;
98  SHAPE_LINE_CHAIN input;
99  bool orientation = Area( false ) >= 0;
100  ssize_t shape_offset = aArcBuffer.size();
101 
102  if( orientation != aRequiredOrientation )
103  input = Reverse();
104  else
105  input = *this;
106 
107  for( int i = 0; i < input.PointCount(); i++ )
108  {
109  const VECTOR2I& vertex = input.CPoint( i );
110 
111  CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
112  size_t z_value_ptr = aZValueBuffer.size();
113  aZValueBuffer.push_back( z_value );
114 
115  c_path.push_back( ClipperLib::IntPoint( vertex.x, vertex.y, z_value_ptr ) );
116  }
117 
118  aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
119 
120  return c_path;
121 }
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 (an zero-thickness chain of connected line segments).
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 356 of file shape_line_chain.h.

357  {
358  if( aIndex < 0 )
359  aIndex += PointCount();
360  else if( aIndex >= PointCount() )
361  aIndex -= PointCount();
362 
363  return m_points[aIndex];
364  }
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(), 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(), 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(), PNS::TOPOLOGY::followTrivialPath(), PCB_IO::format(), CN_ZONE_LAYER::GetAnchor(), PCB_SHAPE::GetFocusPosition(), SHAPE_SIMPLE::GetPoint(), GetPoint(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), 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(), 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 312 of file shape_line_chain.h.

313  {
314  if( aIndex < 0 )
315  aIndex += SegmentCount();
316 
317  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
318  return SEG( m_points[aIndex], m_points[0], aIndex );
319  else
320  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
321  }
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::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(), PCB_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 390 of file shape_line_chain.h.

391  {
392  return m_shapes;
393  }
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 588 of file shape_line_chain.cpp.

589 {
590  return sqrt( SquaredDistance( aP, aOutlineOnly ) );
591 }
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 1282 of file shape_line_chain.cpp.

1283 {
1284  if( !GetPointCount() )
1285  {
1286  return -1;
1287  }
1288  else if( GetPointCount() == 1 )
1289  {
1290  VECTOR2I dist = GetPoint(0) - aPt;
1291  return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
1292  }
1293 
1294  for( size_t i = 0; i < GetSegmentCount(); i++ )
1295  {
1296  const SEG s = GetSegment( i );
1297 
1298  if( s.A == aPt || s.B == aPt )
1299  return i;
1300 
1301  if( s.Distance( aPt ) <= aAccuracy + 1 )
1302  return i;
1303  }
1304 
1305  return -1;
1306 }
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 652 of file shape_line_chain.cpp.

653 {
654  for( int s = 0; s < PointCount(); s++ )
655  {
656  if( aThreshold == 0 )
657  {
658  if( CPoint( s ) == aP )
659  return s;
660  }
661  else
662  {
663  if( (CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
664  return s;
665  }
666  }
667 
668  return -1;
669 }
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 672 of file shape_line_chain.cpp.

673 {
674  for( int s = 0; s < SegmentCount(); s++ )
675  {
676  if( CSegment( s ).Distance( aP ) <= aThreshold )
677  return s;
678  }
679 
680  return -1;
681 }
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().

◆ Format()

const std::string SHAPE_LINE_CHAIN::Format ( ) const
overridevirtual

Reimplemented from SHAPE.

Definition at line 1561 of file shape_line_chain.cpp.

1562 {
1563  std::stringstream ss;
1564 
1565  ss << "SHAPE_LINE_CHAIN( { ";
1566 
1567  for( int i = 0; i < PointCount(); i++ )
1568  {
1569  ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
1570 
1571  if( i != PointCount() -1 )
1572  ss << ", ";
1573  }
1574 
1575  ss << "}, " << ( m_closed ? "true" : "false" );
1576  ss << " );";
1577 
1578  return ss.str();
1579 
1580  /* fixme: arcs
1581  for( size_t i = 0; i < m_arcs.size(); i++ )
1582  ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
1583  << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
1584  << m_arcs[i].GetCentralAngle();
1585 
1586  return ss.str();*/
1587 }
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 407 of file shape_line_chain.h.

408  {
410 
411  if( m_width != 0 )
413  }
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().

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

820 { 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(), BuildFootprintPolygonOutlines(), PNS::LINE::dragCornerFree(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), and TransformArcToPolygon().

◆ GetPointCount()

virtual size_t SHAPE_LINE_CHAIN::GetPointCount ( ) const
inlineoverridevirtual

Implements SHAPE_LINE_CHAIN_BASE.

Definition at line 822 of file shape_line_chain.h.

822 { return PointCount(); }
int PointCount() const
Return the number of points (vertices) in this line chain.

References PointCount().

Referenced by TransformArcToPolygon().

◆ GetSegment()

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

Implements SHAPE_LINE_CHAIN_BASE.

Definition at line 821 of file shape_line_chain.h.

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

References CSegment().

◆ GetSegmentCount()

virtual size_t SHAPE_LINE_CHAIN::GetSegmentCount ( ) const
inlineoverridevirtual

Implements SHAPE_LINE_CHAIN_BASE.

Definition at line 823 of file shape_line_chain.h.

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

References SegmentCount().

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

968 {
969  wxCHECK( aVertex < m_points.size(), /* void */ );
970 
971  if( aVertex > 0 && IsPtOnArc( aVertex ) )
972  splitArc( aVertex );
973 
974  //@todo need to check we aren't creating duplicate points
975  m_points.insert( m_points.begin() + aVertex, aP );
976  m_shapes.insert( m_shapes.begin() + aVertex, SHAPES_ARE_PT );
977 
978  assert( m_shapes.size() == m_points.size() );
979 }
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
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 IsPtOnArc(), m_points, m_shapes, SHAPES_ARE_PT, and splitArc().

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

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

983 {
984  wxCHECK( aVertex < m_points.size(), /* void */ );
985 
986  if( aVertex > 0 && IsPtOnArc( aVertex ) )
987  splitArc( aVertex );
988 
990  ssize_t arc_pos = m_arcs.size();
991 
992  for( auto arc_it = m_shapes.rbegin() ;
993  arc_it != m_shapes.rend() + aVertex;
994  arc_it++ )
995  {
996  if( *arc_it != SHAPES_ARE_PT )
997  {
998  arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
999  arc_pos++;
1000  }
1001  }
1002 
1003  //Increment all arc indices before inserting the new arc
1004  for( auto& sh : m_shapes )
1005  {
1006  alg::run_on_pair( sh,
1007  [&]( ssize_t& aIndex )
1008  {
1009  if( aIndex >= arc_pos )
1010  aIndex++;
1011  } );
1012  }
1013 
1014  m_arcs.insert( m_arcs.begin() + arc_pos, aArc );
1015 
1017  //@todo need to check we aren't creating duplicate points at start or end
1018  auto& chain = aArc.ConvertToPolyline();
1019  m_points.insert( m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1020 
1022  //@todo need to check we aren't creating duplicate points at start or end
1023  std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1024  { arc_pos, SHAPE_IS_PT } );
1025 
1026  m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1027  assert( m_shapes.size() == m_points.size() );
1028 }
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:43
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:459
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_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 1046 of file shape_line_chain.cpp.

1047 {
1048  for( int s = 0; s < SegmentCount(); s++ )
1049  {
1050  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
1051 
1052  if( p )
1053  {
1054  INTERSECTION is;
1055  is.valid = true;
1056  is.index_our = s;
1057  is.index_their = -1;
1058  is.is_corner_our = is.is_corner_their = false;
1059  is.p = *p;
1060  aIp.push_back( is );
1061  }
1062  }
1063 
1064  compareOriginDistance comp( aSeg.A );
1065  sort( aIp.begin(), aIp.end(), comp );
1066 
1067  return aIp.size();
1068 }
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 1086 of file shape_line_chain.cpp.

1088 {
1089  BOX2I bb_other = aChain.BBox();
1090 
1091  for( int s1 = 0; s1 < SegmentCount(); s1++ )
1092  {
1093  const SEG& a = CSegment( s1 );
1094  const BOX2I bb_cur( a.A, a.B - a.A );
1095 
1096  if( !bb_other.Intersects( bb_cur ) )
1097  continue;
1098 
1099  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
1100  {
1101  const SEG& b = aChain.CSegment( s2 );
1102  INTERSECTION is;
1103 
1104  is.index_our = s1;
1105  is.index_their = s2;
1106  is.is_corner_our = false;
1107  is.is_corner_their = false;
1108  is.valid = true;
1109 
1110  OPT_VECTOR2I p = a.Intersect( b );
1111 
1112  bool coll = a.Collinear( b );
1113 
1114  if( coll && ! aExcludeColinearAndTouching )
1115  {
1116  if( a.Contains( b.A ) )
1117  {
1118  is.p = b.A;
1119  is.is_corner_their = true;
1120  addIntersection(aIp, PointCount(), is);
1121  }
1122 
1123  if( a.Contains( b.B ) )
1124  {
1125  is.p = b.B;
1126  is.index_their++;
1127  is.is_corner_their = true;
1128  addIntersection( aIp, PointCount(), is );
1129  }
1130 
1131  if( b.Contains( a.A ) )
1132  {
1133  is.p = a.A;
1134  is.is_corner_our = true;
1135  addIntersection( aIp, PointCount(), is );
1136  }
1137 
1138  if( b.Contains( a.B ) )
1139  {
1140  is.p = a.B;
1141  is.index_our++;
1142  is.is_corner_our = true;
1143  addIntersection( aIp, PointCount(), is );
1144  }
1145  }
1146  else if( p )
1147  {
1148  is.p = *p;
1149  is.is_corner_our = false;
1150  is.is_corner_their = false;
1151 
1152  int distA = ( b.A - *p ).EuclideanNorm();
1153  int distB = ( b.B - *p ).EuclideanNorm();
1154 
1155  if( p == a.A )
1156  {
1157  is.is_corner_our = true;
1158  }
1159 
1160  if( p == a.B )
1161  {
1162  is.is_corner_our = true;
1163  is.index_our++;
1164  }
1165 
1166  if( p == b.A )
1167  {
1168  is.is_corner_their = true;
1169  }
1170 
1171  if( p == b.B )
1172  {
1173  is.is_corner_their = true;
1174  is.index_their++;
1175  }
1176 
1177  addIntersection( aIp, PointCount(), is );
1178  }
1179  }
1180  }
1181 
1182  return aIp.size();
1183 }
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 1609 of file shape_line_chain.cpp.

1610 {
1612  return Intersect( aChain, dummy ) != 0;
1613 }
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:71

References dummy(), and Intersect().

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

◆ IsArcEnd()

bool SHAPE_LINE_CHAIN::IsArcEnd ( size_t  aIndex) const
inline

Definition at line 812 of file shape_line_chain.h.

813  {
814  if( aIndex == static_cast<size_t>( PointCount() ) - 1 )
815  return IsPtOnArc( aIndex );
816 
817  return ( IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex ) ) );
818  }
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.
bool IsArcSegment(size_t aSegment) const
bool IsPtOnArc(size_t aPtIndex) const

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

Referenced by GEOM_TEST::IsOutlineValid(), NearestPoint(), and splitArc().

◆ IsArcSegment()

bool SHAPE_LINE_CHAIN::IsArcSegment ( size_t  aSegment) const
inline

Definition at line 785 of file shape_line_chain.h.

786  {
787  /*
788  * A segment is part of an arc except in the special case of two arcs next to each other
789  * but without a shared vertex. Here there is a segment between the end of the first arc
790  * and the start of the second arc.
791  */
792  size_t nextIdx = aSegment + 1;
793 
794  if( nextIdx > m_shapes.size() - 1 )
795  return false; // Always false, even if the shape is closed
796 
797  return ( IsPtOnArc( aSegment )
798  && ( IsSharedPt( aSegment )
799  || m_shapes[aSegment].first == m_shapes[nextIdx].first ) );
800  }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
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(), and m_shapes.

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

◆ IsArcStart()

bool SHAPE_LINE_CHAIN::IsArcStart ( size_t  aIndex) const
inline

Definition at line 803 of file shape_line_chain.h.

804  {
805  if( aIndex == 0 )
806  return IsPtOnArc( aIndex );
807 
808  return ( IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex - 1 ) ) );
809  }
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 GEOM_TEST::IsOutlineValid(), NearestPoint(), and splitArc().

◆ IsClosed()

bool SHAPE_LINE_CHAIN::IsClosed ( ) const
inlineoverridevirtual
Returns
true when our line is closed.

Implements SHAPE_LINE_CHAIN_BASE.

Definition at line 229 of file shape_line_chain.h.

230  {
231  return m_closed;
232  }
bool m_closed
is the line chain closed?

References m_closed.

Referenced by SHAPE_POLY_SET::AddOutline(), ZONE::AddPolygon(), BuildFootprintPolygonOutlines(), KIGFX::CAIRO_GAL_BASE::drawPoly(), KIGFX::OPENGL_GAL::DrawPolyline(), PLOTTER::PlotPoly(), PNS::pointInside2(), and SelfIntersecting().

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

780  {
781  return aPtIndex < m_shapes.size() && m_shapes[aPtIndex] != SHAPES_ARE_PT;
782  }
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 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(), 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 771 of file shape_line_chain.h.

772  {
773  return aIndex < m_shapes.size() - 1
774  && m_shapes[aIndex].first != SHAPE_IS_PT
775  && m_shapes[aIndex].second != SHAPE_IS_PT;
776  }
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(), IsArcEnd(), IsArcSegment(), IsArcStart(), GEOM_TEST::IsOutlineValid(), Remove(), RemoveShape(), and splitArc().

◆ IsSolid()

bool SHAPE_LINE_CHAIN::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 731 of file shape_line_chain.h.

732  {
733  return false;
734  }

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

413 {
414  long long int l = 0;
415 
416  for( int i = 0; i < SegmentCount(); i++ )
417  {
418  // Only include segments that aren't part of arc shapes
419  if( !IsArcSegment(i) )
420  l += CSegment( i ).Length();
421  }
422 
423  for( int i = 0; i < ArcCount(); i++ )
424  l += CArcs()[i].GetLength();
425 
426  return l;
427 }
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().

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

431 {
432  for( auto& pt : m_points )
433  {
434  if( aX )
435  pt.x = -pt.x + 2 * aRef.x;
436 
437  if( aY )
438  pt.y = -pt.y + 2 * aRef.y;
439  }
440 
441  for( auto& arc : m_arcs )
442  arc.Mirror( aX, aY, aRef );
443 }
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 446 of file shape_line_chain.cpp.

447 {
448  for( auto& pt : m_points )
449  pt = axis.ReflectPoint( pt );
450 
451  for( auto& arc : m_arcs )
452  arc.Mirror( axis );
453 }
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 698 of file shape_line_chain.h.

699  {
700  for( auto& pt : m_points )
701  pt += aVector;
702 
703  for( auto& arc : m_arcs )
704  arc.Move( aVector );
705  }
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(), PCB_SELECTION_TOOL::hitTestDistance(), PCB_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 1481 of file shape_line_chain.cpp.

1483 {
1484  int min_d = INT_MAX;
1485  int nearest = 0;
1486 
1487  for( int i = 0; i < SegmentCount(); i++ )
1488  {
1489  int d = CSegment( i ).Distance( aP );
1490 
1491  bool isInternalShapePoint = false;
1492 
1493  // An internal shape point here is everything after the start of an arc and before the
1494  // second-to-last vertex of the arc, because we are looking at segments here!
1495  if( i > 0 && i < SegmentCount() - 1 && m_shapes[i] != SHAPES_ARE_PT
1496  && ( ( m_shapes[i - 1] != SHAPES_ARE_PT && m_shapes[i - 1] == m_shapes[i] )
1497  && ( m_shapes[i + 2] != SHAPES_ARE_PT && m_shapes[i + 2] == m_shapes[i] ) ) )
1498  {
1499  isInternalShapePoint = true;
1500  }
1501 
1502  if( ( d < min_d ) && ( aAllowInternalShapePoints || !isInternalShapePoint ) )
1503  {
1504  min_d = d;
1505  nearest = i;
1506  }
1507  }
1508 
1509  // Is this the start or end of an arc? If so, return it directly
1510  if( !aAllowInternalShapePoints && ( IsArcStart( nearest ) || IsArcEnd( nearest ) ) )
1511  {
1512  //@todo should we calculate the nearest point to the "true" arc?
1513  return m_points[nearest];
1514  }
1515 
1516  return CSegment( nearest ).NearestPoint( aP );
1517 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
bool IsArcStart(size_t aIndex) const
std::vector< VECTOR2I > m_points
array of vertices
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.
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.
bool IsArcEnd(size_t aIndex) const
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

References CSegment(), SEG::Distance(), IsArcEnd(), IsArcStart(), m_points, m_shapes, SEG::NearestPoint(), SegmentCount(), and SHAPES_ARE_PT.

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

1521 {
1522  int nearest = 0;
1523 
1524  dist = INT_MAX;
1525 
1526  for( int i = 0; i < PointCount(); i++ )
1527  {
1528  int d = aSeg.LineDistance( CPoint( i ) );
1529 
1530  if( d < dist )
1531  {
1532  dist = d;
1533  nearest = i;
1534  }
1535  }
1536 
1537  return CPoint( nearest );
1538 }
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 1541 of file shape_line_chain.cpp.

1542 {
1543  int min_d = INT_MAX;
1544  int nearest = 0;
1545 
1546  for( int i = 0; i < SegmentCount(); i++ )
1547  {
1548  int d = CSegment( i ).Distance( aP );
1549 
1550  if( d < min_d )
1551  {
1552  min_d = d;
1553  nearest = i;
1554  }
1555  }
1556 
1557  return nearest;
1558 }
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 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 aPoint is in the last shape.

If aPoint is the start of a segment, this will be ( aPoint + 1 ). If aPoint 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.

Definition at line 734 of file shape_line_chain.cpp.

735 {
736  if( aPointIndex < 0 )
737  aPointIndex += PointCount();
738 
739  // First or last point?
740  if( ( aForwards && aPointIndex == PointCount() - 1 ) ||
741  ( !aForwards && aPointIndex == 0 ) )
742  {
743  return -1;
744  }
745 
746  int delta = aForwards ? 1 : -1;
747 
748  if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
749  return aPointIndex + delta;
750 
751  int arcStart = aPointIndex;
752 
753  // The second element should only get populated when the point is shared between two shapes.
754  // If not a shared point, then the index should always go on the first element.
755  assert( m_shapes[aPointIndex].first != SHAPE_IS_PT );
756 
757  // Start with the assumption the point is shared
758  int arcIndex = m_shapes[aPointIndex].second;
759 
760  if( arcIndex == SHAPE_IS_PT || !aForwards )
761  arcIndex = m_shapes[aPointIndex].first; // Not a shared point or we are going backwards
762 
763  int numPoints = static_cast<int>( m_shapes.size() );
764 
765  // Now skip the rest of the arc
766  while( aPointIndex < numPoints && aPointIndex >= 0 && m_shapes[aPointIndex].first == arcIndex )
767  aPointIndex += delta;
768 
769  bool indexStillOnArc = alg::pair_contains( m_shapes[aPointIndex], arcIndex );
770 
771  // We want the last vertex of the arc if the initial point was the start of one
772  // Well-formed arcs should generate more than one point to travel above
773  if( aPointIndex - arcStart > 1 && !indexStillOnArc )
774  aPointIndex -= delta;
775 
776  return aPointIndex;
777 }
static const ssize_t SHAPE_IS_PT
int PointCount() const
Return the number of points (vertices) in this 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,...
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:111
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

References m_shapes, alg::pair_contains(), PointCount(), SHAPE_IS_PT, and SHAPES_ARE_PT.

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

◆ operator!=()

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

Definition at line 682 of file shape_line_chain.h.

683  {
684  if( PointCount() != aRhs.PointCount() )
685  return true;
686 
687  for( int i = 0; i < PointCount(); i++ )
688  {
689  if( CPoint( i ) != aRhs.CPoint( i ) )
690  return true;
691  }
692 
693  return false;
694  }
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 1622 of file shape_line_chain.cpp.

1623 {
1624  size_t n_pts;
1625  size_t n_arcs;
1626 
1627  m_points.clear();
1628  aStream >> n_pts;
1629 
1630  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
1631  if( n_pts > aStream.str().size() )
1632  return false;
1633 
1634  aStream >> m_closed;
1635  aStream >> n_arcs;
1636 
1637  if( n_arcs > aStream.str().size() )
1638  return false;
1639 
1640  for( size_t i = 0; i < n_pts; i++ )
1641  {
1642  int x, y;
1643  ssize_t ind;
1644  aStream >> x;
1645  aStream >> y;
1646  m_points.emplace_back( x, y );
1647 
1648  aStream >> ind;
1649  m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
1650  }
1651 
1652  for( size_t i = 0; i < n_arcs; i++ )
1653  {
1654  VECTOR2I p0, pc;
1655  double angle;
1656 
1657  aStream >> pc.x;
1658  aStream >> pc.y;
1659  aStream >> p0.x;
1660  aStream >> p0.y;
1661  aStream >> angle;
1662 
1663  m_arcs.emplace_back( pc, p0, angle );
1664  }
1665 
1666  return true;
1667 }
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 1186 of file shape_line_chain.cpp.

1187 {
1188  int sum = 0;
1189 
1190  for( int i = 0; i < SegmentCount(); i++ )
1191  {
1192  const SEG seg = CSegment( i );
1193  int d = seg.Distance( aP );
1194 
1195  bool indexMatch = true;
1196 
1197  if( aIndex >= 0 )
1198  {
1199  if( aIndex == SegmentCount() )
1200  {
1201  indexMatch = ( i == SegmentCount() - 1 );
1202  }
1203  else
1204  {
1205  indexMatch = ( i == aIndex );
1206  }
1207  }
1208 
1209  if( indexMatch )
1210  {
1211  sum += ( aP - seg.A ).EuclideanNorm();
1212  return sum;
1213  }
1214  else
1215  sum += seg.Length();
1216  }
1217 
1218  return -1;
1219 }
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 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.
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(), SEG::Distance(), EuclideanNorm(), SEG::Length(), and SegmentCount().

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

◆ PointAlong()

const VECTOR2I SHAPE_LINE_CHAIN::PointAlong ( int  aPathLength) const

Definition at line 1670 of file shape_line_chain.cpp.

1671 {
1672  int total = 0;
1673 
1674  if( aPathLength == 0 )
1675  return CPoint( 0 );
1676 
1677  for( int i = 0; i < SegmentCount(); i++ )
1678  {
1679  const SEG& s = CSegment( i );
1680  int l = s.Length();
1681 
1682  if( total + l >= aPathLength )
1683  {
1684  VECTOR2I d( s.B - s.A );
1685  return s.A + d.Resize( aPathLength - total );
1686  }
1687 
1688  total += l;
1689  }
1690 
1691  return CPoint( -1 );
1692 }
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 282 of file shape_line_chain.h.

283  {
284  return m_points.size();
285  }
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(), PCB_SHAPE::BuildPolyPointsList(), 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(), 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_IO::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(), DS_DRAW_ITEM_POLYPOLYGONS::HitTest(), PNS::HullIntersection(), Intersect(), IsArcEnd(), GEOM_TEST::IsOutlineValid(), POLYGON_GEOM_MANAGER::IsPolygonInProgress(), PCB_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 1222 of file shape_line_chain.cpp.

1224 {
1225  /*
1226  * Don't check the bounding box unless it's cached. Building it is about the same speed as
1227  * the rigorous test below and so just slows things down by doing potentially two tests.
1228  */
1229  //if( aUseBBoxCache && !m_bbox.Contains( aPt ) )
1230  //return false;
1231 
1232  // fixme: bbox cache...
1233 
1234  if( !IsClosed() || GetPointCount() < 3 )
1235  return false;
1236 
1237  bool inside = false;
1238 
1239  /*
1240  * To check for interior points, we draw a line in the positive x direction from
1241  * the point. If it intersects an even number of segments, the point is outside the
1242  * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
1243  *
1244  * Note: slope might be denormal here in the case of a horizontal line but we require our
1245  * y to move from above to below the point (or vice versa)
1246  *
1247  * Note: we open-code CPoint() here so that we don't end up calculating the size of the
1248  * vector number-of-points times. This has a non-trivial impact on zone fill times.
1249  */
1250  int pointCount = GetPointCount();
1251 
1252  for( int i = 0; i < pointCount; )
1253  {
1254  const auto p1 = GetPoint( i++ );
1255  const auto p2 = GetPoint( i == pointCount ? 0 : i );
1256  const auto diff = p2 - p1;
1257 
1258  if( diff.y != 0 )
1259  {
1260  const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
1261 
1262  if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
1263  inside = !inside;
1264  }
1265  }
1266 
1267  // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
1268  // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
1269  if( aAccuracy <= 1 )
1270  return inside;
1271  else
1272  return inside || PointOnEdge( aPt, aAccuracy );
1273 }
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::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(), SHAPE_LINE_CHAIN_BASE::Collide(), POLY_GRID_PARTITION::containsPoint(), SHAPE_POLY_SET::containsSingle(), LIB_POLYLINE::HitTest(), 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 1276 of file shape_line_chain.cpp.

1277 {
1278  return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
1279 }
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 LIB_POLYLINE::HitTest(), FABMASTER::loadZones(), SHAPE_LINE_CHAIN_BASE::PointInside(), and PNS::LINE::Walkaround().

◆ PrevShape()

int SHAPE_LINE_CHAIN::PrevShape ( int  aPointIndex) const
inline

Definition at line 337 of file shape_line_chain.h.

338  {
339  return NextShape( aPointIndex, false );
340  }
int NextShape(int aPointIndex, bool aForwards=true) const
Return the vertex index of the next shape in the chain, or -1 if aPoint is in 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 519 of file shape_line_chain.cpp.

520 {
521  assert( m_shapes.size() == m_points.size() );
522 
523  if( aEndIndex < 0 )
524  aEndIndex += PointCount();
525 
526  if( aStartIndex < 0 )
527  aStartIndex += PointCount();
528 
529  if( aStartIndex >= PointCount() )
530  return;
531 
532  aEndIndex = std::min( aEndIndex, PointCount() - 1 );
533 
534  // Split arcs at start index and end just after the end index
535  if( IsPtOnArc( aStartIndex ) )
536  splitArc( aStartIndex );
537 
538  size_t nextIndex = static_cast<size_t>( aEndIndex ) + 1;
539 
540  if( IsPtOnArc( nextIndex ) )
541  splitArc( nextIndex );
542 
543  std::set<size_t> extra_arcs;
544  auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
545  {
546  if( aShapeIndex != SHAPE_IS_PT )
547  extra_arcs.insert( aShapeIndex );
548  };
549 
550  // Remove any overlapping arcs in the point range
551  for( int i = aStartIndex; i <= aEndIndex; i++ )
552  {
553  if( IsSharedPt( i ) )
554  {
555  if( i == aStartIndex )
556  {
557  logArcIdxRemoval( m_shapes[i].second ); // Only remove the arc on the second index
558 
559  // Ensure that m_shapes has been built correctly.
560  assert( i < aEndIndex || m_shapes[i + 1].first == m_shapes[i].second );
561 
562  continue;
563  }
564  else if( i == aEndIndex )
565  {
566  logArcIdxRemoval( m_shapes[i].first ); // Only remove the arc on the first index
567 
568  // Ensure that m_shapes has been built correctly.
569  assert( i > aStartIndex || IsSharedPt( i - 1 )
570  ? m_shapes[i - 1].second == m_shapes[i].first
571  : m_shapes[i - 1].first == m_shapes[i].first );
572  continue;
573  }
574  }
575 
576  alg::run_on_pair( m_shapes[i], logArcIdxRemoval );
577  }
578 
579  for( auto arc : extra_arcs )
580  convertArc( arc );
581 
582  m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
583  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
584  assert( m_shapes.size() == m_points.size() );
585 }
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:43
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(), 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 530 of file shape_line_chain.h.

531  {
532  Remove( aIndex, aIndex );
533  }
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 798 of file shape_line_chain.cpp.

799 {
800  if( aPointIndex < 0 )
801  aPointIndex += PointCount();
802 
803  if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
804  {
805  Remove( aPointIndex );
806  return;
807  }
808 
809  //@todo should this be replaced to use NextShape() / PrevShape()?
810  int start = aPointIndex;
811  int end = aPointIndex;
812  int arcIdx = ArcIndex( aPointIndex );
813 
814  if( !IsSharedPt( aPointIndex ) )
815  {
816  // aPointIndex is not a shared point, so iterate backwards to find the start of the arc
817  while( start >= 0 && m_shapes[start].first == arcIdx )
818  start--;
819 
820  // Check if the previous point might be a shared point and decrement 'start' if so
821  if( start >= 1 && m_shapes[static_cast<ssize_t>( start ) - 1].second == arcIdx )
822  start--;
823  }
824 
825  // For the end point we only need to check the first element in m_shapes (the second one is only
826  // populated if there is an arc after the current one sharing the same point).
827  while( end < static_cast<int>( m_shapes.size() ) - 1 && m_shapes[end].first == arcIdx )
828  end++;
829 
830  Remove( start, end );
831 }
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 456 of file shape_line_chain.cpp.

457 {
458  Remove( aStartIndex, aEndIndex );
459  Insert( aStartIndex, aP );
460  assert( m_shapes.size() == m_points.size() );
461 }
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(), 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 464 of file shape_line_chain.cpp.

465 {
466  if( aEndIndex < 0 )
467  aEndIndex += PointCount();
468 
469  if( aStartIndex < 0 )
470  aStartIndex += PointCount();
471 
472  // We only process lines in order in this house
473  wxASSERT( aStartIndex <= aEndIndex );
474  wxASSERT( aEndIndex < m_points.size() );
475 
476  SHAPE_LINE_CHAIN newLine = aLine;
477 
478  // Remove coincident points in the new line
479  if( newLine.m_points.front() == m_points[aStartIndex] )
480  {
481  aStartIndex++;
482  newLine.Remove( 0 );
483  }
484 
485  if( newLine.m_points.back() == m_points[aEndIndex] && aEndIndex > 0 )
486  {
487  aEndIndex--;
488  newLine.Remove( -1 );
489  }
490 
491  Remove( aStartIndex, aEndIndex );
492 
493  if( !newLine.PointCount() )
494  return;
495 
496  // The total new arcs index is added to the new arc indices
497  size_t prev_arc_count = m_arcs.size();
498  std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.m_shapes;
499 
500  for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
501  {
502  alg::run_on_pair( shape_pair,
503  [&]( ssize_t& aShape )
504  {
505  if( aShape != SHAPE_IS_PT )
506  aShape += prev_arc_count;
507  } );
508  }
509 
510  m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
511  m_points.insert( m_points.begin() + aStartIndex, newLine.m_points.begin(),
512  newLine.m_points.end() );
513  m_arcs.insert( m_arcs.end(), newLine.m_arcs.begin(), newLine.m_arcs.end() );
514 
515  assert( m_shapes.size() == m_points.size() );
516 }
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:43
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 (an zero-thickness chain of connected line segments).

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

367 {
368  SHAPE_LINE_CHAIN a( *this );
369 
370  reverse( a.m_points.begin(), a.m_points.end() );
371  reverse( a.m_shapes.begin(), a.m_shapes.end() );
372  reverse( a.m_arcs.begin(), a.m_arcs.end() );
373 
374  for( auto& sh : a.m_shapes )
375  {
376  if( sh != SHAPES_ARE_PT )
377  {
378  alg::run_on_pair( sh,
379  [&]( ssize_t& aShapeIndex )
380  {
381  if( aShapeIndex != SHAPE_IS_PT )
382  aShapeIndex = a.m_arcs.size() - aShapeIndex - 1;
383  } );
384 
385  if( sh.second != SHAPE_IS_PT )
386  {
387  // If the second element is populated, the first one should be too!
388  assert( sh.first != SHAPE_IS_PT );
389 
390  // Switch round first and second in shared points, as part of reversing the chain
391  std::swap( sh.first, sh.second );
392  }
393  }
394  }
395 
396  for( SHAPE_ARC& arc : a.m_arcs )
397  arc.Reverse();
398 
399  a.m_closed = m_closed;
400 
401  return a;
402 }
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:43
void Reverse()
Definition: shape_arc.cpp:579
Represent a polyline (an zero-thickness chain of connected line segments).
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().

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

299 {
300  for( auto& pt : m_points )
301  {
302  pt -= aCenter;
303  pt = pt.Rotate( aAngle );
304  pt += aCenter;
305  }
306 
307  for( auto& arc : m_arcs )
308  arc.Rotate( aAngle, aCenter );
309 }
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(), PCB_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 294 of file shape_line_chain.h.

295  {
296  if( aIndex < 0 )
297  aIndex += SegmentCount();
298 
299  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
300  return SEG( m_points[aIndex], m_points[0], aIndex );
301  else
302  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
303  }
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(), CADSTAR_SCH_ARCHIVE_LOADER::loadShapeVertices(), PCB_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 259 of file shape_line_chain.h.

260  {
261  int c = m_points.size() - 1;
262  if( m_closed )
263  c++;
264 
265  return std::max( 0, c );
266  }
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(), PCB_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(), PCB_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 1331 of file shape_line_chain.cpp.

1332 {
1333  for( int s1 = 0; s1 < SegmentCount(); s1++ )
1334  {
1335  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
1336  {
1337  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
1338 
1339  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
1340  {
1341  INTERSECTION is;
1342  is.index_our = s1;
1343  is.index_their = s2;
1344  is.p = s2a;
1345  return is;
1346  }
1347  else if( CSegment( s1 ).Contains( s2b ) &&
1348  // for closed polylines, the ending point of the
1349  // last segment == starting point of the first segment
1350  // this is a normal case, not self intersecting case
1351  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
1352  {
1353  INTERSECTION is;
1354  is.index_our = s1;
1355  is.index_their = s2;
1356  is.p = s2b;
1357  return is;
1358  }
1359  else
1360  {
1361  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
1362 
1363  if( p )
1364  {
1365  INTERSECTION is;
1366  is.index_our = s1;
1367  is.index_their = s2;
1368  is.p = *p;
1369  return is;
1370  }
1371  }
1372  }
1373  }
1374 
1376 }
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 221 of file shape_line_chain.h.

222  {
223  m_closed = aClosed;
224  }
bool m_closed
is the line chain closed?

References m_closed.

Referenced by ZONE_FILLER::addHatchFillTypeOnZone(), ZONE::AddPolygon(), PNS::ArcHull(), 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(), PLACEFILE_GERBER_WRITER::CreatePlaceFile(), KIGFX::GERBVIEW_PAINTER::draw(), SHAPE_POLY_SET::fractureSingle(), CADSTAR_PCB_ARCHIVE_LOADER::getLineChainFromShapes(), PNS::MOUSE_TRAIL_TRACER::GetPosture(), HelperShapeLineChainFromAltiumVertices(), LIB_POLYLINE::HitTest(), 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(), CONVERT_TOOL::PolyToLines(), RENDER_3D_LEGACY::reload(), PNS::SegmentHull(), 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 780 of file shape_line_chain.cpp.

781 {
782  if( aIndex < 0 )
783  aIndex += PointCount();
784  else if( aIndex >= PointCount() )
785  aIndex -= PointCount();
786 
787  m_points[aIndex] = aPos;
788 
789  alg::run_on_pair( m_shapes[aIndex],
790  [&]( ssize_t& aIdx )
791  {
792  if( aIdx != SHAPE_IS_PT )
793  convertArc( aIdx );
794  } );
795 }
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:43
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(), and PNS::LINE::dragCornerFree().

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

240  {
241  m_width = aWidth;
242  }
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 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 684 of file shape_line_chain.cpp.

685 {
686  if( m_points.empty() )
687  return 0;
688 
689  int numPoints = static_cast<int>( m_shapes.size() );
690  int numShapes = 0;
691  int arcIdx = -1;
692 
693  for( int i = 0; i < m_points.size() - 1; i++ )
694  {
695  if( m_shapes[i] == SHAPES_ARE_PT )
696  {
697  numShapes++;
698  }
699  else
700  {
701  // Expect that the second index only gets populated when the point is shared between
702  // two shapes. Otherwise, the shape index should always go on the first element of
703  // the pair.
704  assert( m_shapes[i].first != SHAPE_IS_PT );
705 
706  // Start assuming the point is shared with the previous arc
707  // If so, the new/next arc index should be located at the second
708  // element in the pair
709  arcIdx = m_shapes[i].second;
710 
711  if( arcIdx == SHAPE_IS_PT )
712  arcIdx = m_shapes[i].first; // Not a shared point
713 
714  numShapes++;
715 
716  // Now skip the rest of the arc
717  while( i < numPoints && m_shapes[i].first == arcIdx )
718  i++;
719 
720  // Add the "hidden" segment at the end of the arc, if it exists
721  if( i < numPoints && m_points[i] != m_points[i - 1] )
722  {
723  numShapes++;
724  }
725 
726  i--;
727  }
728  }
729 
730  return numShapes;
731 }
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 1379 of file shape_line_chain.cpp.

1380 {
1381  std::vector<VECTOR2I> pts_unique;
1382  std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
1383 
1384  if( PointCount() < 2 )
1385  {
1386  return *this;
1387  }
1388  else if( PointCount() == 2 )
1389  {
1390  if( m_points[0] == m_points[1] )
1391  m_points.pop_back();
1392 
1393  return *this;
1394  }
1395 
1396  int i = 0;
1397  int np = PointCount();
1398 
1399  // stage 1: eliminate duplicate vertices
1400  while( i < np )
1401  {
1402  int j = i + 1;
1403 
1404  // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
1405  // one of them is part of a shape and one is not.
1406  while( j < np && m_points[i] == m_points[j] &&
1407  ( m_shapes[i] == m_shapes[j] ||
1408  m_shapes[i] == SHAPES_ARE_PT ||
1409  m_shapes[j] == SHAPES_ARE_PT ) )
1410  {
1411  j++;
1412  }
1413 
1414  std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
1415 
1416  if( shapeToKeep == SHAPES_ARE_PT )
1417  shapeToKeep = m_shapes[j - 1];
1418 
1419  assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
1420  assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
1421 
1422  pts_unique.push_back( CPoint( i ) );
1423  shapes_unique.push_back( shapeToKeep );
1424 
1425  i = j;
1426  }
1427 
1428  m_points.clear();
1429  m_shapes.clear();
1430  np = pts_unique.size();
1431 
1432  i = 0;
1433 
1434  // stage 2: eliminate colinear segments
1435  while( i < np - 2 )
1436  {
1437  const VECTOR2I p0 = pts_unique[i];
1438  const VECTOR2I p1 = pts_unique[i + 1];
1439  int n = i;
1440 
1441  if( aRemoveColinear && shapes_unique[i] == SHAPES_ARE_PT
1442  && shapes_unique[i + 1] == SHAPES_ARE_PT )
1443  {
1444  while( n < np - 2
1445  && ( SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1
1446  || SEG( p0, p1 ).Collinear( SEG( p1, pts_unique[n + 2] ) ) ) )
1447  n++;
1448  }
1449 
1450  m_points.push_back( p0 );
1451  m_shapes.push_back( shapes_unique[i] );
1452 
1453  if( n > i )
1454  i = n;
1455 
1456  if( n == np - 2 )
1457  {
1458  m_points.push_back( pts_unique[np - 1] );
1459  m_shapes.push_back( shapes_unique[np - 1] );
1460  return *this;
1461  }
1462 
1463  i++;
1464  }
1465 
1466  if( np > 1 )
1467  {
1468  m_points.push_back( pts_unique[np - 2] );
1469  m_shapes.push_back( shapes_unique[np - 2] );
1470  }
1471 
1472  m_points.push_back( pts_unique[np - 1] );
1473  m_shapes.push_back( shapes_unique[np - 1] );
1474 
1475  assert( m_points.size() == m_shapes.size() );
1476 
1477  return *this;
1478 }
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(), 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 834 of file shape_line_chain.cpp.

835 {
836  SHAPE_LINE_CHAIN rv;
837 
838  if( aEndIndex < 0 )
839  aEndIndex += PointCount();
840 
841  if( aStartIndex < 0 )
842  aStartIndex += PointCount();
843 
844  int numPoints = static_cast<int>( m_points.size() );
845 
846  for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i++ )
847  {
848  if( m_shapes[i] != SHAPES_ARE_PT )
849  {
850  int arcIdx = ArcIndex( i );
851  bool wholeArc = true;
852  int arcStart = i;
853  size_t prevIdx = static_cast<size_t>( i ) - 1;
854 
855  if( i > 0 && IsArcSegment( prevIdx ) && ArcIndex( prevIdx ) != arcIdx )
856  wholeArc = false;
857 
858  while( i < numPoints && ArcIndex( i ) == arcIdx )
859  i++;
860 
861  i--;
862 
863  if( i > aEndIndex )
864  wholeArc = false;
865 
866  if( wholeArc )
867  {
868  rv.Append( m_arcs[arcIdx] );
869  }
870  else
871  {
872  //@todo need to split up the arc
873  rv.Append( m_points[arcStart] );
874  i = arcStart;
875  }
876  }
877  else
878  {
879  rv.Append( m_points[i] );
880  }
881  }
882 
883  return rv;
884 }
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 IsArcSegment(size_t aSegment) 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,...
Represent a polyline (an zero-thickness chain of connected line segments).
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT

References Append(), ArcIndex(), IsArcSegment(), m_arcs, m_points, m_shapes, PointCount(), and SHAPES_ARE_PT.

Referenced by PNS::MOUSE_TRAIL_TRACER::AddTrailPoint(), 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 608 of file shape_line_chain.cpp.

609 {
610  int ii = -1;
611  int min_dist = 2;
612 
613  int found_index = Find( aP );
614 
615  for( int s = 0; s < SegmentCount(); s++ )
616  {
617  const SEG seg = CSegment( s );
618  int dist = seg.Distance( aP );
619 
620  // make sure we are not producing a 'slightly concave' primitive. This might happen
621  // if aP lies very close to one of already existing points.
622  if( dist < min_dist && seg.A != aP && seg.B != aP )
623  {
624  min_dist = dist;
625  if( found_index < 0 )
626  ii = s;
627  else if( s < found_index )
628  ii = s;
629  }
630  }
631 
632  if( ii < 0 )
633  ii = found_index;
634 
635  if( ii >= 0 )
636  {
637  // Are we splitting at the beginning of an arc? If so, let's split right before so that
638  // the shape is preserved
639  if( IsArcSegment( ii ) )
640  ii--;
641 
642  m_points.insert( m_points.begin() + ( ii + 1 ), aP );
643  m_shapes.insert( m_shapes.begin() + ( ii + 1 ), SHAPES_ARE_PT );
644 
645  return ii + 1;
646  }
647 
648  return -1;
649 }
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:285
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.
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
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT
VECTOR2I B
Definition: seg.h:49

References SEG::A, SEG::B, CSegment(), SEG::Distance(), Find(), IsArcSegment(), m_points, m_shapes, SegmentCount(), and SHAPES_ARE_PT.

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

171 {
172  if( aPtIndex < 0 )
173  aPtIndex += m_shapes.size();
174 
175  if( !IsSharedPt( aPtIndex ) && IsArcStart( aPtIndex ) )
176  return; // Nothing to do
177 
178  wxCHECK_MSG( aPtIndex < static_cast<ssize_t>( m_shapes.size() ), /* void */,
179  "Invalid point index requested." );
180 
181  if( IsSharedPt( aPtIndex ) || IsArcEnd( aPtIndex ) )
182  {
183  if( aCoincident || aPtIndex == 0 )
184  return; // nothing to do
185 
186  ssize_t firstArcIndex = m_shapes[aPtIndex].first;
187 
188  const VECTOR2I& newStart = m_arcs[firstArcIndex].GetP0(); // don't amend the start
189  const VECTOR2I& newEnd = m_points[aPtIndex - 1];
190  amendArc( firstArcIndex, newStart, newEnd );
191 
192  if( IsSharedPt( aPtIndex ) )
193  {
194  m_shapes[aPtIndex].first = m_shapes[aPtIndex].second;
195  m_shapes[aPtIndex].second = SHAPE_IS_PT;
196  }
197  else
198  {
199  m_shapes[aPtIndex] = SHAPES_ARE_PT;
200  }
201 
202  return;
203  }
204 
205  ssize_t currArcIdx = ArcIndex( aPtIndex );
206  SHAPE_ARC& currentArc = m_arcs[currArcIdx];
207 
208  SHAPE_ARC newArc1;
209  SHAPE_ARC newArc2;
210 
211  VECTOR2I arc1End = ( aCoincident ) ? m_points[aPtIndex] : m_points[aPtIndex - 1];
212  VECTOR2I arc2Start = m_points[aPtIndex];
213 
214  newArc1.ConstructFromStartEndCenter( currentArc.GetP0(), arc1End, currentArc.GetCenter(),
215  currentArc.IsClockwise() );
216 
217  newArc2.ConstructFromStartEndCenter( arc2Start, currentArc.GetP1(), currentArc.GetCenter(),
218  currentArc.IsClockwise() );
219 
220  if( !aCoincident && ArcIndex( aPtIndex - 1 ) != currArcIdx )
221  {
222  //Ignore newArc1 as it has zero points
223  m_arcs[currArcIdx] = newArc2;
224  }
225  else
226  {
227  m_arcs[currArcIdx] = newArc1;
228  m_arcs.insert( m_arcs.begin() + currArcIdx + 1, newArc2 );
229 
230  if( aCoincident )
231  m_shapes[aPtIndex].second = currArcIdx + 1;
232 
233  // Only change the arc indices for the second half of the point range
234  for( int i = aPtIndex; i < PointCount(); i++ )
235  {
236  alg::run_on_pair( m_shapes[i], [&]( ssize_t& aIndex ) {
237  if( aIndex != SHAPE_IS_PT )
238  aIndex++;
239  } );
240  }
241  }
242 }
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
bool IsClockwise() const
Definition: shape_arc.cpp:352
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:43
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
void amendArc(size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)
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:199
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:425

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

Referenced by Insert(), and Remove().

◆ SquaredDistance()

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

Definition at line 594 of file shape_line_chain.cpp.

595 {
597 
598  if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
599  return 0;
600 
601  for( size_t s = 0; s < GetSegmentCount(); s++ )
602  d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
603 
604  return d;
605 }
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 249 of file shape_line_chain.h.

250  {
251  return m_width;
252  }
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(), and ROUTER_PREVIEW_ITEM::drawShape().

Friends And Related Function Documentation

◆ SHAPE_POLY_SET

friend class SHAPE_POLY_SET
friend

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

Referenced by Append(), BBoxFromCache(), and GenerateBBoxCache().

◆ m_closed

bool SHAPE_LINE_CHAIN::m_closed
private

is the line chain closed?

Definition at line 896 of file shape_line_chain.h.

Referenced by Area(), Clear(), CSegment(), Format(), IsClosed(), Parse(), Reverse(), Segment(), SegmentCount(), and SetClosed().

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

Referenced by Append(), ArcIndex(), Clear(), convertArc(), convertToClipper(), CShapes(), Insert(), IsArcSegment(), IsPtOnArc(), IsSharedPt(), NearestPoint(), NextShape(), Parse(), Remove(), RemoveShape(), Replace(), Reverse(), 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 903 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: