计算几何之两条线段的交点
计算几何之两条线段的交点
在计算几何中，判断两条线段是否相交以及求解它们的交点是一个常见的问题。本文将详细介绍如何通过向量和叉乘运算来精确计算二维空间中两条线段的交点，帮助读者深入理解这一算法的核心原理。
1. 概述
可以通过线段的跨立实验[1]判断两条线段是否相交，但是想要进一步求它们的交点还是比较麻烦。[2]给出的方法更加简单，其原理来自求三维空间两条线段的交点[3]。为了更好的理解，本文将详细介绍二维空间两条线段的交点求解过程。
2. 两条线段交点求解过程
给定两条线段(\overline{P_1 P_2})和(\overline{P_3 P_4})，端点表示为(P_1(x_1,y_1))、(P_2(x_2,y_2))、(P_3(x_3,y_3))和(P_4(x_4,y_4))，两条线段对应的向量表示为(\overrightarrow{P_1 P_2})和(\overrightarrow{P_3 P_4})。假设两条线段的交点为(P_0(x_0,y_0))，且(t=\frac{|\overline{P_1 P_0}|}{|\overline{P_1 P_2}|})、(s=\frac{|\overline{P_3 P_0}|}{|\overline{P_3 P_4}|})，那么(P_0)可以表示为：
[\begin{cases} P_0=P_1 + t * \overrightarrow{P_1 P_2} , 0\leq t \leq 1 \ P_0=P_3 + s * \overrightarrow{P_3 P_4} , 0\leq s \leq 1 \end{cases} ]
(t)和(s)在等于(0)或(1)时表示两条线段相交在端点，如果为其他值，表示两条线段不相交。将点坐标代入公式得：
[\begin{cases} x_1 + t * (x_2 - x_1) = x_3 + s * (x_4 - x_3) \ y_1 + t * (y_2 - y_1) = y_3 + s * (y_4 - y_3) \end{cases} ]
利用公式消元法求得(t)和(s)：
[\begin{aligned} t = \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) - (y_2 - y_1)(x_4 - x_3) } \ s = \frac{ (x_3 - x_1)(y_2 - y_1) - (y_3 - y_1)(x_2 - x_1) }{ (x_2 - x_1)(y_4 - y_3) - (y_2 - y_1)(x_4 - x_3)} \end{aligned} ]
(t)和(s)方程的分子和分母都是向量的叉乘：
[\begin{aligned} t = \frac{ \overrightarrow{P_3 P_1} * \overrightarrow{P_4 P_3} } { \overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} } \ s = \frac{ \overrightarrow{P_3 P_1} * \overrightarrow{P_2 P_1} }{ \overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} } \end{aligned} ]
如果(\overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} = 0)，表示两条线段平行，如果端点在另一条线段上，则该端点为交点，否则不是。如果(t)和(s)有一个没有落在区间([0,1])内，则两条线段不相交。那么交点(P_0)的坐标为：
[\begin{cases} x_0 = x_1 + t*(x_2 - x_1) \ y_0 = y_1 + t*(y_2 - y_1) \end{cases} ]
或
[\begin{cases} x_0 = x_3 + s*(x_4 - x_3) \ y_0 = y_3 + s*(y_4 - y_3) \end{cases} ]
至此，整个求解过程介绍完成，再去看[2]的代码就非常容易理解了。