点が2D三角形に含まれるか含まれないかの判定

icon 項目のみ表示/展開表示の切り替え

概要

点が2D三角形に含まれるか含まれないかの判定
ベクトルによる2D三角形の向きの判定を応用すると簡単に判定できます。
下図を例に説明します。

各辺をベクトルとして点に対するベクトルが右が左かを判定します。
この場合のベクトルの原点は、点が三角形に含まれる場合、点のベクトルが全部右側または左側になるように決めるのがみそです。そのような原点に対するベクトルの例を下図に示します。

この場合、見たとおり、全部辺のベクトルに対して点のベクトルは右側になっています。
したがって、点は三角形に含まれることになります。
場合によっては、全部左になる場合もありますが、これも点が三角形に含まれることを示します。
もし、辺と点の外積が0の辺がある場合は、辺のベクトルと点のベクトルが重なっていることを示しているので、三角形が異常ということになります。いずれかの辺のベクトルの符号が異なる場合は、点が三角形に含まれないということです。
では実際の計算過程を示します。
各点 x y
p1 2548.96 2105.31
p2 3092.93 1325.82
p3 1604.4 1641.83
v2ベクトルとv4ベクトルの外積
p1.x p1.y p3.x p3.y v2.x v2.y
v2ベクトル 2548.96 2105.31 1604.4 1641.83 944.56 463.48

po.x po.y p3.x p3.y v4.x v4.y
v4ベクトル 2384.52 1708.61 1604.4 1641.83 780.12 66.78
外積 944.56 * 66.78 - 463.48 * 780.12 = -298492.3008
v3ベクトルとv5ベクトルの外積
p2.x p2.y p1.x p1.y v3.x v3.y
v3ベクトル 3092.93 1325.82 2548.96 2105.31 543.97 -779.49

po.x po.y p1.x p1.y v5.x v5.y
v5ベクトル 2384.52 1708.61 2548.96 2105.31 -164.44 -396.7
外積 543.97 * -396.7 - -779.49 * -164.44 = -343972.2346
v1ベクトルとv6ベクトルの外積
p3.x p3.y p2.x p2.y v1.x v1.y
v1ベクトル 1604.4 1641.83 3092.93 1325.82 -1488.53 316.01

po.x po.y p2.x p2.y v5.x v5.y
v6ベクトル 2384.52 1708.61 3092.93 1325.82 -708.41 382.79
外積 -1488.53 * 382.79 - 316.01 * -708.41 = -345929.7546
3つの外積の値ががすべて同じ符号となるため、点は三角形内に含む。
PDF版