1. 概要

このチュートリアルでは、円と線分または線分との衝突を検出する方法について説明します。

まず、問題を定義し、例を挙げて説明します。 次に、この問題を解決するための2つのアプローチを紹介します。 最初のアプローチは、線と円の間の衝突を検出することであり、2番目のアプローチは、線分と円の間の衝突を検出することです。

2. 問題の定義

ここに、中心と半径を持つ円があります。 また、2つの点で表される線、、があります。 次に、円と線が任意の点で衝突するかどうかを確認します。

これをよりよく理解するために、例を見てみましょう。

図Aでは、指定された線はどの点でも円と交差していません。 したがって、答えは(円と線が衝突しない)です。

対照的に、図Bでは、指定された線は2つの点で指定された円と交差しています。 したがって、答えは(円と線が衝突する)です。

3. 線と円の交点

3.1. 数学的アイデア

このアプローチの主なアイデアは、円の原点と、これも線上にある円の原点に最も近い点との間の最小距離を取得することです。 その距離が円の半径以下の場合、線の一部が円の内側にあるか、円に接触しているため、線は円と衝突します。 そうでなければ、そうではありません。

最初に、指定された線上にある円の原点に最も近い点は、指定された線への円の原点の投影です。 希望する距離は三角形の高さとして想像できます。 次の図を見てみましょう。

ご覧のとおり、円の原点と、2つの点で表される特定の線との間の最小距離、およびは、三角形の高さに等しくなります。 さらに、この三角形の高さを取得するには、三角形の面積を計算するという利点があります。 (三角形の面積が等しいことを思い出してください。)

外積を使用して、頂点の座標から三角形の面積を取得することもできます。 (点で表される三角形の面積は)に等しいことを思い出してください。

これらの2つの方法を使用して三角形の面積を計算することにより、を取得できます。これは、円の原点から、指定された線上にある最も近い点までの最小距離を表します。

最後に、計算された高さが円の半径以下の場合、円は指定された線と衝突します。 そうでなければ、そうではありません。

3.2. トライアングルエリア

次に、外積を使用して三角形の面積を取得するアルゴリズムを見てみましょう。

最初に、3つの点で表される三角形の面積を返す関数を定義します。 さらに、この関数には、三角形の頂点の座標を表す3つのパラメーター、、、およびがあります。

まず、ベクトルの終点から始点の座標を引くことにより、2つのベクトルとを取得します。 次に、2つの外積式のいずれかを使用して、これら2つのベクトルを乗算します。

最後に、三角形の面積は、外積の絶対値を2で割った値に等しくなります。

3.3. アルゴリズム

次に、アルゴリズムの実装を見ていきます。

最初に、指定された円が指定された線と衝突するかどうかを返す関数を定義します。 さらに、この関数には、(円の半径)、(円の原点)、および(指定された線上にある任意の2つの点)の4つのパラメーターがあります。

最初に、を宣言します。これは、指定された円の原点と、指定された線上にあるそれに最も近い点との間の最小距離を表します。 これは三角形の高さに等しくなり、式を使用して計算できます。ここで、は点との間のユークリッド距離です。

最後に、最小距離が円の半径以下の場合、円は指定された線と衝突します。 したがって、trueを返します。 それ以外の場合はそうではなく、falseを返します。

3.4. 複雑さ

このアルゴリズムの時間計算量はです。これは、一定数の算術演算を実行しているためです。

4. 線分と円の交点

4.1. 数学的アイデア

このアプローチでは、前のアプローチと同じアイデアを使用します。 ただし、線分全体が指定された円の内側にないことも確認する必要があります。 したがって、指定された線分上にある円の原点から最も遠い点を取得し、それが指定された円の外側にあるかどうかを確認します。

与えられた線分上にある円の原点に最も近い点は、線分を持つ線の円の原点の投影と必ずしも等しくありません。 これは、原点の投影が線分の境界から外れている可能性があるためです。 この状況では、目的の最も近いポイントを取得するための2つのオプションがあります。

  1. 内積を使用して、円の原点の投影が指定された線分にあるかどうかを確認できます。 2つのベクトル間の内積の特徴の1つは、指定されたベクトル間の角度が度未満の場合にゼロより大きい結果を提供することです。 したがって、ベクトルとの間の内積がゼロよりも重要であり、ベクトルとの間の内積がゼロよりも重要である場合、円の原点投影が指定された線分上にあることを意味します。 その結果、前のアプローチと同様に最小距離が得られます。
  2. 円の原点の投影が指定された線分上にない場合は、目的の最も近い点が線分の端点の1つであることを意味します。 この場合、との間の最小値を取ることで最小距離を取得できます。ここで、関数は2点間のユークリッド距離を返します。 (点間のユークリッド距離はに等しいことを思い出してください。)

次に、円の原点と線分の間の最大距離は、円の原点と、指定された線分の端点の1つである円の原点までの最も遠い点との間の距離に等しくなります。 との間の最大値を取ることにより、最大距離を取得できます。

最後に、最小距離が円の半径以下で、最大距離が円の半径以上の場合、指定された円と指定された線分は衝突します。 そうでなければ、彼らはしません。

4.2. アルゴリズム

次に、アルゴリズムの実装を見てみましょう。

最初に、指定された円が指定された線分と衝突するかどうかを返す関数を定義します。 さらに、この関数には、(指定された円の半径)、(指定された円の原点)、および(指定された線分の端点)の4つのパラメーターがあります。

最初に、を宣言します。これは、指定された円の原点と、指定された線分上にあるそれに最も近い点との間の最小距離を表します。 円の原点の投影がセグメント上にある場合、これは三角形の高さに等しくなります。 それ以外の場合は、原点と端点の1つとの間の最小ユークリッド距離、またはに等しくなります。

次に、原点と端点の1つとの間の最大ユークリッド距離に等しい、または。

最後に、が、以下で、が以上の場合、指定された円と指定された線分は衝突し、trueを返します。 それ以外の場合はそうではなく、falseを返します。

4.3. 複雑さ

このアルゴリズムの時間計算量はです。 これは、一定数の算術演算を実行しているためです。

5. 結論

この記事では、円と線分または線分との衝突を検出する方法を学びました。

まず、問題を説明する例を示しました。 次に、それを解決するための2つのアプローチを検討しました。 最初のアプローチは線と円の間で、2番目のアプローチは線分と円の間でした。

最後に、実装について説明し、各アルゴリズムの時間計算量について説明しました。