我如何确定两条直线是否相交,如果相交,在x,y点处?
当前回答
我将Kris的答案移植到JavaScript。在尝试了许多不同的答案后,他给出了正确的观点。我以为我要疯了,因为我没有得到我需要的分数。
function getLineLineCollision(p0, p1, p2, p3) {
var s1, s2;
s1 = {x: p1.x - p0.x, y: p1.y - p0.y};
s2 = {x: p3.x - p2.x, y: p3.y - p2.y};
var s10_x = p1.x - p0.x;
var s10_y = p1.y - p0.y;
var s32_x = p3.x - p2.x;
var s32_y = p3.y - p2.y;
var denom = s10_x * s32_y - s32_x * s10_y;
if(denom == 0) {
return false;
}
var denom_positive = denom > 0;
var s02_x = p0.x - p2.x;
var s02_y = p0.y - p2.y;
var s_numer = s10_x * s02_y - s10_y * s02_x;
if((s_numer < 0) == denom_positive) {
return false;
}
var t_numer = s32_x * s02_y - s32_y * s02_x;
if((t_numer < 0) == denom_positive) {
return false;
}
if((s_numer > denom) == denom_positive || (t_numer > denom) == denom_positive) {
return false;
}
var t = t_numer / denom;
var p = {x: p0.x + (t * s10_x), y: p0.y + (t * s10_y)};
return p;
}
其他回答
这对我来说很有效。从这里拍的。
// 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;
}
}
如果矩形的每条边都是一条线段,并且用户绘制的部分也是一条线段,那么您只需检查用户绘制的线段是否与四条边线段相交。这应该是一个相当简单的练习,给定每个段的起点和终点。
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
这让我困惑了好几个小时。:(
许多答案把所有的计算都打包成一个函数。如果您需要计算直线斜率、y轴截距或x轴截距,以便在代码的其他地方使用,那么这些计算将是冗余的。我分离出了各自的函数,使用了明显的变量名,并注释了我的代码以使其更易于理解。我需要知道直线是否无限超出它们的端点,所以在JavaScript中:
http://jsfiddle.net/skibulk/evmqq00u/
var point_a = {x:0, y:10},
point_b = {x:12, y:12},
point_c = {x:10, y:0},
point_d = {x:0, y:0},
slope_ab = slope(point_a, point_b),
slope_bc = slope(point_b, point_c),
slope_cd = slope(point_c, point_d),
slope_da = slope(point_d, point_a),
yint_ab = y_intercept(point_a, slope_ab),
yint_bc = y_intercept(point_b, slope_bc),
yint_cd = y_intercept(point_c, slope_cd),
yint_da = y_intercept(point_d, slope_da),
xint_ab = x_intercept(point_a, slope_ab, yint_ab),
xint_bc = x_intercept(point_b, slope_bc, yint_bc),
xint_cd = x_intercept(point_c, slope_cd, yint_cd),
xint_da = x_intercept(point_d, slope_da, yint_da),
point_aa = intersect(slope_da, yint_da, xint_da, slope_ab, yint_ab, xint_ab),
point_bb = intersect(slope_ab, yint_ab, xint_ab, slope_bc, yint_bc, xint_bc),
point_cc = intersect(slope_bc, yint_bc, xint_bc, slope_cd, yint_cd, xint_cd),
point_dd = intersect(slope_cd, yint_cd, xint_cd, slope_da, yint_da, xint_da);
console.log(point_a, point_b, point_c, point_d);
console.log(slope_ab, slope_bc, slope_cd, slope_da);
console.log(yint_ab, yint_bc, yint_cd, yint_da);
console.log(xint_ab, xint_bc, xint_cd, xint_da);
console.log(point_aa, point_bb, point_cc, point_dd);
function slope(point_a, point_b) {
var i = (point_b.y - point_a.y) / (point_b.x - point_a.x);
if (i === -Infinity) return Infinity;
if (i === -0) return 0;
return i;
}
function y_intercept(point, slope) {
// Horizontal Line
if (slope == 0) return point.y;
// Vertical Line
if (slope == Infinity)
{
// THE Y-Axis
if (point.x == 0) return Infinity;
// No Intercept
return null;
}
// Angled Line
return point.y - (slope * point.x);
}
function x_intercept(point, slope, yint) {
// Vertical Line
if (slope == Infinity) return point.x;
// Horizontal Line
if (slope == 0)
{
// THE X-Axis
if (point.y == 0) return Infinity;
// No Intercept
return null;
}
// Angled Line
return -yint / slope;
}
// Intersection of two infinite lines
function intersect(slope_a, yint_a, xint_a, slope_b, yint_b, xint_b) {
if (slope_a == slope_b)
{
// Equal Lines
if (yint_a == yint_b && xint_a == xint_b) return Infinity;
// Parallel Lines
return null;
}
// First Line Vertical
if (slope_a == Infinity)
{
return {
x: xint_a,
y: (slope_b * xint_a) + yint_b
};
}
// Second Line Vertical
if (slope_b == Infinity)
{
return {
x: xint_b,
y: (slope_a * xint_b) + yint_a
};
}
// Not Equal, Not Parallel, Not Vertical
var i = (yint_b - yint_a) / (slope_a - slope_b);
return {
x: i,
y: (slope_a * i) + yint_a
};
}
以下是对加文回答的改进。马普的解决方案也类似,但都没有推迟分割。
这实际上也是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,这是浮点数学的一个限制。