KiCad PCB EDA Suite
SHAPE_LINE_CHAIN Class Reference

Class SHAPE_LINE_CHAIN. More...

#include <shape_line_chain.h>

Inheritance diagram for SHAPE_LINE_CHAIN:
SHAPE

Classes

struct  compareOriginDistance
 
struct  INTERSECTION
 Struct INTERSECTION. More...
 

Public Types

typedef std::vector< INTERSECTIONINTERSECTIONS
 

Public Member Functions

 SHAPE_LINE_CHAIN ()
 Constructor Initializes an empty line chain. More...
 
 SHAPE_LINE_CHAIN (const SHAPE_LINE_CHAIN &aShape)
 Copy Constructor. More...
 
 SHAPE_LINE_CHAIN (const VECTOR2I &aA, const VECTOR2I &aB)
 Constructor Initializes a 2-point line chain (a single segment) More...
 
 SHAPE_LINE_CHAIN (const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC)
 
 SHAPE_LINE_CHAIN (const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC, const VECTOR2I &aD)
 
 SHAPE_LINE_CHAIN (const VECTOR2I *aV, int aCount)
 
 ~SHAPE_LINE_CHAIN ()
 
SHAPEClone () const override
 Function Clone() More...
 
void Clear ()
 Function Clear() Removes all points from the line chain. More...
 
void SetClosed (bool aClosed)
 Function SetClosed() More...
 
bool IsClosed () const
 Function IsClosed() More...
 
int SegmentCount () const
 Function SegmentCount() More...
 
int PointCount () const
 Function PointCount() More...
 
SEG Segment (int aIndex)
 Function Segment() More...
 
const SEG CSegment (int aIndex) const
 Function CSegment() More...
 
VECTOR2IPoint (int aIndex)
 Function Point() More...
 
const VECTOR2ICPoint (int aIndex) const
 Function CPoint() More...
 
const BOX2I BBox (int aClearance=0) const override
 Function BBox() More...
 
bool Collide (const VECTOR2I &aP, int aClearance=0) const override
 Function Collide() More...
 
bool Collide (const SEG &aSeg, int aClearance=0) const override
 Function Collide() More...
 
int Distance (const VECTOR2I &aP) const
 Function Distance() More...
 
const SHAPE_LINE_CHAIN Reverse () const
 Function Reverse() More...
 
int Length () const
 Function Length() More...
 
void Append (int aX, int aY, bool aAllowDuplication=false)
 Function Append() More...
 
void Append (const VECTOR2I &aP, bool aAllowDuplication=false)
 Function Append() More...
 
void Append (const SHAPE_LINE_CHAIN &aOtherLine)
 Function Append() More...
 
void Insert (int aVertex, const VECTOR2I &aP)
 
void Replace (int aStartIndex, int aEndIndex, const VECTOR2I &aP)
 Function Replace() More...
 
void Replace (int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN &aLine)
 Function Replace() More...
 
void Remove (int aStartIndex, int aEndIndex)
 Function Remove() More...
 
void Remove (int aIndex)
 Function Remove() removes the aIndex-th point from the line chain. More...
 
int Split (const VECTOR2I &aP)
 Function Split() More...
 
int Find (const VECTOR2I &aP) const
 Function Find() More...
 
int FindSegment (const VECTOR2I &aP) const
 Function FindSegment() More...
 
const SHAPE_LINE_CHAIN Slice (int aStartIndex, int aEndIndex=-1) const
 Function Slice() More...
 
bool Intersects (const SHAPE_LINE_CHAIN &aChain) const
 
int Intersect (const SEG &aSeg, INTERSECTIONS &aIp) const
 Function Intersect() More...
 
int Intersect (const SHAPE_LINE_CHAIN &aChain, INTERSECTIONS &aIp) const
 Function Intersect() More...
 
int PathLength (const VECTOR2I &aP) const
 Function PathLength() More...
 
bool PointInside (const VECTOR2I &aP) const
 Function PointInside() More...
 
bool PointOnEdge (const VECTOR2I &aP) const
 Function PointOnEdge() More...
 
const boost::optional< INTERSECTIONSelfIntersecting () const
 Function SelfIntersecting() More...
 
SHAPE_LINE_CHAINSimplify ()
 Function Simplify() More...
 
const VECTOR2I NearestPoint (const VECTOR2I &aP) const
 Function NearestPoint() More...
 
const VECTOR2I NearestPoint (const SEG &aSeg, int &dist) const
 Function NearestPoint() 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
 
bool IsSolid () const override
 
const VECTOR2I PointAlong (int aPathLength) const
 
SHAPE_TYPE Type () const
 Function Type() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance, VECTOR2I &aMTV) const
 Function Collide() More...
 
virtual bool Collide (const SHAPE *aShape, int aClearance=0) const
 
virtual VECTOR2I Centre () const
 Function Centre() More...
 

Protected Types

typedef VECTOR2I::extended_type ecoord
 

Protected Attributes

SHAPE_TYPE m_type
 

type of our shape

More...
 

Private Types

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...
 
bool m_closed
 is the line chain closed? More...
 
BOX2I m_bbox
 cached bounding box More...
 

Detailed Description

Class SHAPE_LINE_CHAIN.

Represents a polyline (an zero-thickness chain of connected line segments). I purposedly didn't name it "polyline" to avoid confusion with the existing CPolyLine class in pcbnew.

SHAPE_LINE_CHAIN class shall not be used for polygons!

Definition at line 47 of file shape_line_chain.h.

Member Typedef Documentation

typedef VECTOR2I::extended_type SHAPE::ecoord
protectedinherited

Definition at line 60 of file shape.h.

Definition at line 69 of file shape_line_chain.h.

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

Definition at line 51 of file shape_line_chain.h.

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

Definition at line 50 of file shape_line_chain.h.

Constructor & Destructor Documentation

SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( )
inline

Constructor Initializes an empty line chain.

Definition at line 75 of file shape_line_chain.h.

Referenced by Clone().

75  :
76  SHAPE( SH_LINE_CHAIN ), m_closed( false )
77  {}
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:69
bool m_closed
is the line chain closed?
line segment
Definition: shape.h:45
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const SHAPE_LINE_CHAIN aShape)
inline

Copy Constructor.

Definition at line 82 of file shape_line_chain.h.

82  :
83  SHAPE( SH_LINE_CHAIN ), m_points( aShape.m_points ), m_closed( aShape.m_closed )
84  {}
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:69
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
line segment
Definition: shape.h:45
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const VECTOR2I aA,
const VECTOR2I aB 
)
inline

Constructor Initializes a 2-point line chain (a single segment)

Definition at line 90 of file shape_line_chain.h.

References m_points.

90  :
91  SHAPE( SH_LINE_CHAIN ), m_closed( false )
92  {
93  m_points.resize( 2 );
94  m_points[0] = aA;
95  m_points[1] = aB;
96  }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:69
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
line segment
Definition: shape.h:45
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const VECTOR2I aA,
const VECTOR2I aB,
const VECTOR2I aC 
)
inline

Definition at line 98 of file shape_line_chain.h.

References m_points.

