CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目
面试题 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;
}
}
};