©2024 Thoth Children All rights reserved.

点が三角形の内側か判定したい

ー 概要 ー

点が三角形の内側にあるかどうかを判定したい場合に用いる技術について紹介します.点が三角形の内側か外側かは様々な幾何的なアルゴリズムにおいて使用されます.二次元でも三次元でも同様に判定することができます.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
条件
  • 二次元または3次元座標上の点と三角形をなす3つの点
効果
  • 点が三角形の内側に含まれているかどうかを判定

解 説

点が三角形の内側か判定したいケースはときどきあります.凸包アルゴリズムにおいて三角形に含まれているかどうかやゲームにおいて三角形の中に入ったかどうかの判定など様々な場面で使用します. ここでは点が三角形の中に含まれるかどうかを判定する方法についてまとめてます. 二次元座標の場合も三次元座標の場合も同様にできるので、ここでは二次元座標の場合の紹介になります.
点が三角形の内側か判定したい
二つの考え方があります. ・ベクトルAP=s*ベクトルAB+t*ベクトルACとしてときに 0＜s＜1かつ0＜t＜1かつ0＜1-s-t＜1を満たす ・３つの外積の値の正負が一致するすること 一つ目はベクトルで係数の性質から導かれる解法で 二つ目はベクトルの外積の正負を使った解法です. どちらを用いても大きくは変わりません.お好きな方で選択してください.
点が三角形の内部か判定するアルゴリズム
JSfiddleにてサンプルコードを書かれている方がいらっしゃるのでリンクを貼っておきます.
外部リンク
三角形の中の判定のサンプルプログラム

1.ベクトルの係数による解法

Pを判定したい点の座標として、三角形ABCの内部にあるかを判定します. ベクトルAPをs倍のベクトルABとt倍のベクトルACで表現するとき、 0＜s＜1, 0＜t＜1,0＜1-s-t＜1を満たせば三角形の内部にあることがわかります.
ベクトル係数による判定方法
$$\overrightarrow{ AP } = s \overrightarrow{ AB }+t\overrightarrow{ AC } $$
ある点PをベクトルABとベクトルACの合成で表したもの
C++
?
1
2
3
4
5
6
7
8
9
10
11
//(p0x, p0y),(p1x, p1y),(p2x, p2y)の三角形
//(px, py)が判定したい点
double Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);
double s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
double t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);
 
if((0 < s < 1) && (0 < t < 1)&&(0<1-s-t<1)){
    return 1; //Inside Triangle
}else{
    return 0;
}
ベクトル係数の判定. ここではAreaによる除算をしてしまっているが、0＜s＜Areaのようにすることで除算をしないで済むようにすることが可能. 除算は遅いため回避すべき.

2.外積による解法

外積の性質を用いても求めることができます. これは外積を行ったときの正負が三点で一致する必要があります.
外積による判定方法
C++
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
 
bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    bool b1, b2, b3;
 
    b1 = sign(pt, v1, v2) < 0.0f;
    b2 = sign(pt, v2, v3) < 0.0f;
    b3 = sign(pt, v3, v1) < 0.0f;
 
    return ((b1 == b2) && (b2 == b3));
}
外積の正負による判定 signにて正負を計算. (https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle より引用)
この章を学んで新たに学べる
Comments

Reasons
>>隠す