我如何确定两条直线是否相交，如果相交，在x,y点处?
当前回答
下面是一个基本的c#线段实现，并有相应的交点检测代码。它需要一个名为Vector2f的2D向量/点结构，不过你可以用任何其他具有X/Y属性的类型替换它。如果更适合你的需要，你也可以用double替换float。
这段代码用于我的. net物理库Boing。
public struct LineSegment2f
{
public Vector2f From { get; }
public Vector2f To { get; }
public LineSegment2f(Vector2f @from, Vector2f to)
{
From = @from;
To = to;
}
public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);
/// <summary>
/// Attempt to intersect two line segments.
/// </summary>
/// <remarks>
/// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
/// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
/// </remarks>
/// <param name="other">The line to attempt intersection of this line with.</param>
/// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
/// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
{
var p = From;
var q = other.From;
var r = Delta;
var s = other.Delta;
// t = (q − p) × s / (r × s)
// u = (q − p) × r / (r × s)
var denom = Fake2DCross(r, s);
if (denom == 0)
{
// lines are collinear or parallel
t = float.NaN;
u = float.NaN;
intersectionPoint = default(Vector2f);
return false;
}
var tNumer = Fake2DCross(q - p, s);
var uNumer = Fake2DCross(q - p, r);
t = tNumer / denom;
u = uNumer / denom;
if (t < 0 || t > 1 || u < 0 || u > 1)
{
// line segments do not intersect within their ranges
intersectionPoint = default(Vector2f);
return false;
}
intersectionPoint = p + r * t;
return true;
}
private static float Fake2DCross(Vector2f a, Vector2f b)
{
return a.X * b.Y - a.Y * b.X;
}
}
其他回答
我试过其中一些答案，但它们对我不起作用(对不起伙计们);在网上搜索之后，我找到了这个。
对他的代码做了一点修改，我现在有了这个函数，它将返回交点，如果没有找到交点，它将返回- 1,1。
Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
'// Determines the intersection point of the line segment defined by points A and B
'// with the line segment defined by points C and D.
'//
'// Returns YES if the intersection point was found, and stores that point in X,Y.
'// Returns NO if there is no determinable intersection point, in which case X,Y will
'// be unmodified.
Dim distAB, theCos, theSin, newX, ABpos As Double
'// Fail if either line segment is zero-length.
If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)
'// Fail if the segments share an end-point.
If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)
'// (1) Translate the system so that point A is on the origin.
bx -= ax
by -= ay
cx -= ax
cy -= ay
dx -= ax
dy -= ay
'// Discover the length of segment A-B.
distAB = Math.Sqrt(bx * bx + by * by)
'// (2) Rotate the system so that point B is on the positive X axis.
theCos = bx / distAB
theSin = by / distAB
newX = cx * theCos + cy * theSin
cy = cy * theCos - cx * theSin
cx = newX
newX = dx * theCos + dy * theSin
dy = dy * theCos - dx * theSin
dx = newX
'// Fail if segment C-D doesn't cross line A-B.
If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)
'// (3) Discover the position of the intersection point along line A-B.
ABpos = dx + (cx - dx) * dy / (dy - cy)
'// Fail if segment C-D crosses line A-B outside of segment A-B.
If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)
'// (4) Apply the discovered position to line A-B in the original coordinate system.
'*X=Ax+ABpos*theCos
'*Y=Ay+ABpos*theSin
'// Success.
Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function
下面是一个基本的c#线段实现，并有相应的交点检测代码。它需要一个名为Vector2f的2D向量/点结构，不过你可以用任何其他具有X/Y属性的类型替换它。如果更适合你的需要，你也可以用double替换float。
这段代码用于我的. net物理库Boing。
public struct LineSegment2f
{
public Vector2f From { get; }
public Vector2f To { get; }
public LineSegment2f(Vector2f @from, Vector2f to)
{
From = @from;
To = to;
}
public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);
/// <summary>
/// Attempt to intersect two line segments.
/// </summary>
/// <remarks>
/// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
/// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
/// </remarks>
/// <param name="other">The line to attempt intersection of this line with.</param>
/// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
/// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
{
var p = From;
var q = other.From;
var r = Delta;
var s = other.Delta;
// t = (q − p) × s / (r × s)
// u = (q − p) × r / (r × s)
var denom = Fake2DCross(r, s);
if (denom == 0)
{
// lines are collinear or parallel
t = float.NaN;
u = float.NaN;
intersectionPoint = default(Vector2f);
return false;
}
var tNumer = Fake2DCross(q - p, s);
var uNumer = Fake2DCross(q - p, r);
t = tNumer / denom;
u = uNumer / denom;
if (t < 0 || t > 1 || u < 0 || u > 1)
{
// line segments do not intersect within their ranges
intersectionPoint = default(Vector2f);
return false;
}
intersectionPoint = p + r * t;
return true;
}
private static float Fake2DCross(Vector2f a, Vector2f b)
{
return a.X * b.Y - a.Y * b.X;
}
}
我已经尝试实现上述Jason所描述的算法;不幸的是，虽然在调试数学工作，我发现许多情况下，它不起作用。
例如，考虑点A(10,10) B(20,20) C(10,1) D(1,10) h=。5然而，通过检查可以清楚地看到，这些部分彼此一点也不接近。
将其绘制成图可以清楚地看出，0 < h < 1条件仅表明如果存在截距点，则截距点将位于CD上，而不告诉我们该点是否位于AB上。 为了确保有一个交叉点，你必须对变量g进行对称计算，拦截的要求是: 0 < g < 1 AND 0 < h < 1
以下是对加文回答的改进。马普的解决方案也类似，但都没有推迟分割。
这实际上也是Gareth Rees的答案的一个实际应用，因为向量积在2D中的等价是补点积，这段代码用了其中的三个。切换到3D并使用叉积，在最后插入s和t，结果是3D中直线之间的两个最近点。 不管怎样，2D解:
int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
s10_x = p1_x - p0_x;
s10_y = p1_y - p0_y;
s32_x = p3_x - p2_x;
s32_y = p3_y - p2_y;
denom = s10_x * s32_y - s32_x * s10_y;
if (denom == 0)
return 0; // Collinear
bool denomPositive = denom > 0;
s02_x = p0_x - p2_x;
s02_y = p0_y - p2_y;
s_numer = s10_x * s02_y - s10_y * s02_x;
if ((s_numer < 0) == denomPositive)
return 0; // No collision
t_numer = s32_x * s02_y - s32_y * s02_x;
if ((t_numer < 0) == denomPositive)
return 0; // No collision
if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
return 0; // No collision
// Collision detected
t = t_numer / denom;
if (i_x != NULL)
*i_x = p0_x + (t * s10_x);
if (i_y != NULL)
*i_y = p0_y + (t * s10_y);
return 1;
}
基本上，它将除法延迟到最后一刻，并将大多数测试移动到某些计算完成之前，从而增加了早期退出。最后，它还避免了直线平行时的除零情况。
您可能还想考虑使用ε检验，而不是与零比较。非常接近平行的线会产生稍微偏离的结果。这不是一个bug，这是浮点数学的一个限制。
如果矩形的每条边都是一条线段，并且用户绘制的部分也是一条线段，那么您只需检查用户绘制的线段是否与四条边线段相交。这应该是一个相当简单的练习，给定每个段的起点和终点。
