有一个很好的方法来解决这个问题就是用向量叉乘。定义二维向量叉乘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页的文章“三条线在三维空间中的相交”。在三维空间中，通常的情况是直线是倾斜的(既不平行也不相交)，在这种情况下，该方法给出了两条直线最接近的点。

以下是对加文回答的改进。马普的解决方案也类似，但都没有推迟分割。

这实际上也是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，这是浮点数学的一个限制。

只是想提一下，一个很好的解释和明确的解决方案可以在数字食谱系列中找到。我有这本书的第三版，答案在1117页21.4节。另一种不同命名的解决方案可以在玛丽娜·加夫里洛娃(Marina Gavrilova)的论文中找到。在我看来，她的解决办法要简单一些。

我的实现如下:

bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
   return (x >= x0) && (x <= x1);
}

bool NuGeometry::FindIntersection(const double& x0, const double& y0, 
     const double& x1, const double& y1,
     const double& a0, const double& b0, 
     const double& a1, const double& b1, 
     double& xy, double& ab) {
   // four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
   // returned values xy and ab are the fractional distance along xy and ab
   // and are only defined when the result is true

   bool partial = false;
   double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
   if (denom == 0) {
      xy = -1;
      ab = -1;
   } else {
      xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
      partial = NuGeometry::IsBetween(0, xy, 1);
      if (partial) {
         // no point calculating this unless xy is between 0 & 1
         ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom; 
      }
   }
   if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
      ab = 1-ab;
      xy = 1-xy;
      return true;
   }  else return false;
}

人们似乎对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;
            }
        }
    }
};

问题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相同的逻辑。

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

矢量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 第二页