38 m_line( aOther.m_line ),
39 m_width( aOther.m_width ),
40 m_snapThreshhold( aOther.m_snapThreshhold )
102 s->Unmark( aMarker );
114 marker |= s->Marker();
158 if( x > 0 && x - 1 == y )
161 if( x < max - 1 && x + 1 == y )
167#ifdef TOM_EXTRA_DEBUG
180 const auto pFirst = line.
CPoint(0);
191 enum VERTEX_TYPE { INSIDE = 0,
OUTSIDE, ON_EDGE };
204 std::vector<VERTEX*> neighbours;
210 bool visited =
false;
219 std::vector<VERTEX> vts;
223 for( VERTEX& v : vts )
234 if(
auto isect = pnew.SelfIntersecting() )
236 if( isect->p != pnew.CPoint( -1 ) )
238 pnew.Split( isect->p );
243 for(
auto& ip : ips )
245 if( pnew.Find( ip.p, 1 ) < 0)
250 if( hnew.
Find( ip.p, 1 ) < 0 )
256 for(
int i = 0; i < pnew.PointCount(); i++ )
258 auto p = pnew.CPoint(i);
264 int idx = hnew.
Find( p );
272 #ifdef TOM_EXTRA_DEBUG
273 for(
auto& ip : ips )
275 printf(
"Chk: %d %d\n", pnew.Find( ip.p ), hnew.
Find(ip.p) );
284 vts.reserve( 2 * ( hnew.
PointCount() + pnew.PointCount() ) );
287 for(
int i = 0; i < pnew.PointCount(); i++ )
293 #ifdef TOM_EXTRA_DEBUG
294 printf(
"pnew %d inside %d onedge %d\n", i, !!inside, !!onEdge );
302 v.type = inside && !onEdge ? INSIDE : onEdge ? ON_EDGE :
OUTSIDE;
306 #ifdef TOM_EXTRA_DEBUG
312 for(
int i = 0; i < pnew.PointCount() - 1; i++ )
314 vts[i].neighbours.push_back( &vts[ i+1 ] );
318 for(
int i = 1; i < pnew.PointCount() ; i++ )
320 vts[i].neighbours.push_back( &vts[ i-1 ] );
326 auto hp = hnew.
CPoint( i );
354 vc->neighbours.push_back(vnext);
362 int lastDst = INT_MAX;
365#ifdef TOM_EXTRA_DEBUG
368 if( v.indexh < 0 && v.type == ON_EDGE )
372 printf(
"V %d pos %d %d ip %d ih %d type %d\n", i++, v.pos.x, v.pos.y, v.indexp, v.indexh, v.type );
376 VERTEX* v = &vts[0], *v_prev =
nullptr;
379 int iterLimit = 1000;
382 while( v->indexp != ( pnew.PointCount() - 1 ) )
398#ifdef TOM_EXTRA_DEBUG
399 printf(
"---\nvisit ip %d ih %d type %d outs %d neig %d\n", v->indexp, v->indexh, v->type, out.
PointCount(), v->neighbours.size() );
403 VERTEX* v_next =
nullptr;
410 VERTEX* v_next_fallback =
nullptr;
411 for(
auto vn : v->neighbours )
413 if(
areNeighbours( vn->indexp , v->indexp, pnew.PointCount() ) &&
421 else if( vn != v_prev )
422 v_next_fallback = vn;
427 v_next = v_next_fallback;
432 #ifdef TOM_EXTRA_DEBUG
433 printf(
"FAIL VN fallback %p\n", v_next_fallback );
439 else if( v->type == ON_EDGE )
442 for( VERTEX* vn : v->neighbours )
444#ifdef TOM_EXTRA_DEBUG
445 printf(
"- OUT scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
448 if( vn->type ==
OUTSIDE && !vn->visited )
458 for( VERTEX* vn : v->neighbours )
460 #ifdef TOM_EXTRA_DEBUG
461 printf(
"- scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
463 if( vn->type == ON_EDGE && !vn->isHull &&
465 ( vn->indexh == ( ( v->indexh + 1 ) % hnew.
PointCount() ) ) )
477#ifdef TOM_EXTRA_DEBUG
478 printf(
"still no v_next\n");
480 for( VERTEX* vn : v->neighbours )
482 if( vn->type == ON_EDGE )
484 if( vn->indexh == ( ( v->indexh + 1 ) % hnew.
PointCount() ) )
501#ifdef TOM_EXTRA_DEBUG
502 printf(
"v_next %p\n", v_next);
508 if( inLast && v_next )
510 int d = ( v_next->pos -
CPoint( -1 ) ).SquaredEuclideanNorm();
553 const int IterationLimit = 5;
557 for( i = 0; i < IterationLimit; i++ )
564 VECTOR2I collisionPoint = obs->m_ipFirst;
586 if( i == IterationLimit )
596 std::optional<SHAPE_LINE_CHAIN> picked;
625 for(
int j = 0; j < 2; j++ )
629 if( paths[j].SegmentCount() < 1 )
632 assert( dirCount <
int(
sizeof( dirs ) /
sizeof( dirs[0] ) ) );
634 dirs[dirCount] =
DIRECTION_45( paths[j].CSegment( 0 ) );
638 for(
int j = 0; j < dirCount; j++ )
640 if( dirs[j] == d_start )
650 for(
int j = 0; j < dirCount; j++ )
652 if( dirs[j].IsObtuse( d_prev ) )
666 path.Append( *picked );
698 path.Append( path_rev );
702 path.SetWidth( width );
709 ssize_t idx =
static_cast<ssize_t
>( aIndex );
719 else if( ( idx == numpts - 1 ) || ( idx < numpts - 1 && !
m_line.
IsArcSegment( idx ) ) )
726 wxASSERT_MSG(
false, wxT(
"Attempt to dragCornerFree in the middle of an arc!" ) );
736 wxCHECK_RET( aIndex >= 0, wxT(
"Negative index passed to LINE::DragCorner" ) );
763 int s_start = std::max( aIndex - 2, 0 );
764 int s_end = std::min( aIndex + 2, aPath.
SegmentCount() - 1 );
767 int best_dist = INT_MAX;
773 for( i = s_start; i <= s_end; i++ )
777 for( j = s_start; j < i; j++ )
807 int snap_d[2] = { -1, -1 };
833 int minDist = INT_MAX;
835 for(
int i = 0; i < 2; i++ )
837 if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <=
m_snapThreshhold )
854 SEG guideA[2], guideB[2];
864 if( index == 0 ||
path.IsPtOnArc( index ) )
866 path.Insert( index > 0 ? index + 1 : 0,
path.CPoint( index ) );
870 if( index ==
path.SegmentCount() - 1 )
872 path.Insert(
path.PointCount() - 1,
path.CPoint( -1 ) );
874 else if(
path.IsPtOnArc( index + 1 ) )
876 path.Insert( index + 1,
path.CPoint( index + 1 ) );
879 SEG dragged =
path.CSegment( index );
882 SEG s_prev =
path.CSegment( index - 1 );
883 SEG s_next =
path.CSegment( index + 1 );
888 if( dir_prev == drag_dir )
890 dir_prev = dir_prev.
Left();
891 path.Insert( index,
path.CPoint( index ) );
896 dir_prev = drag_dir.
Left();
899 if( dir_next == drag_dir )
901 dir_next = dir_next.
Right();
902 path.Insert( index + 1,
path.CPoint( index + 1 ) );
906 dir_next = drag_dir.
Right();
909 s_prev =
path.CSegment( index - 1 );
910 s_next =
path.CSegment( index + 1 );
911 dragged =
path.CSegment( index );
920 if( dir_prev.
Angle( drag_dir )
927 guideA[0] = guideA[1] =
SEG( dragged.
A, dragged.
A + dir_prev.
ToVector() );
937 if( dir_next.
Angle( drag_dir )
944 guideB[0] = guideB[1] =
SEG( dragged.
B, dragged.
B + dir_next.
ToVector() );
947 SEG s_current( target, target + drag_dir.
ToVector() );
949 int best_len = INT_MAX;
952 for(
int i = 0; i < 2; i++ )
954 for(
int j = 0; j < 2; j++ )
964 SEG s1( s_prev.
A, *ip1 );
965 SEG s2( *ip1, *ip2 );
966 SEG s3( *ip2, s_next.
B );
976 else if( ( ip = s3.
Intersect( s_prev ) ) )
996 if( np.
Length() < best_len )
1006 else if( aIndex == 0 )
1049 s->SetRank( aRank );
1056 int min_rank = INT_MAX;
1061 min_rank = std::min( min_rank, item->Rank() );
1068 int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
1083 int lastLink = std::max( 0,
static_cast<int>(
m_links.size() ) - 1 );
1091 firstLink = linkIdx;
1093 if( i < 0 || i >= aEnd - 1 || linkIdx >= lastLink )
1102 wxASSERT( lastLink >= firstLink );
1108 wxASSERT(
m_links.size() < INT_MAX );
1109 wxASSERT(
static_cast<int>(
m_links.size() ) >= ( lastLink - firstLink ) );
1118 m_links.resize( lastLink - firstLink + 1 );
1155 bool areaDefined =
false;
1158 int i_end_self = -1, i_end_other = -1;
1168 int n = std::min( np_self, np_other );
1170 for(
int i = 0; i < n; i++ )
1195 for(
int i = 0; i < n; i++ )
1202 i_end_self = np_self - 1 - i;
1203 i_end_other = np_other - 1 - i;
1211 if( i_end_self < 0 )
1212 i_end_self = np_self - 1;
1214 if( i_end_other < 0 )
1215 i_end_other = np_other - 1;
1217 for(
int i = i_start; i <= i_end_self; i++ )
1220 for(
int i = i_start; i <= i_end_other; i++ )
1235 for(
const auto seg :
m_links )
1253 std::stringstream ss;
std::optional< BOX2I > OPT_BOX2I
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Represent route directions & corner angles in a 45-degree metric.
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
const DIRECTION_45 Left() const
Return the direction on the left side of this (i.e.
const VECTOR2I ToVector() const
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
const DIRECTION_45 Right() const
Return the direction on the right side of this (i.e.
virtual const std::string Format() const
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
virtual void Unmark(int aMarker=-1) const override
void dragSegment45(const VECTOR2I &aP, int aIndex)
const VECTOR2I & CPoint(int aIdx) const
virtual void Mark(int aMarker) const override
void ClipVertexRange(int aStart, int aEnd)
Return the number of corners of angles specified by mask aAngles.
int CountCorners(int aAngles) const
ITEM * m_blockingObstacle
For mark obstacle mode.
const SHAPE_LINE_CHAIN & CLine() const
void SetRank(int aRank) override
OPT_BOX2I ChangedArea(const LINE *aOther) const
bool m_hasVia
Optional via at the end point.
LINE()
Makes an empty line.
bool HasLockedSegments() const
SHAPE_LINE_CHAIN & Line()
virtual LINE * Clone() const override
Return a deep copy of the item.
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
void dragCorner45(const VECTOR2I &aP, int aIndex)
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
LINE & operator=(const LINE &aOther)
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
VECTOR2I snapToNeighbourSegments(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
void DragSegment(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
VECTOR2I snapDraggedCorner(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
virtual int Marker() const override
int m_snapThreshhold
Width to smooth out jagged segments.
bool CompareGeometry(const LINE &aOther)
Reverse the point/vertex order.
SHAPE_LINE_CHAIN m_line
The actual shape of the line.
void AppendVia(const VIA &aVia)
bool Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculate a line tightly wrapping a convex hull of an obstacle object (aObstacle).
int Width() const
Return true if the line is geometrically identical as line aOther.
int Rank() const override
void dragCornerFree(const VECTOR2I &aP, int aIndex)
void copyLinks(const LINK_HOLDER *aParent)
< Copy m_links from the line aParent.
bool IsLinked() const
Check if the segment aLink is a part of the line.
Keep the router "world" - i.e.
std::optional< OBSTACLE > OPT_OBSTACLE
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr, bool aUseClearanceEpsilon=true)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
virtual const std::string Format() const override
SEGMENT * Clone() const override
Return a deep copy of the item.
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
const VECTOR2I & Pos() const
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...
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
int Length() const
Return the length (this).
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
bool Contains(const SEG &aSeg) 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.
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
bool IsPtOnArc(size_t aPtIndex) const
int Width() const
Get the current width of the segments in the chain.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
virtual const VECTOR2I GetPoint(int aIndex) const override
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
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.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
void Clear()
Remove all points from the line chain.
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.
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
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.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
void Insert(size_t aVertex, const VECTOR2I &aP)
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
virtual const std::string Format(bool aCplusPlus=true) const override
Push and Shove diff pair dimensions (gap) settings dialog.
static void extendBox(BOX2I &aBox, bool &aDefined, const VECTOR2I &aP)
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
static int areNeighbours(int x, int y, int max=0)
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
SHAPE_LINE_CHAIN dragCornerInternal(const SHAPE_LINE_CHAIN &aOrigin, const VECTOR2I &aP)
@ OUTSIDE
Text appears outside the dimension line (default)
static std::pair< bool, SHAPE_POLY_SET::VERTEX_INDEX > findVertex(SHAPE_POLY_SET &aPolySet, const EDIT_POINT &aPoint)
std::optional< VECTOR2I > OPT_VECTOR2I
double EuclideanNorm(const VECTOR2I &vector)