我如何确定两条直线是否相交，如果相交，在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;
}
}
其他回答
这对我来说很有效。从这里拍的。
// calculates intersection and checks for parallel lines.
// also checks that the intersection point is actually on
// the line segment p1-p2
Point findIntersection(Point p1,Point p2,
Point p3,Point p4) {
float xD1,yD1,xD2,yD2,xD3,yD3;
float dot,deg,len1,len2;
float segmentLen1,segmentLen2;
float ua,ub,div;
// calculate differences
xD1=p2.x-p1.x;
xD2=p4.x-p3.x;
yD1=p2.y-p1.y;
yD2=p4.y-p3.y;
xD3=p1.x-p3.x;
yD3=p1.y-p3.y;
// calculate the lengths of the two lines
len1=sqrt(xD1*xD1+yD1*yD1);
len2=sqrt(xD2*xD2+yD2*yD2);
// calculate angle between the two lines.
dot=(xD1*xD2+yD1*yD2); // dot product
deg=dot/(len1*len2);
// if abs(angle)==1 then the lines are parallell,
// so no intersection is possible
if(abs(deg)==1) return null;
// find intersection Pt between two lines
Point pt=new Point(0,0);
div=yD2*xD1-xD2*yD1;
ua=(xD2*yD3-yD2*xD3)/div;
ub=(xD1*yD3-yD1*xD3)/div;
pt.x=p1.x+ua*xD1;
pt.y=p1.y+ua*yD1;
// calculate the combined length of the two segments
// between Pt-p1 and Pt-p2
xD1=pt.x-p1.x;
xD2=pt.x-p2.x;
yD1=pt.y-p1.y;
yD2=pt.y-p2.y;
segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);
// calculate the combined length of the two segments
// between Pt-p3 and Pt-p4
xD1=pt.x-p3.x;
xD2=pt.x-p4.x;
yD1=pt.y-p3.y;
yD2=pt.y-p4.y;
segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);
// if the lengths of both sets of segments are the same as
// the lenghts of the two lines the point is actually
// on the line segment.
// if the point isn’t on the line, return null
if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)
return null;
// return the valid intersection
return pt;
}
class Point{
float x,y;
Point(float x, float y){
this.x = x;
this.y = y;
}
void set(float x, float y){
this.x = x;
this.y = y;
}
}
iMalc回答的Python版本:
def find_intersection( p0, p1, p2, p3 ) :
s10_x = p1[0] - p0[0]
s10_y = p1[1] - p0[1]
s32_x = p3[0] - p2[0]
s32_y = p3[1] - p2[1]
denom = s10_x * s32_y - s32_x * s10_y
if denom == 0 : return None # collinear
denom_is_positive = denom > 0
s02_x = p0[0] - p2[0]
s02_y = p0[1] - p2[1]
s_numer = s10_x * s02_y - s10_y * s02_x
if (s_numer < 0) == denom_is_positive : return None # no collision
t_numer = s32_x * s02_y - s32_y * s02_x
if (t_numer < 0) == denom_is_positive : return None # no collision
if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision
# collision detected
t = t_numer / denom
intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]
return intersection_point
人们似乎对Gavin的答案很感兴趣，cortijon在评论中提出了一个javascript版本，iMalc提供了一个计算量略少的版本。一些人指出了各种代码建议的缺点，另一些人则评论了一些代码建议的效率。
iMalc通过Gavin的答案提供的算法是我目前在一个javascript项目中使用的算法，我只是想在这里提供一个清理过的版本，如果它可以帮助到任何人的话。
// Some variables for reuse, others may do this differently
var p0x, p1x, p2x, p3x, ix,
p0y, p1y, p2y, p3y, iy,
collisionDetected;
// do stuff, call other functions, set endpoints...
// note: for my purpose I use |t| < |d| as opposed to
// |t| <= |d| which is equivalent to 0 <= t < 1 rather than
// 0 <= t <= 1 as in Gavin's answer - results may vary
var lineSegmentIntersection = function(){
var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t;
dx1 = p1x - p0x; dy1 = p1y - p0y;
dx2 = p3x - p2x; dy2 = p3y - p2y;
dx3 = p0x - p2x; dy3 = p0y - p2y;
collisionDetected = 0;
d = dx1 * dy2 - dx2 * dy1;
if(d !== 0){
s = dx1 * dy3 - dx3 * dy1;
if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){
t = dx2 * dy3 - dx3 * dy2;
if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){
t = t / d;
collisionDetected = 1;
ix = p0x + t * dx1;
iy = p0y + t * dy1;
}
}
}
};
下面是一个基本的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;
}
}
我从《多视图几何》这本书里读到了这些算法
以下文本使用
'作为转置符号
*作为点积
当用作算子时，X作为叉乘
1. 线的定义
点x_vec = (x, y)'在直线ax + by + c = 0上
标记L = (a, b, c)'，点为(x, y, 1)'为齐次坐标
直线方程可以写成
(x, y, 1)(a, b, c)' = 0或x' * L = 0
2. 直线交点
我们有两条直线L1=(a1, b1, c1)'， L2=(a2, b2, c2)'
假设x是一个点，一个向量，x = L1 x L2 (L1叉乘L2)。
注意，x始终是一个二维点，如果你对(L1xL2)是一个三元素向量，x是一个二维坐标感到困惑，请阅读齐次坐标。
根据三重积，我们知道
L1 * (L1 x L2) = 0, L2 * (L1 x L2) = 0，因为L1,L2共平面
我们用向量x代替L1*x，那么L1*x=0, L2*x=0，这意味着x在L1和L2上，x是交点。
注意，这里x是齐次坐标，如果x的最后一个元素是零，这意味着L1和L2是平行的。
