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

以下文本使用

'作为转置符号

*作为点积

当用作算子时，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是平行的。

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

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

根据t3chb0t的答案:

int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
   //L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
   int d;
   d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
   if(!d)
       return 0;
   p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
   p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
   return 1;
}

int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
    return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;

}

int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
    if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
        return 0;

    return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}

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

只是想提一下，一个很好的解释和明确的解决方案可以在数字食谱系列中找到。我有这本书的第三版，答案在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;
}