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
209 enum VERTEX_TYPE { INSIDE = 0,
OUTSIDE, ON_EDGE };
222 std::vector<VERTEX*> neighbours;
228 bool visited =
false;
237 std::vector<VERTEX> vts;
240 [&](
const VECTOR2I& pos ) -> VERTEX*
242 for( VERTEX& v : 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
376 for( VERTEX* &v: vts )
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 );
386 VERTEX* v_prev =
nullptr;
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() );
412 VERTEX* v_next =
nullptr;
419 VERTEX* v_next_fallback =
nullptr;
421 for( VERTEX* vn : v->neighbours )
423 if(
areNeighbours( vn->indexp , v->indexp, pnew.PointCount() )
424 && vn->type != INSIDE )
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() ) )
505 for( VERTEX &
vt : vts )
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++ )
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
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
void SetNet(NET_HANDLE aNet)
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 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.
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, bool aExact=false)
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
Represent an intersection between two line segments.
double EuclideanNorm(const VECTOR2I &vector)