求两线段交点

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

现在假设两条线段的四个点分别为 ( x 1 , y 1 ) ， ( x 2 , y 2 ) ， ( x 3 , y 3 ) ， ( x 4 , y 4 ) (x_1,y_1)，(x_2,y_2)，(x_3,y_3)，(x_4,y_4) (x1​,y1​)，(x2​,y2​)，(x3​,y3​)，(x4​,y4​)，交点为 ( x i n t e r , y i n t e r ) (x_{inter},y_{inter}) (xinter​,yinter​) 可能的情况无非以下几种，相交、平行不共线、共线不相交、共线相交

y 2 − y 1 x 2 − x 1 = y 4 − y 3 x 4 − x 3 \frac{y_2-y_1}{x_2-x_1} = \frac{y_4-y_3}{x_4-x_3} x2​−x1​y2​−y1​​=x4​−x3​y4​−y3​​ 为了避免出现斜率为0的情况，使用乘法。 ( y 2 − y 1 ) ∗ ( x 4 − x 3 ) = ( x 2 − x 1 ) ∗ ( y 4 − y 3 ) (y_2-y_1)*(x_4-x_3)=(x_2-x_1)*(y_4-y_3) (y2​−y1​)∗(x4​−x3​)=(x2​−x1​)∗(y4​−y3​)

用高中学过的参数方程来表示两条直线 { x = x 1 + t 1 ∗ ( x 2 − x 1 ) y = y 1 + t 1 ∗ ( y 2 − y 1 ) \left\{ \begin{aligned} x & = x_1+t_1*(x_2-x_1) \\ y & = y_1+t_1*(y_2-y_1) \\ \end{aligned} \right. {xy​=x1​+t1​∗(x2​−x1​)=y1​+t1​∗(y2​−y1​)​ { x = x 3 + t 2 ∗ ( x 4 − x 3 ) y = y 3 + t 2 ∗ ( y 4 − y 3 ) \left\{ \begin{aligned} x & = x_3+t_2*(x_4-x_3) \\ y & = y_3+t_2*(y_4-y_3) \\ \end{aligned} \right. {xy​=x3​+t2​∗(x4​−x3​)=y3​+t2​∗(y4​−y3​)​

如果求交点，则直接令其联立，求解出 t 1 , t 2 t_1,t_2 t1​,t2​，解得： t 1 = ( 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 ) t 1 ∈ [ 0 , 1 ] 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] t1​=(x2​−x1​)(y4​−y3​)−(x4​−x3​)(y2​−y1​)(x3​−x1​)(y4​−y3​)−(y3​−y1​)(x4​−x3​)​t1​∈[0,1] t 2 = ( 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 ) t 2 ∈ [ 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] t2​=(x4​−x3​)(y2​−y1​)−(x2​−x1​)(y4​−y3​)(x1​−x3​)(y2​−y1​)+(y3​−y1​)(x2​−x1​)​t2​∈[0,1] 假如最后求出来的 t 1 , t 2 t_1,t_2 t1​,t2​在范围内的话，那交点为： { x i n t e r = x 1 + t 1 ∗ ( x 2 − x 1 ) y i n t e r = y 1 + t 1 ∗ ( y 2 − y 1 ) \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. {xinter​yinter​​=x1​+t1​∗(x2​−x1​)=y1​+t1​∗(y2​−y1​)​

下面讨论平行的情况：

( x 3 , y 3 ) (x_3,y_3) (x3​,y3​)是否在 ( x 1 , y 1 ) ， ( x 2 , y 2 ) (x_1,y_1)，(x_2,y_2) (x1​,y1​)，(x2​,y2​)的直线上 y k − y 1 x k − x 1 = y 2 − y 1 x 2 − x 1 \frac{y_k-y_1}{x_k-x_1} = \frac{y_2-y_1}{x_2-x_1} xk​−x1​yk​−y1​​=x2​−x1​y2​−y1​​ 为了避免出现斜率为0的情况，使用乘法。 ( y k − y 1 ) ∗ ( x 2 − x 1 ) = ( y 2 − y 1 ) ∗ ( x k − x 1 ) (y_k-y_1)*(x_2-x_1)=(y_2-y_1)*(x_k-x_1) (yk​−y1​)∗(x2​−x1​)=(y2​−y1​)∗(xk​−x1​)

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