98  :
99  SHAPE( SH_LINE_CHAIN ), m_closed( false )
100  {
101  m_points.resize( 3 );
102  m_points[0] = aA;
103  m_points[1] = aB;
104  m_points[2] = aC;
105  }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:69
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
line segment
Definition: shape.h:45
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const VECTOR2I aA,
const VECTOR2I aB,
const VECTOR2I aC,
const VECTOR2I aD 
)
inline

Definition at line 107 of file shape_line_chain.h.

References m_points.

107  :
108  SHAPE( SH_LINE_CHAIN ), m_closed( false )
109  {
110  m_points.resize( 4 );
111  m_points[0] = aA;
112  m_points[1] = aB;
113  m_points[2] = aC;
114  m_points[3] = aD;
115  }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:69
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
line segment
Definition: shape.h:45
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN ( const VECTOR2I aV,
int  aCount 
)
inline

Definition at line 118 of file shape_line_chain.h.

References m_points.

118  :
119  SHAPE( SH_LINE_CHAIN ),
120  m_closed( false )
121  {
122  m_points.resize( aCount );
123 
124  for( int i = 0; i < aCount; i++ )
125  m_points[i] = *aV++;
126  }
SHAPE(SHAPE_TYPE aType)
Constructor.
Definition: shape.h:69
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
line segment
Definition: shape.h:45
SHAPE_LINE_CHAIN::~SHAPE_LINE_CHAIN ( )
inline

Definition at line 128 of file shape_line_chain.h.

129  {}

Member Function Documentation

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

Function Append()

Appends 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

Definition at line 327 of file shape_line_chain.h.

