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

曾经在这里被接受的答案是不正确的(它已经被不接受了，所以万岁!)它不能正确地消除所有非交点。简单地说，它可能有效，但也可能失败，特别是在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

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

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

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

我试过其中一些答案，但它们对我不起作用(对不起伙计们);在网上搜索之后，我找到了这个。

对他的代码做了一点修改，我现在有了这个函数，它将返回交点，如果没有找到交点，它将返回- 1,1。

    Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
    '//  Determines the intersection point of the line segment defined by points A and B
    '//  with the line segment defined by points C and D.
    '//
    '//  Returns YES if the intersection point was found, and stores that point in X,Y.
    '//  Returns NO if there is no determinable intersection point, in which case X,Y will
    '//  be unmodified.

    Dim distAB, theCos, theSin, newX, ABpos As Double

    '//  Fail if either line segment is zero-length.
    If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)

    '//  Fail if the segments share an end-point.
    If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)

    '//  (1) Translate the system so that point A is on the origin.
    bx -= ax
    by -= ay
    cx -= ax
    cy -= ay
    dx -= ax
    dy -= ay

    '//  Discover the length of segment A-B.
    distAB = Math.Sqrt(bx * bx + by * by)

    '//  (2) Rotate the system so that point B is on the positive X axis.
    theCos = bx / distAB
    theSin = by / distAB
    newX = cx * theCos + cy * theSin
    cy = cy * theCos - cx * theSin
    cx = newX
    newX = dx * theCos + dy * theSin
    dy = dy * theCos - dx * theSin
    dx = newX

    '//  Fail if segment C-D doesn't cross line A-B.
    If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)

    '//  (3) Discover the position of the intersection point along line A-B.
    ABpos = dx + (cx - dx) * dy / (dy - cy)

    '//  Fail if segment C-D crosses line A-B outside of segment A-B.
    If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)

    '//  (4) Apply the discovered position to line A-B in the original coordinate system.
    '*X=Ax+ABpos*theCos
    '*Y=Ay+ABpos*theSin

    '//  Success.
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function