如何计算线段和圆的交点

一个程序里用到了计算线段和圆相交情况的算法，在这里记下来备忘

设线段的两个端点分别是 $P_{1} (x_{1}, y_{1})$ 和 $P_{2} (x_{2}, y_{2})$ ，圆的圆心在 $P_{3} (x_{3}, y_{3})$ ，半径为 $r$ ，那么如果有交点 $P (x, y)$ 的话

\vec{P} = \vec{P_{1}} + u (\vec{P_{2}} - \vec{P_{1}})

其中， $u$ 在0到1之间，转换成各个坐标

{\begin{cases} x & = x_{1} + u (x_{2} - x_{1}) \\ y & = y_{1} + u (y_{2} - y_{1}) \end{cases}

由于P也在圆上，所以

(x - x_{3})^{2} + (y - y_{3})^{2} = r^{2}

联立上面的公式，可以得到

A u^{2} + B u + C = 0

其中

{\begin{cases} A = & (x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2} \\ B = & 2 ((x_{2} - x_{1}) (x_{1} - x_{3}) + (y_{2} - y_{1}) (y_{1} - y_{3})) \\ C = & x_{3}^{2} + y_{3}^{2} + x_{1}^{2} + y_{1}^{2} - 2 (x_{3} x_{1} + y_{3} y_{1}) - r^{2} \end{cases}

解一元二次方程，可以得到

u = \frac{- B \pm \sqrt{B^{2} - 4 A C}}{2 A}

根据 $B 2 - 4 A C$ 的结果，可以判断线段所在直线和圆的相交情况

针对 $P_{1}$ 和 $P_{2}$ 之间的线段，根据计算出的 $u$ 值，有5种结果