ポイントが2D三角形にあるかどうかを判断する方法
1. 概要
このチュートリアルでは、ポイントが2D三角形の内側にあるかどうかを検出する方法について説明します。
まず、問題を定義し、例を挙げて説明します。 次に、この問題を解決するための3つのアプローチを紹介します。 最初のアプローチでは、三角形の面積の式を使用します。 2つ目は、線分交差点を使用します。 最後に、最後のアプローチでは、外積を使用します。
2. 問題の定義
ここに、3つの点、、、で定義された三角形があります。 ポイントもあります。 次に、ポイントが三角形の内側にあるかどうかを確認します。
理解を深めるために、次の例を見てみましょう。
図Aでは、指定された点は三角形の外側にあります。 したがって、答えはです。
対照的に、図Bでは、指定された点は三角形の内側にあります。 したがって、答えはです。
3. トライアングルエリアアプローチ
3.1. 数学的アイデア
このアプローチの主なアイデアは、三角形の面積がサブ三角形、、、およびの面積の合計に等しいかどうかを確認することです。 次に、ポイントは三角形の内側にあります。 そうでなければ、それは外にあります。
最初に、3つの三角形、、、を作成します。 次の図を見てみましょう。
ご覧のとおり、3つのサブ三角形、、の面積の合計は、三角形の面積に等しくなります。 したがって、ポイントは指定された三角形の内側にあります。 外積を使用して、頂点の座標から三角形の面積を取得できます。
点で表される三角形の面積は次のとおりであることを思い出してください。
最後に、3つの三角形の合計、、、が指定された三角形の合計に等しい場合、それはポイントが指定された三角形の内側にあることを意味します。 そうでなければ、それは外にあります。
3.2. トライアングルエリア
次に、外積を使用して三角形の面積を取得するアルゴリズムを見てみましょう。
最初に、3つの点で表される三角形の面積を返す関数を定義します。 さらに、この関数には、三角形の頂点の座標を表す3つのパラメーター、、、およびがあります。
まず、ベクトルの終点から始点の座標を引くことにより、2つのベクトルとを取得します。 その後、2つの外積式のいずれかを使用して、これら2つのベクトルを乗算します。
最後に、三角形の面積は、外積の絶対値を2で割った値に等しくなります。
3.3. アルゴリズム
アルゴリズムの実装を確認しましょう。
最初に、指定された点が三角形の内側にあるかどうかを返す関数を定義します。 さらに、この関数には4つのパラメーターがあります。三角形の内側にあるかどうかを確認するポイント、、、および指定された三角形の頂点です。
まず、与えられた三角形の面積を表すを宣言します。 次に、を宣言します。これは、サブ三角形、、、およびの面積の合計を表します。 次に、前の各サブ三角形の面積を変数に追加します。
最後に、がに等しい場合、それはポイントが三角形の内側にあることを意味します。 したがって、trueを返します。 それ以外の場合は外部にあるため、falseを返します。
4. 線分交差点アプローチ
4.1. 数学的アイデア
このアプローチでは、与えられた点とから遠く離れたランダムな点によって定義される線分を描画します。 次に、与えられた三角形のセグメントとセグメントの間の交点の数を数えます。 交点の数が奇数の場合、それはポイントが三角形の内側にあることを意味します。 そうでなければ、それは外にあります。
理解を深めるために、次の図を見てみましょう。
図Aからわかるように、点は三角形の外側にあります。 から始まり、そこから遠く離れた線分を描画します。この線分は、三角形のセグメントと2点で交差します。したがって、交点の数が偶数であるため、点は三角形の外側にあります。 対照的に、図Bでは交点の数が奇数であるため、点は三角形の内側にあります。
結論として、交差点ごとに、その点の状態が変化していることが想像できます。 最初の交差点では、ポイントは三角形の外側から内側に移動します。 次に、2番目の交差点で、内側から外側に移動します。
このアプローチで直面する可能性がある唯一の弱点は、三角形の頂点の1つを通過するような方法でセグメントを描画する場合です。 したがって、ポイントが三角形の内側にある場合、2つの交点があります。つまり、外側にあるのに外側にないということです。
この問題を回避するために、三角形の頂点を通過する確率を下げるように、から遠く離れたランダムな点になるように点を選択します。
4.2. アルゴリズム
それでは、アルゴリズムの実装を見てみましょう。
最初に、前のアプローチと同じように関数を定義します。
まず、セグメントを宣言します。これは、点と、から遠く離れた無限遠点のランダムな点によって定義されます。 次に、セグメントと三角形セグメント間の交点の数を表すを宣言します。 次に、三角形の各セグメントについて、現在のセグメントとセグメントの間で関数isIntersectを呼び出します。 指定されたセグメントが交差すると、その関数が返されます。 それ以外の場合は、を返します。
最後に、変数は交点の数を格納します。 交点の数が奇数の場合、その点は三角形の内側にあるため、trueを返します。 それ以外の場合は外部にあるため、falseを返します。
5. オリエンテーションアプローチ
5.1. 数学的アイデア
このアプローチでは、ポイントが同じ側（内側）にあるかどうか、つまりポイントが三角形の内側にあるかどうかをすべての三角形セグメントでチェックします。 そうでなければ、それは外にあります。
最初に、各三角形のセグメントについて、テストされたセグメントの右または左にある場合のポイントの位置を確認します。 この方向は、外積を使用して取得できます。
リコールは、ベクトルがベクトルの左側にある場合よりも少なく、右側にある場合よりも大きくなります。
結局、ポイントがすべての三角形セグメントの左側にあるか、すべての三角形セグメントの右側にある場合、それはポイントが三角形の内側にあることを意味します。 そうでなければ、そうではありません。
5.2. オリエンテーション
アルゴリズムを見て、3つのポイントの方向を取得します。
最初に、左折するか右折するかに関係なく、指定されたポイントの方向を返す関数を定義します。 さらに、この関数には、指定された点の座標を表す3つのパラメーター、、、およびがあります。
まず、ベクトルの終点から始点の座標を引くことにより、2つのベクトルとを取得します。 次に、2つの外積式のいずれかを使用して、これら2つのベクトルを乗算します。
最後に、がより大きい場合は、左に曲がったことを意味します（ポイントはセグメントの左側にあります）。したがって、を返します。 それ以外の場合は、右折して戻ります。
5.3. アルゴリズム
アルゴリズムの実装を確認しましょう。
最初に、前のアプローチと同じように関数を定義します。
最初に、変数を宣言します。これは、すべての三角形セグメントに対応するポイントの方向の合計を格納します。
最後に、の絶対値がに等しい場合、それはポイントがすべてのセグメントで同じ側にあり、三角形の内側にあることを意味するため、trueを返します。 それ以外の場合は外部にあるため、falseを返します。
6. 結論
この記事では、ポイントが2D三角形の内側にあるかどうかを検出する方法を学びました。
まず、問題を説明する例を示しました。 次に、それを解決するための3つの異なるアプローチを検討しました。
最後に、実装について説明し、各アルゴリズムの時間計算量について説明しました。
