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

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

许多答案把所有的计算都打包成一个函数。如果您需要计算直线斜率、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
  };
}

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

这是基于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;
}

一个c++程序，用于检查两条给定线段是否相交

#include <iostream>
using namespace std;

struct Point
{
    int x;
    int y;
};

// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;

    return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    // See 10th slides from following link for derivation of the formula
    // http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear

    return (val > 0)? 1: 2; // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases
}

// Driver program to test above functions
int main()
{
    struct Point p1 = {1, 1}, q1 = {10, 1};
    struct Point p2 = {1, 2}, q2 = {10, 2};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    return 0;
}

我从《多视图几何》这本书里读到了这些算法

以下文本使用

'作为转置符号

*作为点积

当用作算子时，X作为叉乘

1. 线的定义

点x_vec = (x, y)'在直线ax + by + c = 0上

标记L = (a, b, c)'，点为(x, y, 1)'为齐次坐标

直线方程可以写成

(x, y, 1)(a, b, c)' = 0或x' * L = 0

2. 直线交点

我们有两条直线L1=(a1, b1, c1)'， L2=(a2, b2, c2)'

假设x是一个点，一个向量，x = L1 x L2 (L1叉乘L2)。

注意，x始终是一个二维点，如果你对(L1xL2)是一个三元素向量，x是一个二维坐标感到困惑，请阅读齐次坐标。

根据三重积，我们知道

L1 * (L1 x L2) = 0, L2 * (L1 x L2) = 0，因为L1,L2共平面

我们用向量x代替L1*x，那么L1*x=0, L2*x=0，这意味着x在L1和L2上，x是交点。

注意，这里x是齐次坐标，如果x的最后一个元素是零，这意味着L1和L2是平行的。