点が 2D 三角形の内側にあるかどうかを判断する最も簡単なアルゴリズムは何ですか?
ベストアンサー1
一般的に、最も単純な(そして非常に最適な)アルゴリズムは、エッジによって作成された半平面のどちら側に点があるかをチェックすることです。
ここに質の高い情報がありますGameDevのトピックパフォーマンスの問題も含まれます。
始めるためのコードは次のとおりです。
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)
{
float d1, d2, d3;
bool has_neg, has_pos;
d1 = sign(pt, v1, v2);
d2 = sign(pt, v2, v3);
d3 = sign(pt, v3, v1);
has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
return !(has_neg && has_pos);
}