曾经在这里被接受的答案是不正确的(它已经被不接受了，所以万岁!)它不能正确地消除所有非交点。简单地说，它可能有效，但也可能失败，特别是在0和1被认为对h有效的情况下。

考虑以下情况:

直线(4,1)-(5,1)和(0,0)-(0,2)

这两条垂线显然不重叠。

= (4,1) B =(5、1) C = (0, 0) D = (0, 2) E = (1) - (4,1) = (1,0) F = (0, 2) - (0, 0) = (0, 2) P = (0, 1) h =((4,1) -(0, 0))点(0,1)/((0,2)点(0,1))= 0

根据上面的答案，这两条线段在端点处相遇(值为0和1)。该端点为:

(0, 0) + (0, 2) * 0 = (0, 0)

So, apparently the two line segments meet at (0,0), which is on line CD, but not on line AB. So what is going wrong? The answer is that the values of 0 and 1 are not valid and only sometimes HAPPEN to correctly predict endpoint intersection. When the extension of one line (but not the other) would meet the line segment, the algorithm predicts an intersection of line segments, but this is not correct. I imagine that by testing starting with AB vs CD and then also testing with CD vs AB, this problem would be eliminated. Only if both fall between 0 and 1 inclusively can they be said to intersect.

如果你必须预测端点，我建议使用向量叉乘法。

-Dan

上面有很多解决方案，但我认为下面的解决方案很简单，很容易理解。

矢量AB和矢量CD相交当且仅当

端点a和b在线段CD的两边。 端点c和d在线段AB的对边。

更具体地说，a和b在线段CD的对面当且仅当两个三元组中有一个是逆时针顺序的。

Intersect(a, b, c, d)
 if CCW(a, c, d) == CCW(b, c, d)
    return false;
 else if CCW(a, b, c) == CCW(a, b, d)
    return false;
 else
    return true;

这里的CCW代表逆时针，根据点的方向返回真/假。

来源:http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf 第二页

我已经尝试实现上述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

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

这让我困惑了好几个小时。：(

我将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;
}

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/