[Algorithm] 円と線分の交差判定 « MISCELLANEUOS DATA STORAGE

[Algorithm] 円と線分の交差判定

円と有限線分の交差判定のアルゴリズムです。
実装はこちらのサイトを参考にしました。

線分ＡＢの始点から終点に向かうベクトルを
$\vec{v}$

、線分の短点から円の中心に向かうベクトルをそれぞれ
$\vec{c} 、 \vec{b}$

　とします。　円の半径を r とすると、円と直線の交差する条件は以下のようになります。

(1) \vec{v} • \vec{c} < 0 かつ |c| < 0 ならば交差

(2) \vec{v} • \vec{c} ≧ 0 のとき：

(2-1) \vec{v} • \vec{c} > {\vec{v}}^{2} かつ |b| < ｒ ならば交差

(2-2) \vec{v} • \vec{c} ≦ 0 かつ {\vec{c}}^{2} - \frac{{(\vec{v} • \vec{c})}^{2}}{{\vec{v}}^{2}} < r^{2} のとき：

(2-2-1) |\vec{c}| > r または |\vec{b}| > r ならば交差

最後の (2-2-1) は、線分の両端が円の内部にある条件です。
前述のサイトには、この条件が含まれていなかったため追記しました。

※ この記事には MathML を使用しています。 Internet Explorer を使用している方は、MathPlayer、Chrome では MathML2CSS などをインストールする必要があるそうです。

この投稿は 2011 年 6 月 26 日日曜日 11:41 AM にアルゴリズム, 雑記カテゴリーに公開されました。この投稿へのコメントは RSS 2.0 フィードで購読することができます。コメントを残すか、ご自分のサイトからトラックバックすることができます。