40 m_line( aOther.m_line ),
41 m_width( aOther.m_width ),
42 m_snapThreshhold( aOther.m_snapThreshhold )
122 s->Unmark( aMarker );
133 marker |= s->Marker();
176 if( x > 0 && x - 1 == y )
179 if( x < max - 1 && x + 1 == y )
185#ifdef TOM_EXTRA_DEBUG
222 std::vector<VERTEX*> neighbours;
228 bool visited =
false;
237 std::vector<VERTEX> vts;
252 if(
const std::optional<SHAPE_LINE_CHAIN::INTERSECTION> isect = pnew.SelfIntersecting() )
254 if( isect->p != pnew.CPoint( -1 ) )
255 pnew.Split( isect->p );
261 if( pnew.Find( ip.p, 1 ) < 0)
264 if( hnew.
Find( ip.p, 1 ) < 0 )
268 for(
int i = 0; i < pnew.PointCount(); i++ )
270 const VECTOR2I& p = pnew.CPoint( i );
276 int idx = hnew.
Find( p );
282 #ifdef TOM_EXTRA_DEBUG
283 for(
auto& ip : ips )
285 printf(
"Chk: %d %d\n", pnew.Find( ip.p ), hnew.
Find(ip.p) );
294 vts.reserve( 2 * ( hnew.
PointCount() + pnew.PointCount() ) );
297 for(
int i = 0; i < pnew.PointCount(); i++ )
303 #ifdef TOM_EXTRA_DEBUG
304 printf(
"pnew %d inside %d onedge %d\n", i, !!inside, !!onEdge );
312 v.type = inside && !onEdge ?
INSIDE : onEdge ? ON_EDGE :
OUTSIDE;
316 #ifdef TOM_EXTRA_DEBUG
322 for(
int i = 0; i < pnew.PointCount() - 1; i++ )
324 vts[i].neighbours.push_back( &vts[ i+1 ] );
328 for(
int i = 1; i < pnew.PointCount() ; i++ )
330 vts[i].neighbours.push_back( &vts[ i-1 ] );
364 vc->neighbours.push_back( vnext );
372 int lastDst = INT_MAX;
375#ifdef TOM_EXTRA_DEBUG
378 if( v.indexh < 0 && v.type == ON_EDGE )
381 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 );
389 int iterLimit = 1000;
392 while( v->indexp != ( pnew.PointCount() - 1 ) )
407#ifdef TOM_EXTRA_DEBUG
408 printf(
"---\nvisit ip %d ih %d type %d outs %d neig %d\n", v->indexp, v->indexh, v->type, out.
PointCount(), v->neighbours.size() );
419 VERTEX* v_next_fallback =
nullptr;
421 for(
VERTEX* vn : v->neighbours )
423 if(
areNeighbours( vn->indexp , v->indexp, pnew.PointCount() )
431 else if( vn != v_prev )
433 v_next_fallback = vn;
439 v_next = v_next_fallback;
444 #ifdef TOM_EXTRA_DEBUG
445 printf(
"FAIL VN fallback %p\n", v_next_fallback );
450 else if( v->type == ON_EDGE )
453 for(
VERTEX* vn : v->neighbours )
455#ifdef TOM_EXTRA_DEBUG
456 printf(
"- OUT scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
459 if( vn->type ==
OUTSIDE && !vn->visited )
469 for(
VERTEX* vn : v->neighbours )
471 #ifdef TOM_EXTRA_DEBUG
472 printf(
"- scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
474 if( vn->type == ON_EDGE && !vn->isHull &&
476 ( vn->indexh == ( ( v->indexh + 1 ) % hnew.
PointCount() ) ) )
488#ifdef TOM_EXTRA_DEBUG
489 printf(
"still no v_next\n");
491 for(
VERTEX* vn : v->neighbours )
493 if( vn->type == ON_EDGE )
495 if( vn->indexh == ( ( v->indexh + 1 ) % hnew.
PointCount() ) )
512#ifdef TOM_EXTRA_DEBUG
513 printf(
"v_next %p\n", v_next);
519 if( inLast && v_next )
521 int d = ( v_next->pos -
CPoint( -1 ) ).SquaredEuclideanNorm();
568 const int IterationLimit = 5;
572 for( i = 0; i < IterationLimit; i++ )
579 VECTOR2I collisionPoint = obs->m_ipFirst;
601 if( i == IterationLimit )
611 std::optional<SHAPE_LINE_CHAIN> picked;
641 for(
int j = 0; j < 2; j++ )
645 if( paths[j].SegmentCount() < 1 )
648 assert( dirCount <
int(
sizeof( dirs ) /
sizeof( dirs[0] ) ) );
650 dirs[dirCount] =
DIRECTION_45( paths[j].CSegment( 0 ) );
654 for(
int j = 0; j < dirCount; j++ )
656 if( dirs[j] == d_start )
666 for(
int j = 0; j < dirCount; j++ )
668 if( dirs[j].IsObtuse( d_prev ) )
682 path.Append( *picked );
718 path.Append( path_rev );
722 path.SetWidth( width );
729 ssize_t idx =
static_cast<ssize_t
>( aIndex );
739 else if( ( idx == numpts - 1 ) || ( idx < numpts - 1 && !
m_line.
IsArcSegment( idx ) ) )
746 wxASSERT_MSG(
false, wxT(
"Attempt to dragCornerFree in the middle of an arc!" ) );
756 wxCHECK_RET( aIndex >= 0, wxT(
"Negative index passed to LINE::DragCorner" ) );
783 int s_start = std::max( aIndex - 2, 0 );
784 int s_end = std::min( aIndex + 2, aPath.
SegmentCount() - 1 );
787 int best_dist = INT_MAX;
793 for( i = s_start; i <= s_end; i++ )
797 for( j = s_start; j < i; j++ )
808 int dist = ( *ip - aP ).EuclideanNorm();
827 int snap_d[2] = { -1, -1 };
853 int minDist = INT_MAX;
855 for(
int i = 0; i < 2; i++ )
857 if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <=
m_snapThreshhold )
874 SEG guideA[2], guideB[2];
884 if( index == 0 ||
path.IsPtOnArc( index ) )
886 path.Insert( index > 0 ? index + 1 : 0,
path.CPoint( index ) );
890 if( index ==
path.SegmentCount() - 1 )
892 path.Insert(
path.PointCount() - 1,
path.CPoint( -1 ) );
894 else if(
path.IsPtOnArc( index + 1 ) )
896 path.Insert( index + 1,
path.CPoint( index + 1 ) );
899 SEG dragged =
path.CSegment( index );
902 SEG s_prev =
path.CSegment( index - 1 );
903 SEG s_next =
path.CSegment( index + 1 );
908 if( dir_prev == drag_dir )
910 dir_prev = dir_prev.
Left();
911 path.Insert( index,
path.CPoint( index ) );
916 dir_prev = drag_dir.
Left();
919 if( dir_next == drag_dir )
921 dir_next = dir_next.
Right();
922 path.Insert( index + 1,
path.CPoint( index + 1 ) );
926 dir_next = drag_dir.
Right();
929 s_prev =
path.CSegment( index - 1 );
930 s_next =
path.CSegment( index + 1 );
931 dragged =
path.CSegment( index );
940 if( dir_prev.
Angle( drag_dir )
947 guideA[0] = guideA[1] =
SEG( dragged.
A, dragged.
A + dir_prev.
ToVector() );
957 if( dir_next.
Angle( drag_dir )
964 guideB[0] = guideB[1] =
SEG( dragged.
B, dragged.
B + dir_next.
ToVector() );
967 SEG s_current( target, target + drag_dir.
ToVector() );
969 int best_len = INT_MAX;
972 for(
int i = 0; i < 2; i++ )
974 for(
int j = 0; j < 2; j++ )
984 SEG s1( s_prev.
A, *ip1 );
985 SEG s2( *ip1, *ip2 );
986 SEG s3( *ip2, s_next.
B );
996 else if( ( ip = s3.
Intersect( s_prev ) ) )
1016 if( np.
Length() < best_len )
1026 else if( aIndex == 0 )
1069 s->SetRank( aRank );
1076 int min_rank = INT_MAX;
1081 min_rank = std::min( min_rank, item->Rank() );
1088 int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
1103 int lastLink = std::max( 0,
static_cast<int>(
m_links.size() ) - 1 );
1111 firstLink = linkIdx;
1113 if( i < 0 || i >= aEnd - 1 || linkIdx >= lastLink )
1122 wxASSERT( lastLink >= firstLink );
1128 wxASSERT(
m_links.size() < INT_MAX );
1129 wxASSERT(
static_cast<int>(
m_links.size() ) >= ( lastLink - firstLink ) );
1138 m_links.resize( lastLink - firstLink + 1 );
1175 bool areaDefined =
false;
1178 int i_end_self = -1, i_end_other = -1;
1188 int n = std::min( np_self, np_other );
1190 for(
int i = 0; i < n; i++ )
1215 for(
int i = 0; i < n; i++ )
1222 i_end_self = np_self - 1 - i;
1223 i_end_other = np_other - 1 - i;
1231 if( i_end_self < 0 )
1232 i_end_self = np_self - 1;
1234 if( i_end_other < 0 )
1235 i_end_other = np_other - 1;
1237 for(
int i = i_start; i <= i_end_self; i++ )
1240 for(
int i = i_start; i <= i_end_other; i++ )
1255 for(
const auto seg :
m_links )
1282 std::stringstream ss;
std::optional< BOX2I > OPT_BOX2I
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
constexpr 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
void SetNet(NET_HANDLE aNet)
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
VECTOR2I snapToNeighbourSegments(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
void ClipVertexRange(int aStart, int aEnd)
Return the number of corners of angles specified by mask aAngles.
const VECTOR2I & CPoint(int aIdx) const
OPT_BOX2I ChangedArea(const LINE *aOther) const
bool HasLockedSegments() const
int Rank() const override
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
virtual void Mark(int aMarker) const override
bool CompareGeometry(const LINE &aOther)
Reverse the point/vertex order.
ITEM * m_blockingObstacle
For mark obstacle mode.
const SHAPE_LINE_CHAIN & CLine() const
VECTOR2I snapDraggedCorner(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
LINE & operator=(const LINE &aOther)
void dragSegment45(const VECTOR2I &aP, int aIndex)
int CountCorners(int aAngles) const
void SetRank(int aRank) override
LINE()
Makes an empty line.
SHAPE_LINE_CHAIN & Line()
virtual int Marker() const override
void AppendVia(const VIA &aVia)
void dragCorner45(const VECTOR2I &aP, int aIndex)
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
virtual void Unmark(int aMarker=-1) const override
int m_snapThreshhold
Width to smooth out jagged segments.
SHAPE_LINE_CHAIN m_line
The actual shape of the line.
void DragSegment(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
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).
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
void dragCornerFree(const VECTOR2I &aP, int aIndex)
virtual LINE * Clone() const override
Return a deep copy of the item.
int Width() const
Return true if the line is geometrically identical as line aOther.
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.
std::vector< LINKED_ITEM * > m_links
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 PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
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.
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, bool aExact=false)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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.
int NextShape(int aPointIndex) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
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
Represent an intersection between two line segments.
VECTOR2< int32_t > VECTOR2I