求两线段交点

本文主要是介绍求两线段交点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

来源于力扣上的一道题目：面试题 16.03. 交点
给定两条线段（表示为起点start = $x_1,y_1)$ 和终点end = $x_2,y_2)$ ，如果它们有交点，请计算其交点，没有交点则返回空值。
要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

解析

现在假设两条线段的四个点分别为 $x_1,y_1)，(x_2,y_2)，(x_3,y_3)，(x_4,y_4)$ ，交点为 $x_{inter},y_{inter})$
可能的情况无非以下几种，相交、平行不共线、共线不相交、共线相交

平行判定

$\frac{y_2-y_1}{x_2-x_1} = \frac{y_4-y_3}{x_4-x_3}$
为了避免出现斜率为0的情况，使用乘法。
$y_2-y_1)*(x_4-x_3)=(x_2-x_1)*(y_4-y_3)$

相交（不平行）

用高中学过的参数方程来表示两条直线
$\left\{ \begin{aligned} x & = x_1+t_1*(x_2-x_1) \\ y & = y_1+t_1*(y_2-y_1) \\ \end{aligned} \right.$
$\left\{ \begin{aligned} x & = x_3+t_2*(x_4-x_3) \\ y & = y_3+t_2*(y_4-y_3) \\ \end{aligned} \right.$

如果求交点，则直接令其联立，求解出 $t_1,t_2$ ，解得：
$t_1 = \frac {(x_3-x_1)(y_4-y_3)-(y_3-y_1)(x_4-x_3)}{(x_2-x_1)(y_4-y_3)-(x_4-x_3)(y_2-y_1)} \quad t_1 \in[0,1]$
$t_2 = \frac {(x_1-x_3)(y_2-y_1)+(y_3-y_1)(x_2-x_1)}{(x_4-x_3)(y_2-y_1)-(x_2-x_1)(y_4-y_3)} \quad t_2 \in[0,1]$
假如最后求出来的 $t_1,t_2$ 在范围内的话，那交点为：
$\left\{ \begin{aligned} x_{inter} & = x_1+t_1*(x_2-x_1) \\ y_{inter} & = y_1+t_1*(y_2-y_1) \\ \end{aligned} \right.$

平行

下面讨论平行的情况：

共线判定

$x_3,y_3)$ 是否在 $x_1,y_1)，(x_2,y_2)$ 的直线上
$\frac{y_k-y_1}{x_k-x_1} = \frac{y_2-y_1}{x_2-x_1}$
为了避免出现斜率为0的情况，使用乘法。
$y_k-y_1)*(x_2-x_1)=(y_2-y_1)*(x_k-x_1)$

// 判断一点(xk,yk)在直线(x1,y1)(x2,y2)上bool commonLine(int x1,int y1,int x2,int y2,int xk,int yk){return (yk-y1)*(x2-x1)==(y2-y1)*(xk-x1);}

平行且共线

判断是否有交点，如果有交点，且最优的交点一定是端点中的一个，下面就来判断已知平行且共线的情况下，判断两线段是否相交

// 已知(x1,y1)(x2,y2)(xk,yk)共线的情况下，判断(xk,yk)是否在(x1,y1)(x2,y2)线段上
bool inside(int x1,int y1,int x2,int y2,int xk,int yk){return (xk>=min(x1,x2)&&xk<=max(x1,x2)&&yk>=min(y1,y2)&&yk<=max(y1,y2));
}

依次去判断

(x3,y3)是否在(x1,y1)(x2,y2)线段中？
(x4,y4)是否在(x1,y1)(x2,y2)线段中？
(x1,y1)是否在(x3,y3)(x4,y4)线段中？
(x2,y2)是否在(x3,y3)(x4,y4)线段中？
如果在的话，端点便是当前的最优交点，然后去更新结果。

平行不共线

无交点

实现

class Solution {
public:// 判断一点(xk,yk)在直线(x1,y1)(x2,y2)上bool commonLine(int x1,int y1,int x2,int y2,int xk,int yk){return (yk-y1)*(x2-x1)==(y2-y1)*(xk-x1);}// 已知(x1,y1)(x2,y2)(xk,yk)共线的情况下，判断(xk,yk)是否在(x1,y1)(x2,y2)线段上bool inside(int x1,int y1,int x2,int y2,int xk,int yk){return (xk>=min(x1,x2)&&xk<=max(x1,x2)&&yk>=min(y1,y2)&&yk<=max(y1,y2));}// 更新交点，使其最优void update(vector<double>&ans,double xk,double yk){if(ans.size()==0){ans.resize(2);ans[0] = xk; ans[1] = yk;}else if(ans[0]>xk||(xk==ans[0]&&yk<ans[1])){ans[0] = xk; ans[1] = yk;}}vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {vector<double> ans;// if(start1.empty()||start2.empty()||end1.empty()||end2.empty()) return ans;int x1 = start1[0],y1 = start1[1], x2 = end1[0], y2 = end1[1];int x3 = start2[0],y3 = start2[1], x4 = end2[0], y4 = end2[1];// 判断两直线是否平行if((y2-y1)*(x4-x3)==(x2-x1)*(y4-y3)){// 两直线共线if(commonLine(x1,y1,x2,y2,x3,y3)){if(inside(x1,y1,x2,y2,x3,y3))update(ans,(double)x3,(double)y3);if(inside(x1,y1,x2,y2,x4,y4))update(ans,(double)x4,(double)y4);if(inside(x3,y3,x4,y4,x1,y1))update(ans,(double)x1,(double)y1);if(inside(x3,y3,x4,y4,x2,y2))update(ans,(double)x2,(double)y2);}}else {double t1 = (double)((x3-x1)*(y4-y3)-(y3-y1)*(x4-x3))/((x2-x1)*(y4-y3)-(x4-x3)*(y2-y1));double t2 = (double)((x1-x3)*(y2-y1)+(y3-y1)*(x2-x1))/((x4-x3)*(y2-y1)-(x2-x1)*(y4-y3));if(t1>=0&&t1<=1.0&&t2>=0&&t2<=1.0){if(ans.size()==0) ans.resize(2);ans[0] = (double)(x1+t1*(x2-x1));ans[1] = double(y1+t1*(y2-y1));}}return ans;}
};