26#ifndef __SHAPE_LINE_CHAIN
27#define __SHAPE_LINE_CHAIN
30#include "router/clipper_kicad/clipper.hpp"
31#include <geometry/seg.h>
32#include <geometry/shape.h>
33#include <geometry/shape_arc.h>
34#include <math/vector2d.h>
48 CLIPPER_Z_VALUE(
const std::pair<ssize_t, ssize_t> aShapeIndices, ssize_t aOffset = 0 )
50 m_FirstArcIdx = aShapeIndices.first;
51 m_SecondArcIdx = aShapeIndices.second;
53 auto offsetVal = [&]( ssize_t& aVal )
59 offsetVal( m_FirstArcIdx );
60 offsetVal( m_SecondArcIdx );
63 ssize_t m_FirstArcIdx;
64 ssize_t m_SecondArcIdx;
83 typedef std::vector<VECTOR2I>::iterator point_iter;
84 typedef std::vector<VECTOR2I>::const_iterator point_citer;
141 typedef std::vector<INTERSECTION> INTERSECTIONS;
155 m_points( aShape.m_points ),
156 m_shapes( aShape.m_shapes ),
157 m_arcs( aShape.m_arcs ),
158 m_closed( aShape.m_closed ),
159 m_width( aShape.m_width ),
160 m_bbox( aShape.m_bbox )
170 m_points.reserve( aV.size() );
173 m_points.emplace_back( pt.x, pt.y );
175 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
184 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
193 m_arcs.emplace_back( aArc );
194 m_arcs.back().SetWidth( 0 );
195 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( m_points.size(), { 0, SHAPE_IS_PT } );
199 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
200 const std::vector<SHAPE_ARC>& aArcBuffer );
217 virtual bool Collide(
const VECTOR2I& aP,
int aClearance = 0,
int* aActual =
nullptr,
218 VECTOR2I* aLocation =
nullptr )
const override;
232 virtual bool Collide(
const SEG& aSeg,
int aClearance = 0,
int* aActual =
nullptr,
233 VECTOR2I* aLocation =
nullptr )
const override;
297 int c = m_points.size() - 1;
301 return std::max( 0, c );
320 return m_points.size();
335 if( aIndex == (
int)( m_points.size() - 1 ) && m_closed )
336 return SEG( m_points[aIndex], m_points[0], aIndex );
338 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
353 if( aIndex == (
int)( m_points.size() - 1 ) && m_closed )
354 return SEG( m_points[aIndex], m_points[0], aIndex );
356 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
372 int NextShape(
int aPointIndex,
bool aForwards =
true )
const;
374 int PrevShape(
int aPointIndex )
const
400 return m_points[aIndex];
403 const std::vector<VECTOR2I>& CPoints()
const
413 return m_points[
static_cast<size_t>(
PointCount() ) - 1];
419 const std::vector<SHAPE_ARC>&
CArcs()
const
427 const std::vector<std::pair<ssize_t, ssize_t>>&
CShapes()
const
438 if( aClearance != 0 || m_width != 0 )
439 bbox.
Inflate( aClearance + m_width );
444 void GenerateBBoxCache()
const
452 BOX2I* GetCachedBBox()
const override
484 long long int Length()
const;
495 void Append(
int aX,
int aY,
bool aAllowDuplication =
false )
498 Append( v, aAllowDuplication );
511 if( m_points.size() == 0 )
514 if( m_points.size() == 0 || aAllowDuplication ||
CPoint( -1 ) != aP )
516 m_points.push_back( aP );
517 m_shapes.push_back( SHAPES_ARE_PT );
531 void Insert(
size_t aVertex,
const VECTOR2I& aP );
533 void Insert(
size_t aVertex,
const SHAPE_ARC& aArc );
560 void Remove(
int aStartIndex,
int aEndIndex );
597 int Find(
const VECTOR2I& aP,
int aThreshold = 0 )
const;
624 return ( m_origin - aA.
p ).EuclideanNorm() < ( m_origin - aB.
p ).
EuclideanNorm();
640 int Intersect(
const SEG& aSeg, INTERSECTIONS& aIp )
const;
651 bool aExcludeColinearAndTouching =
false )
const;
714 const std::string
Format()
const override;
717 bool Parse( std::stringstream& aStream )
override;
735 void Move(
const VECTOR2I& aVector )
override
737 for(
auto& pt : m_points )
740 for(
auto& arc : m_arcs )
751 void Mirror(
bool aX =
true,
bool aY =
false,
const VECTOR2I& aRef = { 0, 0 } );
768 bool IsSolid()
const override
773 const VECTOR2I PointAlong(
int aPathLength )
const;
780 double Area(
bool aAbsolute =
true )
const;
782 size_t ArcCount()
const
784 return m_arcs.size();
793 return m_shapes[aSegment].second;
795 return m_shapes[aSegment].first;
798 const SHAPE_ARC& Arc(
size_t aArc )
const
810 return aIndex < m_shapes.size()
811 && m_shapes[aIndex].first != SHAPE_IS_PT
812 && m_shapes[aIndex].second != SHAPE_IS_PT;
816 bool IsPtOnArc(
size_t aPtIndex )
const
818 return aPtIndex < m_shapes.size() && m_shapes[aPtIndex] != SHAPES_ARE_PT;
822 bool IsArcSegment(
size_t aSegment )
const
829 size_t nextIdx = aSegment + 1;
831 if( nextIdx > m_shapes.size() - 1 )
833 if( nextIdx == m_shapes.size() && m_closed )
839 return ( IsPtOnArc( aSegment )
841 || m_shapes[aSegment].first == m_shapes[nextIdx].first ) );
845 bool IsArcStart(
size_t aIndex )
const
848 return IsPtOnArc( aIndex );
850 return (
IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex - 1 ) ) );
854 bool IsArcEnd(
size_t aIndex )
const
856 return (
IsSharedPt( aIndex ) || ( IsPtOnArc( aIndex ) && !IsArcSegment( aIndex ) ) );
859 virtual const VECTOR2I GetPoint(
int aIndex )
const override {
return CPoint(aIndex); }
860 virtual const SEG GetSegment(
int aIndex )
const override {
return CSegment(aIndex); }
861 virtual size_t GetPointCount()
const override {
return PointCount(); }
862 virtual size_t GetSegmentCount()
const override {
return SegmentCount(); }
886 void splitArc( ssize_t aPtIndex,
bool aCoincident =
false );
888 void amendArc(
size_t aArcIndex,
const VECTOR2I& aNewStart,
const VECTOR2I& aNewEnd );
890 void amendArcStart(
size_t aArcIndex,
const VECTOR2I& aNewStart )
892 amendArc( aArcIndex, aNewStart, m_arcs[aArcIndex].GetP1() );
895 void amendArcEnd(
size_t aArcIndex,
const VECTOR2I& aNewEnd )
897 amendArc( aArcIndex, m_arcs[aArcIndex].GetP0(), aNewEnd );
906 return m_shapes[aSegment].first;
908 return m_shapes[aSegment].second;
915 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
916 std::vector<SHAPE_ARC>& aArcBuffer )
const;
930 static const ssize_t SHAPE_IS_PT;
932 static const std::pair<ssize_t, ssize_t> SHAPES_ARE_PT;
935 std::vector<VECTOR2I> m_points;
951 std::vector<std::pair<ssize_t, ssize_t>> m_shapes;
953 std::vector<SHAPE_ARC> m_arcs;
966 mutable BOX2I m_bbox;
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition box2.h:281
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition box2.h:75
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition box2.h:363
Definition shape_arc.h:36
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=DefaultAccuracyForPCB(), double *aEffectiveAccuracy=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
Definition shape_arc.cpp:458
A dynamic state checking if a point lies within polygon with a dynamically built outline ( with each ...
Definition shape_line_chain.h:122
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Definition shape_line_chain.h:81
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
Definition shape_line_chain.cpp:561
void Remove(int aIndex)
Remove the aIndex-th point from the line chain.
Definition shape_line_chain.h:567
int Width() const
Get the current width of the segments in the chain.
Definition shape_line_chain.h:285
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
Definition shape_line_chain.cpp:220
void Append(const VECTOR2I &aP, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
Definition shape_line_chain.h:509
const std::optional< INTERSECTION > SelfIntersecting() const
Check if the line chain is self-intersecting.
Definition shape_line_chain.cpp:1642
bool Parse(std::stringstream &aStream) override
Definition shape_line_chain.cpp:1946
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.
Definition shape_line_chain.cpp:1620
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
Definition shape_line_chain.cpp:1690
const std::string Format() const override
Definition shape_line_chain.cpp:1885
bool IsClosed() const override
Definition shape_line_chain.h:265
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
Definition shape_line_chain.cpp:1012
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
Definition shape_line_chain.cpp:818
int NextShape(int aPointIndex, bool aForwards=true) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
Definition shape_line_chain.cpp:953
void fixIndicesRotation()
Fix indices of this chain to ensure arcs are not split between the end and start indices.
Definition shape_line_chain.cpp:130
int FindSegment(const VECTOR2I &aP, int aThreshold=1) const
Search for segment containing point aP.
Definition shape_line_chain.cpp:891
int ShapeCount() const
Return the number of shapes (line segments or arcs) in this line chain.
Definition shape_line_chain.cpp:903
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
Definition shape_line_chain.h:256
ssize_t reversedArcIndex(size_t aSegment) const
Return the arc index for the given segment index, looking backwards.
Definition shape_line_chain.h:903
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
Definition shape_line_chain.cpp:1361
SHAPE_LINE_CHAIN()
Initialize an empty line chain.
Definition shape_line_chain.h:147
int PointCount() const
Return the number of points (vertices) in this line chain.
Definition shape_line_chain.h:318
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
Definition shape_line_chain.cpp:651
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.
Definition shape_line_chain.cpp:354
void ClearArcs()
Remove all arc references in the line chain, resulting in a chain formed only of straight segments.
Definition shape_line_chain.cpp:600
void mergeFirstLastPointIfNeeded()
Merge the first and last point if they are the same and this chain is closed.
Definition shape_line_chain.cpp:153
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
Definition shape_line_chain.h:790
void Clear()
Remove all points from the line chain.
Definition shape_line_chain.h:242
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.
Definition shape_line_chain.cpp:1066
const std::vector< SHAPE_ARC > & CArcs() const
Definition shape_line_chain.h:419
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
Definition shape_line_chain.cpp:1865
double Area(bool aAbsolute=true) const
Return the area of this chain.
Definition shape_line_chain.cpp:2019
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both).
Definition shape_line_chain.cpp:625
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
Definition shape_line_chain.h:495
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
Definition shape_line_chain.h:393
const std::vector< std::pair< ssize_t, ssize_t > > & CShapes() const
Definition shape_line_chain.h:427
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
Definition shape_line_chain.cpp:1792
int SegmentCount() const
Return the number of segments in this line chain.
Definition shape_line_chain.h:295
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 l...
Definition shape_line_chain.cpp:1501
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Compute the minimum distance between the line chain and a point aP.
Definition shape_line_chain.cpp:798
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
Definition shape_line_chain.h:411
ClipperLibKiCad::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.
Definition shape_line_chain.cpp:99
void convertArc(ssize_t aArcIndex)
Convert an arc to only a point chain by removing the arc and references.
Definition shape_line_chain.cpp:174
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
Definition shape_line_chain.cpp:729
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Definition shape_line_chain.h:348
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
Definition shape_line_chain.cpp:1030
void SetWidth(int aWidth)
Set the width of all segments in the chain.
Definition shape_line_chain.h:275
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
Definition shape_line_chain.h:808
long long int Length() const
Return length of the line chain in Euclidean metric.
Definition shape_line_chain.cpp:607
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
Definition shape_line_chain.cpp:871
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition shape_line_chain.h:433
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
Definition shape_line_chain.cpp:1940
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
Definition shape_line_chain.h:330
void Rotate(double aAngle, const VECTOR2I &aCenter=VECTOR2I(0, 0)) override
Rotate all vertices by a given angle.
Definition shape_line_chain.cpp:423
Represent a set of closed polygons.
Definition shape_poly_set.h:65
An abstract shape on 2D plane.
Definition shape.h:117
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
Definition shape_line_chain.h:41
Represent an intersection between two line segments.
Definition shape_line_chain.h:91
bool is_corner_their
Auxiliary flag to avoid copying intersection info to intersection refining code, used by the refining...
Definition shape_line_chain.h:108
bool is_corner_our
When true, the corner [index_their] of the 'their' line lies exactly on 'our' line.
Definition shape_line_chain.h:103
int index_our
index of the intersecting corner/segment in the 'their' (Intersect() method parameter) line.
Definition shape_line_chain.h:96
VECTOR2I p
< Point of intersection between our and their.
Definition shape_line_chain.h:93
int index_their
When true, the corner [index_our] of the 'our' line lies exactly on 'their' line.
Definition shape_line_chain.h:100
Definition shape_line_chain.h:617
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition trigo.h:146