我如何确定两条直线是否相交,如果相交,在x,y点处?
当前回答
C和Objective-C
基于Gareth Rees的回答
const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};
AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
return (AGKLine){start, end};
}
double AGKLineLength(AGKLine l)
{
return CGPointLengthBetween_AGK(l.start, l.end);
}
BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
// http://stackoverflow.com/a/565282/202451
CGPoint p = l1.start;
CGPoint q = l2.start;
CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);
double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;
if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
{
if(out_pointOfIntersection != NULL)
{
*out_pointOfIntersection = CGPointZero;
}
return NO;
}
else
{
if(out_pointOfIntersection != NULL)
{
CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
*out_pointOfIntersection = i;
}
return YES;
}
}
CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}
CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}
CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
return (CGPoint){p1.x * factor, p1.y * factor};
}
许多函数和结构都是私有的,但是你应该很容易就能知道发生了什么。 这是公开的在这个回购https://github.com/hfossli/AGGeometryKit/
其他回答
如果矩形的每条边都是一条线段,并且用户绘制的部分也是一条线段,那么您只需检查用户绘制的线段是否与四条边线段相交。这应该是一个相当简单的练习,给定每个段的起点和终点。
我已经尝试实现上述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
有一个很好的方法来解决这个问题就是用向量叉乘。定义二维向量叉乘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页的文章“三条线在三维空间中的相交”。在三维空间中,通常的情况是直线是倾斜的(既不平行也不相交),在这种情况下,该方法给出了两条直线最接近的点。
问题可以简化成这样一个问题:从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
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