我如何确定两条直线是否相交,如果相交,在x,y点处?
当前回答
根据t3chb0t的答案:
int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
//L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
int d;
d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
if(!d)
return 0;
p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
return 1;
}
int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;
}
int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
return 0;
return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}
其他回答
问题C:如何检测两条线段是否相交?
我也搜索过同样的话题,但我对答案并不满意。所以我写了一篇文章,非常详细地解释了如何检查两条线段是否与大量图像相交。这是完整的(并经过测试的)java代码。
以下是这篇文章,截取了最重要的部分:
检查线段a是否与线段b相交的算法如下所示:
什么是边界框?下面是两个线段的边界框:
如果两个边界框都有交点,则移动线段a,使其中一点在(0|0)处。现在你有了一条经过a定义的原点的直线,现在以同样的方式移动线段b,检查线段b的新点是否在直线a的不同两侧。如果是这样,则反过来检查。如果也是这样,线段相交。如果不相交,它们就不相交。
问题A:两条线段在哪里相交?
你知道两条线段a和b相交。如果你不知道,用我在C题中给你的工具检查一下。
现在你可以通过一些情况,并得到解决与七年级数学(见代码和交互示例)。
问题B:你如何检测两条线是否相交?
假设点A = (x1, y1)点B = (x2, y2) C = (x_3, y_3) D = (x_4, y_4) 第一行由AB定义(A != B),第二行由CD定义(C != D)。
function doLinesIntersect(AB, CD) {
if (x1 == x2) {
return !(x3 == x4 && x1 != x3);
} else if (x3 == x4) {
return true;
} else {
// Both lines are not parallel to the y-axis
m1 = (y1-y2)/(x1-x2);
m2 = (y3-y4)/(x3-x4);
return m1 != m2;
}
}
问题D:两条直线在哪里相交?
检查问题B,它们是否相交。
直线a和b由每条直线上的两个点定义。 你基本上可以用和问题A相同的逻辑。
问题可以简化成这样一个问题:从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
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
这让我困惑了好几个小时。:(
以下是对加文回答的改进。马普的解决方案也类似,但都没有推迟分割。
这实际上也是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,这是浮点数学的一个限制。
这是基于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;
}