问题可以简化成这样一个问题:从A到B和从C到D的两条直线相交吗?然后你可以问它四次(在直线和矩形的四条边之间)。

这是做这个的矢量数学。假设A到B的直线就是问题中的直线C到D的直线是其中一条矩形直线。我的表示法是Ax是A的x坐标Cy是c的y坐标“*”表示点积，例如A*B = Ax*Bx + Ay*By。

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

h是键。如果h在0和1之间，两条线相交，否则不相交。如果F*P为零，当然不能进行计算，但在这种情况下，直线是平行的，因此只有在明显的情况下才相交。

交点是C + F*h。

更多的乐趣:

如果h恰好等于0或1，两条直线的端点相交。你可以认为这是一个“交集”，也可以认为不是。

具体来说，h是直线长度乘以多少才能恰好与另一条直线相交。

因此，如果h<0，这意味着矩形线在给定直线的“后面”(“方向”是“从A到B”)，如果h>1，矩形线在给定直线的“前面”。

推导:

A和C是指向直线起点的向量;E和F是由A和C端点组成的直线。

对于平面上任意两条不平行线，必须恰好有一对标量g和h，使得这个方程成立:

A + E*g = C + F*h

为什么?因为两条不平行线必须相交，这意味着你可以将这两条线按一定比例缩放并相互接触。

(起初，这看起来像一个有两个未知数的方程!但当你考虑到这是一个二维矢量方程时，它就不是，这意味着这是一对x和y的方程)

我们必须消去其中一个变量。一个简单的方法是使E项为零。要做到这一点，用一个向量对方程两边做点积这个向量与E点乘到0，我把上面的向量称为P，我做了E的明显变换。

你现在有:

A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h

如果矩形的每条边都是一条线段，并且用户绘制的部分也是一条线段，那么您只需检查用户绘制的线段是否与四条边线段相交。这应该是一个相当简单的练习，给定每个段的起点和终点。

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

基于@Gareth Rees的回答，Python版本:

import numpy as np

def np_perp( a ) :
    b = np.empty_like(a)
    b[0] = a[1]
    b[1] = -a[0]
    return b

def np_cross_product(a, b):
    return np.dot(a, np_perp(b))

def np_seg_intersect(a, b, considerCollinearOverlapAsIntersect = False):
    # https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282
    # http://www.codeproject.com/Tips/862988/Find-the-intersection-point-of-two-line-segments
    r = a[1] - a[0]
    s = b[1] - b[0]
    v = b[0] - a[0]
    num = np_cross_product(v, r)
    denom = np_cross_product(r, s)
    # If r x s = 0 and (q - p) x r = 0, then the two lines are collinear.
    if np.isclose(denom, 0) and np.isclose(num, 0):
        # 1. If either  0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s
        # then the two lines are overlapping,
        if(considerCollinearOverlapAsIntersect):
            vDotR = np.dot(v, r)
            aDotS = np.dot(-v, s)
            if (0 <= vDotR  and vDotR <= np.dot(r,r)) or (0 <= aDotS  and aDotS <= np.dot(s,s)):
                return True
        # 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s
        # then the two lines are collinear but disjoint.
        # No need to implement this expression, as it follows from the expression above.
        return None
    if np.isclose(denom, 0) and not np.isclose(num, 0):
        # Parallel and non intersecting
        return None
    u = num / denom
    t = np_cross_product(v, s) / denom
    if u >= 0 and u <= 1 and t >= 0 and t <= 1:
        res = b[0] + (s*u)
        return res
    # Otherwise, the two line segments are not parallel but do not intersect.
    return None

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

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