点が三角形の内側にあるかどうかを判定する方法（面積比較アルゴリズム）

はじめに

三角形の3つの頂点と、判定対象となる点Pが与えられたとき、その点Pが三角形の内側に存在するかどうかを判定する問題について解説します。

この問題は「面積比較法」と呼ばれる手法で効率よく解くことができます。三角形の頂点をA、B、Cとするとき、次の等式が成り立てば、点Pは三角形の内部にあると判断できます。

ΔABC ＝ ΔABP ＋ ΔPBC ＋ ΔAPC

つまり、元の三角形ABCの面積が、点Pを共有する3つの小さな三角形（ABP・PBC・APC）の面積の合計と一致すれば、点Pは三角形の中にあるということです。逆に点Pが外側にある場合は、これらの面積の合計が元の三角形の面積よりも大きくなります。

入力と出力

入力：
三角形の頂点 {(0, 0), (20, 0), (10, 30)} と 判定する点 p (10, 15)

出力：
点は三角形の内側にあります。

アルゴリズム

isInside(p1, p2, p3, p)

入力： 三角形の3つの頂点、判定する点p

出力： 点pが三角形の内側にある場合はtrue

Begin
    area := triangle(p1, p2, p3) の面積
    area1 := triangle(p, p2, p3) の面積
    area2 := triangle(p1, p, p3) の面積
    area3 := triangle(p1, p2, p) の面積
    if area = (area1 + area2 + area3), then
        return true
    else return false
End

C++による実装例

三角形の面積は、各頂点の座標から直接計算できる「靴ひも公式（Shoelace formula）」を利用して求めます。

#include <iostream>
#include <cmath>
using namespace std;

struct Point {
    int x, y;
};

float triangleArea(Point p1, Point p2, Point p3) {  // p1, p2, p3で構成される三角形の面積を求める
    return abs((p1.x*(p2.y-p3.y) + p2.x*(p3.y-p1.y) + p3.x*(p1.y-p2.y))/2.0);
}

bool isInside(Point p1, Point p2, Point p3, Point p) {  // pが内側かどうかを判定
    float area  = triangleArea(p1, p2, p3);  // 三角形ABCの面積
    float area1 = triangleArea(p, p2, p3);  // 三角形PBCの面積
    float area2 = triangleArea(p1, p, p3);  // 三角形APCの面積
    float area3 = triangleArea(p1, p2, p);  // 三角形ABPの面積

    return (area == area1 + area2 + area3);  // 3つの三角形が元の三角形全体を構成している場合
}

int main() {
    Point p1={0, 0}, p2={20, 0}, p3={10, 30};
    Point p = {10, 15};
    if (isInside(p1, p2, p3, p))
        cout << "Point is inside the triangle.";
    else
        cout << "Point is not inside the triangle";
}

実行結果

Point is inside the triangle.

補足：浮動小数点誤差への注意

実際の開発では、浮動小数点数の丸め誤差により、厳密な等号比較（==）が意図どおりに機能しないことがあります。そのような場合は、微小な許容誤差（イプシロン）を用いて比較するのが安全です。例えば、fabs(area - (area1 + area2 + area3)) < 1e-9 のように判定することで、誤差の影響を回避できます。