40 m_line( aOther.m_line ),
41 m_width( aOther.m_width ),
42 m_snapThreshhold( aOther.m_snapThreshhold )
122 s->Unmark( aMarker );
134 marker |= s->Marker();
178 if( x > 0 && x - 1 == y )
181 if( x < max - 1 && x + 1 == y )
187#ifdef TOM_EXTRA_DEBUG
200 const auto pFirst = line.
CPoint(0);
211 enum VERTEX_TYPE { INSIDE = 0,
OUTSIDE, ON_EDGE };
224 std::vector<VERTEX*> neighbours;
230 bool visited =
false;
239 std::vector<VERTEX> vts;
243 for( VERTEX& v : vts )
254 if(
auto isect = pnew.SelfIntersecting() )
256 if( isect->p != pnew.CPoint( -1 ) )
258 pnew.Split( isect->p );
263 for(
auto& ip : ips )
265 if( pnew.Find( ip.p, 1 ) < 0)
270 if( hnew.
Find( ip.p, 1 ) < 0 )
276 for(
int i = 0; i < pnew.PointCount(); i++ )
278 auto p = pnew.CPoint(i);
284 int idx = hnew.
Find( p );
292 #ifdef TOM_EXTRA_DEBUG
293 for(
auto& ip : ips )
295 printf(
"Chk: %d %d\n", pnew.Find( ip.p ), hnew.
Find(ip.p) );
304 vts.reserve( 2 * ( hnew.
PointCount() + pnew.PointCount() ) );
307 for(
int i = 0; i < pnew.PointCount(); i++ )
313 #ifdef TOM_EXTRA_DEBUG
314 printf(
"pnew %d inside %d onedge %d\n", i, !!inside, !!onEdge );
322 v.type = inside && !onEdge ? INSIDE : onEdge ? ON_EDGE :
OUTSIDE;
326 #ifdef TOM_EXTRA_DEBUG
332 for(
int i = 0; i < pnew.PointCount() - 1; i++ )
334 vts[i].neighbours.push_back( &vts[ i+1 ] );
338 for(
int i = 1; i < pnew.PointCount() ; i++ )
340 vts[i].neighbours.push_back( &vts[ i-1 ] );
346 auto hp = hnew.
CPoint( i );
374 vc->neighbours.push_back(vnext);
382 int lastDst = INT_MAX;
385#ifdef TOM_EXTRA_DEBUG
388 if( v.indexh < 0 && v.type == ON_EDGE )
392 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 );
396 VERTEX* v = &vts[0], *v_prev =
nullptr;
399 int iterLimit = 1000;
402 while( v->indexp != ( pnew.PointCount() - 1 ) )
418#ifdef TOM_EXTRA_DEBUG
419 printf(
"---\nvisit ip %d ih %d type %d outs %d neig %d\n", v->indexp, v->indexh, v->type, out.
PointCount(), v->neighbours.size() );
423 VERTEX* v_next =
nullptr;
430 VERTEX* v_next_fallback =
nullptr;
431 for(
auto vn : v->neighbours )
433 if(
areNeighbours( vn->indexp , v->indexp, pnew.PointCount() ) &&
441 else if( vn != v_prev )
442 v_next_fallback = vn;
447 v_next = v_next_fallback;
452 #ifdef TOM_EXTRA_DEBUG
453 printf(
"FAIL VN fallback %p\n", v_next_fallback );
459 else if( v->type == ON_EDGE )
462 for( VERTEX* vn : v->neighbours )
464#ifdef TOM_EXTRA_DEBUG
465 printf(
"- OUT scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
468 if( vn->type ==
OUTSIDE && !vn->visited )
478 for( VERTEX* vn : v->neighbours )
480 #ifdef TOM_EXTRA_DEBUG
481 printf(
"- scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
483 if( vn->type == ON_EDGE && !vn->isHull &&
485 ( vn->indexh == ( ( v->indexh + 1 ) % hnew.
PointCount() ) ) )
497#ifdef TOM_EXTRA_DEBUG
498 printf(
"still no v_next\n");
500 for( VERTEX* vn : v->neighbours )
502 if( vn->type == ON_EDGE )
504 if( vn->indexh == ( ( v->indexh + 1 ) % hnew.
PointCount() ) )
521#ifdef TOM_EXTRA_DEBUG
522 printf(
"v_next %p\n", v_next);
528 if( inLast && v_next )
530 int d = ( v_next->pos -
CPoint( -1 ) ).SquaredEuclideanNorm();
579 const int IterationLimit = 5;
583 for( i = 0; i < IterationLimit; i++ )
590 VECTOR2I collisionPoint = obs->m_ipFirst;
612 if( i == IterationLimit )
622 std::optional<SHAPE_LINE_CHAIN> picked;
651 for(
int j = 0; j < 2; j++ )
655 if( paths[j].SegmentCount() < 1 )
658 assert( dirCount <
int(
sizeof( dirs ) /
sizeof( dirs[0] ) ) );
660 dirs[dirCount] =
DIRECTION_45( paths[j].CSegment( 0 ) );
664 for(
int j = 0; j < dirCount; j++ )
666 if( dirs[j] == d_start )
676 for(
int j = 0; j < dirCount; j++ )
678 if( dirs[j].IsObtuse( d_prev ) )
692 path.Append( *picked );
724 path.Append( path_rev );
728 path.SetWidth( width );
735 ssize_t idx =
static_cast<ssize_t
>( aIndex );
745 else if( ( idx == numpts - 1 ) || ( idx < numpts - 1 && !
m_line.
IsArcSegment( idx ) ) )
752 wxASSERT_MSG(
false, wxT(
"Attempt to dragCornerFree in the middle of an arc!" ) );
762 wxCHECK_RET( aIndex >= 0, wxT(
"Negative index passed to LINE::DragCorner" ) );
789 int s_start = std::max( aIndex - 2, 0 );
790 int s_end = std::min( aIndex + 2, aPath.
SegmentCount() - 1 );
793 int best_dist = INT_MAX;
799 for( i = s_start; i <= s_end; i++ )
803 for( j = s_start; j < i; j++ )
833 int snap_d[2] = { -1, -1 };
859 int minDist = INT_MAX;
861 for(
int i = 0; i < 2; i++ )
863 if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <=
m_snapThreshhold )
880 SEG guideA[2], guideB[2];
890 if( index == 0 ||
path.IsPtOnArc( index ) )
892 path.Insert( index > 0 ? index + 1 : 0,
path.CPoint( index ) );
896 if( index ==
path.SegmentCount() - 1 )
898 path.Insert(
path.PointCount() - 1,
path.CPoint( -1 ) );
900 else if(
path.IsPtOnArc( index + 1 ) )
902 path.Insert( index + 1,
path.CPoint( index + 1 ) );
905 SEG dragged =
path.CSegment( index );
908 SEG s_prev =
path.CSegment( index - 1 );
909 SEG s_next =
path.CSegment( index + 1 );
914 if( dir_prev == drag_dir )
916 dir_prev = dir_prev.
Left();
917 path.Insert( index,
path.CPoint( index ) );
922 dir_prev = drag_dir.
Left();
925 if( dir_next == drag_dir )
927 dir_next = dir_next.
Right();
928 path.Insert( index + 1,
path.CPoint( index + 1 ) );
932 dir_next = drag_dir.
Right();
935 s_prev =
path.CSegment( index - 1 );
936 s_next =
path.CSegment( index + 1 );
937 dragged =
path.CSegment( index );
946 if( dir_prev.
Angle( drag_dir )
953 guideA[0] = guideA[1] =
SEG( dragged.
A, dragged.
A + dir_prev.
ToVector() );
963 if( dir_next.
Angle( drag_dir )
970 guideB[0] = guideB[1] =
SEG( dragged.
B, dragged.
B + dir_next.
ToVector() );
973 SEG s_current( target, target + drag_dir.
ToVector() );
975 int best_len = INT_MAX;
978 for(
int i = 0; i < 2; i++ )
980 for(
int j = 0; j < 2; j++ )
990 SEG s1( s_prev.
A, *ip1 );
991 SEG s2( *ip1, *ip2 );
992 SEG s3( *ip2, s_next.
B );
1002 else if( ( ip = s3.
Intersect( s_prev ) ) )
1022 if( np.
Length() < best_len )
1032 else if( aIndex == 0 )
1075 s->SetRank( aRank );
1082 int min_rank = INT_MAX;
1087 min_rank = std::min( min_rank, item->Rank() );
1094 int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
1109 int lastLink = std::max( 0,
static_cast<int>(
m_links.size() ) - 1 );
1117 firstLink = linkIdx;
1119 if( i < 0 || i >= aEnd - 1 || linkIdx >= lastLink )
1128 wxASSERT( lastLink >= firstLink );
1134 wxASSERT(
m_links.size() < INT_MAX );
1135 wxASSERT(
static_cast<int>(
m_links.size() ) >= ( lastLink - firstLink ) );
1144 m_links.resize( lastLink - firstLink + 1 );
1181 bool areaDefined =
false;
1184 int i_end_self = -1, i_end_other = -1;
1194 int n = std::min( np_self, np_other );
1196 for(
int i = 0; i < n; i++ )
1221 for(
int i = 0; i < n; i++ )
1228 i_end_self = np_self - 1 - i;
1229 i_end_other = np_other - 1 - i;
1237 if( i_end_self < 0 )
1238 i_end_self = np_self - 1;
1240 if( i_end_other < 0 )
1241 i_end_other = np_other - 1;
1243 for(
int i = i_start; i <= i_end_self; i++ )
1246 for(
int i = i_start; i <= i_end_other; i++ )
1261 for(
const auto seg :
m_links )
1288 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
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, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS())
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
void SetOwner(const ITEM_OWNER *aOwner)
Set the node that owns this item.
const ITEM_OWNER * m_owner
bool BelongsTo(const ITEM_OWNER *aNode) const
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
VIA * Clone() const override
Return a deep copy of the item.
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)