中身を理解しなくても使える円と線分の判定に関する資料がなかったので備忘録として作成しました。
数式が嫌いな方は設定とアルゴリズムだけご覧ください。
設定
円
- 中心 $O(0, 0)$
- 円の中心が原点にない場合は、原点に来るように座標変換し、最後に逆変換すれば良い
- 半径 $r$
線分
- 始点$A(x_a, y_a)$
- 終点$B(x_b, y_b)$
導出
以下一文字のベクトル($\vec{A}$)は位置ベクトルを表す.
円と線分の交点$P$は、$0<t<1$を用いて、以下の2式を満たすはずである.
\vec{P} = \vec{A} + t\vec{AB} =(1-t)\vec{A}+t\vec{B} \\\
|\vec{OP}|=|\vec{P} - \vec{O}|=r
連立して整理すると、
((1-t)x_a+tx_b)^2+((1-t)y_a+ty_b)^2=r^2
tについて整理すると、
at^2+bt+c=0 \\\
a = x_a^2+x_b^2+y_a^2+y_b^2-2x_ax_b-2y_ay_b \\\
b = 2x_ax_b+2y_ay_b-2x_a^2-2y_a^2 \\\
c = x_a^2+y_a^2-r^2
ここで、
D = b^2-4ac
と定義すると、判別式から$D<0$の場合交差しない
$D>0$の場合、直線$AB$は円と交差してそのとき$t$は、
t=\frac{-b±\sqrt{b^2-4ac}}{2a}
となり、直線$AB$と円の交点$P$は、以下で求められる
\vec{P} = \vec{A}+t\vec{AB}
ここで、点$P$が線分$AB$上に存在するための条件は以下の式を満たすことである.
0 \le t \le 1
判定アルゴリズムまとめ
$1.$ $a, b, c$を定義する
a = x_a^2+x_b^2+y_a^2+y_b^2-2x_ax_b-2y_ay_b \\\
b = 2x_ax_b+2y_ay_b-2x_a^2-2y_a^2 \\\
c = x_a^2+y_a^2-r^2
$2.$ $D=b^2-4ac$を定義し、$D \lt 0$なら交差しない
$3.$ $D \ge 0$の場合、$t$を計算する
t=\frac{-b±\sqrt{b^2-4ac}}{2a}
$4.$ 2つの$t$のうち、条件$0 \le t \le 1$を満たすものについて点Pを以下のように計算する
\vec{P} = \vec{A}+t\vec{AB}
$5.$ 点Pは求める交点である.
ここで、条件を満たすtが存在しない場合線分$AB$は円と交差しない.
逆に、$t$が2種類存在する場合、小さい方がより点Aに近い交点である.