交点 shuitang

题目

面试题 16.03. 交点

难度困难46

给定两条线段(表示为起点start = {X1, Y1}和终点end = {X2, Y2}),如果它们有交点,请计算其交点,没有交点则返回空值。

要求浮点型误差不超过10^-6。若有多个交点(线段重叠)则返回 X 值最小的点,X 坐标相同则返回 Y 值最小的点。

示例 1:

输入:
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
输出: {0.5, 0}

示例 2:

输入:
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
输出: {1, 1}

示例 3:

输入:
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
输出: {},两条线段没有交点

提示:

  • 坐标绝对值不会超过 2^7
  • 输入的坐标均是有效的二维坐标

解法

额……这题就是一个数学题,其实思路不难,但是真的细节处理真是让人怀疑人生!!!下面将用向量的方法来解这个题。

首先过两点 $X_1$ 和 $X_2$ ($X_{1,2} \in R^2$) 的线段可以表示为:

\[X_1 + \lambda (X_2-X_1), \lambda \in [0,1]\]

根据题意设出两条线段的向量方程: \(line_1: X_1 + \lambda (X_2-X_1), \lambda \in [0,1] \\ line_2: X_1' + \mu (X_2'-X_1'), \mu \in [0,1]\)

求交点,则向量相等,解方程: \(X_1 + \lambda (X_2-X_1) = X_1' + \mu (X_2'-X_1') => \\ \lambda(X_2-X_1)-\mu(X_2'-X_1') = X_1' - X_1\)

设$ X_1 = [x_1,y_1] , X_2 = [x_2,y_2]; X_1’ = [x_1’,y_1’], X_2’ = [x_2’,y_2’]$; 上式方程可变为:

\[\left[ \begin{matrix} x_2-x_1 & x_1'-x_2' \\ y_2-y_1 & y_1'-y_2' \end{matrix} \right] \left[\begin{matrix} \lambda \\ \mu \end{matrix} \right] = \left[ \begin{matrix} x_1' - x_1 \\ y_1' - y_1 \end{matrix} \right] \tag{1}\]

然后分别用 $A,B,C,D,E,F$ 替代上面的数为:

\[\left[ \begin{matrix} A & B \\ C & D \end{matrix} \right] \left[\begin{matrix} \lambda \\ \mu \end{matrix} \right] = \left[ \begin{matrix} E \\ F \end{matrix} \right] \tag{2}\]

所以只需要求解上述的线性方程组,记左边矩阵为 M .

首先,考 $det(M)$行列式不为0的情况,不为0,直接利用克拉默法则求出 $\lambda$ 和 $\mu$ 的值,然后判断是否在 [0,1] 内。如果是,那么最终返回 $X_1 + \lambda (X_2 - X_1)$.

然而,麻烦是考虑行列式为0的情形。这种情形是相当麻烦的:

  • 没有解的情形,即直线平行
  • 有可能有无数解的情形,即直线重合

无解的情形

这种情况,还是比较好判断,如果行列式为0,则若对应系数比不相等则没有解,所以判断条件为

AF != CE, 则无解。

有可能有无数解的情形

这种情况下需要 AF == CE,然后再判断线段上是否相交。其实这种情况下,如果有解,解肯定是在4个点上。思路就是给这些点排个序,看看某个线段的端点是否在另一线段的里面。

代码如下:

class Solution {
public:
    bool bigger(vector<int>& a, vector<int>& b){
        //定义的用于比较点大小的函数
        return a[0]>b[0] || a[0] == b[0] && a[1] > b[1];
    }

    vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
        double A = end1[0] - start1[0];
        double B = -(end2[0] - start2[0]);
        double C = end1[1] - start1[1];
        double D = -(end2[1] - start2[1]);
        double E = start2[0] - start1[0];
        double F = start2[1] - start1[1];
        //计算行列式值
        double det = A*D - B*C;
        
        vector<double> ans;
        
        //处理行列式为0的情况
        if(abs(det)<1e-7){
            if(abs(A*F-C*E)<1e-7){ //有可能有无数解的情形
                if(bigger(start1,end1)){
                    swap(start1,end1);
                }
                if(bigger(start2,end2)){
                    swap(start2,end2);
                }
                if(bigger(start1,end2) || bigger(start2,end1)) return ans;
                if(bigger(start1,start2)){
                    ans.push_back(double(start1[0]));
                    ans.push_back(double(start1[1]));
                    return ans;
                }else if(bigger(start2,start1)){
                    ans.push_back(double(start2[0]));
                    ans.push_back(double(start2[1]));
                    return ans;
                }
            }else return ans; //平行

        }
        //行列式不为0的情形
        double lamb = (D*E - B*F)/det;
        double mu = (A*F - C*E)/det;
        //cout<<lamb<<" "<<mu<<endl;
        if(lamb >=0 && lamb <= 1 && mu >=0 && mu <= 1){
            ans.push_back(lamb*A + start1[0]);
            ans.push_back(lamb*C + start1[1]);
            return ans;
        }else{ 
            return ans;
        }
    }
};