点の三角形内外判別法

提供: Akionux-wiki
Share/Save/Bookmark
移動: 案内検索

概要

2次元平面上である点が三角形の内部にあるか外部にあるかを判定する方法について述べる。

なお、3次元においては、点が三角形と同じ平面上に存在していることを要請すれば同様に判別可能である。

外積の計算

二つのベクトル

の外積は、

である。

外積の性質

Figure 1のような点とベクトルを考えよう。

Figure 1: 点とベクトル

この場合、次のような関係がある:

すなわち、平面上の任意の点に対して外積は、がベクトルの左側にある(例えば)とき正になり、右側にある(例えば)とき負になる。

これは、原点を同じくする2つのベクトルを基準として反時計回りになす角をとすると、の外積は

であることからわかる。

この外積の性質を利用して、任意の点がを通る直線のどちら側にあるかを判別することができるのである。

三角形の内外判定

外積の性質を応用すれば、三角形の内外判定ができる。

任意の点がFigure 2のような(3つの点を頂点とする三角形)の内か外かを判定するとしよう。

Figure 2: 三角形でできる領域と各領域の外積の符号

直線で平面を区切ると7つの領域に区切ることができる。

Figure 2には領域ごとに(の符号,の符号,の符号)を示した。

の内部においてのみ3つの外積の符号がすべて負になっている。

すなわち、点が次の3つの不等式を満たせば、の内側にある。

ただし、これは三角形の頂点を時計回りに回った場合で、半時計回りにすれば外積の符号は逆になる。

References