Referenced by PNS_PCBNEW_DEBUG_DECORATOR::AddBox(), PNS_PCBNEW_DEBUG_DECORATOR::AddPoint(), ZONE_CONTAINER::AddPolygon(), PNS_PCBNEW_DEBUG_DECORATOR::AddSegment(), CINFO3D_VISU::AddShapeWithClearanceToContainer(), SHAPE_CONVEX::Append(), PNS::DIFF_PAIR::Append(), PNS::NODE::AssembleLine(), PNS::DIFF_PAIR::BuildInitial(), DIRECTION_45::BuildInitialTrace(), CINFO3D_VISU::buildPadShapePolygon(), SHAPE_POLY_SET::chamferFilletPolygon(), PNS::OPTIMIZER::circleBreakouts(), GRID_HELPER::computeAnchors(), SHAPE_POLY_SET::convertFromClipper(), PNS::OPTIMIZER::convexBreakouts(), PNS::ConvexHull(), PNS::MEANDER_PLACER::doMove(), PNS::LINE::DragCorner(), PNS::dragCornerInternal(), PNS::LINE::DragSegment(), ZONE_CONTAINER::FillZoneAreasWithSegments(), PNS::MEANDER_SHAPE::forward(), SHAPE_POLY_SET::fractureSingle(), PNS::MEANDER_SHAPE::genMeanderShape(), PNS::TOPOLOGY::LeadingRatLine(), PNS::MEANDER_SHAPE::MakeCorner(), PNS::MEANDER_SHAPE::makeMiterShape(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeObtuse(), PNS::MEANDER_SHAPE::miter(), PNS::DP_MEANDER_PLACER::Move(), PNS::OctagonalHull(), PNS::LINE_PLACER::optimizeTailHeadTransition(), SHAPE_RECT::Outline(), SHAPE_POLY_SET::Parse(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhStopAtNearestObstacle(), PNS::WALKAROUND::Route(), PNS::SegmentHull(), KIGFX::PREVIEW::POLYGON_ITEM::SetPoints(), PNS::WALKAROUND::singleStep(), Slice(), PNS::OPTIMIZER::smartPadsSingle(), PNS::MEANDER_SHAPE::start(), PNS::LINE_PLACER::Trace(), and PNS::LINE::Walkaround().

328  {
329  VECTOR2I v( aX, aY );
330  Append( v, aAllowDuplication );
331  }
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SHAPE_LINE_CHAIN::Append ( const VECTOR2I aP,
bool  aAllowDuplication = false 
)
inline

Function Append()

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

Parameters
aPthe new point

Definition at line 339 of file shape_line_chain.h.

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

340  {
341  if( m_points.size() == 0 )
342  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
343 
344  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
345  {
346  m_points.push_back( aP );
347  m_bbox.Merge( aP );
348  }
349  }
BOX2I m_bbox
cached bounding box
BOX2< VECTOR2I > BOX2I
Definition: box2.h:468
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590
std::vector< VECTOR2I > m_points
array of vertices
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect...
Definition: box2.h:350
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
void SHAPE_LINE_CHAIN::Append ( const SHAPE_LINE_CHAIN aOtherLine)
inline

Function Append()

Appends another line chain at the end.

Parameters
aOtherLinethe line chain to be appended.

Definition at line 357 of file shape_line_chain.h.

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

358  {
359  if( aOtherLine.PointCount() == 0 )
360  return;
361 
362  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
363  {
364  const VECTOR2I p = aOtherLine.CPoint( 0 );
365  m_points.push_back( p );
366  m_bbox.Merge( p );
367  }
368 
369  for( int i = 1; i < aOtherLine.PointCount(); i++ )
370  {
371  const VECTOR2I p = aOtherLine.CPoint( i );
372  m_points.push_back( p );
373  m_bbox.Merge( p );
374  }
375  }
BOX2I m_bbox
cached bounding box
int PointCount() const
Function PointCount()
std::vector< VECTOR2I > m_points
array of vertices
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect...
Definition: box2.h:350
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
const BOX2I SHAPE_LINE_CHAIN::BBox ( int  aClearance = 0) const
inlineoverridevirtual

Function BBox()

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

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

Implements SHAPE.

Definition at line 264 of file shape_line_chain.h.

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

Referenced by RN_NET::AddItem(), SHAPE_CONVEX::BBox(), fillPolygonWithHorizontalSegments(), Intersect(), and SHAPE_POLY_SET::pointInPolygon().

265  {
266  BOX2I bbox;
267  bbox.Compute( m_points );
268 
269  if( aClearance != 0 )
270  bbox.Inflate( aClearance );
271 
272  return bbox;
273  }
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:79
std::vector< VECTOR2I > m_points
array of vertices
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:266
virtual VECTOR2I SHAPE::Centre ( ) const
inlinevirtualinherited

Function Centre()

Computes a center-of-mass of the shape

Returns
the center-of-mass point

Definition at line 150 of file shape.h.

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

151  {
152  return BBox( 0 ).Centre(); // if nothing better is available....
153  }
virtual const BOX2I BBox(int aClearance=0) const =0
Function BBox()
Vec Centre() const
Definition: box2.h:67
SHAPE * SHAPE_LINE_CHAIN::Clone ( ) const
overridevirtual

Function Clone()

Returns a dynamically allocated copy of the shape

Return values
copyof the shape

Reimplemented from SHAPE.

Definition at line 562 of file shape_line_chain.cpp.

References SHAPE_LINE_CHAIN().

Referenced by ROUTER_PREVIEW_ITEM::Line().

563 {
564  return new SHAPE_LINE_CHAIN( *this );
565 }
SHAPE_LINE_CHAIN()
Constructor Initializes an empty line chain.
bool SHAPE::Collide ( const SHAPE aShape,
int  aClearance,
VECTOR2I aMTV 
) const
virtualinherited

Function Collide()

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

Parameters
aShapeshape to check collision against
aClearanceminimum clearance
aMTVminimum translation vector
Returns
true, if there is a collision.

Definition at line 456 of file shape_collisions.cpp.

References CollideShapes().

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

Definition at line 462 of file shape_collisions.cpp.

References CollideShapes(), and dummy().

463 {
464  VECTOR2I dummy;
465 
466  return CollideShapes( this, aShape, aClerance, false, dummy );
467 }
static LIB_PART * dummy()
Used when a LIB_PART is not found in library to draw a dummy shape This component is a 400 mils squar...
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)
bool SHAPE_LINE_CHAIN::Collide ( const VECTOR2I aP,
int  aClearance = 0 
) const
overridevirtual

Function Collide()

Checks 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.
Returns
true, when a collision has been found

Reimplemented from SHAPE.

Definition at line 30 of file shape_line_chain.cpp.

Referenced by PNS::MEANDERED_LINE::CheckSelfIntersections(), SHAPE_CONVEX::Collide(), and Collide().

31 {
32  // fixme: ugly!
33  SEG s( aP, aP );
34  return this->Collide( s, aClearance );
35 }
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide()
Definition: seg.h:37
bool SHAPE_LINE_CHAIN::Collide ( const SEG aSeg,
int  aClearance = 0 
) const
overridevirtual

Function Collide()

Checks 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.
Returns
true, when a collision has been found

Implements SHAPE.

Definition at line 38 of file shape_line_chain.cpp.

References SEG::A, SEG::B, SEG::Collide(), CSegment(), SegmentCount(), and BOX2< Vec >::SquaredDistance().

39 {
40  BOX2I box_a( aSeg.A, aSeg.B - aSeg.A );
41  BOX2I::ecoord_type dist_sq = (BOX2I::ecoord_type) aClearance * aClearance;
42 
43  for( int i = 0; i < SegmentCount(); i++ )
44  {
45  const SEG& s = CSegment( i );
46  BOX2I box_b( s.A, s.B - s.A );
47 
48  BOX2I::ecoord_type d = box_a.SquaredDistance( box_b );
49 
50  if( d < dist_sq )
51  {
52  if( s.Collide( aSeg, aClearance ) )
53  return true;
54  }
55  }
56 
57  return false;
58 }
const SEG CSegment(int aIndex) const
Function CSegment()
VECTOR2I::extended_type ecoord_type
Definition: box2.h:49
Definition: seg.h:37
VECTOR2I A
Definition: seg.h:47
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:48
bool SHAPE_LINE_CHAIN::CompareGeometry ( const SHAPE_LINE_CHAIN aOther) const

Definition at line 539 of file shape_line_chain.cpp.

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

Referenced by PNS::LINE::CompareGeometry(), and PNS::SHOVE::processHullSet().

540 {
541  SHAPE_LINE_CHAIN a(*this), b( aOther );
542  a.Simplify();
543  b.Simplify();
544 
545  if( a.m_points.size() != b.m_points.size() )
546  return false;
547 
548  for( int i = 0; i < a.PointCount(); i++)
549  if( a.CPoint( i ) != b.CPoint( i ) )
550  return false;
551  return true;
552 }
Class SHAPE_LINE_CHAIN.
const VECTOR2I& SHAPE_LINE_CHAIN::CPoint ( int  aIndex) const
inline

Function CPoint()

Returns a const reference to a given point in the line chain.

Parameters
aIndexindex of the point
Returns
const reference to the point

Definition at line 253 of file shape_line_chain.h.

References m_points, and PointCount().

Referenced by CINFO3D_VISU::AddSolidAreasShapesToContainer(), CLAYER_TRIANGLES::AddToMiddleContourns(), Append(), PNS::LINE::AppendVia(), PNS::LINE_RESTRICTIONS::Build(), BuildConvexHull(), PNS::LINE_PLACER::buildInitialLine(), CINFO3D_VISU::buildPadShapeThickOutlineAsPolygon(), CINFO3D_VISU::buildPadShapeThickOutlineAsSegments(), PNS::LINE::ChangedArea(), DRC::checkClearancePadToPad(), CompareGeometry(), Convert_shape_line_polygon_to_triangles(), ConvertPolySetToPolyList(), SHAPE_POLY_SET::convertToClipper(), PNS::coupledBypass(), SHAPE_CONVEX::CPoint(), PNS::LINE::CPoint(), PNS::dragCornerInternal(), PNS::LINE::DragSegment(), KIGFX::PCB_PAINTER::draw(), ZONE_CONTAINER::DrawFilledArea(), KIGFX::CAIRO_GAL::drawPoly(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolyline(), PNS::LOGGER::dumpShape(), export_vrml_board(), export_vrml_zones(), fillPolygonWithHorizontalSegments(), Find(), PNS::LINE_PLACER::FixRoute(), PNS::TOPOLOGY::followTrivialPath(), FractureEdge::FractureEdge(), PNS::MEANDER_SHAPE::genMeanderShape(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), D_PAD::HitTest(), PNS::LINE_PLACER::mergeHead(), PNS::MEANDER_SHAPE::miter(), PNS::LINE_PLACER::Move(), NearestPoint(), operator!=(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PlotLayerOutlines(), DXF_PLOTTER::PlotPoly(), PointAlong(), SHAPE_POLY_SET::pointInPolygon(), Polygon_Calc_BBox_3DU(), polygon_Convert(), PNS::SHOVE::processHullSet(), PNS::LINE_PLACER::removeLoops(), PNS::DIFF_PAIR_PLACER::routeHead(), PNS::OPTIMIZER::runSmartPads(), Simplify(), ZONE_CONTAINER::TransformSolidAreasShapesToPolygonSet(), PNS::MEANDER_SHAPE::updateBaseSegment(), PNS::LINE::Walkaround(), and PNS::SHOVE::walkaroundLoneVia().

254  {
255  if( aIndex < 0 )
256  aIndex += PointCount();
257  else if( aIndex >= PointCount() )
258  aIndex -= PointCount();
259 
260  return m_points[aIndex];
261  }
int PointCount() const
Function PointCount()
std::vector< VECTOR2I > m_points
array of vertices
const SEG SHAPE_LINE_CHAIN::CSegment ( int  aIndex) const
inline

Function CSegment()

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

Parameters
aIndexindex 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
const SEG - aIndex-th segment in the line chain

Definition at line 218 of file shape_line_chain.h.

References m_closed, m_points, and SegmentCount().

Referenced by PNS::LINE_RESTRICTIONS::Build(), PNS::LINE_PLACER::buildInitialLine(), PNS::LINE_RESTRICTIONS::Check(), PNS::NODE::CheckColliding(), PNS::DIFF_PAIR::CheckConnectionAngle(), PNS::checkGap(), PNS::MEANDERED_LINE::CheckSelfIntersections(), Collide(), Collide(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), PNS::coupledBypass(), PNS::DIFF_PAIR::CoupledLength(), PNS::DIFF_PAIR::CoupledSegmentPairs(), PNS::LINE::CSegment(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), Distance(), PNS::dragCornerInternal(), PNS::LINE::DragSegment(), ROUTER_PREVIEW_ITEM::drawLineChain(), PNS::findCoupledVertices(), FindSegment(), PNS::LINE_PLACER::FixRoute(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), Intersect(), PNS::LINE::Is45Degree(), Length(), PNS::OPTIMIZER::mergeDpStep(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeObtuse(), PNS::OPTIMIZER::mergeStep(), PNS::NODE::NearestObstacle(), NearestPoint(), PathLength(), PointAlong(), PointInside(), PointOnEdge(), PNS::LINE_PLACER::reduceTail(), PNS::LINE_PLACER::rhStopAtNearestObstacle(), PNS::SegmentHull(), SelfIntersecting(), PNS::OPTIMIZER::smartPadsSingle(), PNS::LINE::snapDraggedCorner(), PNS::LINE::snapToNeighbourSegments(), and Split().

219  {
220  if( aIndex < 0 )
221  aIndex += SegmentCount();
222 
223  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
224  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
225  const_cast<VECTOR2I&>( m_points[0] ), aIndex );
226  else
227  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
228  const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex );
229  }
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
Definition: seg.h:37
int SegmentCount() const
Function SegmentCount()
int SHAPE_LINE_CHAIN::Distance ( const VECTOR2I aP) const

Function Distance()

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

Parameters
aPthe point
Returns
minimum distance.

Definition at line 126 of file shape_line_chain.cpp.

References CSegment(), SEG::Distance(), IsClosed(), min, PointInside(), and SegmentCount().

Referenced by Collide().

127 {
128  int d = INT_MAX;
129 
130  if( IsClosed() && PointInside( aP ) )
131  return 0;
132 
133  for( int s = 0; s < SegmentCount(); s++ )
134  d = std::min( d, CSegment( s ).Distance( aP ) );
135 
136  return d;
137 }
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
const SEG CSegment(int aIndex) const
Function CSegment()
bool IsClosed() const
Function IsClosed()
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:185
int SegmentCount() const
Function SegmentCount()
#define min(a, b)
Definition: auxiliary.h:85
int SHAPE_LINE_CHAIN::Find ( const VECTOR2I aP) const

Function Find()

Searches for point aP.

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

Definition at line 178 of file shape_line_chain.cpp.

References CPoint(), and PointCount().

Referenced by PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::DRAGGER::dumbDragVia(), PNS::NODE::FindLinesBetweenJoints(), Split(), and PNS::LINE::Walkaround().

179 {
180  for( int s = 0; s < PointCount(); s++ )
181  if( CPoint( s ) == aP )
182  return s;
183 
184  return -1;
185 }
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int SHAPE_LINE_CHAIN::FindSegment ( const VECTOR2I aP) const

Function FindSegment()

Searches for segment containing point aP.

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

Definition at line 188 of file shape_line_chain.cpp.

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

Referenced by PNS::MEANDER_PLACER_BASE::cutTunedLine().

189 {
190  for( int s = 0; s < SegmentCount(); s++ )
191  if( CSegment( s ).Distance( aP ) <= 1 )
192  return s;
193 
194  return -1;
195 }
const SEG CSegment(int aIndex) const
Function CSegment()
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:185
int SegmentCount() const
Function SegmentCount()
const std::string SHAPE_LINE_CHAIN::Format ( ) const
overridevirtual

Reimplemented from SHAPE.

Definition at line 526 of file shape_line_chain.cpp.

References m_closed, m_points, and PointCount().

527 {
528  std::stringstream ss;
529 
530  ss << m_points.size() << " " << ( m_closed ? 1 : 0 ) << " ";
531 
532  for( int i = 0; i < PointCount(); i++ )
533  ss << m_points[i].x << " " << m_points[i].y << " "; // Format() << " ";
534 
535  return ss.str();
536 }
int PointCount() const
Function PointCount()
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
void SHAPE_LINE_CHAIN::Insert ( int  aVertex,
const VECTOR2I aP 
)
inline

Definition at line 377 of file shape_line_chain.h.

References m_points.

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

378  {
379  m_points.insert( m_points.begin() + aVertex, aP );
380  }
std::vector< VECTOR2I > m_points
array of vertices
int SHAPE_LINE_CHAIN::Intersect ( const SEG aSeg,
INTERSECTIONS aIp 
) const

Function Intersect()

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

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

Definition at line 230 of file shape_line_chain.cpp.

References SEG::A, CSegment(), SEG::Intersect(), SHAPE_LINE_CHAIN::INTERSECTION::our, SHAPE_LINE_CHAIN::INTERSECTION::p, SegmentCount(), and SHAPE_LINE_CHAIN::INTERSECTION::their.

Referenced by PNS::OPTIMIZER::convexBreakouts(), PNS::LINE_PLACER::handleSelfIntersections(), Intersects(), PNS::NODE::NearestObstacle(), and PNS::LINE::Walkaround().

231 {
232  for( int s = 0; s < SegmentCount(); s++ )
233  {
234  OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
235 
236  if( p )
237  {
238  INTERSECTION is;
239  is.our = CSegment( s );
240  is.their = aSeg;
241  is.p = *p;
242  aIp.push_back( is );
243  }
244  }
245 
246  compareOriginDistance comp( aSeg.A );
247  sort( aIp.begin(), aIp.end(), comp );
248 
249  return aIp.size();
250 }
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
const SEG CSegment(int aIndex) const
Function CSegment()
VECTOR2I A
Definition: seg.h:47
int SegmentCount() const
Function SegmentCount()
int SHAPE_LINE_CHAIN::Intersect ( const SHAPE_LINE_CHAIN aChain,
INTERSECTIONS aIp 
) const

Function Intersect()

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

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

Definition at line 253 of file shape_line_chain.cpp.

References SEG::A, SEG::B, BBox(), SEG::Collinear(), SEG::Contains(), CSegment(), SEG::Intersect(), BOX2< Vec >::Intersects(), SHAPE_LINE_CHAIN::INTERSECTION::our, SHAPE_LINE_CHAIN::INTERSECTION::p, SegmentCount(), and SHAPE_LINE_CHAIN::INTERSECTION::their.

254 {
255  BOX2I bb_other = aChain.BBox();
256 
257  for( int s1 = 0; s1 < SegmentCount(); s1++ )
258  {
259  const SEG& a = CSegment( s1 );
260  const BOX2I bb_cur( a.A, a.B - a.A );
261 
262  if( !bb_other.Intersects( bb_cur ) )
263  continue;
264 
265  for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
266  {
267  const SEG& b = aChain.CSegment( s2 );
268  INTERSECTION is;
269 
270  if( a.Collinear( b ) )
271  {
272  is.our = a;
273  is.their = b;
274 
275  if( a.Contains( b.A ) ) { is.p = b.A; aIp.push_back( is ); }
276  if( a.Contains( b.B ) ) { is.p = b.B; aIp.push_back( is ); }
277  if( b.Contains( a.A ) ) { is.p = a.A; aIp.push_back( is ); }
278  if( b.Contains( a.B ) ) { is.p = a.B; aIp.push_back( is ); }
279  }
280  else
281  {
282  OPT_VECTOR2I p = a.Intersect( b );
283 
284  if( p )
285  {
286  is.p = *p;
287  is.our = a;
288  is.their = b;
289  aIp.push_back( is );
290  }
291  }
292  }
293  }
294 
295  return aIp.size();
296 }
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
const SEG CSegment(int aIndex) const
Function CSegment()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
bool Intersects(const BOX2< Vec > &aRect) const
Function Intersects.
Definition: box2.h:224
Definition: seg.h:37
VECTOR2I A
Definition: seg.h:47
bool Collinear(const SEG &aSeg) const
Function Collinear()
Definition: seg.h:221
bool Contains(const VECTOR2I &aP) const
Definition: seg.cpp:155
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:48
bool SHAPE_LINE_CHAIN::Intersects ( const SHAPE_LINE_CHAIN aChain) const

Definition at line 555 of file shape_line_chain.cpp.

References dummy(), and Intersect().

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

556 {
558  return Intersect( aChain, dummy ) != 0;
559 }
std::vector< INTERSECTION > INTERSECTIONS
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
static LIB_PART * dummy()
Used when a LIB_PART is not found in library to draw a dummy shape This component is a 400 mils squar...
bool SHAPE_LINE_CHAIN::IsClosed ( ) const
inline

Function IsClosed()

Returns
aClosed: true, when our line is closed.

Definition at line 160 of file shape_line_chain.h.

References m_closed.

Referenced by SHAPE_POLY_SET::AddOutline(), Distance(), ROUTER_PREVIEW_ITEM::drawLineChain(), KIGFX::CAIRO_GAL::drawPoly(), KIGFX::OPENGL_GAL::DrawPolyline(), PNS::LOGGER::dumpShape(), and SelfIntersecting().

161  {
162  return m_closed;
163  }
bool m_closed
is the line chain closed?
bool SHAPE_LINE_CHAIN::IsSolid ( ) const
inlineoverridevirtual

Implements SHAPE.

Definition at line 592 of file shape_line_chain.h.

593  {
594  return false;
595  }
int SHAPE_LINE_CHAIN::Length ( ) const

Function Length()

Returns length of the line chain in Euclidean metric.

Returns
length of the line chain

Definition at line 72 of file shape_line_chain.cpp.

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

Referenced by PNS::COST_ESTIMATOR::Add(), PNS::LINE::DragSegment(), PNS::OPTIMIZER::fanoutCleanup(), PNS::MEANDER_SHAPE::MaxTunableLength(), PNS::NODE::NearestObstacle(), PNS::SHOVE::onCollidingSegment(), PNS::LINE_PLACER::reduceToNearestObstacle(), PNS::COST_ESTIMATOR::Remove(), PNS::COST_ESTIMATOR::Replace(), PNS::LINE_PLACER::rhStopAtNearestObstacle(), PNS::WALKAROUND::Route(), PNS::WALKAROUND::singleStep(), PNS::DIFF_PAIR::Skew(), PNS::DIFF_PAIR::TotalLength(), and PNS::SHOVE::walkaroundLoneVia().

73 {
74  int l = 0;
75 
76  for( int i = 0; i < SegmentCount(); i++ )
77  l += CSegment( i ).Length();
78 
79  return l;
80 }
int Length() const
Function Length()
Definition: seg.h:282
const SEG CSegment(int aIndex) const
Function CSegment()
int SegmentCount() const
Function SegmentCount()
void SHAPE_LINE_CHAIN::Move ( const VECTOR2I aVector)
inlineoverridevirtual

Implements SHAPE.

Definition at line 586 of file shape_line_chain.h.

References m_points.

Referenced by SHAPE_CONVEX::Move().

587  {
588  for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i )
589  (*i) += aVector;
590  }
std::vector< VECTOR2I > m_points
array of vertices
const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint ( const VECTOR2I aP) const

Function NearestPoint()

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

Returns
the nearest point.

Definition at line 486 of file shape_line_chain.cpp.

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

Referenced by GRID_HELPER::computeAnchors(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), and PNS::MoveDiagonal().

487 {
488  int min_d = INT_MAX;
489  int nearest = 0;
490 
491  for( int i = 0; i < SegmentCount(); i++ )
492  {
493  int d = CSegment( i ).Distance( aP );
494 
495  if( d < min_d )
496  {
497  min_d = d;
498  nearest = i;
499  }
500  }
501 
502  return CSegment( nearest ).NearestPoint( aP );
503 }
const SEG CSegment(int aIndex) const
Function CSegment()
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:354
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:185
int SegmentCount() const
Function SegmentCount()
const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint ( const SEG aSeg,
int &  dist 
) const

Function NearestPoint()

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

Parameters
aSegSegment defining the line.
distreference receiving the distance to the nearest point.
Returns
the nearest point.

Definition at line 506 of file shape_line_chain.cpp.

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

507 {
508  int nearest = 0;
509 
510  dist = INT_MAX;
511  for( int i = 0; i < PointCount(); i++ )
512  {
513  int d = aSeg.LineDistance( CPoint( i ) );
514 
515  if( d < dist )
516  {
517  dist = d;
518  nearest = i;
519  }
520  }
521 
522  return CPoint( nearest );
523 }
int PointCount() const
Function PointCount()
static const int dist[10][10]
Definition: dist.cpp:57
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:337
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
bool SHAPE_LINE_CHAIN::operator!= ( const SHAPE_LINE_CHAIN aRhs) const
inline

Definition at line 570 of file shape_line_chain.h.

References CPoint(), and PointCount().

571  {
572  if( PointCount() != aRhs.PointCount() )
573  return true;
574 
575  for( int i = 0; i < PointCount(); i++ )
576  {
577  if( CPoint( i ) != aRhs.CPoint( i ) )
578  return true;
579  }
580 
581  return false;
582  }
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
bool SHAPE_LINE_CHAIN::Parse ( std::stringstream &  aStream)
overridevirtual

Reimplemented from SHAPE.

Definition at line 567 of file shape_line_chain.cpp.

References m_closed, and m_points.

568 {
569  int n_pts;
570 
571  m_points.clear();
572  aStream >> n_pts;
573 
574  // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
575  if( n_pts < 0 || n_pts > int( aStream.str().size() ) )
576  return false;
577 
578  aStream >> m_closed;
579 
580  for( int i = 0; i < n_pts; i++ )
581  {
582  int x, y;
583  aStream >> x;
584  aStream >> y;
585  m_points.push_back( VECTOR2I( x, y ) );
586  }
587 
588  return true;
589 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
int SHAPE_LINE_CHAIN::PathLength ( const VECTOR2I aP) const

Function PathLength()

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

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

Definition at line 299 of file shape_line_chain.cpp.

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

Referenced by PNS::NODE::NearestObstacle(), and PNS::LINE::Walkaround().

300 {
301  int sum = 0;
302 
303  for( int i = 0; i < SegmentCount(); i++ )
304  {
305  const SEG seg = CSegment( i );
306  int d = seg.Distance( aP );
307 
308  if( d <= 1 )
309  {
310  sum += ( aP - seg.A ).EuclideanNorm();
311  return sum;
312  }
313  else
314  sum += seg.Length();
315  }
316 
317  return -1;
318 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:104
int Length() const
Function Length()
Definition: seg.h:282
const SEG CSegment(int aIndex) const
Function CSegment()
Definition: seg.h:37
VECTOR2I A
Definition: seg.h:47
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:185
int SegmentCount() const
Function SegmentCount()
const VECTOR2I SHAPE_LINE_CHAIN::PointAlong ( int  aPathLength) const

Definition at line 592 of file shape_line_chain.cpp.

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

593 {
594  int total = 0;
595 
596  if( aPathLength == 0 )
597  return CPoint( 0 );
598 
599  for( int i = 0; i < SegmentCount(); i++ )
600  {
601  const SEG& s = CSegment( i );
602  int l = s.Length();
603 
604  if( total + l >= aPathLength )
605  {
606  VECTOR2I d( s.B - s.A );
607  return s.A + d.Resize( aPathLength - total );
608  }
609 
610  total += l;
611  }
612 
613  return CPoint( -1 );
614 }
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:388
int Length() const
Function Length()
Definition: seg.h:282
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:65
const SEG CSegment(int aIndex) const
Function CSegment()
Definition: seg.h:37
VECTOR2I A
Definition: seg.h:47
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:48
int SHAPE_LINE_CHAIN::PointCount ( ) const
inline

Function PointCount()

Returns the number of points (vertices) in this line chain

Returns
number of points

Definition at line 186 of file shape_line_chain.h.

References m_points.

Referenced by CINFO3D_VISU::AddSolidAreasShapesToContainer(), CLAYER_TRIANGLES::AddToMiddleContourns(), Append(), PNS::LINE::AppendVia(), PNS::LINE_RESTRICTIONS::Build(), BuildConvexHull(), CINFO3D_VISU::buildPadShapeThickOutlineAsPolygon(), CINFO3D_VISU::buildPadShapeThickOutlineAsSegments(), PNS::LINE::ChangedArea(), DRC::checkClearancePadToPad(), Convert_shape_line_polygon_to_triangles(), ConvertPolySetToPolyList(), SHAPE_POLY_SET::convertToClipper(), PNS::coupledBypass(), CPoint(), PNS::LINE::DragSegment(), KIGFX::PCB_PAINTER::draw(), APERTURE_MACRO::DrawApertureMacroShape(), ZONE_CONTAINER::DrawFilledArea(), KIGFX::CAIRO_GAL::drawPoly(), KIGFX::OPENGL_GAL::DrawPolygon(), KIGFX::OPENGL_GAL::DrawPolyline(), D_PAD::DrawShape(), PNS::LOGGER::dumpShape(), export_vrml_board(), export_vrml_zones(), DSN::SPECCTRA_DB::fillBOUNDARY(), fillPolygonWithHorizontalSegments(), ZONE_CONTAINER::FillZoneAreasWithSegments(), Find(), PNS::LINE_PLACER::FixRoute(), HPGL_PLOTTER::FlashPadCustom(), PSLIKE_PLOTTER::FlashPadCustom(), GERBER_PLOTTER::FlashPadCustom(), DXF_PLOTTER::FlashPadCustom(), HPGL_PLOTTER::FlashPadRoundRect(), PSLIKE_PLOTTER::FlashPadRoundRect(), GERBER_PLOTTER::FlashPadRoundRect(), DXF_PLOTTER::FlashPadRoundRect(), Format(), PNS::MEANDER_SHAPE::genMeanderShape(), SHAPE_POLY_SET::GetRelativeIndices(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), D_PAD::HitTest(), DRAWING_TOOL::make45DegLine(), PNS::OPTIMIZER::mergeObtuse(), NearestPoint(), operator!=(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PlotLayerOutlines(), DXF_PLOTTER::PlotPoly(), Point(), SHAPE_CONVEX::PointCount(), PNS::LINE::PointCount(), SHAPE_POLY_SET::pointInPolygon(), PointOnEdge(), Polygon_Calc_BBox_3DU(), polygon_Convert(), PNS::SHOVE::processHullSet(), Remove(), Replace(), PNS::OPTIMIZER::runSmartPads(), Simplify(), Slice(), PNS_KICAD_IFACE::syncPad(), ZONE_CONTAINER::TransformSolidAreasShapesToPolygonSet(), POLYGON_GEOM_MANAGER::updateLeaderPoints(), PNS::LINE::Walkaround(), and PNS::SHOVE::walkaroundLoneVia().

187  {
188  return m_points.size();
189  }
std::vector< VECTOR2I > m_points
array of vertices
bool SHAPE_LINE_CHAIN::PointInside ( const VECTOR2I aP) const

Function PointInside()

Checks if point aP lies inside a convex polygon defined by the line chain. For closed shapes only.

Parameters
aPpoint to check
Returns
true if the point is inside the shape (edge is not treated as being inside).

Definition at line 321 of file shape_line_chain.cpp.

References SEG::A, SEG::B, CSegment(), m_closed, SegmentCount(), and SEG::Side().

Referenced by Distance(), and PNS::LINE::Walkaround().

322 {
323  if( !m_closed || SegmentCount() < 3 )
324  return false;
325 
326  int cur = CSegment( 0 ).Side( aP );
327 
328  if( cur == 0 )
329  return false;
330 
331  for( int i = 1; i < SegmentCount(); i++ )
332  {
333  const SEG s = CSegment( i );
334 
335  if( aP == s.A || aP == s.B ) // edge does not belong to the interior!
336  return false;
337 
338  if( s.Side( aP ) != cur )
339  return false;
340  }
341 
342  return true;
343 }
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:123
const SEG CSegment(int aIndex) const
Function CSegment()
bool m_closed
is the line chain closed?
Definition: seg.h:37
VECTOR2I A
Definition: seg.h:47
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:48
bool SHAPE_LINE_CHAIN::PointOnEdge ( const VECTOR2I aP) const

Function PointOnEdge()

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

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

Referenced by PNS::SHOVE::checkBumpDirection(), and SHAPE_POLY_SET::containsSingle().

347 {
348  if( !PointCount() )
349  return false;
350 
351  else if( PointCount() == 1 )
352  return m_points[0] == aP;
353 
354  for( int i = 0; i < SegmentCount(); i++ )
355  {
356  const SEG s = CSegment( i );
357 
358  if( s.A == aP || s.B == aP )
359  return true;
360 
361  if( s.Distance( aP ) <= 1 )
362  return true;
363  }
364 
365  return false;
366 }
int PointCount() const
Function PointCount()
const SEG CSegment(int aIndex) const
Function CSegment()
std::vector< VECTOR2I > m_points
array of vertices
Definition: seg.h:37
VECTOR2I A
Definition: seg.h:47
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:185
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:48
void SHAPE_LINE_CHAIN::Remove ( int  aStartIndex,
int  aEndIndex 
)

Function Remove()

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

Parameters
aStartIndexstart of the point range to be replaced (inclusive)
aEndIndexend of the point range to be replaced (inclusive)

Definition at line 114 of file shape_line_chain.cpp.

References m_points, and PointCount().

Referenced by PNS::LINE_PLACER::buildInitialLine(), PNS::LINE::ClipToNearestObstacle(), PNS::LINE::DragSegment(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::handlePullback(), PNS::LINE_PLACER::handleSelfIntersections(), PNS::LINE_PLACER::mergeHead(), PNS::LINE_PLACER::reduceTail(), Remove(), and PNS::WALKAROUND::Route().

115 {
116  if( aEndIndex < 0 )
117  aEndIndex += PointCount();
118 
119  if( aStartIndex < 0 )
120  aStartIndex += PointCount();
121 
122  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
123 }
int PointCount() const
Function PointCount()
std::vector< VECTOR2I > m_points
array of vertices
void SHAPE_LINE_CHAIN::Remove ( int  aIndex)
inline

Function Remove() removes the aIndex-th point from the line chain.

Parameters
aIndexis the index of the point to be removed.

Definition at line 418 of file shape_line_chain.h.

References Remove().

419  {
420  Remove( aIndex, aIndex );
421  }
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
void SHAPE_LINE_CHAIN::Replace ( int  aStartIndex,
int  aEndIndex,
const VECTOR2I aP 
)

Function Replace()

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

Parameters
aStartIndexstart of the point range to be replaced (inclusive)
aEndIndexend of the point range to be replaced (inclusive)
aPreplacement point

Definition at line 83 of file shape_line_chain.cpp.

References m_points, and PointCount().

Referenced by PNS::coupledBypass(), PNS::LINE::DragSegment(), PNS::OPTIMIZER::mergeDpStep(), PNS::OPTIMIZER::mergeObtuse(), PNS::OPTIMIZER::mergeStep(), and PNS::LINE_PLACER::optimizeTailHeadTransition().

84 {
85  if( aEndIndex < 0 )
86  aEndIndex += PointCount();
87 
88  if( aStartIndex < 0 )
89  aStartIndex += PointCount();
90 
91  if( aStartIndex == aEndIndex )
92  m_points[aStartIndex] = aP;
93  else
94  {
95  m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 );
96  m_points[aStartIndex] = aP;
97  }
98 }
int PointCount() const
Function PointCount()
std::vector< VECTOR2I > m_points
array of vertices
void SHAPE_LINE_CHAIN::Replace ( int  aStartIndex,
int  aEndIndex,
const SHAPE_LINE_CHAIN aLine 
)

Function Replace()

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

Parameters
aStartIndexstart of the point range to be replaced (inclusive)
aEndIndexend of the point range to be replaced (inclusive)
aLinereplacement line chain.

Definition at line 101 of file shape_line_chain.cpp.

References m_points, and PointCount().

102 {
103  if( aEndIndex < 0 )
104  aEndIndex += PointCount();
105 
106  if( aStartIndex < 0 )
107  aStartIndex += PointCount();
108 
109  m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
110  m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() );
111 }
int PointCount() const
Function PointCount()
std::vector< VECTOR2I > m_points
array of vertices
const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Reverse ( ) const

Function Reverse()

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

References m_closed, m_points, and reverse().

Referenced by PNS::coupledBypass(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::LINE::DragCorner(), PNS::DP_GATEWAY::Reverse(), PNS::LINE::Reverse(), PNS::SegmentHull(), and PNS::OPTIMIZER::smartPadsSingle().

62 {
63  SHAPE_LINE_CHAIN a( *this );
64 
65  reverse( a.m_points.begin(), a.m_points.end() );
66  a.m_closed = m_closed;
67 
68  return a;
69 }
bool m_closed
is the line chain closed?
Class SHAPE_LINE_CHAIN.
static void reverse(privcurve_t *curve)
Definition: trace.cpp:1020
SEG SHAPE_LINE_CHAIN::Segment ( int  aIndex)
inline

Function Segment()

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

Parameters
aIndexindex 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
SEG - aIndex-th segment in the line chain

Definition at line 199 of file shape_line_chain.h.

References m_closed, m_points, and SegmentCount().

Referenced by DRC::doEdgeZoneDrc(), and PNS::WALKAROUND::Route().

200  {
201  if( aIndex < 0 )
202  aIndex += SegmentCount();
203 
204  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
205  return SEG( m_points[aIndex], m_points[0], aIndex );
206  else
207  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
208  }
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
Definition: seg.h:37
int SegmentCount() const
Function SegmentCount()
int SHAPE_LINE_CHAIN::SegmentCount ( ) const
inline

Function SegmentCount()

Returns number of segments in this line chain.

Returns
number of segments

Definition at line 171 of file shape_line_chain.h.

References m_closed, m_points, and max.

Referenced by PNS::LINE_PLACER::buildInitialLine(), PNS::LINE_RESTRICTIONS::Check(), PNS::NODE::CheckColliding(), PNS::DIFF_PAIR::CheckConnectionAngle(), PNS::checkGap(), PNS::MEANDERED_LINE::CheckSelfIntersections(), Collide(), Collide(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), PNS::DIFF_PAIR::CoupledLength(), PNS::DIFF_PAIR::CoupledSegmentPairs(), CSegment(), Distance(), PNS::LINE::DragCorner(), PNS::dragCornerInternal(), PNS::LINE::DragSegment(), ROUTER_PREVIEW_ITEM::drawLineChain(), PNS::DIFF_PAIR::Empty(), PNS::findCoupledVertices(), FindSegment(), PNS::LINE_PLACER::FixRoute(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::handlePullback(), Intersect(), PNS::LINE::Is45Degree(), Length(), PNS::OPTIMIZER::mergeDpSegments(), PNS::OPTIMIZER::mergeDpStep(), PNS::OPTIMIZER::mergeFull(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeObtuse(), PNS::OPTIMIZER::mergeStep(), PNS::NODE::NearestObstacle(), NearestPoint(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PathLength(), PointAlong(), PointInside(), PointOnEdge(), PNS::LINE_PLACER::reduceTail(), PNS::WALKAROUND::Route(), Segment(), PNS::LINE::SegmentCount(), SelfIntersecting(), PNS::OPTIMIZER::smartPadsSingle(), PNS::LINE::snapDraggedCorner(), PNS::LINE::snapToNeighbourSegments(), Split(), and PNS::LINE::Walkaround().

172  {
173  int c = m_points.size() - 1;
174  if( m_closed )
175  c++;
176 
177  return std::max( 0, c );
178  }
bool m_closed
is the line chain closed?
std::vector< VECTOR2I > m_points
array of vertices
#define max(a, b)
Definition: auxiliary.h:86
const optional< SHAPE_LINE_CHAIN::INTERSECTION > SHAPE_LINE_CHAIN::SelfIntersecting ( ) const

Function SelfIntersecting()

Checks if the line chain is self-intersecting.

Returns
(optional) first found self-intersection point.

Definition at line 369 of file shape_line_chain.cpp.

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

Referenced by PNS::DIFF_PAIR::BuildInitial(), and PNS::SHOVE::processHullSet().

370 {
371  for( int s1 = 0; s1 < SegmentCount(); s1++ )
372  {
373  for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
374  {
375  const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
376 
377  if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
378  {
379  INTERSECTION is;
380  is.our = CSegment( s1 );
381  is.their = CSegment( s2 );
382  is.p = s2a;
383  return is;
384  }
385  else if( CSegment( s1 ).Contains( s2b ) &&
386  // for closed polylines, the ending point of the
387  // last segment == starting point of the first segment
388  // this is a normal case, not self intersecting case
389  !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
390  {
391  INTERSECTION is;
392  is.our = CSegment( s1 );
393  is.their = CSegment( s2 );
394  is.p = s2b;
395  return is;
396  }
397  else
398  {
399  OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
400 
401  if( p )
402  {
403  INTERSECTION is;
404  is.our = CSegment( s1 );
405  is.their = CSegment( s2 );
406  is.p = *p;
407  return is;
408  }
409  }
410  }
411  }
412 
413  return optional<INTERSECTION>();
414 }
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:65
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
const SEG CSegment(int aIndex) const
Function CSegment()
VECTOR2I A
Definition: seg.h:47
bool IsClosed() const
Function IsClosed()
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:48
SHAPE_LINE_CHAIN & SHAPE_LINE_CHAIN::Simplify ( )

Function Simplify()

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

Returns
reference to self.

Definition at line 417 of file shape_line_chain.cpp.

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

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), DIRECTION_45::BuildInitialTrace(), PNS::LINE::ChangedArea(), CompareGeometry(), PNS::DIFF_PAIR::CoupledSegmentPairs(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::MEANDER_PLACER::doMove(), PNS::LINE::DragCorner(), PNS::LINE::DragSegment(), PNS::OPTIMIZER::mergeDpStep(), PNS::OPTIMIZER::mergeFull(), PNS::LINE_PLACER::mergeHead(), PNS::OPTIMIZER::mergeStep(), PNS::DP_MEANDER_PLACER::Move(), PNS::SHOVE::onCollidingSolid(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::SHOVE::processHullSet(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhStopAtNearestObstacle(), PNS::WALKAROUND::Route(), PNS::OPTIMIZER::runSmartPads(), PNS::TOPOLOGY::SimplifyLine(), PNS::LINE_PLACER::simplifyNewLine(), PNS::WALKAROUND::singleStep(), PNS::OPTIMIZER::smartPadsSingle(), PNS::LINE_PLACER::Trace(), and PNS::LINE::Walkaround().

418 {
419  std::vector<VECTOR2I> pts_unique;
420 
421  if( PointCount() < 2 )
422  {
423  return *this;
424  }
425  else if( PointCount() == 2 )
426  {
427  if( m_points[0] == m_points[1] )
428  m_points.pop_back();
429 
430  return *this;
431  }
432 
433  int i = 0;
434  int np = PointCount();
435 
436  // stage 1: eliminate duplicate vertices
437  while( i < np )
438  {
439  int j = i + 1;
440 
441  while( j < np && CPoint( i ) == CPoint( j ) )
442  j++;
443 
444  pts_unique.push_back( CPoint( i ) );
445  i = j;
446  }
447 
448  m_points.clear();
449  np = pts_unique.size();
450 
451  i = 0;
452 
453  // stage 1: eliminate collinear segments
454  while( i < np - 2 )
455  {
456  const VECTOR2I p0 = pts_unique[i];
457  const VECTOR2I p1 = pts_unique[i + 1];
458  int n = i;
459 
460  while( n < np - 2 && SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1 )
461  n++;
462 
463  m_points.push_back( p0 );
464 
465  if( n > i )
466  i = n;
467 
468  if( n == np )
469  {
470  m_points.push_back( pts_unique[n - 1] );
471  return *this;
472  }
473 
474  i++;
475  }
476 
477  if( np > 1 )
478  m_points.push_back( pts_unique[np - 2] );
479 
480  m_points.push_back( pts_unique[np - 1] );
481 
482  return *this;
483 }
int PointCount() const
Function PointCount()
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:65
std::vector< VECTOR2I > m_points
array of vertices
Definition: seg.h:37
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice ( int  aStartIndex,
int  aEndIndex = -1 
) const

Function Slice()

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

Parameters
aStartIndexstart of the point range to be returned (inclusive)
aEndIndexend of the point range to be returned (inclusive)
Returns
cut line chain.

Definition at line 198 of file shape_line_chain.cpp.

References Append(), m_points, and PointCount().

Referenced by PNS::LINE::ClipVertexRange(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::LINE::DragCorner(), PNS::dragCornerInternal(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::LINE_PLACER::reduceToNearestObstacle(), and PNS::LINE::Walkaround().

199 {
200  SHAPE_LINE_CHAIN rv;
201 
202  if( aEndIndex < 0 )
203  aEndIndex += PointCount();
204 
205  if( aStartIndex < 0 )
206  aStartIndex += PointCount();
207 
208  for( int i = aStartIndex; i <= aEndIndex; i++ )
209  rv.Append( m_points[i] );
210 
211  return rv;
212 }
int PointCount() const
Function PointCount()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
std::vector< VECTOR2I > m_points
array of vertices
Class SHAPE_LINE_CHAIN.
int SHAPE_LINE_CHAIN::Split ( const VECTOR2I aP)

Function Split()

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

Parameters
aPthe 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 140 of file shape_line_chain.cpp.

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

Referenced by PNS::LINE::ClipToNearestObstacle(), PNS::MEANDER_PLACER_BASE::cutTunedLine(), PNS::LINE_PLACER::reduceToNearestObstacle(), and PNS::LINE::Walkaround().

141 {
142  int ii = -1;
143  int min_dist = 2;
144 
145  int found_index = Find( aP );
146 
147  for( int s = 0; s < SegmentCount(); s++ )
148  {
149  const SEG seg = CSegment( s );
150  int dist = seg.Distance( aP );
151 
152  // make sure we are not producing a 'slightly concave' primitive. This might happen
153  // if aP lies very close to one of already existing points.
154  if( dist < min_dist && seg.A != aP && seg.B != aP )
155  {
156  min_dist = dist;
157  if( found_index < 0 )
158  ii = s;
159  else if( s < found_index )
160  ii = s;
161  }
162  }
163 
164  if( ii < 0 )
165  ii = found_index;
166 
167  if( ii >= 0 )
168  {
169  m_points.insert( m_points.begin() + ii + 1, aP );
170 
171  return ii + 1;
172  }
173 
174  return -1;
175 }
static const int dist[10][10]
Definition: dist.cpp:57
const SEG CSegment(int aIndex) const
Function CSegment()
int Find(const VECTOR2I &aP) const
Function Find()
std::vector< VECTOR2I > m_points
array of vertices
Definition: seg.h:37
VECTOR2I A
Definition: seg.h:47
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:185
int SegmentCount() const
Function SegmentCount()
VECTOR2I B
Definition: seg.h:48
SHAPE_TYPE SHAPE::Type ( ) const
inlineinherited

Function Type()

Returns the type of the shape.

Return values
thetype

Definition at line 82 of file shape.h.

References SHAPE::m_type.

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

83  {
84  return m_type;
85  }
SHAPE_TYPE m_type
type of our shape
Definition: shape.h:165

Member Data Documentation

BOX2I SHAPE_LINE_CHAIN::m_bbox
private

cached bounding box

Definition at line 607 of file shape_line_chain.h.

Referenced by Append().

bool SHAPE_LINE_CHAIN::m_closed
private

is the line chain closed?

Definition at line 604 of file shape_line_chain.h.

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

std::vector<VECTOR2I> SHAPE_LINE_CHAIN::m_points
private
SHAPE_TYPE SHAPE::m_type
protectedinherited

type of our shape

Definition at line 165 of file shape.h.

Referenced by SHAPE::Type().


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