49 lines
1.7 KiB
Markdown
49 lines
1.7 KiB
Markdown
---
|
|
title: "如何计算线段和圆的交点"
|
|
tags: 数学 算法
|
|
---
|
|
# 如何计算线段和圆的交点
|
|
|
|
一个程序里用到了计算线段和圆相交情况的算法，在这里记下来备忘
|
|
|
|
|
|
|
|
设线段的两个端点分别是$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
|
|
$$
|
|
联立上面的公式，可以得到
|
|
$$
|
|
Au^2+Bu+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_3x_1+y_3y_1)-r^2 \end{cases}
|
|
$$
|
|
解一元二次方程，可以得到
|
|
$$
|
|
\displaystyle{u=\frac{-B\pm\sqrt{B^2-4AC}}{2A}}
|
|
$$
|
|
根据$B2-4AC$的结果，可以判断线段所在直线和圆的相交情况
|
|
* 如果小于0，表示没有交点
|
|
* 如果等于0，表示相切，只有一个交点
|
|
* 如果大于0，表示有两个交点
|
|
|
|
针对$P_1$和$P_2$之间的线段，根据计算出的$u$值，有5种结果
|
|
* 如果线段和圆没有交点，而且都在圆的外面的话，则$u$的两个解都是小于0或者大于1的
|
|
* 如果线段和圆没有交点，而且都在圆的里面的话，$u$的两个解符号相反，一个小于0，一个大于1
|
|
* 如果线段和圆只有一个交点，则$u$值中有一个是在0和1之间，另一个不是
|
|
* 如果线段和圆有两个交点，则$u$值得两个解都在0和1之间
|
|
* 如果线段和圆相切，则$u$值只有1个解，且在0和1之间
|