我如何确定两条直线是否相交,如果相交,在x,y点处?
当前回答
人们似乎对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;
}
}
}
};
其他回答
问题可以简化成这样一个问题:从A到B和从C到D的两条直线相交吗?然后你可以问它四次(在直线和矩形的四条边之间)。
这是做这个的矢量数学。假设A到B的直线就是问题中的直线C到D的直线是其中一条矩形直线。我的表示法是Ax是A的x坐标Cy是c的y坐标“*”表示点积,例如A*B = Ax*Bx + Ay*By。
E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )
h是键。如果h在0和1之间,两条线相交,否则不相交。如果F*P为零,当然不能进行计算,但在这种情况下,直线是平行的,因此只有在明显的情况下才相交。
交点是C + F*h。
更多的乐趣:
如果h恰好等于0或1,两条直线的端点相交。你可以认为这是一个“交集”,也可以认为不是。
具体来说,h是直线长度乘以多少才能恰好与另一条直线相交。
因此,如果h<0,这意味着矩形线在给定直线的“后面”(“方向”是“从A到B”),如果h>1,矩形线在给定直线的“前面”。
推导:
A和C是指向直线起点的向量;E和F是由A和C端点组成的直线。
对于平面上任意两条不平行线,必须恰好有一对标量g和h,使得这个方程成立:
A + E*g = C + F*h
为什么?因为两条不平行线必须相交,这意味着你可以将这两条线按一定比例缩放并相互接触。
(起初,这看起来像一个有两个未知数的方程!但当你考虑到这是一个二维矢量方程时,它就不是,这意味着这是一对x和y的方程)
我们必须消去其中一个变量。一个简单的方法是使E项为零。要做到这一点,用一个向量对方程两边做点积这个向量与E点乘到0,我把上面的向量称为P,我做了E的明显变换。
你现在有:
A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h
这是基于Gareth Ree的回答。它还返回线段重叠的情况。用c++编写的V是一个简单的向量类。其中二维中两个向量的外积返回一个标量。通过了学校自动测试系统的测试。
//Required input point must be colinear with the line
bool on_segment(const V& p, const LineSegment& l)
{
//If a point is on the line, the sum of the vectors formed by the point to the line endpoints must be equal
V va = p - l.pa;
V vb = p - l.pb;
R ma = va.magnitude();
R mb = vb.magnitude();
R ml = (l.pb - l.pa).magnitude();
R s = ma + mb;
bool r = s <= ml + epsilon;
return r;
}
//Compute using vector math
// Returns 0 points if the lines do not intersect or overlap
// Returns 1 point if the lines intersect
// Returns 2 points if the lines overlap, contain the points where overlapping start starts and stop
std::vector<V> intersect(const LineSegment& la, const LineSegment& lb)
{
std::vector<V> r;
//http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
V oa, ob, da, db; //Origin and direction vectors
R sa, sb; //Scalar values
oa = la.pa;
da = la.pb - la.pa;
ob = lb.pa;
db = lb.pb - lb.pa;
if (da.cross(db) == 0 && (ob - oa).cross(da) == 0) //If colinear
{
if (on_segment(lb.pa, la) && on_segment(lb.pb, la))
{
r.push_back(lb.pa);
r.push_back(lb.pb);
dprintf("colinear, overlapping\n");
return r;
}
if (on_segment(la.pa, lb) && on_segment(la.pb, lb))
{
r.push_back(la.pa);
r.push_back(la.pb);
dprintf("colinear, overlapping\n");
return r;
}
if (on_segment(la.pa, lb))
r.push_back(la.pa);
if (on_segment(la.pb, lb))
r.push_back(la.pb);
if (on_segment(lb.pa, la))
r.push_back(lb.pa);
if (on_segment(lb.pb, la))
r.push_back(lb.pb);
if (r.size() == 0)
dprintf("colinear, non-overlapping\n");
else
dprintf("colinear, overlapping\n");
return r;
}
if (da.cross(db) == 0 && (ob - oa).cross(da) != 0)
{
dprintf("parallel non-intersecting\n");
return r;
}
//Math trick db cross db == 0, which is a single scalar in 2D.
//Crossing both sides with vector db gives:
sa = (ob - oa).cross(db) / da.cross(db);
//Crossing both sides with vector da gives
sb = (oa - ob).cross(da) / db.cross(da);
if (0 <= sa && sa <= 1 && 0 <= sb && sb <= 1)
{
dprintf("intersecting\n");
r.push_back(oa + da * sa);
return r;
}
dprintf("non-intersecting, non-parallel, non-colinear, non-overlapping\n");
return r;
}
我从《多视图几何》这本书里读到了这些算法
以下文本使用
'作为转置符号
*作为点积
当用作算子时,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是平行的。
有一个很好的方法来解决这个问题就是用向量叉乘。定义二维向量叉乘v × w为vx wy−vy wx。
假设这两条线段从p到p + r,从q到q + s。那么第一行上的任意点都可以表示为p + t r(对于标量参数t),第二行上的任意点可以表示为q + u s(对于标量参数u)。
如果t和u满足以下条件,两条直线相交:
P + t r = q + u s
两边叉乘s,得到
(p + r) × s = (q + u s) × s
由于s × s = 0,这意味着
T (r × s) = (q−p) × s
因此,求解t:
T = (q−p) × s / (r × s)
同样地,我们可以解出u:
(p + r) × r = (q + u s) × r U (s × r) = (p−q) × r U = (p−q) × r / (s × r)
为了减少计算步骤,可以方便地将其重写为以下形式(记住s × r =−r × s):
U = q−p × r / (r × s)
现在有四种情况:
If r × s = 0 and (q − p) × r = 0, then the two lines are collinear. In this case, express the endpoints of the second segment (q and q + s) in terms of the equation of the first line segment (p + t r): t0 = (q − p) · r / (r · r) t1 = (q + s − p) · r / (r · r) = t0 + s · r / (r · r) If the interval between t0 and t1 intersects the interval [0, 1] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint. Note that if s and r point in opposite directions, then s · r < 0 and so the interval to be checked is [t1, t0] rather than [t0, t1]. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s. Otherwise, the two line segments are not parallel but do not intersect.
来源:该方法是3D线相交算法的2维专门化,来自Ronald Goldman发表在Graphics Gems,第304页的文章“三条线在三维空间中的相交”。在三维空间中,通常的情况是直线是倾斜的(既不平行也不相交),在这种情况下,该方法给出了两条直线最接近的点。
FWIW,下面的函数(在C中)既检测线的交点,又确定交点。这是基于Andre LeMothe的“Tricks of the Windows Game Programming Gurus”中的一个算法。这与其他答案(例如Gareth的答案)中的一些算法并没有什么不同。然后LeMothe使用克莱默法则(不要问我)来解这些方程。
我可以证明它在我的小行星克隆中起作用,并且似乎正确地处理了Elemental, Dan和Wodzu在其他答案中描述的边缘情况。它也可能比KingNestor发布的代码快,因为它都是乘法和除法,没有平方根!
我想这里有一些除以0的可能性,尽管在我的例子中这不是问题。很容易修改以避免崩溃。
// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines
// intersect the intersection point may be stored in the floats i_x and i_y.
char 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 s1_x, s1_y, s2_x, s2_y;
s1_x = p1_x - p0_x; s1_y = p1_y - p0_y;
s2_x = p3_x - p2_x; s2_y = p3_y - p2_y;
float s, t;
s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
// Collision detected
if (i_x != NULL)
*i_x = p0_x + (t * s1_x);
if (i_y != NULL)
*i_y = p0_y + (t * s1_y);
return 1;
}
return 0; // No collision
}
顺便说一句,我必须说,在LeMothe的书中,虽然他显然得到了正确的算法,但他展示的具体示例插入了错误的数字,并且计算错误。例如:
(4 * (4-1) + 12 * (7-1))/(17 * 4 + 12 * 10) = 844/0.88 = 0.44
这让我困惑了好几个小时。:(