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 )
181 const auto pFirst = line.
CPoint(0);
192 enum VERTEX_TYPE { INSIDE = 0,
OUTSIDE, ON_EDGE };
205 std::vector<VERTEX*> neighbours;
211 bool visited =
false;
220 std::vector<VERTEX> vts;
224 for( VERTEX& v : vts )
235 if(
auto isect = pnew.SelfIntersecting() )
237 if( isect->p != pnew.CPoint( -1 ) )
239 pnew.Split( isect->p );
244 for(
auto& ip : ips )
246 if( pnew.Find( ip.p, 1 ) < 0)
251 if( hnew.
Find( ip.p, 1 ) < 0 )
257 for(
int i = 0; i < pnew.PointCount(); i++ )
259 auto p = pnew.CPoint(i);
265 int idx = hnew.
Find( p );
273 #ifdef TOM_EXTRA_DEBUG 274 for(
auto& ip : ips )
276 printf(
"Chk: %d %d\n", pnew.Find( ip.p ), hnew.
Find(ip.p) );
285 vts.reserve( 2 * ( hnew.
PointCount() + pnew.PointCount() ) );
288 for(
int i = 0; i < pnew.PointCount(); i++ )
294 #ifdef TOM_EXTRA_DEBUG 295 printf(
"pnew %d inside %d onedge %d\n", i, !!inside, !!onEdge );
303 v.type = inside && !onEdge ? INSIDE : onEdge ? ON_EDGE :
OUTSIDE;
307 #ifdef TOM_EXTRA_DEBUG 313 for(
int i = 0; i < pnew.PointCount() - 1; i++ )
315 vts[i].neighbours.push_back( &vts[ i+1 ] );
319 for(
int i = 1; i < pnew.PointCount() ; i++ )
321 vts[i].neighbours.push_back( &vts[ i-1 ] );
327 auto hp = hnew.
CPoint( i );
355 vc->neighbours.push_back(vnext);
363 int lastDst = INT_MAX;
366 #ifdef TOM_EXTRA_DEBUG 369 if( v.indexh < 0 && v.type == ON_EDGE )
373 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 );
377 VERTEX* v = &vts[0], *v_prev =
nullptr;
380 int iterLimit = 1000;
383 while( v->indexp != ( pnew.PointCount() - 1 ) )
399 #ifdef TOM_EXTRA_DEBUG 400 printf(
"---\nvisit ip %d ih %d type %d outs %d neig %d\n", v->indexp, v->indexh, v->type, out.
PointCount(), v->neighbours.size() );
404 VERTEX* v_next =
nullptr;
411 VERTEX* v_next_fallback =
nullptr;
412 for(
auto vn : v->neighbours )
414 if(
areNeighbours( vn->indexp , v->indexp, pnew.PointCount() ) &&
422 else if( vn != v_prev )
423 v_next_fallback = vn;
428 v_next = v_next_fallback;
433 #ifdef TOM_EXTRA_DEBUG 434 printf(
"FAIL VN fallback %p\n", v_next_fallback );
440 else if( v->type == ON_EDGE )
443 for( VERTEX* vn : v->neighbours )
445 #ifdef TOM_EXTRA_DEBUG 446 printf(
"- OUT scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
449 if( vn->type ==
OUTSIDE && !vn->visited )
459 for( VERTEX* vn : v->neighbours )
461 #ifdef TOM_EXTRA_DEBUG 462 printf(
"- scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
464 if( vn->type == ON_EDGE && !vn->isHull &&
466 ( vn->indexh == ( ( v->indexh + 1 ) % hnew.
PointCount() ) ) )
478 for( VERTEX* vn : v->neighbours )
480 if( vn->type == ON_EDGE )
482 if( vn->indexh == ( ( v->indexh + 1 ) % hnew.
PointCount() ) )
493 if( inLast && v_next )
495 int d = ( v_next->pos -
CPoint( -1 ) ).SquaredEuclideanNorm();
549 double angle = 180.0 / M_PI *
550 atan2( (
double) s.
B.
y - (
double) s.
A.
y,
551 (
double) s.
B.
x - (
double) s.
A.
x );
556 double angle_a = fabs( fmod(
angle, 45.0 ) );
558 if( angle_a > 1.0 && angle_a < 44.0 )
568 const int IterationLimit = 5;
572 for( i = 0; i < IterationLimit; i++ )
579 VECTOR2I collisionPoint = obs->m_ipFirst;
601 if( i == IterationLimit )
640 for(
int j = 0; j < 2; j++ )
642 paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
644 if( paths[j].SegmentCount() < 1 )
647 assert( dirCount <
int(
sizeof( dirs ) /
sizeof( dirs[0] ) ) );
649 dirs[dirCount] =
DIRECTION_45( paths[j].CSegment( 0 ) );
653 for(
int j = 0; j < dirCount; j++ )
655 if( dirs[j] == d_start )
665 for(
int j = 0; j < dirCount; j++ )
667 if( dirs[j].IsObtuse( d_prev ) )
681 path.Append( *picked );
713 path.Append( path_rev );
717 path.SetWidth( width );
724 ssize_t idx = static_cast<ssize_t>( aIndex );
734 else if( ( idx == numpts - 1 ) || ( idx < numpts - 1 && !
m_line.
IsArcSegment( idx ) ) )
741 wxASSERT_MSG(
false, wxT(
"Attempt to dragCornerFree in the middle of an arc!" ) );
751 wxCHECK_RET( aIndex >= 0, wxT(
"Negative index passed to LINE::DragCorner" ) );
778 int s_start = std::max( aIndex - 2, 0 );
779 int s_end = std::min( aIndex + 2, aPath.
SegmentCount() - 1 );
782 int best_dist = INT_MAX;
788 for( i = s_start; i <= s_end; i++ )
792 for( j = s_start; j < i; j++ )
822 int snap_d[2] = { -1, -1 };
848 int minDist = INT_MAX;
850 for(
int i = 0; i < 2; i++ )
852 if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <=
m_snapThreshhold )
869 SEG guideA[2], guideB[2];
879 if( index == 0 ||
path.IsPtOnArc( index ) )
881 path.Insert( index > 0 ? index + 1 : 0,
path.CPoint( index ) );
885 if( index ==
path.SegmentCount() - 1 )
887 path.Insert(
path.PointCount() - 1,
path.CPoint( -1 ) );
889 else if(
path.IsPtOnArc( index + 1 ) )
891 path.Insert( index + 1,
path.CPoint( index + 1 ) );
894 SEG dragged =
path.CSegment( index );
897 SEG s_prev =
path.CSegment( index - 1 );
898 SEG s_next =
path.CSegment( index + 1 );
903 if( dir_prev == drag_dir )
905 dir_prev = dir_prev.
Left();
906 path.Insert( index,
path.CPoint( index ) );
911 dir_prev = drag_dir.
Left();
914 if( dir_next == drag_dir )
916 dir_next = dir_next.
Right();
917 path.Insert( index + 1,
path.CPoint( index + 1 ) );
921 dir_next = drag_dir.
Right();
924 s_prev =
path.CSegment( index - 1 );
925 s_next =
path.CSegment( index + 1 );
926 dragged =
path.CSegment( index );
935 if( dir_prev.
Angle( drag_dir )
942 guideA[0] = guideA[1] =
SEG( dragged.
A, dragged.
A + dir_prev.
ToVector() );
952 if( dir_next.
Angle( drag_dir )
959 guideB[0] = guideB[1] =
SEG( dragged.
B, dragged.
B + dir_next.
ToVector() );
962 SEG s_current( target, target + drag_dir.
ToVector() );
964 int best_len = INT_MAX;
967 for(
int i = 0; i < 2; i++ )
969 for(
int j = 0; j < 2; j++ )
971 OPT_VECTOR2I ip1 = s_current.IntersectLines( guideA[i] );
972 OPT_VECTOR2I ip2 = s_current.IntersectLines( guideB[j] );
979 SEG s1( s_prev.
A, *ip1 );
980 SEG s2( *ip1, *ip2 );
981 SEG s3( *ip2, s_next.
B );
991 else if( ( ip = s3.
Intersect( s_prev ) ) )
1011 if( np.
Length() < best_len )
1021 else if( aIndex == 0 )
1064 s->SetRank( aRank );
1071 int min_rank = INT_MAX;
1076 min_rank = std::min( min_rank, s->Rank() );
1082 int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
1097 int lastLink = std::max( 0, static_cast<int>(
m_links.size() ) - 1 );
1105 firstLink = linkIdx;
1107 if( i < 0 || i >= aEnd - 1 || linkIdx >= lastLink )
1116 wxASSERT( lastLink >= firstLink );
1122 wxASSERT(
m_links.size() < INT_MAX );
1123 wxASSERT( static_cast<int>(
m_links.size() ) >= ( lastLink - firstLink ) );
1132 m_links.resize( lastLink - firstLink + 1 );
1169 bool areaDefined =
false;
1172 int i_end_self = -1, i_end_other = -1;
1182 int n = std::min( np_self, np_other );
1184 for(
int i = 0; i < n; i++ )
1186 const VECTOR2I p1 =
self.CPoint( i );
1193 SEG s =
self.CSegment( i );
1209 for(
int i = 0; i < n; i++ )
1211 const VECTOR2I p1 =
self.CPoint( np_self - 1 - i );
1216 i_end_self = np_self - 1 - i;
1217 i_end_other = np_other - 1 - i;
1225 if( i_end_self < 0 )
1226 i_end_self = np_self - 1;
1228 if( i_end_other < 0 )
1229 i_end_other = np_other - 1;
1231 for(
int i = i_start; i <= i_end_self; i++ )
1234 for(
int i = i_start; i <= i_end_other; i++ )
1249 for(
const auto seg :
m_links )
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
int Length() const
Return the length (this).
const SHAPE_LINE_CHAIN & CLine() const
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
long long int Length() const
Return length of the line chain in Euclidean metric.
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
std::vector< INTERSECTION > INTERSECTIONS
Keep the router "world" - i.e.
OPT_BOX2I ChangedArea(const LINE *aOther) const
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).
LINE()
Makes an empty line.
void DragSegment(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
LINE & operator=(const LINE &aOther)
void copyLinks(const LINK_HOLDER *aParent)
< Copy m_links from the line aParent.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
VECTOR2I snapToNeighbourSegments(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
bool Is45Degree() const
Print out all linked segments.
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
int Rank() const override
const VECTOR2I ToVector() const
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 Width() const
Get the current width of the segments in the chain.
SEGMENT * Clone() const override
Return a deep copy of the item.
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.
const DIRECTION_45 Left() const
Return the direction on the left side of this (i.e.
Text appears outside the dimension line (default)
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
void AppendVia(const VIA &aVia)
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
static std::pair< bool, SHAPE_POLY_SET::VERTEX_INDEX > findVertex(SHAPE_POLY_SET &aPolySet, const EDIT_POINT &aPoint)
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...
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
const DIRECTION_45 Right() const
Return the direction on the right side of this (i.e.
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & Pos() const
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
ITEM * m_blockingObstacle
For mark obstacle mode.
SHAPE_LINE_CHAIN dragCornerInternal(const SHAPE_LINE_CHAIN &aOrigin, const VECTOR2I &aP)
const VECTOR2I & CPoint(int aIdx) const
SHAPE_LINE_CHAIN m_line
The actual shape of the line.
void Insert(size_t aVertex, const VECTOR2I &aP)
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
bool IsArcSegment(size_t aSegment) const
OPT< VECTOR2I > OPT_VECTOR2I
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
Represent route directions & corner angles in a 45-degree metric.
bool IsLinked() const
Check if the segment aLink is a part of the line.
void ClipVertexRange(int aStart, int aEnd)
Return the number of corners of angles specified by mask aAngles.
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.
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
bool m_hasVia
Optional via at the end point.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
void SetRank(int aRank) override
int SegmentCount() const
Return the number of segments in this line chain.
virtual const VECTOR2I GetPoint(int aIndex) const override
bool IsPtOnArc(size_t aPtIndex) const
void dragCorner45(const VECTOR2I &aP, int aIndex)
static int areNeighbours(int x, int y, int max=0)
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
SHAPE_LINE_CHAIN & Line()
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
virtual int Marker() const override
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int m_snapThreshhold
Width to smooth out jagged segments.
static void extendBox(BOX2I &aBox, bool &aDefined, const VECTOR2I &aP)
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
int Width() const
Return true if the line is geometrically identical as line aOther.
void Clear()
Remove all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
void dragSegment45(const VECTOR2I &aP, int aIndex)
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
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.
bool CompareGeometry(const LINE &aOther)
Reverse the point/vertex order.
Push and Shove diff pair dimensions (gap) settings dialog.
void dragCornerFree(const VECTOR2I &aP, int aIndex)
virtual LINE * Clone() const override
Return a deep copy of the item.
virtual void Unmark(int aMarker=-1) const override
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
bool HasLockedSegments() const
int CountCorners(int aAngles) const
virtual void Mark(int aMarker) const override
bool Contains(const SEG &aSeg) const
VECTOR2I snapDraggedCorner(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const